A graph distance metric based on the maximal common subgraph

By Horst Bunke, K. Shearer. 1998

How researchers see this paper

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

Citations in the corpus

Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, methodology): “Metrics such as Graph Edit Distance (GED) Bunke (1983) and Maximum Common Subgraph (MCS) Bunke & Shearer (1998) have been widely adopted in graph database search Yan et al. (2005); Liang & Zhao (2017), are well-defined and general to any domain.”
Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity (2009, background): “The distance between genotypes is often hard to compute because typical distances between two graphs, thereby two neural networks, are NPcomplete [32].”
Scalable Graph-based Bug Search for Firmware Images (2016, methodology): “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].”
Similarity Search in Graph Databases: A Multi-Layered Indexing Approach (2017, background): “There has been a rich literature in the modeling and computation of similarity between graphs, such as graph edit distances [15], [21], [32], maximum common subgraphs [23], [9], edge/feature misses [31], [38], [33], [30], graph alignment [25], and graph kernels [19].”
Spectral embedding of graphs (2003, background): “Recently, Bunke [10,11] has shown that the graph edit distance and the size of the maximum common subgraph are related under certain restrictions on the edge and node edit costs.”
Similarity of business process models: Metrics and evaluation (2011, methodology): “then assign a similarity score to two EPCs by computing their graph-edit distance [2].”
Substructure similarity search in graph databases (2005, methodology): “[3] H. Bunke and K. Shearer.”
Structured Lexical Similarity via Convolution Kernels on Dependency Trees (2011, background): “A semantic similarity can be deﬁned at structural level over a graph, e.g. (Freeman, 1977; Bunke and Shearer, 1998; Brandes, 2001; Zhao et al., 2009), as well as combining structural and lexical similarity over semantic networks, e.g. (Cowie et al., 1992; Wu and Palmer, 1994; Resnik, 1995; Jiang…”
A survey of frequent subgraph mining algorithms (2012, background): “Subgraph isomorphism detection techniques can be roughly categorized as being either: exact matching (Ullmann 1976; Schmidt& Druﬀel 1976; McKay 1981; Cordella et al. 1998; Cordella et al. 2001) or error tolerant matching (Shapiro & Haralick 1981; Bunke & Allerman 1983; Christmas et al. 1995; Messmer”
Comparing Stars: On Approximating Graph Edit Distance (2009, background): “A number of graph similarity measures therefore have been proposed [20, 8, 10, 24].”
Decoding brain states from fMRI connectivity graphs (2011, background): “They are typically robust (error-tolerant) with respect to changes in graph structure (such as a different number of vertices) (Bunke et al., 1998), because in many ﬁ elds graphs are computed from real-life data and their topology can ﬂ uctuate from instance to instance.”
Recognition of shapes by editing their shock graphs (2004, unknown): “Hence, graph-matching approaches based on topology without using geometrical information [8], [50] are not applicable for shock graph matching. on the shock graph in the discrete domain.”
Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition (2001, background): “The formal basis of graph edit distance has recently been extended by Bunke and his coworkers [ 9 ], [6] who have shown, among other things, that the edit distance is related to the size of the maximum common subgraph.”
discovRE: Efficient Cross-Architecture Identification of Bugs in Binary Code (2016, background): “9) Comparison to VP Tree: Bunke showed that the maximum common subgraph distance measure dmcs on the basis of the MCS is a metric [18].”