时态二部图上的k跳可达性查询

叶竹文, 谭玉婷, 周军锋, 杜明, 陈子阳

清华大学学报(自然科学版) ›› 2026, Vol. 66 ›› Issue (11) : 2340-2361.

PDF(2185 KB)
PDF(2185 KB)
清华大学学报(自然科学版) ›› 2026, Vol. 66 ›› Issue (11) : 2340-2361. DOI: 10.16511/j.cnki.qhdxxb.2026.28.029
计算机科学与技术

时态二部图上的k跳可达性查询

  • 叶竹文1, 谭玉婷2, 周军锋1, 杜明1, 陈子阳3
作者信息 +

k-hop reachability queries on temporal bipartite graphs

  • YE Zhuwen1, TAN Yuting2, ZHOU Junfeng1, DU Ming1, CHEN Ziyang3
Author information +
文章历史 +

摘要

二部图作为刻画2类实体间关系的重要建模工具,广泛应用于社交网络分析、疾病传播建模及金融交易追踪等领域。随着现实世界中交互行为的时间特性愈发突出,时态二部图因能刻画实体间随时间变化的关联而受到广泛关注。现有关于时态二部图k跳可达查询的研究虽已取得成果,但仍存在假阴性问题,即部分真实存在的可达路径被错误判定为不可达,从而影响传播路径识别的准确性。此外,遍历式方法在大规模图数据下计算开销高、查询延迟大,难以满足实时性要求。针对上述问题,该文系统分析了假阴性的成因,并提出一种兼顾准确性和效率的解决方案。该方法首先重新定义可达路径的时间约束准则,避免边界条件处理不当造成的误判;随后设计高效的索引构建和并行优化机制,通过图结构转换和标签化索引实现快速可达性判定。基于真实数据集的实验结果表明,所提出方法在查询准确率和查询效率方面均优于现有算法,能够为大规模时态二部图的实时可达性分析提供有效支撑。

Abstract

[Objective] Bipartite graphs are crucial for modeling complex relationships between two distinct entity types, demonstrating tremendous potential in areas such as social network analysis, epidemic propagation modeling, and financial transaction tracking. With the increasing prominence of temporal features in real-world interactions, temporal bipartite graphs have attracted considerable attention for their ability to characterize dynamic, time-evolving relationships accurately. However, processing k-hop reachability queries on these highly dynamic structures poses substantial challenges. Existing studies on temporal reachability, despite notable progress, consistently suffer from false negatives (FNs). These occur when a truly reachable vertex pair is incorrectly classified as unreachable due to the mishandling of specific temporal or structural constraints, thereby reducing the reliability of subsequent path inference, anomaly detection, and data analysis. Moreover, traditional traversal-based approaches incur excessive computational overhead and latency on large-scale graphs, rendering them unsuitable for real-time applications. [Methods] To address these challenges, this study systematically investigates the root causes of FNs in existing reachability algorithms. We observe that current methods often fail to simultaneously evaluate temporal validity and hop-step limitations under complex boundary conditions, leading to premature termination of path searches. Consequently, we define a refined temporal reachability criterion specifically tailored to graph data structures that must satisfy strict temporal and hop constraints. This criterion accurately captures the chronological dependencies of edges within a constrained k-hop path, ensuring proper verification of logical boundaries without mathematical abstractions. Based on this criterion, we propose an accurate and efficient solution through a novel index framework, termed the k-hop temporal reachability (KTR) index model. KTR index construction involves processing the temporal bipartite graph to build compact, auxiliary data structures that record reachable sets and temporal intervals without relying on exhaustive sequential traversal. To overcome computational bottlenecks in large-scale graphs, we deeply integrate comprehensive parallelization strategies into the algorithmic framework. By strategically distributing index construction and query processing workloads across multiple processing units, the proposed system is optimized to handle massive volumes of dynamic relationships concurrently, transforming the computation paradigm from linear traversal to parallelized index lookup. [Results] Extensive experiments were conducted on several large-scale real-world datasets to comprehensively evaluate the proposed methodology against state-of-the-art baseline algorithms. Results clearly demonstrate that the proposed method significantly surpasses existing approaches in query accuracy and computational efficiency. First, regarding query accuracy, the refined temporal reachability criterion entirely eradicated the FNs, consistently achieving 100% query accuracy, whereas standard algorithms exhibited notable misclassification rates under challenging temporal boundary conditions. Second, concerning computational efficiency, the KTR index model with parallel optimization dramatically reduced query latency, considerably accelerating average query response times compared to traditional traversal-based methods and satisfying stringent real-time processing requirements. Third, the applied parallelization strategy efficiently shortened index construction time, enabling rapid updates and seamless adaptation to continuously evolving temporal bipartite graphs. Finally, spatial complexity analysis indicates that the memory overhead associated with generating and maintaining the KTR index remains within acceptable limits and scales linearly and predictably with dataset size. [Conclusions] This study successfully addresses the dual challenges of query unreliability and computational inefficiency by analyzing the structural and temporal dynamics of bipartite graphs and integrating a strict temporal reachability criterion with advanced parallel optimization techniques. The proposed method guarantees the absolute elimination of FNs while dramatically enhancing overall system scalability. This research provides a highly robust, accurate, and practically viable computational foundation for real-time relationship tracking and path inference in complex temporal networks.

关键词

时态二部图 / 可达性查询 / 假阴性 / 索引构建 / 并行优化

Key words

temporal bipartite graph / reachability query / false negative / index construction / parallel optimization

引用本文

导出引用
叶竹文, 谭玉婷, 周军锋, 杜明, 陈子阳. 时态二部图上的k跳可达性查询[J]. 清华大学学报(自然科学版). 2026, 66(11): 2340-2361 https://doi.org/10.16511/j.cnki.qhdxxb.2026.28.029
YE Zhuwen, TAN Yuting, ZHOU Junfeng, DU Ming, CHEN Ziyang. k-hop reachability queries on temporal bipartite graphs[J]. Journal of Tsinghua University(Science and Technology). 2026, 66(11): 2340-2361 https://doi.org/10.16511/j.cnki.qhdxxb.2026.28.029
中图分类号: TP311.13   

参考文献

[1] PAVLOPOULOS G A, KONTOU P I, PAVLOPOULOU A, et al. Bipartite graphs in systems biology and medicine: a survey of methods and applications[J]. GigaScience, 2018, 7(4): giy014.
[2] BEGUERISSE-DÍAZ M, BOSQUE G, OYARZÚN D, et al. Flux-dependent graphs for metabolic networks[J]. NPJ Systems Biology and Applications, 2018, 4(1): 32.
[3] WANG K, LIN X M, QIN L, et al. Vertex priority based butterfly counting for large-scale bipartite networks[J]. Proceedings of the VLDB Endowment, 2019, 12(10): 1139-1152
[4] FANG Y X, CHENG R, LI X D, et al. Effective community search over large spatial graphs[J]. Proceedings of the VLDB Endowment, 2017, 10(6): 709-720.
[5] CHEN X S, WANG K, LIN X M, et al. Efficiently answering reachability and path queries on temporal bipartite graphs[J]. Proceedings of the VLDB Endowment, 2021, 14(10): 1845- 1858.
[6] WANG K, CAI M H, CHEN X S, et al. Efficient algorithms for reachability and path queries on temporal bipartite graphs[J]. The VLDB Journal, 2024, 33(5): 1399-1426.
[7] ZHOU J F, WANG Z Y, TAN Y T, et al. Efficient processing of k-hop reachability queries on temporal bipartite graphs[J]. Information Processing & Management, 2025, 62(5): 104178.
[8] MEUNIER L, ZHAO Y. Reachability queries on dynamic temporal bipartite graphs [C]//Proceedings of the 31st ACM International Conference on Advances in Geographic Information Systems. Hamburg, Germany: ACM, 2023: 97.
[9] BHASKAR M, KANAKAGIRI R. Performance-driven optimization of parallel breadth-first search[J]. arXiv: 2503.00430, 2025.
[10] CERF S, DAYAN B, DE AMBROGGIO U, et al. Balanced bidirectional breadth-first search on scale-free networks[J]. arXiv: 2410. 22186, 2024.
[11] ZENG A, GUALDI S, MEDO M, et al. Trend prediction in temporal bipartite networks: the case of MovieLens, Netflix, and Digg[J]. Advances in Complex Systems, 2013, 16(4-5): 1350024.
[12] LATAPY M, MAGNIEN C, VIARD T. Weighted, bipartite, or directed stream graphs for the modeling of temporal networks [M]//HOLME P, SARAMAKI J. Temporal Network Theory. Cham: Springer, 2023: 49-64.
[13] DE BERG M. A note on reachability and distance oracles for transmission graphs [J]. Computing in Geometry and Topology, 2023, 2(1): 4.
[14] AMARA A, FRAINAY C, JOURDAN F, et al. Networks and graphs discovery in metabolomics data analysis and interpretation [J]. Frontiers in Molecular Biosciences, 2022, 9: 841373.
[15] TRI βL S, LESER U. Fast and practical indexing and querying of very large graphs [C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. Beijing, China: ACM, 2007: 845-856.
[16] BARRETT C L, BISSET K R, EUBANK S G, et al. Episimdemics: An efficient algorithm for simulating the spread of infectious disease over large realistic social networks[C]//Proceedings of the 2008 ACM/IEEE Conference on Supercomputing. Austin, USA: IEEE, 2008: 1-12.
[17] ZHOU B, PEI S, MUCHNIK L, et al. Realistic modelling of information spread using peer-to-peer diffusion patterns [J]. Nature Human Behaviour, 2020, 4(11): 1198-1207.
[18] CHENG J, HUANG S L, WU H H, et al. TF-label: a topological-folding labeling scheme for reachability querying in a large graph[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 2013: 193-204.
[19] JIN R M, WANG G. Simple, fast, and scalable reachability oracle [J]. Proceedings of the VLDB Endowment, 2013, 6(14): 1978- 1989.
[20] DA SILVA R F, URRUTIA S, HVATTUM L M. Extended high dimensional indexing approach for reachability queries on very large graphs[J]. Expert Systems with Applications, 2021, 181: 114962.
[21] QIAO M, CHENG H, QIN L, et al. Computing weight constraint reachability in large networks[J]. The VLDB Journal, 2013, 22(3): 275-294.
[22] WU H H, HUANG Y Z, CHENG J, et al. Reachability and time-based path queries in temporal graphs[C]//2016 IEEE 32nd International Conference on Data Engineering. Helsinki, Finland: IEEE, 2016: 145-156.
[23] VALSTAR L D J, FLETCHER G H L, YOSHIDA Y. Landmark indexing for evaluation of label-constrained reachability queries [C]//Proceedings of the 2017 ACM International Conference on Management of Data. Chicago USA: ACM, 2017: 345-358.
[24] PENG Y, ZHANG Y, LIN X M, et al. Answering billion-scale label-constrained reachability queries within microsecond[J]. Proceedings of the VLDB Endowment, 2020, 13(6): 812-825.
[25] PENG Y, LIN X M, ZHANG Y, et al. Answering reachability and K-reach queries on large graphs with label constraints[J]. The VLDB Journal, 2022, 31(1): 101-127.
[26] QIAN H R, ZHENG W G, ZHANG Z J, et al. Answering min-max resource-constrained shortest path queries over large graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2025, 37(1): 60-74.
[27] PENG Y, MA Z, ZHANG W J, et al. Efficiently answering quality constrained shortest distance queries in large graphs [C]//2023 IEEE 39th International Conference on Data Engineering. Anaheim, USA: IEEE, 2023: 856-868.
[28] WEI F. TEDI: Efficient shortest path query answering on graphs [C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. Indianapolis, USA: ACM, 2010: 99-110.
[29] CAI Y Z, LIU S Y, ZHENG W G, et al. Generating k-hop- constrained s-t path graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2025, 37(5): 2584-2599.
[30] YUAN L, LI X, CHEN Z, et al. I/O efficient label-constrained reachability queries in large graphs[J]. Proceedings of the VLDB Endowment, 2024, 17(10): 2590-2602.
[31] AN S, CHO K, JANG L, et al. Dynamic parameterized problems on unit disk graphs[J]. arXiv preprint arXiv:2409.13403, 2024.
[32] YANG Y J, LI H X, ZHU X J, et al. HR-index: An effective index method for historical reachability queries over evolving graphs[J]. Proceedings of the ACM on Management of Data, 2023, 1(2): 127.
[33] WEN D, HUANG Y L, ZHANG Y, et al. Efficiently answering span-reachability queries in large temporal graphs[C]//, 2020 IEEE 36th International Conference on Data Engineering (ICDE). Dallas, USA, 20201153-1164. DOI: 10.1109/ ICDE48307.2020.00104.
[34] XU Z Q, YANG Z Y, CHEN X S, et al. Efficient answering of k-reachability on temporal bipartite graphs.[C]//35th Australasian Database Conference on Databases Theory and Applications. Gold Coast, Australia: Springer, 2024: 224-238. DOI:10.1007/ 978-981-96-1242-0_17.

基金

国家自然科学基金面上项目(62372101)

PDF(2185 KB)

Accesses

Citation

Detail

段落导航
相关文章

/

〈 〉