A survey of graph edit distance

By Xinbo Gao, Bing Xiao, Dacheng Tao, Xuelong Li. 2010

817 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

In Computer Vision and Pattern Recognition

Citations in the corpus

Neural Architecture Search with Bayesian Optimisation and Optimal Transport (2018, background): “The above work either define the distance/kernel between vertices or assume the same vertex (layer) set [9, 20, 26, 35, 46], none of which apply in our setting.”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “Edit distance has attracted most of the interest in the context of metric learning for structured data because (i) it is defined for a variety of objects: sequences (Levenshtein, 1966), trees (Bille, 2005) and graphs (Gao et al., 2010), (ii) it is naturally amenable to learning due to its parameteri”
Graph R-CNN for Scene Graph Generation (2018, background): “We note that graph similarity based on minimum graph edit distance has been well-studied in graph theory [5]; however, computing exact solution is NP-complete and approximation APX-hard [20].”
AfterQC: automatic filtering, trimming, error removing and quality control for fastq data (2017, methodology): “Based on edit distance [11] optimisation, we developed a method to check how each pair of reads overlap, for data from pair-end sequencing.”
Graph Matching Networks for Learning the Similarity of Graph Structured Objects (2019, background): “Graph edit distance is naturally a measure of similarity between graphs and has many applications in graph similarity search (Dijkman et al., 2009; Zeng et al., 2009; Gao et al., 2010).”
Similarity Search in Graph Databases: A Multi-Layered Indexing Approach (2017, background): “The intuitive graph edit operations can precisely capture any fine-grained difference concerning both graph structures and contents [13]; Second, GED defines a theoretical framework for graph proximity modeling and quantification, within which many graph similarity measures, such as maximum common s”
UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats (2020, methodology): “In the realm of malware classiﬁcation and intrusion detection, Classy [72] clusters streams of call graphs to facilitate malware analysis based on graph edit distance (GED) [41] of pairs of graphs using a modiﬁed version of simulated annealing.”
Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search (2020, background): “Previous work considers the neural network architectures as the graphs, then deﬁning various distances and kernels on graphs (Messmer & Bunke, 1998; Wallis et al., 2001; Kondor & Lafferty, 2002; Smola & Kondor, 2003; Gao et al., 2010; Ru et al., 2021).”
The time-evolving epileptic brain network: concepts, definitions, accomplishments, perspectives (2024, background): “…however, continues to be a dif ﬁ cult task (Bronstein et al., 2006; Andrade et al., 2008; Muskulus et al., 2009; Dimitriadis et al., 2010; Gao et al., 2010; van Wijk et al., 2010; Mémoli, 2011; De Domenico and Biamonte, 2016; Schieber et al., 2017; Fraiman and Fraiman, 2018; Carpi et…”