Independent-Set Design of Experiments for Estimating Treatment and Spillover Effects under Network Interference
Authors: Chencheng Cai
Xu Zhang
Edoardo Airoldi
Venue: ICLR 2024 poster (2024)
Keywords: Causal inference
Design of experiments
Interference
Random graph
Spillover effects
Treatment effects
Potential outcomes
Primary area: causal reasoning
TL;DR: We propose a novel design of experiments for estimating treatment and spillover effects under network interference.

Abstract: Interference is ubiquitous when conducting causal experiments over networks. Except for certain network structures, causal inference on the network in the presence of interference is difficult due to the entanglement between the treatment assignments and the interference levels. In this article, we conduct causal inference under interference on an observed, sparse, but connected network, and we propose a novel design of experiments based on an independent set. Compared to conventional designs, the independent-set design focuses on an independent subset of data and controls their interference exposures through the assignments to the rest (auxiliary set). We provide a lower bound on the size of the independent set from a greedy algorithm and justify the theoretical performance of estimators under the proposed design. Our approach is capable of estimating both spillover effects and treatment effects. We justify its superiority over conventional methods and illustrate the empirical performance through simulations.

Published as a conference paper at ICLR 2024
INDEPENDENT-SET DESIGN OF EXPERIMENTS FOR ESTIMATING TREATMENT AND SPILLOVER EFFECTS UNDER NETWORK INTERFERENCE
Chencheng Cai Xu Zhang?* Edoardo M. Airoldi
DDpartment of Mathematics and Statistics, Washington State University Amazon
3 Department of Statistics, Operations, and Data Science, Temple University
chencheng. cai@wsu.ede xuzhangn@amazon com airoldi@temple. edu
ABSTRACT
Interference is ubiquitous when conducting causal experiments over networks. Except for certain network structures, causal inference on the network in the pres- ence of interference is difficult due to the entanglement between the treatment assignments and the interference levels. In this article, we conduct causal infer- ence under interference propose a novel design of experiments based on an independent set. Compared to conventional designs, the independent-sel design focuses on an independent sub- set of data and controls their interference exposures through the assignments to the rest (auxiliary set). We provide a lower bound on the size of the independent set from a greedy algorithm and justify the theoretical performance of estimators under the proposed design. Our approach is capable estimating both spillover effects and treatment effects. We justify its superiority over conventional methods and illustrate the empirical performance through simulations.
observed, sparse, but connected network, and we
INTRODUCTION
Randomized experiments widely regarded the gold standard for estimating causal effects. However, the spillover effect is ubiquitous in experiments when one unit's treatment affects others' outcomes, where the stable unit treatment value assumption (SUTVA) (Imbens & Rubin, 2015) is violated. Examples include the traditional agricultural field experiments (Zaller & Köpke, 2004), ed- ucational studies (Rosenbaum, 2007), econometric assumptions (Banerjee et al., 2013: Johari al., 2020), and social networks (Phan & Airoldi, 2015). The spillover effect is also called "interference", and the two names are used interchangeably in the literature.
Estimating causal effects in the presence of interference is usually difficult, except for certain spe- cial cases. For instance, when the population of units can be well-partitioned into several isolated clusters, randomized saturation design (Hudgens & Halloran, 2008) and its variations (for exam- ple, Eckles et al. (2017), Owen Varian (2020) has shown success in estimating causal effects involving interference by controlling the interference level at each cluster with pre-determined saturation. The difficulties in estimating spillover effects on a well-connected network are two-fold. The first is the entanglement between the treatment assignments and the spillover effects received by the units. Because the spillover effects received by the units are determined by the interference relationships and the assignment of all units, one cannot achieve separate controls on the treatment and the spillover of all units. The second difficulty comes from the collapse of the spillover effect. completely randomized experiment on all units anchors the spillover effect received by each unit at its expectation for large networks because of the law of large numbers. In estimating spillover effects or total treatment effects, where we prefer diversified interference levels for the units, the collapse gives rise to increase in variance and reduction in power.
Although the individual treatment assignments and the interference received cannot be controlled independently for the whole dataset, an approximately separate control is feasible for a subset of
"quaa contribution. Corresponding author.

---

Published as a conference paper at ICLR 2024
the dataset. We propose novel design of experiments on the network, where focus a high- quality subset of units. The subset contains non interrfeen units and is called the "independent set", where we borrow the name from graph theory emphasize that there is no edge in the independent set. The rest of the units form the "auxiliary set", which provides interference to the units in the independent set. The partitioning of the independent and auxiliary sets re-gains separate controls over the treatment and the interference on the independent set. The approach can be viewed as a trade-off between the quantity and the quality of data. The independent set has a smaller sample size compared to the full dataset. However, due to the possibility of separate controls of their treatments and interference, observed outcomes from the independent set units provide more information for the causal effect and, therefore, are more efficient for causal inference purposes.
This paper is organized as follows: Section discusses related studies and summarizes our contri- bution. We formally define the causal effect under interference and introduce the independent set design in Section 3. Section provides the theoretical foundation and quantifies the performance. In Section 5, we evaluate the performance of our approach simulated data. In Section 6, we discuss and highlight potential future work. Theorem proofs are provided in the Appendix.
RELATED WORK AND OUR CONTRIBUTION
In classical methods for randomized experiments, a key assumption is that there is no interference among the units, and the outcome of each unit does not depend on the treatments assigned to the other units (SUTVA). However, this no-interference assumption is not plausible on networks. Many approaches are proposed address the interference problem. First, researchers improve experi- mental designs to reduce interference, such as the custerr-bssed randomized design (Bland, 2004), group-level experimental designs (Sinclair et al., 2012; Basse et al., 2019), randomized saturation design (Hudgens & Halloran, 2008), and graph cluster randomization (Ugander et al., 2013; Fek- les et al., 2017; Ugander & Yin, 2023). These approaches aim to reduce interference by clustering and assume that interference only exists within units in the cluster and that there is interference between clusters (known as partial interference (Sobel, 2006)). However, when the isolated cluster assumption is violated, the randomized saturation design fails to estimate effects accurately (Cai et al., 2022). To extend the cluster-based randomized design, ego-clusters design (Saint-Jacques al., 2019) is proposed to estimate spillover effects, which requires non-overlapping ego-clusters. Karwa & Airoldi (2018) introduced a simple independent set design, which only focuses on esti- mating treatment effect and has no control of bias/variance of the estimator. Unlike graph cluster randomization and ego-cluster randomization, which require non-overlapping clusters, our design allows units to share neighbors. Furthermore, recent studies incorporate network structure in the experiment based primarily on the measurement of local neighbors of units (Awan et al., 2020), and they estimate causal effects by matching the units with similar network structures. Some studies use special network structures in designs to relax SUTVA assumption and estimate causal effects (Aronow & Samii, 2017: Toulis & Kao, 2013; Yuan et al., 2021). In another direction, some stud- ies leverage inference strategies, and they conduct a variety of hypotheses under network inference (Athey et al., 2018; Rosenbaum, 2007; Pouget-Abadie et al., 2019b; Sussman & Airoldi, 2017). When there exists two-sided network two-sided market for units, for example, consumers and suppliers, researchers proposed bipartite experiments (Pouget-Abadie et al., 2019a; Holtz et al., 2020; Doudchenko et al., 2020; Zigler & Papadogeorgou, 2021) to mitigate spillover effects. In bipartite experiments, two distinct groups of units are connected together and form a bipartite graph. In contrast, our approach generates two sets from units that belong one group in a network. In ad- dition, an increasing number of studies focus on observational studies on networks (Liu et al., 2016; Ogburn& VanderWeele, 2017: Forastiere et al., 2021). However, these methods require structural models and need to identify confounders.
Our method makes several key contributions: First, we propose a novel design that partitions data into two disjoint sets to gain separate controls on the treatment and the interference. Second, in contrast to most previous studies, which only focus on estimating the treatment effect or spillover effect, our design works as general framework for network experiments involving interference and is capable of various causal tasks (estimating both treatment and spillover effects). Third, the treatment assignments
the two sets can be optimized directly to control the bias/variance of the estimator. The connection between the objective function and the bias/variance is discussed in Section 4. Fourth, we provide theoretical guarantees, including almost-sure lower bound on
2

---

Published as a conference paper at ICLR 2024
Table 1: Comparison of designs for estimating spillover effects
Design
Network Assumption
Sample Size"
Interference Control
Independent Set
random, sparse random, sparse isolated clusters no
(n log s)/s n/ + 1) n n
high full partial no
Ego-clusters
Randomized Saturation
Completely Randomized
number units used for inference, n: network size, 8: average degree
the sample size and the analytic bias/variance for the estimators. Finally, unlike previous studies, which require SUTVA assumptions and interference between units or are restricted to special network structures to mitigate the spillover effects, our approach does not require SUTVA and could be implemented in arbitrary networks.
In Table 1, we compare our method to few competitive designs in terms of assumptions on net- works, effective sample size, and the ability to control interference.
INDEPENDENT-SET DESIGN
3.1 POTENTIAL OUTCOMES AND CAUSAL EFFECTS UNDER INTERFERENCE
Consider a set of n experimental units labeled with i = I,... n. Each of them is assigned with treatment Z (0, 1). for which denote Z, 1 for treated, Z, for control, and Z (Zi...., Zn for the full treatment vector. Under Rubin's 's framework of potential outcomes (Imbens & Rubin, 2015), we assume (2) is the potential outcome of unit that would be observed if the units were assigned with the treatment vector Z. We say "unit i is interfered by unit j" when Y; depends on Zy. for * j. All the pairwise interference relationships can be represented by graph = (V, E). where V {l...., } is the vertex set, and (i,j) E E if units and j interfere with each other. Here, we assume all pairwise interference is symmetric such that G can be reduced to an undirected graph with each undirected edge representing the original bi-directed edges. The left panel Figure shows a diagram of 12 units and 18 interfering pairs.
Given the graph G, we write the unit i's potential outcome (Z,, Zx,), where A (j e V (i,j) E E} is the neighbor of unit i, and Zv,, := (Z,)jεN, is the neighbor treatment (sub-)vector. Following Forastiere al. (2021); Cai al. (2022), we further assume that Y, depends unit i's neighbor through the proportion of treated neighbors, which is defined by
P: = W Σ Zz-
JEM
Assumption 1 assumes the interference on the proportion of treated neighbor assumption. In this paper, we simply write Y,(,,, Pi): (0, 1) x [0, 1] + R as the potential outcome of unit i.
Assumption (interference on the proportion of treated neighbors) Let z and z' be two treat- ment vectors, and let Y; Z) be the potential outcome of unit i. We assume
Y((=) Yz(²)) whenever = 2 and pi = P/,,
where pt and p are the proportion of treated neighbors induced
and z', correspondingly.
Furthermore, for any two tuples (z, p), (2',p') E (0, 1) x [0, 1]. we define the unit-level causal effect as 7, (2, p, 2 p') = P2(z,)) Y1(2', p.), with certain special cases defined
(direct effect)
(p)
p1.,
(spillover effect)
(2.p.p))
= (2,,,,,,'),
(total effect)
= 7,,,,,,,,0)
The direct effect measures the marginal effect 2; under a given level interference. The indirect effect relates the effect of interference and is often called the "spillover "ffeett The total treatment
3

---

Published as a conference paper at ICLR 2024
12
11
10
10
Independent Set
Auxiliary Set
Z1
Z
Figure 1: Illustration of Independent Set design. (Left) Example graph. (Middle) The graph is partitioned into independent set and auxiliary set. (Right) Conduct experiment the independent set and the auxiliary set. Shaded nodes denote the treated nodes.
effect measures the change in outcome when all units are treated vs all units are controlled. Note that the total treatment effect can be decomposed as combination of direct and indirect effects such that 7/ = Ti (0) T. 1,0)
(d)
Experimenters are usually interested in the population-level average effects, which are defined as 7(2,p, p') == n -1 Σ T2(2, p', The average direct / spillover / total treatment effect is defined in a similar way. The average total treatment effect =(!) is particular interest because measures the average change in outcomes when all units assigned to treatment. Further discus- sions on causal effects under interference can be found in Forastiere et al. (2021).
3.2 INDEPENDENT-SE SET DESIGN
We disentangle the unit-level treatments and the interference by partitioning the units V into two sets, V, and VA. Let G, (V,, Fy) be the sub-graph G by restricting the vertex set V,, and require Gy to be null graph
=A= (VA, EA) be the sub bub-graph by restricting to VA- Specifically, such that E, 2, or equivalently, Vi an independent set of G. We call the counterpart VA as the auxiliary set. The middle panel in Figure gives one such partition for the interference graph in the left panel. We will later see that the two sets play different roles in the inference.
Denote the treatment vectors the independent set Vi and on the auxiliary set VA by Zi and A correspondingly. Define the Vil x |Val interference matrix I between V, and VA by Thi == d, (f, E F.). for all i E Vi.j E VA. where d: is the degree of unit i in G, and T(.} is the indicator function. The interference vector on independent set Pr := (pi)ieV; is determined by restrict our estimation to the independent set Vi,
given by
P₁ TZA. Because I is constant matrix when the graph G is observed, the auxiliary set's treatment vector Z the unit-level treatments Zj and the interference Pı can be separately controlled through Z and A, respectively. We call such a design "independent set design", which partitions the dataset into the independent set and the auxiliary set, controls the treatment and interference separately, and constructs an estimator based on the observed outcomes from the independent set.
The assignments for Z₁ and Za can be designed to accomplish different causal inference goals. For example, to estimate the average direct effect f(4) (p), one can assign Z; by completely random- ized design and optimize Z by minimizing [TZ pl1.- To estimate the average indirect effect 7(2, 1, 0), one can assign Z;
for all i E V, and optimize ZA by maximizing V To estimate the average total treatment effect, one can optimize ZA by maximizing WTr(TZz) and let provide one such assignment of Z and ZA for estimating the total treatment effect. The next sections will discuss the implementations for different causal inference tasks.
Z, 1 (p. 20.5) for all E V₁. In the right panel of Figure
Two aspects are compromised to improve the independent set's data quality. The first one is the sample size. Independent set design restricts estimation by using only observations of the indepen- dent set, which is usually a fraction of the dataset but of higher quality estimation. The second aspect that is compromised is the bias from the representativity of the independent set because the

---

Published as a conference paper at ICLR 2024
average effect the independent set is not necessarily identical the one the whole dataset. The unbiasedness is achieved when we assume the observed interference graph is random and is unconfounded with the potential outcomes. We discuss the assumptions in Section 4.1.
Algorithm 1: Greedy algorithm for finding independent set
Input: graph (V, E)
Output: independent set 7 Ø while V > do
Vi
Choose from V uniformly
V1 t (i}
V V (jeV: (i.5) Eori=
return V
Before proceeding to different design implementations, give greedy algorithm for finding locally largest independent set in Algorithm 1. The independent set of a graph is not unique in For inference purposes,
general any subset of an independent set is another independent would expect the variance of the estimator scales as -((V Therefore, the goal is to find the largest independent set, which known NP-hard (Robson, 1986). In practice, we adopt the fast greedy algorithm that can find the local largest independent set in linear time.
3.3 INFERENCE
In this section, we assume the two sets V, and VA have been obtained through the aforementioned greedy algorithm and discuss the designs of the assignments on Z₁ and Z for different inference tasks. For simplicity, we denote their sizes [V] and [Val by ny and n, respectively. Next, we discuss the estimations of the direct treatment effect and spillover effect separately.
3.3.1 ESTIMATING AVERAGE DIRECT EFFECTS
To estimate the average direct effects (p), one wishes to find an assignment vector ZA on the auxiliary such that all independent units" interference received is close p. The optimal assign- ment vector can be found by the following optimization.
min Z
TZA p1 11-
(2)
On the other hand, the treatment vector Z₁ for the independent set can be assigned randomly with a completely randomized design such that half of the units are randomly assigned to treated. The difference-in-means estimator the independent set can be constructed as
(
1
(obs) Zi
Σ Y (obb)) (1-Zi) VEVI
Zi),
(3)
/2/22
11/2
KEVI
where y/(obe) is the observed outcome of unit
The optimization in equation 2 is convex programming binary/integer space with an objective function bounded below by When p = 0 or 1, the optimization equation has a trivial but perfect solution as A p1 such that all the interference of independent units matches p exactly. However, this lower bound is not attainable for general < < 1. As we will later see Section 1.3.1, the objective function in equation 2 is directly related to the bias of the estimator in equation 3.
3.3.2 ESTIMATING AVERAGE SPILLOVER EFFECTS AND TOTAL TREATMENT EFFECTS
When estimating the average indirect effect (2) (z, 1, 0) or the average total treatment effect =!1), hope the interference received by the independent set units spreads the two extremes: either
Ps = 0 for empty interference or P; = for saturated interference. Therefore, we propose to maximize the variance of (pi)tev, in the following optimization:
max (0,,111
Z
11T TZ
(4)
5

---

Published as a conference paper at ICLR 2024
The above optimization is concave quadratic programming. and the support be expanded to its convex hull: [0, 1 while keeping the same solution. The objective function equa- tion is bounded below by nr/4, the largest eigenvalue of I - " 11",, by taking A = (I,..., 0, .,........ 0). The optimum may not be attainable when it is outside the manifold of T.
Consider a linear additive structure of the potential outcomes such that
(Z,, P:) a + 3Z; - -pp: + Ejt
(5)
where e, represents the heterogeneity potential outcomes and we assume Var[e:] = o².
With the additive linear model in equation 5, the causal effects are written in parametric form such that the direct effect is 3, the spillover effect is 7, and the total treatment effect is / + y- The coefficients can be estimated through standard linear regression estimators for the units in the independent set. Specifically, the estimators are
(a, 100-=(X'3) (X"x)-XXXX
where X [1, Z1, pı] is the design matrix and Yi is the outcome vector the independent set.
The variance of the estimators 3 and & depend inversely on the variance of Z₁ and Pr. respectively. The optimization in equation 4 minimizes the variance of linear regression estimators. Detailed discussions the variance of p, and the variance of the estimator are provided in Section 4.3.2.
Notice that difference-in-means estimators can be used nonparametrically to estimate spillover or total treatment effects. However, this results in fewer units with the required interference levels and, therefore, large variance.
4 THEORETICAL RESULTS
4.1
ASSUMPTIONS
We first list few more assumptions that necessary for subsequent analysis.
Assumption (super-population perspective) We view the n units from the super-populatte per- spective such that their potential outcomes are i.i.d. from some super- aaper-population distribution.
In Assumption 2, we assume the sample units are i.i.d. from a super- popper--pplltiion such that both V1 and V can be viewed as representative finite samples. Furthermore, if we denote as the average causal effects on the independent set V,, then under Assumption 2, we have E[[r]] = E[F]. which gives the unbiasedness of average causal effect on V, with respect to the (full) sample average effects.
Assumption (unconfoundedness of network) We assume the observed network is a realiza- tion of random network, which is unconfounded with the units' potential outcomes such that G I1. V, where y = [Y, Pt) [n], Z, E (0, 1), Px E [0, 1}} is the table of potential outcomes.
Furthermore, assume the network formation is independent of the potential outcomes in As- sumption 3. Note that the greedy algorithm of finding the independent set in Algorithm 1, and the optimizations of Z in equation 2 and equation 4 are not node-symmetric ferent degrees have different probabilities of being assigned to V/. It gives rise to the selection bias of the set Vr. Assuming the network unconfoundedness. the selection bias from a single sample is averaged if we consider multiple sampling repetitions and network randomization.
vertices with dif-
4.2 THE GREEDY ALGORITHM
The first question at hand is how large the set V, we can find from random graph G. Such graph always exists that one can hardly find a large independent set (for example, the complete graph). Due to the randomness of graph G. we can show such extreme cases occur with a negligible probability as + We consider the Erdös- Rényi random graph where each pair of units independently forms an edge with probability p s n. The random graph has an expected average degree pm = Note that most networks of interest (e.g., social networks) are connected and sparse networks. Therefore, we assume = o(n) for sparsity and assume 2(log n) for connectivity. Theorem gives lower bound on the size of the independent set V, resulting from Algorithm 1.

---

Published as a conference paper at ICLR 2024
Theorem (lower bound on the greedy algorithm) Consider Brdös-Rény random graph G with n vertices and edge probability p = =//n for s E M)logn). Then, with high probability, the independent set V1 from the greedy algorithm yields a size at least logen.
Note that Algorithm is greedy approximation in finding the locally largest independent set. Dani & Moore (2011) discussed the size of the globally largest independent set for random graphs. The resulting independent set has similar order of size compared to the globally optimal one. In the egocentric design (Saint-Jacques et al., 2019), the number of ego-clusters is upper bounded by n/(s + 1), which is smaller than ours by factor of log
4.3 ESTIMATION PERFORMANCE
In this section, we analyze the performance of the causal estimators for the tasks discussed Sec- tion 3.3 and provide additional insights into the optimizations in equation and equation 4.
4.3.1 ESTIMATING AVERAGE DIRECT EFFECT
We first investigate the performance of the sffference-in-menne estimator in equation for the direct effect. Recall that in order to construct (p), we first determine Z, through the optimization in equation 2, and then randomly assign half of V, to treated through completely randomized design. Given the sample set, including the potential outcomes Y and the graph G, for any assignment Z on the auxiliary set, we provide upper bound for the (conditional) bias and variance in Theorem 2.
Theorem 2 (bias and variance for estimating direct effects) Suppose Assumptions 1, 2 and 3 hold, and the potential outcomes Yı(z, p) is uniformly Lipschitz in such that there exists L > satisfying p1) Yı(z, P2)] S [|p p2) for all i [m], 2 E {0,1] and P1, [0. 1].
Consider the estimator in equation 3. We have
2L
B[+(0) (0) =()) (0) 10, S
A II and
(d) (p) V, ZA] - Varl7(00
ni mr(ni - 1) (LYman) man! ||I 1 + (
4
T4
where A = AZ p1 is the deviation of interference from the target p. Sy (1. p) + Yy(0,p) =
(n1 1 1---1 (Y,(1, (1(,,)) YL, p)- p), with Y p) = n, Exev, Y((2,))
the sample variance of the potential outcomes on V1, and Ymax = maxiev, PY,(1,)) + Y1(0, (11 (((p))-((00 Y(,, p)] is the maximum deviation of potential outcomes from their mean on Vj.
A represents the distance between the interference received by the independent units and the target value p. When A O. the design is equivalent to completely randomized experiment. In the general case, the optimization in equation 2 minimizes the upper bound for potential bias. Theorem also tells the variance of (d) close to the completely randomized design on V, ||| is small.
4.3.2 ESTIMATING SPILLOVER EFFECT AND TOTAL TREATMENT EFFECT
This section considers the two treatment effects discussed in Section 3.3.2. We focus the linear additive model equation 5 such that the effects can be estimated through linear regression. Recall that, for estimating either the spillover effect or the total treatment effect, the assignment Z, on the auxiliary set is determined through the variance maximization estimating the spillover effect and set Z, depending on P, for the total treatment effect.
equation 4. We set Z, to z for
The following theorem gives the bias and variance for the linear regression estimator for the spillover effects. The spillover effect estimator is always unbiased, and its conditional variance depends inversely on the variance of the interference Pr of the independent units. The optimization in corresponds to the minimization of the conditional variance of the linear regression estimator.
Theorem (bias and variance for estimating spillover effects) Assume Assumptions 1, 2 and 3. Consider a linear regression over the parametric potential outcome model equation 5 with estimated parameters 8 Set V1 =1 and let 7(0) (2,())))))) 1, 9. Then have
d²
(2, y = =(0 1,0)
and
Varl> 1,0) V.9.ZAl Var
7

---

Published as a conference paper at ICLR 2024
Theorem gives the unbiasedness of the total treatment effect estimator and provides lower bound on the variance. Such a lower bound is, in general, not attainable in the binary support of ZA, but provides the reciprocal dependence on Var Var] which was maximized in the optimization 4 as well.
Theorem (bias and variance for estimating total treatment effects) Assume Assumptions and 3. Consider linear regression over the parametric potential outcome model equation 5 with estimated parameters B, 3. Let x(0) = 3 + 3. Corrr Pi)) < 1, we have
a² ny Var Var Cov Z1
Var Zr pr_
B(A()) | =()) and Var(f!0) |9, Z.. Z1]
(ov2[Zi,, Pi)
The variance is lower bounded by o² (2n Var[pil)
EXPERIMENTS
In this section, we implement the independent set design and validate results empirically on synthetic graphs. In order evaluate the performance of the proposed design, we conduct simulations under a variety of simulated settings. The bias and variance of estimators are compared for completely randomized design the independent set (CR), completely randomized design the full graph (Full), ego-clusters, graph cluster, and Independent Set design (IS), which optimizes the assignments on the auxiliary To illustrate the benefits of IS design, implement the design estimate average spillover effects and average direct effects, respectively.
5.1 ESTIMATING AVERAGE SPILLOVER RFFECTS
First, we examine the performance of estimating average spillover effects for different designs. We run experiments on 50 Tedöss-éény random graphs (Erdös & Rényi, 1959) with 60, p 0.1, and estimate the spillover effects. The potential outcomes are randomly generated by (; p:) = U 4G, Vi V. and we let baseline a 1, treatment parameter 3 20, interference parameter 7 = 5, 10, 15, 20, U ~ (O, 1) and 6; ~ ((0,0..3 0.5).
Results are displayed in Figure 2. The independent-set design outperforms all other methods in estimating the average spillover effects. At different levels of interference, IS design shows the lowest bias and variance. We notice that the IS design is more stable than the other methods, and the variance of the IS design stabilizes at very low level as spillover effects increase.
clusle
1.2
Mean
Meus
0.8
Gamma
Gamma
Bias
(b) Variance
Figure 2:
Bias and variance estimate the average spillover effects. The bands around the lines represent the errors the estimator for each value Gamma.
To introduce diversity, we run experiments on distinct random graphs: Erdös-Rényi (Erdös & Rényi, 1959) G(n, p) Barabási-Allertt (Barabási & Albert, 1999) G(n, m) and small-world (Watts & Strogatz, 1998) G(n.p) The potential outcomes are based on (2 p:) V. and a; 1, B 20. 10. c (0, 0.5). Each configuration is run 2,000 times. The results of estimating spillover effects are summarized in Tables 2. As shown Tables 2, IS design outperforms all other methods distinct settings and achieves the lowest bias and variance.
Vi e
8

---

Published as a conference paper at ICLR 2024
Table 2: Performance in estimating average spillover effects under distinct random graphs.
CR
IS
Full
Graph Cluster
Ego Clusters
Graph
Parameters
Bias
Variance
Bias
Variance
Bias
Variance
Bias
Variance
Bias
Variance
100, O. 10
0.598
0.468
0.398
0.242
0,473
0.399
0.497
0.418
0.428
0.491
Frdiss Rényi
p
0.392
0.188
0.366
0.192
0.342
400. 0.15
0,246
0.096
0,225
0.067
0.266
0.094
0.242
0.089
0,239
0.091
Barabisi-AAii Albert
== 100, m
0.192
0.064
0.152
0.032
0.168
0.049
0.177
0.056
0.159
0,072
75, m
0.239
0.055
0.135
0.041
0.181
0.051
0.185
0.067
0.176
0.079
Small world
== 80, p= 0.05
0.303
0.165
0.212
0.087
0.263
0.089
0.274
0.093
0.232
0.117
= 50. p= 0.05
0.351
0.093
0.036
0.277
0.296
0.061
0.089
5.2 ESTIMATING AVERAGE DIRECT EFFECTS
We will next implement an IS design estimate average direct effects and evaluate perfor- mance under various settings. Here, the potential outcomes are randomly generated according to (2, P:) a; + 3Z; +Pp; 4, Vi V, and we have a; 1, 3 20, y 10. e; (O, 0.5). We run experiments 2,000 times and record the bias and variance of estimators. Table 3 shows the results of estimating average direct effects. In the presence of spillover effects, IS design achieves the best performance (the lowest bias and variance). When SUTVA is violated, network interference impairs the performance of conventional approaches. In this case, estimators classical designs are biased in estimating average direct effects. In contrast, IS design could mitigate the spillover effects and improve performance by controlling treatment assignments on the auxiliary set.
Table 3: Performance of designs in estimating average direct effects under distinct random graphs.
CR
IS
Full
Graph Cluster
Graph
Parameters
Bias
Variance
Bias
Variance
Bias
Variance
Bias
Variance
= 100, p 0.1
0.262
0.035
0.117
0.009
0.261
0.023
0.221
0.024
Erdös-Rényi
n 200, p= 0.1
0.193
0.038
0.094
0.005
0.188
0.015
0.156
0.013
400, p 0.1
0.098
0.006
0.062
0.002
0.086
0.004
0.081
0,005
80, m
1.145
0.851
0.237
0.034
1.130
0.949
1.031
0.815
Barabási-Albert
n= 100, m
1.207
0.693
0.278
0.026
1.296
0,832
1.139
0.742
100, 0.05
0.961
0.556
0.278
0.024
1.184
0.791
1.105
0.716
Small world
50, p= 0.05
1.101
0.869
0.225
0.029
1.115
0.877
1.013
0.854
DISCUSSION AND CONCLUSION
Randomization experiments networks can be biased due to interference among units, making causal inference on units challenging. In this study, we propose a new randomized design that separates units into independent and auxiliary sets to control interference. Our design can be applied to any network and provides accurate estimations with good interpretability.
Whilst IS design allows us improve the estimation of causal effects on networks, there several limitations. Due to the segmentation of units in a network, we can only estimate causal effects on the independent set. The experiment's sample size will be smaller than using the full network. Moreover, the computational cost depends on the size of the auxiliary set, so it may take more time optimize the assignments on the auxiliary set. Another limitation is that our design depends on observed networks. The performance of the proposed design on misspecified network is unknown. Future research includes improving the computational efficiency of the algorithm to optimize the assignments on the auxiliary set and further extending it when the network is misspecified.
ACKNOWLEDGEMENTS
This work supported in part by NSF award 1409177 and by ONR award N00014-17-1-2131.

---

Published as a conference paper at ICLR 2024
REFERENCES
Peter M. Aronow and Cyrus Samii. Estimating average causal effects under general interference, with application to a social network experiment. The Annals of Applied Statistics, 11(4):1912 1947, 2017.
Susan Athey, Dean Eckles, and Guido Imbens. Exact p-values for network interference. Journal of the American Statistical Association, 113(521):230 240, 2018.
Usaid Awan, Marco Morucci, Vittorio Orlandi, Sudeepa Roy, Cynthia Rudin, and Alexander Vol- for treatment effect estimation under network interference. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pp. 3252-3266 3262.. PMLR, 2020.
fovsky. Almost-matching-exae
Abhijit Banerjee, Arun G. Chandrasekhar, Esther Duflo, and Matthew O. Jackson. The diffusion of microfinance. Science,
2013.
Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286 (5439):509-51 1999.
Guillaume W Basse, Avi Feller, and Panos Toulis. Randomization tests of causal effects under interference. Biometrika, 106(2):887-494, 2019.
J Martin Bland. Cluster randomised trials in the medical literature: two bibliometric surveys. BMC Medical Research Methodology, 4(1):1-6, 2004.
Chencheng Cai, Jean Pouget-Abadie, and Edoardo M Airoldi. Optimizing randomized and deter- ministic saturation designs under interference. arXiv preprint arXiv:2203.06682 2022.
Varsha Dani and Cristopher Moore. Independent sets random graphs from the weighted sec- ond moment method. In Approximation, Randomization, and Combinatorial Optimization. Algo- rithms and Techniques, pp. 472-482, 2011.
Nick Doudchenko. Minzhengxiong Zhang, Evgeni Drynkin, Edoardo Airoldi, Vahab Mirrokni, and Jean Pouget-Abadie. Causal inference with bipartite designs. arXiv preprint arXiv:2010.02/08, 2020.
Dean Eckles, Brian Karrer, and Johan Ugander. Design and analysis of experiments in networks: Reducing bias from interference. Journal of Causal Inference, 5(1), 2017.
Paul Erdös and Alfréd Rényi. On random graphs i. Publicationes Mathematicae Debrecen, 6(290- 297):18, 1959.
Laura Forastiere, Edoardo M Airoldi, and Fabrizia Mealli. Identification and estimation of treatment and interference effects in observational studies on networks. Journal of the American Statistical Association, 116(534):901-11 2021.
Alan Frieze and Michal Karoński. Introduction to random graphs. Cambridge University Press, 2016.
David Holtz, Ruben Lobel, Inessa Liskovich, and Sinan Aral. Reducing interference bias in online marketplace pricing experiments. arXiv preprint arXiv:2004. 200.:9299....99,,,.. 12489, 2020.
Michael G Hudgens and M Elizabeth Halloran. Toward causal inference with interference. Journal of the American Statistical Association, pp. 832-842, 2008
Guido W. Imbens and Donald B. Rubin. Causal Inference in Statistics, Social, and Biomedical Sciences. Cambridge University Press, 2015.
Ramesh Johari, Hannah Li, and Gabriel Weintraub. Experiment design in two-sided platforms: An analysis bias. In Proceedings of the 21st ACM Conference on Economics and Computation, EC 200 2020.
10

---

Published as a conference paper at ICLR 2024
Vishesh Karwa and Edoardo M Airoldi. A systematic investigation of classical causal inference strategies under mis-speciiication due to network interference. arXiv preprint arXiv:1810.08259, 2018.
Lan Liu, Michael Hudgens, and Sylvia Becker-Dreps. On inverse probability-weighted estimators in the presence of interference. Biometrika, 103(4):829-88) 8422 2016.
Elizabeth Ogburn and Tyler VanderWeele. Vaccines, contagion, and social networks. The Annals of Applied Statisties, 11(2):919 99999999,,,,, 2017.
Art B. Owen and Hal Varian. Optimizing the tie-breaker regression discontinuity design. Electronic Journal of Statistics, 14(2):400440077, 2020.
Tuan Q Phan and Edoardo M Airoldi. A natural experiment of social network formation and dy- namics. Proceedings of the National Academy of Sciences, 112((1))6595--660) 6600, 2015.
Jean Pouget-Abadie, Kevin Aydin, Warren Schudy, Kay Brodersen, and Vahab Mirrokni. Variance reduction in bipartite experiments through correlation clustering. In Advances in Neural Informa- fion Processing Systems, volume 32, 2019a.
Jean Pouget-Abadie, Guillaume Saint-Jacques, Martin Saveski, Weitao Duan, Souvik Ghosh, Ya Xu, and Edoardo M Airoldi. Testing for arbitrary interference on experimentation platforms. Biometrika, 106(4):929-940, 2019b.
John Michael Robson. Algorithms for maximum independent sets. Journal of Algorithms, 7(3): 425 440, 1986.
Paul R Rosenbaum. Interference between units in randomized experiments. Journal of the American Statistical Association, 102(477), 2007.
Guillaume Saint-Jacques, Mancesh Varshney, Jeremy Simpson, and Ya Xu. Using ego-clusters to measure network effects at linkedin. arXiv preprint arXiv: 1903.0875,5 2019.
Betsy Sinclair, Margaret McConnell, and Donald Green. Detecting spillover effects: Design and analysis of multilevel experiments. American Journal of Political Science, 1654)1005,-106, 2012.
Michael E Sobel. What do randomized studies of housing mobility demonstrate? causal inference in the face of interference. Journal of the American Statistical Association, (014476: 1407, 2006.
D. L. Sussman and M. Airoldi. Elements of estimation theory for causal effects in the presence of network interference. arXiv:1702.03578, February 2017.
Panos Toulis and Edward Kao. Estimation of causal peer influence effects. In Proceedings of the 30th International Conference on Machine Learning, pp. 1489-1497, 2013.
Johan Ugander and Hao Yin. Randomized graph cluster randomization. Journal of Causal Inference, I1(1), 2023.
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 Knowledge Discovery and Data Mining, KDD 13, pp. 329-337, 2013.
Martin J Wainwright. High- Hiigh-dimensionl statistics: non-asymptotic viewpoint, volume 48. Cam-
bridge university press, 2019.
Dunean J Watts and Steven H Strogatz. Collective dynamics of wewtwokswrlddnetwww.. Nature, 393 (6684):440-442 1998.
Yuan Yuan, Kristen Altenburger, and Farshad Kooti. Causal network motifs: Identifying heteroge- neous spillover effects in a/b tests. In Proceedings of the Web Conference 2021, WWW '21, pp. 3359-3370, 2021.
11

---

Published as a conference paper at ICLR 2024
Johann G Zaller and Ulrich Köpke. Effects of traditional and biodynamic farmyard manure amend- ment on yields, soil chemical, biochemical and biological properties in long-term field experi- ment. Biology and Fertility of Soils, 40(4))222-229, 2004.
Corwin M. Zigler and Georgia Papadogeorgou. Bipartite causal inference with interference. Statis- lical Science, 36(1):109- - 123, 2021.
12

---

Published as a conference paper at ICLR 2024
Appendix
A PROOF OF THEOREM
In order to prove the lower bound, we follow the differential equation method in (Frieze & Karoński, 2016, Chapter 24).
Recall Algorithm 1, and let V/24 = ,,.... Vil be the selected independent unit at step t. Denote (tt) the set vertices after step in the algorithm such that (()) = n and V v[[Vr] 0. Write
( (t)] as the number of remaining units after picking out independent units. Then the algorithm gives
X(L+ 1) x(1) d(ve+1 1 V()), for 0, ... [V, 1,
where d(v++1 (()) is the degree of 2++1 in the subgraph containing the vertex set Vtt). Let f(t,x)= 8x (1 p) and
(t,x): -=((,a)) D= D=
- <<<<
n1
We now show the conditions (P1)-(P4) in (Frieze & Karoński, 2016, Chapter 24) are satisfied.
(PI): It is obvious X(I) x(0) = n. Therefore, (PI) satisfied with Co = (P2): Since (t (() = d(r++1 V(()) + v d(r++1 Vo) + 1, where e is the vertex deleted at step We claim with high probability,
d(ve41 Vo) max d(v Vo) < 2(s + log n) 1.
wEG
It follows from
max d(v Vo) 26 s Σ vEG
P(d(v Vo) g
VEG
- 1
n
n
nf (n
+ 1)
2 nexp
log
(n
1)8
(n
1)8
1)s
E
< exp logn { log
+
where (i) follows from the Chernoff bound of binomial distributions (see, for example, Chapter 2 in Wainwright (2019)).
By setting & = (s + log - > eas, we have
IP
max d(u Vo) 2 e s + log -1| < ne << e vEG
n=a e
-
Therefore,
+ 1) X() logn)
satisfied with probability at least 1 ----==----0 > - 66 68 (P3):Let & be the event that (P2) holds. Then,
[E(X X(1) V(),. S(/0, x(1)nn)] =
(P4): It immediate that [tt, f(t', s|r x²1.
To use Theorem 24.1 in Frieze & Karoński (2016), we set
Co
3 e + log n)
A n r-11/3
(s + log n)
7 6 E 65
36
13

---

Published as a conference paper at ICLR 2024
Then we have (t) no(t/n) ( + n)) uniformly on < at, with probability
least 1 (n 6 + nn/33-e -n ) = en- 69) 2 O(n O(n-12).
2t) satisfies the following ODE that:
zt) f(t, x(t) sz(() (1 p),
with initial condition that =00 (() The solution is
1 1-p + 11 1 1011-10 st
x(t) =
g
We have z(1) on 0, _/2 log
++1-p I-p
00 log
Therefore, with high probability, (()) 2 0 for
t log n.
In conclusion, we have at least logen iterations in the greedy algorithm, resulting in an independent set of size least log 'n with probability at least O(n
B PROOF OF THEOREM 2
We fix the potential outcomes V, the graph G, and the assignment Z for the auxiliary set. Recall the difference-in- in-means estimator:
7(00 (0)
1
y,
(obs)) Zi 11/2 iEV,
Y
(obs) (1 - Zi).
n1/2 REVI
We have the expectation:
1 Σ Y:(1,p))
1 Σ pi),, n1 iEV,
((+(0()) (2,
n1 iEV;
where we use the facts that Pj is fixed given and Z and E[Z,] 1/2. Therefore, the bias is
B (p) 12.9. ZA] x(4)
Σ
[1(1,
-((1p))
Σ
(V) Y((1
125
n1 iev,
LEV,
2T.
<
Σ
lp:
pl
2L
Pr p1111.
Next, we give the variance.
Var(=(0) (p)
1
=Var
(1) + p:(0,
n1/2 iEVI
4
Σ
(x) + Y:(0, (((0.,:))) (:a(()
n1 iEVi
Σ [ Y:00, (100=/=-~X0000000000000000000110
LjEV,
Σ
[X, p.) Y,(00,
Σ
+Y,(0,
7 IEV,
nZ(ns - 1)
1
s,(M p.) + +Y
ny
14

---

Published as a conference paper at ICLR 2024
Therefore, have
Var (p) 11 ZA] 1 s, vi(O,
11
[25r[Y]LL, + Y1( - S,|Y p) ()1
n1
(28y(0,, (1(1,)) P) + ()( + (,,))
n1
1
< n1 (n) - 1)
[2||6]]] Y mar + +16,11
4
[L| max + +131 |r1li
n1(ni 1)
where 6; = p:), + pt) - Y1(,,)) + Y.(0,))))))))))))) $ 2LA, and
(((L.p)+Y((0. 1 Σ
Y maz
max sVV;
p)
11
iEV
C PROOF OF THEOREM 3
Consider the linear regression Y, a 32; 7P: for V₁. When Z, is constant in the design, the linear regression is equivalent to Y; ~ ā + 7Pi where à == a + Bz. By observing +(0) 1, 0) = 3 the result follows immediately from univariate linear regression.
D PROOF OF THEOREM
Let Y, the observed outcomes on the independent set such that Y, a1 + 32, + +6, We write the design matrix
1
7,
P1
X x= Z1 pi] = 2,
Pr
0
1
0
0
1
where 2, and pr are sample means of Z and pr. correspondingly, and 2, and Pr are de-meaned versions of Z₁ and Pl, correspondingly.
Let à, 3. & be the regression estimators. The unbiasedness of - + f to the true value B + y is immediate. Now we calculate the covariance matrix such that
Covi(á, 8, 0² x X
X
1
7
0 ny Var Zy] ni Covl PI)
0 noCov Zi, pI) ni Var (pi]
1
0
0
2
2,
1
0 1
0
0
Pr
0
- - -7
S-1 5-1(Z, 77, - -
0²
-S 17 pZ.p)
5 Var(p.)
-S Cov Z,,
(2 2
S --v' Zr,pr]
S 1 Var
where S Var Zy Varlps] Cov 2
Therefore, we have
o² Var[Z + Var 2Cov Z1,
Varl3 +
ni Var Z, Var(pı] Cov [2 p1]
Consider the function f()::
Var Z + Var [p]] 2A
A
Var Zr
X2
15

---

Published as a conference paper at ICLR 2024
Then we have
df 2(A (ar - -
dx (Var War/p]] Cov
pı])²
Therefore, when X Var Var[pr)) f()) takes its minimum at X Var A Var[pr] such
that
S(x*) Var Zr] A Var(pi]
2
Varlpi
Therefore, we have
a²
Varl3 91 2
n, Var[pı]
The lower bound can be obtained by choosing Z Ps E 00, 1]" generally outside the binary support for Z
16


Reviews:
[{"review_id": "swH9CYTmLb", "reviewer": "Reviewer_pw71", "summary": "The paper tries to find a lower bound on the random algorithm to find independent sets in Erdos-Reyni random graph. The paper claims that this independent set is of the order of the size of all nodes in the random graph. They further go on to use this result to estimate the bias and variance for direct effects and spillover effects related to their specific problem setup. They seem to further verify these results through computer simulations of an Erdos-Reyni graph. The results seem interesting to me. Specifically, I like Theorem 1 and based on my prior experience with Erdos-Reyni graphs, the results of this theorem seem to be intuitively correct. However, unfortunately I did not put the effort to follow the proofs in the paper in detail so I cannot independently verify their claims.", "questions": "I am not sure about the validity of assumptions used in the paper. Specifically assumptions 1 and 2. I would like to see more reasoning from the side of the authors on why these assumptions make sense. Any motivating examples could help the reader on these assumptions. \n\nIn equation 1, why is interference from neighbors simply summed up without any gains? Could it be the case that the interference from different neighbors can have a different effect on the results and we need to put more emphasis on some interference while putting less emphasis on other types of interference? \n\nI suggest the authors to emphasis more in the paper that these results are derived for an Erdos-Reyni random graph setup and not necessarily any network. For instance, I did not see any mention of that in their abstract. The wording throughout the paper needs to be changed to reflect that these results are derived for random graphs. \n\n I would like the authors to specify in more detail that which part of their results is coming from different sources. For instance, Can the authors mention their contribution over Karwa & Airoldi (2018) in more detail?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "If the claim in Theorem 1 is correct that is an interesting result. Intuitively that result makes sense to me. However, I did not completely verify the proofs. \n\nThe paper presentation is good and readable.", "weaknesses": "I am not sure about the validity of assumptions used in the paper. Specifically assumptions 1 and 2. I would like to see more reasoning from the side of the authors on why these assumptions make sense. Any motivating examples could help the reader on these assumptions. \n\nIn equation 1, why is interference from neighbors simply summed up without any gains? Could it be the case that the interference from different neighbors can have a different effect on the results and we need to put more emphasis on some interference while putting less emphasis on other types of interference? \n\nI suggest the authors to emphasis more in the paper that these results are derived for an Erdos-Reyni random graph setup and not necessarily any network. For instance, I did not see any mention of that in their abstract. The wording throughout the paper needs to be changed to reflect that these results are derived for random graphs. \n\n I would like the authors to specify in more detail that which part of their results is coming from different sources. For instance, Can the authors mention their contribution over Karwa & Airoldi (2018) in more detail?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "MkiJ4SGd7Q", "reviewer": "Reviewer_vRUq", "summary": "This paper proposes to partition a sparse but connected (causal) graph into independent set and auxiliary set. Using this method of partition, treatment can be designed to estimate direct and spillover effects for causal inference tasks. Theoretical guarantees on bias/variance of the estimators were given together with simulation results.", "questions": "1.\tThe simulation results are comparing only to completely randomized design. Is it possible to compare with other designs cited in the introduction and Table 1? \n2.\tThere are some typos, for example, in section 4.3 and 4.3.2, it is referring to section 2.3 and 2.3.2 which does not exist. (Should be 3.3 and 3.3.2?)", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThe problem definition is clear with good illustration to explain the concept of independent set and auxiliary set.\n2.\tTheoretical results are provided with good descriptions of the assumptions and limitations.", "weaknesses": "1.\tThe main weakness in this paper is the lack of a clear comparison to related works both theoretically and numerically. For example, how does the new theoretical guarantees improve over previous works? Otherwise, the analysis looks like an application of linear regression estimator. \n2.\tOne contribution the paper claimed is using fewer assumptions for this model, it would be better to describe this more clearly. For example, what assumptions can be removed compared to previous works?\n3.\tThe results rely on the greedy algorithm 1 to have a decent performance. Theorem 1 only gives the lower bound on ER graph which seems to limit the application of this framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "SD5DWK2x4X", "reviewer": "Reviewer_DrFU", "summary": "The paper proposes experimental designs using the independent set approach to estimate both direct and spillover effects for general networks. Both theoretical justification and experimental results are provided to demonstrate advantages over competing designs.", "questions": "Experimentation Questions:\n- Inconsistency: Why does Figure 2 use n=60 whereas Table 2 uses n={100,200,400}?\n- Why is Graph Cluster omitted from Figure 2?\n- Graph Cluster is not mentioned in the Section 5 introduction, what cluster design is used?\n- Is there a reason some designs mentioned in Section 2 (ego-clusters, randomized saturation) appear to be omitted?\n- Given the discussion in Section 4.2, how do results vary for more varied p/s specifications for ER random graphs?\n- How robust are the results to the size of the independent set?\n- What is the $\\rho$ chosen for the IS design in section 5.2? Is it the usual IS setting from Karwa and Airoldi where $\\rho = 0$?\n\nMinor nomenclature question: The direct effect should be $\\tau_{i}^{(d)}(0)$ and $\\tau_{i}^{(d)}(\\rho)$ represents the total effect in a partial spillover situation, correct?\n\nHow reasonable is Assumption 2 given the greedy algorithm to construct $V_I$ has no concern for representativeness?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Many interference designs focus on estimating the total effect, whereas the literature focusing on designs to measure the spillover effect specifically is more limited. This is an important problem and the paper proposes optimal designs that are flexible and also show strong theoretical and experimental results.\n\nThe proposed designs are novel and simple to implement.", "weaknesses": "The experimentation section could use more polish/clarity, and possibly some additional exploration (see questions below). In particular, there are inconsistencies in the displayed results and limitations due to the greedy algorithm, as well as assumption 2, could be better addressed in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "kkwOYYLkxF", "reviewer": "Reviewer_hHf8", "summary": "Interference is a common problem in experimental designs that biases estimation of treatment effects. This paper attempts to correct for interference by designing an experiment on a subset of the data that consists of non-interfering units. Given an interference network this paper provides an algorithm for treating units for various parameter goals. The paper provides a comparison on the sample efficiency of the method related to other methods and provides bias and variance computations.", "questions": "- How does this method work when G is misspecified? \n- It would be good to see how this could be applied in a practical example with different underlying graphs\n- How does optimizing over treatments effect the randomization assumption? Could this effect the internal validity of the study if randomization is weakened (i.e. in the vein of Bugni, Canay, and Shaikh 2017) moreover could there be distributional differences between the independent set and aux sets?\n- Since treatment effects can only be computed on the independent set how does this impact possible external validity of the study?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "- The paper provides a novel algorithm for treating units to minimize the effects of interference and maximizing sample efficiency for specific graph classes.\n- It is also good that the paper provides an optimization framework that can be used for computation of various causal parameters. This is something that is often missing in interference papers.\n- Theoretical analysis provides proof of unbiasedness and computation of estimator variance showcasing theoretical proof of method.\n- While the theoretical section relies on some stringent assumptions, i.e. G \\perp Y, the algorithm itself is relatively assumption free aside from a requirement of sparsity which is often true in practice", "weaknesses": "It is difficult to assess the contribution of the paper because the idea of designing experiments on non-interfering units has been well studied in previous works -- this is documented in the paper's related works. This paper attempts to design a more robust methodology towards this idea but relies on knowledge of the underlying network G. In practice this is never known and the paper does not consider the case of a misspecified G. \n\nThe theoretical results are good but they rely on stringent assumptions (although possibly weaker than other works). In particular it seems that the sample efficiency results are specific to the case of an erdos-renyi graph. Furthermore, the methodology rules out complete graphs and in general requires a degree of sparsity in the underlying graph. Since G is given or estimated this could be enforced but possibly unpalatable in some cases. Furthermore, as with other approaches to interference using partitioning algorithm there is a trade off with statistical power.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)