How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision

Dongkwan Kim, Alice Oh

TL;DR

Researchers from KAIST have introduced SuperGAT, a self-supervised graph attention network that improves how models handle noisy data. By adding a secondary task—predicting whether an edge exists between two nodes—the model learns more expressive attention weights. The authors also provide a practical "recipe" that selects the best attention mechanism based on a graph's homophily and average degree.

What Problem Does This Paper Address?

Graph Attention Networks (GATs) are widely used to weigh the importance of neighboring nodes when learning representations. However, we don't fully understand what these models actually learn, especially when the input graphs are "noisy" (containing edges between unrelated nodes).

Standard GATs often struggle to distinguish between helpful neighbors and "mislinked" ones. Furthermore, the performance of different attention mechanisms (like additive vs. dot-product) varies wildly across different datasets, leaving researchers to guess which design will work best for their specific graph.

Methods

The authors propose SuperGAT, which incorporates a self-supervised link prediction task. The model doesn't just learn to classify nodes; it also learns to predict the likelihood of an edge existing between nodes $i$ and $j$ based on their attention values.

The paper explores two primary attention building blocks:

  1. GO (GAT Original): An additive mechanism using a single-layer neural network.
  2. DP (Dot-Product): A mechanism that calculates similarity via dot products.

From these, they develop two advanced variants:

  • SuperGAT$_{SD}$ (Scaled Dot-product): Prevents large values from dominating the attention distribution (similar to Transformers).
  • SuperGAT$_{MX}$ (Mixed): A hybrid that uses DP attention to "gate" GO attention, effectively dropping unlikely neighbors while retaining the expressive power of the additive model.
Architecture of SuperGAT variants (GO, DP, SD, MX) integrating self-supervised link prediction.

The core contribution is a "Recipe" for Graph Attention: a set of guidelines that tells you which version of SuperGAT to use based on two graph characteristics: Homophily (how similar neighbors are) and Average Degree (how dense the connections are).

Datasets

The authors conducted an extensive evaluation using:

  • 17 Real-World Datasets: Including classic benchmarks (Cora, CiteSeer, PubMed), large-scale citation networks (ogbn-arxiv), co-authorship networks (CS, Physics), and protein-protein interactions (PPI).
  • 144 Synthetic Graphs: Specifically generated to control for homophily (0.1 to 0.9) and average degree (1 to 100), allowing the authors to map out exactly where each attention design excels.

Key Insights and Ideas

  • The Specialization of Attention: The authors discovered a fundamental trade-off. GO attention is better at capturing "label agreement" (attending to neighbors with the same class), while DP attention is significantly better at predicting whether an edge actually exists.
  • The "Recipe" Logic:
    • If homophily is low ($\leq 0.2$), use SuperGAT$_{SD}$. In these noisy environments, dot-product attention helps the model focus on a very small number of potentially relevant neighbors.
  • If homophily is high and the degree is moderate, use SuperGAT$_{MX}$. This allows the model to benefit from both edge prediction and label agreement.
Performance of SuperGAT variants compared to the original GAT across varying homophily and average degree.
  • Self-Supervision as a Denoising Filter: By forcing the attention mechanism to be predictive of edges, the model naturally learns to assign lower weights to noisy, "mislinked" connections that don't fit the underlying structure.

Key Results

  • Broad Generalization: The proposed "recipe" correctly predicted the best-performing model for 15 out of 17 real-world datasets.
  • Performance Gains: SuperGAT outperformed standard GAT and GCN models across the majority of datasets. Notably, on the PubMed dataset, SuperGAT$_{MX}$ showed significant improvements over baselines.
  • Efficiency: While self-supervision adds some overhead, the authors introduced MPNS (Multi-Processing Negative Sampling), which reduces training time significantly, making SuperGAT competitive with standard models in wall-clock time.

Limitations and Future Work

  • Irregular Graph Distributions: The recipe struggled with two datasets (Flickr and Crocodile). The authors found these graphs have complex "mixture" distributions of degrees and homophily, meaning a single attention design might not fit the entire graph.
  • Degree Information: While SuperGAT handles noisy edges well, the authors note that GCNs sometimes still outperform attention-based models on specific datasets. They suggest future work should investigate how to better embed degree-normalized information directly into the attention mechanism.
  • Inductive vs. Transductive: While tested on both, further exploration into how self-supervision scales to extremely large-scale inductive settings remains an open area.

Summary updated

Abstract

Attention mechanism in graph neural networks is designed to assign larger weights to important neighbor nodes for better representation. However, what graph attention learns is not understood well,...
BibTeX
@inproceedings{kim2021how,
  author = {Dongkwan Kim and Alice Oh},
  title = {{How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=oJcIKxbkAc},
}
Figure