Using ghost edges for classification in sparsely labeled networks

ABSTRACT

We address the problem of classification in partially labeled networks (a.k.a. within-network classification) where observed class labels are sparse. Techniques for statistical relational learning have been shown to perform well on network classification tasks by exploiting dependencies between class labels of neighboring nodes. However, relational classifiers can fail when unlabeled nodes have too few labeled neighbors to support learning (during training phase) and/or inference (during testing phase). This situation arises in real-world problems when observed labels are sparse.

In this paper, we propose a novel approach to within-network classification that combines aspects of statistical relational learning and semi-supervised learning to improve classification performance in sparse networks. Our approach works by adding "ghost edges" to a network, which enable the flow of information from labeled to unlabeled nodes. Through experiments on real-world data sets, we demonstrate that our approach performs well across a range of conditions where existing approaches, such as collective classification and semi-supervised learning, fail. On all tasks, our approach improves area under the ROC curve (AUC) by up to 15 points over existing approaches. Furthermore, we demonstrate that our approach runs in time proportional to L • E, where L is the number of labeled nodes and E is the number of edges.

REFERENCES

• 1: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 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: F. Chung. Spectral graph theory. Number 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Sociaty, 1997.
• 4: W. W. Cohen. Enron email data set. http://www.cs.cmu.edu/ enron/, 2004.
• 5: Nathan Eagle , Alex (Sandy) Pentland, Reality mining: sensing complex social systems, Personal and Ubiquitous Computing, v.10 n.4, p.255-268, March 2006 [doi>10.1007/s00779-005-0046-3]
• 6: S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 6:721--741, 1984.
• 7: Lisa Getoor , Nir Friedman , Daphne Koller , Benjamin Taskar, Learning probabilistic models of link structure, The Journal of Machine Learning Research, 3, 3/1/2003
• 8: D. Jensen. Proximity HEP-TH database. http://kdl.cs.umass.edu/data/hepth/hepth-info.html, 2003.
• 9: V. Krebs. Books about U.S. Politics. http://www.orgnet.com/, 2004.
• 10: Q. Lu and L. Getoor. Link-based classification. In ICML, pages 496--503, 2003.
• 11: S. Macskassy and F. Provost. A simple relational classifier. In Notes of the 2nd Workshop on Multi-relational Data Mining at KDD, 2003.
• 12: 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
• 13: S. A. Macskassy. Improving learning in networked data by combining explicit and mined links. In AAAI, pages 590--595, 2007.
• 14: L. McDowell, K. M. Gupta, and D. W. Aha. Cautious inference in collective classification. In AAAI, pages 596--601, 2007.
• 15: Jennifer Neville , David Jensen, Relational Dependency Networks, The Journal of Machine Learning Research, 8, p.653-692, 5/1/2007
• 16: Jennifer Neville , David Jensen , Lisa Friedland , Michael Hay, Learning relational probability trees, 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.956830]
• 17: P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. Collective classification in network data. AI Magazine (Special Issue on AI and Networks), forthcoming.
• 18: B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In UAI, pages 485--492, 2002.
• 19: Hanghang Tong , Christos Faloutsos , Jia-Yu Pan, Fast Random Walk with Restart and Its Applications, Proceedings of the Sixth International Conference on Data Mining, p.613-622, December 18-22, 2006 [doi>10.1109/ICDM.2006.70]
• 20: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 21: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 22: X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, Department of Computer Sciences, University of Wisconsin, Madison, 2005.
• 23: X. Zhu, Z. Ghahramani, and J. D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, pages 912--919, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
collective classification, random walk, semi-supervised learning, statistical relational learning