Approximate graph edit distance computation by means of bipartite graph matching

By Kaspar Riesen, Horst Bunke. 2009

722 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Yizhou Sun
2. Ting-Li Chen
3. Dawn Song
4. Wei Wang
5. Haoyang Ding
6. Yunsheng Bai
7. Adam Gaier
8. Tingting Chen

In Computer Vision and Pattern Recognition

1. Yizhou Sun
2. Wei Wang
3. Haoyang Ding
4. Yunsheng Bai
5. Ting-Li Chen
6. Kaspar Riesen
7. Horst Bunke
8. Tingting Chen

Citations in the corpus

• Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, methodology): “We take the minimum distance computed by BEAM (Neuhaus et al., 2006), HUNGARIAN (Riesen & Bunke, 2009), and VJ (Fankhauser et al., 2011).”
• Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity (2019, methodology): “This should not be a surprise, because only UGRAPHEMB utilizes the ground-truth GED results collectively determined by BEAM [Neuhaus et al., 2006], HUNGARIAN [Riesen and Bunke, 2009], and VJ [Fankhauser et al., 2011].”
• On Valid Optimal Assignment Kernels and Applications to Graph Classification (2016, background): “, in general graph matching [9, 17] as well as in kernel-based classification [8, 18, 1].”
• Hierarchical graph embedding in vector space by graph pyramid (2017, methodology): “Here, edit distance computation is run by the suboptimal 170 method proposed in [33] which has the polynomial complexity O(n3) in the number of nodes in two graphs.”
• Group Role Assignment via a Kuhn–Munkres Algorithm-Based Solution (2012, methodology): “Fortunately, the well-known K-M algorithm for the GAP has been designed with the complexity of O(m(3))[7], [13], [17] and has been applied widely in industries [20], and its Java code is also available [4].”
• Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection (2017, background): “Last but not least, the search accuracy of this approach is ultimately bounded by the quality of bipartite graph matching [35].”
• An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems (2015, methodology): “This is performed by an assignment algorithm (Riesen and Bunke, 2009) whose complexity is O ( max { n 1 , n 2 } 3 ) .”
• Discriminative prototype selection methods for graph embedding (2013, background): “This section briefly conveys the key terminology and some concepts used in this paper.”
• SimGNN: A Neural Network Approach to Fast Graph Similarity Computation (2018, methodology): “GED has been widely used inmany applications, such as graph similarity search [31, 51, 55, 56, 58], graph classification [40, 41], handwriting recognition [12], image indexing [52], etc.”
• Scalable Graph-based Bug Search for Firmware Images (2016, neutral): “Theoretically, graph matching is an NP-complete problem, but many techniques have been proposed to optimize the process for an approximate matching result [14,49].”
• Data-efficient neuroevolution with kernel-based surrogate models (2018, methodology): “Though approximate measures of graph edit distance have been developed [15, 21], even these are too slow for use as part of every prediction in an optimization algorithm.”