Segmentation of temporal graphs

We study the problem of segmentation of temporal graphs (TGRAPHSEG): given a temporal graph – i.e., a sequence of snapshots depicting the relationships (temporal edges) occurring among entities (vertices) of interest at specific timestamps – aggregate similar consecutive snapshots and replace every aggregated snapshot set with a single, well-representative (newly computed) snapshot, to optimize a tradeoff between data reduction ratio and closeness between segmented and original graphs. This novel fundamental problem produces more compact versions of temporal graphs, thus making them more amenable to resource-efficient and responsible downstream processing, without any need for changing the technology already in place to handle them in their raw form. The proposed TGRAPHSEG is formulated as an instance of Sequence Segmentation (SEQSEG), a well-established combinatorial optimization problem for time-series data reduction. The contextualization of SEQSEG to the temporal-graph setting implies major technical challenges, including defining a proper distance function among snapshots and a methodology to compute representative snapshots from the aggregated ones. Additionally, non-trivial implementation challenges are faced to efficiently adapt popular SEQSEG algorithms to the context at hand. Effective solutions are provided to address all these challenges. Based on these, we devise a principled formulation of TGRAPHSEG, along with two algorithms: an exact, more accurate one and a heuristic, faster one. Our contributions are complemented by an extensive experimental evaluation, which attests to the high performance of the proposed algorithms and their superiority over baselines on a variety of real data and the downstream tasks of vertex similarity search and temporal community detection. Reproducibility: Source code is available at https://github.com/rafgia/temporal-graph-segmentation.