Large-scale social networks can be modeled as decentralized graphs, where each node holds a part of the overall network. Local differential privacy (LDP) has been widely adopted in decentralized graph analysis to ensure privacy for individual nodes. However, existing LDP-based methods often fail to accommodate personalized privacy requirements due to their uniform encoding and equal perturbation mechanisms. To address this issue, we propose PEGS, a novel privacy-preserving decentralized graph synthesis approach that significantly improves utility while respecting user-specific privacy preferences. Specifically, we introduce interactive local differential privacy (iLDP), a new edge-level definition of LDP that relaxes the constraints of node-independent perturbation, thereby enabling the fulfillment of individual privacy needs. Furthermore, we develop a decentralized graph perturbation framework offering three levels of privacy settings. To optimize the balance between information preservation and privacy, we design encoding and perturbation mechanisms leveraging information entropy tailored to different privacy levels. Extensive experimental evaluations and rigorous theoretical analysis demonstrate that our method produces high-quality synthetic graphs while adhering to iLDP guarantees.

Many real-world networks can be modeled as decentralized heterogeneous graphs with different types of nodes, each holds a piece of whole network and has its own privacy preference. Local differential privacy (LDP) has been widely used in decentralized graph synthesis to provide privacy guarantees. This paper shows that existing LDP-based graph synthesis approaches are insufficient for preserving topological properties and satisfying the different privacy requirements of heterogeneous nodes when generating synthetic decentralized graphs. To address these problems due to the clueless perturbation and ignorance of the topological properties of existing approaches, we introduce HeG-LDP, a novel privacy-preserving decentralized heterogeneous graph synthesis approach that achieves a considerable utility boost compared to other methods while satisfying the privacy requirements of different types of nodes. Concretely, we propose a heterogeneous graph information extraction approach that exploits the inherent topological nature of graphs to construct background knowledge from the partial nodes in a diffusion manner, which is then used to guide individuals in topological information extraction and perturbation. In addition, to further improve the quality of the generated graph, we propose a dK-series-based graph generation approach, which can optimize the connection probability of node pairs via a delicate combination of degree values and dK-series information, resulting in better maintenance of the topological utility. Comprehensive experiments and theoretical analysis show that our proposed HeG-LDP can yield high-quality synthetic heterogeneous graphs while satisfying edge-LDP. To promote research in this field, we make our source code and data publicly available athttps://github.com/HeG-LDP/Paper-codes.

Trajectory publication under local differential privacy (LDP) has recently become a research focus. Existing solutions rely on geospatial discretization, elevating trajectory description granularity to alleviate noise injection. However, discretization itself also leads to trajectory information loss. Determining discretization granularity to balance differential noise and trajectory accuracy is challenging. Besides, these solutions commonly protect trajectory privacy via whole-region perturbation yet ignore the actual reachable range of trajectories, resulting in impractical published trajectories. To address these issues, we propose LDPTP, a novel LDP-based trajectory publication method that achieves high-quality publication by perceiving regional popularity in a privacy-preserving way. Specifically, we design a privacy-accuracy balancing mechanism for discretization granularity selection, which can effectively measure the impact of different granularities on noise error and information loss through the Bernoulli model and information entropy, enabling optimized discrete trajectories acquisition. Furthermore, a regional popularity-based perturbation method is presented, which utilizes trajectory distribution features to capture popular regions and then combines region similarity to generate private mobility patterns that better preserve trajectory utility. Finally, we devise a transition probability correction method to enhance the accuracy of Markov model learned from these private patterns, realizing high-utility trajectory synthesis for publication. Extensive experiments are conducted on real-world and synthetic datasets under three levels of utility metrics. The results demonstrate that our proposed LDPTP significantly outperforms the baseline methods.

Local differential privacy federated learning has attracted wide attention because it can solve the problem of data islands without damaging data privacy, but it faces data heterogeneity problems on the client side. Existing solutions commonly cluster clients with similar data distributions into the same training groups by leveraging clients’ model parameters, thus mitigating the impact of data heterogeneity on federated learning performance. However, model parameters, as an indirect representation for client data, often fail to accurately reflect the true data distribution, resulting in inaccurate client groupings. Furthermore, these solutions perturb high-dimensional parameter vectors dimension-by-dimension to protect client data privacy, which introduces substantial LDP noise that significantly further compromises the client grouping accuracy. To tackle these challenges, we propose PCFed-LDP, a privacy-preserving clustered federated learning framework that improves the federated learning performance while protecting client data and satisfying LDP in heterogeneous environments. Specifically, we introduce a client clustering method based on geometric properties of client data subspaces, which conducts label grouping-based principal angle analysis on client data subspaces to accurately capture the similarities in client data distributions, thereby enabling precise client grouping. To reduce the amount of introduced LDP noise, we design an adaptive noise addition method that utilizes the Haar wavelet technique to decouple the relationship between the noise amount and vector dimensionality, and employs noise error minimization strategy-based vector segmentation to inject LDP noise with finer granularity. Theoretical analysis and experiments on real datasets demonstrate that our solution not only satisfies the constraints of local differential privacy but also outperforms state-of-the-art methods.

Many real-world networks can be represented as weighted graphs, where weights represent the closeness or importance of relationships between node pairs. Sharing these graphs is beneficial for many applications while potentially leading to privacy breaches. Variants of deep learning approaches have been developed for synthetic graph publishing, but privacy-preserving graph (especially weighted graph) publishing has not been fully addressed. To bridge this gap, we propose WDP-GAN, a generative adversarial network (GAN) based privacy-preserving weighted graph generation approach, which can generate unlimited synthetic graphs of a given weighted graph while ensuring individual privacy. To do this, we devise a new node sequence sampling method to generate the training set while preserving both the edge weight and topological structure of the original graph. Moreover, we apply the bi-directional long-short term memory (Bi-LSTM) network to capture the interdependence of node pairs. WDP-GAN then approximates the edge weight information using the frequencies of edges produced by the generator. Furthermore, we propose an adaptive gradient perturbation algorithm to improve the speed and stability of the training process while ensuring individual privacy. Theoretical analysis and experiments on real-world network datasets show that WDP-GAN can generate graphs that effectively preserve structural utility while satisfying differential privacy.

The goal of privacy-preserving social graph publishing is to protect individual privacy while preserving data utility. Community structure, which is an important global pattern of nodes, is a crucial data utility as it serves as fundamental operations for many graph analysis tasks. Yet, most existing methods with differential privacy (DP) commonly fall in edge-DP to sacrifice security in exchange for utility. Moreover, they reconstruct graphs from the local feature-extraction of nodes, resulting in poor community preservation. Motivated by this, we propose PrivCom, a strict node-DP graph publishing algorithm to maximize the utility on the community structure while maintaining a higher level of privacy. Specifically, to reduce the huge sensitivity, we devise a Katz index-based private graph feature extraction method, which can capture global graph structure features while greatly reducing the global sensitivity via a sensitivity regulation strategy. Yet, with a fixed sensitivity, the feature captured by Katz index, which is presented in matrix form, requires privacy budget splits. As a result, plenty of noise is injected, thereby mitigating global structural utility. To this end, we design a private Oja algorithm approximating eigen-decomposition, which yields the noisy Katz matrix via privately estimating eigenvectors and eigenvalues from extracted low-dimensional vectors. Experimental results confirm our theoretical findings and the efficacy of PrivCom.

Performance and scalability are two issues that are becoming increasingly pressing as RDF data model is applied to real-world applications. Because neither vertical nor flat structures of RDF storage can handle frequent schema updates and meanwhile avoid possible long-chain joins, there is no clear winner between these two typical structures. In this paper, we propose an alternative storage schema called open user schema. The open user schema consists of flat tables automatically extracted from RDF query streams. A query is divided into two parts and conquered,respectively, on the flat tables in the open user schema and on the vertical table stored in a backend storage. At the core of this divide and conquer architecture with open user schema, an efficient isomorphism decision algorithm is given to guide a query to related flat tables in the open user schema. Our proposal in essence departs from existing methods in that it can accommodate schema updates without possible long-chain joins. We implement our approach and provide empirical evaluations to demonstrate both efficiency and effectiveness of our approach in evaluating complex RDF queries.