Difference between revisions of "Link propagation: A fast semi-supervised learning algorithm for link prediction"
(Created page with 'Link propagation: A fast semi-supervised learning algorithm for link prediction == Citation == Kashima H., Kato T. , Yamanishi Y. , Sugiyama M and Tsuda K (May-2009) Link Pro…') |
|||
Line 7: | Line 7: | ||
== Online version == | == Online version == | ||
− | [http://www.kyb.tuebingen.mpg.de/fileadmin/user_upload/files/publications/kashima_sdm_5654[0].pdf PDF] | + | [[http://www.kyb.tuebingen.mpg.de/fileadmin/user_upload/files/publications/kashima_sdm_5654[0].pdf PDF]] |
== Summary == | == Summary == |
Revision as of 21:10, 1 October 2012
Link propagation: A fast semi-supervised learning algorithm for link prediction
Contents
Citation
Kashima H., Kato T. , Yamanishi Y. , Sugiyama M and Tsuda K (May-2009) Link Propagation: A Fast Semi-supervised Learning Algorithm for Link Prediction In: SDM 2009, 2009 SIAM International Conference on Data Mining, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, 1099-1110.
Online version
[[0.pdf PDF]]
Summary
This paper adopts a semi-supervised algorithm known as "label propagation" and successfully transfers the original one which focus on node labeling to solving link (edge) prediction task. It also solves the problem of combining topological data and node information in the prediction algorithm.
Key Ideas
- Mapping between node labeling and link prediction.
http://www.aladdin.cs.cmu.edu/papers/pdfs/y2003/zgl.pdf Label Propagation is a semi-supervised algorithm which successfully combines topological features and node information in predicting nodes' label(assigning a label for each node on a graph). And the paper we are talking about find a mapping between node labeling and link prediction by treating each link as a triplet , where and represent two nodes and represents a type of link. As the method of this paper also supports the prediction of multiple type of link, if there is only one type of link, we can just set to 1 constantly. And we treat this triplet as one node and consider a problem of assigning two possible label, 0 or 1, for each this triplet and 1 stands for this link exists and 0 otherwise.
The Original Node Labeling Algorithm's Idea
- The goal is to derive a for every node which means the probability for this node to have a label "1". And function has to agree on the training data which we already know the labels.
- With an input of similarity matrix of nodes and the base assumption is that similar nodes should have similar labels
- Have a cost function on the assumption and the goal is to find a which minimize the loss function
- Derive that the minimum loss labels are just a weighted average of neighbor points
Failed to parse (syntax error): {\displaystyle f(j) = \frac{1}{d_j}\sum_{i\~j}{w_{i,j}f(i)} }
Some Modifications
- The loss function is changed
Data sets and Experiments
The paper works with five co-authorship networks, obtained from the author lists of articles contained in five sections of the physics e-Print arXiv. The training interval is defined to be the 3 years from 1994 through 1996 and test interval to be the 3 years from 1997 through 1999.
Each link predictor outputs a ranked list of pairs and the paper takes the first , which is the number of new links from the test set, and count how many of edges from these are in the test set.
Result
The performance is compared with a random predictor.
We can see that Adamic/Adar outperforms other methods and for more detailed results please refer to the paper.
Related papers
Most link prediction solutions can fall to two directories, one is to use topological features and the other is to use node or edge information.
Link propagation: A fast semi-supervised learning algorithm for link prediction suggests a semi-supervised framework which need a node similarity matrix as input. Many applications like protein-protein interactions and social networks are able to provide this information.
Supervised Random Walks: Predicting and Recommending Links in Social Networks adopts a random walk framework and use edge and node information as features to train a transition rate over each edge to maximize the probability of random walk stopping time on positive nodes.
Study Plan
- About Adamic/Adar score
- To understand which graph information these features represent