On the Equivalence Between Temporal and Static Graph Representations for Observational Predictions
This addresses a foundational problem in graph machine learning for researchers and practitioners, offering a novel framework that is incremental but provides practical improvements.
This work tackles the problem of predicting node attribute evolution in temporal graphs by formalizing two representation frameworks, showing that the time-then-graph approach has an expressivity advantage over the popular time-and-graph method when using non-most-expressive GNNs, and experiments demonstrate it achieves better performance and efficiency in some real-world tasks.
This work formalizes the associational task of predicting node attribute evolution in temporal graphs from the perspective of learning equivariant representations. We show that node representations in temporal graphs can be cast into two distinct frameworks: (a) The most popular approach, which we denote as time-and-graph, where equivariant graph (e.g., GNN) and sequence (e.g., RNN) representations are intertwined to represent the temporal evolution of node attributes in the graph; and (b) an approach that we denote as time-then-graph, where the sequences describing the node and edge dynamics are represented first, then fed as node and edge attributes into a static equivariant graph representation that comes after. Interestingly, we show that time-then-graph representations have an expressivity advantage over time-and-graph representations when both use component GNNs that are not most-expressive (e.g., 1-Weisfeiler-Lehman GNNs). Moreover, while our goal is not necessarily to obtain state-of-the-art results, our experiments show that time-then-graph methods are capable of achieving better performance and efficiency than state-of-the-art time-and-graph methods in some real-world tasks, thereby showcasing that the time-then-graph framework is a worthy addition to the graph ML toolbox.