SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching
This addresses the challenge of matching unlabeled graphs with limited seed nodes for applications in network analysis, offering a more efficient and transferable approach compared to previous semi-supervised methods.
The paper tackles the problem of seeded graph matching by proposing SeedGNN, a supervised Graph Neural Network that learns from training graphs to match unseen graphs with only a few seeds, achieving significant performance improvements over existing methods.
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.