Abstract
Message-Passing Neural Networks (MPNNs) frequently suffer from representational rank collapse, a phenomenon where node embeddings become linearly dependent and indistinguishable as network depth increases. This paper introduces Multi-Relational Split MPNNs (MRS-MPNNs), a framework designed to preserve the expressive power of deep GNNs. By partitioning a single graph into multiple directed relations based on node orderings and applying distinct learnable transformations to each, MRS-MPNNs ensure that node representations remain structurally independent. Experimental results across molecular and heterophilic graph benchmarks demonstrate that MRS-MPNNs effectively mitigate rank collapse, outperforming standard MPNNs and specialized architectures in complex graph tasks.
Introduction
In the field of Graph Neural Networks (GNNs), the challenge of "over-smoothing" is well-documented: as layers are added, node features tend to converge toward a common value, rendering the network unable to distinguish between individual nodes. This paper identifies a more fundamental mathematical issue underlying this trend: representational rank collapse.
In standard MPNNs, the graph convolution operation often amplifies the same signal across all feature channels. Consequently, the feature matrix eventually becomes "rank-one," where every node's embedding is merely a scaled version of the same vector. This collapse prevents the model from capturing multi-dimensional relationships or distinguishing nodes with different structural roles. While common techniques like residual connections or normalization provide temporary relief, they do not address the core message-passing mechanism that drives this collapse. This research proposes a structural solution by splitting the computational graph into multiple streams.
Methodology: Multi-Relational Split MPNNs (MRS-MPNNs)
The core of the proposed approach is the Multi-Relational Split MPNN (MRS-MPNN). Rather than treating all edges as homogeneous, the framework splits the graph’s computational structure into several distinct relations based on a strict partial ordering of nodes (denoted as $\prec$).
1. Node Ordering and Graph Splitting
The authors utilize node properties—most commonly node degree—to define a hierarchy. Based on this ordering, every edge $(v_i, v_j)$ in the graph is assigned to one of three mutually exclusive sets:
- Relation 1: $v_i \prec v_j$ (e.g., a message flowing from a low-degree node to a high-degree node).
- Relation 2: $v_j \prec v_i$ (e.g., a message flowing from a high-degree node to a low-degree node).
- Relation 3: "Others" (e.g., messages between nodes with the same degree).
2. Distinct Transformations
Crucially, each relation is processed using its own learnable weight matrix ($W_1, W_2, W_3$). The final node update is a combination of these separate message-passing streams. By using different transformations for different "types" of edges, the model can amplify different signals in different feature dimensions simultaneously, preventing the global convergence to a single signal.
Theoretical Insights
The effectiveness of MRS-MPNNs is rooted in the concept of structural independence. The authors prove that if nodes possess different "weighted in-degree vectors" across the split relations, their representations are guaranteed to remain linearly independent. Splitting a graph into Directed Acyclic Graphs (DAGs) naturally satisfies this condition, which is why the partial ordering approach is so effective. While various orderings (such as PageRank) are possible, node degree serves as a powerful and computationally efficient proxy, allowing the model to learn distinct logic for "hubs" versus "leaves" in the graph topology.
Experimental Evaluation
The authors evaluated MRS-MPNNs across a diverse range of benchmarks, including molecular graphs (ZINC), long-range benchmarks (LRGB), and heterophilic graphs where neighbors often have different labels (e.g., Roman-Empire, Snap-Patents).
Key Results
- Rank Preservation: Using the Rank-One Distance (ROD) metric, the study showed that standard GCN and GraphSAGE models collapse to a rank-one state within 25–50 layers. MRS versions maintained high ROD—indicating diverse, high-rank features—even at depths of 128 layers.
- Performance Gains: On the ZINC molecular dataset, MRS-GCN achieved a Test Mean Absolute Error (MAE) of 0.318, significantly better than the standard GCN's 0.404.
- State-of-the-Art on Heterophily: The MRS-DIR-GCN model achieved top-tier results on challenging heterophilic datasets, reaching 91.87% accuracy on Roman-Empire and 74.72% on Snap-Patents, outperforming specialized models like LinkX and ACM-GCN.
- Efficiency: Despite the increased complexity of processing three relations, the runtime overhead was approximately 35%, which is considered a manageable trade-off for the resulting performance and depth stability.
Discussion and Limitations
While MRS-MPNNs offer a robust solution to rank collapse, they introduce new considerations. The increased expressivity of the model carries a higher risk of overfitting, particularly on smaller datasets. Furthermore, the choice of node ordering is critical; while degree-based splitting is effective for many tasks, it may be sub-optimal for others. For instance, on standard homophilic datasets (like Cora), the split-by-degree approach performed slightly worse than standard GCNs, suggesting that in highly homophilic environments, the "smoothing" effect of traditional GNNs may actually serve as a helpful inductive bias.
Conclusion
MRS-MPNNs provide a theoretically grounded method for building deeper, more expressive Graph Neural Networks. By breaking the symmetry of standard message passing through graph splitting, the framework prevents representational rank collapse and enables GNNs to maintain informative node embeddings across many layers. Future work may involve exploring task-specific orderings, such as chemical properties for molecular graphs, to further refine the model's performance.
Summary updated