Classifying networked entities with modularity kernels

ABSTRACT

Statistical machine learning techniques for data classification usually assume that all entities are i.i.d. (independent and identically distributed). However, real-world entities often interconnect with each other through explicit or implicit relationships to form a complex network. Although some graph-based classification methods have emerged in recent years, they are not really suitable for complex networks as they do not take the degree distribution of network into consideration. In this paper, we propose a new technique, Modularity Kernel, that can effectively exploit the latent community structure of networked entities for their classification. A number of experiments on hypertext datasets show that our proposed approach leads to excellent classification performance in comparison with the state-of-the-art methods.

REFERENCES

• 1: Ralitsa Angelova , Gerhard Weikum, Graph-based text classification: learn from your neighbors, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148254]
• 2: A. Argyriou, M. Herbster, and M. Pontil. Combining graph laplacians for semi-supervised learning. In Advances in Neural Information Processing Systems (NIPS), volume 18, pages 67?-74, Vancouver, Canada, 2005.
• 3: M. Belkin, I. Matveeva, and P. Niyogi. Regularization and semi-supervised learning on large graphs. In Proceedings of the 17th Annual Conference on Learning Theory (COLT), pages 624--638, Banff, Canada, 2004.
• 4: Mikhail Belkin , Partha Niyogi , Vikas Sindhwani, Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples, The Journal of Machine Learning Research, 7, p.2399-2434, 12/1/2006
• 5: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 6: Avrim Blum , Shuchi Chawla, Learning from Labeled and Unlabeled Data using Graph Mincuts, Proceedings of the Eighteenth International Conference on Machine Learning, p.19-26, June 28-July 01, 2001
• 7: Avrim Blum , John Lafferty , Mugizi Robert Rwebangira , Rajashekar Reddy, Semi-supervised learning using randomized mincuts, Proceedings of the twenty-first international conference on Machine learning, p.13, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015429]
• 8: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 9: S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang. Complex networks : Structure and dynamics. Physics Reports, 424(4-5):175--308, 2006.
• 10: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 11: Soumen Chakrabarti, Mining the Web: Discovering Knowledge from HyperText Data, Science & Technology Books, 2002
• 12: 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
• 13: O. Chapelle, B. Scholkopf, and A. Zien, editors. Semi-Supervised Learning. MIT Press, 2005.
• 14: O. Chapelle, J. Weston, and B. Scholkopf. Cluster kernels for semi-supervised learning. In Advances in Neural Information Processing Systems (NIPS), volume 15, pages 585--592, Vancouver, Canada, 2003.
• 15: F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
• 16: Fan Chung , Linyuan Lu, Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics), American Mathematical Society, Boston, MA, 2006
• 17: David Cohn , Huan Chang, Learning to Probabilistically Identify Authoritative Documents, Proceedings of the Seventeenth International Conference on Machine Learning, p.167-174, June 29-July 02, 2000
• 18: D. A. Cohn and T. Hofmann. The missing link - a probabilistic model of document content and hypertext connectivity. In Advances in Neural Information Processing Systems (NIPS), pages 430--436, Denver, CO, USA, 2000.
• 19: Mark Craven , Seán Slattery, Relational learning with statistical predicate invention: better models for hypertext, Machine Learning, v.43 n.1/2, p.97-119, April/May 2001 [doi>10.1023/A:1007676901476]
• 20: L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas. Comparing community structure identification. Journal of Statistical Mechanics, page P09008, 2005.
• 21: Lisa Getoor , Nir Friedman , Daphne Koller , Benjamin Taskar, Learning probabilistic models of link structure, The Journal of Machine Learning Research, 3, 3/1/2003
• 22: G. H. Golub and C. F. V. Loan. Matrix Computations. The Johns Hopkins University Press, 3rd edition, 1996.
• 23: M. Gustafsson, A. Lombardi, and M. Hornquist. Comparison and validation of community structures in complex networks. Physica A, 367:559--576, 2006.
• 24: Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen. Web content categorization using link information. Technical report, Stanford University, 2007.
• 25: Mark Herbster , Massimiliano Pontil , Lisa Wainer, Online learning over graphs, Proceedings of the 22nd international conference on Machine learning, p.305-312, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102390]
• 26: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 27: 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]
• 28: T. Joachims. Transductive learning via spectral graph partitioning. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 290--297, Washington, DC, 2003.
• 29: Thorsten Joachims , Nello Cristianini , John Shawe-Taylor, Composite Kernels for Hypertext Categorisation, Proceedings of the Eighteenth International Conference on Machine Learning, p.250-257, June 28-July 01, 2001
• 30: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 31: 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
• 32: Jennifer Neville , David Jensen, Dependency Networks for Relational Data, Proceedings of the Fourth IEEE International Conference on Data Mining, p.170-177, November 01-04, 2004
• 33: Mark Newman , Albert-Laszlo Barabasi , Duncan J. Watts, The Structure and Dynamics of Networks: (Princeton Studies in Complexity), Princeton University Press, Princeton, NJ, 2006
• 34: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 35: M. E. J. Newman. Detecting community structure in networks. The European Physical Journal B, 38:321--330, 2004.
• 36: M. E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 74:036104, 2006.
• 37: M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences USA, 103:8577--8582, 2006.
• 38: B. Scholkopf and A. J. Smola. Learning with Kernels. MIT Press, Cambridge, MA, 2002.
• 39: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 40: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 41: V. Sindhwani, M. Belkin, and P. Niyogi. The geometric basis of semi-supervised learning. In O. Chapelle, B. Scholkopf, and A. Zien, editors, Semi-Supervised Learning, chapter 12, pages 209--226. MIT Press, 2006.
• 42: Vikas Sindhwani , Partha Niyogi , Mikhail Belkin, Beyond the point cloud: from transductive to semi-supervised learning, Proceedings of the 22nd international conference on Machine learning, p.824-831, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102455]
• 43: Seán Slattery , Mark Craven, Combining Statistical and Relational Methods for Learning in Hypertext Domains, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.38-52, July 22-24, 1998
• 44: M. Szummer and T. Jaakkola. Partially labeled classification with markov random walks. In Advances in Neural Information Processing Systems (NIPS), pages 945--952, Vancouver, Canada, 2001.
• 45: B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence (UAI), pages 485--492, Edmonton, Alberta, Canada, 2002.
• 46: Adriano Veloso , Wagner Meira Jr. , Mohammed J. Zaki, Lazy Associative Classification, Proceedings of the Sixth International Conference on Data Mining, p.645-654, December 18-22, 2006 [doi>10.1109/ICDM.2006.96]
• 47: Q. Yang and X. Wu. 10 challenging problems in data mining research. International Journal of Information Technology and Decision Making, 5(4):597--604, 2006.
• 48: Yiming Yang , Seán Slattery , Rayid Ghani, A Study of Approaches to Hypertext Categorization, Journal of Intelligent Information Systems, v.18 n.2-3, p.219-241, March-May 2002 [doi>10.1023/A:1013685612819]
• 49: Tong Zhang , Alexandrin Popescul , Byron Dom, Linear prediction models with graph regularization for web-page categorization, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150510]
• 50: D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Scholkopf. Learning with local and global consistency. In Advances in Neural Information Processing Systems (NIPS), Vancouver and Whistler, Canada, 2003.
• 51: Dengyong Zhou , Jiayuan Huang , Bernhard Schölkopf, Learning from labeled and unlabeled data on a directed graph, Proceedings of the 22nd international conference on Machine learning, p.1036-1043, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102482]
• 52: D. Zhou, B. Scholkopf, and T. Hofmann. Semi-supervised learning on directed graphs. In Advances in Neural Information Processing Systems (NIPS), Vancouver, Canada, 2004.
• 53: Shenghuo Zhu , Kai Yu , Yun Chi , Yihong Gong, Combining content and link for classification using matrix factorization, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277825]
• 54: X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, Computer Sciences, University of Wisconsin-Madison, 2005. http://www.cs.wisc.edu/ ~jerryzhu/pub/ssl_survey.pdf.
• 55: X. Zhu, Z. Ghahraman, and J. D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 912--919, Washington, DC, 2003.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Experimentation, Performance

Keywords:
community discovery, graph mining, hypertext classification, kernel methods, semi-supervised learning