Source-linked AI summary
Supervised Random Walks: Predicting and Recommending Links in Social Networks
L. Backstrom, J. Leskovec
TL;DR
Link prediction must infer future interactions while combining sparse network structure with rich node and edge attributes. The paper introduces Supervised Random Walks, which learn feature-based edge strengths to guide graph walks toward future-link destinations. Experiments on Facebook and collaboration networks report improvements over unsupervised and feature-extraction-based supervised approaches.
Problem
Link prediction asks which interactions among existing network members will occur in the near future or which existing interactions are missing.
Method
Supervised Random Walks learn edge strengths from node and edge attributes to bias a PageRank-like walk toward positive future-link nodes.
Results
The approach outperforms state-of-the-art unsupervised and feature-extraction-based supervised approaches on Facebook and collaboration networks.
Takeaways & Limitations
The framework combines rich attributes with network structure without network feature generation and extends beyond link prediction to ranking-based tasks.
Takeaways & Limitations
The optimization is generally nonconvex, so gradient descent methods are not guaranteed to find a global minimum.
Abstract
from arXiv · showhide
Predicting the occurrence of links is a fundamental problem in networks. In the link prediction problem we are given a snapshot of a network and would like to infer which interactions among existing members are likely to occur in the near future or which existing interactions are we missing. Although this problem has been extensively studied, the challenge of how to effectively combine the information from the network structure with rich node and edge attribute data remains largely open. We develop an algorithm based on Supervised Random Walks that naturally combines the information from the network structure with node and edge level attributes. We achieve this by using these attributes to guide a random walk on the graph. We formulate a supervised learning task where the goal is to learn a function that assigns strengths to edges in the network such that a random walker is more likely to visit the nodes to which new links will be created in the future. We develop an efficient training algorithm to directly learn the edge strength estimation function. Our experiments on the Facebook social graph and large collaboration networks show that our approach outperforms state-of-the-art unsupervised approaches as well as approaches that are based on feature extraction.
1. INTRODUCTION
Link prediction seeks to forecast future edges from a network snapshot, but combining network structure with node and edge attributes remains challenging. Supervised Random Walks addresses this by learning attribute-guided walks and outperforms established unsupervised and feature-based supervised approaches.
- Problem: Link prediction forecasts edges added between an observed time t and a future time t′, or recommends likely new connections.The task can also illuminate mechanisms of individual edge creation and support social-network applications.
- Challenges: Extreme sparsity makes naïve no-edge predictions highly accurate but practically useless in large networks.A typical Facebook user connects to about 100 of more than 500 million nodes.
- Challenges: A central open challenge is combining network structure with node and edge characteristics in a principled way.Relevant attributes include demographics, interests, interaction information, and social proximity.
- Approach: Supervised Random Walks learns to bias a PageRank-like walk so it visits future-link destinations more often than other nodes.Node and edge features guide learned edge strengths and transition probabilities.
- Approach: The method directly and efficiently learns the edge-strength function parameters rather than imposing an ad hoc strength heuristic.The training formulation uses gradients of random-walk scores and an efficient estimation procedure.
- Results: Experiments on Facebook and large collaboration networks outperform state-of-the-art unsupervised and feature-extraction-based supervised approaches.The approach requires no complex network feature extraction or domain expertise.
2. SUPERVISED RANDOM WALKS
The framework combines graph-based node ranking with supervised learning over node and edge features. It learns edge strengths so random walks rank positive destinations above negative candidates, using a soft regularized objective and acknowledging nonconvex optimization.
- Motivation: Classification formulations face severe class imbalance and cumbersome feature extraction, especially for network connectivity patterns.Positive future-link nodes are a small fraction of all candidates, while useful structural features are difficult to design.
- Framework: Supervised Random Walks combine random-walk proximity with node and edge attributes by learning transition probabilities from feature vectors.The learned walk is biased toward nodes expected to receive links from source node s.
- Framework: For each edge, a parameterized function maps its feature vector to an edge strength representing the random-walk transition probability.These strengths determine which paths the walk is more likely to traverse.
- Prediction: A random walk with restarts produces stationary node probabilities, and top-ranked candidates are predicted as future destinations.The ranking is computed after strengths are assigned to all edges.
- Optimization: Training optimizes parameters so positive destinations receive higher PageRank scores than negative candidates.The objective prefers a short parameter vector for regularization.
- Optimization: Soft constraints penalize violated positive-over-negative rankings while regularization trades model complexity against fit.The loss is zero when a negative candidate scores below a positive destination and positive otherwise.
- Limitations: The optimization is generally nonconvex, so gradient descent is not guaranteed to find a global minimum.The authors use multiple starting points to seek a good solution.
3. EXPERIMENTS ON SYNTHETIC DATA
Synthetic experiments test whether Supervised Random Walks recover edge-strength parameters and classify future destinations under deterministic and probabilistic generation, including noisy attributes. The learned model performs strongly in both settings and remains robust as noise increases.
- Synthetic data: The experiments generate scale-free graphs, edge features, and destination/no-link training data to test recovery of the original edge-strength model.The synthetic graphs contain 10,000 nodes, and attributes are perturbed with Gaussian noise of variance σ2.
- Evaluation: AUC evaluates classification across 50 held-out synthetic graphs, where 1.0 is perfect classification and 0.5 is random guessing.Of 100 generated graphs, 50 train the weights and 50 serve as test graphs.
- Deterministic destinations: In the deterministic case, performance is perfect without noise, and the learned parameters recover [+1, −1] almost exactly.As noise rises, performance decreases and the learned parameter magnitudes shrink.
- Probabilistic destinations: In the probabilistic case, the algorithm outperforms the true-parameter model at p = 0.01 with or without noise.It also continues to outperform the baseline that ignores edge strengths as noise increases.
- Robustness: The learned solution is invariant to parameter initialization, and the validated procedure is then applied to real social networks.The reported convergence holds regardless of the starting parameter vector.
4. EXPERIMENTAL SETUP
The real-data evaluation covers physics co-authorship networks and Facebook Iceland, using temporally defined future links and node, edge, and interaction features. Evaluation emphasizes ranking likely future links with AUC and Precision at Top 20, often within two hops.
- Datasets: Experiments use four physics co-authorship networks and a complete Facebook network of Iceland.The Facebook graph is based on its November 1, 2009 state.
- Evaluation methodology: The evaluation focuses on two-hop candidates because more than half of online-social-network edges close triangles, including 92% in Facebook Iceland.Restricting the graph also makes Supervised Random Walks faster.
- Co-authorship networks: Co-authorship predictions target future edges of active authors with degree ku ≥ 10 and at least five triangle-closing links.The source graph is extracted at the time each author creates their ku/2-th edge.
- Features: Features include author and paper attributes, title similarity, co-authorship timing, edge age, initiator identity, communication, observation, and common-friend counts.Facebook edges receive seven features, while each co-authorship edge receives six listed features.
- Facebook network: The Facebook destinations are friendships formed between November 1, 2009 and January 13, 2010, with active sources required to have |D| > 20.Two-hop neighborhoods are pruned because users can have millions of candidates, while few mutual friends predict very unlikely friendships.
- Evaluation methodology: AUC and Precision at Top 20 evaluate held-out source nodes, measuring ranking quality and how many recommended top-20 nodes actually receive links.Half of the source nodes train the model and half test it.
5. EXPERIMENTS ON REAL DATA
Experiments on five real datasets evaluate design choices and show that Supervised Random Walks perform strongly against unweighted and feature-based baselines. The method benefits from WMW loss and typed edge weights while avoiding complex feature extraction.
- Experimental setup: Five real datasets—four co-authorship networks and Facebook Iceland—are used to evaluate Supervised Random Walks and several algorithmic choices.The evaluation covers loss functions, edge-strength functions, restart parameter α, regularization, and edge-type-specific weights.
- Loss function: WMW loss improves AUC and Prec@20, whereas squared and Huber losses perform little better than unweighted PageRank despite reducing their losses.The authors therefore use WMW loss for the remainder of the experiments.
- Edge-strength function: The edge-strength function has little performance impact; logistic weights are recommended because exponential weights can underflow or overflow.The experiments provide slight evidence favoring the logistic function while finding overall performance comparable.
- Restart parameter: α = 0.3 performs best for unweighted walks, while weighted walks perform similarly across α from 0.3 to 0.7.The role of α diminishes when the algorithm can learn differentiated edge strengths.
- Network-specific features: Typed edge weights provide significant benefit, and adding the common-friends feature increases Facebook link probability by about 50% but decreases it by 37% in co-authorship networks.The feature's effect therefore differs across network domains.
- Real-data results: SRW achieves AUC 0.7–0.8 and Prec@20 4.2–7.6, outperforming unweighted RWR and feature-based methods; Facebook Prec@20 improves by 11% relative.On co-authorship networks, the reported relative improvements are 6% in AUC and nearly 12% in Prec@20.
6. CONCLUSION
Supervised Random Walks combines rich node and edge features with network structure for link prediction and recommendation. The framework also applies to other graph-based node-ranking problems.
- Supervised Random Walks guides random walks toward desired target nodes using node and edge attribute data.The method combines these features with network structure to make predictions.
- Experiments on Facebook and co-authorship networks show good generalization and overall performance.
- The approach improves over Random Walks with Restarts and compares favorably with supervised methods requiring feature extraction.It requires no network feature generation.
- Supervised Random Walks can rank nodes for recommendations, anomaly detection, missing-link identification, and expertise search.