Author Identifier (ORCID)
Abstract
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 a C2P-M framework 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-M selectively 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 ε-Local Differential Privacy (LDP). We formally prove that C2P-M satisfies ε-LDP. Extensive experiments on eight real-world multiplex graph datasets demonstrate that C2P-M significantly outperforms baseline privacy-preserving methods, achieving a better privacy-utility trade-off.
Document Type
Journal Article
Date of Publication
1-1-2026
Publication Title
IEEE Transactions on Knowledge and Data Engineering
Publisher
IEEE
School
School of Engineering
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Comments
Li, C., Ni, W., Ding, M., Qu, Y., Chen, J., Zhang, W., & Rakotoarivelo, T. (2026). C2P-M: Critical connection protection in multiplex graphs. IEEE Transactions on Knowledge and Data Engineering, 38(3), 1512–1526. https://doi.org/10.1109/TKDE.2026.3655741