k-truss is a widely studied cohesive sub graph model that has gained significant attention over the past decades. Truss decomposition, a fundamental task in graph analysis, aims to compute the largest k for which an edge belongs to a k-truss. However, directly performing truss decomposition on sensitive graphs risks exposing the private information of user connections in real-world applications. Edge local differential privacy (edge LDP) is extensively used to protect the privacy of edges in graph analysis. This paper, for the first time, addresses the problem of truss decomposition under edge LDP. A naive approach allows each vertex to perturb its neighbor list locally and generate a noisy graph for truss decomposition. However, it often produces excessive truss number estimations, since the noisy graph is generally much denser and fails to preserve the input graph structure. To obtain more accurate estimates, we propose the Local algorithm that leverages the local information during the truss decomposition process. Furthermore, to avoid adding substantial noise to truss numbers to satisfy edge LDP, we introduce the Global algorithm that optimizes the noise scale of support numbers, enhancing the accuracy of truss decom-position results. We further propose the Global * algorithm that eliminates the need for vertices to download noisy edges by utilizing noisy degrees to adjust support numbers during truss decomposition, achieving high accuracy with significantly lower communication costs. Extensive experiments on 9 real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithms.

Counting the number of triangles in a graph is a fundamental task and has been extensively studied recently. In real-world applications, continuously releasing the triangle count of a graph poses a significant privacy risk for users. To protect sensitive edge information from a central server, we study the problem of estimating the number of triangles under edge local differential privacy (edge LDP). Existing approaches adopt a multi-round computing scheme, allowing the vertices to perform local triangle counting using the noisy graph constructed in the previous round. However, these algorithms not only restrict the noisy graph that can be downloaded to each vertex, but also have coarse upper bounds for the scale of noise added to the estimates. In this paper, we propose a vertex-centric triangle counting algorithm under edge LDP, which improves data utility by leveraging a larger part of the noisy adjacency matrix. Our approach fully exploits the local graph structure to obtain refined estimates of per-vertex triangle counts. We also devise tight bounds for global sensitivities to not only comply with privacy requirements but also control the scale of added noise. Furthermore, we perform a rigorous analysis of the L2 loss of our unbiased estimators and design optimizations for allocating the privacy budget to minimize L2 loss based on the input graph. Extensive experiments on 12 datasets validate the effectiveness and efficiency of our proposed algorithms.

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.

Butterfly counting on bipartite graphs has gained increasing attention in past decades. Inevitably, butterfly counts can reveal the presence of certain edges, posing a privacy risk in real applications. Edge local differential privacy (edge LDP), which requires each vertex to perturb its neighbors locally, has been applied to protect edge privacy in graphs. This paper, for the first time, investigates butterfly counting on bipartite graphs with edge LDP. Although a straightforward approach that allows each vertex to perturb its incident edges locally to construct a noisy graph and perform butterfly counting preserves edge LDP, it often results in severe over-counting and significant bias since the resulting noisy graph is generally much denser than the input graph. To obtain unbiased butterfly counts, we propose a multiple-round interaction algorithm to allow the vertices to download the noisy graph and compute local motif counts. Moreover, to avoid adding substantial noise to satisfy edge LDP, we further propose the Download-free Butterfly. Estimation (DBE) algorithm, which captures motif transformation probabilities and relies on motif counts from the noisy graph to yield unbiased butterfly estimates. DBE significantly enhances accuracy via reduced communication between vertices and the data curator. Extensive experiments on 14 datasets validate the effectiveness and efficiency of our proposed techniques.

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.

Bipartite graphs, formed by two vertex layers, arise as a natural fit for modeling the relationships between two groups of entities. In bipartite graphs, common neighborhood computation between two vertices on the same vertex layer is a basic operator, which is easily solvable in general settings. However, it inevitably involves releasing the neighborhood information of vertices, posing a significant privacy risk for users in real-world applications. To protect edge privacy in bipartite graphs, in this paper, we study the problem of estimating the number of common neighbors of two vertices on the same layer under edge local differential privacy (edge LDP). The problem is challenging in the context of edge LDP since each vertex on the opposite layer of the query vertices can potentially be a common neighbor. To obtain efficient and accurate estimates, we propose a multiple-round framework that significantly reduces the candidate pool of common neighbors and enables the query vertices to construct unbiased estimators locally. Furthermore, we improve data utility by incorporating the estimators built from the neighbors of both query vertices and devise privacy budget allocation optimizations. These improve the estimator's robustness and consistency, particularly against query vertices with imbalanced degrees. Extensive experiments on 15 datasets validate the effectiveness and efficiency of our proposed techniques.

In this paper, we study the k-clique densest subgraph problem, which detects the subgraph that maximizes the ratio between the number of k-cliques and the number of vertices in it. The problem has been extensively studied in the literature and has many applications in a wide range of fields such as biology and finance. Existing solutions rely heavily on repeatedly computing all the k-cliques, which are not scalable to handle large k values on large-scale graphs. In this paper, by adapting the idea of "pivoting", we propose the SCT*-Index to compactly organize the k-cliques. Based on the SCT*-Index, our SCTL algorithm can directly obtain the k-cliques from the index and efficiently achieve near-optimal approximation. To further improve SCTL, we propose SCTL* that includes novel graph reductions and batch-processing optimizations to reduce the search space and decrease the number of visited k-cliques, respectively. As evaluated in our experiments, SCTL* significantly outperform existing approaches by up to two orders of magnitude. In addition, we propose a sampling-based approximate algorithm that can provide reasonable approximations for any k value on billion-scale graphs. Extensive experiments on 12 real-world graphs validate both the efficiency and effectiveness of the proposed techniques.

In this article, we propose the$(\alpha,\beta,\eta)$-core model, which is the first cohesive subgraph model on uncertain bipartite graphs. To capture the uncertainty of relationships/edges,$\eta$-degree is adopted to measure the vertex engagement level, which is the largest integer$k$such that the probability of a vertex having at least$k$neighbors is not less than$\eta$. Given degree constraints$\alpha$and$\beta$, and a probability threshold$\eta$, the$(\alpha,\beta,\eta)$-core requires that each vertex on the upper or lower level have$\eta$-degree no less than$\alpha$or$\beta$, respectively. An$(\alpha,\beta,\eta)$-core can be obtained by iteratively removing the vertices with$\eta$-degrees below the degree constraints. Apart from the online computation algorithm, we propose a probability-aware index to strike a balance between time and space costs. To efficiently build such an index, we design a top-down index construction algorithm to allow computation sharing. Then, we show how to parallelize our query algorithms and index construction algorithms. In addition, we study community search on uncertain bipartite graphs by adopting the$(\alpha,\beta,\eta)$-core model. Extensive experiments are conducted on 13 datasets to validate the efficiency and effectiveness of our proposed techniques.

Bipartite networks, which model relationships between two different types of entities, are prevalent in many real-world applications. On bipartite networks, the cascading node departure undermines the networks' ability to provide sustainable services, which makes reinforcing bipartite networks a vital problem. Although network reinforcement is extensively studied on unipartite networks, it remains largely unexplored on bipartite graphs. On bipartite networks, ($\alpha, \beta$) -core is a stable structure that ensures different minimum engagement levels of the vertices from different layers, and we aim to reinforce bipartite networks by maximizing the ($\alpha, \beta$) -core. Specifically, given a bipartite network$G$, degree constraints$\alpha$and$\beta$, budgets$b_{1}$and$b_{2}$, we aim to find$b_{1}$upper layer vertices and$b_{2}$lower layer vertices as anchors and bring them into the ($\alpha, \beta$) -core s.t. the number of non-anchor vertices entering in the ($\alpha, \beta$) -core is maximized. We prove the problem is NP-hard and propose a heuristic algorithm FILVER to solve the problem. FILVER runs$b_{1}+b_{2}$iterations and choose the best anchor in each iteration. Under a filter-verification framework, it reduces the pool of candidate anchors (in the filter stage) and computes the resulting ($\alpha, \beta$) - core for each anchor vertex more efficiently (in the verification stage). In addition, filter-stage optimizations are proposed to further reduce “dominated” anchors and allow computation-sharing across iterations. To optimize the verification stage, we explore the cumulative effect of placing multiple anchors, which effectively reduces the number of running iterations. Extensive experiments on 18 real-world datasets and a billion-scale synthetic dataset validate the effectiveness and efficiency of our proposed techniques.

Bipartite graphs are extensively used to model relationships between two different types of entities. In many real-world bipartite graphs, relationships are naturally uncertain due to various reasons such as data noise, measurement error and imprecision of data, leading to uncertain bipartite graphs. In this paper, we propose the ($\alpha,\beta,\eta$)-core model, which is the first cohesive subgraph model on uncertain bipartite graphs. To capture the uncertainty of relationships/edges,$\eta$-degree is adopted to measure the vertex engagement level, which is the largest integer$k$such that the probability of a vertex having at least$k$neighbors is not less than$\eta$. Given degree constraints$\alpha$and$\beta$, and a probability threshold$\eta$, the ($\alpha, \beta, \eta$)-core requires that each vertex on the upper or lower level have$\eta$-degree no less than$\alpha$or$\beta$, respectively. An ($\alpha, \beta, \eta$)-core can be derived by iteratively removing a vertex with$\eta$-degree below the degree constraint and updating the$\eta$-degrees of its neighbors. This incurs prohibitively high cost due to the$\eta$-degree computation and updating, and is not scalable to large bipartite graphs. This motivates us to develop index-based approaches. We propose a basic full index that stores ($\alpha, \beta, \eta$)-core for all possible$\alpha, \beta$, and$\eta$combinations, thus supporting optimal retrieval of the vertices in any ($\alpha, \beta, \eta$)-core. Due to its long construction time and high space complexity, we further propose a probability-aware index to achieve a balance between time and space costs. To efficiently build the probability-aware index, we design a bottom-up index construction algorithm and a top-down index construction algorithm. Extensive experiments are conducted on real-world datasets with generated edge probabilities under different distributions, which show that (1) ($\alpha,\beta,\eta$)-core is an effective model; (2) index construction and query processing are significantly sped up by the proposed techniques.