Source-linked AI summary
Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology
Nima Dehmamy, Albert-László Barabási, Rose Yu
TL;DR
The paper asks how much graph topology GCNs can represent through graph moments, given limitations imposed by node permutation invariance. It theoretically analyzes GCN expressiveness and proposes modular designs with different propagation rules and residual connections. The results indicate that depth matters more than width, while modular combinations improve representation power and distinguish graph-generating processes on small graphs.
Problem
The paper addresses limited understanding of how well GCNs capture graph features and graph moments under node permutation invariance.
Method
The paper analyzes GCN representation power theoretically and develops modular GCNs combining different propagation rules with residual connections.
Results
The analysis and experiments show that depth is more influential than width, while modular GCNs improve representation power and distinguish different graph-generating models on small graphs.
Takeaways & Limitations
Learning graph moments benefits from deeper architectures and combining GCN modules with different propagation rules.
Takeaways & Limitations
A multi-layer GCN with fewer than p layers cannot in general learn a graph moment of order p.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper examines what graph convolutional networks can represent about graph topology, focusing on graph moments and node permutation invariance. It finds that standard designs have limited expressiveness, while modular propagation rules and residual connections improve representation power.
- 1 Introduction: Node permutation invariance preserves graph structure under relabelling but restricts GCN expressiveness.GCNs use shared global parameters to satisfy this invariance, and the paper notes they are not universal function approximators.
- 1 Introduction: The paper studies GCN representation power for learning graph topology through graph moments.Graph moments capture key features of the random process generating a graph.
- 1 Introduction: Certain GCN designs can fail to learn graph moments even with multiple layers and nonlinear activation functions.The paper identifies these failures as a central limitation of graph convolutional networks.
- 1 Introduction: Theoretical analysis shows a strict dependence on depth for learning graph moments, while width plays a weaker role in many cases.The paper derives representation-power guarantees in terms of width, depth, and propagation rules.
- 1 Introduction: A modular GCN design using different propagation rules and residual connections can dramatically increase representation power.The approach targets a large class of node permutation-invariant graph functions, including non-smooth functions.
- 1 Introduction: The modular approach is applied to a graph stethoscope that classifies graph-generating processes or topology, with experiments validating the theoretical analysis.The paper reports that the approach can distinguish different graph topologies from small graphs.
2 Learning Graph Moments
The paper defines graph moments as topology-sensitive quantities linked to graph-generation processes and evaluates fully connected and graph convolutional networks for learning them. GCNs can learn some moments efficiently, but propagation rules and permutation invariance create important limitations.
- 2.1 Graph moments: Graph moments characterize the random process from which a graph is generated, analogous to moments characterizing a random variable's distribution.Different graph-generation processes can depend on different moment orders.
- 2.1 Graph moments: The pth graph moment is the ensemble average of an order-p polynomial of the adjacency matrix A.Graph powers encode path counts, and graph moments are invariant to node permutations.
- 2.1 Graph moments: Permutation-invariant linear transformations constrain their matrix parameters to forms proportional to the identity or uniform aggregation matrices.The paper expresses this constraint as W and B being cI or c11T.
- 2.2 Learning with Fully Connected Networks: Fully connected networks can learn first-order moments to MSE ≈10^-4, but require hidden width comparable to graph size and at least 1,000 samples.They treat adjacency matrices as vectors, ignoring graph structure and requiring many parameters and training examples.
- 2.3 Learning with Graph Convolutional Networks: A single-layer GCN uses a propagation rule f(A) on node attributes, with weights coupled to attributes rather than to f(A).The framework includes normalized adjacency rules used by GCN and GraphSAGE.
- 2.3 Learning with Graph Convolutional Networks: A single-layer GCN with f(A)=A learns BA-graph node degrees with as few as 50 samples and one hidden unit, whereas f(A)=D^-1A fails regardless of sample size.This contrast demonstrates a limitation caused by the permutation-invariance constraint.
3 Theoretical Analysis
Theoretical analysis shows that GCN representation power depends strongly on depth and propagation design: shallow or feed-forward architectures can miss graph moments, while residual connections enable broader polynomial representations.
- A fully connected network may require O(p^2N^2q) neurons in the best case to learn a graph moment of order p for N-node graphs.
- A GCN with n < p layers cannot, in general, learn a graph moment of order p for random graphs.
- A bias-free n-layer GCN can generally learn a pth-order moment only when n = p, while bias permits n > p for some single-term moments.
- Feed-forward GCNs with extra layers can fail on mixed-order moments because learning single-term moments requires setting some layer weights to zero.
- Residual connections concatenate intermediate layer outputs, allowing a GCN with O(p) neurons to learn a moment of order p when depth is at least p.
- Theoretical and experimental results indicate that depth matters more than width, with residual GCNs learning target moments whenever layer count reaches the target order.
4 Modular GCN Design
The modular design combines distinct graph propagation rules with node-wise aggregation and residual connections. This architecture expands the functions GCNs can represent while preserving permutation invariance and supports learning higher-order graph moments.
- The modular GCN combines A, D^-1A, and D^-1/2AD^-1/2 propagation rules, concatenates their outputs, and applies a node-wise fully connected layer.
- Feed-forward stacking is restrictive because the propagation rules cannot be expressed as Taylor expansions of one another, limiting learnable graph moments.
- Residual connections from every layer to a final aggregation layer allow approximation of arbitrary polynomial functions of graph moments.
- Experiments on first-, second-, and third-order moments show that residual GCNs learn the target moments whenever the number of layers is at least the target order.
- The modular architecture improves representation power for higher-order graph moments while preserving node permutation invariance.
5 Related Work
Related work situates this study within graph representation learning, neural-network expressiveness, and graph-generation-model classification. Prior research includes broad graph surveys, theoretical analyses of depth and expressiveness, and applications to distinguishing graph-generating processes.
- Graph Representation Learning: Graph neural networks support complex graph representations, including propagation-based embeddings and graph convolutional architectures.
- Expressiveness of Neural Networks: Expressiveness research has studied universal approximation, VC dimension, depth, and the limits of message-passing GCNs under the Weisfeiler-Lehman framework.
- Distinguishing Graph Generation Models: Graph classification research compares graph-generation models using topology or node attributes, historically relying heavily on engineered features and hand-designed similarity measures.
6 Graph Stethoscope: Distinguishing Graph Generation Models
The paper evaluates modular GCNs as graph stethoscopes for distinguishing BA, ER, and configuration-model graphs, while testing how depth, width, and graph size affect accuracy.
- Graph-generation tasks: The evaluation compares BA graphs with ER graphs and with configuration-model graphs that preserve BA degree distributions.The latter is designed as a harder classification task because the compared graphs share exactly the same degree distribution.
- Graph-generation tasks: KS-test distributions for real-real and real-fake BA pairs are almost identical across graph moments.This makes distinguishing BA graphs from configuration-model graphs difficult using standard moment-based tests.
- Representation trends: Increasing network depth improves test accuracy by at least 5%, whereas increasing width has very little effect.The experiments vary depth, width, and graph size using the modular GCN architecture.
- Representation trends: Graphs with N ≥50 nodes reach 100% accuracy for BA-ER classification, while BA-configuration classification reaches a maximum accuracy of 90%.Smaller graphs are harder to learn, and the configuration-model task remains substantially more difficult.
- Module ablation: A single propagation module performs near random guessing, while combining all three modules enables almost perfect BA-ER discrimination.The compared modules are f1 = A, f2 = D−1A, and f3 = D−1/2AD−1/2, with parameter counts held constant.
7 Conclusion
The paper concludes that GCN representation power for graph moments is restricted, but modular designs combining propagation rules and residual connections improve graph-topology learning.
- Conclusion: GCNs can fail to learn graph moments even with multiple layers and nonlinear activation functions.The conclusion identifies this as a central limitation of standard GCN designs.
- Conclusion: Modular GCNs can distinguish different graph generative models for surprisingly small graphs.The conclusion presents this as an empirical capability of the modular approach.
- Conclusion: For learning graph moments, depth is more influential than width, and deeper GCNs better capture higher-order moments.The conclusion states this as the main trend from the theoretical and experimental investigation.
- Conclusion: Combining GCN modules with different propagation rules and residual connections improves representation power.The conclusion emphasizes module combination as critical to the design.
A Learning on graphs using single hidden layer fully connected network
This appendix contrasts fully connected networks with GCNs for learning graph moments, deriving sample and width requirements before motivating modular propagation rules.
- Approximation analysis: For polynomial functions, the approximation complexity depends on the number and magnitude of non-negligible Fourier coefficients.The appendix relates this quantity to the function’s degree and input dimension.
- Approximation analysis: A fully connected network treats an N-node adjacency matrix as an input of dimension d = N^2.The approximation analysis therefore depends on the quadratic input dimension of the adjacency matrix.
- Approximation analysis: When log N ∼O(1), approximating arbitrary functions of the adjacency matrix requires S ∼O(N^2) samples to control the second error term.This bound is presented as a condition for avoiding overfitting.
- Graph moments: Graph moments are polynomial functions of adjacency entries: node degree is first order, while length-two paths are second order.Higher-order moments generally involve higher powers of the adjacency matrix.
- Approximation analysis: For a graph moment of order p, the number of nonzero coefficients can range from O(pN) to O(pN^2), increasing the required network width.The derived coefficient bound gives Cf ∼O(pN^q) with 1 ≤q ≤2.
- Modular design: Combining propagation rules such as D−1A and D−1/2AD−1/2 with node-wise dense layers provides a modular alternative to learning nonlinear functions directly.The node-wise layers mix outputs without mixing different nodes.
B Experiment details
The experiments generate BA, ER, and configuration-model graphs under controlled node, edge, and degree settings for graph-generation classification.
- BA-ER setup: The experiment generates 5,000 graphs, split evenly between BA and ER models, with the same node count and varying numbers of links.The BA graphs are distributed across m = 1, N/8, N/4, 3N/8, and N/2.
- BA-ER setup: BA graphs use preferential attachment, whereas ER graphs assign each link an independent probability p.The ER experiments use four p values uniformly between 1/N and N/2, while graph link counts remain similar.
- Configuration-model setup: The configuration model starts from a degree sequence and repeatedly connects randomly selected node stubs.The degree sequence is drawn from a BA adjacency matrix, and the stub sum must be even.
C Learning graph moments without residual connections
Feed-forward GCN layers without residual connections have limited ability to learn graph moments: performance depends on matching layer count to moment order, and additional depth can hurt.
- C Learning graph moments without residual connections: GCNs without residual connections cannot reliably learn graph moments whose order differs from the number of layers.This limitation persists regardless of how many layers are stacked or how nonlinear the activation function is.
- C Learning graph moments without residual connections: Figure 7 evaluates first-, second-, and third-order graph moments using one to four layers and multiple activation functions.The experiments test linear, ReLU, sigmoid, and tanh activations.
- C Learning graph moments without residual connections: When the target moment order exceeds the layer count, residual-free GCNs fail to learn well.This pattern is observed across the tested graph-moment orders.
- C Learning graph moments without residual connections: With ReLU, increasing depth can sometimes worsen performance rather than improve it.More layers are also not consistently better than using a layer count that exactly matches the target moment order.
D A Note on Graph Attention Networks
Graph Attention Networks modify message passing by learning edge weights from neighboring node features, whereas the paper’s modular approach uses regular propagation rules without distinguishing among neighbors.
- D A Note on Graph Attention Networks: GAT changes neighbor contributions by assigning learned attention weights to graph edges.The attention mechanism determines how much each neighbor contributes to a node’s output.
- D A Note on Graph Attention Networks: The attention score is computed only for neighboring nodes using transformed node features.The mechanism applies a shared weight matrix and a learned function to pairs of neighboring representations.
- D A Note on Graph Attention Networks: Attention scores are normalized over each node’s neighbors with softmax before aggregation.This lets the network assign different weights to different neighbors.
- D A Note on Graph Attention Networks: The paper’s modular approach does not distinguish among neighbors and instead concatenates outputs from multiple regular propagation rules.Each propagation rule remains a standard message-passing step.