Privately Learning from Graphs with Applications in Fine-tuning Large Language Models

We sincerely thank the reviewer for the strong support in accepting our work and for recognizing the novelty and effectiveness of our proposed method for private relational learning. In Sec. 3, we list the general formulation of relational learning, Eq. (1), where multiple types of loss functions are compatible with our pipeline, including the Hinge loss that supports different relation types commonly used for learning from knowledge graphs. We acknowledge that the effort on such an extension is non-trivial, and thus this is left for future study. We thank the reviewer for the suggestion on revising Sec. 3.3. We will incorporate all the discussions and reorganize the complexity analysis of per-tuple gradient clipping, paired with appropriate pseudocode in the final version.

We thank the reviewer for recognizing the novelty of our work in addressing relational learning with DP and the completeness of our empirical study. We address the three concerns below:

Q1 Baseline Limitations

We thank the reviewer for this suggestion. Our work is among the first to provide strict ($\epsilon, \delta$)-DP guarantees for individual relations in a relational learning context. Consequently, Randomized Response (RR) is one of the few existing mechanisms that can be adapted to offer a comparable relation-level DP guarantee, forming our primary baseline.

Regarding the suggestion of 'standard per-sample DP-SGD with entity-level privacy' as an approximate baseline, it's not immediately apparent to us how standard entity-level DP-SGD could be straightforwardly adapted to serve as an 'approximate or relaxed' baseline for our relation-level privacy during the relational supervision phase. Even if entity embeddings were produced with entity-level DP, the core challenge studied in our work would persist: the interdependent gradients arising from relational loss terms (e.g., a positive relation contrasted with several negatives in one loss computation). Our decoupled sampling method is specifically designed to handle this issue for the supervisory loss.

Concerning existing DP-GNN methods: As we discuss in Appendix A.1, these approaches typically focus on privatizing the GNN encoding process (i.e., message passing or node feature aggregation) primarily for tasks like node classification under node-level DP. They do not directly address the problem of ensuring DP for the relational learning objective function itself, where the supervision comes from relations. We are not aware of a simple adjustment to these DP-GNN techniques that would make them directly applicable to our problem of privacy-preserving relational supervision with relation-level DP guarantees.

Q2 No Ablation on Core Design Choices.

We thank the reviewer for pointing this out. We conducted the ablation studies on critical hyperparameters and privacy parameters in Sec. 4.2 (see Figs. 2 and 4). Additionally, we address the following points below.

• We added the ablation study of decoupled sampling of Table R1 (see the response to Reviewer SESE's Q4).
• For efficient per-tuple gradient clipping, the proposed technique is mathematically equivalent to the conventional method of aggregating per-token gradients, which does not affect the result accuracy but substantially saves the memory cost of privacy computing, as detailed in Sec. 3.3 lines 249-252. We added the comparison of these two methods and presented the results in Table R2 (see the response to Reviewer pMGM's Q3).
• The comparison of non-private and private fine-tuning is conducted over models all with LoRA, due to resource constraints and the intensity of privacy computing for large pretrained models. Meanwhile, we do not observe an obvious performance gap between full parameter fine-tuning and LoRA for BERT-based models in non-private fine-tuning.

Q3 ... more continuous privacy-utility curve would strengthen claims about practical deployability.

We appreciate this suggestion. In Figure 2 (Right), we plot the model performance (MRR) against a range of noise multipliers ($\sigma$) for two datasets. Each distinct noise multiplier $\sigma$ corresponds to a specific ($\epsilon,\delta$)-DP guarantee, with smaller $\sigma$ values leading to larger $\epsilon$ (less privacy) and larger $\sigma$ values leading to smaller $\epsilon$ (more privacy). This plot already provides 5-6 points across this spectrum for each dataset, illustrating the privacy-utility trade-off trend, including and extending beyond the specific $\epsilon\approx 4$ and $\epsilon\approx 10$ values highlighted in other tables. We believe this captures the general behavior effectively. For instance, on MAG-USA, the $\sigma$ values range from approximately 0.2 to 0.5, corresponding to a wide spectrum of $\epsilon$ values. We can add the specific $\epsilon$ values for each point to the figure's caption or an appendix table for enhanced clarity if the reviewer suggests.

We sincerely thank the reviewer for their strong support and positive evaluation, particularly for recognizing the novelty, significance, and empirical strength of our work. We address the two minor points raised:

Limited Relation Types

We appreciate this observation. While our experiments primarily focus on pairwise relations to demonstrate the core methodology, our approach is designed to be extensible. As discussed in Section 3 (lines 155-158), the principle of decoupled negative sampling and tuple-level gradient clipping can potentially be applied to more complex relational structures, such as knowledge graph triplets, network motifs, or hyperedges. Given that our current empirical studies on pairwise relations already provide substantial support for the method's effectiveness in private relational learning, we consider the extension to other relation types a promising direction for future work.

Dependency on Graph Structure

Thank you for pointing out the potential influence of graph structure. The concern that decoupled negative sampling might inadvertently select true positive pairs as negatives, especially in dense graphs, is valid. However, several factors mitigate this: (1) Sparsity of Real-World Graphs: Many real-world graphs, including those used in our experiments (with densities ranging from 1.58×10−5 to 5.01×10−6 as derived from Table 4 data), are inherently sparse. In such cases, the probability of randomly sampling an existing positive partner as a negative is quite low. (2) Empirical Utility: Our experiments (Tables 1, 2, and 8) demonstrate strong utility, suggesting that this issue does not significantly degrade performance in practice. This aligns with our note in footnote 1 (line 204) that "no obvious harm to utility is observed in practice."

We thank the reviewer for recognizing the effectiveness of our proposed solution and the completeness of our experiments. We feel sorry for the induced confusion in Sec. 3.3 and will revise it for improved clarity in the final version. We address the reviewer’s concerns and questions below:

Q1 How does tracking tuple-level gradient influence computation cost?

Our primary innovation for tuple-level gradients addresses the significant memory overhead typically associated with per-sample gradients in relational learning. As detailed in Sec. 3.3 (lines 252-256), a naive approach would require caching $O(KM)$ gradient copies per loss term, leading to $O(KMpd)$ memory. Our proposed method (lines 249-252) reduces this to $O(KM(p+d)+pd)$. For large models where the parameter cost $pd$ is substantial, this is a memory saving of approximately a factor of $KM$, making the approach feasible. Once this memory bottleneck is addressed, the computational time for processing a tuple and performing the backward pass to get the aggregated per-tuple gradient becomes efficient. The sum over tokens and entities (as described by $ra^T$ in lines 251-252) is a batched matrix multiplication. The subsequent clipping and noise adding are standard. Thus, the primary drivers of training time per step become the model size, batch size, and sequence length, similar to standard DP training on non-relational data, rather than being prohibitively inflated by the K entities in a tuple.

Q2 There is no standard deviation on the benchmark.

We acknowledge the reviewer's preference for standard deviations. Given the significant computational resources and time required for privately fine-tuning LLMs (up to 7B parameters in our work, as noted in lines 91-93), reporting error bars was unfortunately infeasible through multiple full training runs for each experimental setting. This is a common challenge in the field, and several prior works on private LLM fine-tuning also present results from single runs (e.g., Li et al., 2021; Yu et al., 2022). We ensured our hyperparameter tuning was thorough (Appendix D, Table 6) to find stable optimal performance for the presented results.

Q3 ...show the training time comparison to demonstrate its effectiveness.

Our method's main efficiency gain is a significant reduction in GPU memory usage, which is critical for the practicality of fine-tuning large models on relational data with DP. As detailed in Sec. 3.3 (lines 252-256), a naive per-token gradient approach would incur $O(bKMpd)$ memory per batch, whereas our per-tuple gradient computation reduces this to $O(bKM(p+d)+bpd)$. This represents an approximate memory saving factor of $KM$, which is substantial. This memory efficiency makes it feasible to train large models like Llama2-7B on relational data with DP, which would otherwise be impractical due to out-of-memory (OOM) errors.

Regarding direct training time comparisons with 'other methods':

• Baseline Infeasibility: A direct comparison to a naive DP approach for relational learning that materializes all $O(KM)$ intermediate gradients (the 'Aggregating per-token gradients' baseline) is impossible for LLMs, as it would quickly lead to OOM errors, preventing completion of training or even single steps at reasonable batch sizes.
• Throughput: Our method's efficiency enables practical batch sizes, leading to improved training throughput compared to what would be achievable if one were forced to use extremely small batches with a naive memory-intensive approach. For example, with Llama2-7B (parameters d=4096,p≈4096 or 32000), K$\in$[10,34], and M=32 (lines 254-255), the KM factor is significant.

Instead of direct time, the crucial benefit is feasibility and the ability to use batch sizes large enough for effective DP training (as larger batches improve the signal-to-noise ratio, lines 393-396). We add the Table R2 below with concrete memory usage from our experiments using Llama2-7B with our method v.s. the projected usage for a naive approach, and report the achieved training throughput to illustrate this point.

Q4 Can we just simply include each relationship once in (2) to form loss function?

We assume “include each relationship once in (2)” refers to only including a positive or negative relation for a loss term, which reduces the problem to a standard case for private learning. However, without pairing positive and negative relations in a tuple, the model cannot effectively capture the relational pattern and is prone to drifting due to biased signals. We observed that the model often collapses when only one relationship is included in the loss in a non-private setting, and our study on the impact of negative samples in Fig. 2 is also consistent with such an observation.

We thank the reviewer for acknowledging the importance of our study and the effectiveness of our solution. We address three concerns as follows:

Q1 ... the sampling process is manipulated, it is not clear whether it will bring impact on the learning outcomes.

We appreciate the reviewer's concern about the potential impact of decoupled negative sampling on learning outcomes. Empirically, we address this by comparing decoupled sampling with standard in-batch negative sampling in a non-private setting. We will include these results (see Table R1 in response to Reviewer SESE's Q4) in the revised Appendix. These results show that decoupled sampling achieves comparable utility, indicating no significant adverse impact on learning outcomes (consistent with our observation in footnote 1, line 204).

From a learning perspective, sampling negative relations from the entire entity set $V$ is a well-established strategy in representation learning to provide diverse negative examples for contrastive-style losses. While our primary motivation for this choice is its necessity for enabling relation-level DP (as it decouples dependencies), our experiments (Tables 1 & 8) demonstrate that this 'manipulation' for privacy does not unduly compromise the model's ability to learn relational patterns effectively. A deeper theoretical analysis of the utility trade-offs of different negative sampling strategies under DP could be an interesting direction for future work.

Q2 I am not sure whether it can work for other graph learning tasks, for example, sub-graph classification.

Our proposed method achieves a privacy guarantee of individual relations used for relational learning, which injects structural and contextual patterns of relational data into model weights, as formulated in Sec. 3, lines 138-158. We demonstrate the effectiveness of our pipeline in two types of tasks: relation prediction and entity classification.

Our method can potentially be used for subgraph-level tasks through the readout of entity embeddings of a given subgraph, which provides a relation-level DP. To achieve DP for each individual subgraph, standard DP-SGD can be directly applied for subgraph classification.

Q3 The relation of this paper with LLM is not strong.

We respectfully disagree with the reviewer’s comment, as language models are integral to our work's motivation, methodology, and findings.

1. Leveraging LLM Capabilities: Our approach is designed to fine-tune LLMs (like BERT and Llama2 ) using sensitive graph data. We specifically leverage their strong ability to understand and generalize from the entity's textual attributes to learn relational patterns, especially in challenging cross-domain scenarios (Sec. 4.1) where interpreting rich text is paramount. This can be particularly advantageous compared to models that might not capture nuanced textual semantics as effectively.
2. Methodological Adaptations for LLMs: A core part of our technical contribution is the efficient gradient clipping method (Sec. 3.3), which is specifically designed to handle the computational complexities of applying DP-SGD to LLMs in a relational learning context (involving K entities, each with M tokens). This makes private fine-tuning of large models like Llama2-7B feasible.
3. Extending Private LLM Research: Our work is among the first to systematically investigate privacy-preserving fine-tuning of LLMs specifically for relational learning tasks, extending the body of research on private LLM (which has largely focused on standard non-relational text data) to this new, important domain. We also provide extensive analysis on the privacy, utility, and efficiency trade-offs in this specific context.

We believe these aspects together demonstrate a strong and critical connection to LLMs throughout our research.

We thank the reviewer for recognizing the significance of our work and for the detailed and constructive feedback. We address three concerns as follows:

[Q1] We thank the reviewer for this insightful question, which touches upon a subtle but important aspect of defining differential privacy for relational data.

The reviewer's concern is about the potential change in the entity set $V$ if an entity is unique to an added or removed relation, and how this might affect negative sampling. Our work, as defined in Sec. 3.1, focuses on relation-level DP, where two relation sets $E$ and $E'$ are considered adjacent if one can be obtained from the other by adding or removing a single relation. Critically, for this definition of adjacency, the underlying entity set V is assumed to be fixed. The privacy guarantee pertains to the indistinguishability of models trained on $E$ v.s. $E’$, where only one relation differs, not the entities themselves. This is a common setup when defining relation (edge)-level DP in graph settings.

Thus, when we add or remove a positive relation $e\in E$ (to define adjacent datasets for DP), the overall entity set $V$ (from which negatives are sampled) does not change. Our decoupled negative sampling, which samples negatives uniformly from the set $V$, is designed to be independent of the set $E$ (beyond the specific positive relation in a tuple). This independence is key to ensuring that perturbing one relation $e_i^+$ affects at most one tuple $E_i$ in the mini-batch, allowing DP-SGD to be correctly applied. The dependency on the global entity set $V$ for negative sampling does not violate relation-level DP because $V$ is constant across adjacent relation sets.

We acknowledge that defining DP at the entity level is a different and more complex setting, which is beyond the scope of this work. Our experiments demonstrate that robust relational learning is achievable under our proposed relation-level DP framework. We hope this clarifies the definition of adjacency used and how our negative sampling strategy is compatible with it. We will add the above discussion in Sec. 3.1 to improve clarity.

[Q2] We appreciate the reviewer's perspective and suggestion on the experimental design. While within-domain evaluation is indeed valuable for assessing certain aspects of model performance, our cross-domain setup was a deliberate choice, designed to test a more challenging and practically relevant form of generalization, especially under privacy constraints. Our motivation, as outlined in Sec. 4 (lines 261-273), is to simulate real-world scenarios, e.g., 'cross-category co-purchase recommendation' and 'cross-regional model deployment.' In these situations:

1. Disjoint Data is Realistic: Entities and their specific relationships are often entirely disjoint between, e.g., different product departments or different operational regions.
2. Privacy is Paramount for Sharing: The need for DP often arises precisely because sensitive relational data from one domain cannot be directly shared or used to train models for another, even if within-domain data might have fewer sharing restrictions. Our setup directly reflects this challenge.
3. Transfer of Abstract Knowledge: We aim for the model to learn transferable relational patterns or the underlying knowledge of forming relations from textual attributes, rather than memorizing specific entity-relation instances. For example, an LLM might learn how language describing certain types of products often links to co-purchase relations, even if the products themselves are from different categories. The disjoint nature of entities/relations in our setup rigorously tests this ability to generalize abstract relational knowledge.

[Q3] We agree with the reviewer that sampling negatives from the entity set is conceptually straightforward. However, our contribution is not this specific sampling method alone, but rather the study of this complete and theoretically sound privacy-preserving pipeline for relational learning, which has been previously unaddressed. Our key contributions are:

1. Identifying the DP Challenge: We first pinpoint why common negative sampling methods (e.g., in-batch) are incompatible with DP-SGD in relational learning due to coupled dependencies.
2. A DP-Compatible Solution: We propose a pipeline that uses decoupled negative sampling to enable correct DP-SGD application. This involves tuple-level gradient clipping and noising to protect individual relations.
3. Efficient Implementation for LLMs: Crucially, we introduce a tailored, efficient gradient computation method (Sec. 3.3) that makes this approach practical for large models like LLMs by exploiting low-rank gradient structures, which is essential given the setting of multiple entities per tuple.
4. Rigorous Validation: We provide extensive experiments demonstrating our pipeline's superior utility, assess privacy empirically via MIAs, and analyze practical trade-offs.

We thank the reviewer for recognizing our work addressing the open problem of private relational learning with thorough experimentation and appreciating our practical solution for large-scale applications. We clarify the questions as follows:

Q1 Can you provide memory and wall-clock time analysis?

We provide an analysis of memory complexity savings in Section 3.3 (lines 253-259), where we show our method reduces memory cost by a factor of approximately $O(KM)$ compared to a naive approach. This memory efficiency is crucial for the feasibility of training LLMs on relational data with DP. Below, we provide representative GPU VRAM usages (with batch size $b=32$ relation tuples) and achieved training throughputs from our experiments.

Q2 Can you provide theoretical analysis of privacy guarantees?

With our decoupled negative sampling, the proposed pipeline Alg. 3 in Appendix C achieves ($\epsilon, \delta$)-DP for individual training relation, which is formally defined in Sec. 3.1, lines 162-164. Specifically, the decoupled sampling ensures the sensitivity of the batch gradients is bounded regardless of batch size $b$, i.e., at most one relation tuple would be affected when one relation is added or removed from the relation set $E$. The tuple-level gradient clipping further limits the sensitivity to a constant $C$. We will formalize this analysis into a proposition in our revised version.

Based on the Gaussian mechanism, each parameter update from batch gradient with added Gaussian noise in Alg. 3 achieves DP. Lastly, we leverage the composition theorem (Balle & Wang, 2018) to account for the total privacy loss over T training steps, and convert it to ($\epsilon, \delta$)-DP. The privacy loss $\epsilon$ on each relational dataset used for training is reported in Table 9, Appendix E.

Q3 Have you tried applying the pipeline to knowledge-graph completion datasets?

We haven’t applied our pipeline to KG completion tasks, even though our method can be extended to KG for relational learning as discussed in Sec. 3, lines 151-155. Our current empirical studies have sufficiently supported the effectiveness of our proposed method for private relational learning. We thank the reviewer for pointing out this direction, and it would be great to explore in the KG setting for future work.

Q4 How does decoupled negative sampling affect link-prediction recall or AUC?

We evaluate link prediction using PREC@1 and MRR, which are common ranking metrics for these tasks, focusing on the accuracy of top-ranked predictions. In our experiments (and as noted in footnote 1, line 204), we found that decoupled negative sampling (sampling negatives randomly from the entire entity set $V$) achieves comparable utility to standard in-batch negative sampling in a non-private setting, without the obvious harm to performance that might be feared from its 'simplicity.'

To provide a direct comparison as requested, the following table (Table R1) shows results using our primary metrics for these two negative sampling strategies (both in a non-private training setting to isolate the effect of the sampling strategy itself):