On the Equivalence Between Temporal and Static Graph Representations for Observational Predictions
arXiv:2103.07016
Abstract
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.
References in corpus (18)
- Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling
- Semi-Supervised Classification with Graph Convolutional Networks
- Neural Message Passing for Quantum Chemistry
- Interaction Networks for Learning about Objects, Relations and Physics
- dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning
- Dynamic Graph Convolutional Networks
- Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey
- Temporal motifs in time-dependent networks
- DynGEM: Deep Embedding Method for Dynamic Graphs
- Node Embedding over Temporal Graphs
- Temporal Graph Networks for Deep Learning on Dynamic Graphs
- GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Link Prediction
- Identifiability of Causal Graphs using Functional Models
- The Weisfeiler-Lehman Method and Graph Isomorphism Testing
- On the Expressive Power of Deep Polynomial Neural Networks
- DyLink2Vec: Effective Feature Representation for Link Prediction in Dynamic Networks
- On the Equivalence between Positional Node Embeddings and Structural Graph Representations
- Graph Hawkes Neural Network for Forecasting on Temporal Knowledge Graphs