Group and topic discovery from relations and text

ABSTRACT

We present a probabilistic generative model of entity relationships and textual attributes that simultaneously discovers groups among the entities and topics among the corresponding text. Block-models of relationship data have been studied in social network analysis for some time. Here we simultaneously cluster in several modalities at once, incorporating the words associated with certain relationships. Significantly, joint inference allows the discovery of groups to be guided by the emerging topics, and vice-versa. We present experimental results on two large data sets: sixteen years of bills put before the U.S. Senate, comprising their corresponding text and voting records, and 43 years of similar data from the United Nations. We show that in comparison with traditional, separate latent-variable models for words or Blockstructures for votes, the Group-Topic model's joint inference improves both the groups and topics discovered.

REFERENCES

• 1: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 2: 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]
• 3: I. Bhattacharya and L. Getoor. Deduplication and group detection using links. In LinkKDD, 2004.
• 4: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003 [doi>10.1162/jmlr.2003.3.4-5.993]
• 5: K. Carley. A theory of group stability. American Sociological Review, 56(3):331--354, 1991.
• 6: K. Carley. A comparison of artificial and human organizations. Journal of Economic Behavior and Organization, 56:175--191, 1996.
• 7: G. Cox and K. Poole. On measuring the partisanship in roll-call voting: The U.S. House of Represenatatives, 1887--1999. American Journal of Political Science, 46(1):477--489, 2002.
• 8: W. W. Denham, C. K. McDaniel, and J. R. Atkins. Aranda and Alyawarra kinship: A quantitative argument for a double helix model. American Ethnologist, 6(1):1--24, 1979.
• 9: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, 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.956764]
• 10: D. Fenn, O. Suleman, J. Efstathiou, and N. Johnson. How does Europe make its mind up? Connections, cliques, and compatibility between countries in the Eurovision song contest. arXiv:physics/0505071, 2005.
• 11: S. Hix, A. Noury, and G. Roland. Power to the parties: Cohesion and competition in the European Parliament, 1979--2001. British Journal of Political Science, 35(2):209--234, 2005.
• 12: A. Jakulin and W. Buntine. Analyzing the US Senate in 2003: Similarities, networks, clusters and blocs, 2004.
• 13: C. Kemp, T. L. Griffiths, and J. Tenenbaum. Discovering latent classes in relational data. Technical report, MIT CSAIL, 2004.
• 14: D. Krackhardt and K. M. Carley. A PCANS model of structure in organization. In Int. Sym. on Command and Control Research and Technology, June 1998.
• 15: Jeremy Kubica , Andrew Moore , Jeff Schneider , Yiming Yang, Stochastic link and group detection, Eighteenth national conference on Artificial intelligence, p.798-804, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 16: A. McCallum, A. Corrada-Emanuel, and X. Wang. Topic and role discovery in social networks. In IJCAI, 2005.
• 17: K. Nowicki and T. A. Snijders. Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 96(455), 2001.
• 18: A. Pajala, A. Jakulin, and W. Buntine. Parliamentary group and individual voting behavior in Finnish Parliamentin year 2003: A group cohesion and voting similarity analysis, 2004.
• 19: M. Sparrow. The application of network analysis to criminal intelligence: an assessment of prospects. Social Networks, 13:251--274, 1991.
• 20: E. Voeten. Documenting votes in the UN General Assembly. http://home.gwu.edu/~voeten/UNVoting.htm_Toc82404232.
• 21: S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

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

General Terms:
Algorithms, Experimentation

Keywords:
graphical models, relational learning, text modeling