# GREED: A Neural Framework for Learning Graph Distance Functions

arXiv: https://arxiv.org/abs/2112.13143 · HTML: https://mlsanity.com/paper/2112.13143/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 51 references that are in the map.
- First posted on arXiv 24 Dec 2021.

## Builds on (most cited first, 17 of 17)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [Combinatorial Learning of Graph Edit Distance via Dynamic Embedding](https://mlsanity.com/paper/2011.15039/) (2020)
- [Deep Graph Neural Networks with Shallow Subgraph Samplers](https://mlsanity.com/paper/2012.01380/) (2020)
- [An Analytical Study of Large SPARQL Query Logs](https://mlsanity.com/paper/1708.00363/) (2017)
- [New Techniques for Graph Edit Distance Computation](https://mlsanity.com/paper/1908.00265/) (2019)
- [Hierarchical Graph Matching Network for Graph Similarity Computation](https://mlsanity.com/paper/2006.16551/) (2020)

## Built on by (most cited first, 30 of 32)

- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [A Survey on Explainability of Graph Neural Networks](https://mlsanity.com/paper/2306.01958/) (2023)
- [GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking](https://mlsanity.com/paper/2310.01794/) (2023)
- [Graph Edit Distance with General Costs Using Neural Set Divergence](https://mlsanity.com/paper/2409.17687/) (2024)
- [MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation](https://mlsanity.com/paper/2311.02356/) (2023)
- [GRAFENNE: Learning on Graphs with Heterogeneous and Dynamic Feature Sets](https://mlsanity.com/paper/2306.03447/) (2023)
- [Computing Approximate Graph Edit Distance via Optimal Transport](https://mlsanity.com/paper/2412.18857/) (2024)
- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [Task and Model Agnostic Adversarial Attack on Graph Neural Networks](https://mlsanity.com/paper/2112.13267/) (2021)
- [A Solver-Free Framework for Scalable Learning in Neural ILP Architectures](https://mlsanity.com/paper/2210.09082/) (2022)
- [NeuroCUT: A Neural Approach for Robust Graph Partitioning](https://mlsanity.com/paper/2310.11787/) (2023)
- [Lifelong Learning for Neural powered Mixed Integer Programming](https://mlsanity.com/paper/2208.12226/) (2022)
- [Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval](https://mlsanity.com/paper/2510.22538/) (2025)
- [Deep Probabilistic Graph Matching](https://mlsanity.com/paper/2201.01603/) (2022)
- [Graph Edit Distance Learning via Different Attention](https://mlsanity.com/paper/2308.13871/) (2023)
- [Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance](https://mlsanity.com/paper/2504.06533/) (2025)
- [GEDAN: Learning the Edit Costs for Graph Edit Distance](https://mlsanity.com/paper/2508.03111/) (2025)
- [Graph2Region: Efficient Graph Similarity Learning with Structure and Scale Restoration](https://mlsanity.com/paper/2510.00394/) (2025)
- [Hierarchy-Aware Neural Subgraph Matching with Enhanced Similarity Measure](https://mlsanity.com/paper/2510.00402/) (2025)
- [Colorful Talks with Graphs: Human-Interpretable Graph Encodings for Large Language Models](https://mlsanity.com/paper/2602.10386/) (2026)
- [SPRig: Self-Supervised Pose-Invariant Rigging from Mesh Sequences](https://mlsanity.com/paper/2602.12740/) (2026)
- [EUGENE: Explainable Structure-aware Graph Edit Distance Estimation with Generalized Edit Costs](https://mlsanity.com/paper/2402.05885/) (2024)
- [Solving the Tree Containment Problem Using Graph Neural Networks](https://mlsanity.com/paper/2404.09812/) (2024)
- [Design Requirements for Human-Centered Graph Neural Network Explanations](https://mlsanity.com/paper/2405.06917/) (2024)
- [SaraCoder: Orchestrating Semantic and Structural Cues for Resource-Optimized Repository-Level Code Completion](https://mlsanity.com/paper/2508.10068/) (2025)
- [Contextual Tokenization for Graph Inverted Indices](https://mlsanity.com/paper/2510.22479/) (2025)
- [Charting the Design Space of Neural Graph Representations for Subgraph Matching](https://mlsanity.com/paper/2510.22897/) (2025)
- [U-CECE: A Universal Multi-Resolution Framework for Conceptual Counterfactual Explanations](https://mlsanity.com/paper/2604.08295/) (2026)
- [Towards Metric-Faithful Neural Graph Matching](https://mlsanity.com/paper/2605.06588/) (2026)
- [Agents for Experiments, Experiments for Agents: A Design Grammar for AI-Enabled Experimental Science](https://mlsanity.com/paper/2605.17746/) (2026)

## Abstract (arXiv)

Among various distance functions for graphs, graph and subgraph edit distances (GED and SED respectively) are two of the most popular and expressive measures. Unfortunately, exact computations for both are NP-hard. To overcome this computational bottleneck, neural approaches to learn and predict edit distance in polynomial time have received much interest. While considerable progress has been made, there exist limitations that need to be addressed. First, the efficacy of an approximate distance function lies not only in its approximation accuracy, but also in the preservation of its properties. To elaborate, although GED is a metric, its neural approximations do not provide such a guarantee. This prohibits their usage in higher order tasks that rely on metric distance functions, such as clustering or indexing. Second, several existing frameworks for GED do not extend to SED due to SED being asymmetric. In this work, we design a novel siamese graph neural network called GREED, which through a carefully crafted inductive bias, learns GED and SED in a property-preserving manner. Through extensive experiments across 10 real graph datasets containing up to 7 million edges, we establish that GREED is not only more accurate than the state of the art, but also up to 3 orders of magnitude faster. Even more significantly, due to preserving the triangle inequality, the generated embeddings are indexable and consequently, even in a CPU-only environment, GREED is up to 50 times faster than GPU-powered baselines for graph / subgraph retrieval.