SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks

Bahare Fatemi; Layla El Asri; Seyed Mehran Kazemi

Source-linked AI summary

SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks

Bahare Fatemi, Layla El Asri, Seyed Mehran Kazemi

arXiv:2102.05034v2Feb 9, 2021cs.LGcs.AI

TL;DR

The paper studies latent graph learning when graphs are unavailable and task supervision is insufficient to learn structures alongside GNN parameters. SLAPS adds a feature-reconstruction self-supervised task to latent graph learning, and experiments report stronger benchmark performance and scalability to graphs with hundreds of thousands of nodes.

Problem
When graph structure is unavailable, latent graph learning may suffer supervision starvation for edges far from labeled nodes, impairing learned structures and generalization.
Method
SLAPS jointly learns graph structure and GNN parameters while adding self-supervision that masks or perturbs features and trains adjacency updates to recover them.
Results
SLAPS substantially outperforms existing latent graph-learning baselines across benchmarks and scales to graphs with hundreds of thousands of nodes.
Takeaways & Limitations
Self-supervision provides additional supervision for learning task-specific graph structures, supporting SLAPS’s broad benchmark evaluation and large-graph scalability.
Takeaways & Limitations
Deeper GCNs may alleviate supervision starvation somewhat, but typically produce inferior results, for example through oversmoothing.

Abstract

from arXiv · show

Graph neural networks (GNNs) work well when the graph structure is provided. However, this structure may not always be available in real-world applications. One solution to this problem is to infer a task-specific latent structure and then apply a GNN to the inferred graph. Unfortunately, the space of possible graph structures grows super-exponentially with the number of nodes and so the task-specific supervision may be insufficient for learning both the structure and the GNN parameters. In this work, we propose the Simultaneous Learning of Adjacency and GNN Parameters with Self-supervision, or SLAPS, a method that provides more supervision for inferring a graph structure through self-supervision. A comprehensive experimental study demonstrates that SLAPS scales to large graphs with hundreds of thousands of nodes and outperforms several models that have been proposed to learn a task-specific graph structure on established benchmarks.

1 Introduction

The paper addresses classification when no graph structure is available, focusing on insufficient supervision for learning both latent edges and GNN parameters. SLAPS adds feature-reconstruction self-supervision and is evaluated broadly against existing latent graph-learning baselines.

GNNs perform well for semi-supervised classification when connected nodes often share labels, but this graph structure may be unavailable.
Latent graph learning jointly learns a task-specific graph structure and GNN parameters, often outperforming fixed similarity graphs.
Edges far from labeled nodes can receive insufficient classification supervision, producing poor structures away from labels and poor generalization.
SLAPS supplements classification with self-supervision that masks or perturbs features and trains a GNN to recover them through adjacency updates.
SLAPS is evaluated on nine datasets with thirteen variations spanning different sizes and domains.
The study reports that SLAPS substantially outperforms existing latent graph-learning baselines and scales to graphs with hundreds of thousands of nodes.

2 Related work

Prior graph-structure inference methods use similarity graphs, fully connected parameterizations, latent graph generators, or domain knowledge. SLAPS belongs to latent graph learning and adds self-supervision to increase structural supervision.

Similarity graph: Similarity-graph methods assign edge weights from node similarity and may sparsify connections with kNN, thresholds, or sampling.
Fully connected graph: Fully connected approaches weight all node pairs using metadata or attention, but their rapidly growing complexity limits them to small graphs.
Latent graph learning: Latent graph learning uses learnable generators, projections, or iterative latent spaces to infer adjacency structures rather than relying only on initial-feature similarity.
Leveraging domain knowledge: Domain-knowledge methods guide structure learning using application-specific constraints such as syntax, sparsity, low rank, or feature smoothness.
Proposed method: SLAPS supplements latent graph learning with self-supervision for structure learning, differing from GNN pre-training that applies self-supervision without this structural focus.

3 Background and notation

The paper represents attributed graphs with node sets, adjacency matrices, and feature matrices, then propagates and transforms node representations using normalized graph convolutions. Normalization incorporates self-loops and degree-based scaling.

An attributed graph is represented as G = {V, A, X}, with n nodes, m edges, f features, adjacency A, and feature matrix X.
A_ij denotes the weight of the edge from v_i to v_j, with A_ij = 0 indicating no edge.
A GCN updates node embeddings by applying a normalized adjacency matrix, a trainable weight matrix, and an activation function to the previous layer.
For undirected graphs, normalization is symmetric; for directed graphs, it is row-based, and both forms add self-loops.

4 Proposed method: SLAPS

SLAPS jointly learns a graph structure and GNN parameters, augmenting node-classification supervision with feature denoising to address supervision starvation. Its pipeline generates, processes, and uses an adjacency for classification and self-supervised denoising, while the analysis characterizes starved edges and motivates a feature-prediction prior.

Overview: SLAPS combines a generator, adjacency processor, classifier, and self-supervision component in one latent graph learning model.The generator produces an adjacency, the processor makes it usable for GNN computation, and the classifier and denoiser provide task objectives.
4.1 Generator: The generator can directly optimize an n × n adjacency with FP or construct a sparse kNN graph from MLP-updated node representations.FP is flexible but adds n^2 parameters, limiting scalability and increasing susceptibility to overfitting; MLP-kNN uses learned representations before kNN construction.
4.2 Adjacency processor: The adjacency processor makes generated edge values non-negative, symmetrizes the matrix, and normalizes it before classification.Averaging the processed adjacency with its transpose preserves reciprocal similarities and reduces one-sided connections when kNN neighborhoods are asymmetric.
4.3 Classifier: The classifier applies a two-layer GCN to node features and the normalized generated adjacency to produce class logits.The same generated structure also participates in the self-supervised denoising pathway shown in the model overview.
4.4 Using only the first three components leads to supervision starvation: Classification-only latent graph learning can leave edges without label supervision when they do not affect labeled-node predictions within the GCN’s receptive field.For a two-layer GCN, predictions depend on two-hop neighbors, so edges between nodes disconnected from labeled nodes can be starved while still affecting test-time predictions.
4.4 Using only the first three components leads to supervision starvation: For Erdős–Rényi graphs, starved-edge probabilities are 59.4% for Cora-like statistics, 75.7% for Citeseer, and 96.7% for Pubmed; original graphs show 48.8%, 65.2%, and 91.6%.The theorem assumes q uniformly selected labeled nodes and a two-layer GCN; the reported benchmark figures illustrate the scale of the issue.
4.5 Self-supervision: SLAPS uses feature prediction as a learned prior, training a separate GNN to denoise masked or noisy node features through the generated adjacency.The method relies on the hypothesis that a structure suitable for predicting node features is also suitable for predicting node labels.
4.5 Self-supervision: Deeper GCNs may alleviate supervision starvation somewhat, but typically produce inferior results because of effects such as oversmoothing.This limitation is stated as a caveat to using more layers as a solution.

5 Experiments

Experiments across established graph, non-graph, and MNIST benchmarks show that SLAPS generally outperforms latent graph-learning baselines while scaling to very large graphs. Analyses attribute its performance to self-supervision, especially when labeled supervision is limited, and show that it learns high-homophily structures and can improve noisy initial graphs.

Comparative results: SLAPS consistently outperforms latent graph-learning baselines, sometimes by large margins, across the evaluated benchmarks.On three of four classification datasets, it also outperforms LDS and IDGL; performance is dataset-dependent among graph generators.
Comparative results: SLAPS scales to ogbn-arxiv, whereas the evaluated graph-learning baselines fail on that dataset in the authors’ experiments.The paper notes that IDGL-ANCH also scales to ogbn-arxiv.
The effectiveness of self-supervision: SLAPS2s outperforms kNN-GCN by 8.4% on Cora with an FP generator, despite learning adjacency only from self-supervision.With the FP generator, SLAPS2s achieves performance competitive with SLAPS.
Analyses of the learned adjacency: For noisy Cora graphs, SLAPS removes 76.2% and 70.4% of added edges and recovers 58.3% and 44.5% of removed edges at ρ = 25% and ρ = 50%, respectively.With λ = 0, the corresponding removal rates are 62.8% and 54.9%, and recovery rates are 51.4% and 35.8%. Higher learned edge weights also correspond to greater odds of shared labels.

6 Conclusion

The paper concludes that SLAPS learns graph connectivity and GNN parameters simultaneously from data, using self-supervision to address supervision starvation. Its analyses include label-sharing odds associated with learned edge weights.

Figure 6 relates learned edge weights to the odds that two test-set nodes share a label.
SLAPS simultaneously learns graph connectivity and GNN parameters from data.
The method addresses supervision starvation by supplementing the training objective with a self-supervised task.

7 Funding Transparency Statement

The work was fully funded by Borealis AI.

The work was fully funded by Borealis AI.
Borealis AI provided full funding for this work.
The funding transparency statement identifies Borealis AI as the sole funder.

A More Experiments and Analyses

Additional analyses examine sensitivity to k, network depth, adjacency symmetrization, and manually specified prior graphs. They show that these design choices affect performance, while self-supervision remains stronger than manual prior regularization in the reported comparisons.

Importance of k in kNN: k substantially affects SLAPS performance across all three graph generators on Cora.The FP generator is least sensitive because k only initializes adjacency, whereas MLP and MLP-D retain neighbor counts close to k.
Increasing the number of layers: Without self-supervision, two-, four-, and six-layer GCNs achieve accuracies of 66.2%, 67.1%, and 55.8%, respectively.Performance improves from two to four layers but drops significantly at six layers as oversmoothing dominates.
Symmetrization: Mean symmetrization improves performance on Cora and Citeseer, while max symmetrization performs slightly worse than mean symmetrization.
Fixing a prior graph manually instead of using self-supervision: Regularizing toward a manually designed cosine-similarity prior graph provides good results but falls short of SLAPS with self-supervision.The prior connects each node to its k most similar nodes and adds a Frobenius-norm penalty to the loss.
Redundant or highly correlated node features can negatively affect similarity computations for a manually constructed prior graph.
Self-supervision can learn among multiple feature-predictive structures, while manual regularization targets one particular structure.

B Implementation Details

The implementation uses PyTorch, DGL, and Adam, with tuned validation-based early stopping and comparisons against released baseline implementations. Experiments average results over ten runs and include sparsified differentiable kNN graph construction and generator-specific adjacency processing.

The model uses PyTorch, DGL for sparse operations, and Adam, with early stopping and validation-based hyperparameter tuning.Wine and Cancer use validation cross-entropy loss because many settings achieve 100 percent validation accuracy.
Experiments use two-layer GCNs and MLPs throughout, with two learning rates for the classification and other model parameters.
Results for GRCN, DGCNN, and IDGL use author-released code, while LDS results come directly from its original paper.
All model and baseline results are averaged over 10 runs with mean and standard deviation reported.Experiments ran on a single NVIDIA GeForce GTX 1080 Ti GPU.
kNN Implementation: The kNN graph is sparsified while preserving gradient flow by separating a binary neighbor mask from differentiable similarities.Exact k-nearest neighbors are used in the experiments, with locality-sensitive hashing suggested as an approximation.
Adjacency processor: The adjacency processor uses ReLU for MLP-generated graphs and ELU for fully parameterized graphs to avoid gradient-flow problems.

C Dataset statistics

This section directs readers to Table 5 for the statistics of the datasets used in the experiments.

Table 5 reports the statistics of the datasets used in the experiments.
The dataset statistics are presented as part of the experimental documentation.
Readers can consult Table 5 to find the experimental dataset statistics.

D Supervision starvation in Erd˝os-Rényi and scale-free networks

The analysis formalizes supervision-starved edges as edges whose endpoints are unlabeled and disconnected from labeled nodes. It derives probabilities for Erdős-Rényi and scale-free networks, showing a high starved-edge probability for Cora-sized scale-free graphs.

Erdős-Rényi networks: Theorem 2 gives the probability of a starved edge for an Erdős-Rényi graph with n nodes, m edges, and q uniformly selected labels.
Erdős-Rényi networks: A starved edge is analyzed by requiring both incident nodes to be unlabeled and disconnected from labeled nodes.The proof computes these probabilities in sequence before combining them.
Scale-free networks: For scale-free networks, the analysis computes the probability that a randomly selected edge is starved using the network’s scale parameter γ.
Scale-free networks: 0.87 is the starved-edge probability for γ = −3 when n = 2708 and q = 140, while the probability is 0.76 for γ = −2.
Interpretation: The section motivates supervision starvation by noting that graph structures with identical homophily can have no edges in common.Figure 10 gives two such structures with edge homophily ratio 0.8.

F Limitations

The proposed model has two stated limitations: its self-supervised task requires input features or a substitute embedding, and one graph generator is not inductive.

Without input features, the self-supervised task cannot be readily applied even when an initial noisy structure is available.DeepWalk embeddings are suggested as a possible substitute for node features.
The FP graph generator is not applicable in the inductive setting because it directly optimizes the adjacency matrix.The MLP and MLP-D graph generators can be used inductively.