PaperlayerView exact revision on arXiv

Source-linked AI summary

NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs

Jinsong Chen, Kaiyuan Gao, Gaichao Li, Kun He

arXiv:2206.04910v4cs.LGcs.AI

TL;DR

Existing graph Transformers use one global node-token sequence, making self-attention quadratic in graph size and difficult to scale. NAGphormer instead converts each node’s multi-hop neighborhoods into tokens with Hop2Token, enabling mini-batch Transformer training. The authors report consistent superiority over existing graph Transformers and mainstream GNNs across small and large benchmarks.

  • Problem

    Existing graph Transformers treat nodes as independent tokens in one global sequence, causing quadratic self-attention complexity and making large-graph training difficult.

  • Method

    NAGphormer uses Hop2Token to turn multi-hop neighborhood features into per-node token sequences, then applies a Transformer and adaptive attention-based readout.

  • Results

    NAGphormer consistently outperforms existing graph Transformers and mainstream GNNs on benchmark datasets ranging from small to large.

  • Takeaways & Limitations

    The tokenized design preserves multi-hop neighborhood information while enabling mini-batch training for node classification on large graphs.

  • Takeaways & Limitations

    Message-passing GNNs retain over-smoothing and over-squashing limitations as model depth increases, despite mitigation efforts.

Abstract

from arXiv · show

The graph Transformer emerges as a new architecture and has shown superior performance on various graph mining tasks. In this work, we observe that existing graph Transformers treat nodes as independent tokens and construct a single long sequence composed of all node tokens so as to train the Transformer model, causing it hard to scale to large graphs due to the quadratic complexity on the number of nodes for the self-attention computation. To this end, we propose a Neighborhood Aggregation Graph Transformer (NAGphormer) that treats each node as a sequence containing a series of tokens constructed by our proposed Hop2Token module. For each node, Hop2Token aggregates the neighborhood features from different hops into different representations and thereby produces a sequence of token vectors as one input. In this way, NAGphormer could be trained in a mini-batch manner and thus could scale to large graphs. Moreover, we mathematically show that as compared to a category of advanced Graph Neural Networks (GNNs), the decoupled Graph Convolutional Network, NAGphormer could learn more informative node representations from the multi-hop neighborhoods. Extensive experiments on benchmark datasets from small to large are conducted to demonstrate that NAGphormer consistently outperforms existing graph Transformers and mainstream GNNs. Code is available at https://github.com/JHL-HUST/NAGphormer.

1 INTRODUCTION

Graph Transformers improve graph representation learning but remain difficult to scale because global self-attention over all node tokens is quadratic. NAGphormer addresses this by tokenizing each node’s multi-hop neighborhood into a mini-batchable sequence.

  • Motivation: Message-passing GNNs face over-smoothing and over-squashing as depth increases, limiting their ability to learn deep structural information.Recent methods alleviate but do not completely eliminate these negative influences.
  • Motivation: Existing graph Transformers encode all nodes as one sequence, making self-attention quadratic in the number of nodes and large-graph training resource-intensive.Mini-batch training is unsuitable for this single-long-sequence design, while common GNN scalability strategies do not directly apply.
  • Method: NAGphormer feeds node-specific token sequences into a Transformer and adaptively weights different-hop neighborhoods with an attention-based readout.The framework ends with an MLP-based module for label prediction.
  • Results: The authors report that NAGphormer consistently outperforms existing graph Transformers and mainstream GNNs on benchmark datasets ranging from small to large.The experiments include six small datasets and three large datasets.
  • Method: Hop2Token aggregates neighborhood features from each hop into token vectors, preserving different-hop information as a sequence for every node.This treats graph nodes analogously to token sequences in natural language processing and computer vision.

2 BACKGROUND

This section formulates node classification on attributed graphs, reviews GCNs and decoupled propagation, and introduces Transformer self-attention and graph-Transformer strategies. It emphasizes the trade-off between neighborhood aggregation depth, representation learning, and computational structure.

  • Problem Formulation: Node classification predicts unlabeled-node labels from an attributed graph, using labels from a designated labeled node set.The graph is defined as unweighted and undirected, with node features, adjacency matrix, normalized adjacency, and a class-label matrix.
  • Graph Neural Network: A GCN layer couples neighborhood aggregation with feature transformation, and increasing depth can cause over-smoothing that limits deep structural learning.Decoupled GCNs separate these operations into independent modules.
  • Graph Neural Network: Decoupled GCN propagation combines representations from multiple propagation steps using coefficients β_k after applying a neural network to raw attributes.The design is described as computationally efficient and able to capture deeper structural information.
  • Transformer: Transformer encoders use multi-head self-attention and position-wise feed-forward networks, with attention modeling pairwise similarity among input tokens.The attention matrix is computed from projected token pairs and normalized row-wise with softmax.
  • Graph Transformer: Graph Transformers incorporate structural information through positional encodings, auxiliary GNN modules, or graph bias in the attention matrix.These approaches have achieved competitive performance on graph mining tasks.

3 THE PROPOSED NAGPHORMER

NAGphormer constructs per-node hop-aware token sequences with Hop2Token, processes them using a Transformer, and adaptively aggregates neighborhood representations for scalable node classification.

  • Hop2Token: Hop2Token aggregates each node’s neighborhood information at multiple hops into a sequence of token representations.The 0-hop representation is the node itself; higher-hop representations encode progressively broader neighborhoods.
  • Hop2Token: Repeated multiplication by the normalized adjacency matrix propagates features to larger distances and produces k-hop neighborhood matrices.The process starts from the original feature matrix and applies propagation for K steps.
  • Scalability: Hop2Token is non-parametric, can run offline, and produces outputs compatible with mini-batch training on graphs of arbitrary size.This design supports extending graph Transformers to large-scale graphs.
  • NAGphormer architecture: NAGphormer combines structural encoding, projected hop-token sequences, Transformer layers, and an attention-based readout function.Structural information is incorporated through Laplacian eigenvectors concatenated with node attributes.
  • NAGphormer architecture: The readout learns the importance of each hop by modeling correlations between the node representation and its neighborhood representations.This avoids treating all neighborhoods equally during final representation aggregation.
  • Theoretical analysis: Compared with decoupled GCNs, NAGphormer uses self-attention and adaptive readout to learn more informative representations from multi-hop neighborhoods.The analysis characterizes decoupled GCN aggregation as using a fixed, incomplete attention pattern with fixed coefficients.

4 EXPERIMENTS

Experiments across small and large benchmarks compare NAGphormer with GNNs and graph Transformers, then examine structural encoding, readout functions, and key parameters. NAGphormer consistently outperforms the evaluated baselines, while its adaptive readout and structural encoding improve performance and its parameter sensitivity varies by dataset.

  • Comparison on Small-Scale Datasets: NAGphormer consistently outperforms twelve advanced baselines across six small-scale datasets, using mean accuracy and standard deviation over 10 random-seed trials.The baselines include full-batch GNNs, scalable GNNs, and graph Transformers.
  • Comparison on Small-Scale Datasets: Graphormer, SAN, and GraphGPS encounter out-of-memory errors on some small graphs, highlighting the need for scalable graph Transformers.SAT is also excluded because it reports out-of-memory errors on the authors’ small-scale graphs.
  • Comparison on Large-Scale Datasets: NAGphormer consistently outperforms three scalable GNNs on AMiner-CS, Reddit, and Amazon2M, while existing graph Transformers cannot run on these large-scale datasets.The authors report that training costs in Appendix G demonstrate NAGphormer’s efficiency for large graphs.
  • Ablation Study: Structural encoding improves node-classification performance, but its gains vary across datasets because graph topology differs.The ablation compares NAGphormer with and without Laplacian-based structural encoding.
  • Ablation Study: ATT outperforms SIN and SUM on small-scale datasets, indicating that adaptively weighting information from different hops produces more expressive node representations.SIN uses the node representation itself, whereas SUM weights all hop information equally.
  • Parameter Study: Performance remains stable as propagation steps increase to K = 20 on some datasets, whereas larger Transformer depth L generally degrades performance.On Reddit, performance changes by < 0.1% as K increases; the authors attribute larger-L degradation to likely over-fitting and set L = 3 for AMiner-CS and L = 1 elsewhere.

5 CONCLUSION

NAGphormer tokenizes each node’s multi-hop neighborhood into a sequence, enabling mini-batch training on large graphs while preserving hop-specific information. The paper combines this design with adaptive readout and theoretical analysis, and reports superiority over representative graph Transformers and GNNs.

  • 5 CONCLUSION: NAGphormer represents each node as a sequence of tokens extracted from different-hop neighborhoods, preserving graph structural information.Hop2Token extracts and transforms neighborhood features from multiple hops into tokens for each node.
  • 5 CONCLUSION: The tokenized design enables mini-batch training and allows the graph Transformer to handle large-scale graphs.This addresses the scalability constraints of graph Transformers that process all nodes as one sequence.
  • 5 CONCLUSION: An attention-based readout adaptively learns node representations from multi-hop neighborhoods by assigning different importance to different hops.The readout is motivated by the differing contributions of neighbors at different hops.
  • 5 CONCLUSION: Theoretical analysis indicates that NAGphormer can learn more expressive node representations than the decoupled GCN.The comparison is framed through self-attention and Hop2Token outputs.
  • 5 CONCLUSION: Experiments across datasets from small to large demonstrate superiority over representative graph Transformers and Graph Neural Networks.The conclusion reports a broad comparative outcome rather than a single-dataset result.

B COMPLEXITY ANALYSIS OF NAGPHORMER

NAGphormer’s self-attention operates over each node’s K + 1 hop tokens rather than all graph nodes. Its time complexity scales with n(K + 1)^2d, while its space complexity depends on batch size, token count, feature dimension, and Transformer depth.

  • Time complexity: NAGphormer has time complexity O(n(K + 1)^2d), where n is the number of nodes, K the number of hops, and d the parameter-matrix dimension.The complexity is determined mainly by the Transformer self-attention module.
  • Space complexity: NAGphormer has space complexity O(b(K + 1)^2 + b(K + 1)d + d^2L), where b is batch size and L is the number of Transformer layers.The terms account for attention and hidden representations plus Transformer-layer parameters.

C PROOF OF FACT 1

The proof characterizes decoupled GCN propagation as a fixed self-attention pattern over hop representations. It then relates the resulting decoupled-GCN output to Hop2Token and its self-attention transformation.

  • Proof: Hop2Token and decoupled GCN use the same propagation process to obtain information from different-hop neighborhoods.The proof denotes the neighborhood information at propagation step k by H^(k)_i.
  • Proof: The proof compares the decoupled-GCN output Z_i with the Hop2Token output X_i and the self-attention output T for node i.These representations are expressed using the hop-wise neighborhood information and attention-related coefficients.
  • Proof: Using a summation readout, each element of the final representation T_final is obtained from the transformed hop representations.The displayed derivation leads to Fact 1.

D.1 DATASET DESCRIPTION

The dataset suite spans citation, co-purchase, co-authorship, and social networks. Table 4 reports dataset statistics, while the surrounding descriptions identify the entities and relations represented in each network.

  • Network types: Citation networks include Pubmed, CoraFull, and AMiner-CS, with papers as nodes and citations as edges.These datasets represent citation relationships between papers.
  • Network types: Co-purchase networks include Computer, Photo, and Amazon2M, with goods as nodes and frequent co-purchases as edges.An edge indicates that two connected goods are frequently bought together.
  • Network types: CS and Physics are co-authorship networks, while Reddit is a social network connecting posts commented on by the same user.The network semantics differ across datasets and reflect authorship or user activity.

D.2 IMPLEMENTATION DETAILS

NAGphormer is tuned across Transformer depth, hidden dimension, propagation steps, optimizer settings, learning rate, and weight decay. Its comparison with Gophormer uses matching datasets and random-split ratios, with Gophormer’s reported results.

  • Implementation details: NAGphormer’s configuration searches 1–5 Transformer layers, hidden dimensions of 128, 256, or 512, and 2–20 propagation steps.The search also tunes AdamW learning rates and weight-decay values.
  • Implementation details: The experiments optimize parameters with AdamW using learning rates of 1e−3, 5e−3, or 1e−4 and weight decay of 1e−4, 5e−4, or 1e−5.
  • Comparison setup: For Gophormer, NAGphormer is evaluated on the original datasets with the same random-split ratio, while Gophormer results come from its report.

F ABLATION STUDY OF READOUT FUNCTION ON LARGE-SCALE DATASETS

The readout ablation compares NAGphormer’s attention-based readout with SIN. and SUM. on three large-scale datasets. The attention-based function consistently performs best.

  • Readout comparison: NAGphormer’s attention-based readout consistently outperforms SIN. and SUM. on three large-scale datasets.The comparison evaluates alternative functions for aggregating multi-hop neighborhood representations.
  • Readout comparison: The ablation examines how different readout functions affect NAGphormer’s performance on large-scale datasets.

G EFFICIENCY EXPERIMENTS ON LARGE-SCALE GRAPHS

The efficiency experiment compares NAGphormer with PPRGo, GraphSAINT, and GRAND+ using running time and GPU memory on large-scale graphs. On Amazon2M, NAGphormer is almost three times faster than PPRGo, the second-fastest model.

  • Experimental setup: The experiment measures training cost using running time in seconds and GPU memory in megabytes.NAGphormer is compared with the scalable GNNs PPRGo, GraphSAINT, and GRAND+.
  • Results: On Amazon2M, containing two million nodes and 60 million edges, NAGphormer achieves almost 3× acceleration over PPRGo.PPRGo is identified as the second-fastest model in this comparison.
  • Efficiency rationale: NAGphormer’s time complexity mainly depends on the number of nodes rather than the number of edges.The passage contrasts this with methods whose time consumption is related to edge count.
Loading 2206.04910v4…