Holistic Prediction on a Time-Evolving Attributed Graph

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 13676–13694 July 9-14, 2023 ©2023 Association for Computational Linguistics Holistic Prediction on a Time-Evolving Attributed Graph Shohei Yamasaki1,∗,†, Yuya Sasaki2,∗, Panagiotis Karras3, Makoto Onizuka2 1Nomura Research Institute, Ltd., Japan, 2Osaka University, Japan 3Aarhus University, Denmark s2-yamasaki@nri.co.jp, {sasaki,onizuka}@osaka-u.ac.jp, piekarras@gmail.com Abstract Graph-based prediction is essential in NLP tasks such as temporal knowledge graph com- pletion. A cardinal question in this field is, how to predict the future links, nodes, and attributes of a time-evolving attributed graph? Unfortu- nately, existing techniques assume that each link, node, and attribute prediction is indepen- dent, and fall short of predicting the appearance of new nodes that were not observed in the past. In this paper, we address two interrelated questions; (1) can we exploit task interdepen- dence to improve prediction accuracy? and (2) can we predict new nodes with their attributes? We propose a unified framework that predicts node attributes and topology changes such as the appearance and disappearance of links and the emergence and loss of nodes. This frame- work comprises components for independent and interactive prediction and for predicting new nodes. Our experimental study using real- world data confirms that our interdependent prediction framework achieves higher accuracy than methods based on independent prediction. 1 Introduction Real-world language-based data such as blog posts, documents, and user profiles is often intercon- nected, as in social networks and co-author net- works. This interconnection is modeled by graphs where nodes represent objects and edges represent relationships (Bansal et al., 2019; Bai et al., 2021; Zhu et al., 2019; Wu et al., 2021). The structures and node attributes of such graphs often evolve over time by node addition/deletion, link addi- tion/deletion, and node attribute changes. For in- stance, social networks change over time in terms of participating users, their profiles, and their links. Such temporally malleable graphs are called time- evolving attributed graphs (Rossi et al., 2020). *These authors contributed equally to this work †This work was done when Shohei Yamasaki was a student at Osaka University Graph-based methods are essential in various NLP tasks (Zhou et al., 2021; Mondal et al., 2021; Xie et al., 2021). NLP applications often call for predicting the future of a time-evolving attributed graph such as completing a temporal knowledge graph (Goel et al., 2020; Mirza and Tonelli, 2016; Xu et al., 2021a), predicting a profile in social net- works (Hasanuzzaman et al., 2017), and recom- mending news articles to readers (Wu et al., 2019); the prediction task involved is composite, includ- ing several sub-prediction tasks. Conventionally, this composite prediction task is addressed in a compartmentalized manner, separately applying a technique for each component sub-prediction task. This compartmentalized approach treats compo- nent prediction tasks independently rather than as an interdependent whole and utilizing one predic- tion to inform another. Besides, to our knowledge, existing works in time-evolving graph prediction do not predict new nodes and their attributes. Example 1.1 Let us consider profile prediction in a …

Content truncated to 500 words