Abstract
Graph Neural Networks (GNNs) are powerful tools for relational data, yet they face a fundamental limitation: the inability to distinguish between nodes that are structurally identical but located in different parts of a graph. This paper introduces Stochastic Message Passing (SMP), a framework that resolves the theoretical "impossibility" trade-off between permutation-equivariance and proximity-awareness. By augmenting nodes with stochastic signatures that are propagated through the network, SMP allows GNNs to become both structurally and positionally sensitive.
The Proximity-Equivariance Trade-off
Most GNNs rely on a message-passing mechanism where a node’s representation is an aggregation of its neighbors' features. This leads to permutation-equivariance, ensuring that the model's output is independent of arbitrary node indexing. While beneficial for generalization, this property creates a blind spot. If two nodes have identical local structures (automorphisms), a standard GNN will assign them identical representations, regardless of their distance from each other.
This limitation makes it impossible for standard models to preserve node proximity, which is vital for tasks like link prediction or community detection. Previous attempts to address this, such as Position-aware GNNs (P-GNN), often broke permutation-equivariance or were computationally prohibitive.
Stochastic Message Passing (SMP)
The proposed SMP framework introduces a simple yet elegant solution to break symmetry:
- Symmetry Breaking: Every node is assigned a random initial "signature" vector $E$ sampled from a standard Gaussian distribution.
- Stochastic Propagation: These random signals are propagated across the graph using a GNN, creating a "stochastic representation" $\tilde{E}$ that captures the unique random signatures of a node's neighborhood.
- Hybrid Integration: This stochastic representation is concatenated with standard feature-based representations for downstream tasks.
The authors prove that with sufficient dimensionality, SMP can preserve walk-based proximities (like shortest paths) with high probability. The framework supports both linear instantiations for efficiency and non-linear extensions for complex tasks.
Experimental Evaluation
SMP was evaluated across ten diverse datasets, ranging from synthetic grids and community graphs to large-scale biological (PPI, PPA) and citation networks (Cora, PubMed).
Key Results
A critical "proof-of-concept" experiment highlighted SMP's unique capabilities. The task required identifying both a node's community (a proximity-based task) and its social status/centrality (a structural task).
As shown in the table above, SMP-Linear was the only model capable of excelling at both tasks simultaneously, achieving ~94% accuracy where standard GNNs and even P-GNN failed to capture one or both aspects effectively. Furthermore, on the large-scale PPA link prediction task, SMP-Linear achieved a Hits@100 of 0.3582, significantly outperforming GCN (0.1867).
Conclusion
Stochastic Message Passing provides a theoretically grounded and computationally efficient ($O(M)$) method for enhancing GNNs. By using randomness as a feature, SMP breaks the symmetry of standard message passing, allowing models to be proximity-aware while maintaining the essential property of permutation-equivariance. Future work may explore different noise distributions and the complex optimization landscapes of these stochastic models.
Summary updated