Finding the maximum biclique in a bipartite graph is a fundamental graph analysis problem. Existing methods for maximum biclique search are not very efficient because they cannot effectively reduce the size of a bipartite graph composed of large bicliques that are loosely linked together because the graph reduction strategies adopted by these methods only consider local densities of vertices. This paper proposes a novel approach to maximum biclique search. The unique feature of this approach is building a linear-space data-driven index called BCviz that helps accurately identify subgraphs containing all bicliques with sizes no less than a certain threshold. The core technique of BCviz is determining a total order of vertices that can reveal both the local density and the connectivity of the vertices. Notably, our work is the first one to take connectivity into account in graph reduction. Interestingly, the total order of vertices entails BCviz an illustrative visualization of the distribution of cohesive subgraphs in the input graph. To deeply understand BCviz, we carry out a theoretical study on its properties and reveal how it enables more effective graph reduction. Based on BCviz, we propose an exact maximum biclique search algorithm that searches for results on much smaller subgraphs than any existing method does. In addition, we improve the efficiency of index construction by two techniques. One is approximating an edge's local density with an upper bound that can be derived in linear time. The other is a lightweight vertex ordering method called one-spot ordering which reduces unnecessary cohesion computations. Extensive experiments indicate that the proposed maximum biclique search methods based on BCviz and its variants outperform the state-of-the-art search-based methods by 2--3 orders of magnitude. Compared with the state-of-the-art index for maximum biclique search, the improved BCviz index can reduce the index size by 1--2 orders of magnitude and the index construction time by up to 2 orders of magnitude.

Multi-layer graphs have emerged as a new representation of multi-faceted relationships between entities in the real world. Community detection on multi-layer graphs has been investigated to gain deeper insights into the modular structures of real-world graphs. As an effective and efficient approach to community detection, structural clustering has been investigated on single-layer graphs. However, it has been overlooked in the study of community detection on multi-layer graphs. In this paper, we give a formulation of structural clustering on multilayer graphs for the first time. Two polynomial-time algorithms are proposed to solve the problem. Furthermore, two indexes, namely the core index and the interval index, with respective peferences to time efficiency and space efficiency, are designed to improve the efficiency of the algorithms. The experiments demonstrate the effectiveness of structural clustering in improving the quality of community detection results on multi-layer graphs. The experiments also verify the improvement in running time due to the use of the proposed indexes.

Mining dense subgraphs on multilayer graphs offers the opportunity for more in-depth discoveries than classical dense subgraph mining on single-layer graphs. However, the existing approaches fail to ensure the denseness of a discovered subgraph on layers of users’ interest and simultaneously gain partial supports on the denseness from other layers. In this paper, we introduce a novel dense subgraph model calledFocusCore(FoCore for short) for multilayer graphs, which can pay more attention to the layers focused by users. The FoCore decomposition problem, that is, identifying all nonempty FoCores in a multilayer graph, can be addressed by executing the peeling process with respect to all possible configurations of focus and background layers. Using the nice properties of FoCores, we devise an interleaved peeling algorithm and a vertex-centric algorithm toward efficient FoCore decomposition. We further design a novel cache to minimize the average retrieval time for an arbitrary FoCore without the need for full FoCore decomposition, which significantly improves efficiency in large-scale graph mining tasks. As an application, we propose a FoCore-decomposition-based algorithm to approximate the densest subgraph in a multilayer graph with a provable approximation guarantee. The extensive experiments on real-world datasets verify the effectiveness of the FoCore model and the efficiency of the proposed algorithms.

Community search on multilayer graphs has significant applications in fields such as bioinformatics, social network analysis, and financial fraud detection, offering deeper insights compared to traditional community search on single-layer graphs. However, existing approaches often suffer from several key limitations, including inefficiency and a lack of flexibility in accommodating query requirements. To address these challenges, we investigate the problem of community search over large multilayer graphs. Specifically, we introduce a novel multilayer community model calledPivotTrussCommunity (PiTC) with provably nice structural guarantees. We formalize the PiTC search (PiTCS) problem, which aims to efficiently identify personalized PiTCs for a given query vertex. To solve the PiTCS problem, we propose an efficient algorithm and design an elegant index to accelerate the search process. In addition, we propose a parameter recommendation method to improve the usability of PiTCS. To further optimize performance, we introduce a method to compact the index by making a trade-off between search time and index size. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithms.