∎

11institutetext: Evangelia Tsoukanara 22institutetext: University of
Macedonia, Thessaloniki, Greece
22email<EMAIL_ADDRESS>33institutetext: Georgia Koloniari
44institutetext: University of Macedonia, Thessaloniki, Greece
44email<EMAIL_ADDRESS>55institutetext: Evaggelia Pitoura
66institutetext: University of Ioannina, Ioannina, Greece
66email<EMAIL_ADDRESS>
# Skyline-based exploration of temporal property graphs

Evangelia Tsoukanara1,* Georgia Koloniari2 Evaggelia Pitoura3
<EMAIL_ADDRESS>0000-0002-0720-7608<EMAIL_ADDRESS>0000-0002-9852-7980<EMAIL_ADDRESS>0000-0002-3775-4995

(Received: date / Accepted: date)

###### Abstract

In this paper, we focus on temporal property graphs, that is, property graphs
whose labeled nodes and edges as well as the values of the properties
associated with them may change with time. For instance, consider a
bibliographic network, with nodes representing authors and conferences with
properties such as gender and location respectively, and edges representing
collaboration between authors and publications in conferences. A key challenge
in studying temporal graphs lies in detecting interesting events in their
evolution, defined as time intervals of significant stability, growth, or
shrinkage. To address this challenge, we build aggregated graphs, where nodes
are grouped based on the values of their properties, and seek events at the
aggregated level, for example, time intervals of significant growth in the
collaborations between authors of the same gender. To locate such events, we
propose a novel approach based on unified evolution skylines. A unified
evolution skyline assesses the significance of an event in conjunction with
the duration of the interval in which the event occurs. Significance is
measured by a set of counts, where each count refers to the number of graph
elements that remain stable, are created, or deleted, for a specific property
value. For example, for property gender, we measure the number of female-
female, female-male, and male-male collaborations. Lastly, we share
experimental findings that highlight the efficiency and effectiveness of our
approach.

###### Keywords:

temporal property graph skylines exploration aggregation temporal evolution

1University of Macedonia, Thessaloniki, Greece

ORCID: 0000-0002-0720-7608

2University of Macedonia, Thessaloniki, Greece

ORCID: 0000-0002-9852-7980

3University of Ioannina, Ioannina, Greece

ORCID: 0000-0002-3775-4995

*Corresponding author<EMAIL_ADDRESS>
##  1 Introduction

Property graphs are often used to model relationships and interactions between
real world entities. They consist of nodes and edges of diverse types, called
labels. Both nodes and edges have properties. Property graphs may evolve over
time with nodes and edges being added, or deleted. The value of properties may
also change with time. We call such graphs temporal property graphs. A key
challenge in this context is detecting important events in the evolution of
temporal property graphs, such as periods of significant stability, growth or
shrinkage. It is interesting to detect such events not only at the individual
node and edge level, but also at a higher level. To detect events at a higher
level, we build aggregated property graphs where each node corresponds to sets
of nodes that have the same property values in the original graph, for a given
node label.

For example, consider a face-to-face proximity graph of students and teachers
used for studying the spread of an infectious disease Gemmetto14 . Nodes are
labeled as individual with properties such as class, grade, and gender, while
edges are labeled as interact and correspond to physical interactions between
individuals. Detecting events in the evolution of this graph may reveal
patterns in the disease spread that will facilitate the application of
targeted mitigation strategies. Such patterns may emerge not only at the
individual node level, but also at an aggregated one, for example, between
students of the same class, or gender. For instance, a pattern may be a
correlation between the growth of interactions between 1st graders and an
increase in the disease spread, or a correlation between the shrinkage of
interactions between boys and a drop in the disease spread.

We adopt an interval-based model, where a temporal property graph is modeled
as a property graph whose nodes, edges and properties are annotated with the
time intervals during which the corresponding elements were valid. We model
the evolution of a temporal property graph (including aggregated ones) between
two time intervals $T_{1}$ and $T_{2}$, where $T_{1}$ precedes $T_{2}$ through
three event graphs: (a) the stability graph, that includes nodes and edges
that persist in both $T_{1}$ and $T_{2}$, (b) the growth graph that includes
new nodes and edges that did not exist in $T_{1}$ but appear in $T_{2}$ and
(c) the shrinkage graph that includes deleted nodes and edges that existed in
$T_{1}$ but no longer appear in $T_{2}$. Our goal is to detect intervals in
each of these graphs when significant events occur, where significance is
measured by the number of graph elements that remain stable, are created, or
deleted respectively.

Previous work on evolution exploration is driven either by user queries Rost22
, or requires a threshold on the number of events Tsoukanara23 . Both
approaches require knowledge of the underlying data to achieve appropriate
parameter configuration or create a meaningful query. In this paper, we adopt
a parameter-free novel approach designed for temporal property graphs based on
evolution skylines. An evolution skyline is defined on the significance of the
event (i.e., number of affected graph elements) and the length of the interval
when the event appears. An individual evolution skyline has two dimensions,
namely the length of the interval and the number of affected graph elements
with a specific property value, for example, for growth, the number of new
interactions i.e., between female students. Unified evolution skylines extend
the individual evolution skylines to more than two dimensions. Concretely in a
unified evolution skyline, we keep the number of affected graph elements for
each possible property value, for example, for growth, we have three numbers,
i.e, the number of interactions between female students, between male students
and between female and male students.

The preferred length of the interval in a skyline depends on semantics. In
this paper, we use two different semantics namely: strict and loose semantics.
Strict semantics capture persistent occurrences of nodes and edges, while
loose semantics capture transient changes. For example, we are interested in
the shortest intervals in the case of loose semantics and shrinkage, so as to
capture abrupt changes in the graphs, and in the longest intervals in the case
of strict semantics and stability, so as to capture persistence.

In particular, assume that in the face-to-face proximity graph, there is a
unified skyline point for property gender with an interval of length 10 and
with significance of 30 edges between boys, 20 edges between girls and 15
edges between boys and girls, for the case of stability and strict semantics.
This means that: (a) there is no longer interval where the same number or more
edges between boys, or girls, or boys and girls remained stable, and (b) there
is no interval with length 10 or more where more edges between boys, or girls
or boys and girls remained stable.

We also extend our unified skyline-based strategy to detect the top-$k$
unified skyline where tuples are ranked based on the number of tuples each one
dominates. Finally, we present an experimental evaluation of our approach
using three real datasets, aiming at studying both the efficiency and the
effectiveness of our approach.

The rest of the paper is structured as follows. In Section 2, we introduce
necessary concepts, while in Section 3, we define unified skylines. In Section
4, we present the skyline computation, and Section 5 includes our experimental
results. Section 6 summarizes related work and Section 7 offers conclusions.

##  2 The temporal property graph model

A property graph is a directed labeled graph where each node or edge can have
a set of properties represented as key-value pairs Angles18 . Temporal
property graphs are property graphs that describe the changes occurring in the
graph structure and properties over time, capturing the evolution of a graph.

Specifically, we define a temporal property graph based on the TGraph model
Moffitt17 , additionally, supporting property values that can change with
time. Let $\mathcal{L}$ be a set of node and edge labels, $\mathcal{P}$ a set
of properties, $\mathcal{V}$ a set of property values, and $T$ a set of time
intervals, henceforth termed as temporal element.

######  Definition 1 (Temporal Property Graph)

A temporal property graph is defined as a tuple
$G[T]=(N,E,\rho,\lambda,\xi^{T},\sigma^{T})$, where:

  * •

$N$ is a set of nodes;

  * •

$E$ is a set of edges;

  * •

$\rho:E\rightarrow(N\times N)$ is a function that maps an edge to its source
and destination nodes;

  * •

$\lambda:(N\cup E)\rightarrow\mathcal{L}$ is a function that maps a node or a
an edge to a label;

  * •

$\xi^{T}:(N\cup E)\rightarrow T^{\prime}$ is a function that maps a node or an
edge, to a set $T^{\prime}$ of time subintervals of $T$, indicating existence
of the node or the edge at these subintervals; and

  * •

$\sigma^{T}:(N\cup E)\times\mathcal{P}\times t\rightarrow\mathcal{V}$ is a
partial function that maps a node or an edge, a property, and a time instance
$t\in T$ to a value of the property at this time instance.

Additionally, it holds that a property can have a value only when the relevant
node or edge exists, and that a property has necessarily a value assigned when
the corresponding node or edge exists. Our model supports both static
properties for which $\sigma^{T}$ assigns the same value for all $t\in T$, and
time-varying properties whose values change during $T$.

Although our model supports properties for both nodes and edges, in this
paper, we focus on node properties. Also, hereafter, we collectively refer to
nodes and edges of a graph as graph elements.

Figure 1 depicts an example of a temporal property graph for a bibliographic
network. We have nodes with two different labels, author and conference.
Authors have two properties, a static one, gender, and a time-varying one,
#publications, denoting the number of publications of the author per year.
Conferences have two properties, one static, topic, and one time-varying,
location. All nodes also include a unique ID property. For simplicity, we
associate this property with the temporal elements in which the corresponding
node exists. The other property values are also similarly annotated with
temporal elements. For example, node with ID 1 exists during [1, 2], is
associated with the author label, has the static property gender with value
male, and the time-varying property #publications with value 1 for the
interval [1], and 2 for the interval [2]. Edges in the graph have two labels:
publish that describe relationships between authors and conferences, and
collaborate between authors, both also annotated with their corresponding
temporal elements. For example, there is a publish labeled edge between author
node with ID 1 and conference node with ID 5, denoting that the author
published at this conference in interval [2]. Note, that we denote an interval
that includes a single time point, e.g. $[1,1]$, simply as $[1]$.

Figure 1: An example of a temporal property graph for a bibliographic network
defined on $T=[1,3]$.

###  2.1 Temporal graph operators

To manage and explore the temporal dimension of our graph model, we define
three different set-based operators that take as input two temporal property
graphs and produce a new temporal property graph.

Specifically, given two temporal property graphs $G[T_{1}]$ and $G[T_{2}]$,
the union ($\cup$) operator $G[T_{1}]\cup G[T_{2}]$ generates a new temporal
property graph with graph elements that appear either in $G[T_{1}]$ or
$G[T_{2}]$, i.e., graph elements that exist in any time instance of $T_{1}$ or
$T_{2}$. The intersection ($\cap$) operator $G[T_{1}]\cap G[T_{2}]$ produces a
temporal property graph whose elements appear in both $G[T_{1}]$ and
$G[T_{2}]$. Finally, the difference ($-$) $G[T_{1}]-G[T_{2}]$ outputs a
temporal property graph that includes graph elements that appear in $G[T_{1}]$
but not in $G[T_{2}]$. Note that the definition of the temporal operators is
based on the union, intersection and difference of graph elements, that is, of
the sets of nodes and edges.

(a)

(b)

Figure 2: $G[T_{1}\sqcup T_{2}]$ with (a) loose and (b) strict semantics.

In addition, given a sequence of graphs defined at different temporal
elements, we would like to combine them into a single temporal graph. To this
end, we introduce strict and loose semantics. Strict semantics retain
continuous occurrences of graph elements, while loose semantics retain also
transient ones. Intuitively, persistence is associated with the notion of
intersection which focuses on finding continuous occurrences, and therefore,
consistency over a period. On the other hand, union adopts a more loose
strategy and focuses on all graph elements ever appearing during a period of
time.

Concretely, for two temporal elements, $T_{1}$ and $T_{2}$, let us denote the
combined graph as $G[T_{1}\sqcup T_{2}]$. Graph $G[T_{1}\sqcup T_{2}]$ is
defined with: (a) strict semantics as $G[T_{1}]\cap G[T_{2}]$, i.e., we want a
graph element to appear in all time instances in $T_{1}\cup T_{2}$ and (b)
loose semantics, as $G[T_{1}]\cup G[T_{2}]$, i.e., we want a graph element to
appear in at least one time instance in $T_{1}\cup T_{2}$.

An example of $G[T_{1}\sqcup T_{2}]$ where $T_{1}$ is time instance 1 and
$T_{2}$ is time instance 2 defined with loose semantics is shown in Fig. 2(a)
and with strict semantics in Fig. 2(b). The graph of Fig. 2(a) depicts nodes
and edges that appear in either time instance 1 or 2, while the graph of Fig.
2(b) includes only nodes and edges that appear in both 1 and 2. For example,
node with ID 3 appears in the graph of Fig. 2(a) but not in that of Fig. 2(b)
as it exists only in time instance 2.

###  2.2 Graph evolution and aggregation

Our goal is to capture the evolution of a graph between two consequent time
intervals $T_{1}$ and $T_{2}$ so as to detect whether graph elements remained
stable in both intervals, new graph elements appeared in the most recent one,
or existing ones disappeared in the most recent one. Thus, we want to study
respectively stability, growth and shrinkage, collectively called events.

To model graph evolution with respect to these three types of events, we
exploit the temporal operators and define the following three event graphs.
For a pair of time intervals $T_{1}$, $T_{2}$ where $T_{2}$ follows $T_{1}$:
(a) the stability graph ($s$-graph), denoted as $G_{s}[(T_{2},T_{1})]$, is
defined as $G[T_{1}]\cap G[T_{2}]$ and captures stable graph elements that
appear in both $T_{1}$ and $T_{2}$, (b) the shrinkage graph ($h$-graph),
$G_{h}[(T_{2},T_{1})]$, is defined as $G[T_{1}]-G[T_{2}]$ and captures
elements that disappear from $T_{1}$ to $T_{2}$ and (c) the growth graph
($g$-graph), $G_{g}[(T_{2},T_{1})]$, is defined as $G[T_{2}]-G[T_{1}]$ and
captures graph elements that are new to $T_{2}$ and did not appear in $T_{1}$.
We use $\gamma$ to denote any of the three events.

For example, $G_{s}[(3,[1\sqcup 2])]$, for the graph of Fig. 1 denotes the
part of the graph that did not change between the graph in time interval
$[1\cup 2]$ and the graph in time instance 3 shown in Fig. 3. In case of
strict semantics, the graph elements are the nodes and edges that existed in
both time instances 1 and 2 (Fig. 2(b)) and also remain in time instance 3. In
case of loose semantics, the graph elements are the nodes and edges that
existed in at least one of the time instances 1 and 2 (Fig. 2(a)) and also
remain in time instance 3.

Besides studying the evolution of the graph at the individual node and edge
level, we want to study the evolution at a higher granularity level. For
example, instead of studying stable interactions between individuals, we may
want to study stable interactions between individuals of the same gender, or
age. To this end, we employ graph aggregation where given a set of labels
$L\subseteq\mathcal{L}$ and properties $P$ associated with these labels, we
group nodes that have the same values for these properties, while respecting
the network structure. The resulting property graph consists of two types of
nodes: (a) aggregated nodes that correspond to sets of nodes in the original
graph whose label belong to $L$ and have the same property values, and (b)
nodes of the original graph whose label does not belong to $L$ and thus are
not aggregated.

Figure 3: Graph instance on time point $3$ for the graph of Fig. 1. Figure 4:
Graph $G[[3],\\{gender\\}]$ aggregated by author label and gender property for
the graph of Fig. 3. Figure 5: Graph $G[[3],\\{gender,topic\\}]$ aggregated by
author, conference labels and gender, topic properties for the graph of Fig.
3.

######  Definition 2 (Graph aggregation)

Given a temporal property graph $G[T]$, a set of labels
$L\subseteq\mathcal{L}$ and a set of properties $P\subseteq\mathcal{P}$
associated with labels $L$, we define the graph aggregated by $P$ in $T$,
$G[T,L:P]$, as a property graph where:

  * •

There exists a node $u^{\prime}$ in $G[T,L:P]$ with label $l_{u^{\prime}}=p$
for each distinct property value combination $p$ of the $P$ properties, and a
single property, weight with value equal to the number of distinct nodes in
$G[T]$ that have the specific property value combination $p$. Also, there
exists a node $v^{\prime}$ in $G[T,L:P]$ with label $l_{v}\in\mathcal{L}$, for
each node $v$ in $G[T]$ such that $l_{v}\notin L$, with the same properties
and values as node $v$ and an additional property weight with value equal to
1.

  * •

There exists an edge $e^{\prime}$ with label $l_{e}\in\mathcal{L}$ between two
nodes $u^{\prime},v^{\prime}$ in $G[T,L:P]$, if there is an edge of label
$l_{e}$ between the corresponding nodes in the original graph, and a property,
weight, with value equal to the number of such edges.

For simplicity, we omit labels in the aggregate graph notation using $G[T,P]$
instead of $G[T,L:P]$ to avoid notation overload.

Figure 4 depicts the aggregation for the author label, and the gender property
for the graph of Fig. 3, denoted as $G[[3],\\{gender\\}]$. Nodes that
represent authors are aggregated by gender, whereas the rest of the nodes
(conferences) are not affected by the aggregation. In more detail, the
property gender has two values, namely male, and female, thus there are two
aggregated nodes in Fig. 3, one with label male corresponding to the nodes
with ID 2 and 7 in the original graph, and one with label female corresponding
to nodes with ID 3 and 6. Both nodes have a single property weight with value
2. The aggregate graph also includes two nodes that correspond to the nodes
with label conference in the original graph, i.e., nodes with ID 4 and 5, with
an additional property weight with value 1. For nodes of the same property
values in the original graph, edges with the same label are grouped together
in the aggregated graph and have an additional property weight whose value is
equal to the number of edges in the original graph that they group. For
instance, there is an edge with label $collaborate$ between nodes labeled
$female$ and $male$ corresponding to all collaborations between male and
female authors in the original graph, i.e., edges between nodes with ID 2 and
3, and ID 2 and 6, and its property $weight$ has value 2. Similarly, there is
an edge with label $publish$ and property weight equal to 1, between the node
with label $male$ and the $conference$ node with ID 4 corresponding to the
edge of the original graph between nodes with ID 2 and 4.

As an additional example, Fig. 5 depicts the aggregation for the $author$ and
$conference$ labels and their respective properties, $gender$ and $topic$, for
the graph of Fig. 3, denoted as $G[[3],\\{gender,topic\\}]$. As all node
labels are selected for aggregation, all the nodes of the original graph are
aggregated. The aggregated nodes for authors are the same as in Fig. 4.
Additionally, conferences are aggregated based on topic. Specifically, there
are two conferences of topic data mining in the original graph. Thus, the
aggregate graph includes a node for the two conferences with label data mining
and $weight$ 2\. Edges are formed as previously described. For instance, there
are 3 publications between male authors and the data mining conferences, so
the aggregated graph contains one corresponding edge with $weight$ equal to 3.

Aggregation can be applied similarly on any event graph. For example, Fig. 6
shows the three event graphs for the evolution of the graph from $G[1\sqcup
2]$ defined with loose semantics to $G[3]$ aggregated by gender, that is
$G_{s}[(3,[1\sqcup 2]),\\{gender\\}]$, $G_{g}[(3,[1\sqcup 2]),\\{gender\\}]$
and $G_{h}[(3,[1\sqcup 2]),\\{gender\\}]$.

To evaluate the significance of an event, we measure the affected graph
elements. We focus on events considering edges. Let $l_{e}\in\cal{L}$ be an
edge label, and $p$ and $p^{\prime}$ be two property value combinations for a
set of properties $P$. For an event $\gamma$, we use
$count(G_{\gamma}[(T_{2},T_{1})],l_{e},p,p^{\prime})$ to denote the count of
edges with label $l_{e}$ from nodes with property value combination $p$ to
nodes with property value combination $p^{\prime}$ in the $\gamma$-graph
$G_{\gamma}[(T_{2},T_{1})]$.

###### Proposition 1

Given an aggregate event graph $G_{\gamma}[(T_{2},T_{1}),P]$, if $p$ and
$p^{\prime}$ correspond to values of properties in $P$, then
$count(G_{\gamma}[(T_{2},T_{1})],l_{e},p,p^{\prime})$ is equal to the weight
property of the edge labeled $l_{e}$ between the nodes with labels $p$ and
$p^{\prime}$ in $G_{\gamma}[(T_{2},T_{1}),P]$.

For example, given $G_{s}[(3,[1\sqcup 2]),\\{gender\\}]$ in Fig. 6(a),
$count(G_{s}[3,(1\sqcup 2))],$ $collaborate,male,female)$, which counts the
collaborations between male and female authors that remain stable on $G[3]$
with respect to $G[1\sqcup 2]$, is equal to the $weight$ property of the
collaborate edge between the $male$ and $female$ aggregated nodes, and thus,
$count(G_{s}[3,(1\sqcup 2))],collaborate,male,female)=1$.

(a)

(b)

(c)

Figure 6: (a) Stability ($G_{s}$), (b) growth ($G_{g}$) and (c) shrinkage
($G_{h}$) graphs aggregated on gender for the graph of Fig. 2(a) to that of
Fig. 3.

###  2.3 Graph exploration

We would like to identify points in the history of the graph where the count
of events is high, indicating interesting points in the evolution of the
graph. Specifically, we want to locate time points, termed reference points,
$t_{r}$, where the stability, shrinkage or growth counts,
$count(G_{\gamma}[(t_{r},T_{r})],l_{e},p,p^{\prime})$, are large with respect
to an immediate preceding interval $T_{r}$. To locate such points, for each
reference point $t_{r}$, we perform our search as follows. We initialize
$T_{r}$ to be the time point immediately preceding $t_{r}$, and then we
gradually extend $T_{r}$ to the past, using either the intersection-inspired
strict or the union-inspired loose semantics.

Given $G_{\gamma}[(t_{r},T_{r})]$, edge label $l_{e}$, and property value
combinations $p$ and $p^{\prime}$, we say that $T_{r}$ is: (i) minimal if
$\nexists$ $T^{\prime}_{r}$ such that $T^{\prime}_{r}\subset T_{r}$ and
$count(G_{\gamma}[(t_{r},T^{\prime}_{r})],$ $l_{e},p,p^{\prime})\geq
count(G_{\gamma}[(t_{r},T_{r})],l_{e},p,p^{\prime})$, and (ii) maximal if
$\nexists$ $T^{\prime}_{r}$ such that $T_{r}\subset T^{\prime}_{r}$ and
$count(G_{\gamma}[(t_{r},T^{\prime}_{r})],l_{e},p,p^{\prime})$ $\geq
count(G_{\gamma}[(t_{r},T_{r})],l_{e},p,p^{\prime})$.

We say that a count for an event $\gamma$ with respect to strict (loose)
semantics, is increasing if: for any $T^{\prime}_{r}\supseteq T_{r}$ defined
using strict (resp. loose) semantics,
$count(G_{\gamma}[(t_{r},T^{\prime}_{r})],l_{e},p,p^{\prime})$ $\geq$
$count(G_{\gamma}[(t_{r},T_{r})],l_{e},p,p^{\prime})$, for any edge label
$l_{e}$, any combination of property values $p$ and $p^{\prime}$, and any
reference point $t_{r}$. Similarly, we say that a count for an event $\gamma$
with respect to strict (loose) semantics, is decreasing if: for any
$T^{\prime}_{r}\subseteq T_{r}$ defined using strict (resp. loose) semantics,
$count(G_{\gamma}[(t_{r},T^{\prime}_{r})],l_{e},p,p^{\prime})$ $\leq$
$count(G_{\gamma}[(t_{r},T_{r})],l_{e},p,p^{\prime})$, for any edge label
$l_{e}$, any combination of property values $p$ and $p^{\prime}$, and any
reference point $t_{r}$. It holds that count for:

  * •

stability is decreasing wrt strict and increasing wrt loose semantics,

  * •

growth is increasing wrt strict and decreasing wrt loose semantics, and

  * •

shrinkage is decreasing wrt strict and increasing wrt loose semantics.

Consequently for increasing counts, we are interested in minimal intervals,
while for decreasing counts in maximal intervals.

##  3 Evolution skyline

In the following, we present skyline-based exploration where based on a set of
criteria we filter out the exploration results that appear to be of low
interestingness. A skyline approach retrieves all items that have the “best”
preferred value, in at least one of their features and are not worse in the
others. In particular, for multidimensional data, we say that an item
dominates another item if it is as good in all dimensions, and better in at
least one dimension. A skyline query returns all non-dominated items in a
dataset.

We define two criteria to evaluate the interestingness of an event $\gamma$ in
an event graph $G_{\gamma}[(t_{r},T_{r})]$ with respect to edge label $l_{e}$
and property value combinations $p$ and $p^{\prime}$ of properties $P$: the
length $len_{T_{r}}$ of the temporal element $T_{r}$ defined as the number of
time instances $t\in T_{r}$, and the event count
$count(G_{\gamma}[(t_{r},T_{r})],l_{e},p,p^{\prime})$.

######  Definition 3 (Individual evolution skyline)

Given an event $\gamma$, a graph $G[T]$, edge label $l_{e}\in\cal{L}$ and sets
of property values, $p$ and $p^{\prime}$ of some properties
$P\subseteq\cal{P}$, the individual evolution skyline is defined as all non-
dominated tuples $(t_{r},T_{r},w)$ where $t_{r}$ $\in$ $T$, $T_{r}$ $\subset$
$T$ and $w$ = $count(G_{\gamma}[(t_{r},T_{r})],l_{e},p,p^{\prime})$.

For an event $\gamma$ with semantics that have increasing counts, we say that
a tuple $(t_{r},T_{r},w)$ dominates a tuple
$(t^{\prime}_{r},T^{\prime}_{r},w^{\prime})$ if
$len_{T_{r}}<len_{T^{\prime}_{r}}$ and $w\geq w^{\prime}$, or $w>w^{\prime}$
and $len_{T_{r}}\leq len_{T^{\prime}_{r}}$. Respectively, for an event
$\gamma$ with semantics that have decreasing counts, we say that a tuple
$(t_{r},T_{r},w)$ dominates a tuple
$(t^{\prime}_{r},T^{\prime}_{r},w^{\prime})$ if
$len_{T_{r}}>len_{T^{\prime}_{r}}$ and $w\geq w^{\prime}$, or $w>w^{\prime}$
and $len_{T_{r}}\geq len_{T^{\prime}_{r}}$.

For example, considering stability with strict semantics for collaborations
between male authors, i.e., edges with $l_{e}$:collaborate and
$p,p^{\prime}$:male, male, a tuple $(11,[1\sqcup 10],20)$ in the skyline means
that: (a) there is no longer interval where 20 or more such edges remained
stable, and (b) there is no interval with length 10 or more where more edges
remained stable.

Taking advantage of the increasing and decreasing properties, we restrict the
number of such tuples as follows.

###### Lemma 1

Any non-dominated tuple includes an interval $T$ which is either maximal or
minimal depending on the use of strict or loose semantics.

###### Proof

Without loss of generality, let us consider strict semantics. If the interval
$T_{r}$ of a non-dominated tuple $(t_{r},T_{r},w)$ is not maximal, then there
would exist a pair $(t_{r},T^{\prime}_{r},w^{\prime})$ such that $T_{r}\subset
T^{\prime}_{r}$ and for lengths of $T_{r},T^{\prime}_{r}$, would be
$len_{T^{\prime}_{r}}>len_{T_{r}}$ in which $w^{\prime}\geq w$ events occur.
Thus, $(t_{r},T^{\prime}_{r},w^{\prime})$ dominates $(t_{r},T_{r},w)$.

When studying evolution, instead of focusing on the events concerning edges of
label $l_{e}$ with particular property values, $p,p^{\prime}$ as explored by
individual skylines, we may be interested in events concerning all value
combinations of a particular property set $P\subseteq\mathcal{P}$.

######  Definition 4 (Unified evolution skyline)

Given an event $\gamma$, an edge label $l_{e}\in L$, a set of node properties
$P$ and a graph $G[T]$, the unified evolution skyline is defined as all non-
dominated tuples $(t_{r},T_{r},w_{1},w_{2},\dots,w_{n})$, where $t_{r}\in T$,
$T_{r}$ $\subset$ $T$, and $w_{i}$ =
$count(G_{\gamma}[(t_{r},T_{r})],l_{e},p,p^{\prime})$ for each of the $n$
property value combinations $p,p^{\prime}$ of $P$ with label $l_{e}$.

Considering all value combinations by exploration with unified skylines allows
us to detect points in the evolution of the graph that show interesting events
with any property value of some property set $P$. For instance, considering
property $gender$, instead of focusing on stable collaborations between, e.g,
only male authors (male, male), we also consider at the same time
($male,female$), ($female,male$) and ($female,female$) collaborations at the
same time. Extending our previous example, for stability with strict semantics
and author collaborations ($l_{e}:collaborate$), a tuple $(11,[1\sqcup
10],30,20,15,10)$ in the unified skyline means that: (a) there is no longer
interval where the same number or more edges between male authors, or male and
female authors, or female and male authors or female authors remained stable,
and (b) there is no interval with length 10 or more where more edges between
male authors, or male and female authors, or female and male authors or female
authors remained stable. Note that the direction of the edge indicates
authorship order.

Similarly to individual skylines, for an event $\gamma$ with semantics that
have increasing counts, we say that a tuple
$(t_{r},T_{r},w_{1},w_{2},\dots,w_{n})$ dominates a tuple
$(t^{\prime}_{r},T^{\prime}_{r},w^{\prime}_{1},w^{\prime}_{2},\dots,w^{\prime}_{n})$
if it holds that $len_{T_{r}}<len_{T^{\prime}_{r}}$ and $w_{i}\geq
w^{\prime}_{i}$ $\forall$ $i$, or $len_{T_{r}}\leq len_{T^{\prime}_{r}}$ and
$w_{i}\geq w^{\prime}_{i}$ $\forall$ $i$ and $\exists$ $w_{i}>w^{\prime}_{i}$,
where $i\in\\{1,\dots,n\\}$. Respectively, for an event $\gamma$ with
semantics that have decreasing counts, we say that a tuple
$(t_{r},T_{r},w_{1},w_{2},\dots,w_{n})$ dominates a tuple
$(t^{\prime}_{r},T^{\prime}_{r},w^{\prime}_{1},w^{\prime}_{2},\dots,w^{\prime}_{n})$
if it holds that $len_{T_{r}}>len_{T^{\prime}_{r}}$ and $w_{i}\geq
w^{\prime}_{i}$ $\forall$ $i$, or $len_{T_{r}}\geq len_{T^{\prime}_{r}}$ and
$w_{i}\geq w^{\prime}_{i}$ $\forall$ $i$ and $\exists$ $w_{i}>w^{\prime}_{i}$,
where $i\in\\{1,\dots,n\\}$.

From Lemma 1 we derive that the intervals included in the non-dominated tuples
of the unified evolution skyline are also maximal or minimal.

###### Lemma 2

In the unified skyline, any non-dominated tuple includes an interval $T$ which
is either maximal or minimal depending on the use of strict or loose
semantics.

###### Proof

Without loss of generality, let us consider a decreasing event. If the
interval $T_{r}$ of a non-dominated tuple with $n$ dimensions
$(t_{r},T_{r},w_{1},\dots,w_{n})$ is not maximal, then there would exist a
tuple $(t_{r},T^{\prime}_{r},w^{\prime}_{1},\dots,w^{\prime}_{n})$ such that
$T_{r}\subset T^{\prime}_{r}$ and for lengths of $T_{r},T^{\prime}_{r}$, would
be $len_{T^{\prime}_{r}}>len_{T_{r}}$ in which $w^{\prime}_{i}\geq
w_{i},\forall$ $i\in n$. Thus,
$(t_{r},T^{\prime}_{r},w^{\prime}_{1},\dots,w^{\prime}_{n})$ dominates
$(t_{r},T_{r},w_{1},\dots,w_{n})$.

The following lemmas relate individual with unified skylines.

###### Lemma 3

A tuple $r=(t_{r},T_{r},w_{1},w_{2},\dots,w_{n})$ belongs to the unified
skyline set $S$, if and only if $\exists$ $w_{i}$, $1\leq i\leq n$, for which
it holds $(t_{r},T_{r},w_{i})\in s_{i}$, where $s_{i}$ is the individual
skyline set for the $i$-th combination.

###### Proof

Without loss of generality, let us assume the skyline $S$ for an event
$\gamma$ with decreasing counts.

Let a tuple $r=(t_{r},T_{r},w_{1},w_{2},\dots,w_{n})$ $\in S$ such that
$\nexists$ $w_{i}$ for which $(t_{r},T_{r},w_{i})$ $\in s_{i}$, $1\leq i\leq
n$. Since $r\in S$, then $r$ in not dominated by any other tuple. This implies
that $\nexists$
$r^{\prime}=(t_{r^{\prime}},T_{r^{\prime}},w_{1}^{\prime},w_{2}^{\prime},\dots,w_{n}^{\prime})$
such that either (i) $len_{T_{r}}<len_{T_{r^{\prime}}}$ and $w_{i}\leq
w_{i}^{\prime},\forall i,1\leq i\leq n$, or (ii) $len_{T_{r}}\leq
len_{T_{r^{\prime}}}$ and $w_{i}\leq w_{i}^{\prime},\forall i,1\leq i\leq n$
and $\exists k,1\leq k\leq n$, such that $w_{k}^{\prime}>w_{k}$. If (i) holds,
then $(t_{r},T_{r},w_{i})$ is not dominated for all $i,1\leq i\leq n$, thus,
$(t_{r},T_{r},w_{i})\in s_{i}$ for all dimensions $i$. Otherwise, if (ii)
holds, then $(t_{r},T_{r},w_{k})$ is not dominated and thus,
$(t_{r},T_{r},w_{k})\in s_{k}$.

Let $(t_{r},T_{r},w_{k})\in s_{k}$ and $\nexists
r=(t_{r},T_{r},w_{1},\dots,w_{k},\dots,w_{n})\in S$. Since
$(t_{r},T_{r},w_{k})\in s_{k}$, it means that
$\nexists(t_{r}^{\prime\prime},T_{r}^{\prime\prime},w_{k}^{\prime\prime})$
such that $len_{T_{r}^{\prime\prime}}>len_{T_{r}}$ and
$w_{k}^{\prime\prime}\geq w_{k}$, or $w_{k}^{\prime\prime}>w_{k}$ and
$len_{T_{r}}\leq len{T_{r}^{\prime\prime}}$ (1). Also, since $r\notin S$,
$\exists$
$r^{\prime}=(t_{r^{\prime}},T_{r^{\prime}},w_{1}^{\prime},w_{2}^{\prime},\dots,w_{k}^{\prime},\dots,w_{n}^{\prime})$
that dominates $r$. This means that either (i)
$len_{T_{r}}<len_{T_{r^{\prime}}}$ and $w_{i}\leq w_{i}^{\prime},\forall
i,1\leq i\leq n$, or (ii) $len_{T_{r}}\leq len_{T_{r^{\prime}}}$ and
$w_{i}\leq w_{i}^{\prime},\forall i,1\leq i\leq n$ and $\exists y,1\leq y\leq
n$, such that $w_{y}^{\prime}>w_{y}$. If (i) holds, then
$(t_{r}^{\prime},T_{r}^{\prime},w_{k}^{\prime})$ dominates
$(t_{r},T_{r},w_{k})$ which is false since $(t_{r},T_{r},w_{k})\in s_{k}$.
Otherwise, if (ii) holds and based on (1) it holds that
$len_{T_{r}}=len{T_{r}^{\prime}}$ and $w_{k}=w_{k}^{\prime}$, thus,
$r=r^{\prime}$.

###### Lemma 4

The size of the unified skyline $S$ is at most equal to the sum of the sizes
and at least equal to the size of each of the individual skyline sets
$(s_{1},s_{2},\dots,s_{n})$ for $n$ property values combination.

###### Proof

Let us assume that for the size $|S|$ of $S$ it holds that
$|S|>(|s_{1}|+|s_{2}|+\dots+|s_{n}|)$. This implies that $\exists$ result
$(t_{r},T_{r},w_{1},w_{2},\dots,w_{n})\in S$ for which
$(t_{r},T_{r},w_{i})\notin s_{i}$, $\forall$ $w_{i}\in$
$(w_{1},w_{2},\dots,w_{n})$, which is false according to Lemma 3 as $\forall$
$r\in S$ $\exists$ $w_{i}$ for which holds $(t_{r},T_{r},w_{i})\in s_{i}$.
Also let us assume that $\exists$ $s_{i}$ $\in(s_{1},s_{2},\dots,s_{n})$ for
which $|S|<|s_{i}|$. This implies $\exists$ $(t_{r},T_{r},w_{i})\in s_{i}$
which is not included in any of the results $r$ $\in S$. The assumption is
false according to Lemma 3 as every result in the skyline set is necessarily
included in the results of the unified skyline set.

As skylines may contain many results, especially when considering graphs
evolving over long periods of time and multiple property value combinations,
we extend our definition of the unified evolution skyline to the top-$k$
unified evolution skyline. To this end, we define the domination degree.

######  Definition 5 (Domination Degree)

Given an event $\gamma$ and edge label $l_{e}$, the domination degree of a
tuple $r=(t_{r},T_{r},w_{1},\dots,w_{n})$, $dod(r)$, is defined as the number
of tuples $r$ dominates.

To determine the top-$k$ skylines, we rank all
$(t_{r},T_{r},w_{1},\dots,w_{n})$ tuples in the unified evolution skyline
according to their domination degree and retrieve only the top-$k$ ranking
ones.

##  4 Skyline-based exploration

We now describe the evolution skyline computation process, that given an event
$\gamma$, a temporal property graph $G[T]$, an edge label $l_{e}$ and a set of
properties $P\subseteq\mathcal{P}$, computes all non-dominated tuples
$(t_{r},T_{r},W)$, $t_{r}\in T,T_{r}\subset T$ and $W$ is a hash table
containing the counts $count(G_{\gamma}[(t_{r},T_{r})],$ $l_{e},p,p^{\prime})$
for each $p,p^{\prime}$ of $P$.

A naive approach to compute the skyline would entail two phases. First,
computing all possible $(t_{r},T_{r},W)$, i.e., for each $t_{r}\in T$
enumerate all $T_{r}\subset T$ and computing the corresponding $W$, and then
comparing all these tuples so as to eliminate all the dominated ones. However,
this exhaustive approach can be easily improved by pruning all dominated
results as they are derived. We propose incrementally evaluating the skyline
for each reference point $t_{r}$, while at the same time updating the final
skyline as new results are derived.

Input: A temporal property graph $G[T]$, an edge label $l_{e}$, a set of
properties $P$

Output: Skyline set $S_{sky}$, dominance set $S_{dom}$

1 Initialize hash tables
$S_{sky}:len_{T_{r}}\rightarrow{\\{(t_{r},T_{r},W)\\}}$,
$S_{dom}:(t_{r},T_{r},W)\rightarrow{|d|}$, $d:$ set of dominated items

2

3for  _each reference point $t_{r}$_ do

4 $T_{r}\leftarrow$ longest possible interval for $t_{r}$

5 $len_{T_{r}},len_{T_{r_{max}}}\leftarrow length(T_{r})$

6 while  _$len_{T_{r}}\geq 1$_ do

7 Initialize hash table $W_{curr}$

8 Compute $Intersection$ $G_{s}[(t_{r},T_{r})]=G[t_{r}]\cap G[T_{r}]$

9 Compute $Aggregation$ $G_{s}[(t_{r},T_{r}),P]$

10 for  _each property value combination $p,p^{\prime}$ of $P$_ do

11 $W_{curr}[(p,p^{\prime})]=count(G_{s}[(t_{r},T_{r})],l_{e},p,p^{\prime})$

12 $W_{curr}[length]=len_{T_{r}}$

13 $curr\leftarrow(t_{r},T_{r},W_{curr})$

14 $S_{dom}[curr]\leftarrow 0$

15 $len_{prev}\leftarrow len_{T_{r}}$

16 while  _$\nexists$ $S_{sky}[len_{prev}]$ and $len_{prev}\leq
len_{T_{r_{max}}}$_ do

17 $len_{prev}$ $+=1$

18 if  _$len_{prev} >len_{T_{r_{max}}}$_ then

19 $S_{sky}[len_{T_{r}}]\leftarrow curr$

20 $S_{dom}[curr]$ $+=1$

21

22 else

23 for  _each tuple $prev$ $\in$ $S_{sky}[len_{prev}]$_ do

24 if  _for all $(p,p^{\prime})$
$W_{curr}[(p,p^{\prime})]>=W_{prev}[(p,p^{\prime})]$ $and$
$len_{T_{r}}=len_{prev}$ $and$ $\exists$
$W_{curr}[(p,p^{\prime})]>W_{prev}[(p,p^{\prime})]$_ then

25 $S_{dom}[curr]$ $+=1$

26 $S_{dom}[curr]$ $+=S_{dom}[prev]$

27 $remove$ $prev$ $from$ $S_{sky}[len_{prev}]$

28 $S_{sky}[len_{prev}]\leftarrow curr$

29 else if  _for all counts
$W_{curr}[(p,p^{\prime})]<=W_{prev}[(p,p^{\prime})]$ $and$ $len_{T_{r}}\leq
len_{prev}$ $and$ $(\exists$
$W_{curr}[(p,p^{\prime})]<W_{prev}[(p,p^{\prime})]$ $or$
$len_{T_{r}}<len_{prev})$_ then

30 $S_{dom}[prev]$ $+=1$

31 else

32 $S_{sky}[len_{prev}].append(curr)$

33 if  _$len_{T_{r}} >1$_ then

34 $len_{prev}\leftarrow len_{T_{r}}-1$

35 while  _$\nexists$ $S_{sky}[len_{prev}]$ and $len_{prev}\geq 1$_ do

36 $len_{prev}$ $-=1$

37 if  _for all counts $W_{curr}[(p,p^{\prime})]>=W_{prev}[(p,p^{\prime})]$_
then

38 $S_{dom}[curr]$ $+=1$

39 $S_{dom}[curr]$ $+=S_{dom}[prev]$

40 $remove$ $prev$ $from$ $S_{sky}[len_{prev}]$

41 Reduce $T_{r}$

42 $len_{T_{r}}$ $-=1$

43

return _$S_{sky},S_{dom}$_

Algorithm 1 Skyline-based Stability ($\cap$) Exploration

Thus, given a reference point $t_{r}$, we enumerate all possible $T_{r}$ to
compute our candidate tuples. The order in which we enumerate the temporal
elements depends on the semantics used. In particular, when the event $\gamma$
has increasing counts and the skyline consists of minimal temporal elements,
then we start with the shortest temporal element and gradually extend it using
either strict or loose semantics. Similarly, when $\gamma$ has decreasing
counts and the skyline consists of maximal temporal elements, then we start
with the longest temporal element and gradually extend it using either strict
or loose semantics.

The process repeats iteratively for each $t_{r},T_{r}$ pair. First, the event
graph $G_{\gamma}[(t_{r},T_{r})]$ is computed, and then is aggregated on $P$
producing $G_{\gamma}[(t_{r},T_{r}),P]$. To compute the event graph and its
aggregation, we leverage the methods introduced in the GraphTempo framework
Tsoukanara23  that provides efficient algorithms for the implementation of all
temporal operators and property aggregation differentiating between static and
time-varying properties to handle both more efficiently.

Every derived tuple $(t_{r},T_{r},W)$ is considered as a candidate for the
skyline and compared against previous candidate tuples. If it is dominated, it
is ignored and we proceed with the next shorter or longer $T^{\prime}_{r}$.
Otherwise, $(t_{r},T_{r},W)$ is added to the skyline and any previously added
tuple $(t^{\prime}_{r},T^{\prime}_{r},W^{\prime})$ that it dominates is pruned
from the skyline.

The process for skyline evaluation can be extended to support $top$-$k$
skyline evaluation if we evaluate and maintain the domination degree of each
$(t_{r},T_{r},W)$ that is added in our skylines. Initially,
$dod(t_{r},T_{r},W)$ is set to 0. When $(t_{r},T_{r},W)$ is added to the
skyline, if it substitutes other tuples already in the skyline, its
$dod(t_{r},T_{r},W)$ is set to the sum of the $dod$s of all tuples it
substitutes.

Algorithm 1 presents in detail the implementation of the evolution skyline for
the event of stability ($\cap$) where we are interested in maximal temporal
elements. We next prove that Algorithm 1 correctly computes the skyline, while
similar proofs can be derived for other events and semantics.

###### Lemma 5

If a tuple belongs to the skyline, Algorithm 1 will return it, and vice versa,
any result returned by Algorithm 1 belongs to the skyline.

###### Proof

Algorithm 1 considers skylines with maximal temporal elements. Assume for the
purposes of contradiction, that there is a tuple $s=(t_{r},T_{r},W)$ that
belongs to the skyline but is not returned by the algorithm. Since, the
algorithm considers for all reference points, all intervals, this means that
$s$ was considered and it was either (a) not inserted in the skyline in lines
27-28 or (b) was pruned in lines 22-26 or in lines 35-38. If it was not
inserted in lines 27-28, it means that is was dominated by a previous tuple
with all counts and length at least equal, and either one of the counts larger
or length larger, thus $s$ does not belong to the skyline, which is a
contradiction. If it was pruned in lines 22-26, it means that the new tuple
has all counts at least equal, one of the counts is larger and has the same
length, thus $s$ does not belong to the skyline. If it was pruned in lines
35-38, it means that the new tuple has all counts at least equal and longer
interval, thus $s$ does not belong to the skyline. Similarly, suppose a tuple
$s^{\prime}=(t^{\prime}_{r},T^{\prime}_{r},W^{\prime})\notin S_{sky}$ returned
by Algorithm 1. Then, it holds that $\exists$ $s=(t_{r},T_{r},W)$ that
dominates $s^{\prime}$. If $s$ is examined after $s^{\prime}$, if
$len_{T_{r}}=len_{T^{\prime}_{r}}$, the check of lines 22-26 would prune
$s^{\prime}$ as $s$ would have all counts at least equal to those of
$s^{\prime}$ and at least one of them larger, or if
$len_{T_{r}}>len_{T^{\prime}_{r}}$ the check of lines 35-38 would prune
$s^{\prime}$ with counts of $s$ being at least equal to those of $s^{\prime}$.
Otherwise, if $s^{\prime}$ is examined after $s$, lines 27-28 would prune
$s^{\prime}$. Thus, $s^{\prime}\in S_{sky}$.

##  5 Experimental evaluation

For our experiments, we use three real-world datasets.

DBLP: a bibliographic network extracted from DBLP111https://dblp.uni-
trier.de/. The dataset contains 2 labels for nodes, author, conference and 2
labels for edges, collaborate, publish. The dataset covers a period of 21
years from 2000 to 2020, where each year denotes a time point. There is an
edge of label collaborate when two authors co-author a paper in a year where
the direction of the edge indicates the order of the authors of the paper.
Also, there is an edge of label publish when an author publishes to a
conference at a specific year. There are 2 properties for the authors, one
static, gender with 2 values, and one time-varying, #publications per year
with 3 categorical values (low, average, high), and 2 properties for the
conferences, one static, topic with 16 values, and one time-varying, location
with 50 values. Gender is determined utilizing an appropriate
tool222https://github.com/lead-ratings/gender-guesser, topic is inferred from
the name of the conference and location is derived from DBLP.

MovieLens: a movie ratings datasets build on the benchmark MovieLens Harper16
. There are nodes and edges of a single label, user, and co-rate,
respectively. The datasets covers a period of 6 months from May 1st to October
31st of 2000, and each month represents a time point. There is an edge of
label co-rate between two users when they have both rated the same movie. The
direction on edges denotes the precedence of a rating. Each user has 3 static
properties, gender with 2 values, age with 7 categorical values, occupation
with 21 values, and 1 time-varying, average rating of the user per month with
38 values.

Primary School: a contact network describing the face-to-face proximity of 232
students and 10 teachers of a primary school in Lyon, France. The dataset has
nodes and edges of a single label, that is individual and interact,
respectively. Each interaction denotes a 20-second contact between two
individuals. Each individual has 2 static properties, that is gender, class.
The school has 5 grades, 1 to 5, with 2 classes each (i.e., 1A, 1B, 2A, 2B,
etc) plus teachers, and 3 values for gender property, female, male, and
unspecified. Our dataset covers a period of 17 hours.

Tables 1, 2, and 3 show the size of the graphs per time point for the three
datasets.

Our methods are implemented in Python 3.9 and our experiments are conducted in
a Windows 10 machine with Intel Core i5-2430, 2.40GHz processor and 8GB RAM.
Our code and data are publicly
available333https://github.com/etsoukanara/uskylinexplore.

Table 1: DBLP property graph

Type 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013
2014 2015 2016 2017 2018 2019 2020 Nodes author 1708 2165 1761 2827 3278 4466
4730 5193 5501 5363 6236 6535 6769 7457 7035 8581 8966 9660 11037 12377 12996
conference 15 18 20 19 24 25 25 25 23 27 27 29 25 29 27 28 28 32 35 34 28
Edges collaborate 2336 2949 2458 4130 4821 7145 7296 7620 8528 8740 10163
10090 11871 12989 12072 15844 16873 18470 21197 27455 28546 publish 1902 2402
2067 3188 3789 5266 5553 6140 6419 6445 7278 7874 7954 8891 8338 10205 10617
11538 13463 15203 16246

Table 2: MovieLens property graph

| Type | May | Jun | Jul | Aug | Sep | Oct
---|---|---|---|---|---|---|---
Nodes | user | 486 | 508 | 778 | 1309 | 575 | 498
Edges | co-rate | 100202 | 85334 | 201800 | 610050 | 77216 | 48516

Table 3: Primary School property graph

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

###  5.1 Performance evaluation

In the first set of experiments we study the execution time for the unified
skyline exploration for the events of stability ($G_{s}(\cap)$,
$G_{s}(\cup)$), growth ($G_{g}(\cup)$), and shrinkage ($G_{h}(\cup)$). We use
$\cup$ to denote loose semantics, and $\cap$ strict. We aggregate on various
node labels and study the skylines for various edge labels.

In Figures 7, 8 and 9 we report the runtime for computing the skylines as we
increase the size of the graph, considering intervals up to a specific
reference point for the DBLP, MovieLens and Primary School. We notice that
events with loose semantics need longer time to execute compared to strict
ones. Also, we observe that the most time-consuming event overall is
shrinkage.

In Fig. 7(a), we study collaborations for aggregation by gender, while in Fig.
7(b) publications for aggregation by (gender, topic) for the DBLP dataset.
When aggregating by gender, the resulting graph includes aggregate nodes for
authors grouped by gender, while the rest of the nodes in the aggregated
graph, i.e. conferences, remain the same as in the original graph. When
aggregating by both gender for the authors and topic for the conferences, the
entire graph consists of grouped nodes. Consequently, the aggregated graph
produced in Fig. 7(a) is significantly larger comparing to that in Fig. 7(b),
resulting in higher execution time for all kinds of events, especially
impacting $G_{s}(\cup)$.

Moving on to MovieLens, Fig. 8 depicts the execution time for the exploration
of co-rating when aggregating by gender (Fig. 8(a)), age (Fig. 8(b)), and
(gender, age) (Fig. 8(c)). Despite MovieLens having a significantly larger
number of edges compared to DBLP, the exploration of all events requires less
time. This suggests that the number of time points is a crucial factor
influencing the execution time of our algorithm.

Finally, for Primary School, Fig. 9 depicts the execution time for the
interactions when aggregating by gender (Fig. 9(a)), class (Fig. 9(b)), and
(gender, class) (Fig. 9(c)). Notably, the Primary School graph proves to be
faster to explore for any type of event. This is attributed to its smaller
size with a limited number of nodes and edges.

In conclusion, our findings highlight that exploration time is closely linked
to both the number of time points and the size of the graph.

(a)

(b)

Figure 7: Skyline exploration execution time for DBLP for labels (a)
collaborate and aggregation by gender, (b) publish and aggregation by (gender,
topic).

(a)

(b)

(c)

Figure 8: Skyline exploration execution time for MovieLens for label co-rate
and aggregation by (a) gender, (b) age, (c) (gender, age).

(a)

(b)

(c)

Figure 9: Skyline exploration execution time for Primary School for label
interact and aggregation by (a) gender, (b) class, (c) (gender, class).

###  5.2 Qualitative evaluation

In this set of experiments, we present qualitative results regarding the
skyline-based exploration.

#### Skyline size.

First, let us look on the size of both individual and unified skylines. In
Table 4, we report the size of the individual and the unified (denoted by *)
skylines for $G_{s}(\cap)$, $G_{s}(\cup)$, $G_{g}(\cup)$, $G_{h}(\cup)$ for
DBLP, MovieLens, and Primary School. Female and male values are represented as
F and M, respectively. We notice that the skyline exploration that uses loose
semantics generates larger skylines, probably because aggregation with loose
semantics leads to larger graphs compared to the case of strict semantics.

The size of the skyline also depends on the number of dimensions. For example,
the skyline for DBLP and $G_{s}(\cap)$ has size 22 for the collaboration
edges, where the number of dimensions is 5 (F-F, F-M, M-F, M-M, length), while
for the publication edges the skyline size is 117 and the number of dimensions
is 33. The number of time points also affects significantly the size of the
skyline. For example, the sizes of the skylines for MovieLens are in general
smaller than those for DBLP even when the number of dimensions is large. For
example, for $G_{g}(\cup)$ and MovieLens the skyline is of size 5 for co-
rating edges and aggregation by gender with 5 dimensions, and of size 6 for
aggregation by age with 50 dimensions.

As a general observation, our findings are consistent with Lemma 4, as we
notice that the size for the unified skyline does not exceed the sum of the
sizes of the individual skylines and also, it is larger than the size of any
of the individual skylines.

Next, we present case studies of using skylines to explore graph evolution.

#### Individual skylines for stability.

We zoom-in on individual skylines on gender property for Primary School. The
goal is to locate periods of stability for example to design mitigation
strategies for disease containment. Figure 10 presents the skyline output for
the stable ($\cap$) interactions between girls (Fig. 10(a)) and between boys
(Fig. 10(b)). There are longer stability intervals for boys than girls
interactions. We observe that in the skylines for both girls and boys,
intervals with length longer than 7 maintain at most 9 stable interactions,
which can be seen as a bound on the duration and size of isolation bubbles. On
the other hand, we observe an interval of duration 4 (interval [7, 11] at
point of reference 12) with stability at least 32 for both girls and boys
indicating a potential lower risk zone for disease spread.

#### Unified skylines for locating important time periods.

After studying the individual skylines, we will examine the unified skylines
so that we can decide what is the most important period for each event. Since
the unified skyline provides a high number of results, we will focus on the
top-3 skylines based on dod. In Table 5, we present the top-$3$ skyline
results and the reported dod, for the unified skyline exploration for each of
our graph datasets and the events of $G_{s}(\cap)$, $G_{s}(\cup)$,
$G_{g}(\cup)$, and $G_{h}(\cup)$.

For DBLP, we notice that the most important year for collaborations is 2020
where we notice high stability, growth, and shrinkage at the same time. For
MovieLens, we notice that aug is the month with the greatest growth, as there
is a significant increase in the number of edges for August (Table 2). For
Primary School, we notice that the 12th hour is the reference point with the
highest stability ($G_{s}(\cap)$) for the aggregation by gender for the
intervals [10, 11], [8, 11], and [7, 11], which seems reasonable as from 7th
to 12th hour lessons are held and interactions between students are more
stable comparing to breaks. Also, the 13th time point is the most important
one for the event of growth for the aggregation by gender, as the 13th hour
corresponds to break time where students interact with students from other
classes as well.

Table 4: Skyline and unified skyline size | Aggregate | Edge type | $p-p^{\prime}$ |  $G_{s}$($\cap$) |  $G_{s}$($\cup$) |  $G_{g}$($\cup$) |  $G_{h}$($\cup$)
---|---|---|---|---|---|---|---
DBLP | gender | collaborate | F-F | $5$ | $7$ | $8$ | $20$
F-M | $8$ | $13$ | $14$ | $20$
M-F | $8$ | $13$ | $16$ | $20$
M-M | $12$ | $19$ | $19$ | $20$
* | $22$ | $27$ | $35$ | $20$
(gender, topic) | publish | * | $117$ | $145$ | $182$ | $130$
ML | gender | co-rate | F-F | $3$ | $3$ | $5$ | $5$
F-M | $2$ | $4$ | $5$ | $5$
M-F | $2$ | $4$ | $5$ | $5$
M-M | $2$ | $4$ | $5$ | $5$
* | $3$ | $4$ | $5$ | $5$
age | * | $10$ | $15$ | $6$ | $7$
(gender, age) | * | $10$ | $15$ | $8$ | $11$
PM | gender | interact | F-F | $10$ | $9$ | $12$ | $13$
F-M | $17$ | $10$ | $15$ | $15$
M-M | $13$ | $9$ | $13$ | $15$
* | $28$ | $13$ | $19$ | $31$
class | * | $81$ | $131$ | $132$ | $135$
(gender, class) | * | $103$ | $130$ | $131$ | $136$

(a) Girls interactions

(b) Boys interactions

Figure 10: Skyline for the stability event ($\cap$) for (a) F-F and (b) M-M
interactions for Primary School. Table 5: Top-$3$ unified skyline DBLP
---
| collaborate (gender) | dod | publish ((gender, topic)) | dod
$G_{s}$($\cap$) | ([2017], [2000,2016], 1) | 44 | ([2018], [2008, 2017], 37) | 8
([2020], [2019], 2825) | 19 | ([2017], [2008, 2016], 43) | 6
([2019], [2017, 2018], 645) | 16 | ([2018], [2010, 2017], 67) | 5
$G_{s}$($\cup$) | ([2020], [2019], 2825) | 19 | ([2018], [2016, 2017], 3467) | 4
([2020], [2018, 2019], 3688) | 18 | ([2020], [2014, 2019], 6118) | 3
([2020], [2017, 2019], 3992 | 17 | ([2020], [2015, 2019], 5952) | 3
$G_{g}$($\cup$) | ([2019], [2000, 2018], 23475) | 171 | ([2016], [2000, 2015], 6379) | 7
([2019], [2003, 2018], 23478) | 2 | ([2018], [2013, 2017], 8941) | 3
([2020], [2001, 2019], 24117) | 1 | ([2019], [2000, 2018], 9298) | 2
$G_{h}$($\cup$) | ([2020], [2019], 24630) | 19 | ([2020], [2004, 2019], 82294) | 4
([2020], [2018, 2019], 42464) | 18 | ([2019], [2004, 2018], 73725) | 4
([2020], [2017, 2019], 57659) | 17 | ([2018], [2004, 2017], 66141) | 4
ML
| co-rate (gender) | dod | co-rate (age) | dod
$G_{s}$($\cap$) | ([sep], [aug], 957) | 4 | ([sep], [aug], 957) | 0
([oct], [aug, sep], 30) | 3 | ([aug], [jul], 573) | 0
([aug], [jul], 573) | 0 | ([jul], [jun], 425) | 0
$G_{s}$($\cup$) | ([sep], [jul, aug], 1098) | 6 | ([sep], [may, aug], 1185) | 0
([sep], [jun, aug], 1176) | 4 | ([sep], [jun, aug], 1176) | 0
([sep], [aug], 957) | 4 | ([sep], [jul, aug], 1098) | 0
$G_{g}$($\cup$) | ([aug], [may, jul], 609300) | 9 | ([aug], [may, jul], 609300) | 9
([aug], [jun, jul], 609334) | 4 | ([aug], [jun, jul], 609334) | 4
([sep], [may, aug], 76031) | 4 | ([aug], [jul], 609477) | 2
$G_{h}$($\cup$) | ([sep], [aug], 609093) | 4 | ([sep], [aug], 609093) | 4
([sep], [jul, aug], 810179) | 3 | ([sep], [jul, aug], 810179) | 3
([sep], [jun, aug], 894867) | 2 | ([sep], [jun, aug], 894867) | 1
PS
| interact (gender) | dod | interact (class) | dod
$G_{s}$($\cap$) | ([12], [10, 11], 513) | 19 | ([11], [2, 10], 16) | 9
([12], [8, 11], 211) | 19 | ([12], [2, 11], 12) | 7
([12], [7, 11], 138) | 18 | ([12], [1, 11], 7) | 6
$G_{s}$($\cup$) | ([11], [6, 10], 1416) | 79 | ([17], [2, 16], 1341) | 1
([11], [7, 10], 1383) | 76 | ([16], [6, 15], 1000) | 1
([11], [8, 10], 1282) | 72 | ([16], [8, 15], 993) | 1
$G_{g}$($\cup$) | ([13], [1, 12], 731) | 134 | ([17], [1, 16], 356) | 1
([13], [2, 12], 732) | 37 | ([14], [1, 13], 292) | 1
([13], [9, 12], 1112) | 35 | ([16], [7, 15], 54) | 1
$G_{h}$($\cup$) | ([7], [2, 6], 3896) | 28 | ([5], [2, 4], 3227) | 1
([5], [2, 4], 3121) | 27 | ([16], [1, 15], 6101) | 0
([6], [2, 5], 3310) | 21 | ([16], [2, 15], 6081) | 0

#### Comparing individual and unified skylines.

After having studied the important periods as derived by the top-3 skylines
for each event, we will examine the contribution of the individual skylines on
the unified skyline. In other words, we will study the relevant importance of
each individual skyline (i.e., each specific property value combination) in
the results of the unified skyline. We will look into the most influencing
property values for the top-3 skylines based on dod.

In Fig. 11 and Fig. 12, we provide a visualization of the top-$3$ unified
skylines for DBLP and Primary school, respectively. To get more meaningful
results, we have normalized the count of edges by dividing the count for each
property value combination by the maximum reported count for this combination.
Also, we have excluded from the results edges with zero count. Red-colored
areas represent the 1st skyline result, green-colored areas the 2nd skyline
result, and blue-colored areas the 3rd skyline result.

Figure 11(a) illustrates the top-$3$ results for the stable ($\cap$)
publications for the aggregation on (gender, topic). We observe that (M, data
engineering) and (M, pattern recognition) are the most important types of
edges for the event of stability for all three results. Also, we find only 4
results that contain female authors, while 8 results for male authors, which
reflects that women are underrepresented in academic research through time.
Regarding growth, in Fig. 11(b), where we have excluded results with less than
80 edges (for presentation clarity), we observe that new publications in
databases, data management, information retrieval and AI are the most
significant ones regardless of gender, denoting the rapid growth of the
research interest in those fields.

Figure 12 illustrates the top-$3$ skyline results for the event of stability
($\cap$) (Fig. 12(a)) and growth ($\cup$) (Fig. 12(b)) for the aggregation on
class for Primary School. In Fig. 12(a) we observe that the reported results
include only edges between individuals of the same class, which denotes that
students of a class mainly interact and build stable contacts with students of
the same class. The largest interval of stability is observed at the blue area
for the 12th reference point and interval [1, 11] as reported in Table 5,
which corresponds to class time. Also, the result in the red area is worth of
further investigation as it achieves the highest counts on each of the
reported edges. In Fig. 12(b) for clarity of results, we have excluded results
with less than 10 edges. The depicted results confirm our findings from Fig.
12(a), as we notice that new contacts occur mainly between students of
different classes. Also, we notice that students of classes 1, 2 and 3 are the
ones mainly participating in the results, implying that junior and mid-level
students are more social compared to senior ones.

(a)

(b)

Figure 11: Top-$3$ skylines for (a) stable (stability ($\cap$)) and (b) new
(growth ($\cup$)) publications for aggregation on (gender, topic) for DBLP.

(a)

(b)

Figure 12: Top-$3$ skylines for (a) stable (stability ($\cap$)) and (b) new
(growth ($\cup$)) interactions for aggregation on class for Primary School.

##  6 Related work

In this paper, we have proposed exploration based on skylines, for identifying
time periods that dominate other time periods in terms of increased activity
(shrinkage, growth), or lack thereof (stability). To the best of our
knowledge, this is a novel approach.

Regarding previous work on temporal graphs and their evolution, there is some
previous research in defining temporal operators and time and graph
aggregation but provide no exploration strategies. T-GQL Debrouvier21  is an
extension of GQL with temporal operators to handle temporal paths; evolution
is modeled through continuous and consecutive paths. In Orlando23  authors
introduce TGV, a visualization query-driven tool based on T-GQL. The tool
provides graph visualization for the type of paths presented in Debrouvier21 .
TGraph Moffitt17  uses temporal algebraic operators such as temporal selection
for nodes and edges and traversal with temporal predicates on a temporal
property graph. TGraph is extended with attribute and time aggregation that
allows viewing a graph in different resolutions Aghasadeghi20  but only
stability is studied. GRADOOP Rost21 ; Rost22  introduces various extensions
for supporting temporal property graphs such as temporal operators for
grouping and pattern matching. The system provides different graph
visualizations, i.e., the temporal graph view, the grouped graph view, and the
difference graph view that illustrates new, stable and deleted elements
between two graph snapshots. Unlike our work which facilitates a complete
exploration strategy that concerns the history of the graph, the system is
driven by user queries and provides no exploration strategy.

The GraphTempo framework Tsoukanara23  defines temporal operators and supports
both time and attribute aggregation for temporal attributed graphs. An
evolution graph is built by overlaying an intersection and two difference
graphs and interesting events in intervals are detected based on a threshold-
based strategy. An interactive tool for exploring the graph, its aggregations
and the evolution graph is also provided TsoukanaraKP23a . While our approach
relies on the GraphTempo model, here we focus on property graphs. Furthermore,
the GraphTempo exploration strategy requires selecting appropriate thresholds,
our proposed skyline-based approach detects all events effectively without the
need for parameter configuration.

Another approach to temporal graphs, that does not utilize temporal operators,
is versioning (i.e., maintaining previous graph snapshots). In the EvOLAP
graph Guminska18 , versioning is used both for attributes and graph structure
to enable analytics on changing graphs. In Ghrab13 , explicit labeling of
graph elements is designed to support analytical operations over evolving
graphs, and particularly time-varying attributes, while in Andriamampianina22
the designed conceptual model captures changes on the topology, the set of
attributes and the attributes’ values.

There has been a lot of previous work on skylines. Since its introduction
Borzsonyi01 , the skyline operator has been utilized in several domains to
identify dominating entities in multi-criteria selection problems Kalyvas17 .
Although skyline queries are very popular for multi-dimensional data, there is
not much work on skylines over graphs. A domain where skylines were first used
is road networks where the best detours based on a given route Huang04  or the
best places to visit Jang08  are detected using distances among other possible
criteria. In Kriegel10  skylines of routes based on multiple criteria, such as
distance, and cost are also defined. The network is modeled as an multi-
attribute graph and a vector of different optimization criteria is stored for
each edge. In Chowdhury19 , authors explore the concept of skyline path
queries in the context of location-based services, where given a pick-up point
and a destination point the system applies skyline queries based on a set of
features so as to pertain the most useful routes.

Besides road networks, skylines have been defined for graphs using the
shortest path distances between nodes Zou10 . Specifically, given a set of
query nodes, a node $u$ dominates a node $v$, if $u$ is at least as close as
$v$ to all query points and $u$ is closer than $v$ to at least one query
point. A different approach that does not rely on distances is defined in
Weiguo16 , where a skyline consists of subgraphs that best match a given user
query, also represented as a subgraph. Matching relies on isomorphisms and
uses appropriate encoding schemes that capture both structural and numeric
features of the graph nodes. Finally, skylines on knowledge graphs are defined
in Keles19 . The focus is on supporting skyline queries over entities in an
RDF graph through SPARQL queries and the efficient evaluation of such queries,
but while the data are modeled as a graph, skylines are defined on node
attributes and do not take into account graph structure.

Finally, this paper is an extended version of TsoukanaraADBIS23 . While in
TsoukanaraADBIS23 , we consider temporal attributed graphs, in this paper, we
focus on temporal property graphs and present a new form of aggregation.
Furthermore, we extend individual evolution skylines to unified evolution
skylines and offer an extensive quantitative and qualitative evaluation.

##  7 Conclusions

We introduced a unified skyline-based exploration strategy to detect
interesting intervals when a significant number of events occur in the
evolution of a temporal property graph. We considered aggregate graphs and
explored stability, growth and shrinkage, considering all value combinations
for a given set of properties at the same time. We experimentally evaluated
the efficiency and effectiveness of our approach and presented results on
three real datasets.

As a future work we plan to explore efficient strategies in limiting the
number of property values taking into consideration the most influencing ones.
We also plan to integrate our approach for graph aggregation and skyline-based
exploration in an existing property graph database. Finally, since in many
cases, properties have missing or erroneous values, another direction for
future work is to extend aggregation to address this issue and also study its
effect in the analysis of temporal evolution.

## Declarations

### Ethics Approval and Consent to Participate

Not applicable.

### Consent for Publication

Not applicable.

### Availability of Data and Materials

The datasets generated and/or analysed during the current study are available
in the etsoukanara repository, https://github.com/etsoukanara/uskylinexplore.

### Competing Interests

The authors declare that they have no competing interests.

### Funding

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).

### Authors’ Contributions

The study was designed by Evangelia Tsoukanara, Georgia Koloniari and
Evaggelia Pitoura. Material preparation and data collection were performed by
Evangelia Tsoukanara. The data analysis was performed by Evangelia Tsoukanara,
and Georgia Koloniari and Evaggelia Pitoura provided additional expertise. The
first draft of the manuscript was written by Evangelia Tsoukanara and all
authors commented on previous versions of the manuscript. All authors read and
approved the final manuscript.

### Acknowledgements

Not applicable.

## References

  * (1) Aghasadeghi, A., Moffitt, V.Z., Schelter, S., Stoyanovich, J.: Zooming out on an evolving graph.  In: Proceedings of the 23rd International Conference on Extending Database Technology, EDBT 2020 (2020)
  * (2) Andriamampianina, L., Ravat, F., Song, J., Vallès-Parlangeau, N.: Graph data temporal evolutions: From conceptual modelling to implementation.  Data Knowl. Eng. (2022)
  * (3) Angles, R.: The property graph database model.  In: Alberto Mendelzon Workshop on Foundations of Data Management (2018).  URL https://api.semanticscholar.org/CorpusID:43977243
  * (4) Börzsönyi, S., Kossmann, D., Stocker, K.: The skyline operator.  In: Proceedings of the 17th International Conference on Data Engineering (2001)
  * (5) Chowdhury, N., Arefin, M.S.: Skyline path queries for location-based services.  International Journal of Advanced Computer Science and Applications (2019)
  * (6) Debrouvier, A., Parodi, E., Perazzo, M., Soliani, V., Vaisman, A.A.: A model and query language for temporal graph databases.  VLDB J. (2021)
  * (7) Gemmetto, V., Barrat, A., Cattuto, C.: Mitigation of infectious disease at school: targeted class closure vs school closure.  BMC Infectious Diseases (2014)
  * (8) Ghrab, A., Skhiri, S., Jouili, S., Zimányi, E.: An analytics-aware conceptual model for evolving graphs.  In: Data Warehousing and Knowledge Discovery - 15th International Conference, DaWaK 2013 (2013)
  * (9) Guminska, E., Zawadzka, T.: Evolap graph - evolution and olap-aware graph data model.  In: Beyond Databases, Architectures and Structures. Facing the Challenges of Data Proliferation and Growing Variety - 14th International Conference, BDAS 2018, Communications in Computer and Information Science (2018)
  * (10) Harper, F.M., Konstan, J.A.: The movielens datasets: History and context.  ACM Trans. Interact. Intell. Syst. (2016)
  * (11) Huang, X., Jensen, C.S.: In-route skyline querying for location-based services.  In: Web and Wireless Geographical Information Systems, 4th InternationalWorkshop, W2GIS 2004 (2004)
  * (12) Jang, S., Yoo, J.: Processing continuous skyline queries in road networks.  In: International Symposium on Computer Science and its Applications (2008)
  * (13) Kalyvas, C., Tzouramanis, T.: A survey of skyline query processing.  CoRR (2017)
  * (14) Keles, I., Hose, K.: Skyline queries over knowledge graphs.  In: The Semantic Web – ISWC 2019. Springer International Publishing (2019)
  * (15) Kriegel, H.P., Renz, M., Schubert, M.: Route skyline queries: A multi-preference path planning approach.  In: 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010) (2010)
  * (16) Moffitt, V.Z., Stoyanovich, J.: Temporal graph algebra.  In: Proceedings of The 16th International Symposium on Database Programming Languages, DBPL 2017 (2017)
  * (17) Orlando, D., Ormachea, J., Soliani, V., Vaisman, A.: Tgv: A visualization tool for temporal property graph databases (2023)
  * (18) Rost, C., Gómez, K., Fritzsche, P., Thor, A., Rahm, E.: Exploration and analysis of temporal property graphs.  In: Proceedings of the 24th International Conference on Extending Database Technology, EDBT 2021 (2021)
  * (19) Rost, C., Gómez, K., Täschner, M., Fritzsche, P., Schons, L., Christ, L., Adameit, T., Junghanns, M., Rahm, E.: Distributed temporal graph analytics with GRADOOP.  VLDB J. (2022)
  * (20) Tsoukanara, E., Koloniari, G., Pitoura, E.: Graphtempo: An aggregation framework for evolving graphs.  In: Proceedings 26th International Conference on Extending Database Technology, EDBT 2023 (2023)
  * (21) Tsoukanara, E., Koloniari, G., Pitoura, E.: Skyline-based temporal graph exploration.  In: Advances in Databases and Information Systems - 27th European Conference, ADBIS 2023 (2023)
  * (22) Tsoukanara, E., Koloniari, G., Pitoura, E.: Tempographer: A tool for aggregating and exploring evolving graphs.  In: Proceedings 26th International Conference on Extending Database Technology, EDBT 2023 (2023)
  * (23) Zheng, W., Lian, X., Zou, L., Hong, L., Zhao, D.: Online subgraph skyline analysis over knowledge graphs.  IEEE Trans. Knowl. Data Eng. (2016)
  * (24) Zou, L., Chen, L., Özsu, M.T., Zhao, D.: Dynamic skyline queries in large graphs.  In: Database Systems for Advanced Applications, 15th International Conference, DASFAA 2010 (2010)