PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-hop Attention Graph Neural Network

Guangtao Wang, Rex Ying, Jing Huang, Jure Leskovec

arXiv:2009.14332v5cs.LGstat.ML

TL;DR

Existing graph attention models mainly use directly connected node pairs, limiting each layer's receptive field and omitting useful multi-hop context. MAGNA diffuses edge attention across paths to create context-dependent multi-hop attention, and it improves results across node classification and knowledge graph completion benchmarks.

  • Problem

    Graph attention is computed over connected pairs and depends on their representations, leaving multi-hop neighboring context outside each layer's attention computation.

  • Method

    MAGNA computes edge attention and diffuses it to disconnected node pairs, aggregating attention over paths to enable context-dependent multi-hop interactions.

  • Results

    MAGNA improves state-of-the-art results across node classification and knowledge graph completion, including up to 5.7% relative error reduction and a 7.1% Hit at 1 gain.

  • Takeaways & Limitations

    MAGNA captures large-scale structural information, suppresses higher-frequency graph information, and enables effective long-range message passing within graph attention layers.

Abstract

from arXiv · show

Self-attention mechanism in graph neural networks (GNNs) led to state-of-the-art performance on many graph representation learning tasks. Currently, at every layer, attention is computed between connected pairs of nodes and depends solely on the representation of the two nodes. However, such attention mechanism does not account for nodes that are not directly connected but provide important network context. Here we propose Multi-hop Attention Graph Neural Network (MAGNA), a principled way to incorporate multi-hop context information into every layer of attention computation. MAGNA diffuses the attention scores across the network, which increases the receptive field for every layer of the GNN. Unlike previous approaches, MAGNA uses a diffusion prior on attention values, to efficiently account for all paths between the pair of disconnected nodes. We demonstrate in theory and experiments that MAGNA captures large-scale structural information in every layer, and has a low-pass effect that eliminates noisy high-frequency information from graph data. Experimental results on node classification as well as the knowledge graph completion benchmarks show that MAGNA achieves state-of-the-art results: MAGNA achieves up to 5.7 percent relative error reduction over the previous state-of-the-art on Cora, Citeseer, and Pubmed. MAGNA also obtains the best performance on a large-scale Open Graph Benchmark dataset. On knowledge graph completion MAGNA advances state-of-the-art on WN18RR and FB15k-237 across four different performance metrics.

1 Introduction

MAGNA extends graph attention beyond immediate neighbors by diffusing edge attention across multi-hop paths, making attention context-dependent within each layer. The method is supported by spectral analysis and experiments showing stronger structural modeling and improved benchmark performance.

  • Motivation: GAT attention is restricted to one-hop neighborhoods, while deeper stacks can suffer from over-smoothing and weak performance.Prior multi-hop message-passing methods were not graph-attention based, leaving multi-hop context in attention computation unexplored.
  • MAGNA: MAGNA computes edge attention first, then diffuses it to disconnected node pairs to incorporate multi-hop context in a single layer.The diffusion process uses attention weights on edges to compute self-attention between nodes that are not directly connected.
  • MAGNA: MAGNA aggregates attention over all paths between nodes within a chosen multi-hop neighborhood, enabling context-dependent long-range interactions.Unlike GAT, attention can depend on nodes and paths beyond the directly connected pair.
  • Theory: MAGNA places a Personalized Page Rank prior on attention and emphasizes large-scale graph structure while suppressing noisy, fine-grained information.The spectral analysis links lower Laplacian eigen-values to large-scale structure and higher eigen-values to noise.
  • Experiments: MAGNA achieves up to 5.7% relative error reduction on Cora, Citeseer, and Pubmed, improves a large-scale Open Graph Benchmark result, and advances knowledge graph completion state-of-the-art.On WN18RR and FB15k-237, it improves results across four metrics, with a largest gain of 7.1% in Hit at 1.
  • Experiments: With 3 layers and 6-hop attention per layer, MAGNA significantly outperforms an 18-layer GAT with the same receptive field.The reported ablation also identifies synergistic effects from layer normalization and multi-hop diffused attention.

2 Multi-hop Attention Graph Neural Network (MAGNA)

MAGNA extends graph attention by diffusing edge attention across multi-hop paths, allowing context-dependent attention beyond direct neighbors while retaining an efficient architecture.

  • Multi-hop Attention Diffusion: MAGNA computes edge attention first, then diffuses it to obtain attention between disconnected node pairs.The diffusion module operates on attention scores at each layer and uses graph paths to extend attention beyond edges.
  • Multi-hop Attention Diffusion: Attention diffusion weights paths by hop-dependent decay, with longer relation paths receiving lower weights.The implementation uses θ_i = α(1 − α)^i, and the resulting diffusion corresponds to a Personalized PageRank procedure.
  • Approximate Computation: Exact diffusion can be expensive on large graphs, so MAGNA approximates the required product recursively with complexity O(|E|) times a hop-dependent constant.In practice, K values from 3 to 10 generally provide good performance, with larger graphs motivating larger K and lower α.
  • MAGNA Architecture: The MAGNA block combines multi-head attention diffusion, layer normalization, feed-forward layers, and residual connections.Blocks can be stacked, while layer normalization stabilizes the recursive diffusion computation.
  • MAGNA Architecture: MAGNA removes GAT’s direct-neighbor restriction without requiring additional parameters for the induced diffused attention.The model builds on GAT attention while adding layer normalization and deep aggregation for greater expressive power.

3 Analysis of Graph Attention Diffusion

The analysis interprets graph attention diffusion as a low-pass operation and establishes its equivalence to Personalized PageRank on the attention-weighted graph.

  • Spectral Analysis: MAGNA increases smaller normalized Laplacian eigenvalues and decreases larger ones, producing a graph low-pass effect.The effect becomes stronger as α decreases.
  • Spectral Analysis: Low-frequency eigenvalues represent large-scale graph structure, whereas high eigenvalues correspond to noisy fine-grained information that diffusion suppresses.This spectral behavior supports MAGNA’s emphasis on large-scale structure.
  • Personalized PageRank: With θ_i = α(1 − α)^i, graph attention diffusion is equivalent to Personalized PageRank with teleport probability α.The attention matrix serves as the transition matrix for the corresponding random walk.
  • Personalized PageRank: The diffused attention between two nodes depends on attention scores along all paths connecting them.Thus α controls the PPR prior while path contributions are aggregated through diffusion.

4 Experiments

MAGNA achieves state-of-the-art performance across node classification and knowledge graph completion benchmarks. Its analysis shows benefits from multi-hop attention, spectral filtering, and more informative attention distributions.

  • Benchmark results: 5.7% average relative error reduction is achieved on node classification, while Hit@1 improves by 7.1% on knowledge graph completion.MAGNA is evaluated on node classification and knowledge graph completion tasks.
  • Benchmark results: MAGNA achieves the best node classification results on Cora, Citeseer, Pubmed, and the large-scale ogbn-arxiv benchmark.The experiments compare MAGNA with state-of-the-art GNN baselines and report best performance across the evaluated datasets.
  • Benchmark results: MAGNA achieves new state-of-the-art knowledge graph completion results across all four reported metrics on WN18RR and FB15k-237.The model compares favorably with both shallow and deep embedding methods.
  • Spectral analysis: Low Laplacian eigenvalues are amplified by up to 8×, while high eigenvalues associated with noisy information are suppressed.This spectral behavior indicates a low-pass effect that emphasizes large-scale graph structure.
  • Depth and receptive field: MAGNA remains consistently strong with increasing depth, and its 3-layer, 6-hop model outperforms an 18-layer GAT with the same receptive field.Deep GCN, Diffusion-GCN, and GAT models show degrading performance attributed to over-smoothing, whereas MAGNA remains robust.
  • Hyper-parameter analysis: Performance increases when multi-hop neighbors are included, shows diminishing returns for K ≥6, and drops significantly when α > 0.25.The optimal K correlates with the largest node average shortest path distance, while very small α can overemphasize large-scale structure.
  • Attention analysis: MAGNA learns attention distributions with larger discrepancy from uniform attention than GAT, indicating stronger differentiation of important nodes.The discrepancy metric measures deviation from an uninformative uniform distribution.

5 Related Work

MAGNA combines graph attention and diffusion techniques within a single GNN framework. It uses attention diffusion, layer normalization, and deep aggregation to support context-dependent attention and large-scale structural information.

  • Graph neural network foundations: MAGNA belongs to the GNN family while combining graph attention with diffusion techniques.Graph attention assigns different importance to nodes within the same neighborhood during feature aggregation.

6 Conclusion

MAGNA combines graph attention and diffusion in a single layer to capture context-dependent interactions between distant nodes while retaining scalable graph processing. Its diffusion formulation is supported by an efficient approximation and a practical hop range.

  • MAGNA combines attention diffusion, layer normalization, and deep aggregation in a single graph-neural-network layer.
  • The diffusion approximation uses O(|E|) message communications, with a constant factor determined by the number of hops K.
  • Choosing K between 3 and 10 produces good model performance in practice.
  • Direct Transformer application to graphs is expensive and fails to capture graph structure scalably, whereas MAGNA exploits sparse graph structure.
  • MAGNA computes attention between arbitrary node pairs through a Personalized PageRank prior without compromising scalability on sparse large graphs.

C Spectral Analysis Background and Proof for Proposition 2

The spectral analysis represents graph attention through eigenvalues and eigenvectors, then characterizes attention diffusion as a polynomial graph filter. The proof establishes how diffusion transforms the spectrum under the stated eigenvalue bounds.

  • The graph Fourier transform uses the eigenvector matrix V to map signals to a spectral representation, while the inverse transform reconstructs the signal.
  • Graph attention diffusion can be viewed as a polynomial filter formed from weighted powers of the attention matrix A.
  • The attention matrix A and its diffused counterpart share the same set of eigenvectors.
  • For normalized graph attention, the eigenvalues of A lie in [-1,1], enabling the diffusion-series remainder to converge to zero when 0 < α < 1.

D Graph Learning Tasks

The paper defines node classification as predicting labels for unlabeled graph nodes and knowledge graph completion as predicting an entity participating in a specified relation.

  • Node classification learns f:(X,G)→T to predict labels for unlabeled nodes from node features and graph structure.
  • Knowledge graph completion predicts a head or tail entity given the other entity and a relation.

E Dataset Statistics

The experiments report dataset statistics separately for node-classification benchmarks and knowledge-graph benchmarks.

  • Dataset statistics are presented in Table 4 for node classification and Table 5 for knowledge graph link prediction.

F Knowledge Graph Training and Evaluation

The knowledge graph completion procedure augments the graph with reverse-direction triples and scores entity pairs against all entities simultaneously.

  • Training: Reverse-direction triples convert each knowledge graph into an undirected graph for training.For each (h, r, t), the procedure adds (t, r−1, h).
  • Training: 1-N scoring evaluates both entity-relation directions against all entities simultaneously.The procedure jointly scores (h, r) and (t, r−1) with all entities.

G Results

The results section compares MAGNA with diffusion and attention baselines on node-classification benchmarks, using standard splits, validation-based early stopping, and randomized hyperparameter search.

  • Datasets: The experiments report statistical information for node-classification and knowledge-graph benchmark datasets.These statistics are presented in Tables 4 and 5.
  • Results: Table 6 compares Diffusion GCN, GAT, and MAGNA on node-classification accuracy for Cora, Citeseer, and Pubmed.The comparison includes GAT with hidden dimension = 512.
  • Evaluation: The study uses standard splits and reports standard deviations because random graph splits can produce substantial performance variation.The cited discussion characterizes random splitting as impractical in real scenarios.
  • Evaluation: Models are selected by validation accuracy with early stopping using a window size of 200.This criterion is specified for node classification.
  • Evaluation: Hyperparameters are chosen by random search across learning rate, hop number, teleport probability α, dropout ratios, layers, and hidden dimensions.Search spaces are provided separately for citation-network, ogbn-arxiv, and knowledge-graph settings.
Loading 2009.14332v5…