When to Recompute: Wasserstein Embeddings for Change-Aware Influence Maximization in Temporal Networks
Computation · 07.11.2026 · 14 (11) · 281
DOI: 10.3390/computation14110281 ↗Kurz gefasst
Fachartikel in der Zeitschrift Computation, online erschienen am 07.11.2026. Verfasst von Priyanka Gautam und 1 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: U.S. National Science Foundation.
Abstract (Originalsprache)
Dynamic real-world networks, such as communication, social interaction, and infrastructure networks, evolve continuously, posing significant challenges for scalable graph analysis. Graph-based tasks such as critical node identification, community detection, and influence maximization must be updated as these networks change. Yet, most structural changes have little effect on their results, so recomputing after every update is often redundant. When a change does matter, however, recomputation is expensive: identifying a small set of seed nodes that maximizes information spread under cascade diffusion is NP-hard, and even approximate solutions require greedy search with repeated Monte Carlo simulation. We therefore ask when network evolution invalidates the current seed set enough to justify recomputation. We build on Wasserstein Embedding for Graph Learning (WEGL), whose fixed-dimensional representations allow structural changes between snapshots to be detected through embedding distances. We extend these embeddings to influence maximization by training a regression model that predicts the influence spread of each snapshot without simulation. Combining both signals, we propose WEGL-IM, a framework with a two-stage change detection mechanism and an adaptive baseline, which recomputes the seeds only when both the predicted spread and the structure have drifted since the last recomputation. Experiments on six real-world temporal networks show that the embeddings predict the influence spread well. The test R2 is 0.70–0.97 under independent cascade and 0.49–0.92 under weighted cascade. WEGL is more accurate than graph neural networks in 10 of 12 settings and than graph statistics in 7 of 12. WEGL-IM retains 1–2 percentage points more spread than periodic recomputation with the same budget on Email-Eu-Core and Bitcoin Alpha. On CollegeMsg and MathOverflow, it performs on par with periodic recomputation. On the real networks, whose snapshots are small and sparse, monitoring is slower than recomputing on three of four networks. On synthetic graphs with 20,000 nodes, embedding a snapshot is about 13 times faster than one greedy recomputation.
Förderung
- U.S. National Science Foundation
Zitieren
APA
Gautam, P., & Natarajan, B. (2026). When to Recompute: Wasserstein Embeddings for Change-Aware Influence Maximization in Temporal Networks. Computation, 14(11), 281. https://doi.org/10.3390/computation14110281
Vancouver
Gautam P, Natarajan B. When to Recompute: Wasserstein Embeddings for Change-Aware Influence Maximization in Temporal Networks. Computation. 2026;14(11):281. doi:10.3390/computation14110281
BibTeX
@article{Gautam2026,
author = {Gautam, Priyanka and Natarajan, Balasubramaniam},
title = {When to Recompute: Wasserstein Embeddings for Change-Aware Influence Maximization in Temporal Networks},
journal = {Computation},
year = {2026},
volume = {14},
number = {11},
pages = {281},
doi = {10.3390/computation14110281}
}
EUVIMED