On Compressing Historical Cliques in Temporal Graphs

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Maximal clique is a fundamental cohesive subgraph model that plays an important role in many practical applications such as social network analysis and bioinformatics. Many real-world graphs change over time, with edges arriving continuously, and each edge has a timestamp representing the arrival time of that edge; such graphs are also known as temporal graphs. All maximal cliques in all snapshots since all possible historical moments are called historical cliques. Querying historical cliques has not been explored in existing research efforts. In this paper, we study the problem of compressing historical cliques in temporal graphs. We design a novel trie index structure called HC-Trie to compress historical cliques by exploiting the duration of historical cliques and the overlapping relationship between different historical cliques. We also propose an algorithm for maintaining the index when the graph changes. Experiments on real-world temporal graphs demonstrate that our solution achieves much faster query efficiency than the online solution and significantly less index space than the straightforward solution.

Author Affiliations

@inproceedings{chen2024compressing,
  title = {On Compressing Historical Cliques in Temporal Graphs},
  author = {Chen, Kaiyu and Wen, Dong and Li, Wentao and Yang, Zhengyi and Zhang, Wenjie},
  editor = {Onizuka, Makoto and Lee, Jae-Gil and Tong, Yongxin and Xiao, Chuan and Ishikawa, Yoshiharu and Amer-Yahia, Sihem and Jagadish, H. V. and Lu, Kejing},
  booktitle = {Database Systems for Advanced Applications},
  year = {2024},
  publisher = {Springer Nature Singapore},
  address = {Singapore},
  pages = {37--53},
  isbn = {978-981-97-5552-3}
}