Active Learning for Hidden Attributes in Networks

• Main Authors: Xiao Ran Yan, Jean-baptiste Rouquier, Yao Jia Zhu, Cristopher Moore
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Subjects: Weddell; Weddell Sea
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.2081; http://www.cs.unm.edu/~treport/tr/10-01/paper-2010-02.pdf

In many networks, vertices have hidden attributes that are correlated with the network’s topology. For instance, in social networks, people are more likely to be friends if they are demographically similar. In food webs, predators typically eat prey of lower body mass. We explore a setting in which the network’s topology is known, but these attributes are not. If each vertex can be queried, learning the value of its hidden attributes— but only at some cost—then we need an algorithm which chooses which vertex to query next, in order to learn as much as possible about the attributes of the remaining vertices. We assume that the network is generated by a probabilistic model, but we make no assumptions about the assortativity or disassortativity of the network. We then query the vertex with the largest mutual information between its type and that of the others (a well-known approach in active learning) or with the largest average agreement between two independent samples of the Gibbs distribution which agree on its type. We test these approaches on two networks with known attributes, the Karate Club network and a food web of species in the Weddell Sea. In several cases, we found that the average agreement algorithm performs better than mutual information. The algorithms appear to explore the network intelligently, first querying vertices at the centers of communities, and then querying vertices at the boundaries between communities. 1