Cluster Randomized Designs for One-Sided Bipartite Experiments
Authors: Jennifer Rogers Brennan
Vahab Mirrokni
Jean Pouget-Abadie
Venue: NeurIPS 2022 Accept (2022)
Keywords: causal inference
network interference
marketplace experiments

Abstract: The conclusions of randomized controlled trials may be biased when the outcome of one unit depends on the treatment status of other units, a problem known as \textit{interference}. In this work, we study interference in the setting of one-sided bipartite experiments in which the experimental units---where treatments are randomized and outcomes are measured---do not interact directly. Instead, their interactions are mediated through their connections to \textit{interference units} on the other side of the graph. Examples of this type of interference are common in marketplaces and two-sided platforms. The \textit{cluster-randomized design} is a popular method to mitigate interference when the graph is known, but it has not been well-studied in the one-sided bipartite experiment setting. In this work, we formalize a natural model for interference in one-sided bipartite experiments using the exposure mapping framework. We first exhibit settings under which existing cluster-randomized designs fail to properly mitigate interference under this model. We then show that minimizing the bias of the difference-in-means estimator under our model results in a balanced partitioning clustering objective with a natural interpretation. We further prove that our design is minimax optimal over the class of linear potential outcomes models with bounded interference. We conclude by providing theoretical and experimental evidence of the robustness of our design to a variety of interference graphs and potential outcomes models.

Cluster Randomized Designs for One-Sided Bipartite Experiments
Jennifer Brennan"
Vahab Mirrokni Google Research New York, NY 10011 mirrokni@googla com
Jean Pouget-Abadie Google Research New York, NY 10011 jeanpa@google.com com
Paul G. Allen School of
Computer Science & Engineering, University of Washington Seattle, WA 98195 jrbrennan@google.t com com
Abstract
The conclusions of randomized controlled trials may be biased when the outcome of one unit depends the treatment status of other units, problem known interference. In this work, we study interference in the setting of one-sided bipartite experiments in which the experimental where treatments and outcomes are measured-de not interact directly. Instead, their interactions are mediated through their connections interference units on the other side of the graph. Examples of this type of interference are common in marketplaces and two- sided platforms. The claster-randomized design is popular method to mitigate interference when the graph is known, but it has not been well-studied in the one-sided bipartite experiment setting. this work, we formalize natural model for interference in one-sided bipartite experiments using the exposure mapping framework. We first exhibit settings under which existing Aluster-randomizes designs fail to properly mitigate interference under this model. We then show that minimizing the bias of the difference-in-meann estimator under our model results in balanced partitioning clustering objective with a natural interpretation. We further prove that our design is minimax optimal over the class of linear potential outcomes models with bounded interference. We conclude by providing theoretical and experimental evidence of the robustness of our design to variety of interference graphs and potential outcomes models.
randomized
Introduction
Interference is well-studied phenomenon in causal inference, whereby the treatment status of one unit can affect the outcome of another. Formally violation of the Stable Unit Treatment Value Assumption [1]. interference has been studied in many settings, including agricultural studies [2]. clinical trials [3], social networks [chap. 16 4, 5, 6, 7]. and marketplaces [8, 9, 10, 11, 12]. Marketplaces exhibit unique forms of interference because they involve two types of units: buyers and sellers. Units of the same type do not interact directly, but rather their interactions are mediated through their interactions with units of the opposite type. For example, when buyers compete to buy limited goods, an increase in the price one buyer is willing to pay for good will affect the market-clearing rate for that good, thus increasing the price for all other buyers.
Marketplace experiments can conceptualized running an experiment on a bipartite graph between buyers and sellers, with edges representing buyer-seller interactions. Other settings beyond marketplaces can also formalized bipartite graphs, such as content platforms (matching viewers to creators) or ride-sharing apps (matching riders to drivers) [13]. We consider perhaps the most
Work done while the author was an intern at Google Research, New York, NY.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

straightforward way of running an experiment on bipartite graph: by treating and measuring single side of the graph, a setting we call the one-sided bipartite experiment framework. We refer to the units on this side of the graph as experimental units since they receive treatment and their outcomes appear in our estimators. We refer to the units on the other side of the graph as interference wnits: while they do not explicitly receive treatment, they mediate the interactions between experimental units.
The presence of interference units distinguishes one-sided bipartite experiments from other settings of network interference because the interactions between experimental units are known in the latter case, but must be inferred from the interactions with interference units in the former. In this work, we show that a popular class of experimental designs for network interference, does not extend immediately to this setting. Instead, we propose variant of the cluster-randomize design, with a clustering objective that accounts for the way which interference units mediate the interference between experimental units. We motivate the use of the difference-in-mennt inemnass estimator in this setting and show that clustering according to our objective minimizes the bias of that estimator in minimax sense over the class of linear potential outcomes models with bounded interference. We further illustrate the failure of existing clustering designs when applied to one-sided bipartite experiments, and conclude by illustrating the robustness of our design to a variety of potential outcomes models and bipartite graphs both theoretically and empirically.
designs.
1.1 Related work
Accurate estimation of the treatment effect requires some knowledge of the mechanism of interference [14]; otherwise, having even a single treated (resp. control) unit in a graph of control (resp. treated) units could change the outcome of every unit arbitrarily. Existing work varies in the strength and nature of the assumptions on the interference model, but in general these assumptions take one of two types. The exposure mapping approach [3, 15], formalized by Aronow and Samii [16], defines a notion of when a unit is "completely treated" or "completely controlled," then uses the inverse propensity score (IPS, also known as Horvitz-Thompson estimate of the average treatment effect. By contrast, an alternate approach is to propose model for the effect of interference on the potential outcomes, and then rely on this model to estimate the average treatment effect using data from all units (even the ones experiencing a great deal of interference) 16. 17, 18, 19]. Since the quality of the estimate depends on the accuracy of the modeling assumptions, several methods have been developed to estimate the magnitude and form of interference [5. 20, 21, 22, 23, 24]. Chin [25] lessens the reliance on the form of the interference model by developing a madel-agnostic regression estimator that reduces average treatment effect estimation to problem of feature engineering; however, it assumes that each unit's response follows a shared (but unknown) model, which is more restrictive than the potential outcomes model we use in this work.
estimator construct an unbiased
Even in cases when the model is only approximate, so that including data from units experiencing interference may bias the estimator, Eckles et al. [17] use realistic graph models to argue that the bias incurred is more than offset by the reduction in variance achieved by avoiding an IPS estimator. Our work assumes this same regime, in which the graphs are sufficiently dense that an IPS estimator will be too high-variance to be practical, so we accept an estimator with some bias. We assume a linear model of the potential outcome on the measured exposure, as done in [6, 19]. To avoid strong dependence on the linear assumption, we use the difference-in-nie meens estimator which does not rely on the model of interference, and we choose our experimental design to be minimax optimal over the class of linear potential outcomes models.
Given some model of interference and a choice of estimator, the next question is how to design an experiment (an assignment of units to treatment or control). The most popular experimental design in the case of network interference is the cluster-randomized design, studied by [26, 17, 27] in the case of non- bipparttee graphs. This design first clusters units according to the provided graph, and then assigns each cluster to either treatment or control. In the specific case of bipartite graphs, other works propose modifications to unit-level randomization by choosing which side of the graph to randomize (28, 10, 29]. The authors of [18, 19] look directly at clustered designs on bipartite graphs, but they study a two-sided experimental framework in which one side of the graph is randomized while the other is measured. Perhaps closest to our work is that of Rolnick et al. [9], which suggests a balanced partitioning of geographical regions using clustering objective that is similar to ours. Their work

---

considers a more restrictive form of the potential outcomes model, and uses clustering heuristics that are specific to the geographical setting. By contrast, our work considers the robustness of the design to broader class of potential outcomes models and extends beyond geographical regions to general interference graphs.
2 Models and estimators
We now formalize the interference model using the potential outcomes framework [30]. Let Z 1-1,1) be an assignment of each of the N experimental units to treatment (Z = 1) or control (Z -1). The potential outcome of the 7t experimental unit denoted Y,, and in the most general setting could be function (Z) of the entire treatment assignment vector. We further assume the existence of a (known) bipartite graph between experimental units and interference units, with nonnegative weights w 2 0 encoding the relationship between experimental unit and interference unit 8. Such a graph may be obtained from historical data on interactions between units i and 8, or on similarity between and measured by geography other features [9, 31].
While there are many possible estimands of interest, our primary goal to estimate the average total treatment effect 인 Eig[N] Y =) Yi -1), sometimes referred to as the average treatment effect or total treatment effect. Since we assign some units to treatment and others to control, it is impossible to observe any potential outcome under a fully treated (Z = 1) or fully controlled (Z = 1) condition. If the underlying interference graph among units were composed of multiple connected components, so that only the assignments Ž in a unit's connected component affected its potential outcome, then it would be possible to assign treatment at the level of the connected component and observe fully treated or control outcomes. However, in realistic marketplaces, such a perfect separation almost never occurs. As result, we require some modeling assumptions the potential outcomes to infer the behavior of unit under the fully treated or controlled condition.
2.1 The potential outcome model
A popular approach modeling potential outcomes with network interference is the exposure mapping paradigm [3. 15, 16). An exposure mapping is a function e; {-1, + IR such that Y; (2,,, (Z)) = (Z). In other words, the indirect effect of Zizt unit is captured completely by the exposure e; (Z). When it is clear from context, we will write e, instead of e; (Z) to denote the exposure of unit Given an exposure mapping, we can further posit model for the effect of assignment Z and exposure e; on the outcome Y, We principally consider the linear model
(Z) = a, + 3,2, + 7/E5,
(I)
which is commonly used in the interference literature [6, 19]. although other models are discussed in Section 4. Following the tradition of the finite population model, first defined by Neyman [2). we treat the coefficients as, 8& and 7 as fixed but unknown so that the only randomness in the observation model is due to the choice of treatment assignment Z. This contrasts with alternatives such as a model in which coefficients are drawn from some super-population or a model in which the coefficients common across with some additive error term in the linear model [25]. The finite population model avoids making assumptions about a population from which experimental units are drawn, and for this reason is often preferred in the causal inference literature [32, 33].
2.2 The exposure model
The literature on network interference typically defines the exposure e, as a function of the treatments of the neighbors of [3, 15, 16]. For example, the exposure mapping might be the (weighted) fraction of neighbors that are treated [17]. or the count of neighbors that are treated [26]. In the bipartite setting, experimental units are never immediate neighbors. Instead, experimental units interact through their relationships with interference units. Defining an exposure mapping that is analogous to those used in the network setting requires an analogous definition of the "neighborhood" of an experimental unit, as well as the weight of the connections from a unit to each of its neighbors.
We propose bipartite analogue to the neighborhood parts: the dose d, E [-1,1] of each interference unit & [M] represents the weighted average of the treatment assignment Z, of each experimental unit in the neighborhood of s, while the exposure
exposure mapping, composed of two
3

---

Original Bipartite Graph
Graph Induced by Exposure Mapping
RausoreRanddmiized According H(C)
Experimental Units
Interference Units
E [M]
E Siwet
"exposure"
"Mowe"
Auigrment
R/s "weight"
Figure 1: Overview of our bipartite graph connecting experimental units (left) with interference units (right) with edges of known weight Assigning treatments Z, E 1} each experimental unit induces dose d, on each interference unit, and an exposure e; on each experimental unit. Middle Panel: The exposure of experimental unit depends the assignment of other experimental units which induces graph on the experimental units. Right Panel: Clustering the experimental units based on the induced graph creates clusters of units which heavily influence each others' outcomes. Randomizing the treatment assignment at the level of the cluster provides exposures e; that are much closer to the treatment Z; than would be achieved with unit-randomized design.
experimental design. Left Panel: We are given
E [- of cach experimental unit i [N] represents the weighted average of doses among the interference units in the neighborhood of i:
d, LiE[N] Wis
Σ KE[N)
Wis Zi,
6 E
Σ
Wisdg.
[M] Wis
.E|M]
See Figure 1 for illustration of the exposure mapping. Because the exposure thus defined can be written as linear combination definition of exposure can be viewed in which we must impute the effective "assignment" of interference units s from the assignments of their neighbors. Depending of these terms as an unnormalized linear combination instead of convex combination; we show in Appendix A that all of our results apply the unnormalized setting well.
treatment assignments of the two-hop neighbors unit i, our
exposure mapping where depends on two-hop neighbors.
the problem instance, it may be more appropriate write one both
2.3 Estimators
Estimators for the average total treatment effect r under network interference typically fall into one of two categories: difference-in-men in-meess (DIM) estimators and inverse propensity score (IPS) estimators. The former reports the difference between the mean of Ny treated units and the mean of No control units, where we treat Nr and No as fixed quantities chosen before treatment randomization occurs. The latter requires a notion of which units are "fully exposed" to treatment or to control, perhaps defined by e,, and reweighs fully exposed observations by the inverse probability of achieving that state.
TDIM
Y Σ 2,=1
Y No
FiPs
1 N
Σ VE(N
Yi fully treated)
Y1 (i fully controlled)
Pii fully treated)
P(i fully controlled)
2,=-1
The difference in means estimator can suffer from bias in the presence of interference, because both the treated and control means may be biased estimates for their population quantities n Σ. (1)1) and n E, (-1), respectively. The IPS estimator is unbiased as long "fully treated" unit does in fact behave like unit in which Z = 1 (and likewise for control), however, this comes at a cost high variance if the propensity scores are small. our linear model, full exposure only occurs when e; = Z, which requires all experimental units in the two-hop neighborhood of to have the same assignment as In many realistic bipartite graphs the chance of full exposure for given unit is very low, increasing the bias in the IPS estimator to unacceptable levels. Appendix B IPS estimator for selection of simulated bipartite graphs and variety of definitions of "full treatment." The difference-ing -nnnnnnee----sssss means estimator also has the ad advantage
illustrates the high variance

---

that it outperforms the IPS estimator in the setting of no interference. Y((Z) Yi(),), since in this setting Fpras is unbiased and has the same or lower variance than PyPs for any definition of full exposure. As result, the difference in means estimator can be seen as an "optimistic" choice of estimator, which makes better use of the data the case of no interference while incurring bias in the presence of interference. For the reasons described above, we focus on the difference in means estimator in this work.
3 Experimental design
Having chosen the linear potential outcomes model of Equation (1) with the exposure mapping of Equation (2) and the difference-in -eennce----manss means estimator FDIM. we seek a mechanism for randomly assigning experimental units to treatment or control that achieves low mean squared error (MSE) in recovering the average total treatment effect т. The MSE can be decomposed into the bias and the variance, where the former is caused by interference and the latter is primarily a function of the number of units randomized to treatment and control. Following previous works [26, 17, 27], we consider the class of balanced
designs, formalized in Definition 3.1.
Definition 3.1 (Balanced K-cluster randomized design), Let C {CeY be partition of the N experimental units into K equally sized clusters. balanced K-cluster randomized design D(C) is distribution over vectors Z E 4-1,1y7 generated by assigning Zi = 1 for all experimental units i belonging to a set of KT E (0, K) clusters chosen uniformly at random among all K clusters.
If the clustering faithfully captures patterns of interference, cluster randomization can increase the chance that a treated (resp. control) unit is highly exposed to treatment (resp. control), thereby reducing the bias in FDIM-
We control the variance of the estimator by enforcing a balanced clustering, so that assigning a fixed fraction of clusters to treatment results in consistent fraction of units assigned to treatment. Since cluster randomization can change the effective number of experimental units [9, Section 4.2), the variance of FDIM will depend the number of clusters chosen. In practice, the variance under given clustering can typically be estimated using historical data, often called an A/A test. Practitioners can use these estimates to control the variance in light of the anticipated effect sizes. The bias due to interference, however, is not estimable with historical data when all such data is observed under the control condition. Balanced clustering also has practical implementation benefits, which discuss further in Appendix E.
Since the variance can be estimated from historical data and controlled by the number of balanced clusters, we choose to focus on identifying a clustering that minimizes the bias of TDIM given a fixed number of balanced clusters. Choosing the correct number of clusters trade off bias and variance remains an important direction for future work.
3.1 Existing designs do not work in the one-sided bipartite setting
natural question is whether existing approaches to cluster-randomized designs are adequate for setting of one-sided experiments bipartite graphs. In this section, consider the natural extensions of two clustering algorithms from the literature to our setting and describe failure modes for each of them.
Direct clustering of the bipartite graph. Cluster-randomizze designs have primarily been studied in the context of graphs in which all units are experimental units, such social networks [26, 17]. Within the class of randomieedd designs, balanced partitioning has been suggested as a means to minimize bias [17]. The natural analog in the bipartite setting is to create balanced partitioning of the bipartite graph according to the provided edge weights Wie; this extension was considered as baseline in different bipartite setting by Pouget-Abadie et al. [18]. Clusters may contain both experimental units and interference units, but only experimental units count toward the balancedness constraint.
Unfortunately, this naive approach fails to take into account the two-hop structure of interference in a bipartite graph. Consider for example two experimental units i and j that must be assigned to a different cluster than that of their common neighbor, interference unit 8, perhaps to satisfy balancedness cluster cardinality constraint. There is no benefit for the balanced partitioning
5

---

algorithm on the bipartite graph to assign these two experimental units to the same cluster as each other. despite them sharing a common neighbor. This mode of failure illustrated with an example in Appendix C.I.
Maximizing the variance of the doses. Cluster-randomizee designs have also been considered in the setting of two-sided bipartite experiments, in which treatment is assigned to the experimental units but outcomes are measured on the interference units. When the potential outcome of an interference unit is a linear function of the dose d,, Pouget-Abadie et al. [18] and Harshaw et al. [19] recommend assigning treatments in a way that maximizes the empirical variance of the realized doses. In the one-sided bipartite setting it is important to enforce balancedness of the clusters to control the variance of TDIM- so an extension of their objective this setting would be to maximize Tr( Var(d))
over a balanced causter-randomizee assignment.
Unfortunately, this clustering objective fails in the one-sided bipartite setting. It is possible that the doses de of the interference units are primarily controlled by a small number of experimental units with especially large weights. In this case, ensuring that the doses are close -1 only translates into guarantees about those highly-weighted experimental units, and not necessarily about the typical experimental unit. This idea is illustrated with an example in Appendix C.2.
3.2 The bias-minimizing clustering objective H(CC)
Having shown that these two natural extensions fail to identify the ttas-minimizing cluster-randomized designs, our attention elustering objective H(C) that directly minimizes the bias in fDMM-
Lemma 3.2. Suppose the difference in means estimator FDIM is computed balanced K K-cluster design (CC). Let the potential outcomes follow the linear model (1). Then the bias is given by:
2
K
E
E %
Σ SE[M]
Wis
Wis
K-
E.
Wis Σn Wks
JEC())
Suppose further that all interference terms are bounded in magnitude by a constant, so that ys O())
Then the minimax bias is bounded:
arg min max 7: 7000(1))
T EZzD(C) |rrar
arg min C
ΣΣ>
Wie
Wis
wis Σx Wks
NE[N]
(EC())
M
=: arg min HCC)..
C
To interpret Lemma 3.2, we can consider the cases in which the elustering C can achieve zero bias for FDIM. One way this can occur is when there is interference, the presence of interference, the bias of fDiM can be zero if the cut edges wis : j & C(t) are all of zero weight. In such well-clustered graph, the outcome of unit í depends only on the treatment assignments of other units within its own cluster. Since the same treatment is applied to each element of given cluster, perfectly clustered graph has e, Z, and experiences no bias due to interference.
that 7 0 for all i. Even in
Our objective H(C) has two interpretations: as clustering objective on an induced graph on experimental units, and as statistical objective on the covariance between assignments and exposures.
graphical interpretation of (C). Interference occurs when the treatment assignment of unit affects the exposure of unit i. The influence of Z, on under the linear interference model (1) is
e, (2)))) = Σ sE[ad]
Wis
Wis
(3)
Σ. Wis Σs
wkk
where Zj (resp. Z, ) is the vector with entry 2, set to I (resp. -1). Now consider a directed graph on experimental units where the edge from i j is weighted according to eZ - (Z, ); clustering according to this graph minimizes the objective (C).. This is in fact a similar approach that adopted in [9], which also looked at similar folding of the graph and showed it minimize the bias under a linear potential outcome model motivated by geographical migrations.
A statistical interpretation of H(C). A natural goal of cluster-randomizer design is to ensure that the exposure e; close to the treatment Zz. Lemma 3.3 shows that our clustering objective HCC) maximizes the covariance between the exposures and assignments.

---

Lemma 333. Let D(C) be balanced K K-cluster randomized design. Then we have: arg maxe Tr (Co
(2, e)) = arg mine H(C).
Finally, we observe that our cluster-randomized design is instance of the well-known balanced partitioning problem [34] on the graph over experimental units, with edges given by the explicit formula (3). Balanced partitioning is NP-hard, even in its relaxed form which enforces only partial balancedness, but many tools exist to compute it approximately [34, 35, 36].
Robustness
So far we have shown that cluster-randomizzd design with objective H(C)) minimizes the bias of FDrM under the normalized exposure mapping in by Equation (2) and the linear potential outcomes model in Equation (I). A natural question how robust is this design deviations from this model? In this section we analyze the robustness of the design under alternative potential outcomes models, showing that the design remains minimax optimal for Lipschitz potential outcomes and minimizes an upper bound on the bias for a class of potential outcomes models motivated by the exposure mapping literature. Additionally, there may exist experimental settings where the exposure e, is better modeled without the normalization constant E, Wis, such as when the outcome Y; is proportional to the edge weight incident to unit results remain valid for generalization of the clustering objective which removes the corresponding normalization constant(s) from HC)). This idea is formalized in Appendix A.
this case, or in the case that the dose d, is unnormalized, all of our
4.1 Lipschitz potential outcomes
Let (i(Z,)) e) E Lip (e) be a Lipschitz function in the exposure e, with Lipschitz constant L. Then we can bound the bias in FDIM by multiple of H(C)., and this bound tight in a minimax sense.
Lemma 4.1. Let observations Y, be observed from K-cluster design, with potential outcomes given by Y.(Z.e) e) E (ip Then the bias of the difference- in in-eaas estimator FDIM is bounded above by
2 K
[ - -T' NK- 1 H(C).
L.
Furthermore, this bound is tight over the class of Lipshitz functions, so that balanced clustering according to the objective H(C) is tight in minimax sense among all balanced clusterings:
arg min max [[fDrM] - 7- arg min H(C).
C (elip.(e)
We note that the objective H(CC) is minimax optimal over the class of L-Lipschitz functions regardless of the Lipschitz constant As a result, the practitioner need know this constant in order find the minimax optimal clustering.
4.2 Functions constant in neighborhoods of (-1,1}
A common assumption in the exposure mapping literature is that units with exposure e; close enough to their treatment assignment Z, behave as their entire neighborhood were assigned to Z,- This assumption motivates the use of IPS estimators, which are unbiased that setting. If we let A denote the neighborhood of Z: in which an exposure is considered fully treated or controlled, then we have the following constraint the potential outcome function.
=0 0
if Z cl< otherwise
12e(-1,11 Ve [-1,1
B
Under this assumption the behavior of Y,, we upper bound the bias of the difference-in-means estimator by a quantity that will turn out to be minimized by minimizing H(C).
Lemma 4.2. Let observations Y, be observed from K K-cluster design, with potential outcomes satisfying Equation (4). Then the bias of the difference-ine sifferencc-in-mmann estimate FDIM is bounded above by
2B K
E E -
NA K - H(C).

---

Table Relative bias of FDIM MoIM& as the bipartite stochastic block model changes (see 5.1)
p=0.0 0.0
p = 0.005
p = 0.05
p = 0.5
H(C)
0.02(=0.06)
3.90(+0.06)
11.54(=0.05)
12.98(==0.08)
Tr(Var(d)) objective
0.01(=0.06)
3.84(10.05)
11.49(=0.06)
12.91(#0.07)
Direct clustering
0.01(=0.055)
9.10(#+013)
12.95(#0.07) 12.68(=0007))
EXPOSURE-DESIGG
0.33(=00.06)
4.06(++0.06)
11.90(+0.07)
13.00(+0008))
Unit-level randomization
12.44(=0.08)
12.55(+0.08)
12.76(+0.08)
12.95(+0.08)
True clusters
0.01(=0.06)
3.88(+0.06)
11.58(=0.06)
12.96(+0.06)
Lemma 4.2 presents only an upper bound on the bias, and in general this bound is not tight. However, we provide simulations Section 5.2 showing that the objective HCC) is reasonable heuristic for functions that satisfy Equation (4).
5
Experiments
We explore the performance our cluster-based randomized design in several settings using simulated graphs. We compare the baseline of unit- randomization well as cluster-leve level randomization according to several clustering schemes: the true clustering, direct clustering on the original bipartite graph (Section 3.1), maximizing the Tr( (ar(dd) objective (Section 3.1), and maximizing the expected empirical variance of the doses as motivated by [18, 19). We use code provided by the authors of [35] to identify minimum-cost balanced partitioning of the graphs induced by the objectives H(C), Tr(Var(d)), and the direct clustering. For the last objective, which is not balanced partitioning, we use code provided by the authors of [19] to minimize the EXPOSURE-DESIGH objective, reporting results with the hyperparameter ø tuned to minimize mean squared error. See Appendix H for an overview of the algorithms.
5.1 Robustness clusterability in the stochastic block model
We begin by studying the performance of our design as the amount of interference varies. We construct synthetic graph according the bipartite stochastic block model with N 1, 000 experimental units and M = 2, 000 interference units. Both sides of the graph are partitioned into 20 equally sized groups with label i E [20]. Experimental and interference units with the same label have an edge of weight 1 with probability 0.5, while units with different labels have edge of weight 1 with probability p. We experiment with values from p = (no interference between clusters) to = 0.5 (the absence of an underlying clustering structure). Potential outcomes were drawn according to the linear model (1), with coefficients drawn Os ~ (0, 1), B, ~ (1,, and 7/ ~ (-11,, All clustering designs used K = 20 clusters, with K = 10 clusters assigned to treatment. Table 1 shows the relative bias (defined as [ T//T) of TDIM under each cluster-randomizzd design; variance is inconsequential in this setting, the variance and MSE are reported in the supplementary materials. Uncertainty represents the 95% confidence interval as determined by bootstrapping over 100 random draws of treatment assignment Z, over single draw of the graph and potential outcomes.
As anticipated, all designs incur lower bias when there less interference in the graph (i.e., when p is smaller). Our clustering objective M(CC) and the Tr( (Vr((d)) objective perform on par with the true clustering for all values of p. The low bias of the H(C) objective unsurprising given the minimax optimality result in Lemma 3.2. The equivalent performance of the Tr( Var(d)) objective is due to the symmetry inherent in the bipartite stochastic block model, in which each interference unit has the same incoming edge weight Σ, Wis in expectation, and the same is true of the experimental units' edge weights E. Wis. In such a symmetric setting the objectives HC) and Tr (r(Var(d)) are equivalent, can be seen by comparing their representations in Lemma 3.2 and Equation (5).
5.2 Robustness to nonlinearity
Next we explore the robustness of our design to nonlinearity the potential outcomes model Y, by simulating outcomes according to Equation (4), in which the potential outcome is constant for e; in

---

Table Relative bias of FDIM as the neighborhood pure exposure, A, widens (see 5.2)
A = 0.1
A = 0.3
A = 0.5
H((C)
1.000(=0.004)
0.457(=0.005
0.001(=0.000)
Tr(Var(d) objective
1.002(=0.004)
0.460(=0.004)
0.000(=0.000)
Direct clustering
0.950(=0.008) 0.907(=0.005)
0.600(=0.020)
EXPOSURE-DESIGN
1.001(+00.04)) 0.509(=0.005)
0.009(=00001)
Unit-level randomization
0.998(=00004)
1.000(=0.004)
0.998(=0.003)
True clusters
1.001(=0.004)
0.458(=0.004) 0.001(=0.000)
A neighborhood of Z, We simulate Y; Z, if e; Z,l A and Y, ud-1,1111 1)) otherwise. encoding setting in which no knowledge can be gained about when e is A-far from Z. The graph given by the bipartite stochastic block model described in Section 5.1 with 20 groups. with p 0.5 chance of an edge between units belonging to the same group and 0.005 for units belonging to different groups. All clustering designs used K 20 clusters, with Kr treatment. Table 2 shows the results of these experiments. Uncertainty represents the 95% confidence interval as determined by bootstrapping over 100 random draws of treatment assignment Z, over a single draw of the graph and potential outcomes.
clusters assigned to
We that all designs have lower bias when A is large, reflecting the fact that observations with exposure E A-far from Z, are useless in determining т, and it is easier to get Appure observations for large A. The results in Table 2 support our claim that (C) is a reasonable design heuristic for this setting (motivated by the bias upper bound in Lemma 4.2). We observe again that the Tr( Var(d)) objective does as well as the H(C)) objective; as described in Section 5.1, this is due to the fact that these objectives are nearly equivalent under the symmetry of our simulated graphs.
5.3 Performance on power-law graphs
To contrast with the bipartite stochastic block models studied above, experiment bipartite graph model with a power-law distribution of the vertices. Our graph model combines the bipartite preferential attachment model of [37] with the affinity model of [38]. In this model, each experimental unit is assigned to one of K latent classes. For each experimental unit i, a degree de is drawn from the power-law distribution d, 2X X Zi)f(3). For each edge j E [d.]. it is either attached X, or to newly drawn interference unit with
to an existing interference unit with probability probability A. If attached an existing unit, unit is chosen with probability proportional (d, + p) if s is of the same latent class as i, or d, + if is of a different class. If new unit is drawn, then is of the same class as unit with probability p(p + (K 1)g)-1 and of each other class with probability o(p (K - 1)q)=1 We chose N = 100, K = 10, A = 0.5, = 0.02p. We experimented with both p- 0.1 (weak latent structure) and p 100 (strong latent structure).
Table 3 shows the relative bias four estimators when the potential outcomes are drawn from the linear model given in Section 1. Interestingly, in this setting we see that the dluster-randomized designs outperform the true latent clusters; this is possible because the interference occurs with respect a single draw of the random graph, which the clustering algorithm gets to see. We speculate that factors specific to the power-law graphs, notably the existence of vertices with very high degree, might cause the optimal clustering for a given draw of the graph be very different from the optimal clustering for the graph on average. This could have negative consequences for experimental design when only a random draw of the edges observed, but the interference occurs according to the underlying latent structure.
5.4 Robustness to exposure mapping: an Airbnb case study
So far we have only considered potential outcomes models where the outcome Y, is function of the assignment Z; and the exposure e; as defined in Equation (2). However, in many reae-life settings, an exposure model is only approximation to the true mechanism of interference.
We test the robustness of our experimental design to misspecification of the exposure mapping by simulating outcomes according to model developed for vacation rentals by Li et al. [10], in which

---

Table 3: Relative bias of FDIM under an affinity model with power-law distribution (see 5.3)
Strong latent structure
Weak latent structure
H(C)
1.9(10.11
3.5(=0.1)
Tr(Var(d) objective
2.0(=:011)
3.7(=0.1)
Direct clustering
1.8(=0.2)
3.3(=0.2)
Unit-level randomization
4.9(+..1)
5.4(+0.1)
True clusters
2.9(+0.1)
5.2(40.1)
0.5
0.25
0.35
0.30
RWSBIT
0.15
0.3
0.10
0.20
0:15
0.10
0.00
0.1
1.1
1.2
1.3
1.4
1.5
Md
T(Vorid)) objective
Tue clusters
Unit level randomiaiooonoooonn
EXPOSURE-DESION
Figure Performance of various clustering algorithms as the treatment effect increases. Uncertainty represents 95% empirical confidence intervals over 500 draws of the treatment assignment Z. Direct balanced partitioning had error 4-8 times the second-word algorithm, and is not shown.
there is explicit exposure mapping defined. We call the experimental units customers and the interference units listings. In the first phase of the model, each customer applies to each listing with probability dis. In the second phase, listings with applications randomly select application to accept. The measured outcome Y, if customer successfully booked a listing, and 0 otherwise. In alignment with previous work in this literature [10, 28] create natural clustering structure on the network by assigning each customer and each listing to one of 20 types. Our simulation takes N 500 customers and M 1000 listings, with application probability under the control assignment of di = 0.016 if and are of the same type, and dis 0.0001 otherwise. Treating customer increases these application probabilities by factor of
When rumning this marketplace experiment, an experimenter would typically have access to historical data about the rate of successful applications of customer i listing s, but would not know the consideration probabilities Φis- To be faithful to this observation model, we constructed the bipartite graph using twelve rounds of interaction in this marketplace under the control condition. This graph was sampled once and fixed for all experiments. All clustering designs used K = 20 clusters, with treatment. Simulations were performed by extending code provided by the authors of Li et al. [10] to the cluster-randomized setting. The relative bias, standard deviation, and root mean squared error (RMSE) of FDIM of various clustering algorithms
KT 10 assigned
shown in Figure 2.
We observe that all clustering algorithms had similar variance but that the bias HCC) and Tr( (ar(d)) closest to that of the true clustering, giving those two methods the lowest RMSE. Notably, the unit-randomized design suggested by [10] in this setting (N < M), but our cluster-randomized design outperforms it. We conclude that our clustering method still outperforms other baselines, setting where the potential outcome does not obey the exposure mapping model we hypothesized.
Acknowledgments
The authors would like thank Christopher Harshaw, Khashayar Khosravi, Kay Brodersen, Vahan Nanumyan, and Kevin Jamieson for helpful discussions; Hannah Li and Geng Zhao for sharing their code for the Airbub simulator; David Eisenstat for assistance with the clustering code; and Robbie Weber for feedback on the paper organization.
10

---

References
[1] Donald Rubin. Discussion of "randomization analysis of experimental data in the fisher randomization test" by d. basu. Journal of the American statistical association, 75:591-593, 1980.
[2] Jerzy Neyman. On the application of probability theory to agricultural experiments. essay on principles. section 9 (translated). reprinted ed. Statistical Science, 5:465-4722 1923.
[3] Michael G Hudgens and M Elizabeth Halloran. Toward causal inference with interference. Journal of the American Statistical Association, 103(482) 842, 2008.
[4] Peter M Aronow, Dean Eckles, Cyrus Samii, and Stephanic Zonszein. Spillover effects in experimental data. Advances in Experimental Political Science, 289:319, 2021.
[5] Sinan Aral and Dylan Walker. Creating social contagion through viral product design: A randomized trial of peer influence in networks. Management science, 57(9):1623-1633) 2011.
[6] Huan Gui, Ya Xu, Anmol Bhasin, and Jiawei Han. Network a/b testing: From sampling to estimation. In Proceedings the 24th International Conference World Wide Web, pages 399-409, 2015.
[7] Dean Eckles, René F Kizilcec, and Eytan Bakshy. Estimating peer effects in networks with peer encouragement designs. Proceedings of the National Academy of Sciences, 13(227::33167322) 2016.
[8] Thomas Blake and Dominic Coey. Why marketplace experimentation is harder than it seems: The role of test-control interference. In Proceedings of the fifteenth ACM conference Economics and computation, pages 567-582, 2014.
[9] David Rolnick, Kevin Aydin, Jean Pouget-Abadie, Shahab Kamali, Vahab Mirrokni, and Amir Najmi. Randomized experimental design via geographic clustering. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2745-2753, 2019.
[10] Hannah Li, Geng Zhao, Ramesh Johari, and Gabriel Y Weintraub. Interference, bias, and variance in two-sided marketplace experimentation: Guidance for platforms. In Proceedings of the ACM Web Conference 2022, pages 182-192, 2022.
[11] Stefan Wager and Kuang Xu. Experimenting in equilibrium. Management Science, 67(11): 6694-67 019946715,, 6715,6177766 2021.
[12] Evan Munro, Stefan Wager, and Kuang Xu. Treatment effects in market equilibrium. arXiv preprint arXiv:2109.11647 2021.
[13] Chamandy, lyft. Experimentation in a ridesharing marketplace lyft engineering. URL: https://eeg. 2016.
[14] Guillaume W Basse and Edoardo M Airoldi. Limitations of design-based causal inference and a/b testing under arbitrary and network interference. Sociological Methodology, 48(1):16-1151 2018.
[15] Charles F Manski. Identification of treatment response with social interactions. The Economet- rics Journal, 16(1):51-S23, 2013.
[16] Peter M Aronow and Cyrus Samii. Estimating average causal effects under general interference, with application to social network experiment. The Annals of Applied Statistics, 11(4): 1912-1947, 2017.
[17] Dean Eckles, Brian Karrer, and Johan Ugander. Design and analysis of experiments networks: Reducing bias from interference. Journal of Causal Inference, 5(1), 2017.
[18] Jean Pouget-Abadie, Kevin Aydin, Warren Schudy, Kay Brodersen, and Vahab Mirrokni. Variance reduction bipartite experiments through correlation clustering. Advances Neural Information Processing Systems, 32: 133999 2019.

---

[19] Christopher Harshaw, Fredrik Sävje, David Eisenstat, Vahab Mirrokni, and Jean Pouget-Abadie Abadie. Design and analysis of bipartite experiments under linear exposure- response model. EC', 2022.
[20] Martin Saveski, Jean Pouget-Abadie, Guillaume Saint-Jacques, Weitao Duan, Souvik Ghosh, Ya Xu, and Edoardo M Airoldi. Detecting network effects: Randomizing over randomized experiments. In Proceedings of the 23rd ACM SIGKDD international conference knowledge discovery and data mining, pages 1027-1035, 2017.
[21] Peter M Aronow. A general method for detecting interference between units in randomized experiments. Sociological Methods & Research, 41(1):3-11 2012.
[22] Susan Athey, Dean Eckles, and Guido W Imbens. Exact p-values for network interference. Journal of the American Statistical Association, 113(521) ::230124:::2000 2018
[23] Panos Toulis and Edward Kao. Estimation of causal peer influence effects. In International conference on machine learning, pages 1489-1497. PMLR, 2013.
[24] Fredrik Sävje, Peter M Aronow, and Michael G Hudgens. Average treatment effects in the presence of unknown interference. The Annals of Statistics, 49(2):673 701, 2021.
[25] Alex Chin. Regression adjustments for estimating the global treatment effect in experiments with interference. Journal of Causal Inference, 7(2), 2019.
[26] Johan Ugander, Brian Karrer, Lars Backstrom, and Jon Kleinberg. Graph cluster randomization: Network exposure to multiple universes. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 329-337, 2013.
[27] Ozan Candogan, Chen Chen, and Rad Niazadeh. Near-optimal experimentl design for networks: Independent block randomization. Available at SSRN, 2021.
[28] Ramesh Johari, Hannah Li, Inessa Liskovich, and Gabriel Y Weintraub. Experimental design in two-sided platforms: An analysis of bias. Management Science, 2022.
[29] Patrick Bajari, Brian Burdick, Guido W Imbens, Lorenzo Masoero, James McQueen, Thomas Richardson, and Ido M Rosen. Multiple randomization designs. arXiv preprini 11Xiv22112.13495, 2021.
[30] Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015.
[31] Corwin M Zigler and Georgia Papadogeorgou. Bipartite causal inference with interference. Statistical science: a review journal of the Institute of Mathematical Statistics, 36(1):109) 2021.
[32] Donald B Rubin. Comment: Neyman (1923) and causal inference in experiments and observa- tional studies. Statistical Science, 5(4))472-48)) 1990.
[33] Peng Ding, Xinran Li, and Luke W Miratrix. Bridging finite and super population causal inference. Journal of Causal Inference, 5(2), 2017.
[34] Konstantin Andreev and Harald Racke. Balanced graph partitioning. Theory of Computing 396)) 939, 2006.
[35] Kevin Aydin, MohanmadHossein Bateni, and Vahab Mirrokni. Distributed balanced partitioning via linear embedding. Algorithms,, 12(8):162, 2019.
[36] Joel Nishimura and Johan Ugander. Restreaming graph partitioning: simple versatile algorithms for advanced balancing. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1106-1114, 2013.
[37] Jean-Loup Guillaume and Matthieu Latapy. Bipartite graphs as models of complex networks. Physica A: Statistical Mechanics and its Applications, 371(2):795-81) 813, 2006.
[38] Jay Lee, Manzil Zaheer, Stephan Günnemann, and Alex Smola. Preferential attachment in graphs with affinities. In Artificial Intelligence and Statistics, pages 571 571-580. PMLR, 2015.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] These are discussed in Appendix
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs are provided in Append F
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [No] The balanced partitioning code was shared with us by the authors of Aydin et al. [35], and code to optimize the EXPOSURE- DESIGN objective was shared by the authors of Harshaw al. [19], but neither is publicly available.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cited the creators of code we used: [35, 19, 10]
(b) Did you mention the license of the assets? [N/A] No new assets are being released
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
No new assets being released
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] All data was simulated.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] All data was simulated.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "YJqrSamKLIL", "reviewer": "Reviewer_nu8Q", "summary": "The authors examine a setting of experimentation they refer to as \"one-side bipartite experimentation\", in which treatment and outcomes are measured on one set of units, but connections between units (and, therefore, interference) operates through a distinct set of units. The authors provide theoretical results and simulations which demonstrate that clustering on a special objective function can effectively allow for inference in this setting with minimal bias.\n", "questions": "The authors claim \"variance is inconsequential in this setting\". Surely there are scope conditions or assumptions necessary for this statement to hold. I think the authors may be assuming that methods compared are methods of clustered-RA (or unit-level RA where bias is extremely large)? If all clustering methods use the same number of clusters, this would be true, but I don't see why that would necessarily be the case if one were choosing the number of clusters as a practitioner would be (e.g. through finding an elbow, etc). The appropriate number of clusters could look quite different depending on the clustering objective. In any event, I'd appreciate the authors to clarify this (also in the text).", "limitations": "Methods like this which allow for better and more accurate experimentation are a key way to detect and analyze biases in complex real-world systems.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n- The theoretical analyses are not particularly novel.\n- The setting, while interesting, is pretty straightforward: the one-sided bipartite graph just implies a straightforward way to construct an exposure graph. The methods thereafter are fairly straightforward.\n\nQuality:\n+ The authors do a good job of drawing out the implications of their main clustering result\n+ The focus on design rather than analysis is very welcome.\n\nClarity:\n+ Found the paper quite easy to follow.\n\nSignificance:\n+ The problem setting is interesting and relevant to many practitioners.\n\nSection 2.1 defines a model which is, essentially, the \"Linear-in-Means\" model of [1]. This important related work should be discussed. In particular, [1] draws out an agnostic basis for this model. Section 2.2 also has a discussion of exposure maps which greatly parallels section 3.1 of [1]. This is not an accusation of plagiarism, to be clear, but the paper would be improved by drawing more heavily on this.\n\nGreater discussion of the estimand under less favorable data generating processes (in the vein of [2]), could be an interesting direction to make the work more useful in practice. The simple SBM of section 5.2, for example, obviously aligns nicely with a clustering-based design.\n\n[1] A. Chin, Regression adjustments for estimating the global treatment effect in experiments with interference, Journal of Causal Inference, May 2019. https://arxiv.org/abs/1808.08683\n[2] Fredrik Sävje. Peter M. Aronow. Michael G. Hudgens. \"Average treatment effects in the presence of unknown interference.\" Ann. Statist. 49 (2) 673 - 701, April 2021. https://doi.org/10.1214/20-AOS1973", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RmV-sbJ-x-P", "reviewer": "Reviewer_pzrY", "summary": "The paper studies cluster randomized designs for one-sided bipartite experiments. The authors assume a linear potential outcome model, and a normalized exposure mapping model, and focus on difference-in-means estimators to estimate the average total treatment effect. They propose to find the design that minimizes the bias among balanced K-cluster randomized designs. The authors then demonstrate the robustness of the design to deviations from the assumed potential outcome model/the exposure mapping model. Finally, simulations studies are conducted to show the empirical performance of the design. ", "questions": "-\tI’m curious to see how the proposed design compares to the two-sided designs proposed in [27, 28] (I used the same references as in the paper) Do you believe the proposed design can outperform the two-sided ones? I understand that in practice, it would require different platforms to run one-sided experiments/two-sided ones, so it is not 100% comparable, but I’d love to see some more comparisons and discussions. Thank you!\n\n-\tLine 179-184. The authors argue that balancedness helps reduce variance. By how much does balancedness help reduce variance? It will be helpful to see some theoretical/empirical results on this. Or even some more detailed references will be very helpful. \n\n-\tLine 238-241. Is the proposed method implemented with the algorithm in [34]? I don’t think this is made 100% clear except a brief mention in line 284, which seems to be referring to how the benchmark methods are implemented. It will be helpful to clarify what specific algorithms are used. Are exact balancedness achieved? If only partial balancedness is achieved, how close is this to exact balancedness? \n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work. \n\n", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n-\tThe paper is very well-written. The proposed designed is motivated and explained in a very nice way. \n\n-\tThe paper addresses an interesting and important question: estimating the total treatment effect in the setting of one-sided bipartite experiments. \n\n-\tThe proposed design appears to have good performance both theoretically and empirically. \n\n-\tThe paper does a great job discussing robustness to model misspecifications both theoretically and empirically.\n\nWeaknesses\n\n-\tI would love to see more detailed discussions on 1. Comparison with two-sided designs. 2. By how much balancedness helps reduce variance. 3. Implementation details (See questions section for more details)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BwJHhGdpo9C", "reviewer": "Reviewer_Vi8h", "summary": "\nIn this work, the authors study a new experimental design problem under interference. The underlying graph capturing the interference is a bipartite graph with two types of units (corresponding to the two partitions): experimental and interference units. The goal is to assign the experimental units to treatment or control to estimate the total treatment effect on the experiment units. The only purpose of the interference units is to facilitate interactions between experimental units. The authors motivate this setting with marketplace experiments, where buyers interact with sellers.\n\nFor this problem, they study the performance of difference-in-means estimators for cluster-randomized balanced designs, under a suitable linear exposure model. The main claim is a min-max optimal equivalence between treatment effect estimation and identifying a good clustering. In other words, they showed that the clustering that minimizes the maximum bias will result in identifying a partitioning of a weighted graph, with weights representing the strength of interference between the units. They demonstrate the performance of their approaches empirically, along with a robustness study, when the underlying data deviates from the studied exposure model.\n\n\n", "questions": "Can the exposure model be tied into some of the earlier literature works? Isn't there double counting with respect to edge weights? (It suggests that the model was chosen after discovering the correct clustering objective)\n\nIn Lemma 3.2, are the terms corresponding to gamma0 and gamma1 missing? Although the proof in the appendix states it clearly, I would suggest fixing it to avoid any confusion.\n\nIt would be interesting to see the differences in the relative bias (Table 1) with respect to Tr(Var(d)) and H(C) for other synthetic graphs, such as power-law, which exhibit skewed distributions (unlike the stochastic block model used for simulations).\n\n", "limitations": "As this is a theoretical paper, with simulated experiments, they did not discuss the potential negative societal impact of their work. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The presentation in the paper is excellent, containing extensive discussions on their choice of experimental designs and estimators. \n\nThey relate two important quantities of interest to a graph partitioning objective: bias of the estimator and robustness of the design. The robustness is captured using covariance of the exposure vector (under the interference model) and the design vector. From the proofs in the appendix, it is evident that the bias is a constant factor away from the graph partitioning objective, which is computationally challenging to solve exactly, and for which many approximation algorithms are already known in the literature. These new relationships/equivalences are novel and could be helpful in furthering our understanding of experimental designs under interference.\n\nIt certainly would be an important addition to strengthen the current work by considering confidence interval bounds for the bias of the considered estimator. \n\nThe authors restrict themselves to balanced designs -- it is not immediately clear if this is necessary. They claim that it reduces the variance in the estimator. It would be helpful to understand the exact dependence of parameters here. Moreover, the theoretical claims in the paper do not compare directly with respect to a simple baseline, such as unit-level randomization. As stated, they show the equivalence in terms of the exact clustering, but not the objective values themselves.\n\nAlthough min-max optimal results are useful, it would be interesting to look at specific cases, for which one can do better than off-the-self graph partitioning (clustering) algorithms from prior literature.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2K3lZFbswDy", "reviewer": "Reviewer_qE7Y", "summary": "The paper studies cluster randomized signs for one-sided bipartite experiments under network interferences. The paper discussed many different models, but I will only define the main one studied. There is a weighted bipartite graph between a set of experiments and a set of interference units, with the weight w_{is} between the experiment i and interference unit s indicating relationship between i and s.  For each experiment i, we can assign either \"control\" (Z_i = -1) or \"treat\" (Z_i = 1) to i.  The outcome for the i-th experiment is a real number Y_i(Z) = alpha_i + beta_i Z_i  + gamma_i e_i(Y). The alpha_i + beta_i Z_i is a linear function of the treatment Z_i for i, and e_i is called the exposure, which captures the interferences of the (Z_j)_{j\\neq i} values to the outcome for i. e_i(Y) is called the exposure mapping.\n\nThe paper propose a bipartite analogue of the neighborhood-based exposure mapping. In this model, the dose of an interference unit s is computed as the weighted average of the treatment assignment Z_i among the neighboring experiments i of s, where weights are w_{is} values. Then, the exposure e_i is the weighted average of the doses of neighboring interference units s of i, again using w_{is} values.\n\nThe average total treatment effect tau is defined as 1/N * sum_{i \\in [N]} (Y_i(vector Z = all 1 vector) - Y_i(vector Z = all -1 vector)). In the difference-in-means (DIM) estimator for tau, we choose randomly N_T experiments to treat, and N_C experiments to control, where N_T and N_C are numbers chosen upfront. The estimation given by the DIM estimator is \\hat \\tau_DIM := \\sum_{i:Z_i = 1} Y_i/ N_T - \\sum_{i:Z_i = - 1} Y_i/N_C.  The bias of the estimation is defined as \\tau - \\hat \\tau_DIM.\n\nThe main goal of the paper is to use balanced clustering to reduce the mean squared error (MSE) of the DIM estimator. Let C be a partition of the N experiments into K equally sized clusters.  A balanced k-cluster randomized design D(C) is a distribution over vectors Z \\in {-1, 1}^N, such that experiments in the same cluster have the same +-1 values, and there are K_T clusters with +1 values. The authors gave the formula for the bias under the cluster design, presented some robustness results, and conducted experiments on the effectiveness of the method. ", "questions": "It would be good to compare the clustering-based algorithm and the original one (without the clustering used) theoretically.  This could be done using an example, or a theorem that covers typical cases that arise in practice. ", "limitations": "Not applicable. ", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Evaluations:  The main contribution of the paper is use of the one-sided cluster design algorithm to reduce the bias of DIM estimator.  However, after giving the formula and the optimization problem in Lemma 3.2, I fail to see why this algorithm is better than the standard one without the clustering. A lemma about some typical cases or even an example suggesting this would be helpful.  Moreover, the clustering idea was not new. It is used in cases where all units are experimental units, and where there are experimental and interference units, but the outcomes are measured in the interference units.  It is not so hard to extend the idea to the setting studied in this paper. \n\nI am also annoyed by the bad format of the supplementary material. There are so many places where the mathematical formulas exceed the width of a line by a lot. The authors may have submitted the paper (at least the supplementary material) in a hurry. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept