Lune

VLDB2024Top-tier venue

Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs

Yanping Wu, Renjie Sun, Xiaoyang Wang, Dong Wen, Ying Zhang, Lu Qin, Xuemin Lin

2024Year
11Citations
8Top-tier citations

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.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

lune papers fulltext 0e6b9752-ab5f-44b5-8afa-62dd747c90e8

Cited by top-tier papers8

Ask how each one uses it

Builds on16

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines