Multiplex graphs represent diverse real-world interactions among entities, where multiple relationship types coexist within the same set of entities. These graphs introduce privacy risks, as data collectors can exploit cross-layer dependencies to infer hidden and sensitive connections. In this work, we propose aC2P-Mframework that identifies and protects critical connections while preserving the structural information in multiplex graphs. Unlike conventional methods for single-layer graphs that perturb all edges uniformly,C2P-Mselectively protects critical connections, maintaining the analytical usability of the graph. To achieve this, we introduce the multiplex$p$-cohesion model, which incorporates new score functions that account for both intra-layer and inter-layer dependencies, enabling precise identification of critical connections for each vertex. For privacy protection, our method protects the identified critical connections, leveraging an adaptive Randomized Response (RR) mechanism to ensure$\varepsilon$-Local Differential Privacy (LDP). We formally prove thatC2P-Msatisfies$\varepsilon$-LDP. Extensive experiments on eight real-world multiplex graph datasets demonstrate thatC2P-Msignificantly outperforms baseline privacy-preserving methods, achieving a better privacy-utility trade-off.

Spatio-temporal trajectories carry identifying information and are vulnerable to privacy breaches. Existing studies predominantly focus on the spatial domain. The temporal aspect remains underexplored, leaving privacy risks unaddressed. This paper highlights these risks by introducing a new trajectory matching model, ST-ATT, which leverages attention-enhanced Long Short-Term Memory (LSTM) to effectively capture the spatio-temporal correlations within trajectories. ST-ATT excels in identifying similar trajectories. To defend against linkage attacks on spatio-temporal trajectories, including advanced models like ST-ATT, we propose a novel Differential Privacy (DP) mechanism specifically designed to address the privacy risks. We reveal that the privacy budget and violation probability for each spatial point explicitly depend on earlier timestamps. The privacy budget can be flexibly redistributed between spatial and temporal domains without compromising overall privacy. This mechanism complies with DP, even when spatio-temporal points are reordered due to perturbation. Experiments show that ST-ATT can accurately identify spatio-temporal trajectories perturbed by the existing DP methods adding noise solely to the spatial domain. The proposed spatio-temporal DP mechanism resists ST-ATT, highlighting the need for considering spatio-temporal correlations to ensure robust privacy protection in spatio-temporal trajectories.

Network Dismantling (ND) seeks to identify the smallest subset of nodes whose removal fragments a network into disconnected components. Traditional methods rely on fixed centrality heuristics or supervised models trained on synthetic data, often failing to generalize across diverse topologies. We introduce GRLND, a Graph Reinforcement Learning framework that enables fully unsupervised, structure-aware dismantling through end-to-end optimization. GRLND formulates ND as a single-step Markov Decision Process (MDP), where the action is a binary mask indicating the nodes to be removed-allowing the agent to generate a complete dismantling strategy in a single forward pass while accounting for the joint effect of multiple node removals. The framework combines a Graph Convolutional Network (GCN) for topological encoding with a stochastic policy trained via the REINFORCE algorithm. Additionally, we design a task-specific reward that balances connectivity disruption and removal sparsity, guiding the policy toward compact yet high-impact dismantling solutions. Experiments on both synthetic and real-world networks show that GRLND consistently outperforms classical heuristics and recent learning-based methods, achieving strong generalization without requiring labels or pretraining.

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.

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.

Service composition platforms play a crucial role in creating personalized service processes. Challenges, including the risk of tampering with service data during service invocation and the potential single point of failure in centralized service registration centers, hinder the efficient and responsible creation of service processes. This paper presents a novel framework called Context-Aware Responsible Service Process Creation and Recommendation (SPCR-CA), which incorporates blockchain, Recurrent Neural Networks (RNNs), and a Skip-Gram model holistically to enhance the security, efficiency, and quality of service process creation and recommendation. Specifically, the blockchain establishes a trusted service provision environment, ensuring transparent and secure transactions between services and mitigating the risk of tampering. The RNN trains responsible service processes, contextualizing service components and producing coherent recommendations of linkage components. The Skip-Gram model trains responsible user-service process records, generating semantic vectors that facilitate the recommendation of similar service processes to users. Experiments using the Programmable-Web dataset demonstrate the superiority of the SPCR-CA framework to existing benchmarks in precision and recall. The proposed framework enhances the reliability, efficiency, and quality of service process creation and recommendation, enabling users to create responsible and tailored service processes. The SPCR-CA framework offers promising potential to provide users with secure and user-centric service creation and recommendation capabilities.

Many real-world interconnections among entities can be characterized as graphs. Collecting local graph information with balanced privacy and data utility has garnered notable interest recently. This paper delves into the problem of identifying and protecting critical information of entity connections for individual participants in a graph based on cohesive subgraph searches. This problem has not been addressed in the literature. To address the problem, we propose to extract the critical connections of a queried vertex using a fortress-like cohesive subgraph model known as$p$-cohesion. A user's connections within a fortress are obfuscated when being released, to protect critical information about the user. Novel merit and penalty score functions are designed to measure each participant's critical connections in the minimal$p$-cohesion., facilitating effective identification of the connections. We further propose to preserve the privacy of a vertex enquired by only protecting its critical connections when responding to queries raised by data collectors. We prove that, under the decentralized differential privacy (DDP) mechanism, one's response satisfies$(\varepsilon , \delta )$-DDP when its critical connections are protected while the rest remains unperturbed. The effectiveness of our proposed method is demonstrated through extensive experiments on real-life graph datasets.

Obfuscating a dataset by adding random noises to protect the privacy of sensitive samples in the training dataset is crucial to prevent data leakage to untrusted parties when dataset sharing is essential. We conduct comprehensive experiments to investigate how the dataset obfuscation can affect the resultant model weights —in terms of the model accuracy, ℓ 2 -distance-based model distance, and level of data privacy—and discuss the potential applications with the proposed Privacy, Utility, and Distinguishability (PUD)-triangle diagram to visualize the requirement preferences. Our experiments are based on the popular MNIST and CIFAR-10 datasets under both independent and identically distributed (IID) and non-IID settings. Significant results include a tradeoff between the model accuracy and privacy level and a tradeoff between the model difference and privacy level. The results indicate broad application prospects for training outsourcing and guarding against attacks in federated learning both of which have been increasingly attractive in many areas, particularly learning in edge computing.

User rating of a service is the explicit behavior of users expressing their preference for the service. Most exciting recommendation methods focus on predicting user-service ratings according to users' historical rating behaviors. However, the behavior of users invoking services is implicit feedback. By analyzing the services called by users, mining their potential semantic representations can also help model users' hidden interests. To this end, how to integrate the implicit feedback and explicit rating of users to provide users with better recommendation experience is a problem to be addressed for service recommendation. In this paper, we propose a novel latent semantic integrated explicit rating (LSIER) scheme to recommend services to users. The LSIER scheme is designed by integrating the probabilistic matrix factorization (PMF) model and the probabilistic latent semantic index (PLSI) model. consists of the two stages: (1) the PMF model is used to generate a user feature matrix and a service feature matrix, and the two feature matrices are updated to complete the missing service score records of the users, and (2) the PLSI model is used to train users access records, where an expectation maximization algorithm is applied to derive the model parameters to realize unsupervised soft clustering of services. When the user gives explicit or implicit feedback to the service, the LSIER scheme can identify the current interest probability distribution of the user according to the category to which the called service belongs, and provide the user with a list of service recommendations with scores. The performance of the proposed LSIER scheme is evaluated using the Netflix data set and the Movielens data set. Experiments show that the scheme can achieve better recommendation accuracy and recall rate than existing methods.