Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs
Yanping Wu, Renjie Sun, Xiaoyang Wang, Dong Wen, Ying Zhang, Lu Qin, Xuemin Lin
Abstract
Cohesive subgraph mining is a fundamental problem in bipartite graph analysis. In reality, relationships between two types of entities often occur at some specific timestamps, which can be modeled as a temporal bipartite graph. However, the temporal information is widely neglected by previous studies. Moreover, directly extending the existing models may fail to find some critical groups in temporal bipartite graphs, which appear in a unilateral (i.e., one-layer) form. To fill the gap, in this paper, we propose a novel model, called maximal λ -frequency group (MFG). Given a temporal bipartite graph 𝒢
(U, V, ℰ ), a vertex set V
S
⊆ V is an MFG if i ) there are no less than λ timestamps, at each of which
V S
can form a (
τ U , τ V
)-biclique with some vertices in U at the corresponding snapshot, and ii ) it is maximal. To solve the problem, a filter-and-verification (FilterV) method is proposed based on the Bron-Kerbosch framework, incorporating novel filtering techniques to reduce the search space and array-based strategy to accelerate the frequency and maximality verification. Nevertheless, the cost of frequency verification in each valid candidate set computation and maximality check could limit the scalability of FilterV to larger graphs. Therefore, we further develop a novel verification-free (VFree) approach by leveraging the advanced dynamic counting structure proposed. Theoretically, we prove that VFree can reduce the cost of each valid candidate set computation in FilterV by a factor of O (| V |). Furthermore, VFree can avoid the explicit maximality verification because of the developed search paradigm. Finally, comprehensive experiments on 15 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques and model.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 0e6b9752-ab5f-44b5-8afa-62dd747c90e8Cited by top-tier papers8
- Paths-over-Graph: Knowledge Graph Empowered Large Language Model ReasoningXingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu et al.WWW 2025 · 86 citations
- MemoTime: Memory-Augmented Temporal Knowledge Graph Enhanced Large Language Model ReasoningXingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu et al.WWW 2026 · 10 citations
- Effective Influence Maximization with PriorityJinghao Wang, Yanping Wu, Xiaoyang Wang, Chen Chen et al.WWW 2025 · 9 citations
- Efficient Dynamic Attributed Graph GenerationFan Li, Xiaoyang Wang, Dawei Cheng, Cong Chen et al.ICDE 2025 · 5 citations
- HydraRAG: Structured Cross-Source Enhanced Large Language Model ReasoningXingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu et al.EMNLP 2025 · 2 citations
Builds on16
- Efficient Bitruss Decomposition for Large-scale Bipartite GraphsKai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang et al.ICDE 2020 · 107 citations
- Maximum Biclique Search at Billion ScaleBingqing Lyu, Lu Qin, Xuemin Lin, Ying Zhang et al.VLDB 2020 · 103 citations
- Efficient Maximal Biclique Enumeration for Large Sparse Bipartite GraphsLu Chen, Chengfei Liu, Rui Zhou, Jiajie Xu et al.VLDB 2022 · 62 citations
- Efficiently Answering Reachability and Path Queries on Temporal Bipartite GraphsXiaoshuang Chen, Kai Wang, Xuemin Lin, Wenjie Zhang et al.VLDB 2021 · 51 citations
- Efficient Bi-triangle Counting for Large Bipartite NetworksYixing Yang, Yixiang Fang, Maria E. Orlowska, Wenjie Zhang et al.VLDB 2021 · 39 citations
Related papers
- Efficient Maximal Temporal Plex EnumerationYanping Wu, Renjie Sun, Xiaoyang Wang, Ying Zhang et al.ICDE 2024 · 9 citations
- Efficient Index for Temporal Core Queries over Bipartite GraphsAnxin Tian, Alexander Zhou, Yue Wang, Xun Jian et al.VLDB 2024 · 8 citations
- Querying Historical Cohesive Subgraphs Over Temporal Bipartite GraphsShunyang Li, Kai Wang, Xuemin Lin, Wenjie Zhang et al.ICDE 2024 · 7 citations
- Discovering Frequency Bursting Patterns in Temporal GraphsQianzhen Zhang, Deke Guo, Xiang Zhao, Long Yuan et al.ICDE 2023 · 10 citations
- Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based ApproachesQiangqiang Dai, Rong-Hua Li, Xiaowei Ye, Meihao Liao et al.SIGMOD 2023 · 19 citations
