Elamur Research⌕
☰
home / papers / 2008 / Collective Classification in Network Data

Collective Classification in Network Data

Paper · 2008 · Prithviraj Sen, Galileo Namata, Mustafa Bilgic et al.

Summary

Many datasets come as graphs: web pages joined by hyperlinks, people joined by communication links, papers joined by citations. Labelling each node in isolation ignores that linked nodes tend to share labels, and the neighbours' labels are often unknown too. The authors survey collective classification, which predicts all unknown labels jointly. It draws on three signals: a node's own attributes, the observed attributes and labels of its neighbours, and the neighbours' still-unknown labels. Exact inference is NP-hard in general, so the report focuses on four approximate methods in two families. The first relies on local conditional classifiers (iterative classification, Gibbs sampling). The second optimizes one global objective (loopy belief propagation, mean-field relaxation labeling). Each method gets pseudo-code, a running webpage example, theoretical motivation and practical advice, and all four are compared on synthetic and real-world networks. The supplied excerpt notes that ICA converges in a few iterations while Gibbs sampling needs many more; the detailed accuracy results sit in the omitted part. The paper remains a standard introduction to node classification in networks.

Key points

  • Covers four inference algorithms: iterative classification (ICA), Gibbs sampling (GS), loopy belief propagation (LBP, also called the sum-product algorithm) and mean-field relaxation labeling (MF).
  • Neighbourhoods vary in size, so ICA turns them into fixed-length feature vectors with aggregation operators such as count or mode. This lets a single local classifier (e.g., a decision tree or an SVM) be reused for every node.
  • In the reported setup, GS runs 200 burn-in iterations plus 800 sampling iterations, making it much slower than ICA.
  • Related work traces the ideas back to relaxation labeling in computer vision, Besag's iterated conditional modes, and turbo-code decoding (which led to LBP). The authors list heterogeneous networks as an open research direction.
  • The text is also available as UMD technical report CS-TR-4905 / UMIACS-TR-2008-04 (University of Maryland and Lawrence Livermore National Laboratory).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of Maryland, College ParkCollege Park · United States141 works · 29,174 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksPhysics and Astronomy · 52 worksStatistical and Nonlinear Physics · 47 works

Cite

Cite as Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher and Tina Eliassi-Rad. 2008. Collective Classification in Network Data. AI Magazine 29(3).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1609/aimag.v29i3.2157

@article{sen2008collective,
  title = {{Collective Classification in Network Data}},
  author = {Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher and Tina Eliassi-Rad},
  journal = {AI Magazine 29(3)},
  year = {2008},
  doi = {10.1609/aimag.v29i3.2157},
  url = {https://doi.org/10.1609/aimag.v29i3.2157}
}

References

68 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aji, S. M., and McEliece, R. J. 2001. The generalized distributive law and free energy minimization. In Proceedings of the 39th Allerton Conference on Communication, Control and Computing. find
  2. Anguelov, D.; Taskar, B.; Chatalbashev, V.; Koller, D.; Gupta, D.; Heitz, G.; and Ng, A. 2005. Discriminative learning of markov random fields for segmentation of 3d scan data. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition. find
  3. Barabasi, A.-L., and Albert, R. 2002. Statistical mechanics of complex networks. Reviews of Modern Physics 74:47–97. find
  4. Berrou, C.; Glavieux, A.; and Thitimajshima, P. 1993. Near Shannon limit error-correcting coding and decoding: Turbo codes. In Proceedings of IEEE International Communications Conference. find
  5. Besag, J. 1986. On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society. find
  6. Boykov, Y.; Veksler, O.; and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence. find
  7. Carvalho, V., and Cohen, W. W. 2005. On the collective classification of email speech acts. In Special Interest Group on Information Retrieval. find
  8. Chakrabarti, S.; Dom, B.; and Indyk, P. 1998. Enhanced hypertext categorization using hyperlinks. In International Conference on Management of Data. find
  9. Chen, L.; Wainwright, M.; Cetin, M.; and Willsky, A. 2003. Multitarget-multisensor data association using the tree-reweighted max-product algorithm. In SPIE Aerosense conference. find
  10. Cohn, D., and Hofmann, T. 2001. The missing link—a probabilistic model of document content and hypertext connectivity. In Neural Information Processing Systems. find
  11. Dechter, R. 1996. Bucket elimination: A unifying framework for probabilistic inference. In Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence. find
  12. Friedman, N.; Getoor, L.; Koller, D.; and Pfeffer, A. 1999. Learning probabilistic relational models. In International Joint Conference on Artificial Intelligence. find
  13. Gallagher, B., and Eliassi-Rad, T. 2007a. An evaluation of experimental methodology for classifiers of relational data. In Workshop on Mining Graphs and Complex Structures, IEEE International Conference on Data Mining (ICDM). find
  14. Gallagher, B., and Eliassi-Rad, T. 2007b. Leveraging network structure to infer missing values in relational data. Technical Report UCRL-TR-231993, Lawrence Livermore National Laboratory. find
  15. Geman, S., and Geman, D. 1984. Stochastic relaxation, gibbs distributions and the bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence. find
  16. Getoor, L.; Friedman, N.; Koller, D.; and Taskar, B. 2001a. Probabilistic models of relational structure. In Proc. ICML01. find
  17. Getoor, L.; Segal, E.; Taskar, B.; and Koller, D. 2001b. Probabilistic models of text and link structure for hypertext classification. In IJCAI Workshop on Text Learning: Beyond Supervision. find
  18. Getoor, L. 2005. Advanced Methods for Knowledge Discovery from Complex Data. Springer. chapter Link-based classification. find
  19. Giles, C. L.; Bollacker, K.; and Lawrence, S. 1998. Citeseer: An automatic citation indexing system. In ACM Digital Libraries. find
  20. Gilks, W. R.; Richardson, S.; and Spiegelhalter, D. J. 1996. Markov Chain Monte Carlo in Practice. Interdisciplinary Statistics. Chapman & Hall/CRC. find
  21. Gupta, R.; Diwan, A. A.; and Sarawagi, S. 2007. Efficient inference with cardinality-based clique potentials. In Proceedings of the International Conference on Machine Learning. find
  22. Huang, C., and Darwiche, A. 1994. Inference in belief networks: A procedural guide. International Journal of Approximate Reasoning. find
  23. Hummel, R., and Zucker, S. 1983. On the foundations of relaxation labeling processes. In IEEE Transactions on Pattern Analysis and Machine Intelligence. find
  24. Jensen, D., and Neville, J. 2002. Linkage and autocorrelation cause feature selection bias in relational learning. In ICML ’02: Proceedings of the Nineteenth International Conference on Machine Learning. find
  25. Jensen, D.; Neville, J.; and Gallagher, B. 2004. Why collective inference improves relational classification. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. find
  26. Jordan, M. I.; Ghahramani, Z.; Jaakkola, T. S.; and Saul, L. K. 1999. An introduction to variational methods for graphical models. Machine Learning. find
  27. Kleinberg, J., and Tardos, E. 1999. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. In IEEE Symposium on Foundations of Computer Science. find
  28. Knobbe, A.; deHaas, M.; and Siebes, A. 2001. Propositionalisation and aggregates. In Proceedings of the Fifth European Conference on Principles of Data Mining and Knowledge Discovery. find
  29. Kramer, S.; Lavrac, N.; and Flach, P. 2001. Propositionalization approaches to relational data mining. In Dzeroski, S., and Lavrac, N., eds., Relational Data Mining. New York: Springer-Verlag. find
  30. Krogel, M.; Rawles, S.; Zeezny, F.; Flach, P.; Lavrac, N.; and Wrobel, S. 2003. Comparative evaluation of approaches to propositionalization. In International Conference on Inductive Logic Programming. find
  31. Kschischang, F. R., and Frey, B. J. 1998. Iterative decoding of compound codes by probability progation in graphical models. IEEE Journal on Selected Areas in Communication. find
  32. Kschischang, F. R.; Frey, B. J.; and Loeliger, H. A. 2001. Factor graphs and the sum-product algorithm. In IEEE Transactions on Information Theory. find
  33. Lafferty, J. D.; McCallum, A.; and Pereira, F. C. N. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning. find
  34. Li, S.; Wang, H.; and Petrou, M. 1994. Relaxation labeling of markov random fields. In In Proceedings of International Conference Pattern Recognition, volume 94. find
  35. Lu, Q., and Getoor, L. 2003. Link based classification. In Proceedings of the International Conference on Machine Learning. find
  36. Macskassy, S., and Provost, F. 2007. Classification in networked data: A toolkit and a univariate case study. Journal of Machine Learning Research. find
  37. Macskassy, S. A. 2007. Improving learning in networked data by combining explicit and mined links. In Proceedings of the Twenty-Second Conference on Artificial Intelligence. find
  38. McCallum, A.; Nigam, K.; Rennie, J.; and Seymore, K. 2000. Automating the construction of internet portals with machine learning. Information Retrieval Journal. find
  39. McDowell, L. K.; Gupta, K. M.; and Aha, D. W. 2007. Cautious inference in collective classification. In Proceedings of AAAI. find
  40. McEliece, R. J.; MacKay, D. J. C.; and Cheng, J. F. 1998. Turbo decoding as an instance of Pearl’s belief propagation algorithm. IEEE Journal on Selected Areas in Communication. find
  41. McPherson, M.; Smith-Lovin, L.; and Cook, J. M. 2001. Birds of a feather: Homophily in social networks. Annual Review of Sociology 27. This article consists of 30 page(s). find
  42. Minka, T. 2001. Expectation propagation for approximate bayesian inference. In Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence. find
  43. Mooij, J. M., and Kappen, H. J. 2004. Validity estimates for loopy belief propagation on binary real-world networks. In NIPS. find
  44. Neville, J., and Jensen, D. 2000. Iterative classification in relational data. In Workshop on Statistical Relational Learning, AAAI. find
  45. Neville, J., and Jensen, D. 2007a. Bias/variance analysis for relational domains. In International Conference on Inductive Logic Programming. find
  46. Neville, J., and Jensen, D. 2007b. Relational dependency networks. Journal of Machine Learning Research. find
  47. Pearl, J. 1988. Probabilistic reasoning in intelligent systems. In Morgan Kaufmann, San Fansisco. find
  48. Perlich, C., and Provost, F. 2003. Aggregation-based feature invention and relational concept classes. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. find
  49. Perlich, C., and Provost, F. 2006. Distribution-based aggregation for relational learning with identifier attributes. Machine Learning Journal. find
  50. Popescul, A., and Ungar, L. 2003. Structural logistic regression for link analysis. In KDD Workshop on Multi-Relational Data Mining. find
  51. Richardson, M., and Domingos, P. 2006. Markov logic networks. Machine Learning. find
  52. Sen, P., and Getoor, L. 2006. Empirical comparison of approximate inference algorithms for networked data. In ICML workshop on Open Problems in Statistical Relational Learning (SRL2006). find
  53. Sen, P., and Getoor, L. 2007. Link-based classification. Technical Report CS-TR-4858, University of Maryland. find
  54. Slattery, S., and Craven, M. 1998. Combining statistical and relational methods for learning in hypertext domains. In International Conference on Inductive Logic Programming. find
  55. Taskar, B.; Abbeel, P.; and Koller, D. 2002. Discriminative probabilistic models for relational data. In Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence. find
  56. Taskar, B.; Wong, M. F.; Abbeel, P.; and Koller, D. 2003. Link prediction in relational data. In Neural Information Processing Systems. find
  57. Taskar, B.; Chatalbashev, V.; Koller, D.; and Guestrin, C. 2005. Learning structured prediction models: A large margin approach. In Proceedings of the International Conference on Machine Learning. find
  58. Taskar, B.; Guestrin, C.; and Koller, D. 2003. Max-margin markov networks. In Neural Information Processing Systems. find
  59. Taskar, B.; Segal, E.; and Koller, D. 2001. Probabilistic classification and clustering in relational data. In Proceedings of the International Joint Conference on Artificial Intelligence. find
  60. Wainwright, M. J.; Jaakkola, T. S.; and Willsky, A. S. 2005. Map estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches. In IEEE Transactions on Information Theory. find
  61. Weiss, Y. 2001. Advanced Mean Field Methods, Manfred Opper and David Saad (eds). MIT Press. chapter Comparing the mean field method and belief propagation for approximate inference in MRFs. find
  62. Xu, L.; Wilkinson, D.; Southey, F.; and Schuurmans, D. 2006. Discriminative unsupervised learning of structured predictors. In Proceedings of the International Conference on Machine Learning. find
  63. Yang, Y.; Slattery, S.; and Ghani, R. 2002. A study of approaches to hypertext categorization. Journal of Intelligent Information Systems. find
  64. Yanover, C., and Weiss, Y. 2002. Approximate inference and protein-folding. In Neural Information Processing Systems. find
  65. Yedidia, J.; Freeman, W.; and Weiss, Y. 2005. Constructing free-energy approximations and generalized belief propagation algorithms. In IEEE Transactions on Information Theory. find
  66. Yedidia, J.; W.T.Freeman; and Weiss, Y. 2000. Generalized belief propagation. In Neural Information Processing Systems. find
  67. Yuille, A. L. 2002. CCCP algorithms to minimize the bethe and kikuchi free energies: Convergent alternatives to belief propagation. In Neural Information Processing Systems. find
  68. Zhang, N. L., and Poole, D. 1994. A simple approach to bayesian network computations. In Canadian Conference on Artificial Intelligence. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sen-2008-collective-classification-network-data/