Active Learning on Adversarially Corrupted Graphs

Technische Samenvatting: Active Learning op Adversarieel Gecorrumpeerde Grafen

Probleemformulering
Het artikel behandelt het probleem van active learning op grafen waarbij de onderliggende structuur is gemanipuleerd door een tegenstander (adversary). De setting betreft een initiële "grondwaarheid"-graaf $G^* = (V^*, E^*)$ en een verzameling gecorrumpeerde (kwaadwillige) knopen $I$. Een tegenstander met een budget $b$ construeert een uiteindelijke graaf $G$ via drie stappen:

1. Het creëren van een willekeurige subgraaf op een verzameling nieuwe knopen $I$ (waarbij $|I| \le |V^*|$).
2. Het verbinden van maximaal $b$ knopen uit $V^*$ met de verzameling $I$. Dit definieert de macht van de tegenstander: de grootte van de grens (frontier) van $I$ in $G$ is begrensd (d.w.z. $|\partial_G(I)| \le b$).
3. Het willekeurig toevoegen van randen binnen $G^*$.

Het algoritme ontvangt de resulterende graaf $G$ en heeft toegang tot een label-orakel $O_{G,I}$, dat onthult of een gezochte knoop tot $I$ behoort. Het doel is om zwakke recovery te bereiken: het identificeren van een deelverzameling $\hat{I}$ zodanig dat de symmetrische verschil $|\hat{I} \triangle I| \le \gamma |V(G)|$ met een hoge waarschijnlijkheid, met een minimaal aantal label-queries. De uitdaging ligt in het feit dat $G^*$ en de gecorrumpeerde subgraaf $G[I]$ willekeurig kunnen zijn en de tegenstander de graafstructuur aanzienlijk kan manipuleren, mits het aantal verbindingen naar de oorspronkelijke graaf klein blijft.

Methodologie
De voorgestelde oplossing steunt op de structurele eigenschap van vertex expansion (knoop-expansie) en een recursief algoritmisch kader.

1. Structureel Inzicht: De kernintuïtie is dat als de verzameling gecorrumpeerde knopen $I$ een significant kleinere vertex expansion heeft dan de "goede" delen van de graaf $G^*$, deze geïsoleerd kan worden. Specifiek definiëren de auteurs een conditie waarbij $I$ "slecht expandeert" ten opzichte van de rest van de graaf. Als $I$ aan een specifieke expansie-gap-conditie voldoet, moet elke verzameling $S$ met een kleine grens en een grootte vergelijkbaar met $I$, sterk gecorreleerd zijn met $I$.

2. Algoritmische Kern (Sum-of-Squares): Om een dergelijke verzameling $S$ te vinden, passen de auteurs Sum-of-Squares (SoS) algoritmen aan, specifiek door de semidefinite programming (SDP) relaxatie voor vertex expansion voorgesteld door Feige et al. (2005) te modificeren.

   • Standaard vertex expansion algoritmen falen vaak in het garanderen van de grootte van de geretourneerde verzameling of bieden benaderingsfactoren die te zwak zijn voor deze specifieke adversariële setting.
   • De auteurs introduceren een nieuw rounding algoritme voor de degree-4 SoS relaxatie. Deze rounding zorgt ervoor dat de output-verzameling $S$ voldoet aan cardinaliteitsrestricties (specifiek, $|S| = \Theta(|I|)$) terwijl een kleine grens behouden blijft.
   • Deze aanpassing maakt het mogelijk voor het algoritme om een verzameling $S$ te vinden die de minimale vertex expansion benadert onder groottebeperkingen, een resultaat van onafhankelijke interesse (Theorem 4).

3. Recursieve Verfijning: Het algoritme werkt iteratief:

   • Het gebruikt de SoS-gebaseerde procedure om een verzameling $S$ te vinden die sterk gecorreleerd is met de resterende gecorrumpeerde knopen.
   • Het bevraagt het orakel op een kleine willekeurige steekproef van $S$ en de complementaire verzameling om te bepalen welke verzameling de meerderheid van de gecorrumpeerde knopen bevat.
   • De geïdentificeerde verzameling wordt verwijderd uit de graaf, en het proces wordt herhaald op de residu-graaf.
   • De auteurs bewijzen dat de structurele eigenschappen (specifiek de vertex expansion van de resterende grondwaarheid-graaf) voldoende behouden blijven tijdens deze iteraties, waardoor het algoritme kan doorgaan met het terugwinnen van gecorrumpeerde knopen totdat een hoog deel is geïdentificeerd.

Belangrijkste Resultaten
De belangrijkste bijdrage is Theorem 3, die de query complexiteit vaststelt voor zwakke recovery. Het algoritme bereikt $(\gamma, \delta, q, b)$-weak recovery als:

• Het query-budget $q$ schaalt als $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$.
• Het budget van de tegenstander $b$ begrensd is door de vertex expansion van de grondwaarheid-graaf $G^*$: $b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$, waarbij $\partial_{\eta n}(G^*)$ de minimale frontier is van deelverzamelingen van grootte ten minste $\eta n$.

In essentie is het aantal vereiste queries lineair in het budget van de tegenstander $b$ en omgekeerd evenredig aan de gewenste nauwkeurigheid $\gamma$, mits het budget van de tegenstander klein is in verhouding tot de connectiviteit (vertex expansion) van de graaf.

Daarnaast presenteert Theorem 4 een aanvullend resultaat: een gerandomiseerd polynomial-time algoritme dat een verzameling vindt met een kleine vertex expansion en een grootte binnen een gebalanceerd bereik $[m, n-m]$, waarbij een benaderingsfactor van $O(\sqrt{\log n})$ wordt bereikt voor bepaalde parameters. Dit verbetert of complementeert bestaande grenzen voor small-set expansion problemen.

Betekenis en Claims
Het artikel beweert de eerste te zijn die aantoont dat vertex expansion een fundamentele maatstaf is die de query complexiteit bepaalt van active learning algoritmen die robuust zijn tegen structurele adversariële aanvallen.

• Nieuwigheid: In tegenstelling tot eerder werk over Sybil-aanvallen of graph poisoning, dat vaak aanneemt dat de "goede" graaf een expander is of het aantal toegevoegde randen begrenst, staat dit model willekeurige interne structuren toe in zowel de goede als de slechte subgrafen, waarbij alleen de grootte van de grens (boundary) wordt begrensd.
• Theoretische Onderbouwing: Het werk biedt een theoretische link tussen graafconnectiviteit (vertex expansion) en de haalbaarheid van het detecteren van gecorrumpeerde knopen. Het toont aan dat zelfs als de grondwaarheid-graaf geen globale expander is, zwakke recovery mogelijk is zolang het budget van de tegenstander klein is ten opzichte van de expansie van voldoende grote deelverzamelingen.
• Algoritmische Bijdrage: Het artikel introduceert een polynomial-time algoritme voor het vinden van verzamelingen met een kleine vertex expansion onder cardinaliteitsrestricties, een probleem dat bekend staat als computationeel moeilijk, door gebruik te maken van en aan te passen van Sum-of-Squares technieken.

De auteurs hanteren een bescheiden toon en merken op dat hun resultaten rusten op specifieke expansie-gaps en dat de query complexiteit afneemt naarmate de gewenste nauwkeurigheid $\gamma$ afneemt of het budget van de tegenstander toeneemt. Ze beweren niet het probleem voor alle mogelijke graafstructuren of willekeurige tegenstander-budgetten op te lossen, maar stellen een precieze afruil vast tussen query kosten, nauwkeurigheid en de structurele eigenschappen van de invoer-graaf.