Michelle Doering (Hasso Plattner Institute, Germany)
Reachability in temporal graph settings: A structural comparison
Abstract:
Temporal graphs model networks with time-dependent connections. Small changes in their definition—such as whether paths must strictly increase in time,
whether adjacent edges may be active simultaneously, or whether multiple labels are allowed—give rise to different classes of temporal graphs
(temporal settings). In this talk, we analyze these classes through the lens of reachability equivalence: when do two temporal graph (classes)
induce the same reachability graphs? We discuss recent results and analyze the relations between aforementioned temporal settings.
Duncan Adamson (University of St. Andrews, UK)
Exploring temporal graphs with frequent edges
Abstract:
Exploration is one of the best studied problems on temporal graphs, asking if an agent can visit every vertex in a temporal graph within a given
timeframe, while only being allowed to transition across a single active edge in each tilmestep. In this talk, we focus on on temporal graphs
with frequent edges, edges where we have a bound on the number of time steps between each activation.
We show that temporal graphs with highly frequent edges can be explored efficiently, requiring \(2F\) time steps where \(F\)
is a parameter based on the weight of the spanning tree on the underlying graph, with each edge weighted by it frequency.
We extend this to several applications, including public transport network graphs (graphs formed by merging several temporal walks)
and broadcast networks (temporal graphs modelling communication networks in the broadcast model).
Nicolas Klodt (Hasso Plattner Institute, Germany)
Exploration of random temporal graphs
Abstract:
The temporal exploration problem (TEXP) asks for a walk in a given temporal graph, where at most one edge is traversed in each time step,
and all vertices are visited. In this talk we will consider the temporal exploration problem (TEXP) on a model of random temporal graphs
which are connected in each time step. It is known that there are n-vertex temporal graphs which are connected in each time step but
require \(\Omega(n^2)\) steps to explore, our aim is to understand what happens against a random adversary.
In our model an adversary supplies a measure \(\mu\) supported on a set of (labelled) spanning trees on \(n\) vertices,
and we obtain a (random) temporal graph by sampling a spanning tree from \(\mu\) at each time step independently.
We show that, for any \(\mu\), w.h.p. there is a schedule which explores the corresponding temporal graph in time \(O(n^{3/2})\).
Furthermore, we provide an example of \(\mu\) which requires \(\Omega(n^{3/2})\) steps to explore in expectation.
This is joint work with Samuel Baguley, Andreas Göbel, George Skretas, John Sylvester and Viktor Zamaraev.
Gabor Lugosi (Universitat Pompeu Fabra, Barcelona, Spain)
Paths and cliques in random temporal graphs
Abstract:
Motivated by modeling time-dependent processes on networks like social interactions and infection spread, we consider a version of the
classical Erdős–Rényi random graph \(G(n,p)\) where each edge has a distinct random timestamp, and connectivity is constrained to sequences
of edges with increasing time stamps. We present results on the lengths of the shortest and longest increasing paths, as well as the size
of the largest temporal clique that exhibits a remarkable phase transition. We also introduce a novel random tree model motivated by random
temporal graphs. This talk is based on joint work with Nicolas Broutin, Nina Kamčev, Caelan Atamanchuk, and Luc Devroye.
Daniele Carnevale (Gran Sasso Science Institute, Italy)
Dismountability in temporal cliques revisited
Abstract:
Temporal graphs do not always admit small subsets of edges that preserve connectivity (temporal spanners).
However, in the case of temporal cliques, spanners of size \(O(n log n)\) are guaranteed. The original proof of this result combined
a number of techniques, one of which is dismountability. In this talk, we show that dismountability is actually all you need,
combining different versions of this core principle that have been developed by several groups of researchers in the recent years.
If time permits, I will then discuss some connections between dismountability and another core technique called pivotability,
and present a new class of labelings that admit spanners of size \(2n-3\).
This is joint work with Arnaud Casteigts and Timothée Corsini [SAND 2025].
Jayakrishnan Madathil (University of Glasgow, UK)
Temporal triadic closure: Finding dense structures in social networks that evolve
Abstract: A graph \(G\) is \(c\)-closed if every two vertices with at least \(c\) common neighbors are adjacent to each other. This definition is an abstraction of the triadic closure property exhibited by many real-world social networks, namely, friends of friends tend to be friends themselves. Social networks, however, are often temporal rather than static---the connections change over a period of time. And hence temporal graphs, rather than static graphs, are often better suited to model social networks. Motivated by this, we introduce a definition of temporal \(c\)-closed graphs, in which if two vertices \(u\) and \(v\) have at least \(c\) common neighbors during a short interval of time, then \(u\) and \(v\) are adjacent to each other around that time. Our preliminary empirical analysis indicates that real-world temporal networks are \(c\)-closed for rather small values of \(c\). We also study the computational problems of enumerating maximal cliques and similar dense subgraphs in temporal \(c\)-closed graphs. We bound the number of such maximal dense subgraphs in a temporal \(c\)-closed graph that evolves slowly, and thus show that the corresponding enumeration problems admit efficient algorithms; by slow evolution, we mean that between consecutive time-steps, the local change in adjacencies remains small. Our work also adds to a growing body of literature on defining suitable structural parameters for temporal graphs that can be leveraged to design efficient algorithms. This is joint work with Tom Davot, Jessica Enright and Kitty Meeks.
Ana Silva (Federal University of Ceará, Brasil)
On graph problems stemming from temporal graphs
Abstract:
In this talk, I will present some graph open problems and results that stemmed from research on Temporal Graphs.
Mikael Rabie (Université Paris Cité, France)
How to color temporal graphs to ensure proper transitions
Abstract: Graph Coloring consists in assigning colors to vertices, ensuring that two adjacent vertices do not have the same color. In dynamic graphs, this notion is not well defined, as we need to decide if different colors for adjacent vertices must happen all the time or not, and how to go from a coloring at one time to the next one. We will define a coloring notion for Temporal Graphs where, at each step, the coloring must be proper. It uses a notion of compatibility between two consecutive snapshots that implies that the coloring stays proper while the transition happens. Given a graph, the minimum number of colors needed to ensure that such a coloring exists is the Temporal Chromatic Number of this graph. With those notions, we provide some lower and upper bounds for the temporal chromatic number in the general case. We then dive into some specific classes of graphs, such as trees, graphs with bounded degree, or bounded degeneracy. Finally, we consider temporal graphs where grow pace is one, that is, a single edge can be added and a single other one can be removed between two time steps. In that case, we consider bipartite and bounded-degree graphs. Even though the problem is defined with full knowledge of the temporal graph, our results also work in the case where future snapshots are given online: we need to choose the coloring of the next snapshot after having computed the current one, not knowing what will come later. This is a joint work with Allen Ibiapina, Minh-Hang Nguyen and Cléophée Robin. arXiv version: https://arxiv.org/abs/2505.10207.
Aurora Rossi (DS4H Université Côte d’Azur, France)
Temporal graph neural networks and their applications
Abstract:
Graphs offer a flexible way to represent complex relationships in many domains, including social networks, biology, and neuroscience.
In recent years, Graph Neural Networks (GNNs) have become popular tools for learning from such structured data, showing strong performance
in tasks like node classification, link prediction, and graph-level analysis. However, many systems in the real world are not static,
they change over time. To take these dynamics into account, we need models that can reason not only about how things are connected, but also when.
In this talk, I will give a general introduction to GNNs and then focus on their temporal counterparts: Temporal Graph Neural Networks (TGNNs).
These models are designed to work with dynamic graphs, where both the structure and features can evolve.
I will describe some of the main types of TGNNs proposed in the literature and explain how they work.
To conclude, I will show a few examples of how TGNNs can be applied in practice, including in the analysis of traffic data and the
modeling of brain activity over time.
Ilie Sarpe (KTH, Sweden)
Scalable temporal motif densest subnetwork discovery
Abstract:
Finding dense subnetworks, with density based on edges or more complex structures, such as subgraphs or $k$-cliques,
is a fundamental algorithmic problem with many applications. While the problem has been studied extensively in static networks,
much remains to be explored for temporal networks.
In this work we introduce the novel problem of identifying the temporal motif densest subnetwork, i.e., the densest subnetwork
with respect to temporal motifs, which are high-order patterns characterizing temporal networks. Identifying temporal motifs is
an extremely challenging task, and thus, efficient methods are required to compute the temporal motif densest subnetwork.
To address this challenge, we design two novel randomized greedy approximation algorithms with rigorous probabilistic guarantees
that provide high-quality solutions. We perform extensive experiments showing that our methods outperform baselines based on
state-of-the-art approaches for an analogous static problem. Furthermore, our algorithms scale on networks with up to billions
of temporal edges, while baselines cannot handle such large networks. We use our techniques to analyze a financial network and
show that our formulation reveals important network structures.
This is joint work with Fabio Vandin and Aristides Gionis [KDD 2024].
Workshop organizers*
George B. Mertzios (Durham University, UK)
Paul G. Spirakis (University of Liverpool, UK and University of Patras, Greece)
Eleni C. Akrida (Durham University, UK)
Viktor Zamaraev (University of Liverpool, UK)
* Partially supported by the EPSRC grants EP/P020372/1 and EP/P02002X/1, and by the EEE/CS University of Liverpool Initiative NeST.