Active Learning on Adversarially Corrupted Graphs

Resumen Técnico: Aprendizaje Activo en Grafos Adversarialmente Corruptos

Formulación del Problema
El artículo aborda el problema del aprendizaje activo en grafos donde la estructura subyacente ha sido manipulada por un adversario. El entorno implica un grafo inicial de "verdad fundamental" $G^* = (V^*, E^*)$ y un conjunto de vértices corruptos (maliciosos) $I$. Un adversario con un presupuesto $b$ construye un grafo final $G$ a través de tres pasos:

1. Crear un subgrafo arbitrario sobre un conjunto de vértices nuevos $I$ (donde $|I| \le |V^*|$).
2. Conectar como máximo $b$ vértices de $V^*$ al conjunto $I$. Esto define el poder del adversario: el tamaño de la frontera de $I$ en $G$ está acotado por $b$ (es decir, $|\partial_G(I)| \le b$).
3. Añadir arbitrariamente aristas dentro de $G^*$.
   El algoritmo recibe el grafo resultante $G$ y tiene acceso a un oráculo de etiquetas $O_{G,I}$, que revela si un vértice consultado pertenece a $I$. El objetivo es lograr la recuperación débil: identificar un subconjunto $\hat{I}$ tal que la diferencia simétrica $|\hat{I} \triangle I| \le \gamma |V(G)|$ con alta probabilidad, utilizando un número mínimo de consultas de etiquetas. El desafío radica en que $G^*$ y el subgrafo corrupto $G[I]$ pueden ser arbitrarios, y el adversario puede manipular significativamente la estructura del grafo, siempre que el número de conexiones al grafo original permanezca pequeño.

Metodología
La solución propuesta se basa en la propiedad estructural de la expansión de vértices y un marco algorítmico recursivo.

1. Perspicacia Estructural: La intuición central es que si el conjunto de vértices corruptos $I$ tiene una expansión de vértices significativamente menor que las partes "buenas" del grafo $G^*$, este puede ser aislado. Específicamente, los autores definen una condición donde $I$ es "pobremente expansivo" en relación con el resto del grafo. Si $I$ satisface una condición de brecha de expansión específica, cualquier conjunto $S$ con una frontera pequeña y un tamaño comparable al de $I$ debe estar fuertemente correlacionado con $I$.

2. Núcleo Algorítmico (Sum-of-Squares): Para encontrar tal conjunto $S$, los autores adaptan algoritmos de Sum-of-Squares (SoS), específicamente modificando la relajación de programación semidefinida (SDP) para la expansión de vértices propuesta por Feige et al. (2005).

   • Los algoritmos estándar de expansión de vértices a menudo fallan en garantizar el tamaño del conjunto devuelto o proporcionan factores de aproximación demasiado laxos para este entorno adversarial específico.
   • Los autores introducen un nuevo algoritmo de redondeo para la relajación SoS de grado 4. Este redondeo asegura que el conjunto $S$ resultante satisfaga restricciones de cardinalidad (específicamente, $|S| = \Theta(|I||)$) manteniendo al mismo tiempo una frontera pequeña.
   • Esta adaptación permite al algoritmo encontrar un conjunto $S$ que aproxima la expansión de vértices mínima sujeta a restricciones de tamaño, un resultado de interés independiente (Teorema 4).

3. Refinamiento Recursivo: El algoritmo opera de forma iterativa:

   • Utiliza el procedimiento basado en SoS para encontrar un conjunto $S$ que esté altamente correlacionado con los vértices corruptos restantes.
   • Consulta el oráculo en una pequeña muestra aleatoria de $S$ y su complemento para determinar qué conjunto contiene la mayoría de los nodos corruptos.
   • El conjunto identificado se elimina del grafo, y el proceso se repite en el grafo residual.
   • Los autores demuestran que las propiedades estructurales (específicamente, la expansión de vértices del grafo de verdad fundamental restante) se preservan suficientemente a través de estas iteraciones, permitiendo que el algoritmo continúe recuperando los nodos corruptos hasta que se identifica una fracción elevada.

Resultados Clave
La contribución principal es el Teorema 3, que establece la complejidad de consulta para la recuperación débil. El algoritmo logra la recuperación débil $(\gamma, \delta, q, b)$ si:

• El presupuesto de consultas $q$ escala como $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$.
• El presupuesto del adversario $b$ está acotado por la expansión de vértices del grafo de verdad fundamental $G^*$: $b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$, donde $\partial_{\eta n}(G^*)$ es la frontera mínima de los subconjuntos de tamaño al menos $\eta n$.

Esencialmente, el número de consultas requeridas es lineal en el presupuesto del adversario $b$ e inversamente proporcional a la precisión deseada $\gamma$, siempre que el presupuesto del adversario sea pequeño en relación con la conectividad (expansión de vértices) del grafo.

Además, el Teorema 4 presenta un resultado auxiliar: un algoritmo de tiempo polinomial aleatorizado que encuentra un conjunto con pequeña expansión de vértices y tamaño dentro de un rango equilibrado $[m, n-m]$, logrando un factor de aproximación de $O(\sqrt{\log n})$ para ciertos parámetros. Esto mejora o complementa los límites existentes para problemas de expansión de conjuntos pequeños.

Significancia y Reivindicaciones
El artículo afirma ser el primero en demostrar que la expresión de vértices es una medida fundamental que determina la complejidad de consulta de los algoritmos de aprendizaje activo robustos a ataques estructurales adversariales.

• Novedad: A diferencia de trabajos previos sobre ataques Sybil o envenenamiento de grafos que a menudo asumen que el grafo "bueno" es un expansor o limitan el número de aristas añadidas, este modelo permite estructuras internas arbitrarias tanto en los subgrafos buenos como en los malos, limitando únicamente el tamaño de la frontera.
• Fundamentación Teórica: El trabajo proporciona un vínculo teórico entre la conectividad del grafo (expansión de vértices) y la viabilidad de detectar nodos corruptos. Muestra que incluso si el grafo de verdad fundamental no es un expansor global, la recuperación débil es posible siempre que el presupuesto del adversario sea pequeño en comparación con la expansión de subconjuntos suficientemente grandes.
• Contribución Algorítmica: El artículo introduce un algoritmo de tiempo polinomial para encontrar conjuntos con pequeña expansión de vértices bajo restricciones de cardinalidad, un problema conocido por ser computacionalmente difícil, aprovechando y adaptando técnicas de Sum-of-Squares.

Los autores mantienen un tono modesto, señalando que sus resultados dependen de brechas de expansión específicas y que la complejidad de consulta se degrada a medida que la precisión deseada $\gamma$ disminuye o el presupuesto del adversario aumenta. No pretenden resolver el problema para todas las posibles estructuras de grafos o presupuestos de adversario arbitrarios, sino establecer un compromiso preciso entre el costo de consulta, la precisión y las propiedades estructurales del grafo de entrada.