Differentially Private Relational Learning with Entity-level Privacy Guarantees
Authors: Yinan Huang
Haoteng Yin
Eli Chien
Rongzhe Wei
Pan Li
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Relational Learning
Privacy Amplification
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Learning with relational and network-structured data is increasingly vital in sensitive domains where protecting the privacy of individual entities is paramount. Differential Privacy (DP) offers a principled approach for quantifying privacy risks, with DP-SGD emerging as a standard mechanism for private model training. However, directly applying DP-SGD to relational learning is challenging due to two key factors: (i) entities often participate in multiple relations, resulting in high and difficult-to-control sensitivity; and (ii) relational learning typically involves multi-stage, potentially coupled (interdependent) sampling procedures that make standard privacy amplification analyses inapplicable. This work presents a principled framework for relational learning with formal entity-level DP guarantees. We provide a rigorous sensitivity analysis and introduce an adaptive gradient clipping scheme that modulates clipping thresholds based on entity occurrence frequency. We also extend the privacy amplification results to a tractable subclass of coupled sampling, where the dependence arises only through sample sizes. These contributions lead to a tailored DP-SGD variant for relational data with provable privacy guarantees. Experiments on fine-tuning text encoders over text-attributed network-structured relational data demonstrate the strong utility-privacy trade-offs of our approach.

Differentially Private Relational Learning with Entity-level Privacy Guarantees
Yinan Huang" Georgia Institute of Technology yhuang903ggatech.c edu
Haoteng Yin" Purdue University yinht@acm.com org
Eli Chien Georgia Institute of Technology ichien6@gatech. edu
Rongzhe Wei
Pan
Georgia Institute of Technology rongzhe wei@gatech. edu
Georgia Institute of Technology
panliggatech. edu
Abstract
Learning with relational and sitive domains where protecting the privacy of individual entities is paramount. Differential Privacy (DP) offers a principled approach for quantifying privacy risks, with DP-SGD emerging
data is increasingly vital in sen-
standard mechanism for private model training. How- ever, directly applying DP-SGD to relational learning is challenging due to two key factors: (i) entities often participate in multiple relations, resulting in high and diffecult-o-connrol sensitivity; and (ii) relational learning typically involves multi- stage, potentially coupled (interdependent) sampling procedures that make standard privacy amplification analyses inapplicable. This work presents a principled frame- work for relational learning with formal entity-level DP guarantees. We provide rigorous sensitivity analysis and introduce an adaptive gradient clipping scheme that modulates clipping thresholds based on entity occurrence frequency. We also extend the privacy amplification results to a tractable subclass of coupled sampling, where the dependence arises only through sample sizes. These contributions lead to a tailored DP-SGD variant for relational data with provable privacy guarantees. Experiments on fine-tuning text encoders over rext-attributed network -struccrt relational data demonstrate the strong utility-privacy trade-offs of our approach. Our code available at https//ggiibbbcco///rrpp-OO/o/oo
1
Introduction
Complex real-world relationships and interactions among individuals are commonly modeled as graphs, where nodes represent these individuals (or broadly, entities) and edges depict their connections. These graph structures are invaluable for analyzing intricate systems and networks [ 2
3 6 Machine learning methods that leverage these structures have demonstrated significant potential in tasks reliant on such relational information, such as recommendation systems, financial network analysis, and some healthcare applications 7 8
12 Particularly, relational learning integrates relational information into the models, enabling them to capture and infer complex dependencies beyond isolated data points 14 [5] I6) One promising application is fine-tuning foundation models- originally trained on text or images using relational datasets to improve their
predictive performance and adaptability to relational contexts [17 19 20
Privacy concerns emerge when relational data to be incorporated into models contains sensitive information, particularly in healthcare and finance. For example, in patient-medical record network
Equal contributions, listed in alphabetical order.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Positive Sampling
Negative Sampling
Edge List
Node Set V sample
Mini-batch B
e
(1.3)
(1,3)
(1.2)
(1,3)
(1,4)
(1,4)
10
(15)
(1,5)
T2
3
(2.3)
(2.3)
(2,3).(211)
(2
fe g. Paisson
Sampling:
(2,4)
pairigg
(2,1)
(2,4).(2,1)
High sensitivity to
Edge List
Node Set V\EL)
e
Mini-batch 3 e'
CxR
sample
C
7
6
D
(1,33-6122)
(2,3)
Cxf
D
(1,3XLL5))
(2.4)
Je.g. Puisson
(2.3)
(2.7)
(2,3).
7i
samplng)
(2.4)
paining
(2.6)
(2.4).(2.6)
Figure 1: The mini-bater sampling process in relational learning is two-stage sampling that first samples edges from full edge list (positive sampling) and then construct negative edges based on the sampled positive edges (negative sampling). A node can occur in multiple positive and negative edges, leading to high sensitivity. Note than the entire batch changes due to the removal of node 1.
data, patient diagnoses (entity attributes) and medical treatments (relations) represent confidential details. Machine learning models are susceptible to privacy vulnerabilities, potentially leading to unintended exposure of sensitive training data [2 22
Differential Privacy (DP) provides a principled framework quantify and mitigate privacy risks for individual data [23 A prominent approach to train deep learning models under the DP framework is DP-SGD [24
30]. DP-SGD initially developed for unstructured data with independent samples, where modifying a single data point impacts only one gradient term. Privacy preservation is thus achieved by controlling gradient sensitivity via per-sample gradient clipping and adding calibrated Gaussian noise to mask individual contributions and prevent privacy leakage.
25 26
27
28
29
Moreover, SPD benefits from privacy analysis technique known privacy amplification by subsampling 266 31 32 33], Specifically, applying a differentially private algorithm to a randomly subsampled dataset rather than the entire dataset strengthens privacy guarantees. This mechanism aligns with mini-batch sampling, further reinforcing the privacy protection capability of DP-SGD.
However, deploying DP-SGD in relational learning to protect entity-level privacy presents unique challenges due to the interconnected nature of entities and the relationshipp-oriente training paradigm (Figure D. These challenges include: a) high sensitivity: entities often participate in multiple relations, thereby appearing in multiple loss terms, significantly increasing sensitivity to entity removal and the risk of sensitive information leakage; and b) coupled sampling: mini-batches in relational learning typically involve multiple interdependent sampling steps, such as sampling positive relations first and subsequently generating negative relations conditioned on these positives [34] 35). This coupled sampling approach diverges from the standard single-step independent sampling assumed by traditional DP- analyses, complicating the direct application of established privacy guarantees.
This work addresses entity-level private relational learning with the following contributions:
We provide a gradient sensitivity analysis for the general contrastive loss used in relational learning, considering scenarios where nodes participate multiple loss terms via multiple positive or negative relations. To mitigate this high sensitivity, we propose an adaptive gradient clipping method that adjusts gradient clipping thresholds based on node occurrences within mini-batches.
We formalize privacy amplification under coupled sampling. While general coupled sampling poses significant analytical challenges, we identify a tractable subclass where coupling arises solely from sample sizes across multiple stages. We derive corresponding amplification bounds for this setting and show that mini-batch construction in relational learning can be aligned with this structure through carefully designed negative sampling methods.
Integrating the above ideas, we propose DP-SGD variant tailored for relational learning with entity-level privacy guarantees. This variant incorporates precise sensitivity control and rigorous privacy bounds. We demonstrate its effectiveness by fine-tuning pre-trained text encoders on datasets, highlighting promising utility-privace trade-offs.
text-attributed

---

2 Related Works
Differentially Private Network Analysis and Learning. Extensive research has focused on de-
veloping privacy-preserving algorithms for network analysis and learning under differential privacy (DP) guarantees [36
(38] studied differentially private community detection for stochastic block 40] considered the privatization of the graph Laplacian spectrum. [41] proposed
37].
models. (39
locally differentially private algorithm for graph neural networks (GNNs). For node-level learning
tasks, 42
43
44
45
46 developed DP methods for training GNNs. + employed teacher-student
framework to support differentially private GNN model release. Note that existing DP GNN methods not applicable due to the distinet challenges of relational learning. These methods primarily address node label prediction tasks, with their privacy mechanisms focused on preventing leakage of node features during neighborhood aggregation, where the interaction data used the input fea- tures to the model. In contrast, the central privacy risk in relational learning stems from the relations themselves being part of the loss function computation, i.e., the loss format, where mini-batches constructed through complex, coupled sampling of relations, and a single entity can participate in numerous such relations.
Privacy Amplification by Subsampling. Privacy amplification refers to an enhanced privacy guarantee that comes from subsampling the raw dataset [48,
49 50 Most existing analyses focus
on neighboring datasets that differ by a single data point 31 51
33 52]. Recently, it has been extended to group privacy, allowing neighboring datasets to differ by multiple data points 53 54 55
These works commonly assume the dataset is an unstructured collection of independent data points, and the sampling mechanism simply outputs a subset of it. Our work instead extends the sampling mechanisms to coupled sampling, an interdependent sampling process from composite dataset.
3 Preliminary
Entity/Node-level Differential Privacy. We use graph notations to denote the relationships between entities. Let 9 = EV,E, X) be a undirected graph defined on node (entity) set V and edge (relation) set & Node attributes X assign each node e E V an attribute 2y. The notion of differential privacy (DP) or Renyi DP (RDP) is defined based on neighboring unstructured dataset differed by one data point 23 (6).
To extend it to graphs, neighboring graphs are defined correspondingly.
Definition 3.1. Two graphs G, G' are called (node-level) neighboring. denoted by g g', if they are differed in a single node and all its associated edges (by removing or inserting a node).
Definition 3.2. An algorithm M is called node-level (e, 8)- for all neighboring graphs 9 ~ G', and any outpul subset S C RRnge( M), it satisfies IP (G) E S) S ePM(M E ES)+
Definition 3.3. An algorithm M is called node-level (a,, RDDP if all neighboring graphs g ~ g',
it satisfies log (P()))(())))) S where P, Q are the distributions of M M(").
DP-SGD for Private Learning. DP-SGD is a variant of the standard SGD algorithm, designed to ensure that the training process of machine learning model adheres to differential privacy [2 26 25
It assumes that the mini-batch gradient is decomposable with respect to each training sample: for
mini-batch B- (x),-... ........)) }. the gradient satisfies g(B) = Ex,ers gxr;). This assumption enables bounding the sensitivity max8-.8' llg g(B') la S C via per-sample gradient clipping, where each g(x;) is replaced by g(x4)/ max((lg((;)) C). We refer to this per-sample, independently applied clipping as standard clipping throughout the paper.
Privacy Amplification by Subsampling. Let D be generic dataset, and S be sampling mechanism that produces a random mini-batch B S(D). Traditionally, the dataset is unstructured collection of samples D = {II,,.., .... NN and S(D) a random subset B = {I ...,, sampling without replacement
..., F..} C D, e.g., S is Poisson sampling. In relational learning. however, D is a graph G and S involves a complex, multi-stage sampling process over nodes and edges, which we will elaborate in Section 4.2 Let M o denote the mechanism that first applies sampling to the dataset and then runs randomized algorithm M. Given a (e, 8)-DP algorithm M, the goal of privacy amplification is to estimate the privacy parameters (E', 8') for the composed mechanism M S [52]
3

---

4 Problem Formulation and Main Results
Relational learning aims to develop node attribute encoders for predicting and inferring relationships between nodes [57 58 59]. A key advantage is that once trained, these refined encoders can be deployed for new, unseen entities to predict potential relationships in a zero-shot manner. This capability particularly valuable applications such as addressing zero-shot recommendation systems 660 61 62 63]. and anomaly detection, where interactions involving the new entities are inherently sparse (64 65I. Formally, suppose node attribute encoder se maps entity attributes zu to feature vector ha (zw).. The goal of relational learning is to leverage the edge set & to learn the parameters O. We use scoring function (u.re = score(h,, (b,, h2) that reflects the likelihood of an edge existing between entities u and To provide supervision signals, we use both positive (observed) edges e+ E E and negative (missing) edges e & E, typically grouped into edge tuples T, = (ef" .i,1:-.... hiaee consisting of one positive edge versus Kueg negative edges [66]. Positive edges usually sampled from E, while various strategies exist for sampling negative edges [4 35) An illustration of the mini-batch sampling process is provided in Figure 1 Once the edge tuples are constructed, training proceeds by minimizing loss function C(O, T:) that encourages higher scores for positive edges and lower scores for negative ones. Common loss functions include the
InfoNCE loss, (.), - log [ep score, ) / /.ET, exp(score.) 667. and the Hinge loss,
L(e, ( max scorc,t + score,,,) ), with margin parameter ?
66 69 70
71] For
conceptual simplicity, our discussion focuses on binary relations where edges are either present or absent, though the approach can be extended to multi-relational settings.
Consider a mini-batch of edge tuples = [Ti,... Tb}, whose gradient g(B) has the general form:
g(B) Σ g g(T))
Σ glet e G,21 e C.,kany))
Eq. (I) fundamentally departs from the standard DP-SGD setting, the sensitive data unit-a node, in this case- appear in multiple edge tuples T; therehy influencing several gradient terms g(T:). This setup is also technically distinct from group differential privacy [53) since node's presence in positive versus negative edges can yield different contributions to the overall sensitivity. A detailed discussion on this point and sensitivity analysis, along with an adaptive gradient clipping method for sensitivity control, will be presented in Section 4.1
Beyond the sensitivity issue, another key challenge is that B cannot be interpreted as direct sample (i.e., a subset) from the dataset D. Instead, B consists of edge tuples composed of both positive and negative edges, each sampled from distinct mechanisms (c.g., from the set of observed edges and from randomly paired nodes, respectively). Moreover, depending on the specific negative sampling strategy employed, these two sampling processes are typically mutually dependent. In Section [.2 we formalize this sampling procedure as coupled sampling, a novel and generally challenging setting for privacy analysis. One of our main contributions is to provide privacy amplification bound for a subclass of coupled sampling where the coupling arises solely from sample size constraints across multiple stages. Notably, one such coupled sampling strategy can be employed in practice and achieves reasonably good utility in relational learning.
4.1 Sensitivity Analysis
Let us fix a node u" to be removed and analyze the local sensitivity (lg(B)- - -BB) where B' is neighboring mini-batch of B by removing node u' from B. Formally, we define neighboring mini-batches B ~ B' as follows: let B = (Ti...., Tr} where each edge tuple is of the form If node u² appears in the positive edge ext, then the whole tuple T, is removed in 13'; If, instead, node u" appears only in a negative edge CT, and not in et then B' contains the correponding tuple T, but replaces all occurrences of u² with arbitrary nodes sampled We adopt this definition of neighboring mini-batches because
T, = ,eT,,,,....... ,.,
from the graph, as shown in Fig. []] appears in our later privacy amplification analysis, corresponding to the dominating pairs that capture the statistical divergence of the subsampled mechanism when applied to neighboring graphs.
For mini-batch B3 we define: B (w) = {T; E B u E e edge tuples whose positive edges contain node B (u) (T. E B 8:a a & et 3j E [Knog]] E eTy) as edge tuples whose positive edges do not involve node but negative edges do, and Bo(u) (B((B(u)) U B-). Given the

---

Algorithm 1 Frequency-based Adaptive Gradient Clipping (FREQ-CLIP)
Input: Batch B {Ti,..., To} where Ti (e, C1,1 "ikkzg gradient terms (g(Ti), .T.))))))) and gradient norm clipping threshold C. Find the set of nodes Vr, occurred in each edge tuple T, and let V/= U, Vn. for E VB do freq(u) < Σx, cB llv E E,e or o U for T, B
Kack eig)
P Compute [B [B](+]++ (B-(w)
max (Tx-freq(T.)) t max freq(e)
g(:)) - ((Z))) (maxx) max-freq(T:) (
Return g >, (E,)
Clipped mini-batch gradient with sensitivity C
Similarly, mini-batch B' can be partitioned into two parts: B" = Ba("") U B (w"), where B ("(")) shares the (u*) " is replaced by some other nodes in Bd (u") By applying triangle inequality, the local sensitivity w.r.t. removal of u" becomes
removal node u", we can partition B into three parts: B = Bo(u") (,
(u").
same positive edges as B_ (u"), ), but every node u* in B_ B_(u")
(B) g(B")ll S
E (w))
Ig(T))II+
E (lg(T))++
E lgg(T))
(2)
(wEB_(w)
T)EB((M)
Equation is technically more difficull to analyze, as positive part and negative part jointly contributes to the sensitivity with different forms impact.
In standard DP-SGD, a common practice for controlling mini-batch sensitivity is to apply per-sample gradient clipping with a fixed constant i.e., force (T.)l I C for any T,. e implies this induces local sensitivity (IB (u*) + 2|8_(''' I) C' w.r.t. the removal of u². Although [B (u")) could be
bounded by maximal node degree, there is no guarantee for |B_ (u"). J. At the worst case, node u"
could appear in every T, via negative edges (while not appeared in any positive edges), resulting in global sensitivity of [B] C, which is too large to afford.
Adaptive Clipping. A key observation is that there is no fundamental obstacle to defining a dynamic clipping threshold, i.e., foreing [lg(T:)]| S C(T,, B) where the threshold CTT; B3) can depend on the edge tuple T; to be clipped and the whole mini-batch B. Intuitively. when mini-batch B is sampled, some nodes may exhibit high sensitivity (appearing frequently), while others may have low sensitivity (appearing infrequently). By allowing the clipping threshold to vary accordingly, we can tailor the gradient clipping to the actual sensitivity profile of the batch, rather than always accounting for the worst-case scenario as in constant clipping. Proposition 4.1 demonstrates that a simple adaptive clipping strategy (implemented by Algorithm [ can effectively reduce sensitivity.
Proposition 4.1 (Local sensitivity of adaptive clipping). For any (Ti,..., To), define clipped gradient g(T,) = g(T.)/ max (1, (lllgg((T))))) B)ll} with C(T,, B) = C/(SuPueT, [B(w)) + |3_ (u))). Then for any pair of neighboring mini-batches B ~ B that differs with respective to node u", satisfies (lg(B) g(B')] s (1 [B((""))) (w")))
Constant global sensitivity by restricting [B_ (1)). Proposition 4.1 implies that if we restrict (5=" by some constant for any u", then the local sensitivity can also be bounded by a constant for any node u" for removal, thus bounding the global sensitivity sups-B/ [lg(BB g 3(B")) by the same constant. This can be achieved by choosing any negative edge sampling algorithms that every node appears most once in the negative edges of the minibatch, yielding |B_ (u*)] 1.
Comparison with Standard Clipping. Compared to standard clipping by C. adaptive clipping (Algorithm [ reduces sensitivity and thus requires less noise for the same privacy budget, but at the cost of "penalizing" the gradients of high-degree nodes due to their potentially large (u). We argue that this penalty may not significantly harm relational learning practice. As positive edges are sampled uniformly, high-degree nodes are more frequently included and thus more prone to overfitting. wown-weighting their gradients can help mitigate overfitting and improve generalization to low-degree nodes. Our empirical studies in Section 5.2 shows that adaptive clipping indeed has a better -privay trade-off than standard gradient clipping.
Remark. Adaptive clipping in DP-SGD has been extensively studied for non-relational learning 772 which typically adjusts the clipping threshold based on statistics of individual gradient norms, such
5

---

Algorithm 2 Negative Sampling Without Replacement (NEG-SAMPLE-WOR)
Input: A mini-batch of positive edges E feet ,2,,,., ...., o }. number of negative samples per positive edge Kong, and node set V. Randomly sample b lineg nodes (U1,1,...: Aacc U2 I Ub, Facx) without replacement from V. for v5,j in [v1,1, 21, "1,Aucx* 12,1, Ub, do w f a random end in e,", and eT,, + (w0 H455)
pair w with the sampled node va
Return B = i T2, ... ToF = ((e,,,,,, C dann Him.....
distributional moments 774. In contrast, our approach for relational learning employs a normalization strategy based on node occurrences within a batch to address the unique challenges of this setting.
as quantiles 73
4.2 Coupled Sampling and Its Privacy Amplification
We study the privacy amplification of noisy gradient g(B) + (N(0, with randomly drawn mini-batch B in relational learning. The mini-batch is constructed by two steps of sampling: sampling of positive edges e,t and sampling of negative edges ei,1,... Hauex We formalize this problem in general manner, by introducing an abstract, two-step sampling called coupled sampling.
Definition 4.1 (Coupled Sampling). Let D = (DD), D(2)) be a composite dataset consisting of two datasets D(1), D(2) possibly from different domains. A coupled sampling mechanism S consists of two steps of sampling defined by the following procedure: (1) sample subset ((1) from D(2); ( ~
p(-1D0)) with (B)) 2D"), ; (2) sample (2(2) conditioned on D)22) and B(); BB() q(-1D(2),Bl)))
(3) the resulting mini-batch is B = S(D) = ,,(") :i= |B
Here coupling refers to the dependency of (B on (()) Coupled sampling is general framework that covers most relational learning sampling settings. For instance, a common practice to first sample some positive edges and "perturb" one end of these positive edges to form negative edges [68]. In this case, D = E, (() = E (non-edges), and: (1) (( = p(et" e ...(E) randomly sample a few positive edges from & (e.g., Poisson sampling): (2) to sample negative edges By(2) (e --. (. ). first randomly sample one end of e,t denoted by üi and then sample king
negative edges Bx(2) from {(ū,, v) (ū,, v) E E i.e., non-edges localized at ū, (3) the resulting mini-batch is B {(e C.,1..., Ei,knes) ) ) 1,.,,,,,1111. |B.
Coupled sampling extends the existing privacy amplification framework by generalizing the sampling process to multi-step, dependent procedure, where the flexible and potentially intricate dependencies between steps pose new analytical challenges. the absence of such dependencies, that is, (2
q( (2),, ), the contributions of each sampling step can be decomposed, allowing existing privacy amplification results to be adapted: in this decoupled case, the mini-batch B = ((B()) _.(2)) )
can be viewed as a single-step sampling from the Cartesian product dataset D x D(2), However, when dependencies are introduced, this separation no longer holds.
aardinality-depender Sampling. While general coupled sampling can be complex, there exists tractable subclass where the coupling arises solely from cardinality constraints. That is, the sampling of ((2) depends only on the cardinality of 1) and not on its specific contents: (13(3)
D(2), B))) ( D(2), (.))..
In the context of relational learning, cardinality-deee -deeendet sampling can be realized by choosing negative sampling methods that are independent of the contents of the sampled positive edges. For instance, we adopt Poisson subsampling as positive sampling, and adopt Algorithm for negative sampling, which first randomly draws some nodes from the node set (independent of specific posítive edges), and then constructs contrastive pairs by pairing one end positive edges with the sampled nodes. Note that this pairing may occasionally produce negative edges that are actually true positives- known issue in node pairing methods like in-batch sampling (35]. However, this occurs with negligible probability, especially given the sparsity of real-world graphs.

---

Algorithm 3 Relational Learning with Entity-level Differential Privacy
node attribute encoder fe, graph G = (V, E, X), loss function L, maximal node degree K, learning rate Tj, batch size b, number of negative samples per positive sample Knegs gradient norm clipping threshold C. noise multiplier a.
Input:
Initialize Randomly drop edges from so that maximal node degree is capped by K and obtain & 42 Algorithm 1J. Let positive sampling rate Y + 6/(E).
& Node degree capping
for t = 1 to I' do
positive edges E+ <- independently choosing each positive relation from E with probability 7 Generate mini-batch edge tuples B, = (71, ... NEG-SAMPLE-WORI , V)
(T(T.) t a., /ae,
g: f FREQ-CLIP(B, (g. (Ti), (15).....
> Adaptive clipping Algorithm !
5 g (V (0,, C*1]
gi f-
0c+1 0r T/
Output Dr
Treating the above pairing process as a post-processing operation, the entire coupled sampling can be viewed as a purdinalitt-depeendee sampling with D E, D = V: (1) B ~ Poisson, (E) includes each positive edge independently with probability y (2) B ~ Samplewor (V; kneg
[B( draws nodes without replacement of size kine (1)) from the node set V.
The negative sampling Saporitthm@hhas. advantages in two folds: (1) it decouples negative and positive samplings to cardinality-dependent only: (2) also restricts (x) S 1 for any node u, which is crucial to control the sensitivity as discussed in Section
Though there may exist other designs of negative sampling algorithms that also satisfy both properties, we adopt node sampling without replacement due to its implementation simplicity, as well as its regular sample size that allows to efficiently perform the negative edge pairing (c.g., compared to Poisson sampling).
Here, we provide the first privacy amplification bound for pondinaliiy-dependeen sampling. For the notion of neighboring mini-batches, we adopt removals/insertinns of K data points for (11) (denote by (3() ~A.K B))) and replacement of one data point for (322) (denoted by B ~-, B))))))
These neighboring notions align with the Poisson subsampling for g²1) and the sampling without replacement for ( The parameter K accounts for the fact that multiple associated edges can be removed due to the removal of a node. Also note that neighboring definition ( ~A,K B()),
(z(2) ~, B(2). matches the neighboring definition B ~ B3' in Section 4.1
Theorem 4.1. Consider composite dataset D = (D(1), D(2) of size |DOI| m, |D(2) n. Consider a prrdinality-dependded coupled sampling S(D): (1) B()) ~ (oisson,((D))) is Poisson
sampling with rate y; (2) ( ~ Samplewon (D))); king - (1( is sampling without replacement
of size kineg" |B{1) |. Assume function f satisfies (B(L), ((2) - _(BB(),, < C for any
B()) ~AKK B()}, and (B2) ~y B(W,, Then for any a 2 1, Gaussian mechanism f(S(D)
N/ I)) is (a.E((a)-RDD) with
1
c(a)= a 1 log Be~Bin(m.)) Va N(0,-)))(0000)++++0 ((11, N(1,,))
(3)
where Bin(m, 7) stands for the Binomial distribution, effective sampling rate I = 1- (1-1-)11k(()) (1-
(.Rue)) and V. (PlIQ) Ex==q(((x)/(())) for two distributions P, Q.
n
The proof is deferred to Appendix
B V here is a univariate integral and can be numerically 32 Although Theorem 4.1 adopts (11) as Poisson sampling and
calculated up to arbitrary precision ((2) as sampling without replacement, the analysis and results can be extended to other combinations of sampling strategies. We leave these generalizations to the extended version of this work.
So far we have addressed the two key challenges: a) sensitivity: the mini- gradient sensitivity can be bounded by a constant (Proposition 4.1). by adopting adaptive clipping (A (Algorithm [T] and restricting |B_ (w) < 1 (achieved by Algorithm 2 b) coupled sampling: the mini-batch sampling can be simplified to cardinalit--deeedden cost can be computed by Eq. (3). Integrating these ideas, we propose a DP-SGI for relational
sampling (also achieved by Algorithm 2). and the privacy
learning that leverage node sampling without replacement for negative sampling and adaptive gradient
7

---

RDP bounds (K=5)
RDP bounds (K=50)
DP composition bounds (K=
DF compostion bounds (K-50)
10a
162
Gar bound iitandes sigiigg
Out bound osandart dippiia
10t
10a
100
10
RDP RDPgia)
sound redacle digeng!
0.00
Cone boand paisite Spaso
10-1
10"2
10
bound iedestive cippiig
10
Our wwu.ennddrrrrre.. (otrdad chasing
101
10
10 107 10
10
12
30"
12
10a
10r
10"
Iteration
Iteration 7
Figure 2: Comparison of per-iteration RDP bound E((=) (left two figures) and DP composition bound (D) over T' iterations (right two figures), under different capped node degree K. Our bound (adaptive clipping) refers bound (3. Our bound (standard clipping) uses similar amplification analysis but with standard clipping. Naive bound is the Gaussian RDP bound E(a) = a/o?.
clipping, as described in Algorithm 3 The assumption in Theorem 4.1 that f (i.c., gradients) has a constant sensitivity C' regardless of the number of removals is guaranteed by adaptive clipping and (2) I 1. As a result, Proposition 4.1 and Theorem 4.1 directly implies Corollary 4.1
Corollary 4.1. Algorithm 3 achieves (a,)(()))RDP with s(a) defined in Eq.33 where D D V, and K is the maximal node degree.
Note that the bound (q.(3) depends on the maximal node degree K. To mitigate the influence of high-degree nodes, in practice we cap each node's degree at a desired constant K by randomly sampling its neighbors, same as Algorithm of [42]. The effect of degree capping on utility is explored in Figure in our later experiments.
5 Experimental Results
In this section, empirically evaluate the privacy and utility characteristics of proposed method. First, we numerically compute and compare the privacy bounds (Eq. (3). Second, we consider an application of finetuning text encoders on relational data evaluate the privacy-utility trade-offs. In particular, the experiments demonstrate the superiority of our method over standard DP-SGD.
5.1 Numerical Results for Eq. (3p
Parameters. We set the parameters based on the real-world graph statistics (Appendix F Table 2) we will use the latter experiments. By default: number of nodes n 109, number edges 5 x 106, capped node degree K = 5, sampling rate 7 10 Gaussian noise levels
0.5
and number of negative edges per positive edge kineg = 4. The clipping threshold C is set to 1. We also evaluate different combinations of parameters, which can be found at Appendix [
Per-iteration RDP Bounds. We evaluate the RDP bound =(a)) ()) shown in the left two subfig-
ures of Figure 2 which characterizes the per-iteration privacy loss in DP-SGD. Our bound is compared
against two baselines: (a) the naive Gaussian mechanism bound Gaussian (a) = a/2o² (56) without any amplification analyses; (b) the amplification bound with standard gradient clipping in place of
the proposed adaptive clipping. The latter is also supled-sampling amplification bound we derived using an analysis similar to that of Theorem 4.1 and is provided in Appendix
DP Bounds over Composition. We also compare the accumulated privacy loss of applying multiple iterations of DP-SGD in terms of (e, 8D-P, tracked by composition theorems of RDP (56) and translating RDP DP (75. We choose privacy budget ė = 1/m 0.2 10 6 and compare EDP((T) as function of iteration T. The results of DP bound over composition are shown in the right two subfigures in Figure
We observe that the composite DP bound of our method is remarkably smaller than the naive Gaussian well the amplification one with standard clipping. This strongly suggests better model utility our proposed method can bring, which we explore in the next section.
5.2 Private Relational Learning for Pretrained Text Encoders
We study the application of private relational learning for finetuning a text encoder on where relational information is injected into the encoder. We use relation prediction text-attributed graphs as the
8

---

evaluation task. The fine-tumed text encoder can be used to predict relations for unseen node sets, analogous to zero-shot link recommendation. Specifically, the training graph treated as private. and the encoder weights are privately fine-tuned using Algorithm 3 After fine-tuning, model utility evaluated by the relation prediction performance on a separate test graph. Note that although we adopt fine-tuning text encoders specific application, our al algorithm can be applied to more general relational learning scenarios (e.g., to train the weights of MLPs when entities hold dense features).
Table 1: Results relation prediction with entity-level differentially private relational learning. MAG(CHN-USSA means the model is fine-tuned on MAG-CHN and then tested on MAG-USA.
Privacy
Pretrained Models
MAG(CHN
PRECe1
sUSA) MRR
PREC81
MAGGUSA
sCHN)
AMAZISports
PREC
(loth)
PREC81
AMAZ(Cloth
sports) MRR
BERT. base
4.41
9.94
6.48
12.69
14,90
22.41
8.36
14.04
base model (wlo -uninn)
SciBERT
laRT.aagg
2,00
8.70
5.48
2.71
6.39
5.72
10.11
3.78
7.37
LinkB-RTlarge
1.09
4.01
1.46
4.75
4.01
8.60
2,06
5:37
Llama2-7B 7B
4.21
8.68
5.21
9.71
19.45
27.41
6.13
10.11
base
28.07
39:11
41.93
53.91
36.13
47.07
29.84
39.61
(non- privatei fine suning)
Hi-Tllarge
26.37
37:73
40.90
53.16
36.89
47.50
29. 30
39:76
Llama2-7B
32,80
46.67
45.65
41.01
29.21
BERT.base
12.44
21 33.80
28.26
40.29
23.66
33.31
20.18
29.59
10
(standard clipping)
BaRRlaagg
11.36
20.67
28.15
40.57
12.39
19.91
21.33
31.10
Llama2-7B
21.35
20.10
29.99
hase.
17.39
27.51
29.93
42.01
27.76
37.80
22,80
32.71
<- 10 (Ours)
lagge
18.43
29.36
31.25
43.83
19.07
28.17
24.88
35.01
Llama2-78
30.27
26.15
33.46
BERT. base
11.03
20.05
26.69
38.53
21.24
30.63
18.31
27.10
(standard clipping)
==
large
Llama2-78
8.85
17.25
22.42
17.96
32,20
28.00
7.33
13.01
18.64
27.63
DERT base
15.18
25.07
28.00
39.86
26.13
36.03
21.88
31.52
(Ours)
larg
15.32
25.78
28.22
40.78
16.09
24.57
23.72
33.76
Lluma2.77 7B
15.69
26.93
23.66
36.89
32.69
44.04
21.20
31.02
Effect of Negatiie Samp hase (MM2 s 101
The Effect Node Capping X
Privacy Utiilyy Trade-off for Reletion Prediction
Purformmm (4606)
4%
BEAT baee (V002 sport. -M
(009)
base CM002
buse wsth 121
2ome mun Mobe
95-
220ef
30-
3.59
12
13
16
0.1
0'8
#higgalye Samples Keg
Masimal Node Degiew K
Noke Mull gller
Figure Utility of different #negative sample per positive kmeg degree capping K, and noise multiplier a for zero-shot relation prediction. The legend AMAZ-sports means training on AMAZ- cloth and testing on AMAZ-sports, and similar for the legend AMAZ-cloth. the rightmost figure, numbers along each line indicate the corresponding privacy parameter EDP at different noise levels.
Experimental Settings, We adopt two pre-trained language models BERT 766 and Llama2 77 as the text encoders, and four aext-attributed graphs from two subdomain pairs: two citation networks (MAG-CHN, MAG-USA) (78) and two co-purchase networks (AMZA-Sports, AMZA-Cloth [79]. The models are first privately fine-tuned on one network (e.g., MAG-CHN), and then its utility is evaluated another same-domain network (e.g., MAG-USA). We report the overall privacy loss in terms of (e, 8),DP, where 6 is set to 1/ISurinl the size of the relation set used for training after degree capping. We use the ranking metrics of top@1 precision (PREC@ 1) and mean reciprocal rank (MRR) to evaluate the relation prediction performance. The maximal node degree is capped by See Appendix E for more implementation details.
K according to Algorithm 3
Baselines. We compare against the following baselines: (a) Base models without fine-tuning: text encoders are applied directly to the test graph without any relational learning on the training graph and thus preserve the privacy; (b) Non-private fine-tuning: text encoders are fine-tuned on the training graph without any privacy constraints; and (c) standard clipping: text encoders are fine-tuned using Algorithm
3 but with standard per-sample gradient clipping in place of our proposed method.
Evaluation Results. Table shows that all models menddtuned by our proposed algorithm outperform their non-fine-tuned base models on all four corresponding test domains for relation prediction by a large margin, even under the constraints of node-level DP E [4, 10). Meanwhile, it also consistently outperforms the one with standard gradient clipping under the same privacy budgets. This results validates the effectiveness of our proposed
algorithm for relational learning.

---

trade-off's than Ablation study. Figure 3 shows an ablation study of our method, examining the effect of the number of negative samples per positive knng- the capped node degree K, and privacy-utility trade-offs. We find that increasing K, Kneg generally brings better model utility under the same privacy budget.
Conclusion
We propose a DP-SGD variant tailored for relational learning with rigorous entity-level privacy guarantees. Gradient sensitivity is tightly controlled via carefully chosen negative sampling strategy and novel adaptive clipping. We extend privacy amplification analysis to account for bati-batches with positive and negative samples drawn from distinct yet dependent sampling mechanisms. Experiments on real-world relational data show that our method achieves better existing approaches.
Acknowledgments and Disclosure of Funding
The work is supported by NSF awards PHY-2117997, IIS-2239565, CCF-2402816, IIS-2428777, JPMC faculty award and Meta award.
References
[1] Minoru Kanehisa and Susumu Goto. Kegg: kyoto encyclopedia of genes and genomes. Nucleic acids research, 28(1):27-30, 2000.
[2] Mark EJ Newman. The structure and function of complex networks. SIAM review, 45(2):167-
256, 2003.
[3] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery data mining, pages 177-187, 2005.
[4] Jure Leskovec, Lada A Adamic, and Bernardo A Huberman. The dynamics of viral marketing. ACM Transactions on the Web (TWEBB, 1(1):-es,, 2007.
[5] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. What is twitter, social network or news media? In Proceedings of the 19th International Conference on World Wide Web, pages 591-600, 2010.
[6] Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13)i4457ii466 2018.
[7] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[8] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, volume 30, 2017.
[9] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
[10] Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom- -ooo--Acermman, et al. deep learning approach antibiotic discovery. Cell, 180(4):688-702. 2020.
[11] Jianian Wang, Sheng Zhang, Yanghua Xiao, and Rui Song. A review on graph neural network methods in financial applications. arXiv preprint arXiv:2111.15367, 2021.
[12] David Petersson. Graph-based deep learning for medical diagnosis and analysis: past, present and future. Sensors, 21(14): 2021.
Mohammad Ali Armin, Simon Denman, Clinton Fookes, and Lars
10

---

[13] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1 ):4 24, 2020.
[14] Wenhan Xiong, Mo Yu, Shiyu Chang, Xiaoxiao Guo, and William Yang Wang. One-shot relational learning for knowledge graphs. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1980-1990, 2018.
[15] Zhengyan Zhang, Xu Han, Zhiyuan Liu, Xin Jiang, Maosong Sun, and Qun Liu. Ernie: Enhanced language representation with informative entities. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1441-1451, 2019.
[16] Han Fang, Pengfei Xiong, Luhui Xu, and Wenhan Luo. Transferring image-clip to video-text retrieval via temporal relations. IEEE Transactions on Multimedia, 25:7772-7785, 2022.
[17] Tong Wu, Yunlong Wang, Yue Wang, Emily Zhao, and Yilian Yuan. Leveraging graph-based hierarchical medical entity emhedding for healthcare applications. Scientific reports, 11(1):5888, 2021.
[18] Xikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren, Percy Liang, Christopher D Manning, and Jure Leskovec. Greaselm: Graph reasoning enhanced language models. In International Conference on Learning Representations, 2022.
[19] Yanjun Gao, Ruizhe Li, John Caskey, Dmitriy Dligach, Timothy Miller, Matthew M Churpek, and Majid Afshar. Leveraging medical knowledge graph into large language models for diagnosis prediction. arXiv preprint arXiv: 14321, 2023.
[20] Emily Alsentzer, John R Murphy, Willie Boag, Wei-Hung Weng, Di Jin, Tristan Naumann, WA Redmond, and Matthew BA McDermott. Publicly available clinical bert embeddings. NAACL HLT 2019, page 72, 2019.
[21] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
[22] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX security symposium (USENIX security 19), pages 267-284, 2019.
[23] Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pages 1-12. Springer, 2006.
[24] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245 248.. IEEE, 2013.
[25] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE annual symposium on foundations of computer science, pages 464-473. IEEE, 2014.
[26] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308-318, 2016
[27] Alexander Ziller, Dmitrii Usynin, Rickmer Braren, Marcus Makowski, Daniel Rueckert, and Georgios Kaissis. Medical imaging deep learning with differential privacy. Scientific Reports, 11(1):13524, 2021.
[28] Helena Klause, Alexander Ziller, Daniel Rueckert, Kerstin Hammernik, and Georgios Kaissis. Differentially private training of residual networks with scale normalisation. arXiv preprint 0rXiv:2203.0032. 2022.
[29] Le Fang, Bingqian Du, and Chuan Wu. Differentially private recommender system with variational autoencoders. Knowledge-Basse Based Systems, 250: 200:40 2022.
11

---

[30] Mohammed A Adnan, Shivam Kalra, Jesse C Cresswell, Graham W Taylor, and Hamid R Tizhoosh. Federated learning and differential privacy for medical image analysis. Scientific reports, I 1291)) 2022.
[31] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, volume 31, 2018.
[32] Ilya Mironov, Kunal Talwar, and Li Zhang. R 'nyy differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 10530, 2019.
[33] Yuqing Zhu and Yu-Xiang Wang. Poission subsampled rényi differential privacy. In Interna- tional Conference on Machine Learning, pages 7634-7642. PMLR, 2019.
[34] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, pages 1597-1607. PMLR, 2020.
[35] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang. and Yang Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems, volume 33, pages 5812-5823, 2020.
[36] Yang Li. Michael Purcell, Thierry Rakotoarivelo, David Smith, Thilina Ranbaduge, and Kee Siong Ng. Private graph data release: A survey. ACM Computing Surveys, 55(11):1-
39, 2023.
[37] Tamara T Mueller, Dmitrii Usynin, Johannes C Paetzold, Daniel Rueckert, and Georgios Kaissis. Sok: Differential privacy on graph-structured data, arXiv preprint arXiv:2203.0922 2022.
[38] Mohamed S Mohamed, Dung Nguyen, Anil Vullikanti, and Ravi Tandon. Differentially private community detection for stochastic block models. In International Conference on Machine Learning, pages 15858-15894. PMLR, 2022.
[39] Yue Wang, Xintao Wu, and Leting Wu. Differential privacy preserving spectral graph analysis. In Advances in Knowledge Discovery and Data Mining: 17th Pacific-Asia Conference, PAKDD 2013, Gold Coast, Australia, April 14-17, 2013, Proceedings, Part Il 17, pages 329-340. Springer, 2013.
[40] Calvin Hawkins, Bo Chen, Kasra Yazdani, and Matthew Hale. Node and edge differential privacy for graph laplacian spectra: Mechanisms and scaling laws. IEEE Transactions on Network Science and Engineering, 2023.
[41] Sina Sajadmanesh and Daniel Gatica-Perez. Locally private graph neural networks. In Proceed- ings of the 2021 ACM SIGSAC Conference Computer and Communications Security, pages 2130-2144 2021.
[42] Ameya Daigavane, Gagan Madan, Aditya Sinha, Abhradeep Guha Thakurta, Gaurav Aggarwal, and Prateek Jain. Node-level differentially private graph neural networks. arXiv preprint arXiv:2111.155 15521, 2021.
[43] Sina Sajadmanesh, Ali Shahin Shamsabadi, Aurélien Bellet, and Daniel Gatica-Perez. (GAP): Differentially private graph neural networks with aggregation perturbation. In 32nd USENIX Security Symposium (USENIX Security 23), pages 3223-3240. 2023.
[44] Sina Sajadmanesh and Daniel Gatica-Perez. Progap: Progressive graph neural networks with differential privacy guarantees. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pages 596-605, 2024.
[45] Eli Chien, Wei-Ning Chen, Chao Pan, Pan Li, Ayfer Ozgur, and Olgica Milenkovic. Differen- tially private decoupled graph convolutions for multigranular topology protection. In Advances in Neural Information Processing Systems, volume 36, 2024.
[46] Zihang Xiang, Tianhao Wang, and Di Wang. Preserving node-level privacy in graph neural networks. In 2024 IEFE Symposium on Security and Privacy (SP), pages 4732- IEEE, 2024.
12

---

[47] Iyiola Emmanuel Olatunji, Thorben Funke, and Megha Khosla. Releasing graph neural networks with differential privacy guarantees. Transactions on Machine Learning Research, 2023.
[48] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011.
[49] Ninghui Li, Wahbeh Qardaji, and Dong Su. On sampling, anonymization, and differential pri- vacy k-anonymization meets differential privacy. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pages 32-33, 2012.
[50] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of private learners. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 97-110, 2013.
[51] Yu-Xiang Wang. Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1226-1235. PMLR, 2019.
[52] Thomas Steinke. Composition of differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:2210.00559, 2022.
[53] Arun Ganesh. Tight group-level dp guarantees for dp-sgd with sampling via mixture of gaussians mechanisms. arXiv preprint arXiv:2401. 10294, 2024.
[54] Jan Schuchardt, Mihail Stoian, Arthur Kosmala, and Stephan Günnemann. Unified mechanism- specific amplification by subsampling and group privacy amplification. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
[55] Yangfan Jiang, Xinjian Luo, Yin Yang, and Xiaokui Xiao. Calibrating noise for group privacy in subsampled mechanisms. arXiv preprint M.Xi:::40..09944 2024.
[56) Uya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEÉ, 2017.
[57] Michihiro Yasunaga, Jure Leskovec, and Percy Liang. LinkBERT: Pretraining language models with document links. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 8003-8016, 2022.
[58] Keyu Duan, Qian Liu, Tat-Seng Chua, Shuicheng Yan, Wei Tsang Ooi, Qizhe Xie, and Junxian He. Simteg: A frustratingly simple approach improves textual graph learning. arXiv preprint arXiv:2308.0255. 02565.. 2023.
[59] Han Xie, Da Zheng, Jun Ma, Houyu Zhang, Vassilis N loannidis, Xiang Song, Qing Ping, Sheng Wang, Carl Yang, Yi Xu, et al. Graph-aware language model pre-training large graph corpus can help multiple graph applications. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 5270-5281, 2023.
[60] Vincent Leroy, B Barla Cambazoglu, and Francesco Bonchi. Cold start link prediction. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 393-402, 2010.
[61] Jianhuan Zhuo Jianxun Lian, Lanling Xu, Ming Gong, Linjun Shou, Daxin Jiang, Xing Xie, and Yinliang Yue. Tiger: Transferable interest graph embedding for domain- zero-shot recommendation. In Proceedings of the 31 ACM International Conference on Information & Knowledge Management, pages 2806-2816, 2022.
[62] Junting Wang, Adit Krishnan, Hari Sundaram, and Yunzhe Li. Pre-trained neural recom- menders: A transferable zero-shot framework for recommendation systems. arXiv preprint arXiv:2309.01 188, 2023.
[63] Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Junchi Yan, and Hongyuan Zha. Towards open- world recommendation: An inductive model-based collaborative filtering approach. In International Conference Machine Learning, pages 11329-11338 11339. PMLR, 1021.
13

---

[64] Stephen Ranshous, Shitian Shen, Danai Koutra, Steve Harenberg, Christos Faloutsos, and Nagiza F Samatova. Anomaly detection in dynamic networks: a survey. Wiley Interdisciplinary
Reviews: Computational Statistics, 7(3):223-24) 2015.
[65] Tal Reiss, George Kour, Naama Zwerdling, Ateret Anaby Tavor, and Yedid Hoshen. From zero to hero: Cold-start anomaly detection. In Findings of the Association for Computational Linguistics ACL 2024, pages 7607-7617, 2024.
[66] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11-33, 2015.
[67] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1807.00344 2018.
[68] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems, volume 26, 2013.
[69] Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplanes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
[70] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In International Conference on Learning Representations, 2015.
[71] Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[72] Egor Shulgin and Peter Richtárik. On the convergence of DP-SGD with adaptive clipping. arXiv preprint arXiv:2401. /2916, 2024. A version of this work appeared as arXiv:2401. .111166... Previous search results mentioned arXiv:2412. 19916 which appears to be a typo and likely refers to very different paper given the date. The most relevant result for adaptive clipping by Shulgin & Richtárik that was found consistently in search results related to "On Convergence of DP-SGD with Adaptive Clipping" pointed versions from early 2024, for example, one version of the paper with this title and authors is arXiv:2401. 12916. If there's 's specific December 2024 version (2412.xxxx), its BibTeX would be similar but with the updated arxiv ID and potentially year if it's a major revision or new paper.
[73] Galen Andrew, Om Thakkar, H. Brendan McMahan, and Swaroop Ramaswamy, Differentially private learning with adaptive clipping. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 20461-200000 104755. Curran Associates, Inc., 2021.
[74] Chengkun Wei, Xianrong Wu, Yawen Liu, and Yiguang Chen. DC-SGD: Differentially private SGD with dynamic clipping through gradient norm distribution estimation. arXiv preprini 2.Xiv:5503.22980 2025.
[75] Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis test- ing interpretations and renyi differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 2006. PMLR, 2020.
[76] Jacob Devlin, Ming-Wes Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pages 4171-41866 2019.
[77] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.0928: 2023.
14

---

[78] Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma. Darrin Eide, Bo-June Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th International Conference World Wide Web, pages 243-246, 2015.
[79] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 43-52, 2015.
[80] Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory, 60(7):3797-3820, 2014.
[81] Haoteng Yin, Rongzhe Wei, Eli Chien, and Pan Li. Privately learning from graphs with applications in fine-tuning large language models. arXiv preprint arXiv:2410.08299, 2024.
[82] Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2015.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claimed contributions of sensitivity analysis, adaptive gradient clipping
algorithm and privacy amplification analyses are presented in Section 4.1 4.2 Experimental
section 5.2 validates the effectiveness our proposed methods in terms of privacy-utility
trade-offs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer: [Yes]
Justification: Theorems 4.1 4. are described with full set of assumptions along with complete proofs in Appendix A and Appendix B respectively.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Experimental setup is described Section 5.2 and details can be found at Appendix E
We also provide code in supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
17

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code to reproduce the experiments can be found in supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //iiss.cc/pill wttpcccpppppppppeeeeeeeeeeeeeeee http:///gggeeee/ooeSSuuiiiiisss /Cc////oddiiisssseeeeeee www.siiiccciiyiiccoo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Please refer to Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Due the time complexity of our experiments (fine-tuning large language models), we do not report statistical error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
18

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research is carried out according to the NeurIPS code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer to Appendix G
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our work aims to develop theoretical framework for node-DP DP relation learning, and does not involve the release of large-scale powerful models or sensitive datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The models and the datasets in our experiments properly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: the code used in our experiments is released along with clear documentation and instructions for reproduction.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
21

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy buttps://neure wwwparripp..ccoooeeeeeeeeeea /t/CCooffeeencss//2222 for what should or should be described.
22

---

A Proof of Proposition 4.1
Proof. Recall in Section
we derive the sensitivity of removing node u" for neighboring mini-
batches B ~ B²:
llg(3) gg"
Σ
(T))+
Σ
Ig(
lg( TEBL(())
Σ
(4)
(wn)
T,EB-(w) (w*)
Now consider the adaptive gradient clipping ((T)) = g / max (1, (ollll(((///TT B)Il with
C(T, B) = C/(SupweT, [B+ (u)] + (u)). For T; E B+(x)) or E BB_ (w*), since u' E T, we have
C
C
(g(TT)ll
(5)
(SuP (2)) (b)l ([++(u)) (u*)))
For T. E B" (""), the node is replaced by arbitrary other nodes, so generally u' T. We can only use pessimistic bound (lg(()) & C. Overall, the sensivity becomes
[g) g(B))l
C
(1+)B CC, (6)
< (14 (u ) + IB_ (u"))) ( (u*)1 + B (u*))
+
where we use the fact |B' [=')]= = |B_ (w-)
B Proof of Theorem 411
Theorem 4.1. Consider composite dataset D (D(), D(2)) of size |D(1) m. (D(2)
Consider a
coupled sampling S(D): (1) (()) ~ Poisson, is Poisson
sampling with rate Y; (2) ((2) SamplewoR (DAOOORRRR()) (D(2); Koog (B is sampling without replacement
of size kneg |B Assume function f satisfies [ ( f(B S C for any
B()) ~A.K B()) and B(2) ~r B(2),. Then for any a 2 1, Gaussian mechanism f(S(D))
(00,022 C2 is (ar, (c,,e(())-DD) with
E(a) 1
log Bim(,)))))) Vo ((1-T))) +r N(L, (0))
(3)
where Bin(m 7) stands for the Binomial distribution, effective sampling rate I = 1- 1- (1-2) (1- E.Rnex) and V V (PIIQ) (p==)(((=))(()))) for two distributions P, Q.
n
Proof. Notation. We use the removal/insertion notation of DP: we have two neighboring graphs G G= (V,,)), G' (V", where V = (1,2, n1. V 21, ..., n - 1} and = E {(n, u.). i 1,2, K}. Let m = [&]. Let X = 2 -2,X' X' = 2 be the all possible subset edges that represents the space of positive samplings. Let W {(y1, 1/2.., yb-k y; E V.be E [m], yi * yz) represent all possible ordered node set that represents the space of negative samplings. For simplicity. we will assume knng end we will show how to adapt to case Kneg > 1. An actual dataset we are computing on is (x, y) for some I E x, Y or (a',y) ,y" for some x' E X', y Y (again, X', Y the sampling space of positive edges and ordered node set defined on neighboring graph G'), We denote Hary as the output distribution of the mechanism acting on fixed sampled dataset (æ, y). and denote p, 9 as the mixture output distribution of the mechanism acting on a randomly sampled dataset (z, y) and (a', a/') respectively. By definition, we have
i.e., each positive sample is only paired with one negative sample. In the
Σ w(a (( J.
q= --
(a' (la'.g')pw '
p
x'.8""
where w(x, (Ir,y),ww w/''''',,, (x', are probabilistic distributions of the samplings. With abuse of notation, we also write w(r, y) wxx)w(y)x) and w'xx', (a",,")) w'(')w' (1//w/))///) Our goal is to bound V (pllg) = " and (g(pp))) Ep(p/p) i... the logarithm of Rényi divergence.
23

---

Proof idea. The proof is basically divided into three steps: (1) we will show how it is possible to extend Conditional Coupling [54] to this product data (z. y); (2) a concrete conditional coupling is constructed and proved to be valid. Using the conditional coupling, we can apply Jensen's 's inequality to obtain bound for RDP e; (3) finally, we derive the final bound by considering the properties of i.e., a constant-sensitivity mechanism.
specific Algorithm
g
Jensen's inequality by conditional coupling. The key idea is to apply Jensen's inequality to V. (-Il-)
as Vo is jointly convex [80]. To do so, we need to re-write q in terms of balancing summation. we will generalize the conditional coupling technique [54] to our case. In the following we will
show how we can achieve this in high-level view. Consider the conditional distributions wxr)AA),
where A, represents the event "r has ē removed edges (i.e., the edges involve the removed node n)", and conditional distributions wyyl By: z), = 0, 1, where BB(B,) represents the event "[yls(=) has (no) removed node n²,, where S(x) is a subset of indices defined by S(x) = {e E { 2 .... [x]}
Te has no removed edges}. We define coupling πT as a probabilistic measure on X xK+1
X' x
x2(K+1) x YY As a shorthand we write I = (Io,..., IK) E k+ g(d) = (v6 .... K )
(
kk+
and ō = (7 D)) We require coupling ( x "..''' = (t x'' JF (J, o' 12 x²) to satisfy:
Σ (á,,)) = w(zi)Ai), Ma
(8)
Σ ((Z,)) = =('xz')='(zz')
(9)
(V.0/%,,)' = w(v) (0) Bz)
(10)
M b.y'
Σ (V.V = w'1'22))
(11)
Specifically, let us denote the size |5(xx)] by L and define pn.m = 1////nnn1n..... (n-m the inverse of falling factorial from n n + 1, then we can explicitly write down the marginal probability:
m 1) be
(xx1AA,) 71211(1 7) m-mll 1 11111-111- - -K1111+ (1) (1 k) (K)
(12)
w'(x') = ? 10' ((1 m) -1
(13)
w(y; (0) |Bo, 224)
Pn- 1.- 1.11x.1- L.
(14)
ww) (1) [B,, x44)
T PP I.- 1. T. 7.Pn-1lal-1
1
(15)
w'(y') Pu-11
(16)
Suppose these requirements are satisfied, then one can rewrite g in terms of the coupling distribution (Ø x', F.y'). We start with rewriting p:
p = Σ W(x,y)xxx = Σ (wa))w(yl))un
(17)
Z.
N.
Σ w(El (I Eullla Eu( BB)((B14)
(18)
Z.
Σ
(a)4A) (w) (B, pz)
(19)
1. x.9
24

---

Now we for each index j, we can rename the dummy variable æ, by Fez v.
(1 B2 )ul( (3 1))
(20)
waaglAi)w(( (u) los, By )uo (Ar (By 2..1/
(21)
Σ x(ā,a')
Σ ((,'',Z;'')
(22)
Σ
Σ
(23)
iJ 2, J.y'
= Σ -,
(24)
2,z' N.y!
Similarly, we rewrite q in terms of n.:
q w'' (')',,')''''
Σ w' (x')a(( (oooo////c)) (
(25)
x
Σ
Σ ((ā,
(26)
n (F, x' U. No
(27)
Z, T.9''
These imply that by convexity of V (-1l-,, we have
(a(p))) S
Σ
(F. <F..d,
w( (ai))a (B)lo)) I
(28)
F. N.''
is
V. (glp)) S
Σ
Pewll ((,) (B) (B)))((BB)))))))) (
(29)
E g.v'
Construct coupling, Now we are going to construct a specific π to bound V. V.((ll)) and (a(ll)))
The sampling process of π (ā x', J. v') goes as follows:
first sample zo w.(lA)). and denote the size of by L;
for each 1, 2, .... K, sample by randomly drawing a size-i subset of the removed edges and adding the subset to zo:
let x = 2o:
sample (0) w. zo);
then sample v0" (1) by randomly replacing node in (0) with the new node n;
for each i K,
sample yi (0)
(0) to and adding them to oo:;; by randomly choosing nodes (not in yo
sample y (1) by first randomly replacing node in (0) with the removed node
(call this intermediate sample ÿ) and then randomly choosing nodes (not in ğ and not include the new node n) and adding ÿ.
let y/ y0
25

---

Note that this particularly construction yields the following factorization:
((,, x' U. v') = (ā. x' ( [7, x'),
(30)
K
π x(ž,x'= = ( 20)
(2;;)00)
(31)
r AJ. ",,y""Z, (vb (0) (1/ 1110 (0)
(0) )T )
11) 100
II
(v;
(0) (0)
Mo ) (T( (w00))
(1)
(32)
Now let's verify the coupling constraints 8 to 11I Exrtaohar x ((,xx))= (2o) Azo desired. When i 2 1,
For Eq. 8 when i = 0, we have
Σ (T, x') Σ ( = 1111 m) [a)
w(r((Ai); (33)
(7)
where we use the basic fact from our construction that x ( w(Fo|AA) (1)))-)) -7)m-Kk-
(1))) 1/(5), and (4)
7I jm b- /(((((())))) (K) (1 -))- 74(1
((.)- Thus Eqn.(8) holds. For Eqn. (9). clearly Σx
a xT x²) = Em, T(z)) (xO) =
E x (xr))((x) 2o) = π (x') w<xll Ao) 7 (11(1 (1 ) K-1 = =w'xx'. So Eqn. (9) holds as
well.
For Eqn.q00.. when j = 0, we have Σ i ( J,y - 1/ p x') = T(=²)) = w(y (0) Bo, mo) by
our construction. When + 0, = 0, recall that Pr,m = 1/n(n 1) ... (n m + 1) the inverse of falling factorial from to m + 1, then
Σ
Σ
x T36 (0) (o)
(0) (0) 90 x4) Pn-1,1Pm--a L,1 = 1. 1.o----PP---l--- 1
Ma J.a
= =w(y;" (0) ( T:).
(34)
Here we use the fact that |xs| = |ool + i Lii. When + 0, we have
Σ (T.V'K,,''
Σ
Tuu (0) [20) 10
(0) xx,)) = (n - L) 1n- I Pn
=
Aol Dar
(35)
1
L Pn-1,12.1-1 w(y (1) B1,
1
P
L
Finally, (T, = w(y'l vo) = 1,7 Pn-1,la'). Therefore, the constructed n is
valid coupling and thus Eqns 28
29
hold.
Derive explicit bound. Now
going to derive bounds for Eqns. 28 and (29 by plugging
into it. Note that coefficients
satisfy Eig ((A, Jw B (..) 1 and thus
Enjoo w( (AA)) = - ((An) ) ( Bn (z)). Therefore, we can write
Σ (((A,) (B,
w(A))w Bo 2o. (0) + Σ (B))),Bll m
(36)
1970
((A))a(B)lrz (x:)
(w(A))u(Bolzo)) n Moo
( +1 - ((n)) H M (er.)")) )
I - (A)) ) Boluo)
(37)
Notice that (w, By 1x.l w Ap) (Bol)(BBBll)) Bolxz))) Fissoo are coefficients of convex combination. Thus by Jensen's 's inequality, Eqn. becomes
T x x T. F.V') w(A,) Ja B (B, (z:)
V (pllg) <
Σ
w(o ) (Bolllll (Bolzo)
8,w¹ B. A.040
(38)
Va (w(A))w(BB)) Bolwo) Moo. + (1 (w Meangn (ll
26

---

and similarly for Va (9llp)). It is worthy noticing that this Jensen's 's inequality is generally not tight. Fortunately, if we assume the sensitivity of Gaussian mechanism Mur.,(")) ( is constant regardless of number of removals and replacements j. then the Jensen inequality is indeed tight.
The coupling ensures that Zo x', (0) y and (2i, )) is "neighboring" to (zo, ' ), i.e.,
the difference the mean of 4 =so.y6" and s.. is bounded. On the other hand, the coefficient
/zol/n depends on the size of zo. which is Binomial distributed |zo| Bin(m, ?). That means the divergence V (-Il)) varies with different (zo| To reflect this dependency, we write the sum conditioning on different [2o] E:
w 20)
V o (pllg) 1
(A (B,(
Σ Bin Bin(l)m,,)
E
x(T,I', 2/2/oll = E)
w( Ao) )uv Bo (ro)
(39)
H.x Bol 3.0000
v. (w(Ao)w (Bol 1 Mao.s
(0) + (1 - www (w (Bolz0)) 1 /. (IMerr))
Now to get rid of the coefficients we take supremum over all possible neighboring xo ~ and (0) (5)
Yo Yi subject to |zol = f. That is, we are interested in
sup La (u(A))w(Bolag Pzo.v.") + (1 (An) xo)) P2 so.vo -
=
(40)
Since M., Ma.,y," () is isotropic Gaussian, (-ll-) is rotational invariant, and the supremum reduces to univariate Gaussian:
Aa (i,
Va (w(An) NNO,, o²) + +1 ((oo)))Bo)zo)) N(L2(i,). o²) (2)
(41)
where [22(1, is the 1.2-sensitivity of neighboring zo Iz. y0u v under |
t. Note
that Theorem 4.1 assumes Le is a constant C' (WLGO we further take L = C = 1) regardless of i, E if we use adaptive clipping. As result, A,(i, (e) is only function of e (as w( (olo = 1- L/mn), and
((Ai)u(BBlar)) Aa(e)
V. (plla) S Σ Bin(E
Σ 2,x' Shal A.0
= =0) 0.y'
w( ) ( (mo)
(42)
=Σ Bin(e(m,,)A.(0))
For another side V. (g(lp), we can follow the same procedure and use the fact V, (N of)
(0, a²) + (N((c < V, ((1 (), o²) + y/N (c) 32 This will lead to the same upper bound V (qllp) $ E, Bin(E/m, A) Therefore, the amplified e(a) satisfies
<(a) <
log Σ Bin(E]m, ())
(43)
The only thing left is calculate Aa()). By defining (B f/n), we can write
A. V. V1 ((1-),)(0000 +T
(44)
which is well studied in previous literature and can be numerically calculated up to any desired precision. See 322. Finally, to generalize the case where each positive sample can be paired with kneg > negative samples, we can think of first copy positive samples knrg times and follow the same derivation above. It is thus equivalent to replace E by kingg l in Te, with others remaining the same.
27

---

C Amplification Bound for Linear Sensitivity (Standard Clipping)
In this section, derive privacy bounds for but with standard clipping in place of adaptive clipping. Recall that if we apply standard gradient clipping, the sensitivity is C- (IB+(")) +2 |B_ (l) according to Eq (
sampling stated in Theorem 4.1
Theorem C.I. Consider a composite dataset D (DO), D(2) of size |DCI m. |D Consider a cardinalit--depnndee
coupled sampling S(D): (1) B(L) Poisson, (D(L) is Poisson
sampling with rate qi (2) (( SamplewoR (D)))) (D(2); Kneg |B(1)) is sampling without replacement of size kneg."
| Suppose a function f satisfies
[(BB)) - f(B (138))))
- C- (k: + 2), Bf ~A. (C)),B(a ~ep B(0)
(45)
[(B() ,B()) I(B())) ((B))
< c. iB" ~ak B
(46)
for any S K. Then for any a 2 1, Gaussian mechanism ((S(D)) + +N(00, is (a, RDP with
K ΣΣ
=(a) = 1
(t) ( + 23
max log Bin(m, aa
i=0
(47)
K
log Be- Va [N(0,02)
ΣΣ
Wr.5 (0) NN 2j. 22) 22,0011
i=0
Here Bin(m, 7) stands for the Binomial distribution, (i, = (1) (1 E-l0-g--ne/fl
knek////// (T) and
(f) = (K) (1-)) () Kig- knog/ n, and V. (PllQ) = ( for two distributions P.Q.
Proof. The proof first follows the exact same coupling construction in the proof of Theorem Appendix B
4.1 in
up to coupling bounds Equations 28 and 29
(a(p)) S
Σ
Σ i.j
(A, (B)l:))
(48)
(gll)) <
Σ
U.V.
Va
Pay Σ
((i))
ma
(49)
Again, we first condition on |zoo and obtain (we take Vo (xllg) for example, similar holds for V. (gllp))
(a(p)) S Σ Bin(elm, 7)
Σ n(ē 1'..'.'.'1 T.2'|0zo a
I (B)))u(BBl v.. [ of
(50)
Recall that in the coupling म, n (ā J.y') # if and only if x' xo, sf' y) xy has extra (0) has no removal node n and yf has removal node We can take the worst
samples than wo. Vi case and obtain
V. (p(p)) Σ Bin(elm,n)
Va Σ w (AA)) 2.. llMe w
sup F.z' (F,, Fa (
(51)
here note that w( (B, (x:) only depends on the size of S(xs), i.e., the subset of o; without the removal node n. We have (((x)) = lool = f. due to our construction of coupling π. Given we are using Gaus- sian mechanism, that / "
N((( (1) o2I) with sensitivity |u v (1)), p(xy w/ (11)) S
)
28

---

RDP bounds 22
RDP bounds (1
RDP bounds (0)
bounds (Rae
10a
10
10
10
10
104
Out bound intap
2ound iadaziive
102
Our sound isdadia cliping
107
RDP
10
auriean Loa lippke)
10-3
10-2
10-2
10-
voaarlreaaiie ceppie
sound (oundard dlpaing
10
10
10
10
10
10'
10
10
10
10
10
10
10
10'
10'
10
DP composition Lounds 16
DP composition bounds Uh... -4)
DP composition bounds UK -B)
DP composition Go bourdss (h -66]
16
Out sound colptin paping Saren Craaettr de Apoird
10a
seasd rezasik di spogi
10a
Ou sxare resache cipprg!
10a
bourd recastin cippegt
Sibr beart intipto Spenn
Nawe tourd Entiption cupang)
104
10a
10
101
10"
105
102
107
16
107
102
102
16
10
10:
103
Reration
Baration
Beration
Daraaion T
Figure Comparison of per-iteration RDP bound E(a) (first row) and DP composition bound D (T)
over I' iterations (second figures), under different number of negative edges per positive kueg. Our bound (adaptive clipping) refers to the bound in Theorem 4.1 Our bound (standard clipping) refers
to the similar amplification bound with standard clipping in place of adaptive clipping. Naive bound
simply the Gaussian mechanism RDP bound e(o) = a//o².
l - -i-i'++ 2 j'|. the worst case is achieved by univariate Gaussian (Theorem 3.8, 54
Therefore,
(a(plla) s Σ Bin(L|m,
Σ ((A))w(BB1))) N( 21
(52)
Va(gllp)= S
[N(0,03) Σ
N(i 2j,0²
(53)
Finally, recall that (A,) = (K) (1))((1 - >)* and (B = 1 and w(B = l/n. For
kneg > 1, we replace by kneg L, as we argued in Appendix B This finishes the proof. O
D Numerical Results of RDP and DP Bounds
We provide more results of comparison of per-iteration RDP and DP composite bounds over T iterations (Figures 4 and 5) at different combinations of parameters. Again, by default we have: number of nodes n 10s. number of edges m x 10 capped node degree K = 5, sampling rate 0.5 and number of negative edges per positive edge Kneg 4. We vary one of them while keeping others unchanged. To obtain composite DP bounds, the composite RDP parameters
y 10-5 Gaussian noise levels
translated into DP parameters using the following formula.
Theorem D.1 (175)). If an algorithm M is (R,E)-RDP, then it is (s + log((a 1)/a) (log 8
loga)/(a- - 1), 8)-DP for any
E More Experimental Details and Results
Dataset. There are four text-attributed graphs among two subdomain pairs, i.e., citation relations of papers written by authors from USA and China in Microsoft Academia Graphs (MAG, (78)) and co-purchased relations in clothing and sports categories from Amazon Shopping Graphs (AMAZ, (79). The statistics of the real-world dataset are summarized in Table 2 We followed the same procedure of preprocessing datasets and performing evaluation for all models as [T. For degree capping, we adapted the approach from
42 to drop edges and obtain the degree-capped training set.
29

---

[am]]
(.m
10
10
10
10
10
10
18
Oet bound ledagt dasiny 5a.e www.e chpiel
10-1
bound ledapioe dizaing Saier Gelerie cippett
Garkkandd laagete dgaap Raten boed Saighe cipprt
bound locastive deang) Nater www.eeeeeeeeeeeeeeeeeeeeeeeeeeee
10a
10
10-4
10-
10
10-4
10-4
DP composition Lounds 0.50
DP composition bourds 1g
DP composi ion bouncss 1om2
DP compuss kien bounds Iom
10a
bound jedaps Out boand jeandess rgt
bound jita staade di pigggg
10a
Gut bound istadde daping
Gar boand
our boand lcardadd cagang)
lecatt dasing)
10
10
10
16
10
10-1
106
122 10F 10-
302
30 10a 30.
10'
12a
13F
162
12
10
Iteration
Figure 5: Comparison of per-iteration RDP bound e(a) (first row) and DP composition bound CD over T iterations (second figures), under different noise level a. Our bound (adaptive clipping) refers to the bound in Theorem 4.1 Our bound (standard clipping) refers to the similar amplification bound with standard clipping in place of adaptive clipping. Naive bound simply the Gaussian mechanism RDP bound e(a) = a/o².
(T)
Experimental details. Each LLM fine-tuned through the proposed Algorithm 3 Jusing the InfoNCE loss. The overall privacy loss is tracked through Theorem 4.1 and converted to (e, dDDP, where 1/ E/aiiai),, the size of the relation set used for training after degree capping. Note that actually adopt Adam optimizer to update model parameters in Algorithm 3 which has the same privacy guarantee of SGD-style update in the original form, due the post- proteprocessing property of
DP 82 26].
Compute Resources. We server with AMD EPYC 7543 CPUs, 512GB DRAM, and NVIDIA Quadro RTX 6000 (24GB) GPUs for experiments of BERT-based models and A100 (80GB) GPUs for Llama2-7B models. The codebase is built PyTorch 2.1.2, Transformers 4.23.0, PEFT 10.0,, and Opacus 1. The source code is attached and should be used with the specified version of Transformers and PEFT packages from HuggingFace and the Opacus library above.
Impacts of node degree capping. Table further shows the effects of node degree capping for non-pe non-private training. Interestingly, the with node degree capping usually outperforms the one without node degree capping. We hypothesis that the node degree capping could prevent overfitting to the high-degree nodes and help generalization,
argued for the adaptive clipping.
Table 2: Dataset statistics and experimental setup for evaluation.
Dataset
#Entity
#Relation
#Entity (Test)
#Classes
#Relation (Test)
Test Domain
AMAZ-Cloth
960,613
4,626,125
476,510
9
10,000
AMAZ-Sports
AMAZ-Sport
357,936
2,024,691
129,669
16
10,000
AMAZ-Cloth
MAG-USA
132,558
702.482
6.653
40
63,635
MAG-CHN
MAG-CHN
101,952
285,991
6,534
40
34,603
MAG-USA
Table 3: Results on srhatii prediction of model fine-tuned with and without degree capping.
Privacy
Pretrained Models
MAGICHN
PRFC01
-USA)
MRR
MAGIUSA
PRECC
-CHN)
MRR
AMAZiSports
PREC01
-Clth) MRR
AMAZiCloth
PREC6
-Sports)
MRR
BERT.buse
-- no (no capping)
BaRT.
26.37
37.73
40.90
53.16
36,89
47.50
29.30
39.76
Llama2-78
32.80
46.67
45.65
58.59
41.01
52.39
29.21
41.44
bERT.buse
39.98
<- (K=5)
HaRT.argge
27.67
39.23
40.40
52,79
36.25
46.90
30.75
41.36
Llama2-7B
39.68
53.35
46.29
59.96
38.73
50.95
32.54
45,16
30

---

Limitations and Future Works
For adaptive clipping, we mainly focused on comparison between clipping by constant (i.e., standard clipping) and clipping by number of node occurrence (which leads to constant sensitivity). It will be an interesting future direction to further explore the privacy-utilly trade-offs of general adaptive clipping strategy based some functions of node occurrence.
For the privacy amplification bounds of cardinality-depenie bound was not yet explored, which can be also an interesting future work.
coupled sampling, the tightness of the
G Broader Impacts
This work develops node-level differentially private DP-SGD framework for relational learning, advancing the theory and practice of savacc-preserving machine learning on graph-structured data. Graph data are ubiquitous in modern machine learning applications, and our work helps protect the sensitive attributes or existence of individuals in network while still enabling meaningful relational inference.
We do not foresee significant negative societal impacts from this work, since our contribution is theoretical and does not involve the release of high-risk models or data.
31


Reviews:
[{"review_id": "VJPF7QTcQe", "reviewer": "Reviewer_nM78", "summary": "This paper introduces a novel framework for relational learning with entity-level differential privacy (DP) guarantees, addressing challenges unique to graph-structured data.  Relational learning, which leverages relationships between entities, is increasingly applied in sensitive domains like healthcare and finance, where privacy concerns are paramount.  Standard DP mechanisms, such as DP-SGD, struggle to handle relational data due to high sensitivity caused by entities participating in multiple relations and coupled sampling processes that complicate privacy amplification analyses.  To overcome these challenges, the authors propose a tailored DP-SGD variant that incorporates adaptive gradient clipping based on entity occurrence frequency and a privacy amplification analysis for a tractable subclass of coupled sampling. These innovations ensure rigorous privacy guarantees while maintaining strong utility in relational learning tasks. \n\nThe framework is validated through experiments on fine-tuning pre-trained text encoders using text-attributed relational datasets.  Results demonstrate that the proposed method achieves better privacy-utility trade-offs compared to standard DP-SGD approaches.  The paper also provides detailed sensitivity analyses, theoretical proofs, and privacy amplification bounds, ensuring the robustness of the proposed method.  Additionally, the authors explore the impact of key parameters, such as node degree capping and the number of negative samples, on model performance and privacy guarantees.  By advancing the theory and practice of privacy-preserving machine learning for graph data, this work contributes to safeguarding sensitive information while enabling meaningful relational inference in real-world applications.", "questions": "Please focus on addressing the weaknesses raised above.", "limitations": "Yes.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n- Extensive theoretical analysis and experimental results are conducted on the proposed method, providing a thorough study of the method.\n- The proposed method provides an optimization process for relational learning under strong privacy protection of node-level DP.\n- The proposed mechanism can be easily adapted from an existing mechanism (DP-SGD).\n\n## Weaknesses\n\n- The analysis of local sensitivity is conducted on a scenario where any node $u^*$ sampled in an edge tuple $B$ must only exist in one edge tuple $T_i$ (based on lines 157-160). However, the proposed mechanism never discusses how to ensure this happens in Algorithms 1, 2, or 3. Furthermore, in this scenario, the sampling of the batch $B$ does not follow Poisson sampling anymore because it has to ensure any node $u$ only appears in one edge tuple $T_i$, leading to the uncertainty of the privacy guarantee of Alg. 3.\n- Although the proposed method leverages an adaptive clipping method, it is not very efficient. Specifically, in the clipping process of Alg. 2, after adding the $max-freq(T_i)$ to the clipping threshold, it seems like the new threshold is always smaller than $C$, incurring more information loss from the gradient. Furthermore, the noise added to the gradient is still $N(0, \\sigma^2C^2I)$, which is not scaled to the local sensitivity. Although the DP protection stays the same as the original DP-SGD, the information loss is higher due to the lower gradient clipping threshold.\n- The privacy application analysis in Theorem 4.1 ignores the impact of multiple training rounds $T$. This is a critical point because the training process is conducted with multiple training rounds, which incur more privacy amplification as discussed in DP-SGD.\n- The experiments do not consider other state-of-the-art baselines for both node-level DP (e.g., Sajadmanesh et al. [1]) and entity-level DP (e.g., Lai et al. [2]).\n- The presentation of the paper is hard to follow. The mathematical proofs of the theorems and propositions are very confusing, with lots of notation that was never introduced in the main body.\n\n[1] Sajadmanesh, Sina, et al. \"{GAP}: Differentially private graph neural networks with aggregation perturbation.\" 32nd USENIX Security Symposium (USENIX Security 23). 2023.\n\n[2] Lai, Phung, et al. \"User-entity differential privacy in learning natural language models.\" 2022 IEEE International Conference on Big Data (Big Data). IEEE, 2022.", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer nM78 for their comments. Here is our response.\n\n> **W1-1**: “The analysis of local sensitivity is conducted on a scenario where any node $u^\\{\\*\\}$ must only exist in one edge tuple $T_i$ (based on lines 157-160). However, the proposed mechanism never discusses how to ensure this happens in Algorithms 1, 2, or 3”\n\nWe thank the reviewer for their valuable feedback. We apologize for the lack of clarity in our manuscript that led to confusion regarding our sensitivity analysis. We would like to clarify that our framework **does not assume** a node exists in only one edge tuple; on the contrary, it is designed to handle the general case where a node can appear in an **arbitrary number** of edge tuples. \n\nThe passage on lines 157-160, which describes when a \"node $u^\\{\\*\\}$ appears only in a negative edge,\" serves to formally define a neighboring mini-batch for the purpose of our analysis. It illustrates the impact of removing $u^\\{\\*\\}$ on a specific subset of edge tuples (denoted by $B_\\{-\\}(u)$) whose negative edges contain $u^*$. The fact that an entity can be associated with an arbitrary number of edge tuples is precisely what leads to the high sensitivity that we aim to resolve. Our analysis captures this explicitly in Equation (2), which sums the gradient contributions over all tuples containing the node $u^\\{\\*\\}$.\n\n\nTo manage this high sensitivity, our work proposes two key strategies:\n- Adaptive Clipping (Algorithm 1): We introduce FREQ-CLIP, which calculates the occurrence frequency of each node within the mini-batch and uses this frequency to modulate the gradient clipping threshold. This directly counteracts the large influence of nodes that appear in many tuples.\n- Constraining Negative Occurrences (Algorithm 2): We propose to use a specific negative sampling strategy, NEG-SAMPLE-WOR, which samples nodes without replacement. This design is crucial as it guarantees that any given node can appear in the negative edges of at most one tuple within the batch (i.e., $|B_\\{-\\}​(u)|\\le 1$ ).\n\nAs demonstrated in Proposition 4.1, the combined use of these two strategies successfully bounds the global sensitivity to a constant, which is a key requirement for DP-SGD.\n\n\n> **W1-2**: \"Furthermore, in this scenario, the sampling of the batch $B$ does not follow Poisson sampling anymore because it has to ensure any node only appears in one edge tuple, leading to the uncertainty of the privacy guarantee of Alg. 3.\"\n\nIt is indeed correct that the batch $B$ does not solely follow Poisson sampling. To control batch sensitivity and ensure a rigorous privacy guarantee, our approach involves a specific negative sampling strategy, such as sampling without replacement, which ensures that each node appears in at most one negative edge within a mini-batch. The mini-batch $B$ is constructed through a two-step sampling process (see lines 143–147), which we formally define as 'Coupled Sampling' in Definition 4.1. A key contribution of our work is providing a **rigorous privacy amplification guarantee** for this coupled sampling scheme (Theorem 4.1), which directly quantifies the privacy leakage of Algorithm 3.\n\n\n> **W2**: “it seems like the new threshold is always smaller than $C$ , incurring more information loss from the gradient. Furthermore, the noise added to the gradient is still $N(0, \\sigma^2C^2I)$ , which is not scaled to the local sensitivity”\n\nWe appreciate the reviewer's insightful observation that the adaptive clipping thresholds can be smaller than $C$. The adaptive clipping thresholds indeed vary for different edge tuples within a data batch, and they are designed to be potentially smaller than $C$ to ensure the **overall batch sensitivity** remains bounded by $C$. The noise added to the batch gradient is scheduled according to this overall batch sensitivity $C$, ensuring that the clipping threshold appropriately matches the injected noise.\n\nRegarding the concern about potential information loss: while the gradient clipping threshold is lower for some high-degree nodes, these nodes are also sampled more often during training. This repeated exposure could help compensate for any potential information loss from individual gradient terms. Furthermore, as discussed in lines 195–202, down-weighting the gradients of high-degree nodes can actually help mitigate overfitting and improve generalization to low-degree nodes. Our empirical results in Table 1 indeed demonstrate that adaptive clipping achieves a better utility-privacy trade-off compared to standard gradient clipping, which clips all gradient terms using a constant threshold.\n\n\n\n> **W3**: “The privacy amplification analysis in Theorem 4.1 ignores the impact of multiple training rounds”\n\nPrivacy amplification Theorem 4.1 calculates a **per-round** privacy bound, and we calculate the overall privacy bound for multiple training rounds by RDP **composition theorem** ([3], Proposition 1). This is common practice for privacy amplification analysis, e.g., [4]. Thank you for making this point, and we will highlight this as a per-round bound in the revised manuscript.\n\n\n> **W4**: “The experiments do not consider other state-of-the-art baselines for node-DP [1,2]”\n\nWe appreciate the reviewer's suggestion to consider additional state-of-the-art baselines for node-DP, such as those in [1] and [2]. However, it's important to note that these methods are **not directly applicable** to providing entity-level differential privacy guarantees within the context of relational learning. This is due to the unique technical challenges presented by the relational learning training objective (Equation (1)). Specifically, relational learning introduces complex sensitivity issues (Equation (2)) and a distinct privacy analysis problem for coupled sampling (Definition 4.1).\n\nIn contrast, [1] primarily focuses on node classification tasks with Graph Neural Networks (GNNs), where privacy mechanisms prevent leakage of node features during neighborhood aggregation. [2] addresses user privacy in language model training on textual data. Neither of these approaches is designed to handle the core privacy risk in relational learning, where relations themselves are part of the loss function computation and mini-batches are constructed through complex, coupled sampling of relations. We provided a more detailed discussion on why existing DP-GNN methods are not applicable in our Related Work section (lines 68–81).\n\n\n\n[1] Sajadmanesh, Sina, et al. \"{GAP}: Differentially private graph neural networks with aggregation perturbation.\" 32nd USENIX Security Symposium (USENIX Security 23). 2023.\n\n[2] Lai, Phung, et al. \"User-entity differential privacy in learning natural language models.\" 2022 IEEE International Conference on Big Data (Big Data). IEEE, 2022.\n\n[3] Mironov, Ilya. \"Rényi differential privacy.\" 2017 IEEE 30th computer security foundations symposium (CSF). IEEE, 2017.\n\n[4] Zhu, Yuqing, and Yu-Xiang Wang. \"Poission subsampled rényi differential privacy.\" International Conference on Machine Learning. PMLR, 2019."}, {"review_id": "hnyaz5TZhP", "reviewer": "Reviewer_xnXK", "summary": "This paper proposes a principled framework for differentially private relational learning, focusing on edge existence as the sensitive attribute. It introduces adaptive gradient clipping and a novel sampling analysis to handle high sensitivity and interdependent data and uses these to introduce an new DP-SGD framework suited to relational learning.", "questions": "- Would the performance improvement be as significant in the high privacy regime?\n- Can you provide an upper bound for ε(α) in the theorem to help with its interpretation?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper addresses a timely and previously unexplored problem, contributing novel insights to the field.\n\n- It presents a comprehensive critique of existing approaches, clearly articulating their limitations. The proposed framework demonstrates significantly improved privacy guarantees compared to naive baselines.\n\nWeaknesses:\n-The experimental evaluation lacks results for high-privacy regimes (e.g., epsilon = 1), which limits the assessment of the framework's performance under stricter privacy constraints.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer xnXK for their positive feedback.\n\n> **W1 & Q1**: “The experimental evaluation lacks results for high-privacy regimes”\n\nWe thank the reviewer for the comment. Our experimental evaluation, specifically the rightmost panel in Figure 3, already studies the utility-privacy trade-offs across a range of privacy budgets, from $\\epsilon>10^5$ down to $\\epsilon=2$. This range of $\\epsilon$ is consistent with previous works in node-DP graph learning, such as [1]. Generally, achieving very strong node-level (entity-level) differential privacy, such as setting $\\epsilon=1$, can lead to significant degradation in model utility, as observed in other node-DP literature (e.g., [2], Figure 6). We believe the chosen range adequately demonstrates the trade-offs of our proposed method.\n\n\n\n> **Q2**: “An upper bound for $\\epsilon(\\alpha)$ to help with its interpretation”\n\nThe amplification bound in Equation (3) admits a natural interpretation: the $\\Psi$ term corresponds to the exponential of the Rényi divergence between a Gaussian mixture and a zero-mean Gaussian. This mirrors the form of the standard Rényi differential privacy amplification bound [3], but with a modified effective sampling rate that depends on node degree. The upper bounds presented in [3] are applicable to our setting and can be used to estimate the divergence, albeit with some loss in tightness.\n\n\n[1] Daigavane, Ameya, et al. \"Node-level differentially private graph neural networks.\" arXiv preprint arXiv:2111.15521 (2021).\n\n[2] Sajadmanesh, Sina, et al. \"{GAP}: Differentially private graph neural networks with aggregation perturbation.\" 32nd USENIX Security Symposium (USENIX Security 23). 2023.\n\n[3] Mironov, Ilya, Kunal Talwar, and Li Zhang. \"R\\'enyi differential privacy of the sampled gaussian mechanism.\" arXiv preprint arXiv:1908.10530 (2019)."}, {"review_id": "rVMPX1itRU", "reviewer": "Reviewer_m1UV", "summary": "This paper proposes a DP-SGD framework for relational learning with formal node-level differential privacy guarantees. To address high sensitivity and coupled sampling challenges, the authors introduce adaptive gradient clipping based on node frequency and a new privacy amplification analysis for cardinality-dependent sampling. Experiments on fine-tuning text encoders demonstrate improved privacy–utility trade-offs over standard DP-SGD.", "questions": "- This work focuses on node-level DP. Does it offer any insights or potential solutions for achieving edge-level DP in the same context?\n- Why is fine-tuning pretrained text encoders chosen as the application? In the task of relational learning, or more specifically, link prediction, GNNs are often directly applied. Is this method suitable for such cases as well?\n- In scenarios like online social platform recommendations, where the number of high-degree nodes can be very large, with degrees reaching into the hundreds or thousands, how does degree capping influence performance in such cases?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths \n- The paper proposes adaptive gradient clipping and a new amplification analysis tailored for relational learning, offering node-level differential privacy guarantees.\n- The proposed method achieves strong privacy–utility trade-offs across various datasets.\n- This paper is clearly written, and the tables and charts are easy to understand.\n\nWeaknesses\n- The work feels somewhat related to the well-established problem of differentially private link prediction. A discussion highlighting the differences and connections with existing literature on DP link prediction would help clarify the unique contribution of this approach.\n- The compared baselines (standard clipping) are limited. Adapting additional recent baselines for comparison would provide a more comprehensive evaluation of the efficacy of the proposed method.", "was_revised": true, "final_justification": "The authors have clarified the novelty and positioning of their work relative to DP link prediction, and addressed questions regarding applicability and degree capping. As the authors note, the set of available empirical baselines meeting the rigorous entity-level privacy definition is limited. Overall, most concerns have been resolved, and the work makes a meaningful contribution, with the score reflecting its novelty and soundness.", "rebuttal": "We thank the reviewer m1UV for their construcive comments. Here is our response.\n\n> **W1**: “The work feels somewhat related to the well-established problem of differentially private link prediction. A discussion highlighting the differences and connections with existing literature on DP link prediction would help clarify the unique contribution of this approach.”\n\nWe thank the reviewer for this constructive suggestion. While link prediction can be considered a special case of relational learning involving binary relations, differentially private link prediction remains an **emerging and relatively underexplored** area. Some recent works have begun to address this topic, such as [1] which focuses on protecting a specific subset of node pairs, and [2] which provides link-level privacy guarantees.\n\nIn contrast to these existing approaches, our work offers several key distinctions that highlight its unique contribution:\n\n- Most notably, neither [1] nor [2] addresses entity-level (i.e., node-level) privacy guarantees, which is the core focus of our framework.\n- [2] adopts a binary classification objective function with uniformly sampled positive and negative edges. Our work, however, considers a more general contrastive loss, which involves a more complex process of sampling and grouping negative instances per positive instance.\n- In terms of application, [2] trains graph neural networks for link prediction. Our work, by contrast, focuses on fine-tuning large language models on one relational dataset and then inferring new relations on a different dataset.\n\nWe will include a discussion of these related works in the final version of the manuscript.\n\n\n> **W2**: “The compared baselines (standard clipping) are limited. Adapting additional recent baselines for comparison would provide a more comprehensive evaluation of the efficacy of the proposed method.”\n\nWe appreciate the reviewer's suggestion. To the best of our knowledge, our approach is the first to provide a formal entity-level privacy guarantee for relational learning. Adapting recent other baselines (which is not for entity-DP relational learning) to meet the rigorous entity-level privacy definition in relational learning is highly nontrivial. Therefore, we focused our comparison against the standard clipping approach adapted to our relational learning setting, which serves as a relevant baseline within this novel problem formulation.\n\n> **Q1**: “This work focuses on node-level DP. Does it offer any insights or potential solutions for achieving edge-level DP in the same context”\n\nWhile our primary focus is on entity-level (node-level) differential privacy, it can indeed be adapted to provide edge-level DP guarantees within the same context. Entity-level DP considers two neighboring graphs that differ by a single node and all its associated edges. In contrast, edge-level DP considers neighboring graphs that differ by only a single edge. Precisely, the edge-level privacy guarantee of Algorithm 3 can be accordingly provided by Theorem 4.1., with maximal node degree $K$ replaced by 1 (reflecting only one edge can be removed/inserted) and $k_{neg}$ replaced by $0$ (reflecting no nodes is removed/inserted, so no privacy leakage from negative edges).\n\n> **Q2-1**: “Why is fine-tuning pretrained text encoders chosen as the application?”\n\nBroadly, our framework is able to ensure entity-level privacy of relational learning for both fine-tuning pretrained models or training a model from scratch. We chose to focus on fine-tuning pre-trained text encoders because this approach closely aligns with current real-world applications of relational learning. In practice, pre-trained or foundation models are widely utilized for relational data of specific modalities, for example, large language models for textual data in recommendation systems [3], finance [4,6], and healthcare [5], or vision-language models for image data [7].\n\n\n\n\n> **Q2-2**: “In the task of relational learning, or more specifically, link prediction, GNNs are often applied. Is this method suitable for such cases as well?”\n\nWhile our current method is broadly applicable to relational learning, integrating it directly with GNN architectures introduces additional privacy risks. This is because GNNs involve node feature aggregation via the graph structure. Several existing works have investigated privacy guarantees for GNNs in the context of node classification [8, 9]. Exploring entity-level private relational learning specifically in conjunction with GNN architectures remains a promising direction for future research.\n\n\n> **Q3**: “how does high degree capping influence performance in such cases?”\n\nDegree capping is a tunable hyperparameter that influences the trade-off between utility and privacy. In Figure 3 (middle), we evaluate model utility under varying degree caps while keeping the privacy budget fixed. The results show that utility remains quite robust across different levels of degree capping.\n\n[1] De, Abir, and Soumen Chakrabarti. \"Differentially private link prediction with protected connections.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 1. 2021.\n\n[2] Ran, Xun, et al. \"Differentially private graph neural networks for link prediction.\" 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024.\n\n[3] Zhao, Zihuai, et al. \"Recommender systems in the era of large language models (llms).\" IEEE Transactions on Knowledge and Data Engineering 36.11 (2024): 6889-6907.\n\n[4] Peng, Bo, et al. \"eCeLLM: Generalizing Large Language Models for E-commerce from Large-scale, High-quality Instruction Data.\" Forty-first International Conference on Machine Learning.\n\n[5] Gao, Y., et al. \"Leveraging a medical knowledge graph into large language models for diagnosis prediction. arXiv. 2023.\" arXiv preprint arXiv:2308.14321.\n\n[6] Ouyang, Kun, et al. \"Modal-adaptive knowledge-enhanced graph-based financial prediction from monetary policy conference calls with LLM.\" arXiv preprint arXiv:2403.16055 (2024).\n\n[7] Li, Xin, et al. \"Graphadapter: Tuning vision-language models with dual knowledge graph.\" Advances in Neural Information Processing Systems 36 (2023): 13448-13466.\n\n[8] Daigavane, Ameya, et al. \"Node-level differentially private graph neural networks.\" arXiv preprint arXiv:2111.15521 (2021).\n\n[9] Sajadmanesh, Sina, et al. \"{GAP}: Differentially private graph neural networks with aggregation perturbation.\" 32nd USENIX Security Symposium (USENIX Security 23). 2023."}, {"review_id": "DnoxqBEugk", "reviewer": "Reviewer_LSG2", "summary": "A fundamental problem that limits the DP-SGD in relational learning is that DP-SGD considers the i.i.d assumption of samples when clipping the gradient and mini-batching. In relational learning, the samples, i.e., the nodes and edges, are dependent. To mitigate this problem, the authors design a new DP-SGD with a specifically designed gradient-clipping strategy and mini-batch construction strategy in this paper.", "questions": "1. I think the adaptive clipping scheme relies on per-entity frequency, but the paper does not analyse how the joint distribution of frequencies affects the optimal clip threshold once entities number in the millions (e.g., social graphs). A worst-case entity that appears in most relations could still dominate sensitivity—even with adaptive scaling—forcing very large noise that may erase the reported utility gains. It's might be too complex to present in a single paper, but I'm curious about how the authors think about this problem.\n\n2. Entity-level DP is stronger but costlier than edge-level DP. I'm curious about how much additional noise is paid relative to edge-level privacy.", "limitations": "No.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. This paper has good presentation quality.\n\n2. The analysis of the problem and the intuition of new methods is comprehensive and makes sense to me.\n\n3. The problem studied by the paper is vital for protecting training data privacy in relational learning.\n\n\nWeakness:\n\n1. I think the authors should publish their code to increase the reproducibility.\n\n2. Some questions are not answered, please check the questions part.", "was_revised": true, "final_justification": "I think the responses have addressed my questions. And I think the contributions could be vital for related problems in privacy. Therefore, I think this paper should be accepted.", "rebuttal": "We thank the reviewer LSG2 for their positive feedback. Here is our response.\n\n> **W1**: “The authors should publish their code to increase the reproducibility”\n\nThank you for the suggestion. We provided code to reproduce all results in the supplementary materials. We will make the code publicly available after the review process \n\n> **Q1**: “I think the adaptive clipping scheme relies on per-entity frequency, but the paper does not analyse how the joint distribution of frequencies affects the optimal clip threshold once entities number in the millions (e.g., social graphs). A worst-case entity that appears in most relations could still dominate sensitivity—even with adaptive scaling—forcing very large noise that may erase the reported utility gains.\"\n\nIt is true that in the worst case, a hub node with a very high degree can appear in all sampled relations in a mini-batch. In our experiments, we mitigate this issue by capping node degrees below a fixed threshold (Line 285-288). We also investigate how this degree capping impacts utility under a fixed privacy budget (Figure 3, middle panel). This may not be the optimal strategy for handling high-degree nodes, and we agree that it is an important direction for future work.\n\n> **Q2**: “Entity-level DP is stronger but costlier than edge-level DP. I'm curious about how much additional noise is paid relative to edge-level privacy.”\n\nThat is a good question. We can actually calculate the privacy leakage for edge-level privacy using our framework. Let us denote the standard privacy amplification bound (e.g., Poisson sampling) of sampling rate $\\gamma$ by $\\epsilon(\\gamma)$ (see the bound from Theorem 4 of [1]). We can show that the $\\epsilon_{edge}$ parameter of edge-level privacy is equal to $\\epsilon(\\gamma)$ ($\\gamma$ is the sampling rate of positive edge in our context), because only one \"row\" of positive edge is affected. For a very coarse approximation and comparison here, the $\\epsilon_{entity}$ parameter of entity-level privacy (equation (3)) can be roughly approximated by $\\epsilon(\\Gamma)$ with an “effective” sampling rate $\\Gamma:=(K+d\\*k_\\{neg\\})*\\gamma$, where $K$ is the maximal node degree, $d$ is the average node degree and $k_{neg}$ is the number of negative sampling per positive. This implies that, compared to edge-level privacy, entity-level privacy incurs an extra factor of $K+d\\*k_{neg}$ in its effective sampling rate, which depends on node degree.\n\n[1] Mironov, Ilya, Kunal Talwar, and Li Zhang. \"R\\'enyi differential privacy of the sampled gaussian mechanism.\" arXiv preprint arXiv:1908.10530 (2019)."}]

Author rebuttal:

Meta-review: The manuscript aims to adapt differentially private stochastic gradient descent (DP-SGD) to relational learning tasks where each node corresponds to a entity/user and preserve entity-level/node-level DP in low privacy settings. The theoretical and experimental results are appreciated [nM78, m1UV, LSG2] except rather high privacy parameters [xnXK] ](eps >= 2 implies that the model would be over 7x more/less likely in case of the presence/absence of a data point). While more baselines were desired [nM78, m1UV], the studied problem was considered very relevant [nM78, xnXK].
Decision: Accept (poster)