TL;DR
Self-Supervised Similarity-based Link Prediction (3SLP) bridges the gap between traditional heuristic link prediction and modern graph neural networks for completely unlabeled, edgeless graphs. By using self-supervised contrastive learning on a smartly initialized proxy graph, 3SLP infuses raw node attributes with topological structure, boosting link prediction accuracy (AUC) by up to 21.2% without requiring a single ground-truth link label.
What Problem Does This Paper Address?
Link prediction (LP)—predicting whether two nodes in a network should be connected—is a cornerstone of graph mining, powering everything from friend recommendations to drug-drug interaction discoveries. While deep learning-based methods currently dominate the field, they suffer from a major Achilles' heel: they are heavily supervised and require a large number of existing links to train.
But what happens during a "cold start" scenario, such as introducing a brand-new drug into a medical database? You are left with an edgeless graph containing only node attributes and zero known links.
In these unsupervised settings, researchers resort to traditional similarity-based LP methods, which assume that nodes with similar attributes are more likely to link. However, relying purely on raw, static node attributes ignores the complex, latent topological structures of graphs. The authors of this paper ask a compelling question: Can we use self-supervised learning (SSL) to automatically inject structural awareness into node features, even when no initial links are known?
Methods
The authors introduce 3SLP, a framework that enhances a standard Pairwise Similarity-based Clustering (PSC) backbone using a novel Dual-View Contrastive Node Representation Learning (DCNRL) pipeline.
The 3SLP workflow consists of four main stages:
- Graph Structure Initialization (Similarity Wiring): Since the graph starts with no edges, 3SLP constructs a proxy graph by connecting each node to its top-$k$ nearest neighbors based on the cosine similarity of their raw attributes.
- Data Augmentation via Edge Diffusion: To help the model learn higher-order relationships beyond immediate neighbors, the framework applies Personalized PageRank (PPR) diffusion. By using two different teleportation probabilities ($\alpha_1$ and $\alpha_2$), it generates two distinct structural "views" of the graph.
- Cross-Scale Contrastive Learning: The two views are fed into separate Graph Convolutional Network (GCN) encoders to extract both local node-level and global graph-level representations. 3SLP then contrasts these representations across scales (e.g., matching a node's embedding from View 1 with the global graph embedding of View 2) to maximize mutual information and learn robust topological features.
- Link Prediction Backbone: The self-supervised, learned node embeddings replace the raw attributes. Pairwise similarities are calculated, and a simple K-Means clustering algorithm ($K=2$) separates the node pairs into "linked" or "not linked" categories.
Datasets
The authors evaluated 3SLP on four widely adopted real-world benchmark datasets, stripped of their edge information to simulate a strict cold-start scenario:
- Cora, Citeseer, and PubMed: Standard citation networks where nodes represent papers (with text attributes) and edges represent citations.
- Reddit: A social post network where nodes are posts and edges represent user comments linking them.
Key Insights and Ideas
- The Homophily Dependency: The entire framework relies on the homophily assumption—the idea that similar nodes associate with each other. As shown in Figure 3, 3SLP's performance scales beautifully with Attribute Assortativity Coefficient (AAC), a measure of attribute homophily.
- Why it Fails on Heterophilic Graphs: On graphs exhibiting heterophily (where connected nodes tend to be dissimilar, like the Reddit dataset), the initial similarity wiring step creates an incorrect proxy graph. Garbage in, garbage out: the self-supervised loop ends up reinforcing the wrong structural patterns.
- Spectrum Alignment is the Secret Sauce: Through singular value decomposition (SVD), the authors proved that homophilic datasets show strong "spectrum alignment" between the initialized proxy graph and the true, hidden adjacency matrix. This mathematical alignment is what allows SSL to successfully recover global and local structural embeddings.
Key Results
- Massive Baseline Boosts: 3SLP dramatically outperformed the major baseline (PSC-NA, which uses raw attributes). It achieved an absolute AUC improvement of 17.4% on Cora and 21.2% on Citeseer.
- Beating Supervised Alternatives: Surprisingly, 3SLP outperformed methods that utilized auxiliary supervised knowledge (like PSC-Repr and PSC-Pos, which use node classification labels), proving that self-supervision can extract cleaner structural signals for link prediction than unrelated supervised tasks.
- Outperforming Knowledge Transfer: The authors compared 3SLP against a Graph Autoencoder (GAE) trained on a completely different dataset and transferred over. 3SLP easily beat the transferred GAEs, avoiding the common pitfalls of "negative transfer" where mismatched dataset dynamics degrade performance.
Limitations and Future Work
The primary limitation of 3SLP is its strict reliance on graph homophily. If a domain is inherently heterophilic, the initial $k$-NN graph construction fails, causing the subsequent contrastive learning steps to stall or degrade (as observed on the Reddit dataset).
Additionally, calculating pairwise similarities for the clustering backbone naively scales at $O(N^2)$, which poses challenges for massive, web-scale graphs. The authors note that approximate nearest-neighbor algorithms (like NN-Descent) can mitigate this, but exploring alternative initializations and extending 3SLP to handle heterophilic graphs remain the core focuses for future research.
Summary updated