Source-linked AI summary
Hierarchical Graph Transformer with Adaptive Node Sampling
Zaixi Zhang, Qi Liu, Qingyong Hu, Chee-Kong Lee
TL;DR
Graph Transformers face scalability constraints on large graphs, and existing sampling may ignore graph properties or miss long-range dependencies. The paper combines adaptive bandit-based node sampling with hierarchical attention and graph coarsening; experiments report advantages over Graph Transformers and popular GNNs across six benchmark datasets.
Problem
For large graphs, Graph Transformers face costly attention, while fixed sampling can ignore graph properties and local-neighbor sampling can miss long-range dependencies.
Source: §1 · pp. 1–2Method
ANS-GT adapts sampling-heuristic weights using an adversarial bandit formulation and combines local attention with coarse-grained global attention over coarsened graphs.
Source: §1 · p. 2Results
ANS-GT outperforms existing Graph Transformer architectures and achieves state-of-the-art results on six benchmark datasets, with reported advantages over popular GNNs.
Source: §1 · p. 2Takeaways & Limitations
The analysis indicates that adaptive node sampling can adjust sampling strategies according to graph properties.
Source: §7 · p. 10
Abstract
from arXiv · showhide
The Transformer architecture has achieved remarkable success in a number of domains including natural language processing and computer vision. However, when it comes to graph-structured data, transformers have not achieved competitive performance, especially on large graphs. In this paper, we identify the main deficiencies of current graph transformers:(1) Existing node sampling strategies in Graph Transformers are agnostic to the graph characteristics and the training process. (2) Most sampling strategies only focus on local neighbors and neglect the long-range dependencies in the graph. We conduct experimental investigations on synthetic datasets to show that existing sampling strategies are sub-optimal. To tackle the aforementioned problems, we formulate the optimization strategies of node sampling in Graph Transformer as an adversary bandit problem, where the rewards are related to the attention weights and can vary in the training procedure. Meanwhile, we propose a hierarchical attention scheme with graph coarsening to capture the long-range interactions while reducing computational complexity. Finally, we conduct extensive experiments on real-world datasets to demonstrate the superiority of our method over existing graph transformers and popular GNNs.
1 Introduction
The paper targets graph transformers’ scalability and sampling limitations on large graphs, proposing adaptive node sampling and hierarchical attention to address them. Experiments report advantages over existing graph transformers and popular GNNs on six benchmark datasets.
1 Introduction
- Existing approaches face quadratic or at least sub-quadratic resource costs on large graphs, while fixed local sampling can ignore graph properties and miss long-range context.Full attention may also introduce noise from irrelevant nodes.Source: §1 · pp. 1–2
- ANS-GT adapts weights over sampling heuristics using an adversarial bandit formulation, with rewards related to node attention weights and sampling probabilities.The sampling strategy updates during training to select informative nodes.Source: §1 · p. 2
- Hierarchical attention combines sampled local attention with coarse-grained global attention over super-nodes produced by graph coarsening.The global component is intended to capture long-distance dependencies while reducing computational complexity.Source: §1 · p. 2
- ANS-GT outperforms existing Graph Transformer architectures and achieves state-of-the-art results on six benchmark datasets, with reported advantages over popular GNNs.Detailed analysis and ablations also support the adaptive node sampling module and hierarchical attention scheme.Source: §1 · p. 2
2 Related Work
Related work covers graph-specific Transformers and sparse-attention approaches to scalability, alongside GNN sampling methods. It distinguishes fixed and adaptive sampling while noting that GNN samplers do not directly transfer to Graph Transformers.
2.1 Transformers for Graph
- Graph Transformers address positional encoding and scalability through restricted receptive fields, but fixed sampling can sacrifice Transformer flexibility; SAC uses an LSTM edge predictor whose limited parallelizability reduces efficiency.Examples include 1-hop neighborhoods in GAT and GT-Sparse [9], ego-graph sampling in Gophormer [46], and top-k intimacy scores in Graph-Bert [41].Source: §2.1 · pp. 2–3
2.2 Sparse Transformers
- Sparse Transformer methods reduce attention cost with techniques such as block patterns, locality-sensitive hashing, clustering, low-rank approximation, or local windows, but do not account for graph-specific properties.Linformer [35] reduces complexity from O(n^2) to O(n).Source: §2.2 · p. 3
2.3 Graph Neural Networks and Node Sampling
- GNN sampling limits neighborhood expansion through node-wise or layer-wise strategies, with fixed and adaptive variants, but these methods do not directly apply to Graph Transformers’ non-message-passing architecture.Node-wise sampling can grow to O(k^l) nodes at layer l.Source: §2.3 · p. 3
3 Preliminaries
The preliminaries define semi-supervised node classification, outline the Transformer operations used in the paper, and introduce graph coarsening as a way to construct a smaller graph while retaining global information.
3.1 Problem Definition
- Semi-supervised node classification uses labels for a subset of nodes to infer labels for the remaining nodes.The graph is represented by an adjacency matrix and a node-attribute matrix.Source: §3.1 · p. 3
3.2 Transformer Architecture
- A Transformer layer contains multi-head self-attention and a position-wise feed-forward network, with the attention input projected into query, key, and value spaces.The heads’ outputs are concatenated and transformed to produce the multi-head attention output.Source: §3.2 · pp. 3–4
3.3 Graph Coarsening
- Graph coarsening partitions nodes into clusters represented as super-nodes, then derives coarse-graph features and weighted adjacency from the partition matrix.The resulting graph has substantially fewer nodes and edges than the original.Source: §3.3 · p. 4
4 Motivating Observations
On Newman networks, no node-sampling strategy dominates across homophily levels. The experiments show that which strategy performs best varies with graph properties, motivating adaptive sampling.
4 Motivating Observations
- The case study varies homophily on Newman artificial networks and compares 1-hop, 2-hop, PPR, and kNN sampling for node classification.Homophily is the fraction of edges connecting nodes with the same class label.Source: §4 · p. 4
- No sampling strategy dominates across the homophily spectrum in Newman networks, supporting the need for adaptive sampling.Figure 1 compares 1-hop, 2-hop, PPR, and kNN sampling.Source: §4 · pp. 4–5, Figure 1 · p. 4
- At α = 0.05, 2-hop sampling achieves 73.1% accuracy, exceeding 1-hop and PPR; at α = 1.0, 1-hop or top-PPR sampling yields high accuracy.The authors suggest 2-hop neighbors may become more homophilous as inter-class edges increase.Source: §4 · p. 5
- At α = 0.25, kNN achieves 77.2% accuracy on a randomly connected Newman network, where it gives the most consistent results.The authors attribute this consistency to kNN using attribute similarity alone.Source: §4 · p. 5
- These observations motivate sampling the most informative nodes adaptively for attention across differing graph properties.The paper uses these observations to motivate its hierarchical Graph Transformer with adaptive node sampling.Source: §4 · p. 5
5 The Proposed Method
The method combines adaptive node sampling with hierarchical local and global attention to address graph-transformer sampling and long-range dependency challenges. Its stated computational complexity is O(n).
5.1 Adaptive Node Sampling
- ANS-GT frames node sampling as an adversarial bandit problem, adapting sampling-strategy weights as node contributions and rewards vary during training.The method modifies EXP4.P and updates sampling weights and resamples nodes every T epochs for efficiency and stability.Source: §5.1 · pp. 5–6
- The reward scheme uses attention-derived node significance and sampling probabilities to favor strategies whose sampled-node distributions better match significance scores.Node significance is based on the first attention-matrix row multiplied by the corresponding value-vector magnitude; scores are averaged across heads and layers.Source: §5.1 · p. 6
5.2 Hierarchical Graph Attention
- Hierarchical attention pairs adaptively sampled fine-grained local nodes with coarse-grained super-nodes and learnable global nodes to represent broader context.Graph coarsening creates a coarse graph, whose sampled super-nodes capture long-range dependencies.Source: §5.2 · pp. 6–7
5.3 Optimization and Inference
- Training minimizes average cross-entropy over labeled nodes; inference aggregates predictions from S sampled input sequences using bagging.The paper states that bagging is used to improve accuracy and reduce variance.Source: §5.3 · p. 7
5.4 Computational Complexity
- ANS-GT has O(n) overall computational complexity when sampled-node counts, super-node counts, global-node counts, and augmentation counts are fixed.Graph coarsening is linear in n and performed once before training; sampling-weight updates are also linear in n.Source: §5 · p. 5, §5.4 · p. 8
6 Experiments
ANS-GT is evaluated on six benchmark datasets against GNN and Graph Transformer baselines. The experiments report strong classification performance, adaptive changes in sampling weights, and sensitivity to graph-coarsening settings.
6.1 Experimental Setup
- The evaluation uses a 60%/20%/20% train-validation-test split, compares 12 baseline methods—8 GNNs and 4 Graph Transformers—for graph representation learning, and measures node-classification accuracy.The implementation uses AdamW and Variational Neighborhoods with a default coarsening rate of 0.01.Source: §6.1 · p. 8
6.2 Effectiveness of ANS-GT
- ANS-GT outperforms all Graph Transformer baselines and achieves state-of-the-art node-classification results on all six datasets.On Squirrel, ANS-GT reaches 45.88% accuracy versus 43.15% for the best baseline.Source: §6.2 · p. 9
- Sampling weights are time-sensitive and gradually stabilize during training, with PPR and 1-hop neighbors weighted highly on Cora and 2-hop neighbors on Squirrel.KNN weights rise initially and then decline on CiteSeer and Actor.Source: §6.2 · p. 9, Figure 3 · p. 9
- On Chameleon, ANS-GT achieves 65.42% while its variant without adaptive sampling, HGT, achieves 57.20%.Figure 4 presents ablation studies of the adaptive node-sampling module.Source: §6.2 · p. 9, Figure 4 · p. 9
- Different coarsening algorithms show no significant performance difference, while coarsening rates from 0.01 to 0.10 perform best.The sensitivity analysis considers Variation Neighborhoods, Variation Edges, and Algebraic coarsening.Source: §6.2 · pp. 9–10, Table 2 · p. 9
7 Conclusion
The conclusion presents ANS-GT as a graph-transformer approach that combines adaptive node sampling with hierarchical attention, and reports an empirical advantage on six benchmark datasets.
7 Conclusion
- ANS-GT modifies a multi-armed bandit algorithm to adaptively sample nodes for attention.The conclusion says detailed analysis shows the sampling module can adjust strategies according to graph properties.Source: §7 · p. 10
- A hierarchical graph-attention scheme uses graph coarsening for coarse-grained attention to incorporate long-range dependencies and global contexts.Source: §7 · p. 10
- Experiments on six benchmark datasets show an advantage over existing Graph Transformers and popular GNNs.Source: §7 · p. 10
Checklist
The checklist reports that limitations and potential negative social impacts are addressed in the Appendix, and that code was not yet available.
Checklist
- The checklist directs readers to the Appendix for the paper's limitations and potential negative social impacts.Source: Checklist · p. 13
- The code was not included with the submission; the checklist says it would be released once the paper was accepted.Source: Checklist · p. 13
- The checklist reports that training details, error bars across repeated runs, and computing resources were specified.Source: Checklist · p. 13
A More Details of Motivating Observations
The motivating experiments use Newman artificial networks with controlled homophily, randomness, and heterophily, alongside class-associated and irrelevant node attributes.
A More Details of Motivating Observations
- Each Newman network has 128 nodes in four classes, with 16 average edges per node split between intra-class and inter-class edges.The ratio of within-class to between-class edge probabilities distinguishes homophily, randomness, and heterophily.Source: A More Details of Motivating… · p. 14
- The generated 200-dimensional binary attributes include class-associated dimensions and irrelevant dimensions, with Gophormer sampling 10 nodes per strategy for 16 augmentations.The compared strategies are 1-hop, 2-hop, KNN, and PPR.Source: A More Details of Motivating… · p. 14
- Figure 5 depicts adjacency matrices for strong homophily, randomness, and strong heterophily, marking edges yellow and non-edges purple.Source: Figure 5 · p. 14, A More Details of Motivating… · p. 14
B Dataset Statistics
This material reports dataset-statistics coverage, graph-coarsening timing information, and Cora hyperparameter sensitivity. It recommends specific Cora settings after examining how model performance changes as key hyperparameters vary.
B Dataset Statistics
- Table 3 presents statistics for nine datasets.The supplied passage does not provide the table's individual values.Source: Table 3 · p. 14, B Dataset Statistics · p. 14
C.1 Hyper-parameter Analysis
- 5 transformer layers, 3 super-nodes, 2 global nodes, and augmentation number 16 are recommended for Cora.Performance rises initially with more layers, then decreases slightly beyond six; performance also peaks and declines as super-node and global-node counts increase, while augmentation gains stabilize.Source: Figure 6 · p. 15, §C.1 · p. 15
C Additional Results and Analysis
- Table 4 reports graph-coarsening time in seconds.Its caption also identifies a coarsening-rate definition, but the supplied text does not give the full definition or cell values.Source: Table 4 · p. 15
C.2 Efficiency Analysis of ANS-GT
Supplementary experiments report ANS-GT results on large OGB graphs and compare training efficiency with Graph Transformer baselines. The material also describes implementation choices and limitations, including added finetuning hyperparameters and possible sampling bias.
C.2 Efficiency Analysis of ANS-GT
- Graph coarsening is performed once during preprocessing; adaptive-sampling weights update every 100 epochs, and that module's time cost is described as trivial.The coarsening time is characterized as acceptable.Source: §C.2 · p. 16
C.3 Limitations and Potential Negative Social Impacts
- A limitation is the added finetuning hyperparameters, and adaptive node sampling may introduce sampling bias.Source: §C.3 · p. 16
D Supplementary Information of Graph Coarsening
- Variation Neighborhoods contracts node-neighborhood subsets, Variation Edges contracts edges, and Algebraic JC contracts close neighboring nodes into clusters.These are the three graph-coarsening algorithms used in ANS-GT.Source: D Supplementary Information of Graph… · p. 16
E Further Discussions of ANS-GT
- ANS-GT optimizes weights over predefined sampling heuristics rather than directly predicting attended nodes; this narrows the search space, while direct prediction is described as costly and hard to optimize.Hierarchical attention is not incorporated into the bandit learning because it samples supernodes from the coarsened graph rather than nodes from the four heuristics.Source: E Further Discussions of ANS-GT · pp. 16–17
C.2 Efficiency Analysis of ANS-GT
- ANS-GT has training time comparable to Gophormer and much better efficiency than Graphormer.The comparison reports average training time per epoch.Source: §C.2 · p. 16, Table 6 · p. 17
C.4 Additional Results on OGB Datasets
- ANS-GT overperforms selected baselines on ogbn-arxiv (169,343 nodes) and ogbn-products (2,449,029 nodes).The comparison uses GCN, GraphSAGE, and GPRGNN, with average accuracies and standard deviations over five runs.Source: §C.4 · p. 16, Table 7 · p. 17