Unsupervised Link Selection in Networks

16th International Conference on Artificial Intelligence and Statistics

Quanquan Gu Charu Aggarwal Jiawei Han ; IBM T.J. Watson Research Center ; Dept. of Computer Science

PID  :  121186

来源: CEUR

【 摘 要 】

Realworld networks are often noisy, and the existing linkage structure may not be reli able. For example, a link which connects nodes from different communities may affect the group assignment of nodes in a negative way. In this paper, we study a new problem called link selection, which can be seen as the network equivalent of the traditional feature selection problem in machine learning. More specifically, we investigate unsupervised link selection as follows: given a network, it se lects a subset of informative links from the original network which enhance the quality of community structures. To achieve this goal, we use Ratio Cut size of a network as the quality measure. The resulting link selection approach can be formulated as a semidefinite programming problem. In order to solve it efficiently, we propose a backward elimina tion algorithm using sequential optimization. Experiments on benchmark network datasets