  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.
