Cohesive subgraph computation on bipartite graphs has drawn significant research interest recently. As a popular cohesive subgraph model,$k$-bitruss is defined as the maximal subgraph where each edge is contained in at least$k$butterflies (i.e., a (2, 2)-biclique). The bitruss decomposition problem is widely studied, which aims to compute all$k$-bitrusses for$k \geq 0$. The state-of-the-art CPU-based solutions require extensive costs to construct an index structure for grouping butterflies, leading to scalability challenges on large bipartite graphs. In this paper, we explore bitruss decomposition with GPU by leveraging the parallel computing capabilities of GPU architectures. As the index-based approach requires extensive space and the memory resources of GPUs are limited, we proposeGBiD, which is a peeling-based algorithm on GPUs that utilizes a block-centric computation scheme to enable space-efficient bitruss decomposition without any indexing structure. In addition, cost-aware common neighbor exploration and neighbor list accessing optimizations are proposed to enhanceGBiDby reducing the cost of enumerating butterflies and accessing the graph structure during the peeling process. Extensive experiments conducted on 10 real-world datasets demonstrate that our proposed techniques significantly surpass existing CPU-based solutions in terms of both space and time efficiency.

In many real-world scenarios, relationships between two different entities can be naturally represented as bipartite graphs, such as author-paper, user-item, and people-location. Cohesive subgraph search, which aims to find densely connected subgraphs, is a popular research topic on bipartite graphs. While various cohesive subgraph models are proposed on bipartite graphs, none of them consider the temporal dimension, which expresses dynamic changes occurring in cohesive subgraphs over time. In this paper, we propose the first cohesive subgraph model$(\alpha,\ \beta,\ \mathcal{T})$-core on temporal bipartite graphs. Given degree constraints$\alpha$and$\beta$, as well as a time window$\mathcal{T}=[t_{s},t_{e}],(\alpha,\beta,\ \mathcal{T})$-core guarantees that each vertex in the upper or lower layer has at least$\alpha$or$\beta$neighbors, respectively, within the snapshot over the time window$\mathcal{T}$. An intuitive solution to compute the$(\alpha,\ \beta,\ \mathcal{T})$-core is to iteratively remove the vertices that do not satisfy the degree constraints in the snapshot, which suffers from inefficiency and is impractical on large temporal bipartite graphs. Therefore, we turn to index-based methods to enhance query performance. To support efficient arbitrary$(\alpha,\ \beta,\ \mathcal{T})$-core queries, we propose a vertex-partitioning historical index called VH-Index and a time-partitioning historical index called TH-Index. Note that these two indexes need to store$(\alpha,\ \beta,\ \mathcal{T})$-core for each possible combination of$\alpha, \beta$, and$a\mathcal{T}$and incur large construction costs. Therefore, we further propose a temporal intersection index called TH*-Index to strike a balance between the efficiency of query processing and the space cost of the index. We develop both sequential and parallel algorithms for efficiently constructing the temporal-intersection index. Extensive experiments are conducted on 10 real-world temporal bipartite graphs to validate the effectiveness of the$(\alpha,\ \beta,\ \mathcal{T})$-core model and the efficiency of our proposed algorithms.

Hypergraphs are a generalisation of graphs in which a hyperedge can connect any number of vertices. It can describe n-ary relationships and high-order information among entities compared to conventional graphs. In this paper, we study the fundamental problem of subgraph matching on hypergraphs (i.e., subhypergraph matching). Existing methods directly extend sub-graph matching algorithms to the case of hypergraphs. However, this approach delays hyperedge verification and underutilises the high-order information in hypergraphs, which leads to large search space and high enumeration costs. Furthermore, with the growing size of hypergraphs, it is becoming hard to compute subhypergraph matching sequentially. Thus, we propose an efficient and parallel subhypergraph matching system, HGMatch, to handle subhypergraph matching in massive hypergraphs. We propose a novel match-by-hyperedge framework to utilise high-order information in hypergraphs and use set operations for efficient candidate generation. Moreover, we develop an optimised parallel execution engine in HGMatch based on the dataflow model, which features a task-based scheduler and fine-grained dynamic work stealing to achieve bounded memory execution and better load balancing. Experimental evaluation on 10 real-world datasets shows that HGMatch outperforms the extended version of the state-of-the-art subgraph matching algorithms (CFL, DAF, CECI, and RapidMatch) by orders of magnitude when using a single thread, and achieves almost linear scalability when the number of threads increases.

Bipartite graph is a widely used model to describe relationships between two different types of entities. Exploring graph hierarchy with cohesive subgraphs has been extensively studied on unipartite graphs, while only a few works focus on bipartite graphs. In this paper, we propose the bipartite hierarchy, which is the first model to discover the hierarchical structure of bipartite graphs based on the concept of$(\alpha_{2}\beta){-}$core and graph connectivity. Notably,$(\alpha, \beta)-\text{core}$is a vertex- centric model that conforms to the special structure of bipartite graphs (i.e., formed by two different vertex layers). Accordingly, the bipartite hierarchy has two parts (i.e., the upper and lower hierarchies) to record the hierarchical relationships among upper and lower vertices, respectively. We theoretically prove that the bipartite hierarchy is space-efficient (i.e., its space cost is linear to the graph size) and clearly illustrate its structure via visualization. In addition, efficient algorithms for building the bipartite hierarchy are proposed by utilizing the nested property of$(\alpha, \beta)-\text{core}$. Since bipartite graphs can be dynamically changed in real-world scenarios, we also study the bipartite hierarchy maintenance algorithms against the edge insertion/deletion cases. These algorithms can effectively identify the affected regions to limit computation scope and avoid re-building the bipartite hierarchy from scratch. Extensive experiments on 10 real-world graphs not only demonstrate the effectiveness of the proposed bipartite hierarchy but also validate the efficiency of our hierarchy construction and maintenance algorithms.