Privately Learning from Graphs with Applications in Fine-tuning Large Language Models
Authors: Haoteng Yin
Rongzhe Wei
Eli Chien
Pan Li
Venue: COLM 2025 (2025)
Keywords: differential privacy
relational learning
private learning
language models
fine-tuning
TL;DR: We present a privacy-preserving framework for relational learning, showcased by fine-tuning LLMs on sensitive graphs with differential privacy.

Abstract: Graphs offer unique insights into relationships between entities, complementing data modalities like text and images and enabling AI models to extend their capabilities beyond traditional tasks. However, learning from graphs often involves handling sensitive relations, raising significant privacy concerns. Existing privacy-preserving methods, such as DP-SGD, rely on gradient decoupling assumptions and are incompatible with relational learning due to the inherent dependencies between training samples. To address this challenge, we propose a privacy-preserving pipeline for relational learning that decouples dependencies in sampled relations during training, ensuring differential privacy through a tailored application of DP-SGD. We apply this approach to fine-tune large language models (LLMs), such as BERT and Llama2, on sensitive graph data while addressing the associated computational complexities. Our method is evaluated on four real-world text-attributed graphs, demonstrating significant improvements in relational learning tasks while maintaining robust privacy guarantees. Additionally, we analyze the trade-offs between privacy, utility, and computational efficiency, offering insights into the practical deployment of our approach for privacy-preserving relational learning. Code is available at https://github.com/Graph-COM/PvGaLM.

Published as a conference paper at COLM 2025
Privately Learning from Graphs with Applications in Fine- tuning Large Language Models
Haoteng Yin
Rongzhe Wei, Eli Chien & Pan Li Georgia Institute of Technology {rongzhe wei, icciinc,,nnn paniiin @ggtech..
Purdue University yinht@acm. org
Abstract
Graphs offer unique insights into relationships between entities, comple- menting data modalities like text and images and enabling Al models to extend their capabilities beyond traditional tasks. However, learning from graphs often involves handling sensitive relations, raising significant pri- vacy concerns. Existing sevvacy-preeevvngg methods, such as DP-SGD, rely on gradient decoupling assumptions and are incompatible with relational learning due to the inherent dependencies between training samples. To address this challenge, we propose privacy- ppreeryii pipeline for rela- tional learning that decouples dependencies in sampled relations during training, ensuring differential privacy through tailored application of DP- SGD. We apply this approach to fine-tune large language models (LLMs), such as BERT and Llama2, on sensitive graph data while addressing the associated computational complexities. Our method is evaluated on four real-world text-attributed graphs, demonstrating significant improvements in relational learning tasks while maintaining robust privacy guarantees. Additionally, we analyze the trade-offs between privacy, utility, and com- putational efficiency, offering insights into the practical deployment of our approach for privacy-preserrve relational learning. Code is available at https://gi thub. COMP////CaCC
1 Introduction
Graph data, commonly used to represent relationships between entities, are widely em- ployed to model complex systems in the real world (Leskovec et al., 2007; Kwak et al., 2010; Shamsi al., 2022; Madani et al., 2022). Recently, the relationships captured by graph structures have been used to enhance foundation models pretrained on other modalities (e.g., text and images) with complementary information, which enables these models to more effectively handle multi-entity tasks of emerging AI applications (Brown et al., 2020; Dosovitskiy et al., 2021; Zhang et al., 2024a; Madan et al., 2024). For instance, models trained on product descriptions or pictures may not fully capture the relationships revealed by user behaviors, such as co-purchases or co-viewings. Incorporating relational information can allow Al models to better meet users' needs (e.g,, in product recommendations) Models pretrained on text or images and subsequently fine-tuned with relational information from graphs have recently found applications in various domains (Ling et al., 2023), including healthcare (Wu et al., 2021; Zhang et al., 2022; Gao et al., 2023), finance (Ouyang et al., 2024), and computer vision (Li et al., 2023a). However, the relationships involved in these applications often contain sensitive information, such as matient-hospita visits for clinical diagnosis (Luu& & Uddin, 2023), financial transactions for fraud detection (Kurshan & Shen, 2020), and social connections for recommendations (Zheng et al., 2022). This raises critical concerns about how to protect the privacy of relational data when exposed to Al models, motivating this research.
Differential Privacy (DP) (Dwork, 2006; Dwork et al., 2014) is widely considered the gold standard for measuring the privacy guarantees of data-processing algorithms (Xu et al., 2021; Pan et al., 2024). Current DP methods for model training, such as DP-SGD (Song et al., 2013; Abadi et al., 2016; Ponomareva et al., 2023), are primarily designed for tasks

---

Published as a conference paper at COLM 2025
other than relational learning. DP-SGD, in particular, operates under the assumption that the gradient in each training step can be decoupled with respect to individual training samples that require privacy protection. Under this assumption, DP-SGD controls the norm of the gradient induced by each sample, obfuscates it by adding Gaussian noise, and thus ensures privacy guarantee. However, relational learning on graphs introduces unique challenges because each loss term typically involves multiple relationships (e.g., observed and unobserved relations from the graph), and each relationship involves multiple entities. Consequently, the gradient in relational learning cannot be decomposed into specific privacy-preserver samples, which violates the per-sample decoupling assumption, rendering DP-SGD not directly applicable.
training of graph neural networks (GNNs) (Daigavane et al., 2021; Olatunji et al., 2023; Sajadmanesh & Gatica-Perez, 2021; Mueller et al., 2022; Sajadmanesh et al., 2023; Sajadmanesh & Gatica-Perez, 2024; Chien et al., 2024) do not address this issue, though they also work with relational data. These works are mainly designed for training with node classification labels, where the loss term is decomposable to specific nodes given the representations of these nodes output by GNNs. Their methods, which obfuscate the message-passing process to prevent privacy leakage during GNN encoding, do not mitigale privacy risks arising from relational learning, where the loss term cannot be decomposed on the supervision side. We further discuss the critical gap of current DP-GNNs in solving the problem of differentially private relational learning in Appx. A.1.
Recent studies on privacy-preserre
This study aims to introduce a privacy-preserving pipeline to address the gap in relational learning, where each loss term typically involves an observed relation paired with one or more unobserved relations for contrast. Common practice often couples the sampling of observed and unobserved relations, where removing or adding an observed relation may impact the gradients of multiple loss terms within the sampled batch, causing sensitive relational information leakage. Our key insight to decouple the sampling process for observed and unobserved relations. By doing so, we ensure that removing or adding an observed relation affects at most one loss term, thereby limiting the sensitivity of data perturbation in relational learning and making it theoretically compatible with the privacy accounting of the DP-SGD framework.
As application, we apply this privacy-preserving pipeline to fine-tune pretrained models using graph data, choosing LLMs as a proof of concept. Modern privacy libraries like Opacus (Yousefpour et al., 2021), TensorFlow Privacy (McMahan et al., 2018), and JAX Privacy (Balle et al., 2022) support clipping per-sample gradients to apply DP-SGD, but they are designed for each sample with a single input. The per-sample gradient computing relies on caching intermediate results of backpropagation, which are tracked through individual input tokens for sequence models (LLMs included) and leading to common inefficiencies. Relational learning introduces another dimension to the problem: Each loss term typically involves K entities, and each entity with textual attributes contains M tokens. Naively computing per-sample gradients requires keeping O(KM) gradient copies in memory per loss term, where modern GPUs easily run into out-of-memory issues for large models at moderate batch sizes. To eliminate the instantiation of O (KM) gradients, we propose to directly compute per-loss-term gradients by utilizing the low-rank structure of gradients through individual tokens. This approach alleviates memory constraints for models with billions of parameters, enabling efficient private fine-tuning on relational data with large batch sizes, which are empirically preferred to enhance privacy preservation (Li et al., 2021; Anil et al., 2022; Räisä et al., 2024).
computiig
We evaluate the proposed pipeline by testing whether target models can learn from private domains rich in relational data and generalize to new domains lacking such information to infer relationships between entities. Using real-world relational data from four text- attributed graphs, we fine-tune BERT (Devlin et al., 2019) and Llama2 (Touvron et al., 2023) at various model sizes (110M, 340M, 7B) under different levels of DP (e S 10) to stimulate two popular use cases that require data privacy: Cross-category co-purchase recommendation and Cross-region model deployment. Our results demonstrate that LLMs can effectively learn from relational data to address relational learning tasks, even with DP guarantees. The privacy risks of these fine-tuned models are empirically examined by conducting membership inference attacks. Additionally, we investigate the trade-offs
2

---

Published as a conference paper at COLM 2025
between utility, privacy, and computational efficiency in LLM-based relational learning, extending existing research of privacy-presevvngg learning with LLMs on standard (non- relational) text data (Li et al., 2021). These findings offer valuable insights for the practical relational learning scenarios.
deployment of LLMs in
2 Preliminaries: Notations and Standard Learning via DP-SGD
Graph (V,E, consists of a relation set & that describes the relationship between entities in V = [N]. Each entity v E V is associated with an attribute X, of text, images, or other data modalities.
(e, DDffferrrett Privacy. randomized mechanism M satisfies an (e.,))differentin) privacy if for any adjacent datasets D, D' that differ in one sample, and any output set C Range(MM, (PM E S) < (M(M(D)) E S) + where 6, > 0 measure the privacy loss and smaller values imply stronger privacy guarantees. The notion of adjacent datasets can be generalized to relational data. Two relation sets E, are considered adjacent if one can be obtained from the other by adding or removing a relation. The overall entity set V is constant across adjacent relation sets. We provide the formal definition of the DP guarantees provided by this work in Sec. 3.1.
Standard DP Learning Paradigm. Consider training neural network using mini-batch B of b samples. The model parameters @ is updated iteratively as (++1 = O 17/ (B), where 1 is the learning rate, and gr (B) de; //0/; is the gradient of the loss l on B w.r. the parameters O at step f. Adding or removing one sample from may change g (B), causing privacy leakage that can be measured by the sensitivity A2 maxg,8 (lg(5) g g(BB)) 1.
where B' and B are different in one sample (B\BB') (B") (B"
DP-SGD (Song et al., 2013; Abadi et al., 2016) (see Alg. 1) was proposed to achieve data privacy for training deep learning models. It first clips per-sample gradients to control the sensitivity and then adds Gaussian noise to obfuscate the potential change as g(B) = [Ener
(00, where g(x;) is the parameter gradient of the loss on sample X;, and Cl g/ max(1, / for some constant C > 0. At each step of parameter update, clipping per-sample gradients limits the sensitivity to at most C, and the Gaussian noise with standard deviation oC is added to achieve DP based on the Gaussian mechanism (Dwork et al., 2014). To obtain the DP guarantee for the entire training procedure, the composition theorem (Balle & Wang, 2018) is used to account for the total privacy loss over steps. Mini-batch sampling also allows for some privacy amplification, for which interested readers may check relevant works for more details (Balle et al., 2018; Wang et al., 2019).
3 Methodology
In this section, we first introduce the technical difficulty of applying standard DP-SGD when training models in relational learning. Then, we propose a pipeline that addresses this difficulty and can provably achieve differential privacy in learning from relational data. Lastly, we address the computing challenge induced by the control of gradient sensitivity involving multiple relations and entities, especially when applying the proposed pipeline to sequence models on text-attributed graphs.
Enhance Models with Relational Data. Relationships provide complementary informa- tion to models trained on a specific modality, enabling them to more effectively handle tasks involving multiple entities. Suppose the representation of each entity u is obtained from model parameterized by O encoding its attribute, i.e., h, (x,). A common approach of relational learning is to use relationships between entities to refine their representations (Ya- sunaga et al., 2022b; Duan et al., 2023; Xie et al., 2023). This is typically achieved via training based on a loss & that can be generally written as the following form (Hadsell et al., 2006; Schroff et al., 2015; Song et al., 2016; Sohn, 2016; Ying et al., 2018; Oord et al., 2018). Given tuple F,, consisting of an observed (positive) relation ef E m and several unobserved
3

---

Published as a conference paper at COLM 2025
(negative) relations { ( j==1 where e; & E, the loss is denoted as E()) For mini-batch B of tuples, the loss sum for B is computed as
(o( = E ((O)F,) = E EJEB
e(0) (e) (e.......
(1)
EJEB
For convenience, let Ze = TT(h,, h. denote the joint representations of entities in each
relationship. One popular choice of l is the InfoNCE loss (Oord et al., 2018): {(0; E;)
- lnn (ex(((Z,,) Lrer, exp(z))). Another choice is the pairwise Hinge loss { Ej) =
2+ // |+, which is commonly used for learning from complex multi-relations in
knowledge graphs (Bordes et al., 2013; Wang et al., 2014; Yang et al., 2015; Lin et al., 2015).
Here, y represents the margin, and Ze also encodes the representation of the relationship besides the entities. Note that our method for relational learning can potentially be extended to the case where each relationship contains more than two entities, such as network motifs (Milo et al., 2002; Benson et al., 2016) and hyperedges (Berge, 1984), although the later discussion focuses on pairwise relationships.
3.1 Challenges in Privately Learning Relations
For relational learning, the information subjected to be protected is the existence of relation in the relation set &, formally defined as follows.
DP for Relational Data. An (e, 0DDDP algorithm for relational data ensures that the output obtained from randomized mechanism M : X + y for any adjacent relation sets E,E' X and measurable sets C y satisfy: (E) E Y) < ((((M(E)) E Y) 8. Achieving DP for relational data limits the ability of the best possible adversary to uncover any specific relationship between entities used for training from the model parameters. When the set of relations is defined by plain graph, the above concept reduces to edge- level DP, which is widely used in privacy-preser preserving graph algorithms (Hay et al., 2009).
Recall that DP-SGD relies on clipping per-sample gradients to control the sensitivity of the gradient update from a mini-batch. In relational learning, the gradient sum g(B) of mini-batch B is given by
(Be(B) de
ae(O; E,)
az,t
de(O) E,) dz.
dz
8(
(())) =
Σ FEEB
(2)
dzzt
a
a0
FEB
Positive Relation
Negative Relations
The challenge comes from the fact that prac- tical sampling of negative relations is usually coupled with positive relations in the same mini-batch. As result, removing or adding positive relation e E & will not only change the tuple E, that contains e but also potentially affect other tuples in the batch B. The impact on multiple terms in the sum of gradients in Eq. (2) prohibits us from properly controlling the sensitivity of g(B) ))) by clipping each indi- vidual gradient g(E,). Specifically, In-batch Negative is commonly used to obtain nega- tive relations for training large models, due to its simplicity and memory efficiency (for the privacy concerns of other negative sam- pling methods, see Appx. A.2) (Chen et al., 2020; You et al., 2020; Gao et al., 2021; Radford et al., 2021). Specifically, given a positive re- lation et, In-batch Negative implicitly samples negatives by pairing one end of ex with any
Relation
Decoupled Sampling
Fastive
Negative
[t.ee).a all (arg))
(o.n), (e. (..aa)
(Auus)) Ou. s)) In. Aff
(1ud) (o 9), (ey)) (n-s))
Samelled Mal- lutad S
Entiy Set
Wreepaheee
Agpingation
Differentially Private Relational Learning
hoby
2u/B: 69
Privdiiod
Figure 1: Challenges in differentially private relational learning: Each loss term typically in- volves coupled relations through negative sam- pling mini-batch, where perturbing one rela- tion may affect multiple loss terms the same batch (e.g., removing relation (u, w) from the set E may affect all tuples in B). Decoupled sam- pling (e-g,, pairing negatives from the set V) lim- its such perfurbation affect at most one relation tuple E, in mini-batch.
4

---

Published as a conference paper at COLM 2025
entity in other positive relations sampled in the same batch negative relations (see the upper right of Fig. 1). This practice can lead to the worst case with high sensitivity that perturbing one positive relation impacts the whole mini-batch: If a positive relation ej sampled in the batch B is removed, the loss of every other tuple Ej B will be affected as the entities in e may be used to form negative relations in E,.
3.2 Privacy-preserving Relational Learning
To address the above challenge, we propose to decouple the sampling of negative relations from the set of positive relations. Specifically, the sampling method to form negative relations should not rely on accessing the relation set & nor leverage sampled positive relations in the same batch. One direct way is to randomly pair one end of the positive relation e/ with k entities (Vig....., Vit) sampled uniformly at random from the whole entity set V as negatives {er, 1/=1 for each tuple E,, illustrated in the upper middle of Fig. 1. Now, removing adding positive relation will change most one tuple E; in mini-batch B. Therefore, by clipping the norm of the gradient of each tuple g(E) (E)), we can bound the sensitivity of the gradient sum g(B), independent of the batch size: The k-many negative relations {e,, 1 also contribute to the gradient computation of g(B), but in this new strategy, they only depend on the positive relation e/" in the same tuple and their effect is bounded through clipping g( E;). Overall, this sampling method is compatible with DP-SGD: Each aggregated gradient g( [E)) in mini-batch is clipped and noised as
g(B) = 5
Clip (B(E)) ( EEEB
(3)
With decoupled negative sampling and gradient obfuscation via Eq. (3), the privacy analysis of standard DP-SGD holds for relational learning with the loss of Eq. (1), since each relation & influences the gradient sum most C. The full pipeline to achieve (e, for relational learning is summarized in Alg. 3, Appx. C.
Another challenge in applying DP-SGD is computing the per-sample gradient, which requires correctly tracking the norm of the gradient for each training sample. This is common bottleneck in private learning and amplified in relational learning tasks. Modern privacy libraries such as Opacus (Yousefpour et al., 2021) support tracking the parameter gradient through a training sample when one sample takes only one data point. In the case of relational learning, relation tuple contains multiple entities, which makes these libraries not directly applicable. naive implementation to hook the parameter gradient
through each entity g(ule', , E,) O(L,) dz Sh, during a backward pass. This means oz, Sh, do
that the gradient gEE; of model parameters through one tuple needs to be calculated via all entities in this tuple, i.e., gEE;) = Ee'E; Euce g(ule', Et). Computing and caching gradients g(ule',F,, F2) through each entity incurs significant overhead for tuples with large sizes k. This issue becomes more pressing for training large models. Next, we aim to address this unique computational problem in private relational learning.
3.3 Efficient Gradient Clipping in Relational Learning
The lack of support for tracking the tuple-level gradient g(E) and tuple size k introduced by relational learning constitutes the primary bottleneck for applying DP-SGD. The situation worsens when the relational data for training contains textual attributes (Jin et al., 2023a). Specifically, sequence models commonly used in such scenarios (e.g., Transformers (Vaswani et al., 2017)) take multiple tokens as input, where applying DP-SGD requires hooking the parameter gradients through each token prediction. This means that when the proposed
Decoupled negative sampling may treat entity pairs with observed relations as negatives with low probability (similar to in-batch negatives), but no obvious harm to utility is observed in practice (see Table Appx. D).
5

---

Published as a conference paper at COLM 2025
Alg. is applied to privacy-preserving relational learning on LLMs, the parameter gradients through each token m in entity u need to be hooked for privacy computation. This results in an intractable cost of maintaining two cascaded levels of gradient copies in memory. Prior work (Lee & Kifer, 2021; Li et al., 2021) proposed some strategies to address the issue for privately fine-tuning LLMs on standard text data, but we found that these techniques are insufficient for the use cases in relational learning.
Next, we present a tailored approach for efficiently computing the per-tuple gradient 8(E), which leverages the low-rank nature of per-sample gradient (Goodfellow, 2015) and the structure of g(E) in relational learning. We demonstrate this using the linear (or embedding) layer of Transformers, while non-sequential models can be considered as cases where the input does not have token dimension. For a linear layer in Transformers, its weight matrix is W E RPxd, where d, p are the input and output dimensions, respectively. For a relation tuple E, let a E RKxMxd denote the concatenated input, which contains K = 2(k + 1) entities, and each entity is associated with M tokens. Let E RKxMxp be the output, where sijj Wa., corresponds to the j-th token of the i-th entity in the
tuple. Denote the gradient w.r.t. the output S as Tij ar((:E) Then, the gradient of W
ds:j
through Sij can be calculated as Vw s.j l = a((O,))
as..
= =. E RPxd, To obtain the aw
per-tuple gradient w.r.t. i.e., Σ E V Wiss, l, is inefficient to first instantiate rijaffj for each token and then sum them over. A cheaper way is to record the low-rank parts [..... ........ E RKXM and [.... a....... E R for all KM tokens, and accomplish the sum via Ta This strategy can reduce the memory cost from O (KMpd) to (K + d) + pd). Our experiments use Llama2-7B (Touvron et al., 2023), where K E 34 and M = 32 while p d 4096 in attention blocks and p 32000, d = 409 in the embedding block. So, pd >> KM + d) and thus the overall saving based on the above approach is a factor of (KM). In addition, some parameter-efficient fine-tuning techniques such as LoRA (Hu et al., 2022) can be incorporated to further reduce the memory cost to OKM((p + d + 2r) + (p d)r), where is the rank of adjustment AW for parameter W.
4 Experiments
Problem Setting & Datasets. Our experiment design aims to simulate common scenarios of applying relational learning in sensitive domains, where the graph data used enhance target models contain personal or proprietary relations that need to be protected, such as in applications of e-commerce (Peng et al., 2024), finance (Wu et al., 2023; Ouyang et al., 2022), and healthcare (Gao et al., 2023). We consider two specific use cases: Cross-category recommendation When launching new product lines, RecSys models often face the problem of lacking historical data for prediction (e.g., co-purchase), which can be alleviated by utilizing user purchase history of complementary categories. Sensitive user behaviors contained in these co-purchase relations should be protected. Cross-regional model deployment Financial institutions operate in multiple regions, and their service models (e-g., fraud detection) are normally trained on transaction data collected from major markets and then deployed to multiple regions after fine-tuning. Such practices must comply with data export and protection regulations.
Two publicly available real-world text-attributed graphs with millions of entities and re- lationships are selected simulate the two scenarios above: the e-commerce network from Amazon (AMAZ) (McAuley et al., 2015) and the academic network from Microsoft Academic Graph (MAG) (Sinha al., 2015). In the AMAZ dataset, each entity is shopping item, and the relation between them indicates that they were co-purchased by customers. is split into two domains based on the item category: clothing and sports. the MAG dataset, each entity is a research paper, and the relation between them reflects one citing the other. It is split into two domains based on the region of the main authors: USA and China. In total, four dppaai-specific subgraphs (see Table 8, Appx. D) are used for relational learning, where the target model is evaluated on the corresponding test domain, such as trained on co-purchased relations from AMAZ-Cloth and tested on AMAZ-Sports.
6

---

Published as a conference paper at COLM 2025
MAG-USA
MAG-CHI
AMAZ-Cloth
AMAZ-Sports
Privacy
Target Model
PRECØ1
MRR
PRECØ1
MRR
PREC01
MRR
PRECØ1
MRR
BERTbase
4.41
9.94
6.48
12.69
14,90
22.41
8.36
14.04
base model
BaRT
2,00
5.48
2.71
6.39
5.72
10.11
3.78
7.37
zero-shot
SciBERT
17.12
13.89
23,96
LinkBERT.larg
1.09
4,U1
1.46
4.75
4.01
8.60
2.06
5.37
Llama2-7B
4.24
8.68
5.21
9.71
19:45
27.41
6.13
10.11
BERT
28.07
39.11
41.93
53.91
36.13
47.07
29.84
39.61
é 00
BaRTlarge
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
basT
3.28
8,70
5.10
11.47
19.97
29.76
8.03
13.73
<= 10 (RR)
BERT.arrge
5.67
11.75
8.65
15.43
22.81
32.31
7.36
12.15
Llama2-7B
13.64
22.33
9.92
16.67
30.39
41.48
19.63
66
basT
23.29
33,98
35.64
47.74
32,63
43.17
26.66
36.76
é 10 (Ours)
BERT.arge
22.71
33.76
35.18
47.03
31.20
41.28
28.18
38.68
Llama2-78
24.17
37.53
34.58
48.76
40.16
51.25
29.54
39,90
BERT
22.08
32,69
31.42
43.54
33.24
43.67
26.82
36.90
c 4 (Ours)
laRg.
21.78
32.60
34.84
46.62
29.73
39.63
27.63
38.06
Llama2-7B
22.55
35.47
32.50
46.68
39.67
51.09
29.25
39.35
Table 1: Results on zero-shot relation prediction with privacy-preserving relationn learning.
We conduct a comprehensive set of empirical studies with the objective of addressing two key research questions: RQ1 Can the target model learn relational knowledge from the training graph with privacy preservation and generalize to relational learning tasks on new test domains? RQ2 How does negative sampling size impact the results in relational learning? What about the choice of other hyperparameters, such the batch size, learning rate, and privacy hyperparameters 0, C? Does it follow the same rules of the private non-relational setting (Li et al., 2021)?
Tasks & Metrics. Privately fine-tuned models are deployed to new test domains under the settings of zero-shot and 16-shot for relation prediction, and 8-shot for entity classification. We use ranking metrics of top@1 precision (PREC@1) and mean reciprocal rank (MRR) to evaluate each model on in-batch negative samples with batch size of 256 (same Jin et al. (2023b)) for relation prediction, while Macro-F1 and Micro-F1 for entity classification.
Implementation Details. The pretrained models are fine-tuned under the supervision of relational information with the InfoNCE loss and optimized by DP-Adam through our proposed pipeline (see Alg. 3). The privacy loss is tracked through PRV accounting (Gopi et al, 2021). Following prior work on private fine-tuning of LLMs (Li et al., 2021; Yu et al., 2022), we consider privacy levels (4, 10) and å Perain for training set of size |Erain Hyperparameters are tuned under given privacy parameters. See Appx. D for other details.
Baselines. To the best of our knowledge, our approach is the first for relational learning with differential privacy. DP-GNNs are excluded from baselines due to their insufficiency in properly preserving privacy in relational learning. To compare with feasible privacy- preserving techniques that satisfy DP for relational data, we apply the standard randomized response (RR) baseline to the relation set and then perform model fine-tuning on the processed relation set that achieves e-DP (Epasto et al., 2022). Given an entity for each pair v), V, v * ut we apply the randomized response mechanism (Dwork et al., 2014). With probability p (1 + exp(c)), the relation label of (u, v) is flipped; otherwise, the original label is kept. Note that this baseline requires ((N2) time complexity and drastically increases the number of relations for small values e, which severely limits its applicability.
4.1 Evaluation of Privately Fine-tuned Models (RQ1)
In this section, we study the effectiveness of the proposed pipeline by evaluating privately fine-tuned models on new test domains for relation prediction and entity classification. The scale of privacy noise and the exact privacy loss on relational data used for training each model are reported in Table 11, Appx. E. The privacy risks fine-tuned models are empirically examined via membership inference attacks
7

---

Published as a conference paper at COLM 2025
MAG-USA
MAG-CHN
AMAZ-Cloth
AMAZ-Sporn -pootts
Privacy
Model
PREC&1
MRR
PREC#1
MRR
PREC&1 MRR
PREC#1
MRR
baRT
10.24
18.94
17.10
27.84
20.42
29.74
14.70
23.46
base model few-shot
lagge
6.57
13.88
9.61
17.75
19.57
28.69
11.23
17.80
SciBERT
22.27
34.24
32.42
46.10
Lane
21.76
31.93
35.09
47.80
13.41
19.24
23.21
30.95
Llama2-7B
6.21
12.26
6.29
11.51
20.25
28.42
7.17
11.79
BERT
27.28
38.61
39.15
51.28
33.45
44.42
29.57
39.71
CO
lagge
26.19
37.69
37.91
49.93
34.60
45.
29.85
40.79
Llama2-7B
35.45
49.30
58.84
41.42
52.59
31.92
44.83
BERT
24.56
35.55
33.62
45.72
33.40
44.23
28.64
38.34
(Ours)
laRge
23.09
34.21
37.23
48.65
30.39
40.78
27.80
37.87
Llama2-7B
22.88
35.94
32.07
46.22
39.94
51.10
29.78
40.27
Table 2: Results on 16-shot relation prediction with privacy-preserving relational learning.
MAG-USA
MAG-CHN
AMAZ-Cloll
AMAZ-Sports
Privacy
Model
Macro-Fl
Micro-F1
Macro-F1 Micro-F]
Macro-F1
MicroFF1
Macro-F1
Micro-F]
BERTbase
2.40
3.06
2.08
3.18
9.75
16.31
7.26
8.39
base model few-shot
laRe
SciBERT
4.70
10.01
5.14
6.51
LinkBERT
0.81
1.32
1.45
1.77
10:45
36.06
0.16
10.90
Llama2-7B
32.26
49.34
BERTbase
2,02
2,88
2.23
17.50
19.81
O0
BERTTaagee
6.88
11.57
4.90
5.32
26.31
35.59
23.53
24.42
Llama2-7B
14.97
18.77
11.52
10.85
32.94
30.65
37.53
63.15
BERTbase
17.87
c (Ours)
BERTlarge
6.31
11.16
3.07
6.45
16.77
22.98
21.71
22.67
Llama2-7B
16.55
18.59
13.56
13.29
35,43
54.85
44.74
50.47
Table 3: Results on 8-shot entity classification with privacy-preserving relational learning.
Relation Prediction. This task aims to estimate the likelihood of forming a relationship between two entities with specific semantics. Under the zero-shot setting, all pretrained language models are privately fine-tuned on relations from the training graph and then are directly deployed on the test domain for inference. This is often faced in cold-start recommendation problems, where the test domain lacks relational information. Results of zero-shot relation prediction in Table show that using co-purchase/ citation relations from training graphs to fine-tune language models through our approach can improve their base models' performance on new test domains under DP guarantee e = (4, 10). There is only modest performance drop compared to the non-private fine-tuned baselines (c = co, oracle), which much smaller than all results from training on relational sets processed by the randomized response mechanism (not computationally feasible for 4). This observation validates the effectiveness of generalizable relational patterns and knowledge without compromising individual privacy. Among different types of target models, decoder-only models tend to perform worse than encoder models in embedding text (Li & Li, 2024; BehnamGhader al., 2024), reflected in the performance disparity between their base models in Table 1. Through (private) relational learning, Llama2-7B can generate rich contextual representations to predict relations and outperform the widely used BERT-based encoder.
relational learning in light of capturing
Next, we consider the few--hot setting used for cases like cross-regional model deployment, which is often limited by resource or data availability. The model obtained above is further fine-tuned using 16 training and 16 validation relations from the test domain. Table 2 shows that privately fine-tuned language models still outperform their base models if few-shot fine-tuning is allowed. In particular, they outperform SciBERT (Beltagy et al., 2019) and LinkBERT (Yasunaga et al., 2022a) on the MAG dataset, both of which are pretrained documents and associated relationships in the scientific domain.
Entity Classification. This task aims to investigate whether injecting relational information helps language models classify entities with textual attributes in adjacent domains. It is motivated by the above observation, where introducing structural knowledge between entities can go beyond contextual semantics and help models refine internal entity represen- tations across domains. We use the language model encoder and attach classifier to
8

---

Published as a conference paper at COLM 2025
MAG-USA
MAG-CIIN
Method
TPR00005 FPR
WSRT p-value
TPR80.05 FPR
WSRT p-value
Non-D>
0.06877
3.14e-82
0.0551
1.39e-88
Ours
10
0.0672
4.36e-54
0.0480
4.72e-25
Ours
0.0600
1.51e-46
0.0469
6.69e-20
Table 4: Attack results against LLamma-7B fine-tuned on training graphs of MAG-USA/CHN, A smaller p-value in the Wilcoxon test shows the difference observed between member and non-member distributions is statistically significant, indicating more leakage.
The Effest of Negelire Samples
The tilsct of busch S 121
2t Tuaeyy ULBly Thedl ofl for Iddetion Proditioo Stostett
Uodea Feetrmmee (HRN)
320
330 bas (dlob-dees e.5.00
Doa Nuthorm seree Foree
10
(900 cau
RE 2000
SERE 21NTE Lave3 GORSS OT LiPe XXII Batc Gripp
63
Figure 2: Effects of negative sample &, batch size b, and noise multiplier o for zero-shot relation prediction with privacy preservation.
take entity embeddings for classification. The parameters of language models are frozen, where only limited examples are used initialize the classifier. The entity classes are coarse-grained category names from AMAZ and MAG networks. 8 labeled training and validation entities of each class are used for training, while thousands of new entities are reserved for testing. Table shows that models fine-tuned privately on relational data generally produce entity embeddings of better quality than those directly generated from base models. In some cases, private models outperform non-private models (c = =o), which can be attributed to the regularization effect of DP-SGD under the setting of limited examples. The performance drop on AMAZ-cloth is due to the potential misalignment between the objective of relation-based fine-tuning and entity classification, which has been observed in the non-private relational learning setting by Xie et al. (2023) and in the private non-relational setting by Li et al. (2021).
Privacy Attacks. We perform the membership inference attacks (MIAs) on relation samples to empirically estimate the privacy risk of models fine-tuned on the training graph. The high computational cost of training multiple copies of shadow models (Shokri et al., 2017) makes it intractable to perform such attacks on LLM-based relational learning, Thus, we consider an unsupervised approach to determine the membership of target relations based a distance-basee
score function (He et al., 2021; Wang & Wang, 2023). We follow similar setting as He et al. (2021), where the adversary has knowledge of the target dataset's entity attributes. The attack relies on the posteriors of entity embeddings obtained from the target model to measure the score between entity pairs and classify the membership of their relations. To evaluate the attack, we use the True-Positive Rate (TPR) low Palst-Pesi Rates (FPR) (Carlini et al., 2022), and p-value of the Wilcoxon signed-rank test (WSRT) (Wilcoxon, 1992) conducted on the score distributions obtained over relations contained in and not in training (Kim et al., 2024). The small p-value suggests that the observed difference between two distributions is statistically significant. From Table 4, we observe that attacks on non-private fine-tuned models (e = co) have a higher success rate than models trained by our approach on both datasets, where the stricter privacy budget of e leads to lower success rate of MIAs both in terms of the TPR at 0,05 FPR and the statistical test. We also include the plotting of score distributions obtained from different target models in Fig. 4, Appx. E.
4.2 Utility, Privacy and Computational Efficiency Trade-offs (RQ2)
In this section, we study the trade-offs between utility, privacy, and computational com- plexity in privacy-preserving relational learning. We first investigate the hyperparameters of negative sampling k, batch size b, and learning rate y in realistic setting, where the

---

Published as a conference paper at COLM 2025
The Prlect of clpping Nor Threshold
The Effect of cleping Nerm Threshid
0:35
SERT hase (NAG-US4) with pw0.32, B-
Model Performa g3 (MRR)
BERTibul IMAG cnll with ow0.32 6-16
leamiig rate
18.99 29:5500
2.30
0.40
0.45
Modo pertomman
3.25
0:35
C-0.1
0.30
C+0.1
0-1
C-1
10090
0.15
C-10
0.20
C+10
75 36 3034-332
Cm100
C-100
0.10
16 64 128 256
1011012500 15000
batch size b
Step
Step
Figure 3: Effects of learning rate and batch size (Left), and clipping norm threshold C (Right) for zero-shot relation prediction with privacy preservation.
training steps are fixed. Fig. 2 (Left) shows the impact of negative sampling in relational learning: Increasing k generally improves prediction performance but with a rapidly de- creasing marginal benefit. To achieve a trade-off between performance and computational complexity, the optimal region is located at k E [4,8]. Fig. 2 (Middle) shows the effect of batch size on different models under the same privacy budget: Larger b leads to better model performance and quicker convergence, especially for Llama2-7B. This observation is consistent with non-relational private learning, where increasing b achieves a better signal-to-noise ratio between the sum of clipped gradients and the Gaussian noise added via Eq. (3). The joint effect of batch size and learning rate is further studied and depicted in Fig. 3 (Left): Larger batches and learning rates together lead to good performance under fixed training steps, which echoes the findings in privately fine-tuning LLMs on standard text data (Li et al., 2021). The main obstacle to using larger b is the linearly increased privacy computing and memory cost associated with controlling per-sample gradients as discussed in Sec. 3.3. We report the memory cost and throughput of base models in Table 10, Appx. D.
Next, we study how privacy parameters impact model utility. Fig. 2 (Right) plots the privacy-utility curve of BERT.base on zero-shot relation prediction over MAG-USA/CHN datasets using different privacy budgets by adjusting noise multiplier o while keeping other parameters constant. In this case, the scale of added noise solely determines the privacy leakage, where the model performance decays proportionally as the value of o increases. The threshold of norm clipping C does not affect the privacy budget but is crucial to the utility performance of DP' models (Bu et al., 2024), and its impact on relational learning tasks is shown in Fig. 3 (Right). Picking a threshold C that larger than the actual gradient norm means that most clipping through Eq. (3) is not effective, and the noise oC is added more than necessary. Small values of C generally work better for relational learning, which aligns with the practice and observation of DP learning on non-relational data in both vision and language tasks (Tramer & Boneh, 2021; Li et al., 2021).
5 Conclusion
Leveraging relational data to enhance AI models holds great promise. This work proposes a novel privacy-preserving training pipeline that addresses the unique privacy and com- putational challenges in relational learning by decoupling the dependencies in sampled relations for training and exploiting gradient structure through individual samples for efficient clipping. We consider scenarios frequently encountered in applying relational learning to fine-tune pretrained language models and enforce privacy guarantees on the relationships used for training. Our study on privacy-preservinn relational learning shows that fine-tunde tieettnnig language models with our approach can significantly improve their perfor- mance on new test domains while keeping the relational training data differentially private. We further explore the privacy, utility, and computational efficiency trade-offs and conduct an extensive study on hyperparameter selection for relational learning in private settings.
Acknowledgments
This work is supported by NSF awards CCF-2402816, IIS- 2239552,,,, and the JPMC faculty award.
10

---

Published as a conference paper at COLM 2025
References
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Tla Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communicatiins Security, pp. 308-318, 2016.
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-scale differentially private BERT. In Findings of the Associalion for Computational Linguistics: EMNLP 2022, pp. 6481-6491, 2022.
Balle, L Berrada, S De, J Hayes, SL Smith, and R Stanforth. Jax-privacy: Algo- rithms for privacy-preserving machine learning in jax, 2022. URL http://gi http:://ggtttu.... thub.chom pesplleeddeemmnn//j.ppxvvvaae
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy. Analytical calibration and optimal denoising. In International Conference on Machine Learning, pp. 394-403, PMLR, 2018.
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.
Wenxuan Bao, Francesco Pittaluga, Vijay Kumar BG, and Vincent Bindschaedler. Dp-mix: mixup-based data augmentation for differentially private learning. In Advances in Neural Information Processing Systems, volume 36, 2024.
Priyam Basu, Tiasa Singha Roy, Rakshit Naidu, Zumrut Muftuoglu, Sahib Singh, and Fatemehsadat Mireshghallah. Benchmarking differential privacy and federated learning for bert models. arviv preprint arXiv:2106.1397 133973,,,.. 2021.
Parishad BehnamGhader, Vaibhav Adlakha, Marius Mosbach, Dzmitry Bahdanau, Nicolas Chapados, and Siva Reddy, LLM2Vec: Large language models are secretly powerful text encoders. In First Conference on Language Modeling, 2024. URL forum?1d==W1PRPVEEB.
net/
Iz Beltagy, Kyle Lo, and Arman Cohan. SciBERT: A pretrained language model for scientific text. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNL.P-ICCNIP),, pp. 3615-3620, 2019.
Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, (336629)) 2016.
Claude Berge. Hypergraphs: combinatorics of finite sets, volume 45. Elsevier, 1984.
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.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901, 2020.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differen- tially private deep learning made easier and stronger. In Advances in Neural Information Processing Systems, volume 36, 2024.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897-1914. IEEE, 2022.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple frame- work for contrastive learning of visual representations. In International Conference on Machine Learning, pp- 1597-1607. PMLR, 2020.
11

---

Published as a conference paper at COLM 2025
Eli Chien, Wei-Cheng Chang, Cho-Jui Hsieh, Hs Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit S Dhillon. Node feature extraction by self-supervised multi-scale neighbor- hood prediction. In International Conference on Learning Representations, 2022.
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.
Ameya Daigavane, Gagan Madan, Aditya Sinha, Abhradeep Guha Thakurta, Gaurav Aggarwal, and Prateek Jain. Node-level differentially private graph neural networks. Xiv preprint ar Xriv:2111..55211 2021.
Jacob Devlin, Ming-Wei 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 Linguisties: Human Language Techmologies, Volume 1 (Long and Short Papers), pp. 4171-4186, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
Keyu Duan, Qian Liu, Tat-Seng Chua, Shuicheng Yan, Wei Isang Ooi, Qizhe Xie, and Junxian He. Simteg: A frustratingly simple approach improves textual graph learning. arxiv preprint ar 2tt::2308.025655 2023.
Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211-400 2014.
Alessandro Epasto, Vahab Mirrokni, Bryan Perozzi, Anton Tsitsulin, and Peilin Zhong, Differentially private graph learning via sensitivity personalized pagerank. In Adoances in Neural Information Processing Systems, volume 35, pp. 22617-22661 2022.
Tianyu Gao, Xingcheng Yao, and Danqi Chen. SimCSE: Simple contrastive learning of sentence embeddings. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 6894-6910, 2021.
Yanjun Gao, Ruizhe Li, John Caskey, Dmitriy Dligach, Timothy Miller, Matthew M Churpek, and Majid Afshar. Leveraging a medical knowledge graph into large language models for diagnosis prediction. arXiv preprint arXio:2308.14321, 2023.
Ian Goodfellow. Efficient per-example gradient computations.
arXiv preprint
axXiv:1510.01799, 2015.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. In Advances in Neural Information Processing Systems, volume 34, pp. 11631-11642, 2021.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning invariant mapping. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, volume 2, pp. 1735-1742, 2006.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Dala Eng. Bull., 40(3):52-74, 2017.
Michael Hay, Chao Li, Gerome Miklau, and David Jensen. Accurate estimation of the degree distribution of private networks. 2009 Ninth IEEE International Conference on Data Mining, pp. 178. IEFF, 2009.
12

---

Published as a conference paper at COLM 2025
Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, and Yang Zhang. Stealing links from graph neural networks. In 30th USENIX Security Symposium (USENIX security 21), pp. 2669-2686, 2021.
Shlomo Hoory, Amir Feder, Avichai Tendler, Sofia Erell, Alon Peled-Cohen, Itay Laish, Hootan Nakhost, Uri Stemmer, Ayelet Benjamini, Avinatan Hassidim, et al. Learning and evaluating differentially private pre-trained language model. In Findings of the Association for Computational Linguistics: EMNLP 2021, pp. 1178-1189, 2021.
Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Alu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, volume 33, pp. 22118-22133, 2020.
Bowen Jin, Gang Liu, Chi Han, Meng Jiang, Heng Ji, and Jiawei Han. Large language models on graphs: A comprehensive survey. ar preprini ar arXi::3312.02788, 2023a.
Bowen Jin, Wentao Zhang, Yu Zhang, Yu Meng, Xinyang Zhang, Qi Zhu, and Jiawei Han. Patton: Language model pretraining on text-rich networks. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 7005-7020, 2023b.
Gavin Kerrigan, Dylan Slack, and Jens Tuyls. Differentially private language models benefit from public pre-training. In Proceedings of the Second Workshop on Prioucy in NLP, pp. 39-45, 2020.
Siwon Kim, Sangdoo Yun, Hwaran Lee, Martin Gubri, Sungroh Yoon, and Seong Joon Oh. Propile: Probing privacy leakage in large language models. Advances in Neural Information Processing Systems, 36, 2024.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
William Kong, Andrés Muñoz Medina, and Mónica Ribero. Dp-sgd for non-decomposable objective functions. In International Conference on Learning Representations, 2025.
Eren Kurshan and Hongda Shen. Graph computing for financial crime and fraud detection: Trends, challenges and outlook. International Journal of Semantic Computing, 14((4))565-589, 2020.
Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. What is twitter, social network or a news media? In Proceedings of the 19th International Conference on World Wide Web, pp. 591-600, 2010.
Jaewoo Lee and Daniel Kifer. Scaling up differentially private deep learning with fast per-example gradient clipping. Proceedings on Privacy Enhancing Technologies, 2021.
Jure Leskovec, Lada A Adamic, and Bernardo A Huberman. The dynamics of viral market- ing. ACM Transactions on the Web (TWEB), (11::5ess, 2007.
2007.
Wenjun Li, Anli Yan, Di Wu, Taoyu Zhu, Teng Huang, Xuandi Luo, and Shaowei Wang Dpel: Contrastive representation learning with differential privacy. International Journal of Intelligent Systems, 37 371119997199775 2022.
Xianming Li and Jing Li. BeLLM: Backward dependency enhanced large language model for sentence embeddings. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 7D2-992-04 2024.
13

---

Published as a conference paper at COLM 2025
Xin Li, Dongze Lian, Zhihe Lu, Jiawang Bai, Zhibo Chen, and Xinchao Wang. Graphadapter: Tuning vision-language models with dual knowledge graph. In Advances in Neural Information Processing Systems, volume 36, 2023a.
Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language mod- els can be strong differentially private learners. In International Conference on Learning Representations, 2021.
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, 2023b.
Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and rela- tion embeddíngs for knowledge graph completion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Chen Ling, Xujiang Zhao, Jiaying Lu, Chengyuan Deng, Can Zheng, Junxiang Wang, Tanmoy Chowdhury, Yun Li, Hejie Cui, Tianjiao Zhao, al. Beyond -llloolel-its--ll:: A survey of domain speciaizziinn for large language models. ar preprint arXiv:2305.18703, 2023.
Haohui Lu and Shahadat Uddin. Disease prediction using graph machine learning based on electronic health data: review of approaches and trends. In Healthcare, volume 11, pp. 1031. MDPI, 2023.
Neelu Madan, Andreas Moegelmose, Rajat Modi, Yogesh S Rawat, and Thomas Moeslund. Foundation models for video understanding: A survey, arXiv preprint ar 03770, 2024.
Rajja
Omid Madani, Sai Ankith Averineni, and Shashidhar Gandham. A dataset of networks of computing hosts. In Proceedings of the 2022 ACM on International Workshop on Security and Privacy Analytics, pp. 100-104, 2022.
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, pp. 43 52,52, 2015.
H Brendan McMahan, Galen Andrew, Ulfar Erlingsson, Steve Chien, 1lya Mironov, Nicolas Papernot, and Peter Kairouz. A general approach to adding differential privacy to iterative training procedures. arviv preprint ar Xtx::1812..06210 2018.
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594) 2002.
Tamara T Mueller, Johannes C Paetzold, Chinmay Prabhakar, Dmitrii Usynin, Daniel Rueckert, and Georgios Kaissis. Differentially private graph neural networks for whole- graph classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(6): 7308-7318, 2022.
Tyiola Emmanuel Olatunji, Thorben Funke, and Megha Khosla. Releasing graph neural networks with differential privacy guarantees. Transactions Machine Learning Research, 2023.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprini arXio:1807. 10f014887.03748,, 00744,, 2018.
Kun Ouyang, Yi Liu, Shicheng Li, Ruihan Bao, Keiko Harimoto, and Xu Sun. Modal- adaptive knowledge-enhanced graph-based financial prediction from monetary policy conference calls with 1lm. Xiv preprint 7Xir:2403.16655. 2024.
14

---

Published as a conference paper at COLM 2025
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. In Adoances in Neural Information Processing Systems, volume 35, pp. 27730-27744, 2022.
Ke Pan, Yew-Soon Ong, Maoguo Gong, Hui Li, AK Qin, and Yuan Gao. Differential privacy in deep learning: A literature survey. Neurocomputingg, pp. 127663, 2024.
Nicolas Papernot, Shuang Song, llya Mironov, Ananth Raghunathan, Kunal Talwar, and Ülfar Erlingsson. Scalable private learning with pate. In International Conference on Learning Represenlations, 2018.
Bo Peng, Xinyi Ling, Ziru Chen, Huan Sun, and Xia Ning. ecellm: Generalizing large language models for e-commerce from large-scale, high-quality instruction data. In International Conference on Machine Learning. PMLR, 2024.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social rep- resentations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701-710, 2014.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Bren- dan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113-1201 2023.
Jason Priem, Heather Piwowar, and Richard Orr. Openalex: A fully-open index of scholarly works, authors, venues, institutions, and concepts. arXiv preprint ar Xix::205500883. 2022.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 8748-8763. PMLR, 2021.
Ossi Räisä, Joonas Jälkö, and Antti Honkela. Subsampling is not magic: Why large batch sizes work for differentially private stochastic optimisation. In International Conference on Machine Learning. PMLR, 2024.
Sofya Raskhodnikova and Adam Smith. Lipschitz extensions for node-private graph statistics and the generalized exponential mechanism. In 2016 JEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 495-504. IEEE, 2016.
Sina Sajadmanesh and Daniel Gatica-Perez. Locally private graph neural networks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 2130-2145, 2021.
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 Dala Mining, pp. 596-605, 2024.
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), pp. 3223-3240, 2023.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 815-823, 2015.
Manuel Senge, Timour Igamberdiev, and Ivan Habernal. One size does not fit all: Investi- gating strategies for differeetialll--rriatte learning across NLP tasks. In Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, pp. 7340-7353, 2022.
Kiarash Shamsi, Yulia R. Gel, Murat Kantarcioglu, and Cuneyt G. Akcora. Chartalist: Labeled graph datasets for utxo and account-based blockchains. In Advances in Neural Information Processing Systems, volume 35, pp. 14929-34939, 2022.
15

---

Published as a conference paper at COLM 2025
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Prioucy (SP), pp. 3-18. IEEE, 2017.
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 on World Wide Web, pp. 243-246, 2015.
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. In Advances in Neural Information Processing Systems, volume 29, 2016.
Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese, Deep metric learning via lifted structured feature embedding. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEFE Global Conference on Signal and Information Processing, pp. 245-248. IEEE, 2013.
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 (XXi::3377.09888 2023.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference on Learning Representations, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
Xiuling Wang and Wendy Hui Wang. Link membership inference attacks against unsuper- vised graph representation learning. In Proceedings of the 39th Annual Computer Security Applications Conference, pp. 477-491, 2023.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differ- ential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1226-1235. PMLR, 2019.
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.
Rongzhe Wei, Eli Chien, and Pan Li. Differentially private graph diffusion with applications in personalized pageranks. In Advances in Neural Information Processing Systems, 2024.
Frank Wilcoxon. Individual comparisons by ranking methods. In Breakthroughs in statistics: Methodology and distribution, pp. 196-202. Springer, 1992.
Shijie Wu, Ozan Irsoy, Steven Lu, Vadim Dabravolski, Mark Dredze, Sebastian Gehrmann, Prabhanjan Kambadur, David Rosenberg, and Gideon Mann. Bloomberggpt: A large language model for finance. arXiv preprint ar arXff:2303.17564 2023.
Tong Wu, Yunlong Wang, Yue Wang, Emily Zhao, and Yilian Yuan. Leveraging graph-based hierarchical medical entity embedding for healthcare applications. Scientific reports, 11(1): 5858, 2021.
Han Xie, Da Zheng, Jun Ma, Houyu Zhang, Vassilis Ioannidis, Xiang Song, Qing Ping, Sheng Wang, Carl Yang, Yi Xu, et al. Graph-aware language model pre-training on large graph corpus can help multiple graph applications. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 5270-5281, 2023.
Depeng Xu, Shuhan Yuan, Xintao Wu, and HaiNhat Phan. Dpne: Differentially private network embedding. In Advances in Knowledge Discovery and Data Mining: 22nd Pacific-Asia Conference, pp. 235-246 Springer, 2018
16

---

Published as a conference paper at COLM 2025
Runhua Xu, Nathalie Baracaldo, and James Joshi. Privacy-preserving machine learning: Methods, challenges and directions. arx preprint arXiv:2108.0444 04417, 2021.
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.
Zhen Yang, Ming Ding, Tinglin Huang, Yukuo Cen, Junshuai Song, Bin Xu, Yuxiao Dong, and Jie Tang. Does negative sampling matter? review with insights into its theory and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Yifan Yao, Jinhao Duan, Kaidi Xu, Yuanfang Cai, Zhibo Sun, and Yue Zhang. A survey on large language model (Ilm) security and privacy: The good, the bad, and the ugly. High-Confidence Computing, pp. 100211, 2024.
Michihiro Yasunaga, Antoine Bosselut, Hongyu Ren, Xikun Zhang, Christopher D Manning, Percy S Liang, and Jure Leskovec. Deep bidirectional language-knowleddgs graph pre- training. In Advances in Neural Information Processing Systems, volume 35, pp. 37309-37323, 2022a.
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), pp. 8003-8016, 2022b.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974-983, 2018
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Process- ing Systems, volume 33, pp. 5812-5823, 2020.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, et al. Opacus: User-friendly differential privacy library in pytorch. arXiv preprint ar Xit:2109.12296 2021.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially pri- vate fine-tuning of language models. In International Conference on Learning Representations, 2022.
Jingyi Zhang, Jiaxing Huang, Sheng Jin, and Shijian Lu. Vision-language models for vision tasks: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024a.
Qiuchen Zhang, Hong kyu Lee, Jing Ma, Jian Lou, Carl Yang, and Li Xiong, Dpar: Decoupled graph neural networks with node-level differential privacy. In Proceedings of the ACM on Web Conference 2024, pp. 1170-1181, 2024b.
Sen Zhang and Weiwei Ni. Graph embedding matrix sharing with differential privacy. IEEE Access, 7:89390-89388 2019.
Xikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren, Percy Liang, Christo- pher D Manning, and Jure Leskovec. Greaselm: Graph reasoning enhanced language models. In International Conference on Learning Representations, 2022.
Xuanzhi Zheng, Guoshuai Zhao, Li Zhu, Jihua Zhu, and Xueming Qian. What you like, what am: online dating recommendation via matching individual preferences with features. IEEE Transactions on Knowledge and Data Engineering, 35(5):5400- 2022.
Jing Zhu, Xiang Song, Vassilis loannidis, Danai Koutra, and Christos Faloutsos. Touchup-g: Improving feature representation through graph-centric finetuning. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2662-2666, 2024.
17

---

Published as a conference paper at COLM 2025
Appendix
A
Privacy Risks in Relational Learning
Relational learning aims to inject observed relational information between entities into target models, commonly captured by graph data G (V,E, X). Suppose the representation of each entity E V is obtained from a model parameterized by O encoding its attribute, i.., hy = fo (X)).. To make the target model relation-aware, the refinement usually through optimizing the parameter @ via a relation-based loss, generally in the form of ((;; (e,, ( )-=))) The following uses a pairwise relation as an example: e = (u,v) v) is observed in relation set &, usually termed as positive relation, while the unobserved relation e, (u, w) E E is referred to as negative. Let (-) be score function that measures or labels the relationship between entities based on their embeddings output by the model. The intuition behind common loss used in relational learning (e.g,, InfoNCE loss (Oord et al., 2018) and pairwise Hinge loss (Bordes et al., 2013)), is to promote positive relations zet = rhh., he) having a higher score than paired negative relations 2, = [h,,, hw) The
overall objective can be written as
θ = arg
Σ E(() (Z,7, (Z,7 1/=1). E
(4)
Here, O is the parameter of any target model that can encode entity attributes. The relational information is only exposed to the model through the loss function l as labels for supervision and carried into model parameters during backpropagation. The privacy risk of relational learning through the above procedure can be mitigated by carefully limiting and obfuscating the update of model parameters induced by individual relations, which is the main objective studied in this work.
A.1
Differentially Private GNNs are Insufficient for Relational Learning with Differential Privacy
Graph neural networks (GNNs) (Kipf & Welling, 2017) are one of the most popular encoders that can be directly applied to relational data for obtaining entity embeddings. The key mechanism of GNNs is message-passing, where information is propagated and aggregated among neighborhoods of entities along the graph topology. A typical GNN consists of L sequential graph convolution layers, which are formulated as
h = upd agg
(1-1) (ha-1) Vo (N(o))) :0!"
(5)
where M()) = fo (u, E }} denotes the set of neighboring entities to entity u, and hg (1-1) is the embedding of an neighboring entity v at layer - agg(.) is a differentiable, permutation invariant aggregation function (e.g., sum, mean, max). upd(.) is a learnable
function, such as multi-layer perception (MLP), parameterized by ) that takes the
aggregated embeddings and outputs the updated embedding for the root entity h.""
Next, we show why previous methods that build differentially private GNNs cannot handle the challenges of relational learning with differential privacy. DP-GNNs (Daigavane et al., 2021; Zhang et al., 2024b; Sajadmanesh et al., 2023; Sajadmanesh & Gatica-Perez, 2024; Chien et al., 2024) primarily address the privacy issue during graph data encoding. Specifically, in GNN models, perturbing node or an edge affects not only itself and its direct neighbors but also multi-hop neighbors through recursive layer-wise message passing, as shown in Eq. (5). Existing efforts mainly focus on limiting such correlation in message passing (e.g,, node degree and number of hops) so that the sensitivity of graph encoding in GNNs can be bounded, which makes it feasible for DP training on entity- or graph-level tasks. Unfortunately, these techniques are insufficient for relational learning because coupled relations in the loss (e.g., Eq. (4)) make the gradient not decomposable into specific privacy- preserved samples and thus still leaves srrvacy-reesevvig relational learning an open problem. We aim to solve this problem in this work.
18

---

Published as a conference paper at COLM 2025
A.2 Privacy Concerns with Other Types of Negative Sampling in Relational Learning
As discussed in Section 3.1, the main challenge in applying DP-SGD to privacy-preserving relational learning is the coupled sampling of positive and negative relations during training. Here, we showcase the coupling caused by other types of negative sampling. Random Negative Sampling is one of the most widely used methods (Yang et al., 2024). Given positive relation et- = w)), it uniformly samples negative relations containing either entity w from the complement set & = (2)E,, for example, e; = (u,v) E E. This
method requires access to & obtain & for negative selection and makes the sampled negative relations dependent on the positive relations that share common entities. If an originally negative relation (u, v) is flipped as positive and added to the relation set &, all tuples in the batch B that previously sampled (u, v) as negative relations will be affected. In the worst-case scenario, it may affect the entire mini-batch, introducing a high sensitivity that cannot be properly controlled by clipping the gradient of each tuple. This observation also makes all sampling methods that require accessing the relation set ineligible for relational learning in private settings, such as cauuaritty-bssed Negative Sampling and the family of Hard Negative Sampling that generates true negative samples.
B Related Work
LLMs with Relational Data. Extensive work has focused on using relational data to enhance foundation models, especially for fine-tuning LLMs on graphs, in light of their strong generalization ability. These methods can be classified into two types. Objectioe-only: Yasunaga et al. (2022b); Duan et al. (2023); Xie et al. (2023) proposed to associate entity representations from LLMs with relational information by optimizing the objective based on specific graph tasks. For example, relation prediction ís a typical task in unsupervised graph learning, adopted in this work. Graph-encoder-bess
Chien et al. (2022); Yasunaga et al. (2022a); Zhu et al. (2024); Xie et al. (2023); Jin et al. (2023b) pair LLMs with a graph encoder (e.g., GNNs (Kipf& & Welling, 2017)) to incorporate relational information end-to-end manner, where LLMs act as feature extractors for textual attributes, and their output with associated graph topology is fed into GNNs for aggregation and prediction. These models may be privatized by combining the approach proposed in this work with the privatized method for graph encoders (Sajadmanesh et al., 2023; Chien et al., 2024), though the entire pipeline could be complex and beyond the scope of this work.
an
Privacy-preserving for LLMs Data privacy in LLMs focuses on safeguarding sensitive information that could be exposed during operations (Yao et al., 2024). Recent efforts have utilized DP-SGD for both pretraining and fine-tuning LLMs. For instance, Anil et al. (2022) trained
BaRT. model from scratch. However, due to the resource- intensive nature of LLMs, the focus has shifted towards private fine-tuning of publicly pretrained models. Hoory et al. (2021) explored private full fine-tuning of BERT models with domain-specific data, while recent advancements in this field include the works of Basu al. (2021); Kerrigan et al. (2020); Senge et al. (2022); Li et al. (2021). There growing interest in efficient private fine-tuning techniques. Yu et al. (2022) applied parameter-efffcient fine-tuning methods for private fine-tuning of LLMs, and Li et al. (2021) introduced ghost clipping to accelerate gradient clipping in DP-SGD. However, these methods primarily address privacy concerns for standard text data. In contrast, our work extends these privacy- preserving techniques to relational data, filling an important gap in this research area.
Privacy-preserving Graph Learning. Significant research has focused on privacy-preeerving graph embedding and learning algorithms with DP guarantees (Li et al., 2023b). Daigavane et al. (2021) proposed a privacy-preserving DP- Olatunji et al. (2023) adopted teacher-student models to enable the DP release of GNNs. Sajadmanesh et al. (2023) improved utility-privacy trade-offs by decoupling feature propagation and model training, and their work further got extended in subsequent studies (Sajadmanesh & Patica,Perez, 2024; Chien et al., 2024). These methods specialize in generating private node representations and privatizing the graph exposed to encoders for
approach for training GNNs via extensions of
19

---

Published as a conference paper at COLM 2025
feature propagation and aggregation, which do not mitigate privacy risks when relational information is used for supervision.
B.1 Other Related Work
Private Graph Embedding Methods. Graph embedding encodes nodes into low- dimensional vectors, preserving topological information (Hamilton et al., 2017). Xu al. (2018) proposed private network embedding method using objective perturbation in Deep- Walk (Perozzi et al., 2014) but faced scalability issues for complex sensitivity calculations. Zhang & Ni (2019) addressed these issues by applying Lipschitz condition (Raskhod- nikova & Smith, 2016) and gradient clipping. Epasto et al. (2022); Wei et al. (2024) studied DP PageRank methods, which can be leveraged to generate DP graph embedding well. These methods specialize in preventing privacy leakage during generating node embeddings, but cannot protect the privacy of relations that are used for supervision studied in this work.
Private Aggregation of Teacher Ensembles. PATE and its variants (Papernot et al., 2018) are an alternative leverages an ensemble of teacher models that are trained on disjoint datasets containing sensitive data. These models are not published but instead used as teacher models for separate student model. The student model cannot access any single teacher model or the underlying data. It learns to predict an output chosen by noisy voting performed across all teacher models. The student is trained on a publicly available, unlabelled dataset, where the labels come from the aggregate votes of the teachers. The availability of public data is one notable limitation of PATE, as well as the complexity of training collection of teacher models. Olatunji et al. (2023) proposed a PATE framework to release GNNs with node-DP for node-level tasks. Adopting PATE in graph settings faces challenges of low utility due to the physical separation of datasets in graph learning that destroys structural information and limited generality beyond graph classification settings.
method to achieve DP in machine learning, which
Existing studies on private contrastive learning aim to eliminate the risk of sample correlation in contrastive losses and thus protect the privacy of individual training samples. Li et al. (2022) proposed to add privacy noise to the similarity matrix between pairs of inputs reduce the sensitivity of gradients w.r.t. the contrastive loss. Kong et al. (2025) extended it to similarity-basee loss functions by bounding the pairwise similarity gradients. Bao al. (2024) proposed train vision models with the mixup technique under DP by leveraging augmentation multiplicity. These methods focus on learning representations of non-relationa samples differentially private by contrastive views, but they cannot be used to address the privacy challenges of coupled relations in training models on relational data.
Contrastive Learning with Differential Privacy.
C Learning Pipelines of Standard DP and Relational Settings
DP-SGD (see Alg. 1) (Song et al., 2016; Abadi et al., 2016) is proposed for training deep learning models on (non-relational) samples with a privacy guarantee. DP-Adam (see Alg. 2) works similarly to regular Adam (Kingma & Ba, 2015) but performs updates and moment accumulation with privatized gradients. The gradient privatization part is the same as that performed in DP-SGD, where the privacy analysis and guarantees for DP-SGD still hold for DP-Adam due to the post-processing property of DP (Dwork al., 2014). We use DD-Adam (see Alg. 2) as the default optimizer, same as previous work (Li et al., 2021; Yu et al., 2022). relational learning pipeline is summarized in Alg. 3.
The proposed
D Experimental Details
Datasets. Item and paper titles are used as textual attributes associated with entities in the Amazon e-commerce network (AMAZ) (McAuley et al., 2015) and the Microsoft Academic
20

---

Published as a conference paper at COLM 2025
Algorithm 1 DP-SGD from Abadi et al. (2016)
Input:
x:); Parameters: learning Training data XN,, loss function ( - N Paraaeetteaar
rate f)t, batch size b, gradient norm threshold C, noise multiplier o or privacy budget e. Initialize find the optimal value of o via calibration if is given.
for = 1 to do
Subsampling
Randomly sample B, with sampling probability b/N
Compute Gradient
For each x; B,, compute g (x;) + Vo,
Gradient Clipping
(x(x;) - (x;) max 11, (1(()
Add Noise
- 1 L (x;) +N((0,
g+
Parameter Update
++1 + - end for Output Or and calculate the overall privacy cost (e,5) using an accounting method if is given.
Algorithm 2 DP-Adam (Kingma & Ba, 2015; Abadi et al., 2016)
Training data Xi, XN, loss function L(O) I L(O, x;); Parameters: learning rate //,, batch size b, gradient norm threshold C, noise multiplier a or privacy budget initial moment estimates mo, Pü, exponential decay rates ß1, $2, avoid division-by-zero constant yy
Input:
Initialize find the optimal value of a via calibration if e is given.
for /or:= to T do Subsampling
Randomly sample B, with sampling probability b/N
Compute Gradient
For each x; B,, compute gr (x;) Vo,
Gradient Clipping
(x(x;; 4 (x;)/ max 11, [
Add Noise
g: + 1 (x;) (0,(0)
Parameter AdamUpdate
MH+1 + f1-m; (1 f1) Bt, ut41 +- f2 vz +(1 (1-B2) gg
M m41111111111111 0 t- 1/11 B3)
0,41 < O 1/: ft-m441/ (V0 +
end for
Output O and calculate the overall privacy cost (e, using an accounting method if is given.
21

---

Published as a conference paper at COLM 2025
Algorithm 3 Learning on Relational Data with Differential Privacy
Input: target model fe (e.g,, LLMs), graph g = EV,E, X), scoring function I', loss function &; Parameters: learning rate !]t, batch size b, number of negative samples k, threshold of gradient norm C, noise multiplier o privacy budget Initialize find the optimal value of via calibration if is given.
for = to T do Subsampling
I. Randomly sample B, from & with sampling ratio b/|E).
II. For each sampled positive relation e; in the batch, randomly sample k entities (Pir...,,Py without replacement from and pair them with one end of et as negatives
{ez 14 Jj=1, which forms tuple of k + relations as E; = (ef A4j 1/21).
Compute & Aggregate Gradient
(:(E)) = Le'E Luee'
a((OE))) ăzy ah, dz. Sh 20
where zz = [h, h2) for relation e' (u,
and h = fo for entity u. Note that the actual computation of g:(E)) performed by the efficient approach introduced in Sec. 3.3. Gradient Clipping & Add Privacy Noise
8: - 1 LE,eB, gr /E,) max (1, (EE)))/ +N
Parameter Update
+++ θ 1//8/ end for Output Or and calculate the overall privacy cost (e,ō) using an accounting method if or is given.
AMAZ-Cloth
AMAZ-Sports
Label
Name
Label
Name
0
girls
accessories
1
men
action sports boating & water sports
2
novelty
3
luggage
clothing
4
baby
cycling
5
fashion watches
baby
6
shoes
exercise & leisure sports fan shop
7
boys
8
adidas
golf
hunting & fishing & game room 10
outdoor gear fitness
11
12
paintball & airsoft
13
racquet sports
14
snow sports
team sports
Table Class names of the AMAZ dataset.
22

---

Published as a conference paper at COLM 2025
Target Model
baRT.base
laRTlarge
Llama2-7B
DP Guarantee ()
(-1//)mmain)
(-1/ (-11/Errain) (train))
(,1//(mmi)))
Clipping threshold C
1
Noise multiplier
[0.3, 0.5]
[0.3, 0.5]
[0.3, 0.5]
LoRA rank
(2,4,116)
(2,48,16)
(2,4,8166)
LoRA alpha a
16
16
16
LoRA dropout
0.2]
[0, 0.2]
[0, 0.2]
Target module
query, key, value, dense
query, key, value, dense
4 proj, v. p.ojj
Batch size
(8, 16, 32, 64)
{8, 16, 32, 64)
(12, 16, 32, 64, 128)
Learning rate
[10 10
[10 10
[10 10-61 cosine
LR scheduler
linear
linear
Weight decay A
[0, 10 31
[0. 10 $1
0 (4, 8, 12, 16)
Negative sample
[4, 6, 8, 16)
(4, 6, 8, 16}
Table 6: Hyperparameter search range for different models.
Target Model
License
Model Card
BaRe
Apache License 2.0
nttps://huggingfaace
http:://hhggggggaaa....ogggggeee moooglebbert/bert base uncased
BERTlarge
Apache License 2.0
https://hugginggacee co/google- beooggetbertbbert-eeee tabeertaaeeeeee----eeeeeerrreeee uncaeed
SciBERT
Apache License 2.0
https: https://hugginngaac.. wow.allemaissiieetttssiiiiii www.obbabb...cobbbbb.......oeeee uncased
LinkBERTlarge
Apache License 2.0
https://huggingfe
inkBERT-lagee
Llama2-77
Meta Community License
https://hugiingface. co/neta- 11ama/Llama22-7001
Table 7: Model card of pretrained language models.
Dataset
#Entity
#Relation
#Entity (Test)
#Classes
#Relation (Test)
Test Domain
AMAZ-CImP Cloth
960,613
4,626,125
476,510
10,000
AMAZ-Sports
AMAZ- Sports
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 8: Dataset statistics for evaluation.
MAG-USA PREC@1
MAG-CHN
AMAZ-Cloth PRECØ1
AMAZ-Sports
Sampling Method
MRR
PREC@1
MRR
MRR
PREC@1
MRR
In-batch negatives
28.07
39.11
41.93
53.91
36.13
47.07
29.84
39.61
Decoupled sampling
28.44
39.45
41.90
54.19
35.78
46.79
28.33
38.59
Table 9: Results on zero-shot relation prediction with different negative sampling strategies used for non-private fine-tuning on BERT.base.
Model
VRAM (Base + Adapter)
VRAM (Backprop.)
Peak VRAM
Throughput
BERT.base
1,178 MB
6,044 MB
12,175 MB
67.52 tuples/s
BERT.arge
2,006 MB
14,284 MB
21,428 MB
14.04 tuples/s
Tlama2-7B
26,419 MB
66,562 MB
79,020 MB
14.41 tuples/s
Table 10: Efficiency analysis for privacy-preserving relational learning: GPU memory and throughput with batch size b of 32.
23

---

Published as a conference paper at COLM 2025
Graph (MAG) (Sinha et al., 2015), respectively. OpenAlex API (Priem et al., 2022) is used to obtain metadata of papers in the MAG dataset, as the Microsoft Academic service has been retired. For some items/ / papers, we concatenate their titles with the corresponding description/anl /absttact /abstracc following Jin et al. (2023b) since the text of the title is too short. The max length of the input token M is set to 32. The semantics of relational information used and "paper-cited-paper for AMAZ and MAG networks, respectively. To mimic the case in the cross-category recommendation, two subgraphs are selected from AMAZ that only contain items belonging to the category of clothing (AMAZ-Cloth) and sports (AMAZ-Sports). For entity classification, the class names of the AMAZ dataset are listed in Table 5. Based on the geographic metadata of the main authors, we select two subgraphs from MAG containing papers written by authors from the United States (MAG-USA) and China (MAG-CHN) to simulate the case in cross-regional model deployment. The coarse-grained class of papers in the MAG dataset is refined by selecting the Toc-K-occurrence of 349-class obtained from Open Graph Benchmark 4 (Hu et al., 2020) and merging the rest of the classes into one. The processed data is available at https://zenod:: org/ hegg///rrs/////e/o//ooe/ooo.ss (eprrrs///116651 5186566..
for supervision are -item-co-uurcased-iteee
Target Models. Off-the-shelf pretrained language models: BERT (Devlin et al., 2019),
language model pretrained with objectives of masked language modeling (MLM) and next sentence prediction on Wikipedia and BookCorpus, with parameters of 110M (base) and 340M (large). SciBERT (Beltagy et al., 2019) is trained on 1.14M paper abstracts and full text from Semantic Scholar under the same pertaining as BERT. LinkBERT (Yasunaga al., 2022b) is pretrained with MLM as BERT and the relation-based objective for predicting the linkage between documents. Note that some documents and relations in the MAG dataset may be used during the pretraining of SciBERT and LinkBERT, which potentially causes some data leakage. Llama2-7B (Touvron et al., 2023) is one of the most popular open-source pretrained and fine-tuned LLMs with 7 billion parameters.
Environment. We use a server with two AMD EPYC 7543 CPUs, 512GB DRAM, and NVIDIA Quadro RTX 6000 (24GB) GPUs for BERT-based models and A100 (80GB) GPUs for Llama2-7B models. The codebase is built on PyTorch 2.1.2, Transformers 4.23.0, PEFT 0.10.0, and Opacus 1.4.1. The source code is included and should be paired with the Transformers and PEFT packages from HuggingFac and the Opacus library specified above.
Private Fine-tuning. We use DP-Adam, variant of DP-SGD, as the default optimizer for updating model parameters in a srivacy-preservingg manner: given privacy parameters of noise multiplier o (or calibrated if é is given) and clipping threshold of gradient norm C, with a learning rate 1j from 1e-4 to 1e-6, weight decay from 0 to 1e-3, first 10% as warm-up steps. The batch size of testing is set to 256 for relation prediction, which follows Jin et al. (2023b) that uses in-batch negatives for computing ranking metrics. We use gradient accumulation over multiple mini-batches to simulate training at the expected batch size in case the actual memory needs exceed the physical memory limit of VRAM for large pretrained models. We search optimal training hyperparameters under given privacy parameters, where their ranges are summarized in Table 6. All pretrained model weights are publicly available and directly downloaded from Huggingface under proper licenses listed in Table 7.
Inference Setting. Once the model is privately fine-tuned on relational data, it is deployed for inference under two settings for relation prediction and entity classification on the corresponding test domains (see Table 8): Zero-shot, where the model is directly used without further training on samples from the test domain. This setting is only applied for relation prediction, where the dot product between entity embeddings is used as the scoring function I for inference. Few-shot, where limited labels from the test domain are provided to further fine-tune the target models obtained after This setting is used for both relation prediction and entity classification (the classifier
relational learning.
PODC-BY License, refer to https::/ http:/ee.orreeeeeeeeeeeeeeeeeeee /rt.///iceeee///////////////
$CCO License, refer to https::/ccreatiivecommsss htt.://ateeeeeooooooooor/r/obbee http:///www......ooooooooo/oo/// /omaai/iccccmmmii/cee////
4ODC-BY License
24

---

Published as a conference paper at COLM 2025
MAG-USA
MAG-CHN
AMAZ-Cloth
AMAZ-Sports
Privacy Model
e
BERTbase
0.32
9.95
4
0.32
8.74
2
0.3
9.71
0.3
9.06
10
BERT.arree
0.34
8.72
4
0.33
8.56
2
0.3
9.94
0.32
7.69
Llama2-7B
0.378
7.91
4
0.357
8.16
4
0,326
8.50
8
0.315
8,83
8
BERT.base
0.42
3.30
8
0.4
3.99
2
0.4
3.34
2
0.4
2.65
2
lagT
0.42
3.82
4
0.41
3.32
2
0.376
4.00
8
0.4
3.27
2
Llama2-7B
0.456
3.97
4
0.433
4.00
4
0.4
4.00
0.4
3.88
Table 11: Privacy loss c of model fine-tuning on relational data. 07, r are noise multiplier, privacy loss, and LoRA rank.
prictt Moded Nos USA
Intvuaally funetaneed Hodal (mm20) MAGUSA
Prtudalyy /tnu-arrdddddd Hoddl (eeds MMC-USA
0:34
Dut
0.50
0.4
0:22
L37e-4
Nenegrvate Pww.o on MAS-CH
Phaaddy Finecured Hocel (ew MAG-CWY
P1eatey Tiee funed Modid tendl MAG
0.18
0.24
1.23
082
prodsee
0- wwl.oddd 220 25
podlue
000
0.5
Figure 4: Membership inference attacks on target models fine-tuned non-privately vs privately (ours) over MAG-USA/CHN datasets. The distributions of relationship scores between each entity pair in the training and test sets are plotted. The p-value obtained from the statistical test using the Wilcoxon signed-rank test (Wilcoxon, 1992) is reported, where small p-value suggests that the observed difference between the score distributions of the training and test set is statistically significant.
requires some labels for initializing parameters), corresponding to the scenario of relational data scarcity from the test domain and limited resources to perform full domain-specific fine-tuning.
E Details for Studies in Section 4.1
After privately fine-tuning target models on relations from the training graph, we use the PRV accounting (Gopi et al., 2021) to track privacy loss and convert it to (c, 0)-P.. Table 11 summarizes the values of noise multiplier used and the actual privacy loss for training each model on sensitive relational data, which corresponds to the results reported in Table 1 under the zero-shot setting and in Tables 2, under the few-shot setting. Models under the few-shot setting have the same privacy loss as zero-shot since the examples used for further fine-tuning are non-private from the test domain. The scale of noise Co determines the privacy budget in DP-SGD, where higher privacy noise leads to lower privacy leakage e. Training with the same scale of privacy noise may result in different reported in Table
11: Different batch sizes b (sampling ratio p b/(E() and numbers of iterations T used in training also impact the privacy accounting in DP-SGD (Balle & Wang, 2018).
25


Reviews:
[{"review_id": "eF0DR1yVSF", "reviewer": "Reviewer_7KXH", "summary": "This paper introduces a framework for privacy-preserving relational learning, with a focus on fine-tuning large language models (LLMs) using graph-structured data under differential privacy (DP) guarantees. \n\nThe core challenge addressed is the incompatibility of existing DP methods like DP-SGD with relational learning, due to interdependent data samples inherent in graph structures. The authors propose a training pipeline that decouples observed and unobserved relational samples, thereby restoring the theoretical soundness of DP-SGD in this context.\n\nThe approach is evaluated on real-world datasets, demonstrating that it significantly outperforms existing DP baselines (e.g., randomized response) while maintaining strong privacy guarantees (ε ≤ 10). Experimental results also highlight favorable trade-offs among utility, privacy, and computational efficiency, making this solution practically relevant.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The paper tackles the challenge of applying differential privacy to relational learning tasks. While DP has been well studied in standard supervised settings, its integration with relational data—where dependencies between samples violate DP-SGD assumptions—remains underexplored.\n\n2. The proposed solution—decoupling the sampling of negative relations to ensure compatibility with DP-SGD—is well motivated. The authors also address practical challenges in computing per-sample gradients for large models by introducing an efficient low-rank approximation method, enabling scalable training on modern LLMs. \n\n3. The evaluation goes beyond utility metrics by also including privacy risk assessment via membership inference attacks, and a study of trade-offs among privacy, utility, and efficiency.", "reasons_to_reject": "While the paper addresses an important problem at the intersection of privacy and relational learning, the reviewer has several concerns.\n\n**First**, the core privacy argument relies on the claim that decoupled negative sampling ensures that adding or removing a single positive relation affects at most one tuple in a mini-batch, thereby enabling the use of DP-SGD. However, sampling negative entities from the entire entity set introduces a global dependency: adding or removing a relation can change the composition of the entity set itself. If an entity is unique to a newly added or removed relation, its presence or absence would alter the distribution from which negatives are sampled, thereby potentially affecting many tuples in a mini-batch. I am not an expert in relational learning, so if there are standard practices or assumptions I am missing (such as assuming a fixed entity set independent of the relation set), I welcome clarification.\n\n**Second**, the experimental design is somewhat intuitively not reasonable to the reviewer. The authors evaluate generalization by fine-tuning on one domain and testing on a completely different domain, where both the entities and their relationships are disjoint. It is unclear what meaningful relational knowledge could transfer in such a setting, especially when the core assumption of relational learning is that structure matters. For my perspective, a more intuitive and controlled experiment might involve within-domain generalization—e.g., holding out a subset of entities and their associated relations from the training set—so that the model is tested on structurally similar but unseen data.  This would better isolate the model's ability to generalize relational patterns. The current design casts doubt on whether the observed performance gains are attributable to relational learning or merely from memorizing local patterns. Again, I am not an expert in relational learning. So if there is precedent for the current cross-domain setup in prior work, it would be helpful for the authors to cite and explain it.\n\n**Third**, the method that sampling negatives from the full entity set is relatively straightforward and simple. One might argue that this is a more natural choice than in-batch negatives (although the latter may be typically used for efficiency). The main contribution, therefore, seems to be an analysis showing that global negative sampling is more amenable to DP-SGD, rather than providing a novel DP learning pipeline tailored specifically for relational learning.", "questions_to_authors": "Refer to Reasons To Reject.", "extra_scores": {}}, {"review_id": "pjWaeOOIbv", "reviewer": "Reviewer_SESE", "summary": "This paper addresses the open problem of differentially-private relational learning—training models with supervision coming from pairs or tuples of related entities (e.g. co-purchase edges) rather than independent samples. Empirical studies show improvements in relational learning tasks while maintaining robust privacy guarantees.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The authors conduct a lot of experiments, providing solid empirical validation.\n2. Efficient gradient clipping methods make the approach viable for large-scale applications", "reasons_to_reject": "1. The private guarantee is stated informally; a theorem with assumptions and proof sketch would strengthen rigor.\n2. The evaluation primarily focuses on relational prediction tasks. Broader validation across more diverse relational learning tasks might enhance the claims.", "questions_to_authors": "1. Can you provide memory and wall-clock time analysis?\n2. Can you provide theoretical analysis of privacy guarantees?\n3. Have you tried applying the pipeline to knowledge-graph completion datasets?\n4. How does decoupled negative sampling affect link-prediction recall or AUC?", "extra_scores": {}}, {"review_id": "EdYj1xTghn", "reviewer": "Reviewer_Uv6C", "summary": "This paper presents a sampling method named decoupled sampling for graph data private learning. The problem this paper aims to solve is that when applying traditional DP-SGD method to graph data, the positive sample and sampled negative sample may contain the same entities, which breaks the gradient decoupling assumptions. In the proposed decoupled sampling, the positive and negative samples are involved with different entities, which can bypass this problem. The experiments on a few datasets validate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. Graph data private learning is an important research topic.\n\n2. The proposed method seems reasonable.\n\n3. The experimental results are promising.", "reasons_to_reject": "1. The proposed method is very simple. One concern is that since the sampling process is manipulated, it is not clear whether it will bring impact on the learning outcomes. More solid theoretical analysis should be included.\n\n2. The proposed method seems designed for relation prediction. I am not sure whether it can work for other graph learning tasks, for example, sub-graph classification.\n\n3. The relation of this paper with LLM is not strong.", "questions_to_authors": "Please refer to above comments.", "extra_scores": {}}, {"review_id": "MFHZobaORq", "reviewer": "Reviewer_pMGM", "summary": "Due to efficiency, most graph neural network leverage one edge as positive and negative examples in one mini-batch. This lead to larger influence when changing one relationship. To solve this problem, the paper proposed to sample random from the whole entity set as negatives. The paper also proposes a low-rank characterization of per-sample gradient to improve computation efficiency. Many experiments has been proposed to demonstrate effectiveness of the method.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The ablation study on the tradeoff is complete. \nThe proposed method is incremental but together may provide a good solution for private learning in graph in finetuning LLMs.", "reasons_to_reject": "Section 3.3 is really hard to read for people who are unfamiliar with the domain. How does tracking tuple-level gradient influence computation cost?\nThere is no standard deviation on the benchmark. This makes me hard to judge method's performance.\nWhen the author mentioned that their methods are efficient, it is useful to show the training time comparison to demonstrate its effectiveness. The paper did mentioned the trade off but did not mention how efficient the method is compared to other methods.", "questions_to_authors": "1. Can we just simply include each relationship once in (2) to form loss function? The potential impact of changing one relationship will only impact one part of loss function then.", "extra_scores": {}}, {"review_id": "cOq8GW8mox", "reviewer": "Reviewer_qk3t", "summary": "Quality: The paper presents a high-quality contribution, offering a theoretically grounded and empirically validated method for differentially private relational learning. The approach is carefully designed to overcome limitations of existing DP training methods when applied to graph-structured data. Experiments are comprehensive and support the claims.\n\nClarity: The paper is generally well-written and easy to follow. The problem is clearly motivated, and the proposed solution is explained with appropriate use of figures and equations.\n\nOriginality: The work introduces a novel decoupling method for negative sampling to make DP-SGD applicable in relational settings, and it proposes an efficient gradient clipping technique for large-scale models. These contributions address a clear gap in both privacy and graph learning literature.\n\nSignificance: The significance is strong. The ability to privately fine-tune LLMs on graph data has wide applications in sensitive domains. The proposed method advances the field of privacy-preserving machine learning in a meaningful way.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. Novel and principled methodology: The decoupling of negative sampling for DP compatibility is elegant and effective. The custom gradient computation strategy to reduce O(KM) overhead is clever and practically necessary.\n\n2. Strong empirical results: The approach consistently improves upon baseline models while respecting differential privacy constraints.\n\n3. Scalability: Demonstrating private fine-tuning of models as large as Llama2-7B, which is non-trivial under memory and privacy constraints.\n\n4. Comprehensive analysis: Includes motivation to decouple the sampling process, empirical privacy leakage, and utility-privacy-computation trade-offs.", "reasons_to_reject": "1. Limited relation types: The paper focuses solely on binary relations. \n\n2. Dependency on graph structure: The approach assumes that relational samples can be reasonably decoupled, which might not hold in densely connected or overlapping relations.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T7y9F8sWPK", "reviewer": "Reviewer_VoeN", "summary": "This paper studies the technical difficulty of applying standard DP-SGD when training models in relational learning. The paper describes a pipeline that can provably achieve DP in learning from relational data. The main computational bottleneck of applying DP-SGD is the tuple size $k$ introduced by relational learning and the lack of support for tracking tuple-level gradients $g(E)$. The situation worsens when the relational data contain textual attributes and the target model is a language model. The paper provides experimental results to simulate common scenarios of applying relational learning in sensitive domains, where the graph data used to enhance target models contain personal or proprietary relations need to be protected. The authors choose two publicly available real-world text-attributed graphs with millions of entities/relations for the simulation: the e-commerce network from Amazon  and the academic network from Microsoft Academic Graph.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The problem statement and formalization is well-defined. \nThe proposed approach is the first for relational learning with DP.\nThe explanation of why current DP-GNNs are not sufficient to address the problem of differentially private relational learning is discussed\nThe evaluation is conducted over a data set that does seem appropriate for this model.\nOverall, the paper does a convincing job of demonstrating that LLMs can effectively learn from relational data to address relational learning tasks while providing DP.", "reasons_to_reject": "The claim that the proposed techniques for pairwise relationships can be extended easily to relational graph models is unclear, but the paper seems strong enough without this.", "questions_to_authors": "Section 3.3. could use some re-structuring to better explain the space/memory complexity of the gradient clipping approach, ideally in the form of a function pseudocode.", "extra_scores": {}}, {"review_id": "27F76R3CME", "reviewer": "Reviewer_n351", "summary": "This paper proposes a novel pipeline for differentially private relational learning using LLMs on text-attributed graphs. The core innovation lies in addressing the incompatibility of traditional DP-SGD with relational learning, where gradients inherently depend on multiple interdependent relations. The authors introduce a decoupled negative sampling strategy to isolate gradients per relation, enabling per-sample clipping and DP noise addition.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. Novelty: The paper introduces a conceptually novel and practical solution for learning from relational data with differential privacy DP, which is an area not addressed by existing DP methods.\n2. The paper is clearly written, transparent about its assumptions and limitations.\n2.The paper conducts a thorough empirical study across large-scale text-attributed graphs (Amazon and MAG), covering both zero-shot and few-shot settings for relation prediction and entity classification. It explores key hyperparameters, including negative sample size \nbatch size  and noise multiplier σ and analyzes their effects on privacy-utility trade-offs. \n3. The inclusion of membership inference attacks and statistical significance testing to quantify privacy leakage strengthens the empirical validation of the proposed approach’s privacy guarantees.", "reasons_to_reject": "1. Baseline Limitations: The experimental comparison primarily relies on a randomized response (RR) baseline and non-private fine-tuning. While the authors argue that existing DP-GNN methods are not directly applicable, they do not include even approximate or relaxed alternatives such as standard per-sample DP-SGD with entity-level privacy. Including such baseline would provide a stronger empirical foundation and better highlight the practical advantages of the proposed method.\n2. No Ablation on Core Design Choices: The contributions decoupled sampling, low-rank gradient clipping, use of LoRA are not individually ablated.\n3.  While results are shown for ϵ=4 and 10,  more continuous privacy-utility curve would strengthen claims about practical deployability.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses the important problem of differentially-private relational learning. The authors propose a method that separates the sampling of positive and negative relations and introduces an efficient tuple-level gradient clipping mechanism, enabling practical application of DP-SGD even for large-scale (7B parameters) language models. Experiments across four real-world text-attributed graphs demonstrate clear improvements over a baseline employing randomized-response under practical privacy budgets (ε ≤ 10). Privacy leakage was analyzed via membership-inference attacks, adding practical relevance to the approach.

Pros:

Clearly motivated, addressing an under-explored and significant problem relevant to private fine-tuning of large language models.

The technical contribution of decoupling negative sampling and using a low-rank gradient clipping technique provides practical scalability.

Extensive and thorough experiments illustrate robust privacy–utility–efficiency trade-offs, supported by meaningful ablations and empirical privacy analyses.

General consensus among reviewers is positive, noting methodological soundness and strong empirical validation.

Cons:

The paper lacks a formal privacy guarantee with a rigorous proof, which reviewers suggest should be included to enhance theoretical grounding.

Section 3.3, describing the tuple-level gradient approach, needs clearer presentation, possibly via pseudocode or concrete examples.

Experiments are primarily restricted to binary relations, and extending the approach to multi-relation or hyper-edge scenarios would enhance generality.

Variance and computational details (e.g., multiple runs with reported variance) are currently limited, potentially impacting reproducibility and confidence in results.

Cross-domain evaluation alone raised some reviewer concerns; including an in-domain baseline would better contextualize performance.
Decision: Accept