PEG: Local differential privacy for edge-attributed graphs

Abstract

Edge-attributed graphs are a particular class of graphs designed to represent networks whose edge content indicates a relationship between two nodes. The study of edge-attributed graphs finds applications in diverse fields, such as anomaly detection, mobility analysis, and community search. Since edge-attributed graphs usually contain sensitive information, preserving privacy when releasing this data type for graph analytics becomes an important issue. In this context, local differential privacy (LDP) has emerged as a robust definition for data release under solid privacy guarantees. However, existing graph LDP techniques in the literature primarily focus on traditional graph structures without considering the nuanced attributes associated with edges in attributed graphs. This paper introduces PEG, a novel approach designed to release edge-attributed graphs with local differential privacy guarantees. Combining partitioning and clustering techniques enables more effective noise distribution among similar nodes, which preserves the inherent structure and relationships within the released graph. Extensive experiments on real-world datasets show that PEG can effectively release useful and private edge-attributed graphs, enabling subsequent computation of various graph analysis metrics with high utility, including applications in community detection.