Graffiti: node labeling in heterogeneous networks

ABSTRACT

We introduce a multi-label classification model and algorithm for labeling heterogeneous networks, where nodes belong to different types and different types have different sets of classification labels. We present a graph-based approach which models the mutual influence between nodes in the network as a random walk. When viewing class labels as "colors", the random surfer is "spraying" different node types with different color palettes; hence the name Graffiti. We demonstrate the performance gains of our method by comparing it to three state-of-the-art techniques for graph-based classification.

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: 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: Lise Getoor, Link mining: a new data mining challenge, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959253]
• 4: Lise Getoor , Ben Taskar, Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning), The MIT Press, 2007
• 5: Lise Getoor , Christopher P. Diehl, Link mining: a survey, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.3-12, December 2005 [doi>10.1145/1117454.1117456]
• 6: Kalervo Järvelin , Jaana Kekäläinen, IR evaluation methods for retrieving highly relevant documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41-48, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345545]
• 7: 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
• 8: Lan Nie , Brian D. Davison , Xiaoguang Qi, Topical link analysis for web search, 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.1148189]
• 9: Hyo-Jung Oh , Sung Hyon Myaeng , Mann-Ho Lee, A practical hypertext catergorization method using links and incrementally available class information, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.264-271, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345594]
• 10: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 11: Fei Wang , Changshui Zhang, Label propagation through linear neighborhoods, Proceedings of the 23rd international conference on Machine learning, p.985-992, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143968]
• 12: Ting-Fan Wu , Chih-Jen Lin , Ruby C. Weng, Probability Estimates for Multi-class Classification by Pairwise Coupling, The Journal of Machine Learning Research, 5, p.975-1005, 12/1/2004

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:
graph classification, web 2.0 ir