A/B Testing in Dense Large-Scale Networks: Design and Inference

Design of experiments and estimation of treatment effects in large-scale networks, in the presence of strong interference, is a challenging and important problem. Most existing methods' performance deteriorates as the density of the network increases. In this paper, we present a novel strategy for accurately estimating the causal effects of a class of treatments in a dense large-scale network. First, we design an approximate randomized controlled experiment, by solving an optimization problem to allocate treatments that mimic the competition effect. Then we apply an importance sampling adjustment to correct for the design bias in estimating treatment effects from experimental data. We provide theoretical guarantees, verify robustness in a simulation study, and validate the usefulness of our procedure in a real-world experiment.


Introduction
Measuring the effect of variants is a fundamental problem in several fields of study such as psychology (Rubin, 1974), epidemiology (Hernán & Robins, 2006), and many other sub-fields in medicine (Armitage et al., 2008). A/B testing is a commonly used method wherein randomized experiments are run with two or more variants. In the internet industry, A/B testing is very widely used in almost every aspect of product design and model improvements (Kohavi et al., 2013;2014;Tang et al., 2010;Xu et al., 2015).
Traditional A/B testing depends on the key assumption that the effect of treatment on an experiment unit is independent of the treatment allocation to other experiment units -commonly called "Stable Unit Treatment Value Assumption" (SUTVA) (Rubin, 1974). However, in many important network settings, this assumption is violated due to interference (Katzir et al., 2012;Toulis & Kao, 2013;Ugander et al., 2013). Estimating treatment effects under SUTVA violation is an important area of research. Several forms of network interference have been studied in the past (Backstrom & Kleinberg, 2011;Katzir et al., 2012;Aronow & Samii, 2012;Gui et al., 2015;Ugander et al., 2013).
In this paper, we focus on one such class of problems -a marketplace of commodity producers and consumers. Producers produce and make a commodity available for consumers, who in turn consume and give some desired utility back to the producers, which incentivizes them to keep producing. An example of such a marketplace is a social media platform, where the commodity is content and the return utility is feedback. Examples include Facebook, Instagram, LinkedIn, Twitter, etc. Other marketplace problems differ primarily on the commodity and return utility in question. Rides are commodities in Uber and Lyft, retail items are commodities in marketplaces like Amazon and eBay, and money is the common return utility.
In the marketplace setting, we define a treatment class represented by an edge-level boost factor, say T ij , where i is the producer and j is the consumer. From a consumer j's viewpoint, the boost factors T .j control or shape the consumer's exposure to different producers. This abstraction represents a very general class of treatments since any redistribution or shift in producer and consumer exposure can be expressed via appropriate edge-level boost factors. In content marketplaces, such treatments can reshape the content creator's exposure to their audience, whereas, in a transportation marketplace, it can reshape the likelihood of specific drivers and riders being matched.
For such treatments in marketplace problems, SUTVA is violated because of interference from the network. For instance, when we consider commodity producers as the experimental units, the effect of treatment on a producer is influenced by the effect of the treatment on all potential consumers of that producer, which in turn depend on each of their producers' experiences -thus leading to competition among producers connected to common consumers. For commodity consumers as well, SUTVA could be violated since a consumer's experience is determined by all of their potential producers.
When SUTVA is violated, then the primary principle used to measure the effect of treatment is to allocate experimental units as well as their first-degree neighbors (or first and second-degree neighbors, depending upon the interference arXiv:1901.10505v1 [stat.ME] 29 Jan 2019 function) to the same treatment (or control) (Eckles et al., 2017). The number of such units for which we can successfully allocate treatments in this fashion (i.e., whose neighborhood is appropriately treated) decrease with increasing density in the graph. Fewer experimental units result in lower statistical power in the measurements.
In this paper, we propose a novel technique named OASIS, "Optimal Allocation Strategy and Importance Sampling Adjustment", that provides a randomized testing framework for large-scale marketplace problems in the presence of interference. Our method actually works very well with dense graphs (with an increase in density being more helpful) and can be used to obtain high-power measurements as our approach does not require to allocate all first-degree (and second-degree) neighbors of an experimental unit to be in the same treatment. Our approach relies on the existence of an "intervening variable" -i.e., the effect of the treatment allocation to a unit's network on the experimental unit is fully captured by a sufficient statistic (cf. Arellano & Bover (1995); Cragg & Donald (1993);MacKinnon et al. (2002)). In marketplace problems, the total feedback received by a producer is a good example of such an intervening variable. The producers in a marketplace compete with each other for receiving feedback, and we attempt to mimic this competition effect in the design of experiment as much as possible. Furthermore, we construct an unbiased estimator of the treatment effect by applying an importance sampling correction. We show both from simulation studies and from a real-world experiment on a large social network graph that our technique works quite well for large-scale dense graphs. The method is also robust to small unknown deviations from the key assumptions. This technique can be used in any marketplace problem where the treatment in question can be expressed via the T ij abstraction, and where the key assumptions (outlined as Assumption 1, 2 and 3 in later sections) are satisfied.
The rest of the paper is organized as follows. In Section 2 we formulate the problem and discuss the setup in detail.
The key aspects of how we design an experiment via an optimization formulation are described in Section 3. We propose the OASIS estimator and provide theoretical guarantees in Section 4. In Section 5, we provide some empirical results both from an elaborate simulation study and a realworld experiment on a large social network graph, before concluding with a discussion in Section 6.

Problem Setup
A content marketplace can be represented as a graph, where every member is a node, and can be both a producer and a consumer. In mathematical terms, let us consider a network (or graph) G = (Ω, E), where Ω denotes the set of all members (or nodes) in G and E denotes the set of edges in G. We denote the set of neighbors of a member i in G by Ne(i) = {j : (i, j) ∈ E}. A producer i can only influence the set of consumers Ne(i) and a consumer j can only be influenced by the set of producers Ne(j). Let p base ij denote the normalized influence of producer i on consumer j so that we have i∈Ne(j) p base ij = 1 for all j. For example, p base ij can be the conditional probability that consumer j views a content produced by i given that consumer j views a content produced by Ne(j). A treatment T ij is a boost factor to the influence of a producer i on consumer j and we define T E = {T ij : (i, j) ∈ E}. Therefore, the normalized influence of producer i on consumer j in the treatment condition T E is given by (1) where Y (T E ) denote the response of a randomly chosen member when the entire population is under treatment condition T E . We consider m treatments T (1) E )} from a single randomized experiment. To this end, we randomly select m+1 disjoint subsets Ω 0 , . . . , Ω m of Ω. We aim to design an experiment T * E such that members in Ω r have the experience of the treatment condition T (r) E for all r = 0, . . . , m simultaneously. In order to quantify member experience, we make the following assumptions. Assumption 1. The response of member i depends on the treatment condition T E only through 1. The exposure of producers in Ne(i) to consumer i, defined as {p : k ∈ Ne(i)}, and 2. The total exposure of producer i to consumers, denoted by Z i (T E ).
Assumption 2. The total exposure of producer i to consumers Z i (T E ) depends on the treatment condition T E only through j∈Ne(i) α ij p for some constants α ij 's representing the strength of the relationship between producer i and consumer j. We further assume that α ij 's do not depend on the treatment condition T E .
An example of α ij can be the total number of interactions received by member i from member j when member j views i's content. In this example, Z i (T E ) would denote the total expected feedback received by member i. When α ij 's are known, it is natural to design an experiment T * E comprising of probabilities p * ij such that, 1. Exposure as consumer is satisfied. That is, for any i ∈ Ω r , r = 0, . . . , m and for all k ∈ Ne(i) we have 2. Exposure to consumer is matched. That is, If we are able to design such an experiment, then under Assumptions 1 and 2, an estimator of τ (T (r) In the following section, we discuss a strategy for designing T * E which satisfies the above two requirements under some constraints that control the risk and exposure of the experiment. We also theoretically demonstrate the robustness of our estimator under the violation of the assumption that α ij 's are known. In Section 4.2, we propose an importance sampling based modification of the estimatorτ (T (r) E ) that does not rely on the definition of the total exposure of a producer given in Assumption 2.

Design of Experiment
Let us denote Ω = ∪ m r=0 Ω r which we shall use for the rest of this paper. In this section, we construct an experiment T * E satisfying (2) and (3). Note that, since the probabilities are edge level, it is possible to easily obtain (2), by defining ki for all i ∈ Ω and k ∈ Ne(i). Thus, for all members chosen in the experiment, we can guarantee that their exposure as a consumer will match the true exposure as if the entire universe was exposed. Constructing T * E to satisfy (3) is a much harder task. We construct the experiment to satisfy (3) under the following constraints: 1. T * ij = 1 for all j ∈ S, where S is a randomly chosen subset of Ω satisfying E[|S|/|Ω|] = b and S ∩ Ω = ∅ for some pre-specified b < 1. This condition controls the risk of the experiment by forbidding a set of consumers S (disjoint from Ω ) to be exposed to treatment.

P[T
r∈0 Λ r is a set of consumers with predefined treatment allocation (described in details in Section 4.2). This condition controls the expected number of neighbors of a producer to be exposed to the experimental condition. The reason for letting q i 's depend on producer i is that we may want q i to be a function of the degree of member i.
3. T min ≤ T * ij ≤ T max , for some constants T min , T max satisfying 0 ≤ T min ≤ 1 ≤ T max . This third condition provides us a control over the maximum and the minimum value of the modified boost factors to be applied.
In Algorithm 1 we construct T * E , where for each producer i ∈ Ω we randomly choose a subset of neighbors ki for all k ∈ Ne(i), i ∈ Ω r ∪ Λ r and r ∈ {0, . . . , m}; 2: For each i ∈ Ω , construct a subset of neighbors C i by selecting each member in Ne(i) \ (Ω ∪ S ∪ m r=0 Λ r ) with probability q i ; 3: Obtain {p * ij : j ∈ C i , i ∈ Ω } by solving the optimization problem given in (5); C i respecting the first two conditions. Then we obtain {p * ij : j ∈ C i , i ∈ Ω } by solving a constrained optimization problem such that condition (3) is satisfied (detailed in Section 3.1). Finally, we obtain the modified boost factors as Note that that above choice of T * ij comes from the fact that if we use that in (1) we get, p

Optimization Problem
To satisfy (3) we would want to get p * ij which minimizes, under certain constraints. Recall that some of the p * ij are fixed by (2) and risk control (condition 1). Thus, we only need to find We add constraints to the optimization problem in a way such that T min ≤ T * ij ≤ T max . We choose 0 < R min < 1 < R max in order to control the ratio ∈ Ω } is defined as a solution of the following optimization problem:

Scaling the Problem
Solving the above optimization problem (5) is not an easy task especially when the number of edges n = |{(i, j) : i ∈ Ω , j ∈ C i }| is large. Even in moderately sized experiments in social network graphs, we can expect n to range in billions. Solving the generic quadratic programming (QP) problem in that scale is almost close to impossible. Thus, in order to be able to solve such a problem, we devise the following algorithm which solves it through an iterative approximation approach.
Let S denote the set of all consumers in the optimization formulation, that is, S = ∪ i∈Ω C i . We split this group of consumers into disjoint sets S k of roughly equal sizes, such that S = ∪ K k=1 S k . Since this induces a natural partition in the constraint space of (5), it is easy to see that any candidate solution {p old ij : i ∈ Ω , j ∈ S} of (5) can be improved by updating {p old ij : i ∈ Ω , j ∈ S k } with the solution of the following optimization problem, for all k ∈ {1, . . . , K}.
Note that (6) and (5) have the same set of constraints for each j ∈ S k , since {i : We provide an efficient strategy in Algorithm 2 to solve the overall optimization problem. We start with a feasible candidate p old ij = p base ij and run an iterative scheme to update p ij using (6) as we loop over each k = {1, . . . , K}. Once this inner loop completes, we get the full next best {p ij : i ∈ Ω , j ∈ S}. We continue the outer loop till convergence. By doing this iterative scheme we are able to solve much larger problems, since size of the each optimization problem n k := |{(i, j) : i ∈ Ne(j) ∩ Ω , j ∈ S k }| is much smaller than n. In fact, the worst-case complexity of the iterative method with nIter outer iterations is given by O(nIter × K k=1 n 3 k ), while the worst-case complexity of the original optimization problem (5) is O(( K k=1 n k ) 3 ). Moreover, we can tune on the size of the partition of S such that we can optimize the on the total time given the memory restriction on the QP solver. We use the Operator Splitting method to solve individual QP (Stellato et al., 2017;Banjac et al., 2017a;. Algorithm 2 Solving for Optimal p ij 1: Input: Group Size g, tolerance level tol, Outer Iteration Limit maxIter 2: Initialize the p ij = p Solve the optimization problem as in (6) ij for all (i, j). 10: end for 11: Return the optimal p * ij = p (maxIter+1) ij

Theoretical Analysis
In this section, we theoretically demonstrate the robustness of our estimator under the violation that the α ij 's are known. We also derive an unbiased estimator based of τ (T (r) E ) via importance sampling that does not depend on the definition of total exposure. All proofs are pushed to the supplementary materials for brevity.

Robustness
In order to demonstrate robustness of our experimental design when Assumptions 1 and 2 hold but α ij 's are not known, let us assume that we construct an experiment T * E by randomly perturbing p for some known β ij 's. In the following theorem, we show that as long as the random perturbation does not depend on β ij p where g is a differentiable function with respect to the first coordinate, such that {U * ij : j ∈ Ne(i)} are identically distributed random variables satisfying If there exist an experimental design T * E such that

Importance Sampling Adjustment
We have assumed that response of producer i depends on the total exposure or feedback obtained from all consumers which we denoted by Z i (T E ). That in turn was assumed to depend only through j∈Ne(i) α ij p . As a result, we wanted to match on the above quantity. However, in many cases, we would not be able to exactly match this quantity for every i. As a result, we only requested an approximate matching (3) in our experimental design. In this section, we describe a method that allows us to get an unbiased estimator of τ (T (r) E ), even when we are only able to get an approximate matching. We begin with a formal assumption. Assumption 3. There exists an observable random variable X i (T E ) such that the conditional distribution of Y i (T E ) given X i (T E ) depends on the treatment condition only through W i (T E ), an unknown function of {p Note that when Assumption 1 holds, Assumption 3 implies that Y i (T E ) and Z i (T E ) are independent conditionally on X i (T E ) for any treatment condition T E . Furthermore, Theorem 2. Let f r denote the density of X(T (r) E ), and let f * r denote the density of X i (T * E ) conditionally on i ∈ Ω r , where T * E is the output of Algorithm 1. We definê .
Remark. Note that this allows us to skip Assumption 2 while doing the experimental design. However, from a practical standpoint, if we (approximately) know the dependency of Z i (T E ), we should definitely use it to do the matching while designing the experiment. The design of experiment step is crucial for reducing the variance of the importance sampling weights as well as the corresponding estimator.

Density Estimation
The densities f * r and f r are unknown and we need to estimate them from the data. Since we observe {X i (T * E ) : i ∈ Ω r }, any parametric or non-parametric density estimation method can be applied for estimating f * r . For estimating f r , we make the following additional assumptions: , where X 1 d = X 2 denotes that X 1 and X 2 have identical probability distributions. E ) : j ∈ Ne(i) ∩ Λ r , i ∈ Ω r , r = 0, . . . , m} are observable for sets of members Λ r ⊆ ∪ i∈Ωr Ne(i) (see Algorithm 3).

Assumption 5. For each treatment condition T
Assumption 4 allows us to obtain an estimate of f r by adjusting the mean and the variance of an estimated f * r . Assumption 5 facilitates the estimation of moments of X(T (r) E ) from the data {X ij (T (r) E ) : j ∈ Ne(i) ∩ Λ, i ∈ Ω r }. In following theorem, we propose consistent estimators of the first and the second moments of X(T (r) E ). Theorem 3. Fix r ∈ {0, . . . , m}. Let Λ r be as in Assumption 5. Assume that are independent of |Ne(i)|, µ i and σ 2 i . We define Then, under Assumption 5, In the following algorithm, we propose a method for selecting {Λ 0 , . . . , Λ m } such that Λ r ⊆ ∪ i∈Ωr Ne(i). It is easy to verify that Algorithm 3 does not introduce any selection bias for choosing Λ r in the sense that each member in ∪ i∈Ωr Ne(i) has the same probability to be included in Λ r . Note that we use the same {Λ 0 , . . . , Λ m } in Algorithm 1.

OASIS
We conclude this section by gluing all the pieces together in the following algorithm, called Optimal Allocation Strategy and Importance Sampling Adjustment (OASIS).

Algorithm 4 OASIS
Output:τ (T Computeτ (T (r) where Φ is the CDF of the standard normal distribution.

Experiments
In this section, we describe an in-depth simulation study to demonstrate the robustness of our method under moderate violations of Assumptions 2 and 3. Furthermore, we compare OASIS with an oracle cluster-based method that uses a given set of clusters for applying full treatments to all members in a randomly chosen cluster. We also apply our technique to a real-world experiment on the LinkedIn graph. We were able to validate our mechanism by being able to match the results for a full population experiment. The details are given below.

Simulation Study
We generate a random graph G with |Ω| = 50000 vertices and the average degree equals 100 as follows. We first obtain a graph G BA = (Ω, E BA ) by combining 10 randomly generated graphs with 5000 vertices and average degree equals 80, where each graph is generated according to the Barabasi-Albert model (Barabási & Albert, 1999) with the power of the preferential attachment equals 0.25. Then we generate an Erdös-Rényi graph (Erdös & Rényi, 1959) G ER = (Ω, E ER ) with 50000 vertices and average degree equals 20, where all pairs of nodes have an equal probability of being connected. Finally, we obtain G = (Ω, E BA ∪ E ER ). For each ordered pair of edge (i, j), we independently generate α ij and p base ij from the following distributions: where d j denotes the degree of node j, U ij 's are i.i.d. U nif orm[10, 100] random variables and V ij 's are i.i.d. U nif orm[1, 2] random variables. For all treatment conditions T E , we define where η ij 's are independently distributed N (0, (d i d j ) −1 ) random variables. Next, we define where g(x) = 10/(1 + exp(−x/10)), β ∈ {0, 1} and i 's are independently distributed as a standard Gaussian random variable. Note that β = 0 corresponds to the absence of the second order effect. Furthermore, the strength of the second order effect Z i (T E , δ) decreases as δ increases. Finally, we define We consider three different treatment conditions corresponding to γ ∈ {0, 0.5, 1.5}, where γ = 0 corresponds to the control case.
It is easy to see that our simulation setting respects Assumption 1. Assumption 2 is satisfied if and only if δ = 1 and α ij 's are known, and Assumption 3 is satisfied if Z ij (T E , δ)'s are observable. In order to verify robustness of our method, we do not assume that α ij 's are known, and we apply Algorithm 1 for constructing T * E assuming α ij = 1. Furthermore, we assume that we are able to observe only a noisy version of Z ij (T E , δ), given by Therefore, we apply the importance sampling correction based on estimated densities of X i (T * E , δ) and X i (T E (γ, δ)), where X i (T E , δ) := j∈Ne(i) X ij (T E , δ). In particular, we assume that both X i (T * E , δ) and X i (T E (γ, δ)) have Gaussian distributions and we estimate the moments using the technique described in Section 4.3. The detailed parameter setting are given in the supplementary material.
We use OASIS (see Algorithm 4) with the self-normalized importance sampling 1 wi Y i w i , as it is known to have a more stable behavior in practice. Furthermore, we apply the bootstrap method for estimating the variances of the OASIS estimators, as described in Section 4.4. Table 1 demonstrates that the OASIS estimator can achieve satisfactory coverage probability even under violations of the underlying assumptions, except for the few cases corresponding to strong violations of assumptions 1 .
Next, we compare OASIS with an oracle cluster-based method that takes advantage of the presence of disjoint connected components in G BA to design the following experiment: where H(γ)'s are randomly chosen disjoint connected components of G BA for γ ∈ {0, 0.5, 1.5}.   Figure 1 shows that OASIS performs equally well or slightly better than the oracle cluster-based method in all simulation settings, except for β = 1 and δ = 1.5. This could be explained by the facts that (i) smaller values of δ tend to induce more bias in the cluster-based estimator, and (ii) larger values of δ lead to stronger violations of Assumption 3 as the observed variable X i (T E , δ) suffer from low signalto-noise ratio.

Real World Experiments
Although the above-described simulation study shows the robustness of our technique, we were interested in validating the result on a real-world experiment. In order to do so, we considered the LinkedIn social network graph. For simplicity, we only considered a single experimental setting T E = {T ij : (i, j) ∈ E}, where T ij are the boost factors for boosting content from producer i to consumer j and E is the set of all edges in the LinkedIn connection graph. We aim to validate our method by matching the feed metric measurements with a proxy of the 100% ramp on Ω. Since we lack an oracle, in this case, we create the following group of randomized members.
1. True Treatment Producer (M 1 )-These members have their entire first degree exposed to the treatment. Moreover, the first degree will see boosts from all eligible producers. Their behavior will mimic the 100% ramp on Ω. We fix this to 0.5% of the members.
2. Balanced Treatment Producer (Ω 1 ) For these members, we apply our mechanism. That is, we randomly pick some of their first degree members and appropriately change the boost factors so that the total interaction received (an approximation of Z i (T E )) is similar in distribution to M 1 . We keep this set to 1%.
This experimental setup is slightly different than that usual A/B testing setup. Here, we want to match the OASIS estimate with an unbiased estimate of the true effect, obtained from M 1 . Note that we cannot have a pure control group simultaneously with M 1 , since the graph is not separable. Thus, we compare the treatment effects with the control effect estimated before the start of the experiment. We would consider this experiment a success if we are able to match the metric reads from M 1 with Ω 1 . Remark. Even with such a small ramp, the total number of members and edges that were exposed to T * ij = 1 was about 13 million and 130 million respectively.
We ran the experiment for a week and observed that there was no significant impact on the consumer side metrics (such as clicks, likes, comments, etc). For the producer side metrics (such post creations, contributions, etc) we saw that there were significant differences between both M 1 vs control and Ω 1 vs control, which was expected. For proper validation, as explained before, we were interested in comparing M 1 vs Ω 1 . In doing so, four metrics came to be significant at the 5% level, namely mobile messaged from feed (m 1 ), mobile shares from feed (m 2 ), all messages from feed uniques (m 3 ) and mobile messages from feed uniques (m 4 ). However, after importance sampling adjustment, we were able to correct the p-values and all metrics were insignificant at the 5% level (see Table 2). All other feed related producer side metrics when compared between M 1 and Ω 1 were non-significant, thus verifying our network measurement mechanism was working as expected in real dense graphs. All parameter settings are given in the supplementary material.

Discussion
We have presented a two-step method, called OASIS, for estimating the average treatment effect for a class of continuous treatments in networks with interference. First, we design an experiment by optimally allocating treatment exposure to a set of randomly selected consumer-producer pairs in the network. We solve a large-scale linearly constrained quadratic program to achieve this optimal allocation of the treatment exposure. Secondly, we apply an importance sampling correction for estimating the average treatment effect from the experimental data. The importance sampling adjustment corrects for the design bias induced by the violations of assumptions and/or the restrictions applied to the optimization problem for controlling the risk of the experiment. We estimate the variance of the OASIS estimator by applying the bootstrap method. The correctness of the OASIS estimator relies on a number of assumptions, and we demonstrate the robustness of OASIS to moderate violations of these assumptions with an extensive simulation study. Finally, we validated the usefulness of OASIS with a real-world experiment on a large network.
OASIS provides a number of interpretable, tuning knobs for controlling the risk of the experiment as compared to cluster-based methods. These knobs can be set to their extreme values to make the design the most favorable to the OASIS estimator. A crucial advantage of the OASIS estimator is that it tends to perform better for dense networks, while the cluster-based method would have an advantage over OASIS for sparse networks that can be easily decomposed into clusters. An interesting future work could be to combine a cluster-based approach with OASIS in order to gain additional robustness and efficiency.
For some marketplaces (e.g., Uber, Lyft, Amazon), the graph is inherently dynamic or partially known. Our work assumes that the graph is completely known and fixed. Approximating a dynamic graph with a static graph which includes the various possibilities can work, but would not scale well. Hence, we will need to extend our method to partially known and/or temporally dynamic networks. We recognize this as an important and challenging future work.
This completes the proof. Therefore, where the last equality follows from (9) and the fact that ρ i and µ i d i are independently distributed.
Next, it follows from similar calculations that Furthermore, it is easy to verify that ρ 2 Using the independence of (ρ i , ρ i ) and (d i , µ i , σ i ), we obtain Hence, we have,