Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks
This provides a theoretical guarantee for graph neural networks in matching noisy graphs, which is incremental for applications like network alignment and data integration.
The paper tackles the graph matching problem with noisy vertex features by showing that a two-layer graph neural network can achieve perfect recovery of the vertex mapping under certain sparsity and noise conditions, tolerating noise levels up to a power of the graph size, while direct matching fails at constant noise.
We study the graph matching problem in the presence of vertex feature information using shallow graph neural networks. Specifically, given two graphs that are independent perturbations of a single random geometric graph with sparse binary 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 two-layer graph neural network can, with high probability, recover the correct mapping between the vertices with the help of the graph structure. Additionally, we prove that our condition on the noise parameter is tight up to logarithmic factors. Finally, we compare the performance of the graph neural network to directly solving an assignment problem using the noisy vertex features and demonstrate that when the noise level is at least constant, this direct matching fails to achieve perfect recovery, whereas the graph neural network can tolerate noise levels growing as fast as a power of the size of the graph. Our theoretical findings are further supported by numerical studies as well as real-world data experiments.