Acyclic Graph Pattern Counting under Local Differential Privacy

Titel: Acyclische Grafpatroon-telling onder Lokale Differentiële Privacy

Auteurs: Yihua Hu, Kuncan Wang en Wei Dong (Nanyang Technological University, Singapore)
Publicatie: Proc. ACM Manag. Data (SIGMOD), Juni 2026

---

1. Probleemstelling

Het tellen van grafpatronen (zoals paden, sterren of bomen) is fundamenteel voor netwerkanalyse, met toepassingen in gemeenschapsdetectie, fraudeopsporing en netwerkkarakterisering. Echter, het vrijgeven van dergelijke analyseresultaten vormt een groot privacyrisico, aangezien tegenstanders gevoelige informatie over knopen of randen kunnen afleiden.

Om dit te adresseren wordt Lokale Differentiële Privacy (LDP) gebruikt. In tegenstelling tot centrale DP (waar een vertrouwde curator de data heeft), privatiseert elke knoop in een gedecentraliseerd netwerk zijn eigen lokale data (zijn incidentele randen) voordat deze naar een analyzer wordt gestuurd.

De uitdagingen:
Bestaande LDP-oplossingen zijn vaak specifiek voor eenvoudige patronen zoals sterren of driehoeken. Er ontbreekt een algemene methode voor het tellen van willekeurige acyclische patronen (patronen zonder cycli, zoals paden of bomen) onder edge-LDP (privacy op randniveau). De twee fundamentele problemen zijn:

1. Generalisatie van patroonconstructie: Bestaande methoden zijn te specifiek voor bepaalde structuren en kunnen niet eenvoudig worden uitgebreid naar complexe, willekeurige acyclische patronen.
2. Eliminatie van knoopduplicatie: In een acyclisch patroon mogen alle knopen uniek zijn. In een gedecentraliseerde LDP-setting is het echter moeilijk voor een enkele knoop om te detecteren of een knoop al eerder in het patroon is gebruikt, omdat het geen globaal overzicht heeft.

Een simpele aanpak (zoals het gebruik van Warner's Randomized Response om een ruisig globaal graf te reconstrueren) leidt tot een zeer hoge foutmarge ($O(N^k)$), wat onpraktisch is voor grote netwerken.

2. Methodologie

De auteurs stellen een algemeen raamwerk voor dat twee hoofdstappen combineert: een recursieve tellingsstrategie en een "random marking" techniek.

A. Recursieve Subpatroon-telling (voor Walks)

Om complexe patronen te tellen, breken ze het probleem op in kleinere stappen.

• Kernidee: In plaats van direct het volledige patroon te tellen, tellen ze eerst het aantal "wandelingen" (walks) van lengte $k$. Een wandeling is een reeks knopen verbonden door randen, waarbij herhaling van knopen is toegestaan (in tegenstelling tot paden).
• Meerdere rondes: Het mechanisme werkt in $k-1$ communicatierondes.
  • In ronde 0 start elke knoop met een telling van 1.
  • In elke volgende ronde $\ell$, verzamelt een knoop de tellingen van wandelingen van lengte $\ell-1$ die bij zijn buren eindigen.
  • De knoop sommeert deze waarden, voegt Laplace-ruis toe (voor privacy) en publiceert het resultaat.
• Privacy: De ruis wordt geschaald op basis van de maximale telling uit de vorige ronde (in plaats van een vaste clip-threshold), wat de nuttigheid verbetert. Het privacybudget $\varepsilon$ wordt verdeeld over de rondes.

B. Random Marking (voor Pad-telling en Acyclische Patronen)

Om het probleem van knoopduplicatie op te lossen (zodat een wandeling een geldig pad of acyclisch patroon wordt), gebruiken ze een techniek geïnspireerd op "color-coding".

• Mechanisme: Elke knoop krijgt een willekeurige "markering" (een getal $r_i$) toegewezen uit $\{0, 1, ..., k\}$.
• Beperking: Een knoop mag in een tellend proces alleen optreden op de positie die overeenkomt met zijn markering. Bijvoorbeeld, een knoop met markering 0 mag alleen het startpunt zijn; een knoop met markering 1 mag alleen de tweede knoop zijn, enzovoort.
• Effect: Dit garandeert dat een knoop nooit twee keer in hetzelfde patroon voorkomt, omdat hij maar één specifieke positie mag innemen.
• Schatting: Omdat niet alle knopen de juiste markering krijgen voor een specifiek patroon, wordt het resultaat later vermenigvuldigd met een correctiefactor ($(k+1)^{k+1}$) om een onbevooroordeelde schatting te krijgen.

C. Uitbreiding naar Willekeurige Acyclische Patronen

Voor algemene acyclische patronen (die geen lineaire paden hoeven te zijn) wordt het patroon eerst omgezet in een boomstructuur met een gedefinieerde volgorde (van bladeren naar wortel). Het recursieve tellingsproces wordt dan toegepast op deze boom, waarbij de "random marking" techniek zorgt voor de uniciteit van de knopen.

3. Belangrijkste Bijdragen

1. Eerste algemene oplossing: Dit is het eerste mechanisme dat willekeurige acyclische grafpatronen kan tellen onder edge-LDP.
2. Verbeterde Foutmarge: Het mechanisme bereikt een additieve fout van $\tilde{O}(\sqrt{N} \cdot d(G)^k)$, waarbij $N$ het aantal knopen is en $d(G)$ de maximale graad. Dit is een aanzienlijke verbetering ten opzichte van de $O(N^k)$ fout van eerdere RR-gebaseerde methoden.
3. Efficiëntie:
   • Communicatie: De totale communicatiekosten zijn $O(M + N)$ (waarbij $M$ het aantal randen is), in plaats van $O(N^2)$.
   • Berekening: De berekeningskosten per knoop zijn $O(d(G))$ en voor de analyzer $O(N)$.
4. Unbiased Schatting: Het mechanisme levert een onbevooroordeelde schatting op, wat cruciaal is voor nauwkeurige analyse.

4. Resultaten

De auteurs hebben hun methode getest op zes real-world datasets (o.a. AstroPh, Enron, Twitter) en vergeleken met state-of-the-art baselines (zoals RR-based enumeratie en WalkClip).

• Nuttigheid (Utility):
  • Voor $k$-lijn wandelingen: Relatieve fout < 8% op alle datasets.
  • Voor paden en acyclische patronen: De methode toont een verbetering in nuttigheid van 46x tot 2600x ten opzichte van de baselines.
  • Voor ster-tellingen: Relatieve fout < 0,5% en een verbetering van tot 710x.
• Communicatiekosten:
  • Er is een reductie in communicatiekosten van 300x tot 650x vergeleken met de RR-baselines.
  • De kosten blijven stabiel en laag, zelfs voor grotere patronen ($k$), dankzij de lokale communicatie tussen buren in plaats van globale broadcasts.
• Privacy Budget: De prestaties verbeteren naarmate het privacybudget $\varepsilon$ toeneemt, maar zelfs bij lage $\varepsilon$ (bijv. 0,2) blijft de methode superieur.

5. Betekenis en Impact

Deze studie vult een belangrijke lacune in de privacy-wetenschap. Het biedt een schaalbare, algemene oplossing voor een van de meest fundamentele problemen in netwerkanalyse (patroontelling) zonder in te leveren op privacy.

• Praktische toepasbaarheid: De methode is geschikt voor gedecentraliseerde omgevingen (zoals sociale netwerken over verschillende platforms) waar geen centrale trust is.
• Theoretische doorbraak: Het bewijst dat het mogelijk is om complexe, niet-lokale grafpatronen te tellen onder LDP met een foutmarge die slechts een factor $\sqrt{N}$ en een polynoom in de graad $d(G)$ afwijkt van het ideale geval, in plaats van exponentieel in $N$.
• Toekomstige richting: De auteurs wijzen op cyclische patronen (zoals driehoeken of kringen) als een volgende uitdaging, aangezien deze niet recursief kunnen worden opgebouwd op dezelfde manier als acyclische patronen.

Kortom, dit werk zet een nieuwe standaard voor privacy-bewuste grafanalyse in gedecentraliseerde systemen.