SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching
Recently, there have been significant interests 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 seeds. However,
most previous GNN architectures for seeded graph matching employ a
semi-supervised approach, which learns from only the seed set in a single pair
of graphs, and therefore does not attempt to learn from many training
examples/graphs to best match future unseen graphs. In contrast, this paper is
the first to propose a supervised approach for seeded graph matching, which had
so far only been used for seedless graph matching. Our proposed SeedGNN
architecture employs a number of novel design choices that are inspired by
theoretical studies of seeded graph matching. First, SeedGNN can easily learn
the capability of counting and using witnesses of different hops, in a way that
can be generalized to graphs with different sizes. Second, SeedGNN can use
easily-matched pairs as new seeds to percolate and match other nodes. We
evaluate SeedGNN on both synthetic and real graphs, and demonstrate significant
performance improvement over both non-learning and learning algorithms in the
existing literature. Further, our experiments confirm that the knowledge
learned by SeedGNN from training graphs can be generalized to test graphs with
different sizes and categories.