Research map / Graph learning / GNN architectures
HONGAT: Graph Attention Networks in the Presence of High-Order Neighbors
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes HONGAT, a graph attention network that adds K-order common-neighbor similarity and a learnable multi-range masking matrix so nodes can attend to high-order neighbors without over-smoothing.
Problem
Standard graph attention networks only attend to one-hop neighbors, leaving useful high-order neighbors unexploited, while simply stacking layers causes over-smoothing.
Approach
Generalizes the common neighbors index to K-order topological similarity (a polynomial of the normalized adjacency) combined with GAT's feature attention, and uses a learnable binary masking matrix over polynomial orders to adaptively set the averaging range and mitigate over-smoothing.
Key results
- HONGAT reaches 83.1% on Cora, 69.5% on Citeseer and 81.1% on Pubmed, outperforming GAT (81.2%, 68.4%, 78.9%) and ADSF (82.3%, 69.1%, 80.0%).
- GAT10 degrades sharply to 66.3% on Cora, 20.8% on Citeseer, 42.3% on Pubmed, showing over-smoothing in deep GATs.
- Removing the masking matrix (HONGAT†) lowers accuracy to 82.1% on Cora, 69.3% on Citeseer and 80.7% on Pubmed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add high-order common-neighbor topology and masking to GAT | GAT · Cora | accuracy: 2.3% | Helped |
| add high-order common-neighbor topology and masking to GAT | GAT · Citeseer | accuracy: 1.6% | Helped |
| add high-order common-neighbor topology and masking to GAT | GAT · Pubmed | accuracy: 2.7% | Helped |
| add the masking matrix (ablation) | HONGAT · Cora | accuracy: 82.1±1.5% -> 83.1±1.0% | Helped |
| add the masking matrix (ablation) | HONGAT · Citeseer | accuracy: 69.3±1.4% -> 69.5±1.2% | Helped |
| add the masking matrix (ablation) | HONGAT · Pubmed | accuracy: 80.7±1.3% -> 81.1±0.8% | Helped |
| add topological similarity while retaining masking (ablation) | HONGAT · Cora | accuracy: 20.5±4.9% -> 83.1±1.0% | Helped |
| add topological similarity while retaining masking (ablation) | HONGAT · Citeseer | accuracy: 27.9±6.1% -> 69.5±1.2% | Helped |
| add topological similarity while retaining masking (ablation) | HONGAT · Pubmed | accuracy: 43.6±5.4% -> 81.1±0.8% | Helped |
| add topological similarity and masking instead of semantic-only attention (ablation) | HONGAT · Cora | accuracy: 18.0±6.5% -> 83.1±1.0% | Helped |
| add topological similarity and masking instead of semantic-only attention (ablation) | HONGAT · Citeseer | accuracy: 18.6±1.8% -> 69.5±1.2% | Helped |
| add topological similarity and masking instead of semantic-only attention (ablation) | HONGAT · Pubmed | accuracy: 30.1±4.1% -> 81.1±0.8% | Helped |
Surprising findings
- Deep 10-layer GAT collapses to 20.8% on Citeseer, indicating severe over-smoothing at matched receptive field.
- Using only topological common-neighbor similarity (w/o SEM) performs close to full HONGAT on Cora and Pubmed, though removing topology entirely (w/o TOPO1/TOPO2) causes large drops.
Limitations
- Evaluated only on three small citation benchmarks (Cora, Citeseer, Pubmed) in the main text; large and heterophilic datasets are only in the appendix.
- Precomputing high-order polynomial operators costs O(K|E|n) and may be expensive for large graphs.
Experimental setup
Datasets: Cora Citeseer Pubmed
Benchmarks: Cora Citeseer Pubmed
Metrics: classification accuracy (mean ± std over 10 runs)
Baselines: MLP DeepWalk Chebyshev JKNet SGC GCN APPNP GPR-GNN S2GC SIGN GAT GAT3
Builds on: GAT JKNet SPAGAN ADSF
Closest papers by meaning
- Graph Attention Networks (ICLR 2018 · similarity 0.89)
- GATE: How to Keep Out Intrusive Neighbors (ICML 2024 · similarity 0.88)
- Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models (ICML 2025 · similarity 0.87)
- Less is More: on the Over-Globalizing Problem in Graph Transformers (ICML 2024 · similarity 0.86)
- A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks (ICML 2025 · similarity 0.86)
- Graph External Attention Enhanced Transformer (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.