Gophormer: Ego-Graph Transformer for Node Classification

1 INTRODUCTION

• Message-passing GNNs can suffer over-smoothing as layers accumulate [6] and over-squashing as computation paths grow exponentially with model depth [1].Over-smoothing makes node representations indistinguishable; over-squashing impedes long-range interactions.Source: §1 · p. 1
• Full-graph attention has quadratic memory dependence on graph size, can incorporate irrelevant distant nodes, and is harder to train with scarce annotations.Graph transformers have more learnable parameters than GNNs, making them more vulnerable to overfitting in data-scarce settings.Source: §1 · p. 2
• Node2Seq samples ego-graphs as transformer inputs, reducing input size, preserving local context, filtering high-order noise, and providing data augmentation.The introduction also identifies challenges: retaining structural information in attention, adding global context, and stabilizing predictions when samples omit information.Source: §1 · p. 2
• Gophormer combines Node2Seq with proximity-enhanced attention, ego-graph consistency regularization during training, and multi-sample inference during testing.The proximity-based attention considers feature and structural proximity.Source: §1 · p. 2
• Gophormer achieves state-of-the-art performance on six benchmark datasets, and Node2Seq also boosts existing graph transformer frameworks on node classification.The authors describe the results as demonstrating the potential of graph transformers.Source: §1 · p. 2

2 BACKGROUND

• Node classification uses the graph, node features, and observed labels to infer the unobserved labels.The task is formulated over a graph G=(V,E), with labeled nodes V_L and unlabeled nodes whose labels are Y_U.Source: §2 · p. 2

2.1 Graph Neural Network

• Message-passing GNNs aggregate and transform neighborhood embeddings, but repeated propagation can make node representations indistinguishable and hinder long-range interactions [22], [1].The background names these problems over-smoothing and over-squashing, respectively.Source: §2.1 · pp. 2–3

2.2 Graph Transformers

• Graph transformers must preserve structural information because feature-based attention alone loses graph structure, while full-graph attention scales poorly and faces data scarcity when only one graph is available.Prior approaches use positional, centrality, spatial, or edge encodings to incorporate structure [12], [20],.Source: §2.2 · p. 3

3.1 Node2Seq

• Node2Seq samples D-hop ego-graphs for training nodes and turns them into transformer inputs, reducing attention to local context.Sampling different ego-graphs across epochs also acts as data augmentation; global nodes shared across ego-graphs provide global context alongside local neighbors.Source: §3.1 · p. 4

3.2 Proximity-Enhanced Transformer

• Proximity-enhanced attention uses multiple structural views to distinguish node pairs by order-specific connectivity and global-node presence.Its proximity encoding preserves fine-grained structural information for node pairs; the paper describes Graphormer’s shortest-path bias as a special case.Source: §3.2 · pp. 4–5

3.3 Optimization

• A classifier predicts node classes from center-node representations, while supervised loss and consistency regularization train the model.Consistency regularization encourages similar predictions for ego-graphs sampled from the same center node, and the overall loss weights it against supervised loss.Source: §3.3 · p. 5

3.4 Inference

• At test time, multi-sample inference averages predictions from multiple ego-graphs sampled with the training strategy.The paper proposes this approach to bridge the training–testing input gap and alleviate information loss from individual samples.Source: §3.4 · p. 5

• The experiments use node classification to evaluate Gophormer’s effectiveness.The choice follows prior work.Source: §4 · p. 5
• Ablation studies assess the importance of different model components.Source: §4 · p. 5
• The experiments also examine how performance responds to several core parameters.Source: §4 · p. 5

4.1 Experimental Setup

• The evaluation uses a 60%/20%/20% train-validation-test split across six benchmark datasets.Source: §4.1.1 · p. 5

4.1.1 Datasets.

• The datasets comprise four citation networks—Cora, Citeseer, Pubmed, and DBLP—and two social networks, Blogcatalog and Flickr.Source: §4.1.1 · p. 5
• Comparisons include popular GNN methods and graph-transformer baselines.The listed GNNs are GCN, GAT, GraphSAGE, JKNet, and APPNP; the graph transformers are GT-Sparse, GT-Full, Graphormer, and SAN.Source: §4.1.2 · p. 5

4.1.3 Implementation Details.

• Implementation uses Python, PyTorch, and DGL, with Adam and a validation-based learning-rate scheduler.The setup fixes several hyperparameters and tunes learning rate, batch size, layer count, global-node count, structural-view count, and regularization coefficient by grid search.Source: §4.1.3 · pp. 5–6, §4.1.4 · p. 6

4.2 Node Classification Performance

• Graph-transformer baselines are generally outperformed by GNNs, especially on the small Cora and Citeseer datasets.The authors suggest larger transformer parameter counts and noise from full-graph attention as possible reasons.Source: §4.2 · p. 6
• Gophormer outperforms all graph-transformer baselines on all six datasets and beats GNN baselines on Cora and Citeseer.The authors report that its gains are more significant on larger graphs such as Flickr, Pubmed, and DBLP than on Cora and Citeseer.Source: §4.2 · p. 6
• Gophormer's gains are more significant on larger graphs, which the authors associate with transformers' data-hungry nature and greater augmentation opportunities.They note that larger graphs provide more nodes, edges, and possible data-augmentation samples.Source: §4.2 · p. 6

4.3 Effectiveness of Node2Seq

• Node2Seq training trajectories are smoother and outperform full-graph training from early in training.The authors describe full-graph training as more intractable, possibly because long-distance neighbors introduce noise.Source: §4.3 · p. 6, Figure 2 · p. 7
• The section evaluates whether Node2Seq can improve the performance of two graph-transformer baselines.The tested models are SAN and Graphormer, with Node2Seq variants named SAN-Node2Seq and Graphormer-Node2Seq.Source: §4.3 · pp. 6–7
• SAN and Graphormer consistently outperform their vanilla versions with Node2Seq, while Gophormer still outperforms graph-transformer baselines using Node2Seq.Figure 3 presents the classification results of the models and variants.Source: §4.3 · p. 7, Figure 3 · p. 7

4.4 Ablation Studies

• Gophormer with proximity-based attention outperforms the version without it on all six datasets.The mechanism uses feature and structural proximity, whereas vanilla transformer attention relies on node attributes alone.Source: §4.4.1 · p. 7, Figure 4 · p. 7

4.4.2 Consistency Regularization.

• Removing consistency regularization drops performance; the authors link it to differing predictions from distinct ego-graphs sampled for the same node.The regularizer encourages classification distributions from those ego-graphs to be similar.Source: §4.4.2 · pp. 7–8, Figure 4 · p. 7
• Removing shared global nodes significantly lowers performance across datasets, limiting the model to localized ego-graph context.The paper describes global nodes as intermediaries that convey global information complementary to local ego-graph information.Source: Figure 4 · p. 7, §4.4.3 · p. 8

4.4.4 Multi-sample Inference.

• Multi-sample inference boosts performance over FullInf, which trains on sampled ego-graphs but tests on full ego-graphs without sampling.The authors describe consistent graph sampling between training and testing as crucial for desirable performance.Source: Figure 4 · p. 7, §4.4.4 · p. 8

4.4.5 Evaluation on Inference Strategies.

• FullInf and MSI-1-sample perform worst; performance first rises with more MSI samples, then levels off.The authors attribute FullInf's result to train–test structural inconsistency and MSI-1-sample's result to uncertainty from relying on a single sample.Source: §4.4.5 · p. 8, Figure 5 · p. 8

4.5.1 Global Nodes.

• Performance rises and then falls as the number of global nodes increases from 0 to 4; excessive nodes may hurt generalization.The authors attribute the pattern to a balance between useful global information and excess parameters.Source: §4.5.1 · p. 8, Figure 6 · p. 8

4.5.2 Number of Gophormer Layers.

• Performance improves initially with more layers but declines at five layers; small datasets perform best with 2 or 3 layers, and larger datasets often with 3 or 4.The authors attribute the decline at five layers to overfitting and advise choosing layer count based on graph scale and characteristics.Source: §4.5.2 · pp. 8–9, Figure 7 · p. 9

• Experiments show the effectiveness of Gophormer and point to the promise of graph transformers for node classification.Source: §5 · p. 9
• Gophormer incorporates structural information through Node2Seq and proximity-enhanced attention.Source: §5 · p. 9
• Consistency regularization and multi-sample inference are designed to mitigate negative impacts of ego-graph sampling.Source: §5 · p. 9