Active Learning on Adversarially Corrupted Graphs

Technische Zusammenfassung: Aktives Lernen auf adversariell korrumpierten Graphen

Problemformulierung
Die Arbeit befasst sich mit dem Problem des aktiven Lernens auf Graphen, deren zugrunde liegende Struktur durch einen Adversären manipuliert wurde. Das Szenario umfasst einen initialen „Ground-Truth“-Graphen $G^* = (V^*, E^*)$ und eine Menge korrumpierter (böswilliger) Knoten $I$. Ein Adversär konstruiert mit einem Budget $b$ einen finalen Graphen $G$ durch drei Schritte:

1. Erstellung eines beliebigen Subgraphen auf einer Menge frischer Knoten $I$ (wobei $|I| \le |V^*|$).
2. Verbindung von höchstens $b$ Knoten aus $V^*$ mit der Menge $I$. Dies definiert die Macht des Adversären: Die Größe der Frontier (Randmenge) von $I$ in $G$ ist beschränkt (d. h. $|\partial_G(I)| \le b$).
3. Beliebige Hinzufügung von Kanten innerhalb von $G^*$.

Der Algorithmus erhält den resultierenden Graphen $G$ und hat Zugriff auf ein Label-Orakel $O_{G,I}$, das offenbart, ob ein angefragter Knoten zu $I$ gehört. Das Ziel ist die Erreichung einer schwachen Rekuperation (Weak Recovery): Identifizierung einer Teilmenge $\hat{I}$ sodass die symmetrische Differenz $|\hat{I} \triangle I| \le \gamma |V(G)|$ mit hoher Wahrscheinlichkeit gilt, unter Verwendung einer minimalen Anzahl an Label-Abfragen. Die Herausforderung besteht darin, dass $G^*$ und der korrumpierte Subgraph $G[I]$ beliebig sein können und der Adversär die Graphstruktur signifikant manipulieren kann, sofern die Anzahl der Verbindungen zum ursprünglichen Graphen gering bleibt.

Methodik
Die vorgeschlagene Lösung stützt sich auf die strukturelle Eigenschaft der Vertex Expansion (Knotenexpansion) und ein rekursives algorithmisches Framework.

1. Strukturelle Einsicht: Die zentrale Intuition ist, dass die Menge der korrumpierten Knoten $I$ isoliert werden kann, wenn sie eine signifikant geringere Vertex Expansion aufweist als die „guten“ Teile des Graphen $G^*$. Speziell definieren die Autoren eine Bedingung, bei der $I$ „schlecht expandierend“ im Verhältnis zum Rest des Graphen ist. Wenn $I$ eine spezifische Expansionslücke erfüllt, muss jede Menge $S$ mit einer kleinen Randmenge und einer Größe vergleichbar mit $I$ stark mit $I$ korreliert sein.

2. Algorithmischer Kern (Sum-of-Squares): Um eine solche Menge $S$ zu finden, passen die Autoren Sum-of-Squares (SoS)-Algorithmen an, insbesondere durch Modifikation der Semidefiniten Programmierung (SDP)-Relaxierung für die Vertex Expansion, wie sie von Feige et al. (2005) vorgeschlagen wurde.

   • Standardmäßige Algorithmen zur Vertex Expansion scheitern oft daran, die Größe der zurückgegebenen Menge zu garantieren oder liefern Approximationsfaktoren, die für diesen spezifischen adversariellen Kontext zu schwach sind.
   • Die Autoren führen einen neuartigen Rounding-Algorithmus für die Grad-4 SoS-Relaxierung ein. Dieses Rounding stellt sicher, dass die ausgegebene Menge $S$ Kardinalitätsbeschränkungen erfüllt (speziell $|S| = \Theta(|I|)$), während sie gleichzeitig eine kleine Randmenge beibehält.
   • Diese Anpassung ermöglicht es dem Algorithmus, eine Menge $S$ zu finden, die die minimale Vertex Expansion unter Kardinalitätsbeschränkungen approximiert, ein Ergebnis von eigenständigem Interesse (Theorem 4).

3. Rekursive Verfeinerung: Der Algorithmus arbeitet iterativ:

   • Er nutzt das SoS-basierte Verfahren, um eine Menge $S$ zu finden, die hoch korreliert mit den verbleibenden korrumpierten Knoten ist.
   • Er fragt das Orakel auf einer kleinen Zufallsstichprobe von $S$ und dessen Komplement ab, um zu bestimmen, welche Menge die Mehrheit der korrumpierten Knoten enthält.
   • Die identifizierte Menge wird aus dem Graphen entfernt, und der Prozess wiederholt sich auf dem residualen Graphen.
   • Die Autoren beweisen, dass die strukturellen Eigenschaften (speziell die Vertex Expansion des verbleibenden Ground-Truth-Graphen) durch diese Iterationen hinreichend bewahrt werden, sodass der Algorithmus fortfahren kann, korrumpierte Knoten zu rekonstruieren, bis ein hoher Anteil identifiziert ist.

Wichtigste Ergebnisse
Der Hauptbeitrag ist Theorem 3, welches die Abfragekomplexität für die schwache Rekuperation festlegt. Der Algorithmus erreicht eine $(\gamma, \delta, q, b)$-schwache Rekuperation, wenn:

• Das Abfragebudget $q$ skaliert als $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$.
• Das Budget des Adversären $b$ durch die Vertex Expansion des Ground-Truth-Graphen $G^*$ beschränkt ist: $b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$, wobei $\partial_{\eta n}(G^*)$ die minimale Frontier von Teilmengen der Größe mindestens $\eta n$ ist.

Im Wesentlichen ist die Anzahl der erforderlichen Abfragen linear zum Budget des Adversären $b$ und umgekehrt proportional zur gewünschten Genauigkeit $\gamma$, vorausgesetzt, das Budget des Adversären ist klein im Verhältnis zur Konnektivität (Vertex Expansion) des Graphen.

Zusätzlich präsentiert Theorem 4 ein Hilfsergebnis: ein randomisierter Algorithmus in Polynomialzeit, der eine Menge mit kleiner Vertex Expansion und einer Größe innerhalb eines balancierten Bereichs $[m, n-m]$ findet und dabei einen Approximationsfaktor von $O(\sqrt{\log n})$ für bestimmte Parameter erreicht. Dies verbessert oder ergänzt bestehende Schranken für Small-Set-Expansion-Probleme.

Bedeutung und Behauptungen
Die Arbeit behauptet, die erste zu sein, die zeigt, dass die Vertex Expansion ein fundamentales Maß ist, welches die Abfragekomplexität von aktiven Lernalgorithmen bestimmt, die robust gegenüber strukturellen adversariellen Angriffen sind.

• Neuheit: Im Gegensatz zu bisherigen Arbeiten zu Sybil-Angriffen oder Graph-Poisoning, die oft voraussetzen, dass der „gute“ Graph ein Expander ist oder die Anzahl der hinzugefügten Kanten begrenzen, erlaubt dieses Modell beliebige interne Strukturen sowohl in den guten als auch in den schlechten Subgraphen, wobei lediglich die Größe der Randmenge beschränkt wird.
• Theoretische Fundierung: Die Arbeit liefert eine theoretische Verbindung zwischen der Graph-Konnektivität (Vertex Expansion) und der Durchführbarkeit der Detektion korrumpierter Knoten. Sie zeigt, dass selbst wenn der Ground-Truth-Graph kein globaler Expander ist, eine schwache Rekuperation möglich ist, solange das Budget des Adversären klein im Vergleich zur Expansion ausreichend großer Teilmengen ist.
• Algorithmischer Beitrag: Die Arbeit führt einen Polynomialzeit-Algorithmus zur Findung von Mengen mit kleiner Vertex Expansion unter Kardinalitätsbeschränkungen ein – ein Problem, das als rechnerisch schwer bekannt ist – indem sie SoS-Techniken nutzt und anpasst.

Die Autoren wahren einen bescheidenen Ton und merken an, dass ihre Ergebnisse auf spezifischen Expansionslücken beruhen und dass die Abfragekomplexität sinkt, wenn die gewünschte Genauigkeit $\gamma$ abnimmt oder das Budget des Adversären steigt. Sie behaupten nicht, das Problem für alle möglichen Graphstrukturen oder beliebige Budgets des Adversären gelöst zu haben, sondern etablieren einen präzisen Trade-off zwischen Abfragekosten, Genauigkeit und den strukturellen Eigenschaften des Eingabegraphen.