Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-28T17:42:48.827Z Has data issue: false hasContentIssue false
  • English
  • Français

Relational time series forecasting

Published online by Cambridge University Press:  18 April 2018

Ryan A. Rossi
Ryan A. Rossi*
Affiliation:
Adobe Research, 345 Park Ave, San Jose, CA 95110 e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Networks encode dependencies between entities (people, computers, proteins) and allow us to study phenomena across social, technological, and biological domains. These networks naturally evolve over time by the addition, deletion, and changing of links, nodes, and attributes. Despite the importance of modeling these dynamics, existing work in relational machine learning has ignored relational time series data. Relational time series learning lies at the intersection of traditional time series analysis and statistical relational learning, and bridges the gap between these two fundamentally important problems. This paper formulates the relational time series learning problem, and a general framework and taxonomy for representation discovery tasks of both nodes and links including predicting their existence, label, and weight (importance), as well as systematically constructing features. We also reinterpret the prediction task leading to the proposal of two important relational time series forecasting tasks consisting of (i) relational time series classification (predicts a future class or label of an entity), and (ii) relational time series regression (predicts a future real-valued attribute or weight). Relational time series models are designed to leverage both relational and temporal dependencies to minimize forecasting error for both relational time series classification and regression. Finally, we discuss challenges and open problems that remain to be addressed.

Type
Survey Article
Information
The Knowledge Engineering Review , Volume 33 , 2018 , e1
Copyright
© Cambridge University Press, 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Acar, E., Dunlavy, D. & Kolda, T. 2009. Link prediction on evolving data using matrix and tensor factorizations. In Proceedings of the 9th IEEE International Conference on Data Mining Workshops, 262–269.Google Scholar
Agami, N., Atiya, A., Saleh, M. & El-Shishiny, H. 2009. A neural network based dynamic forecasting model for trend impact analysis. Technological Forecasting and Social Change 76(7), 952–962.CrossRefGoogle Scholar
Ahmed, N., Atiya, A., El Gayar, N. & El-Shishiny, H. 2010. An empirical comparison of machine learning models for time series forecasting. Econometric Reviews 29(5–6), 594–621.CrossRefGoogle Scholar
Albert, R., Jeong, H. & Barabási, A. 1999. Internet: diameter of the world-wide web. Nature 401(6749), 130–131.CrossRefGoogle Scholar
Al Hasan, M. & Zaki, M. J. 2011. A survey of link prediction in social networks. In Social Network Data Analytics, 243–275. Springer.CrossRefGoogle Scholar
Anderson, J. R., Michalski, R. S., Michalski, R. S., Carbonell, J. G. & Mitchell, T. M. 1986. Machine Learning: An Artificial Intelligence Approach, 2. Morgan Kaufmann.Google Scholar
Bengio, Y. 2009. Learning deep architectures for AI. Foundations and Trends in Machine Learning 2(1), 1–127.CrossRefGoogle Scholar
Ben Taieb, S., Bontempi, G., Atiya, A. F. & Sorjamaa, A. 2012. A review and comparison of strategies for multi-step ahead time series forecasting based on the NN5 forecasting competition. Expert Systems with Applications 39(8), 7067–7083.CrossRefGoogle Scholar
Bhadra, S. & Ferreira, A. 2003. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Ad-Hoc, Mobile, and Wireless Networks, 259–270.Google Scholar
Bifet, A., Holmes, G., Pfahringer, B., Kirkby, R. & Gavaldà, R. 2009. New ensemble methods for evolving data streams. In Proceeding of the 15th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 139–148.Google Scholar
Bishop, C. M. 2006. Pattern Recognition and Machine Learning. Springer.Google Scholar
Bock, J., Cooray, A., Hanany, S., Keating, B., Lee, A., Matsumura, T., Milligan, M., Ponthieu, N., Renbarger, T. & Tran, H. 2008. The experimental probe of inflationary cosmology (EPIC): a mission concept study for NASA’s Einstein inflation probe. arXiv:0805.4207.Google Scholar
Boureau, Y.-L., Bach, F., LeCun, Y. & Ponce, J. 2010. Learning mid-level features for recognition. In IEEE Conference on Computer Vision and Pattern Recognition, 2559–2566.Google Scholar
Box, G. E., Jenkins, G. M. & Reinsel, G. C. 2013. Time Series Analysis: Forecasting and Control. John Wiley & Sons.Google Scholar
Brockwell, P. J. & Davis, R. A. 2002. Introduction to Time Series and Forecasting, 1. Taylor & Francis.CrossRefGoogle Scholar
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A. & Wiener, J. 2000. Graph structure in the web. Computer Networks 33(1–6), 309–320.CrossRefGoogle Scholar
Bunke, H. & Kraetzl, M. 2004. Classification and detection of abnormal events in time series of graphs. In Mark Last, Abraham Kandel, Horst Bunke, Data Mining in Time Series Databases, Last, M., Kandel, A. & Bunke H (eds). World Scientific, 127–148.Google Scholar
Camacho, J., Guimerà, R. & Nunes Amaral, L. 2002. Robust patterns in food web structure. Physical Review Letters 88(22), 228102: 1–4.CrossRefGoogle ScholarPubMed
Chakrabarti, S., Dom, B. & Indyk, P. 1998. Enhanced hypertext categorization using hyperlinks. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 307–318.Google Scholar
Chandola, V., Banerjee, A. & Kumar, V. 2009. Anomaly detection: a survey. ACM Computing Surveys 41(3), 15.CrossRefGoogle Scholar
Chen, C., Yin, H., Yao, J. & Cui, B. 2013. TeRec: a temporal recommender system over tweet stream. Proceedings of the VLDB Endowment 6(12), 1254–1257.CrossRefGoogle Scholar
Clements, M. & Hendry, D. 1998. Forecasting Economic Time Series. Cambridge University Press.CrossRefGoogle Scholar
Couprie, C., Farabet, C. & LeCun, Y. 2013. Causal graph-based video segmentation. arXiv:1301.1671.CrossRefGoogle Scholar
Couprie, C., Farabet, C., LeCun, Y., & Najman, L. 2013, September. Causal graph-based video segmentation. In Image Processing (ICIP), 2013 20th IEEE International Conference on (pp. 4249–4253). IEEE.CrossRefGoogle Scholar
Craven, M., DiPasquo, D., Freitag, D., McCallum, A., Mitchell, T., Nigam, K. & Slattery, S. 1998. Learning to extract symbolic knowledge from the World Wide Web. In Proceedings of the 15th AAAI Conference on Artificial Intelligence, 509–516.Google Scholar
Croushore, D. & Stark, T. 2001. A real-time data set for macroeconomists. Journal of Econometrics 105(1), 111–130.CrossRefGoogle Scholar
Das Sarma, A., Gollapudi, S. & Panigrahy, R. 2008. Estimating PageRank on graph streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 69–78.Google Scholar
Deng, L. & Li, X. 2013. Machine learning paradigms for speech recognition: an overview. Transactions on Audio, Speech and Language Processing 21(5), 1060–1089.CrossRefGoogle Scholar
De Raedt, L. & Kersting, K. 2008. Probabilistic Inductive Logic Programming. Springer-Verlag.CrossRefGoogle Scholar
Domingos, P. & Richardson, M. 2001. Mining the network value of customers. In Proceeding of the 7th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 57–66.Google Scholar
Dunlavy, D. M., Kolda, T. G. & Acar, E. 2011. Temporal link prediction using matrix and tensor factorizations. Transactions on Knowledge Discovery from Data 5(2), 10:1–10:27.Google Scholar
Dunne, J., Williams, R. & Martinez, N. 2002. Food-web structure and network theory: the role of connectance and size. Proceedings of the National Academy of Sciences of the United States of America 99(20), 12917.CrossRefGoogle ScholarPubMed
Einstein, A. 1906. Zur theorie der brownschen bewegung. Annalen der Physik 324(2), 371–381.CrossRefGoogle Scholar
Eldardiry, H. & Neville, J. 2011. Across-model collective ensemble classification. In Proceedings of the 25th AAAI Conference on Artificial Intelligence, 343–349.Google Scholar
Esling, P. & Agon, C. 2012. Time-series data mining. ACM Computing Surveys 45(1), 12.CrossRefGoogle Scholar
Faloutsos, M., Faloutsos, P. & Faloutsos, C. 1999. On power-law relationships of the internet topology. In Proceedings of the ACM SIGCOMM International Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 251–262.Google Scholar
Friedman, N., Getoor, L., Koller, D. & Pfeffer, A. 1999. Learning probabilistic relational models. In Proceedings of the 16th International Joint Conference on Artificial Intelligence, 1300–1309. Springer-Verlag.Google Scholar
Getoor, L. & Taskar, B. (eds) 2007. Introduction to Statistical Relational Learning. MIT Press.CrossRefGoogle Scholar
Güneş, İ, Çataltepe, Z. & Öğüdücü, Ş. G. 2011. GA-TVRC: a novel relational time varying classifier to extract temporal information using genetic algorithms. In Machine Learning and Data Mining in Pattern Recognition, 568–583. Springer.CrossRefGoogle Scholar
Hasan, M. A., Chaoji, V., Salem, S. & Zaki, M. 2006. Link prediction using supervised learning. In Proceedings of the SDM Workshop on Link Analysis, Counterterrorism and Security.Google Scholar
Hearst, M. A., Dumais, S., Osman, E., Platt, J. & Scholkopf, B. 1998. Support vector machines. Intelligent Systems and their Applications 13(4), 18–28.CrossRefGoogle Scholar
Hinton, G. E., Osindero, S. & Teh, Y.-W. 2006. A fast learning algorithm for deep belief nets. Neural Computation 18(7), 1527–1554.CrossRefGoogle ScholarPubMed
Holme, P. & Saramäki, J. 2012. Temporal networks. Physics Reports.CrossRefGoogle Scholar
Hornik, K., Stinchcombe, M. & White, H. 1989. Multilayer feedforward networks are universal approximators. Neural Networks 2(5), 359–366.CrossRefGoogle Scholar
Ide, T. & Kashima, H. 2004. Eigenspace-based anomaly detection in computer systems. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 440–449.Google Scholar
Jensen, D., Neville, J. & Gallagher, B. 2004. Why collective inference improves relational classification. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 593–598.Google Scholar
Jeong, H., Mason, S. P., Barabási, A. L. & Oltvai, Z. N. 2001. Lethality and centrality in protein networks. Nature, 411(6833), 41.CrossRefGoogle ScholarPubMed
Jeong, H., Mason, S., Barabasi, A. & Oltvai, Z. 2001. Lethality and centrality in protein networks. arXiv preprint cond-mat/0105306.CrossRefGoogle Scholar
Jeong, H., Tombor, B., Albert, R., Oltvai, Z. & Barabási, A. 2000. The large-scale organization of metabolic networks. Nature 407(6804), 651–654.CrossRefGoogle ScholarPubMed
Kleczkowski, A. & Grenfell, B. 1999. Mean-field-type equations for spread of epidemics: the small world model. Physica A: Statistical Mechanics and its Applications 274(1–2), 355–360.CrossRefGoogle Scholar
Koren, Y. 2010. Collaborative filtering with temporal dynamics. Communications of the ACM 53(4), 89–97.CrossRefGoogle Scholar
Koren, Y., Bell, R. & Volinsky, C. 2009. Matrix factorization techniques for recommender systems. IEEE Computer 42(8), 30–37.CrossRefGoogle Scholar
Kovanen, L., Karsai, M., Kaski, K., Kertész, J. & Saramäki, J. 2011. Temporal motifs in time-dependent networks. Journal of Statistical Mechanics: Theory and Experiment 2011(11), P11005.CrossRefGoogle Scholar
Krebs, V. 2002. Mapping networks of terrorist cells. Connections 24(3), 43–52.Google Scholar
Lahiri, M. & Berger-Wolf, T. 2008. Mining periodic behavior in dynamic social networks. In Proceedings of the 8th IEEE International Conference on Data Mining, 373–382.Google Scholar
Lahiri, M. & Berger-Wolf, T. Y. 2007. Structure prediction in temporal networks using frequent subgraphs. In IEEE Symposium on Computational Intelligence and Data Mining, 35–42.Google Scholar
Lassez, J.-L., Rossi, R. & Jeev, K. 2008. Ranking links on the web: search and surf engines. In Proceedings of the IEA/AIE International Conference, 199–208. Springer.CrossRefGoogle Scholar
LeCun, Y., Bottou, L., Bengio, Y. & Haffner, P. 1998. Gradient-based learning applied to document recognition. Proceedings of the IEEE 86(11), 2278–2324.CrossRefGoogle Scholar
Lee, H., Grosse, R., Ranganath, R. & Ng, A. Y. 2009. Convolutional deep belief networks for scalable unsupervised learning of hierarchical representations. In Proceedings of the 26th International Conference on Machine Learning, 609–616.Google Scholar
Leskovec, J., Adamic, L. & Huberman, B. 2007a. The dynamics of viral marketing. Transactions on the Web 1(1), 1–39.Google Scholar
Leskovec, J., Kleinberg, J. & Faloutsos, C. 2007b. Graph evolution: densification and shrinking diameters. Transactions on Knowledge Discovery from Data 1(1), 1–41. https://dl.acm.org/citation.cfm?id=1217301.Google Scholar
Lezama, J., Alahari, K., Sivic, J. & Laptev, I. 2011. Track to the future: spatio-temporal video segmentation with long-range motion cues. In IEEE Conference on Computer Vision and Pattern Recognition.CrossRefGoogle Scholar
Li, L., Zheng, L., Yang, F. & Li, T. 2014. Modeling and broadening temporal user interest in personalized news recommendation. Expert Systems with Applications 41(7), 3168–3177.CrossRefGoogle Scholar
Liben-Nowell, D. & Kleinberg, J. 2007. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology 58(7), 1019–1031.CrossRefGoogle Scholar
Liu, N. N., He, L. & Zhao, M. 2013. Social temporal collaborative ranking for context aware movie recommendation. ACM Transactions on Intelligent Systems and Technology 4(1), 15.CrossRefGoogle Scholar
Lu, Q. & Getoor, L. 2003. Link-based classification. In Proceedings of the 20th International Conference on Machine Learning, 496–503.Google Scholar
Ma, H., Yang, H., Lyu, M. R. & King, I. 2008. SoRec: social recommendation using probabilistic matrix factorization. In Proceedings of the 17th ACM Conference on Information and Knowledge Management, 931–940.Google Scholar
Macskassy, S. & Provost, F. 2003. A simple relational classifier. In Proceedings of the SIGKDD 2nd Workshop on Multi-Relational Data Mining, 64–76.Google Scholar
Marc’Aurelio Ranzato, Y., Boureau, L. & LeCun, Y. 2007. Sparse feature learning for deep belief networks. Advances in Neural Information Processing Systems 20, 1185–1192.Google Scholar
Marcellino, M., Stock, J. H. & Watson, M. W. 2006. A comparison of direct and iterated multistep are methods for forecasting macroeconomic time series. Journal of Econometrics 135(1), 499–526.CrossRefGoogle Scholar
Maslov, S. & Sneppen, K. 2002. Specificity and stability in topology of protein networks. Science 296(5569), 910–913.CrossRefGoogle ScholarPubMed
May, R. & Lloyd, A. 2001. Infection dynamics on scale-free networks. Physical Review E 64(6), 66112.CrossRefGoogle ScholarPubMed
McDowell, L., Gupta, K. & Aha, D. 2010. Meta-prediction for collective classification. In Proceedings of the 23rd International FLAIRS Conference.Google Scholar
McDowell, L. K., Gupta, K. M. & Aha, D. W. 2009. Cautious collective classification. Journal of Machine Learning Research 10, 2777–2836.Google Scholar
McGovern, A., Collier, N., Matthew Gagne, I., Brown, D. & Rodger, A. 2008. Spatiotemporal relational probability trees: an introduction. In Proceedings of the 8th IEEE International Conference on Data Mining, 935–940.Google Scholar
McGovern, A., Friedland, L., Hay, M., Gallagher, B., Fast, A., Neville, J. & Jensen, D. 2003. Exploiting relational structure to understand publication patterns in high-energy physics. SIGKDD Explorations 5(2), 165–172.CrossRefGoogle Scholar
McPherson, M., Smith-Lovin, L. & Cook, J. M. 2001. Birds of a feather: homophily in social networks. Annual Review of Sociology 27(1), 415–444.CrossRefGoogle Scholar
Menon, A. & Elkan, C. 2011. Link prediction via matrix factorization. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 437–452.Google Scholar
Moore, C. & Newman, M. 2000. Epidemics and percolation in small-world networks. Physical Review E 61(5), 5678–5682.CrossRefGoogle ScholarPubMed
Neville, J., Jensen, D. & Gallagher, B. 2003. Simple estimators for relational Bayesian classifers. In Proceedings of the 3rd IEEE International Conference on Data Mining, 609–612.Google Scholar
Neville, J., Simsek, O., Jensen, D., Komoroske, J., Palmer, K. & Goldberg, H. 2005. Using relational knowledge discovery to prevent securities fraud. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 449–458.Google Scholar
Newman, M. 2001. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences 98(2), 404–409.CrossRefGoogle ScholarPubMed
Newman, M., Barabasi, A.-L. & Watts, D. J. 2006. The Structure and Dynamics of Networks. Princeton University Press.Google Scholar
Nguyen, G. H., Lee, J. B., Rossi, R. A., Ahmed, N. K., Koh, E. & Kim, S. 2018. Continuous-time dynamic network embeddings. In 3rd International Workshop on Learning Representations for Big Networks (WWW BigNet).CrossRefGoogle Scholar
Noble, C. & Cook, D. 2003. Graph-based anomaly detection. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 631–636.Google Scholar
O’Madadhain, J. & Smyth, P. 2005. EventRank: a framework for ranking time-varying networks. In Proceedings of the LinkKDD Workshop, 9–16.Google Scholar
Oyama, S., Hayashi, K. & Kashima, H. 2011. Cross-temporal link prediction. In Proceedings of the 11th International Conference on Data Mining, 1188–1193.Google Scholar
Pastor-Satorras, R. & Vespignani, A. 2001. Epidemic spreading in scale-free networks. Physical Review Letters 86(14), 3200–3203.CrossRefGoogle ScholarPubMed
Pindyck, R. S. & Rubinfeld, D. L. 1981. Econometric Models and Economic Forecasts, 2. McGraw-Hill New York.Google Scholar
Preisach, C. & Schmidt-Thieme, L. 2006. Relational ensemble classification. In Proceedings of the 6th International Conference on Data Mining, 499–509.Google Scholar
Preisach, C. & Schmidt-Thieme, L. 2008. Ensembles of relational classifiers. Knowledge and Information Systems 14(3), 249–272.CrossRefGoogle Scholar
Redmond, U., Harrigan, M. & Cunningham, P. 2012. Identifying time-respecting subgraphs in temporal networks. In Proceedings of the 3rd International Workshop on Mining Ubiquitous and Social Environments, 51–63.Google Scholar
Rossi, R. A. 2014. Fast triangle core decomposition for mining large graphs. In Advances in Knowledge Discovery and Data Mining, 8443, 310–322.Google Scholar
Rossi, R. A. 2015. Improving Relational Machine Learning by Modeling Temporal Dependencies. PhD thesis, Purdue University.Google Scholar
Rossi, R. A., Gallagher, B., Neville, J. & Henderson, K. 2013a. Modeling dynamic behavior in large evolving graphs. In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, 667–676.Google Scholar
Rossi, R. A. & Gleich, D. 2012. Dynamic PageRank using evolving teleportation. Algorithms and Models for the Web Graph 7323, 126–137.CrossRefGoogle Scholar
Rossi, R. A., Gleich, D. & Gebremedhin, A. 2013b. Triangle core decomposition and maximum cliques. In SIAM Network Science Workshop, 1–2.Google Scholar
Rossi, R. A., Gleich, D. F., Gebremedhin, A. H. & Patwary, M. A. 2012a. What if clique were fast? Maximum cliques in information networks and strong components in temporal networks. arXiv:1210.5802, 1–11.Google Scholar
Rossi, R. A., Gleich, D. F., Gebremedhin, A. H. & Patwary, M. A. 2013c. A fast parallel maximum clique algorithm for large sparse graphs and temporal strong components. arXiv:1302.6256, 1–9.Google Scholar
Rossi, R. A., McDowell, L. K., Aha, D. W. & Neville, J. 2012b. Transforming graph data for statistical relational learning. Journal of Artificial Intelligence Research 45, 363–441.CrossRefGoogle Scholar
Rossi, R. A. & Neville, J. 2010. Modeling the evolution of discussion topics and communication to improve relational classification. In Proceedings of the ACM SIGKDD 1st Workshop on Social Media Analytics, 89–97.Google Scholar
Rossi, R. A. & Neville, J. 2012. Time-evolving relational classification and ensemble methods. In Advances in Knowledge Discovery and Data Mining 7301, 1–13. Springer.CrossRefGoogle Scholar
Salakhutdinov, R. & Hinton, G. E. 2009. Deep Boltzmann machines. In International Conference on Artificial Intelligence and Statistics, 448–455.Google Scholar
Schall, D. 2014. Link prediction in directed social networks. Social Network Analysis and Mining 4(1), 1–14.CrossRefGoogle Scholar
Sharan, U. & Neville, J. 2008. Temporal-relational classifiers for prediction in evolving domains. In Proceedings of the 8th IEEE International Conference on Data Mining, 540–549.Google Scholar
Tang, J., Musolesi, M., Mascolo, C. & Latora, V. 2009. Temporal distance metrics for social network analysis. In Proceedings of the 2nd ACM Workshop on Online Social Networks, 31–36.Google Scholar
Tang, J., Musolesi, M., Mascolo, C., Latora, V. & Nicosia, V. 2010. Analysing information flows and key mediators through temporal centrality metrics. In Proceedings of the 3rd Workshop on Social Network Systems, 1–6.Google Scholar
Tong, H. & Lin, C. 2011. Non-negative residual matrix factorization with application to graph anomaly detection. In Proceedings of the 7th SIAM International Conference on Data Mining.CrossRefGoogle Scholar
Wagner, A. & Fell, D. 2001. The small world inside large metabolic networks. Proceedings of the Royal Society of London. Series B: Biological Sciences 268(1478), 1803–1810.CrossRefGoogle ScholarPubMed
Watts, D. J. & Strogatz, S. H. 1998. Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442.CrossRefGoogle ScholarPubMed
Xiang, L., Yuan, Q., Zhao, S., Chen, L., Zhang, X., Yang, Q. & Sun, J. 2010a. Temporal recommendation on graphs via long-and short-term preference fusion. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 723–732.Google Scholar
Xiang, R., Neville, J. & Rogati, M. 2010b. Modeling relationship strength in online social networks. In Proceedings of the 19th International World Wide Web Conference, 981–990.Google Scholar
Xuan, B., Ferreira, A. & Jarry, A. 2003. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science 14(2), 267–285.CrossRefGoogle Scholar