Graph Masked Autoencoders with Transformers

1 INTRODUCTION

• Transformers capture global information by aggregating all graph nodes, unlike GCNs, whose local aggregation is limited by neighborhood depth and oversmoothing.Deep GCNs often perform worse because oversmoothing makes node representations increasingly similar, whereas global information is important for graph representations.Source: §1 · pp. 1–2, Figure 1 · p. 1
• Graph transformers are difficult to train from scratch and require quadratic memory in the number of nodes, which is problematic for large real-world graphs.Deep models need tailored training schemes, while large node sets can frequently cause memory exhaustion.Source: §1 · p. 2
• GMAE masks graph nodes, encodes the partially masked graph, and reconstructs the features of masked nodes with a self-supervised objective.The masking mechanism reduces the number of encoder inputs, and reconstruction compares predicted masked-node features with their originals.Source: §1 · p. 2
• Its asymmetric design uses a deep transformer encoder and shallow decoder, reducing memory load while allowing deeper encoding and simplifying downstream training.After self-supervised pre-training, the encoder can be fine-tuned for specific tasks with fewer tailored training schemes.Source: §1 · p. 2
• GMAE achieves state-of-the-art performance on self-supervised graph and node classification, while pre-training and fine-tuning reaches comparable performance to end-to-end training.The reported results cover both task types under common downstream evaluation protocols.Source: §1 · p. 2

2.1 Self-supervised Graph-level Representation Learning

• Graph-level self-supervised learning progressed from handcrafted graph kernels to contrastive methods such as GraphCL, MVGRL, and GCC.Kernel methods compare shared subgraphs, whereas contrastive methods maximize agreement between different graph views.Source: §2.1 · p. 2

2.2 Self-supervised Node-level Representation Learning

• Node-level self-supervision includes random-walk methods, adjacency or neighborhood reconstruction, and graph contrastive approaches such as DGI, GRACE, and GCA.Earlier random-walk methods emphasize local structure and may ignore node features, while later methods generate alternative graph views.Source: §2.2 · p. 2

2.3 Transformers

• Transformers have achieved state-of-the-art results across NLP and computer vision, with BERT serving as a prominent transformer language model.The related work discusses architectures including sparse, long-context, and linear transformer variants.Source: §2.3 · p. 3
• Graph transformer studies use structural positional encodings or modified attention, but most are supervised end-to-end and suffer from difficult training and quadratic memory costs.Examples include Graphormer, Gophormer, SAN, MAT, and related graph-transformer architectures.Source: §2.3 · p. 3

3.1 Notations and Definitions

• Graphs are represented with nodes, edges, adjacency matrices, and optional node and edge features used for learning.Source: §3.1 · p. 3
• Graph self-supervised learning trains a model on unlabeled graph data to output node embeddings.Source: §3.1 · p. 3

3.2 Graph Transformers

• Transformer self-attention computes queries, keys, and values, then aggregates value representations using query-key attention weights.Source: §3.2 · p. 3
• A two-layer feed-forward network projects node representations and increases model capacity.Source: §3.2 · p. 3
• Graph transformers use centrality, spatial, and edge positional encodings to represent degree, shortest-path, and edge-feature structure.Source: §3.2 · p. 3
• GMAE masks nodes, encodes visible-node features and positional embeddings, inserts a shared mask token, and reconstructs masked-node features.Source: Figure 2 · p. 4

4 GRAPH MASKED AUTOENCODER

• GMAE uses Graphormer graph transformers as both encoder and decoder within a masked autoencoder.Source: §4 · p. 4

4.1 Training

• During training, GMAE masks nodes, encodes only observed-node features, inserts a shared learnable mask token, and reconstructs masked-node features.The encoder receives X_o^V ∈ R^{n_o×d_V} rather than the full feature matrix, and reconstruction uses a loss such as cross-entropy.Source: §4.1 · p. 4

4.2 Positional Embeddings

• GMAE computes centrality, spatial, and edge positional embeddings from the whole graph, applying masking only to node features.The encodings are added to encoder and decoder inputs and to attention matrices; edge encoding requires edge features.Source: §4.2 · p. 4

4.3 Evaluation

• After training, GMAE discards the decoder, uses the unmasked whole graph with the encoder, and supports node or graph embeddings for downstream tasks.Graph-level embeddings can use readout functions such as average pooling, with either fixed-encoder self-supervised use or fine-tuning for pre-training tasks.Source: §4.3 · p. 4

4.4.3 Scalability

• Masking and asymmetric depth make GMAE potentially scalable to large graphs and deeper encoders with relatively small memory consumption.Source: §4.4 · p. 4, §4.4.3 · p. 5

4.4.1 Masking mechanism

• Masking half the nodes generally performs well, while some datasets reach their best mask ratio at 90%, reducing quadratic memory use.Source: §4.4.1 · p. 4

4.4.2 Asymmetric encoder-decoder design

• A 16-layer encoder with a 2-layer decoder achieves state-of-the-art performance in most cases while saving computation through asymmetric depth.The encoder processes a reduced feature matrix, while the shallow decoder keeps the full-size reconstruction stage computationally small.Source: §4.4.2 · p. 5

5 EXPERIMENTS

• Experiments compare GMAE with popular self-supervised graph representation models on graph and node classification, then compare pre-training and fine-tuning with supervised graph-classification models.Source: §5 · p. 5

5.1.1 Baselines

• The six baselines comprise sub2vec, graph2vec, GCN, Graphormer, InfoGraph, and GraphCL.GCN and Graphormer are adapted for self-supervised learning using the graph loss introduced in GraphSage [41].Source: §5.1.1 · p. 5

5.1.2 Datasets

• The study uses seven TU Dortmund benchmark datasets and 10-fold cross-validation for every dataset.The datasets are PROTEINS, BZR, COX2, NCI1, MUTAG, ER_MD, and DHFR.Source: §5.1.2 · p. 5

5.1.3 Experiment Settings

• Graph classification accuracy is evaluated with an SVM classifier using learned graph embeddings and averaged over five runs.GMAE encoder depth and mask ratio are tuned, while the default decoder depth is two layers.Source: §5.1.3 · p. 5

5.1.4 Results

• GMAE outperforms other methods on 5 of 7 graph classification datasets, including InfoGraph and GraphCL.The evaluation uses downstream SVM classification, and the compared methods include random-walk, GCN, Graphormer, and contrastive-learning baselines.Source: §5.1 · p. 5, §5.1.4 · p. 6

5.2.1 Baselines

• The four baselines are GAE, DGI, MVGRL, and GCA, representing graph autoencoding and graph contrastive learning approaches.These models are described as state-of-the-art self-supervised node classification baselines and outperform traditional methods such as DeepWalk and node2vec.Source: §5.2.1 · p. 6

5.2.2 Datasets

• The evaluation covers six datasets: Cora, CiteSeer, PubMed, Wiki-CS, Amazon-Computers, and Amazon-Photo.Public splits are used for four datasets, while the two Amazon datasets use random 80%/10%/10% train/validation/test splits.Source: §5.2.2 · p. 6

5.2.3 Experiment Settings

• GMAE trains on randomly sampled 2-hop ego-graphs with masked nodes and reconstructs their features.At inference, ten sampled ego-graphs are averaged for each target-node embedding before logistic-regression evaluation.Source: §5.2.3 · pp. 6–7

5.2.4 Results

• GMAE outperforms four baselines on 5 of 6 node classification datasets, including DGI, MVGRL, and GCA.The authors conclude that GMAE is effective for self-supervised representation learning at both graph and node levels.Source: §5.2.4 · p. 7, Table 4 · p. 7

5.3 GMAE Pre-training & Fine-tuning

• Figure 3 compares the memory usage of GMAE and Graphormer as the number of nodes varies.Source: Figure 3 · p. 7
• The ZINC experiment pre-trains a 12-layer encoder with a 2-layer decoder, discards the decoder, and fine-tunes the encoder with a linear projection layer.Pre-training uses only the training set, while fine-tuning is supervised on the training set and evaluated with test MAE.Source: §5.3 · p. 7
• GMAE shows slightly better performance than the state-of-the-art Graphormer on the ZINC regression task.The comparison reports test mean absolute error, where smaller values indicate better performance.Source: §5.3 · p. 7
• Pre-training transfers learned data-structure and feature knowledge to downstream tasks, allowing a larger learning rate and fewer fine-tuning epochs.The authors state that this avoids a very tailored training scheme.Source: §5.3 · pp. 7–8
• Figures 4 and 5 analyze accuracy across mask ratios and decoder-layer counts, respectively.In both figures, the y-axis is accuracy and larger values indicate better performance.Source: Figure 4 · p. 8, Figure 5 · p. 8

5.4.1 Memory Consumption

• 20% memory reduction at 110 nodes suggests GMAE can train larger graphs and deeper graph transformers despite overhead outside self-attention.With a 0.7 mask ratio, the theoretical encoder self-attention complexity is O(0.49n^2), but other model components limit the observed reduction.Source: §5.4.1 · pp. 8–9

5.4.2 Mask Ratio

• GMAE generally performs well with mask ratios around 0.4 or 0.7, although the best ratio depends on the dataset.COX2 and MUTAG favor high ratios, ER_MD and NCI1 favor ratios near 0.3, and PROTEINS has peaks near 0.4 and 0.7.Source: §5.4.2 · p. 9

5.4.3 Number of Decoder Layers

• Shallow decoders with 1 or 2 layers generally outperform deeper decoders while also saving memory.This supports the asymmetric encoder-decoder design used by GMAE.Source: §5.4.3 · p. 9

• GMAE masks a large portion of graph nodes and reconstructs their features using an asymmetric encoder-decoder design.Source: §6 · p. 9
• GMAE achieves state-of-the-art performance on graph and node classification under commonly used self-supervised downstream protocols.Source: §6 · p. 9
• Pre-training and fine-tuning with GMAE achieves comparable performance to end-to-end training while simplifying the training process.Source: §6 · p. 9
• Masking and the asymmetric encoder-decoder design largely reduce memory consumption compared with conventional graph transformers.The reduced memory use supports training large graphs and deep transformers.Source: §6 · p. 9