Network Completion with Node Similarity
Authors:
Open Access
- 25 August 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 302-307
Abstract
This paper investigates the network completion problem, where it is assumed that only a small sample of a network (e.g., a complete or partially observed subgraph of a social graph) is observed and we would like to infer the unobserved part of the network. In this paper, we assume that besides the observed subgraph, side information about the nodes such as the pairwise similarity between them is also provided. In contrast to the original network completion problem where the standard methods such as matrix completion is inapplicable due the non-uniform sampling of observed links, we show that by effectively exploiting the side information, it is possible to accurately predict the unobserved links. In contrast to existing matrix completion methods with side information such as shared subsapce learning and matrix completion with transduction, the proposed algorithm decouples the completion from transduction to effectively exploit the similarity information. This crucial difference greatly boosts the performance when appropriate similarity information is used. The recovery error of the proposed algorithm is theoretically analyzed based on the richness of the similarity information and the size of the observed submatrix. To the best of our knowledge, this is the first algorithm that addresses the network completion with similarity of nodes with provable guarantees. Experiments on synthetic and real networks from Facebook and Google+ show that the proposed two-stage method is able to accurately reconstruct the network and outperforms other methods.Keywords
This publication has 14 references indexed in Scilit:
- Kernelized Probabilistic Matrix Factorization: Exploiting Graphs and Side Information2012
- Matrix co-factorization for recommendation with rich side information and implicit feedback2011
- What you see is not what you get: how sampling affects macroscopic features of biological networksInterface Focus, 2011
- The Network Completion Problem: Inferring Missing Nodes and Edges in Networks2011
- Link Prediction via Matrix Factorization2011
- A Singular Value Thresholding Algorithm for Matrix CompletionSIAM Journal on Optimization, 2010
- Missing and spurious interactions and the reconstruction of complex networksProceedings of the National Academy of Sciences, 2009
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Annotating gene function by combining expression data with a modular gene networkBioinformatics, 2007
- The link‐prediction problem for social networksJournal of the American Society for Information Science and Technology, 2007