Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening

Graph coarsening is a fundamental dimensionality reduction technique for scaling large graphs while preserving structural and feature information. However, most existing coarsening methods are designed for static graphs and do not extend well to dynamic settings where nodes, edges, and connectivity patterns evolve over time. Recomputing a coarsened graph from scratch after every update is often infeasible, which limits scalability and real-time applicability. To address this, we propose a unified framework for coarsening discrete-time dynamic graphs by incrementally updating the coarsening mapping matrix. The framework initializes from any static coarsening technique and then efficiently incorporates real-world graph events, including node additions, node deletions, and edge modifications. We instantiate this framework with two optimization based incremental update algorithms tailored to different dynamic regimes, one focusing on efficiently integrating growth related changes and another handling broader topology evolution with adaptive reassignment. We derive fast and scalable solvers with convergence guarantees, and provide theoretical guarantee via $\epsilon$-similarity bounds that quantify and control quality degradation in the coarsened graph. Extensive experiments under realistic dynamic scenarios show substantial improvements in runtime and memory, delivering significant speedups while maintaining or improving downstream task performance, including graph neural network accuracy.

Many real-world systems can be represented as networks: people interact in social networks, papers cite other papers, computers communicate with each other, and molecules contain connected atoms. These networks are often very large, so researchers commonly create smaller versions that are faster to store, process, and use for machine learning. However, real networks do not stay fixed: new nodes appear, old nodes disappear, and connections change over time. Existing methods usually rebuild the smaller network from scratch after every change, which can be slow and memory-intensive. This paper introduces a way to update the smaller network efficiently as the original network evolves. Instead of starting over each time, our method reuses the previous compressed network and only updates the parts affected by new or changed connections. We develop two update strategies: one for networks that mostly grow over time, and another for networks whose existing structure also changes. Experiments on real and synthetic datasets show that our approach reduces runtime and memory use while preserving the information needed for downstream tasks such as node classification. This makes large evolving networks easier to analyze in practical settings where updates happen repeatedly.