Modelos de Resposta para Experimentos Randomizados em Redes Sociais de Larga Escala

Francisco Galuppo Azevedo, Bruno Demattos Nogueira, Fabricio Murai, Ana Paula Couto da SilvaarXiv 2018 · DOI · OpenReview

TL;DR

This paper tackles the challenge of accurately estimating the impact of new features in online platforms (like social networks) using A/B tests, especially when user behavior is influenced by their connections. They introduce a novel response model called "τ-Exposure" and provide theoretical bounds for estimation errors, demonstrating empirically that choosing the wrong model can significantly inflate error.

What Problem Does This Paper Address?

Online platforms frequently use A/B tests to evaluate the impact of new features. A key assumption in traditional A/B testing is the Stable Unit Treatment Value Assumption (SUTVA), which states that a user's outcome is independent of others' treatment assignments. However, in social networks, this assumption is often violated due to "spillover" effects – a user's behavior can be influenced by what treatments their friends receive. This makes estimating the true average treatment effect (ATE) difficult. The paper addresses the lack of consensus on which response model best captures these network effects and how to quantify the error introduced by misspecifying the model.

Methods

The authors propose a new response model called τ-Exposure. This model defines a user as "exposed" to a treatment if they receive it and a certain fraction (τ) of their neighbors also receive the same treatment. This captures the idea of a saturation threshold for network influence. They also derive theoretical lower bounds for the estimation error of ATE for various response models, including linear, probit, and logistic models, using the Cramér-Rao Lower Bound. Finally, they conduct empirical studies by simulating data from these models and evaluating the Mean Squared Error (MSE) of different estimators, particularly when the assumed response model doesn't match the true data-generating process.

Datasets

The empirical study uses three real-world social network datasets from the SNAP collection at Stanford:

  • Bitcoin OTC: Represents trust relationships in Bitcoin transactions.
  • Enron Email: Represents communication patterns within the Enron corporation.
  • Wiki-Vote: Represents voting relationships among Wikipedia collaborators.

These datasets differ in size and structure, allowing for a comprehensive evaluation of the proposed methods.

Key Insights and Ideas

  • Network effects are crucial: Ignoring how a user's neighbors are treated can lead to significantly biased ATE estimates, especially when network influence is strong.
  • τ-Exposure offers a nuanced view: The proposed τ-Exposure model provides a more flexible way to model network influence by incorporating a saturation threshold (τ), going beyond simpler neighborhood models.
  • Model misspecification is costly: The empirical results highlight that using an incorrect response model can lead to substantially higher estimation errors (MSE) compared to using the correct model or even simpler, but potentially biased, estimators.
  • Theoretical bounds provide a benchmark: Deriving theoretical lower bounds for estimation error allows researchers to understand the best possible performance for a given model and dataset, and to assess how close their estimators come to this ideal.

Key Results

  • The τ-Exposure model was proposed as a new way to model network effects in A/B testing.
  • Theoretical lower bounds for estimation error were derived for linear, probit, logistic, and τ-exposure models.
  • Empirical studies showed that when the SUTVA assumption is violated, estimators that account for network effects (like τ-Exposure) generally perform better than those that ignore it (like SUTVA).
  • The MSE of estimators can be significantly higher when the assumed response model is incorrect. For instance, in some cases, assuming SUTVA when it's violated led to MSEs orders of magnitude larger than using a correct network-aware model.
  • The paper found that while biased estimators (like Logit and Probit) can sometimes achieve lower MSE than unbiased ones due to a bias-variance trade-off, they still don't always reach the theoretical CRLB, especially when the true model is complex.

Limitations and Future Work

  • Model selection remains a challenge: The paper acknowledges that there's no definitive rule for choosing the best response model for a given dataset, and the error from misspecification depends on the network structure and parameter values.
  • Computational complexity: While not explicitly detailed as a limitation, the complexity of estimating parameters for network-aware models can be a practical concern.
  • Future work could explore: Developing more robust methods for model selection in the presence of network effects, and investigating the impact of different network structures on the performance of various estimators. The authors also suggest further analysis of the bias-variance trade-off for biased estimators.

Summary updated

Abstract

A/B tests are randomized experiments frequently used by companies that offer services on the Web for assessing the impact of new features. During an experiment, each user is randomly redirected to one of two versions of the website, called treatments. Several response models were proposed to describe the behavior of a user in a social network website, where the treatment assigned to her neighbors must be taken into account. However, there is no consensus as to which model should be applied to a given dataset. In this work, we propose a new response model, derive theoretical limits for the estimation error of several models, and obtain empirical results for cases where the response model was misspecified.
BibTeX
@misc{azevedo2018modelos,
  author = {Francisco Galuppo Azevedo and Bruno Demattos Nogueira and Fabricio Murai and Ana Paula Couto da Silva},
  title = {{Modelos de Resposta para Experimentos Randomizados em Redes Sociais de Larga Escala}},
  year = {2018},
  eprint = {1803.03497},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.03497},
}
Figure