Source-linked AI summary
Graph-Bert: Only Attention is Needed for Learning Graph Representations
Jiawei Zhang, Haopeng Zhang, Congying Xia, Li Sun
TL;DR
Existing link-dependent GNNs face suspended animation, over-smoothing, and limited parallelization on large graphs. GRAPH-BERT instead uses attention over sampled linkless subgraphs, with pre-training and transfer across tasks; experiments report strong effectiveness and efficiency relative to existing GNNs.
Problem
Existing GNNs can suffer suspended animation and over-smoothing, while graph connectivity limits parallelization and batching for large graph inputs.
Method
GRAPH-BERT uses attention-only representation learning on sampled linkless subgraphs, with node attribute reconstruction and graph structure recovery for pre-training.
Results
GRAPH-BERT out-performed most baseline methods on Cora and Pubmed, ranked among the top 3 on Citeseer, and remained responsive at 50 layers.
Takeaways & Limitations
Pre-trained GRAPH-BERT can be transferred directly or fine-tuned for new tasks and used as a graph representation component in learning pipelines.
Takeaways & Limitations
The graph setting assumes feature and label spaces represented as Euclidean spaces, with X = R^dx and Y = R^dy.
Abstract
from arXiv · showhide
The dominant graph neural networks (GNNs) over-rely on the graph links, several serious performance problems with which have been witnessed already, e.g., suspended animation problem and over-smoothing problem. What's more, the inherently inter-connected nature precludes parallelization within the graph, which becomes critical for large-sized graph, as memory constraints limit batching across the nodes. In this paper, we will introduce a new graph neural network, namely GRAPH-BERT (Graph based BERT), solely based on the attention mechanism without any graph convolution or aggregation operators. Instead of feeding GRAPH-BERT with the complete large input graph, we propose to train GRAPH-BERT with sampled linkless subgraphs within their local contexts. GRAPH-BERT can be learned effectively in a standalone mode. Meanwhile, a pre-trained GRAPH-BERT can also be transferred to other application tasks directly or with necessary fine-tuning if any supervised label information or certain application oriented objective is available. We have tested the effectiveness of GRAPH-BERT on several graph benchmark datasets. Based the pre-trained GRAPH-BERT with the node attribute reconstruction and structure recovery tasks, we further fine-tune GRAPH-BERT on node classification and graph clustering tasks specifically. The experimental results have demonstrated that GRAPH-BERT can out-perform the existing GNNs in both the learning effectiveness and efficiency.
1 Introduction
GRAPH-BERT addresses limitations of link-dependent GNNs with attention-only learning over sampled linkless subgraphs. It supports unsupervised pre-training, task-specific fine-tuning, and transfer across graph-learning tasks.
- Motivation: Existing GNNs can suffer from suspended animation and over-smoothing, while graph connectivity limits parallelization for large inputs.These issues hinder deep graph representation learning and batching across nodes.
- GRAPH-BERT: GRAPH-BERT learns representations from sampled target nodes and context nodes in linkless subgraphs rather than relying on graph links during representation learning.The model is based purely on attention mechanisms instead of graph convolution or aggregation operators.
- Efficiency: Training cost depends on the number of training instances and sampled subgraph size, not the input graph size.This design is described as more efficient than GNNs constructed for the complete input graph.
- Pre-training: Unsupervised pre-training uses node attribute reconstruction and graph structure recovery to capture attributes and preserve local and global structural properties.The two tasks support learning from unlabeled graph data.
- Fine-tuning and transfer: Pre-trained GRAPH-BERT can be fine-tuned for node classification and graph clustering or transferred to other sequential models.The paper presents transfer as a way to construct functional graph-learning pipelines.
2 Related Work
Related work covers graph neural networks and the attention-based Transformer and BERT architectures. GRAPH-BERT draws on attention-only sequence modeling while targeting graph representation learning.
- Graph Neural Networks: Representative GNNs include GCN, GraphSAGE, and LOOPYNET, with GCN variants based on approximated graph convolutional operators.The related-work discussion also mentions network embedding and other extended GNN models.
- Transformer and BERT: Transformers were proposed as architectures based solely on attention mechanisms, dispensing with recurrence and convolutions to address sequential training constraints.This attention-only design motivates GRAPH-BERT’s architectural direction.
3 Method
GRAPH-BERT is organized as a pipeline that batches linkless subgraphs, embeds node inputs, encodes them with a graph Transformer, fuses representations, and produces task-specific outputs.
- Architecture: The model begins with linkless subgraph batching and node input embedding before applying a graph-Transformer-based encoder.
- Architecture: Representation fusion produces the target-node representation used by the functional component.The functional component generates different outputs depending on the application task.
- Architecture: Each sampled subgraph contains a target node together with surrounding context nodes.
3.1 Notations
The notation section establishes conventions for scalars, vectors, matrices, sets or high-order tensors, transposes, norms, and vector operations.
- Notation conventions: Lowercase letters denote scalars, lowercase bold letters column vectors, bold uppercase letters matrices, and calligraphic uppercase letters sets or high-order tensors.
- Norms and transposes: Matrix and vector transposes are written with ⊺, while vector Lp-norms and matrix Frobenius norms are explicitly defined.
- Vector operations: The element-wise product of equal-dimensional vectors is denoted by ⊗, and concatenation by ⊔.
3.2 Linkless Subgraph Batching
GRAPH-BERT samples linkless subgraphs around each target node instead of processing the complete graph. Sampling uses PageRank-based intimacy scores to select each node’s learning context.
- The input graph is represented as nodes, links, weights, raw features, and labels, while pre-training requires no label supervision.
- GRAPH-BERT trains on sampled linkless subgraph batches, enabling parallelizable learning on extremely large graphs.The paper states that this can support graphs existing GNNs cannot handle.
- PageRank defines the intimacy matrix S, whose entries measure the intimacy between node pairs.
- A node’s learning context contains nodes whose intimacy score exceeds threshold θ_i.
- The threshold is the kth sorted intimacy score, so each context contains the target node’s top-k intimate nodes, which may be local or distant.
3.3 Node Input Vector Embeddings
GRAPH-BERT embeds each sampled node using raw features and structural or positional signals. These signals combine global role information with local intimacy and hop-distance information.
- Nodes in a linkless subgraph are serialized by decreasing intimacy score, although GRAPH-BERT itself does not require node order.
- Each input embedding combines raw features, Weisfeiler-Lehman absolute roles, intimacy-based relative positions, and hop-based relative distances.
- Raw node features are mapped into a shared dimension d_h through an Embed function that can use CNNs, LSTM/BERT, or fully connected layers.
- The Weisfeiler-Lehman algorithm assigns identical structural-role codes to nodes with identical roles, and these codes are embedded for the model.
- Relative positional embeddings capture local subgraph information from serialized placement, while hop embeddings balance global role and local distance information.
3.4 Graph Transformer based Encoder
The graph-transformer encoder initializes node embeddings by summing their component vectors, updates them through multiple layers, and fuses the resulting representations for the target node.
- GRAPH-BERT aggregates each node’s embedding components by vector summation to form the initial input matrix H^(0).
- The graph-transformer encoder iteratively updates node representations through D layers.
- The encoder uses learned query, key, and value projections together with graph residual terms.
- Unlike conventional residual learning, the target node’s residual term is added to every node’s hidden state in the subgraph at each layer.
- Fusion averages the final representations of input nodes to produce the target node representation z_i, while H^(D) is also passed onward.
4 GRAPH-BERT Learning
GRAPH-BERT is pre-trained to preserve node attributes and graph structure, then transferred directly or fine-tuned for downstream graph tasks. The supplied passages describe reconstruction, recovery, classification, and clustering objectives.
- GRAPH-BERT is pre-trained with node attribute reconstruction and graph structure recovery.
- Attribute reconstruction targets node attributes, whereas structure recovery targets graph connection information.
- Node representations are decoded through a fully connected layer to reconstruct each target node’s raw attributes.
- Structure recovery infers pairwise connection scores from cosine similarity between learned node representations.
- Pre-trained representations can be used directly or adjusted for downstream tasks; node classification requires fine-tuning, while graph clustering can use representations directly.
- Graph clustering partitions nodes into groups and uses the learned representations as node features rather than retraining GRAPH-BERT jointly.
5 Experiments
Experiments on Cora, Citeseer, and Pubmed evaluate GRAPH-BERT’s standalone learning, convergence, architectural choices, and transfer-related components. Results indicate fast convergence, strong node-classification performance, sensitivity to subgraph size and embeddings, and benefits from selected residual terms.
- Dataset and learning settings: Experiments evaluate GRAPH-BERT on the Cora, Citeseer, and Pubmed benchmark datasets using node classification, clustering, and representation-learning analyses.The datasets are standard graph benchmarks, with subgraph sizes and model settings varied across experiments.
- Learning convergence of deep GRAPH-BERT: GRAPH-BERT converges on node classification in less than 10 epochs, and even its 50-layer model responds effectively to training data without suspended animation.The depth analysis uses Cora and compares architectures from 1 to 50 layers.
- Node classification results: GRAPH-BERT outperforms most baseline methods on Cora and Pubmed, while ranking among the top three methods on Citeseer.The comparison includes classic and state-of-the-art GNN baselines, but excludes several extended GCN and GAT variants.
- Subgraph size k analysis: On Cora, performance improves as subgraph size k increases from 1 to 7, then degrades dramatically for larger k, while time cost rises with k.The optimal k differs across datasets, and the reported time increase is described as minor relative to GCN and GAT.
- Graph residual analysis: The graph-raw residual term outperforms the other two residual-term variants.This result is reported as consistent with prior experimental observations cited by the authors.
- Initial embedding analysis: Raw feature embeddings contribute substantially, while combining them with complementary role, hop-distance, and intimacy-based embeddings improves performance over raw features alone.The complementary embeddings perform poorly when used alone in the reported analysis.
5.3 Graph Clustering without Pre-Training
This section evaluates GRAPH-BERT for graph clustering without pre-training. The setup uses KMeans on raw node features and reports clustering metrics on three benchmark datasets, while the supplied results also motivate comparison with pre-trained variants.
- Clustering setup: Without pre-training, GRAPH-BERT performs graph clustering on Cora, Citeseer, and Pubmed using KMeans applied to nodes’ raw feature vectors.The results are evaluated with several clustering metrics, including mutual information.
- Comparison with pre-training: The supplied discussion states that, with enough training epochs, GRAPH-BERT models with and without pre-training can both converge to very good learning results.The authors therefore compare them using only 15 of the normal fine-tuning epochs in Table 6.
- Pre-training effects: Pre-training improves graph clustering on Cora and Citeseer but degrades clustering results on Pubmed.The same passage reports that pre-training helps node classification on Pubmed, showing task- and dataset-specific effects.
6 Conclusion
GRAPH-BERT learns graph representations from sampled linkless subgraphs using extended graph-transformer layers, rather than relying on graph links. Its pre-trained representations can support new graph-learning tasks directly or through fine-tuning.
- 6 Conclusion: GRAPH-BERT learns target-node representations from batches of linkless subgraphs sampled from the original graph.The model uses extended graph-transformer layers in this process.
- 6 Conclusion: GRAPH-BERT works well in deep architectures without the common problems reported for other GNNs.
- 6 Conclusion: Pre-trained GRAPH-BERT can serve as a graph representation component and transfer to new tasks directly or with necessary fine-tuning.