Incremental Multi-graph Matching via Diversity and Randomness based Graph Clustering
Multi-graph matching refers to finding correspondences across graphs, which are traditionally solved by matching all the graphs in a single batch. However in real-world applications, graphs are often collected incrementally, rather than once for all. In this paper, we present an incremental multi-graph matching approach, which deals with the arriving graph utilizing the previous matching results under the global consistency constraint. When a new graph arrives, rather than re-optimizing over all graphs, we propose to partition graphs into subsets with certain topological structure and conduct optimization within each subset. The partitioning procedure is guided by the diversity within partitions and randomness over iterations, and we present an interpretation showing why these two factors are essential. The final matching results are calculated over all subsets via an intersection graph. Extensive experimental results on synthetic and real image datasets show that our algorithm notably improves the efficiency without sacrificing the accuracy.
Code (0)
등록된 구현이 없습니다.
Tasks
AllClusteringDiversityGraph ClusteringGraph MatchingSimilar Papers 제목 키워드 기반
Layered Neighborhood Expansion for Incremental Multiple Graph Matching
Graph matching has been a fundamental problem in computer vision and pattern recognition, for its practical flexibility as well as NP hardness challenge. Though the matching between two graphs and among multiple graphs h…
Graph MatchingCluster-and-Conquer: When Randomness Meets Graph Locality
K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, wh…
ClusteringDBkWik++ -- Multi Source Matching of Knowledge Graphs
Large knowledge graphs like DBpedia and YAGO are always based on the same source, i.e., Wikipedia. But there are more wikis that contain information about long-tail entities such as wiki hosting platforms like Fandom. In…
Knowledge GraphsThe ontogeny of discourse structure mimics the development of literature
Discourse varies with age, education, psychiatric state and historical epoch, but the ontogenetic and cultural dynamics of discourse structure remain to be quantitatively characterized. To this end we investigated word g…
DiversityStochastic Iterative Graph Matching
Recent works leveraging Graph Neural Networks to approach graph matching tasks have shown promising results. Recent progress in learning discrete distributions poses new opportunities for learning graph matching models. …
Graph MatchingStochastic Optimization