[a]Jannis Lang

# Precise SMEFT predictions for di-Higgs production

###### Abstract

We present results of precision calculations for di-Higgs production that
combine NLO QCD corrections with operators at canonical dimension six within
Standard Model Effective Field Theory (SMEFT). We discuss possible options for
operator contributions within a given EFT framework and sources of theory
uncertainties.

##  1 Introduction and discussion of relevant contributions

Despite its tremendous success in the description of the physics at collider
experiments, the Standard Model (SM) is commonly understood to be only an
effective theory at currently probed energies and precision. As the energy
range of experiments will not increase much in the near future, effects beyond
the SM (BSM) are to be observed in the precision domain. Potential BSM
deviations in the Higgs potential have not yet been investigated at high
precision, for which di-Higgs production is the key process.

The lack of direct BSM signals in the data suggests that the BSM degrees of
freedom are well separated from the electroweak (EW) scale, which is a
scenario consistently described in the framework of bottom-up effective field
theories (EFTs) in a model-agnostic way. Under the assumption of a decoupling
BSM scenario that respects the SM symmetries, the low energy effects are
expressed by the linear EFT realisation of Standard Model effective field
theory (SMEFT) [1, 2, 3]. The SMEFT Lagrangian is described by an expansion in
canonical dimension where higher order operators are suppressed by higher
powers of the scale of new physics $\Lambda$, i.e.

${\cal L}_{\text{SMEFT}}={\cal
L}_{\text{SM}}+\sum_{i}\frac{\mathcal{C}_{i}}{\Lambda^{2}}\mathcal{O}_{i}+\mathcal{O}\left(\Lambda^{-4}\right)\;,$
(1)

neglecting baryon- and lepton-number violating operators. For sufficiently
large $\Lambda$ the dominant BSM effects are expected to emerge from
dimension-6 operators.

We constrain our investigations to the gluon fusion channel due to the high
luminosity of gluons in proton-proton collisions, which leads to a cross
section that dominates the other main di-Higgs production channels by a factor
of 10 [4]. Moreover, we apply an exact flavour symmetry
$\mathcal{G}_{\text{flavour}}=U(2)_{q}\times U(2)_{u}\times U(3)_{d}$ that is
compatible with the five-flavour scheme of QCD. This choice also reflects the
importance of the top-quark for many concrete BSM realisations.

SMEFT predictions are evaluated in a mixed expansion in canonical dimension
and loops, which we combine with a tree-loop classification of Wilson
coefficients of the Warsaw basis based on the generic assumption of
renormalisability and weak coupling in the BSM sector [5, 6]. Thus, retaining
only CP-even operators, the leading SMEFT contribution originates from

$\displaystyle\Delta{\cal L}_{\text{SMEFT}}^{\text{lead}}$
$\displaystyle=\frac{\mathcal{C}_{H\Box}}{\Lambda^{2}}(\phi^{\dagger}\phi)\Box(\phi^{\dagger}\phi)+\frac{\mathcal{C}_{HD}}{\Lambda^{2}}(\phi^{\dagger}D_{\mu}\phi)^{\ast}(\phi^{\dagger}D^{\mu}\phi)+\frac{\mathcal{C}_{H}}{\Lambda^{2}}(\phi^{\dagger}\phi)^{3}$
(2)
$\displaystyle+\frac{\mathcal{C}_{tH}}{\Lambda^{2}}\left((\phi^{\dagger}{\phi})(\bar{Q}_{L}t_{R}\tilde{\phi})+\text{H.c.}\right)+\frac{\mathcal{C}_{HG}}{\Lambda^{2}}(\phi^{\dagger}\phi)\,G_{\mu\nu}^{a}G^{\mu\nu,a}\;,$

which has been calculated and studied at fixed order NLO QCD [7] for different
truncation options of the cross section. The combination with the subset of
contributions with additional suppression by a loop factor $(16\pi)^{-1}$
originating from

$\displaystyle\Delta{\cal L}_{\text{SMEFT}}^{\text{sublead}}$
$\displaystyle\supset\frac{\mathcal{C}_{tG}}{\Lambda^{2}}\left((\bar{Q}_{L}\sigma^{\mu\nu}T^{a}t_{R}\tilde{\phi})G^{a}_{\mu\nu}+\text{H.c.}\right)+\frac{\mathcal{C}_{tt}}{\Lambda^{2}}\bar{t}_{R}\gamma^{\mu}t_{R}\,\bar{t}_{R}\gamma_{\mu}t_{R}$
(3)
$\displaystyle+\frac{\mathcal{C}_{Qt}^{(1)}}{\Lambda^{2}}(\bar{Q}_{L}\gamma^{\mu}Q_{L})\,\bar{t}_{R}\gamma_{\mu}t_{R}+\frac{\mathcal{C}_{Qt}^{(8)}}{\Lambda^{2}}(\bar{Q}_{L}\gamma^{\mu}T^{a}Q_{L})\bar{t}_{R}\gamma_{\mu}T^{a}t_{R}$
$\displaystyle+\frac{\mathcal{C}_{QQ}^{(1)}}{\Lambda^{2}}(\bar{Q}_{L}\gamma^{\mu}Q_{L})(\bar{Q}_{L}\gamma_{\mu}Q_{L})+\frac{\mathcal{C}_{QQ}^{(8)}}{\Lambda^{2}}(\bar{Q}_{L}\gamma^{\mu}T^{a}Q_{L})(\bar{Q}_{L}\gamma_{\mu}T^{a}Q_{L})\;,$

has been described in Ref. [8]. For reference, we also list the relevant
Lagrangian terms of the non-linear EFT realisation (HEFT) contributing to di-
Higgs production

$\Delta{\cal
L}_{\text{HEFT}}=-m_{t}\left(c_{tth}\frac{h}{v}+c_{tthh}\frac{h^{2}}{v^{2}}\right)\,\bar{t}\,t-c_{hhh}\frac{m_{h}^{2}}{2v}h^{3}+\frac{\alpha_{s}}{8\pi}\left(c_{ggh}\frac{h}{v}+c_{gghh}\frac{h^{2}}{v^{2}}\right)\,G^{a}_{\mu\nu}G^{a,\mu\nu}\;,$
(4)

whose contributions have been thoroughly investigated in Refs. [9, 10].

##  2 Distributions of leading and subleading contributions

In this section we present sample diagrams of di-Higgs invariant mass
($m_{hh}$)-distributions generated using the POWHEG-BOX-V2 code ggHH_SMEFT [7,
8] and mention sources of theory uncertainties one needs to be aware of.

benchmark | $c_{hhh}$ | $c_{tth}$ | $c_{tthh}$ | $c_{ggh}$ | $c_{gghh}$ | $\mathcal{C}_{H;\,\text{kin}}$ | $\mathcal{C}_{H}$ | $\mathcal{C}_{tH}$ | $\mathcal{C}_{HG}$
---|---|---|---|---|---|---|---|---|---
SM | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
$1$ | $5.105$ | $1.1$ | $0$ | $0$ | $0$ | $4.95$ | $-6.81$ | $3.28$ | $0$
Table 1: Definition of benchmark scenarios (with
$\mathcal{C}_{H;\,\text{kin}}=\mathcal{C}_{H\Box}-\mathcal{C}_{HD}/4$).
Benchmark point 1 refers to the set in Refs. [7, 11], which is an updated
version of Ref. [12]. The parameters were originally derived in HEFT and
(naively) translated to SMEFT for $\Lambda=1\;$TeV.

In Fig.1, the distributions for benchmark 1 defined in Table 1 are displayed
for $\Lambda=1,\,2\;$TeV and for the linear (a) and linear+quadratic (b)
truncation options of the cross section. The SM and HEFT distributions are
shown for comparison.

Figure 1:  Differential cross section distributions for the invariant mass
$m_{hh}$ for benchmark point 1 defined in Table 1. Left: $\Lambda=1$ TeV,
right: $\Lambda=2$ TeV.

The negative cross section for truncation option (a) demonstrates that the
naive translation from a valid HEFT point to SMEFT leads to parameter points
incompatible with a truncation at canonical dimension-6, highlighting the
importance to study HEFT and SMEFT separately. Moreover, approaching the SM
configuration with increasing value of $\Lambda$ shows a convergence of the
difference between the truncation options, which reflects the expected
behaviour of being a qualitative proxy for the estimation of the uncertainty
related to the SMEFT truncation.

In Fig 2 we present the variation of $\mathcal{C}_{tG}$ and
$\mathcal{C}_{Qt}^{(1)}$ using conservative bounds from marginalised fits of
Ref. [13].

Figure 2:  Differential cross section for a variation of $\mathcal{C}_{tG}$
(left) and $\mathcal{C}_{Qt}^{(1)}$ (right) w.r.t. the SM
$m_{hh}$-distribution. The ranges are taken from Ref. [13] based on a
marginalised ${\cal O}(\Lambda^{-2})$ fit.

Variations of the other Wilson coefficients in Eq. (3) can be found in Ref.
[8] which also discusses the effect of different $\gamma_{5}$ schemes
following the derivation of Ref. [14]. The observed deviations from the SM
curve together with the study of Ref. [15] demonstrate the potential for
improved limits for $\mathcal{C}_{Qt}^{(1)}$ and $\mathcal{C}_{Qt}^{(8)}$ in
global fits when indirect effects in single and di-Higgs production are
included.

In the following, we briefly list the relevant sources of theory uncertainties
which are described in more detail in Ref. [11]:

SMEFT truncation:

There is no quantitative prescription available yet [16]. It is possible to
get a qualitative picture comparing different truncation options as proxy for
each EFT point [7].

Scale uncertainty:

The scale uncertainty is assessed by a variation of renormalisation and
factorisation scales around the central choice $\mu_{0}=m_{hh}/2$.

PDF+$\alpha_{s}$ uncertainty:

Estimated to be about $\pm 3\%$ for $\sqrt{s}=13$ and $14\;$TeV, which appears
to be robust for $c_{hhh}$-variations [17].

$m_{t}$ renormalisation scheme:

Comparison between on-shell and $\overline{\text{MS}}$ for different scales
results in ${}_{-18\%}^{+4\%}$ for the SM at $\sqrt{s}=13\;$TeV, a dependency
on $c_{hhh}$ and bin width has been observed [18, 19].

EW corrections:

Have been calculated for SM [20, 21], but are not translatable to SMEFT.

NLO QCD virtual corrections:

The two-loop virtual corrections are encoded in numerical grids based on the
distributions of events in the SM. For SMEFT scenarios where the low-$m_{hh}$
region or the tail of the $m_{hh}$-distribution is much more populated than in
the SM, large statistical uncertainties can arise due to an insufficient
number of grid points in the region.

##  3 Conclusions

We presented results of state-of-the-art predictions for di-Higgs production
in SMEFT, pointed out different options for the truncation of the EFT
expansion and the inclusion of subleading operators and briefly mentioned the
remaining theory uncertainties. An important outstanding task is the inclusion
renormalisation group evolution effects, as they are expected to be sizable
following recent results for other processes [22, 23, 24].

## Acknowledgements

This research was supported by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) under grant 396021762 - TRR 257.

## References

  * [1] W. Buchmüller and D. Wyler, _Effective Lagrangian Analysis of New Interactions and Flavor Conservation_ , _Nucl. Phys. B_ 268 (1986) 621.
  * [2] B. Grzadkowski, M. Iskrzynski, M. Misiak and J. Rosiek, _Dimension-Six Terms in the Standard Model Lagrangian_ , _JHEP_ 10 (2010) 085 [1008.4884].
  * [3] I. Brivio and M. Trott, _The Standard Model as an Effective Field Theory_ , _Phys. Rept._ 793 (2019) 1 [1706.08945].
  * [4] J. Alison et al., _Higgs boson potential at colliders: Status and perspectives_ , _Rev. Phys._ 5 (2020) 100045 [1910.00012].
  * [5] C. Arzt, M.B. Einhorn and J. Wudka, _Patterns of deviation from the standard model_ , _Nucl. Phys. B_ 433 (1995) 41 [hep-ph/9405214].
  * [6] G. Buchalla, G. Heinrich, C. Müller-Salditt and F. Pandler, _Loop counting matters in SMEFT_ , _SciPost Phys._ 15 (2023) 088 [2204.11808].
  * [7] G. Heinrich, J. Lang and L. Scyboz, _SMEFT predictions for $gg\to hh$ at full NLO QCD and truncation uncertainties_, _JHEP_ 08 (2022) 079 [2204.13045].
  * [8] G. Heinrich and J. Lang, _Combining chromomagnetic and four-fermion operators with leading SMEFT operators for $gg\to hh$ at NLO QCD_, 2311.15004.
  * [9] G. Buchalla, M. Capozi, A. Celis, G. Heinrich and L. Scyboz, _Higgs boson pair production in non-linear Effective Field Theory with full $m_{t}$-dependence at NLO QCD_, _JHEP_ 09 (2018) 057 [1806.05162].
  * [10] G. Heinrich, S.P. Jones, M. Kerner and L. Scyboz, _A non-linear EFT description of $gg\to HH$ at NLO interfaced to POWHEG_, _JHEP_ 10 (2020) 021 [2006.16877].
  * [11] L. Alasfar et al., _Effective Field Theory descriptions of Higgs boson pair production_ , 2304.01968.
  * [12] M. Capozi and G. Heinrich, _Exploring anomalous couplings in Higgs boson pair production through shape analysis_ , _JHEP_ 03 (2020) 091 [1908.08923].
  * [13] SMEFiT collaboration, _Combined SMEFT interpretation of Higgs, diboson, and top quark data from the LHC_ , _JHEP_ 11 (2021) 089 [2105.00006].
  * [14] S. Di Noi, R. Gröber, G. Heinrich, J. Lang and M. Vitti, _On $\gamma_{5}$ schemes and the interplay of SMEFT operators in the Higgs-gluon coupling_, 2310.18221.
  * [15] L. Alasfar, J. de Blas and R. Gröber, _Higgs probes of top quark contact interactions and their interplay with the Higgs self-coupling_ , _JHEP_ 05 (2022) 111 [2202.02333].
  * [16] I. Brivio et al., _Truncation, validity, uncertainties_ , 2201.04974.
  * [17] _LHC Higgs working group, twiki page LHC Higgs WG4 group_ , 2022.
  * [18] J. Baglio, F. Campanario, S. Glaus, M. Mühlleitner, J. Ronca and M. Spira, _$gg\to HH$ : Combined uncertainties_, _Phys. Rev. D_ 103 (2021) 056002 [2008.11626].
  * [19] E. Bagnaschi, G. Degrassi and R. Gröber, _Higgs boson pair production at NLO in the Powheg approach and the top quark mass uncertainties_ , _Eur. Phys. J. C_ 83 (2023) 1054 [2309.10525].
  * [20] H.-Y. Bi, L.-H. Huang, R.-J. Huang, Y.-Q. Ma and H.-M. Yu, _Electroweak corrections to double Higgs production at the LHC_ , 2311.16963.
  * [21] J. Davies, K. Schönwald, M. Steinhauser and H. Zhang, _Next-to-leading order electroweak corrections to $gg\to HH$ and $gg\to gH$ in the large-mt limit_, _JHEP_ 10 (2023) 033 [2308.01355].
  * [22] M. Battaglia, M. Grazzini, M. Spira and M. Wiesemann, _Sensitivity to BSM effects in the Higgs p T spectrum within SMEFT_, _JHEP_ 11 (2021) 173 [2109.02987].
  * [23] R. Aoude, F. Maltoni, O. Mattelaer, C. Severi and E. Vryonidou, _Renormalisation group effects on SMEFT interpretations of LHC data_ , 2212.05067.
  * [24] S. Di Noi and R. Gröber, _Renormalisation group running effects in $pp\to t\bar{t}h$ in the Standard Model Effective Field Theory_, 2312.11327.


# The GraphTempo Framework for Exploring the Evolution of a Graph through
Pattern Aggregation

Evangelia Tsoukanara
Department of Applied Informatics,
University of Macedonia, Greece
<EMAIL_ADDRESS>Georgia Koloniari
Department of Applied Informatics,
University of Macedonia, Greece
<EMAIL_ADDRESS>Evaggelia Pitoura
Department of Computer Science &
Engineering, University of Ioannina, Greece
<EMAIL_ADDRESS>Peter Triantafillou
Department of Computer Science,
University of Warwick, Coventry, UK
<EMAIL_ADDRESS>
###### Abstract

When the focus is on the relationships or interactions between entities,
graphs offer an intuitive model for many real-world data. Such graphs are
usually large and change over time, thus, requiring models and strategies that
explore their evolution. We study the evolution of aggregated graphs and
introduce the GraphTempo model that allows temporal and attribute aggregation
not only on node level by grouping individual nodes, but on a pattern level as
well, where subgraphs are grouped together. Furthermore, We propose an
efficient strategy for exploring the evolution of the graph based on
identifying time intervals of significant growth, shrinkage or stability.
Finally, we evaluate the efficiency and effectiveness of the proposed approach
using three real graphs.

##  1 Introduction

Graphs provide an intuitive model for representing relationships and
interactions between entities. Their use expands a variety of domains ranging
from social and contact networks to road and biological networks. Most such
graphs are usually large and dynamic, thus requiring efficient models to
capture their evolution and identify trends or events of interest.

Instead of studying the evolution of individual graph nodes, we consider
aggregate graphs that offer a summarized view of the network and allow us to
study evolution at a global level. There has been a lot of work on aggregation
of static graphs e.g., [28, 4], and more recently on dynamic graphs, where
problems such as alternative temporal graph models [11], [18], [1], temporal
paths evaluation [5], graph analytics [14] and visualization [22] have been
addressed. In this paper, we focus on aggregate graph evolution and propose
novel strategies for detecting periods of significant stability, growth or
shrinkage.

We consider temporal attributed graphs where nodes have properties whose
values may or not change with time, and introduce the GraphTempo model for
aggregating such graphs and exploring their evolution. Our model supports
three types of aggregation: temporal aggregation that enables us to study a
graph at different levels of temporal resolution, attribute aggregation that
groups nodes that share common attribute values and, pattern aggregation that
extends attribute aggregation by grouping together subgraphs.

To motivate our work, consider a contact network modeling the interactions of
students and teachers to study the spread of an infectious disease [10]. As
students tend to interact with others of their own grade and mostly within
their class, studying the aggregated graph based on time and class attribute
enables us to identify stable relationships between students of the same class
that can be seen as isolation bubbles that hinder disease spread, while
periods showing growth between interaction of students of different classes
identifies time periods, such as breaks that pose a higher risk in disease
spread. Furthermore, extending our study to larger groups of students, for
instance by considering three students that form a pattern of a closed
triangle with their interactions and aggregating the graph by grouping
triangles of students of the same class, can offer us further intuitions on
the size of the isolation bubbles.

To support temporal aggregation we define set based temporal operators using
either tight intersection semantics or more relaxed union semantics. We
discern between distinct and non-distinct aggregation and provide algorithms
for all types of aggregation. We also propose optimizations that reuse
evaluated aggregate graphs to compute other aggregate graphs more efficiently
without having to access the original temporal graphs.

With regards to evolution, we define three types of events pertaining to the
growth, stability and shrinkage of the graph. We define the evolution graph
that captures the three types of evolution events by overlaying three
different graphs defined using appropriate temporal operators for each event
type. To explore graph evolution, we define the novel problem of finding pairs
of intervals $(\mathcal{T}_{1},\mathcal{T}_{2})$ such that at least $k$ events
of interest have occurred between $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$.
Since the number of candidate interval pairs can grow exponentially, we
propose an efficient exploration strategy that considers a fixed reference
point and utilizes intersection and union semantics to extend intervals while
exploiting monotonicity to further prune the exploration space. Our
experimental evaluation utilizes three diverse real world datasets to showcase
both the efficiency and the effectiveness of the proposed approach.

The rest of the paper is structured as follows. In Section 2, we define the
three types of graph aggregation, and the evolution graph, and in Section 3,
our problem of exploring graph evolution and the exploration strategies. In
Section 4, we present our algorithms, and in Section 5 our experimental
results. Section 6 summarizes related work, while Section 7 offers
conclusions.

##  2 The GraphTempo Model

To define a temporal graph model, we first consider a linearly ordered
discrete time domain consisting of time points $t$, where the linear ordering
signifies that if $t_{i}<t_{i+1}$ then $t_{i}$ happens before $t_{i+1}$. Given
$t_{i},t_{j},t_{i}<t_{j}$, a time interval $\mathcal{T}$ is defined as
$\mathcal{T}=[t_{i},t_{j}]$, and includes all times points $t$ from $t_{i}\leq
t\leq t_{j}$. The length of the interval, $length(\mathcal{T})$ is defined as
the number of time points $t\in\mathcal{T}$. We assume an interval-based
definition, where an attributed temporal graph in a time interval
$\mathcal{T}$ is a graph whose elements, i.e., nodes, edges and attributes are
annotated with the set of intervals in $\mathcal{T}$ during which they were
valid.

######  Definition 2.1 (Temporal Attributed Graph).

A temporal attributed graph in $\mathcal{T}$ is a graph $G(V,E,\tau u,\tau
e,A)$ where $V$ is the set of nodes and $E$ is the set of edges $(u,v)$ with
$u,v$ $\in$ $V$. Each node in $V$ is associated with a timestamp $\tau
u:V\rightarrow\mathcal{T}$ where $\tau u(u)$ is the set of intervals during
which $u$ exists. Similarly each edge $e$ in $E$ is associated with a
timestamp $\tau e:E\rightarrow\mathcal{T}$ where $\tau e(e)$ is the set of
intervals during which $e$ exists. $A$ is a set of arrays, one for each of the
set of $n$ attributes associated with vertices of $V$. That is, for each $u\in
V$ and $t\in\tau u(u)$, there is an array,
$A(u,t)=\\{A^{1}(u,t),A^{2}(u,t)\dots A^{k}(u,t)\\}$, where $A^{i}(u,t)$
denotes the value of $u$ at time $t$ $\in\tau u(u)$ on the $i$-th attribute.

An attribute $A^{i}$ is called static, if its value does not change with time,
i.e., $A^{i}(u,t)=A^{i}(u,t^{\prime})$, $\forall u\in V$ and $\forall
t,t^{\prime}\in\tau(u)\subseteq T$, and time-varying otherwise.

Figure 1 depicts an example of a temporal co-authorship attributed graph in
time interval $\mathcal{T}=[t_{0},t_{2}]$. The nodes have two attributes,
“Gender”, a static categorical attribute with values $\\{m,f\\}$ and
“#Publications”, a time-varying numerical attribute.

Figure 1: A temporal attributed graph. Figure 2: Union graph of the graph of
Fig. 1 in $[t_{0},t_{1}]$.

###  2.1 Temporal Aggregation

To define temporal attributed graphs in intervals of different length and
combinations of intervals, we introduce temporal aggregation.

We first define an auxiliary operator, project, that defines a subgraph of the
original temporal graph in specific time intervals.

######  Definition 2.2 (Time Project Operator).

The projection $G[\mathcal{T}_{1}]$ of $G$ in
$\mathcal{T}_{1}\subseteq\mathcal{T}$ is a temporal attributed graph in
$\mathcal{T}_{1}$ $G[\mathcal{T}_{1}](V_{1},E_{1},\tau u_{1},\tau
e_{1},A_{1})$, where $V_{1}$ includes all nodes $u\in V$ for which
${\mathcal{T}_{1}}\subseteq\tau u(u)$, $E_{1}$ all edges $e\in E$ for which
${\mathcal{T}_{1}}\subseteq\tau e(e)$, and $\forall u\in V_{1}$, $\tau
u_{1}(u)=\tau u(u)\cap\mathcal{T}_{1}$, and $\forall e\in E_{1}$, $\tau
e_{1}=\tau e(e)\cap\mathcal{T}_{1}$ and $A_{1}\subseteq A$ includes all
$A(u,t)$ for which $u\in V_{1}$ and $t\in\tau u_{1}(u)$.

We provide operators that given two sets of time intervals $\mathcal{T}_{1}$
and $\mathcal{T}_{2}$, they output the graph with all elements that exist in
$\mathcal{T}_{1}$ or $\mathcal{T}_{2}$ (union), in both $\mathcal{T}_{1}$ and
$\mathcal{T}_{2}$ (intersection), or in $\mathcal{T}_{1}$ and not
$\mathcal{T}_{2}$ (difference). In particular:

  * •

union ($\cup$) defines graph
$G[\mathcal{T}_{1}\cup\mathcal{T}_{2}](V_{\cup},E_{\cup},\tau u_{\cup},$ $\tau
e_{\cup},A_{\cup})$, where $V_{\cup}=\\{u|(\tau
u(u)\cap(\mathcal{T}_{1}\cup\mathcal{T}_{2})\neq\emptyset\\}$,
$E_{\cup}=\\{e|(\tau
u(u)\cap(\mathcal{T}_{1}\cup\mathcal{T}_{2})\neq\emptyset\\}$, $\forall u\in
V_{\cup}$, $\tau u_{\cup}(u)=\tau
u(u)\cap(\mathcal{T}_{1}\cup\mathcal{T}_{2})$, $\forall e\in E_{\cup}$, $\tau
e_{\cup}(e)=\tau e(e)\cap(\mathcal{T}_{1}\cup\mathcal{T}_{2})$ and $A_{\cup}$
includes all $A(u,t)$ for which $u\in V_{\cup}$ and $t\in\tau u_{\cup}(u)$.

  * •

intersection ($\cap$) defines graph
$G[\mathcal{T}_{1}\cap\mathcal{T}_{2}](V_{\cap},E_{\cap},$ $\tau u_{\cap},\tau
e_{\cap},A_{\cap})$, where $V_{\cap}=\\{u|(\tau
u(u)\cap\mathcal{T}_{1}\neq\emptyset)\textit{ and }(\tau
u(u)\cap\mathcal{T}_{2}\neq\emptyset)\\}$, $E_{\cap}=\\{e|(\tau
e(e)\cap\mathcal{T}_{1}\neq\emptyset)\textit{ and }(\tau
e(e)\cap\mathcal{T}_{2}\neq\emptyset)\\}$, $\forall u\in V_{\cap}$, $\tau
u_{\cap}(u)=\tau u(u)\cap(\mathcal{T}_{1}\cup\mathcal{T}_{2})$, $\forall e\in
E_{\cap}$, $\tau e_{\cap}=\tau e(e)\cap(\mathcal{T}_{1}\cup\mathcal{T}_{2})$
and $A_{\cap}$ includes all $A(u,t)$ for which $u\in V_{\cap}$ and $t\in\tau
u_{\cap}(u)$.

  * •

difference ($-$) between $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ that defines
graph $G[\mathcal{T}_{1}-\mathcal{T}_{2}](V_{-},E_{-},\tau u_{-},\tau
e_{-}A_{-})$, where $V_{-}=\\{u|(\tau
u(u)\cap\mathcal{T}_{1}\neq\emptyset)\textit{ and }((\tau
u(u)\cap\mathcal{T}_{2}=\emptyset)\textit{ or }(\exists(u,v)\in E_{-})\\}$,
$E_{-}=\\{u|(\tau e(e)\cap\mathcal{T}_{1}\neq\emptyset)\textit{ and }(\tau
e(e)\cap\mathcal{T}_{2}=\emptyset)\\}$, $\forall u\in V_{-}$, $\tau
u_{-}(u)=\tau u(u)\cap\mathcal{T}_{1}$, $\forall e\in E_{-}$, $\tau e_{-}=\tau
e(e)\cap\mathcal{T}_{1}$ and $A_{-}$ includes all $A(u,t)$ for which $u\in
V_{-}$ and $t\in\tau u_{-}(u)\cup\tau e_{-}(u,v)$.

Figure 2 depicts the union graph $G_{\cup}$ of the temporal graph of Fig. 1
for $\mathcal{T}_{1}=[t_{0},t_{0}]$ and $\mathcal{T}_{2}=[t_{1},t_{1}]$.

Temporal aggregation also enables us to study the changes that occur in a
graph through time. Given $G$ and two sets of time intervals $\mathcal{T}_{1}$
and $\mathcal{T}_{2}$, its evolution from $\mathcal{T}_{1}$ to
$\mathcal{T}_{2}$ is captured by the following three graphs:

  * •

$G[\mathcal{T}_{1}\cap\mathcal{T}_{2}]$ with entities that exist in both
$\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ and capture stability,

  * •

$G[\mathcal{T}_{1}-\mathcal{T}_{2}]$, with entities that exist in
$\mathcal{T}_{1}$ but not $\mathcal{T}_{2}$ and capture shrinkage, and

  * •

$G[\mathcal{T}_{2}-\mathcal{T}_{1}]$, with entities that did not exist in
interval $\mathcal{T}_{1}$ but appear in $\mathcal{T}_{2}$ and capture growth.

Overlaying the three graphs, we represent them as one evolution graph as shown
in Fig. 3(a) depicting the evolution of the graph of Fig.1 from
$[t_{0},t_{0}]$ to $[t_{1},t_{1}]$, where labels $S$, $G$ and $R$
differentiate between entities with stability, growth and shrinkage
respectively.

(a)

(b)

(c)

Figure 3: (a) Evolution graph on (Gender, #Publications), (b) its aggregation,
and (c) triangle-based evolution graph aggregation on Gender for $t_{0}$,
$t_{1}$ of the graph of Fig. 1.

(a) $t_{0}$

(b) $t_{1}$

(c) $t_{2}$

(d) $t_{0}$

(e) $t_{1}$

Figure 4: Time point aggregate (a-c) graphs on (gender, #publications) and
(d-e) tri-graphs on gender for the graph of Fig.1.

###  2.2 Graph Aggregation

Besides temporal aggregation, we define graph or attribute aggregation by
grouping nodes based on (some of) their attribute values, while taking network
structure into account. So, each aggregate node (node in the aggregate graph)
corresponds to a set of the original nodes, and aggregate edges are built
based on the interactions of the aggregate nodes in the original graph.

######  Definition 2.3 (Graph Aggregation).

Given a temporal attributed graph $G(V,E,\tau u,\tau e,A)$ in $\mathcal{T}$,
and $n$ aggregate attributes, $1\leq n\leq k$,
$A^{\prime}_{1},A^{\prime}_{2},..,A^{\prime}_{n}\in A$, the aggregated graph
$G^{\prime}$ is defined as a weighted graph
$G^{\prime}(V^{\prime},E^{\prime},w_{V^{\prime}},w_{E^{\prime}},A^{\prime})$,
where for each distinct tuple ($A^{1}(u,t),A^{2}(u,t),\dots,A^{n}(u,t)$),
$u\in V$ and $t\in\tau u(u)$, there is a node $u^{\prime}\in V^{\prime}$ with
$A^{\prime i}(u^{\prime})=A^{i}(u,t),\forall i,1\leq i\leq n$, and there is an
edge $e^{\prime}\in E^{\prime}$ between $u^{\prime},v^{\prime}\in V^{\prime}$,
if and only if $\exists e\in E$ between nodes $u,v\in V$ with $A^{\prime
i}(u^{\prime})=A^{i}(u,t)$ and $A^{\prime i}(v^{\prime})=A^{i}(v,t),\forall
i,1\leq i\leq n$. The weights $w_{V^{\prime}}$ and $w_{E}$ are aggregate
functions $f_{V}$ and $f_{E}$ defined upon nodes and edges respectively.

We use COUNT as our aggregation function for both nodes and edges, in the rest
of this paper, and discern between distinct aggregation (denoted as DIST) and
non-distinct aggregation (denoted as ALL). Distinct aggregation counts unique
nodes and edges of the original graph, while, in non-distinct aggregation,
duplicates are not identified and counted each time they appear.

Figure 4(a-c) depicts the aggregate graphs on gender and publications of the
projections of the graph of Fig. 1 in $t_{0},t_{1}$ and $t_{2}$ respectively.
As we show aggregate graphs on time points, there is no difference between
distinct and non-distinct aggregation. We can see the difference in Fig.
5(a-b) that shows $G^{\prime}_{DIST}$ (Fig. 5(a)) and $G^{\prime}_{ALL}$ (Fig.
5(b)) for the union graph of Fig. 2. The weight for node ‘f,1’, of female
authors with 1 publication, in $G^{\prime}_{DIST}$ is 3, as 3 distinct nodes
appear with this attribute value combination in the union graph, while in
$G^{\prime}_{ALL}$ it is 5, as there are 5 total appearances of this
combination in the union graph.

Aggregation can be applied not only by grouping single nodes together, but
subgraphs that match a specific pattern as well. For instance, we may be
interested in closed triangles (i.e., cliques of size 3), and group them based
on the attribute values of the nodes that form them.

Let us define a pattern $P$, as a non-attributed weakly connected subgraph,
and let $p$ denote the number of nodes forming the subgraph. Graph aggregation
can then be defined on patterns so that all subgraphs in $G$ that match $P$
(i.e. have the same structure) are grouped based on the attribute values of
the nodes that belong to them, so that for $n$ aggregate attributes, each
group of subgraphs corresponds to a distinct combination of $p*n$ attribute
values.

######  Definition 2.4 (Pattern Aggregation).

Given a temporal attributed graph $G(V,E,\tau u,\tau e,A)$ in $\mathcal{T}$,
structural pattern $P$ and $n$ aggregation attributes, $1\leq n\leq k$, the
aggregated graph $G^{\prime}_{P}$ is defined as an undirected weighted graph
$G^{\prime}_{P}(V^{\prime},E^{\prime},w_{V^{\prime}},w_{E^{\prime}},A^{\prime})$,
where there is a node $v^{\prime}\in V^{\prime}$ for each group of subgraphs
matching $P$ in the original graph whose nodes have the same $p*n$ attribute
values forming $A^{\prime}(v^{\prime})$, and there is an edge $e^{\prime}\in
E^{\prime}$ between $u^{\prime},v^{\prime}\in V^{\prime}$, if and only if any
subgraphs belonging to the groups of $u^{\prime}$ and $v^{\prime}$ in $G$
share at least one common node. The weights $w_{V^{\prime}}$ and
$w_{E^{\prime}}$ are aggregate functions defined on the patterns and their
common nodes in $G$.

We use COUNT as our aggregation function, similarly to graph aggregation.

Figure 4(d-e) shows the aggregate graphs when aggregating based on patterns
consisting of undirected triangles and gender. In $t_{0}$, the aggregate graph
consists of a single node ‘ffm’ that corresponds to triangles formed by 2
female and 1 male author, since in the graph of Fig. 1, there are two such
triangles $u_{1},u_{2},u_{4}$ and $u_{1},u_{3},u_{4}$. As the two triangles
share node $u_{1}$ there is a self-loop in the aggregate graph. In $t_{1}$,
besides the ‘ffm’ node that corresponds to $u_{1},u_{2},u_{4}$, there is also
a ‘fff’ node corresponding to $u_{2},u_{4},u_{5}$, while the aggregate graph
for $t_{2}$ is empty, as no triangles are formed in $t_{2}$ in the original
graph. In Fig. 5(c-d), we can see the same pattern aggregation for the union
graph of Fig. 2. In Fig. 5(c), the weight of node ‘ffm’ is 2 as there are 2
distinct triangles formed in the union graph, while in Fig. 5(d) it is 3 as
$u_{1},u_{2},u_{4}$ appears in both time points.

(a) $G^{\prime}_{DIST}$

(b) $G^{\prime}_{ALL}$

(c) $G^{\prime}_{DIST}$

(d) $G^{\prime}_{ALL}$

Figure 5: Aggregate (a-b) graphs on (gender, #publications) and (c-d)
triangle-based graphs on gender for the graph of Fig. 2.

As evolution is captured by three temporal attributed graphs, aggregation may
be applied as well to provide a concrete view of graph evolution. The three
graphs representing graph evolution are aggregated and overlaid, while
different weights corresponding to each entity are used so as to discern
between growth, shrinkage and stability. Figure 3(b) depicts the aggregation
of the evolution graph of Fig. 3(a), where we can discern the weights for
stability, growth and shrinkage. For instance, node ‘f,1’ has: a) stability
weight 1, as it had 1 stable appearance on node $u_{2}$ at both $t_{0}$ and
$t_{1}$, b) growth weight 0, because no new appearance of $(f,1)$ occurs and
c) shrinkage weight 1, because one appearance on $u_{3}$ at $t_{0}$ is removed
in $t_{1}$. Similarly, Fig. 3(c) shows the triangle-based aggregate evolution
graph of Fig. 3(a), where for instance node ‘ffm’ has stability weight 1, as
$u_{2},u_{1},u_{4}$ remains at both $t_{0}$ and $t_{1}$, growth weight 0, and
shrinkage weight 1 as $u_{1},u_{4},u_{3}$ at $t_{0}$ disappears in $t_{1}$.

##  3 Exploration

We will now explore the evolution graph to detect interesting events through
time. We are interested in three event types, namely growth, shrinkage and
stability which correspond respectively to additions, deletions or persistence
of graph elements, e.g., edges , nodes or patterns and their connections. We
want to study different time granularities and different aggregation
attributes both on the individual node and pattern level.

###  3.1 Union and Intersection Semantics

We study the evolution of the graph between two sets of time intervals
($\mathcal{T}_{i}$, $\mathcal{T}_{j}$) by studying the corresponding aggregate
graphs of these intervals. Our goal is to detect interesting interval pairs
such that many elements have been added (growth), deleted (shrinkage) or
remained (stability) between $\mathcal{T}_{i}$ and $\mathcal{T}_{j}$.

Since the number of potential sets of intervals and corresponding aggregate
graphs is exponential, we need a way to efficiently explore the corresponding
search space. We start from intervals consisting of single time points, i.e.,
$\mathcal{T}_{i}=[t_{i},t_{i}]$. If we consider $\mathcal{T}_{i}$ as the
elements of a set $\mathcal{T}$, we may construct the lattice of the powerset
$\mathcal{T}$. Since we want to extend intervals based on combining successive
intervals, we only focus on a sub lattice of the powerset lattice of
$\mathcal{T}$, that is the tree that combines at each level $t$ of the lattice
two elements of the previous level $t-1$ if they differ only by one element.
As a powerset lattice is defined on union and intersection set operators, it
follows by the definitions of the temporal operators union and intersection,
that the graphs defined on the time intervals of the sub lattice also form a
sub lattice with respect to these operations.

######  Definition 3.1 (Monotonically Increasing/Decreasing).

Given intervals $\mathcal{T}_{k},\mathcal{T}_{i},\mathcal{T}_{j}$ such that
$\mathcal{T}_{i}\subseteq\mathcal{T}_{j}$ and aggregate graphs
$G_{i}(V_{i},E_{i},W_{V_{i}},W_{E_{i}},A_{i})$ and
$G_{j}(V_{j},E_{j},W_{V_{j}},W_{E_{j}},A_{j})$ defined as
$G_{i}[\mathcal{T}_{k}\cdot\mathcal{T}_{i}]$ and
$G_{j}[\mathcal{T}_{k}\cdot\mathcal{T}_{j}]$ respectively, temporal
aggregation w.r.t operator $(\cdot)$, is defined as:

  * •

monotonically increasing or increasing if it holds that (i) $\forall v\in
V_{j}$, if $v\in V_{i}$ then $w_{V_{i}}(v)\leq w_{V_{j}}(v)$, and (ii)
$\forall e\in E_{j}$, if $e\in E_{i}$ then $w_{E_{i}}(e)\leq w_{E_{j}}(e)$,
and

  * •

monotonically decreasing or decreasing if it holds that (i) $\forall v\in
V_{j}$, if $v\in V_{i}$ then $w_{V_{i}}(v)\geq w_{V_{j}}(v)$, and (ii)
$\forall e\in E_{j}$, if $e\in E_{i}$ then $w_{E_{i}}(e)\geq w_{E_{j}}(e)$.

Regarding union and intersection semantics it easily follows from their
definition that:

######  Lemma 1.

Temporal aggregation is monotonically increasing with union and monotonically
decreasing with intersection.

Thus, expanding intervals with union increases the size of the aggregate
graphs and the number of events we find, while expanding with intersection
reduces both the size of the graph and the event. Thus, the highest number of
events of interest are detected when considering the largest intervals with
union, and the smallest with intersection. Consequently, it is interesting to
detect the minimal or maximal interval pairs at which events occur depending
on the use of union or intersection respectively.

######  Definition 3.2 (Minimal/Maximal Interval Pair).

An interval pair $\mathcal{T}_{i},\mathcal{T}_{j}$ for which a number $k$ of
events occurred from $\mathcal{T}_{i}$ to $\mathcal{T}_{j}$, is defined as:

  * •

minimal if for the same
$\mathcal{T}_{i},\nexists\mathcal{T}_{j^{\prime}}\subset\mathcal{T}_{j}$ for
which $k^{\prime}\geq k$ events occurred from $\mathcal{T}_{i}$ to
$\mathcal{T}_{j^{\prime}}$, and

  * •

maximal if for the same
$\mathcal{T}_{i},\nexists\mathcal{T}_{j^{\prime}}:\mathcal{T}_{j}\subset\mathcal{T}_{j^{\prime}}$
for which $k^{\prime}\geq k$ events occurred from $\mathcal{T}_{i}$ to
$\mathcal{T}_{j^{\prime}}$.

Based on the above, we define our problem as follows.

######  Definition 3.3 (Problem Definition).

Given an attributed graph $G$, a time period $\mathcal{T}$ and a user-defined
threshold $k$, find the minimal and maximal interval pairs in which at least
$k$ events of either stability, growth or shrinkage occur.

###  3.2 Stability

Let us focus on the stability issue first. Given two time intervals
$\mathcal{T}_{old}$ and $\mathcal{T}_{new}$, where $\mathcal{T}_{old}$
precedes $\mathcal{T}_{new}$, we study stability by studying the aggregate
graph $G[\mathcal{T}_{old}\cap\mathcal{T}_{new}]$. The weights of the entities
in the aggregate graph are the corresponding numbers of entities between
$\mathcal{T}_{old}$ and $\mathcal{T}_{new}$ that remained stable.

We propose a more efficient exploration of the candidate interval pairs by
exploiting their monotonicity properties. We keep one of the two ends of the
interval fixed, as a reference, and since we start with single intervals as
our starting points we refer to this as reference point. We gradually extend
the other end of the interval by exploiting union or intersection. When our
focus is on the original graph then we maintain $\mathcal{T}_{old}$ fixed as
our reference point while when our focus is on the latest state of the graph,
$\mathcal{T}_{new}$ is viewed as our fixed reference point.

We first consider union semantics, thus, our problem is defined as finding the
minimal interval pairs in which at least $k$ entities remain stable.

Without loss of generality, let $w$ be the weight in the aggregate graph of
the entity we are interested in, and let us further assume that we maintain
$\mathcal{T}_{old}$ fixed and gradually extend $\mathcal{T}_{new}$. Given
$\mathcal{T}_{i},1\leq i\leq n$, we apply the following steps:

  1. 1.

First compute all aggregate graphs $G[\mathcal{T}_{i}\cap\mathcal{T}_{i+1}]$,
$1\leq i<n$.

  2. 2.

If for any of the aggregate graphs $G[\mathcal{T}_{i}\cap\mathcal{T}_{i+1}]$,
it holds that $w\geq k$, return $G[\mathcal{T}_{i}\cap\mathcal{T}_{i+1}]$ and
prune any pair with $\mathcal{T}_{i}$ as its left end.

  3. 3.

For each pair $\mathcal{T}_{i},\mathcal{T}_{i+1}$ that continues, extend its
right end by substituting $\mathcal{T}_{i+1}$ with its right child in the
union semi-lattice (i.e., $\mathcal{T}_{i+1}\cup\mathcal{T}_{i+2}$), and apply
step 2.

  4. 4.

The previous is repeated by extending the right end of each surviving interval
with its right child in the union semi-lattice (i.e.,
$\mathcal{T}_{i+1}\cup\mathcal{T}_{i+2}\cup\dots\cup\mathcal{T}_{i+l}$) until
either $i+l=n$ or no interval survives further.

We refer to this algorithm as Union Exploration, (U-Explore). U-Explore can be
adapted to perform extension on the left end of each interval, i.e., by
maintaining $\mathcal{T}_{new}$ fixed, and extending $\mathcal{T}_{old}$ by
substituting in the next step by its left child in the union semi-lattice.

######  Theorem 1.

The minimal interval pairs for stability derived by extending
$\mathcal{T}_{new}$ are not equal to those derived by extending
$\mathcal{T}_{old}$.

Theorem and lemma proofs can be found in [26].

Let us now focus on intersection semantics, thus, our problem is finding the
maximal intervals pairs in which at least $k$ nodes remain stable. Without
loss of generality, let as assume that we maintain $\mathcal{T}_{old}$ and
gradually extend $\mathcal{T}_{new}$. Given $\mathcal{T}_{i},1\leq i\leq n$,
we apply the following steps:

  1. 1.

First compute all aggregate graphs $G[\mathcal{T}_{i}\cap\mathcal{T}_{i+1}]$,
$1\leq i<n$.

  2. 2.

If for any aggregate graph $G[\mathcal{T}_{i}\cap\mathcal{T}_{i+1}]$, it holds
that $w\geq k$, add $G$ to candidate set $C$, else prune any pair with
$\mathcal{T}_{i}$ as its left end.

  3. 3.

For each pair $\mathcal{T}_{i},\mathcal{T}_{i+1}$ that continues, extend its
right end by substituting $\mathcal{T}_{i+1}$ with its right child in the
intersection semi-lattice (i.e., $\mathcal{T}_{i+1}\cap\mathcal{T}_{i+2}$) and
apply step 2, and for any graph $G$ added to $C$, remove from $C$ its
predecessor (i.e., the aggregate graph
$G[\mathcal{T}_{i}\cap\mathcal{T}_{i+1}]$).

  4. 4.

The previous is repeated by extending the right end of each surviving interval
with its right child in the intersection semi-lattice (i.e.,
$\mathcal{T}_{i+1}\cap\mathcal{T}_{i+2}\cap\dots\cap\mathcal{T}_{i+l}$) until
either $i+l=n$ or no interval survives further.

  5. 5.

The final candidate set $C$ is returned.

We refer to this algorithm as Intersection Exploration, (I-Explore). I-Explore
can be adapted to perform extension on the left end of each interval, i.e., by
maintaining $\mathcal{T}_{new}$ fixed, and extending $\mathcal{T}_{old}$ by
substituting it in the next step by its left child in the intersection semi-
lattice.

######  Theorem 2.

The maximal interval pairs for stability derived by extending
$\mathcal{T}_{new}$ are equivalent to those derived by extending
$\mathcal{T}_{old}$.

Table 1: Exploration Intervals Properties

Event Type Case Left Right Mon. Increasing Mon. Decreasing $\subseteq$ of
Growth Min. $\mathcal{T}_{new}$ \- $\mathcal{T}_{old}$($\cup$) t.p. t.p. ✓
$\mathcal{T}_{new}$($\cup$) - $\mathcal{T}_{old}$ $\mathcal{T}_{new}$($\cup$)
- $\mathcal{T}_{old}$ t.p. / interval t.p. ✓ Max. $\mathcal{T}_{new}$ \-
$\mathcal{T}_{old}$($\cap$) t.p. longest interval ✓
$\mathcal{T}_{new}$($\cap$) - $\mathcal{T}_{old}$ t.p. / interval t.p. ✓
Shrinkage Min. $\mathcal{T}_{old}$($\cup$) - $\mathcal{T}_{new}$ t.p. /
interval t.p. ✓ $\mathcal{T}_{old}$ \- $\mathcal{T}_{new}$($\cup$) t.p. t.p. ✓
$\mathcal{T}_{old}$($\cup$) - $\mathcal{T}_{new}$ Max.
$\mathcal{T}_{old}$($\cap$) - $\mathcal{T}_{new}$ t.p. / interval t.p. ✓
$\mathcal{T}_{old}$ \- $\mathcal{T}_{new}$($\cap$) t.p. longest interval ✓
Stability Min. $\mathcal{T}_{old}$($\cup$) $\cap$ $\mathcal{T}_{new}$ t.p. /
interval t.p. ✓ $\mathcal{T}_{new}$($\cup$) $\cap$ $\mathcal{T}_{old}$ t.p. /
interval t.p. ✓ Max. $\mathcal{T}_{old}$($\cap$) $\cap$ $\mathcal{T}_{new}$
t.p. / interval t.p. ✓ $\mathcal{T}_{new}$($\cap$) $\cap$ $\mathcal{T}_{old}$
$\mathcal{T}_{new}$($\cap$) $\cap$ $\mathcal{T}_{old}$ t.p. / interval t.p. ✓
$\mathcal{T}_{old}$($\cap$) $\cap$ $\mathcal{T}_{new}$

###  3.3 Growth and Shrinkage

For growth, we study the aggregate graph
$G[\mathcal{T}_{new}-\mathcal{T}_{old}]$.

With union semantics, our problem is defined as finding the minimal interval
pairs in which at least $k$ entities are added. As difference is not a
symmetric operator, when extending $\mathcal{T}_{old}$, we expect $w$ to
decrease, while when extending $\mathcal{T}_{new}$, we expect an increase to
$w$.

Let us first extend $\mathcal{T}_{old}$. We adopt U-Explore by computing at
step (1), instead of the intersection, the difference graphs
$G[\mathcal{T}_{i+1}-\mathcal{T}_{i}]$, and then apply step (2). We claim that
we do not need to proceed to further steps as for any aggregate graph for
which $w<k$ extending the right interval will not increase the result size on
the derived aggregate graph.

######  Lemma 2.

Temporal aggregation with difference $G[\mathcal{T}_{new}-\mathcal{T}_{old}]$
is monotonically decreasing when we extend $\mathcal{T}_{old}$ and
monotonically increasing when we extend $\mathcal{T}_{new}$, using union
semantics.

Let us now consider extending $\mathcal{T}_{new}$. Again, we adopt U-Explore,
by computing the difference aggregate graphs
$G[\mathcal{T}_{i+1}-\mathcal{T}_{i}]$ instead of the intersection aggregate
graphs. The rest of the steps are applied as defined.

With intersection semantics, we determine the maximal intervals pairs in which
at least $k$ entities are added. We first extend $\mathcal{T}_{old}$.

######  Lemma 3.

Temporal aggregation with difference $G[\mathcal{T}_{new}-\mathcal{T}_{old}]$
is monotonically increasing when we extend $\mathcal{T}_{old}$ and
monotonically decreasing when we extend $\mathcal{T}_{new}$, using
intersection semantics.

Based on the above lemma, the maximal interval pairs are: each point of
reference $\mathcal{T}_{new}$, with the longest possible $\mathcal{T}_{old}$
as long as for the defined aggregate graph, $w\geq k$.

When extending $\mathcal{T}_{new}$, I-Explore is adopted appropriately. In all
respective steps, we compute the aggregate difference graphs
$G[\mathcal{T}_{i+1}-\mathcal{T}_{i}]$, and then apply the rest of the steps
accordingly.

To study shrinkage, we study $G[\mathcal{T}_{old}-\mathcal{T}_{new}]$ and our
problem is symmetrical to growth. Thus, with union semantics we are interested
in finding minimal interval pairs and U-Explore is deployed, while with
intersection semantics we are interested in maximal interval pairs and use
I-Explore.

All cases are summarized on Table 1. Column Case shows the reference point and
the extended interval using either union ($\cup$) or intersection ($\cap$)
semantics. Columns Left and Right refer to the left and right interval in the
result interval pairs. One of the elements in the pair is always a time point
(t.p.) while the other can be either time point or interval and longest
interval. The last column shows the relationships between the results of
different cases, and in particular when the result of one case is a subset of
the result of another case.

###  3.4 Initialization of k

The appropriate value of the threshold $k$ depends each time on the given
graph and its data. To configure this threshold, we propose an initial value
for $k$, indicating a threshold of interestingness and acting as a starting
point so as to attain some results and then continue with its tuning. In
particular, given the type of entity we are interested in, we initialize $k$
to a value $w_{th}$ which is defined as the minimum or the maximum weight of
the given type of entity in the aggregation graph for any graph defined on the
temporal aggregation of pairs of consecutive time points. For stability, we
compute the aggregate graphs on intersections of pairs of consecutive time
points, while for growth and shrinkage we compute the aggregate graphs on the
appropriate difference graphs. Further, for a monotonically increasing
operator, we start with $w_{th}$ as the minimum aggregation weight for a given
entity type, and increase it gradually, while for the monotonically decreasing
operators $w_{th}$ corresponds to the maximum aggregation weight and is
gradually decreased as the exploration progresses.

Table 2: Arrays $\mathbf{V}$, $\mathbf{S}$ for Gender, and $\mathbf{A}$ for
#Publications for the graph of Fig. 1.

Id $t_{0}$ $t_{1}$ $t_{2}$ $u_{1}$ $1$ $1$ $0$ $u_{2}$ $1$ $1$ $1$ $u_{3}$ $1$
$0$ $0$ $u_{4}$ $1$ $1$ $1$ $u_{5}$ $0$ $1$ $1$

Id $u_{1}$ $m$ $u_{2}$ $f$ $u_{3}$ $f$ $u_{4}$ $f$ $u_{5}$ $f$

Id $t_{0}$ $t_{1}$ $t_{2}$ $u_{1}$ $3$ $1$ - $u_{2}$ $1$ $1$ $1$ $u_{3}$ $1$ -
- $u_{4}$ $2$ $1$ $1$ $u_{5}$ - $2$ $2$

##  4 Algorithms

To store an attributed temporal graph $G(V,E,\tau u,\tau e,A)$ defined in a
set of time intervals $\mathcal{T}$, we maintain separate structures for $V$,
$E$ and $A$. For each $v\in V$, $\tau u(u)$ is represented by a binary vector
of size $|\mathcal{T}|$, where each element in the vector corresponds to a
time $t\in\mathcal{T}$, and is 1 iff $t\in\tau u(v)$. Combining the temporal
information for all nodes, we store these vectors as a labeled array
$\mathbf{V}$ with $|V|$ rows labeled with the nodes ids and $|\mathcal{T}|$
columns labeled with the time $t$. A similar representation is deployed for
the edges that are also stored in a labeled array $\mathbf{E}$, with $|E|$
rows labeled with the edges ids denoted as the edges end points $(u,v)$ and
$|\mathcal{T}|$ columns labeled with the time $t$.

For efficient storage and processing, we discern between static and time-
varying attributes. For static-attributes a labeled array $\mathbf{S}$
maintains a row for each node $v\in V$, labeled by the node id, and a number
of columns equal to the number of static attributes, labeled by the
corresponding attribute name. Each row $v$ in the array associates node $v$
with its corresponding static attributes values. In contrast, we maintain a
labeled array $\mathbf{A}^{i}$, for each of the time-varying attributes
$A^{i}$. Rows are similarly to $\mathbf{S}$ labeled with node ids, while the
columns maintain temporal information. Each cell $\mathbf{A}^{i}[v,t]$
maintains the value of attribute $A^{i}$ of $v$ at time $t$. Table 2 depicts
$\mathbf{V}$, $\mathbf{S}$ and $\mathbf{A}$ for the graph of Fig. 1.

###  4.1 Temporal Aggregation Implementation

Based on our data representation, time projection is easily implemented by
restricting the arrays to the columns corresponding to a given time interval.

We present in detail the algorithm implementing the union operator of a graph
$G(V,E,A)$ for $\mathcal{T}_{1},\mathcal{T}_{2}$ as depicted in Alg. 1. The
algorithm takes as input the labeled arrays
$\mathbf{V},\mathbf{E},\mathbf{S}\text{ and }\mathbf{A}^{i}$ for all time-
varying attributes $A^{i}\in A$, and outputs the labeled arrays
$\mathbf{V}_{\cup},\mathbf{E}_{\cup},\mathbf{S}_{\cup}\text{ and
}\mathbf{A}_{i\cup}$ that maintain the information of the derived union graph
$G[\mathcal{T}_{1}\cup\mathcal{T}_{2}]$. As our result is defined in
$(\mathcal{T}_{1},\mathcal{T}_{2})$, we initialize all
$\mathbf{V}_{\cup},\mathbf{E}_{\cup}$ and $\mathbf{A}^{i}_{\cup}$s as empty
arrays with one column for each $t\in\mathcal{T}_{1}\cup\mathcal{T}_{2}$ (line
1). Similarly, we restrict the input tables, except $\mathbf{S}$ that stores
no temporal information, only to the columns corresponding to time
$t\in\mathcal{T}_{1}\cup\mathcal{T}_{2}$ (line 2). For each row $v$ of
$\mathbf{V}$, if there is a value in any $\mathbf{V}[v,t]$ equal to $1$, the
row is inserted in $\mathbf{V}_{\cup}$. The corresponding entries for the
attributes of $v$ are updated. That is, row $v$ in $\mathbf{S}$ and for each
time-varying attribute $A^{i}$ the corresponding rows from arrays
$\mathbf{A}^{i}$ are copied to $\mathbf{S}_{\cup}$ and $\mathbf{A}_{i\cup}$
respectively (lines 3-7). Similarly, for each row $e$ of $\mathbf{E}$, if
there is a value in any $\mathbf{E}[e,t]$ equal to $1$, the row is inserted in
$\mathbf{E}_{\cup}$ (lines 8-10).

Intersection is applied similarly to union, only for a row $v$ of $\mathbf{V}$
to be inserted into $\mathbf{V}_{\cap}$, we require that all elements
$\mathbf{V}[v,t]$ with $t\in\mathcal{T}_{1}$ and $\mathbf{V}[v,t^{\prime}]$
with $t^{\prime}\in\mathcal{T}_{2}$ are equal to 1. The insertion of edges is
also changed accordingly.

Finally, for the difference operator, let
$G[\mathcal{T}_{1}-\mathcal{T}_{2}]$, a row $v$ of $\mathbf{V}$ is inserted
into $\mathbf{V}_{-}$ if any $\mathbf{V}[v,t]$ with $t\in\mathcal{T}_{1}$ is
equal to 1, and all $\mathbf{V}[v,t^{\prime}]$ with
$t^{\prime}\in\mathcal{T}_{2}$ are equal to 0.

###  4.2 Attribute Aggregation Implementation

Aggregation differentiates between distinct and non-distinct. Furthermore, to
improve efficiency, static and time-varying attributes can be treated
separately.

Algorithm 2 applies distinct aggregation when at least one of the attributes
of aggregation is time-varying. It takes as input
$\mathbf{V},\mathbf{E},\mathbf{S}\text{ and }\mathbf{A}^{i}$ for all time-
varying attributes $A^{i}\in A$, interval $\mathcal{T}$ and a list $L$ of the
aggregation attributes, and outputs the labeled vectors
$\mathbf{V^{\prime}},\mathbf{E^{\prime}}$ representing the aggregated graph
$G^{\prime}$. For each attribute $A^{i}$ in $L$, the array $\mathbf{A}^{i}$ is
unpivoted, i.e., its columns corresponding to time points in $\mathcal{T}$ are
appended as rows (lines 1-2), and then merged into a new array
$\mathbf{A^{\prime}}$ (line 3). $\mathbf{A^{\prime}}$ is then deduplicated
based on key $(u,a^{\prime})$, where $a^{\prime}$ is a tuple formed by the
aggregate attributes, so that each node $u$ appears with a given attribute
tuple $a^{\prime}$ only once (line 4). For static attributes, we restrict
$\mathbf{S}$ to the columns corresponding to attributes in $L$ (line 5) and
merge them into $\mathbf{A^{\prime}}$ (line 6). Groups are then formed on
$\mathbf{A^{\prime}}$ based on each distinct attribute tuple $a^{\prime}$ and
its appearances are counted (line 7). Each such group corresponds to a node
that is inserted in the aggregate graph, labeled by the attribute tuple
$a^{\prime}$ and with value equal to the groups count which constitutes the
node’s weight (lines 8-10). To add the edges in the aggregation graph, we
traverse the edge array $\mathbf{E}$ and lookup the edge ends (nodes) in
$\mathbf{A^{\prime}}$ to retrieve the pair of attribute tuples corresponding
to the given nodes at each time point. Each such tuple pair is inserted into a
new temporary array $\mathbf{A^{\prime\prime}}$ (lines 11-14). The rest of the
procedure is similar to our treatment of nodes. $\mathbf{A^{\prime\prime}}$ is
deduplicated based on key $(u,v),(a^{\prime},a^{\prime\prime})$, groups are
formed based on pairs $(a^{\prime},a^{\prime\prime})$ and their appearances
counted (lines 15-16). Finally, for each group a new row with label
$(a^{\prime},a^{\prime\prime})$ is inserted in $\mathbf{E^{\prime}}$,
representing a new edge, and with weight equal to its count that is assigned
as its value (lines 17-19).

For non-distinct aggregation, Alg. 2 is modified by omitting deduplication for
nodes and edges, thus counting all appearances of each attribute tuple, or
pair of attribute tuples respectively.

Optimization is possible if aggregation concerns only static attributes. For
distinct aggregation, we do not require unpivoting nor deduplication as each
node has a unique value for each static attribute . Further, for each edge the
lookups required for its ends do not depend on time and again no deduplication
is required. For non-distinct aggregation, as we need to count all appearances
of a node, we initialize corresponding weights for each $(u,a^{\prime})$ (or
$(u,v),(a^{\prime},a^{\prime\prime})$) by counting the columns in $\mathbf{V}$
(or $\mathbf{E}$) equal to 1. Then, instead of counting the appearances of
each group $a^{\prime}$ (or $(a^{\prime},a^{\prime\prime})$, we sum their
weights.

Input: A temporal attributed graph $G$ represented by
$\mathbf{V},\mathbf{E},\mathbf{S}\text{ and }\\{\mathbf{A}_{i}\\}$, intervals
$\mathcal{T}_{1},\mathcal{T}_{2}$

Output: The union graph $G_{\cup}$ represented by
$\mathbf{V}_{\cup},\mathbf{E}_{\cup},\mathbf{S_{\cup}},\\{\mathbf{A}_{i\cup}\\}$

1

2Initialize $\mathbf{V}_{\cup},\mathbf{E}_{\cup},\\{\mathbf{A}_{i\cup}\\}$ in
$\mathcal{T}_{1}\cup\mathcal{T}_{2}$, and $\mathbf{S_{\cup}}$

3 Restrict $\mathbf{V},\mathbf{E},\text{ and }\\{\mathbf{A}_{i}\\}$ in
$\mathcal{T}_{1}\cup\mathcal{T}_{2}$

4

5for  _each row $v\in\mathbf{V}$_ do

6 if  _$any$ $\mathbf{V}[v,t]=1$_ then //
$t\in\mathcal{T}_{1}\cup\mathcal{T}_{2}$

7 Insert $\mathbf{V}[v]$ in $\mathbf{V}_{\cup}$

8 Insert $\mathbf{S}[v]$ in $\mathbf{S}_{\cup}$

9 Insert each $\mathbf{A}_{i}[v]$ in the corresponding $\mathbf{A}_{i\cup}$

10

11for  _each row $e\in\mathbf{E}$_ do

12 if  _$any$ $\mathbf{E}[e,t]=1$_ then //
$t\in\mathcal{T}_{1}\cup\mathcal{T}_{2}$

13 Insert $\mathbf{E}[e]$ in $\mathbf{E}_{\cup}$

14

return
_$\mathbf{V}_{\cup},\mathbf{E}_{\cup},\mathbf{S_{\cup}},\\{\mathbf{A}_{i\cup}\\}$_

Algorithm 1 Union

###  4.3 Pattern Aggregation Implementation

For pattern-based aggregation, we need to group the nodes of the input
temporal attributed graph based on the given aggregation pattern, and then
count the connections between such groups. To facilitate this process, given a
pattern $P$, we rely on an intermediate pattern-based temporal attributed
graph, we call pattern graph, $G_{P}$, that has a node $v$ for each set of
nodes that match pattern $P$ in $G$, and there is an edge $(u,v)$ in $G_{P}$
if there is at least one common node between the sets of nodes that correspond
to $u$ and $v$. Here, we describe the algorithm for building the pattern graph
when $P$ is an undirected closed triangle, (Alg. 3).

Input: A temporal attributed graph $G$ represented by
$\mathbf{V},\mathbf{E},\mathbf{S}\text{ and }\\{\mathbf{A}_{i}\\}$, intervals
$\mathcal{T}$ and a list $L$ of aggregation attributes

Output: The aggregate graph $G^{\prime}$ represented by arrays
$\mathbf{V^{\prime}}$ and $\mathbf{E^{\prime}}$

1 for  _$A_{i}\in L$_ do

2 $\mathbf{A^{\prime}}_{i}\leftarrow unpivot(\mathbf{A}_{i})$

3$\mathbf{A^{\prime}}\leftarrow$ Merge all $\mathbf{A^{\prime}}_{i}$s

4$\mathbf{A^{\prime}}\leftarrow\mathbf{A^{\prime}}.deduplicate(v,a^{\prime})$

5$\mathbf{S^{\prime}}$ restrict to columns for $s\in L$

6$\mathbf{A^{\prime}}\leftarrow$ Merge $\mathbf{A^{\prime}}$ and $S$

7$GroupsA^{\prime}\leftarrow\mathbf{A^{\prime}}.groupby(a^{\prime}).count()$

8for  _each group in $GroupsA^{\prime}$_ do

9 Insert row $a^{\prime}$ in $\mathbf{V^{\prime}}$

10 $\mathbf{V^{\prime}}[a^{\prime}]\leftarrow a^{\prime}.count$

11for  _$(e(u,v),t)\in\mathbf{E}$_ do

12 $a^{\prime}\leftarrow$ Look up $(u,t)$ in $\mathbf{A^{\prime}}$

13 $a^{\prime\prime}\leftarrow$ Look up $(v,t)$ in $\mathbf{A^{\prime}}$

14 Insert $(a^{\prime},a^{\prime\prime})$ to $\mathbf{A^{\prime\prime}}$

15$\mathbf{A^{\prime\prime}}.deduplicate((u,v),(a^{\prime},a^{\prime\prime}))$

16$GroupsA^{\prime\prime}\leftarrow\mathbf{A^{\prime\prime}}.groupby((a^{\prime},a^{\prime\prime})).count()$

17for  _each group in $GroupsA^{\prime\prime}$_ do

18 Insert row $(a^{\prime},a^{\prime\prime})$ to $\mathbf{E^{\prime}}$

19
$\mathbf{E^{\prime}}[(a^{\prime},a^{\prime\prime})]\leftarrow(a^{\prime},a^{\prime\prime}).count$

return _$\mathbf{V^{\prime}},\mathbf{E^{\prime}}$_

Algorithm 2 Distinct Aggregation

The algorithm takes as input the labeled arrays that constitute the graph $G$
in $\mathcal{T}$, that is, $\mathbf{V}$, $\mathbf{E}$, $\mathbf{S}$, and
$\\{\mathbf{A}_{i}\\}$ and outputs the labeled arrays of the tri-graph
${G}_{tri}(\mathbf{V}_{tri},\mathbf{E}_{tri},\mathbf{S}_{tri},\\{\mathbf{A}_{{i}_{tri}}\\})$
in $\mathcal{T}$. First, we initialize $\mathbf{V}_{tri}$, $\mathbf{E}_{tri}$,
$\mathbf{S}_{tri}$, $\mathbf{A}_{{i}_{tri}}$ as empty arrays (line 1). Next,
we find all triangles that exist in $G$. For each $v\in\mathbf{V}$, we locate
all edges $(i,j)$ that close triangles between neighbors $i$ and $j$ of $v$
and add a triangle $(i,j,v)$ in $\mathbf{V}_{tri}$ with $1$ in column
$t\in\mathcal{T}$ if
$\mathbf{E}[(i,j),t]=\mathbf{E}[(i,v),t]=\mathbf{E}[(j,v),t]=1$ (lines 2-7).

To create the edges in the tri-graph, we use a hash table $\mathcal{H}$, where
we store the node – triangles mappings (line 8). Specifically, each triangle
$v_{tri}$ is inserted in $\mathcal{H}[v]$, $v\in v_{tri}$ (lines 9-10). For
all pairs of triangles $(v_{tri},n_{tri})$ in $\mathcal{H}[v]$, we set
$\mathbf{E}_{tri}[(v_{tri},n_{tri}),t]$ to 1, if both triangles exist in $t$
(lines 12-15).

Finally, $\mathbf{S}_{tri},\\{\mathbf{A}_{{i}_{tri}}\\}$ are filled by
retrieving for each node $v_{tri}=\\{v_{1},v_{2},v_{3}\\}\in\mathbf{V}_{tri}$
the corresponding rows of $v_{1},v_{2}$ and $v_{3}$ in
$\mathbf{S},\\{\mathbf{A}_{{i}}\\}$. For the time-varying attributes, the
algorithm also needs to check the attribute values at each $t\in T$ (lines
16-20).

We can utilize this pattern graph for pattern aggregation in two ways. In the
first approach, we first create the tri-graph of the original temporal
attributed graph and then apply any temporal operation and distinct or non-
distinct aggregation on it. In the second approach, we first perform temporal
aggregation on the original graph, and then construct the tri-graph of the
result and apply pattern aggregation. The second approach, leverages a
possibly smaller graph derived after applying the temporal operator, for
operations such as intersection.

###  4.4 Optimizations

To implement our aggregation framework, we need to materialize all possible
combinations of dimensions and all possible interval aggregations. Although,
this is the best option in terms of response time of OLAP queries, for a large
multidimensional network it is quite unrealistic as it requires excessive
storage space. We propose using partial materialization based on the
properties of the aggregate graphs and which graphs can be derived by other
aggregates without accessing the original graph.

Given an aggregate graph $G^{\prime}$ on a set of attributes
$A^{\prime}=\\{A^{1},A^{2},\dots,A^{k}\\}$ any aggregate graph
$G^{\prime\prime}$ on $A^{\prime\prime}\subseteq A^{\prime}$ can be derived
directly from $G^{\prime}$. Nodes and edges between them in $G^{\prime}$ with
attributes corresponding to distinct tuples in $A^{\prime\prime}$ are grouped
to form new aggregate nodes and edges in $G^{\prime\prime}$. Weights in
$G^{\prime\prime}$ are evaluated by summing up the respective weights of the
entities of $G^{\prime}$ belonging to each group. Consequently,aggregation
with COUNT is identified as a D-distributive measure w.r.t. top-down
aggregations.

With respect to time, we claim that union and non-distinct aggregation is
T-distributive. That is, to compute the weights of the higher level aggregate
union graph, we sum up the weights for the respective nodes and edges in each
of the lower level graphs. Based on the above, we propose precomputing
aggregations on the unit of time that can be combined with union to attain the
aggregate graphs of higher granularity. However, distinct union aggregates are
not T-distributive, as we need to identify distinct nodes across multiple
graphs.

Input: A temporal attributed graph ${G}$ represented by
$\mathbf{V},\mathbf{E},\mathbf{S}\text{ and }\\{\mathbf{A}_{i}\\}$, set of
intervals $\mathcal{T}$

Output: The triangle-based graph $G_{tri}$ represented by
$\mathbf{V}_{tri},\mathbf{E}_{tri},\mathbf{S}_{tri},\\{\mathbf{A}_{{i}_{tri}}\\}$

1 Initialize
$\mathbf{V}_{tri},\mathbf{E}_{tri},\mathbf{S}_{tri},\\{\mathbf{A}_{{i}_{tri}}\\}$

2 for  _each node $v$ in $\mathbf{V}$ and $t\in\mathcal{T}$_ do

Find all edges $(i,j)\in E$ for which $(i,v)\in E$ and $(j,v)\in E$// $i,j\neq
v$

3 if  _$\mathbf{E}[(i,j),t]=1$ and $\mathbf{E}[(i,v),t]=1$ and
$\mathbf{E}[(j,v),t]=1$_ then

4 $\mathbf{V}_{tri}[(i,j,v),t]=1$

5 else

6 $\mathbf{V}_{tri}[(i,j,v),t]=0$

7Initialize $\mathcal{H}$ hash table

8 for  _each triangle $v_{tri}$ in $\mathbf{V}_{tri}$_ do

$\mathcal{H}[v_{i}]\leftarrow v_{tri}$// $v_{i}\in\mathcal{V}_{i}$

9

10for  _each pair $(v_{tri},n_{tri})$ in $\mathcal{H}[v_{i}]$ and
$t\in\mathcal{T}$_ do

11 if  _$\mathbf{V}_{tri}[v_{tri},t]=1$ and $\mathbf{V}_{tri}[n_{tri},t]=1$_
then

12 $\mathbf{E}_{tri}[(v_{tri},n_{tri}),t]=1$

13 else

14 $\mathbf{E}_{tri}[(v_{tri},n_{tri}),t]=0$

// pseudocode for one time-varying attribute

15 for  _each triangle $(v_{1},v_{2},v_{3})$ in $\mathbf{V}_{tri}$ and
$t\in\mathcal{T}$_ do

16 if  _$\mathbf{V}[v_{1},t]=1$ and $\mathbf{V}[v_{2},t]=1$ and
$\mathbf{V}[v_{3},t]=1$_ then

17
$\mathbf{A}_{{1}_{tri}}[(v_{1},v_{2},v_{3}),t]=(\mathbf{A}_{1}[v_{1},t],\mathbf{A}_{1}[v_{2},t],\mathbf{A}_{1}[v_{3},t])$

18 else

19 $\mathbf{A}_{{1}_{tri}}[(v_{1},v_{2},v_{3}),t]=None$

// $\mathbf{S}_{tri}$ is developed similarly omitting the dimension of time

return
_$\mathbf{V}_{tri},\mathbf{E}_{tri},\mathbf{S}_{tri},\\{\mathbf{A}_{{i}_{tri}}\\}$_

Algorithm 3 Tri-Graph Construction Table 3: DBLP Graph

#TP 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014
2015 2016 2017 2018 2019 2020 #Nodes 1708 2165 1761 2827 3278 4466 4730 5193
5501 5363 6236 6535 6769 7457 7035 8581 8966 9660 11037 12377 12996 #Edges
2336 2949 2458 4130 4821 7145 7296 7620 8528 8740 10163 10090 11871 12989
12072 15844 16873 18470 21197 27455 28546

Table 4: MovieLens Graph

#TP May Jun Jul Aug Sep Oct #Nodes 486 508 778 1309 575 498 #Edges 100202
85334 201800 610050 77216 48516

Table 5: Primary School Graph

#TP 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #Nodes 228 231 233 220 118 217
215 232 238 235 235 236 147 119 211 175 187 #Edges 857 2124 1765 1890 1253
1560 1051 1971 1170 1230 2039 1556 1654 1336 1457 1065 1767

Table 6: Primary School-tri Graph

#TP 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #Nodes 1133 7231 4125 5388 3865
2785 2965 5815 1982 2880 6917 4561 5948 5319 2774 3138 5599 #Edges 39131
1593930 471918 1089250 767900 288369 454160 940229 112147 299886 1154406
549094 1737343 1791138 248773 394605 1184264

##  5 Evaluation

Our methods are implemented in Python 3.7.9 utilizing the Modin multiprocess
library [19] and our experiments are conducted in a Windows 10 machine with
Intel Core i5-2430, 2.40GHz processor and 8GB RAM. We use three real-world
datasets, a collaboration network, DBLP, a movie ratings dataset, MovieLens
[15] and a contact network, Primary School. Our code and data are publicly
available111https://github.com/etsoukanara/graphtempo-structure.

The DBLP dataset is extracted from DBLP222https://dblp.uni-trier.de/. Each
node corresponds to an author and two authors are connected with an edge if
they co-author one or more papers in a year. Our DBLP dataset covers a period
of 21 years from 2000 to 2020 and we limit it to publications at 21
conferences related to data management. The derived graph is directed and the
direction of the edges indicates the order of a paper’s authors. Each node is
associated with one static attribute that is gender ($G$) and one time-varying
attribute the number of an author’s publications ($P$) each year.

The MovieLens dataset is built on the benchmark MovieLens [15] movie ratings
dataset. We select a period of six months, from May 2000 up to October 2000,
where each month corresponds to a time point. Each node corresponds to a user
and an edge between two users denotes that they have rated the same movie. Our
dataset is directed based on the precedence of ratings, and does not contain
multiple edges in the unit of time. Each node has 3 static attributes: gender
($G$), age ($A$) with 6 discrete values according to the age group of a user,
and occupation ($O$) with 21 discrete values, and 1 time-varying attribute:
the average rating ($R$) of the user per month.

The Primary School [16], [10] dataset is a contact network of 232 students and
10 teachers of a primary school in Lyon, France, describing the face-to-face
proximity of students and teachers and covering a period of 17 hours. Each
edge denotes a 20-seconds contact, and each node in the network has two static
attributes, gender with 3 values: female (F), male (M), and unspecified (U),
and class with 11 values, i.e., the school has 5 grades, 1 to 5, with 2
classes each (i.e., 1A, 1B, 2A, 2B, etc) plus teachers.

Tables 3, 4, 5 show nodes and edges per time point for the DBLP, MovieLens and
Primary School dataset respectively.

With regards to pattern aggregation, we study triangle based aggregation. In
Fig. 6(a), we show the number of triangles, that is the nodes, and edges for
each time point for the DBLP dataset, while Fig. 6(b) reports construction
time for the corresponding tri-graph. We can see that construction is time-
consuming and the tri-graph size is much greater than the original graphs.
Table 6 reports the corresponding nodes and edges for the Primary School tri-
graph.

#TP 2000 2001 2002 2003 2004 2005 2006 #Nodes 1707 2565 1713 3602 4079 7550
6100 #Edges 28180 135721 23978 146819 162685 481634 171002 #TP 2007 2008 2009
2010 2011 2012 2013 #Nodes 5169 6370 7787 9336 7896 16064 16285 #Edges 68807
92935 260132 315183 191535 3255547 3106984 #TP 2014 2015 2016 2017 2018 2019
2020 #Nodes 12310 18423 22429 24720 22981 55951 44889 #Edges 988132 1124155
3581241 4268275 1070694 33354625 7522430

(a) Statistics

(b) Triangles creation time

Figure 6: DBLP-tri Graph.

(a) DBLP

(b) MovieLens

(c) Primary School

(d) DBLP-tri

Figure 7: Aggregation time per attribute and groups of attributes per time
point.

(a) Union

(b) Intersection

(c) Difference ($\mathcal{T}_{old}$($\cup$) - $\mathcal{T}_{new}$)

(d) Difference ($\mathcal{T}_{new}$ \- $\mathcal{T}_{old}$($\cup$))

Figure 8: Temporal and attribute aggregation for DBLP.

(a) Union

(b) Intersection

Figure 9: Temporal and pattern aggregation for DBLP-tri.

(a) DBLP

(b) MovieLens

(c) DBLP-tri

Figure 10: Speedup of efficient Union aggregation (ALL).

(a) Single attributes

(b) Single attributes

(c) Pairs of attributes

(d) Triples of attributes

(e) Single attributes

Figure 11: Speedup of efficient attribute aggregation per time point for (a)
DBLP, (b-d) MovieLens, (e) DBLP-tri.

(a) Primary School

(b) Primary School-tri

Figure 12: Evolution on Gender for the 4th (break) as to 3rd (lesson) time
point.

(a) Stability ($\mathcal{T}_{old}$($\cap$) $\cap$ $\mathcal{T}_{new}$)

(b) Growth ($\mathcal{T}_{new}$ \- $\mathcal{T}_{old}$($\cup$))

(c) Shrinkage ($\mathcal{T}_{old}$($\cup$) - $\mathcal{T}_{new}$)

Figure 13: Exploration cases with (a) intersection, and (b), (c) union
semantics on $k$ for girls interactions of Primary School.

###  5.1 Performance Evaluation

In the first set of experiments, we evaluate the performance of our algorithms
by measuring execution times.

Type of Attribute. In Fig. 7, we measure aggregation time per attribute and
all attributes combinations on time points. While we expect static attributes
to be faster compared to time-varying ones, in Fig. 7(a), for DBLP time is
similar for both attributes, since both aggregations have similar behaviour
when dealing with time points. Their difference is due to the larger domain of
the time-varying attribute, as gender has 2 distinct values, while
publications vary from 7 to 18. The aggregation (gender, publications) needs
0.18s on 2020, almost 3 times the time for gender (0.06s) and publications
(0.07s). When combining attributes, the domain gets larger, e.g. there are 28
distinct values for (gender, publications) forming the number of aggregate
nodes.

In Fig. 7(b) for MovieLens, for presentation clarity, we report part of all
possible attribute combinations as the ones omitted behave in a similar way.
We depict aggregation time for each attribute, and, from all possible groups
with a specific number of attributes, we selectively report a representative
example combining static and time-varying attributes. We notice a similar to
Fig. 7(a) pattern as gender aggregation hits the best time overall, while
aggregation on all 4 attributes has the longest time. The results confirm that
time is analogous to the distinct values in the aggregation attribute or
combination of attributes domain. The peak observed during August is due to
its high number of nodes and edges compared to other months (Table 4).

For the Primary School in Fig. 7(c), we see a similar behavior with the
aggregation for gender requiring the minimum time, while the aggregation for
the combination of attributes is the most time-consuming.The graph size is
well-balanced across time, thus, we see almost no change on performance.

For pattern aggregation, we report time for the DBLP tri-graph (Fig. 7(d)).
Note that aggregation is performed on the tri-graph whose construction as we
saw dominates the time consumption, e.g., it reaches 2541s in 2019 (Fig.
6(b)). Aggregation is comparatively much faster, only reaching up to 111s for
the attribute combination in 2019, but is still slower compared to the other
cases as the tri-graph size is also much larger.

Temporal Operators. Figures 8 and 9 focus on temporal aggregations for
different operators comparing static and time-varying attributes while
extending time intervals. We report the time of operation and aggregation
separately per attribute for DBLP, and DBLP-tri.

Figure 8(a) illustrates results for union ($\cup$) in logarithmic scale and
compares non-distinct ($a$) and distinct ($d$) aggregation for DBLP. The type
of attribute greatly influences behavior. Non-distinct aggregation for the
longest interval needs 0.53s for gender, while 5.9s for the time-varying
attribute. This difference is observed because for time-varying attributes, we
need to capture all their different values in the interval. Figure 8(b)
depicts intersection ($\cap$), where the results refer up to [2000, 2017],
indicating the longest interval there exists at least one common edge. The
type of attribute is again the controlling performance factor. In contrast to
union, intersection is more costly than aggregation for the static attribute.
This is due to the decreasing graph size as the intervals expand. For time-
varying attributes, the operation time is similar to static, but aggregation
takes much longer due to the increase in the distinct attribute values. For
difference ($\Delta$), we extend $\mathcal{T}_{old}$ with union semantics,
while $\mathcal{T}_{new}$ is our reference point, and we present our results
at logarithmic scale. In Fig. 8(c), we consider $\mathcal{T}_{old}$ \-
$\mathcal{T}_{new}$. As $\mathcal{T}_{old}$ expands, time increases as the
output of the operation also grows. Regarding static attributes, similar to
intersection, difference requires more than double the time required for both
types of aggregation, whereas for the time-varying attribute aggregation is
more expensive. Figure 8(d) depicts $\mathcal{T}_{new}$ \-
$\mathcal{T}_{old}$, that needs less time compared to $\mathcal{T}_{old}$ \-
$\mathcal{T}_{new}$, as the operation output decreases. Any aggregation is
faster than the operation for both the static and time-varying attribute, as
it is actually time point aggregation.

Figure 9 depicts the aggregation time of the union ($\cup$) and intersection
($\cap$) for the static attribute in tri-DBLP. Besides the times for the
operation, and aggregation, we also present the time for the the tri-graph
construction ($G$-$tri$). For union (Fig. 9(a)), we first construct the tri-
graphs and then apply union on them as this approach records a 2.5x speedup
compared to the alternative that would need to compute the triangles in a very
large union graph. The tri-graph construction is the most time-consuming
requiring from 31s for the shortest interval up to 9k for the longest one. For
intersection (Figure 8(b)), we employ the second aggregation method, first
creating the intersection graph and then computing and aggregating the tri-
graph, as we register a 125x speedup in comparison to the first approach,
since intersection reduces the size of the graph on which we need to compute
the triangles. Here, aggregation needs the most time up to 0.71s in [2000,
2002], while the operation is similar on all intervals with average time equal
to 0.02s, and the creation of the triangles does not exceed 0.14s.

Partial Materialization. We evaluate our proposed optimizations by measuring
speedup defined as the execution time of the proposed aggregation algorithms
to the time of optimized aggregation that exploits precomputed results. In
Fig. 10, we report speedup when exploiting precomputed aggregations on time
points to derive their non-distinct union compared to computing it from
scratch. For DBLP, aggregation over the years offers an 8x to 20x speedup for
static attributes (Fig. 10(a)), and from 8x up to 78x for time-varying ones
(Fig. 10(b)). For the gender attribute of DBLP-tri in Fig. 10(c), we record up
to 252Kx speedup. The high speedups achieved in this case are due to the
significant amount of time required for the creation of the triangle-based
graph of DBLP, while the optimized aggregation time is only slightly affected
by the size of the graph.

Figure 11 depicts speedup when exploiting precomputed attributes aggregations
to derive aggregations on subsets of those attributes compared to computing
them from scratch. Figure 11(a) shows gender and publications aggregation when
computed from the aggregation of all DBLP attributes with a speedup of 6x up
to 21x. For MovieLens, first we report each attribute when computed from all
pairs of attributes (Fig. 11(b)). In particular, gender is computed in $G1$
from (gender, age), in $G2$ from (gender, rating) and in $G3$ from (gender,
occupation), and similarly for rating, with $R1$ from (rating, gender), $R2$
from (rating, age) and $R3$ from (rating, occupation), where we achieve a
significant speedup of up to 48x. For MovieLens, we also report results for
computing all pairs (Fig. 11(c)) and triplets (Fig. 11(d)) of attributes from
the aggregate of all 4 attributes, where we observe up to 8x and 6x speedup,
respectively. Improvement is greater for single attributes followed by pairs
and then, triplets. Finally, in Fig. 11(e), we present the speedup for the
triangle-based graph of DBLP, where similarly to efficient union, we record
high speedups up to 210Kx.

###  5.2 Qualitative Evaluation

In this set of experiments, we focus on the Primary School dataset, and
supposing we want to study disease spread dynamics, we perform a qualitative
study of its evolution.

Figure 12(a) depicts the evolution graph on the aggregation for gender,
omitting nodes of unspecified gender (U), from the 3rd hour, lesson time, to
the 4th hour, break time. For each graph element, we provide the distribution
for the events of stability, growth and shrinkage, and the total number of
events. Similarly, Fig. 12(b) presents the corresponding evolution graph for
Primary School-tri. It seems that evolution does not depend on gender.
Comparing the two graphs, we see that edges between females (F-F) exhibit
16.6% stability, which is about 5x higher compared to triangles of females
(FFF) with 2.9% stability. Similarly, for males there is a stability of 16.6%
for M-M edges and 3.1% for MMM triangles, showing that relationships between
larger groups of students have much smaller stability regardless of their
gender, showing little opportunity for isolation bubbles.

Next, we focus on F-F interactions. For stability with maximal interval pairs,
we gradually decrease the maximum weight ($w_{th}=242$), setting
$k_{3}=w{th}$, $k_{2}=w{th}/2$ and $k_{1}=w{th}/8$. We observe the highest
stability for reference point 12 w.r.t. 11, denoted as (12, [11, 11]) where
there are at least 242 common edges between girls. Figure 13(b) depicts growth
with minimal interval pairs, where $w_{th}=342$ and $k_{3}=w{th}$,
$k_{2}=w{th}/2$ and $k_{1}=w{th}/4$. We observe the greatest growth on the 2nd
hour w.r.t. to the 1st with at least 342 new edges. For shrinkage and minimal
intervals pairs with $w_{th}=47$ which is gradually increased, setting
$k_{1}=w{th}$, $k_{2}=w{th}*4$ and $k_{3}=w{th}*8$, we observe the greatest
shrinkage on (12, [8, 11]), where 47 edges are eliminated (Fig. 13(c)). From
the above, we can derive that the 2nd time point appears to be of the highest
risk for disease spread, while the 12th reports high rates of stable and
deleted interactions between girls.

Finally, we further explore stability (Fig. 14). First, we focus on gender and
compare the exploration results for $k=50$ stable contacts between girls (fig.
14(a)) and boys (fig. 14(b)). The highest stability for girls is on (12, [8,
11]), (9, [6, 8]) and (11, [8, 10]), while for boys on (12, [8, 11]), (4, [1,
3]), (10, [7, 9]), (11, [8, 10]), (14, [11, 13]) and (15, [12, 14]), showing
that boys interactions are more stable in comparison to girls. Next, we study
the class attribute, and $k=10$ stable contacts. In Fig. 14(c) for students of
junior class (1A), the highest stability is in (10, [6, 9]), (11, [7, 10]) and
(12, [8, 11]). For students of a senior class (5A), we observe that a long
interval (12, [6, 11]) indicates the highest stability, so we derive that
older students have more stable contacts compared to younger ones (Fig.
14(d)). Consequently, boys seem to build more stable connections compared to
girls and senior students appear to be of lower risk compared to junior ones
for disease spread.

(a) Girls interactions

(b) Boys interactions

(c) 1A’s children interactions

(d) 5A’s children interactions

Figure 14: Stability event for interactions between children with the same
attribute value for Primary School.

##  6 Related Work

With respect to related work, we discern between works that focus on graph
OLAP that ignores time, temporal relational data and temporal graph OLAP.

Graph OLAP. In [3, 4], dimensions, measures and operators for graph OLAP are
defined. Aggregate graphs are defined on both attribute and structural
dimensions and roll-up, drill-down, slice and dice are supported. Partial
materialization is discussed, while efficient computation for structural OLAP
is also addressed in [20]. In [24], drill-down and roll-up are supported on
graphs aggregated based on node attributes and relationships between them.
GraphCube [28] also defines aggregate graphs based on both attributes and
structure, where the evaluated measure is the actual aggregated graph, while
it extends OLAP with queries between aggregated graphs. Graphoids are defined
in [13] over labeled directed multi-hypergraphs to deal with heterogeneous
data that are connected with more than binary relationships. In [8],
aggregates on RDF graphs are based on SPARQL aggregation semantics, and the
problem of efficiently determining the most interesting attribute aggregations
is addressed. In [6], TigerGraph’s query language defines accumulators for
aggregating values returned by pattern matching. State information is
gradually computed for nodes accumulating the corresponding aggregate values
for a query. In [17], aggregation is based on random walks. Each node has a
score based on the concentration of the attribute values of nodes in its
vicinity. The goal is to determine interesting nodes based on a user-defined
threshold. For more, a comprehensive review on graph OLAP can be found in
[21]. Also, as graph aggregation provides a concise graph representation, it
is also deployed for graph summarization [27]. All works above do not focus on
temporal data, and while various types of graph aggregation including
attribute aggregation were previously defined, they cannot support time-
varying attributes or varying temporal resolution without significant changes
to their methods and increase in their cost.

Temporal Relational OLAP. There is a lot of work in temporal relational
databases. Temporal relational algebra [7] employs multidimensional tuple
timestamping and supports both valid and transactional time. Relational
operators are extended to preserve snapshot semantics, and temporal projection
and group by are defined. In [9], new temporal operators on sets of intervals
are implemented to overcome the complexity of temporal calculations. A survey
[12] on time management in data warehouses covers several issues such as
warehouse design, querying and schema changes.

Temporal Graph OLAP. Works on incorporating time in the graph OLAP model
introduce new temporal models and operators. In [5], GQL is extended to T-GQL
for handling temporal paths. Continuous paths address evolution and
consecutive paths travel scheduling problems. In [11], a conceptual model with
explicit labeling of graph elements is designed to support analytical
operations over evolving graphs, and particularly time-varying attributes.
This model incurs redundancy by adding elements that could be discovered
through graph traversal, sacrificing performance for richer analysis support.
In the EvOLAP Graph [14], versioning is also used, both on attributes and
graph structure to enable analytics on changing graphs but no temporal
operators are supported. In contrast to our work, events are described as the
difference of an entity state around a time point and do not capture evolution
on periods of time. In TGraph [18], temporal algebraic operators such as
temporal selection for nodes and edges and traversal with temporal predicates
are defined for a temporal property graph to capture the evolution of nodes,
edges and their attributes on periods of validity. TGraph is further extended
to allow aggregation on attributes and time [1], while we also support pattern
aggregation. Time aggregation focuses on viewing a graph in the appropriate
resolution and studies stability, whereas, we focus on different events such
as growth and shrinkage besides stability, and define an evolution graph that
models all three through set based temporal operators. In [22, 23], the
authors present a tool that builds on the extensions of GRADOOP for temporal
property graphs and supports graph summarization based on time and attribute
aggregation. They provide different visualizations of a graph, i.e., the
temporal graph view, the grouped graph view where grouped elements are
enriched with both attribute and temporal aggregate information, and the
difference graph view that illustrates new, stable and deleted elements
between two graph snapshots. In contrast to our work, the system is driven by
user queries and provides no exploration strategy to determine intervals with
events of interest. In [2], a conceptual model based on the property graph and
the interval-based data model is utilized. This work focuses on the evolution
of the graph both structurally and capturing capturing changes on the set of
attributes and attributes’ values, though no temporal operators are used.
While aggregation and evolution have been addressed, none of the above works
provide any exploration strategies to detect important parts of a graph
without depending on user-defined selections.

Finally, the GraphTempo model for aggregating temporal attributed graphs is
first introduced in [25]. Temporal and attribute aggregation is defined, along
with the evolution graph and the two exploration strategies. In this work, we
first introduce pattern aggregation by extending attribute aggregation to
consider subgraphs that share common attribute values instead of individual
nodes. We also define a new structure, the pattern graph, and present
algorithms for using this structure to efficiently evaluate pattern
aggregation as we experimentally show.

##  7 Conclusions

In this paper, we introduce GraphTempo, a model supporting temporal, attribute
and pattern aggregation of evolving graphs. We define a set of temporal
operators with both tight and relaxed semantics to support temporal
aggregation and extend attribute aggregation to pattern aggregation that
groups whole subgraphs instead of individual nodes. We also define a novel
structure that captures graph evolution, and develop exploration strategies to
determine minimal intervals with significant growth and shrinkage or maximal
intervals with significant stability. We experimentally evaluate the
efficiency of the proposed operators while also performing a qualitative
evaluation based on three real datasets. We plan to extend the exploration
strategies by considering top-$k$ and skyline queries to detect interesting
events without requiring parameter configuration.

## Acknowledgments

Research work supported by the Hellenic Foundation for Research and Innovation
(H.F.R.I.) under the “1st Call for H.F.R.I. Research Projects to Support
Faculty Members & Researchers and Procure High-Value Research Equipment”
(Project Number: HFRI-FM17-1873, GraphTempo).

## References

  * [1] A. Aghasadeghi, V. Z. Moffitt, S. Schelter, and J. Stoyanovich.  Zooming out on an evolving graph.  In Proc. of the 23rd EDBT, pages 25–36, 2020.
  * [2] L. Andriamampianina, F. Ravat, J. Song, and N. Vallès-Parlangeau.  Graph data temporal evolutions: From conceptual modelling to implementation.  Data Knowl. Eng., 139:102017, 2022.
  * [3] C. Chen, X. Yan, F. Zhu, J. Han, and P. S. Yu.  Graph OLAP: towards online analytical processing on graphs.  In Proc. of the 8th IEEE ICDM, pages 103–112, 2008.
  * [4] C. Chen, X. Yan, F. Zhu, J. Han, and P. S. Yu.  Graph OLAP: a multi-dimensional framework for graph data analysis.  Knowl. Inf. Syst., 21(1):41–63, 2009.
  * [5] A. Debrouvier, E. Parodi, M. Perazzo, V. Soliani, and A. A. Vaisman.  A model and query language for temporal graph databases.  VLDB J., 30(5):825–858, 2021.
  * [6] A. Deutsch, Y. Xu, M. Wu, and V. E. Lee.  Aggregation support for modern graph analytics in tigergraph.  In Proc. of the ACM SIGMOD, page 377–392, 2020.
  * [7] D. Dey, T. M. Barron, and V. C. Storey.  A complete temporal relational algebra.  VLDB J., 5(3):167–180, 1996.
  * [8] Y. Diao, P. Guzewicz, I. Manolescu, and M. Mazuran.  Efficient exploration of interesting aggregates in RDF graphs.  In Proc. of the 2021 SIGMOD, pages 392–404. ACM, 2021.
  * [9] A. Dohr, C. Engels, and A. Behrend.  Algebraic operators for processing sets of temporal intervals in relational databases.  In 25th Int. Symp. on Temporal Representation and Reasoning, (TIME), volume 120, pages 11:1–11:16, 2018.
  * [10] V. Gemmetto, A. Barrat, and C. Cattuto.  Mitigation of infectious disease at school: targeted class closure vs school closure.  BMC Infectious Diseases, 14:695, 2014.
  * [11] A. Ghrab, S. Skhiri, S. Jouili, and E. Zimányi.  An analytics-aware conceptual model for evolving graphs.  In Proc. of the 15th Int. Conf. Data Warehousing and Knowledge Discovery, (DaWaK), volume 8057, pages 1–12, 2013.
  * [12] M. Golfarelli and S. Rizzi.  A survey on temporal data warehousing.  Int. J. Data Warehous. Min., 5(1):1–17, 2009.
  * [13] L. I. Gómez, B. Kuijpers, and A. A. Vaisman.  Online analytical processing on graph data.  Intell. Data Anal., 24(3):515–541, 2020.
  * [14] E. Guminska and T. Zawadzka.  Evolap graph - evolution and olap-aware graph data model.  In Proc. of 14th BDAS, volume 928, pages 75–89. Springer, 2018.
  * [15] F. M. Harper and J. A. Konstan.  The movielens datasets: History and context.  ACM Trans. Interact. Intell. Syst., 5(4):19:1–19:19, 2016.
  * [16] S. Juliette, V. Nicolas, B. Alain, C. Ciro, I. Lorenzo, P. Jean-François, Q. Marco, V. Wouter, R. Corinne, L. Bruno, and V. Philippe.  High-resolution measurements of face-to-face contact patterns in a primary school.  PLOS ONE, 6(8):e23176, 2011.
  * [17] N. Li, Z. Guan, L. Ren, J. Wu, J. Han, and X. Yan.  giceberg: Towards iceberg analysis in large graphs.  In 2013 IEEE 29th Int. Conf. on Data Engineering (ICDE), pages 1021–1032, 2013.
  * [18] V. Z. Moffitt and J. Stoyanovich.  Temporal graph algebra.  In Proc of The 16th International Symposium on Database Programming Languages, DBPL, pages 10:1–10:12. ACM, 2017.
  * [19] D. Petersohn, W. W. Ma, D. J. L. Lee, S. Macke, D. Xin, X. Mo, J. Gonzalez, J. M. Hellerstein, A. D. Joseph, and A. G. Parameswaran.  Towards scalable dataframe systems.  Proc. VLDB Endow., 13(11):2033–2046, 2020.
  * [20] Q. Qu, F. Zhu, X. Yan, J. Han, P. S. Yu, and H. Li.  Efficient topological OLAP on information networks.  In Proc. of the 16th DASFAA - Part I, volume 6587, pages 389–403, 2011.
  * [21] P. O. Queiroz-Sousa and A. C. Salgado.  A review on OLAP technologies applied to information networks.  ACM Trans. Knowl. Discov. Data, 14(1):8:1–8:25, 2020.
  * [22] C. Rost, K. Gómez, P. Fritzsche, A. Thor, and E. Rahm.  Exploration and analysis of temporal property graphs.  In Proc. of the 24th EDBT, pages 682–685, 2021.
  * [23] C. Rost, K. Gómez, M. Täschner, P. Fritzsche, L. Schons, L. Christ, T. Adameit, M. Junghanns, and E. Rahm.  Distributed temporal graph analytics with GRADOOP.  VLDB J., 31(2):375–401, 2022.
  * [24] Y. Tian, R. A. Hankins, and J. M. Patel.  Efficient aggregation for graph summarization.  In Proc. of the ACM SIGMOD, pages 567–580, 2008.
  * [25] E. Tsoukanara, G. Koloniari, and E. Pitoura.  Graphtempo: An aggregation framework for evolving graphs.  In Proc. of the 26th EDBT, pages 221–233, 2023.
  * [26] E. Tsoukanara, G. Koloniari, E. Pitoura, and P. Triantafillou.  The graphtempo framework for exploring the evolution of a graph through pattern aggregation (supplemental material), 2023.
  * [27] v. Čebirić, F. Goasdoué, H. Kondylakis, D. Kotzinos, I. Manolescu, G. Troullinou, and M. Zneika.  Summarizing semantic graphs: A survey.  The VLDB Journal, 28(3):295–327, 2019.
  * [28] P. Zhao, X. Li, D. Xin, and J. Han.  Graph cube: on warehousing and OLAP multidimensional networks.  In Proc. of the ACM SIGMOD, pages 853–864, 2011.