Heuristics for Covering the Timeline in Temporal Graphs

Complex systems are usually modeled through graphs or networks in order to understand their properties and behaviors. The availability of temporal information of relations between vertices has led to the introduction of temporal graphs [7, 13, 9], where edges, called temporal edges, represent interactions between two entities at a given time. Note that different variations of the temporal graph model have been introduced; here we consider a model where the time domain, over which the temporal edges are defined, is discrete [7, 13, 9].

Temporal graphs have been considered in several domains, e.g., social network analysis [17], computational biology [8] and epidemiology [1]. We consider an approach defined for the summarizations of temporal interactions in social networks [12, 16, 15, 14]. In this context, a user activity in a social network (called activity timeline) is represented with one or more time intervals; the goal is to represent users interaction, so that if an interaction is observed at time $t$, then at least one of the user activity timeline include $t$ [14, 15, 6, 3, 2, 4, 5]. The objective function, following a parsimonious approach, is the minimization of the overall length (called span) of timeline activities or the minimization of the maximum length of the timeline activity. Here, we focus on the first objective function.

We present an example to show how activity timelines can be useful in understanding evolution of events. Consider the King Charles Coronation in May 2023. Figure 1 shows temporal co-occurrence of hashtag related to this event. The timelines, associated indicated in pink, helps to identify the main topics in the online discussions.

Several papers have studied the complexity of $k$-MinTimelineCover [15, 6, 3, 2], also in some restricted variant. In particular, the case $k=1$, where the activity timeline of each vertex is defined as a single interval, has been deeply studied, due also to the link with a foundational problem in theoretical computer science, that is Minimum Vertex Cover. For $k=1$ $k$-MinTimelineCover is NP-hard and hard to approximate within constant factor [15, 6, 3, 2]. For $k\ge 2$, the problem is even harder, as even deciding if there exists a solution (of any span) is an NP-complete problem [15].

Due to the hardness of the problem and of its restrictions, some heuristic methods have been developed, for the general problem [15, 14] and for the restriction with $k=1$ [15, 14, 11]. Only the paper that has introduced $k$-MinTimelineCover has designed practical methods for the problem [15] when $k\ge 2$, thus in this contribution we focus on designing methods for it. First, we design an ILP method that is able to solve the problem for moderate size instances, then we present a polynomial-time heuristic for $k$-MinTimelineCover, based on local search, so that it is applicable even on larger temporal graphs. In order to design our heuristic, we present a dynamic programming algorithm for a related problem, called $k$-MinIntervalCover, that runs in polynomial time.

We consider the performance of our methods on synthetic datasets, both in for the efficiency and the quality of the solutions returned. For this latter aspect we show that our heuristic, is able to shrink significantly the activity timeline lengths, with respect to the methods presented in [15].

A temporal graph $G=(V,E)$, with $V$ a set of vertices and $E$ a set of temporal edges, which are defined on time domain $[T]=[1,T]$ of timestamps (note that in the model we consider the time domain is discrete and $T$ represents the maximum timestamp value). Each temporal edge is represented by a timestamped triplet $(u,v,t)$ such that $u,v\in V$ and $t\in [T]$ represents the time when the interaction between $u$ and $v$ occurred. Note that in the temporal graphs we consider, temporal edges are undirected and unweighted.

Consider a vertex $v$ and two timestamps $s_v\in [T]$ and $e_v\in [T]$ with $s_v\le e_v$, $I_v=[s_v,e_v]$ is an activity interval of $v$. An activity timeline ${𝒯}_k(v)$ of a vertex $v\in V$ is a set of $k$ (where $k\ge 1$) activity intervals $I_{v_i}=[s_{v_i},e_{v_i}],i\in [k]$, where $s_{v_i}\le e_{v_i}$, with the constraint that for each $i\in [k-1]$. The last constraint guarantees that the activity intervals of an activity timeline of a vertex are time disjoint. Given a vertex $v\in V$ and an activity timeline ${𝒯}_k(v)$ of $v$, we say that $v$ is active in a timestamp $t$ that is included in an interval of ${𝒯}_k(v)$; if $t$ is not included in an interval of ${𝒯}_k(v)$, $v$ is said to be inactive in $t$.

Moreover, we define the span of interval $I_{v_i}$ $\delta (I_{v_i})=e_{v_i}-s_{v_i}$ as the duration of the interval $i$ for the vertex $v$. We define the span of an activity timeline ${𝒯}_k(v)$ of $v$, consisting of interval $I_{v_i}=[s_{v_i},e_{v_i}],i\in [k]$, as

The activity timeline of temporal graph $G$ is defined as:

The sum span of the activity timeline ${𝒯}_k$ of a graph $G$ is defined as the sum spam over all vertices in the temporal graph:

An important fact to note is that a vertex can have at most $k$ activity intervals, so the problem setting admits empty intervals.

Now, we define how an activity timeline covers temporal edges of a temporal graph.

Now, we are able to formally define the problem we are interested in.

Note that in the following, we will focus on the case $k\ge 2$.

Figure 2 shows an example of timeline covering over a 2-timestamps graph with 5 vertices.

In the following, we present an ILP model formulation for $k$-MinTimelineCover. Let $G=(V,E)$ be a temporal graph, and $k$ be the number of activity intervals per vertex. The ILP model is based on the following variables. Binary variables $x_v^t$, $v\in V,t\in [T]$, are used to define the timestamp that belongs to an activity timeline of $v$; $x_v^t=1$ if and only if vertex $v$ is active at time $t$. The ILP formulation also defines variables $y_v^t$, $v\in V,t\in [T]$, which are used to guarantee that the activity timeline of $v$ consists of $k$ intervals. $y_v^t=1$ if and only if vertex $v\in V$ is defined active (inactive, respectively) at time $t$, $t\in [T-1]$, and becomes inactive (active, respectively) at time $t+1$.

In this section, we present a heuristic based on local search and on a polynomial-time algorithm for a subproblem of $k$-MinTimelineCover. The motivation behind the use of the local search technique is that for large graph instances and a large $k$, we have observed that along the intervals produced by the heuristic solutions there were many which could be left out of the solution without affecting the correctness of $k$-MinTimelineCover.

Before we introduce the steps of the local search procedure (see below), we introduce the concept of loss inspired by the paper of Lazzarinetti et al. [10]. For each vertex $v\in V$ at timestamp $t\in [T]$ we define its associated loss $loss(v,t)$ as the number of edges covered that would become uncovered if $v$ becomes inactive at time $t$. Given an interval $I(v)$ of an activity timeline $𝒯(v)$ of a vertex $v$, the interval loss $loss(I(v))$ is defined as:

Our improvement algorithm improves the solution provided by the heuristics in [15] and refines it using local search. The local search algorithm: (1) finds for each vertex $v$ if there exists an activity interval of $loss=0$ in the solution; (2) it removes the activity timeline ${𝒯}_k(v)$ from the solution; (3) it computes the timestamps associated with the temporal edges incident in $v$ left uncovered by the pruning of step (2); (4) it computes by dynamic programming algorithm an activity timeline of $v$ of minimum span, containing the timestamps of step (3).

The motivation for this strategy is that, if there is an interval $I(v)$ of $loss=0$, it is not useful to cover temporal edges, instead of removing only $I(v)$, we decide to remove all the activity timeline ${𝒯}_k(v)$. This allows us to define a new activity timeline for $v$ with $k$ intervals. Basically, by reconfiguring the whole activity interval, we can find a new structure for ordering the activity timestamps which would allow for a smaller span than the one which would result by only deleting a single activity interval. Even though the strategy produces additional cost regarding computation, it can produce a much better solution because it saves not only the span of the deleted interval, but also the span saved by reshuffling the activity timestamps into new intervals.

For example, assume that ${𝒯}_k(v)$ contains another interval $I^{\prime }(v)$ of positive loss, such that $I^{\prime }(v)$ covers a temporal edge $(u,v,t)$. If $(u,v,t)$ is covered also by an interval of vertex $u$, we don’t require to cover $(u,v,t)$ when we recompute the timeline activity of $v$. Note that the activity timeline computed at point (4) does not increase the span with respect to ${𝒯}_k(v)$.

We begin by describing how our heuristic deals with steps (1) - (3), by constructing a specialized data structure, to which we will refer as loss dictionary, based on the initial solution. This structure associates each activity interval of every vertex with a corresponding loss value, which is initialized to zero. For each temporal edge in $G$, we examine whether it is covered in the initial solution by both incident vertices or only by one. If the edge is covered by both vertices, no modification is made in the loss dictionary. However, if it is covered by only one vertex, this implies that the vertex must be active at that specific timestamp, otherwise the temporal edge would become uncovered. Consequently, we increment the loss value $loss(I(v))$ of the activity interval of the corresponding vertex by one. After iterating through all temporal edges and updating the loss dictionary accordingly, we identify all vertices that possess at least one activity interval with a loss value of zero. These intervals are deemed redundant and subsequently, for that vertex we recalculate its activity timeline from scratch, by parsing through the timestamps and looking for the uncovered timestamped edges.

Following this pruning step, we recompute the activity timeline for that vertex using a dynamic programming algorithm. We must specify the fact that indeed, the pruning step can be done also for vertices not associated with an activity interval of $loss=0$. We tested this on relatively small synthetically generated datasets and the result was very similar to the result of our approach, because for most of the vertices which do not contain $loss=0$ intervals, the recalculation process is not able to shrink the activity timeline.

Now, we formally present the dynamic programming step (4), which solves the following problem.

Note that, given $i\in [z]$, we denote by $𝒰[i]$ the $i$-th timestamp in $𝒰$. Now, we give the dynamic programming recurrence to solve in polynomial time $k$-MinIntervalCover. Let $z=|U|$. Define $DP[i][j]$, where $i\in [z]$ and $j\in [k]$, as the minimum span of a sequence of $j$ intervals in $[𝒰[i],𝒰[z]]$ that covers each timestamp in $𝒰$ from the $i$-th to the $z$-th one. Furthermore, we assume that $z$ is a timestamp that contains no temporal edge and thus not need to be covered. This is used to allow some interval to be empty. Also note that empty intervals do not need to be time disjoint. The recurrence of compute $DP[i][j]$, where $i\in [z]$ and $j\in [k]$, is defined in the following.

For the base cases $DP[i][0]=+\mathrm{\infty }$, for each $i\in z$; $DP[z][0]=0$.

Next, we prove the correctness of Recurrence 5.

We begin this section by describing how we create the synthetically generated dataset on which we will test both the ILP model and the heuristic. It is based on the generated dataset of [14] and for each iteration of our algorithms we consider a static underlying graph structure $G=(V,E)$. For each $v\in V$ we simulate a set of temporal interaction intervals at different timestamps. The parameters controlling the generation process include the number of interaction intervals per vertex, the distance between events, the inter-interval spacing, and the degree of temporal overlap between consecutive intervals. For simplicity and replicability, parameters were held constant across iterations. The generator ensures stochastic yet reproducible behavior through a fixed random seed. The resulting dataset consists of a chronologically ordered list of timestamped interactions $(u,v,t)$, as well as a mapping of vertices to their corresponding $k$ active time intervals. Experiments were conducted on a Macbook Pro machine with $11$ CPU cores, $18$ GB RAM, and $M3$ $ARM$ processor to ensure consistency in runtime comparisons.

We evaluate the performance of our Integer Linear Programming (ILP) formulation on synthetically generated temporal networks. We used a Gurobi solver in its current configuration, the model scales effectively to instances comprising up to $50,000$ temporal edges, with total runtime remaining under $25$ minutes. The formulation demonstrates optimal performance in scenarios characterized by a relatively small number of activity intervals per vertex. For our standard benchmarking experiments, we fixed the number of activity intervals at $k=10$ and used an overlap coefficient of $0.5$. Additionally, to assess the scalability of the approach under alternative structural conditions, we conducted a separate test with a reduced $k$ value and a larger graph containing more vertices and edges. Empirically, we observed that lower overlap coefficients lead to faster computational times; nonetheless, we maintained a minimum overlap of $0.5$ in most experiments to better reflect real-world temporal dynamics. Across all tested configurations, the ILP formulation consistently achieved high solution accuracy, with both precision and recall exceeding $99\%$, indicating the correctness and robustness of the approach.

In the following, we compare the results of the k-Baseline and k-Inner heuristics of [14] with their improved versions using the heuristic algorithm. We will do a separate analysis for each of the considered algorithms. Starting with k-Baseline, we observe that, precision-wise the results are similar. This apparent discrepancy occurs because both sets of intervals are being compared against the ground-truth results, which remain considerably smaller in magnitude. The standard comparison metrics do not fully capture the practical significance of our improvements because both the initial approach and our method necessarily produce solutions that deviate substantially from the optimal (given the NP-hard nature of the problem and its known approximation hardness of any factor). Nevertheless, when examining the total interval length across all vertex variations, we observe a clear and consistent improvement. This improvement stems directly from our algorithm (as detailed in Section 5), which calculates the loss of every interval for each vertex and, for vertices containing intervals with zero loss, recalculates the activity timestamps and optimally reorders them using dynamic programming.

Comparative analysis of our approach against the baseline reveals consistent improvements in precision and recall metrics, which are represented by an average improvement that exceeds $2.5\%$ and peak differentials of more than $5\%$ in maximum values. We use Figure 4 for reference. Other relevant average comparisons are for recall, which stays the same for the Baseline and the Heuristic Improvement algorithm at $0.65$. More significantly, our method demonstrates substantial optimization of the total interval length, reducing it from $3.0\ast 1e6$ to $2.5\ast 1e6$, which constitutes a reduction of $16.7\%$. This considerable decrease in total length, coupled with the consistent precision improvements, underscores the robustness and practicality of our algorithmic refinements.

In the experimental phase aimed at enhancing the k-Inner algorithm, we adopted a slightly modified approach. Specifically, we conducted a dry run for all vertices $v\in V$ with a loss value of zero, retaining the newly generated activity intervals only if they resulted in a lower total cost compared to the baseline established by the original k-Inner algorithm. This conservative strategy was employed as a safeguard, given that the original heuristic already achieves a high precision of approximately $75\%$. In earlier iterations, we observed instances where modifying certain vertices adversely affected the interval structure, leading to significant reductions in overall precision. Despite these challenges, our modified heuristic yields slight but consistent improvements. However, given the already high baseline precision, these gains typically fall within a margin of approximately $1\%$. To ensure robustness in evaluation, we extended the number of iterations and increased the total number of vertices analyzed. As shown in Figure 6, our approach surpasses the $75\%$ precision threshold for a limited number of vertices, after which the performance aligns closely with that of the original k-Inner algorithm. This convergence is expected, as the algorithm already performs near-optimally, leaving few opportunities for zero-loss interval modifications. Consequently, the impact on the total interval length remains minimal.

We have considered $k$-MinTimelineCover, a problem defined for complex data summarization. We have presented an ILP formulation for moderate size instances and we have designed an efficient heuristic based on local search. We have presented an experimental evaluation on synthetic data sets for both methods. Future works include an experimental evaluation on real-word datasets and an investigation of the performance of variants of our heuristics that extend the local search approach, for example when more than one vertex containing an interval of loss equal to $0$ is considered in this step.