Optimal Design under Interference, Homophily, and Robustness Trade-offs

1. Problema e Motivação

O artigo aborda o desafio de estimar o Efeito Médio Global do Tratamento (GATE) em experimentos onde existe interferência de rede (o resultado de uma unidade depende do tratamento atribuído aos seus vizinhos).

• O Dilema Tradicional: A abordagem padrão para reduzir o viés causado pela interferência é o randomização em clusters (agrupar unidades conectadas e tratá-las uniformemente). No entanto, em redes sociais reais, existe frequentemente homofilia (tendência de indivíduos semelhantes se conectarem).
• O Conflito: Quando a homofilia está presente, a randomização em clusters pode, paradoxalmente, aumentar o Erro Quadrático Médio (MSE). Isso ocorre porque clusters podem se tornar desbalanceados em termos de covariáveis (ex: um cluster pode conter apenas indivíduos de um grupo demográfico específico), levando a amostras não representativas e inflando a variância do estimador.
• A Lacuna: Existe uma necessidade de projetar experimentos que equilibrem três forças concorrentes:
  1. Minimizar o viés da interferência (agrupando vizinhos).
  2. Minimizar o viés da homofilia (espalhando tratamentos entre grupos semelhantes para balancear covariáveis).
  3. Garantir robustez contra variação heterogênea não explicada pela estrutura da rede (requerendo randomização).

2. Metodologia

Os autores desenvolvem um novo modelo de resultados potenciais que formaliza matematicamente essas três fontes de erro e propõe um framework de otimização para encontrar o design de tratamento ideal.

A. Modelagem Matemática

O modelo de resultados para uma unidade $i$ sob tratamento $z$ é decomposto em:
$$Y_i(z) = \alpha_i + \phi_i z_i + s_i(z)$$
Onde:

• $\alpha$: Baseline (resultado sob controle).
• $\phi$: Efeito do tratamento.
• $s(z)$: Componente de interferência.

O modelo impõe restrições sobre esses componentes usando parâmetros de trade-off:

1. Homofilia ($\eta$): A variação suave dos coeficientes de resultado ao longo da rede é limitada pela forma quadrática $h^T L h \leq \eta$, onde $L$ é o Laplaciano do grafo.
2. Interferência ($\gamma$): A magnitude da interferência é limitada por $s(z)^T L^\dagger s(z) \leq \gamma$, onde $L^\dagger$ é o pseudoinverso do Laplaciano.
3. Robustez ($\kappa$): A variação heterogênea não explicada ($\epsilon$) é limitada por normas de Schatten da matriz de covariância, controlando o pior caso de erro.

B. Formulação de Otimização

O objetivo é minimizar o limite superior do MSE (Erro Quadrático Médio) do estimador de Horvitz-Thompson. O problema é reformulado como uma otimização sobre a matriz de covariância do design $X = E[xx^T]$, onde $x$ é o vetor de atribuição de tratamento codificado.

A função objetivo a ser minimizada é uma combinação linear de termos que representam os trade-offs:
$$\min_X \quad \tilde{\eta}\text{Tr}(L^\dagger X) + \tilde{\gamma}\text{Tr}(LX) + \tilde{\kappa}\|X\|_q + \text{Tr}(\mathbf{1}\mathbf{1}^T X)$$
Sujeito a $X \succeq 0$ e $\text{diag}(X) = 1$.

• $\text{Tr}(LX)$: Penaliza designs que não agrupam vizinhos (favorece clusters para reduzir interferência).
• $\text{Tr}(L^\dagger X)$: Penaliza designs que não espalham o tratamento (favorece dispersão para reduzir viés de homofilia).
• $\|X\|_q$: Penaliza a estrutura de covariância para garantir robustez (favorece randomização).

C. Algoritmos Propostos

Os autores propõem duas abordagens complementares para resolver esse problema e gerar atribuições binárias ($z \in \{0,1\}^n$):

1. Relaxação SDP + Arredondamento Gaussiano:

   • Formula o problema como um Programa Semidefinido (SDP).
   • Resolve a relaxação convexa para obter $X_{SDP}$.
   • Aplica um procedimento de arredondamento gaussiano (inspirado no algoritmo de Goemans-Williamson para MAXCUT) para amostrar um vetor gaussiano e arredondar suas coordenadas para obter a atribuição final.
   • Vantagem: Garantias teóricas fortes de aproximação.
   • Desvantagem: Custo computacional alto para grandes $n$.

2. Algoritmo Adaptado Gram-Schmidt Walk (GSW):

   • Adapta o algoritmo de "Caminhada Gram-Schmidt" (recentemente proposto por Harshaw et al.) para o contexto de balanceamento de covariáveis induzidas pela rede.
   • Trata o problema como um balanceamento de vetores onde as "covariáveis" são derivadas dos autovalores do Laplaciano e da matriz de robustez.
   • Vantagem: Escalabilidade computacional superior para grandes redes.
   • Desvantagem: Limites teóricos de erro ligeiramente mais frouxos em comparação ao SDP ideal.

3. Contribuições Principais

• Framework Unificado: Apresenta o primeiro framework que formaliza e otimiza simultaneamente os trade-offs entre interferência, homofilia e robustez, recuperando designs existentes (como randomização em clusters ou Bernoulli) como casos limites.
• Novo Modelo de Resultados: Introduz uma decomposição de resultados potenciais que separa explicitamente componentes homofílicos, de interferência e de variação heterogênea, permitindo uma análise de pior caso rigorosa.
• Interpretação Espectral: Demonstra que a minimização do MSE sob interferência e homofilia pode ser vista como um problema de balanceamento de covariáveis, onde as "covariáveis" são os autovetores escalados do Laplaciano da rede.
• Algoritmos Práticos: Desenvolve e analisa dois algoritmos (SDP + Rounding e GSW Adaptado) que são implementáveis e oferecem garantias de desempenho.

4. Resultados e Avaliação

Os autores avaliam seus designs através de simulações em redes sintéticas (Modelos de Blocos Estocásticos - SBM, Barabási-Albert, Erdős-Rényi) e em um conjunto de dados real de redes de vilas na Índia (Banerjee et al., 2013), que exibe forte homofilia baseada em castas.

• Desempenho em Pior Caso: Os designs otimizados (SDP e GSW) superam consistentemente os designs tradicionais (Randomização em Clusters, Louvain, Spectral Clustering, Bernoulli) em termos de limites superiores de MSE, especialmente quando há um equilíbrio delicado entre homofilia e interferência.
• Trade-off Visualizado: As simulações mostram que, à medida que a homofilia aumenta, o design ótimo transita de um padrão "agrupado" (clusterizado) para um padrão "difuso" (espalhado), enquanto o aumento da robustez ($\kappa$) força o design para uma randomização mais próxima da Bernoulli.
• Dados Reais: No conjunto de dados das vilas indianas, os designs tradicionais tendem a alinhar clusters com grupos de castas, exacerbando o viés. O design proposto consegue distribuir o tratamento de forma a quebrar essa correlação, reduzindo o erro de estimação.

5. Significado e Impacto

Este trabalho é significativo porque:

1. Resolve uma contradição prática: Mostra como sair da dicotomia "clusters vs. randomização" quando a estrutura da rede e a homofilia estão em conflito.
2. Generaliza a Literatura: Conecta a literatura de inferência causal em redes com a de otimização combinatória (SDP, MAXCUT) e balanceamento de covariáveis (Gram-Schmidt Walk).
3. Aplicabilidade: Oferece ferramentas práticas para pesquisadores e analistas que realizam experimentos em redes sociais, plataformas digitais ou intervenções de saúde pública, onde a interferência e a homofilia são inevitáveis.
4. Robustez: Introduz uma abordagem de "pior caso" que não depende de suposições distribucionais fortes sobre os resultados, tornando os experimentos mais confiáveis em cenários complexos e mal especificados.

Em resumo, o artigo fornece uma teoria e algoritmos robustos para projetar experimentos que são simultaneamente sensíveis à estrutura de rede (interferência), à similaridade dos nós (homofilia) e à incerteza do modelo (robustez).