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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\tau$</tex-math></inline-formula> (e.g., 1 mo). In contrast, it has recently been shown that constructing a time-series of graphs where each graph maintains a fixed <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula> number of edges, namely <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-graph time-series, leads to better performance on downstream applications, but there has yet to be a detailed investigation on why <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-graphs outperform <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\tau$</tex-math></inline-formula>-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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-graph time-series representation effectively captures the structural properties of the graphs across time whereas the commonly used <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\tau$</tex-math></inline-formula>-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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-graph time-series. To help pave the way, we release a benchmark for the evaluation and development of better models.