TL;DR
This paper addresses critical flaws in existing datasets used to evaluate Graph Edit Distance (GED) estimation models, specifically isomorphism bias leading to data leakage and a lack of varied edit costs. The authors introduce a new, comprehensive suite of datasets designed to eliminate these issues, enabling more robust and reliable benchmarking of neural GED methods and advancing research in the field.
What Problem Does This Paper Address?
Graph Edit Distance (GED) is a fundamental measure for quantifying the similarity between two graphs by calculating the minimum cost of transforming one into the other using operations like node/edge insertions, deletions, and substitutions. This is crucial for various graph comparison tasks. However, computing exact GED is computationally intractable, leading to the development of neural GED estimators that approximate it.
The problem arises in how these neural models are evaluated. Existing benchmark datasets suffer from two major issues:
- Isomorphism Bias and Train-Test Leakage: Many datasets contain a high proportion of structurally identical (isomorphic) graphs. This means that graphs in the test set might be structurally identical to graphs in the training set, leading to inflated performance metrics that don't reflect true generalization capabilities. The paper highlights that only a small fraction of graphs in common datasets like LINUX, IMDB, and AIDS are structurally unique.
- Uniform Edit Costs: Current datasets primarily use uniform costs for all edit operations (e.g., each operation costs 1). This limits the evaluation of GED methods' ability to handle the inherent flexibility of GED, which allows for asymmetric relationships and varying costs for different operations. This is a significant drawback, as real-world applications often require non-uniform costs.
These limitations cast doubt on the validity of existing research and hinder the development of truly robust GED estimation models.
Methods
The core contribution of this paper is the creation of a new suite of datasets and a methodology for generating them. The process involves:
- Graph Filtering: Starting with standard graph benchmark datasets, the authors perform an extensive isomorphism check to filter out duplicate structures, ensuring that the remaining graphs are structurally unique.
- Data Splitting: The unique graphs are then split into training, validation, and testing sets using a 60:20:20 ratio.
- Pair Generation: For each split, all possible pairs of graphs (including self-pairs) are generated to create the training, validation, and test pairs. This results in a large number of pairs for evaluation.
- Ground Truth GED Computation: The ground truth GED for each pair is computed using the MIP-F2 solver, a standard tool for exact GED calculation. Crucially, this is done with varying edit cost configurations, addressing the limitation of uniform costs in previous datasets.
The paper introduces four distinct edit cost configurations:
- Uniform-GED (U-GED): Standard uniform costs (all operations cost 1, except node substitution which is 0).
- Non-uniform-GED (NU-GED): Non-uniform costs for node and edge operations.
- Label-GED (L-GED): Incorporates a cost for label substitution.
- Non-uniform-edge-GED (NUE-GED): Focuses solely on edge alignment costs by setting node-related costs to zero.
Datasets
The paper introduces a comprehensive suite of datasets derived from standard graph benchmarks, tailored for GED evaluation. These include:
- Mutagenicity (Mutag)
- Ogbg-Code2 (Code2)
- Ogbg-Molhiv (Molhiv)
- Ogbg-Molpcba (Molpcba)
- AIDS
- Linux
- Yeast
These datasets are made available with four different edit cost configurations (U-GED, NU-GED, L-GED, NUE-GED), providing a richer and more realistic evaluation environment compared to previous benchmarks.
Key Insights and Ideas
- The "Isomorphism Problem" is a Major Hurdle: The paper convincingly demonstrates that existing datasets are heavily contaminated with isomorphic graphs, severely compromising the reliability of evaluation metrics for neural GED models. This is a critical insight for anyone working in graph similarity.
- Beyond Uniform Costs is Essential: The reliance on uniform edit costs in prior work is a significant oversimplification. Real-world graph comparison often involves nuanced costs, and the new datasets allow for testing how well models adapt to these variations.
- A Foundation for Fairer Comparisons: By providing datasets that eliminate leakage and offer diverse cost settings, the authors lay the groundwork for more equitable and meaningful comparisons between different GED estimation methods. This will help researchers identify truly superior approaches.
- Open-Source is Key for Progress: Releasing these datasets and the generation methodology democratizes research in this area, lowering the barrier to entry and fostering collaboration.
Key Results
The paper presents benchmarking results for nine state-of-the-art GED estimation methods across the newly proposed datasets and cost variants. While specific "best" performers vary by dataset and cost configuration, some general trends emerge:
- EGSC and ERIC are frequently among the top performers, particularly on the Uniform-GED and Non-uniform-GED tasks.
- Methods that rely on Euclidean distance between graph vectors (like GMN-Match, GMN-Embed, and GREED) tend to perform poorly on non-uniform cost settings, indicating they don't effectively capture the nuances of varied edit costs.
- The paper provides detailed Mean Squared Error (MSE) tables for each method and dataset/cost combination, allowing for in-depth analysis of performance differences. For instance, on the Uniform-GED task for the Mutag dataset, GMN-Match achieved an MSE of 0.797 ± 0.013, while EGSC achieved 0.765 ± 0.011.
Limitations and Future Work
- Computational Cost of GED Ground Truth: While the MIP-F2 solver is used for ground truth, it remains computationally expensive, especially for larger graphs. The paper acknowledges this and mentions that early neural GED papers focused on smaller graphs due to this limitation.
- Method Limitations: The paper notes that none of the evaluated methods explicitly incorporate edit costs into their formulations, treating them as external features. This suggests a potential avenue for future research: developing models that can natively learn and utilize variable edit costs.
- Future Work: The authors explicitly state their intention to release the datasets and code, which will facilitate further research. They also implicitly suggest that future work should focus on developing GED estimation methods that are more robust to varying edit costs and can generalize better across different graph structures and cost settings.
Summary updated