mlsanityData to 14 Oct 2026

Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology

arXiv 1907.05008 ↗First posted 11 Jul 2019cs.LG physics.data-an stat.MLcited by 52

Not on the map. Why?

Abstract (arXiv)

To deepen our understanding of graph neural networks, we investigate the representation power of Graph Convolutional Networks (GCN) through the looking glass of graph moments, a key property of graph topology encoding path of various lengths. We find that GCNs are rather restrictive in learning graph moments. Without careful design, GCNs can fail miserably even with multiple layers and nonlinear activation functions. We analyze theoretically the expressiveness of GCNs, concluding a modular GCN design, using different propagation rules with residual connections could significantly improve the performance of GCN. We demonstrate that such modular designs are capable of distinguishing graphs from different graph generation models for surprisingly small graphs, a notoriously difficult problem in network science. Our investigation suggests that, depth is much more influential than width, with deeper GCNs being more capable of learning higher order graph moments. Additionally, combining GCN modules with different propagation rules is critical to the representation power of GCNs.

Key facts. Cited by 52 papers in the map (data through 14 Oct 2026). First posted on arXiv 11 Jul 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 17; 2022: 9; 2023: 8; 2024: 10; 2025: 6; 2026: 2.

52 papers.

Sort:

  1. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  2. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  3. 2021Hierarchical Graph Representations in Digital Pathologycited by 59
  4. 2022Provably expressive temporal graph networkscited by 56
  5. 2023How does over-squashing affect the power of GNNs?cited by 53
  6. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  7. 2021Spatial Aggregation and Temporal Convolution Networks for Real-time Krigingcited by 27
  8. 2021Graph Pointer Neural Networkscited by 27
  9. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  10. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  11. 2021Leveraging power grid topology in machine learning assisted optimal power flowcited by 22
  12. 2021Semi-Supervised Graph-to-Graph Translationcited by 18
38 more
  1. 2021Unlimited Neighborhood Interaction for Heterogeneous Trajectory Predictioncited by 17
  2. 2021AutoGEL: An Automated Graph Neural Network with Explicit Link Informationcited by 17
  3. 2021Graph Neural Networks: Methods, Applications, and Opportunitiescited by 16
  4. 2022SkinningNet: Two-Stream Graph Convolutional Neural Network for Skinning Prediction of Synthetic Characterscited by 16
  5. 2024Understanding Virtual Nodes: Oversquashing and Node Heterogeneitycited by 14
  6. 2023GRIL: A 2-parameter Persistence Based Vectorization for Machine Learningcited by 13
  7. 2022On the Ability of Graph Neural Networks to Model Interactions Between Verticescited by 12
  8. 2022MM-GNN: Mix-Moment Graph Neural Network towards Modeling Neighborhood Feature Distributioncited by 11
  9. 2021Attentive Walk-Aggregating Graph Neural Networkscited by 10
  10. 2022Node Representation Learning in Graph via Node-to-Neighbourhood Mutual Information Maximizationcited by 9
  11. 2021Multi-Level Attention Pooling for Graph Neural Networks: Unifying Graph Representations with Multiple Localitiescited by 8
  12. 2021Predicting cognitive scores with graph neural networks through sample selection learningcited by 7
  13. 2024Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalizationcited by 6
  14. 2024D-GRIL: End-to-End Topological Learning with 2-parameter Persistencecited by 5
  15. 2023Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structurecited by 4
  16. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  17. 2021RAN-GNNs: breaking the capacity limits of graph neural networkscited by 3
  18. 2022Generalizing Aggregation Functions in GNNs:High-Capacity GNNs via Nonlinear Neighborhood Aggregatorscited by 3
  19. 2022Graph Representation Learning with Individualization and Refinementcited by 3
  20. 2023How Graph Neural Networks Learn: Lessons from Training Dynamicscited by 3
  21. 2024PF-GNN: Differentiable particle filtering based approximation of universal graph representationscited by 3
  22. 2024ForecastGrapher: Redefining Multivariate Time Series Forecasting with Graph Neural Networkscited by 3
  23. 2023Graph-Free Learning in Graph-Structured Data: A More Efficient and Accurate Spatiotemporal Learning Perspectivecited by 2
  24. 2023PAMI: partition input and aggregate outputs for model interpretationcited by 2
  25. 2021Bermuda Triangles: GNNs Fail to Detect Simple Topological Structurescited by 1
  26. 2021SoGCN: Second-Order Graph Convolutional Networkscited by 1
  27. 2024MEGA: Message Passing Neural Networks for Multigraphs with EdGe Attributescited by 1
  28. 2024GNN Applied to Ego-nets for Friend Suggestionscited by 1
  29. 2025WGLE:Backdoor-free and Multi-bit Black-box Watermarking for Graph Neural Networkscited by 1
  30. 2025TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtrationcited by 1
  31. 2025Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networkscited by 1
  32. 2021Distance and Hop-wise Structures Encoding Enhanced Graph Attention Networkscited by 0
  33. 2022Faster Optimization on Sparse Graphs via Neural Reparametrizationcited by 0
  34. 2024Learning the mechanisms of network growthcited by 0
  35. 2024Lightweight Spatial Modeling for Combinatorial Information Extraction From Documentscited by 0
  36. 2024A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networkscited by 0
  37. 2025Transformers trained on proteins can learn to attend to Euclidean distancecited by 0
  38. 2025LearnAD: Learning Interpretable Rules for Brain Networks in Alzheimer's Disease Classificationcited by 0

50 most cited of 52 All 52 (JSON)