Towards Metric-Faithful Neural Graph Matching

• URL: http://arxiv.org/abs/2605.06588v1
• Date: Thu, 07 May 2026 17:16:54 GMT
• Title: Towards Metric-Faithful Neural Graph Matching
• Abstract summary: Graph Edit Distance (GED) is a fundamental, albeit NP-hard, metric for structural graph similarity.<n>Recent neural graph matching architectures approximate GED by first encoding graphs with a Graph Neural Network (GNN) and then applying either a graph-level regression head or a matching-based alignment module.<n>Despite substantial architectural progress, the role of encoder geometry in neural GED estimation remains poorly understood.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Graph Edit Distance (GED) is a fundamental, albeit NP-hard, metric for structural graph similarity. Recent neural graph matching architectures approximate GED by first encoding graphs with a Graph Neural Network (GNN) and then applying either a graph-level regression head or a matching-based alignment module. Despite substantial architectural progress, the role of encoder geometry in neural GED estimation remains poorly understood. In this paper, we develop a theoretical framework that connects encoder geometry to GED estimation quality for two broad classes of neural GED estimators: graph similarity predictors and alignment-based methods. On fixed graph collections, where the doubly-stochastic metric $d_{\mathrm{DS}}$ is comparable to GED, we show that graph-level bi-Lipschitz encoders yield controlled GED surrogates and improved ranking stability; for matching-based estimators, node-level bi-Lipschitz geometry propagates to encoder-induced alignment costs and the resulting optimized alignment objective. We instantiate this perspective using FSW-GNN, a bi-Lipschitz WL-equivalent encoder, as a drop-in replacement in representative neural GED architectures. Across representative baselines and benchmark datasets, the resulting geometry-aware variants significantly improve GED prediction and ranking metrics. A faithfulness case study of untrained encoders, together with ablations and transfer experiments, supports the view that these gains arise from improved representation geometry, positioning encoder geometry as a useful design principle for neural graph matching.

Related papers

• GED-Consistent Disentanglement of Aligned and Unaligned Substructures for Graph Similarity Learning [8.811956084670328]
  We propose GCGSim, a GED-consistent graph similarity learning framework centering on graph-level matching and substructure-level edit costs.<n>Our experiments on four benchmark datasets show that GCGSim achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2025-11-25T02:07:30Z)
• Chi-Geometry: A Library for Benchmarking Chirality Prediction of GNNs [0.0]
  Chi-Geometry is a library that generates graph data for testing and benchmarking GNNs' ability to predict chirality.<n>Chi-Geometry allows more interpretable and less confounding benchmarking of GNNs for prediction of chirality in the graph samples.
  arXiv  Detail & Related papers  (2025-08-12T17:24:56Z)
• GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Code [11.73546901244934]
  Graph Edit Distance (GED) is a widely used metric for measuring similarity between two graphs.<n> neural methods have achieved improved approximation quality compared to non-neural approaches.<n>GRAIL employs a novel combination of large language models (LLMs) and automated prompt tuning to generate a program that is used to compute GED.
  arXiv  Detail & Related papers  (2025-05-04T14:14:24Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• UniG-Encoder: A Universal Feature Encoder for Graph and Hypergraph Node Classification [6.977634174845066]
  A universal feature encoder for both graph and hypergraph representation learning is designed, called UniG-Encoder. The architecture starts with a forward transformation of the topological relationships of connected nodes into edge or hyperedge features. The encoded node embeddings are then derived from the reversed transformation, described by the transpose of the projection matrix.
  arXiv  Detail & Related papers  (2023-08-03T09:32:50Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network [72.16255675586089]
  We propose an Adaptive Curvature Exploration Hyperbolic Graph NeuralNetwork named ACE-HGNN to adaptively learn the optimal curvature according to the input graph and downstream tasks. Experiments on multiple real-world graph datasets demonstrate a significant and consistent performance improvement in model quality with competitive performance and good generalization ability.
  arXiv  Detail & Related papers  (2021-10-15T07:18:57Z)
• Self-supervised Geometric Perception [96.89966337518854]
  Self-supervised geometric perception is a framework to learn a feature descriptor for correspondence matching without any ground-truth geometric model labels. We show that SGP achieves state-of-the-art performance that is on-par or superior to the supervised oracles trained using ground-truth labels.
  arXiv  Detail & Related papers  (2021-03-04T15:34:43Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN) We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE) EGAE consists of one encoder and dual decoders.
  arXiv  Detail & Related papers  (2020-02-20T09:53:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.