Graph Self-Supervised Learning: A Survey

In plain words

Graph neural networks usually learn from labeled examples, and labels are expensive. Self-supervised learning avoids this by inventing a practice task from the data itself, such as hiding part of a graph and asking the model to fill it in, then reusing what the model learned for the real task.

This survey collects the many ways people have done this for graphs. Graphs are harder than images or text because nodes are connected to each other, so tricks from those fields do not transfer directly. The authors group the methods by what the practice task asks for: rebuilding the graph, predicting properties computed from it, pulling two views of the same node or graph together, or combining several of these. They also describe how the practice stage is combined with the final task.

TL;DR

• A survey, not a method: there is no single algorithm to implement. Pick a method from the taxonomy and implement it from its original paper.
• One encoder-decoder formulation covers all surveyed methods: a graph encoder is trained on a pretext loss, then a downstream decoder is trained on labels §3.1 eq. 1 eq. 2.
• Four pretext-task categories (generation, auxiliary property, contrast, hybrid) and three training schemes (pre-train and fine-tune, joint learning, unsupervised representation learning) §3.2 §3.3.
• The only numbers are accuracies compiled from the cited works for node classification (Cora, Citeseer, Pubmed, PPI) and graph classification (nine datasets) tab. 5 tab. 7.
• The compiled numbers come from different papers and protocols, so treat them as a literature overview, not a controlled comparison (see Pitfalls).

Problem

Supervised graph models depend on manual labels, which are costly to collect, especially in domains that need expert knowledge. Purely supervised training over-fits when labels are scarce, and label-based training is reported to be vulnerable to adversarial attacks §1. Self-supervised learning tries to avoid these problems by training on pretext tasks whose supervision comes from the data itself §2.

Pretext tasks from computer vision and NLP do not map directly onto graphs. Graphs live in an irregular, non-Euclidean space, and nodes are linked to each other, so they are not independent samples the way images or sentences are §1 fig. 1. The paper's assumptions: unlabeled graph data is available, and a downstream task with labels exists for evaluation §2 §3.4.

Method

Framework §3.1. An encoder f_\theta, usually a graph neural network, maps node features \mathbf{X} and the adjacency matrix \mathbf{A} to node embeddings \mathbf{H}. An optional readout function turns node embeddings into a graph-level embedding §2. A pretext decoder p_\phi consumes \mathbf{H}, and the pretext loss \mathcal{L}_{ssl} is minimised over the unlabeled data distribution \mathcal{D} eq. 1. The downstream decoder q_\psi is trained on labels y with the supervised loss \mathcal{L}_{sup} eq. 2.

\theta^{*}, \phi^{*} = \arg\min_{\theta, \phi} \mathcal{L}_{ssl}(f_\theta, p_\phi, \mathcal{D}) \quad [\text{eq. 1}]

\theta^{**}, \psi^{*} = \arg\min_{\theta^{*}, \psi} \mathcal{L}_{sup}(f_{\theta^{*}}, q_\psi, \mathcal{G}, y) \quad [\text{eq. 2}]

Four pretext-task categories §3.2 fig. 2 fig. 3.

1. Generation-based §4. The input may be perturbed, and the decoder rebuilds the original graph. The reconstruction can target node features (feature generation, §4.1) or edges and adjacency (structure generation, §4.2). The loss measures how far the reconstruction is from the original eq. 3. GAE, which rebuilds the adjacency matrix, is the canonical example §3.2.
2. Auxiliary property-based §5. Properties that are free to compute from the graph serve as targets. Classification-based variants use pseudo labels, for example cluster indices, with cross-entropy loss; regression-based variants predict local or global properties such as node degree, with mean squared error eq. 4 §3.2. Clustering-based and pair-relation-based classification are described in §5.1.1 and §5.1.2; regression in §5.2.
3. Contrast-based §6. Two augmented views of the same node, subgraph or graph are made. The model is trained to maximise mutual information between positive pairs (views of the same object) and to reduce it for negatives. A discriminator, such as a bilinear function or a dot product, scores agreement eq. 5. Augmentations split into attribute-level (feature masking, feature shuffling) and topology-level (edge modification, graph diffusion, subgraph sampling) §6.1. Same-scale contrast (node or graph level) is in §6.2.1, cross-scale contrast in §6.2.2, and the mutual-information estimators (Jensen-Shannon, noise-contrastive, triplet, BYOL, Barlow Twins) in §6.3.
4. Hybrid §7. Two or more pretext tasks are trained together as a weighted sum of their losses, each with its own decoder and data distribution §7 (the sum is written in the section; its equation number is not cited here).

Training schemes §3.3 fig. 4.

• Pre-training and fine-tuning (PF). Pre-train the encoder on pretext tasks, then fine-tune it with labels. Pre-training and fine-tuning data may differ eq. 6.
• Joint learning (JL). Optimise the pretext loss and the supervised loss together, weighted by a trade-off hyperparameter \alpha eq. 7.
• Unsupervised representation learning (URL). Pre-train the encoder on pretext tasks, freeze it, and train only the downstream decoder on the same dataset eq. 8.

\alpha\,\mathcal{L}_{ssl}(f_\theta, p_\phi, \mathcal{D}) + \mathcal{L}_{sup}(f_\theta, q_\psi, \mathcal{G}, y) \quad [\text{eq. 7}]

Downstream tasks §3.4 app. C. Node-level (predict node properties), link-level (predict edge or node-pair properties), and graph-level (predict a property of each graph in a multi-graph dataset) tasks.

Pseudocode. The paper has no algorithm box. The loop below is a generic form of the pretext stage in eq. 1 and §3.2, not a method from the paper.

# Generic pretext stage: fit encoder and pretext decoder  [§3.1] [eq. 1]
# Input:  unlabeled graphs D; encoder f; pretext decoder p
# Output: encoder parameters theta*

def pretrain(D, f, p, loss_ssl, optimizer):
    # Build the pretext inputs: one perturbed graph for generation,
    # two augmented views for contrast  [§4] [§6]
    for graph in D:
        inputs = make_pretext_inputs(graph)
        # Node embeddings for each input  [§2]
        embeddings = [f(view) for view in inputs]
        # Pretext decoder maps embeddings to the pretext prediction  [§3.1]
        prediction = p(embeddings)
        # Compare with the pretext target (reconstruction, property
        # or agreement between views)  [eq. 3] [eq. 4] [eq. 5]
        loss = loss_ssl(prediction, graph)
        loss.backward()
        optimizer.step()
    return f.parameters()

Hyperparameters

The survey gives no training settings for any surveyed method. The rows below are the evaluation protocol and the only parameters the text names.

Results

Author-reported, compiled by the survey from the cited works (not a single controlled run). Setup: node classification on transductive citation networks and inductive PPI, measured by accuracy; GCN and GAT as baselines §8.

Node classification tab. 5

The G. Comp. row has three values in the source, so its PPI cell is empty there. Category codes are defined in the table captions of tab. 1–tab. 4.

Points the survey makes about tab. 5 §8:

• Random-walk and autoencoder methods (DeepWalk, GraphSAGE, GAE, SIG-VAE) score below most SSL methods.
• Visual contrastive objectives borrowed directly (BYOL in BGRL, Barlow Twins in G-BT) are not better than other graph methods.
• Contrastive methods (MVGRL, MERIT, SubG-Con) outperform generation- and auxiliary-based methods.
• Hybrid methods are competitive, and some beat the supervised baselines.
• The PF/JL group generally scores higher than the URL group.

Highest values in tab. 5: G-Zoom on Cora (84.7) and Citeseer (74.2); GCA on Pubmed (82.8); SuperGAT on PPI among SSL rows (74.4). GAT's 97.3 on PPI is far above all SSL rows (see Pitfalls).

Graph classification tab. 7 app. D

Nine datasets, classification accuracy, GIN as the supervised baseline. Dataset split taken from the GIN paper.

Points the survey makes about tab. 7 app. D: URL methods score overall below the supervised GIN baseline. Cross-scale contrast tends to beat same-scale contrast. Label use (PF/JL) does not always help: GCC is not uniformly better than its URL variant, so pre-trained encoders can hurt downstream results. The survey calls for unified graph-level benchmarks.

Other tables. tab. 1–tab. 4 summarise, per method, the pretext categories, downstream level, training scheme and graph type for the generation, auxiliary, contrast and hybrid groups. tab. 8 lists the benchmark datasets and tab. 9 lists open-source implementations app. E app. F.

Paper vs code

No official code. The survey links third-party repositories for many surveyed methods app. F tab. 9. These are not the authors' code and are not used here.

Pitfalls

• No method to implement. The framework eq. 1–eq. 2 and the four categories are generic. Hyperparameters, loss weights and architectures must come from each method's original paper.
• Mixed provenance of the numbers. Section 8 says the authors "conduct an experimental comparison" §8, but the LaTeX source labels most rows of tab. 5 "from original paper", "from SIG-VAE", "from CG3" or "from you2020" (raw/src/2103.00111/content.tex#L982-L1041). The values therefore come from different papers and protocols; the survey does not say which were re-run.
• PPI metric and scale. The text says accuracy is measured for both settings §8, but PPI is a multi-label task and the metric is not named. GAT's 97.3 is far above every SSL row (51–74), so do not compare the PPI column across rows without checking each original paper.
• Uneven coverage. Many cells are "-" (not reported) in tab. 5 and tab. 7. A row's mean or ranking hides which datasets it was evaluated on.
• Graph-level numbers are not comparable. Methods use different graph-level datasets and splits; the survey says no unified benchmark exists app. D.
• Equation notation. In eq. 6 the supervised term is written with p_{\theta^*} where the encoder f_{\theta^*} is meant, and the left-hand side lists \phi^* although the minimisation is over \theta and \psi §3.3. Read it as the PF scheme of eq. 2 (encoder f_{\theta^*}, decoder \psi).
• Mutual-information estimators. The survey notes the choice of MI estimator still relies on empirical studies §10, so results depend on that choice as well as the augmentations.
• Hybrid weights. The trade-off weights \alpha_i §7 are not given values, and the survey says balancing the components is a main challenge §3.2.
• Cost. Generation-based methods can be memory-heavy on large graphs; contrast-based methods depend on time-consuming empirical tuning of augmentations, losses and frameworks §3.2.
• Literature cut-off. The card is compiled from arXiv v5 (updated 2022-05-04) [raw/arxiv/2103.00111.json]. Methods published later are not covered.

Lineage

• Builds on: early unsupervised graph embedding (DeepWalk, node2vec) and the graph autoencoder GAE, which the survey treats as early graph SSL §1 §3.2. The survey's representative contrast methods are DGI and GraphCL §3.2.
• Compared against: other surveys the authors name: general self-supervised learning, self-supervised learning for computer vision, self-supervised contrastive learning, and two earlier graph self-supervised surveys §1.
• Superseded by: not known from content already in this wiki.