Bootstrap Learning for Combinatorial Graph Alignment with Sequential GNNs

• URL: http://arxiv.org/abs/2510.03086v1
• Date: Fri, 03 Oct 2025 15:17:00 GMT
• Title: Bootstrap Learning for Combinatorial Graph Alignment with Sequential GNNs
• Authors: Marc Lelarge,
• Abstract summary: Graph neural networks (GNNs) have struggled to outperform traditional optimization methods on neural problems, limiting their practical impact.<n>We introduce a novel chaining procedure for the graph alignment problem, using only structural information.<n>Our method trains a sequence of GNNs where each network learns to iteratively refine similarity matrices produced by previous networks.<n>During inference, this creates a bootstrap effect: each GNN improves upon partial solutions by incorporating discrete ranking information about node alignment quality from prior iterations.
• Score: 8.49454123392354
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) have struggled to outperform traditional optimization methods on combinatorial problems, limiting their practical impact. We address this gap by introducing a novel chaining procedure for the graph alignment problem, a fundamental NP-hard task of finding optimal node correspondences between unlabeled graphs using only structural information. Our method trains a sequence of GNNs where each network learns to iteratively refine similarity matrices produced by previous networks. During inference, this creates a bootstrap effect: each GNN improves upon partial solutions by incorporating discrete ranking information about node alignment quality from prior iterations. We combine this with a powerful architecture that operates on node pairs rather than individual nodes, capturing global structural patterns essential for alignment that standard message-passing networks cannot represent. Extensive experiments on synthetic benchmarks demonstrate substantial improvements: our chained GNNs achieve over 3x better accuracy than existing methods on challenging instances, and uniquely solve regular graphs where all competing approaches fail. When combined with traditional optimization as post-processing, our method substantially outperforms state-of-the-art solvers on the graph alignment benchmark.

Related papers

• DREAM: Dual-Standard Semantic Homogeneity with Dynamic Optimization for Graph Learning with Label Noise [53.55187452152358]
  This paper proposes a novel method, Dual-Standard Semantic Homogeneity with Dynamic Optimization (DREAM) for reliable, relation-informed optimization on graphs with label noise.<n>Specifically, we design a relation-informed dynamic optimization framework that iteratively reevaluates the reliability of each labeled node in the graph.
  arXiv  Detail & Related papers  (2026-01-24T12:54:18Z)
• Graph Neural Networks Powered by Encoder Embedding for Improved Node Learning [17.31465642587528]
  Graph neural networks (GNNs) have emerged as a powerful framework for a wide range of node-level graph learning tasks.<n>In this paper, we leverage a statistically grounded method, one-hot graph encoder embedding (GEE), to generate high-quality initial node features.<n>We demonstrate its effectiveness through extensive simulations and real-world experiments across both unsupervised and supervised settings.
  arXiv  Detail & Related papers  (2025-07-15T21:01:54Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant [1.8606770727950463]
  We propose several GNN-based architectures to tackle the graph partitioning problem for Markov Chains described as kinetic networks. This approach aims to minimize how much a proposed partitioning changes the Kemeny constant. We show how simple GraphSAGE-based GNNs with linear layers can outperform much larger and more expressive attention-based models in this context.
  arXiv  Detail & Related papers  (2023-12-22T17:19:50Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  We modify the Graph Neural Network (GNN) architecture so that the weight matrices are learned, separately, for the nodes in each group. This simple-to-implement modification seems to improve performance across datasets and GNN methods.
  arXiv  Detail & Related papers  (2023-12-16T14:09:23Z)
• A GAN Approach for Node Embedding in Heterogeneous Graphs Using Subgraph Sampling [33.50085646298074]
  We propose a novel framework that combines Graph Neural Network (GNN) and Generative Adrial Network (GAN) to enhance classification for underrepresented node classes. The framework incorporates an advanced edge generation and selection module, enabling the simultaneous creation of synthetic nodes and edges.
  arXiv  Detail & Related papers  (2023-12-11T16:52:20Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• GPN: A Joint Structural Learning Framework for Graph Neural Networks [36.38529113603987]
  We propose a GNN-based joint learning framework that simultaneously learns the graph structure and the downstream task. Our method is the first GNN-based bilevel optimization framework for resolving this task.
  arXiv  Detail & Related papers  (2022-05-12T09:06:04Z)
• Policy-GNN: Aggregation Optimization for Graph Neural Networks [60.50932472042379]
  Graph neural networks (GNNs) aim to model the local graph structures and capture the hierarchical patterns by aggregating the information from neighbors. It is a challenging task to develop an effective aggregation strategy for each node, given complex graphs and sparse features. We propose Policy-GNN, a meta-policy framework that models the sampling procedure and message passing of GNNs into a combined learning process.
  arXiv  Detail & Related papers  (2020-06-26T17:03:06Z)

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.