Querying Historical $k$-Dense Subgraphs on Temporal Graphs

Historical cohesive subgraph queries in temporal graphs identify dense substructures within snapshots corresponding to given time intervals, gaining attention due to their broad applications. Existing works primarily focus on $k$-core, which fails to consider subgraph density (measured as the ratio of edges to vertices) and may fragment natural community structures. Borradaile et al. introduced density decomposition, hierarchically organizing graphs into nested $k$-dense subgraphs, with each subgraph ensuring a minimum density of $(k-1)$. Building on this, we, for the first time, formalize and comprehensively investigate the historical $k$-dense subgraph query problem. We propose Online, which identifies $k$-dense subgraphs in the detemporal graph over the query interval by employing max-flow computation. We then present Online+ and Online++, two corepruning based algorithms that significantly reduce the number of edges requiring max-flow computation. Furthermore, three index structures are developed to support efficient query processing. Specifically, VPI leverages time interval inclusion relationships to achieve significant space savings compared to the naive index storing all $k$-dense subgraphs for all time intervals, while preserving query performance. TPI refines the structure of VPI to attain optimal query time at the cost of increased space consumption. A compromise index, TUI, reduces space usage while maintaining near-optimal query efficiency by integrating temporal inclusion relationships with the hierarchical nesting of $k$-dense subgraphs. Additionally, we propose three construction algorithms for VPI: a baseline (BasicVPI) and two optimized variants (BatInsVPI, IncInsVPI). These algorithms are later extended to construct TPI and TUI. The IndexUpdate algorithm for index maintenance is also developed. Extensive experiments and case studies demonstrate the efficiency and effectiveness of our solutions.