HoGA: Higher-Order Graph Attention via Diversity-Aware k-Hop Sampling
This addresses the problem of discovering higher-order relationships in graph learning for tasks like node classification, representing an incremental improvement over existing higher-order attention methods.
The paper tackled the limited expressive power of edge-based Message Passing Neural Networks (MPNNs) for capturing higher-order relationships in graphs by introducing the Higher-Order Graph Attention (HoGA) module, which achieved at least a 5% accuracy gain on all benchmark node classification datasets and outperformed recent baselines on six of eight datasets.
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. Code is available at https://github.com/TB862/Higher_Order.