Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs
Yanping Wu, Renjie Sun, Xiaoyang Wang, Dong Wen, Ying Zhang, Lu Qin, Xuemin Lin
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper8
- Paths-over-Graph: Knowledge Graph Empowered Large Language Model ReasoningXingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu 等WWW 2025 · 被引用 86 次
- MemoTime: Memory-Augmented Temporal Knowledge Graph Enhanced Large Language Model ReasoningXingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu 等WWW 2026 · 被引用 10 次
- Effective Influence Maximization with PriorityJinghao Wang, Yanping Wu, Xiaoyang Wang, Chen Chen 等WWW 2025 · 被引用 9 次
- Efficient Dynamic Attributed Graph GenerationFan Li, Xiaoyang Wang, Dawei Cheng, Cong Chen 等ICDE 2025 · 被引用 5 次
- HydraRAG: Structured Cross-Source Enhanced Large Language Model ReasoningXingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu 等EMNLP 2025 · 被引用 2 次
它引用的顶会 Paper16
- Efficient Bitruss Decomposition for Large-scale Bipartite GraphsKai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang 等ICDE 2020 · 被引用 107 次
- Maximum Biclique Search at Billion ScaleBingqing Lyu, Lu Qin, Xuemin Lin, Ying Zhang 等VLDB 2020 · 被引用 103 次
- Efficient Maximal Biclique Enumeration for Large Sparse Bipartite GraphsLu Chen, Chengfei Liu, Rui Zhou, Jiajie Xu 等VLDB 2022 · 被引用 62 次
- Efficiently Answering Reachability and Path Queries on Temporal Bipartite GraphsXiaoshuang Chen, Kai Wang, Xuemin Lin, Wenjie Zhang 等VLDB 2021 · 被引用 51 次
- Efficient Bi-triangle Counting for Large Bipartite NetworksYixing Yang, Yixiang Fang, Maria E. Orlowska, Wenjie Zhang 等VLDB 2021 · 被引用 39 次
相关 Paper
- Efficient Maximal Temporal Plex EnumerationYanping Wu, Renjie Sun, Xiaoyang Wang, Ying Zhang 等ICDE 2024 · 被引用 9 次
- Efficient Index for Temporal Core Queries over Bipartite GraphsAnxin Tian, Alexander Zhou, Yue Wang, Xun Jian 等VLDB 2024 · 被引用 8 次
- Querying Historical Cohesive Subgraphs Over Temporal Bipartite GraphsShunyang Li, Kai Wang, Xuemin Lin, Wenjie Zhang 等ICDE 2024 · 被引用 7 次
- Discovering Frequency Bursting Patterns in Temporal GraphsQianzhen Zhang, Deke Guo, Xiang Zhao, Long Yuan 等ICDE 2023 · 被引用 10 次
- Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based ApproachesQiangqiang Dai, Rong-Hua Li, Xiaowei Ye, Meihao Liao 等SIGMOD 2023 · 被引用 19 次
