Active Learning on Adversarially Corrupted Graphs

Resumo Técnico: Aprendizado Ativo em Grafos Adversarialmente Corrompidos

Formulação do Problema
O artigo aborda o problema de aprendizado ativo em grafos onde a estrutura subjacente foi manipulada por um adversário. O cenário envolve um grafo inicial de "verdade fundamental" (ground-truth) $G^* = (V^*, E^*)$ e um conjunto de vértices corrompidos (maliciosos) $I$. Um adversário com um orçamento $b$ constrói um grafo final $G$ através de três etapas:

1. Criar um subgrafo arbitrário em um conjunto de novos vértices $I$ (onde $|I| \le |V^*|$).
2. Conectar no máximo $b$ vértices de $V^*$ ao conjunto $I$. Isso define o poder do adversário: o tamanho da fronteira de $I$ em $G$ é limitado (ou seja, $|\partial_G(I)| \le b$).
3. Adicionar arbitrariamente arestas dentro de $G^*$.

O algoritmo recebe o grafo resultante $G$ e tem acesso a um oráculo de rótulos $O_{G,I}$, que revela se um vértice consultado pertence a $I$. O objetivo é alcançar a recuperação fraca (weak recovery): identificar um subconjunto $\hat{I}$ tal que a diferença simétrica $|\hat{I} \triangle I| \le \gamma |V(G)|$ com alta probabilidade, utilizando um número mínimo de consultas de rótulos. O desafio reside no fato de que $G^*$ e o subgrafo corrompido $G[I]$ podem ser arbitrários, e o adversário pode manipular a estrutura do grafo significativamente, desde que o número de conexões com o grafo original permaneça pequeno.

Metodologia
A solução proposta baseia-se na propriedade estrutural de expansão de vértices e em uma estrutura algorítmica recursiva.

1. Insight Estrutural: A intuição central é que, se o conjunto de vértices corrompidos $I$ possui uma expansão de vértices significativamente menor do que as partes "boas" do grafo $G^*$, ele pode ser isolado. Especificamente, os autores definem uma condição onde $I$ é "mal expandido" em relação ao restante do grafo. Se $I$ satisfizer uma condição específica de lacuna de expansão (expansion gap), qualquer conjunto $S$ com uma fronteira pequena e tamanho comparável a $I$ deve estar fortemente correlacionado com $I$.

2. Núcleo Algorítmico (Sum-of-Squares): Para encontrar tal conjunto $S$, os autores adaptam algoritmos de Soma de Quadrados (SoS), especificamente modificando a relaxação de programação semidefinida (SDP) para expansão de vértices proposta por Feige et al. (2005).

   • Algoritmos padrão de expansão de vértices frequentemente falham em garantir o tamanho do conjunto retornado ou fornecem fatores de aproximação que são muito frouxos para este cenário adversarial específico.
   • Os autores introduzem um novo algoritmo de arredondamento para a relaxação SoS de grau 4. Este arredondamento garante que o conjunto de saída $S$ satisfaça restrições de cardinalidade (especificamente, $|S| = \Theta(|I||)$ enquanto mantém uma fronteira pequena.
   • Esta adaptação permite que o algoritmo encontre um conjunto $S$ que aproxima a expansão mínima de vértices sujeita a restrições de tamanho, um resultado de interesse independente (Teorema 4).

3. Refinamento Recursivo: O algoritmo opera iterativamente:

   • Ele utiliza o procedimento baseado em SoS para encontrar um conjunto $S$ que esteja altamente correlacionado com os vértices corrompidos restantes.
   • Ele consulta o oráculo em uma pequena amostra aleatória de $S$ e seu complemento para determinar qual conjunto contém a maioria dos nós corrompidos.
   • O conjunto identificado é removido do grafo, e o processo se repete no grafo residual.
   • Os autores provam que as propriedades estruturais (especificamente, a expansão de vértices do grafo de verdade fundamental restante) são preservadas suficientemente através dessas iterações, permitindo que o algoritmo continue recuperando os nós corrompidos até que uma fração elevada seja identificada.

Principais Resultados
A principal contribuição é o Teorema 3, que estabelece a complexidade de consulta para a recuperação fraca. O algoritmo alcança a recuperação $(\gamma, \delta, q, b)$-fraca se:

• O orçamento de consultas $q$ escala como $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$.
• O orçamento do adversário $b$ é limitado pela expansão de vértices do grafo de verdade fundamental $G^*$: $b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$, onde $\partial_{\eta n}(G^*)$ é a fronteira mínima de subconjuntos de tamanho pelo menos $\eta n$.

Essencialmente, o número de consultas necessárias é linear no orçamento do adversário $b$ e inversamente proporcional à precisão desejada $\gamma$, desde que o orçamento do adversário seja pequeno em relação à conectividade (expansão de vértices) do grafo.

Adicionalmente, o Teorema 4 apresenta um resultado auxiliar: um algoritmo de tempo polinomial randomized que encontra um conjunto com pequena expansão de vértices e tamanho dentro de uma faixa equilibrada $[m, n-m]$, alcançando um fator de aproximação de $O(\sqrt{\log n})$ para certos parâmetros. Isso melhora ou complementa limites existentes para problemas de expansão de conjuntos pequenos (small-set expansion).

Significância e Alegações
O artigo afirma ser o primeiro a demonstrar que a expansão de vértices é uma medida fundamental que determina a complexidade de consulta de algoritmos de aprendizado ativo robustos a ataques estruturais adversariais.

• Novidade: Diferente de trabalhos anteriores sobre ataques Sybil ou envenenamento de grafos que frequentemente assumem que o grafo "bom" é um expansor ou limitam o número de arestas adicionadas, este modelo permite estruturas internas arbitrárias tanto nos subgrafos bons quanto nos ruins, limitando apenas o tamanho da fronteira.
• Fundamentação Teórica: O trabalho fornece um elo teórico entre a conectividade do grafo (expansão de vértices) e a viabilidade de detectar nós corrompidos. Mostra que mesmo que o grafo de verdade fundamental não seja um expansor global, a recuperação fraca é possível desde que o orçamento do adversário seja pequeno em relação à expansão de subconjuntos suficientemente grandes.
• Contribuição Algorítmica: O artigo introduz um algoritmo de tempo polinomial para encontrar conjuntos com pequena expansão de vértices sob restrições de cardinalidade, um problema conhecido por ser computacionalmente difícil, ao utilizar e adaptar técnicas de Soma de Quadrados (Sum-of-Squares).

Os autores mantêm um tom modesto, observando que seus resultados dependem de lacunas de expansão específicas e que a complexidade de consulta degrada conforme a precisão desejada $\gamma$ diminui ou o orçamento do adversário aumenta. Eles não alegam resolver o problema para todas as possíveis estruturas de grafos ou orçamentos arbitrários de adversários, mas sim estabelecer um trade-off preciso entre custo de consulta, precisão e as propriedades estruturais do grafo de entrada.