Improving Graph Attention Networks with Large Margin-based Constraints

Guangtao Wang, Rex Ying, Jing Huang, Jure LeskovecarXiv 2019 · arXiv

Introduction

Graph Attention Networks (GATs) have emerged as a cornerstone for learning on graph-structured data, leveraging attention mechanisms to weigh neighbor contributions dynamically. Despite their success, GATs are plagued by two significant issues: overfitting due to a lack of direct supervision for attention weights, and "over-smoothing," where stacking multiple layers causes node representations to converge and become indistinguishable. This paper by Wang et al. introduces Constrained Graph Attention Networks (C-GAT), a framework designed to mitigate these challenges through margin-based constraints.

Problem Statement: Overfitting and Over-smoothing

Standard GATs often learn complex attention patterns that do not generalize well to unseen graph structures. Furthermore, as network depth increases, GATs tend to "bleed" information across class boundaries. The authors provide a mathematical proof demonstrating that a standard GAT layer acts as a form of Laplacian smoothing. In deep architectures, this process converges to a state where all nodes in a connected component share identical features, rendering the model ineffective for node classification.

Methodology: The C-GAT Framework

To address these limitations, C-GAT introduces three primary innovations centered around forcing attention weights to respect both graph topology and semantic boundaries.

1. Margin-based Constraints

C-GAT incorporates two additional loss functions during training:

  • Graph Structure Constraint: This ensures the model assigns significantly higher attention to direct (1-hop) neighbors compared to distant or unreachable nodes.
  • Class Boundary Constraint: This forces the model to prioritize neighbors sharing the same class label, effectively penalizing attention directed toward nodes across decision boundaries.
Conceptual diagram of Graph Structure and Class Boundary constraints.

2. Constrained Feature Aggregation (Top-k)

Rather than aggregating information from the entire neighborhood, C-GAT employs a hard filter, listening only to the top-$k$ neighbors with the highest attention weights. This mechanism acts as a robust defense against "noisy" edges that might connect disparate classes.

3. Adaptive Negative Sampling

To optimize the training of the structure constraint, the authors utilize a layer-wise sampling strategy. This identifies "informative" negative nodes—distant nodes that the model is likely to misidentify as relevant—rather than relying on simple random sampling.

Experimental Results

The C-GAT framework was evaluated on standard benchmarks, including citation networks (Cora, Citeseer, Pubmed) and protein-protein interaction (PPI) graphs. C-GAT consistently outperformed baseline models like GCN, GraphSAGE, and standard GAT, achieving a state-of-the-art accuracy of 98.8% on the PPI dataset.

Solving the Depth Issue

A critical finding was C-GAT's resilience to increasing network depth. While standard GAT performance drops sharply beyond a few layers due to over-smoothing, C-GAT maintains high accuracy even at 8 layers.

Comparison of GAT and C-GAT accuracy across different network depths (2, 4, and 8 layers).

Robustness to Noise

The model also demonstrated exceptional stability in the presence of noise. In experiments where random edges were added to the Cora dataset, C-GAT's performance remained nearly flat, whereas standard GAT's accuracy plummeted. The margin constraints effectively allow the attention mechanism to act as a "data cleaner," pruning irrelevant or noisy connections during the forward pass.

Conclusion

C-GAT provides a robust solution to the fundamental limitations of Graph Attention Networks. By introducing margin-based constraints and top-$k$ aggregation, the framework prevents over-smoothing and overfitting, enabling the training of deeper and more noise-resistant models. Future work may involve extending these constraints to unsupervised settings and other graph-based tasks like link prediction.

Summary updated

Abstract

Graph Attention Networks (GATs) are the state-of-the-art neural architecture for representation learning with graphs. GATs learn attention functions that assign weights to nodes so that different nodes have different influences in the feature aggregation steps. In practice, however, induced attention functions are prone to over-fitting due to the increasing number of parameters and the lack of direct supervision on attention weights. GATs also suffer from over-smoothing at the decision boundary of nodes. Here we propose a framework to address their weaknesses via margin-based constraints on attention during training. We first theoretically demonstrate the over-smoothing behavior of GATs and then develop an approach using constraint on the attention weights according to the class boundary and feature aggregation pattern. Furthermore, to alleviate the over-fitting problem, we propose additional constraints on the graph structure. Extensive experiments and ablation studies on common benchmark datasets demonstrate the effectiveness of our method, which leads to significant improvements over the previous state-of-the-art graph attention methods on all datasets.
BibTeX
@misc{wang2019improving,
  author = {Guangtao Wang and Rex Ying and Jing Huang and Jure Leskovec},
  title = {{Improving Graph Attention Networks with Large Margin-based Constraints}},
  year = {2019},
  eprint = {1910.11945},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.11945},
}
Figure