In this paper, we study the problem of maximal similar-weight biclique enumeration for large bipartite graphs. Given an edge-weighted bipartite graph$G=(U,\ V,\ E)$and a weight difference threshold$\delta$, we aim to efficiently enumerate all maximal similar-weight bicliques in$G$, where a maximal similar-weight biclique is a maximal complete subgraph$B(L,\ R)$of$G$such that the weight difference of edges in$E(B)$is not larger than$\delta$. This problem has many applications, such as item recommendation, fraud detection, and biclustering of gene expression data, etc. To the best of our knowledge, we are the first to systematically study this problem. It is very challenging to efficiently solve this problem due to its #P-completeness. In this paper, we propose a two-phase branch-and-bound baseline method, namely MSWBE, which explores the search space in a depth-first manner. Although MSWBE offers a useful computation framework to our problem, its performance is not yet satisfactory due to the large candidate set during the enumeration. To alleviate this, we propose an advanced approach, called MSWBE++. In particular, MSWBE++ exploits the search space by utilizing the edge connectivity and weight information simultaneously, and therefore refines the candidate set significantly. Observing that a straightforward implementation of MSWBE++ by following a depth-first search strategy may generate non-maximal bicliques, we develop a breadth-first search strategy to realize MSWBE++, which can discard the non-maximal sets at an early stage. To accelerate the computation, we introduce effective graph reduction techniques. Our extensive experimental results on 10 real-life datasets demonstrate that MSWBE++ significantly outperforms the baseline methods by up to 2 orders of magnitude. We conduct a case study to show that maximal similar-weight bicliques can provide useful searching hints for fraudulent rating detection.

Continuous subgraph matching (CSM) is a critical task for analyzing dynamic graphs and has a wide range of applications, such as merchant fraud detection, cyber-attack hunting, and rumor detection. Although many efficient CSM algorithms have been recently proposed, they are mainly designed to process a single query. However, in some application scenarios, multi-query oriented continuous subgraph matching (MQCSM) may be of more interest. To our knowledge, the two existing solutions to MQCSM are outdated due to unsatisfactory performance. In this paper, we propose MQ-Match, an efficient approach to MQCSM. First, we design a compact yet effective index structure CCG, which maintains the local matching result of vertices in the data graph using a directed graph. The directed edges in CCG can be utilized as an effective pruning rule for the subsequent incremental matching algorithm when expanding a partial match. Then, we develop a computation sharing incremental matching algorithm. In specific, a set of matching trees is constructed based on the depth-first search trees of the query graphs. By utilizing CCG, we conduct subgraph matching for the matching tree to collect the incremental matches for the query graphs, where the common structures of query graphs are matched only once. Extensive experiments show that MQ-Match can achieve 3.1x-7071.4x speedup over the competitors, and consumes much less memory under the majority of the experiment settings.

Continuously monitoring structural patterns in streaming graphs is a critical task in many real-time graph-based applications. In this paper, we study the problem of time-constrained continuous subgraph matching (shorted as TCSM) over streaming graphs. Given a query graph Q with timing order constraint and a data graph stream G , TCSM aims to report all incremental matches of Q in G for each update of G , where a match should obey both structure constraint (i.e., isomorphism) and timing order constraint of Q. Although TCSM has a wide range of applications, such as cyber-attack detection and credit card fraud detection, we note that this problem has not been well addressed. The state-of-the-art bears the limitations of high index space cost and intermediate result maintenance cost. In this paper, we propose TC-Match, an effective approach to TCSM. First, we design a space and time cost-effective index CSS, which is essentially a k -partite graph structure where a node corresponds to an edge in G. By carefully creating links between nodes, we can encapsulate into CSS the partial embedding and timing order information between edges in G. We theoretically show that CSS has polynomial space and construction time complexities. Second, based on the property of CSS, we develop an efficient incremental matching algorithm with an effective node merging optimization. Extensive experiments show that TC-Match can achieve up to 3 orders of magnitude query performance improvement over the baseline methods, and meanwhile the memory consumption is reduced by 48.7%-86.7%.

In this article, we study the problem of maximal biclique enumeration on large uncertain bipartite graphs. Given an uncertain bipartite graph$\mathcal {G}=(U,V,E,p)$, a probability threshold$\tau$, and two size constraints$\alpha$and$\beta$, we aim to efficiently enumerate all maximal$\tau$-bicliques in$\mathcal {G}$, where a maximal$\tau$-biclique$B(L,R)$is a complete subgraph of$\mathcal {G}$with (1) the probability of$B$is no less than$\tau$, (2)$|L| \geq \alpha$and$|R| \geq \beta$, and (3)$B$is a maximal complete subgraph satisfying (1) and (2). This problem has many applications, such as biclustering of gene expression data, fraud detection, similar group identification, etc. Despite the wide range of applications, to the best of our knowledge, we note that there are no efficient and scalable solutions to this problem in the literature. This problem is computationally challenging due to its #P-completeness. In this article, we propose a competitive branch-and-bound method, namely${\sf MBEN}$, which explores the search space in a depth-first manner with a variety of pruning techniques. To improve the performance of${\sf MBEN}$, we propose several novel and efficient search processing optimizations. First, we always select the side with fewer candidates to expand the search space. With this search strategy, we have a chance to prune the fruitless branches early. Second, we devise an advanced pruning technique by considering the size pruning and probability pruning at the same time to boost the pruning capacity. Last, we implement${\sf MBEN}$with pre-allocated arrays and pointer maintaining techniques such that the frequent work sets creating operations can be substituted by array element switching operations. In addition, we introduce useful graph reduction techniques to further accelerate the computation. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by more than two orders of magnitude.