Comparing Stars: On Approximating Graph Edit Distance
By Zhiping Zeng, Anthony K. H. Tung, Jianyong Wang, Jianhua Feng, Lizhu Zhou. 2009
463 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing
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
- Mohit Bansal
- Pushmeet Kohli
- Xia Hu
- Jason Baldridge
- Jianfeng Gao
- Quoc V. Le
- Percy Liang
- Luke S. Zettlemoyer
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Cordelia Schmid
- Dacheng Tao
- Trevor Darrell
- Ming-Hsuan Yang
- Jitendra Malik
- Andrew Zisserman
- Xiaogang Wang
In Signal Processing
- Ashish Vaswani
- Jason Baldridge
- Gabriel Ilharco
- Pushmeet Kohli
- Yongjiang Liang
- Oriol Vinyals
- Chenjie Gu
- Peixiang Zhao
Citations in the corpus
- Efficient Neural Architecture Search with Network Morphism (2018, background): “Calculating the edit-distance of two neural networks can be mapped to calculating the edit-distance of two graphs, which is an NP-hard problem [31].”
- An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems (2015, methodology): “Many fast heuristic methods have been proposed in the literature such as (Christmas et al., 1995); (Zeng et al., 2009); (Fankhauser et al., 2012); and (Andreas Fischer, 2013).”
- Auto-Keras: Efficient Neural Architecture Search with Network Morphism (2018, background): “Calculating the edit-distance of two neural networks can be mapped to calculating the edit-distance of two graphs, which is an NP-hard problem (Zeng et al., 2009).”
- 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].”
- Stay on the Path: Instruction Fidelity in Vision-and-Language Navigation (2019, background): “Unfortunately, the exact solution to graph edit distance, even with fixed weights for the operations is an NP-hard problem (Zeng et al., 2009), so Desideratum (5) is left unsatisfied.”
- Distance-based Kernels for Surrogate Model-based Neuroevolution (2018, background): “Computing the graph edit distance is NP-hard [9].”
- Graph Matching Networks for Learning the Similarity of Graph Structured Objects (2019, methodology): “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).”