PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Dongkwan Kim, Alice Oh

arXiv:2204.04879v1cs.LGcs.AIcs.SIstat.ML

TL;DR

Graph attention is difficult to interpret and may learn poorly from noisy connections. SuperGAT self-supervises attention by predicting edges and selects attention designs using graph homophily and average degree; its recipe generalizes across real-world datasets and improves performance over baselines.

  • Problem

    Noisy graphs make it unclear what graph attention learns and can lead GNNs toward suboptimal representations.

  • Method

    SuperGAT self-supervises graph attention with edge-presence prediction and offers GO, DP, scaled dot-product, and mixed attention forms.

  • Results

    The attention-design recipe generalizes across real-world datasets, and models developed by the method improve performance over baselines.

  • Takeaways & Limitations

    Attention should be designed according to graph homophily and average degree because GO and DP differ in capturing label agreement and edge presence.

  • Takeaways & Limitations

    Mixed-distribution graphs such as Flickr and Crocodile can produce inconsistent results with the attention-design recipe.

Abstract

from arXiv · show

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, particularly when graphs are noisy. In this paper, we propose a self-supervised graph attention network (SuperGAT), an improved graph attention model for noisy graphs. Specifically, we exploit two attention forms compatible with a self-supervised task to predict edges, whose presence and absence contain the inherent information about the importance of the relationships between nodes. By encoding edges, SuperGAT learns more expressive attention in distinguishing mislinked neighbors. We find two graph characteristics influence the effectiveness of attention forms and self-supervision: homophily and average degree. Thus, our recipe provides guidance on which attention design to use when those two graph characteristics are known. Our experiment on 17 real-world datasets demonstrates that our recipe generalizes across 15 datasets of them, and our models designed by recipe show improved performance over baselines.

1 INTRODUCTION

SuperGAT addresses noisy graph representations by self-supervising attention with edge information and tailoring attention design to graph homophily and average degree. Its recipe generalizes across real-world datasets and improves performance over baselines.

  • Noisy connections between unrelated nodes can cause GNNs to learn suboptimal representations, motivating improved graph attention.
  • SuperGAT self-supervises attention using edge presence or absence as information about relational importance.
  • DP attention performs better at link prediction, whereas GO attention better captures label agreement between target nodes and neighbors.
  • Scaled dot-product and mixed GO-DP SuperGAT variants combine the strengths of the two attention mechanisms.
  • Attention design effectiveness depends on graph average degree and homophily, guiding a recipe for selecting attention mechanisms.
  • Experiments on 17 real-world datasets show that the recipe generalizes across them and that recipe-designed models improve performance over baselines.

2 RELATED WORK

Prior graph learning methods use self-attention, self-supervision, and graph structure learning, but existing structure-learning approaches can be computationally expensive. SuperGAT connects edge prediction with attention to learn graph structure more efficiently.

  • GNN research includes self-attention-based graph models whose attention variants are generally trained without direct supervision.
  • Self-supervised GNN tasks exploit graph structure through clustering, partitioning, masked-node context prediction, and masked-attribute completion.
  • SuperGAT uses edge-presence prediction to self-supervise graph attention, paralleling link prediction and dot-product edge reconstruction.
  • Graph structure learning jointly learns underlying graph structure and downstream tasks, but some methods require O(|V|^2) space and computation or time-intensive iterative training.
  • SuperGAT moderates these costs with parallelizable graph-attention operations and no additional parameters while learning attention values predictive of edges.

3 MODEL

SuperGAT augments graph attention with an edge-prediction objective: attention produces node-aggregation weights while a sigmoid score estimates edge probabilities. GO, DP, scaled dot-product, and mixed variants provide alternative designs.

  • A graph attention layer transforms node features, aggregates first-order neighbors with attention coefficients, and applies a nonlinear activation.
  • GO computes attention coefficients with a single-layer feed-forward network, while DP uses dot-product attention and a link-prediction score.
  • SuperGAT guides attention using edge labels, assigning one to linked node pairs and zero to unlinked pairs, then infers edge probability with a sigmoid.
  • The model provides four forms—GO, DP, scaled dot-product, and mixed GO-DP—with corresponding unnormalized attention and edge-probability designs.
  • Mixed GO-DP attention multiplies GO attention by sigmoid-transformed DP attention, softly downweighting neighbors unlikely to be linked.
  • Scaled dot-product divides node dot-products by the square root of feature dimension to prevent large values from dominating softmax attention.
  • Negative sampling avoids using every non-edge, selecting pn · |E| negative examples from the complement of the edge set.
  • SuperGAT combines node-label cross-entropy with self-supervised attention losses across layers and retains GAT’s time and space complexity without extra parameters.

4 EXPERIMENTS

The experiments evaluate what graph attention learns, how edge self-supervision affects it, and which attention design suits graphs with different homophily and average degree. They use KL divergence, link prediction, synthetic graphs, and 17 real-world datasets to assess these questions.

  • Research questions: The experiments ask whether graph attention captures label-agreement and predicts edge presence, then test which attention design suits different graph characteristics.The study focuses on homophily and average degree and examines generalization from synthetic to real-world datasets.
  • RQ1: Attention and label-agreement: Label-agreement is treated as relational-importance ground truth because attending to label-agreed neighbors helps preserve label distinctions in deep GATs.Attention is compared with label-agreement using KL divergence, whose smaller values indicate closer alignment.
  • RQ2: Attention and edge presence: Link prediction evaluates whether edge information is encoded in SuperGATGO and SuperGATDP using last-layer φij and AUC across multiple λE values.The experiments train with incomplete edges and test on missing edges and the same number of non-edges.
  • RQ3: Design choice: Synthetic random partition graphs vary average degree and homophily through within-class and between-class connection probabilities to compare attention designs.The graph generator controls average degree using pin + (c −1) · pout = δ.
  • RQ4: Real-world generalization: The evaluation covers 17 real-world datasets spanning citation, co-authorship, co-purchase, web-page, and biology domains, with scales from 2k to 169k nodes.The datasets include Cora, CiteSeer, PubMed, ogbn-arxiv, Flickr, and PPI, among others.
  • Experimental analysis: Figure 2 compares two-layer and four-layer GAT attention with label agreement using KL-divergence distributions across Cora nodes and layers.The distributions are long-tailed, and maximum KL divergence varies with node degree; uniform-attention distributions provide a reference.

5 RESULTS

The results show that GO better captures label agreement, whereas DP better predicts edge presence, and that graph characteristics determine which attention design performs best. A recipe based on homophily and average degree generalizes to 15 of 17 real-world datasets, while mixed or specialized designs yield context-dependent gains.

  • Attention analysis: GO attention learns label-agreement better than DP, while DP predicts edge presence better than GO.KLD analyses indicate GO resembles uniform attention, whereas DP diverges more from label-agreement distributions; link-prediction experiments favor DP.
  • Attention analysis: Increasing the self-supervision weight improves link prediction but generally reduces node-classification performance, revealing a trade-off between the two tasks.This pattern occurs for all datasets except PubMed at the largest tested coefficient, and it suggests that optimizing attention for edge prediction alone is insufficient.
  • Graph-aware design recipe: SuperGATSD performs best when homophily is low (≤0.2), because DP attention focuses on a small number of neighbors.At low homophily, performance gains over GAT increase with average degree up to around 10, indicating that sufficient edges provide more self-supervision.
  • Graph-aware design recipe: SuperGATMX performs better than or similarly to SuperGATSD when homophily exceeds 0.2 and average degree is neither too low nor too high.Mixing GO and DP combines label-agreement modeling with edge-presence modeling; when both graph characteristics are sufficiently high, all models can perform similarly.
  • Real-world validation: The design recipe generalizes to 15 of 17 real-world datasets, with SuperGATMX favored in nine datasets and no significant attention-model difference in five.Flickr and Crocodile show inconsistent results because their nodes mix more complex distributions of homophily and average degree.
  • Real-world validation: Across 17 datasets, SuperGAT outperforms GCN on 13, GAT on 12, and GraphSAGE on 16 datasets.The paper also reports that some iterative-training baselines achieve higher results in cases but require substantially more computation.

6 CONCLUSION

The paper concludes that self-supervised graph attention should be designed according to average degree and homophily, with recipe-based models outperforming baselines across varied real-world datasets.

  • SuperGAT self-supervises graph attention using edge information and designs attention architectures around graph characteristics.The conclusion identifies average degree and homophily as the guiding characteristics.
  • The analysis finds that original GAT and dot-product attention have difficulty encoding label-agreement and edge presence simultaneously.
  • The recipe generalizes across various real-world datasets, and recipe-designed models outperform other baseline models.
  • The evaluation covers citation, co-author, co-purchase, Wikipedia, university web-page, Flickr, and protein-interaction graphs.The datasets include seven citation networks, co-author networks, Amazon co-purchase graphs, Wikipedia networks, Four-Univ, Flickr, and PPI.
  • Real-world experiments use node-classification datasets alongside the inductive multi-label PPI benchmark.PPI contains 20 training graphs, two validation graphs, and two test graphs.

A.3 SYNTHETIC DATASET

The synthetic datasets vary graph average degree and homophily through δ and p_in, and visualize their resulting node-feature and edge structures with t-SNE.

  • Average degree increases with δ, while homophily increases with p_in in the synthetic graph construction.The relationships are d_avg = n · δ and h = p_in/δ.
  • Figure 6 shows t-SNE plots of node features and edges across δ values 0.025 and 0.2.Columns vary p_in across 0.1δ, 0.5δ, and 0.9δ.

A.4 DISTRIBUTION OF DEGREE AND HOMOPHILY OF DATASETS

The appendix examines degree and per-node homophily distributions in real-world graphs, identifying multimodal structure that limits the recipe’s fit for Flickr and Crocodile.

  • Per-node homophily is the ratio of same-label neighbors for each center node, while graph homophily averages this quantity across nodes.The appendix visualizes these distributions with kernel density estimation plots.
  • Flickr and Crocodile exhibit wider gaps between distribution modes than most datasets.Crocodile combines high-degree, low-homophily and low-degree, high-homophily modes; Flickr spans much of homophily at a specific degree.
  • The authors interpret mixed degree–homophily distributions as mixtures of sub-graphs and identify them as the reason the recipe does not fit Flickr and Crocodile.
  • The appendix focuses on regions outside degree-one nodes and zero per-node homophily because these leaf nodes do not significantly affect overall graph representation learning.

A.6 CGAT IMPLEMENTATION

The CGAT implementation adapts label-dependent auxiliary losses for semi-supervised learning, omits NINS, and validates the implementation against reported performance before timing models.

  • CGAT’s graph-structure and class-boundary losses use attention margins and unnormalized attention values over neighbor sets.The notation distinguishes one-hop neighbors, non-label-sharing neighbors, margins, and unnormalized attention.
  • Because CGAT’s losses include labels, the implementation uses only the graph-structure loss modified for semi-supervised learning.
  • The implementation uses modified losses and top-k softmax but omits NINS because of training and implementation complexity.For PPI, the same loss is used because multi-label cases could not be accurately implemented from the description.
  • The reproduced CGAT implementation achieves almost the same performance as the original paper in a full-supervised setting.SuperGAT and CGAT show almost similar performance in that setting.
  • Efficiency is measured by mean wall-clock training time over three runs on one GeForce GTX 1080Ti GPU, comparing SuperGAT with GAT and GAM.

B.2 FULL RESULT OF SYNTHETIC GRAPH EXPERIMENTS

The synthetic-graph experiments span controlled homophily and average-degree settings, while KL-divergence analyses compare how GO and DP attention align with label agreement across network depths.

  • Figure 8 compares KL divergence between normalized attention and label-agreement distributions for two-layer and four-layer GATs.
  • DP attention does not capture label agreement as well as GO attention.
  • The mismatch between DP attention and label agreement becomes stronger in deeper layers.

B.4 WALL-CLOCK TIME RESULT

The wall-clock analysis reports training time for GAT, GAM, and SuperGATMX, with Table 9 presenting mean times over three runs on real-world datasets.

  • Negative-edge sampling is the bottleneck in SuperGAT training.
  • GCN + GAM requires ×53.9–×328.1 the training time of GAT across all datasets.
  • SuperGATMX+ MPNS adds multiprocessing for sampling negative edges.
  • Figures 9–11 examine performance against λE, pn, and pe for SuperGATMX on citation networks and SuperGATSD on PPI.

B.5 SENSITIVITY ANALYSIS OF HYPER-PARAMETERS

Sensitivity analysis shows that edge-supervision strength and negative-sampling quantity have dataset-dependent optima, while edge-sampling effects vary substantially across datasets.

  • A specific λE range maximizes test performance across all datasets.On PPI, performance is largest at λE = 10^-3, with a relatively small difference from other settings.
  • Using too large λE degrades node-classification performance.
  • The optimal negative-sampling ratio is dataset-specific and remains below the number of positive samples, pn < 1.0.Increasing pn also increases GPU-memory requirements.
  • At pn = 5.0, PPI cannot fit the model and data on one GeForce GTX 1080Ti GPU.
  • Changing pe produces dataset-specific performance patterns: convex curves for Cora and PubMed, general decreases for CiteSeer, and no noticeable change for PPI.
Loading 2204.04879v1…