# SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 78 references that are in the map.
- First posted on arXiv 26 May 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [Deep Graph Matching Consensus](https://mlsanity.com/paper/2001.09621/) (2020)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [Product Manifold Filter: Non-Rigid Shape Correspondence via Kernel Density Estimation in the Product Space](https://mlsanity.com/paper/1701.00669/) (2017)
- [Multi-level Graph Convolutional Networks for Cross-platform Anchor Link Prediction](https://mlsanity.com/paper/2006.01963/) (2020)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Efficient Deformable Shape Correspondence via Kernel Matching](https://mlsanity.com/paper/1707.08991/) (2017)
- [Seeded graph matching for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1304.7844/) (2013)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [Meta-Inductive Node Classification across Graphs](https://mlsanity.com/paper/2105.06725/) (2021)
- [An efficient reconciliation algorithm for social networks](https://mlsanity.com/paper/1307.1690/) (2013)
- [Optimal De-Anonymization in Random Graphs with Community Structure](https://mlsanity.com/paper/1602.01409/) (2016)
- [Graph Matching with Partially-Correct Seeds](https://mlsanity.com/paper/2004.03816/) (2020)
- [The Power of D-hops in Matching Power-Law Graphs](https://mlsanity.com/paper/2102.12975/) (2021)
- [Deep Adversarial Network Alignment](https://mlsanity.com/paper/1902.10307/) (2019)
- [Triangular Alignment (TAME): A Tensor-based Approach for Higher-order Network Alignment](https://mlsanity.com/paper/1510.06482/) (2015)
- [Graph Neural Networks for User Identity Linkage](https://mlsanity.com/paper/1903.02174/) (2019)

## Built on by (most cited first, 3 of 3)

- [Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks](https://mlsanity.com/paper/2402.07340/) (2024)
- [Chaining 2-FWL GNNs for Combinatorial Graph Alignment](https://mlsanity.com/paper/2510.03086/) (2025)
- [Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts](https://mlsanity.com/paper/2605.09382/) (2026)

## Abstract (arXiv)

There is a growing interest in designing Graph Neural Networks (GNNs) for seeded graph matching, which aims to match two unlabeled graphs using only topological information and a small set of seed nodes. However, most previous GNNs for this task use a semi-supervised approach, which requires a large number of seeds and cannot learn knowledge that is transferable to unseen graphs. In contrast, this paper proposes a new supervised approach that can learn from a training set how to match unseen graphs with only a few seeds. Our SeedGNN architecture incorporates several novel designs, inspired by theoretical studies of seeded graph matching: 1) it can learn to compute and use witness-like information from different hops, in a way that can be generalized to graphs of different sizes; 2) it can use easily-matched node-pairs as new seeds to improve the matching in subsequent layers. We evaluate SeedGNN on synthetic and real-world graphs and demonstrate significant performance improvements over both non-learning and learning algorithms in the existing literature. Furthermore, our experiments confirm that the knowledge learned by SeedGNN from training graphs can be generalized to test graphs of different sizes and categories.