TY - GEN
T1 - Querying Historical k-Dense Subgraphs on Temporal Graphs
AU - Zhang, Qi
AU - Zhang, Yalong
AU - Li, Rong Hua
AU - Yin, Xu Cheng
AU - Wang, Guoren
N1 - Publisher Copyright:
© 2026 IEEE.
PY - 2026
Y1 - 2026
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/105048942279
U2 - 10.1109/ICDE65706.2026.00008
DO - 10.1109/ICDE65706.2026.00008
M3 - Conference contribution
AN - SCOPUS:105048942279
T3 - Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026
SP - 1
EP - 13
BT - Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026
A2 - Daudjee, Khuzaima
A2 - Luo, Qiong
A2 - Simitsis, Alkis
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 42nd International Conference on Data Engineering, ICDE 2026
Y2 - 4 May 2026
ER -