2025-11-18T15:58:13.889736

A Survey of Graph Unlearning

Said, Tran, Zhao et al.
Graph unlearning emerges as a crucial advancement in the pursuit of responsible AI, providing the means to remove sensitive data traces from trained models, thereby upholding the \textit{right to be forgotten}. It is evident that graph machine learning exhibits sensitivity to data privacy and adversarial attacks, necessitating the application of graph unlearning techniques to address these concerns effectively. In this comprehensive survey paper, we present the first systematic review of graph unlearning approaches, encompassing a diverse array of methodologies and offering a detailed taxonomy and up-to-date literature overview to facilitate the understanding of researchers new to this field. To ensure clarity, we provide lucid explanations of the fundamental concepts and evaluation measures used in graph unlearning, catering to a broader audience with varying levels of expertise. Delving into potential applications, we explore the versatility of graph unlearning across various domains, including but not limited to social networks, adversarial settings, recommender systems, and resource-constrained environments like the Internet of Things, illustrating its potential impact in safeguarding data privacy and enhancing AI systems' robustness. Finally, we shed light on promising research directions, encouraging further progress and innovation within the domain of graph unlearning. By laying a solid foundation and fostering continued progress, this survey seeks to inspire researchers to further advance the field of graph unlearning, thereby instilling confidence in the ethical growth of AI systems and reinforcing the responsible application of machine learning techniques in various domains.
academic

Eine Übersicht über Graph Unlearning

Grundlegende Informationen

  • Paper-ID: 2310.02164
  • Titel: A Survey of Graph Unlearning
  • Autoren: Anwar Said, Ngoc N. Tran, Yuying Zhao, Tyler Derr, Mudassir Shabbir, Waseem Abbas, Xenofon Koutsoukos
  • Klassifizierung: cs.LG (Maschinelles Lernen)
  • Veröffentlichungsdatum: arXiv Oktober 2023 (neueste Version 14. Oktober 2025)
  • Paper-Link: https://arxiv.org/abs/2310.02164

Zusammenfassung

Graph Machine Unlearning (Graph-Maschinenvergessenheit) stellt als Schlüsseltechnologie in der Entwicklung verantwortungsvoller KI ein Mittel dar, um Spuren sensibler Daten aus trainierten Modellen zu entfernen und damit das "Recht auf Vergessenwerden" zu wahren. Angesichts der Empfindlichkeit des Graph-Maschinenlernens gegenüber Datenschutz und adversarialen Angriffen wird die Anwendung von Graph-Unlearning-Techniken zur wirksamen Bewältigung dieser Probleme besonders notwendig. Diese Übersichtsarbeit bietet die erste systematische Überprüfung von Graph-Unlearning-Methoden, umfasst vielfältige methodische Ansätze und bietet eine detaillierte Taxonomie sowie einen Überblick über die aktuelle Literatur, um Neulingen in diesem Forschungsbereich Orientierung zu geben. Um Klarheit zu gewährleisten, werden grundlegende Konzepte und Bewertungsmetriken des Graph Unlearning klar erläutert und für ein breites Publikum mit unterschiedlichem Fachwissen aufbereitet.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Datenschutzanforderungen: Mit der Umsetzung von Datenschutzbestimmungen (wie GDPR, CCPA) haben Einzelpersonen das Recht, die Löschung ihrer Daten aus Maschinenlernmodellen zu fordern
  2. Komplexität von Graphdaten: Die gegenseitige Abhängigkeit von Knoten und Kanten in Graphstrukturdaten macht das einfache Löschen von Daten schwierig, da Informationen durch Nachrichtenübermittlungsmechanismen zu entfernten Knoten propagiert werden
  3. Schutz vor adversarialen Angriffen: Notwendigkeit, böswillig eingefügte Daten aus dem Modell zu entfernen, um die Systemintegrität zu wahren
  4. Unzulänglichkeit bestehender Methoden: Traditionelle Maschinenlern-Unlearning-Methoden können nicht direkt auf Graphstrukturdaten angewendet werden

Forschungsbedeutung

  • Rechtliche Compliance: Erfüllung von Anforderungen der Datenschutzbestimmungen
  • Datenschutz: Schutz persönlicher sensibler Informationen vor Modelloffenlegung
  • Sicherheitsschutz: Abwehr von Daten-Poisoning und anderen adversarialen Angriffen
  • Ethische KI: Förderung der Entwicklung verantwortungsvoller KI-Systeme

Bestehende Einschränkungen

  • Mangel an systematischer Übersicht über Graph-Unlearning-Methoden
  • Die vernetzte Natur von Graphdaten macht vollständiges Vergessenwerden komplex
  • Schwierige Abwägung zwischen Effizienz und Vollständigkeit
  • Mangel an einheitlichen Bewertungsstandards

Kernbeiträge

  1. Erste systematische Übersicht: Bietet die erste umfassende systematische Überprüfung des Graph-Unlearning-Bereichs
  2. Detaillierte Taxonomie: Klassifiziert Graph-Unlearning-Methoden in zwei Hauptkategorien: Exaktes Unlearning (Exact Unlearning) und Approximatives Unlearning (Approximate Unlearning)
  3. Umfassende Anwendungsanalyse: Erörtert die Anwendung von Graph Unlearning in mehreren Bereichen wie sozialen Netzwerken, Empfehlungssystemen und medizinischen Netzwerken
  4. Bewertungsrahmen: Bietet Methoden zur Bewertung von Vergessenskompletheit, Effizienz und Modellnutzen
  5. Zukünftige Richtungen: Weist auf mehrere vielversprechende Forschungsrichtungen hin

Methodische Details

Aufgabendefinition

Grundkonzepte

  • Graphdefinition: G = (V, E, X, Xe), wobei V die Knotenmenge ist, E die Kantenmenge, X die Knotenfeature-Matrix und Xe die Kantenfeature-Matrix
  • Vergessensset: S ⊆ D, das die Teilmenge der Daten darstellt, die vergessen werden soll
  • Ziel: Aktualisierung der Modellparameter θ, so dass die Leistung der Umschulung auf D\S entspricht

(ε, δ)-Vergessens-Definition

Für einen festen Datensatz D, ein Vergessensset S und einen randomisierten Lernalgorithmus A ist ein Vergessensalgorithmus U (ε, δ)-vergessend, wenn und nur wenn für alle R ⊆ R:

Pr[A(D \ S) ∈ R] ≤ e^ε Pr[U(A(D), S, D) ∈ R] + δ
Pr[U(A(D), S, D) ∈ R] ≤ e^ε Pr[A(D \ S) ∈ R] + δ

Klassifizierung von Graph-Unlearning-Typen

1. Transduktives Unlearning (Transductive)

  • Knoten-Unlearning: Entfernung spezifischer Knoten und aller ihrer Verbindungen
  • Kanten-Unlearning: Entfernung spezifischer Kanten unter Beibehaltung der Knoten
  • Knoten-Feature-Unlearning: Entfernung spezifischer Merkmale von Knoten

2. Induktives Unlearning (Inductive)

  • Induktives Knoten-Unlearning: Entfernung von Knotenmengen aus mehreren Graphen
  • Induktives Kanten-Unlearning: Entfernung von Kantenmengen aus mehreren Graphen
  • Graph-Level-Unlearning: Entfernung ganzer Graph-Instanzen

Technische Rahmenwerke

Exakte Unlearning-Methoden

  1. SISA-Rahmenwerk: Partitionierung von Trainingsdaten, wobei nur betroffene Partitionen umgeschult werden müssen
  2. Parameterneutraining: Speicherung historischer Parameter, Neutraining ab dem ersten Auftreten gelöschter Daten
  3. Geschlossene Lösungen: Wie GraphEditor, das GNN-Training in analytisch lösbare Probleme umwandelt

Approximative Unlearning-Methoden

  1. Methoden in konvexen Einstellungen:
    • Nutzung der Hessian-Matrix für Parameteraktualisierungen
    • Einflussfunktion-Schätzung des Dateneinflusses
    • Bereitstellung theoretischer Garantien
  2. Methoden in nicht-konvexen Einstellungen:
    • Einflussfunktion-basiertes Kanten-Unlearning (CEU)
    • Hierarchische Löschoperationen (GNNDelete)
    • Wissensdestillationsmethoden (GUKD, D2DGN)

Experimentelle Einrichtung

Bewertungsdimensionen

1. Vergessenskompletheit

  • Mitgliedschafts-Inferenz-Angriffe: Bewertung, ob gelöschte Daten noch erkannt werden können
  • Vorhersagedifferenz: Vergleich der Ausgabedifferenzen zwischen Vergessensmodell und umgeschultem Modell
  • Parameterdifferenz: Vergleich der euklidischen Distanz von Modellparametern

2. Vergessenseffizienz

  • Zeitkomplexität: Die meisten Methoden haben eine Komplexität, die linear mit der Schichtanzahl und quadratisch mit der Feature-Dimension korreliert
  • Empirische Laufzeit: Tatsächlich benötigte Zeit für Vergessensoperationen

3. Modellnutzen

  • Downstream-Task-Leistung: F1-Score, Genauigkeit, AUROC usw.
  • Vergleich mit Baselines: Typischerweise Vergleich mit der Leistung des Neutrainings von Grund auf

Datensätze

Die im Paper erwähnten Methoden werden auf verschiedenen Graphdatensätzen evaluiert:

  • Soziale Netzwerkdaten
  • Zitationsnetzwerke
  • Molekulare Graphdaten
  • Empfehlungssystemdaten

Experimentelle Ergebnisse

Hauptergebnisse

Exakte vs. approximative Methoden

  • Exakte Methoden: Bieten perfekte Vergessensgarantien, aber mit großem Rechenaufwand
  • Approximative Methoden: Erreichen ein Gleichgewicht zwischen Effizienz und Vergessensqualität

Leistungsabwägungen

  • Grundsätzliche Abwägung zwischen Vergessenskompletheit und Recheneffizienz
  • Die Vernetzung von Graphen führt dazu, dass lokales Vergessen die globale Leistung beeinflusst
  • Verschiedene Vergessenstypen (Knoten/Kanten/Features) haben unterschiedliche Komplexität

Methodenvergleich

Nach der Zusammenfassung in Tabelle II:

  • SISA-ähnliche Methoden zeigen hervorragende Leistung bei Genauigkeit
  • Einflussfunktion-Methoden sind beim approximativen Unlearning effizienter
  • Wissensdestillationsmethoden haben Vorteile bei der Beibehaltung des Modellnutzens

Anwendungseffektivität

  • Empfehlungssysteme: Methoden wie RecEraser handhaben effektiv das Vergessen von Benutzer-Artikel-Interaktionen
  • Soziale Netzwerke: GraphEraser ermöglicht effizientes Vergessen durch Graphpartitionierung
  • Adversariale Abwehr: Vergessenmethoden können effektiv böswillig eingefügte Daten entfernen

Verwandte Arbeiten

Traditionelles Maschinenlern-Unlearning

  • Konzentriert sich hauptsächlich auf unabhängig und identisch verteilte Daten
  • Kann nicht direkt auf Graphstrukturdaten angewendet werden
  • Berücksichtigt keine Abhängigkeiten zwischen Daten

Graph-Maschinenlernens

  • Knotenklassifizierung, Linkvorhersage, Graphklassifizierung und andere Aufgaben
  • Nachrichtenübermittlungsmechanismen machen Informationsausbreitung komplex
  • Erfordert spezialisierte Vergessenstechniken

Datenschutz

  • Anwendung von Differenzieller Privatsphäre auf Graphdaten
  • Verbindung von Federated Learning mit Graphneuralen Netzwerken
  • Mitgliedschafts-Inferenz-Angriffe und deren Abwehr

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Graph Unlearning ist eine Schlüsseltechnologie für verantwortungsvolle KI
  2. Exakte und approximative Methoden haben jeweils Vorteile und sollten je nach Anwendungsanforderungen gewählt werden
  3. Bewertungsstandards müssen weiter verfeinert und standardisiert werden
  4. Anwendungen über Bereiche hinweg zeigen enormes Potenzial

Einschränkungen

  1. Bewertungsstandard-Kontroversen: Bestehende Bewertungsmethoden haben Zuverlässigkeitsprobleme
  2. Herausforderungen in nicht-konvexen Einstellungen: Die meisten praktischen GNN-Modelle sind nicht-konvex, theoretische Garantien sind schwierig
  3. Skalierungsbeschränkungen: Die Effizienz des Vergessens bei großen Graphen muss noch verbessert werden
  4. Komplexe Graphstrukturen: Unzureichende Unterstützung für gerichtete Graphen, zeitliche Graphen usw.

Zukünftige Richtungen

1. Technische Entwicklung

  • Approximatives Unlearning in nicht-konvexen Einstellungen: Entwicklung von Vergessenmethoden für komplexe GNN-Modelle
  • Universelles Graph-Unlearning-Rahmenwerk: Einheitliche Methoden, die mehrere Vergessenstypen unterstützen
  • Unterstützung komplexer Graphstrukturen: Erweiterung auf gerichtete Graphen, zeitliche Graphen, Wissensgraphen

2. Anwendungserweiterung

  • Basis-Modell-Unlearning: Anpassung an Vergessensanforderungen großer Graph-Basismodelle
  • Multi-Benutzer-Interaktionen: Behandlung ethischer Fragen beim Vergessen von Benutzerinteraktionsdaten
  • Edge-Computing-Umgebungen: Effizientes Vergessen in ressourcenbeschränkten Umgebungen

3. Theoretische Verbesserung

  • Zertifizierte Entfernungsmethoden: Bereitstellung stärkerer theoretischer Garantien
  • Bewertungsstandardisierung: Etablierung eines zuverlässigen Bewertungsrahmens für Vergessen
  • Datenschutz-Quantifizierung: Präzisere Methoden zur Quantifizierung von Datenschutzverletzungen

Tiefgreifende Bewertung

Stärken

  1. Bahnbrechendes Werk: Erste systematische Übersicht des Graph-Unlearning-Bereichs
  2. Umfassendheit: Deckt Methoden, Anwendungen, Bewertung und weitere Dimensionen ab
  3. Praktische Anwendbarkeit: Bietet Forschern und Praktikern eine klare technische Roadmap
  4. Zukunftsorientierung: Weist auf mehrere wertvolle zukünftige Forschungsrichtungen hin
  5. Normativität: Etabliert grundlegende Konzepte und Klassifizierungsrahmen des Bereichs

Mängel

  1. Begrenzte empirische Analyse: Als Übersichtsarbeit fehlen neue experimentelle Validierungen
  2. Methodische Tiefe: Technische Details einiger komplexer Methoden könnten tiefer beschrieben werden
  3. Fehlende Benchmarks: Mangel an einheitlichen Benchmark-Tests und Vergleichsstandards
  4. Theoretische Analyse: Theoretische Komplexitätsanalyse verschiedener Methoden könnte detaillierter sein

Auswirkungen

  1. Akademischer Wert: Legt theoretische Grundlagen für den aufstrebenden Graph-Unlearning-Bereich
  2. Praktische Orientierung: Bietet Richtlinien zur Methodenauswahl für industrielle Anwendungen
  3. Forschungsförderung: Dürfte mehr verwandte Forschungsarbeiten anregen
  4. Standardisierung: Trägt zur Etablierung von Bewertungs- und Vergleichsstandards des Bereichs bei

Anwendungsszenarien

  1. Datenschutz-sensitive Anwendungen: Bereiche wie Gesundheitswesen und Finanzen, die strengen Datenschutz erfordern
  2. Großflächige Graphsysteme: Soziale Netzwerke, Empfehlungssysteme und andere Internetanwendungen
  3. Adversariale Umgebungen: Sicherheitskritische Systeme, die Daten-Poisoning-Angriffen widerstehen müssen
  4. Compliance-Anforderungen: Systeme, die GDPR und andere Datenschutzbestimmungen erfüllen müssen

Literaturverzeichnis

Das Paper zitiert 113 relevante Referenzen, die wichtige Arbeiten aus mehreren verwandten Bereichen wie Maschinenlern-Unlearning, Graphneurale Netzwerke und Datenschutz abdecken und Lesern eine umfassende Literaturgrundlage bieten.

Gesamtbewertung: Dies ist eine hochwertige Übersichtsarbeit, die den Forschungsstand des aufstrebenden Graph-Unlearning-Bereichs systematisch darstellt und wichtige Grundlagen für die Entwicklung dieses Bereichs schafft. Das Paper ist klar organisiert, inhaltlich umfassend und hat wichtige Bedeutung für die Förderung der Entwicklung verantwortungsvoller KI.