Abstract
The mechanism of message passing in graph neural networks (GNNs) is still mysterious for the literature. No one, to our knowledge, has given another possible theoretical origin for GNNs apart from convolutional neural networks. Somewhat to our surprise, the message passing can be best understood in terms of the power iteration. By removing activation functions and layer weights of GNNs, we propose power iteration clustering (SPIC) models which are naturally interpretable and scalable. The experiment shows our models extend the existing GNNs and enhance its capability of processing random featured networks. Moreover, we demonstrate the redundancy of some state-of-the-art GNNs in designing and define a lower limit for model evaluation by randomly initializing the aggregator of message passing.
Introduction: Beyond the CNN Analogy
While Graph Neural Networks (GNNs) have become the standard for graph-structured data, their internal mechanics are often treated as a black box. Most researchers explain GNNs by drawing analogies to Convolutional Neural Networks (CNNs), where nodes aggregate local "pixels" or neighbors. However, this analogy fails to explain why GNNs remain effective even when shallow or why certain non-linear components appear optional in practice.
This research proposes a different origin story: GNNs are iterative solvers that project graph features into a subspace defined by the graph's Laplacian eigenvectors—a process mathematically known as power iteration.
GNNs as Power Iteration
The authors introduce Subspace Power Iteration Clustering (SPIC) models to demystify GNN behavior. By stripping away activation functions (like ReLU) and layer weights, they analyze the core aggregator mechanism. They categorize existing GNNs into three "SPIC" flavors based on their aggregator matrices:
- Static Laplacian SPIC: Uses a single, fixed aggregator matrix (e.g., GCN, GraphSAGE).
- Semi-static Laplacian SPIC: Uses a linear combination of different powers of the Laplacian (e.g., ChebNet, APPNP).
- Dynamic Laplacian SPIC: Uses learnable, graph-dependent aggregators like attention mechanisms (e.g., GAT, AGNN).
By analyzing the equation $X' = M^k X$ (where $M$ is the aggregator and $X$ are features), the study demonstrates that each GNN layer is essentially one step of a power iteration. This process pushes node features toward the dominant eigenvectors of the graph, which naturally represent the graph's underlying cluster structure.
Key Insights: Eigenvector Alignment and Redundancy
- Mathematical Filtering: Message passing acts as a filter that downweights "bad" dimensions (associated with small eigenvalues) and emphasizes "good" dimensions (dominant eigenvectors) that define clear clusters.
- Design Redundancy: For many popular datasets like Cora, ReLU activations and specific layer weights are surprisingly redundant. A purely linear SPIC model often performs as well as a full GNN, suggesting that the graph structure itself does the heavy lifting.
- The Random Aggregator Baseline: The authors show that even a randomly initialized aggregator can perform remarkably well. They suggest that if a new GNN architecture cannot outperform a random Laplacian, it isn't effectively learning the graph structure beyond what is already inherent in the topology.
Experimental Results: The Role of Non-linearity
The study evaluates these concepts on standard node classification benchmarks, distinguishing between "linear" structured data (Citation networks like Cora) and "nonlinear" complex data (Biological networks like PPI).
On the Cora dataset, a simplified linear model (DAD/SGC) achieved 82.3% accuracy, virtually identical to the standard GCN's 82.2%. However, the PPI dataset revealed the limits of pure linearity. While a purely linear model failed (51.0% F1 score), adding just one ReLU layer (DAD_relu1) boosted performance to 64.4%, rivaling the much more complex GAT model (65.5%).
Conclusion
The power iteration perspective provides a robust theoretical framework for understanding GNNs. It explains why shallow networks are often sufficient and provides a natural explanation for "over-smoothing" as convergence toward a single dominant eigenvector. By identifying the redundancy in modern GNN design, this work pushes the boundaries of how we evaluate and build neural networks for graph data.
Summary updated