Higher Order Graph Attention Probabilistic Walk Networks

Thomas Bailie, Yun Sing Koh, Karthik Mukkavilli

TL;DR

This paper introduces HoGA, a novel graph attention module that captures higher-order relationships in graphs by intelligently sampling diverse k-hop neighborhoods. This approach significantly boosts performance on node classification tasks, outperforming existing methods by better capturing complex structural patterns often missed by traditional, local graph neural networks.

What Problem Does This Paper Address?

Message Passing Neural Networks (MPNNs) are powerful tools for analyzing graph-structured data, but they often suffer from a "locality bias." This means they primarily focus on direct connections (1-hop relationships) between nodes, neglecting potentially crucial information embedded in longer-range dependencies (k-hop relationships). This limitation can lead to a loss of important structural signals and theoretical bounds on what these models can detect. While some methods attempt to capture higher-order information, they often rely on greedy sampling strategies that can lead to redundant exploration of the k-hop feature space, limiting their effectiveness. The challenge is to efficiently and effectively capture these higher-order relationships without an exponential increase in computational cost.

Methods

The core contribution is the Higher-Order Graph Attention (HoGA) module. HoGA addresses the problem by:

  • Diversity-Aware k-Hop Sampling: Instead of greedily resampling similar k-hop relationships, HoGA employs a "heuristically guided walk" to sample subgraphs that maximize diversity among feature vectors. This ensures a broader and more representative capture of higher-order substructures.
  • k-Order Line Graph: HoGA constructs an attention matrix based on k-order line graphs, which represent relationships between nodes connected by paths of length k.
  • History Buffer: To avoid repetitive sampling and ensure tractability, HoGA utilizes a history buffer that keeps track of previously visited k-hop features. This heuristic walk balances global and local diversity metrics, enabling a high-fidelity approximation of the k-hop state space.
  • Integration with Existing Models: HoGA is designed to be a plug-and-play module that can be integrated into existing single-hop attention-based models, such as GAT and GRAND, by replacing their standard adjacency matrices with HoGA's higher-order attention matrix.

Datasets

The paper evaluates HoGA on several standard benchmark node classification datasets:

  • Homophilic Datasets: Cora, Citeseer, Pubmed, Computers, Actor, Photo, Wisconsin, Texas.
  • Heterophilic Datasets: Wisconsin, Texas.

The paper uses public train, test, and validation splits for Cora, Citeseer, and Pubmed, as proposed in the original paper [44]. For other datasets, they employ a random split of 60% train, 20% validation, and 20% test.

Key Insights and Ideas

  • Diversity is Key: The paper strongly emphasizes that maximizing diversity in sampled k-hop neighborhoods is crucial for capturing complex graph structures, rather than simply sampling more or greedier paths.
  • Heuristic Walk Outperforms Greedy: The proposed heuristic walk, which considers feature diversity and a history buffer, significantly outperforms greedy sampling methods in capturing higher-order relationships.
  • HoGA is Generalizable: The module can be seamlessly integrated into existing popular GNN architectures (GAT, GRAND), demonstrating its versatility and broad applicability.
  • Mitigating Oversmoothing: By accessing more diverse higher-order information, HoGA appears to help mitigate the oversmoothing problem, where node representations become too similar in deep GNNs.

Key Results

  • Accuracy Gains: HoGA-enhanced models (HoGA-GAT and HoGA-GRAND) achieved substantial accuracy gains on node classification tasks. They reported at least a 5% accuracy gain on all benchmark datasets and outperformed recent baselines on six out of eight datasets.
  • Outperforming Baselines: HoGA-GAT and HoGA-GRAND consistently achieved higher accuracy compared to their single-hop counterparts and other state-of-the-art higher-order attention methods. For instance, HoGA-GAT showed significant improvements on Citeseer, Computers, and Actor datasets.
  • Robustness to Hop Number: The models showed stable performance with varying maximum hop numbers (K), typically plateauing around K=3, indicating that the higher-order information is effectively captured.
  • Runtime and Memory: While there is some overhead, the HoGA module remains computationally feasible, with runtime and GPU memory usage comparable to other advanced baselines.

Limitations and Future Work

  • Heterophily Sensitivity: While HoGA helps counteract heterophily effects, the paper notes that HoGA-GRAND's accuracy typically decays after 3-hops on heterophilic datasets, indicating heightened sensitivity to repeated information.
  • Computational Cost: Although manageable, the k-hop sampling process inherently adds computational cost compared to purely 1-hop methods. The paper mentions that increasing the number of sampled edges from the k-order line graph tends to increase accuracy but also computational cost.
  • Future Work: The authors suggest further exploration of the heuristic walk's hyperparameters and its application to other graph-based tasks beyond node classification. They also hint at the potential for HoGA to be applied in more complex scenarios where higher-order dependencies are critical.

Summary updated

BibTeX
@inproceedings{bailie2026higher,
  author = {Thomas Bailie and Yun Sing Koh and Karthik Mukkavilli},
  title = {{Higher Order Graph Attention Probabilistic Walk Networks}},
  booktitle = {WSDM},
  year = {2026},
  doi = {10.1145/3773966.3777960},
}
Figure