Technische Samenvatting: Parametrische Bootstrap voor Netwerkmodellen met Vaste Kans op Randen

Probleemstelling

Het artikel behandelt de uitdaging om de onzekerheid van netwerkstatistieken (bijvoorbeeld aantallen subgrafieken, clusteringcoëfficiënten, centraliteitsmaten) in willekeurige netwerkdata te kwantificeren. Hoewel bestaande methoden voor het hersampling van netwerken, zoals subsampling en jackknife-procedures, voornamelijk zijn ontwikkeld voor telstatistieken onder grafonmodellen met uitwisselbare knopen, slagen ze er vaak niet in twee kritieke problemen aan te pakken:

1. Niet-uitwisselbaarheid: Veel praktische toepassingen betreffen netwerken met heterogene knopeigenschappen waarbij de aanname van knopenuitwisselbaarheid (onveranderlijkheid onder labelpermutaties) ongewenst of onjuist is. In dergelijke gevallen is het behoud van knopspecifieke informatie cruciaal.
2. Bootstrap-bias: De standaard "natuurlijke" parametrische bootstrap, die de parameters van het netwerkgenererende model schat en vervolgens hersample uit het geschatte model, lijdt aan een niet-verwaarloosbare bias. Deze bias ontstaat omdat de plug-in-schatting van de netwerkstatistiek, $\hat{\mu} = \mu(\hat{P})$, de ware verwachting $\mu(P)$ niet nauwkeurig benadert wanneer het aantal parameters meegroeit met de netwerkgrootte $n$. Specifiek kan de verhouding tussen bias en standaardafwijking de orde $\Theta(p^{-1/2})$ of $\Theta((np)^{-1/2})$ hebben, waardoor standaard betrouwbaarheidsintervallen ongeldig worden, met name in schaarse netwerken.

De auteurs richten zich op het Chung–Lu-model (een model met vaste kans op randen waarbij $P_{ij} = p\theta_i\theta_j$) als werkframework. In tegenstelling tot grafonmodellen, waarbij latente posities willekeurig zijn, gaat deze setting uit van vaste latente posities (of een vaste matrix voor kansen op randen $P$), wat betekent dat de enige willekeur voortkomt uit de onafhankelijke Bernoulli-realizatie van randen.

Methodologie

Het artikel stelt een twee-niveau (dubbele) bootstrap-procedure voor om de bias inherent aan de standaard parametrische bootstrap te corrigeren.

1. Natuurlijke Parametrische Bootstrap (Één Niveau):

   • Schat de matrix voor kansen op randen $\hat{P}$ uit het waargenomen netwerk $A$ (bijvoorbeeld met Maximum Likelihood Schatting of SVD).
   • Genereer $B$ bootstrap-netwerken $\hat{A}^{(b)}$ uit $\hat{P}$.
   • Bereken de statistiek $T(\hat{A}^{(b)})$ voor elke steekproef.
   • De verdeling van deze statistieken benadert de verdeling van $T(A)$, maar het gemiddelde van deze bootstrap-verdeling, $\mu(\hat{P})$, is bevooroordeeld ten opzichte van het ware gemiddelde $\mu(P)$.

2. Twee-Niveau Bootstrap (Biascorrectie):

   • Niveau 1: Genereer $B_1$ bootstrap-netwerken $\hat{A}^{(b)}$ uit het geschatte model $\hat{P}$.
   • Niveau 2: Voor elk $\hat{A}^{(b)}$ herbereken de modelparameters om $\hat{\hat{P}}^{(b)}$ te verkrijgen. Genereer vervolgens $B_2$ tweede-niveau netwerken $\hat{\hat{A}}^{(b,c)}$ uit $\hat{\hat{P}}^{(b)}$.
   • Bias-schatting: De bias van de éénniveau-schatting wordt geschat als:
     $$\widehat{\text{Bias}}_{\hat{P}} = \mathbb{E}_{\hat{P}}[\mu(\hat{\hat{P}})] - \mu(\hat{P}) \approx \frac{1}{B_1} \sum_{b=1}^{B_1} \mu(\hat{\hat{P}}^{(b)}) - \mu(\hat{P})$$
   • Correctie: De bias-gecorrigeerde punt-schatting wordt geconstrueerd als $2\mu(\hat{P}) - \mathbb{E}_{\hat{P}}[\mu(\hat{\hat{P}})]$.

Deze benadering breidt het klassieke iteratieve bootstrap-principe uit naar de netwerkomgeving, waar de parameterdimensie schaalt met $n$. De methode is toepasbaar op zowel globale statistieken (bijvoorbeeld totaal aantal driehoeken) als lokale statistieken (bijvoorbeeld aantal gewortelde subgrafieken, lokale clusteringcoëfficiënten).

Belangrijkste Bijdragen en Theoretische Resultaten

1. Karakterisering van Bootstrap-bias

De auteurs leiden de asymptotische orde van de bootstrap-bias voor aantallen subgrafieken onder het Chung–Lu-model af.

• Voor een geworteld aantal subgrafieken van een graaf $R$ met $v$ hoekpunten en $e$ randen, is de bias van de orde $\Theta(n^{v-2}p^{e-1})$.
• Voor een globaal aantal subgrafieken is de bias van de orde $\Theta(n^{v-1}p^{e-1})$.
• Cruciaal is dat de verhouding tussen bias en standaardafwijking wordt aangetoond als niet-verwaarloosbaar:
  • Globale aantallen: $\Theta(p^{-1/2})$.
  • Gewortelde aantallen: $\Theta((np)^{-1/2})$.
    Dit bevestigt dat zelfs bij consistente parameterschatting de plug-in-schatting $\mu(\hat{P})$ bevooroordeeld is ten opzichte van de steekproefvariatie, wat leidt tot ongeldige inferentie indien niet gecorrigeerd.

2. Biasreductie via Twee-Niveau Bootstrap

Het artikel bewijst dat de twee-niveau bootstrap de orde van de resterende bias vermindert:

• Voor gewortelde aantallen is de resterende bias ten opzichte van de oorspronkelijke bias $O_P((np)^{-1/2})$.
• Voor globale aantallen is de reductie $O_P((np)^{-1})$.
  Gevolg hiervan is dat de resterende bias verwaarloosbaar wordt ten opzichte van de standaardafwijking, waardoor de constructie van geldige betrouwbaarheidsintervallen mogelijk wordt.

3. Variatieschatting en Betrouwbaarheidsintervallen

De auteurs stellen vast dat de tweede-niveau bootstrap een consistente schatter biedt voor de variantie van de plug-in-schatting $\mu(\hat{P})$.

• Vergelijking van Variantie: Voor veel statistieken geldt $\text{Var}_P(\mu(\hat{P})) \ll \text{Var}_P(T(A))$. Dit impliceert dat betrouwbaarheidsintervallen gebaseerd op de verdeling van de plug-in-schatting $\mu(\hat{P})$ (die de volledige netwerkstructuur gebruikt) aanzienlijk smaller zijn dan die gebaseerd op de ruwe statistiek $T(A)$ alleen.
• Constructie van Intervallen: Het artikel stelt zowel intervallen gebaseerd op normale benadering als niet-normale (empirische bootstrap) intervallen voor, beide gecentreerd rond de bias-gecorrigeerde schatter.

4. Centrale Limietstelling (CLT)

Als nevenproduct vestigt het artikel een CLT voor aantallen subgrafieken onder het inhomogene Erdős–Rényi-model (een generalisatie van het Chung–Lu-model). Dit resultaat is van toepassing op zowel globale als gewortelde aantallen subgrafieken onder schaarsheidsvoorwaarden die zwakker zijn dan die vereist door bestaande grafon-gebaseerde literatuur.

Empirische Resultaten

Numerieke experimenten zijn uitgevoerd met:

• Synthetische Data: Netwerken gegenereerd uit Stochastische Blockmodellen (SBM) en Degree-Corrected SBM's (DCSBM) met variërende schaarsheidsniveaus.
• Real Data: Het netwerk van de Zachary's Karate Club en het Political Blogs-netwerk.

Vondsten:

• Biascorrectie: De naïeve bootstrap-intervallen (zonder biascorrectie) dekken de ware parameter ernstig te weinig, vooral in schaarse netwerken. De bias-gecorrigeerde intervallen bereiken een dekking die dicht bij het nominale niveau ligt (bijvoorbeeld 95%).
• Intervallbreedte: Intervallen gebaseerd op de verdeling van $\mu(\hat{P})$ zijn consequent smaller dan die gebaseerd op $T(A)$, met name voor lokale statistieken en in schaarse regimes.
• Robuustheid van de Schatter: De biascorrectie werkt effectief, zelfs wanneer $\hat{P}$ wordt geschat via SVD of wanneer het model lichtjes verkeerd gespecificeerd is (bijvoorbeeld het verkeerde aantal gemeenschappen), hoewel de DCSBM-schatting over het algemeen betere prestaties levert dan SVD.
• Berekeningskosten: Hoewel de twee-niveau bootstrap rekenintensief is ($O(B_1 B_2 n^2)$), is deze paralleliseerbaar. De auteurs merken op dat voor statistieken waarbij de normale benadering geldt, de berekeningskosten kunnen worden verlaagd door de bootstrap alleen te gebruiken voor variantschatting.

Betekenis en Aanspraken

Het artikel claimt een algemeen remedie te bieden voor het probleem van bootstrap-bias in netwerkstatistieken onder modellen met vaste kansen op randen. De betekenis hiervan ligt in:

1. Uitbreiding van Bootstrap-theorie: Het past het iteratieve bootstrap-concept aan op situaties waar het aantal parameters meegroeit met de steekproefgrootte, een scenario waarin standaard bootstrap-consistentie vaak faalt.
2. Omgaan met Niet-uitwisselbaarheid: Door te conditioneren op vaste latente posities (of een vaste $P$), behoudt de methode knopspecifieke eigenschappen, waardoor deze geschikt is voor het analyseren van lokale statistieken en heterogene netwerken waar aannames over knopenuitwisselbaarheid onvanlijk zijn.
3. Praktische Inferentie: De voorgestelde methode maakt de constructie van nauwkeurige, smalle betrouwbaarheidsintervallen mogelijk voor een brede klasse van netwerkstatistieken, inclusief die welke geen U-statistieken zijn, en vult zo een gat dat wordt gelaten door bestaande hersampling-methoden die zich voornamelijk richten op telstatistieken onder grafonmodellen.
4. Theoretische Grondslag: De afleiding van de bias-orde en het bewijs van de CLT voor aantallen subgrafieken onder inhomogene Erdős–Rényi-modellen bieden een rigoureuze theoretische basis voor netwerkinferentie in schaarse regimes.

De auteurs benadrukken dat hoewel de analyse is uitgevoerd onder het Chung–Lu-model, het bias-fenomeen naar verwachting ook zal optreden in complexere modellen (zoals multi-gemeenschap DCSBM's), en dat de twee-niveau bootstrap dient als een robuust, op simulatie gebaseerd correctiemechanisme dat toepasbaar is in deze omgevingen.