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

arXiv: https://arxiv.org/abs/1907.05008 · HTML: https://mlsanity.com/paper/1907.05008/

## Key facts

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

## Built on by (most cited first, 30 of 52)

- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Hierarchical Graph Representations in Digital Pathology](https://mlsanity.com/paper/2102.11057/) (2021)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Spatial Aggregation and Temporal Convolution Networks for Real-time Kriging](https://mlsanity.com/paper/2109.12144/) (2021)
- [Graph Pointer Neural Networks](https://mlsanity.com/paper/2110.00973/) (2021)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Leveraging power grid topology in machine learning assisted optimal power flow](https://mlsanity.com/paper/2110.00306/) (2021)
- [Semi-Supervised Graph-to-Graph Translation](https://mlsanity.com/paper/2103.08827/) (2021)
- [Unlimited Neighborhood Interaction for Heterogeneous Trajectory Prediction](https://mlsanity.com/paper/2108.00238/) (2021)
- [AutoGEL: An Automated Graph Neural Network with Explicit Link Information](https://mlsanity.com/paper/2112.01064/) (2021)
- [Graph Neural Networks: Methods, Applications, and Opportunities](https://mlsanity.com/paper/2108.10733/) (2021)
- [SkinningNet: Two-Stream Graph Convolutional Neural Network for Skinning Prediction of Synthetic Characters](https://mlsanity.com/paper/2203.04746/) (2022)
- [Understanding Virtual Nodes: Oversquashing and Node Heterogeneity](https://mlsanity.com/paper/2405.13526/) (2024)
- [GRIL: A 2-parameter Persistence Based Vectorization for Machine Learning](https://mlsanity.com/paper/2304.04970/) (2023)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [MM-GNN: Mix-Moment Graph Neural Network towards Modeling Neighborhood Feature Distribution](https://mlsanity.com/paper/2208.07012/) (2022)
- [Attentive Walk-Aggregating Graph Neural Networks](https://mlsanity.com/paper/2110.02667/) (2021)
- [Node Representation Learning in Graph via Node-to-Neighbourhood Mutual Information Maximization](https://mlsanity.com/paper/2203.12265/) (2022)
- [Multi-Level Attention Pooling for Graph Neural Networks: Unifying Graph Representations with Multiple Localities](https://mlsanity.com/paper/2103.01488/) (2021)
- [Predicting cognitive scores with graph neural networks through sample selection learning](https://mlsanity.com/paper/2106.09408/) (2021)
- [Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization](https://mlsanity.com/paper/2410.08473/) (2024)
- [D-GRIL: End-to-End Topological Learning with 2-parameter Persistence](https://mlsanity.com/paper/2406.07100/) (2024)
- [Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structure](https://mlsanity.com/paper/2301.10956/) (2023)
- [Exact Verification of Graph Neural Networks with Incremental Constraint Solving](https://mlsanity.com/paper/2508.09320/) (2025)
- [RAN-GNNs: breaking the capacity limits of graph neural networks](https://mlsanity.com/paper/2103.15565/) (2021)
- [Generalizing Aggregation Functions in GNNs:High-Capacity GNNs via Nonlinear Neighborhood Aggregators](https://mlsanity.com/paper/2202.09145/) (2022)

## 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.