Exploiting time-varying relationships in statistical relational models

ABSTRACT

In a growing number of relational domains, the data record temporal sequences of interactions among entities. For example, in citation domains authors publish scientific papers together each year and in telephone fraud detection domains people make calls to each other each day. The temporal dynamics of these interactions contain information that can improve predictive models (e.g., people publishing together frequently are likely to be publishing on the same topic) but to date there has been little effort to incorporate timevarying dependencies into relational models. Past work in relational learning has focused primarily on static "snapshots" of relational data. In this paper, we present an initial approach to modeling dynamic relational data graphs in predictive models of attributes. More specifically, we use a two-step process that first summarizes the dynamic graph with a weighted static graph and then incorporates the link weights in a relational Bayes classifier. We evaluate our approach on the Cora dataset (where co-author and citation links vary over time) showing that our approach results in significant performance gains over a baseline snapshot approach that ignores the temporal component of the data.

REFERENCES

• 1: D. Cai, Z. Shao, X. He, X. Yan, and J. Han. Community mining from multi-relational networks. In Proceedings of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, 2005.
• 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: Corinna Cortes , Daryl Pregibon , Chris Volinsky, Communities of Interest, Proceedings of the 4th International Conference on Advances in Intelligent Data Analysis, p.105-114, September 13-15, 2001
• 4: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 5: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 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: Zoubin Ghahramani, Learning Dynamic Bayesian Networks, Adaptive Processing of Sequences and Data Structures, International Summer School on Neural Networks, "E.R. Caianiello"-Tutorial Lectures, p.168-197, September 06-13, 1997
• 8: S. Hill, D. Agarwal, R. Bell, and C. Volinsky. Building an effective representation of dynamic networks. Journal of Computational and Graphical Statistics, Sept, 2006.
• 9: 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]
• 10: Andrew McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, A Machine Learning Approach to Building Domain-Specific Search Engines, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.662-667, July 31-August 06, 1999
• 11: Amy McGovern , Lisa Friedland , Michael Hay , Brian Gallagher , Andrew Fast , Jennifer Neville , David Jensen, Exploiting relational structure to understand publication patterns in high-energy physics, ACM SIGKDD Explorations Newsletter, v.5 n.2, December 2003 [doi>10.1145/980972.980999]
• 12: M. McPherson, L. Smith-Lovin, and J. Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27:415--445, 2001.
• 13: B. Milch, B. Marthi, S. Russell, D. Sontag, D. Ong, and A. Kolobov. Blog: Probabilistic models with unknown objects. In Introduction to Statistical Relational Learning, 2007.
• 14: Jennifer Neville , Özgür Şimşek , David Jensen , John Komoroske , Kelly Palmer , Henry Goldberg, Using relational knowledge discovery to prevent securities fraud, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081922]
• 15: 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]
• 16: Jennifer Neville , David Jensen , Brian Gallagher, Simple Estimators for Relational Bayesian Classifiers, Proceedings of the Third IEEE International Conference on Data Mining, p.609, November 19-22, 2003
• 17: Claudia Perlich , Foster Provost, Aggregation-based feature invention and relational concept classes, 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.956772]
• 18: S. Sanghai, P. Domingos, and D. Weld. Learning statistical models of time-varying relational data. In Proceedings of the Workshop on Statistical Relational Learning, 18th International Joint Conference on Artificial Intelligence, 2003.
• 19: B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, pages 485--492, 2002.