Several recent works utilize deep learning (DL) techniques for subgraph retrieval via matching, yet most only return approximate isomorphism relations between queries and data graphs--failing to retrieve all exact matching locations, a critical demand for structured graph retrieval in information retrieval. Unlike these DL-based approximate methods, we propose a learning-based framework for subgraph retrieval, called the graph neural network (GNN)-based anchor embedding framework (GNN-AE), which can efficiently retrieve all exact matching locations. In contrast to most traditional exact subgraph matching methods, which create auxiliary structures online for each query, our method has two core optimizations: (1) We construct offline, one-time-only efficient embedding indices for small feature subgraphs (namely, anchored subgraphs and anchored paths) in the data graph and obtain candidates for the query on these indexed feature subgraphs, trading space for time to reduce online query latency; (2) We leverage GNNs to perform graph isomorphism tests on indexed feature subgraphs and generate low-conflict embeddings for these feature subgraphs, yielding a high-quality, compact set of candidates that further enhances query efficiency. Beyond these core optimizations, we develop a parallel matching growth algorithm and design a cost-based DFS query strategy to retrieve all matching locations. Extensive experiments on both real and synthetic datasets validate the efficiency and effectiveness of our GNN-AE for exact subgraph retrieval.

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.

Centrality is a family of metrics for characterizing the importance of a vertex in a graph. Although a large number of centrality metrics have been proposed, a majority of them ignores uncertainty in graph data. In this article, we formulate closeness centrality on uncertain graphs and define the batch closeness centrality evaluation problem that computes the closeness centrality of a subset of vertices in an uncertain graph. We develop three algorithms, MS-BCC , MG-BCC, and MGMS-BCC , based on sampling to approximate the closeness centrality of the specified vertices. All these algorithms require to perform breadth-first searches (BFS) starting from the specified vertices on a large number of sampled possible worlds of the uncertain graph. To improve the efficiency of the algorithms, we exploit operation-level parallelism of the BFS traversals and simultaneously execute the shared sequences of operations in the breadth-first searches. Parallelization is realized at different levels in these algorithms. The experimental results show that the proposed algorithms can efficiently and accurately approximate the closeness centrality of the given vertices. MGMS-BCC is faster than both MS-BCC and MG-BCC because it avoids more repeated executions of the shared operation sequences in the BFS traversals.