Landmark-based 3-hop cover labeling is a category of approaches for shortest distance/path queries on large-scale complex networks. It pre-computes an index offline to accelerate the online distance/path query. Most real-world graphs undergo rapid changes in topology, which makes index maintenance on dynamic graphs necessary. So far, the majority of index maintenance methods can handle only one edge update (either an addition or deletion) each time. To keep up with frequently changing graphs, we research the ful ly b atch m aintenance problem for the 3-hop cover labeling, and proposed the method called FulBM . FulBM is composed of two algorithms: InsBM and DelBM, which are designed to handle batch edge insertions and deletions, respectively. This separation is motivated by the insight that batch maintenance for edge insertions are much more time-efficient and the fact that most edge updates in the real world are incremental. Both InsBM and DelBM are equipped with well-designed pruning strategies to minimize the number of vertex accesses. We have conducted comprehensive experiments on both synthetic and real-world graphs to verify the efficiency of FulBM and its variants for weighted graphs. The results show that our methods achieve 5.5× to 228× speedup compared with the state-of-the-art method.

Haoran Luo, Haihong E, Yuhao Yang, Yikai Guo, Mingzhi Sun, Tianyu Yao, Zichen Tang, Kaiyang Wan, Meina Song, Wei Lin. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2023.

Multi-hop logical reasoning over knowledge graph plays a fundamental role in many artificial intelligence tasks. Recent complex query embedding methods for reasoning focus on static KGs, while temporal knowledge graphs have not been fully explored. Reasoning over TKGs has two challenges: 1. The query should answer entities or timestamps; 2. The operators should consider both set logic on entity set and temporal logic on timestamp set. To bridge this gap, we introduce the multi-hop logical reasoning problem on TKGs and then propose the first temporal complex query embedding named Temporal Feature-Logic Embedding framework (TFLEX) to answer the temporal complex queries. Specifically, we utilize fuzzy logic to compute the logic part of the Temporal Feature-Logic embedding, thus naturally modeling all first-order logic operations on the entity set. In addition, we further extend fuzzy logic on timestamp set to cope with three extra temporal operators (**After**, **Before** and **Between**). Experiments on numerous query patterns demonstrate the effectiveness of our method.