Technische Samenvatting: Optimalisatie van Behandelingstoewijzing bij Aanwezigheid van Interferentie (OTAPI)

1. Probleemdefinitie

Het artikel behandelt de uitdaging van Optimale Behandelingstoewijzing in netwerkomgevingen waar entiteiten elkaar beïnvloeden, een fenomeen dat bekend staat als interferentie of spillover-effecten. Dit probleem bevindt zich op het snijvlak van twee gevestigde vakgebieden:

• Influence Maximization (IM): Richt zich traditioneel op het selecteren van een set van $k$ seed-nodes om de invloedsspreiding te maximaliseren (bijv. virale marketing, vaccinatie). Standaard IM-benaderingen vertrouwen vaak op veronderstelde diffusieprocessen (bijv. Independent Cascade, Linear Threshold) en netwerkstructuur (bijv. graadcentraliteit), maar negeren vaak node-specifieke kenmerken en heterogene behandelingseffecten.
• Uplift Modeling (UM): Richt zich op het schatten van individuele behandelingseffecten (ITE) om entiteiten te rangschikken en de top $k$ te selecteren. Echter, standaard UM gaat uit van onafhankelijkheid tussen entiteiten. In netwerksituaties wordt deze aanname geschonden; het behandelen van één entiteit verandert de potentiële uitkomsten van zijn buren, waardoor eenvoudige rangschikkingsstrategieën suboptimaal worden.

Het kernprobleel wordt geformaliseerd als het vinden van een behandelingstoewijzingsvector $t^*$ (waarbij $t_i \in \{0,1\}$) die de Totale Behandelingseffect (TTE) over het netwerk maximaliseert, onder een budgetrestrictie $\sum t_i \leq k$. De TTE is de som van de Individuele Totale Behandelingseffecten (ITTE), die zowel het directe effect van de behandeling op een entiteit als de indirecte spillover-effecten van behandelde buren meerekenen. De auteurs merken op dat het vinden van de optimale $t^*$ NP-hard is.

2. Methodologie: OTAPI

De auteurs stellen OTAPI voor (Optimizing Treatment Allocation in the Presence of Interference), een tweestaps-framework dat de kloof tussen UM en IM overbrugt door gebruik te maken van data-gestuurde causale schattingen binnen combinatorische optimalisatie-algoritmen.

Stap 1: Relationele Causale Schatting

De eerste stap houdt in dat een relationele causale estimator wordt getraind op observationele data om potentiële uitkomsten te voorspellen onder verschillende behandelings- en expositiescenario's.

• Causale Structuur: Het model gaat ervan uit dat de uitkomst $Y_i$ van een entiteit afhangt van de eigen kenmerken $X_i$, de eigen behandeling $T_i$, de kenmerken van de buren $X_{N_i}$ en de behandelingen van de buren $T_{N_i}$.
• Expositie Mapping: Om de behandelingen van buren samen te vatten, gebruiken de auteurs een expositie-mapping $Z_i = \frac{\sum_{j \in N_i} T_j}{|N_i|}$, die de proportie behandelde buren vertegenwoordigt.
• Estimator Architectuur: Het artikel maakt gebruik van NetEst (Jiang en Sun, 2022), een op Graph Neural Networks (GNN) gebaseerde estimator. NetEst maakt gebruik van adversarial representation balancing om confounding bias te mitigeren. Het gebruikt een Graph Convolutional Network (GCN) om kenmerken van buren te aggregeren en twee discriminatoren om ervoor te zorgen dat de geleerde latente representatie $\phi_i$ invariant is voor de behandelingsassignatie $T_i$ en de expositie $Z_i$.
• Output: Het getrainde model schat het Individuele Totale Behandelingseffect (ITTE), aangeduid als $\hat{\omega}_i(t_i, z_i)$, voor elke gegeven toewijzing.

Stap 2: Optimalisatie

De tweede stap gebruikt de ITTE-schattingen uit Stap 1 als de objectieve functie voor een combinatorisch optimalisatie-algoritme om de optimale set van $k$ nodes te vinden.

• Algoritme Selectie: Omdat het probleem NP-hard is, gebruikt OTAPI heuristieken uit de IM-literatuur. De auteurs implementeren twee varianten:
  • OTAPI-GR: Gebruikt een Greedy Algoritme dat iteratief de node toevoegt die de hoogste marginale winst oplevert in de geschatte TTE.
  • OTAPI-GA: Gebruikt een Genetic Algorithm die een populatie van behandelingstoewijzingsvectoren evolueert via crossover en mutatie, waarbij de geschatte TTE dient als de fitnessfunctie.
• Flexibiliteit: Het framework is agnostisch ten opzichte van de specifieke causale estimator of het gebruikte optimalisatie-algoritme, waardoor de integratie van andere relationele estimators of heuristieken (bijv. Simulated Annealing) mogelijk is.

3. Belangrijkste Bijdragen

1. Probleemformalisering: De auteurs formaliseren het probleem van het vinden van optimale behandelingstoewijzingen bij aanwezigheid van interferentie, waarbij ze de ITTE en TTE expliciet definiëren in een netwerkcontext waar traditionele consistentie-aannames worden versoepeld.
2. OTAPI Framework: Ze introduceren een nieuwe tweestaps-methode die relationele causale inferentie integreert met klassieke IM-optimalisatie-algoritmen, waarmee ze verder gaan dan de beperkingen van pure rangschikking (UM) of zuivere structurele heuristieken (IM).
3. Empirische Validatie: Uitgebreide experimenten op synthetische en semi-synthetische datasets (BlogCatalog, Flickr, Enron) tonen aan dat OTAPI de traditionele baselines overtreft.

4. Experimentele Resultaten

De auteurs evalueerden OTAPI tegenover verschillende baselines:

• Baselines: Degree (DEG), Single Discount (SD), CELF (klassieke IM met diffusie-simulatie), en TARNet (standaard UM zonder netwerkinformatie). Een "Oracle Greedy" (OG) die het ware data-genererende proces gebruikt, diende als een bovengrens.
• Metrieken: Prestaties werden gemeten met behulp van Liftup (relatieve toename in TTE ten opzichte van willekeurige toewijzing) en RISEO (relatieve toename in de som van verwachte uitkomsten).

Belangrijkste Bevindingen:

• Superieure Prestaties: OTAPI (zowel GR als GA varianten) presteerde consequent beter dan alle baselines over diverse budgetgroottes ($k$) en spillover-magnitudes ($\beta_{spillover}$).
• Robuustheid tegenover Spillover: Naarmate de magnitude van de spillover-effecten toenam, degradeerde de prestatie van TARNet (UM) aanzienlijk, terwijl OTAPI een hoge prestatie behield door interferentie expliciet te modelleren.
• Budgetgevoeligheid:
  • Bij kleine budgetten presteerden op netwerkstructuur gebaseerde methoden (DEG, SD) redelijk goed vanwege de power-law graadverdeling van de netwerken.
  • Naarmate de budgetten toenamen, werd TARNet competitiever omdat individuele behandelingseffecten (MITE) dominanter werden dan spillover-effecten.
  • OTAPI slaagde erin zowel spillover-effecten als MITE's te vangen, en presteerde goed over het gehele bereik van budgetten.
• Generalisatie: OTAPI behield zijn voordeel over verschillende netwerktopologieën (Barabási-Albert vs. Watts-Strogatz), datasetgroottes en feature-dimensionaliteiten.
• Runtime: Hoewel de Greedy-variant (OTAPI-GR) slecht schaalt met de netwerkomvang vanwege herhaalde TTE-berekeningen, vertoonde de Genetic Algorithm-variant (OTAPI-GA) slechts een lichte toename in runtime met de datasetgrootte, wat een meer schaalbare oplossing biedt voor grote netwerken.

5. Betekenis en Beperkingen

Betekenis:
Het artikel beweert dat OTAPI een kritieke kloof vult tussen Influence Maximization en Uplift Modeling. Door data-gestuurde causale effectschatting te combineren met combinatorische optimalisatie, biedt het een robuustere oplossing voor behandelingstoewijzing in netwerken waar interferentie aanwezig is. De auteurs stellen dat het uitsluitend vertrouwen op node-rangschikking (UM) of veronderstelde diffusiemodellen (IM) leidt tot suboptimale beslissingen, terwijl OTAPI zowel individuele heterogeniteit als netwerkdynamiek benut.

Beperkingen en Toekomstig Werk:
De auteurs erkennen enkele beperkingen:

• Causale Aannames: Het huidige model gaat uit van een specifieke causale structuur die contagion-effecten (waarbij een uitkomst op tijdstip $t$ een andere op $t+1$ beïnvloedt) uitsluit.
• Expositie Mapping: De afhankelijkheid van een eenvoudige expositie-mapping (ratio van behandelde buren) houdt mogelijk niet in alle praktische scenario's stand. Ze merken echter op dat OTAPI modulair is en meer complexe estimators kan accommoderen die deze aanname versoepelen.
• Schattingfout: Fouten in de causale estimator kunnen propageren naar de optimalisatiestap. De auteurs suggereren het onderzoeken van end-to-end benaderingen waarbij behandelingstoewijzing direct vanuit de inputdata wordt geleerd als een toekomstige richting.
• Kosten-Batenanalyse: Het huidige framework houdt geen rekening met de kosten van behandeling of de economische waarde van uitkomsten om het optimale budget $k^*$ te bepalen, wat zij identificeren als een veelbelovend gebied voor toekomstig onderzoek.