Query-Limited Community Recovery in Stochastic Block Models

Resumen Técnico: Recuperación de Comunidades con Limitación de Consultas en Modelos de Bloques Estocásticos

Formulación del Problema
Este artículo investiga el problema de la recuperación exacta de comunidades en el Modelo de Bloques Estocásticos (SBM, por sus siglas en inglés) de dos comunidades en $n$ vértices bajo condiciones de acceso a datos limitados y ruidosos. El grafo subyacente $G \sim \text{SBM}(n, p, q)$ se define con probabilidades de arista $p = \alpha \frac{\log n}{n}$ y $q = \beta \frac{\log n}{n}$ para vértices dentro de las mismas comunidades y entre comunidades, respectivamente. El aprendiz no observa el grafo completo directamente. En su lugar, se le concede acceso a través de un oráculo de vecindad ruidoso y, en un modelo secundario, un grafo submuestreado.

El oráculo opera con ruido unidireccional: cuando se consulta un vértice $v$, el oráculo revela cada vecino real de forma independiente con una probabilidad $w$ y nunca reporta no-vecinos. El aprendiz opera bajo un presupuesto de consultas finito $k$. El desafío central es determinar cómo la asignación de estas consultas —específicamente, el compromiso entre las estrategias uniformes (no adaptativas) y adaptativas— afecta los umbrales de información teórica para la recuperación exacta (recuperar todas las etiquetas salvo un giro global).

Los autores analizan dos escenarios distintos:

1. Acceso Solo mediante Oráculo: El aprendiz no tiene una observación inicial del grafo y depende enteramente del registro del oráculo.
2. Grafo Submuestreado más Oráculo: El aprendiz observa primero un grafo submuestreado $G_{sub}$ (donde las aristas se retienen con una probabilidad $s$) y luego utiliza el oráculo para refinar la recuperación.

Metodología y Enfoque Técnico
El artículo contrasta la consulta uniforme no adaptativa con estrategias adaptativas de dos etapas. Un obstáculo técnico primordial identificado es que la consulta adaptativa interrumpe la estructura de observación homogénea estándar en el análisis de SBM, ya que el recuento de consultas se vuelve dependiente de las observaciones previas y la selección de vértices para el refinamiento introduce sesgo.

Para abordar esto, los autores introducen un marco de cribado de dejar uno fuera (leave-one-out screening). Este mecanismo es distinto de su uso en modelos previos de observación pasiva; aquí, sirve como el motor estructural para la recuperación adaptativa. El marco opera de la siguiente manera:

• Separación de Datos: Para cualquier vértice $v$, el método particiona la información disponible en conjuntos disjuntos: un conjunto de referencia utilizado para construir una etiqueta preliminar (excluyendo aristas incidentes a $v$), un conjunto de cribado utilizado para decidir si $v$ es ambiguo, y un conjunto de comparación fresco reservado para la prueba de verosimilitud final.
• Estrategia de Dos Etapas:
  1. Estimación Gruesa (Stage 1): Se gasta un presupuesto (de forma uniforme o de otro modo) para generar un boceto global tosco e identificar un "conjunto cribado" $A$ de vértices con etiquetas inciertas.
  2. Refinamiento (Stage 2): El presupuesto restante se concentra exclusivamente en los vértices en $A$. Se utilizan consultas frescas al oráculo para clasificar estos vértices frente a los conjuntos de referencia disjuntos previamente computados.

Contribuciones Clave y Resultados

1. Modelo Solo Oráculo: Brecha de Adaptatividad en el Régimen Lineal

• Referencia Uniforme: Los autores establecen que la consulta uniforme equilibrada (donde cada vértice es consultado $m = k/n$ veces) reduce el problema a un SBM con probabilidades de arista atenuadas. La recuperación exacta es posible si y solo si $\theta_{unif}(k,w)(\sqrt{\alpha} - \sqrt{\beta})^2 > 2$, donde $\theta_{unif}$ es el factor de retención de aristas. Esto requiere un presupuesto de consultas lineal $k = \Omega(n)$.
• Mejora Adaptativa: El artículo demuestra que la consulta uniforme no es adaptativamente óptima. Una estrategia adaptativa de dos etapas puede lograr la recuperación exacta con $n + o(n)$ consultas en regímenes donde la consulta uniforme requiere $mn$ consultas para algún $m > 1$.
• Límite Inferior: A pesar de la mejora en las constantes, los autores prueban que cualquier estrategia de oráculo exitosa requiere un número lineal de consultas ($k = \Omega(n)$). Por lo tanto, la adaptatividad mejora el factor constante en el régimen lineal, pero no reduce el orden de la complejidad de las consultas.

2. Modelo de Grafo Submuestreado más Oráculo: Brecha de Adaptatividad Sublineal

• Fallo Uniforme: Cuando un grafo submuestreado $G_{sub}$ está disponible, la consulta uniforme con un presupuesto sublineal ($k = o(n)$) falla en mejorar el umbral de recuperación exacta más allá de lo que $G_{sub}$ proporciona por sí solo. Si $G_{sub}$ está por debajo del umbral de recuperación, las consultas al oráculo uniformes no pueden rescatar la recuperación porque no pueden dirigirse a los vértices específicos que son ambiguos.
• Éxito Adaptativo: En contraste, una estrategia adaptativa puede utilizar $G_{sub}$ para identificar un pequeño conjunto de vértices inciertos. Al concentrar el presupuesto sublineal exclusivamente en este conjunto, la estrategia logra la recuperación exacta en regímenes donde la consulta uniforme falla.
• Significancia: Esto establece una verdadera brecha de adaptatividad sublineal. A diferencia del modelo de solo oráculo donde la brecha está en la constante lineal, la presencia de información lateral permite que la adquisición adaptativa cambie fundamentalmente la factibilidad de la recuperación exacta dentro de un presupuesto sublineal.

Significancia y Reivindicaciones
El artículo afirma extender la literatura sobre la recuperación exacta en SBM con información lateral correlacionada al hacer que la adquisición de datos sea parte del problema de inferencia. Mientras que trabajos previos trataban los mecanismos de observación como exógenos (fijos de antemano), este trabajo trata la asignación de consultas como una variable de decisión.

Los autores identifican regímenes específicos donde:

• La consulta adaptativa no proporciona ningún beneficio de información sobre la consulta uniforme (por ejemplo, en el modelo de solo oráculo con presupuestos sublineales, donde la recuperación es imposible independientemente de la estrategia).
• La información lateral gruesa (el grafo submuestreado) permite una verdadera brecha de adaptatividad, permitiendo que las estrategias adaptativas tengan éxito donde las estrategias uniformes fallan con el mismo presupuesto.

El trabajo es teórico y asintótico, centrándose en los límites de información teóricos del SBM de dos comunidades equilibradas de grado logarítmico con ruido de oráculo unidireccional independiente. No propone despliegues experimentales específicos ni reclama aplicaciones prácticas inmediatas, sino que busca aclarar los límites fundamentales de las mediciones locales limitadas en la recuperación de redes.