Holistic Prediction on a Time-Evolving Attributed Graph (2023)

Abstract: Graph-based prediction is essential in NLP tasks such as temporal knowledge graph completion. A cardinal question in this field is, how to predict the future links, nodes, and attributes of a time-evolving attributed graph? Unfortunately, existing techniques assume that each link, node, and attribute prediction is independent, 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 interdependence 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.

## introduction real-world language-based data such as blog posts, documents, and user profiles is often interconnected, as in social networks and co-author networks. this interconnection is modeled by graphs where nodes represent objects and edges represent relationships @xcite @xcite . the structures and node attributes of such graphs often evolve over time by node addition/deletion, link addition/deletion, and node attribute changes. for instance, social networks change over time in terms of participating users, their profiles, and their links. such temporally malleable graphs are called timeevolving attributed graphs @xcite . * 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 @xcite @xcite . nlp applications often call for predicting the future of a time-evolving attributed graph such as completing a temporal knowledge graph @xcite @xcite , predicting a profile in social networks @xcite , and recommending news articles to readers @xcite ; the prediction task involved is composite, including 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 component prediction tasks independently rather than as an interdependent whole and utilizing one prediction 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 social network over a span of time in the future, e.g., job post in two years @xcite . profile information can be predicted from posts and connections to other users. a social network is time-evolving, user profiles change dynamically, new users register their accounts and some users delete their accounts. connections also change; newly registered accounts acquire connections to existing accounts with whom they have similar profiles; accounts connected to deleted accounts may connect to other accounts. these predictions are interdependent. in this paper, we introduce the problem of holistically predicting the future in a time-evolving attributed graph. figure 1 illustrates the problem, including multiple sub-predictions, such as those of node loss and new node appearance. to achieve high prediction accuracy, we need to capture the interdependence between sub-prediction tasks. as it is difficult for a single method to capture all interdependences, we must effectively combine several methods and interactively reuse the results of one task in other tasks. further, as existing methods cannot predict new node appearances, we need novel prediction methods for this sub-problem. we propose agate (a general framework for predicting attributed time-evolving graphs), a holistic, versatile prediction framework that leverages the interdependence between the tasks of predicting new nodes, lost nodes, appearing links, disappearing links, and node attributes from observed past graphs. agate comprises components for predicting the future graph and capturing task interdependence: (i) one to predict the size of an evolving graph, (ii) one to predict existing-node structure and attributes, as well as new nodes, and (iii) a reuse mechanism that reuses the results of (ii) to achieve predictions that capture the interdependence between sub-predictions. our framework can use existing methods as components. we develop a novel prediction method, proser for predicting new node appearance with attributes. we assess agate vs. the state of the art on three real-world time-evolving attributed graphs, showing that it benefits from allowing prediction tasks to affect each other, its reuse mechanism improves accuracy, and it effectively predicts new nodes with attributes. our source code is available. 1 we summarize our contributions as follows: each dimension in x may be categorical or numerical. we consider a timeevolving graph, where the number of nodes and links and values of node attributes changing over time, with d constant: definition 1 a time-evolving attributed graph is a sequence of attributed graphs ⟨g 1 , • • • , g t ⟩ over discrete time steps, where t is the number of observed time steps and g t := (v t , e t , x t ) the attributed graph at time step t. it is known as discretetime dynamic graph (dtdg). in a time-evolving graph, nodes and links appear and disappear dynamically. we discern three types of nodes at time step t: existing nodes v e t , new nodes v n t , and lost nodes v l t : at both time steps t and t -1, while those in v n t appear and those in v l t disappear at time step t. likewise, we discern existing links e e t , links connected to new nodes e n t , appearing links e a t , and disappearing links e d t : we define the problem as follows: problem 1 given a time-evolving attributed graph, ⟨g t -l+1 , g t -l+2 , . . . , g t ⟩, including appearing and disappearing nodes and links and changing node attributes, the holistic time-evolving attributed graph prediction problem asks to predict the graph at time step this problem calls to predict the whole of g t +1 , rather than one of its components. ## agate: our framework agate holistically predicts the future of timeevolving attributed graphs, exploiting the interdependence of sub-prediction tasks. figure 2 illustrates its architecture, comprising three main components for graph size, independent, and reuse predictions; the independent prediction component is subdivided in parts for existing and new nodes. agate is modular; it can employ any existing method as a component in independent and reuse predictions; as no existing method predicts new nodes with attributes, we develop our own methods for this task. agate supports prediction in attributed graphs that are either partially or fully time-evolving, e.g., it can accommodate static attributes or no link disappearance. algorithm 1 shows the pseudo code of agate. agate first predicts the output graph size (lines 1-3). then it first conducts each sub-prediction task independently to obtain a preliminary predicted graph at time step t +1 (lines 4-6), and updates the results of each such task by reusing the results of other tasks (lines 6-10). we explain each component. pink, green, and blue boxes indicate graph data, learning models, and predicted results, respectively. algorithm 1: agate input :⟨g t -l+1 , g t -l+2 , . . . , g t ⟩, a natural number i output : ĝ(i) t +1 /* graph size prediction */ 1 extract sequences of new nodes, lost nodes, appearing links, disappearing links, and links of new nodes from ⟨g t -l+1 , g t -l+2 , . . . , g t ⟩; 2 count and normalize them by dividing its maximum value; 3 predicting |v n t +1 |, |v l t +1 |, |e n t +1 |, |e a t +1 |, |e d t +1 | from each sequence of normalized values; /* independent prediction */ 4 predicting ## proser we develop a novel method, probabilistic selection rule (proser), to predict new node attributes. proser aims to maximize the matching similarity in the prediction of new node attributes. in a preliminary analysis, we observed that most new nodes have similar attributes to those of new nodes at the previous time step. thus, accuracy is relatively high when we randomly sample attributes of new nodes at the previous time step. we refine this process by selecting appropriate nodes to increase the matching similarity. by simple random sampling, matching similarity would be low when the similarity of sampled attributes to any attributes of new nodes at time step t +1 is low. proser avoids selecting such attributes by estimating the highest similarity between sampled attributes and those of new nodes. besides, matching similarity would not increase by frequently sampling a few attributes that are highly similar to some real node attributes, as each match in a perfect matching is unique. instead, we sample attributes x n t having a similar distribution to that of new node attributes in time t +1, x n t+1 . proser employs logistic regression to learn probabilities that similarities between sampled and actual new node attributes are higher than a threshold θ. before model training, we compute θ to maximize matching similarity, as: in the inference phase, proser randomly samples attributes from the set of new node attributes at time t and calculates probabilities. if these are higher than θ, we add these attributes to prediction results, otherwise discard them. we repeat, until the number of predicted attributes reaches that of new nodes. since we randomly select candidates of predicted attributes, predictions are diverse. ## experiments we experimentally validate the performance of agate and analyze the performance gain due to the exploitation of task interdependence. all experiments are conducted on a linux server with intel(r) xeon(r) cpu e5-2640 v4 @ 2.40ghz. dataset. we use three datasets with diverse timeevolving features with linguistic node attributes: nba foot_2 , reddit foot_3 , and aminer foot_4 . node attributes are embeddings of the subreddits @xcite . nodes and links change dynamically, while node attributes are static. reddit includes 7,756 unique nodes, 23,554 unique edges, 300 attributes, and 14 time steps. we divide time steps into training, validation, and test data with a 7:2:1 ratio; in nba data, that is time steps 1-48, 49-60, and 61-66, respectively; in reddit, time steps 1-11, 12-13, and 14; in aminer, time steps 1-18, 19-22, and 23-24. compared methods. we apply different methods for comparison in each sub-prediction task, since not all methods are applicable to all tasks. when predicting existing node features, we use 9 methods grouped in four categories: simple, dynamic graph embeddings, static graph gnns, and dynamic graph gnns. simple methods are: (1) baseline, which outputs g t as the predicted graph for g t +1 , (2) random, which randomly samples the predicted targets, (3) fnn, and (4) lstm. we use (5) dyngem @xcite as a dynamic graph embedding and ( 6 ) gcn @xcite as a static graph gnn. as dynamic graph gnns, we use (7) stgcn @xcite , ( 8 ) evolvegcn @xcite , which has two versions, evolvegcn-h and evelovegcn-o, and (9) tggnn that we modified gated cnn to graph tasks (see appendix in detail). to predict new nodes with attributes, we use proser and the three baseline methods described in section 3. to predict links connected to new nodes, we use cosine similarity (cs for short), fnn, and deal @xcite based upon the results predicting new nodes with attributes. deal is the state-of-the-art method. agate repeatedly predicts g t +1 ; we identify the best model for each sub-prediction task on the validation data, and go on reusing the best model's results. hyper-parameters. we run the model with at most 1,000 training iterations, 10-100 early stopping patience, batch size 1 or 2, and learning rate 0.01 with the adam optimizer. on temporal graphs, we use 3, 3, and 5 as l for nba, reddit, and aminer, respectively. we set the number i of repeated updates in reuse prediction to 3. we use cosine similarity as w(•, •) in eq. ( 1 ). we note that we tune hyper-parameters independently of models close to the input, and in reuse prediction models remain consistent. thus, hyper-parameter tuning is not hard compared to common graph prediction tasks. please see the appendix in detail. the training time totally took about 500, 700, and 200 cpu hours on nba, reddit, and aminer, respectively. our framework can run in parallel. ## related work we categorize graph prediction methods in four groups: (1) static embedding methods (e.g., @xcite ), (2) dynamic embedding methods (e.g., @xcite ), (3) static graph neural network methods (e.g., @xcite @xcite : impact of reuse iterations on node/link prediction, exist. nodes (legend split among two figures). 2018; @xcite @xcite ), and (4) dynamic graph neural network methods (e.g., @xcite @xcite @xcite @xcite @xcite ). embedding methods first derive an embedding independently of target tasks, and then build a model for each target task using the embedding as input; on the other hand, graph neural network methods directly build a model for each target task. there are two types of graph prediction tasks: static and dynamic. most methods assume that the underlying graph is static, and predict or reconstruct links or attributes. yet real-world systems and data are dynamic. while it may be possible to apply static graph methods @xcite to dynamic graphs ignoring temporal evolution, this approach is sub-optimal @xcite . learning on dynamic graphs has been recently studied, yet limited to the transductive case involving observed elements (e.g., @xcite .) such approaches are insufficient for real-world settings in which a graph evolves with links and new nodes appearing any time. some methods @xcite support the inductive setting, involving nodes unobserved in training. each method makes its own assumptions about graph properties and inference, which may not apply to all prediction tasks. discrete vs continuous. in this study, we assume discrete-time dynamic network (dtdn) as timeevolving graphs, while continuous-time dynamic network (ctdn) have been actively studied recently @xcite @xcite @xcite @xcite . ctdns are represented by a sequence of temporal graph updates instead of a sequence of temporal graphs. ctdns are often used for event-based graphs (e.g., e-commerce and message communication) as they assume each link temporally appears at a given time instead of persistent existences (e.g., friend relationships). they have different semantics and applications. thus, neural network models for ctdns do not directly apply to dtdn tasks and vice versa. other similar tasks and methods. graph generation @xcite @xcite and completion @xcite cannot be applied in our problem; they aim to generate dynamic graph topologies without attributes, or fill out missing information in a static graph. summary. there are numerous studies on timeevolving attributed graphs, yet none studies holistic time-evolving attributed graph prediction. in addition, no prior study investigate task interdependence. our work is the first to holistically predict a future time-evolving graph including new node appearance and analyze task interdependence. ## conclusion we proposed agate, a framework for holistic prediction on a time-evolving attributed graph that exploits task interdependencem and uses a novel method, proser, for predictions about new nodes and their attributes. our study showed that prediction accuracy largely improves by exploiting task interdependence.