New perspectives and methods in link prediction

By Ryan Lichtenwalter, Jake T. Lussier, Nitesh V. Chawla. Knowledge Discovery and Data Mining, 2010

716 citations recorded by the source corpus.

This paper examines important factors for link prediction in networks and provides a general, high-performance framework for the prediction task. Link prediction in sparse networks presents a significant challenge due to the inherent disproportion of links that can form to links that do form. Previous research has typically approached this as an unsupervised problem. While this is not the first work to explore supervised learning, many factors significant in influencing and guiding classification remain unexplored. In this paper, we consider these factors by first motivating the use of a supervised framework through a careful investigation of issues such as network observational period, generality of existing methods, variance reduction, topological causes and degrees of imbalance, and sampling approaches. We also present an effective flow-based predicting algorithm, offer formal bounds on imbalance in sparse network link prediction, and employ an evaluation method appropriate for the observed imbalance. Our careful consideration of the above issues ultimately leads to a completely general framework that outperforms unsupervised link prediction methods by more than 30% AUC.

Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/fd29c0ee1564883fe84b20c21fb82dcbcb921b64

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 Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Inferring anchor links across multiple heterogeneous social networks (2013, background): “Unlike most prior work on link prediction [9, 13, 10, 23, 14] and network alignment [3], we assume that anchor links are one-to-one relationships among the two sets of user accounts (i.”
Link prediction in social networks: the state-of-the-art (2014, methodology): “• University of Notre Dame Lichtenwalter et al. presented a ﬂow-based predicting algorithm PropFlow [81], which is proportional to the probability based on a restricted random walk.”
SMOTE for Learning from Imbalanced Data: Progress and Challenges, Marking the 15-year Anniversary (2018, background): “The significance of this area of research continues to grow largely driven by the challenging problem statements from different application areas (such as face recognition, software engineering, social media, social networks, and medical diagnosis), providing a novel and contemporaneous set of chall”
Cross-domain collaboration recommendation (2012, background): “Researchers have studied various issues in social networks, such as network properties [6, 11] and generation processes [18], link predictions [19, 20, 21, 32] and recommendations [2, 7, 17].”
Dropout Training of Matrix Factorization and Autoencoder for Link Prediction in Sparse Graphs (2015, background): “MF+AE is also related to the supervised learning based methods [3, 13].”
Co-author Relationship Prediction in Heterogeneous Bibliographic Networks (2011, methodology): “Random walk measure along a meta path is defined as RWR(ai, aj) = PCR(ai,aj) PCR(ai,·) , which is a natural generalization of PropFlow [8].”
Inferring social ties across heterogenous networks (2012, methodology): “Recently, [22] designs a flow based method for link prediction.”
Exploiting place features in link prediction on location-based social networks (2011, background): “have presented a detailed analysis of challenges in link prediction systems, discussing imbalance problems and proposing to treat prediction separately for different classes of potential friends [17].”
Event-based social networks: linking the online and offline social worlds (2012, methodology): “A similar diffusion method has also been studied by [17] for link prediction.”
RolX: structural role extraction & mining in large graphs (2012, background): “In [19], the authors propose extracting topological features for pairs of nodes for link prediction.”
Negative Link Prediction in Social Media (2014, methodology): “Supervised methods consider the link prediction problem as a classiﬁcation problem by using the existence of links as labels and have several advantages over unsupervised methods such as superior performance, adapt-ability to diﬀerent data domains, and variance reduction [17].”
It's who you know: graph mining using recursive structural features (2011, background): “One study approaches link prediction as a supervised learning problem [21].”
Link Prediction via Matrix Factorization (2011, methodology): “One solution is un-dersampling the set of training dyads [14,21], but this has the disadvantage of necessarily throwing away information.”
Joint Link Prediction and Attribute Inference Using a Social-Attribute Network (2014, methodology): “Mapping link prediction to a classiﬁcation problem [Hasan et al. 2006; Lichtenwalter et al. 2010; Doppa et al. 2010] is another way to incorporate attributes.”
Recommender Systems (2016, neutral): “It is well known [355] that supervised methods for link prediction generally outperform unsupervised methods.”
Cross View Link Prediction by Learning Noise-resilient Representation Consensus (2017, methodology): “For example, Lichtenwalter et al. studied how to ensemble different measures for link prediction [12].”