PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Graph Attention Networks

Yang Ye, Shihao Ji

arXiv:1912.00552v2cs.LGstat.ML

TL;DR

GATs can be redundant and vulnerable to noisy neighborhoods, especially on disassortative graphs. SGAT learns sparse, shared edge attentions with L0 regularization, producing an edge-sparsified graph that preserves or improves classification accuracy, though sparsity does not automatically reduce runtime or memory use.

  • Problem

    GATs assign multiple layer- and head-specific coefficients to edges, creating redundancy, while local aggregation can fail on noisy disassortative graphs.

  • Method

    SGAT uses L0-norm regularization and shares one sparse attention coefficient per edge across all heads and GNN layers.

  • Results

    SGAT identifies removable noisy edges and achieves similar or improved classification accuracy across assortative and disassortative graphs.

  • Takeaways & Limitations

    Edge-sparsified graphs can retain or exceed the predictive performance of original graphs, indicating substantial graph-edge redundancy.

  • Takeaways & Limitations

    Despite pruning many edges, SGAT has similar overall runtime and memory consumption to GAT because sparse-attention learning and feature storage remain costly.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have proved to be an effective representation learning framework for graph-structured data, and have achieved state-of-the-art performance on many practical predictive tasks, such as node classification, link prediction and graph classification. Among the variants of GNNs, Graph Attention Networks (GATs) learn to assign dense attention coefficients over all neighbors of a node for feature aggregation, and improve the performance of many graph learning tasks. However, real-world graphs are often very large and noisy, and GATs are prone to overfitting if not regularized properly. Even worse, the local aggregation mechanism of GATs may fail on disassortative graphs, where nodes within local neighborhood provide more noise than useful information for feature aggregation. In this paper, we propose Sparse Graph Attention Networks (SGATs) that learn sparse attention coefficients under an $L_0$-norm regularization, and the learned sparse attentions are then used for all GNN layers, resulting in an edge-sparsified graph. By doing so, we can identify noisy/task-irrelevant edges, and thus perform feature aggregation on most informative neighbors. Extensive experiments on synthetic and real-world graph learning benchmarks demonstrate the superior performance of SGATs. In particular, SGATs can remove about 50\%-80\% edges from large assortative graphs, while retaining similar classification accuracies. On disassortative graphs, SGATs prune majority of noisy edges and outperform GATs in classification accuracies by significant margins. Furthermore, the removed edges can be interpreted intuitively and quantitatively. To the best of our knowledge, this is the first graph learning algorithm that shows significant redundancies in graphs and edge-sparsified graphs can achieve similar or sometimes higher predictive performances than original graphs.

1 INTRODUCTION

GNNs learn representations by exploiting graph structure, while neighbor aggregation methods extend convolution to irregular graphs. GATs adaptively weight neighbors but can exhibit substantial redundancy and overhead from multi-head, layer-specific attention.

  • GNNs learn node embeddings for graph tasks including link prediction, graph classification, and node classification.
  • Neighbor aggregation methods update each node by aggregating its neighbors’ features with shared parameterized functions.Stacking k layers enables aggregation from k-hop neighborhoods.
  • GATs calculate feature-dependent edge weights and attend adaptively over all neighbors, using multi-head attention to increase expressiveness.
  • A 2-layer, 8-head GAT assigns 16 attention coefficients to each edge, creating computation, memory, and overfitting concerns.
  • SGAT simplifies GAT modeling by assigning one attention coefficient to each edge across all GNN layers.

2 BACKGROUND AND RELATED WORK

The background reviews graph notation, neighbor aggregation, GATs, and graph sparsification. SGAT differs from prior approaches by learning a permanent task-oriented edge-sparsified graph through sparse attention.

  • Graph notation: A graph G = (V, E) consists of nodes V connected by edges E, with node features stored in X and structure represented by adjacency matrix A.Adding self-loops gives the augmented adjacency matrix ˜A = A + I_N.
  • Neighbor aggregation methods: Neighbor aggregation maps a node’s features and its neighbors’ features to a new representation using a parameter-sharing aggregator.
  • Neighbor aggregation methods: GCNs use symmetrically normalized adjacency coefficients shared across layers, while GraphSage learns aggregators and samples neighbors for large-scale or inductive learning.
  • Graph Attention Networks: GATs learn attention coefficients from node features for neighbor aggregation, with different attention functions across layers and multiple independently computed heads.
  • Sparse graph attention: SGAT applies L0-norm regularization and one attention coefficient per edge across all layers to remove noisy or task-irrelevant edges.The resulting sparse graph can retain similar or higher predictive performance.
  • Graph sparsification: Prior sparsification methods include spectral compression and stochastic DropEdge, but they do not generally learn a permanent task-oriented sparse graph for classification.DropEdge removes different edges during training and uses the full graph at validation and test time.
  • Graph sparsification: SGAT is presented as addressing the lack of prior methods that retain similar or improved accuracy on both assortative and noisy disassortative graphs.

3 SPARSE GRAPH ATTENTION NETWORKS

SGATs sparsify graph attention by learning binary edge gates with L0 regularization and sharing one attention coefficient per edge across all layers. A stochastic hard-concrete optimization procedure makes these discrete masks trainable and yields an edge-sparsified graph.

  • Sparse attention formulation: SGAT attaches a binary gate to each edge and optimizes model parameters and gates with an L0-regularized loss.The gates determine whether edges participate in neighbor aggregation.
  • Sparse attention formulation: Each edge receives one attention coefficient shared across all layers, unlike GAT’s layer-dependent coefficients.Directed edges are treated separately, so eij and eji have distinct gates.
  • Sparse attention formulation: Attention coefficients are computed by row-wise normalization of the gated adjacency matrix rather than GAT’s softmax normalization.The binary gates and nonnegative adjacency entries make the gated products nonnegative.
  • Sparse attention formulation: One shared coefficient set is computationally K times cheaper than multiple sets and can serve as interpretable edge-importance scores.The paper links this design to lower overfitting risk and removal of noisy or task-irrelevant edges.
  • Model optimization: The hard-concrete estimator provides a differentiable surrogate for optimizing binary masks whose expectation-based objective has an intractable gradient.During training, log αij is optimized; at test time, a deterministic mask is generated.
  • Model optimization: The sampled mask produces an edge-sparsified graph for downstream classification, with continuous training values ideally concentrating many mask elements at zero.The paper’s inductive pipeline generates masks for new edges from node-pair features.

4 EVALUATION

The evaluation covers synthetic and real-world graph datasets spanning assortative and disassortative structures, with both transductive and inductive node-classification settings. Comparisons include established GNN baselines and graph-sparsification methods.

  • Evaluation scope: SGAT is evaluated on synthetic and real-world semi-supervised node-classification benchmarks in both transductive and inductive settings.The benchmark suite includes seven assortative and four disassortative graphs.
  • Baselines: The comparison set includes GCN, GraphSage, GAT, SuperGAT, DropEdge, and PTDNet.Experiments follow the configurations of the competing algorithms.
  • Graph datasets: Assortative graphs provide useful local neighborhood information, whereas disassortative graphs provide more noisy than useful local features.The paper evaluates both types to assess pruning of redundant and noisy edges.
  • Transductive learning tasks: Transductive experiments use Cora, Citeseer, Pubmed, Amazon Computers, and Amazon Photo for document and product classification.Test graphs are included in training graphs for feature aggregation.
  • Inductive learning tasks: Inductive experiments use PPI and Reddit, where test graphs are excluded during parameter learning and test-node representations are generated from trained aggregators.PPI contains 24 subgraphs, with 20 for training, 2 for validation, and 2 for testing.

4.2 Models and Experimental Setup

The experiments use a two-layer, two-head SGAT for node classification, compare it with matched GAT variants and other state-of-the-art models, and report both accuracy and graph sparsity.

  • Models and setup: The main model is a 2-layer SGAT with 2-head attention at each layer followed by a softmax classifier.ReLU activations and Adam optimization are used with learning rate lr = 1e−2.
  • Models and setup: SGAT is compared with state-of-the-art models using node-classification accuracy and percentage of edges removed.The edge-removal metric reflects the sparsified graph induced by SGAT.
  • Baselines: GAT-2head-top-k matches SGAT-2head’s architecture but removes the top-k smallest dense-attention coefficients instead of using L0-induced sparse coefficients.The baseline is designed to isolate the sparse-attention mechanism’s effectiveness.
  • Baselines: Matched 1-head and 2-head GAT models are run to compare sparse attention with standard dense attention.L2 regularization and dropout are used to reduce overfitting on small datasets.

4.3 Experiments on Synthetic Dataset

On Zachary’s Karate Club, SGAT progressively removes insignificant edges while preserving high classification accuracy. Its final sparsified graph removes nearly half the edges and matches competing full-graph methods.

  • Synthetic dataset: Zachary’s Karate Club contains 34 members linked by outside-club interactions, with the task predicting post-split group memberships.Only the instructor and administrator are labeled, making the task semi-supervised.
  • Synthetic results: 46% of edges are removed while SGAT retains 96.88% accuracy, matching GCN and other full-graph competitors.Only one node is misclassified at the end of training.
  • Synthetic results: SGAT’s edge removals can reflect asymmetric neighborhood importance, such as removing one direction of an edge while retaining the reverse.The paper explains this using different neighbor counts for the two incident nodes.

4.4 Experiments on Assortative Graphs

On assortative graphs, SGAT maintains competitive classification accuracy while removing redundant or task-irrelevant edges, with especially large sparsification on larger or denser benchmarks.

  • SGAT outperforms GCN and GraphSage on PPI while achieving similar accuracies on the other assortative benchmarks.
  • SGAT removes 46% of Karate Club edges while retaining 96.88% accuracy, matching competing methods using the full graph.
  • On Reddit, SGATs outperform GATs by 2-3% while sparsifying the graph by 80.8%.
  • SGAT-2head outperforms GAT-2head-top-k by 1%-4% on larger benchmarks when a large percentage of edges is removed.
  • On small citation networks, SGAT removes only 1-2% of edges, whereas large or dense assortative graphs contain 40-80% removable redundancy with no or minor accuracy losses.

4.5 Experiments on Disassortative Graphs

On disassortative graphs, noisy neighbors undermine local aggregation, while SGAT achieves the best reported accuracies by pruning most edges before feature aggregation.

  • Disassortative graphs have H(G) values around 0.1-0.2, indicating that most neighboring nodes have different labels.
  • Neighbor aggregation methods such as GAT, GCN, and GraphSage fail to learn good representations when neighborhood features are extremely noisy.
  • The comparison includes GAT, Geom-GCN, MLP, DropEdge, SuperGAT, and PTDNet under the reported experimental settings.
  • SGAT achieves the best accuracies among the evaluated algorithms on the four disassortative graphs.
  • SGAT keeps less than 10% of edges for feature aggregation across all evaluated disassortative graphs.

4.6 Analysis of Removed Edges

SGAT identifies edges whose removal has different effects on classification accuracy, revealing substantial redundancy in some graphs. On PPI, learned edge importance is more informative than random or bottom-ranked removal.

  • 49.3% of PPI edges and over 88.1% of Texas edges are removed, indicating substantial edge redundancy.
  • 2% of Cora edges are removed slowly during training because Cora is a sparse graph.
  • Fig. 4 tracks classification accuracy and kept-edge counts across training epochs on Cora, PPI, and Texas.
  • Removing top-k% edges ranked by log αij causes dramatically greater accuracy loss than random or bottom-k% removal on PPI.
  • Fig. 5 compares PPI classification accuracies under different edge-removal percentages and three edge-selection strategies.

4.7 Hyperparameter Tuning

Hyperparameter studies examine how sparsity regularization and attention-head count affect SGAT’s accuracy–sparsity trade-off. Their effects differ across datasets, with two heads performing best or nearly best on PPI and Texas.

  • λ tuning: Increasing λ strengthens L0 regularization and prunes more edges.
  • λ tuning: Fig. 6 measures λ’s impact on classification accuracy and edge sparsity on PPI and Texas validation datasets.
  • λ tuning: When λ ≤ 2e −6 on PPI, accuracy changes little, but it drops significantly when λ > 2e −6.
  • Number of heads: K = 2 yields the best or close-to-best SGAT accuracies on both PPI and Texas.
  • Number of heads: Fig. 7 plots SGAT classification accuracy against the number of heads on PPI and Texas.
  • Feature representations: The learned penultimate-layer feature representations are visualized with t-SNE on Cora and Texas.

4.9 Discussion

SGAT can remove many edges while preserving or improving classification accuracy, but this sparsification does not automatically reduce runtime or memory use. A proposed training shortcut remains approximate and may reduce accuracy.

  • SGAT is not faster or more memory efficient than GAT despite removing many edges.Learning sparse coefficients has similar complexity to dense attention, while feature representations consume most memory.
  • Skipping computation for edges with z ≈ 0 could speed training, but those edges may reactivate later.
  • The proposed z ≈ 0 training heuristic is approximate and potentially causes an accuracy drop.
  • SGAT identifies noisy or task-irrelevant edges on assortative and disassortative graphs while achieving similar or improved classification accuracy.

5 CONCLUSION

SGAT combines sparse attention with L0 regularization and shared edge coefficients to remove noisy edges while maintaining or improving downstream classification accuracy. Experiments across assortative and disassortative graphs support its robustness, while future work targets adversarial edges and unsupervised domain adaptation.

  • SGAT applies L0-norm regularization and shares one attention-coefficient set across all heads and layers.
  • The resulting algorithm detects and removes noisy or task-irrelevant edges while achieving similar or improved downstream classification accuracy.
  • Experiments on seven assortative and four disassortative graphs demonstrate SGAT’s robustness.
  • Future extensions include detecting superficial or malicious adversarial edges and applying sparse attention to unsupervised graph domain adaptation.
Loading 1912.00552v2…