Towards Unsupervised Deep Graph Structure Learning

In plain words

Many graph models assume the connections between items are already known. Often they are not, or the known ones are noisy. This paper asks whether a model can work out useful connections by itself, without any labels.

The method keeps two versions of the connection map. The first is the one the model is learning. The second is a reference copy that starts from the data and is nudged, slowly and over time, toward the learned map. A training signal asks the two versions to agree about each item after both have been randomly perturbed. The learned map therefore improves against a reference that keeps improving too, which the authors argue avoids copying the original noise and avoids over-fitting the starting graph.

The result is a graph that can be used by a normal graph neural network for classification or clustering. The authors report that it competes with methods that do use labels.

TL;DR

SUBLIME is an unsupervised graph structure learning framework. A learner (full-matrix, attentive, MLP or GNN) produces an adjacency matrix, which is sparsified, symmetrised and normalised. A two-view contrastive loss, computed with a 2-layer GCN encoder, matches each node across the learned graph and an anchor graph. The anchor is updated by an exponential moving average toward the learned graph. Author-reported results are competitive with supervised structure-learning baselines on eight benchmarks §5.2.

Problem

Graph neural networks depend on a given graph. Noisy edges hurt them, and they cannot be applied directly to unstructured data §1. Deep graph structure learning (GSL) methods fix this by learning the graph jointly with a GNN, but the existing ones are supervised: they need node labels, which can be biased toward some edge types and limit the tasks they can serve §1.

The paper defines two unsupervised tasks, with no labels used for structure optimisation §3:

• Structure inference: from features X alone, learn an adjacency S in [0, 1]^(n x n) §3, Definition 1.
• Structure refinement: given a noisy adjacency A and features X, learn a refined S §3, Definition 2.

The working hypothesis is that a downstream model fed with S performs better than one fed with the original input §3.

Method

The framework has two modules: a graph structure learning module (learner and post-processor) and a structure bootstrapping contrastive learning module §4, fig. 1.

Graph learner §4.1. The learner produces a sketched matrix S~ from parameters ω. Four variants are defined:

• FGP learner eq. 1: one free parameter per matrix entry, S~ = sigma(Omega) with Omega in R^(n x n). Each edge is assumed independent. It has O(n^2) memory and parameters app. B.
• Metric learners eq. 2: an embedding network h gives node embeddings E, and a non-parametric similarity phi (cosine or Minkowski) gives S~ = phi(E). Three embedding networks are defined:
  • Attentive eq. 3: each layer multiplies features elementwise by a learned vector w, then applies a nonlinearity. Despite the GAT-like description, no attention coefficients are computed.
  • MLP eq. 4: each layer is a dense matrix Omega^(l) followed by a nonlinearity.
  • GNN eq. 5: GCN layers on features and the original adjacency A with self-loops (A~ = A + I). The paper says it is only used for structure refinement §4.1.

The learner is chosen per dataset. For graphs under 3000 nodes, FGP. For larger graphs with high-dimensional features, attentive. For large graphs with low-dimensional features, MLP. GNN can be added for refinement app. B.

Post-processor §4.2. Four steps turn S~ into S, applied in this order:

1. Sparsification eq. 6: keep each row's top-k entries, set the rest to 0. FGP is not sparsified, to keep gradients flowing. For large graphs, the kNN search is restricted to a batch of nodes §4.2, citing SLAPS.
2. Activation sigma_q eq. 7: ReLU for metric learners; ELU for FGP.
3. Symmetrisation eq. 7: average the matrix with its transpose.
4. Normalisation eq. 8: symmetric degree normalisation, D^(-1/2) S D^(-1/2), with D the degree matrix of the symmetrised matrix.

Two views and augmentation §4.3.1, §4.3.2.

• Learner view: G_l = (S, X). It is initialised as the kNN graph on the features. For FGP the kNN entries start at 1 and the rest at 0. For attentive, every weight starts at 1. For MLP and GNN, the weight matrices start as identity §4.3.1.
• Anchor view: G_a = (A_a, X). For refinement A_a starts as the original A. For inference A_a starts as the identity I. It is not trained by gradient descent but by the bootstrapping rule below §4.3.1.
• Augmentation: feature masking zeroes a random subset of feature dimensions with a shared mask across nodes eq. 9. Edge dropping removes entries of the adjacency with an independent mask eq. 10. The learner and anchor views use different feature-masking rates p_l and p_a, and the same edge-dropping rate eq. 11, §4.3.2.

Node-level contrastive learning §4.3.3. A GCN encoder f_theta with L1 = 2 layers produces H_l and H_a eq. 12. A projector g_phi with L2 = 2 MLP layers produces Z_l and Z_a eq. 13. The loss is a symmetric NT-Xent over cosine similarities with temperature t, matching node i in one view to node i in the other eq. 14:

\mathcal{L} = \frac{1}{2n} \sum_{i=1}^{n} \Big[ \ell(z_{l,i},z_{a,i}) + \ell(z_{a,i},z_{l,i}) \Big], \quad \ell(z_{l,i},z_{a,i}) = \log\frac{e^{\mathrm{sim}(z_{l,i},z_{a,i})/t}}{\sum_{k=1}^{n} e^{\mathrm{sim}(z_{l,i},z_{a,k})/t}} eq. 14

The equation is printed without a leading minus sign. Minimising it as printed would maximise agreement. The released code uses the negative log, and the Pitfalls and Paper vs code sections explain how the code's version also differs in the denominator.

Structure bootstrapping §4.4. With a fixed anchor, the learner can copy the anchor's noise, lose guidance once the anchor is learned, and over-fit the anchor. So the anchor is moved every c iterations toward the learned graph, with decay tau in [0, 1]:

\mathbf{A}_a \leftarrow \tau \mathbf{A}_a + (1 - \tau) \mathbf{S} eq. 15

The paper says tau > 0.99 keeps training stable §4.4. Setting tau = 1 freezes the anchor §5.3.

Training §4.5, alg. 1 in app. D. All parameters (learner, encoder, projector) are updated jointly with Adam. After the update, the anchor is updated every c iterations. The paper notes a complexity of O(n^2 d + m d1 L1 + n d1^2 L1 + n d2^2 L2 + n k) §4.5, app. C. Scalability measures are: metric learners instead of FGP, locality-sensitive kNN, mini-batch contrast, and c >= 10 §4.5.

# SUBLIME training loop  [alg. 1]  [§4.5]
# Input:  features (n, d); adjacency (n, n) or None; k; tau; c; epochs
# Output: learned adjacency (n, n)

def train(features, adjacency, k, tau, c, epochs):
    # Anchor starts at the given graph, or at the identity  [alg. 1]
    if adjacency is not None:
        anchor = adjacency
    else:
        anchor = identity(n)                 # (n, n)
    # Learner, encoder and projector parameters  [alg. 1]
    learner, encoder, projector = init_parameters(features, k)
    for epoch in range(epochs):
        # Learned graph: sketch, then post-process  [§4.1] [§4.2]
        sketch = learner(features)           # (n, n)
        learned = post_process(sketch, k, learner.kind)
        # Learner view: masked features and dropped edges  [§4.3.2] [eq. 9-11]
        learner_view = augment(learned, features, rate_learner, p_edge)
        # Anchor view, with its own feature-mask rate  [§4.3.2] [eq. 11]
        anchor_view = augment(anchor, features, rate_anchor, p_edge)
        # Encode, project, and compare the two views  [§4.3.3] [eq. 12-13]
        z_learner = projector(encoder(learner_view))
        z_anchor = projector(encoder(anchor_view))
        loss = contrastive_loss(z_learner, z_anchor, t=0.2)  # [eq. 14]
        # Joint gradient step over learner, encoder and projector  [alg. 1]
        gradient_step(loss, learner, encoder, projector)
        # Bootstrap: anchor moves toward the learned graph  [§4.4] [eq. 15]
        if epoch % c == 0:
            anchor = tau * anchor + (1 - tau) * learned
    return learned

# Post-processor  [§4.2] [eq. 6-8]
# Input:  sketch (n, n); k; kind in {fgp, attentive, mlp, gnn}

def post_process(sketch, k, kind):
    # Sparsify to the top-k entries of each row; FGP is skipped  [eq. 6]
    if kind != "fgp":
        sketch = keep_top_k_per_row(sketch, k)     # (n, n)
    # Activation: ELU for FGP, ReLU for metric learners  [eq. 7]
    if kind == "fgp":
        sketch = elu(sketch)
    else:
        sketch = relu(sketch)
    # Symmetrise by averaging with the transpose  [eq. 7]
    sketch = (sketch + sketch.T) / 2
    # Symmetric degree normalisation  [eq. 8]
    degree = sketch.sum(axis=1)                    # (n,)
    inv_sqrt = 1 / sqrt(degree)
    return inv_sqrt[:, None] * sketch * inv_sqrt[None, :]

# Augmentation for one view  [§4.3.2] [eq. 9-10]
# Input:  adjacency (n, n); features (n, d); rates in [0, 1]

def augment(adjacency, features, feat_rate, edge_rate):
    # Feature masking: zero the same random subset of dimensions for all nodes
    keep_dims = bernoulli(1 - feat_rate, size=d)    # (d,)
    masked_features = features * keep_dims          # (n, d)
    # Edge dropping: each entry removed independently with edge_rate
    keep_edges = bernoulli(1 - edge_rate, size=(n, n))  # (n, n)
    masked_adjacency = adjacency * keep_edges       # (n, n)
    return masked_adjacency, masked_features

Hyperparameters

Paper values come from the text and appendix. Script values come from the released run scripts, which are the settings behind the cited Cora and Citeseer runs. Where the paper states no value, the card says so.

Dataset statistics (nodes, edges, classes, features, label rate) are in tab. 7. Dataset splits follow prior work app. E.

Results

Author-reported. Setup: eight benchmarks, five seeds for classification, GCN evaluators trained on the learned graph, baselines reproduced from their official code or copied from their papers app. F. Bold and underline markers from the paper are omitted. The Available data column lists what each method uses during graph learning: X features, Y labels, A_knn kNN graph, A the original graph tab. 1, tab. 2.

Node classification, structure inference tab. 1

Node classification, structure refinement tab. 2

Node clustering, structure refinement tab. 3

Bootstrap decay ablation, structure refinement tab. 4

The authors say the bootstrapping step adds about 1.5 points on average over tau = 1 §5.3. Their learning curves for Cora show a drop around 1500 iterations when tau = 1 §5.3, fig. 2.

Other results. Sensitivity to feature-masking rate and kNN size [§5.4, fig. 3]. Robustness to random edge deletion and addition on Cora, against GCN and Pro-GNN §5.5, fig. 4. Heatmaps of learned Cora edges, showing more intra-class edges than the original graph §5.6, fig. 5.

Paper vs code

Code: official repository at commit 93398db994f21bd2b03f15db414e1e03244144e9, linked in §5.1 of the paper, MIT License LICENSE. Discrepancies checked against model.py, utils.py, graph_learners.py, layers.py, main.py, data_loader.py and the run scripts.

• Contrastive denominator. The paper's denominator sums over all k, including k = i eq. 14. The code subtracts the positive term from the column and row sums, so each loss is minus the log of positive over the negatives only model.py. Paper says: positive over all. Code does: positive over negatives. The code also uses the negative log, as standard NT-Xent does, while eq. 14 is printed without the minus.
• Edge dropout is rescaled. Eq. 10 gives A ⊙ M with no rescale. The code uses nn.Dropout(p) on the dense adjacency, which scales surviving entries by 1/(1 - p) model.py model.py. The sparse path also rescales layers.py.
• Feature masking is a fixed count. Eq. 9 and §4.3.2 describe a Bernoulli mask per dimension. The code draws exactly floor(d · rate) dimensions without replacement and uses them for every node utils.py.
• Top-k keeps k + 1 entries. The metric learners keep k + 1 entries per row, so the node itself is counted as a neighbour graph_learners.py graph_learners.py graph_learners.py. Paper says top-k.
• FGP off-kNN entries are not zero. Parameters are initialised to 0 on kNN entries and to -6 elsewhere, and the activation is ELU + 1. This gives 1 for kNN entries and about exp(-6) ≈ 0.0025 for the rest, not exactly 0 [code: utils.py#L91-L96] graph_learners.py. The code uses ELU + 1, not plain ELU as in §4.2.
• Sparse path differs. In the sparse path (Pubmed), degree normalisation happens inside kNN construction before the ReLU, and the symmetrised pair is added as duplicate directed edges, not averaged graph_learners.py utils.py. This does not match eq. 7 and 8 literally.
• Last-layer activation. The attentive and MLP learners apply the nonlinearity between layers but not after the last one, while eq. 3 and 4 write it for each layer graph_learners.py graph_learners.py.
• MLP learner keeps biases. It sets the weights to identity, but the bias of nn.Linear is not reset graph_learners.py.
• Encoder dropout. The encoder applies dropout after each hidden layer with rate 0.5 by default. The paper does not mention encoder dropout model.py main.py.
• Bootstrapping is off in released scripts. tau defaults to 1, which disables the update main.py main.py. The Cora and Pubmed structure inference scripts use tau = 1 cora_si.sh pubmed_si.sh. Citeseer structure inference uses 0.9999 citeseer_si.sh. The paper's tau ablation is a refinement study §5.3.
• Bootstrap interval. The default c is 0, so the anchor updates every step, while §4.5 says c >= 10 main.py main.py. The Pubmed refinement script uses c = 50 pubmed_sr.sh.
• Contrast batches are contiguous. Mini-batching splits node indices into consecutive blocks, and the shuffle is commented out main.py. Each block's loss is weighted by its size.
• GNN learner has no self-loops and a fixed anchor. The GNN learner uses the normalised input adjacency without adding I, and it holds the anchor from the start of training, so it does not see bootstrapped updates [code: graph_learners.py#L131-L143] main.py data_loader.py. No released script uses the GNN learner.
• Datasets missing. The code accepts only cora, citeseer and pubmed main.py. There is no loader for ogbn-arxiv, Wine, Cancer, Digits or 20news, so those rows cannot be reproduced from this release.
• Clustering reports the last evaluation. The printed clustering metrics are from the last evaluation step, not the best one main.py main.py.
• Clustering seed. The code runs one trial with seed 0 and 10 K-means restarts, which matches app. F main.py.
• Evaluator is retrained per evaluation step. A fresh GCN is trained on the learned graph at each evaluation epoch, with dropout set per script main.py cora_si.sh cora_sr.sh.
• Hyperparameter grid. The paper's grid goes up to 512 dimensions. The released scripts use 256 for Cora and Citeseer cora_si.sh.
• Checked, no discrepancy. The anchor update uses the learned graph from before the optimiser step, as Algorithm 1 does main.py app. D. The anchor update formula matches eq. 15 main.py.

Pitfalls

• p is a drop rate, not a keep rate. §4.3.2 says each mask element is drawn from a Bernoulli with probability p, and eq. 9 keeps dimensions where the mask is 1. The text on sensitivity and the code both treat p as the fraction removed. The code does features * (1 - mask) main.py. Implement p as the removal rate.
• Rescaling changes the loss scale. With edge dropout rescaled by 1/(1 - p), the surviving edges are heavier than the eq. 10 version. Decide which to implement and report it.
• Denominator choice changes the objective. Excluding the positive from the denominator, as the code does, makes a per-node term negative whenever the positive similarity exceeds the sum over negatives. An implementer following eq. 14 will not match the released numbers.
• Missing sign in eq. 14. Without the minus, the stated objective would push the two views apart. Use the negative log.
• Bootstrapping is the key claim, and the released scripts turn it off for Cora and Pubmed structure inference. The paper's tau ablation is on refinement, not inference. Reproducing the inference numbers therefore means setting tau = 1.
• Anchor update interval. The paper says c >= 10 for scale, but the default is every step. The effect of c on accuracy is not reported.
• Sparse versus dense paths. The Pubmed numbers come from the sparse path, which does not compute the same symmetrisation and normalisation as the dense one. A dense reimplementation will not match Pubmed results.
• Learner choice is per dataset. The paper gives only the node-count and dimension guidance app. B. FGP needs O(n^2) memory and parameters, so it is unsuitable for large graphs app. B app. C. The paper uses FGP for Cora.
• Hardware and software. The released code calls .cuda() in several places and needs CUDA utils.py utils.py. It pins PyTorch 1.7.1 and DGL 0.7.1 app. F. np.bool in the data loader does not exist in current NumPy releases data_loader.py.
• Evaluation details differ per script. The evaluator's dropout and epochs change between scripts, and the paper states only the layer count and width app. F cora_si.sh cora_sr.sh.
• Baselines. Some baselines are copied from their papers and some are rerun with tuned settings, so the comparison mixes sources app. F.
• Scale. The paper's large-graph path uses kNN sparsification, a locality-sensitive kNN and mini-batch contrast §4.5. The ogbn-arxiv configuration is not in the release.
• No results from the code. This card does not report numbers from running the released code. All numbers are the paper's.

Lineage

• Builds on: the graph learner family and kNN initialisation of LDS, SLAPS and IDGL, and the sparsification and locality-sensitive kNN of SLAPS [§4.1, §4.2, app. B]. The NT-Xent loss and the SimCLR-style framework §4.3.3. The bootstrapping idea from earlier self-supervised work §4.4.
• Compared against: GCN, GAT, SAGE, LDS, GRCN, Pro-GNN, GEN, IDGL, SLAPS, GDC, SLAPS-2s for classification §5.1; K-means, SC, GE, DW, DNGR, M-NMF, RMSC, TADW, VGAE, ARGA, MGAE, AGC, DAEGC for clustering §5.1.
• Superseded by: not stated in this wiki.