Link Prediction via Subgraph Embedding-Based Convex Matrix Completion

Zhu Cao, Linlin Wang, Gerard de MeloAAAI 2018 · DOI

Abstract

SEMAC (Subgraph Embedding-Based Convex Matrix Completion) is a novel framework for link prediction that learns node representations by embedding local subgraphs and refining them through convex matrix completion. By moving beyond simple node-to-node transitions and utilizing nuclear norm regularization, it captures complex topological features while effectively filtering out network noise. Experimental results on diverse real-world networks demonstrate that SEMAC consistently outperforms state-of-the-art methods like node2vec and DeepWalk, achieving significant improvements in AUC while maintaining linear scalability.

Introduction

Link prediction—predicting whether a connection exists between two nodes—is a cornerstone of network science, powering applications from friend recommendations to drug discovery. However, real-world networks are often "partially observed" and contain significant noise. Traditional methods generally fall into two categories: simple heuristics like Common Neighbors, which miss deep structural patterns, and representation learning methods like DeepWalk or node2vec. The latter often rely on models that implicitly assume non-observed edges are non-existent, a problematic assumption in incomplete networks. SEMAC bridges this gap by capturing irregular topological features while handling sparsity through a convex optimization framework.

Methodology

SEMAC operates through a five-stage pipeline designed to capture fine-grained local neighborhood information and denoise the network structure.

The SEMAC framework architecture, illustrating the flow from network input to subgraph embedding and matrix completion.
  1. Subgraph Extraction: The algorithm uses Breadth-First Search (BFS) to extract subgraphs at various depths around each node, creating a vocabulary of structural patterns.
  2. Radial Contextualization: The model identifies how subgraphs at different depths relate to one another, capturing the evolution of local structures.
  3. PPMI Matrix Construction: A Positive Pointwise Mutual Information (PPMI) matrix is computed based on these subgraph-context relationships.
  4. Convex Matrix Completion: This is the core innovation. Using Nuclear Norm Regularization (NNR) via the SOFT-IMPUTE algorithm, SEMAC treats missing entries as truly unknown rather than zero. This iterative process finds the lowest-rank matrix that fits the observed data, effectively filtering out noise.
  5. Node Embedding & Prediction: Subgraph embeddings are concatenated into a final node vector, and link probability is calculated using cosine similarity.

Experimental Results

The model was evaluated on several diverse real-world datasets, including Facebook social circles, Wikipedia page links, Coauthorship networks, and Protein-Protein Interaction (PPI) biological networks.

Comparison of AUC scores across various datasets and baseline methods, showing SEMAC's consistent superior performance.

As shown in the table above, SEMAC consistently outperformed all baselines, including heuristic indices and advanced embedding methods like node2vec and GraRep. Key findings include:

  • Accuracy: SEMAC achieved an absolute improvement in AUC of 0.8% to 2.9% over the second-best performing algorithms.
  • Noise Resistance: On the Facebook dataset, the model reached a peak AUC of 98% within just 10 iterations of the rank minimization process.
  • Scalability: Despite its mathematical complexity, SEMAC demonstrates linear scalability $O(n)$. In tests on synthetic Erdős–Rényi graphs, it successfully processed a graph with 1 million nodes and 10 million edges in approximately 7.4 hours on standard hardware.

Discussion and Conclusion

SEMAC's success stems from its ability to prioritize subgraphs over individual nodes and its use of convex optimization to avoid local minima. The iterative denoising provided by nuclear norm regularization allows it to preserve core structural signals while discarding spurious edges. Future work may involve extending the framework to handle edge heterogeneity (e.g., in PPI networks where links have different biological meanings) and incorporating node-specific side information like text or user profiles.

Summary updated

BibTeX
@inproceedings{cao2018link,
  author = {Zhu Cao and Linlin Wang and Gerard de Melo},
  title = {{Link Prediction via Subgraph Embedding-Based Convex Matrix Completion}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11655},
}
Figure