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

Nima Dehmamy, Albert-László Barabási, Rose Yu

Graph Convolutional Networks (GCNs) are widely celebrated for their efficiency and relational inductive bias, driving successes in fields ranging from biology to robotics. However, they are often treated as "black box" feature extractors under the assumption that they can learn any arbitrary representation of graph data.

This paper provides a rigorous look under the hood of GCNs, revealing that standard architectures are surprisingly limited in their ability to learn basic graph properties—specifically "graph moments"—unless they are designed with specific architectural features like modularity and depth.

The Problem: GCNs and Graph Moments

Because GCNs must be node permutation invariant (meaning the output shouldn't change just because nodes are re-indexed), they are not "universal function approximators" in the same way standard fully connected neural networks are.

The authors investigate whether GCNs can learn graph moments. In network science, graph moments (such as the average degree or the number of paths of a certain length) act as the "DNA" of a graph’s topology. If a GCN cannot learn these fundamental structures, it cannot truly understand the data it is processing.

Methods: A Modular Approach to GCNs

To analyze GCNs, the researchers view them through the lens of matrix polynomials, defining a $p$-th order graph moment as a polynomial of the adjacency matrix $A$. For example, a 1st-order moment relates to node degrees, while higher-order moments relate to longer paths and loops.

Instead of relying on a single "propagation rule" (the way information flows between nodes), the authors propose a Modular GCN architecture.

Modular GCN and Residual Architecture

This modular design combines three different rules in a single layer:

  1. The raw adjacency matrix ($A$)
  2. The random-walk normalized matrix ($D^{-1}A$)
  3. The symmetric normalized matrix ($D^{-1/2}AD^{-1/2}$)

Furthermore, they emphasize the use of residual connections to allow the network to "mix" moments of different orders, effectively combining information about immediate neighbors with information about nodes several hops away.

Key Insights: The Depth Bottleneck

The most striking theoretical and empirical finding is the depth bottleneck. To learn a $p$-th order graph moment (paths of length $p$), a GCN must have at least $p$ layers. Adding more hidden units (width) does almost nothing to help a shallow network understand deep topology.

Test Loss for Graph Moments by Network Depth

Other critical insights include:

  • Standard GCNs Can Fail: A standard GCN using only normalized propagation rules can completely fail to learn something as simple as node degrees, regardless of how much data it processes.
  • Efficiency vs. Expressiveness: While Fully Connected (FC) networks can learn these moments, they are incredibly inefficient, requiring $O(N^2)$ neurons. A properly designed GCN can achieve the same with only $O(p)$ neurons, making its parameter count independent of the graph's size.
  • Modularity is Key: Different normalization schemes capture different topological "frequencies." By concatenating multiple propagation rules, the GCN gains a much richer vocabulary for describing the graph.

Key Results

The authors tested their theories using synthetic graph generation models (like Erdős-Rényi and Barabási-Albert) to provide a ground truth for topology. They introduced a "Graph Stethoscope" diagnostic task to classify the generating process of small graphs.

  • BA vs. ER Classification: A single-rule GCN achieved only ~53.5% accuracy (barely better than random guessing). In contrast, the Modular GCN reached 98.8% accuracy.
  • Distinguishing "Fake" Graphs: On the notoriously difficult task of distinguishing BA graphs from Configuration Model graphs (which are engineered to have the exact same degree distribution but different higher-order structures), the modular design achieved ~90% accuracy. This proves it can capture higher-order topological features that standard methods miss.
  • Empirical Validation of Depth: Experiments confirmed that a 3-layer GCN could learn 3rd-order moments, but a 2-layer GCN could not, regardless of its width.

Limitations and Future Work

While the theoretical proofs are robust, the analysis is heavily rooted in synthetic random graph models. Real-world graphs (like social networks or molecules) may have noisier or more localized topological features. Additionally, using multiple propagation rules increases the computational footprint per layer, which may require optimized sparse-matrix implementations for massive graphs with billions of edges.

Ultimately, the "Graph Stethoscope" approach introduced here provides a powerful framework to better understand the inductive biases of other Graph Neural Network variants in the future.

Summary updated

Abstract

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, arriving at a modular GCN design, using different propagation rules. Our modular design is 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 and deeper GCNs are more capable of learning higher order graph moments. Additionally, combining GCN modules with different propagation rules is critical to the representation power of GCNs.
BibTeX
@inproceedings{dehmamy2019understanding,
  author = {Nima Dehmamy and Albert-László Barabási and Rose Yu},
  title = {{Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure