Graph neural networks (GNNs) have achieved significant success in graph representation learning and have been applied to various domains. However, many real-world graphs contain sensitive personal information, such as user profiles in social networks, raising serious privacy concerns when graph learning is performed using GNNs. To address this issue, locally private graph learning protocols have gained considerable attention. These protocols leverage the privacy advantages of local differential privacy (LDP) and the effectiveness of GNN's message-passing in calibrating noisy data, offering strict privacy guarantees for users' local data while maintaining high utility (e.g., node classification accuracy) for graph learning. Despite these advantages, such protocols may be vulnerable to data poisoning attacks, a threat that has not been considered in previous research. Identifying and addressing these threats is crucial for ensuring the robustness and security of privacy-preserving graph learning frameworks. This work introduces the first data poisoning attack targeting locally private graph learning protocols. The attacker injects fake users into the protocol, manipulates these fake users to establish links with genuine users, and sends carefully crafted data to the server, ultimately compromising the utility of private graph learning. The effectiveness of the attack is demonstrated both theoretically and empirically. In addition, several defense strategies have also been explored, but their limited effectiveness highlights the need for more robust defenses.

Traditional sequential recommendation methods assume that users' sequence data is clean enough to learn accurate sequence representations to reflect user preferences. In practice, users' sequences inevitably contain noise (e.g., accidental interactions), leading to incorrect reflections of user preferences. Consequently, some pioneer studies have explored modeling sequentiality and correlations in sequences to implicitly or explicitly reduce noise's influence. However, relying on only available intra-sequence information (i.e., sequentiality and correlations in a sequence) is insufficient and may result in over-denoising and under-denoising problems (OUPs), especially for short sequences. To improve reliability, we propose to augment sequences by inserting items before denoising. However, due to the data sparsity issue and computational costs, it is challenging to select proper items from the entire item universe to insert into proper positions in a target sequence. Motivated by the above observation, we propose a novel framework-Self-augmented Sequence Denoising for sequential Recommendation (SSDRec) with a three-stage learning paradigm to solve the above challenges. In the first stage, we empower SSDRec by a global relation encoder to learn multi-faceted inter-sequence relations in a data-driven manner. These relations serve as prior knowledge to guide subsequent stages. In the second stage, we devise a self-augmentation module to augment sequences to alleviate OUPs. Finally, we employ a hierarchical denoising module in the third stage to reduce the risk of false augmentations and pinpoint all noise in raw sequences. Extensive experiments on five real-world datasets demonstrate the superiority of SSDRec over state-of-the-art denoising methods and its flexible applications to mainstream sequential recommendation models. The source code is available online at https://github.com/zc-97/SSDRec.

Local differential privacy (LDP) has been established as a strong privacy standard for collecting sensitive information from users. Although it has attracted much research attention in recent years, the majority of existing works focus on applying LDP to frequency distribution estimation for each individual value in a discrete domain. This paper concerns the important range queries involving multiple discrete values. Till now, only a few works target this problem. They all rely on the B-ary tree to construct a uniform and hierarchical decomposition, so as to decrease the error when answering large range queries. However, the uniform splitting manner ignores the properties of decomposed sub-domains and processes them equally without preferences, which leads to significant performance penalty.In this paper, we tackle the problem head on: our proposal, privNUD, is a novel domain hierarchical decomposition mechanism. It dynamically decomposes each domain with a tailored granularity into some sub-domains, which sensitively considers the potential chances to answer one range query. The issue of granularity is carefully analyzed for better performance. It also can smartly prune the sub-domains with small frequencies. Besides, an adaptive user allocation technique is designed to dynamically decide the scale of users that are involved in each sub-domain’s frequency estimation. Extensive experiments using real and synthetic datasets demonstrate that privNUD achieves significantly higher result accuracy compared to the up-to-date solutions.

Given a set of local sequential datasets held by multiple parties, we study the problem of publishing a synthetic dataset that preserves approximate sequentiality information of the integrated dataset while satisfying differential privacy for each local dataset. The existing solutions for publishing differentially private sequential data in the centralized setting mostly adopt tree-based approaches. Such approaches rely on different tree structures that encode sequential data's statistical information. The construction of a tree structure is normally done by recursively splitting nodes whose noisyscores(e.g., entropy or count) are larger than a given threshold. However, extending similar ideas to the multi-party setting is challenging. First, the comparison between noisy scores and a given threshold needs to be done in a distributed manner without letting the parties know the noisy scores, while satisfying differential privacy for each local dataset. Second, in the multi-party setting the large number of node splitting decisions incurs prohibitive computation costs. In addressing the above challenges, we presentDPST, a distributed prediction suffix tree construction solution. In DPST, we first introduce a novel node splitting decision method that calculates the comparison result under encryption with substantially improved efficiency. Then we present a novel batch-based tree construction approach to reduce computation costs. In order to achieve high parallel performance without incurring any extra communication cost, we introduce theconjunctionandslidemethods to ensure that each batch contains a stable number of carefully arrangeddecision tasks. To further reduce communication and computation costs, we propose a prefix-based pre-pruning method to reduce the number of nodes that need to be judged whether to split by an interactive protocol. Extensive experiments on real datasets demonstrate that our DPST solution offers desirable data utility with low computation and communication costs.

Given a set of local sequential datasets held by multiple parties, we study the problem of publishing a synthetic dataset that preserves approximate sequentiality information of the integrated dataset while satisfying differential privacy for each local dataset. The existing solutions for publishing differentially private sequential data in the centralized setting mostly adopt tree-based approaches. Such approaches rely on different tree structures that encode sequential data's statistical information. The construction of a tree structure is normally done by recursively splitting nodes whose noisy scores (e.g., entropy or count) are larger than a given threshold. However, extending similar ideas to the multi-party setting is challenging. First, the comparison between noisy scores and a given threshold needs to be done in a distributed manner without letting the parties know the noisy scores, while satisfying differential privacy for each local dataset. Second, in the multi-party setting the large number of node splitting decisions incurs prohibitive computation costs. In addressing the above challenges, we present DPST, a distributed prediction suffix tree construction solution. In DPST, we first introduce a novel node splitting decision method that calculates the comparison result under encryption with substantially improved efficiency. Then we present a novel batch-based tree construction approach to reduce the computation costs. In order to achieve high parallel performance without incurring any extra communication cost, we introduce the conjunction and slide methods to ensure that each batch contains a stable number of carefully arranged decision tasks. Extensive experiments on real datasets demonstrate that our DPST solution offers desirable data utility with low computation and communication costs.

In this paper, we study the problem of publishing high-dimensional data in a distributed multi-party environment under differential privacy. In particular, with the assistance of a semi-trusted curator, the parties (i.e., local data owners) collectively generate a synthetic integrated dataset while satisfying ε-differential privacy. To solve this problem, we present a differentially private sequential update of Bayesian network (DP-SUBN) approach. In DP-SUBN, the parties and the curator collaboratively identify the Bayesian network N that best fits the integrated dataset in a sequential manner, from which a synthetic dataset can then be generated. The fundamental advantage of adopting the sequential update manner is that the parties can treat the intermediate results provided by previous parties as their prior knowledge to direct how to learn N. The core of DP-SUBN is the construction of the search frontier, which can be seen as a priori knowledge to guide the parties to update N. By exploiting the correlations of attribute pairs, we propose exact and heuristic methods to construct the search frontier. In particular, to privately quantify the correlations of attribute pairs without introducing too much noise, we first put forward a non-overlapping covering design (NOCD) method, and then devise a dynamic programming method for determining the optimal parameters used in NOCD. Through privacy analysis, we show that DP-SUBN satisfies ε-differential privacy. Extensive experiments on real datasets demonstrate that DP-SUBN offers desirable data utility with low communication cost.

In this paper, we study the novel problem of publishing high-dimensional data in a distributed multi-party environment under differential privacy. In particular, with the assistance of a semi-trusted curator, the involved parties (i.e., local data owners) collectively generate a synthetic integrated dataset while satisfying ε-differential privacy for any local dataset. To solve this problem, we present a differentially private sequential update of Bayesian network (DP-SUBN) solution. In DP-SUBN, the parties and the curator collaboratively identify the Bayesian network ℕ that best fits the integrated dataset D in a sequential manner, from which a synthetic dataset can then be generated. The fundamental advantage of adopting the sequential update manner is that the parties can treat the statistical results provided by previous parties as their prior knowledge to direct how to learn ℕ. The core of DP-SUBN is the construction of the search frontier, which can be seen as a priori knowledge to guide the parties to update ℕ. To improve the fitness of ℕ and reduce the communication cost, we introduce a correlation-aware search frontier construction (CSFC) approach, where attribute pairs with strong correlations are used to construct the search frontier. In particular, to privately quantify the correlations of attribute pairs without introducing too much noise, we first propose a non-overlapping covering design (NOCD) method, and then introduce a dynamic programming method to find the optimal parameters used in NOCD to ensure that the injected noise is minimum. Through formal privacy analysis, we show that DP-SUBN satisfies ε-differential privacy for any local dataset. Extensive experiments on a real dataset demonstrate that DP-SUBN offers desirable data utility with low communication cost.