MetaFac: community discovery via relational hypergraph factorization

ABSTRACT

This paper aims at discovering community structure in rich media social networks, through analysis of time-varying, multi-relational data. Community structure represents the latent social context of user actions. It has important applications in information tasks such as search and recommendation. Social media has several unique challenges. (a) In social media, the context of user actions is constantly changing and co-evolving; hence the social context contains time-evolving multi-dimensional relations. (b) The social context is determined by the available system features and is unique in each social media website. In this paper we propose MetaFac (MetaGraph Factorization), a framework that extracts community structures from various social contexts and interactions. Our work has three key contributions: (1) metagraph, a novel relational hypergraph representation for modeling multi-relational and multi-dimensional social data; (2) an efficient factorization method for community extraction on a given metagraph; (3) an on-line method to handle time-varying relations through incremental metagraph factorization. Extensive experiments on real-world social data collected from the Digg social media website suggest that our technique is scalable and is able to extract meaningful communities based on the social media contexts. We illustrate the usefulness of our framework through prediction tasks. We outperform baseline methods (including aspect model and tensor analysis) by an order of magnitude.

REFERENCES

• 1: Brett W. Bader , Tamara G. Kolda, Algorithm 862: MATLAB tensor classes for fast algorithm prototyping, ACM Transactions on Mathematical Software (TOMS), v.32 n.4, p.635-653, December 2006 [doi>10.1145/1186785.1186794]
• 2: A. BANERJEE, S. BASU and S. MERUGU (2007). Multi-way Clustering on Relation Graphs, SDM, 2007.
• 3: Ron Bekkerman , Ran El-Yaniv , Andrew McCallum, Multi-way distributional clustering via pairwise interactions, Proceedings of the 22nd international conference on Machine learning, p.41-48, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102357]
• 4: Deepayan Chakrabarti , Ravi Kumar , Andrew Tomkins, Evolutionary clustering, 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.1150467]
• 5: Yun Chi , Shenghuo Zhu , Yihong Gong , Yi Zhang, Probabilistic polyadic factorization and its application to personalized recommendation, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458206]
• 6: Nir Friedman , Lise Getoor , Daphne Koller , Avi Pfeffer, Learning Probabilistic Relational Models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1300-1309, July 31-August 06, 1999
• 7: 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]
• 8: Charles Kemp , Joshua B. Tenenbaum , Thomas L. Griffiths , Takeshi Yamada , Naonori Ueda, Learning systems of concepts with an infinite relational model, Proceedings of the 21st national conference on Artificial intelligence, p.381-388, July 16-20, 2006, Boston, Massachusetts
• 9: Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, 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.1150476]
• 10: D. LEE and H. SEUNG (2001). Algorithms for non-negative matrix factorization, NIPS, 556--562, 2001.
• 11: Yu-Ru Lin , Yun Chi , Shenghuo Zhu , Hari Sundaram , Belle L. Tseng, Facetnet: a framework for analyzing communities and their evolutions in dynamic networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367590]
• 12: Bo Long , Zhongfei Mark Zhang , Philip S. Yu, A probabilistic framework for relational clustering, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281244]
• 13: Alexandrin Popescul , Lyle H. Ungar , David M. Pennock , Steve Lawrence, Probabilistic Models for Unified Collaborative and Content-Based Recommendation in Sparse-Data Environments, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.437-444, August 02-05, 2001
• 14: Jimeng Sun , Christos Faloutsos , Spiros Papadimitriou , Philip S. Yu, GraphScope: parameter-free mining of large time-evolving graphs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281266]
• 15: 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]

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
          Subjects: Information filtering

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
MetaFac, community discovery, dynamic social network analysis, metagraph factorization, non-negative tensor factorization, relational hypergraph