Query-Limited Community Recovery in Stochastic Block Models

Resumo Técnico: Recuperação de Comunidades com Limitação de Consultas em Modelos de Blocos Estocásticos

Formulação do Problema
Este artigo investiga o problema da recuperação exata de comunidades no Modelo de Blocos Estocásticos (SBM) de duas comunidades em $n$ vértices, sob condições de acesso a dados limitados e ruidosos. O grafo subjacente $G \sim \text{SBM}(n, p, q)$ é definido com probabilidades de aresta $p = \alpha \frac{\log n}{n}$ e $q = \beta \frac{\log n}{n}$ para vértices dentro e entre comunidades, respectivamente. O aprendiz não observa o grafo completo diretamente. Em vez disso, o acesso é concedido através de um oráculo de vizinhança ruidoso e, em um modelo secundário, um grafo subamostrado.

O oráculo opera com ruído unilateral: quando um vértice $v$ é consultado, o oráculo revela cada vizinho verdadeiro independentemente com probabilidade $w$ e nunca reporta não-vizinhos. O aprendiz opera sob um orçamento finito de consultas $k$. O desafio central é determinar como a alocação dessas consultas — especificamente, o compromisso entre estratégias uniformes (não adaptativas) e adaptativas — afeta os limiares de informação para a recuperação exata (recuperar todos os rótulos até uma inversão global).

Os autores analisam dois cenários distintos:

1. Acesso Apenas via Oráculo: O aprendiz não possui observação inicial do grafo e depende inteiramente do registro do oráculo.
2. Grafo Subamostrado Mais Oráculo: O aprendiz primeiro observa um grafo subamostrado $G_{sub}$ (onde as arestas são retidas com probabilidade $s$) e, em seguida, utiliza o oráculo para refinar a recuperação.

Metodologia e Abordagem Técnica
O artigo contrasta a consulta uniforme não adaptativa com estratégias adaptativas de dois estágios. Um principal obstáculo técnico identificado é que a consulta adaptativa interrompe a estrutura de observação homogênea padrão na análise de SBM, pois as contagens de consultas tornam-se dependentes das observações anteriores e a seleção de vértices para refinamento introduz viés.

Para abordar isso, os autores introduzem um framework de triagem de "deixar um fora" (leave-one-out screening). Este mecanismo é distinto de seu uso em modelos de observação passiva prévios; aqui, ele serve como o motor estrutural para a recuperação adaptativa. O framework opera da seguinte forma:

• Separação de Dados: Para qualquer vértice $v$, o método particiona a informação disponível em conjuntos disjuntos: um conjunto de referência usado para construir um rótulo preliminar (excluindo arestas incidentes a $v$), um conjunto de triagem usado para decidir se $v$ é ambíguo e um conjunto de comparação novo reservado para o teste de verossimilhança final.
• Estratégia de Dois Estágios:
  1. Estágio 1 (Estimativa Grossa): Um orçamento é gasto (uniformemente ou de outra forma) para gerar um esboço global bruto e identificar um "conjunto de triagem" $A$ de vértices com rótulos incertos.
  2. Estágio 2 (Refinamento): O orçamento restante é concentrado exclusivamente nos vértices em $A$. Novas consultas ao oráculo são usadas para classificar esses vértices contra os conjuntos de referência disjuntos pré-computados.

Contribuições Principais e Resultados

1. Modelo Apenas via Oráculo: Lacuna de Adaptatividade no Regime Linear

• Referência Uniforme: Os autores estabelecem que a consulta uniforme balanceada (onde cada vértice é consultado $m = k/n$ vezes) reduz o problema a um SBM com probabilidades de aresta atenuadas. A recuperação exata é possível se, e somente se, $\theta_{unif}(k,w)(\sqrt{\alpha} - \sqrt{\beta})^2 > 2$, onde $\theta_{unif}$ é o fator de retenção de arestas. Isso requer um orçamento de consulta linear $k = \Omega(n)$.
• Melhoria Adaptativa: O artigo demonstra que a consulta uniforme não é adaptativamente ótima. Uma estratégia adaptativa de dois estágios pode alcançar a recuperação exata com $n + o(n)$ consultas em regimes onde a consulta uniforme requer $mn$ consultas para algum $m > 1$.
• Limite Inferior: Apesar da melhoria nas constantes, os autores provam que qualquer estratégia de oráculo bem-sucedida requer um número linear de consultas ($k = \Omega(n)$). Assim, a adaptatividade melhora o fator constante no regime linear, mas não reduz a ordem de complexidade de consulta.

2. Modelo de Grafo Subamostrado Mais Oráculo: Lacuna de Adaptatividade Sublinear

• Falha Uniforme: Quando um grafo subamostrado $G_{sub}$ está disponível, a consulta uniforme com um orçamento sublinear ($k = o(n)$) falha em melhorar o limiar de recuperação exata além do que $G_{sub}$ sozinho proporciona. Se $G_{sub}$ estiver abaixo do limiar de recuperação, as consultas ao oráculo uniformes não podem resgatar a recuperação porque não conseguem visar os vértices específicos ambíguos.
• Sucesso Adaptativo: Em contraste, uma estratégia adaptativa pode utilizar $G_{sub}$ para identificar um pequeno conjunto de vértices incertos. Ao concentrar o orçamento sublinear exclusivamente neste conjunto, a estratégia alcança a recuperação exata em regimes onde a consulta uniforme falha.
• Significância: Isso estabelece uma lacuna de adaptatividade genuinamente sublinear. Diferente do modelo apenas via oráculo, onde a lacuna está na constante linear, a presença de informação lateral permite que a aquisição adaptativa mude fundamentalmente a viabilidade da recuperação exata dentro de um orçamento sublinear.

Significância e Alegações
O artigo afirma estender a literatura sobre recuperação exata em SBMs com informação lateral correlacionada ao tornar a própria aquisição de dados parte do problema de inferência. Enquanto trabalhos anteriores trataram os mecanismos de observação como exógenos (fixos de antemão), este trabalho trata a alocação de consultas como uma variável de decisão.

Os autores identificam regimes específicos onde:

• A consulta adaptativa não fornece benefício de informação sobre a consulta uniforme (por exemplo, no modelo apenas via oráculo com orçamentos sublineares, onde a recuperação é impossível independentemente da estratégia).
• Informação lateral grosseira (o grafo subamostrado) permite uma lacuna de adaptatividade genuína, permitindo que estratégias adaptativas tenham sucesso onde estratégias uniformes falham com o mesmo orçamento.

O trabalho é teórico e assintótico, focando nos limites de informação do SBM de grau logarítmico e duas comunidades balanceadas com ruído de oráculo unilateral independente. Não propõe implementações experimentais específicas nem reivindica aplicações práticas imediatas, mas visa esclarecer os limites fundamentais das medições locais limitadas na recuperação de redes.