Supervised random walks: predicting and recommending links in social networks

By Lars Backstrom, Jure Leskovec. 2010

1,152 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

node2vec: Scalable Feature Learning for Networks (2016, background): “Link prediction is useful in a wide variety of domains; for instance, in genomics, it helps us discover novel interactions between genes, and in social networks, it can identify real-world friends [2, 34].”
Poisoning Attacks to Graph-Based Recommender Systems (2018, methodology): “ating scoresrv to the system. 11: R R [rv. 12: end for 13: return rv 1 ;rv 2 ; ;rv m . function: lu = Õ i2L u g„pui put”; (4) whereg„x”= 1 1+exp„xšb” is called the Wilcoxon-Mann-Whitney loss function [3] andb is a parameter called width. In the machine learning community, the Wilcoxon-Mann-Whitney l”
Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time (2017, background): “However, classical recommender systems that consider catalogs that only contain millions of items (movies [5, 18], videos [4, 7, 10], friends to follow [2, 14, 15]).”
FAST-PPR: scaling personalized pagerank estimation for large graphs (2014, background): “hem infeasible for large networks when = O(1=n) or O(log(n)=n). In addition to social-search, PPR is also used for a variety of other tasks across dierent domains: friend recommendation on Facebook [7], who to follow on Twitter [8], graph partitioning [9], community detection [10], and other applica”
Inferring social ties across heterogenous networks (2012, background): “[2] propose a supervised random walk algorithm to estimate the strength of social links.”
Link prediction in social networks: the state-of-the-art (2014, background): “It combines the network structure with the features of nodes and edges of the network into a uniﬁed link prediction algorithm [55].”
Distance-Aware DAG Embedding for Proximity Search on Heterogeneous Graphs (2018, positive): “Supervised Random Walk (SRW) (Backstrom and Leskovec 2011) assigns different edge weights to bias the random walk for different relations.”
WTF: the who to follow service at Twitter (2013, methodology): “We adopt a standard formulation of user recommendation as a binary classification problem [10, 1].”
Graph convolutional networks: a comprehensive review (2019, background): “Graphs naturally arise in many real-world applications, including social analysis [1], fraud detection [2, 3], traffic prediction [4], computer vision [5], and many more.”
You Are Who You Know and How You Behave: Attribute Inference Attacks via Users' Social Friends and Behaviors (2016, background): “Therefore, the attacker could adapt supervised random walk [3] to learn the link weights.”
ClusCite: effective citation recommendation by information network-based clustering (2014, methodology): “Paper II [2] Supervised Random Walks: Predicting and Recommending Links in Social Networks Quasi-Newton method”
The science of science: from the perspective of complex systems (2017, methodology): “Backstorm and Leskovec [273] proposed an algorithm based on supervised random walks and validate it on an ArXiv dataset.”