Effective label acquisition for collective classification

ABSTRACT

Information diffusion, viral marketing, and collective classification all attempt to model and exploit the relationships in a network to make inferences about the labels of nodes. A variety of techniques have been introduced and methods that combine attribute information and neighboring label information have been shown to be effective for collective labeling of the nodes in a network. However, in part because of the correlation between node labels that the techniques exploit, it is easy to find cases in which, once a misclassification is made, incorrect information propagates throughout the network. This problem can be mitigated if the system is allowed to judiciously acquire the labels for a small number of nodes. Unfortunately, under relatively general assumptions, determining the optimal set of labels to acquire is intractable. Here we propose an acquisition method that learns the cases when a given collective classification algorithm makes mistakes, and suggests acquisitions to correct those mistakes. We empirically show on both real and synthetic datasets that this method significantly outperforms a greedy approximate inference approach, a viral marketing approach, and approaches based on network structural measures such as node degree and network clustering. In addition to significantly improving accuracy with just a small amount of labeled data, our method is tractable on large networks.

REFERENCES

• 1: M. Bilgic and L. Getoor. VOILA: Efficient feature-value acquisition for classification. In AAAI, 2007.
• 2: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 3: D. A. Cohn, Z. Ghahramani, and M. I. Jordan. Active learning with statistical models. Journal of Artificial Intelligence Research, 4:129--145, 1996.
• 4: C. Lee Giles , Kurt D. Bollacker , Steve Lawrence, CiteSeer: an automatic citation indexing system, Proceedings of the third ACM conference on Digital libraries, p.89-98, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276685]
• 5: W. R. Gilks, S. Richardson, and D. J. Spiegelhalter. Markov Chain Monte Carlo in Practice. Interdisciplinary Statistics. Chapman & Hall/CRC, 1996.
• 6: R. A. Howard. Information value theory. IEEE Transactions on Systems Science and Cybernetics, 2(1):22--26, 1966.
• 7: David Jensen , Jennifer Neville , Brian Gallagher, Why collective inference improves relational classification, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014125]
• 8: M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul. An introduction to variational methods for graphical models. Machine Learning, 1999.
• 9: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 10: A. Krause and C. Guestrin. Optimal nonmyopic value of information in graphical models - efficient algorithms and theoretical limits. In IJCAI, 2005.
• 11: Jure Leskovec , Lada A. Adamic , Bernardo A. Huberman, The dynamics of viral marketing, ACM Transactions on the Web (TWEB), v.1 n.1, p.5-es, May 2007 [doi>10.1145/1232722.1232727]
• 12: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graph evolution: Densification and shrinking diameters, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.2-es, March 2007 [doi>10.1145/1217299.1217301]
• 13: Q. Lu and L. Getoor. Link based classification. In ICML, 2003.
• 14: S. Macskassy and F. Provost. A simple relational classifier. In Workshop on Multi-Relational Data Mining in conj. with KDD (MRDM), 2003.
• 15: Sofus A. Macskassy , Foster Provost, Classification in Networked Data: A Toolkit and a Univariate Case Study, The Journal of Machine Learning Research, 8, p.935-983, 5/1/2007
• 16: Andrew McCallum , Kamal Nigam, Employing EM and Pool-Based Active Learning for Text Classification, Proceedings of the Fifteenth International Conference on Machine Learning, p.350-358, July 24-27, 1998
• 17: Andrew Kachites McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, Automating the Construction of Internet Portals with Machine Learning, Information Retrieval, v.3 n.2, p.127-163, July 2000 [doi>10.1023/A:1009953814988]
• 18: L. McDowell, K. M. Gupta, and D. W. Aha. Cautious inference in collective classification. In AAAI, 2007.
• 19: J. Neville and D. Jensen. Iterative classification in relational data. In SRL Workshop in AAAI, 2000.
• 20: M. E. J. Newman. Mixing patterns in networks. Physical Review E, 67(2):026126, Feb 2003.
• 21: Foster Provost , Prem Melville , Maytal Saar-Tsechansky, Data acquisition and cost-effective predictive modeling: targeting offers for electronic commerce, Proceedings of the ninth international conference on Electronic commerce, August 19-22, 2007, Minneapolis, MN, USA [doi>10.1145/1282100.1282172]
• 22: Matthew J. Rattigan , Marc Maier , David Jensen Bin Wu , Xin Pei , JianBin Tan , Yi Wang, Exploiting Network Structure for Active Inference in Collective Classification, Proceedings of the Seventh IEEE International Conference on Data Mining Workshops, p.429-434, October 28-31, 2007 [doi>10.1109/ICDMW.2007.41]
• 23: Matthew Richardson , Pedro Domingos, Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775057]
• 24: P. Sen, G. M. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. Collective classification in network data. Technical Report CS-TR-4905, University of Maryland, College Park, 2008.
• 25: Victor S. Sheng , Charles X. Ling, Feature value acquisition in testing: a sequential batch test algorithm, Proceedings of the 23rd international conference on Machine learning, p.809-816, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143946]
• 26: B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In UAI, 2002.
• 27: Simon Tong , Daphne Koller, Support vector machine active learning with applications to text classification, The Journal of Machine Learning Research, 2, p.45-66, 3/1/2002
• 28: J. Yedidia, W.T.Freeman, and Y. Weiss. Generalized belief propagation. In NIPS, 2000.
• 29: Bianca Zadrozny , Charles Elkan, Learning and making decisions when costs and probabilities are both unknown, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.204-213, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502540]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms

Keywords:
active inference, collective classification, label acquisition