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

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

Abstract

Graph Convolutional Networks (GCNs) have become a cornerstone of graph-based machine learning, yet their mathematical representation power remains poorly understood. This paper investigates the ability of GCNs to learn fundamental topological features, specifically graph moments—statistical properties derived from paths of varying lengths. We demonstrate that standard GCNs are fundamentally depth-constrained: a network requires at least $p$ layers to represent a $p$-th order graph moment. To overcome these limitations, we propose a modular GCN architecture utilizing multiple propagation rules and residual skip-connections, proving that for learning graph topology, depth and architectural design are more critical than width.

Introduction

Despite the widespread adoption of GCNs in domains like drug discovery and social network analysis, they are often treated as "black boxes." A common assumption is that GCNs can learn any arbitrary graph feature given enough parameters. However, because GCNs must be node permutation invariant, they face inherent mathematical restrictions. This study addresses a foundational question: Can a GCN learn the underlying "recipe" or topology of a graph? Specifically, can it learn graph moments, which define structures ranging from simple node degrees to complex higher-order path distributions?

Methods

The research explores GCN expressiveness through theoretical proofs and the introduction of a novel architectural framework:

  1. Graph Moments Analysis: Topology is defined through polynomials of the adjacency matrix ($A$), where a $p$-th order moment corresponds to paths of length $p$.
  2. Depth Constraints: The authors prove that a standard feed-forward GCN with $n$ layers cannot learn a graph moment of order $p$ if $n < p$. Depth is the primary driver of topological awareness.
  3. Modular GCN Design: To enhance representational power, the authors propose a "Modular GCN" that combines three distinct propagation rules: Adjacency ($A$), Random Walk ($D^{-1}A$), and Symmetric Normalized ($D^{-1/2}AD^{-1/2}$).
  4. Residual Connections: Skip-connections are employed to concatenate the output of every layer to the final output. This allows the model to preserve low-order features (like degrees) while simultaneously computing high-order features in deeper layers.
The proposed Modular GCN module and the Residual Architecture used to capture multi-order graph moments.

Datasets

The study utilizes synthetic graph generation models to establish a topological ground truth:

  • Erdős-Rényi (ER): Random graphs with fixed edge probabilities.
  • Barabási-Albert (BA): Scale-free graphs generated via preferential attachment.
  • Configuration Model: A challenging dataset where "fake" BA graphs are constructed to match the degree distribution of real BA graphs but differ in higher-order structures.

Key Insights: The Depth Imperative

A central finding is that in GCNs learning topology, depth cannot be traded for width. Unlike standard deep learning where wider layers can sometimes compensate for shallower architectures, a GCN must have a depth proportional to the path length it aims to represent.

Test loss across different moments ($A^1, A^2, A^3$) and activations, demonstrating that higher-order moments require increased depth to achieve convergence.

Furthermore, simple stacking of layers is insufficient. Without residual connections, networks often "forget" lower-order moments as they attempt to compute more complex ones. The modular approach acts as a "graph stethoscope," allowing the network to probe the generative process of even very small graphs ($N < 50$) by viewing them through multiple mathematical "lenses."

Key Results

  • Efficiency: While fully connected networks require thousands of neurons to learn simple moments, a properly designed GCN can achieve the same with just one neuron per layer.
  • Classification Accuracy: The modular GCN achieved 98.8% accuracy in distinguishing BA from ER graphs.
  • The Hard Test: In the difficult task of separating real BA graphs from Configuration Model "fakes," the modular design reached ~90% accuracy, significantly outperforming single-module GCNs.
  • Ablation Study: Removing residual connections led to a total failure in learning mixed-order moments, confirming that skip-connections are vital for multi-scale topological representation.

Limitations and Future Work

While this work proves the "stethoscope" concept on small graphs ($N=20$ to $N=50$), the scaling behavior on massive, million-node graphs remains an open question. Additionally, the modular approach increases computational costs per layer. Future research should investigate how these designs perform on "noisy" real-world data where topological signals may be obscured by missing or spurious edges.

Summary updated

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