[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
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
References
[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.