# GED-Consistent Disentanglement of Aligned and Unaligned Substructures for Graph Similarity Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 25 Nov 2025.

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

- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [MINE: Mutual Information Neural Estimation](https://mlsanity.com/paper/1801.04062/) (2018)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (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)
- [Learning Disentangled Representations via Mutual Information Estimation](https://mlsanity.com/paper/1912.03915/) (2019)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [Multilevel Graph Matching Networks for Deep Graph Similarity Learning](https://mlsanity.com/paper/2007.04395/) (2020)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [Combinatorial Learning of Graph Edit Distance via Dynamic Embedding](https://mlsanity.com/paper/2011.15039/) (2020)
- [Computing Approximate Graph Edit Distance via Optimal Transport](https://mlsanity.com/paper/2412.18857/) (2024)
- [GraSP: Simple yet Effective Graph Similarity Predictions](https://mlsanity.com/paper/2412.09968/) (2024)
- [Graph Edit Distance Learning via Different Attention](https://mlsanity.com/paper/2308.13871/) (2023)

## Abstract (arXiv)

Graph Similarity Computation (GSC) is a fundamental graph related task where Graph Edit Distance (GED) serves as a prevalent metric. GED is determined by an optimal alignment between a pair of graphs that partitions each into aligned (zero-cost) and unaligned (cost-incurring) substructures. Due to NP-hard nature of exact GED computation, GED approximations based on Graph Neural Network(GNN) have emerged. Existing GNN-based GED approaches typically learn node embeddings for each graph and then aggregate pairwise node similarities to estimate the final similarity. Despite their effectiveness, we identify a mismatch between this prevalent node-centric matching paradigm and the core principles of GED. This discrepancy leads to two critical limitations: (1) a failure to capture the global structural correspondence for optimal alignment, and (2) a misattribution of edit costs driven by spurious node level signals. To address these limitations, we propose GCGSim, a GED-consistent graph similarity learning framework centering on graph-level matching and substructure-level edit costs. Specifically, we make three core technical contributions. Extensive experiments on four benchmark datasets show that GCGSim achieves state-of-the-art performance. Our comprehensive analyses further validate that the framework effectively learns disentangled and semantically meaningful substructure representations.