mlsanityData to 7 Oct 2026

Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks

arXiv 2402.07340 ↗First posted 12 Feb 2024cs.LG cs.IT cs.SIcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 37 of its 60 references that are in the map. First posted on arXiv 12 Feb 2024.

Builds on

37 of 60 references.

References · 37

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  5. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  6. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  7. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  9. 2019Graph Neural Networks for Social Recommendationcited by 711
  10. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  11. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  12. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
25 more
  1. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  2. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  3. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  4. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  5. 2018Efficient random graph matching via degree profilescited by 48
  6. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  7. 2021Transferability Properties of Graph Neural Networkscited by 42
  8. 2019Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universalitycited by 27
  9. 2018Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignmentcited by 25
  10. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  11. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  12. 2018On the Non-asymptotic and Sharp Lower Tail Bounds of Random Variablescited by 19
  13. 2018Mean-field theory of graph neural networks in graph partitioningcited by 16
  14. 2021Random Graph Matching with Improved Noise Robustnesscited by 16
  15. 2022Matching recovery threshold for correlated random graphscited by 16
  16. 2020Graph and graphon neural network stabilitycited by 15
  17. 2021Strong recovery of geometric planted matchingscited by 12
  18. 2023Optimal Inference in Contextual Stochastic Block Modelscited by 11
  19. 2019Phase Transitions for Detecting Latent Geometry in Random Graphscited by 9
  20. 2020The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Versioncited by 6
  21. 2021Phase transition in noisy high-dimensional random geometric graphscited by 6
  22. 2023Matching Correlated Inhomogeneous Random Graphs using the k-core Estimatorcited by 6
  23. 2021A probabilistic view of latent space graphs and phase transitionscited by 5
  24. 2022SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matchingcited by 3
  25. 2024Statistical Guarantees for Link Prediction using Graph Neural Networkscited by 2

Built on by

Not cited yet.