🤖 machine learning

Differentially Private Relational Learning with Entity-level Privacy Guarantees

Dit artikel stelt een principieel kader voor voor differentieel private relationele leerprocessen die de uitdagingen van hoge entiteitssensitiviteit en gekoppelde bemonstering aanpakt door adaptieve gradiëntclipping en uitgebreide privacy-amplificatie-analyses te introduceren, waardoor formele entiteitsniveau-privacygaranties met sterke bruikbaarheid worden bereikt.

Oorspronkelijke auteurs: Yinan Huang, Haoteng Yin, Eli Chien, Rongzhe Wei, Pan Li

Gepubliceerd 2026-02-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yinan Huang, Haoteng Yin, Eli Chien, Rongzhe Wei, Pan Li

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een computer probeert te leren hoe mensen met elkaar verbonden zijn—zoals uitzoeken wie met wie bevriend is, of welke producten vaak samen worden gekocht. Dit wordt relationeel leren genoemd. De computer leert door te kijken naar een enorme kaart van verbindingen (een graaf) waarbij stippen mensen (entiteiten) zijn en lijnen hun relaties vertegenken.

Het probleem? Deze kaarten bevatten vaak gevoelige geheimen. Misschien laat de kaart zien wie welk dokter bezocht heeft, of welke medicatie iemand heeft gekocht. Als je de computer simpelweg traint op deze gegevens, kan hij deze geheimen per ongeluk "onthouden" en ze later lekken.

Om dit te stoppen, gebruiken wetenschappers een schild genaamd Differential Privacy (DP). Denk aan DP als een "ruismachine" die statische ruis toevoegt aan het leerproces van de computer, waardoor het onmogelijk wordt om te bepalen of een specifep persoon in de trainingsdata zat of niet.

De auteurs van dit artikel ontdekten echter dat de standaard manier van het gebruiken van dit privacyschild (genaamd DP-SGD) vastloopt wanneer het wordt toegepast op deze verbindingenkaarten. Hier is waarom, en hoe ze het hebben opgelost, met behulp van eenvoudige analogieën:

De Twee Grote Problemen

1. Het "Eén Persoon, Veel Rollen"-probleem (Hoge Sensitiviteit)
In normale data is één persoon meestal slechts één datapunt. Maar in een verbindingkaart kan één persoon betrokken zijn bij tientallen relaties.

De Analogie: Stel je een leraar voor die een klas beoordeelt. In een normale klas, als één student vertrekt, mist de leraar slechts één huiswerkopdracht. Maar in deze relationele klas, als één student vertrekt, neemt diegene ook al hun groepsopdrachten, hun peer reviews en hun studiegenoten met zich mee. Plotseling verandert het cijferlijst van de leraar drastisch omdat één persoon ontbreekt.
Het Risico: Omdat één persoon zoveel delen van de wiskunde beïnvloedt, moet de "ruis" die nodig is om hen te verbergen enorm groot zijn, wat de capaciteit van de computer om nuttige dingen te leren ruïneert.

2. Het "Twee-Stappen-Dans"-probleem (Gekoppelde Steekproefverdeling)
Om de computer te leren, laten we de hele kaart niet in één keer zien. We laten hem kleine stukjes zien (mini-batches). Om zo'n stukje te maken, kiezen we eerst enkele echte verbindingen (positieve samples) en verzinnen we vervolgens enkele nepverbindingen (negatieve samples) om de computer te leren wat hij niet moet verwachten.

De Analogie: Stel je voor dat je een afspeellijst maakt. Eerst kies je 5 echte nummers die je leuk vindt. Daarna kies je, om de afspeellijst interessant te maken, 5 willekeurige nummers die je niet leuk vindt om de eerste 5 mee te vergelijken.
Het Risico: De tweede stap (het kiezen van de "niet leuk"-nummers) hangt volledig af van de eerste stap. Als je de eerste 5 nummers verandert, veranderen de tweede 5 ook. De standaard privacy-wiskunde gaat ervan uit dat deze stappen onafhankelijk zijn, alsocht het kiezen van twee aparte afspeellijsten. Omdat ze aan elkaar gekoppeld zijn, werkt de oude privacy-wiskunde niet, en weten we niet hoe veilig de data echt is.

De Oplossing: Een Slimmer Privacy-Schild

De auteurs hebben een nieuwe versie van het privacyschild gebouwd die specifiek voor deze verbindingen is gemaakt. Ze hebben de twee problemen hierboven opgelost met twee slimme trucs:

1. De "Rechtvaardige Clipper" (Adaptieve Gradiënt Clipping)
In plaats van een regel van één maat voor iedereen te gebruiken om te beperken hoeveel invloed een persoon heeft, hebben ze de regel dynamisch gemaakt.

De Fix: Als een persoon in veel relaties voorkomt in de huidige batch, "zet het systeem het volume automatisch lager" voor hun bijdrage dan normaal. Als iemand zelden voorkomt, blijft het volume normaal.
Het Resultaat: Dit houdt de wiskunde stabiel. Het voorkomt dat één populaire persoon het leerproces domineert, wat betekent dat we minder "ruis" hoeven toe te voegen om hen te beschermen. Het is als een leraar die weet dat als één student in 10 groepen zit, diegene voor het eindcijfer slechts als één student telt, en niet als tien.

2. De "Strikt Geordende Dans" (Cardinaliteit-Afhankelijke Steekproefverdeling)
Ze hebben de manier waarop ze de nepverbindingen kiezen veranderd, zodat de twee stappen van de dans slechts losjes aan elkaar verbonden zijn.

De Fix: In plaats van nepverbindingen te kiezen op basis van de specifieke echte verbindingen die zijn gekozen, kiezen ze eerst een vast aantal willekeurige mensen en koppelen die vervolgens aan elkaar.
Het Resultaat: Dit maakt de twee stappen wiskundig voorspelbaar. Het stelt de auteurs in staat om precies te bewijzen hoeveel privacy wordt gewaarborgd, ook al zijn de stappen aan elkaar gekoppeld. Het is alsof je zegt: "We zullen precies 10 willekeurige mensen kiezen voor de 'niet leuk'-lijst, ongeacht welke 5 nummers we kozen voor de 'leuk'-lijst."

De Resultaten

Het team heeft deze nieuwe methode getest op echte gegevens, specifal het finetunen van grote taalmodellen (zoals de modellen die chatbots aansturen) om relaties in netwerken van wetenschappelijke artikelen en online winkelgegevens te begrijpen.

Betere Privacy: Ze hebben wiskundig bewezen dat hun methode sterke garanties biedt dat de gegevens van een enkel persoon niet kan worden teruggevonden.
Beter Leren: Omdat hun methode niet zoveel "ruis" hoefde toe te voegen als de oude methoden, leerde de computer veel beter. Het kon relaties voorspellen (zoals "wie zal dit nu kopen") veel nauwkeuriger dan eerdere privacy-bewarende methoden.

In een Notendop

Dit artikel gaat over het leren van computers uit complexe webben van relaties zonder de geheimen van de individuen in dat web te onthullen. De auteurs realiseerden zich dat de oude privacytools te lomp waren voor deze taak, dus bouwden ze een op maat gemaakte tool die de privacyregels aanpast op basis van hoe druk een persoon is en hoe de data wordt gesampled. Het resultaat is een systeem dat geheimen veilig houdt terwijl het de computer nog steeds effectief laat leren.

Technische Samenvatting: Differentieel Private Relationele Lerning met Entiteitsniveau Privacygaranties

1. Probleemformulering

Het artikel behandelt de uitdaging van het trainen van machine learning-modellen op relationele en netwerkgestructureerde data terwijl formele entiteitsniveau (node-level) Differential Privacy (DP) garanties worden geboden. Bij relationeel leren worden modellen (zoals node-attribuut encoders) getraind om relaties (edges) tussen entiteiten (nodes) te voorspellen met behulp van contrastieve verliesfuncties.

Standaard Differentially Private Stochastic Gradient Descent (DP-SGD), ontworpen voor ongestructureerde, onafhankelijke data, kampt met twee kritieke defecten wanneer het direct wordt toegepast op relationeel leren:

Hoge Sensitiviteit: In graafdata neemt een enkele entiteit (node) vaak deel aan meerdere relaties. Als gevolg hiervan kan het verwijderen of wijzigen van een enkele node meerdere edge-tuples binnen een mini-batch veranderen, waardoor de gradiënt aanzienlijk verandert over vele termen. Dit leidt tot ongekende of excessief hoge sensitiviteit, wat een verbijsterende hoeveelheid ruis vereist om de bijdrage van de node te maskeren.
Gekoppelde Bemonstering (Coupled Sampling): Mini-batches voor relationeel leren worden doorgaans geconstrueerd via een proces met meerdere stadia: eerst het bemonsteren van positieve edges (geobserveerde relaties) en vervolgens het genereren van negatieve edges (ontbrekende relaties) onder conditie van de positieve samples. Deze interdependentie schendt de standaard DP-SGD-aanname van onafhankelijke, eenstapsbemonstering, waardoor traditionele privacy-amplificatie-analyses (die rusten op het subsampling van onafhankelijke datasets) ontoepasbaar zijn.

2. Methodologie

De auteurs stellen een op maat gemaakte DP-SGD-framework voor die drie kerncomponenten integreert om deze uitdagingen te overwinnen:

A. Adaptieve Gradiënt Clipping (FREQ-CLIP)
Om de hoge sensitiviteit aan te pakken, introduceert het artikel een adaptief gradiënt clipping-schema. In tegenstelling tot standaard clipping dat een vaste drempelwaarde $C$ gebruikt voor alle samples, past deze methode de clipping-drempelwaarde dynamisch aan op basis van de frequentie van het voorkomen van nodes binnen een mini-batch.

Mechanisme: Voor elke edge-tuple $T_i$ wordt de clipping-drempelwaarde geschaald door de maximale frequentie van elke node die in die tuple voorkomt (zowel in positieve als negatieve edges).
Effect: Dit zorgt ervoor dat de lokale sensitiviteit van de mini-batch gradiënt ten opzichte van het verwijderen van een enkele node begrensd wordt door een constante, zelfs als de node in meerdere relaties voorkomt. Specifiek begrenst het de sensitiviteit door $(1 + |B^-(u^*)|) \cdot C$ , waarbij $|B^-(u^*)|$ het aantal edge-tuples is waarin de node alleen in negatieve edges voorkomt.

B. Cardinaliteit-afhankelijke Gekoppelde Bemonstering
Om de privacy-analyse van multi-stage sampling te behandelen, formaliseren de auteurs een subclass van gekoppelde bemonstering (coupled sampling) waarbij de afhankelijkheid tussen de stadia uitsluitend voortvloeit uit steekproefomvang beperkingen (cardinality), en niet uit de specifieke inhoud van de samples.

Implementatie: Ze stellen een specifieke negatieve samplingstrategie voor (Algoritme 2: Negative Sampling Without Replacement). In dit schema worden negatieve edges geconstrueerd door nodes die onafhankelijk uit de node-set zijn gesampled te koppelen aan de eindpunten van de gesamplede positieve edges.
Voordeel: Dit ontwerp zorgt ervoor dat de negatieve samplingstap alleen afhangt van het aantal gesamplede positieve edges, niet van hun specifieke identiteiten. Deze ontkoppeling maakt het mogelijk om het complexe tweestaps-proces te analyseren als een tractabele cardinaliteit-afhankelijke bemonsteringsmechanisme.

C. Privacy-amplificatie Analyse
Het artikel leidt een rigoureuze privacy-amplificatie-bound af voor deze specifieke setting van cardinaliteit-afhankelijke gekoppelde bemonstering.

Resultaat: Ze bewijzen dat voor een samengestelde dataset waarbij de eerste fase Poisson-sampling is en de tweede sampling zonder teruglegging (afhankelijk van enkel de grootte van de eerste), de privacykosten nauwkeurig kunnen worden begrensd met behulp van Rényi Differential Privacy (RDP).
Integratie: Door de adaptieve clipping (die de sensitiviteit begrenst) te combineren met de specifieke samplingstrategie (die de amplificatie-bound mogelijk maakt), bieden de auteurs een bewijsbaar $(\alpha, \epsilon(\alpha))$ -RDP-garantie voor het gehele trainingsproces.

3. Belangrijkste Bijdragen

Sensitiviteitsanalyse & Adaptieve Clipping: Een rigoureuze analyse van gradiënt-sensitiviteit in relationeel leren, leidend tot een frequentie-gebaseerd adaptief gradiënt clipping-algoritme dat de sensitiviteit effectief controleert zonder uit te gaan van een worst-case node-graad.
Formalisering van Gekoppelde Bemonstering: De uitbreiding van de privacy-amplificatie-theorie naar een tractabele subclass van gekoppelde bemonstering waarbij afhankelijkheden beperkt zijn tot steekproefomvang, wat de eerste amplificatie-bounds biedt voor deze setting.
Op Maat Gemaakte DP-SGD Variant: Een volledig algoritme (Algoritme 3) dat degree capping, adaptieve clipping en cardinaliteit-afhankelijke bemonstering integreert om entiteitsniveau privacygaranties te bereiken.
Empirische Validatie: Demonstratie van de effectiviteit van de methode bij het fine-tunen van pre-trained tekst-encoders (bijv. BERT, Llama2) op tekst-geattributueerde netwerken voor zero-shot relatievoorspelling.

4. Experimentele Resultaten

De auteurs evalueerden hun methode op tekst-geattributueerde netwerkdatasets (MAG citatienetwerken en Amazon co-purchase netwerken) met als doel de encoders te fine-tunen voor relatievoorspelling.

Privacy Bounds: Numerieke analyse van de afgeleide RDP-bounds (Eq. 3) laat zien dat de voorgestelde methode aanzienlijk nauwere privacy-bounds bereikt vergeleken met naïeve Gaussische mechanismen en standaard DP-SGD met vaste clipping.
Utility-Privacy Trade-off: In relatievoorspellings-taken (gemeten via PREC@1 en MRR) presteert de voorgestelde methode consistent beter dan:
- Niet-private fine-tuning (zoals verwacht, maar met privacygaranties).
- Niet-gefine-tuned basismodellen.
- Standaard DP-SGD met vaste gradiënt clipping onder dezelfde privacy-budgetten ( $\epsilon = 4$ en $\epsilon = 10$ ).
Ablatie-studies: Experimenten geven aan dat het verhogen van het aantal negatieve samples per positieve edge en de gecapte node-graad over het algemeen de bruikbaarheid (utility) van het model verbetert onder vaste privacy-restricties.

5. Betekenis en Claims

Het artikel claimt het eerste principiële framework te bieden voor entiteitsniveau differentieel private relationele lerning dat formele garanties biedt. De betekenis ligt in:

Het Overbruggen van de Kloof: Het adresseert de specifieke structurele uitdagingen van graafdata (hoge sensitiviteit en gekoppelde bemonstering) die de directe toepassing van standaard DP-SGD verhinderen.
Theoretische Rigor: Het gaat verder dan heuristische toepassingen van DP op grafen door een rigoureuze sensitiviteitsanalyse en een nieuw privacy-amplificatie-theorema voor afhankelijke bemonsteringsprocessen te bieden.
Praktische Bruikbaarheid: Het demonstreert dat strikte entiteitsniveau privacy kan worden gehandhaafd zonder catastrofaal verlies in modelprestaties, wat het levensvatbaar maakt voor gevoelige domeinen zoals de gezondheidszorg en de financiële sector waar relationele data veel voorkomt.

De auteurs benadrukken dat hun aanpak het mogelijk maakt om fundamentele modellen te fine-tunen op relationele data terwijl de privacy van individuele entiteiten wordt beschermd, een capaciteit die voorheen werd gehinderd door het gebrek aan geschikte privacy-mechanismen voor gekoppelde, relationele bemonstering.