Speeding Up Graph Edit Distance Computation through Fast Bipartite Matching

136 citations recorded by the source corpus.

How researchers see this paper

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

Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, methodology): “, 2006), HUNGARIAN (Riesen & Bunke, 2009), and VJ (Fankhauser et al., 2011): They are approximate GED computation algorithms with sub-exponential time complexity, quadratic time complexity, and quadratic time complexity, respectively.”
Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity (2019, methodology): “ one. 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 & Bunke, 2009), and VJ (Fankhauser et al., 2011). UGRAPHEMB even outperforms HED (Fischer et al., 2015), a state-of-the-art ”
SimGNN: A Neural Network Approach to Fast Graph Similarity Computation (2018, methodology): “” To properly handle the IMDB dataset, we take the smallest distance computed by three well-known approximate algorithms, Beam [33], Hungarian [28, 41], and VJ [11, 22].”
Similarity Search in Graph Databases: A Multi-Layered Indexing Approach (2017, methodology): “The GED computation is NP-hard [14], and the state-of-the-art GED method is based on an A* search strategy with bipartite matching heuristics [12].”