Learning from Labeled and Unlabeled Vertices in Networks
Wei Ye (University of Munich);Linfei Zhou (University of Munich);Dominik Mautz (University of Munich);Claudia Plant (University of Vienna);Christian Böhm (University of Munich)
Abstract
Networks such as social networks, citation networks, protein-protein interaction networks, etc., are prevalent in real world. However, only very few vertices have labels compared to large amount of unlabeled vertices. For example, in social networks, not every user provides his/her profile information such as the personal interests which are better for social networking advertising. Can we leverage the limited user information and friendship network wisely to infer the likely labels of unlabeled users? In this paper, we propose a semi-supervised learning framework called weighted-vote Geometric Neighbor classifier (wvGN) to infer the likely labels of unlabeled vertices. wvGN exploits random walks to explore not only local but also global neighborhood information of a vertex. Then the label of the vertex is determined by the accumulated local and global neighborhood information. Specifically, wvGN optimizes a proposed objective function by a search strategy which is based on the gradient and coordinate descent methods. The search strategy iteratively conducts a coarse search and a fine search to escape from local optima. Extensive experiments on various synthetic and real-world data verifies the effectiveness of wvGN compared to the state-of-the-art approaches.
