Permutation-Equivariant and Proximity-Aware Graph Neural Networks With Stochastic Message Passing

Ziwei Zhang, Chenhao Niu, Peng Cui, Jian Pei, Bo Zhang, Wenwu Zhu

TL;DR

This paper introduces Stochastic Message Passing (SMP), a novel Graph Neural Network (GNN) architecture that simultaneously preserves two crucial graph properties: permutation-equivariance and proximity-awareness. SMP achieves this by augmenting standard GNNs with stochastic node representations, enabling it to excel in tasks where both properties are essential, outperforming existing methods.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are powerful tools for learning on graph-structured data. However, many real-world graph tasks require GNNs to satisfy two key properties:

  1. Permutation-Equivariance: The model's output should change predictably if the order of nodes is permuted, reflecting the inherent symmetry of graphs. This is crucial for tasks like node classification or graph classification.
  2. Proximity-Awareness: The model should effectively capture how "close" or related nodes are to each other. This is vital for tasks like community detection or link prediction, where nodes within a community or likely to form a link are highly connected.

The authors argue that existing message-passing GNNs, while good at permutation-equivariance, often fail to preserve node proximities. Conversely, models designed for proximity-awareness might sacrifice permutation-equivariance. This creates a dilemma, as different tasks might require different balances of these properties, and existing models struggle to satisfy both simultaneously.

Methods

The core innovation is the Stochastic Message Passing (SMP) model. SMP augments existing GNN architectures with a novel component: stochastic node representations.

Here's how it works:

  • Stochastic Node Representations: For each node, SMP generates a random vector drawn from a distribution (e.g., Gaussian). These random vectors are independent of the graph structure itself, acting as a "symmetry breaker."
  • Message Passing on Stochastic Signals: A separate message-passing GNN is applied to these stochastic signals. This process allows nodes to exchange information through these random representations, theoretically enabling the preservation of node proximities.
  • Concatenation and Aggregation: The learned stochastic representations are then concatenated with the standard node representations learned by a permutation-equivariant GNN (which processes the graph's features and structure). This combined representation is then fed into an output layer.

The authors theoretically prove that this mechanism allows SMP to preserve walk-based proximities while maintaining permutation-equivariance. They also show that a simple, linear instantiation of SMP is often sufficient, making it computationally efficient.

Datasets

The paper evaluates SMP on a variety of datasets:

  • Simulation Datasets: Grid, Communities.
  • Communication Dataset: Email.
  • Coauthor Networks: CS, Physics.
  • Protein Interaction Networks: PPI, PPA.
  • Benchmark Datasets: Cora, CiteSeer, PubMed.

They also introduce a proof-of-concept synthetic dataset designed to specifically test the interplay between community structure (proximity-awareness) and social status (permutation-equivariance).

Key Insights and Ideas

  • Incompatibility of Properties: The paper rigorously demonstrates that standard permutation-equivariant GNNs cannot preserve arbitrary walk-based proximities, except in trivial cases. This is a fundamental limitation of existing architectures.
  • Stochasticity as a "Symmetry Breaker": The introduction of random, structure-agnostic node representations is a clever way to break the symmetry that prevents proximity preservation in traditional GNNs, without sacrificing permutation-equivariance.
  • Generality and Flexibility: SMP is presented as a general framework that can be applied to various GNN backbones, making it adaptable to different graph structures and tasks.
  • Efficiency of Linear SMP: The authors find that a simple, linear version of SMP is often as effective as more complex non-linear extensions, making it computationally efficient and scalable.

Key Results

  • Superior Performance: SMP consistently outperforms or is highly competitive with state-of-the-art baselines across various tasks, including link prediction, node classification, and pairwise node classification.
  • Link Prediction: SMP achieves the best AUC scores on a majority of datasets for link prediction, significantly outperforming permutation-equivariant GNNs and demonstrating its ability to capture node proximities.
  • Node Classification: On the synthetic dataset, SMP excels in predicting both community labels (proximity-aware) and social status (permutation-equivariant), while other models struggle with one or both.
  • Efficiency: SMP's computational complexity is comparable to simpler GNNs like SGC, making it significantly faster and less memory-intensive than proximity-aware methods like P-GNN, especially on large graphs.
  • Ablation Studies: The results suggest that while non-linear extensions can sometimes help, a linear SMP instantiation with a learnable output layer is often sufficient and robust.

Limitations and Future Work

  • Stochastic Signal Choice: The paper primarily uses Gaussian distributions for stochastic signals. Future work could explore other distributions or methods for generating these signals.
  • Non-linear Extensions: While linear SMP is effective, the paper acknowledges that more sophisticated non-linear extensions might further enhance expressiveness, though they come with increased complexity and risk of overfitting.
  • Inductive vs. Transductive Settings: The paper notes that fixing stochastic signals works better for transductive tasks, while resampling is preferred for inductive tasks. Further investigation into optimal strategies for different settings could be beneficial.
  • Theoretical Guarantees: While theoretical proofs are provided for proximity preservation, exploring deeper theoretical understanding of SMP's expressiveness and generalization capabilities remains an area for future research.

Summary updated

Abstract

Graph neural networks (GNNs) are emerging machine learning models on graphs. Permutation-equivariance and proximity-awareness are two important properties highly desirable for GNNs. Both properties are needed to tackle some challenging graph problems, such as finding communities and leaders. In this paper, we first analytically show that the existing GNNs, mostly based on the message-passing mechanism, cannot simultaneously preserve the two properties. Then, we propose Stochastic Message Passing (SMP) model, a general and simple GNN to maintain both proximity-awareness and permutation-equivariance. In order to preserve node proximities, we augment the existing GNNs with stochastic node representations. We theoretically prove that the mechanism can enable GNNs to preserve node proximities, and at the same time, maintain permutation-equivariance with certain parametrization. We report extensive experimental results on ten datasets and demonstrate the effectiveness and efficiency of SMP for various typical graph mining tasks, including graph reconstruction, node classification, and link prediction.
BibTeX
@article{zhang2023permutation,
  author = {Ziwei Zhang and Chenhao Niu and Peng Cui and Jian Pei and Bo Zhang and Wenwu Zhu},
  title = {{Permutation-Equivariant and Proximity-Aware Graph Neural Networks With Stochastic Message Passing}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  url = {https://openreview.net/forum?id=V0zTWlbvKO},
}
Figure