Sintesi Tecnica: Apprendimento delle Probabilità di Influenza tra Pari con Banditi Contestuali Lineari

1. Formulazione del Problema

Il documento affronta la sfida di apprendere le probabilità di influenza tra pari eterogenee in ambienti di rete. Nelle reti sociali, la probabilità che un utente (ricevente) adotti un'azione dopo aver ricevuto una raccomandazione da un altro utente (mittente) varia significativamente in base agli attributi dei nodi, alle caratteristiche degli archi e alla struttura della rete.

Gli autori formulano questo scenario come un problema di multi-armed bandit contestuale (CMAB) bi-obiettivo. L'ambiente prevede un agente che interagisce con una rete diretta con attributi $G=(V, E)$ su $T$ round. In ogni round:

1. L'agente osserva un pool di archi candidati (interazioni).
2. L'agente seleziona un sottoinsieme di $k$ archi per l'intervento (ad esempio, mostrare un post a un set specifico di destinatari).
3. L'agente osserva ricompense binarie (attivazione: 1 se il ricevente agisce, 0 altrimenti).

La difficoltà principale risiede nel bilanciare due obiettivi contrastanti:

• Minimizzazione del Regret Cumulativo ($Regret_T$): Massimizzare le ricompense immediate selezionando gli archi con le probabilità di influenza stimate più elevate (sfruttamento/exploitation).
• Minimizzazione dell'Errore di Stima ($RMSE_T$): Stimare accuratamente le vere probabilità di influenza per tutti gli archi della rete, inclusi quelli con influenza bassa o incerta (esplorazione/exploration).

Il documento sostiene che i metodi standard di apprendimento online o sprecano risorse tramite un'esplorazione casuale (basse garanzie di regret) o ottimizzano esclusivamente le ricompense, portando ad elevati errori di stima per gli archi a bassa probabilità. Al contrario, i metodi statici non riescono a separare la vera influenza da fattori confondenti come l'omofilia.

2. Metodologia: Influence Contextual Bandit ($InfluenceCB$)

Gli autori propongono $InfluenceCB$, un framework progettato per navigare il compromesso tra regret ed errore di stima. Il metodo opera sotto un modello di ricompensa lineare dove la ricompensa attesa per un arco con vettore di contesto $X$ è $E[r] = X^\top \theta^*$, con $\theta^*$ un vettore di parametri ignoto.

Componenti Chiave:

1. Esplorazione Guidata dall'Incertezza:

   • L'algoritmo calcola l'incertezza di stima per gli archi candidati utilizzando la metrica standard di incertezza dei bandit lineari: $U_t(X) = \sqrt{X^\top V_{t-1}^{-1} X}$, dove $V_{t-1}$ è la matrice di covarianza regolarizzata delle feature osservate.
   • Se l'incertezza massima nel pool corrente supera una soglia dinamica ($C_t / t^\beta$), l'algoritmo entra in una fase di esplorazione, selezionando i top-$k$ archi con i punteggi di incertezza più elevati. Ciò garantisce che gli archi con bassa probabilità o incerti vengano campionati per migliorare la stima globale.

2. Sfruttamento Guidato dalla Ricompensa:

   • Se l'incertezza scende al di sotto della soglia, l'algoritmo entra in una fase di sfruttamento.
   • Utilizza una sottoprocedura standard di CMAB lineare (ad es., CombLinUCB) per selezionare gli archi che massimizzano le ricompense immediate attese, minimizzando così il regret.

3. Controllo del Compromesso:

   • Parametro $\beta$: Controlla il tasso asintotico del compromesso. Un $\beta$ più basso (ad es., 0.25) privilegia la minimizzazione del regret, mentre un $\beta$ più alto (ad es., 0.5) privilegia l'accuratezza della stima (RMSE).
   • Parametro $C_t$: Una soglia adattiva appresa nel tempo basata sui tassi di attivazione o sulle statistiche di incertezza, che permette al sistema di regolare dinamicamente l'equilibrio tra esplorazione e sfruttamento.

3. Contributi Teorici

Il documento fornisce un'analisi teorica rigorosa stabilendo i limiti fondamentali di questo problema:

• Esistenza di un Compromesso: Gli autori dimostrano che nessun singolo algoritmo può raggiungere simultaneamente i tassi ottimali sia per il regret cumulativo che per l'errore di stima globale.
• Coppie di Tassi Raggiungibili: Caratterizzano la frontiera di Pareto dei tassi raggiungibili. Nello specifico, per qualsiasi policy $\pi$, se il regret scala come $O(T^{2\beta})$, l'RMSE deve scalare come $\Omega(T^{-\beta})$, dove $\beta \in [1/4, 1/2]$.
  • Il regret ottimale ($\beta=1/4$) implica un RMSE sub-ottimale ($\Omega(T^{-1/4})$).
  • L'RMSE ottimale ($\beta=1/2$) implica un regret lineare.
• Raggiungibilità: Il Teorema 5.1 dimostra che $InfluenceCB$ può raggiungere qualsiasi punto su questa frontiera di Pareto regolando il parametro $\beta$, soddisfacendo i vincoli:
  $$Regret_T \in \tilde{O}(T^{2\beta}), \quad RMSE_T \in \tilde{O}(T^{-\beta})$$

4. Risultati Sperimentali

Gli autori hanno valutato $InfluenceCB$ su tre dataset semi-sintetici derivati da reti reali: BlogCatalog, Flickr e Hateful (Twitter). Le probabilità di influenza reali sono state generate sinteticamente sulla base di combinazioni lineari di feature di nodi e archi.

Baseline:

• Modelli Statici: Random, Similarity, Link Prediction (Ridge, GraphSAGE, NCNC) e un raccomandatore SOTA (ContextGNN).
• Apprendimento Online: Varianti di sfruttamento ed esplorazione basate su SGD.
• Banditi Contestuali: LinUCB, EENet, Graph Neural Bandits (GNB) e Takemura et al. (combinatorial semi-bandit).

Risultati Chiave:

• Espansione della Frontiera di Pareto: $InfluenceCB$ espande la frontiera di Pareto oltre tutte le baseline. Mentre i classici bandit (come LinUCB) ottimizzano per il regret, presentano errori di stima più elevati. I modelli statici performano scarsamente su entrambi i parametri.
• Compromessi Regolabili: Regolando $\beta$, $InfluenceCB$ può ridurre significativamente l'RMSE (fino a ~60% su Flickr) a costo di un aumento del regret, o minimizzare il regret (superando LinUCB di circa il 5-10%) con un lieve aumento dell'RMSE.
• Sensibilità ai Parametri: Il parametro $C$ (soglia) influenza significativamente il compromesso. L'apprendimento adattivo di $C$ permette all'algoritmo di trovare un equilibrio senza una sintonizzazione manuale per specifiche esigenze applicative.
• Robustezza: Il metodo mantiene prestazioni competitive nelle metriche di ranking (NDCG@k) e nell'errore di calibrazione (ECE) attraverso diversi setting di rete (selezione degli archi basata su rete vs basata su vicinato).

5. Significato e Rivendicazioni

Il documento afferma di essere il primo a formulare esplicitamente l'apprendimento delle probabilità di influenza tra pari come un problema bi-obiettivo indipendente, distinto dai compiti di massimizzazione dell'influenza o di raccomandazione dove le probabilità sono assunte come note o secondarie.

• Insight Teorico: Stabilisce che la minimizzazione del regret e la minimizzazione dell'errore di stima globale sono obiettivi fondamentalmente contrastanti in contesti di bandit di rete, un compromesso precedentemente non caratterizzato in questo specifico contesto.
• Utilità Pratica: Il framework consente ai professionisti di scegliere esplicitamente una policy allineata con le priorità della loro applicazione. Ad esempio, una campagna di marketing virale potrebbe dare priorità al regret (vendite immediate), mentre un audit di policy o una simulazione di diffusione potrebbe dare priorità all'RMSE (mappe di influenza globale accurate).
• Limitazioni e Lavori Futuri: Gli autori notano che la loro analisi attuale assume attivazioni Bernoulli indipendenti e non modella effetti di interferenza complessi (ad esempio, l'esposizione cumulativa da parte di più vicini). Si suggerisce come lavoro futuro estendere il framework a setting non lineari e a reti dinamiche o parzialmente osservate.

In sintesi, $InfluenceCB$ fornisce un meccanismo fondato per navigare la tensione tra l'apprendimento di modelli di influenza accurati e la massimizzazione delle immediate interazioni di rete, offrendo uno strumento flessibile per il decision-making in rete.