Adversarial Signed Graph Learning with Differential Privacy Conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1; August 09–13, 2026; Jeju Island, Republic of Korea Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.
Haobin Ke, Sen Zhang, Qingqing Ye, Xun Ran, Haibo Hu · 2025
Read Adversarial Signed Graph Learning with Differential Privacy Conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1; August 09–13, 2026; Jeju Island, Republic of Korea Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. by Haobin Ke, Sen Zhang, Qingqing Ye, Xun Ran, Haibo Hu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00307.txt.
Introduction
Social networks carry signed ties: friendships pull nodes together, while hostility pushes them apart. Haobin Ke and co-authors study adversarial signed graph learning with differential privacy in 2025. Balance theory lets learning methods infer edge signs from multi-hop pairs of nodes.
Training on sensitive signed graphs raises privacy concerns, because model parameters may leak private link information. The authors combine adversarial training with privacy guarantees so embeddings preserve structure and sign without exposing relationships. The work matters for platforms that analyze trust and conflict while owing their users real confidentiality. Adversarial training hardens the embeddings against attempts to extract the hidden links. Signed graphs are also the natural language of trust networks and political blocs.
Catalog record
| CREATOR | Haobin Ke, Sen Zhang, Qingqing Ye, Xun Ran, Haibo Hu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-00307
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Adversarial Signed Graph Learning with Differential Privacy Conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1; August 09–13, 2026; Jeju Island, Republic of Korea Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1 (KDD ’26), August 09–13, 2026, Jeju Island, Republic of Korea DOI: 10.1145/3770854.3780282 ISBN: 979-8-4007-2258-5/2026/08 CCS: Security and privacy Data anonymization and sanitization Haobin Ke, Sen Zhang, Qingqing Ye, Xun Ran, Haibo Hu Abstract . Signed graphs with positive and negative edges can model complex relationships in social networks. Leveraging on balance theory that deduces edge signs from multi-hop node pairs, signed graph learning can generate node embeddings that preserve both structural and sign information. However, training on sensitive signed graphs raises significant privacy concerns, as model parameters may leak private link information. Existing protection methods with differential privacy (DP) typically rely on edge or gradient perturbation for unsigned graph protection. Yet, they are not well-suited for signed graphs, mainly because edge perturbation tends to cascading errors in edge sign inference under balance theory, while gradient perturbation increases sensitivity due to node interdependence and gradient polarity change caused by sign flips, resulting in larger noise injection. In this paper, motivated by the robustness of adversarial learning to noisy interactions, we present ASGL, a privacy-preserving adversarial signed graph learning method that preserves high utility while achieving node-level DP. We first decompose signed graphs into positive and negative subgraphs based on edge signs, and then design a gradient-perturbed adversarial module to approximate the true signed connectivity distribution. In particular, the gradient perturbation helps mitigate cascading errors, while the subgraph separation facilitates sensitivity reduction. Further, we devise a constrained breadth-first search tree strategy that fuses with balance theory to identify the edge signs between generated node pairs. This strategy also enables gradient decoupling, thereby effectively lowering gradient sensitivity. Extensive experiments on real-world datasets show that ASGL achieves favorable privacy-utility trade-offs across multiple downstream tasks. Our code and data are available in https://github.com/KHBDL/ASGL-KDD26 . † † cc-license: by 1. Introduction The signed graph is a common and widely adopted graph structure that can represent both positive and negative relationships using signed edges ( 30 ; 7 ; 4 ) . For example, in online social networks shown in Fig. 1 , while user interactions reflect positive relationships (e.g., like, trust, friendship), negative relationships (e.g., dislike, distrust, complaint) also exist. Signed graphs provide more expressive power than unsigned graphs to capture such complex user interactions. Recently, some studies ( 16 ; 26 ; 22 ) have explored signed graph learning methods, aiming to obtain low-dimensional vector representations of nodes that preserve key signed graph properties: neighbor proximity and structural balance. These embeddings are subsequently applied to downstream tasks such as edge sign prediction, node clustering, and node classification. Among existing signed graph learning methods, balance theory ( 3 ) has proven effective in identifying the edge signs between the source node and multi-hop neighbor nodes. It is leveraged in graph neural network (GNN)-based models to guide message passing across signed edges, ensuring that information aggregation is aligned with the node proximity ( 6 ; 17 ; 18 ) . Moreover, to enhance the robustness and generalization capability of deep learning models, the adversarial graph embedding model ( 33 ; 21 ) learns the underlying connectivity distribution of signed graphs by generating high-quality node embeddings that preserve signed node proximity. Despite their ability to effectively capture signed relationships between nodes, graph learning models remain vulnerable to link stealing attacks ( 35 ; 13 ; 41 ) , which aim to infer the existence of links between arbitrary node pairs in the training graph. For instance, in online social graphs, such attacks may reveal whether two users share a friendly or adversarial relationship, compromising user privacy and damaging personal or professional reputations. Figure 1. A signed social graph with blue edges for positive links and red edges for negative links. Differential privacy (DP) ( 9 ) is a rigorous privacy framework that guarantees statistically indistinguishable outputs regardless of any individual data presence. Such guarantee is achieved through sufficient perturbation while maintaining provable privacy bounds and computational feasibility. Existing privacy-preserving graph learning methods with DP can be categorized into two types based on the perturbation mechanism: one applies edge perturbation ( 23 ) to protect the link information by modifying the graph structure, and the other adopts gradient perturbation ( 37 ; 36 ) to obscure the relationships between nodes during model training. However, these methods are not well-suited for signed graph learning due to the following two challenges: • Cascading error : As illustrated in Fig. 2 , balance theory facilitates the inference of the edge sign between two unconnected nodes by computing the product of edge signs along a path. However, existing methods that use edge perturbation to protect link information may alter the sign of any edge along the path, thereby leading to incorrect inference of edge signs under balance theory. Such a local error can further propagate along the path, resulting in cascading errors in edge sign inference. • High sensitivity : While gradient perturbation methods without directly perturbing edges may mitigate cascading errors, they are still ill-suited for signed graph learning because the node interdependence in signed graphs leads to high gradient sensitivity. 1 1 1 The presence or absence of a node affects gradient updates of itself and its neighbors. Furthermore, edge change may induce sign flips that reverse gradient polarity within the loss function (see Eq. ( 10 ) for details), resulting in higher sensitivity compared to unsigned graphs. This increased sensitivity requires larger noise for privacy protection, thereby reducing the data utility. To address these challenges, we turn to an adversarial learning-based approach for private signed graph learning. The core motivation is that this adversarial method generates node embeddings by approximating the true connectivity distribution, making it naturally robust to noisy interactions during optimization. As a result, we propose ASGL, a differentially private adversarial signed graph learning method that achieves high utility while maintaining node-level differential privacy. Within ASGL, the signed graph is first decomposed into positive and negative subgraphs based on edge signs. These subgraphs are then processed through an adversarial learning module within shared model parameters, enabling both positive and negative node pairs to be mapped into a unified embedding space while effectively preserving signed proximity. Based on this, we develop the adversarial learning module with differentially private stochastic gradient descent (DPSGD), which generates private node embeddings that closely approximate the true signed connectivity distribution. In particular, the gradient perturbation helps mitigate cascading errors, while the subgraph separation avoids gradient polarity reversals induced by edge sign flips within the loss function, thereby reducing the sensitivity to changes in edge signs. Considering that node interdependence further increases gradient sensitivity, we design a constrained breadth-first search (BFS) tree strategy within adversarial learning. This strategy integrates balance theory to identify the edge signs between generated node pairs, while also constraining the receptive fields of nodes to enable gradient decoupling, thereby effectively lowering gradient sensitivity and reducing noise injection. Our main contributions are listed as follows: • We present a privacy-preserving adversarial learning method for signed graphs, called ASGL.