A temporal graph dissimilarity measure capturing epidemic spreading behavior

Salvatore Freni; Lorenzo Dall'Amico; Francesca Pistilli; Alain Barrat; Tatiana Tommasi; Ciro Cattuto

cs.SIOct 12, 2026

A temporal graph dissimilarity measure capturing epidemic spreading behavior

Authors: Salvatore Freni, Lorenzo Dall'Amico, Francesca Pistilli, Alain Barrat, Tatiana Tommasi, Ciro Cattuto

Organizations: ISI Foundation, Turin, Italy · Politecnico di Torino, Turin, Italy · Aix Marseille Univ, Univ Toulon, CNRS, CPT, Turing Center for Living Systems, Marseille, France

Abstract

Comparing temporal networks is a challenging problem in network analysis. Commonly adopted methods compare structural properties of temporal graphs and can be highly sensitive to the pre-selected features. However, temporal networks are the support of dynamical processes, and a process may take place in statistically indistinguishable ways on structurally different temporal graphs. In particular, a dissimilarity measure that compares temporal graphs based on how spreading processes unfold on them is highly desirable. In this work, we first define the Time-Shift DTW, a dissimilarity between epidemic curves that accounts for both differences in their shape and temporal shifts. We then introduce Epidemic-Aware Temporal Graph Dissimilarity (EATGD), a deterministic and differentiable dissimilarity between temporal graphs that combines an embedding-based temporal graph distance with a set of topological and temporal features. Its parameters are calibrated using stochastic SIR simulations to maximize the correlation with the Time-Shift DTW, after which graph comparisons require no further epidemic simulations. Using empirical human proximity networks from the SocioPatterns collaboration and synthetic temporal graphs, we show that EATGD captures epidemic-based graph dissimilarity and generalizes across heterogeneous network settings. Its differentiability and computational efficiency make EATGD suitable for integration into machine-learning pipelines and provide a potential loss function for training generative models to reproduce epidemic dynamics without requiring an exact reconstruction of fine-grained network structure.

Figures & tables

Figure 1: Visual representation of the Time-Shift DTW. (a) DTW alignment between two trajectories. The dashed gray lines illustrate the point-to-point matching. (b) The cumulative cost matrix with the optimal warping path $p^{\ast}$ . (c) The normalized index difference $i/T_{1}-j/T_{2}$ evaluated along the normalized path position. The vertical dashed line indicates the average of these differences, yielding the normalized lead-lag, used to penalize the temporal misalignment.

Figure 2: Comparison of epidemic similarities across three pairs of curves of number of infected individuals. (a) Epidemic trajectories, represented by the fraction of infected nodes over time, for three pairs of temporal networks (Network 1 and Network 2 in each pair). The details of the implementation are given in the Methods. Solid lines indicate the mean trajectories, while the shaded areas delimit the 5th–95th percentile bands of the simulations. The curves display increasing levels of dynamic discrepancy and temporal misalignment from left to right, yielding

\text{DTW}^{\text{norm}}_{\text{time-shift}}=0.02

0.10

, and

0.37

, respectively. Both dissimilarity measures (

{\rm DTW}^{\rm norm}_{\rm time-shfit}

and

{\rm JSD}^{\rm norm}

) are normalized by their respective 90th percentiles across the dataset, allowing their values to be compared on the same scale; normalized quantities are denoted by the superscript

\mathrm{norm}

. (b) Boxplots of the corresponding final epidemic sizes. All three pairs yield highly similar final distributions, with

\text{JSD}^{\rm norm}=0

0

, and

0.09

for the left, center, and right panels, respectively.

Category	Name	Definition
Topological	avg_strength	Average node strength
	std_strength	Standard deviation of strength across nodes
	weighted_clustering	Average fraction of closed triangles per node
	assortativity	Degree assortativity coefficient
	community_entropy	Quantifies the strength of a community structure
	n_nodes	Number of nodes

Table 1: Topological and temporal graph features used in the analysis. Detailed definitions are provided in Section 4.4 .

Context	Description	Nodes	Duration
Primary School [ 43 ]	Students and teachers from a primary school	242	2 days
High School 1 [ 44 ]	Students and teachers from a high school	126	4 days
High School 2 [ 44 ]	Students from a high school	180	7 days
High School 3 [ 45 ]	Students from a high school	327	5 days
Conference [ 46 ]	Participants in a scientific conference	405	2 days
Office [ 46 ]	Workers in an office	232	10 days

Table 2: Summary description of the SocioPatterns social networks. It includes a description of the environment, the number of nodes and the duration of the data collection.

Figure 3: Feature importance for the calibrated EATGD. (Top) Learned weights

\gamma_{i}^{*}

assigned to each of the

15

graph features when calibrating EATGD on the SocioPatterns training set, colored by feature category (topological vs. temporal). (Bottom) Distribution of the importance weights attributed by the Differentiable Information Imbalance (DII) to each feature, for three target dissimilarities: Time-Shift DTW, the baseline temporal graph distance, and the optimized EATGD. Boxplots are obtained from

50

independent DII runs with random initializations.

Figure 4: Performance of EATGD in out-of-distribution scenarios. The scatter plots compare the Time-Shift DTW with: (left panel) the baseline temporal graph distance,

\log[d(\mathcal{G}_{1},\mathcal{G}_{2})+1]

; (center panel) the unconstrained feature-based component of EATGD,

\sum_{f}\gamma_{f}(\Delta f)^{2}

, excluding the graph-distance term; and (right panel) the constrained EATGD, which includes only the features that are well represented in the training set, as described in the main text. The titles report the Pearson correlation coefficient

\rho

. The

p

-values are reported only for non-significant correlations.

Figure 5: Sensitivity analysis of the Time-Shift DTW. (a) Schematic representation of the morphological transformations applied to the baseline bi-Gaussian curve (dashed blue lines) to generate the perturbed trajectories (solid outlines). (b) Distributions of the empirically computed sensitivities for each parameter. The strictly positive boxplots, evaluated over a large set of randomly sampled configurations, demonstrate the measure’s consistent responsiveness to diverse temporal and morphological variations.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure S.1 : Feature importance distributions across target measures (synthetic dataset). (Top) Learned weights

\gamma_{i}^{*}

for each graph feature obtained when calibrating EATGD on the synthetic training set, colored by feature category (topological vs. temporal). (Bottom) Comparison of the importance weights attributed by DII to each feature for Time-Shift DTW, the baseline temporal graph distance, and the optimized EATGD. Boxplots are obtained from 50 independent DII runs.

Figure S.2 : Extended performance of EATGD in out-of-distribution scenarios. Each row reports a different cross-environment evaluation: all temporal graphs from the two environments named above the row ( e.g. , Highschool 2011 and Hospital ) are held out as the test set, while EATGD is calibrated on the remaining SocioPatterns environments. The scatter plots compare the Time-Shift DTW against: (left) the baseline topological distance,

\log[d(\mathcal{G}_{1},\mathcal{G}_{2})+1]

; (center) the unconstrained feature-based component of EATGD,

\sum_{f}\gamma_{f}(\Delta f)^{2}

, excluding the graph-distance term; and (right) the constrained EATGD, obtained by applying the statistical gating described in the main text. The unconstrained feature-based component is unstable out of distribution — in the most extreme case ( Highschool 2012 and Primary School , bottom row) it is anti-correlated with the Time-Shift DTW (

\rho=-0.98

) — whereas the constrained EATGD consistently matches or outperforms the topological baseline across all four held-out pairs.

Dynamic Time Warping

Dynamic Time Warping aligns sequences with nonlinear timing differences to compare, classify, or transform time-series data.

See all 14 papers

Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs
May 30, 2025Franziska Heeg, Jonas Sauer, Petra Mutzel +1Temporal GNNs GNN Expressivity
Chair of Machine Learning for Complex Networks, Center for AI and Data Science (CAIDAS), University of Würzburg, Würzburg, Germany · Karlsruhe Institute of Technology, University of Karlsruhe, Karlsruhe, Germany · Chair of Computational Analytics, Institute for Computer Science 1, University of Bonn, Bonn, Germany
Learning and Forecasting Multiscale Spatiotemporal Epidemic Dynamics with Lagrangian-Eulerian Graph Neural ODEs
Oct 15, 2026Jinyi Duan, Qian Li, Biao TangEpidemic Forecasting Spatial Epidemic Modeling
School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, 710049, People’s Republic of China . · School of Mathematics and Statistics, Xi’an University of Technology, Xi’an, 710054, People’s Republic of China . · Center for Intersection of Mathematics and Life Sciences, Xi’an Jiaotong University, Xi’an, 710049, People’s Republic of China .
Time-Varying Graph Learning with Constraints on Graph Temporal Variation
Jan 10, 2020Haruki Yokota, Koki Yamada, Yuichi Tanaka +1Graph Signal Processing Graph Structure Learning
Graduate School of Engineering, The University of Osaka, Osaka 565-0871, Japan · Graduate School of Engineering, Tokyo University of Agriculture and Technology, Tokyo 184-8588, Japan · Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA 90089 USA

May 30, 2025J/K move · Enter open · S save

Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs

Franziska Heeg, Jonas Sauer, Petra Mutzel, Ingo Scholtes

Chair of Machine Learning for Complex Networks, Center for AI and Data Science (CAIDAS), University of Würzburg, Würzburg, Germany · Karlsruhe Institute of Technology, University of Karlsruhe, Karlsruhe, Germany · Chair of Computational Analytics, Institute for Computer Science 1, University of Bonn, Bonn, Germany

Temporal GNNs GNN Expressivity

Open paper AskPDF arXiv

An important characteristic of temporal graphs is how the directed arrow of time influences their causal topology, i.e., which nodes can possibly influence each other causally via time-respecting paths. The resulting patterns are often neglected by temporal graph neural networks (TGNNs). To formally analyze the expressive power of TGNNs, we lack a generalization of graph isomorphism to temporal graphs that fully captures their causal topology. Addressing this gap, we introduce the notion of consistent event graph isomorphism, which utilizes a time-unfolded representation of time-respecting paths in temporal graphs. We compare this definition with existing notions of temporal graph isomorphisms. We illustrate and highlight the advantages of our approach and develop a temporal generalization of the Weisfeiler-Leman algorithm to heuristically distinguish non-isomorphic temporal graphs. Building on this theoretical foundation, we derive a novel message passing scheme for temporal graph neural networks that operates on the event graph representation of temporal graphs. An experimental evaluation shows that our approach performs well in a temporal graph classification experiment.

Abstract

Dynamic Time Warping

Explore similar work

Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs

Learning and Forecasting Multiscale Spatiotemporal Epidemic Dynamics with Lagrangian-Eulerian Graph Neural ODEs

Time-Varying Graph Learning with Constraints on Graph Temporal Variation