Query-Limited Community Recovery in Stochastic Block Models

Sintesi Tecnica: Recupero di Comunità con Limite di Query nei Modelli a Blocchi Stocastici

Formulazione del Problema
Questo articolo investiga il problema del recupero esatto delle comunità nel Modello a Blocchi Stocastici (SBM) a due comunità su $n$ vertici, in condizioni di accesso ai dati limitato e rumoroso. Il grafo sottostante $G \sim \text{SBM}(n, p, q)$ è definito con probabilità di arco $p = \alpha \frac{\log n}{n}$ e $q = \beta \frac{\log n}{n}$ per i vertici all'interno e tra le comunità, rispettivamente. L'apprendista non osserva direttamente l'intero grafo. Invece, l'accesso viene concesso attraverso un oracolo di vicinato rumoroso e, in un modello secondario, un grafo sottocampionato.

L'oracolo opera con rumore unidirezionale: quando un vertice $v$ viene interrogato, l'oracolo rivela ogni vero vicino indipendentemente con probabilità $w$ e non riporta mai i non-vicini. L'apprendista opera sotto un budget di query finito $k$. La sfida centrale è determinare come l'allocazione di queste query — specificamente, il compromesso tra strategie uniformi (non adattive) e adattive — influenzi le soglie informazionali per il recupero esatto (recuperare tutte le etichette salvo un flip globale).

Gli autori analizzano due scenari distinti:

1. Accesso Solo tramite Oracolo: L'apprendista non possiede un'osservazione iniziale del grafo e si affida interamente alla trascrizione dell'oracolo.
2. Grafo Sottocampionato Più Oracolo: L'apprendista osserva prima un grafo sottocampionato $G_{sub}$ (dove gli archi sono mantenuti con probabilità $s$) e poi utilizza l'oracolo per raffinare il recupero.

Metodologia e Approccio Tecnico
L'articolo mette a confronto l'interrogazione uniforme non adattiva con le strategie adattive a due stadi. Un ostacolo tecnico primario identificato è che l'interrogazione adattiva interrompe la struttura di osservazione omogenea standard nell'analisi SBM, poiché il conteggio delle query diventa dipendente dalle osservazioni precedenti e la selezione dei vertici per il raffinamento introduce un bias.

Per affrontare ciò, gli autori introducono un framework di screening leave-one-out. Questo meccanismo è distinto dal suo uso in precedenti modelli di osservazione passiva; qui, funge da motore strutturale per il recupero adattivo. Il framework opera come segue:

• Separazione dei Dati: Per ogni vertice $v$, il metodo partiziona l'informazione disponibile in insiemi disgiunti: un insieme di riferimento utilizzato per costruire un'etichetta preliminare (escludendo gli archi incidenti a $v$), un insieme di screening utilizzato per decidere se $v$ è ambiguo, e un nuovo insieme di confronto riservato al test di verosimiglianza finale.
• Strategia a Due Stadi:
  1. Stadio 1 (Stima Grossolana): Un budget viene speso (uniformemente o diversamente) per generare uno schizzo globale approssimativo e identificare un "insieme schermato" $A$ di vertici con etichette incerte.
  2. Stadio 2 (Raffinamento): Il budget rimanente è concentrato esclusivamente sui vertici in $A$. Nuove query all'oracolo vengono utilizzate per classificare questi vertici rispetto agli insiemi di riferimento pre-calcolati e disgiunti.

Contributi Chiave e Risultati

1. Modello Solo Oracolo: Gap di Adattività nel Regime Lineare

• Benchmark Uniforme: Gli autori stabiliscono che l'interrogazione uniforme bilanciata (dove ogni vertice viene interrogato $m = k/n$ volte) riduce il problema a un SBM con probabilità di arco attenuate. Il recupero esatto è possibile se e solo se $\theta_{unif}(k,w)(\sqrt{\alpha} - \sqrt{\beta})^2 > 2$, dove $\theta_{unif}$ è il fattore di ritenzione degli archi. Ciò richiede un budget di query lineare $k = \Omega(n)$.
• Miglioramento Adattivo: L'articolo dimostra che l'interrogazione uniforme non è adattivamente ottimale. Una strategia adattiva a due stadi può raggiungere il recupero esatto con $n + o(n)$ query in regimi in cui l'interrogazione uniforme richiede $mn$ query per qualche $m > 1$.
• Limite Inferiore: Nonostante il miglioramento nelle costanti, gli autori dimostrano che qualsiasi strategia efficace di solo oracolo richiede un numero lineare di query ($k = \Omega(n)$). Pertanto, l'adattività migliora il fattore costante nel regime lineare ma non riduce l'ordine della complessità delle query.

2. Modello Grafo Sottocampionato Più Oracolo: Gap di Adattività Sublineare

• Fallimento Uniforme: Quando un grafo sottocampionato $G_{sub}$ è disponibile, l'interrogazione uniforme con un budget sublineare ($k = o(n)$) fallisce nel migliorare la soglia di recupero esatto oltre quanto fornito da $G_{sub}$ stesso. Se $G_{sub}$ è al di sotto della soglia di recupero, le query all'oracolo uniformi non possono salvare il recupero perché non possono mirare ai vertici specifici ambigui.
• Successo Adattivo: Al contrario, una strategia adattiva può utilizzare $G_{sub}$ per identificare un piccolo insieme di vertici incerti. Concentrando il budget sublineare esclusivamente su questo insieme, la strategia raggiunge il recupero esatto in regimi in cui l'interrogazione uniforme fallisce.
• Significatività: Ciò stabilisce un vero gap di adattività sublineare. A differenza del modello solo oracolo dove il gap risiede nella costante lineare, la presenza di informazioni collaterali permette all'acquisizione adattiva di cambiare fondamentalmente la fattibilità del recupero esatto entro un budget sublineare.

Significatività e Rivendicazioni
L'articolo sostiene di estendere la letteratura sul recupero esatto negli SBM con informazioni collaterali correlate rendendo l'acquisizione dei dati stessa parte del problema di inferenza. Mentre i lavori precedenti trattavano i meccanismi di osservazione come esogeni (fissi in anticipo), questo lavoro tratta l'allocazione delle query come una variabile decisionale.

Gli autori identificano regimi specifici in cui:

• L'interrogazione adattiva non fornisce alcun beneficio informazionale rispetto all'interrogazione uniforme (ad esempio, nel modello solo oracolo con budget sublineari, dove il recupero è impossibile indipendentemente dalla strategia).
• Le informazioni collaterali grossolane (il grafo sottocampionato) consentono un vero gap di adattività, permettendo alle strategie adattive di avere successo dove le strategie uniformi falliscono con lo stesso budget.

Il lavoro è teorico e asintotico, focalizzato sui limiti informazionali del modello SBM a due comunità con grado logaritmico e rumore dell'oracolo unidirezionale indipendente e bilanciato. Non propone specifiche implementazioni sperimentali né rivendica applicazioni pratiche immediate, ma mira a chiarire i limiti fondamentali delle misurazioni locali limitate nel recupero di reti.