Resumo Técnico: Aprendendo Probabilidades de Influência de Pares com Bandidos Contextuais Lineares

1. Formulação do Problema

O artigo aborda o desafio de aprender probabilidades de influência de pares heterogêneas em ambientes de rede. Em redes sociais, a probabilidade de um usuário (recipiente) adotar uma ação após receber uma recomendação de outro usuário (remetente) varia significativamente com base nos atributos dos nós, características das arestas e estrutura da rede.

Os autores formulam isso como um problema de bandido contextual de múltiplos braços (CMAB) bi-objetivo. O cenário envolve um agente interagindo com uma rede direcionada e atribuída $G=(V, E)$ ao longo de $T$ rodadas. Em cada rodada:

1. O agente observa um conjunto de arestas candidatas (interações).
2. O agente seleciona um subconjunto de $k$ arestas para intervenção (ex: mostrar uma postagem para um conjunto específico de recipientes).
3. O agente observa recompensas binárias (ativação: 1 se o recipiente agir, 0 caso contrário).

A dificuldade central reside em equilibrar dois objetivos conflitantes:

• Minimizar o Arrependimento Cumulativo ($Regret_T$): Maximizar recompensas imediatas selecionando arestas com as maiores probabilidades de influência estimada (explotação).
• Minimizar o Erro de Estimativa ($RMSE_T$): Estimar com precisão as verdadeiras probabilidades de influência para todas as arestas na rede, incluindo aquelas com baixa probabilidade ou incerteza (exploração).

O artigo argumenta que os métodos padrão de aprendizado online ou desperdiçam recursos via exploração aleatória (baixas garantias de arrependimento) ou otimizam apenas para recompensas, levando a altos erros de estimativa para arestas de baixa probabilidade. Por outro lado, métodos estáticos falham em separar a influência real de fatores de confusão como a homofilia.

2. Metodologia: Bandido Contextual de Influência ($InfluenceCB$)

Os autores propõem o $InfluenceCB$, um framework projetado para navegar o compromisso entre arrependimento e erro de estimativa. O método opera sob um modelo de recompensa linear onde a recompensa esperada para uma aresta com contexto $X$ é $E[r] = X^\top \theta^*$, sendo $\theta^*$ um vetor de parâmetros desconhecidos.

Componentes Principais:

1. Exploração Guiada pela Incerteza:

   • O algoritmo calcula a incerteza de estimativa para arestas candidatas usando a métrica de incerteza padrão de bandidos lineares: $U_t(X) = \sqrt{X^\top V_{t-1}^{-1} X}$, onde $V_{t-1}$ é a matriz de covariância regularizada dos atributos observados.
   • Se a incerteza máxima no conjunto atual exceder um limiar dinâmico ($C_t / t^\beta$), o algoritmo entra em uma fase de exploração, selecionando as $k$ arestas com as maiores pontuações de incerteza. Isso garante que arestas de baixa probabilidade ou incertas sejam amostradas para melhorar a estimativa global.

2. Explotação Guiada pela Recompensa:

   • Se a incerteza cair abaixo do limiar, o algoritmo entra em uma fase de explotação.
   • Ele emprega uma sub-rotina de CMAB linear padrão (ex: CombLinUCB) para selecionar arestas que maximizam as recompensas imediatas esperadas, minimizando assim o arrependimento.

3. Controle de Compromisso (Trade-off):

   • Parâmetro $\beta$: Controla a taxa assintótica do compromisso. Um $\beta$ menor (ex: 0,25) prioriza a minimização do arrependimento, enquanto um $\beta$ maior (ex: 0,5) prioriza a precisão da estimativa (RMSE).
   • Parâmetro $C_t$: Um limiar adaptativo aprendido ao longo do tempo com base em taxas de ativação ou estatísticas de incerteza, permitindo que o sistema ajuste o equilíbrio entre exploração e explotação dinamicamente.

3. Contribuições Teóricas

O artigo fornece uma análise teórica rigorosa estabelecendo os limites fundamentais deste problema:

• Existência de um Compromisso: Os autores provam que nenhum algoritmo único pode alcançar simultaneamente as taxas ótimas tanto para o arrependimento cumulativo quanto para o erro de estimativa global.
• Pares de Taxas Alcançáveis: Eles caracterizam a fronteira de Pareto de taxas alcançáveis. Especificamente, para qualquer política $\pi$, se o arrependimento escala como $O(T^{2\beta})$, o RMSE deve escalar como $\Omega(T^{-\beta})$, onde $\beta \in [1/4, 1/2]$.
  • Arrependimento ótimo ($\beta=1/4$) implica RMSE subótimo ($\Omega(T^{-1/4})$).
  • RMSE ótimo ($\beta=1/2$) implica arrependimento linear.
• Alcançabilidade: O Teorema 5.1 demonstra que o $InfluenceCB$ pode atingir qualquer ponto nesta fronteira de Pareto ao ajustar o parâmetro $\beta$, satisfazendo os limites:
  $$Regret_T \in \tilde{O}(T^{2\beta}), \quad RMSE_T \in \tilde{O}(T^{-\beta})$$

4. Resultados Experimentais

Os autores avaliaram o $InfluenceCB$ em três conjuntos de dados semi-sintéticos derivados de redes do mundo real: BlogCatalog, Flickr e Hateful (Twitter). As probabilidades de influência de verdade fundamental foram geradas sinteticamente com base em combinações lineares de atributos de nós e arestas.

Baselines (Modelos de Referência):

• Modelos Estáticos: Aleatório, Similaridade, Predição de Ligação (Ridge, GraphSAGE, NCNC) e um Recomendador de Estado da Arte (ContextGNN).
• Aprendizado Online: Variantes de explotação e exploração baseadas em SGD.
• Bandidos Contextuais: LinUCB, EENet, Bandidos de Grafo (GNB) e Takemura et al. (semi-bandido combinatório).

Principais Descobertas:

• Expansão da Fronteira de Pareto: O $InfluenceCB$ expande a fronteira de Pareto além de todos os modelos de referência. Enquanto os bandidos padrão (como o LinUCB) otimizam para o arrependimento, eles exibem erros de estimativa mais altos. Modelos estáticos performam mal em ambas as métricas.
• Compromissos Ajustáveis: Ao ajustar $\beta$, o $InfluenceCB$ pode reduzir significativamente o RMSE (até ~60% no Flickr) ao custo de um aumento no arrependimento, ou minimizar o arrependimento (superando o LinUCB em ~5-10%) com um leve aumento no RMSE.
• Sensibilidade de Parâmetros: O parâmetro $C$ (limiar) impacta significativamente o compromisso. O aprendizado adaptativo de $C$ permite que o algoritmo encontre um equilíbrio sem ajuste manual para necessidades específicas de aplicação.
• Robustez: O método mantém um desempenho competitivo em métricas de ranking (NDCG@k) e erro de calibração (ECE) através de diferentes configurações de rede (seleção de arestas baseada em rede vs. baseada em vizinhos).

5. Significância e Alegações

O artigo afirma ser o primeiro a formular explicitamente o aprendizado de probabilidades de influência de pares como um problema bi-objetivo independente, distinto de tarefas de maximização de influência ou recomendação onde as probabilidades são assumidas como conhecidas ou secundárias.

• Insight Teórico: Estabelece que minimizar o arrependimento e minimizar o erro de estimativa global são objetivos fundamentalmente conflitantes em configurações de bandidos de rede, um compromisso anteriormente não caracterizado neste contexto específico.
• Utilidade Prática: O framework permite que profissionais escolham explicitamente uma política alinhada com as prioridades de sua aplicação. Por exemplo, uma campanha de marketing viral pode priorizar o arrependimento (vendas imediatas), enquanto uma auditoria de política ou simulação de difusão pode priorizar o RMSE (mapas de influência global precisos).
• Limitações e Trabalhos Futuros: Os autores observam que sua análise atual assume ativações de Bernoulli independentes e não modela efeitos de interferência complexos (ex: exposição cumulativa de múltiplos vizinhos). Sugere-se que trabalhos futuros estendam o framework para configurações não lineares e redes dinâmicas ou parcialmente observadas.

Em resumo, o $InfluenceCB$ fornece um mecanismo principiado para navegar a tensão entre aprender modelos de influência precisos e maximizar intervenções de rede imediatas, oferecendo uma ferramenta flexível para a tomada de decisão em redes.