Relational learning via latent social dimensions

ABSTRACT

Social media such as blogs, Facebook, Flickr, etc., presents data in a network format rather than classical IID distribution. To address the interdependency among data instances, relational learning has been proposed, and collective inference based on network connectivity is adopted for prediction. However, connections in social media are often multi-dimensional. An actor can connect to another actor for different reasons, e.g., alumni, colleagues, living in the same city, sharing similar interests, etc. Collective inference normally does not differentiate these connections. In this work, we propose to extract latent social dimensions based on network information, and then utilize them as features for discriminative learning. These social dimensions describe diverse affiliations of actors hidden in the network, and the discriminative learning can automatically determine which affiliations are better aligned with the class labels. Such a scheme is preferred when multiple diverse relations are associated with the same network. We conduct extensive experiments on social media data (one from a real-world blog site and the other from a popular content sharing site). Our model outperforms representative relational learning methods based on collective inference, especially when few labeled data are available. The sensitivity of this model and its connection to existing methods are also examined.

REFERENCES

• 1: Edoardo M. Airoldi , David M. Blei , Stephen E. Fienberg , Eric P. Xing, Mixed Membership Stochastic Blockmodels, The Journal of Machine Learning Research, 9, p.1981-2014, 6/1/2008
• 2: U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner. Maximizing modularity is hard. Arxiv preprint physics, %/0608255, 2006.
• 3: Deepayan Chakrabarti , Christos Faloutsos, Graph mining: Laws, generators, and algorithms, ACM Computing Surveys (CSUR), v.38 n.1, p.2-es, 2006 [doi>http://doi.acm.org/10.1145/1132952.1132954]
• 4: 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
• 5: G. Chen, F. Wang, and C. Zhang. Semi-supervised multi-label learning by solving a sylvester equation. In SDM, 2008.
• 6: L. Danon, J. Duch, A. Arenas, and A. Díaz-guilera. Comparing community structure identification. J. Stat. Mech, 2005.
• 7: R.-E. Fan and C.-J. Lin. A study on threshold selection for multi-label classication. 2007.
• 8: Brian Gallagher , Hanghang Tong , Tina Eliassi-Rad , Christos Faloutsos, Using ghost edges for classification in sparsely labeled networks, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401925]
• 9: S. Geman , D. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, Readings in uncertain reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 10: Lise Getoor , Ben Taskar, Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning), The MIT Press, 2007
• 11: M. S. Handcock, A. E. Raftery, and J. M. Tantrum. Model-based clustering for social networks. Journal Of The Royal Statistical Society Series A, 2007.
• 12: P. D. Hoff and M. S. H. Adrian E. Raftery. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97(460):1090--1098, 2002.
• 13: John Hopcroft , Omar Khan , Brian Kulis , Bart Selman, Natural communities in large linked networks, 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.956816]
• 14: 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]
• 15: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 16: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 17: Huan Liu , Hiroshi Motoda, Computational Methods of Feature Selection (Chapman & Hall/Crc Data Mining and Knowledge Discovery Series), Chapman & Hall/CRC, 2007
• 18: Yi Liu , Rong Jin , Liu Yang, Semi-supervised multi-label learning by constrained non-negative matrix factorization, Proceedings of the 21st national conference on Artificial intelligence, p.421-426, July 16-20, 2006, Boston, Massachusetts
• 19: Q. Lu and L. Getoor. Link-based classification. In ICML '03: Proceedings of the 20th international conference on Machine learning, 2003.
• 20: S. A. Macskassy and F. Provost. A simple relational classifier. In Proceedings of the Multi-Relational Data Mining Workshop (MRDM) at the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003.
• 21: 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
• 22: J. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27:415--444, 2001.
• 23: Jennifer Neville , David Jensen, Leveraging relational autocorrelation with latent group models, Proceedings of the 4th international workshop on Multi-relational mining, p.49-55, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1090193.1090201]
• 24: 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]
• 25: M. Newman. Finding community structure in networks using the eigenvectors of matrices. Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 74(3), 2006.
• 26: M. Newman. Modularity and community structure in networks. PNAS, 103(23):8577--8582, 2006.
• 27: M. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69:026113, 2004.
• 28: K. Nowicki and T. A. B. Snijders. Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 96(455):1077--1087, 2001.
• 29: Purnamrita Sarkar , Andrew W. Moore, Dynamic social network analysis using latent space models, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.31-40, December 2005 [doi>10.1145/1117454.1117459]
• 30: Lei Tang , Huan Liu , Jianping Zhang , Nitin Agarwal , John J. Salerno, Topic taxonomy adaptation for group profiling, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.4, p.1-28, January 2008 [doi>10.1145/1324172.1324173]
• 31: Lei Tang , Huan Liu , Jianping Zhang , Zohreh Nazeri, Community evolution in dynamic multi-mode networks, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401972]
• 32: Lei Tang , Suju Rajan , Vijay K. Narayanan, Large scale multi-label classification via metalabeler, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526738]
• 33: B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In UAI, pages 485--492, 2002.
• 34: J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry, 32(4):425--443, 1969.
• 35: Ioannis Tsochantaridis , Thomas Hofmann , Thorsten Joachims , Yasemin Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the twenty-first international conference on Machine learning, p.104, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015341]
• 36: Koji Tsuda , William Stafford Noble, Learning kernels from biological networks by maximizing entropy, Bioinformatics, v.20 n.1, p.326-333, January 2004 [doi>10.1093/bioinformatics/bth906]
• 37: Ulrike Luxburg, A tutorial on spectral clustering, Statistics and Computing, v.17 n.4, p.395-416, December 2007 [doi>10.1007/s11222-007-9033-z]
• 38: Z. Xu, V. Tresp, S. Yu, and K. Yu. Nonparametric relational learning for social network analysis. In KDD'2008 Workshop on Social Network Mining and Analysis, 2008.
• 39: X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, 2003.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Sociology

General Terms:
Algorithms, Experimentation

Keywords:
behavior prediction, modularity, relational learning, social dimensions, social media