Abstract
Graphs model latent variable relationships in many real-world systems, and Message Passing Neural Networks (MPNNs) are widely used to learn such structures for downstream tasks. While edge-based MPNNs effectively capture local interactions, their expressive power is theoretically bounded, limiting the discovery of higher-order relationships. We introduce the Higher-Order Graph Attention (HoGA) module, which constructs a k-order attention matrix by sampling subgraphs to maximize diversity among feature vectors. Unlike existing higher-order attention methods that greedily resample similar k-order relationships, HoGA targets diverse modalities in higher-order topology, reducing redundancy and expanding the range of captured substructures. Applied to two single-hop attention models, HoGA achieves at least a 5% accuracy gain on all benchmark node classification datasets and outperforms recent baselines on six of eight datasets.
Introduction: Beyond the Locality Bias
Most modern Message Passing Neural Networks (MPNNs) are inherently "single-hop" models. They update node representations by aggregating information from immediate neighbors. While computationally efficient, this design choice introduces a significant locality bias. In many real-world graphs—ranging from molecular structures to social networks—critical patterns are often found in higher-order relationships that span multiple hops.
Existing attempts to capture these long-range dependencies often struggle with the "exponential explosion" of possible paths as the distance $k$ increases. Furthermore, standard sampling methods tend to be "greedy," repeatedly visiting similar nodes and creating informational redundancy. The Higher-Order Graph Attention (HoGA) module addresses these challenges by prioritizing diversity over density during the exploration of the graph topology.
Methodology: The Heuristic Probabilistic Walk
The core of HoGA is a novel sampling strategy called the Heuristic Probabilistic Walk. This approach moves beyond simple random walks by balancing two competing objectives to ensure the model captures a broad spectrum of the graph's feature space:
- Local Diversity: The walker is biased toward nodes whose feature vectors are most distinct from the current node's representation. This prevents the model from getting bogged down in clusters of highly similar nodes.
- Global Diversity (The History Buffer): To avoid the cycles and redundancy common in greedy methods, HoGA maintains a history buffer of previously encountered feature "concepts." The walker is actively discouraged from revisiting feature modalities it has already seen, forcing it to explore novel regions of the $k$-hop neighborhood.
Architecture and Integration
Once the diverse $k$-hop relationships are sampled, they are integrated into a higher-order attention matrix. HoGA employs a weighting function, $eta(k)$, to scale the importance of messages based on their distance from the target node. By using a harmonic series for this weighting, the model effectively mitigates "oversquashing," a common issue where long-range signals are drowned out by local noise.
This modular design allows HoGA to be integrated into existing GNN architectures like Graph Attention Networks (GAT) or Graph Neural Diffusion (GRAND) with minimal overhead.
Experimental Results and Key Insights
The researchers evaluated HoGA across eight benchmark datasets, including both homophilic (where similar nodes connect) and heterophilic (where dissimilar nodes connect) graphs.
- Significant Performance Gains: HoGA-enhanced models achieved a minimum of 5% accuracy improvement across all benchmarks.
- The Actor Breakthrough: On the Actor dataset, which features complex, non-trivial topologies, HoGA-GAT demonstrated a massive 20% improvement over the base GAT model.
- Stability and Depth: Unlike standard GNNs that suffer from "oversmoothing" (where node features become indistinguishable in deep layers), HoGA's ability to reach across multiple hops allows it to maintain descriptive, distinct node representations even as network depth increases.
Conclusion
HoGA demonstrates that what a model samples is more important than how much it samples. By replacing redundant, greedy exploration with a diversity-aware heuristic, HoGA provides a more representative sketch of a graph's higher-order topology. This approach not only improves classification accuracy but also provides a robust framework for overcoming the traditional limitations of locality bias and over-smoothing in graph representation learning.
Summary updated