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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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∗p^{\ast} . (c) The normalized index difference i/T1−j/T2i/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 DTWtime-shiftnorm=0.02\text{DTW}^{\text{norm}}_{\text{time-shift}}=0.02 , 0.100.10 , and 0.370.37 , respectively. Both dissimilarity measures ( DTWtime−shfitnorm{\rm DTW}^{\rm norm}_{\rm time-shfit} and JSDnorm{\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 norm\mathrm{norm} . (b) Boxplots of the corresponding final epidemic sizes. All three pairs yield highly similar final distributions, with JSDnorm=0\text{JSD}^{\rm norm}=0 , 00 , and 0.090.09 for the left, center, and right panels, respectively.
CategoryNameDefinition
Topologicalavg_strengthAverage node strength
std_strengthStandard deviation of strength across nodes
weighted_clusteringAverage fraction of closed triangles per node
assortativityDegree assortativity coefficient
community_entropyQuantifies the strength of a community structure
n_nodesNumber of nodes
Table 1: Topological and temporal graph features used in the analysis. Detailed definitions are provided in Section 4.4 .
ContextDescriptionNodesDuration
Primary School [ 43 ]Students and teachers from a primary school2422 days
High School 1 [ 44 ]Students and teachers from a high school1264 days
High School 2 [ 44 ]Students from a high school1807 days
High School 3 [ 45 ]Students from a high school3275 days
Conference [ 46 ]Participants in a scientific conference4052 days
Office [ 46 ]Workers in an office23210 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 γi∗\gamma_{i}^{*} assigned to each of the 1515 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 5050 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(G1,G2)+1]\log[d(\mathcal{G}_{1},\mathcal{G}_{2})+1] ; (center panel) the unconstrained feature-based component of EATGD, ∑fγf(Δf)2\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 pp -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 γi∗\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(G1,G2)+1]\log[d(\mathcal{G}_{1},\mathcal{G}_{2})+1] ; (center) the unconstrained feature-based component of EATGD, ∑fγf(Δf)2\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 ( ρ=−0.98\rho=-0.98 ) — whereas the constrained EATGD consistently matches or outperforms the topological baseline across all four held-out pairs.
More in this topic

Dynamic Time Warping

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

See all 14 papers

Explore similar work

CardsList
May 30, 2025

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

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.

Franziska Heeg, Jonas Sauer, Petra Mutzel +1

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 GNNsGNN Expressivity
AskPDF
Oct 15, 2026

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

Accurate medium- to long-range epidemic forecasting requires extrapolating high-dimensional, heterogeneous and nonstationary dynamics from partial observations. Yet hybrid models often leave implicit which observations inform which epidemic processes and how learned graph interactions modify system state. We introduce LE-EpiGNODE, which replaces generic message passing with process-specific, mechanism-guided neural operators: age-contact information drives Lagrangian infection generation, whereas mobility drives conservative Eulerian population transport within a structure-preserving universal differential equation. We evaluated LE-EpiGNODE across 14 controlled synthetic mechanisms spanning time-modulated, state-dependent, nonlinear and coupled dynamics, three complementary COVID-19 settings, 21 comparator models and five targeted ablations. Forecasting gains tended to become more pronounced at longer horizons; at the longest horizon, LE-EpiGNODE achieved the lowest WMAPE in all three real-world datasets, reducing error by 17.7-40.0% relative to the best baseline. Controlled ablations linked these gains to the Lagrangian-Eulerian decomposition and process-aligned priors, while synthetic ground truth showed that learned operators and induced state fluxes track known generating dynamics. These results support mechanism-organized graph neural dynamics as a route to reliable long-horizon extrapolation with directly testable, process-level mechanistic interpretation beyond trajectory accuracy.

Jinyi Duan, Qian Li, Biao Tang

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 .

Epidemic ForecastingSpatial Epidemic ModelingSpatiotemporal GNNsLong-Term Time Series ForecastingNeural ODEsExplainable Time Series Forecasting
AskPDF
Jan 10, 2020

Time-Varying Graph Learning with Constraints on Graph Temporal Variation

We propose a novel framework for learning time-varying graphs from spatiotemporal measurements. Given an appropriate prior on the temporal behavior of signals, our proposed method can estimate time-varying graphs from a small number of available measurements. To achieve this, we introduce three regularization terms in convex optimization problems that constrain the sparseness of temporal variations of the time-varying networks. Moreover, a computationally scalable algorithm is introduced to solve the optimization problem efficiently. The experimental results with synthetic and real datasets (point cloud, temperature, and EEG data) demonstrate that our proposed method outperforms state-of-the-art methods.

Haruki Yokota, Koki Yamada, Yuichi Tanaka +1

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

Graph Signal ProcessingGraph Structure LearningGraph Representation LearningDynamic Graph Learning
AskPDF