# Scalable Temporal Motif Densest Subnetwork Discovery

Ilie Sarpe  0009-0007-5894-0774 KTH Royal Institute of
TechnologyStockholmSweden<EMAIL_ADDRESS>,  Fabio Vandin  0000-0003-2244-2320
University of PadovaPadovaItaly<EMAIL_ADDRESS>and  Aristides Gionis
0000-0002-5211-112X KTH Royal Institute of TechnologyStockholmSweden
<EMAIL_ADDRESS>
(2024)

###### Abstract.

Finding dense subnetworks, with density based on edges or more complex
structures, such as subgraphs or $k$-cliques, is a fundamental algorithmic
problem with many applications. While the problem has been studied extensively
in static networks, much remains to be explored for _temporal networks_.

In this work we introduce the novel problem of identifying the _temporal motif
densest subnetwork_ , i.e., the densest subnetwork with respect to _temporal
motifs_ , which are high-order patterns characterizing temporal networks.
Identifying temporal motifs is an extremely challenging task, and thus,
efficient methods are required. To address this challenge, we design two novel
randomized approximation algorithms with rigorous probabilistic guarantees
that provide high-quality solutions. We perform extensive experiments showing
that our methods outperform baselines. Furthermore, our algorithms scale on
networks with up to _billions_ of temporal edges, while baselines cannot
handle such large networks. We use our techniques to analyze a financial
network and show that our formulation reveals important network structures,
such as bursty temporal events and communities of users with similar
interests.

temporal motifs; temporal networks; randomized algorithms

††journalyear: 2024††copyright: rightsretained††conference: Proceedings of the
30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; August
25–29, 2024; Barcelona, Spain††booktitle: Proceedings of the 30th ACM SIGKDD
Conference on Knowledge Discovery and Data Mining (KDD ’24), August 25–29,
2024, Barcelona, Spain††doi: 10.1145/3637528.3671889††isbn:
979-8-4007-0490-1/24/08††ccs: Theory of computation Graph algorithms
analysis††ccs: Mathematics of computing Probabilistic algorithms

##  1\. Introduction

(a)

(b)

Figure 1. 1a: Representation of a temporal network $T$ with $n=7$ vertices,
$m=18$ edges (edge labels denote the timings, and commas denote multiple
edges), and a temporal motif $M$ with its ordering $\sigma$ (i.e., $\sigma$
captures the temporal dynamics of the motif $M$). 1b: for $\delta=10$ only the
green sequences ($S_{1},S_{2}$) are $\delta$-instances of $M$ in $T$; the red
sequences are not $\delta$-instances, since $S_{3}$ cannot be mapped on the
motif $M$ following $\sigma$, and $S_{4}$ exceeds the timing constraint on
$\delta$.

Networks (or graphs) are fundamental abstractions for understanding and
characterizing complex systems, such as social networks (Freeman, 2004),
biological systems (Dorogovtsev and Mendes, 2003), and more (Lee et al., 2012;
Huebsch et al., 2003). An important primitive in graph mining is the discovery
of _dense subgraphs_ (Gionis and Tsourakakis, 2015). Dense-subgraphs find
applications in areas such as visualization (Sariyuce et al., 2015), anomaly
detection (Chen and Tsourakakis, 2022), finance (Boginski et al., 2003), and
social networks (Henry et al., 2007; Fazzone et al., 2022). The _density_ of a
subnetwork is often defined as the total number of its _edges_ divided by the
number of its vertices, and the _densest subnetwork_ is the one attaining
maximum density. The definition of density can be extended to higher-order
structures, such as $k$-_cliques_ or $k$-_vertex motifs_ (Tsourakakis, 2015;
Fang et al., 2019; Sun et al., 2020b), leading to subnetworks that offer a
more nuanced characterization of the data, e.g., more tightly-connected
communities in social networks.

Many real-world networks are inherently _temporal_ (Holme and Saramäki, 2012),
containing information about the timing of the interactions (Masuda and
Lambiotte, 2016). Temporal networks enable the study of _novel_ phenomena not
observable otherwise, such as bursty activities (Lambiotte et al., 2013),
dynamic reachability, temporal centrality (Santoro and Sarpe, 2022; Tang et
al., 2010; Oettershagen and Mutzel, 2020), and more (Holme and Saramäki, 2019;
Oettershagen et al., 2023b).

_Temporal motifs_ are small-size subgraphs with edges having temporal
information and a duration bound (Liu et al., 2019, 2021; Zhao et al., 2010;
Kovanen et al., 2011). The temporal information on the edges captures the
_temporal dynamics_ of the motif, for example, information can spread on a
temporal path $x\stackrel{{\scriptstyle t_{1}}}{{\to}}z\stackrel{{\scriptstyle
t_{2}}}{{\to}}w$ only if $t_{1}<t_{2}$. In addition, a duration constraint
ensures that relevant events occur sufficiently close in time, e.g.,
$t_{2}-t_{1}$ is not too large. Temporal motifs are building blocks for
temporal networks, finding novel applications, such as cryptocurrency network
analysis (Wu et al., 2022; Arnold et al., 2024), anomaly detection (Belth et
al., 2020), and more (Liu and Sariyüce, 2023; Lei et al., 2020).

There has been growing interest in developing efficient algorithms to count
and enumerate temporal motifs (Pashanasangi and Seshadhri, 2021; Wang et al.,
2020a; Sarpe and Vandin, 2021b, a; Liu et al., 2019; Mackey et al., 2018; Cai
et al., 2023; Pu et al., 2023). Identifying temporal motifs is a challenging
task, considerably harder than its counterpart in static networks. In fact,
there are motifs that can be identified in polynomial time in static networks
but their identification becomes $\mathbf{NP}$-hard in temporal networks (Liu
et al., 2019). Therefore, little has been done in characterizing _temporal
subnetworks_ with respect to temporal motif instances.

In this work we introduce and study the novel problem of discovering the
densest temporal subnetwork with respect to a temporal motif, that is given a
large temporal network and a temporal motif, our goal is to find the
_temporal-motif densest subnetwork_ , i.e., the subnetwork maximizing a
density function that accounts for the number of temporal motif instances
normalized by its size.

Example. Consider a financial temporal network and a temporal triangle
$M:x\stackrel{{\scriptstyle t_{1}}}{{\to}}z\stackrel{{\scriptstyle
t_{2}}}{{\to}}w\stackrel{{\scriptstyle t_{3}}}{{\to}}x$ as from Figure 1a,
where $M$ captures potential money laundering activities occurring between
users in a short duration (Wu et al., 2022; Liu et al., 2024). Some users may
be known to be involved in suspicious activities (e.g., they transfer large
amount of money; shown in red in Fig. 1a) while others are not (e.g., no
history is available for their transactions; shown in yellow or blue in Fig.
1a). By finding the marked densest subnetwork ($\\{v_{1},\dots,v_{5}\\}$)
according to motif $M$ we can identify a tightly-connected subset of users
potentially involved in suspicious activities. Interestingly, this subnetwork
may contain new suspicious users (in yellow in Fig. 1a), not previously
identified.

Other promising applications captured by our formulation are, for example, (i)
identifying frequent destinations appearing together from user travel data,
i.e., groups of attractions visited following a specified travel journey
captured by a temporal motif (Lei et al., 2020); and (ii) detecting _dense_
groups of users and items according to specific purchase sequences on
e-commerce platforms, again captured trough temporal motifs (Pu et al., 2023;
Cai et al., 2023). In both scenarios, the _temporal motif-subnetwork densest
subnetwork_ can provide unique insights, for (i) it can be used to design
novel public transport routes or travel passes; and for (ii) it can be used
for personalized advertising or identifying users with common purchase habits.

Solving the problem we propose requires _exact enumeration_ of _all_ temporal
motif instances in the input network, which is extremely inefficient to
perform. To address this issue we propose ALDENTE, a suite of randomized
approximation ALgorithms for the temporal motif DENsest subneTwork problEm.
ALDENTE contains two novel approximation algorithms leveraging a _randomized
sampling_ procedure, which has been successfully employed for temporal motif
counting (Liu et al., 2019; Sarpe and Vandin, 2021b, a; Pu et al., 2023). Our
novel algorithms can leverage any state-of-the-art unbiased sampling algorithm
for temporal motif counting. The first algorithm in ALDENTE peels the vertex
set in _batches_ until it becomes empty (removing vertices participating in
few temporal motif instances), _estimating_ for small $\varepsilon>0$ within
$(1\pm\varepsilon)$ the different counts needed for peeling. The second
algorithm adopts a similar estimated _batch-peeling_ technique but only for a
fixed number of steps. On the remaining vertices it applies a _greedy-peeling_
approach, where vertices that participate in few temporal motif instances are
peeled one at a time. By carefully combining estimates, our methods output a
high-quality solution with controlled error probability. Both our algorithms
_avoid exhaustive enumeration_ of all temporal motifs in the input network.

We show that the problem we study cannot be solved by directly applying
existing techniques tailored to static high-order density formulations that
ignore the information provided by temporal motifs (Tsourakakis, 2014; Wang et
al., 2020b; Tsourakakis, 2015; Fang et al., 2019; Mitzenmacher et al., 2015;
Chen et al., 2023; Sun et al., 2020b), as this leads to poor quality
solutions. We then _embed temporal information_ in a weighted set of
subgraphs, which can be used to leverage existing techniques for the
identification of $k$-vertex Motif Densest Subnetworks ($k$-MDS). This results
into three baselines (an exact methods and two approximate ones), extending
previous ideas for static networks (Goldberg, 1984; Charikar, 2000; Bahmani et
al., 2012; Epasto et al., 2015).

We finally show that the methods in ALDENTE find high-quality solutions on
_billion-edge temporal networks in few hundreds of seconds_ , where all other
baselines cannot terminate in hours.

Summarizing, our contributions are as follows:

1. We introduce the Temporal Motif Densest Subnetwork (TMDS) problem, asking for the densest subnetwork of a temporal network, where the density considers the number of instances of a temporal motif. The TMDS problem strongly differs from existing temporal cohesive subgraph formulations given its _temporal motif_ -based density formulation. We show that the TMDS problem is not captured by analogous formulations on static networks ($k$-MDS) that disregard temporal information. We then develop three baselines extending ideas for $k$-MDS discovery embedding temporal information in a suitable weighted set of subgraphs, unfortunately such algorithms do not scale on large data.

2. We design ALDENTE, a suite of two novel approximation algorithms based on randomized sampling and peeling techniques, providing _high-quality solutions_ and _scaling on massive networks_.

3. We perform experiments on medium- and large-size temporal networks, with up to billions of edges, validating ALDENTE. We show that baselines are often inefficient on large datasets. Our randomized algorithms consistently achieve speedups from $\times 2$ to $\times 43$, saving hundreds of GBs of memory, and reporting high-quality solutions. We conclude with a case study on a financial network discovering interesting temporal motif dense subnetworks.

Details on application scenarios for TMDS are provided in App. A, and a
summary of the notation is found in App. B. We report in the Appendix,
detailed proofs of our results (App. E), additional discussion on methods
(App. D and App. F) and experiments (App. H). Our implementation is publicly
available.111https://github.com/iliesarpe/ALDENTE.

##  2\. Preliminaries

A _temporal network_ is a pair $T=(V_{T},E_{T})$, where
$V_{T}=\\{v_{1},\dots,v_{n}\\}$ is a set of vertices and
$E_{T}=\\{(u,v,t):u,v\in V_{T},t\in\mathbb{R}^{+}\\}$ is a set of _temporal
edges_. We let $n=|V_{T}|$ be the number of vertices and $m=|E_{T}|$ be the
number of edges. Each edge $e=(u,v,t)\in E_{T}$ contains a timestamp $t$,
representing the time of its occurrence.222We will denote directed edges by
“$(\ldots)$” and undirected edges by “$\\{\ldots\\}$”. Without loss of
generality we assume that the edges in $E_{T}$ are listed by increasing
timestamp and that timestamps are distinct.333In practice priority bits are
assigned to enforce a strict total ordering over $E_{T}$.

Next we introduce _temporal motifs_. For concreteness, we adopt the definition
of temporal motifs proposed by Paranjape et al. (2017) that is one of the most
commonly used in practice, but our results can be extended to other
definitions of temporal motifs, e.g., the ones surveyed by Liu et al.
(2021).444By suitably replacing some of the subroutines of the algorithms in
ALDENTE. While we focus on unlabeled networks, our approach can be also
extended to labeled networks.

###### Definition 2.1 (Paranjape et al. (2017)).

A _$k$ -vertex $\ell$-edge temporal motif_ with $k,\ell\geq 2$ is a pair
$M=({K},\sigma)$, where ${K}=(V_{K},E_{K})$ is a directed and weakly-connected
_(multi-)graph_ , with $|V_{K}|=k$, $|E_{K}|=\ell$, and $\sigma$ is an
ordering of the $\ell$ edges in $E_{K}$.

A $k$-vertex $\ell$-edge temporal motif is also identified by the _sequence_
$\langle(x_{1},y_{1}),\dots,(x_{\ell},y_{\ell})\rangle$ of $\ell$ edges of
$E_{K}$ _ordered_ according to $\sigma$. An illustration of a temporal motif
is shown in Figure 1a.

###### Definition 2.2 ($\delta$-instance of a temporal motif).

Given a temporal network $T$, a temporal motif $M$, and a value
$\delta\in\mathbb{R}^{+}$ corresponding to a _time-interval length_ , a _time-
ordered_ sequence
$S=\langle(x_{1}^{\prime},y_{1}^{\prime},t_{1}^{\prime}),\dots,(x_{\ell}^{\prime},y_{\ell}^{\prime},t_{\ell}^{\prime})\rangle$
of $\ell$ unique temporal edges of $T$ is a _$\delta$ -instance_ of the
temporal motif
$M=\langle(x_{1},y_{1}),\dots,\allowbreak(x_{\ell},y_{\ell})\rangle$ if:

(1) there exists a bijection $h$ from the vertices appearing in $S$ to the
vertices of $M$, with $h(x_{i}^{\prime})=x_{i}$ and $h(y_{i}^{\prime})=y_{i}$,
and $i\in[\ell]$;

(2) the edges of $S$ occur within $\delta$ time; i.e.,
$t_{\ell}^{\prime}-t_{1}^{\prime}\leq\delta$.

The bijection implies that edges in $S$ are mapped onto edges in $M$ in the
_same ordering_ $\sigma$. Additionally, a $\delta$-instance is not required to
be vertex-induced. An example of Definition 2.2 is shown in Fig. 1b.

Let $\mathcal{S}_{T}=\\{S:S\text{ is a }\delta\text{-instance of }M\text{ in
}T\\}$ be the _set of $\delta$-instances of a motif $M$_ for a given time-
interval length $\delta$. Computing the set $\mathcal{S}_{T}$ is extremely
demanding, first such a set can have size
$\mathcal{O}\\!\left({m\choose\ell}\right)$, and, in general even detecting a
single $\delta$-instance of a temporal motif is an $\mathbf{NP}$-hard problem
(Liu et al., 2019).

We define a _weighting function_ $\tau:\mathcal{S}_{T}\mapsto\mathbb{R}^{+}$
that assigns a non-negative weight to each $\delta$-instance
$S\in\mathcal{S}_{T}$ based on its edges and vertices, e.g., accounting for
importance scores for vertices and/or edges, or available metadata. Given
$S=\langle(x_{1},y_{1},t_{1}),\dots,\allowbreak(x_{\ell},y_{\ell},t_{\ell})\rangle\in\mathcal{S}_{T}$
two possible realizations of weighting functions are:

(i) a _constant_ function $\tau_{c}$: $\tau_{c}(S)=1$, and

(ii) a _decaying_ function $\tau_{d}$:
$\tau_{d}(S)=\frac{1}{\ell-1}\sum_{j=2}^{\ell}\exp(-\lambda(t_{j}-t_{j-1})),$
where $\lambda>0$ controls the time-exponential decay.

In the above, $\tau_{c}$ is a simple weighting function where each
$\delta$-instance receives a unitary weight, this can be used in most
exploratory analyses where no prior information is known about the network.
The decaying function $\tau_{d}$ is inspired from link-decay models, where the
value of $\lambda$ corresponds to the inverse of the average inter-time
distance of the timestamps in $E_{T}$. Therefore, the function $\tau_{d}$
accounts for decaying processes over networks, which are common in various
domains, e.g., email communications, and spreading of diseases (Ahmed et al.,
2021; Ahmad et al., 2021; Vazquez et al., 2007).

As an example, considering the instance $S_{1}$ from Fig. 1a, then
$\tau_{c}(S_{1})=1$, while for $\lambda=0.1$ then
$\tau_{d}(S_{1})=\frac{1}{2}(e^{-3\lambda}+e^{-6\lambda})\approx 0.64$.

Given $T=(V_{T},E_{T})$ and a subset of vertices $W\subseteq V_{T}$, we denote
with $T[W]$ the temporal subnetwork _induced_ by $W$ as $T[W]=(W,E_{T}[W])$,
where $E_{T}[W]=\\{(u,v,t):u\in W,\allowbreak v\in W,\allowbreak(u,v,t)\in
E_{T}\\}$ is the set edges from $E_{T}$ among the vertices in $W$. Given
$W\subseteq V_{T}$, a temporal motif $M$, and $\delta\in\mathbb{R}^{+}$, for
ease of notation, we denote with $\mathcal{S}_{W}$ the set of all
$\delta$-instances of $M$ in $T[W]$. With these definitions at hand we can now
assign _weights_ to the set of $\delta$-instances of a temporal motif $M$ in a
temporal subnetwork. Finally, given $W\subseteq V_{T}$ and a weighting
function $\tau$ we define the the _total weight_ of the set of
$\delta$-instances of motif $M$ in $T[W]$ as
$\mathcal{\tau}(W)=\sum_{S\in\mathcal{S}_{W}}\tau(S).$

As an example, for $T$ and $M$ as in Fig. 1a, for $W=\\{v_{1},v_{2},v_{3}\\}$,
the constant weight function $\tau_{c}$, and $\delta=20$, we have $\tau(W)=4$.

We are now ready to state the problem we address in this paper.

###### Problem 1 (Temporal Motif Densest Subnetwork (TMDS)).

Given a temporal network $T=(V,E)$, a temporal motif $M$, a time-interval
length $\delta\in\mathbb{R}^{+}$, and a weighting function
$\tau:\mathcal{S}_{T}\mapsto\mathbb{R}_{>0}$, find a subset of vertices
$W^{*}\subseteq V$ that maximizes the density function

$\rho(W)=\frac{\tau(W)}{|W|}.$

The TMDS problem takes in input a temporal motif $M$, a weighting function
$\tau$, and the time-interval length $\delta\in\mathbb{R}^{+}$. Differently
from existing works in the literature of temporal-networks we are _not_ trying
to find a time-window to maximize a static (or temporal) density score. As an
example, consider $T$ and $M$ from Fig. 1a, and the TMDS problem with constant
weighting function $\tau_{c}$. Fig. 1a shows the solution obtained with
$\delta=10$, where the optimal solution is
$W^{*}=\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$ with
$\rho(W^{*})=\tau(W^{*})/|W^{*}|=6/5$. Note that the timestamps in $T[W^{*}]$
span an interval length greater than $\delta$ (i.e., $[1,17]$).

Throughout this paper we say that a vertex set $W\subseteq V$ achieves an
$\alpha$-_approximation ratio_ , with $\alpha\leq 1$, if
$\rho(W)/\mathrm{OPT}\geq\alpha$, where $\mathrm{OPT}\mathbin{=}\rho(W^{*})$
is the value of an optimal solution to Problem 1. An algorithm that returns a
solution with an $\alpha$-approximation ratio is an _$\alpha$ -approximation
algorithm_.

We conclude the preliminaries with defining the _temporal motif degree_ of
vertex $v\in V_{T}$ by
${d}_{V_{T}}^{\tau}(v)\mathbin{=}\sum_{S\in\mathcal{S}_{V_{T}}}(\tau(S)\mathbbm{1}[v\in
S]$), where $\mathbbm{1}[v\in S]$ is an indicator function denoting if the
vertex appears at least once over the edges in the $\delta$-instance $S$. As
an example, if we consider $T$ and $M$ as in Fig. 1a, $\tau_{c}$, and
$\delta=10$, then ${d}_{V_{T}}^{\tau}(v_{4})=2$, as $v_{4}$ participates in
two $\delta$-instances of $M$. We provide a notation table in Appendix B and
all the missing proofs are deferred to Appendix E.

##  3\. Related work

Densest subgraphs in static networks. Densest-subgraph discovery (DSD) is a
widely-studied problem asking to find a subset of vertices that maximizes
_edge density_ (Gionis and Tsourakakis, 2015; Lee et al., 2010; Fang et al.,
2022; Lanciano et al., 2023). Goldberg (1984) proposed a polynomial-time
algorithm for computing the exact solution using min-cut. Since min-cut
algorithms are expensive, such an algorithm is not practical for large
networks. Charikar (2000) developed a faster greedy algorithm achieving a
$\tfrac{1}{2}$-approximation ratio. The idea is to iteratively remove the
vertex with the smallest degree, and return the vertex set that maximizes the
edge density over all vertex sets considered. Bahmani et al. (2012) proposed
methods trading accuracy for efficiency, including a
$\tfrac{1}{2(1+\xi)}$-approximation algorithm, controlled by a parameter
$\xi>0$.

Most related to TMDS are the problems of $k$-clique, or $k$-motif densest
subgraphs (Tsourakakis, 2014; Wang et al., 2020b; Tsourakakis, 2015; Fang et
al., 2019; Mitzenmacher et al., 2015; Chen et al., 2023; Sun et al., 2020b; He
et al., 2023). The $k$-clique densest-subgraph problem modifies the standard
density definition by replacing edges with the number of $k$-cliques induced
by a vertex set. This problem is $\mathbf{NP}$-hard. Tsourakakis (2014)
developed exact and approximate algorithms (extending Goldberg’s and
Charikar’s algorithm, respectively) for the $k$-clique and triangle-densest
subgraph problem ($k=3$), further studied by Wang et al. (2020b). High-order
core decomposition has been used to approximate the $k$-clique and the
$k$-motif densest-subgraph problems, where density is defined on $k$-vertex
subgraphs (Fang et al., 2019). The techniques proposed by Fang et al. (2019)
rely on exact enumeration of $k$-vertex subgraphs, which in the case of
temporal networks is impractical, especially on large data.

For the $k$-clique densest-subgraph problem, Mitzenmacher et al. (2015)
applied sparsification, which requires exhaustive enumeration of all
$k$-cliques. Sun et al. (2020b) developed convex optimization-based algorithms
and a related sampling approach requiring a subroutine that performs exact
enumeration of $k$-cliques. For TMDS, we cannot afford listing the set
$\mathcal{S}_{T}$ as such expensive procedure has exponential computational
cost in general. In our work, we develop two randomized approximation
algorithms that _avoid_ exhaustive enumeration of $\mathcal{S}_{T}$,
significantly differing from existing approaches.

Densest-subgraph discovery in temporal networks. We do not discuss methods for
DSD on temporal networks defined over snapshots of static graphs. Such a model
is used for representing more coarse-grained temporal data than the fine-
grained model we adopt, and it is less powerful (Holme and Saramäki, 2012;
Gionis et al., 2024).

Several cohesive subgraph models have been studied (Gionis et al., 2024), such
as, periodic densest subgraphs (Qin et al., 2023), bursty communities (Qin et
al., 2022), densest subgraphs across snapshots (Semertzidis et al., 2018),
correlated subgraphs (Preti et al., 2021), and subgraphs with specific core
properties (Zhong et al., 2024). Our work differs significantly from all these
definitions, as it is based on temporal motifs. Several problems have been
proposed to identify the time frames maximizing specific density scores
(Rozenshtein et al., 2019) and extensions of core-numbers to the temporal
scenario (Galimberti et al., 2020; Li et al., 2018; Oettershagen et al.,
2023a) or temporal quasi-cliques (Lin et al., 2022). Again, our problem
strongly differs from all these works we provide extensive details in Appendix
C. We also note that, for brevity, we do not discuss algorithms for _dynamic
graphs_ , i.e., static graphs where edges are added or removed over time. A
large literature exists for this model (Epasto et al., 2015; Bhattacharya et
al., 2015; Hanauer et al., 2021), which, however, differs significantly from
the one we consider.

Algorithms for temporal motifs. We briefly discuss relevant algorithms for
finding temporal motifs, as per Def. 2.1. Paranjape et al. (2017), who
introduced such a definition, developed dynamic-programming algorithms
tailored to specific $3$-edge and $2$\- or $3$-vertex temporal motifs.
Subsequently, Mackey et al. (2018) developed a backtracking algorithm to
enumerate all $\delta$-instances of an arbitrary temporal motif; the
complexity of such algorithm is $\mathcal{O}(m^{\ell})$, i.e., exponential and
not practical. Many other exact-counting algorithms exist, usually tailored to
specific classes of temporal motifs such as triangles (Pashanasangi and
Seshadhri, 2021) or small motifs (Gao et al., 2022; Cai et al., 2023). Since
exact counting is often impractical, many sampling-based algorithms have been
developed (Liu et al., 2019; Sarpe and Vandin, 2021b, a; Wang et al., 2020a;
Pu et al., 2023). In our work, when needed, we will use the state-of-the-art
randomized algorithm by Sarpe and Vandin (2021b) for estimating the motif
count of an arbitrary temporal motif, which provides
$(\varepsilon,\eta)$-approximation guarantees, i.e., it offers an unbiased
estimate $\hat{\tau}(V_{T})$ for which
$\mathbb{P}\left[|\hat{\tau}(V_{T})-\tau(V_{T})|\leq\varepsilon\tau(V_{T})\right]>1-\eta$
when the constant weighting function is considered, which we extend to
arbitrary non-negative weighting functions $\tau$.

##  4\. Randomized algorithms

We now introduce the novel randomized approximation algorithms with tight
probabilistic guarantees that we develop in ALDENTE. The algorithms in ALDENTE
will address the TMDS avoiding the expensive exhaustive enumeration of the set
$\mathcal{S}_{T}$, trough which the TMDS problem can be solved (see discussion
in Section 5).

###  4.1. ProbPeel

The main idea behind ProbPeel is to avoid exhaustive enumeration of
$\mathcal{S}_{T}$ by using _random sampling_ and peeling vertices in “batches”
according to an _estimate_ of their temporal-motif degree. ProbPeel carefully
combines highly-accurate probabilistic (1$\pm\varepsilon,\varepsilon>0$)
estimates of the temporal motif degrees of all vertices (that are obtained by
suitably leveraging existing algorithms for global temporal motif estimation
(Sarpe and Vandin, 2021b; Wang et al., 2020a)), and peels vertices in batches
at each step of such a schema, similar _non_ -approximate batch-peeling
techniques have been employed successfully in other settings (Bahmani et al.,
2012; Epasto et al., 2015; Sun et al., 2020a).

We briefly introduce some definitions. Let
$T^{\prime}=(V^{\prime},E^{\prime})\subseteq T=(V_{T},E_{T})$, and recall that
$\mathcal{S}_{T^{\prime}}=\\{S:S\text{ is a }\delta\text{-instance of }M\text{
in }T^{\prime}\\}$ is the set of $\delta$-instances from $\mathcal{S}_{T}$
computed only on the subnetwork $T^{\prime}$, where $T^{\prime}$ is _not_
required to the subnetwork induced by $V^{\prime}$. For a given vertex $v\in
V_{T}$, extending our previous notation, let
${d}_{T^{\prime}}^{\tau}(v)\mathbin{=}\sum_{S\in\mathcal{S}_{T^{\prime}}}\tau(S)$
be the temporal motif degree of vertex $v$ in the subnetwork $T^{\prime}$.
Clearly, $\sum_{v\in V_{T}}{d}_{T}^{\tau}(v)=k\tau(V_{T})$.

We assume a sampling algorithm $\mathcal{A}$, which outputs a sample
$T^{\prime}=(V^{\prime},E^{\prime})\subseteq T[W]$ of a subnetwork $T[W]$.
Given a subnetwork $T[W]\subseteq T$ we will execute the sampling algorithm
$\mathcal{A}$ to obtain $r\in\mathbb{N}$ i.i.d. subnetworks
$\mathcal{D}=\\{{T}_{1},\dots,{T}_{r}:{T}_{i}=\mathcal{A}(T[W])\subseteq
T[W],i\in[r]\\}$. We use the subnetworks in $\mathcal{D}$ to compute an
_unbiased_ estimator $\hat{d}_{W}^{\tau}(w)$ of the temporal-motif degree for
$w\in W$, and for the correct choice of $r$ it holds
$\hat{d}_{W}^{\tau}(w)\in(1\pm\varepsilon){d}_{W}^{\tau}(w)$, and combine
these estimates to obtain an estimator
$\hat{\tau}(W)\in(1\pm\varepsilon)\tau(W)$. More details on the estimators are
given in Appendix D.1.1.

Input:
$T=(V_{T},E_{T}),M,\delta\in\mathbb{R}^{+},\tau,\xi>0,\varepsilon>0,\eta\in(0,1)$.

Output: $W$.

1 $W_{1}\leftarrow V_{T}$; $i\leftarrow 1$;

2 while  _$W_{i}\neq\emptyset$_ do

3 $r_{i}\leftarrow\mathtt{GetBound}(W_{i},\varepsilon,\eta/2^{i})$;

4
$\mathcal{D}=\\{T_{1},\dots,T_{r_{i}}\\}\leftarrow\mathcal{A}^{r_{i}}(T[W_{i}])$;

5
$\hat{d}_{W_{i}}^{\tau}(w_{1}),\dots,\hat{d}_{W_{i}}^{\tau}(w_{|W_{i}|})\leftarrow\mathtt{GetEstimates}(W_{i},\mathcal{D})$;

6 $\hat{\tau}(W_{i})\leftarrow 1/k\sum_{w\in W_{i}}\hat{d}_{W_{i}}^{\tau}(w)$;

7 $L(W_{i})\leftarrow\left\\{w\in W_{i}:\hat{d}_{W_{i}}^{\tau}(w)\leq
k(1+\xi)\hat{\tau}(W_{i})/|W_{i}|\right\\}$;

8 $W_{i+1}\leftarrow W_{i}\setminus L(W_{i})$; $i\leftarrow i+1$;

9

return
_$W=\operatorname*{arg\,max}_{j=1,\dots,i}\\{\hat{\tau}(W_{j})/|W_{j}|\\}$ ;_

Algorithm 1 ProbPeel

Algorithm description. We now present ProbPeel (Algorithm 1), our
probabilistic batch-peeling algorithm. The algorithm has three parameters,
$\varepsilon>0$, $\eta\in(0,1)$ and $\xi>0$. The parameter $\varepsilon$
controls the relative $\varepsilon$-approximation ratio of $\hat{\tau}(W)$ and
$\hat{d}_{W}^{\tau}(w)$, and $\eta$ controls the failure probability of the
algorithm, i.e., the guarantees of ProbPeel hold with probability $>1-\eta$.
Last, $\xi>0$ controls the number of vertices to be peeled at each iteration,
with higher values of $\xi$ more vertices are peeled, so ProbPeel performs
less iterations, at the price of lower quality solutions (line 1).

First, ProbPeel instantiates the vertex set to be peeled (line 1). Then it
starts the main loop that ends when the vertex set $V_{T}$ becomes empty (line
1), and at each iteration $i>0$ it computes a bound $r_{i}$ ensuring that with
$r_{i}$ it holds
$\hat{d}_{W_{i}}^{\tau}(w)\in(1\pm\varepsilon){d}_{W_{i}}^{\tau}(w)$ with
probability $>1-\eta/2^{i}$ _simultaneously_ for each $w\in W_{i}$, through
the function $\mathtt{GetBound}$ (line 1). It then samples $r_{i}$ subnetworks
from $T_{[W_{i}]}$ using the sampling algorithm $\mathcal{A}$, denoted by
$\mathcal{A}^{r_{i}}(T[W_{i}])$, the samples are stored in $\mathcal{D}$ (line
1). Then it computes the estimates $\hat{d}_{W_{i}}^{\tau}(w)$ for each $w\in
W_{i}$ (line 1). The algorithm proceeds by peeling vertices in batches
according to a threshold that combines the estimator $\hat{\tau}(W_{i})$
(computed in line 1) and $\hat{d}_{W_{i}}^{\tau}(w),w\in W_{i}$ and $\xi>0$
(line 1). ProbPeel then updates the vertex set and counter for the next
iteration (line 1). Finally, the algorithm returns the vertex set maximizing
the estimated objective function $\hat{\tau}(W_{j})/|W_{j}|$ over all the
iterations $j=1,\dots,\mathcal{O}(\log_{1+\xi}(n))$ (line 1).

Building the estimator. We briefly describe how to compute the estimates of
the temporal motif degrees ${d}_{W}^{\tau}(w)$ of vertices $w\in W$ trough the
function $\mathtt{GetEstimates}$. The general schema we introduce captures
many existing estimators, i.e., (Sarpe and Vandin, 2021b; Liu et al., 2019;
Wang et al., 2020b). Invoking $\mathcal{A}$ on a subnetwork $T[W]$,
$W\subseteq V_{T}$, we get a sample
$T^{\prime}=(V^{\prime},E^{\prime})\subseteq T[W]$, therefore using such a
sample $T^{\prime}$ we compute an estimate of the degree ${d}_{W}^{\tau}(w)$,
for each $w\in W$ as

(1)
$\hat{d}_{W}^{\tau}(w,T^{\prime})=\sum\nolimits_{S\in\mathcal{S}_{{T}^{\prime}}:w\in
S}\tau(S)/p_{S},$

where $p_{S}$ is the probability of observing $S\in\mathcal{S}_{{T}^{\prime}}$
in the sampled subnetwork ${T}^{\prime}=({V}^{\prime},{E}^{\prime})$.

###### Lemma 4.1.

For any $w\in W$, the count $\hat{d}_{W}^{\tau}(w,T^{\prime})$ computed on a
sampled subnetwork $T^{\prime}\subseteq T[W]$ is an unbiased estimate of
${d}_{W}^{\tau}(w)$.

The final estimators $\hat{d}_{W}^{\tau}(w)$ for $w\in W$ are then computed as
the sample average over all the $r$ sampled subnetworks (in line 1) of Eq.
(1), that is
$\hat{d}_{W}^{\tau}(w)\mathbin{=}1/r\sum_{i=1}^{r}\hat{d}_{W}^{\tau}(w,T_{i})$
for all $w\in W$. Note also that $\hat{\tau}(W)$ (obtained in line 1) is an
unbiased estimator of $\tau(W)$.

Bounding the sample size. Algorithm 1 can employ any unbiased sampling
algorithm $\mathcal{A}:T\mapsto 2^{T}$ as subroutine (Liu et al., 2019; Wang
et al., 2020b; Sarpe and Vandin, 2021b). We used PRESTO-A (Sarpe and Vandin,
2021b) for which the authors provide bounds on the number of samples $r$ for
event “$\hat{\tau}(W_{i})\in(1\pm\varepsilon)\tau(W_{i})$” to hold with
arbitrary probability $>1-\eta$ for $\eta\in(0,1)$. In our function
$\mathtt{GetBound}$ we need a stronger result as we need
$(1\pm\varepsilon)$-approximation for _all_ temporal motif degree of vertices
$w\in W_{i}$. Hence we bound individually, for each vertex, the probability
that $\hat{d}_{W_{i}}^{\tau}(w)\notin(1\pm\varepsilon){d}_{W_{i}}^{\tau}(w)$
and combine such result with a union bound over all vertices. (more details
are in Appendix D.1.2).

Guarantees. The next result establishes the quality guarantees of ProbPeel.

###### Theorem 4.2.

With probability at least $1-\eta$, ProbPeel achieves a
$\frac{(1-\varepsilon)^{2}}{k(1+\xi)(1+\varepsilon)^{2}}$-approximation ratio
for the TMDS problem.

Note that if the parameter $\varepsilon$ is small (e.g.,
$\varepsilon\\!\approx\\!10^{-3}$), then ProbPeel outputs a solution with
approximation ratio close to $\tfrac{1}{k(1+\xi)}$. In Appendix D.1.2 we
discuss in details how to leverage existing state-of-the-art sampling
algorithms, and their guarantees, to obtain a
$(1\pm\varepsilon)$-approximation of the temporal motif degrees to be used by
ProbPeel (in line 1), where we also report all the missing details of the
functions GetBound and GetEstimates.

Time complexity. ProbPeel does not require an _exhaustive_ enumeration of all
$\delta$-instances in the network $T$. In fact, it only estimates the temporal
motif degrees of the vertices in $W_{i}$ at each iteration $i$ of the
algorithm. The running time depends on the number of samples $r_{i}$ collected
at each iteration and the time required to process each sample, which is
$\mathcal{O}(\hat{m}^{\ell})$ where $\hat{m}$ denotes the maximum number of
edges of $E_{T}$ in a time-window of length $\delta$.

Thus, the time complexity is
$\mathcal{O}\\!\left(r_{\max}\left(\hat{m}^{\ell}\log_{1+\xi}(n)+\frac{(1+\xi)n}{\xi}\right)\right)$,
where $r_{\max}\mathbin{=}\max_{i}\\{r_{i}\\}$, which depends on $\varepsilon$
and $\eta$. Such result comes from an analysis similar to the one we perform
for a baseline in Appendix F.3. Since the algorithm does not require
exhaustive enumeration of $\mathcal{S}_{T}$ we expect it to be particularly
efficient. In addition, since we only store the estimates of the various
vertices at each iteration we expect also the algorithm to be memory
efficient.

###  4.2. HybridPeel

In this section we develop a novel probabilistic hybrid-peeling algorithm,
denoted by HybridPeel, which combines the randomized batch-peeling technique
of ProbPeel (to overcome full enumeration of $\mathcal{S}_{T}$) with a more
refined peeling approach that peels vertices one at a time, to obtain higher
quality solutions (as in (Charikar, 2000)).

Algorithm description. The algorithm works as follows: (i) given temporal
network $T=(V,E)$, it starts by removing nodes in a similar fashion to
ProbPeel. That is, at each iteration it computes a
$(1\pm\varepsilon)$-approximation of the temporal motif degree of each vertex,
and vertices are removed in “batches” according to a threshold controlled by
$\xi>0$. Instead of iterating the process until the vertex set becomes empty,
the algorithm executes the randomized peeling phase for a fixed number of
iterations $J\geq 1$ provided in input. After such $J$ iterations, HybridPeel
considers the vertex set $W_{J+1}$ and its induced temporal network
$T[W_{J+1}]$. Then it enumerates all temporal motifs on $T[W_{J+1}]$
(computing $\mathcal{S}_{W_{J+1}}$) and peels $W_{J+1}$ one vertex at a time
according to the minimum temporal motif degree, storing the vertex set
maximizing the objective function $\rho(\cdot)$, among the ones observed.
Hence, this second procedure returns a vertex set $W^{\prime}$ maximizing
$\rho(\cdot)$ among the $\mathcal{O}(|W_{J+1}|-k)$ vertex sets explored, and
HybridPeel then returns
$W\mathbin{=}\operatorname*{arg\,max}\\{\hat{\tau}(W_{1})/|W_{1}|,\dots,\hat{\tau}(W_{J})/|W_{J}|,\tau(W^{\prime})/|W^{\prime}|\\}$.
The pseudocode is reported in Appendix D.2.

The design of HybridPeel is motivated by a drawback of ProbPeel: even for very
accurate estimates of temporal motif degrees it may provide a sub-optimal
solution to TMDS, since even for $\varepsilon$ close to 0, ProbPeel only
converges to the approximation ratio of $\frac{1}{k(1+\xi)}$, while the
peeling procedure we apply on $W_{J+1}$ provides denser solutions (close to
$1/k$). The intuition behind HybridPeel is that, the first $J$ iterations are
used to prune the network sufficiently, for the algorithm to maintain in
$W_{J+1}$ a dense subnetwork $W^{\prime}\subseteq W_{J+1}$ attaining at least
a $1/k$-approximation ratio. Therefore: (i) the algorithm is scalable, as it
avoids the computation of $\mathcal{S}_{T}$, and (ii) is expected to output
high-quality solutions.

Next we show the approximation ratio of HybridPeel.

###### Theorem 4.3.

With probability at least $1-\eta$, HybridPeel is a
$\frac{(1-\varepsilon)^{2}}{k(1+\xi)(1+\varepsilon)^{2}}$-approximation
algorithm for the TMDS problem when $J>1$, while for $J=1$ it achieves a
$\frac{(1-\varepsilon)^{2}}{k(1+\xi)(1+\varepsilon)}$-approximation ratio.

Time complexity. The time complexity of the algorithm can be bounded by
$\mathcal{O}({RT}_{\mathtt{ProbPeel}-J}(T)+{RT}_{\mathtt{Greedy}}(T[W_{J+1}]))$,
i.e., the sum of the runtime ($RT$) of executing ProbPeel for $J$ iterations,
and then the peeling procedure that we denote with Greedy on $T[W_{J+1}]$. The
analysis follows from ProbPeel and our analysis of a baselines in Appendix
F.2. By noting that there exists a value $\gamma>1$ such that
$|W_{J+1}|=\mathcal{O}(n^{1/\gamma})$ the complexity is bounded by
$\mathcal{O}\\!(Jr_{\max}\hat{m}^{\ell}+\gamma^{-1}k^{3}\,n^{k/\gamma}\log(n))$.
This highlights that first peeling the network with the randomized batch
peeling technique enables HybridPeel to work on a significantly small network,
over which to execute a more refined peeling algorithm, affording an exact
enumeration of temporal motif instances on $T[W_{J+1}]$, leading to an overall
scalable and practical algorithm.

Table 1. Baselines and algorithms in ALDENTE. For each algorithm we report:
its name, the approximation ratio, its parameters, the guaranteed probability
(“1” means deterministic), “Avoid Enum.”: if it avoids computing the set
$\mathcal{H}$ (and therefore $\mathcal{S}_{T}$), and its time complexity. The
first three algorithms are baselines, while the latter two algorithms are part
of ALDENTE (see Section 4).

Name | Approximation | Parameters | Probability | Avoid Enum. | Time Complexity
---|---|---|---|---|---
Exact | 1 | - | 1 | ✗ | $\mathcal{O}\left(m\hat{m}^{\ell-1}+kn^{2k}\log(n\tau(V))\right)$
Greedy | $\frac{1}{k}$ | - | 1 | ✗ | $\mathcal{O}\\!\left(m\hat{m}^{(\ell-1)}+k^{3}n^{k}\log(n)\right)$
Batch | $\frac{1}{k(1+\xi)}$ | $\xi>0$ | 1 | ✗ | $\mathcal{O}\\!\left(m\hat{m}^{(\ell-1)}+k^{3}n^{k}\log(n)\right)$
ProbPeel | $\frac{(1-\varepsilon)^{2}}{k(1+\xi)(1+\varepsilon)^{2}}$ | $\xi>0,\varepsilon,\eta\in(0,1)$ | $>1-\eta$ | ✓ | $\mathcal{O}\\!\left(r(\varepsilon,\eta)\left(\hat{m}^{\ell}\log_{1+\xi}(n)+\frac{(1+\xi)n}{\xi}\right)\right)$
HybridPeel | $\frac{(1-\varepsilon)^{2}}{k(1+\xi)(1+\varepsilon)^{2}}$ | $\xi>0,\varepsilon,\eta\in(0,1),J>0$ | $>1-\eta$ | ✓ | $\mathcal{O}\\!\left(Jr(\varepsilon,\eta)\hat{m}^{\ell}+\gamma^{-1}k^{3}\,n^{k/\gamma}\log(n)\right)$

##  5\. Temporal information impact and baselines

A natural question is if the temporal information in the temporal network $T$
is necessary, or if the directed static network _associated to $T$_ already
captures the TMDS problem formulation. Given a temporal network
$T=(V_{T},E_{T})$ the _associated static network_ of $T$ is
$G_{T}=(V_{T},E_{G})$, where $E_{G}=\\{\\{u,v\\}\mid\text{there exists
}(u,v,t)\in E_{T}\text{ or }(v,u,t)\in E_{T}\\}$. If we keep the edge
directions, a static directed network is denoted by $D_{T}$.555The static
network of a temporal network $T$ simply ignores the timestamps of $T$,
collapsing multiple temporal edges on the same static edge. For a subset of
vertices $W\subseteq V$ we denote by $G_{T}[W]$ its associated static network.

We first show that even for a very simple temporal motif, the optimal solution
on $D_{T}$ can be arbitrarily bad when evaluated on the temporal network $T$.
This highlights that Problem 1 _cannot_ be addressed by existing algorithms
for $k$-MDS on static networks or aggregations of the input temporal network
(i.e., disregarding temporal information). We then show how to embed temporal
information in a weighted set of subgraphs to solve the TMDS problem, to
obtain our baselines. Computing such a set requires _full enumeration_ of
temporal motif instances on $T$, which we recall to be extremely demanding,
especially on large temporal networks.

Temporal vs. static. We start by some definitions. For a temporal motif
$M=({K},\sigma)$, we use $G[M]$ to denote the undirected graph associated to
${K}$, i.e., $G[M]=(V_{{K}},\\{\\{u,v\\}:\text{there exists
}\allowbreak(u,v)\allowbreak\text{or }(v,u)\text{ in }E_{K}\\})$, ignoring
directions and multiple edges in $K$. We say that a temporal motif $M$ is a
_2-path_ if $M=\langle(u,v),(v,w)\rangle$, with $u\neq v\neq w$. Given a
directed static graph $D_{T}=(V_{T},E_{D})$ we define the number of _static
2-paths_ (i.e., directed paths of length 2) induced by a subset of vertices
$H\subseteq V_{T}$ as $|P_{2}(H)|$. Therefore, a static version of the TMDS
problem on temporal networks with $M$ being a 2-path, is to consider the
aggregated network of $T$ (i.e., $D_{T}$) with the goal of identifying
$H^{*}\subseteq V_{T}$ maximizing
$\rho_{2}(H)\mathbin{=}\frac{|P_{2}(H)|}{|H|}$. We refer to this problem as
S2DS (Static 2-path Densest Subnetwork).

We can show that an optimal solution to S2DS, computed on $D_{T}$, the static
network associated to $T$, can be arbitrarily bad when evaluated for TMDS on
$T$ with $M$ being a 2-path. Without loss of generality, we assume the
constant weighting function $\tau_{c}$.

###### Lemma 5.1.

Given a temporal network $T=(V_{T},E_{T})$, and its associated directed
network $D_{T}$, let $H^{*}$ be a solution to S2DS on $D_{T}$. Let $W^{*}$ on
$T$ be the optimal solution of TMDS, for a 2-path motif, with fixed
$\delta\geq 1$. Then there exists a temporal network $T$ such that
$\rho(H^{*})=0$ while $\rho(W^{*})=\mathcal{O}(n^{2})$. Furthermore, the two
solution sets $H^{*}$ and $W^{*}$ are disjoint.

Embedding temporal information. Since we cannot simply disregard temporal
information, we investigate how to compute a suitable weighted set of static
subgraphs embedding temporal information. Such a set can be used to solve the
TMDS problem by leveraging existing techniques. Given the input to TMDS, we
define $\mathcal{H}\mathbin{=}\\{H:H=(V_{H},E_{H})\subseteq G_{T},\text{ for
some }H^{\prime}\subseteq H\text{ it holds
}H^{\prime}\\!\sim\\!G[M],~{}\tau(V_{H})>0,\text{ and }|V_{H}|=k\\}$ be the
set of $k$-connected induced subgraphs ($k$-CISs) from $G_{T}$,666Symbol
“$\sim$” denotes standard graph isomorphism. where each $k$-CIS,
$H\in\mathcal{H}$, encodes a subgraph containing at least a $\delta$-instance
$S\in\mathcal{S}_{T}$ with $\tau(S)>0$, and $H$ is induced in $G_{T}$, i.e.,
has all the edges among the vertices $V_{H}$. The above conditions are ensured
by requiring the existence of $H^{\prime}\subseteq H$ such that
$H^{\prime}\mathbin{\sim}\mathbin{G}[M]$ and $\tau(V_{H})>0$, where $G[M]$ is
the undirected graph associated to the temporal motif $M$. For example,
considering the motif $M$, and the temporal network $T$ from Fig. 1, and
$\delta=10$, then the corresponding set $\mathcal{H}$ is
$\mathcal{H}=\\{(H_{1}=G_{T}[\\{v_{1},v_{2},v_{3}\\}],~{}H_{2}=G_{T}[\\{v_{2},v_{3},v_{4}\\}],~{}H_{3}=G_{T}[\\{v_{1},v_{3},v_{5}\\}],~{}H_{4}=G_{T}[\\{v_{3},v_{4},v_{5}\\}]\\}$.

Next, we need to define the weight of each subgraph $H=(V_{H},E_{H})$ in
$\mathcal{H}$. This is done by
$\tau(V_{H})=\sum_{S\in\mathcal{S}_{V_{H}}}\tau(S)$, i.e., the weight of the
subgraph $H$ is the sum of the weights of the $\delta$-instances that occur
among the nodes of $V_{H}$ in $T$. As an example, consider
$H_{1}=(V_{H_{1}}=\\{v_{1},v_{2},v_{3}\\},\\{\\{v_{1},v_{2}\\},\\{v_{2},v_{3}\\},$
$\\{v_{3},v_{1}\\}\\})\in\mathcal{H}$ from Fig. 1, then $\tau(V_{H_{1}})=2$
under weight $\tau_{c}$, and $\delta=10$, as there are two $\delta$-instances
among such nodes. Note that such a construction is in accordance with Lemma
5.1, as to build, and weight the set $\mathcal{H}$ we are exploiting full
information about the temporal motif $\delta$-instances of $M$ in $T$. In
Section 6.1 we provide a summary on how to leverage the set $\mathcal{H}$ to
adapt existing techniques for high-order subgraph discovery to solve TMDS,
while a more detailed description can be found in Appendix F. Such algorithms
will be used as baselines for comparison against ALDENTE in our experimental
evaluation. All resulting baselines, and the algorithms in ALDENTE that we
developed are finally summarized in Table 1.

##  6\. Experimental evaluation

In this section we evaluate the algorithms in ALDENTE against the baselines.
We describe the experimental setup in Section 6.2, and we compare the solution
quality, and runtime of all the algorithms in Section 6.3. Finally, in Section
6.4 we conduct a case study on a real-world transaction network from the Venmo
platform to support the usefulness of solving the TMDS problem. We defer to
appendices for additional results, e.g., on parameter sensitivity (in Section
H.2), memory usage (in Section H.4) and results under decaying weighting
function $\tau_{d}$ (in Section H.3).

###  6.1. Baseline overview

We give a brief, description of our baselines, that leverage the construction
of the set $\mathcal{H}$ (as from Section 5) and that are based on known ideas
in the field, see and Appendix F for more details.

Exact: Exact algorithm embedding the set $\mathcal{H}$ is a properly weighted
flow network, adapting ideas from (Goldberg, 1984; Mitzenmacher et al., 2015;
Fang et al., 2019). It computes multiple min-cut solutions on the flow
network, the algorithm identifies an optimal solution to the TMDS problem.

Greedy: A $1/k$-approximation greedy algorithm that extend the ideas in
(Charikar, 2000; Fang et al., 2019). The algorithm performs $\mathcal{O}(n-k)$
iterations where at each iteration a vertex with minimum temporal motif degree
is removed and the set $\mathcal{H}$ is updated accordingly. The algorithm
returns the vertex set with maximum density observed.

Batch: A $1/(k(1+\xi)),\xi>0$ greedy approximation algorithm extending ideas
from (Bahmani et al., 2012; Epasto et al., 2015; Tsourakakis, 2015). At each
step the algorithm removes vertices with small temporal motif degree in
“batches” and updates the set $\mathcal{H}$ returning the maximum density
vertex set observed, the overall number of iterations is bounded by
$\mathcal{O}(\log n/\xi)$.

All such baselines require the computation of the set $\mathcal{H}$, and
therefore $\mathcal{S}_{T}$.777This holds for most of other existing
techniques even based on sampling, see Section 3. Unfortunately, this is
extremely inefficient and does not scale on large data, as we will show next.

Table 2. Networks used in our experiments. $n$: vertices, $m$: temporal edges,
$|E_{G}|$: edges in the undirected static network, time-interval length
$\delta$: value used for counting $\delta$-instances.

| Network | $n$ | $m$ | $|E_{G}|$ | Precision | Timespan | $\delta$
---|---|---|---|---|---|---|---
Medium | Sms | 44 K | 545 K | 52 K | sec | 338 (days) | 172.8 K
Facebook | 45.8 K | 856 K | 183 K | sec | 1561 (days) | 86.4 K
Askubuntu | 157 K | 727 K | 455 K | sec | 2614 (days) | 172.8 K
Wikitalk | 1 100 K | 6 100 K | 2 800 K | sec | 2277 (days) | 43.2 K
Large | Stackoverflow | 2.6 M | 47.9 M | 28.1 M | sec | 2774 (days) | 172.8 K
Bitcoin | 48.1 M | 113 M | 84.3 M | sec | 2585 (days) | 7.2 K
Reddit | 8.4 M | 636 M | 435.3 M | sec | 3687 (days) | 14.4 K
EquinixChicago | 11.2 M | 2 300 M | 66.8 M |  $\mu$-sec | 62.0 (mins) | 50 K
| Venmo | 19.1 K | 131 K | 18.5 K | sec | 2091 (days) | -

Figure 2. Temporal motifs ($\mathsf{M}_{i},i\in[10]$) used in the experimental
evaluation. Motifs with blue vertices are not used on EquinixChicago since
this network is bipartite. For each motif $t_{i},i=1,\ldots$ denotes the
ordering of its edges in $\sigma$.

---
(a)  (b)

Figure 3. For each configuration we report (top): the quality of the solution
compared to the best empirical solution (i.e., $\hat{\mathrm{OPT}}$), and
(bottom): the average running times to achieve such solution.

###  6.2. Setup

Implementation details and hardware. All the algorithms are implemented in
C++20 and compiled under Ubuntu 20.04 with gcc 9.4.0 with optimization flags.
The experiments are executed sequentially on a 72-core Intel Xeon Gold 5520
@2.2 GHz machine with 1008 GB of RAM memory available. For Exact, we use the
algorithm by Boykov and Kolmogorov (2004) to compute the $(s,z)$-min cut on
the flow network. For the implementation of the min-heap we use the data
structures provided by the Boost library.888https://www.boost.org/ We use the
algorithm of Mackey et al. (2018) for exact enumeration of temporal motif
$\delta$-instances. We use PRESTO-A (Sarpe and Vandin, 2021b), with parameter
$q=1.25$, as sampling algorithm in ProbPeel and HybridPeel. At each iteration
of ProbPeel (and HybridPeel) we set $r_{i}=r$, (i.e., a fixed value for all
iterations) and we set this parameter accordingly for each dataset; we discuss
the sensitivity of the solution to parameter $r$ in Section H.2. We consider
as weighting function $\tau$ the constant function $\tau_{c}$. Our code is
available online.999https://github.com/iliesarpe/ALDENTE.

Datasets and time-interval length. The datasets considered in this work span
medium and large sizes and are reported in Table 2. For each dataset we set
$\delta$ to be some multiple of the respecting time unit (e.g., for datasets
with precision in seconds setting $\delta=7.2$K corresponds to two hours). We
also select a value of $\delta$ that is consistent with previous studies and
application scenarios (Paranjape et al., 2017; Liu and Sariyüce, 2023;
Pashanasangi and Seshadhri, 2021; Liu et al., 2024), and large enough to be
computationally challenging. See more details on datasets in Appendix G.

Temporal motifs. The temporal motifs we use are good representative of a
general input to TMDS in most applications, and are reported in Fig. 2. They
represent different topologies, e.g., triangles, squares and more complicated
patterns, spanning different values of $k$ and $\ell$, and the largest
temporal motifs correspond to particularly challenging inputs.

###  6.3. Solution quality and runtime

We now compare the runtime and quality of the solution reported by the
algorithms in ALDENTE (ProbPeel, and HybridPeel) against the baselines (Exact,
Greedy, and Batch).

Setup and metrics. For each configuration (dataset, motif, value of $\delta$)
we run each algorithm five times with a time limit of three hours and maximum
RAM of 150 GB on all datasets but EquinixChicago, on which we set the memory
limit to 200 GB. For each algorithm we compute the average running time over
the five runs. To assess the quality of the solution of the randomized
algorithms, we compute the actual value of the solution in the original
temporal network on the returned vertex set. For each configuration over all
the algorithms that terminate we compute $\hat{\mathrm{OPT}}$,101010Such value
is guaranteed to be the actual optimum $\mathrm{OPT}$ only when Exact
terminates. i.e., the best empirical solution obtained across all algorithms,
and we use this value as reference for comparison of the different algorithms.
For all the deterministic algorithms we show the approximation factor as
$\frac{\tau(W)/|W|}{\hat{\mathrm{OPT}}}$, where $W$ is the solution returned
by a given algorithm; for ProbPeel and HybridPeel we show the average
approximation factor over the five runs, and we also report the standard
deviation.

We set $\xi=0.3$ for Batch over all experiments we performed, as it provides
sufficiently good solutions in most cases (see Section H.2 for a detailed
empirical evaluation of such parameter), and use the same values of $\xi$ for
ProbPeel and HybridPeel. For HybridPeel we set $J=3$ on large datasets, and
$J=2$ otherwise. When an algorithm does not terminate within the time limit we
set its time to three hours, and its approximation factor to 0. Since our
focus is on scalability we place particular emphasis on _large_ datasets, so
we defer results on medium-size datasets to Appendix H.1 as they follow
similar trends to the ones we will discuss. We also discuss results concerning
memory usage in App. H.4.

Results. The results are reported in Fig. 3. Concerning the runtime, we
observe different trends on the various datasets. First on Stackoverflow, most
of the motifs require a small runtime, of few hundreds of seconds, to be
counted (even by Exact), and on such motifs most algorithms achieve a
comparable runtime. While on some hard motifs, our proposed randomized
algorithms achieve a significant speed-up of more than $\times 4$ and up to
$\times 9$ over the baselines (e.g., on motifs $\mathsf{M}_{1}$ and
$\mathsf{M}_{2}$). On Bitcoin we observe that the runtime for counting most
motifs is prohibitive, and Exact is not able to complete the execution on any
motif on such dataset. Remarkably, our proposed randomized algorithms achieve
a consistent speed-up of at least $\times 3$ up to $\times 8$ over Greedy and
Batch, and more importantly our algorithms are able to complete their
execution even when the baselines do not scale their computation (e.g., motifs
$\mathsf{M}_{1}$ and $\mathsf{M}_{2}$). The scalability aspect becomes more
clear on the biggest datasets that we considered, in fact on Reddit, despite
of being consistently more efficient than the baselines, our HybridPeel is the
only one that is able to complete its execution on $\mathsf{M}_{10}$ over all
techniques considered. Finally, on EquinixChicago (with more than two billions
of temporal edges), our randomized algorithms (ProbPeel and HybridPeel) are
the only ones that terminate their execution in a small amount of time. We
observe that ProbPeel is significantly more efficient than HybridPeel, at the
expense of a slightly less accurate solution, which we will discuss next. On
some of the configurations all algorithms do not terminate, this is because
some of the motifs are extremely challenging, therefore the timelimit we set
is too strict as a constraint even for randomized algorithms. Overall these
experiments suggest that our randomized algorithms successfully enable the
discovery of temporal motif densest subnetworks on large temporal networks.
This closely matches our theoretical insights, capturing the superior
efficiency and scalability of our randomized algorithms against baselines.

Concerning the solution quality we observe similar trends on most datasets.
Batch provides solutions with smaller density than Greedy, and ProbPeel
closely matches Batch’s results (as captured by our analysis). Greedy is the
deterministic approximation algorithm that mostly often provides the solution
with highest density when it terminates, and our HybridPeel closely matches
such results, so our HybridPeel results accurate, scalable and efficient (as
it is consistently faster than Greedy). Interestingly on the EquinixChicago
dataset, where only our proposed randomized algorithms are able to terminate
in less than three hours (ProbPeel takes few hundreds of seconds), the
difference in the quality of the solutions provided by ProbPeel and HybridPeel
is not significantly large, suggesting that on massive data ProbPeel may be a
good candidate to obtain high-quality solutions in a very short amount of
time.

Summary. To summarize, our experiments show that techniques based on existing
ideas do not scale on challenging motifs and large datasets for TMDS. In
contrast, our proposed algorithms in ALDENTE provide high-quality solutions in
a short amount of time and scale their computation on large datasets, enabling
the practical discovery of temporal motif dense subnetworks.

###  6.4. Case study

Recently, Liu et al. (2023) released a dataset containing a small number of
transactions from the Venmo money-transfer platform, where each transaction is
accompanied by a message. The corresponding temporal network $T=(V_{T},E_{T})$
is as follows: each temporal edge is a tuple $(u,v,t,\phi,\gamma)\in E_{T}$
where $(u,v,t)$ is the temporal edge as considered up to now and $\phi,\gamma$
are metadata: $\phi\in\\{0,1\\}$ denotes if $(u,v)$ are friends in the social
network and $\gamma$ is a text message. Since the dataset is very small (see
Table 2), we computed _exact solutions_ to Problem 1. We investigated the
following question.

Q: What insights about the Venmo platform are captured by optimal solutions to
the TMDS problem according to a temporal motif $M$, and what subnetworks are
captured by varying $\delta\in\mathbb{R}^{+}$?

To answer Q we select motif $\mathsf{M}_{5}$ in Fig. 2, a temporal star with
four temporal edges, corresponding to finding groups of users (i.e., the
vertex at the center of $\mathsf{M}_{5}$) sending many transactions to their
neighbors (i.e., the vertices with no out-edges in $\mathsf{M}_{5}$) in a
time-scale controlled by $\delta\in\mathbb{R}^{+}$. In addition to
$\mathsf{M}_{5}$, we provide as input to TMDS the constant weighting function
$\tau_{c}$ and $\delta_{1}=7\,200$ (i.e., 2-hours), to capture short-time
scale patterns.

The optimal solution $T[W^{*}_{\delta_{1}}]$ has 14 vertices, and we report
its directed static network and its temporal support in Fig. 4 (Left).
Interestingly, this is a star shaped network, with only the central vertex
($v_{1}$) exchanging money with all the other vertices (not reciprocated), and
vertices are not friends. The message associated to each transaction is
identical for all transactions: _“Sorry! We’re already sold out for tonight!
Feel free to join us this even in the regular line and pay cover when you get
there. Thanks!”_. Even more interestingly, all events occur really close in
time (see Fig. 4 (Left)). In fact, this corresponds to a _bursty event_ with
merchant $v_{1}$ overbooking for a specific event, which is identified by the
combination of $\mathsf{M}_{5}$ and small $\delta\in\mathbb{R}^{+}$. We also
observe that such a subnetwork _cannot be captured by the existing
formulations_ for dense temporal subnetworks (see Section 3) as both
$T[W^{*}_{\delta_{1}}]$ and its directed static network have very _small edge-
density_ , i.e., $13/14<1$.

We then consider $\mathsf{M}_{5}$ but analyze a much larger time-scale, that
is we solve TMDS with $\delta_{2}=172\,800$. Under this settings of parameters
we expect the optimal solution to contain instances of $\mathsf{M}_{5}$ with a
longer duration (accounting for more historical user activities). The optimal
subnetwork has 16 vertices and it is shown again in Fig. 4 (Right). As
expected the temporal support of such subnetwork is significantly long
(spanning from Oct. 2018 to Feb. 2021). The messages over the transactions of
such subnetwork are usually related to food, theatre and social activities,
denoting that users share similar interests. But we also identify transactions
that are likely related to sport gambling. Such suspicious transactions report
terms such as _“bracket season”_ or emojis of basketballs (in fact,
$\mathsf{M}_{5}$ captures such patterns as once a user loses a gamble with its
friends, it usually sends the money using a pattern similar to
$\mathsf{M}_{5}$).111111 An histogram of the words associated to the
transactions is in Fig. 12.  Our findings also support the insights by Liu et
al. (2023), who use temporal motifs to identify poker gamblers on Venmo.

In summary, by solving the TMDS problem for temporal motifs of interest and
different values of the time-window $\delta$ we can gain precious insights on
the network being analyzed not captured otherwise by previous formulations.

|
---|---
Figure 4. Directed static network of $T[W^{*}_{\delta}]$ according to
different values of $\delta$ on $\mathsf{M}_{5}$, we color edges according to
the number temporal edges that map on each static edge. Below each static
network we report the temporal support of $T[W^{*}_{\delta}]$, i.e., we place
a bar in correspondence of the timings of the events in $T[W_{\delta}^{*}]$
over the timespan of observation of the network. (Left): $\delta_{1}=7\,200$.
(Right): $\delta_{2}=172\,800$.

##  7\. Conclusions

We introduced a new problem, requiring to identify the temporal motif densest
subnetwork (TMDS) of a large temporal network. We developed two novel
algorithms based on randomized sampling, for which we proved a probabilistic
approximation ratio and show experimentally that they are efficient and
scalable over large data. The techniques developed in this work may be useful
in other problems, such as the $k$-clique problem (Tsourakakis, 2015;
Mitzenmacher et al., 2015; Fang et al., 2019) given the availability of many
sampling algorithms with tight guarantees for estimating $k$-clique counts
(Jain and Seshadhri, 2017; Bressan et al., 2021).

There are many possible directions for future work, such as improving the
theoretical guarantees offered by our randomized algorithm through motif-
dependent approximation ratios, and understanding if randomization can be
coupled with recent ideas in the field of densest-subgraph discovery, such as
techniques in (Boob et al., 2020; Chekuri et al., 2022).

###### Acknowledgements.

We thank Matteo Ceccarello for helpful comments on an earlier version of the
current work. This work is supported, in part, by MUR of Italy, under project
PRIN n. 2022TS4Y3N “EXPAND: scalable algorithms for EXPloratory Analyses of
heterogeneous and dynamic Networked Data”, and project “National Centre for
HPC, Big Data and Quantum Computing” (CN00000013). This work is also supported
by the ERC Advanced Grant REBOUND (834862), the EC H2020 RIA project
SoBigData++ (871042), and the Wallenberg AI, Autonomous Systems and Software
Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

## References

  * (1)
  * Ahmad et al. (2021) Walid Ahmad, Mason A. Porter, and Mariano Beguerisse-Diaz. 2021\.  Tie-Decay Networks in Continuous Time and Eigenvector-Based Centralities.  _IEEE Transactions on Network Science and Engineering_ 8, 2 (April 2021), 1759–1771.  https://doi.org/10.1109/tnse.2021.3071429
  * Ahmed et al. (2021) Nesreen K. Ahmed, Nick Duffield, and Ryan A. Rossi. 2021\.  Online Sampling of Temporal Networks.  _ACM Transactions on Knowledge Discovery from Data_ 15, 4 (April 2021), 1–27.  https://doi.org/10.1145/3442202
  * Arnold et al. (2024) Naomi A. Arnold, Peijie Zhong, Cheick Tidiane Ba, Ben Steer, Raul Mondragon, Felix Cuadrado, Renaud Lambiotte, and Richard G. Clegg. 2024.  Insights and caveats from mining local and global temporal motifs in cryptocurrency transaction networks.  https://doi.org/10.48550/ARXIV.2402.09272
  * Bahmani et al. (2012) Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. 2012\.  Densest Subgraph in Streaming and MapReduce.  _Proceedings of the VLDB Endowment (PVLDB) Vol. 5, No. 5, pp. 454-465_ (2012).  arXiv:1201.6567 [cs.DB]
  * Belth et al. (2020) Caleb Belth, Xinyi Zheng, and Danai Koutra. 2020.  Mining Persistent Activity in Continually Evolving Networks. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. ACM.  https://doi.org/10.1145/3394486.3403136
  * Bhattacharya et al. (2015) Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. 2015.  Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. In _Proceedings of the forty-seventh annual ACM symposium on Theory of Computing_ (2015-06). ACM.  https://doi.org/10.1145/2746539.2746592
  * Boginski et al. (2003) Vladimir Boginski, Sergiy Butenko, and Panos M. Pardalos. 2003\.  On Structural Properties of the Market Graph.  In _Innovations in Financial and Economic Networks_. Edward Elgar Publishing, 29–45.  https://doi.org/10.4337/9781035304998.00010
  * Boob et al. (2020) Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. 2020.  Flowless: Extracting Densest Subgraphs Without Flow Computations. In _Proceedings of The Web Conference 2020_. ACM.  https://doi.org/10.1145/3366423.3380140
  * Boykov and Kolmogorov (2004) Y. Boykov and V. Kolmogorov. 2004.  An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 26, 9 (sep 2004), 1124–1137.  https://doi.org/10.1109/tpami.2004.60
  * Bressan et al. (2021) Marco Bressan, Stefano Leucci, and Alessandro Panconesi. 2021\.  Faster Motif Counting via Succinct Color Coding and Adaptive Sampling.  _ACM Transactions on Knowledge Discovery from Data_ 15, 6 (may 2021), 1–27.  https://doi.org/10.1145/3447397
  * Cai et al. (2023) Xinwei Cai, Xiangyu Ke, Kai Wang, Lu Chen, Tianming Zhang, Qing Liu, and Yunjun Gao. 2023.  Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs.  https://doi.org/10.48550/ARXIV.2306.00893
  * Charikar (2000) Moses Charikar. 2000\.  Greedy Approximation Algorithms for Finding Dense Components in a Graph.  In _Approximation Algorithms for Combinatorial Optimization_. Springer Berlin Heidelberg, 84–95.  https://doi.org/10.1007/3-540-44436-x_10
  * Chekuri et al. (2022) Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. 2022\.  Densest Subgraph: Supermodularity, Iterative Peeling, and Flow.  In _Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_. Society for Industrial and Applied Mathematics, 1531–1555.  https://doi.org/10.1137/1.9781611977073.64
  * Chen et al. (2023) Tianyi Chen, Brian Matejek, Michael Mitzenmacher, and Charalampos E. Tsourakakis. 2023\.  Algorithmic Tools for Understanding the Motif Structure of Networks.  In _Machine Learning and Knowledge Discovery in Databases_. Springer International Publishing, 3–19.  https://doi.org/10.1007/978-3-031-26390-3_1
  * Chen and Tsourakakis (2022) Tianyi Chen and Charalampos Tsourakakis. 2022.  AntiBenford Subgraphs: Unsupervised Anomaly Detection in Financial Networks. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. ACM.  https://doi.org/10.1145/3534678.3539100
  * Dorogovtsev and Mendes (2003) S.N. Dorogovtsev and J.F.F. Mendes. 2003.  _Evolution of Networks_.  Oxford University Press.  https://doi.org/10.1093/acprof:oso/9780198515906.001.0001
  * Epasto et al. (2015) Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio. 2015\.  Efficient Densest Subgraph Computation in Evolving Graphs. In _Proceedings of the 24th International Conference on World Wide Web_ (2015-05). International World Wide Web Conferences Steering Committee.  https://doi.org/10.1145/2736277.2741638
  * Fang et al. (2022) Yixiang Fang, Wensheng Luo, and Chenhao Ma. 2022.  Densest subgraph discovery on large graphs.  _Proceedings of the VLDB Endowment_ 15, 12 (2022), 3766–3769.  https://doi.org/10.14778/3554821.3554895
  * Fang et al. (2019) Yixiang Fang, Kaiqiang Yu, Reynold Cheng, Laks V. S. Lakshmanan, and Xuemin Lin. 2019\.  Efficient algorithms for densest subgraph discovery.  _Proceedings of the VLDB Endowment_ 12, 11 (2019), 1719–1732.  https://doi.org/10.14778/3342263.3342645
  * Fazzone et al. (2022) Adriano Fazzone, Tommaso Lanciano, Riccardo Denni, Charalampos E. Tsourakakis, and Francesco Bonchi. 2022\.  Discovering Polarization Niches via Dense Subgraphs with Attractors and Repulsers.  _Proceedings of the VLDB Endowment_ 15, 13 (sep 2022), 3883–3896.  https://doi.org/10.14778/3565838.3565843
  * Freeman (2004) Linton C. Freeman. 2004\.  _The development of social network analysis_.  Empirical Press. 205 pages.
  * Galimberti et al. (2020) Edoardo Galimberti, Martino Ciaperoni, Alain Barrat, Francesco Bonchi, Ciro Cattuto, and Francesco Gullo. 2020.  Span-core Decomposition for Temporal Networks.  _ACM Transactions on Knowledge Discovery from Data_ 15, 1 (2020), 1–44.  https://doi.org/10.1145/3418226
  * Gao et al. (2022) Zhongqiang Gao, Chuanqi Cheng, Yanwei Yu, Lei Cao, Chao Huang, and Junyu Dong. 2022\.  Scalable Motif Counting for Large-scale Temporal Graphs. In _2022 IEEE 38th International Conference on Data Engineering (ICDE)_ (2022-05). IEEE.  https://doi.org/10.1109/icde53745.2022.00244
  * Gionis et al. (2024) Aristides Gionis, Lutz Oettershagen, and Ilie Sarpe. 2024\.  Mining Temporal Networks. In _Companion Proceedings of the ACM on Web Conference 2024_ _(WWW ’24)_. ACM.  https://doi.org/10.1145/3589335.3641245
  * Gionis and Tsourakakis (2015) Aristides Gionis and Charalampos E. Tsourakakis. 2015\.  Dense Subgraph Discovery. In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (2015-08). ACM.  https://doi.org/10.1145/2783258.2789987
  * Goldberg (1984) A. V. Goldberg. 1984\.  _Finding a Maximum Density Subgraph_.  Technical Report. EECS Department, University of California, Berkeley.  http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5956.html
  * Hanauer et al. (2021) Kathrin Hanauer, Monika Henzinger, and Christian Schulz. 2021\.  Recent Advances in Fully Dynamic Graph Algorithms.  _arXiv_ (2021).  arXiv:2102.11169 [cs.DS]
  * He et al. (2023) Yizhang He, Kai Wang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2023.  Scaling Up k-Clique Densest Subgraph Detection.  _Proceedings of the ACM on Management of Data_ 1, 1 (May 2023), 1–26.  https://doi.org/10.1145/3588923
  * Henry et al. (2007) Nathalie Henry, Jean-Daniel Fekete, and Michael J. McGuffin. 2007.  NodeTrix: a Hybrid Visualization of Social Networks.  _IEEE Transactions on Visualization and Computer Graphics_ 13, 6 (nov 2007), 1302–1309.  https://doi.org/10.1109/tvcg.2007.70582
  * Holme and Saramäki (2019) Petter Holme and Jari Saramäki (Eds.). 2019.  _Temporal Network Theory_.  Springer International Publishing, Cham.  https://doi.org/10.1007/978-3-030-23495-9
  * Holme and Saramäki (2012) Petter Holme and Jari Saramäki. 2012.  Temporal networks.  _Physics Reports_ 519, 3 (2012), 97–125.  https://doi.org/10.1016/j.physrep.2012.03.001
  * Huebsch et al. (2003) Ryan Huebsch, Joseph M. Hellerstein, Nick Lanham, Boon Thau Loo, Scott Shenker, and Ion Stoica. 2003\.  Querying the Internet with PIER.  In _Proceedings 2003 VLDB Conference_. Elsevier, 321–332.  https://doi.org/10.1016/b978-012722442-8/50036-7
  * Jain and Seshadhri (2017) Shweta Jain and C. Seshadhri. 2017.  A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem. In _Proceedings of the 26th International Conference on World Wide Web_. International World Wide Web Conferences Steering Committee.  https://doi.org/10.1145/3038912.3052636
  * Kovanen et al. (2011) Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. 2011.  Temporal motifs in time-dependent networks.  _J. Stat. Mech. (2011) P11005_ (2011).  https://doi.org/10.1088/1742-5468/2011/11/P11005 arXiv:1107.5646 [physics.data-an]
  * Lambiotte et al. (2013) Renaud Lambiotte, Lionel Tabourier, and Jean-Charles Delvenne. 2013\.  Burstiness and spreading on temporal networks.  _The European Physical Journal B_ 86, 7 (jul 2013).  https://doi.org/10.1140/epjb/e2013-40456-9
  * Lanciano et al. (2023) Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. 2023.  A Survey on the Densest Subgraph Problem and its Variants.  (March 2023).  arXiv:2303.14467 [cs.DS]
  * Lee et al. (2012) Jinsoo Lee, Wook-Shin Han, Romans Kasperovics, and Jeong-Hoon Lee. 2012.  An in-depth comparison of subgraph isomorphism algorithms in graph databases.  _Proceedings of the VLDB Endowment_ 6, 2 (dec 2012), 133–144.  https://doi.org/10.14778/2535568.2448946
  * Lee et al. (2010) Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. 2010\.  A Survey of Algorithms for Dense Subgraph Discovery.  In _Managing and Mining Graph Data_. Springer US, 303–336.  https://doi.org/10.1007/978-1-4419-6045-0_10
  * Lei et al. (2020) Da Lei, Xuewu Chen, Long Cheng, Lin Zhang, Satish V. Ukkusuri, and Frank Witlox. 2020\.  Inferring temporal motifs for travel pattern analysis using large scale smart card data.  _Transportation Research Part C: Emerging Technologies_ 120 (nov 2020), 102810.  https://doi.org/10.1016/j.trc.2020.102810
  * Li et al. (2018) Rong-Hua Li, Jiao Su, Lu Qin, Jeffrey Xu Yu, and Qiangqiang Dai. 2018.  Persistent Community Search in Temporal Networks. In _2018 IEEE 34th International Conference on Data Engineering (ICDE)_. IEEE.  https://doi.org/10.1109/icde.2018.00077
  * Lin et al. (2022) Longlong Lin, Pingpeng Yuan, Rong-Hua Li, Jifei Wang, Ling Liu, and Hai Jin. 2022\.  Mining Stable Quasi-Cliques on Temporal Networks.  _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ 52, 6 (jun 2022), 3731–3745.  https://doi.org/10.1109/tsmc.2021.3071721
  * Liu et al. (2024) Jieli Liu, Jinze Chen, Jiajing Wu, Zhiying Wu, Junyuan Fang, and Zibin Zheng. 2024\.  Fishing for Fraudsters: Uncovering Ethereum Phishing Gangs With Blockchain Data.  _IEEE Transactions on Information Forensics and Security_ 19 (2024), 3038–3050.  https://doi.org/10.1109/tifs.2024.3359000
  * Liu et al. (2023) Penghang Liu, Rupam Acharyya, Robert E. Tillman, Shunya Kimura, Naoki Masuda, and Ahmet Erdem Sarıyüce. 2023.  Temporal Motifs for Financial Networks: A Study on Mercari, JPMC, and Venmo Platforms.  _arXiv_ (2023).  arXiv:2301.07791 [cs.SI]
  * Liu et al. (2019) Paul Liu, Austin R. Benson, and Moses Charikar. 2019\.  Sampling Methods for Counting Temporal Motifs. In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining - WSDM ’19_ (Melbourne VIC, Australia, 2019). ACM Press, 294–302.  https://doi.org/10.1145/3289600.3290988
  * Liu et al. (2021) Penghang Liu, Valerio Guarrasi, and A. Erdem Sariyuce. 2021\.  Temporal Network Motifs: Models, Limitations, Evaluation.  _IEEE Transactions on Knowledge and Data Engineering_ (2021), 1–1.  https://doi.org/10.1109/tkde.2021.3077495
  * Liu and Sariyüce (2023) Penghang Liu and Ahmet Erdem Sariyüce. 2023.  Using Motif Transitions for Temporal Graph Generation. In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. ACM.  https://doi.org/10.1145/3580305.3599540
  * Mackey et al. (2018) Patrick Mackey, Katherine Porterfield, Erin Fitzhenry, Sutanay Choudhury, and George Chin. 2018\.  A Chronological Edge-Driven Approach to Temporal Subgraph Isomorphism. In _2018 IEEE International Conference on Big Data (Big Data)_ (2018-12). IEEE.  https://doi.org/10.1109/bigdata.2018.8622100
  * Masuda and Lambiotte (2016) Naoki Masuda and Renaud Lambiotte. 2016.  _A Guide to Temporal Networks_.  WORLD SCIENTIFIC (EUROPE).  https://doi.org/10.1142/q0033
  * Mitzenmacher et al. (2015) Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos Tsourakakis, and Shen Chen Xu. 2015.  Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling. In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (2015-08). ACM.  https://doi.org/10.1145/2783258.2783385
  * Oettershagen et al. (2023a) Lutz Oettershagen, Athanasios L. Konstantinidis, and Giuseppe F. Italiano. 2023a.  Temporal Network Core Decomposition and Community Search.  https://doi.org/10.48550/ARXIV.2309.11843
  * Oettershagen et al. (2023b) Lutz Oettershagen, Nils M. Kriege, and Petra Mutzel. 2023b.  A Higher-Order Temporal H-Index for Evolving Networks. In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. ACM.  https://doi.org/10.1145/3580305.3599242
  * Oettershagen and Mutzel (2020) Lutz Oettershagen and Petra Mutzel. 2020.  Efficient Top-k Temporal Closeness Calculation in Temporal Networks. In _2020 IEEE International Conference on Data Mining (ICDM)_. IEEE.  https://doi.org/10.1109/icdm50108.2020.00049
  * Paranjape et al. (2017) Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. 2017\.  Motifs in Temporal Networks.  _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_ (2017).  https://doi.org/10.1145/3018661.3018731 arXiv:1612.09259 [cs.SI]
  * Pashanasangi and Seshadhri (2021) Noujan Pashanasangi and C. Seshadhri. 2021.  Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_ (2021-08). ACM.  https://doi.org/10.1145/3447548.3467374
  * Preti et al. (2021) Giulia Preti, Polina Rozenshtein, Aristides Gionis, and Yannis Velegrakis. 2021.  Discovering Dense Correlated Subgraphs in Dynamic Networks.  In _Advances in Knowledge Discovery and Data Mining_. Springer International Publishing, 395–407.  https://doi.org/10.1007/978-3-030-75762-5_32
  * Pu et al. (2023) Jiaxi Pu, Yanhao Wang, Yuchen Li, and Xuan Zhou. 2023\.  Sampling Algorithms for Butterfly Counting on Temporal Bipartite Graphs.  https://doi.org/10.48550/ARXIV.2310.11886
  * Qin et al. (2023) Hongchao Qin, Rong-Hua Li, Ye Yuan, Yongheng Dai, and Guoren Wang. 2023.  Densest Periodic Subgraph Mining on Large Temporal Graphs.  _IEEE Transactions on Knowledge and Data Engineering_ (2023), 1–14.  https://doi.org/10.1109/tkde.2022.3233788
  * Qin et al. (2022) Hongchao Qin, Rong-Hua Li, Ye Yuan, Guoren Wang, Lu Qin, and Zhiwei Zhang. 2022\.  Mining Bursting Core in Large Temporal Graphs.  _Proceedings of the VLDB Endowment_ 15, 13 (2022), 3911–3923.  https://doi.org/10.14778/3565838.3565845
  * Rozenshtein et al. (2019) Polina Rozenshtein, Francesco Bonchi, Aristides Gionis, Mauro Sozio, and Nikolaj Tatti. 2019\.  Finding events in temporal networks: segmentation meets densest subgraph discovery.  _Knowledge and Information Systems_ 62, 4 (2019), 1611–1639.  https://doi.org/10.1007/s10115-019-01403-9
  * Santoro and Sarpe (2022) Diego Santoro and Ilie Sarpe. 2022.  ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks. In _Proceedings of the ACM Web Conference 2022_. ACM.  https://doi.org/10.1145/3485447.3512204
  * Sariyuce et al. (2015) Ahmet Erdem Sariyuce, C. Seshadhri, Ali Pinar, and Umit V. Catalyurek. 2015.  Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions. In _Proceedings of the 24th International Conference on World Wide Web_. International World Wide Web Conferences Steering Committee.  https://doi.org/10.1145/2736277.2741640
  * Sarpe and Vandin (2021a) Ilie Sarpe and Fabio Vandin. 2021a.  odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_ (2021-10). ACM.  https://doi.org/10.1145/3459637.3482459
  * Sarpe and Vandin (2021b) Ilie Sarpe and Fabio Vandin. 2021b.  PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts.  In _Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)_. Society for Industrial and Applied Mathematics, 145–153.  https://doi.org/10.1137/1.9781611976700.17
  * Semertzidis et al. (2018) Konstantinos Semertzidis, Evaggelia Pitoura, Evimaria Terzi, and Panayiotis Tsaparas. 2018.  Finding lasting dense subgraphs.  _Data Mining and Knowledge Discovery_ 33, 5 (2018), 1417–1445.  https://doi.org/10.1007/s10618-018-0602-x
  * Sun et al. (2020a) Bintao Sun, T.-H. Hubert Chan, and Mauro Sozio. 2020a.  Fully Dynamic Approximate k-Core Decomposition in Hypergraphs.  _ACM Transactions on Knowledge Discovery from Data_ 14, 4 (May 2020), 1–21.  https://doi.org/10.1145/3385416
  * Sun et al. (2020b) Bintao Sun, Maximilien Danisch, T-H. Hubert Chan, and Mauro Sozio. 2020b.  KClist++: a simple algorithm for finding $k$-clique densest subgraphs in large graphs.  _Proceedings of the VLDB Endowment_ 13, 10 (jun 2020), 1628–1640.  https://doi.org/10.14778/3401960.3401962
  * Tang et al. (2010) John Tang, Mirco Musolesi, Cecilia Mascolo, and Vito Latora. 2010.  Characterising temporal distance and reachability in mobile and online social networks.  _ACM SIGCOMM Computer Communication Review_ 40, 1 (jan 2010), 118–124.  https://doi.org/10.1145/1672308.1672329
  * Tsourakakis (2015) Charalampos Tsourakakis. 2015\.  The K-clique Densest Subgraph Problem. In _Proceedings of the 24th International Conference on World Wide Web_ (2015-05). International World Wide Web Conferences Steering Committee.  https://doi.org/10.1145/2736277.2741098
  * Tsourakakis (2014) Charalampos E. Tsourakakis. 2014\.  A Novel Approach to Finding Near-Cliques: The Triangle-Densest Subgraph Problem.  _arXiv_ (2014).  arXiv:1405.1477 [cs.DS]
  * Vazquez et al. (2007) Alexei Vazquez, Balázs Rácz, András Lukács, and Albert-László Barabási. 2007\.  Impact of Non-Poissonian Activity Patterns on Spreading Processes.  _Physical Review Letters_ 98, 15 (April 2007), 158702.  https://doi.org/10.1103/physrevlett.98.158702
  * Wang et al. (2020b) Jiabing Wang, Rongjie Wang, Jia Wei, Qianli Ma, and Guihua Wen. 2020b.  Finding dense subgraphs with maximum weighted triangle density.  _Information Sciences_ 539 (2020), 36–48.  https://doi.org/10.1016/j.ins.2020.06.004
  * Wang et al. (2020a) Jingjing Wang, Yanhao Wang, Wenjun Jiang, Yuchen Li, and Kian-Lee Tan. 2020a.  Efficient Sampling Algorithms for Approximate Temporal Motif Counting. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_. ACM.  https://doi.org/10.1145/3340531.3411862
  * Wu et al. (2022) Jiajing Wu, Jieli Liu, Weili Chen, Huawei Huang, Zibin Zheng, and Yan Zhang. 2022\.  Detecting Mixing Services via Mining Bitcoin Transaction Network With Hybrid Motifs.  _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ 52, 4 (apr 2022), 2237–2249.  https://doi.org/10.1109/tsmc.2021.3049278
  * Zhao et al. (2010) Qiankun Zhao, Yuan Tian, Qi He, Nuria Oliver, Ruoming Jin, and Wang-Chien Lee. 2010\.  Communication motifs. In _Proceedings of the 19th ACM international conference on Information and knowledge management - CIKM '10_. ACM Press.  https://doi.org/10.1145/1871437.1871694
  * Zhong et al. (2024) Ming Zhong, Junyong Yang, Yuanyuan Zhu, Tieyun Qian, Mengchi Liu, and Jeffrey Xu Yu. 2024\.  A Unified and Scalable Algorithm Framework of User-Defined Temporal $(k,\mathcal{X})$-Core Query.  _IEEE Transactions on Knowledge and Data Engineering_ (2024), 1–15.  https://doi.org/10.1109/tkde.2023.3349310

##  Appendix A Application scenarios for the TMDS problem

While we study the TMDS problem in its general form, in this section we
discuss more in depth two possible applications of our novel problem
formulation, showing that the TMDS is a really versatile and powerful tool for
temporal network analysis. We will discuss how the Temporal Motif Densest
Subnetwork (TMDS) can be used to discover important insights from (i) travel
networks and (ii) e-commerce networks capturing online platforms.

(i) A travel network can be modeled as a temporal network $T=(V,E)$ with $V$
being the set of vertices corresponding to Points Of Interest (POIs) or
particular geographic areas of a city (Lei et al., 2020), and edges of the
form $(u,v,t)\in E$ represent trips by user that travel from point $u\in V$ to
point $v\in V$ at time $t$. A temporal motif $M$ on such network captures
therefore travel patterns and their dynamics. As an example a temporal motif
$M:x\stackrel{{\scriptstyle t_{1}}}{{\to}}y\stackrel{{\scriptstyle
t_{2}}}{{\to}}x$ occurring within one day often corresponds to a round trip by
a user from $x$ being the home location, to $y$ being the work location. The
TMDS problem formulation, in such a scenario can provide unique insights on
the POIs appearing frequently together in the various travel patterns
(isomorphic to $M$) of the various users. Furthermore, analyzing different
time-scales as captured by the temporal motif duration, can yield unique
insights about daily vs. weekly vs. monthly patterns. As for our Figure 1 in
the TMDS several POIs often coexist, and such information can be used to
improve connections between POIs that are not well connected by public
transport, or for the design of travel passes for specific areas of a city
with specific time-duration, based on POIs that are often visited together in
the various trips.

(ii) E-commerce online platforms can be modeled as temporal bipartite networks
$T=(V,E)$, where the set of vertices is partitioned in two layers $V=U\cup P$,
with $U$ being the set of users (i.e., customers that purchase online
products), and $P$ the set of products available for purchase. A temporal edge
$e=(u,p,t)$ on such a network captures that user $u\in U$ purchased product
$p\in P$ at a given time $t$. As an example a temporal motif
$M^{\prime}:x\stackrel{{\scriptstyle t_{1}}}{{\to}}y,x\stackrel{{\scriptstyle
t_{2}}}{{\to}}z$ occurring within a time-limit corresponds to a pair of
products i.e., $y$ and $z$ that user $x$ buys at distance of at most the
provided time-limit, note also that $z$ is purchased after $y$. A temporal
motif $M$ therefore captures specific purchase habits of users within a
limited time-limit (as again controlled by the duration parameter of the
temporal motif). The optimal TMDS can be used to collect a set of users (and
items) that frequently co-occur. In particular, the TMDS can contain several
vertices (i.e., users) with similar purchase sequences or buying habits, this
enables the design of personalized advertisement for those users in the TMDS
(e.g., by leveraging the history of other users in the TMDS), furthermore this
can be studied at different time-scales. Note also that this is more powerful
than only considering products that are frequently co-purchased together
(e.g., consider $M^{\prime}$, then the products $y$ and $z$ are purchased in
different moments), for which many techniques already exist.

Table 3. Notation table.

Symbol | Description
---|---
$T=(V_{T},E_{T})$ | Temporal network
$T[W],W\subseteq V_{T}$ | Induced temporal sub-network by $W$
$n,m$ | Number of nodes and temporal edges of $T$
$D_{T},G_{T}$ | Directed and undirected static network of $T$
$M=(K,\sigma)$ |  $k$-vertex $\ell$-edge temporal motif
$K=(V_{K},E_{K})$ | Multi-graph of the temporal motif $M$
$\sigma$ | Ordering of the edges of $E_{K}$ in a motif
$\delta$ | Time window-length of a temporal motif instance
$\mathcal{S}_{T^{\prime}}$ | Set of $\delta$-instances of $M$ in the network $T^{\prime}$
$\mathcal{S}_{W},W\subseteq V_{T}$ | Set of $\delta$-instances of $M$ in the network $T[W]$
$\tau$ | Weighting function over $\mathcal{S}_{T}$
$\tau(W),W\subseteq V_{T}$ | Total weight of the $\delta$-instances in $\mathcal{S}_{W}$
$\rho(\cdot)$ | TMDS objective function
$G[M]$ | Undirected graph associated to $K$
$\mathcal{H}$ | Set of $k$-CIS over $G_{T}$
${d}_{W}^{\tau}(v),W\subseteq V_{T}$ | Temporal motif degree of vertex $v$ in $T[W]$
${d}_{T^{\prime}}^{\tau}(v),T^{\prime}\subseteq T$ | Temporal motif degree of vertex $v$ in $T^{\prime}$
$\xi>0$ | Threshold for batch peeling
$\varepsilon,\eta$ | Accuracy and confidence parameters
$r$ | Sample size in ProbPeel, HybridPeel
$\hat{d}_{W}^{\tau}(v)$ | Estimate of the temporal motif degree of $v$ in $T[W]$
$\hat{m}$ |  Maximum edges from $E_{T}$ in a window length of $\delta$
$q$ | Parameter of the subroutine PRESTO-A (Sarpe and Vandin, 2021b)

##  Appendix B Notation

A summary of the notation used throughout the paper is reported in Table 3.

Table 4. _Directed_ denotes if the edges of the network are directed or not.
_Aggregation_ means: (i) the objective is based on purely static quantities
over snapshots (i.e., it discards temporal information) (ii) the edges are
assumed to be in the form $(u,v,[t_{1},t_{2}])$, that is each edge is
associated with an interval instead of a timestamp, in such interval the graph
is static (iii) the optimal scores are computed on specific time-intervals of
the network. _High-order structures_ denotes if the objective function of the
formulation considers more than node or edge degrees, accounting for cliques
or larger patterns. $\mathsf{D}$ vs $\mathsf{C}$ denotes if the objective is
to compute cores ($\mathsf{C}$) or dense subnetworks ($\mathsf{D}$).
_Segmentation_ denotes that the formulation controls the temporal properties
of the reported solution, e.g., burstiness-persistence or a specific temporal
support duration.

Formulation | Directed | Aggregation | High-order structures | Density ($\mathsf{D}$) vs Cores ($\mathsf{C}$) | Segmentation
---|---|---|---|---|---
TMDS (ours) | ✓ | ✗ | ✓ | $\mathsf{D}$ | ✗
(Galimberti et al., 2020) | ✗ | ✓ | ✗ | $\mathsf{C}$ | ✓
(Li et al., 2018) | ✗ | ✓ | ✗ | $\mathsf{C}$ | ✓
(Oettershagen et al., 2023a) | ✗ | ✗ | ✗ | $\mathsf{C}$ | ✗
(Qin et al., 2022) | ✗ | ✓ | ✗ | $\mathsf{C}$ | ✓
(Zhong et al., 2024) | ✗ | ✓ | ✗ | $\mathsf{C}$ | ✓
(Lin et al., 2022) | ✗ | ✓ | ✓ | $\mathsf{D}$ | ✓
(Qin et al., 2023) | ✗ | ✓ | ✗ | $\mathsf{D}$ | ✓
(Rozenshtein et al., 2019) | ✗ | ✓ | ✗ | $\mathsf{D}$ | ✓

##  Appendix C TMDS vs existing formulations

In this section we present an overview of the existing formulations for
cohesive subnetwork discovery in temporal networks comparing them with our
TMDS formulation. The extensive comparison is reported in Table 4. As a
summary of such table we highlight the following, our formulation is the
unique of its kind combining _high-order structures_ with _purely temporal
informal information_ avoiding therefore temporal aggregation, and
additionally it can be used on directed temporal networks.

First we observe that most of the existing formulations work on _undirected_
temporal networks, and it is not straightforward to adapt (or extend) them on
directed temporal networks, which are more general models. Our formulation
naturally captures directed temporal networks, and in fact fully exploits such
information, as an example, with the definition of temporal motif that we
assume (Definition 2.1) there are eight possible triangles on directed
temporal networks, but _only one_ such triangle exists on undirected temporal
networks, reducing significantly the information that we can gain by analyzing
such patterns. Then our formulation avoids a temporal network model leading to
aggregation, which is known to cause information loss (Holme and Saramäki,
2019), as computing snapshots of temporal networks (or constraining optimal
scores to specific fixed intervals) may obfuscate the general temporal
properties in the data. Additionally, only one of the surveyed formulations
(i.e., (Lin et al., 2022)) accounts for high-order structures in the form of
_static quasi-cliques_ which is a completely different formulation compared to
TMDS. Our formulation is in fact much more flexible as the temporal motif can
by _any arbitrary temporal motif_ of interest. Finally we also avoid
segmentation as the constrain on the time-interval length $\delta$ well
correlates with the overall timespan of the reported solution, and with more
complex weighting functions $\tau$ defined over $\mathcal{S}_{T}$ it is also
possible to control for the temporal properties of the reported solution
(e.g., a persistence score from (Belth et al., 2020)).

##  Appendix D Randomized algorithms

In this section we present some missing results about our ALDENTE algorithms
based on randomized sampling, that is in Section D.1 we discuss how to
estimate temporal motif degrees of the vertices and leverage such results with
an existing sampling algorithm to prove concentration of the various
estimates, these results are used both for ProbPeel and for HybridPeel.
Lastly, in Section D.2 we illustrate the pseudocode of HybridPeel.

###  D.1. Estimating temporal motif-degrees

####  D.1.1. Building the estimator

We briefly recall from Section 4 how to compute a $(1\pm\varepsilon)$ estimate
of the temporal motif degree ${d}_{W}^{\tau}(w)$ of a vertex $w\in W$. First
recall that we assume access to a sampling algorithm $\mathcal{A}$, which,
given as input a subnetwork $T[W]$, $W\subseteq V_{T}$, it outputs a sample
$T^{\prime}=(V^{\prime},E^{\prime})\subseteq T[W]$. Using such a sample
$T^{\prime}$ we can compute an estimate $\hat{d}_{W}^{\tau}(w,T^{\prime})$ of
the degree ${d}_{W}^{\tau}(w)$, for each $w\in W$ as

(2)
$\hat{d}_{W}^{\tau}(w,T^{\prime})=\sum_{S\in\mathcal{S}_{{T}^{\prime}}:w\in
S}\frac{\tau(S)}{p_{S}},$

where $p_{S}$ is the probability of observing $S\in\mathcal{S}_{{T}^{\prime}}$
in the sampled subnetwork ${T}^{\prime}=({V}^{\prime},{E}^{\prime})$.

###### Lemma D.1.

For any $w\in W$, the count $\hat{d}_{W}^{\tau}(w,T^{\prime})$ computed on a
sampled subnetwork $T^{\prime}\subseteq T[W]$ is an unbiased estimate of
${d}_{W}^{\tau}(w)$.

###### Proof.

We can rewrite the estimator as

$\hat{d}_{W}^{\tau}(w,T^{\prime})=\sum_{S\in\mathcal{S}_{T[W]}:w\in
S}\frac{\tau(S)}{p_{S}}\mathbbm{1}[\\{S\in\mathcal{S}_{{T}^{\prime}}\\}],$

where $\mathbbm{1}[\cdot]$ is an indicator random variable taking value 1 if
the predicate holds, and 0 otherwise. By taking expectation on both sides,
combined with the linearity of expectation, and the fact that
$\mathbb{E}[\mathbbm{1}[\\{S\in\mathcal{S}_{{T}^{\prime}}\\}]]=p_{S}$ the
claim follows by the definition of ${d}_{W}^{\tau}(w)$. ∎

Given a subnetwork $T[W]\subseteq T,W\subseteq V_{T}$ we execute the sampling
algorithm $\mathcal{A}$ to obtain $r\in\mathbb{N}$ i.i.d. sampled subnetworks
$\mathcal{D}=\\{{T}_{1},\dots,{T}_{r}:{T}_{i}=\mathcal{A}(T[W])\subseteq
T[W],i\in[r]\\}$ (in line 1). We can therefore compute the sample average of
the estimates obtained on each sampled subnetwork obtaining the estimators
$\hat{d}_{W}^{\tau}(w)$ for $w\in W$, where

$\hat{d}_{W}^{\tau}(w)=\frac{1}{r}\sum_{i=1}^{r}\hat{d}_{W}^{\tau}(w,T_{i}),\quad\text{for
all }w\in W,$

and $\hat{d}_{W}^{\tau}(w,T_{i})$ is computed with Equation (2) on the $i$-th
sampled subnetwork $T_{i}$ from the randomized sampling algorithm
$\mathcal{A}$. As discussed in Section 4, it also holds that
$\hat{\tau}(W)=1/k\sum_{w\in W}\hat{d}_{W}^{\tau}(w)$ is an unbiased estimate
of $\tau(W)$, as $\mathbb{E}[\hat{d}_{W}^{\tau}(w)]={d}_{W}^{\tau}(w)$ by
Lemma D.1 combined with the linearity of expectation and the fact that
$\tau(W)=1/k\sum_{w\in W}{d}_{W}^{\tau}(w)$, which is an important property
for the final convergence guarantees of our algorithms in ALDENTE.

####  D.1.2. Leveraging a sampling algorithm

Algorithm 1 can employ any sampling algorithm $\mathcal{A}:T\mapsto 2^{T}$ as
subroutine. In practice we used the state-of-the-art sampling algorithm
PRESTO-A (Sarpe and Vandin, 2021b) for estimating temporal motif counts of
arbitrary shape.121212Other specialized sampling algorithms for triangles or
butterflies can be adopted in our ALDENTE algorithms speeding up our suite
(Wang et al., 2020a; Pu et al., 2023). For PRESTO-A the authors provide bounds
on the number of samples $r$ for event
“$\hat{\tau}(W_{i})\in(1\pm\varepsilon)\tau(W_{i})$” to hold with arbitrary
probability $>1-\eta$ for $\eta\in(0,1)$, which needs to be adapted to work in
our scenario since we require _stricter_ guarantees. We adapt such algorithm
to general weighting functions $\tau$ over the set of $\delta$-instances, and
to compute $\hat{d}_{W_{i}}^{\tau}(w),w\in W_{i}$ at each iteration $i$ of
Algorithm 1. We now briefly describe how PRESTO-A works and proceed to
illustrate how to adapt the bound in (Sarpe and Vandin, 2021b) to the function
$\mathtt{GetBound}$, since a tighter concentration result is needed.

Given a subnetwork $T[W_{i}]$, PRESTO-A samples a small-size subnetwork
${T}^{\prime}=({V}^{\prime},{E}^{\prime})\subseteq T[W_{i}]$ ensuring that all
its edges are contained in a window of length $q\delta,q>1$, i.e., let
$t_{1},\dots,t_{|{E}^{\prime}|}$ be the sorted timestamps of the edges of
$T^{\prime}$ then $t_{|{E}^{\prime}|}-t_{1}\leq q\delta$. On such subnetwork
PRESTO-A computes Equation (2) for each $w\in W_{i}$, where
$p_{S}=\frac{q\delta-\Delta_{S}}{\Delta_{T[W_{i}]}}$, where $\Delta_{S}$ is
the length of the $\delta$-instance $S\in\mathcal{S}_{{T}^{\prime}}$ and
$\Delta_{T[W_{i}]}=\mathcal{O}(t_{|E_{T}[W_{i}]|}-t_{1})$, i.e., it is simply
proportional to the length of the timespan of $T[W_{i}]$. Such algorithm
extracts $r_{i}$ sampled subnetworks and computes the unbiased estimates
$\hat{d}_{W_{i}}^{\tau}(w),w\in W_{i}$ and $\hat{\tau}(W_{i})=1/k\sum_{w\in
W_{i}}\hat{d}_{W_{i}}^{\tau}(w)$. Next we show that leveraging the techniques
in (Sarpe and Vandin, 2021b) we obtain a bound on the number of samples
$r_{i},i\in[I]$ computed through $\mathtt{GetBound}$. In particular, by
performing a similar analysis to the one in (Sarpe and Vandin, 2021b) we
obtain the following corollary, which specifies the output of the function
$\mathtt{GetBound}$.

###### Corollary D.2.

Let $T[W_{i}]$ be the induced temporal network by $W_{i}$ at an arbitrary
iteration $i$ of Algorithm 1, given $\varepsilon>0,\eta/2^{i}>0,q>1$ if
$r_{i}\geq\left(\frac{\Delta_{T[W_{i}]}}{(q-1)\delta}-1\right)\frac{1}{(1+\varepsilon)\ln(1+\varepsilon)-\varepsilon}\ln\left(\frac{2|W_{i}|}{\eta/2^{i}}\right)$
then $\hat{d}_{W_{i}}^{\tau}(w)\in(1\pm\varepsilon){d}_{W_{i}}^{\tau}(w)$
simultaneously for each $w\in W_{i}$ with probability $>1-\eta/2^{i}$.

###### Proof (skecth)..

The proof is identical and directly follows from the guarantees obtained in
(Sarpe and Vandin, 2021b, Theorem 3.4., extended arXiv version) combined with
a union bound. Fix an arbitrary vertex $w\in W_{i}$ and a sample
$T^{\prime}\subseteq W_{i}$, then from Lemma D.1 the estimator
$\hat{d}_{W_{i}}^{\tau}(w,T^{\prime})$ is unbiased where under the sampling
algorithm PRESTO-A we set
$p_{S}=\tfrac{q\delta-\Delta_{S}}{\Delta_{T[W_{i}]}}$ where $\Delta_{S}$ is
the duration of each $\delta$-instance $S\in\mathcal{S}_{W_{i}}$ and
$\Delta_{T[W_{i}]}=t_{|E_{T}[W_{i}]|-\ell}-t_{\ell}+c\delta$ where $t_{i}$
denotes the timestamp of the $i$-th edge (of $E_{T}[W_{i}]$) assuming that
such edges are sorted by increasing timestamps. This implies that the bound on
the variance of such estimator is the same as (Sarpe and Vandin, 2021b, Lemma
3.2., extended arXiv version) where the global motif count is replaced with
the temporal motif degree, i.e.,
$\mathbb{E}[\hat{d}_{W_{i}}^{\tau}(w,T^{\prime})^{2}]\leq\frac{{d}_{W_{i}}^{\tau}(w)^{2}\Delta_{T[W_{i}]}}{(c-1)\delta}$.
Using (Sarpe and Vandin, 2021b, Theorem 3.4., extended arXiv version) for an
arbitrary vertex $w\in W_{i}$ it holds, that if
$r_{i}\geq\left(\frac{\Delta_{T[W_{i}]}}{(q-1)\delta}-1\right)\frac{1}{(1+\varepsilon)\ln(1+\varepsilon)-\varepsilon}\ln\left(\frac{2}{\eta/2^{i}}\right)$
then
$\mathbb{P}[|\hat{d}_{W}^{\tau}(w)-{d}_{W}^{\tau}(w)|\geq\varepsilon{d}_{W}^{\tau}(w)]\leq\eta/2^{i}$.
The final claims from a direct application of the union bound over all
vertices $w\in W_{i}$. ∎

###  D.2.  HybridPeel— pseudocode

Input:
$T=(V_{T},E_{T}),M,\delta\in\mathbb{R}^{+},\tau,\xi>0,\varepsilon>0,\eta\in(0,1),J\geq
1$.

Output: $W$.

1 $W_{1}\leftarrow V_{T}$;

2 for  _$(i\leftarrow 1,\dots,J)\land(W_{i}\neq\emptyset)$_ do

3 $r_{i}\leftarrow\mathtt{GetBound}(W_{i},\varepsilon,\eta/J)$;

4
$\mathcal{D}=\\{T_{1},\dots,T_{r_{i}}\\}\leftarrow\mathcal{A}^{r_{i}}(T[W_{i}])$;

5
$\hat{d}_{W_{i}}^{\tau}(w_{1}),\dots,\hat{d}_{W_{i}}^{\tau}(w_{|W_{i}|})\leftarrow\mathtt{GetEstimates}(W_{i},\mathcal{D})$;

6 $\hat{\tau}(W_{i})\leftarrow 1/k\sum_{w\in W_{i}}\hat{d}_{W_{i}}^{\tau}(w)$;

7 $L(W_{i})\leftarrow\left\\{w\in W_{i}:\hat{d}_{W_{i}}^{\tau}(w)\leq
k(1+\xi)\hat{\tau}(W_{i})/|W_{i}|\right\\}$;

8 $W_{i+1}\leftarrow W_{i}\setminus L(W_{i})$; $i\leftarrow i+1$;

9

10$W^{\prime}\leftarrow$ Greedy ($T[W_{J+1}],M,\delta,\tau$);

return
_$W=\operatorname*{arg\,max}_{j=1,\dots,J}\\{\hat{\tau}(W_{j})/|W_{j}|,\rho(W^{\prime})\\}$._

Algorithm 2 HybridPeel

We report the missing pseudocode of HybridPeel in Algorithm 2. The algorithm
proceeds as follows, it runs for $J$ iterations the randomized batch peeling
approach (lines 2-2), obtaining therefore the sets $W_{1},\dots,W_{J}$ and
$W_{J+1}$. For the vertex sets $W_{i},i\in[J]$ the algorithm has only
approximate density $\hat{\tau}(W_{i})/|W_{i}|$ where the approximation factor
is controlled by the parameter $\varepsilon$ (i.e.,
$\hat{\tau}(W_{i})\in(1\pm\varepsilon)\tau(W_{i})$), instead on $W_{J+1}$ the
algorithm can be summarized by applying Greedy on $T[W_{J+1}]$ (that we
discuss in details in Section F.2). Therefore greedy peeling is applied on
$T[W_{J+1}]$, which proceeds by removing vertices one at a time according to
their exact temporal motif degree in $T[W_{J+1}]$ (line 2). That is, the
algorithm computes all temporal motif-instances in $T[W_{J+1}]$ and it
greedily removes, one at a time, the vertices with minimum temporal motif-
degree, Greedy therefore returns the solution with maximum density among the
$\mathcal{O}(|W_{J+1}|-k)$ vertex sets observed (i.e., it starts from
$W_{J+1}$ and peels it one vertex at a time until it becomes empty). The
solution with maximum density is finally returned by HybridPeel, where the
maximum is taken over the $J$ solutions obtained in the randomized batch
peeling loop and the best solution identified by Greedy when executed on
$T[W_{J+1}]$ (line 2). The approximation ratio HybridPeel is shown in Theorem
4.3, and it is presented in the next section.

We recall that intuitively, HybridPeel achieves very good performances and
scales on large data since, at the beginning of its execution during the first
$J$ iterations (when the temporal network is large) it relies on the
approximate estimation of temporal motif degrees for the batch peeling step,
while when the network size is small (after the $J$ iterations) HybridPeel
peels vertices one at a time according to their actual temporal motif degrees
in the remaining subnetwork, which can be computed efficiently.

##  Appendix E Missing proofs

Lemma F.3Lemma F.4Lemma F.5Theorem 4.2Theorem 4.3 Figure 5. Dependency graph
for the main results we obtain, i.e., Theorem 4.2 and Theorem 4.3.

In this section we present the missing proofs for Theorem 4.2, Theorem 4.3,
and Lemma 5.1. We show in Figure 5 the dependency graph for the proofs of
Theorem 4.2 and Theorem 4.3 as they depend on results that we obtain in
Section F, for a better understanding, we suggest to follow the proofs in
reverse order of dependence.

###### Proof of Theorem 4.2.

We first fix the random variable corresponding to the number of iterations of
Algorithm 1 to $I\leq\mathcal{O}(\log_{1+\xi}(n))$ since an analogous result
to Lemma F.5 holds also for Algorithm 1, i.e., we are conditioning on the
realization of $I$ in its range. In the following analysis we assume that the
events
$``\hat{d}_{W_{i}}^{\tau}(w)\in(1\pm\varepsilon){d}_{W_{i}}^{\tau}(w),w\in
W_{i}$” hold at each iteration $i\in[I]$ of our Algorithm 1 with probability
$>1-\eta/2^{i}$, note that this is ensured by the function GetBound.

First we note that there should exist at least one vertex in
$L(W_{i}),i\in[I]$, since for contradiction let
$\hat{d}_{W_{i}}^{\tau}(w)>k(1+\xi)\hat{\tau}(W_{i})/|W_{i}|$ for each $w\in
W_{i}$, then we can prove the following $k\hat{\tau}(W_{i})=\sum_{w\in
W_{i}}\hat{d}_{W_{i}}^{\tau}(w)>k(1+\xi)|W_{i}|\hat{\tau}(W_{i})/|W_{i}|$
hence $1>(1+\xi),\xi>0$, leading to the contradiction. The analysis is similar
to Lemma F.4 but complicated by the fact that the quantities involved are
estimates. Consider the iteration in which the first vertex $v\in W^{*}$ is
removed, let $W^{\prime}$ be the set of vertices in such iteration and notice
that $W^{*}\subseteq W^{\prime}$. Connecting $\hat{\tau}(W^{\prime})$ and
$\tau(W^{\prime})$ through $\hat{d}_{W^{\prime}}^{\tau}(w),w\in W^{\prime}$.

$\hat{\tau}(W^{\prime})=\frac{1}{k}\sum_{w\in
W^{\prime}}\hat{d}_{W^{\prime}}^{\tau}(w)\geq\frac{1}{k}\sum_{w\in
W^{\prime}}(1-\varepsilon){d}_{W^{\prime}}^{\tau}(w)\geq(1-\varepsilon)\tau(W^{\prime})$

And similarly $(1+\varepsilon)\tau(W^{\prime})\geq\hat{\tau}(W^{\prime})$. We
recall that for $v\in W^{*}$ it holds that
${d}_{W^{*}}^{\tau}(v)\geq\tau(W^{*})/|W^{*}|$. And that
$\hat{d}_{W^{\prime}}^{\tau}(v)\geq(1-\varepsilon){d}_{W^{\prime}}^{\tau}(v)\geq(1-\varepsilon){d}_{W^{*}}^{\tau}(v)$,
since $W^{*}\subseteq W^{\prime}$. Combining everything we get

$\displaystyle
k(1+\xi)(1+\varepsilon)\frac{\tau(W^{\prime})}{|W^{\prime}|}\geq
k(1+\xi)\frac{\hat{\tau}(W^{\prime})}{|W^{\prime}|}\geq\hat{d}_{W^{\prime}}^{\tau}(v)\geq(1-\varepsilon){d}_{W^{*}}^{\tau}(v)$
(3)
$\displaystyle\geq(1-\varepsilon)\frac{\tau(W^{*})}{|W^{*}|}\Leftrightarrow\frac{\tau(W^{\prime})}{|W^{\prime}|}\geq\frac{(1-\varepsilon)}{k(1+\xi)(1+\varepsilon)}\frac{\tau(W^{*})}{|W^{*}|}.$

Let $W$ be the vertex set returned by Algorithm 1 and $W^{\prime}$ the
solution achieving the approximation in Equation (3), note that
$\hat{\tau}(W^{\prime})/|W^{\prime}|\geq(1-\varepsilon)\rho(W^{\prime})$ and
the output $W$ may be such that
$\hat{\tau}(W)/|W|\geq(1-\varepsilon)\rho(W^{\prime})$ but with
$\rho(W)\leq\rho(W^{\prime})$, but noting that
$\hat{\tau}(W)\in(1\pm\varepsilon)\tau(W)$ then
$(1-\varepsilon)\rho(W^{\prime})\leq\hat{\tau}(W)/|W|\leq(1+\varepsilon)\rho(W)$
therefore $\rho(W)\geq\frac{(1-\varepsilon)}{(1+\varepsilon)}\rho(W^{\prime})$
hence the claim follows by combining the above with Equation (3) and the fact
that Algorithm 1 will return a vertex set achieving at least the solution
attained by $W$, which proves the bound on the approximation factor. Finally,
to show that such guarantees hold with probability $>1-\eta$, let $F_{i}$ be
the event that the probabilistic guarantees of Algorithm 1 fail at iteration
$i\in[I]$, this occurs only if the following bad event occurs:
$F_{i}\mathbin{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{=}}\text{``there
exist }w\in W_{i}\text{ such that
}\hat{d}_{W_{i}}^{\tau}(w)\notin(1\pm\varepsilon){d}_{W_{i}}^{\tau}(w)$”.
Recall that at each iteration $i\in[1,\mathcal{O}(\log n)]$ the sample size
obtained by GetBound guarantees that $\mathbb{P}[F_{i}]\leq\eta/2^{i}$, then
the probability of the event $F_{R}$ that the algorithm fails under random
iterations $R$ during its execution is bounded by

$\mathbb{P}\left(F_{R}\right)<\sum_{i=1}^{+\infty}(\mathbb{P}\left[F_{R}|R=i\right]\mathbb{P}\left[I=i\right])\leq\sum_{i=1}^{+\infty}\mathbb{P}[F_{i}]\leq\sum_{i=1}^{+\infty}\frac{\eta}{2^{i}}\leq\eta,$

combining the union bound and the geometric series, concluding the proof. ∎

---
Figure 6. Temporal network
$T\mathbin{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{=}}(T_{1}=(V_{1},E_{1})\cup
T_{2}=(V_{2},E_{2}))$ as constructed in the proof of Lemma 5.1. The timestamps
of the temporal edges are placed below each layer, for simplicity of
visualization. $V_{1}$ is the optimal solution for S2DS but it achieves a
solution that is 0 for TMDS problem, for which the vertices in $V_{2}$ achieve
the optimal solution $\mathcal{O}$ ($n^{2}$).

###### Proof of Theorem 4.3 (Sketch).

The proof is similar to the one of Lemma 4.2. We only need to account for some
sub-cases that may occur when considering the solution $W^{\prime}$ obtained
in Line 2 that is obtained by running Greedy on $W_{J+1}$. As for the proof of
Lemma 4.2 we assume that at each iteration of the $J$ iterations by using
approximate temporal-motif degrees it holds that
“$\hat{d}_{W_{i}}^{\tau}(w_{j})\in(1\pm\varepsilon){d}_{W_{i}}^{\tau}(w_{j})$”
for each $w_{j}\in W_{i}$ and $i=1,\dots,J$. Which also implies that
$\hat{\tau}(W_{j})/|W_{j}|\in(1\pm\varepsilon)\tau(W_{j})/|W_{j}|$. Now let us
consider the first node $v\in W^{*}$ that gets removed across the iterations
of the algorithm, then there may be two distinct cases (I). $v\in W_{i}$ for
some $i=1,\dots,J$; and (II) or $v\in W_{J+1}$. (I) In this case the algorithm
returns a solution which attains the same approximation quality as in Lemma
4.2 since it is easy to see that $W^{\prime}$ (i.e., the subnetwork obtain by
Greedy) cannot provide a much worse solution than the best solution observed
by the algorithm during the $J$ iterations using approximate temporal motif
degrees. Let $W_{a}$ be the solution achieving the
$\tfrac{(1-\varepsilon)}{k(1+\xi)(1+\varepsilon)}$-approximation factor
(recall that $v\in W^{*}$ and $v\in W_{i}$, for $i\in[J]$ so such a solution
must exists). Let $W_{b}$ be the best estimated solution by the algorithm
i.e.,
$W_{b}=\operatorname*{arg\,max}\\{\hat{\tau}(W_{i})/|W_{i}|,\rho(W^{\prime})\\}$
returned by HybridPeel, then it is easy to see that $\rho(W^{\prime})$ cannot
be less than $(1-\varepsilon)\rho(W_{a})$ since otherwise the algorithm will
pick $\hat{\tau}(W_{a})/|W_{a}|$ as optimal solution, therefore the worst case
still remains the one as in Lemma 4.2 leading to the
$\tfrac{(1-\varepsilon)^{2}}{k(1+\xi)(1+\varepsilon)^{2}}$-approximation
factor. (II) If for $v\in W^{*}$, it holds $v\in W_{J+1}$ then it follows that
$\rho(W^{\prime})\geq 1/k\rho(W^{*})$ from Lemma F.3, note that the algorithm
may return a solution $W_{j}$ for some $j\in[J]$ such that
$\rho(W_{j})\leq\rho(W^{\prime})$ but
$\hat{\tau}(W_{j})/|W_{j}|\geq\rho(W^{\prime})$, clearly for such a solution
it holds $\rho(W_{j})\geq\tfrac{\rho(W^{*})}{k(1+\varepsilon)}$. Therefore the
approximation-ratio of the algorithm is bounded by
$\min\left\\{\tfrac{(1-\varepsilon)^{2}}{k(1+\xi)(1+\varepsilon)^{2}},\tfrac{1}{k(1+\varepsilon)}\right\\}$.
Finally we need to take the union bound over the $J$ iterations to guarantee
that the failure probability when running the randomized batch-peeling is
bounded by $\eta\in(0,1)$. Note that when $J=1$ for case (I) the approximation
ratio is bounded by $\tfrac{(1-\varepsilon)^{2}}{k(1+\xi)(1+\varepsilon)}$
since Greedy evaluates $\rho(\cdot)$ exactly on $W^{\prime}$ and not
approximately, concluding therefore the claim. ∎

###### Proof of Lemma 5.1.

First fix $n$ arbitrary large and also assume $n/12\in\mathbb{N}$ to keep the
notation simple. Let $T=T_{1}\cup T_{2}$ be the union of two temporal networks
with similar structure, the first one $T_{1}=(V_{1},E_{1})$ where
$V_{1}=\\{v_{1},\dots,v_{3n/4}\\}$ and
$E_{1}=\\{(v_{i},v_{j},2):i\in[1,n/4],j\in[n/4+1,n/2]\\}\cup\\{(v_{i},v_{j},1):i\in[n/4+1,n/2],j\in[n/2+1,3n/4]\\}$
and the other network is $T_{2}=(V_{2},E_{2})$ where
$V_{2}=\\{v^{\prime}_{1},\dots,v^{\prime}_{n/4}\\}$ and
$E_{2}=\\{(v^{\prime}_{i},v^{\prime}_{j},1):i\in[1,n/12],j\in[n/12+1,n/6]\\}\cup\\{(v^{\prime}_{i},v^{\prime}_{j},2):i\in[n/12+1,n/6],j\in[n/6+1,n/4]\\}$.
See Fig. 6 for a visualization of the resulting network $T$. Let $D_{T}$ be
the directed static network associated to $T$, then the solutions of S2DS on
$V_{1}$ and $V_{2}$ are respectively $(n/4)^{3}/(3n/4)$ and $(n/12)^{3}/(n/4)$
hence the optimal solution is achieved by $H^{*}=V_{1}$. But when we consider
TMDS problem on $T$ on a 2-path temporal motif for $\delta$ fixed at least to
1, $V_{1}$ has a solution whose value is $0$ (i.e., $\rho(H^{*})=0$), since
none of its temporal paths are time-respecting (there are no instances of
2-paths in $T_{1}$), while $W^{*}=V_{2}$ achieves a solution
$\rho(W^{*})=\mathcal{O}(n^{2})$. Finally note that $H^{*}\cap
W^{*}=\emptyset$. ∎

##  Appendix F Baseline algorithms

In the next sections we describe, prove the guarantees and give bounds on the
time complexity of each baseline algorithm considered, we recall that a
summary of such baselines is given in Table 1.

###  F.1. Exact

We first present Exact, an exact algorithm for the TMDS problem, which solves
multiple $(s,z)$-min-cut instances on a flow network encoding weights of
$\delta$-instances in $\mathcal{S}_{T}$, leveraging $\mathcal{H}$ (which we
briefly mentioned in Section 5). This algorithm extends ideas developed for
the exact solution of $k$-vertex motif and triangle (or $k$-clique) densest-
subgraph problems in static networks (Goldberg, 1984; Tsourakakis, 2014; Wang
et al., 2020b; Tsourakakis, 2015; Mitzenmacher et al., 2015; Fang et al.,
2019).

A flow network $Z=(V_{Z},E_{Z})$ is a directed network with two special
vertices $s\in V_{Z}$ (source) and $z\in V_{Z}$ (sink) and a set of
intermediate vertices, such that the source has edges of the form $(s,\cdot)$
and the sink is connected by edges of $(\cdot,z)$ where “$\cdot$” represents
an intermediate vertex. Additionally, each edge $e\in E_{Z}$ over the network
is assigned with a weight $w(e)$, and a $(s,z)$-min-cut on such network is a
partition $(\mathsf{S},\mathsf{Z})$ of the vertices $V_{Z}$ such that
$s\in\mathsf{S}$ and $z\in\mathsf{Z}$, and the cost of the cut (defined as sum
of the weights of the edges going from vertices in $\mathsf{S}$ to vertices in
$\mathsf{Z}$) is minimized.

We first recall some definitions, starting from graph isomorphism: we say that
$G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ are _isomorphic_ (denoted by
$G_{1}\\!\sim\\!G_{2}$) if there exists a bijection $g$ on the vertices such
that $e_{1}=(x,y)\in E_{1}$ if and only if $e_{2}=(g(x),g(y))\in E_{2}$.

Next we recall the construction of the set $\mathcal{H}$, that is given a
parameter $k\in\mathbb{N}$, we defined
$\mathcal{H}=\\{H:H=(V_{H},E_{H})\subseteq G_{T},\text{ for some
}H^{\prime}\subseteq H\text{ it holds
}H^{\prime}\\!\sim\\!G[M],\tau(V_{H})>0,\text{ and }|V_{H}|=k\\}$ to be the
set of $k$-connected induced subgraphs ($k$-CIS) from $G_{T}$, where each
$k$-CIS $H$ encodes a subgraph containing at least a $\delta$-instance $S$
with $\tau(S)>0$, and is induced in $G_{T}$, i.e., it contains all edges among
the vertices $V_{H}$. Note that this condition is ensured by requiring the
existence of $H^{\prime}\subseteq H$ such that $H^{\prime}\\!\sim\\!G[M]$ and
$\tau(V_{H})>0$, where $G[M]$ is the undirected graph associated to the
temporal motif $M$. Given a $k$-vertex $\ell$-edge temporal motif $M$ and a
temporal network $T=(V_{T},E_{T})$, let us consider the weighted flow network
$Z=(V_{Z}=\\{s\\}\cup V_{\mathcal{H}}\cup V_{T}\cup\\{z\\},E_{Z})$, with
$w_{Z,\zeta}:E_{Z}\mapsto\mathbb{R}_{0}^{+}$, where:

  * •

each vertex $v_{H}\in V_{\mathcal{H}}$ is associated to a $k$-CIS
$H\in\mathcal{H}$;

  * •

$s$ and $z$ are the source and sink vertices of the flow network;

  * •

$E_{Z}=(E_{1}\cup E_{2}\cup E_{3})$ where $E_{1}=\\{(s,v_{H}):v_{H}\in
V_{\mathcal{H}}\\}$, $E_{2}=\\{(v_{H},v):v_{H}\in V_{\mathcal{H}},v\in
V_{T},v\in V_{H}\\}$, $E_{3}=\\{(v,z):v\in V_{T}\\}$, i.e., $E_{1}$ connects
the source $s$ to all vertices in $V_{\mathcal{H}}$, $E_{2}$ connects each
vertex $v_{H}\in V_{\mathcal{H}}$ representing a $k$-CIS
$H=(V_{H},E_{H})\in\mathcal{H}$ to its vertices in $V_{H}\subseteq V_{T}$, and
$E_{3}$ connects each vertex of $V_{T}$ to the sink $z$;

  * •

the weighting function is defined as follows, given $\zeta\geq 0$:

$w_{Z,\zeta}(e)=\begin{cases}\tau(V_{H})=\sum_{S\in\mathcal{S}_{H}}\tau(S)&\text{if
}e=(s,v_{H})\in E_{1},\\\ +\infty&\text{if }e\in E_{2},\text{ and}\\\
\zeta&\text{if }e=(v,z)\in E_{3}.\end{cases}$

We show how the optimal solution $W^{*}$ to the TMDS problem is computed in
Algorithm 3. The algorithm first enumerates all $\delta$-instances in the
temporal network $T$ (line 3) and builds the flow network $Z$ described above
(line 3). It then instantiates $a,b$, i.e., the range in which we will seek
for the optimal values of the solution to Problem 1, $\tau_{\min}$ and $\zeta$
used for finding the optimal values through binary search (lines 3-3). Then
the algorithm starts its main loop (line 3) seeking at each iteration for the
optimal solution $W^{*}$ by repeatedly solving the $(s,z)$-min cut on the flow
network $Z$ with weights $w_{Z,\zeta}$, and updating $\zeta$ accordingly at
each iteration, while maintaining the candidate optimal solution (line 3).

We show in the next lemma that Algorithm 3 correctly identifies the optimal
density value $\rho^{*}\mathbin{=}\rho(W^{*})=\tau(W^{*})/|W^{*}|$ to Problem
1 therefore returning the optimal solution $W^{*}$.

The proof follows similar arguments as in previous work (Wang et al., 2020b;
Tsourakakis, 2015; Mitzenmacher et al., 2015). Some of details are not
immediately transferable from previous proofs, such as the connection to the
solution on the temporal network $T$, therefore, we present in detail the
proof below.

###### Lemma F.1.

Given a temporal network $T=(V_{T},E_{T})$, a temporal motif $M$, and
$\delta>0$, let $\rho^{*}$ be the optimal value for the solution of TMDS
problem with weighting function $\tau$. Let $(\mathsf{S},\mathsf{Z})$ be the
$(s,z)$-min cut on $Z$ with weighting function $w_{Z,\zeta},\zeta\geq 0$ at an
arbitrary iteration of Algorithm 3. If $V^{\prime}=\mathsf{S}\cap
V_{T}\neq\emptyset$ then $\zeta\leq\rho^{*}$ else $\zeta\geq\rho^{*}$.

Input: $T=(V_{T},E_{T}),M,\delta\in\mathbb{R}^{+},\tau$.

Output: $W^{*}$ optimal solution to Problem 1.

1 $\mathcal{S}\leftarrow\\{S:S\text{ is }\delta\text{-instance of }M\text{ in
}T\\}$;

2 if  _$\mathcal{S}=\emptyset$_ then return _$\emptyset$_ ;

3 $Z\leftarrow\mathtt{BuildGraph}(T,\mathcal{S})$;

4 $a\leftarrow
0;b\leftarrow\sum_{S\in\mathcal{S}}\tau(S);\tau_{\min}\leftarrow\min_{S\in\mathcal{S}}\\{\tau(S)\\}$;

5 $\zeta\leftarrow(b+a)/2$;

6 while  _$b-a\geq\frac{\tau_{\min}}{n(n-1)}$_ do

7 $(\mathsf{S},\mathsf{Z})\leftarrow\mathtt{MinCut}(s,z,Z,w_{Z,\zeta})$;

8 if  _$\mathsf{S}=\\{s\\}$_ then $b\leftarrow\zeta$;

9 else

10 $a\leftarrow\zeta$; $V^{\prime}\leftarrow\mathsf{S}\cap V_{T}$;

11

12 $\zeta\leftarrow(b+a)/2$;

13

14return _$W^{*}\leftarrow V^{\prime}$_ ;

Algorithm 3 Exact

###### Proof.

First of all we note that every min cut $(\mathsf{S},\mathsf{Z})$ should be
finite, since trivially the cut $(\\{s\\},V_{Z}\setminus\\{s\\})$ has a value
of the cut $\tau(V_{T})$131313Recall that for a directed and weighted flow
network, the cost of the cut $(\mathsf{S},\mathsf{Z})$ is the sum of the
weights on the outgoing edges from $\mathsf{S}$ to $\mathsf{Z}$. and such
value is finite. Fix a $(s,z)$-min cut $(\mathsf{S},\mathsf{Z})$ then let
$V^{\prime}=\mathsf{S}\cap V_{T}$. First of all note that if
$v_{H=(V_{H},E_{H})}\in\mathsf{S},v_{H}\in V_{\mathcal{H}}$ then $v\in
V^{\prime}$, for all $v\in V_{H}\subseteq V_{T}$ and therefore
$\mathcal{S}_{H}=\mathcal{S}_{V_{H}}\subseteq\mathcal{S}_{V^{\prime}}$ in $T$,
since every minimum cut is finite.

Let us consider a finite min-cut $(\mathsf{S}^{\prime},\mathsf{Z}^{\prime})$.
Let $V^{\prime}=\mathsf{S}^{\prime}\cap V_{T}$ and let $G[{V^{\prime}}]$ be
the induced subgraph of $V^{\prime}$ in $G_{T}$ and $T[V^{\prime}]$ the
induced subnetwork of $V^{\prime}$ in $T$. Let $C$ denote the cost of the cut,
i.e., sum of the outgoing weighted edges from $\mathsf{S}^{\prime}$ to
$\mathsf{Z}^{\prime}$. Since the minimum cut can only be finite, we have the
following:

$\displaystyle C(\mathsf{S}^{\prime},\mathsf{Z}^{\prime})$
$\displaystyle=C(\\{s\\},V_{\mathcal{H}}\cap\mathsf{Z}^{\prime})+C(\mathsf{S}^{\prime}\cap
V_{T},\\{t\\})$ (4) $\displaystyle=\sum_{v_{H}\in
V_{\mathcal{H}}\cap\mathsf{Z}^{\prime}}\tau(V_{H})+\sum_{v\in\mathsf{S}^{\prime}\cap
V_{T}}\zeta$ (5) $\displaystyle=\sum_{v_{H}\in
V_{\mathcal{H}}}\tau(V_{H})-\sum_{v_{H}\in
V_{\mathcal{H}}\cap\mathsf{S}^{\prime}}\left(\tau(V_{H})-\zeta|V^{\prime}|\right)$
(6)
$\displaystyle=\tau(V_{T})-\left(\tau(V^{\prime})-\zeta|V^{\prime}|\right)$

In the above derivation, Equation (4) follows from the definition of the cost
of a cut, and the fact that if $v_{H}\in\mathsf{S}^{\prime}$ then each vertex
$v\in V_{T}$ in $V_{H}$ is also in $\mathsf{S}^{\prime}$ since the min-cut is
finite. Equation (5) follows from the definition of $V^{\prime}$ and the fact
that
$V_{\mathcal{H}}=(V_{\mathcal{H}}\cap\mathsf{Z}^{\prime})\cup(V_{\mathcal{H}}\cap\mathsf{S}^{\prime})$.
To see why Equation (6) holds, let $V_{\mathcal{H}}^{\prime}\subseteq
V_{\mathcal{H}}$ and we have

(7) $\\!\\!\\!\sum_{v_{H=(V_{H},E_{H})}\in
V_{\mathcal{H}}^{\prime}}\\!\\!\\!\tau(V_{H})=\sum_{v_{H}\in
V_{\mathcal{H}}^{\prime}}\sum_{S\in\mathcal{S}_{V_{H}}}\tau(S)=\\!\\!\\!\sum_{S\in\mathcal{S}_{\cup_{v_{H}\in
V_{\mathcal{H}}^{\prime}}V_{H}}}\\!\\!\\!\tau(S).$

Note that the above holds since each vertex in $V_{\mathcal{H}}$ represents a
distinct $k$-CIS, i.e., the same vertex cannot represent two identical vertex
sets in the original network $G_{T}$. Given Equation (7), we now obtain
Equation (6) by combining $\mathcal{S}_{\cup_{v_{H}\in
V_{\mathcal{H}}}V_{H}}=\mathcal{S}_{V_{T}}$, the definition of $V^{\prime}$,
and the fact that given $V_{H}\subseteq V^{\prime}$ there exists $v_{H}\in
V_{\mathcal{H}}$ such that $v_{H}$ is in
$V_{\mathcal{H}}\cap\mathsf{S}^{\prime}$ since the cut is optimal, and
conversely, if a given vertex $v_{H}$ is in
$V_{\mathcal{H}}\cap\mathsf{S}^{\prime}$ then $V_{H}\subseteq V^{\prime}$ by
the finiteness of the minimum cut.

We are now ready to show that if $V^{\prime}\neq\emptyset$ then
$\tau(V^{\prime})-\zeta|V^{\prime}|\geq 0$. If
$\tau(V^{\prime})-\zeta|V^{\prime}|<0$, then by Equation (6) this min-cut
would be larger than the cut $C(\\{s\\},V_{Z}\setminus\\{s\\})$ contradicting
its optimality. Hence it holds that
$\zeta\leq\frac{\tau(V^{\prime})}{|V^{\prime}|}\leq\rho^{*}$.

Conversely, if $V^{\prime}=\emptyset$ then we show that $\tau(W)-\zeta|W|\leq
0$ for each $W\subseteq V_{T}$. Note that this is trivial if
$V_{\mathcal{H}}\cap\mathsf{S}^{\prime}=\emptyset$, so we will assume that the
set $V_{\mathcal{H}}\cap\mathsf{S}^{\prime}$ is not empty. Let for
contradiction $\tau(W)-\zeta|W|>0$ for a certain $W\subseteq V_{T}$. Let
$V_{\mathcal{H}}[W]$ be the set of vertices in $V_{\mathcal{H}}$ corresponding
to $k$-CIS between vertices of $W$ in $G_{T}$ with at least one
$\delta$-instance $S\in\mathcal{S}_{W}$, $\tau(S)>0$, for which it holds
$V_{\mathcal{H}}\cap\mathsf{S}^{\prime}=V_{\mathcal{H}}[W]$. Consider also the
cut $(\mathsf{S},\mathsf{Z})=(\\{s\\}\cup W\cup
V_{\mathcal{H}}[W],V_{Z}\setminus\\{\\{s\\}\cup W\cup V_{\mathcal{H}}[W]\\})$.
Since this cut is finite, by applying Equation (6) we get

$C(\mathsf{S},\mathsf{Z})=\tau(V_{T})-\left(\tau(W)-\zeta|W|\right)<\tau(V_{T}),$

obtaining a value of the cut that is smaller than the cut
$(\mathsf{S}^{\prime},\mathsf{Z}^{\prime})$, that is $\tau(V_{T})$ when
$V^{\prime}=\emptyset$. This contradicts the initial assumption that the min-
cut ($\mathsf{S}^{\prime},\mathsf{Z}^{\prime}$) is optimal. Hence, we have
that $\zeta\geq\frac{\tau(W)}{|W|}$ for all $W\subseteq V_{T}$, and hence
$\zeta\geq\rho^{*}$. ∎

Lemma F.1 proves that Algorithm 3 correctly identifies the optimal solution
$W^{*}$ by finding the optimal density $\rho^{*}$ through binary search. Next
we show how to determine when to stop the search.

###### Lemma F.2.

Given a temporal network $T=(V_{T},E_{T})$, let
$\tau_{\min}=\min_{S\in\mathcal{S}}\\{\tau(S)\\}$. Given two distinct and non-
empty vertex sets $V_{1},V_{2}\subseteq V_{T}$ such that
$\rho(V_{1})\neq\rho(V_{2})$, then it holds that

$\left|\frac{\tau(V_{1})}{|V_{1}|}-\frac{\tau(V_{2})}{|V_{2}|}\right|\geq\frac{\tau_{\min}}{n(n-1)}.$

###### Proof.

If $|V_{1}|=|V_{2}|$, it easy to see that
$|\tau(V_{1})/|V_{1}|-\tau(V_{2})/|V_{2}||\geq\tau_{\min}/n\geq\tau_{\min}/(n(n-1))$,
for $n\geq 2$, otherwise it holds
$|\tau(V_{1})/|V_{1}|-\tau(V_{2})/|V_{2}||\geq\tau_{\min}/(|V_{1}||V_{2}|)\geq\tau_{\min}/(n(n-1))$,
for $n\geq 2$. Therefore, the claim follows. ∎

By Lemma F.2, Algorithm 3 terminates in at most
$\mathcal{O}(\log{n}+\log(\tau(V_{T})/\tau_{\min}))$ steps of binary search,
since it explores the range $[0,\zeta=\tau(V_{T})]$, which is halved at each
step.141414Some optimization according to Fang et al. (2019) can be used to
reduce this range but it cannot improve the overall worst-case complexity. In
fact, let $x$ be the number of steps until termination, the claimed bound is
achieved by solving for $x$ the following equation

$\frac{\tau(V_{T})}{2^{x}}=\mathcal{O}\\!\left(\frac{\tau_{\min}}{n^{2}}\right).$

Time complexity. The execution time of Algorithm 3 is bounded by
$\mathcal{O}(T_{\mathrm{enum}}+T_{\mathrm{flow}}(\log(n)+\log(\tau(V)/\tau_{\min})))$,
where $T_{\mathrm{enum}}$ is the running time of enumerating all the
$\delta$-instances of a temporal motif $M$.151515We assume that $\tau(S)$ can
be computed in at most $\mathcal{O}(\ell)$ for each given $\delta$-instance
$S$. By using Mackey’s algorithm (Mackey et al., 2018) it holds that
$T_{\mathrm{enum}}=\mathcal{O}(m\hat{m}^{\ell-1})$, where $\hat{m}$ is the
maximum number of temporal edges of the temporal network $T$ in a time-
interval length $\delta$. The cost of each min-cut solution can be computed in
time $\mathcal{O}(n_{Z}m_{Z})$, where $Z$ is the flow network on which the
solution is found.161616More advanced algorithms may require smaller running
time. Therefore, $n_{Z}=\mathcal{O}(n+|\mathcal{H}|)$ and
$m_{Z}=\mathcal{O}(k|\mathcal{H}|+n)$; recall also that
$|\mathcal{H}|=\mathcal{O}(n^{k})$. Hence the cost of computing a single min
cut is $\mathcal{O}(k|\mathcal{H}|(n+|\mathcal{H}|)+n^{2})$. Therefore, the
final complexity of the algorithm is
$\mathcal{O}(m\hat{m}^{\ell-1}+(k|\mathcal{H}|(n+|\mathcal{H}|)+n^{2})(\log(n)+\log(\tau(V_{T})/\tau_{\min})))$,
which in general is prohibitive in most applications.

###  F.2. Greedy

In this section we present Greedy, a $1/k$-approximation algorithm for the
TMDS problem. In particular, Algorithm 4 is based on an extension of
Charikar’s algorithm for the edge densest-subgraph problem (Charikar, 2000).
Greedy removes vertices one at a time according to the minimum temporal motif
degree in the subset of vertices being examined. This will be done by first
computing the set $\mathcal{H}$, and then maintaining such set updated over
the peeling procedure, as we show next.

Algorithm description. Given a temporal network $T=(V_{T},E_{T})$ a temporal
motif $M$, a value of $\delta$ and the weighting function $\tau$, let $v\in
V_{T}$ let
$\mathcal{S}_{V_{T}}(v)\mathbin{=}\\{S:S\in\mathcal{S}_{V_{T}}\text{ and }v\in
S\\}$, that is the set of $\delta$-instances in the subnetwork induced by
$V_{T}$ in which $v\in V$ participates. Therefore, the temporal motif degree
(under weighting function $\tau$) of vertex $v\in V$ is
${d}_{V_{T}}^{\tau}(v)=\sum_{S\in\mathcal{S}_{V_{T}}(v)}\tau(S)$, and we write
${d}_{V_{T}}^{\tau}(v)$ when $M$ and $\delta$ are clear from the context. We
are ready to describe Algorithm 4, which first enumerates all
$\delta$-instances of the temporal motif $M$ in $T$ (line 4) and then
initializes two sets $W_{n}$ and $\mathcal{S}_{n}$, maintaining respectively
the vertex set of the network and its corresponding set of $\delta$-instances
(line 4). Entering the main loop (line 4), at iteration $i$ the algorithm
removes the vertex with the minimum temporal motif degree in the subnetwork
induced by $W_{i}$, updating the corresponding sets of remaining vertices and
$\delta$-instances (lines 4-4), and this is done by properly encoding the set
$\mathcal{H}$ (see the time complexity analysis for more details). The
algorithm returns as solution the set that maximizes the TMDS objective
function among all $n-k$ vertex sets examined. The following result
establishes the approximation ratio of Algorithm 4.