Edges Matter: An Analysis of Graph Time-Series Representations for Temporal Networks

Representations of temporal networks arising from a stream of edges lie at the heart of models learned on it and its performance on downstream applications. Previous modeling work has mainly represented a stream of timestamped edges using a time-series of graphs based on a specific time-scaleτ(e.g., 1 mo). In contrast, it has recently been shown that constructing a time-series of graphs where each graph maintains a fixedεnumber of edges, namelyε-graph time-series, leads to better performance on downstream applications, but there has yet to be a detailed investigation on whyε-graphs outperformτ-graphs. In this work, we design extensive experiments on a benchmark of over 25 temporal network datasets, investigating the impact of edge randomization and the various representations on graph statistics. Our results indicate that theε-graph time-series representation effectively captures the structural properties of the graphs across time whereas the commonly usedτ-graph time-series mostly captures the frequency of edges. This motivates the need for a paradigm shift to developing temporal network representation learning frameworks built uponε-graph time-series. To help pave the way, we release a benchmark for the evaluation and development of better models.