Source-linked AI summary
Non-Local Graph Neural Networks
Meng Liu, Zhengyang Wang, Shuiwang Ji
TL;DR
Disassortative graphs can require non-local aggregation, while local aggregation may be harmful and standard non-local attention is computationally expensive. The paper introduces attention-guided sorting for efficient non-local GNNs and reports superior accuracy and speed across seven benchmark datasets.
Problem
Disassortative graphs may require non-local aggregation, while multilayer local aggregation can introduce noise and suffer from over-smoothing and over-squashing.
Method
The paper uses efficient attention-guided sorting to order node embeddings, enabling non-local aggregation through local convolution operators and constructing various non-local GNNs.
Results
Our non-local GNNs significantly outperform previous state-of-the-art methods on seven benchmark disassortative graph datasets in both accuracy and speed.
Takeaways & Limitations
Attention-guided sorting provides a low-cost framework for applying non-local aggregation to disassortative graph node classification.
Takeaways & Limitations
Stacking local GNN layers can expand receptive fields while introducing noise and over-smoothing or over-squashing issues.
Abstract
from arXiv · showhide
Modern graph neural networks (GNNs) learn node embeddings through multilayer local aggregation and achieve great success in applications on assortative graphs. However, tasks on disassortative graphs usually require non-local aggregation. In addition, we find that local aggregation is even harmful for some disassortative graphs. In this work, we propose a simple yet effective non-local aggregation framework with an efficient attention-guided sorting for GNNs. Based on it, we develop various non-local GNNs. We perform thorough experiments to analyze disassortative graph datasets and evaluate our non-local GNNs. Experimental results demonstrate that our non-local GNNs significantly outperform previous state-of-the-art methods on seven benchmark datasets of disassortative graphs, in terms of both model performance and efficiency.
1 INTRODUCTION
Disassortative graphs challenge GNNs because informative same-label nodes can be distant, while straightforward non-local attention is computationally expensive. The paper proposes an efficient attention-guided sorting framework and reports strong results across seven benchmark datasets.
- Disassortative graphs often place same-label, informative nodes far outside local neighborhoods, making non-local aggregation important.
- Quadratic-time non-local attention is computationally prohibitive for large-scale graphs.
- The proposed framework uses efficient attention-guided sorting to enable non-local aggregation through standard local aggregation operators.
- The framework augments common GNNs with low computational costs and supports multiple non-local GNN architectures.
- Non-local GNNs significantly outperform previous methods on node classification across seven benchmark disassortative graph datasets.
2 BACKGROUND AND RELATED WORK
The paper reviews the limits of local aggregation on disassortative graphs and the cost of extending attention globally. It motivates attention-guided sorting as an efficient way to connect distant, structurally informative nodes.
- 2.1 Graph Neural Networks: Most GNN layers aggregate only 1-hop information, while deeper stacking can introduce noise and cause over-smoothing and over-squashing.
- 2.2 Assortative and Disassortative Graphs: Disassortative graphs contain more same-label nodes that are distant from one another, unlike high-homophily assortative graphs.
- 2.2 Assortative and Disassortative Graphs: Distant same-label nodes can be structurally similar and informative to each other, so local GNNs may fail when such nodes lie beyond local multi-hop neighborhoods.
- 2.3 Attention Mechanism: Attention uses query, key, and value vectors to compute scores, but conventional graph attention usually restricts keys and values to directly connected neighbors.
- 2.3 Attention Mechanism: Applying attention between every pair of nodes enables non-local aggregation but requires O(n^2) time, whereas the proposed method requires O(n log n) time.
3 THE PROPOSED METHOD
The framework augments local node embeddings with attention-guided sorting so convolution can aggregate non-local information, while retaining local dependencies and efficient training.
- Framework overview: The framework has three steps: local embedding, attention-guided sorting, and non-local aggregation.Local embedding may use an MLP or common GNNs, while the final stage uses convolution.
- Local embedding: Local embeddings can be extracted from node features alone or through GNNs that capture local structural information.Using an MLP excludes neighborhood information, which can help on some disassortative graphs.
- Attention-guided sorting: Attention-guided sorting learns an ordering that places distant but informative nodes near one another.A jointly learned calibration vector produces attention scores whose sorted order defines the node sequence.
- Non-local aggregation: One-dimensional convolution over the sorted sequence aggregates non-local information when nearby sequence positions correspond to distant informative nodes.The resulting non-local embedding is concatenated with the original local embedding for classification, preserving both dependency types.
- Efficiency: The framework requires O(n log n) time because attention scores are computed once and sorting dominates the complexity.This contrasts with O(n^2) attention-based aggregation that evaluates attention between every pair of nodes.
4 EXPERIMENTS
Experiments analyze seven disassortative datasets, classify them by whether local aggregation is useful, and evaluate category-specific non-local GNNs. The proposed models achieve strong performance while retaining efficiency and supporting non-local aggregation through attention-guided sorting.
- Datasets: Experiments cover seven disassortative and four assortative graph datasets for node classification, including citation, Wikipedia, co-occurrence, webpage-linking, and patent graphs.The disassortative datasets are snap-patents, Chameleon, Squirrel, Actor, Cornell, Texas, and Wisconsin; the assortative datasets are Cora, Citeseer, Pubmed, and ogbn-arxiv.
- Analysis of Disassortative Graph Datasets: The analysis divides disassortative datasets by comparing MLP with common GNNs, using average best validation accuracy over runs.This distinguishes datasets where local neighborhoods provide more noise than useful information from those where informative nodes occur both locally and distantly.
- Analysis of Disassortative Graph Datasets: Actor, Cornell, Texas, and Wisconsin belong to the first category, whereas snap-patents, Chameleon, and Squirrel belong to the second.The first category favors avoiding local aggregation; the second retains useful local information alongside distant information.
- Comparisons with Baselines: NLMLP consistently outperforms Geom-GCN-s by large margins and sets new state-of-the-art performance on the four first-category datasets.NLMLP is built on MLP to exclude local noises and collect information from non-local informative nodes.
- Comparisons with Baselines: NLGCN achieves the best performance on snap-patents, Chameleon, and Squirrel, including test accuracies of 41.3 and 60.0 versus 37.0 and 56.9 for CPGCN on Chameleon and Squirrel.NLGCN and NLGAT also improve over their GCN and GAT counterparts, respectively.
- Analysis of the Attention-Guided Sorting: The re-connected graphs have much larger homophily than the original graphs, while sorted sequences tend to cluster nodes with the same label.These observations indicate that attention-guided sorting enables the proposed models to perform non-local aggregation.
- Efficiency Comparisons: NLGCN is only slightly slower than GCN and faster than GAT, whereas Geom-GCN is significantly slower because it has O(n^2) time complexity.The comparison uses real running time in milliseconds.
5 CONCLUSION
The paper proposes an efficient non-local aggregation framework for GNNs and evaluates it on disassortative graph node-classification tasks. Its non-local GNNs outperform previous state-of-the-art methods across benchmark datasets in both accuracy and speed.
- The framework uses efficient attention-guided sorting to enable non-local aggregation through convolution.It supports building non-local GNNs with low computational costs.
- The experiments analyze disassortative graph datasets and apply different non-local GNNs accordingly.The evaluation focuses on node classification tasks.
- The proposed non-local GNNs significantly outperform previous state-of-the-art methods on all benchmark disassortative graph datasets in accuracy and speed.