Random Geometric Graph Alignment with Graph Neural Networks
Suqi Liu Morgane Austern
We characterize the performance of graph neural networks for graph alignment
problems in the presence of vertex feature information. More specifically,
given two graphs that are independent perturbations of a single random
geometric graph with noisy sparse features, the task is to recover an unknown
one-to-one mapping between the vertices of the two graphs. We show under
certain conditions on the sparsity and noise level of the feature vectors, a
carefully designed one-layer graph neural network can with high probability
recover the correct alignment between the vertices with the help of the graph
structure. We also prove that our conditions on the noise level are tight up to
logarithmic factors. Finally we compare the performance of the graph neural
network to directly solving an assignment problem on the noisy vertex features.
We demonstrate that when the noise level is at least constant this direct
matching fails to have perfect recovery while the graph neural network can
tolerate noise level growing as fast as a power of the size of the graph.