Querying Cohesive Subgraphs in Temporal Graphs

Temporal graphs are widely used to model dynamic interactions across diverse domains, including social networks, biology, and e-commerce. Querying historical cohesive subgraphs, defined as extracting cohesive subgraphs from the graph snapshot induced by a given time interval, is a fundamental task in temporal graph analytics. Yet, current index-based methods are typically designed for a single model. This specialization yields high performance for a specific target but cannot be reused for others, which limits extensibility. In this paper, we propose a unified index-based framework to address this limitation. We focus on a generalized class of Historical CSMs (His-CSMs), which is characterized by two structural properties: non-overlapping (resultant subgraphs are vertex-disjoint) and monotonic (validity in a time interval implies validity in any super interval). This class includes prominent models such as historical connected components (His-CC) and historical k -cores (His-Core). To address the His-CSM query problem, we reduce queries for different CSMs to a single canonical query, the spanning connected component query, and design an index-based solution to answer this query efficiently. Building on this framework, we provide concrete instantiations for both His-CC and His-Core queries. Extensive experiments on real-world temporal graphs show that our method outperforms state-of-the-art baselines, achieving up to 60X speedups for His-CC and up to 100X speedups for His-Core.