# Causal Inference under Network Interference Using a Mixture of Randomized
Experiments

Yiming Jiang
School of Industrial and Systems Engineering
Georgia Institute of Technology
Atlanta, GA 30332
<EMAIL_ADDRESS>
&He Wang
School of Industrial and Systems Engineering
Georgia Institute of Technology
Atlanta, GA 30332
<EMAIL_ADDRESS>

###### Abstract

In randomized experiments, the classic _stable unit treatment value
assumption_ (SUTVA) states that the outcome for one experimental unit does not
depend on the treatment assigned to other units. However, the SUTVA assumption
is often violated in applications such as online marketplaces and social
networks where units interfere with each other. We consider the estimation of
the average treatment effect in a network interference model using a mixed
randomization design that combines two commonly used experimental methods:
Bernoulli randomized design, where treatment is independently assigned for
each individual unit, and cluster-based design, where treatment is assigned at
an aggregate level. Essentially, a mixed randomization experiment runs these
two designs simultaneously, allowing it to better measure the effect of
network interference. We propose an unbiased estimator for the average
treatment effect under the mixed design and show the variance of the estimator
is bounded by $O({d^{2}}n^{-1}p^{-1})$ where $d$ is the maximum degree of the
network, $n$ is the network size, and $p$ is the probability of treatment. We
also establish a lower bound of $\Omega(d^{1.5}n^{-1}p^{-1})$ for the variance
of any mixed design. For a family of sparse networks characterized by a growth
constant $\kappa\leq d$, we improve the upper bound to
$O({\kappa^{7}d}n^{-1}p^{-1})$. Furthermore, when interference weights on the
edges of the network are unknown, we propose a weight-invariant design that
achieves a variance bound of $O({d^{3}}n^{-1}p^{-1})$.

_Keywords_ experimental design $\cdot$ causal inference $\cdot$ network
interference $\cdot$ clustering $\cdot$ SUTVA

##  1 Introduction

Randomized experiments are a powerful tool for understanding the causal impact
of changes. For example, online marketplaces use randomized experiments to
test the effectiveness of new features (Johari et al.,, 2022); tech companies
build large-scale experimentation platforms to improve their products and
systems (Paluck et al.,, 2016; Saveski et al.,, 2017); economists and social
science researchers rely heavily on randomized experiments to understand the
effects of economic and social changes (Leung, 2022a, ). The overarching goal
of randomized experiments is to impute the difference between two universes
that cannot be observed simultaneously: a factual universe where the
treatments assigned to all units remain unchanged, and a counterfactual
universe where all units receive a new treatment. The difference in the
average outcome between these two universes is commonly known as the average
treatment effect (ATE). Standard estimation approaches for the ATE such as A/B
testing rely heavily on a fundamental independence assumption: the _stable
unit treatment value assumption_ (SUTVA) (Imbens and Rubin,, 2015), which
states that the outcome for each experimental unit depends only on the
treatment it received, and not on the treatment assigned of any other units.

However, SUTVA is often violated in settings where experimental units interact
with each other. In such cases, ignoring the interference between treatment
and control groups may lead to significant estimation bias of the ATE. For
example, suppose an e-commerce retailer wants to determine the causal effect
on its sales by applying a price promotion to all products. One simple
approach is to run an experiment that applies promotion randomly to a subset
of products, and then compare the average sales of promoted products with non-
promoted products. However, simply comparing the difference in the two groups
will likely overestimate the average treatment effect of the promotion,
because customers may alter their shopping behavior in the experiment by
substituting non-promoted products for similar promoted products. As such, if
the retailer decides to implement the price promotion for all products on its
platform based on the result of this experiment, the realized sales lift may
be smaller than expected.

One common approach for reducing the estimation bias of ATE in the presence of
interference is _cluster-based randomization_ , which assigns treatment at an
aggregate level rather than at the individual level. In such a design, the
population of the experiment is often represented by an underlying network
$G(V,E)$, where each vertex in the set $V$ represents an individual
experimental unit, and a directed edge $(i,j)\in E$ indicates that the outcome
of unit $i$ may be affected by the treatment of another unit $j$. The weights
on the edges represent the magnitude of interference between two units. Note
that the weights on $(i,j)$ and $(j,i)$ can be different, as the interference
between two units may be asymmetric. A cluster-based randomization design
partitions the network into disjoint subsets of vertices (i.e., clusters) and
applies the same treatment to all units within the same cluster. Clearly,
using larger clusters will reduce the number of edges across clusters and will
better capture the network interference effect between units, which leads to a
smaller bias. However, a downside of using larger clusters is that there will
be fewer _randomization units_ in the experiment, resulting in higher variance
in the ATE estimation. Considering this bias-variance trade-off, a substantial
body of literature delves into optimal cluster design under network
interference (Ugander et al.,, 2013; Candogan et al.,, 2023; Leung, 2022b, ;
Brennan et al.,, 2022).

In this paper, we propose a modification of cluster-based randomization by
mixing it with another commonly used experiment design in which each unit is
individually and independently randomized, i.e., _Bernoulli randomization_. As
one experimental unit cannot receive two different treatments at the same
time, the mixed design determines which randomization method applies to a
given unit by a coin flip. Essentially, the mixed design _simultaneously_ runs
a cluster-based randomized experiment on one half of the network and an
individually randomized experiment on the other half. The idea of mixing
cluster-based and Bernoulli designs is proposed by (Saveski et al.,, 2017;
Pouget-Abadie et al., 2019b, ), which uses the mixed design to detect the
existence of network inference effect (i.e., hypothesis testing for SUTVA).
But to the best of our knowledge, the effect of using mixed randomization
design in estimating average treatment effects has not been previously
studied.

We summarize the main results of the paper as follows. In Section 3, we define
an unbiased estimator for the ATE under mixed randomization designs and
establish bounds on the variance of the estimator given any cluster design
(which is used in the cluster-based part of the experiment). Due to
computational challenges, these variance bounds cannot be directly applied to
optimize cluster design. We propose several heuristics for clustering and
analyze the variance of the estimator in these heuristics. For general
networks, we prove a bound on the ATE estimation variance in the order of
$O({d^{2}}/(np))$ where $d$ is the maximum degree of the network, $n$ is the
network size, and $p$ is the fraction of units that receive treatment. Our
result improves the state-of-the-art $O(d^{6}/(np))$ upper bound in Ugander
and Yin, (2023), which uses cluster-based randomization design. We also
establish a lower bound of $\Omega(d^{1.5}/(np))$ for any mixed design that
matches the upper bound up to a factor of $\sqrt{d}$. For a family of sparse
networks characterized by a growth constant $\kappa\ll d$, we improve the
upper bound to $O({\kappa^{7}d}/(np))$.

In Section 4, we extend the analysis to the case where the degree of
interference between units, namely, the edge weights of the network, are
unknown _a priori_. We propose a weight-invariant mixed randomization design
that is agnostic to edge weights, and show the algorithm has an upper bound on
the estimation variance in the order of $O({d^{3}}/(np))$. Furthermore, we
show that our proposed estimators are consistent and asymptotically normal
provided that the graph is sufficiently sparse (Section 5). Finally, we use
numerical experiments to illustrate the efficacy of the proposed mixed
randomization algorithms in Section 6 and compare it with (pure) cluster-based
randomization.

##  2 Related Works

There is extensive literature that explores experiment design where
experimental units interfere with each other. Halloran and Struchiner, (1995)
considered designing and analyzing experiments with interference motivated by
infectious diseases. Hudgens and Halloran, (2008) extended their work by
estimating the causal effects of treatments when interference exists within
disjoint groups. Manski, (2013) and Aronow and Samii, (2017) further
generalized the approach to problems where interference is represented by a
treatment vector known as exposure mapping. The exposure mapping framework
forms a foundation for subsequent studies of various types of experiments,
such as graph experiment (Ugander et al.,, 2013; Ugander and Yin,, 2023),
bipartite experiment (Pouget-Abadie et al., 2019a, ; Brennan et al.,, 2022;
Harshaw et al.,, 2023), switchback experiment (Bojinov et al.,, 2023), and
micro-randomized trials (Li and Wager,, 2022), among others.

When the SUTVA assumption is violated by interference between units, several
experiment design approaches have been proposed to to mitigate the estimation
bias. One common approach is cluster-based randomization, which partitions
units into clusters and then assigns random treatments at the cluster level.
Previous studies have shown that cluster-based design can reduce bias when
interference exists (Eckles et al.,, 2016; Leung, 2022b, ) as well as
estimation variance under neighborhood interference (using an unbiased
Horvitz-Thompson (HT) estimator) (Ugander et al.,, 2013; Ugander and Yin,,
2023). Another approach is using a multi-level randomization design where
treatments are applied with different proportions to groups, assuming that
there is no interference between groups (Hudgens and Halloran,, 2008; Tchetgen
and VanderWeele,, 2012). A third approach is using regression adjustment in
experiments with covariates to improve estimation precision (Chin,, 2019).

Our work studies causal inference with network interference. Specifically, we
consider a setting with linear exposure mapping, which is a generalization of
the partial interference assumption and stratified interference assumption in
Hudgens and Halloran, (2008). The linear exposure mapping assumption is also
common in studies of bipartite experiments (Brennan et al.,, 2022; Harshaw et
al.,, 2023)) and social network experiments (Bramoullé et al.,, 2009; Toulis
and Kao,, 2013; Pouget-Abadie et al., 2019b, ). Another common assumption on
the exposure mapping in the literature is that interference solely comes from
a unit’s neighbors (Ugander et al.,, 2013; Ugander and Yin,, 2023) and
otherwise allows for inference under arbitrary exposure mappings. More
recently, problems under more general exposure mapping assumptions have been
studied. For example, Leung, 2022b  studied the case where interference may be
present between any pair of units but the extent of interference diminishes
with spatial distance. A similar analysis was also presented in Leung, 2022a .
Sävje, (2023) considered the setting where the exposure mapping may be
misspecified and discussed the conditions under which unbiased causal effects
can be estimated.

Our main goal in this paper is to correctly estimate the average treatment
effect (ATE) under network inference. In addition to this goal, there are
other goals that have attracted the attention of researchers. Saveski et al.,
(2017) and Pouget-Abadie et al., 2019b  considered a hypothesis testing
problem of detecting the existence of network interference. Our approach is
partially motivated by the randomization over randomized experiments approach
proposed in those papers. Sävje et al., (2021) considered the inferential
target of estimating the direct treatment effect under unknown interference.
Candogan et al., (2023) developed a family of experiments called independent
block randomization, which aims at correlating the treatment probability of
clusters to minimize the worse-case variance.

##  3 Analysis of Mixed Randomization Design

###  3.1 Notation

Let $[n]:=\\{1,...,n\\}$ for any $n\in\mathbb{Z}_{+}$. And let $[a:b]$ be the
set of integers $\\{a,a+1,...,b-1,b\\}$ for any $a,b\in\mathbb{Z}$ and $a\leq
b$. Throughout the paper, we use the boldface symbols (e.g., $\BFx$) to denote
a vector and $x_{i}$ to denote its $i^{\text{th}}$ element.

###  3.2 Network Causal Inference Model

Below, we define a causal inference problem with network interference using
the exposure mapping framework (Aronow and Samii,, 2017). Consider an
experiment with $n$ individual units. Each unit $i\in[n]$ is associated with a
potential outcome function $Y_{i}(\cdot):\\{0,1\\}^{n}\rightarrow\mathbb{R}$,
which maps a treatment vector $\BFz\in\\{0,1\\}^{n}$ to a potential outcome
value. Let the average expected outcome of all units given the assignment
$\BFz$ be

$\displaystyle\mu(\BFz)=\frac{1}{n}\sum_{i=1}^{n}Y_{i}(\BFz).$

Let $\textbf{1}\in\mathbb{R}_{n}$ be a vector of 1’s and
$\textbf{0}\in\mathbb{R}_{n}$ be a vector of 0’s. Our goal is to measure the
(global) average treatment effect (ATE):
$\operatorname{\mathbb{E}}[\mu(\textbf{1})-\mu(\textbf{0})]$.

Because the number of possible treatment assignments is exponential in $n$
(i.e., $2^{n}$), making causal inferences on the ATE is impractical unless
further assumption is imposed on the structure of the outcome function
$Y_{i}$. Throughout this paper, we assume that $Y_{i}(\BFz)$ depends only on
the treatments of units from a subset $\mathcal{N}_{i}\subset V$, which is
referred to as the _neighborhood set_ of unit $i$. More formally, for any two
assignment vector $\BFz$ and $\BFz^{\prime}$ such that $z_{i}=z^{\prime}_{i}$
and $z_{j}=z^{\prime}_{j}$ for all $j\in\mathcal{N}_{i}$, we have
$Y_{i}(\BFz)=Y_{i}(\BFz^{\prime})$. We assume that the neighborhood set is
known and correctly specified for each unit. By connecting units with their
neighbors, we get a directed graph $G(V,E)$ where $V$ is the set of all units
and $E$ is the set of all edges. Without loss of generality, we assume the
graph is connected; otherwise, the problem can be decomposed into separate
subgraphs.

We focus on a linear exposure model where the magnitude of interference on
unit $i$ from unit $j$ is measured by a constant factor $v_{ij}$,
$\forall(i,j)\in E$. Without loss of generality, we assume the weights are
normalized such that $\sum_{j\in\mathcal{N}_{i}}|v_{ij}|\leq 1,\;\forall i\in
V$ and $\sum_{i}\sum_{j\in\mathcal{N}_{i}}v_{ij}\geq 0$. The outcome function
$Y_{i}(\BFz)$ of unit $i$ is given by

$Y_{i}(\BFz)=\alpha_{i}+z_{i}\beta_{i}+\gamma\sum_{j\in\mathcal{N}_{i}}v_{ij}z_{j},\quad\forall
i\in V.$ (1)

In Eq (1), $\alpha_{i}\in\mathbb{R}$ is the potential outcome of unit $i$
without any treatment, $\beta_{i}\in\mathbb{R}$ is the direct treatment effect
on unit $i$, $\gamma v_{ij}z_{j}$ is the spillover effect from an adjacent
unit $j\in\mathcal{N}_{i}$. Because $\sum_{j\in\mathcal{N}_{i}}|v_{ij}|\leq
1$, the value $|\gamma|$ can be interpreted as the maximum absolute
interference effect from neighbors. We treat the coefficients $\alpha_{i}$,
$\beta_{i}$, and $\gamma$ as fixed but unknown so that the only randomness in
the observation model is due to the choice of treatment assignment $\BFz$. In
this section, we assume the weights $v_{ij}$’s are known. For example, Saveski
et al., (2017) considers a social network experiment where each unit
represents a user and $v_{ij}$ is the same for all $(i,j)\in E$ (up to a
normalization factor). As another example, for an experiment on a
transportation network, we may set $v_{ij}$ as the traffic flow from node $j$
to node $i$. The setting with unknown $v_{ij}$’s will be studied in Section 4.

The linear exposure mapping model in Eq (1) can be viewed as a first-order
approximation of more general network interference patterns. Similar linear
exposure assumptions are common in the causal inference literature (Toulis and
Kao,, 2013; Brennan et al.,, 2022; Harshaw et al.,, 2023) and our model
generalizes some previous studies by allowing weighted inference from
neighboring units. Throughout the paper, we assume the outcomes are bounded,
that is, there exist constants $Y_{L}$ and $Y_{M}$ such that $Y_{L}\leq
Y_{i}(\BFz)\leq Y_{M}$ for all $i\in V$ and all $\BFz\in\\{0,1\\}^{n}$. We
also assume $Y_{L}>0$ without loss of generality (e.g., by shifting the
outcome of all units by a fixed constant).

One common approach used in the literature to reduce the bias of ATE under
network interference is _cluster-based_ randomization, where the network is
partitioned into disjoint clusters, and units within the same cluster are
assigned the same treatment. Specifically, let $m\in\mathbb{Z}_{+}$ and let
the clusters $\\{C_{1},C_{2},...,C_{m}\\}$ be a partition of the vertex set
$V$. We define $c(i)$ as a function that maps the index of unit $i$ to its
associated cluster, i.e., $c(i)=t$ if and only if $i\in C_{t}$. The standard
estimator for ATE in cluster-based design is the _Horvitz-Thompson_ estimator,
which is defined below.

######  Definition 1 (Cluster-based Randomization).

Let $p\in(0,1)$ be the treatment probability. Under cluster-based randomized
design, each unit’s treatment is a Bernoulli random variable, i.e. $z_{i}\sim$
Bernoulli($p$) for all $i\in V$. Moreover, for $i\neq j$, the correlation
coefficient of $z_{i}$ and $z_{j}$ is
corr$(z_{i},z_{j})=\boldsymbol{1}\\{c(i)=c(j)\\}$. The Horvitz-Thompson (HT)
estimator for the ATE in cluster-based design (denoted by the subscript _cb_)
is

$\tau_{cb}=\frac{1}{n}\sum_{i=1}^{n}\left(\frac{z_{i}}{p}-\frac{1-z_{i}}{1-p}\right)Y_{i}(\BFz).$
(2)

We note that there exist other definitions of HT estimators in cluster-based
randomization design (e.g. Ugander et al.,, 2013) to make it unbiased, but the
HT estimator defined in Eq (2) is commonly used one in practice.

It is easily verified that for the linear exposure mapping model given by Eq
(1), the true ATE is equal to
$\bar{\beta}+{\gamma}\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}/n$, where
$\bar{\beta}=\sum_{i=1}^{n}\beta_{i}/n$. However, the expectation of the HT
estimator is not always equal to the ATE.

######  Lemma 1.

Let $\tau_{cb}$ be the HT estimator of cluster-based design in Definition 1.
Its expectation is given by

$\displaystyle\operatorname{\mathbb{E}}[\tau_{cb}]=\bar{\beta}+\frac{\gamma}{n}\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}\boldsymbol{1}\\{c(i)=c(j)\\}.$
(3)

###### Proof.

Let $t_{i}={z_{i}}/{p}-{(1-z_{i})}/{(1-p)}$. Since
$\operatorname{\mathbb{E}}[t_{i}z_{j}]=\boldsymbol{1}\\{c(i)=c(j)\\}$, the
result follows by substituting Eq (1) into Eq (2) and taking the expectation.
∎

By Lemma 1, the HT estimator $\tau_{cb}$ of a cluster-based design is unbiased
if and only if all clusters are independent, i.e., there does not exist
$i,j\in V$ such that $j\in\mathcal{N}_{i}$ but $c(i)\neq c(j)$. Nevertheless,
in most randomized experiments, the underlying network cannot be perfectly
partitioned into independent clusters.

As a motivating example, let us consider a $d$-regular network (i.e.
$|\mathcal{N}_{i}|=d$ for every $i\in\mathcal{N}$) with $v_{ij}=1/d$ for all
$(i,j)\in E$. The ATE for this network is $\bar{\beta}+\gamma$. However,
assuming between-cluster connections account for half of all the connections,
the HT estimator gives
$\operatorname{\mathbb{E}}[\tau_{cb}]=\bar{\beta}+\gamma/2$, which may cause
significant bias in the ATE estimation. To reduce the bias, we may
additionally use a _Bernoulli randomization design_ , where each individual
unit receives an i.i.d. treatment with probability $p$. The Bernoulli design
can be viewed as a special case of cluster-based design where each cluster
contains a single unit, i.e. $m=n$ and $|C_{1}|=|C_{2}|=...=|C_{n}|=1$. By
Lemma 1, the mean of the HT estimator for the Bernoulli design is
$\tau_{b}:=\bar{\beta}$. If we were able to get estimations from _both_
$\tau_{cb}$ and $\tau_{b}$, we can use a new estimator
$\tau^{\prime}:2\tau_{cb}-\tau_{b}$, which is an unbiased estimator for the
ATE with $\operatorname{\mathbb{E}}[\tau]=\bar{\beta}+\gamma$. However, this
estimation approach is infeasible, as each unit in the network can only
receive one treatment at a time, so we cannot obtain both $\tau_{cb}$ and
$\tau_{b}$.

The challenge above motivates us to consider a mixture of two randomization
designs, which we call the _mixed design_. In the mixed design, we first draw
random numbers to determine whether a unit will receive treatment according to
a cluster-based design or a Bernoulli design, and then assign treatments
according to each design separately. The key idea of the mixed design is to
simultaneously obtain estimations from both the cluster-based and Bernoulli
designs. The formal definition of the mixed design will be presented in the
next subsection.

Finally, we provide lower and upper bounds of the HT estimator $\tau_{cb}$ for
the cluster-based design, which will be used in subsequent sections. The proof
is given in Appendix A.

######  Proposition 2.

The variance of the HT estimator under cluster-based design is bounded by

$\displaystyle\left(\frac{Y_{L}^{2}}{p(1-p)}-\frac{1}{2}Y_{M}^{2}\right)\eta+\gamma^{2}\delta\leq\operatorname{\mathrm{Var}}(\tau_{cb})\leq\left((\frac{1}{p(1-p)}+2)Y_{M}^{2}-Y_{M}Y_{L}\right)\eta+\gamma^{2}\delta,$
(4)

where

$\displaystyle\eta:=\frac{1}{n^{2}}\sum_{k=1}^{m}|C_{k}|^{2},\quad\delta:=\frac{1}{n^{2}}\sum_{1\leq
k\neq l\leq m}\left(\sum_{i\in C_{k}}\sum_{i^{\prime}\in\mathcal{N}_{i}\cap
C_{l}}v_{ii^{\prime}}\right)\left(\sum_{j\in
C_{l}}\sum_{j^{\prime}\in\mathcal{N}_{j}\cap C_{k}}v_{jj^{\prime}}\right).$

###  3.3 Mixed Randomization Design

Our proposed mixed design assigns treatment using a two-stage randomization.
In the first stage, all nodes in the network are randomly partitioned into two
subsets. In the second stage, one subset receives random treatments according
to a cluster-based design, and the other subset receives random treatments
according to a Bernoulli design. (Random numbers used in the two stages are
independent.) We note that similar mixed designs are proposed by Saveski et
al., (2017); Pouget-Abadie et al., 2019b . However, their papers focus on
hypothesis testing for the existence of network inference, whereas our work
aims to estimate the ATE.

The complete steps of creating a mixed randomization design are described as
follows:

  1. 1.

Let $\\{C_{1},C_{2},\ldots,C_{m}\\}$ be a set of clusters that forms a
partition of the network $G(V,E)$. Let $\BFW\in\\{0,1\\}^{m}$ be a random
vector indicating the assignment of each cluster to either cluster-based or
Bernoulli design. That is, $W_{j}=1$ implies that the cluster $C_{j}$ uses
cluster-based design, and $W_{j}=0$ implies the cluster $C_{j}$ uses Bernoulli
design. We require $W_{j}$ to be i.i.d. Bernoulli random variables with mean
$1/2$ ($\forall j\in[m]$). Let $\tilde{\BFw}\in\\{0,1\\}^{n}$ be the
corresponding unit-level assignment vector, namely, $\tilde{w}_{i}=W_{c(i)}$
for all $i\in V$.

  2. 2.

For cluster $C_{j}$ ($j=1,\ldots,m$): if $W_{j}=1$, assign all the units in
this cluster treatment $z_{i}=1$ with probability $p$, and assign all the
units treatment $z_{i}=0$ with probability $1-p$. If $W_{j}=0$, assign
treatment to the units in cluster $C_{j}$ by i.i.d. Bernoulli variables with
mean $p$.

Note that the above procedure does not specify how the clusters
$\\{C_{1},C_{2},\ldots,C_{m}\\}$ should be chosen. We will study how to design
clustering algorithms to optimize the efficiency of the mixed randomization
design in the next subsection.

Define the following estimators $\tau_{c}$ for those units using cluster-based
design and $\tau_{b}$ for those units using Bernoulli design:

$\displaystyle\tau_{c}$
$\displaystyle=\frac{2}{n}\sum_{i=1}^{n}\tilde{w}_{i}(\frac{z_{i}}{p}-\frac{1-z_{i}}{1-p})Y_{i}(\BFz),$
(5a) $\displaystyle\ \tau_{b}$
$\displaystyle=\frac{2}{n}\sum_{i=1}^{n}(1-\tilde{w}_{i})(\frac{z_{i}}{p}-\frac{1-z_{i}}{1-p})Y_{i}(\BFz).$
(5b)

It is easily verified that
$\operatorname{\mathbb{E}}[\tau_{c}]=\bar{\beta}+{\gamma}\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}\boldsymbol{1}\\{c(i)=c(j)\\}/n$
and $\operatorname{\mathbb{E}}[\tau_{b}]=\bar{\beta}$ (the proof is similar to
Lemma 1 and is thus omitted). Using this fact, we define the estimator $\tau$
for the mixed randomization design.

######  Definition 2 (ATE Estimator in Mixed Design).

Let

$\tau:=\rho\tau_{c}-(\rho-1)\tau_{b},$

where $\tau_{c}$ and $\tau_{b}$ are defined in (5a) and (5b), respectively,
and

$\displaystyle\rho:=\frac{\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}}{\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}\boldsymbol{1}\\{c(i)=c(j)\\}}.$
(6)

The following lemma shows that $\tau$ is indeed an unbiased estimator for the
ATE.

######  Lemma 3.

If $\rho$ is given by Eq (6), we have

$\displaystyle\operatorname{\mathbb{E}}[\tau]=\operatorname{\mathbb{E}}[\mu(\BFone)-\mu(\BFzero)]=\bar{\beta}+\frac{\gamma}{n}\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}.$

###### Proof.

The equality follows immediately from Definition 2. ∎

Note that computing the coefficient $\rho$ by Eq (6) requires full knowledge
of the weight coefficients $v_{ij}$ on all edges $(i,j)\in E$. Analogous to
Proposition 2, we have the following lower and upper bounds on the variance of
$\tau$.

######  Proposition 4.

Suppose there exist $Y_{L}>0$ and $Y_{M}>0$ such that $Y_{L}\leq
Y_{i}(\BFz)\leq Y_{M}$ for all $i\in V$ and all $\BFz\in\\{0,1\\}^{n}$. Then,
we have

$\displaystyle\operatorname{\mathrm{Var}}(\tau)\leq$
$\displaystyle\left((\frac{2}{p(1-p)}+1)Y_{M}^{2}-Y_{M}Y_{L}-Y_{L}^{2}\right)\rho^{2}\eta+\gamma^{2}\rho^{2}\delta+O\left(\frac{\rho^{2}}{np(1-p)}\right),$
(7) $\displaystyle\operatorname{\mathrm{Var}}(\tau)\geq$
$\displaystyle\left(\frac{2}{p(1-p)}Y_{L}^{2}-2Y_{M}^{2}+Y_{M}Y_{L}\right)\rho^{2}\eta+\gamma^{2}\rho^{2}\delta+O\left(\frac{\rho^{2}}{np(1-p)}\right),$
(8)

where

$\displaystyle\eta:=\frac{1}{n^{2}}\sum_{k=1}^{m}|C_{k}|^{2},\quad\delta:=\frac{1}{n^{2}}\sum_{1\leq
k\neq l\leq m}\left(\sum_{i\in C_{k}}\sum_{i^{\prime}\in\mathcal{N}_{i}\cap
C_{l}}v_{ii^{\prime}}\right)\left(\sum_{j\in
C_{l}}\sum_{j^{\prime}\in\mathcal{N}_{j}\cap C_{k}}v_{jj^{\prime}}\right).$

The proof of Proposition 4 can be found in Appendix A. Note that the variance
bounds in Proposition 4 for the estimator $\tau$ under mixed design have a
similar form as the variance bound under cluster-based design (see Prop. 2).
In particular, the bounds depend on the number and sizes of the clusters
($\eta$), and the weights of between-cluster connections ($\delta$).
Proposition 4 also provides a bound on the maximum size of each cluster if
$\tau$ is consistent. When $v_{ij}\geq 0$ for all $(i,j)\in E$, we have
$|\rho|\geq 1$. If $\operatorname{\mathrm{Var}}(\tau)\to 0$ as the population
size $n$ goes to infinity, we must have $\eta\rightarrow 0$ by the first term
of the bound, which implies $\max_{k}|C_{k}|=o(n)$. Using Proposition 4, we
propose an efficient clustering algorithm to upper bound the variance of
$\tau$ in Section 3.4. We then provide a lower bound on the variance of $\tau$
for any clustering algorithm in Section 3.5.

###  3.4 Upper Bound on the Estimator Variance

Recall that Eq (7) in Proposition 4 provides an expression for an upper bound
of the variance of the mixed design estimator $\tau$. However, finding an
exact algorithm to minimize the expression in Eq (7) is computationally
challenging, as it requires us to optimize the factor $\rho^{2}\eta$ in the
first term. Andreev and Räcke, (2004) showed that no polynomial time
approximation algorithm can guarantee a finite approximation ratio in graph
partitioning (in our case, a finite bound on $\rho$) unless
$\mathcal{P}=\mathcal{NP}$. Therefore, instead of searching for an optimal
algorithm to minimize the bound in Eq (7), we resort to finding an efficient
clustering algorithm that leads to an asymptotic bound on
$\operatorname{\mathrm{Var}}(\tau)$.

We first consider arbitrary network structures and propose a clustering
algorithm based on a greedy heuristic (Algorithm 1). The key idea is to use
maximum weight matching to generate clusters with sizes of 1 and 2, and then
merge these small clusters together to create the desired clustering. The
merging step follows a greedy rule, where we iteratively look for two clusters
to merge to minimize an approximation of the variance upper bound:

$\displaystyle
A(\\{C_{1},...,C_{m}\\})=\left((\frac{2}{p(1-p)}+1)Y_{M}^{2}-Y_{M}Y_{L}-Y_{L}^{2}\right)\rho^{2}\eta+\left(\frac{Y_{M}-Y_{L}}{a}\right)^{2}\rho^{2}|\delta|,$
(9)

where $\eta$, $\delta$, $Y_{L}$ and $Y_{M}$ are defined in Proposition 4 and
$a=\max_{i}(\sum_{j\in\mathcal{N}_{i}}\max\\{v_{ij},0\\})$. The main
differences between the approximate variance upper bound $A(\cdot)$ and the
variance upper bound in Proposition 4 are: (1) we replace the unknown
parameter $\gamma^{2}$ by a known value $(Y_{M}-Y_{L})^{2}/a^{2}$ and take the
absolute value of $\delta$; (2) the $O(\cdot)$ term is omitted. After merging
two clusters $C_{k},C_{l}\in\BFC$, we obtain a new cluster set
$\BFC^{\prime}=\BFC/\\{C_{k},C_{l}\\}\cup\\{C_{k}\cup C_{l}\\}$, and the
corresponding approximate variance upper bound becomes $A(\BFC^{\prime})$. We
use $\Delta A_{\BFC}(C_{k},C_{l})$ to denote the value of
$A(\BFC^{\prime})-A(\BFC)$:

$\displaystyle\Delta
A_{\BFC}(C_{k},C_{l})=A(\BFC/\\{C_{k},C_{l}\\}\cup\\{C_{k}\cup
C_{l}\\})-A(\BFC).$ (10)

Within each iteration, the algorithm looks for a pair of clusters
$(C_{k},C_{l})$ minimizing the value of $\Delta
A_{\BFC}(C_{k_{1}},C_{k_{2}})$. The stopping criterion is to check whether
$\Delta A_{\BFC}(C_{k},C_{l})$ is positive, which tells whether the
approximate variance upper bound can be further improved by merging clusters.

Note that the computational complexity of Algorithm 1 is $O(n^{3})$. Firstly,
finding a maximum matching in a general graph with $n$ vertices is $O(n^{3})$
(Galil, 1986), thus line 1 to 4 in Algorithm 1 takes $O(n^{3})$ time.
Secondly, the while loop from Line 5 to Line 7 can iterate at most $n$ times
since there are $n$ vertices. Finally, Line 6 can be implemented in $O(|E|)$
time if we enumerate the edge set $E$ to find all adjacent clusters and
calculate $\sum_{i\in C_{k}}\sum_{i^{\prime}\in\mathcal{N}_{i}\cap
C_{l}}v_{ii^{\prime}}$ for every adjacent $(C_{l},C_{l})$. Thus, Line 5 to
Line 7 in Algorithm 1 takes $O(n|E|)$ time, in which $E$ is the edge set and
thus $|E|\leq n(n-1)$.

Throughout the paper, we use $d:=\max_{i\in V}|\mathcal{N}_{i}|$ to denote the
maximum degree of the network. The variance of $\tau$ using the output of
Algorithm 1 is bounded as follows.

Input: A graph $G(V,E)$

Output: A clustering $\\{C_{1},C_{2},\ldots\\}$ of the graph

1

2Find a maximum weight matching
$M=\\{(i_{1},j_{1}),(i_{2},j_{2}),...,(i_{m},j_{m})\\}$ of the graph $G$ using
the weights $v_{ij}$ in Eq (1)

3 Initialize the clusters: $\BFC\leftarrow M$

4 for  _any $k\in[n]$ such that $\nexists j\in\mathcal{N}_{k}$ with $(k,j)\in
M$ or $(j,k)\in M$_ do

5 $\BFC\leftarrow\BFC\cup\\{\\{k\\}\\}$

6

7 while
_$\operatornamewithlimits{min}\limits_{C_{k_{1}},C_{k_{2}}\in\BFC,k_{1}\neq
k_{2}}\Delta A_{\BFC}(C_{k},C_{l}) <0$ _ do

$(C_{k},C_{l})\leftarrow\operatornamewithlimits{argmin}\limits_{C_{k_{1}},C_{k_{2}}\in\BFC,k_{1}\neq
k_{2}}\Delta A_{\BFC}(C_{k_{1}},C_{k_{2}})$

/* finding two clusters to merge */

8 $\BFC\leftarrow\BFC/\\{C_{k},C_{l}\\}\cup\\{C_{k}\cup C_{l}\\}$

9

10return $\BFC$

Algorithm 1 Greedy Clustering

######  Theorem 5.

The variance of the estimator $\tau$ in mixed randomization design using
clustering from Algorithm 1 is upper bounded by
$O\left(\frac{d^{2}}{np(1-p)}\right)$.

The complete proof is included in Appendix A. Theorem 5 guarantees an
$O(d^{2})$ upper bound on the variance of $\tau$ for general networks. For
networks with $d=o(\sqrt{n})$, the estimator $\tau$ is consistent, as the
variance converges to 0 as the network size $n\to\infty$.

The dependence on $d$ can be further improved by making additional assumptions
on the sparsity of the network. Specifically, we consider a family of graphs
satisfying the _restricted-growth_ condition (Ugander et al.,, 2013).

######  Definition 3 (restricted-growth graph).

Let $B_{r}(v)$ be the set of vertices within $r$ hops of a vertex $v$ (i.e.,
all vertices connected to $v$ by a path with length no more than $r$). A graph
$G=(V,E)$ is a restricted-growth graph if there exists a constant $\kappa>0$,
such that for all vertices $v\in V$ and all $r\in\mathbb{Z}_{+}$, it holds
that $|B_{r+1}(v)|\leq\kappa|B_{r}(v)|$.

By definition, we have $\kappa\leq d$. Empirical evidence shows that the
growth constant $\kappa$ for most networks in practice can be significantly
less than $d$. For example, the empirical analysis by Ugander and Yin, (2023)
on Facebook social networks shows that $\kappa$ is typically on the order of
$25\%-50\%$ of $d$.

Assuming the restricted-growth condition, when the spillover effects from
neighbors are either always positive or always negative, we propose another
clustering algorithm (Algorithm 2). The algorithm has two steps. In the first
step, it finds a vertex $v_{0}$ whose 2-hop does not overlap with any existing
cluster, and adds the 2-hop of $v_{0}$ as a new cluster. Note that by
Definition 3, the size of each 2-hop is no more than $\kappa(d+1)$. In the
second step, it forms clusters among the remaining vertices to ensure that the
maximum cluster size does not exceed $\kappa(d+1)$. We show that Algorithm 2
gives a tighter upper bound on the estimation variance
$\operatorname{\mathrm{Var}}(\tau)$, which is linear in the maximum degree $d$
of the network.

Input: A graph $G(V,E)$

Output: A clustering $\\{C_{1},C_{2},...\\}$

1

2Initialize set $U=V$

3 Initialize the clustering: $\BFC=\\{\\}$

while  _$\exists\;v_{0}\in U$ such that $B_{2}(v_{0})\subset U$ _

__ /* adding 2-hops to the clusters */

4 do

5 Add a new cluster $\BFC\leftarrow\BFC\cup\\{B_{2}(v_{0})\\}$

6 Update $U\leftarrow U/B_{2}(v_{0})$

7

while  _$|U| >\kappa(d+1)$ _

__ /* keeping cluster size $\leq\kappa(d+1)$ */

8 do

9 Select an arbitrary subset $S\subset U$ with $\kappa(d+1)$ vertices

10 Add a new cluster $\BFC\leftarrow\BFC\cup\\{S\\}$

11 Update $U\leftarrow U/S$

12

$\BFC\leftarrow\BFC\cup\\{U\\}$

Algorithm 2 2-Hop Clustering

######  Theorem 6.

If $v_{ij}\geq 0$ for all $(i,j)\in E$ and there exists a positive constant
$\epsilon>0$ such that $\sum_{j\in\mathcal{N}_{i}}v_{ij}\geq\epsilon$ for all
$i\in V$, the variance of estimator $\tau$ using clustering from Algorithm 2
is upper bounded by $O\left(\frac{\kappa^{7}d}{np(1-p)}\right)$ .

The bounds in Theorem 5 and 6 compare favorably to the state-of-the-art
variance bounds for ATE estimators under cluster-based randomization design.
Ugander and Yin, (2023) achieved an $O(d^{2}\kappa^{4}n^{-1}p^{-1})$ variance
bound for restricted-growth graphs, which implies an $O(d^{6}n^{-1}p^{-1})$
bound for general graphs (since $\kappa\leq d$). Our bounds for mixed
randomization design have better dependence on the maximum degree $d$ for both
general networks and restricted-growth graphs.

###  3.5 Lower Bound on the Estimator Variance

To put the upper bounds in Section 3.4 into perspective, we present a lower
bound of the variance of $\tau$ for any clustering algorithm. To establish the
lower bound, we consider a specific family of networks and measure the
dependence on the maximum degree $d$ and the growth constant $\kappa$ by
applying the lower bound in Proposition 4.

We define a family of cycle networks whose structure is controlled by two
parameters, $d$ and $\kappa$.

######  Definition 4 (Cycle network).

We call a network $(d,\kappa)$-cycle with $1\leq\kappa\leq d$ if each unit
$i\in[n]$ is connected to the units indexed by $\\{(i\pm 1)\mod n,(i\pm 2)\mod
n,...,(i\pm(\kappa-1))\mod n\\}$ and $\\{(i\pm\kappa)\mod n,(i\pm 2\kappa)\mod
n,...,(i\pm d\kappa)\mod n\\}$.

It is easily verified that a cycle network in Definition 4 has a maximum
degree of $2(d+\kappa)\leq 4d$ and a maximum growth factor of $2\kappa$ (see
Definition 3). Therefore, the parameter $d$ controls the magnitude of the
maximum degree and the parameter $\kappa$ controls the growth rate. The
following theorem establishes a lower bound on
$\operatorname{\mathrm{Var}}(\tau)$.

######  Theorem 7.

Consider a $(d,\kappa)$-cycle network whose treatment effect is given by

$\displaystyle
Y_{i}(\BFz)=\alpha_{i}+z_{i}\beta_{i}+\frac{\gamma}{|\mathcal{N}_{i}|}\sum_{j\in\mathcal{N}_{i}}z_{j},\quad\forall
i\in V.$

For any clustering algorithm, the estimator $\tau$ in mixed design (Definition
2) satisfies

$\operatorname{\mathrm{Var}}(\tau)=\Omega\left(\frac{\min\\{\kappa
d,d^{2}/\kappa\\}}{np(1-p)}\right).$

The proof is given in Appendix A. Because $1\leq\kappa\leq d$, the above
result implies that the variance of the estimator $\tau$ for restricted-growth
networks in terms of $d$ is at least $\Omega(d)$, which matches the upper
bound in Theorem 6. For general networks, by setting $\kappa=\sqrt{d}$, the
above theorem implies a $\Omega({d^{1.5}}/(np(1-p)))$ lower bound for networks
with a maximum degree $d$. This lower bound differs from the
$O({d^{2}}/(np(1-p)))$ upper bound in Theorem 5 by only a factor of
$O(\sqrt{d})$. Notice that the lower bound in Theorem 7 holds even when we use
_randomized_ clusters, which will be studied in the next section.

##  4 Weight-Invariant Mixed Design for Unknown Edge Weights

The mixed experiment design proposed in Section 3 requires full knowledge of
the weight coefficients $v_{ij}$ for all edges $(i,j)\in E$. However, in many
applications, the weights are unknown a priori. In this section, we extend the
mixed experiment design by constructing a clustering algorithm with a
corresponding ATE estimator that is agnostic to the weight coefficients.
Recall the mixed randomization design is based on a clustering of the network.
In the previous section, we assume the clusters are fixed. The key to
extending the design to unknown weights is to use _randomized_ clusters. Our
approach is motivated by Ugander and Yin, (2023) who showed that randomized
clustering algorithms can provide better variance upper bounds for cluster-
based design.

Consider a randomized clustering algorithm that produces $k$ different
clusterings $\BFC_{1},\BFC_{2},\cdots,\BFC_{k}$ for a graph $G(V,E)$. Each
clustering $\BFC_{l}$ ($\forall l\in[k]$) is a set of clusters that forms a
partition of the network, i.e.
$\BFC_{l}=\\{C_{1}^{l},C_{2}^{l},...,C_{m_{l}}^{l}\\}$. Suppose $\BFC_{l}$ is
generated by the clustering algorithm with probability $p(l)$. (We require
$\sum_{l=1}^{k}p(l)=1$). Let $c_{l}(i):V\to[m_{l}]$ be the function that maps
each unit $i\in V$ to the cluster index in the $l^{\text{th}}$ clustering.

To simplify the notation for the analysis below, we rewrite the interference
model in Eq (1) as

$\displaystyle
Y_{i}(\BFz)=\alpha_{i}+z_{i}\beta_{i}+\gamma_{i}\sum_{j\in\mathcal{N}_{i}}w_{ij}z_{j},\quad\forall
i\in V.$

where $\gamma_{i}:=\gamma\sum_{j\in\mathcal{N}_{i}}v_{ij}$ and
$w_{ij}:=v_{ij}/(\sum_{j\in\mathcal{N}_{i}}v_{ij})$. Then for any parameter
$\rho$ in mixed design (see Definition 2), the expectation of the estimator
$\tau$ is

$\displaystyle\operatorname{\mathbb{E}}[\tau]=\bar{\beta}+\frac{\rho}{n}\sum_{i=1}^{n}\gamma_{i}\sum_{j\in\mathcal{N}_{i}}w_{ij}\sum_{l=1}^{k}p(k)\boldsymbol{1}\\{c_{l}(i)=c_{l}(j)\\}.$
(11)

We say the estimator $\tau$ is _weight-invariant_ , if the value of
$\operatorname{\mathbb{E}}[\tau]$ and $\rho$ are independent of the weights
$w_{ij}$. Below is a formal definition.

######  Definition 5 (weight-invariant).

The mixed design estimator $\tau$ in Definition 2 is weight-invariant if
$\rho$ does not depend on $w_{ij}$ and the following condition holds. For any
unit $i\in V$ and any two sets of weights
$\\{w_{ij}\in\mathbb{R}|\sum_{j\in\mathcal{N}_{i}}w_{ij}=1,\;\forall i\\}$ and
$\\{w^{\prime}_{ij}\in\mathbb{R}|\sum_{j\in\mathcal{N}_{i}}w^{\prime}_{ij}=1,\;\forall
i\\}$, it holds that

$\displaystyle\sum_{j\in\mathcal{N}_{i}}w_{ij}\sum_{l=1}^{k}p(l)\boldsymbol{1}\\{c_{l}(i)=c_{l}(j)\\}=\sum_{j\in\mathcal{N}_{i}}w^{\prime}_{ij}\sum_{l=1}^{k}p(l)\boldsymbol{1}\\{c_{l}(i)=c_{l}(j)\\}.$

The following lemma provides a sufficient and necessary condition under which
the estimator $\tau$ is weight-invariant and unbiased.

######  Lemma 8.

The estimator $\tau$ is weight-invariant and unbiased if and only if

$\displaystyle\rho=\left(\sum_{l=1}^{k}p(l)\boldsymbol{1}\\{c_{l}(i)=c_{l}(j)\\}\right)^{-1}=\operatorname{\mathbb{E}}[\boldsymbol{1}\\{c(i)=c(j)\\}]^{-1}\quad\forall(i,j)\in
E.$ (12)

Lemma 8 follows immediately from Definition 5, so we omit the proof. For a
weight-invariant estimator $\tau$, the parameter $\rho$ does not depend on the
weight coefficients $w_{ij}$, and only on the clustering algorithm itself.

The main challenge for creating a weight-invariant design is to find a
clustering algorithm that satisfies Eq (12). Denote the $|E|$-by-$|E|$ edge
incidence matrix of the graph $G(V,E)$ by $M$, where $M_{ij}\in\\{0,1\\}$ and
1 means the $i^{\text{th}}$ edge and the $j^{\text{th}}$ edge share a common
vertex. We propose a weight-invariant clustering method in Algorithm 3.

Input: A graph $G(V,E)$

1 Initialize the clustering $\BFC\leftarrow\\{\\}$

2 Initialize the edge incidence matrix $M\in\\{0,1\\}_{|E|\times|E|}$

3 Find the maximum eigenvalue $\lambda^{*}$ of $M$ and a corresponding
eigenvector $\boldsymbol{\omega}$

4 for  _$(i,j)\in E$_ do

$X_{(i,j)}\leftarrow Beta(\omega_{(i,j)},1)$

/* sample from Beta distribution */

5

6for  _$(i,j)\in E$_ do

7 if  _$X_{(i,j)}=\max\\{X_{(u,v)}|(u,v)\in E,u=i\textbf{ or }u=j\\}$_ then

8 $\BFC\leftarrow\BFC\cup\\{\\{i,j\\}\\}$

9

10

11for  _$v\in V$_ do

12 if  _$v\notin C_{k}\;\forall k\in[|\BFC|]$_ then

13 $\BFC\leftarrow\BFC\cup\\{\\{v\\}\\}$

14

15

Output: Clustering $\BFC$

Algorithm 3 Weight-invariant Clustering

Note that Algorithm 3 generates random clusters of maximum size $2$. By lines
7-8, the output of the algorithm is a valid clustering, because each vertex
occurs in exactly one cluster in $\BFC$. The following proposition shows the
efficacy of Algorithm 3:

######  Proposition 9.

Using the clustering output generated by Algorithm 3, the mixed design ATE
estimator $\tau$ is weight-invariant and unbiased with $\rho=\lambda^{*}$.

###### Proof.

Suppose $X_{1}$, $X_{2}$, $...$, $X_{k}$ are independent Beta distributed
random variables with parameter $(w_{1},1)$, $(w_{2},1)$, $...$, $(w_{k},1)$.
Then

$\displaystyle
P(X_{1}=\max\\{X_{2},...,X_{k}\\})=\frac{w_{1}}{\sum_{j=1}^{k}w_{j}}.$

For any edge $(i,j)\in E$, let $I_{ij}=\\{(u,v)\in E|u=i\textbf{ or }u=j\\}$
denote the set of edges incident to $(i,j)$. Since $\boldsymbol{\omega}$ is a
eigenvector of the edge incidence matrix $M$ associated with the largest
eigenvalue $\lambda^{*}$, by the Perron–Frobenius theorem, we have
$\lambda^{*}\geq 0$ and the probability that $i$ and $j$ belong to the same
cluster is

$\displaystyle\frac{\omega_{(i,j)}}{\sum_{(u,v)\in E\cap
I_{ij}}\omega_{(u,v)}}=\frac{1}{\lambda^{*}}.$

By Lemma 8, we have

$\rho=\frac{1}{\operatorname{\mathbb{E}}[\boldsymbol{1}\\{c(i)=c(j)\\}]}=\frac{\sum_{(u,v)\in
E\cap I_{ij}}\omega_{(u,v)}}{\omega_{(i,j)}}=\lambda^{*}.$

Because $\lambda^{*}$ is determined by the edge incidence matrix $M$, the
parameter $\rho$ does not dependent on the weights $w_{ij}$ of the network. As
a result, the estimator $\tau$ using Algorithm 3 is weight-invariant and
unbiased. ∎

Finally, we give an upper bound on the variance of $\tau$ under Algorithm 3.
This upper bound differs from the bound in Theorem 5 by a factor of $O(d)$,
since Algorithm 3 does not require the knowledge of the weight coefficients
$w_{ij}$ (or $v_{ij}$), $\forall(i,j)\in E$.

######  Theorem 10.

The variance of $\tau$ using Algorithm 3 is bounded by
$O\left(\frac{d^{3}}{np(1-p)}\right)$.

###### Proof.

Let $x_{ij}(\BFC_{k}):=\boldsymbol{1}\\{c_{k}(i)=c_{k}(j)\\}$, then

$\displaystyle\operatorname{\mathrm{Var}}(\operatorname{\mathbb{E}}[\tau|\BFC])=$
$\displaystyle\operatorname{\mathrm{Var}}(\bar{\beta}+\rho\gamma/n\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}x_{ij}(\BFC))$
$\displaystyle=$
$\displaystyle\frac{\rho^{2}\gamma^{2}}{n^{2}}\operatorname{\mathrm{Var}}(\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}x_{ij}(\BFC)).$

To simplify the notation, we do not distinguish $(i,j)$ and $(j,i)$ in the
following due to the symmetry of $x_{ij}(\cdot)$ and $x_{ji}(\cdot)$. Let
$E^{\prime}$ be the undirected version of the edge set $E$, i.e. if $(i,j)\in
E$ then there exists $e\in E^{\prime}$ such that $e:=(i,j)$ and $e:=(j,i)$.
The weight of edge $e\in E^{\prime}$ is defined to be
$v_{e}=\boldsymbol{1}\\{(i,j)\in E\\}v_{ij}+\boldsymbol{1}\\{(j,i)\in
E\\}v_{ji}$ if $e:=(i,j):=(j,i)$. Also,
$x_{e}(\BFC_{k})=\boldsymbol{1}\\{c_{k}(i)=c_{k}(j)\\}$ if $e:=(i,j):=(j,i)$.
Then we can rewrite

$\displaystyle\operatorname{\mathrm{Var}}(\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}x_{ij}(\BFC))=\operatorname{\mathrm{Var}}\left(\sum_{e\in
E^{\prime}}v_{e}x_{e}(\BFC)\right).$

For every edge $e\in E^{\prime}$, let $I_{e}$ be the set of edges incident to
$e$. Moreover, let $A_{1}(e)=I_{e}$, $A_{2}(e)=\\{f\in E^{\prime}:f\notin
I_{e}\cup\\{e\\}\text{ and }I_{f}\cap I_{e}\neq\emptyset\\}$ and
$A_{3}(e)=E^{\prime}/(A_{1}(e)\cup A_{2}(e))$. Note that if $f\in A_{1}(e)$,
then $x_{e}(\BFC)x_{f}(\BFC)=0$. If $f\in A_{3}(e)$, $x_{e}(\BFC)$ and
$x_{f}(\BFC)$ are independent. Then

$\displaystyle\operatorname{\mathrm{Var}}\left(\sum_{e\in
E^{\prime}}v_{e}x_{e}(\BFC)\right)=$
$\displaystyle\operatorname{\mathbb{E}}[\sum_{e\in
E^{\prime}}v_{e}x_{e}(\BFC)]^{2}-(\sum_{e\in E^{\prime}}v_{e})^{2}/\rho^{2}$
$\displaystyle=$ $\displaystyle\sum_{e\in
E^{\prime}}v_{e}\Bigl{(}v_{e}\operatorname{\mathbb{E}}[x_{e}(\BFC)]+\sum_{f\in
A_{1}(e)}v_{f}\operatorname{\mathbb{E}}[x_{e}(\BFC)x_{f}(\BFC)]+\sum_{f\in
A_{2}(e)}v_{f}\operatorname{\mathbb{E}}[x_{e}(\BFC)x_{f}(\BFC)]$
$\displaystyle+\sum_{f\in
A_{3}(e)}v_{f}\operatorname{\mathbb{E}}[x_{e}(\BFC)x_{f}(\BFC)]\Bigr{)}-(\sum_{e\in
E^{\prime}}v_{e})^{2}/\rho^{2}$ $\displaystyle=$ $\displaystyle\sum_{e\in
E^{\prime}}v_{e}\Bigl{(}\frac{1}{\rho}v_{e}+\sum_{f\in
A_{2}(e)}v_{f}(\frac{1}{\rho^{2}}+\operatorname{\mathrm{Cov}}(x_{e}(\BFC)x_{f}(\BFC)))+\sum_{f\in
A_{3}(e)}v_{f}\frac{1}{\rho^{2}}\Bigr{)}-(\sum_{e\in
E^{\prime}}v_{e})^{2}/\rho^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{\rho}\left(1-\frac{1}{\rho}\right)\sum_{e\in
E^{\prime}}v_{e}^{2}-\frac{1}{\rho^{2}}\sum_{e\in E^{\prime}}\sum_{f\in
A_{1}(e)}v_{e}v_{f}+\sum_{e\in E^{\prime}}\sum_{f\in
A_{2}(e)}v_{e}v_{f}\operatorname{\mathrm{Cov}}(x_{e}(\BFC)x_{f}(\BFC)).$

Note that $-2\leq v_{e}\leq 2$ for all $e\in E^{\prime}$ and $\sum_{e\in
E^{\prime}}|v_{e}|\leq\sum_{(i,j)\in E}|v_{ij}|\leq n$ by the assumption
$\sum_{j\in\mathcal{N}_{i}}|v_{ij}|\leq 1$ for all $i\in[n]$. Also,
$|A_{1}(e)|\leq 2d-2$ and $|A_{2}(e)|\leq 2(d-1)^{2}$ since the maximum degree
is $d$. Then

$\displaystyle\sum_{e\in E^{\prime}}v_{e}^{2}\leq\sum_{e\in
E^{\prime}}2v_{e}\leq 2n$ $\displaystyle\sum_{e\in E^{\prime}}\sum_{f\in
A_{1}(e)}v_{e}v_{f}\geq-\sum_{e\in E^{\prime}}\sum_{f\in
A_{1}(e)}2|v_{e}|\geq-2\sum_{e\in E^{\prime}}|v_{e}||A_{1}(e)|\geq-4(d-1)n$
$\displaystyle\sum_{e\in E^{\prime}}\sum_{f\in
A_{2}(e)}|v_{e}v_{f}|\leq\sum_{e\in E^{\prime}}\sum_{f\in
A_{2}(e)}2|v_{e}|=2\sum_{e\in E^{\prime}}|v_{e}||A_{2}(e)|\leq 4(d-1)^{2}n$

Since
$-\rho^{-2}\leq\operatorname{\mathrm{Cov}}(x_{e}(\BFC)x_{f}(\BFC))=\operatorname{\mathbb{E}}(x_{e}(\BFC)x_{f}(\BFC))-\rho^{-2}\leq{\rho}^{-1}-\rho^{-2}$,
we have

$\displaystyle\operatorname{\mathrm{Var}}\left(\sum_{e\in
E^{\prime}}v_{e}x_{e}(\BFC)\right)\leq\frac{2n}{\rho}+\frac{4(d-1)n}{\rho^{2}}+\frac{4(d-1)^{2}n}{\rho}.$

To bound $\operatorname{\mathrm{Var}}(\tau|\BFC)$, we find upper bounds for
$\eta$ and $\delta$ (defined in Proposition 4), respectively. Since Algorithm
3 produce clusters with maximum size 2, we have $\eta\leq\sum_{k\in
1}^{m}2|C_{k}|/n^{2}=2/n$ and $\delta\leq 2/n$ by Lemma 13. Then we apply
Proposition 4 and obtain
$\operatorname{\mathrm{Var}}(\tau|\BFC)=O({d^{2}}/(np(1-p)))$. By the
Perron–Frobenius theorem, $\rho=\lambda^{*}\leq\max_{i\in E\sum_{j\in
E}M_{ij}}\leq 2d$. By the variance decomposition formula,
$\operatorname{\mathrm{Var}}(\tau)=\operatorname{\mathrm{Var}}(\operatorname{\mathbb{E}}[\tau|\BFC])+\operatorname{\mathbb{E}}[\operatorname{\mathrm{Var}}(\tau|\BFC)]$.
Combining everything, we get
$\operatorname{\mathrm{Var}}(\tau)=O({d^{3}}/(np(1-p)))$. ∎

##  5 Statistical Inference

In this section, we prove asymptotic normality results for the estimator
$\tau$ under mixed randomization design. This result will be useful for
performing statistic inference on the ATE, e.g., by hypothesis testing or
constructing confidence intervals.

Typically, proofs for asymptotic normality rely on certain versions of the
Central Limit Theorem. To this end, we rewrite the estimator $\tau$ in the
following form:

$\displaystyle\tau$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}2(2\rho\tilde{w}_{i}-\rho-\tilde{w}_{i}+1)\left(\frac{z_{i}}{p}-\frac{1-z_{i}}{1-p}\right)Y_{i}(\BFz),$

where $\tilde{w}_{i}$ indicates whether unit $i$ received a cluster-based
treatment assignment or a Bernoulli assignment (see Eq (5a) and (5b)). Let
$L_{i}$ be the term within the above summation. Then
$\tau=\frac{1}{n}\sum_{i=1}^{n}L_{i}$ is the average of $n$ dependent random
variables. We say the random variable $L_{i}$ has dependent neighborhood
$N_{i}\subset[n]$, if $i\in N_{i}$ and $X_{i}$ is independent of
$\\{L_{j}\\}_{j\neq N_{i}}$. The following result is an extension of Stein’s
method for bounding the distance between probability distributions in the
Wasserstein metric.

######  Lemma 11 (Ross,, 2011, Theorem 3.6).

Let $X_{1},\ldots,X_{n}$ be random variables such that
$\operatorname{\mathbb{E}}[X_{i}^{4}]<\infty$,
$\operatorname{\mathbb{E}}[X_{i}]=0$,
$\sigma^{2}=\operatorname{\mathrm{Var}}(\sum_{i=1}^{n}X_{i})$, and define
$W=\sum_{i=1}^{n}X_{i}/\sigma$. Let the collection $(X_{1},\ldots,X_{n})$ have
dependency neighborhoods $N_{i}$, $\forall i=[n]$, and also define
$D=\max_{i\in[n]}|N_{i}|$. Then for a standard normal random variable $Z$, we
have

$\displaystyle
d_{W}(W,Z)\leq\frac{D^{2}}{\sigma^{3}}\sum_{i=1}^{n}\operatorname{\mathbb{E}}[|X_{i}|^{3}]+\frac{\sqrt{28}D^{3/2}}{\sqrt{\pi}\sigma^{2}}\sqrt{\sum_{i=1}^{n}\operatorname{\mathbb{E}}[|X_{i}|^{4}]},$

where $d_{W}(\cdot,\cdot)$ is the Wasserstein metric:

$\displaystyle d_{W}(\mu,\upsilon)\ :=\
\sup_{\\{h\in\mathbb{R}\rightarrow\mathbb{R}:|h(x)-h(y)|\leq|x-y|\\}}\left|\int
h(x)d\mu(x)-\int h(x)d\upsilon(x)\right|.$

By Lemma 11, we establish sufficient conditions for asymptotic normality of
the estimator $\tau$.

######  Theorem 12.

Define $\sigma^{2}_{n}=\operatorname{\mathrm{Var}}({\sqrt{n}}\tau/{\rho})$. If
$\liminf_{n\rightarrow\infty}\sigma^{2}_{n}>0$, then we have

$\displaystyle\frac{\sqrt{n}(\tau-\operatorname{\mathbb{E}}[\tau])}{\sigma_{n}\rho}\mathop{\rightarrow}\limits^{d}N(0,1)$

under one of the following conditions:

(1) The design applies fixed clustering from Algorithm 1, and
${d^{8}}/{n}\rightarrow 0$;

(2) The design applies weight-invariant clustering from Algorithm 3, and
${d^{12}}/{n}\rightarrow 0$.

##  6 Numerical Experiments

###  6.1 Test Instances

We generalize networks in the numerical experiments from the random geometric
graph (RGG) model (Ugander et al.,, 2013). The RGG model is a spatial graph
where $n$ units are scattered according to a uniform distribution in the
region $[0,\sqrt{n}]\times[0,\sqrt{n}]$. Two units $i$ and $j$ are connected
if $dist(i,j)\leq\sqrt{r_{0}/\pi}$, where $r_{0}$ is the limiting expected
degree of the RGG model. To simulate the long-range dependency, we allow a
unit to connect with $r_{1}$ units outside the radius $\sqrt{r_{0}/\pi}$,
which are selected uniformly at random. Figure 1 shows two randomly generated
RGG model with different parameters. Furthermore, if $i$ and $j$ are
connected, we assign the weight coefficient $v_{ij}$ independently from a
uniform distribution $U(-1/r,2/r)$, where $r=r_{0}+r_{1}$. Note that the
magnitude of the inference is inversely proportional to the average degree.

Figure 1: Examples of RGG networks: the left figure is randomly generated from
$(n,r_{0},r_{1})=(100,10,0)$ and the right figure $(n,r_{0},r_{1})=(100,5,5)$.

To choose the parameters in the exposure mapping model Eq (1), we first
generate $\hat{\alpha}_{i}$ and $\hat{\beta}_{i}$ independently from $U(-1,1)$
for each $i\in[n]$. We then re-scale the parameters by
$\alpha_{i}=\hat{\alpha}_{i}+5-\frac{1}{n}\sum_{j=1}^{n}\hat{\alpha}_{j}$,
$\beta_{i}=\hat{\beta}_{i}+0.5-\frac{1}{n}\sum_{j=1}^{n}\hat{\beta}_{j}$ and
$\gamma=0.5\left(\sum_{i=1^{n}}\sum_{j\in\mathcal{N}_{i}}v_{ij}\right)^{-1}$.
The re-scaling step ensures that the true baseline parameter, , the direct
treatment effect parameter, and the interference effect parameter are
$\bar{\alpha}=5$, $\bar{\beta}=0.5$, and
$\gamma\sum_{i=1^{n}}\sum_{j\in\mathcal{N}_{i}}v_{ij}=0.5$, respectively. The
true value of the ATE is equal to $1$ in all randomly generated instances.

###  6.2 Comparison of Different Designs

The first design in our test is the fixed-cluster mixed randomization design
in Section 3 with known interference weights $v_{ij}$. In the experiment, we
generate the clusters using Algorithm 1 and implement the treatment assignment
steps in Section 3.3. The second design is the weight-invariant design
described in Section 4, which is agnostic to the weight coefficients $v_{ij}$.
Finally, we test the randomized graph cluster randomization (RGCR) design
Ugander and Yin, (2023), which is the state-of-the-art method for cluster-
based design. In all designs, we fix the probability of treatment to be
$p=0.5$. We denote the estimators of the above three designs by $\tau_{F}$,
$\tau_{W}$, and $\tau_{R}$, respectively.

To compare the performance under different network sizes and structures, we
generate $3\times 6=18$ test instances, parameterized by $(n,r_{0},r_{1})$.
The network size $n$ is chosen from $\\{1000,2000,4000\\}$. The value of
$(r_{0},r_{1})$ is chosen from the set
$\\{(4,0),(2,2),(0,4),(16,0),(8,8),(0,16)\\}$. Note that $r_{0}+r_{1}$ is
either 4 or 16, which represents the expected average degree in the RGG model.
Recall that when $r_{0}$ is positive and $r_{1}$ is zero, units are only
connected to those in short distances. When $r_{1}$ is positive, units may be
subject to long-range inference.

We consider three performance metrics for the ATE estimators $\tau$: mean
($\operatorname{\mathbb{E}}[\tau]$), variance
($\operatorname{\mathrm{Var}}(\tau)$), and theoretical variance upper bounds
($\widehat{\operatorname{\mathrm{Var}}(\tau)}$) given by Proposition 4. For
each instance, we run 10,000 independent simulations for each design. The
(exact) variances for $\tau_{F}$ and $\tau_{W}$ are approximated by sample
variances, while the variance of the RGCR is calculated according to formula
(2.1) to (2.3) in Ugander and Yin, (2023). To calculate theoretical upper
bounds on the variance, we use $Y_{M}=6$. The variance upper bound for the
RGCR design is given by
$\widehat{\operatorname{\mathrm{Var}}(\tau_{R})}={2}Y_{M}^{2}\sum_{i=1}^{n}|B_{2}(i)||B_{4}(i)|/n$
(this bound is in fact tighter than the bound used in Ugander and Yin,
(2023)). The simulation results are summarized in Table 1.

$(n,r_{0},r_{1})$ | $\operatorname{\mathbb{E}}[\tau_{F}]$ | $\operatorname{\mathbb{E}}[\tau_{W}]$ | $\operatorname{\mathbb{E}}[\tau_{R}]$ | $\operatorname{\mathrm{Var}}(\tau_{F})$ | $\operatorname{\mathrm{Var}}(\tau_{W})$ | $\operatorname{\mathrm{Var}}(\tau_{R})$ | $\widehat{\operatorname{\mathrm{Var}}(\tau_{F})}$ | $\widehat{\operatorname{\mathrm{Var}}(\tau_{W})}$ | $\widehat{\operatorname{\mathrm{Var}}(\tau_{R})}$
---|---|---|---|---|---|---|---|---|---
(1000,4,0) | 1.01 | 0.98 | 1.05 | 1.18 | 98.48 | 1.60 | 2.31 | 217.93 | 58.87
(1000,2,2) | 1.04 | 1.01 | 1.00 | 1.58 | 61.18 | 3.10 | 2.76 | 108.44 | 562.53
(1000,0,4) | 1.03 | 1.00 | 1.03 | 1.81 | 20.84 | 3.47 | 2.98 | 37.15 | 728.85
(1000,16,0) | 1.06 | 1.98 | 0.99 | 6.32 | 1225.79 | 11.36 | 12.69 | 3465.31 | 1910.17
(1000,8,8) | 1.04 | 1.26 | 0.93 | 13.22 | 639.16 | 32.89 | 25.44 | 2267.65 | 53433.22
(1000,0,16) | 1.07 | 0.57 | 0.96 | 15.37 | 507.15 | 45.77 | 30.13 | 2077.55 | 66028.03
(2000,4,0) | 1.01 | 1.53 | 1.01 | 0.64 | 76.97 | 0.85 | 1.20 | 133.91 | 29.18
(2000,2,2) | 1.01 | 1.02 | 1.01 | 0.83 | 42.80 | 1.67 | 1.49 | 80.48 | 330.58
(2000,0,4) | 0.99 | 0.92 | 1.00 | 0.79 | 9.87 | 1.66 | 1.52 | 18.57 | 378.55
(2000,16,0) | 0.97 | 1.29 | 1.03 | 3.53 | 485.21 | 5.71 | 6.79 | 2167.94 | 1066.67
(2000,8,8) | 1.04 | 1.44 | 1.00 | 6.56 | 355.62 | 18.59 | 12.35 | 1419.96 | 57776.42
(2000,0,16) | 1.02 | 0.99 | 1.05 | 7.53 | 254.43 | 26.25 | 15.09 | 1038.87 | 69962.69
(4000,4,0) | 1.01 | 1.36 | 0.97 | 0.34 | 63.24 | 0.41 | 0.64 | 105.77 | 15.44
(4000,2,2) | 1.01 | 0.82 | 0.99 | 0.42 | 33.58 | 0.88 | 0.76 | 59.63 | 193.27
(4000,0,4) | 1.00 | 1.04 | 1.02 | 0.44 | 5.43 | 0.93 | 0.75 | 9.29 | 193.31
(4000,16,0) | 1.02 | 0.97 | 0.98 | 1.85 | 289.58 | 3.27 | 3.63 | 1203.06 | 575.97
(4000,8,8) | 1.00 | 1.10 | 0.97 | 3.25 | 215.23 | 9.68 | 6.42 | 998.78 | 59398.23
(4000,0,16) | 1.00 | 1.12 | 1.05 | 3.91 | 130.46 | 12.15 | 7.63 | 519.46 | 71930.99
Table 1: Simulation Results for Different Experimental Designs.

We have several observations from the results in Table 1. First, let us
examine the metrics for $\tau_{F}$ (fixed clustering) and $\tau_{W}$ (weight-
invariant random clustering) under the mixed randomization design. As both
estimators are unbiased, we expect that the means will be closer to the ATE
when the sample variances are small. This relationship is confirmed by the
simulation result. For sample variances
$\operatorname{\mathrm{Var}}(\tau_{F})$, we observe from Table 1 that given
$(r_{0},r_{1})$, if the network size $n$ doubles, sample variances will
decrease approximately by a half. Additionally, given $n$, as the limiting
expected degree $(r_{0}+r_{1})$ increases, the variances of $\tau_{F}$
increase by approximately $(r_{0}+r_{1})^{2}$. These relationships imply that
the $O(d^{2}/n)$ bound in Theorem 5 is probably tight. We also observe that
the theoretical variance upper bounds of $\tau_{F}$ from Proposition 4,
$\widehat{\operatorname{\mathrm{Var}}(\cdot)}$, is often less than twice the
simulated sample variance, $\operatorname{\mathrm{Var}}(\cdot)$, suggesting
that the bound in Proposition 4 serves as a good approximation of the true
variance.

Next, let us compare the variances of the estimators across all three designs,
including $\tau_{R}$ for the RGCR cluster-based design (Ugander and Yin,,
2023). The estimator $\tau_{F}$ under fixed clustering achieves the smallest
sample variance and estimation errors among all three methods. The weight-
invariant design ($\tau_{W}$) has significantly larger sample variance and
estimation errors of the ATE compared to either the fixed-cluster mixed design
($\tau_{F}$) or cluster-based design ($\tau_{R}$). This is not surprising as
the weight-invariant design assumes unknown edge weights. The fixed-cluster
mixed design has a significantly smaller variance upper bound
($\widehat{\operatorname{\mathrm{Var}}(\tau_{F})}$) than the other designs,
whereas the upper bound of the RGCR design
($\widehat{\operatorname{\mathrm{Var}}(\tau_{R})}$) is the largest compared to
the others. However, empirically, the sample variances of RGCR are much
smaller than the theoretical upper bounds, which indicates there might be a
gap in the theoretical analysis of RGCR.

Finally, we examine the impact of the network structure parameters $r_{0}$ and
$r_{1}$ on the performance of these ATE estimators. For each setting
$r_{0}+r_{1}=4$ or $r_{0}+r_{1}=16$, we consider three values of $r_{0}$.
Recall that when the average degree ($r_{0}+r_{1}$) is fixed, a larger $r_{0}$
indicates that more neighbors are located in short distances, whereas a larger
$r_{1}$ implies more influences from long-range neighbors. Interestingly, we
find that the fixed-cluster mixed design $\tau_{F}$ is robust across all three
cases and the variance barely changes with $r_{0}$. The weight-invariant
design performs better under long-range interference (i.e., larger $r_{1}$)
but performs poorly under local network interference. However, the RGCR
performs better with strong local network inference (i.e., larger $r_{0}$).

##  7 Conclusions

We consider the problem of estimating the average treatment effect when units
in an experiment may interfere with other units. The interference pattern is
represented by an edge-weighted network, where the weights denote the
magnitude of interference between a pair of units. Based on previous
literature (Saveski et al.,, 2017; Pouget-Abadie et al., 2019b, ), we propose
a mixed experiment design that combines two commonly used methods: cluster-
based randomization and Bernoulli randomization. We propose an unbiased
estimator for the average treatment effect and establish upper and lower
bounds on the variance of this estimator. Both the known edge weights case and
the unknown edge weights case are studied. Moreover, we show the consistency
and asymptotic normality of the proposed estimator given the network satisfies
certain sparsity conditions.

##  Appendix A Proof of Main Results

###  A.1 Proof of Proposition 2

###### Proof.

We introduce the following notations:

$\displaystyle x_{ij}$
$\displaystyle:=\boldsymbol{1}\\{c(i)=c(j)\\},\quad\forall i,j,$
$\displaystyle t_{i}$
$\displaystyle:=(\frac{z_{i}}{p}-\frac{1-z_{i}}{1-p})=\frac{(-1)^{1-z_{i}}}{p^{z_{i}}(1-p)^{1-z_{i}}},\quad\forall
i,$ $\displaystyle r_{i}$
$\displaystyle:=\sum_{j\in\mathcal{N}_{i}}v_{ij}z_{i},\quad\forall i.$

Rewrite $\tau_{cb}=(\sum_{i=1}^{n}t_{i}Y_{i}(\BFz))/n$ and
$Y_{i}(\BFz)=\alpha_{i}+z_{i}\beta_{i}+\gamma r_{i}$, we have

$\begin{split}\operatorname{\mathbb{E}}[\tau_{cb}^{2}]=&\frac{1}{n^{2}}E\left(\sum_{1\leq
i,j\leq n}t_{i}t_{j}Y_{i}(\BFz)Y_{j}(\BFz)\right)\\\
=&\frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}(\alpha_{i}\alpha_{j}\operatorname{\mathbb{E}}[t_{i}t_{j}]+\beta_{i}\beta_{j}\operatorname{\mathbb{E}}[t_{i}t_{j}z_{i}z_{j}]+\gamma^{2}\operatorname{\mathbb{E}}[t_{i}t_{j}r_{i}r_{j}]\\\
&+2\alpha_{i}\beta_{j}\operatorname{\mathbb{E}}[t_{i}t_{j}z_{j}]+2\alpha_{i}\gamma\operatorname{\mathbb{E}}[t_{i}t_{j}r_{j}]+2\beta_{i}\gamma\operatorname{\mathbb{E}}[t_{i}t_{j}z_{i}r_{j}]).\end{split}$
(13)

Notice that
$\operatorname{\mathbb{E}}[t_{i}t_{j}]=x_{ij}\operatorname{\mathbb{E}}[t_{i}^{2}]$,
$\operatorname{\mathbb{E}}[t_{i}t_{j}z_{i}z_{j}]=x_{ij}\operatorname{\mathbb{E}}[t_{i}^{2}z_{i}^{2}]+(1-x_{ij})$,
$\operatorname{\mathbb{E}}[t_{i}t_{j}z_{j}]=x_{ij}\operatorname{\mathbb{E}}[t_{i}^{2}z_{i}]$,
$\operatorname{\mathbb{E}}[t_{i}t_{j}r_{j}]=x_{ij}\operatorname{\mathbb{E}}[t_{i}^{2}r_{j}]$,
$\operatorname{\mathbb{E}}[t_{i}t_{j}z_{i}r_{j}]=x_{ij}\operatorname{\mathbb{E}}[t_{i}^{2}z_{i}r_{j}]+(1-x_{ij})\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{jj^{\prime}}$
and
$\operatorname{\mathbb{E}}[t_{i}t_{j}r_{i}r_{j}]=x_{ij}\operatorname{\mathbb{E}}[t_{i}^{2}r_{i}r_{j}]+(1-x_{ij})[(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ii^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{jj^{\prime}})+(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ji^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{ij^{\prime}})]$.
Plugging these into Eq (13), we have

$\begin{split}\operatorname{\mathbb{E}}[\tau_{cb}^{2}]=&\frac{1}{n^{2}}\sum_{1\leq
i,j\leq n}x_{ij}E\left(t_{i}^{2}Y_{i}(\BFz)(\alpha_{j}+\beta_{j}z_{i}+\gamma
r_{j})\right)\\\ &+\frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}\left(\beta_{i}\beta_{j}(1-x_{ij})+2\beta_{i}\gamma(1-x_{ij})\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{jj^{\prime}}\right)\\\
&+\frac{\gamma^{2}}{n^{2}}\sum_{1\leq i,j\leq
n}\left((1-x_{ij})\left[(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ii^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{jj^{\prime}})+(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ji^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{ij^{\prime}})\right]\right).\end{split}$
(14)

By Lemma 1 and
$\operatorname{\mathrm{Var}}(\tau_{cb})=\operatorname{\mathbb{E}}[\tau_{cb}^{2}]-\operatorname{\mathbb{E}}[\tau_{cb}]^{2}$,
we have

$\begin{split}\operatorname{\mathrm{Var}}(\tau_{cb})=&\frac{1}{n^{2}}\sum_{1\leq
i,j\leq n}x_{ij}E\left(t_{i}^{2}Y_{i}(\BFz)(\alpha_{j}+\beta_{j}z_{i}+\gamma
r_{j})\right)\\\ &-\frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}x_{ij}\left(\beta_{i}\beta_{j}+2\beta_{i}\gamma\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{jj^{\prime}}+\gamma^{2}(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ii^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{jj^{\prime}})\right)\\\
&+\frac{\gamma^{2}}{n^{2}}\sum_{1\leq i,j\leq
n}\left((1-x_{ij})(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ji^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{ij^{\prime}})\right).\\\
\end{split}$ (15)

Recall that $0<Y_{L}\leq Y_{i}(\BFz)\leq Y_{M}$ for all $i\in V$ and
$\BFz\in\\{0,1\\}^{n}$, which implies that
$0<Y_{L}\leq\alpha_{j}+\beta_{j}z_{i}+\gamma r_{j}\leq Y_{M}$ for all $i,j\in
V$. Thus,

$\displaystyle\frac{Y_{L}^{2}}{p(1-p)}=\operatorname{\mathbb{E}}[t_{i}^{2}Y_{L}^{2}]\leq\operatorname{\mathbb{E}}\left[t_{i}^{2}Y_{i}(\BFz)(\alpha_{j}+\beta_{j}z_{i}+\gamma
r_{j})\right]\leq\operatorname{\mathbb{E}}[t_{i}^{2}Y_{M}^{2}]=\frac{Y_{M}^{2}}{p(1-p)},\quad\forall
i,j\in V.$

Furthermore, $Y_{i}(\boldsymbol{0})>0$ implies $\alpha_{i}>0$ for all $i$. Let
$s_{i}:=\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ii^{\prime}}$,
then we have

$\displaystyle 2Y_{M}(Y_{L}-Y_{M})$ $\displaystyle\leq$
$\displaystyle\beta_{i}\beta_{j}+\beta_{i}\gamma s_{j}+\beta_{j}\gamma
s_{i}+\gamma^{2}s_{i}s_{j}$ $\displaystyle=$
$\displaystyle(\alpha_{i}+\beta_{i}+\gamma s_{i})(\alpha_{j}+\beta_{j}+\gamma
s_{j})-2\alpha_{i}(\alpha_{j}+\beta_{j}+\gamma s_{j})+\alpha_{i}\alpha_{j}$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}Y_{M}^{2}.$

Finally, let $x_{C_{k},i}=x_{i,C_{k}}:=\boldsymbol{1}\\{c(i)=C_{k}\\}$. By Eq
(1), we have

$\displaystyle\sum_{1\leq i,j\leq
n}\left((1-x_{ij})(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ji^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{ij^{\prime}})\right)$
$\displaystyle=$ $\displaystyle\sum_{1\leq k\neq l\leq m}\sum_{i\in
C_{k}}\sum_{j\in
C_{l}}(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ji^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{ij^{\prime}})$
$\displaystyle=$ $\displaystyle\sum_{1\leq k\neq l\leq m}\sum_{i\in
C_{k}}(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{C_{l},i^{\prime}})\sum_{j\in
C_{l}}(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{C_{k},j^{\prime}})$
$\displaystyle=$ $\displaystyle\sum_{1\leq k\neq l\leq m}(\sum_{i\in
C_{k}}\sum_{i^{\prime}\in\mathcal{N}_{i}\cap C_{l}}v_{ii^{\prime}})(\sum_{j\in
C_{l}}\sum_{j^{\prime}\in\mathcal{N}_{j}\cap C_{k}}v_{jj^{\prime}}).$ (16)

Combine all above together and using the fact that $\sum_{1\leq i,j\leq
n}x_{ij}=\sum_{k=1}^{m}|C_{k}|^{2}$, the proof is complete.

∎

###  A.2 Proof of Proposition 4

###### Proof.

Note that

$\displaystyle\operatorname{\mathrm{Var}}(\tau)=\rho^{2}\operatorname{\mathbb{E}}[\tau_{c}^{2}]+(\rho-1)^{2}\operatorname{\mathbb{E}}[\tau_{b}^{2}]-2\rho(\rho-1)\operatorname{\mathbb{E}}[\tau_{c}\tau_{b}]-(\bar{\beta}+\frac{\gamma}{n}\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij})^{2}.$

Below, we inherit the notations defined in the proof of Proposition 2.
Analogous to the proof of Proposition 2, we have

$\displaystyle\operatorname{\mathbb{E}}[\tau_{c}^{2}]=$
$\displaystyle\frac{4}{n^{2}}\sum_{1\leq i,j\leq
n}x_{ij}E\left(\tilde{w}_{i}t_{i}^{2}Y_{i}(\BFz)(\alpha_{j}+\beta_{j}z_{i}+\gamma
r_{j})\right)$ $\displaystyle+\frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}(1-x_{ij})\left(\beta_{i}\beta_{j}+2\beta_{i}\gamma\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{jj^{\prime}}\right)$
$\displaystyle+\frac{\gamma^{2}}{n^{2}}\sum_{1\leq i,j\leq
n}\left((1-x_{ij})\left[(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ii^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{jj^{\prime}})+(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ji^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{ij^{\prime}})\right]\right),$
$\displaystyle\operatorname{\mathbb{E}}[\tau_{b}^{2}]=$
$\displaystyle\frac{4}{n^{2}}\sum_{i=1}^{n}E\left((1-\tilde{w}_{i})t_{i}^{2}Y_{i}(\BFz)(\alpha_{j}+\beta_{j}z_{i}+\gamma
r_{j})\right)+\bar{\beta}-\frac{1}{n^{2}}\sum_{i=1}^{n}\beta_{i}^{2}$
$\displaystyle+\frac{\gamma^{2}}{n^{2}}\sum_{i=1}^{n}\sum_{\\{j\in\mathcal{N}_{i}:i\in\mathcal{N}_{j}\\}}v_{ij}v_{ji},$
$\displaystyle\operatorname{\mathbb{E}}[\tau_{c}\tau_{b}]=$
$\displaystyle\frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}(1-x_{ij})\left(\beta_{i}\beta_{j}+\beta_{i}\gamma\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{jj^{\prime}}\right).$

Combining the above equations, we have

$\displaystyle\operatorname{\mathrm{Var}}(\tau)\leq$
$\displaystyle\frac{2}{p(1-p)}Y_{M}^{2}(\rho^{2}\eta+\frac{1}{n}(\rho-1)^{2})-(\rho-1)^{2}\frac{1}{n^{2}}\sum_{i=1}^{n}\beta_{i}^{2}$
$\displaystyle-\frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}[(\rho-1)^{2}\beta_{i}\beta_{j}+(\beta_{i}+\rho\gamma
s_{i})(\beta_{j}+\rho\gamma s_{j})]x_{ij}$
$\displaystyle+(\rho-1)^{2}\frac{\gamma^{2}}{n^{2}}\sum_{i=1}^{n}\sum_{\\{j\in\mathcal{N}_{i}:i\in\mathcal{N}_{j}\\}}v_{ij}v_{ji}+\rho^{2}\gamma^{2}\delta.$

Recall that $0<Y_{L}\leq Y_{i}(\BFz)\leq Y_{M}$ for all $i\in V$ and
$\BFz\in\\{0,1\\}^{n}$, which implies that $Y_{L}-Y_{M}\leq\beta_{i}+\gamma
s_{i}=Y_{i}(1,\BFz_{-i})-\alpha_{i}\leq Y_{M}-Y_{L}$ for all $i\in V$ (here
$\BFz_{-i}$ is the treatment for all units other than $i$). So

$\displaystyle\rho^{2}(Y_{L}^{2}+Y_{M}Y_{L}-Y_{M}^{2})$ $\displaystyle\leq$
$\displaystyle(\rho-1)^{2}\beta_{i}\beta_{j}+(\beta_{i}+\rho\gamma
s_{i})(\beta_{j}+\rho\gamma s_{j})$ $\displaystyle=$
$\displaystyle\rho^{2}(\beta_{i}+\gamma s_{i})(\beta_{j}+\gamma
s_{j})-\rho(\rho-1)(\beta_{i}\gamma s_{j}+\beta_{j}\gamma s_{i})$
$\displaystyle\leq$ $\displaystyle\rho^{2}Y_{M}(2Y_{M}-Y_{L}).$

Next, consider another clustering $\BFC^{\prime}$ of the network $G(V,E)$
where each vertex forms an individual cluster (i.e.,
$\BFC^{\prime}=\\{C^{\prime}_{1},C^{\prime}_{2},...,C^{\prime}_{n}\\}=\\{\\{1\\},\\{2\\},...,\\{n\\}\\}$).
By inequality (17) in Lemma 13

$\displaystyle\sum_{i=1}^{n}\sum_{\\{j\in\mathcal{N}_{i}:i\in\mathcal{N}_{j}\\}}v_{ij}v_{ji}=\sum_{1\leq
k\neq l\leq n}\left(\sum_{i\in
C^{\prime}_{k}}\sum_{i^{\prime}\in\mathcal{N}_{i}\cap
C^{\prime}_{l}}v_{ii^{\prime}}\right)\left(\sum_{j\in
C^{\prime}_{l}}\sum_{j^{\prime}\in\mathcal{N}_{j}\cap
C^{\prime}_{k}}v_{jj^{\prime}}\right)\leq n.$

Then the upper bound in Eq (7) follows. The proof for the lower bound in Eq
(8) is almost identical and thus is omitted.

∎

###  A.3 Proof of Theorem 5

###### Proof.

The proof includes two steps. Firstly, we would show that under the cluster
set $\BFC$ generated by maximum weight matching, the approximate variance
upper bound $A(\BFC)$ defined in (9) is $O(d^{2}/(np(1-p)))$. Since the
merging step in Algorithm 1 strictly decrease the value of $A(\BFC)$, we then
show that $A(\BFC)=O(d^{2}/(np(1-p)))$ implies the variance of the estimator
$\tau$ is also $O(d^{2}/(np(1-p)))$, which completes the proof.

To bound $A(\BFC)$ under the cluster set $\BFC$ generated by maximum weight
matching, we bound $\rho$, $\eta$ and $\delta$, respectively. By Lemma 15 in
Appendix B, a maximum weight matching guarantees $\sum_{i\in
V}\sum_{j\in\mathcal{N}_{i}}v_{ij}\boldsymbol{1}\\{c(i)=c(j)\\}\geq(\sum_{i\in
V}\sum_{j\in\mathcal{N}_{i}}v_{ij})/{2d}$ in a graph with maximum degree $d$,
thus

$\displaystyle\rho=\frac{\sum_{i\in
V}\sum_{j\in\mathcal{N}_{i}}v_{ij}}{\sum_{i\in
V}\sum_{j\in\mathcal{N}_{i}}v_{ij}\boldsymbol{1}\\{c(i)=c(j)\\}}\leq 2d.$

To bound $\eta$, because $|C_{k}|\leq 2$ in the max weight matching and
$\sum_{k=1}^{m}|C_{k}|=n$, we have

$\eta=\sum_{k=1}^{m}\frac{|C_{k}|^{2}}{n^{2}}\leq\sum_{k=1}^{m}\frac{2|C_{k}|}{n^{2}}=\frac{2}{n}.$

By Lemma 13, $\delta\leq 2/n$ since the maximum cluster size is 2. Combining
the upper bounds for $\rho$, $\eta$ and $\delta$, $A(\BFC)$ defined in (9) is
$O(d^{2}/(np(1-p)))$.

Next, we show that $A(\BFC)=O(d^{2}/(np(1-p)))$ implies
$\operatorname{\mathrm{Var}}(\tau)=O(d^{2}/(np(1-p)))$. We first prove that
$(Y_{M}-Y_{L})^{2}/a^{2}$ is an upper bound for $\gamma^{2}$. By the
assumption that $Y_{L}\leq Y_{i}(\BFz)\leq Y_{M}$ for all $i\in[n]$ and
$\BFz\in\\{0,1\\}^{n}$, we have $Y_{L}\leq\alpha_{i}\leq Y_{M}$ and
$Y_{L}\leq\alpha_{i}+\gamma\sum_{j\in\mathcal{N}_{i}}v_{ij}z_{j}\leq Y_{M}$
for all $i\in[n]$ and $\BFz\in\\{0,1\\}^{n}$. Thus

$Y_{L}\leq Y_{M}\leq
Y_{L}-\alpha_{i}\leq\gamma\sum_{j\in\mathcal{N}_{i}}v_{ij}z_{j}\leq
Y_{M}-\alpha_{i}\leq Y_{M}-Y_{L},\quad\forall i\in[n],\BFz\in\\{0,1\\}^{n},$

which implies

$\gamma^{2}\leq\frac{(Y_{M}-Y_{L})^{2}}{(\sum_{j\in\mathcal{N}_{i}}v_{ij}z_{j})^{2}},\quad\forall
i\in[n],\BFz\in\\{0,1\\}^{n},$

and therefore,

$\gamma^{2}\leq\frac{(Y_{M}-Y_{L})^{2}}{(\max_{i\in[n]}\sum_{j\in\mathcal{N}_{i}}\max\\{v_{ij},0\\})^{2}}=\frac{(Y_{M}-Y_{L})^{2}}{a^{2}}.$

Then by the variance upper bound in Proposition 4, there exists a positive
constant $C_{0}$ such that

$\displaystyle\operatorname{\mathrm{Var}}(\tau)\leq$
$\displaystyle\left((\frac{2}{p(1-p)}+1)Y_{M}^{2}-Y_{M}Y_{L}-Y_{L}^{2}\right)\rho^{2}\eta+\gamma^{2}\rho^{2}\delta+C_{0}\frac{\rho^{2}}{np(1-p)}$
$\displaystyle\leq$
$\displaystyle\left((\frac{2+C_{0}}{p(1-p)}+1)Y_{M}^{2}-Y_{M}Y_{L}-Y_{L}^{2}+C_{0}\right)\rho^{2}\eta+\frac{(Y_{M}-Y_{L})^{2}}{a^{2}}\rho^{2}|\delta|$
$\displaystyle\leq$ $\displaystyle
C_{1}A(\BFC)=O\left(\frac{d^{2}}{np(1-p)}\right),$

where the second inequality follows from
$\eta=\sum_{k=1}^{m}|C_{k}|^{2}/n^{2}\geq\sum_{k=1}^{m}|C_{k}|/n^{2}=1/n$ and
$\gamma^{2}\leq{(Y_{M}-Y_{L})^{2}}/{a^{2}}$, and $C_{1}$ in the third
inequality is a constant. ∎

###  A.4 Proof of Theorem 6

###### Proof.

Below, we use the upper bound Eq (7) in Proposition 4 and find bounds for
$\rho$, $\eta$, and $\delta$, respectively.

Recall that by the definition of Algorithm 2, the size of any cluster is no
more than $\kappa(d+1)$. Let $v_{0}$ denote the center vertex of a 2-hop
cluster in the first step of the algorithm, and $V_{0}$ be the set of all such
vertices. Suppose there exists $u\in V$ such that $u\notin B_{4}(v_{0})$ for
any $v_{0}\in V_{0}$, then $B_{2}(u)$ does not intersect with $B_{2}(v_{0})$
for any $v_{0}\in V_{0}$. Otherwise, there exists $v^{\prime}_{0}$ and a path
from $v^{\prime}_{0}$ to $u$ with at most 4 hops, which is a contradiction.
Thus for any $u\in V$, $u\in B_{4}(v)$ for some $v$ chosen in the first step
of the algorithm.

Suppose $|V_{0}|=m$ and $V_{0}$ consists of vertices
$\\{v_{1},v_{2},...,v_{m}\\}$ generated from the first step of the algorithm.
Since $V\subset\cup_{k=1}^{m}B_{4}(v_{k})$, we have

$n=|V|\leq\sum_{k=1}^{m}|B_{4}(v_{k})|\leq\kappa^{3}\sum_{k=1}^{m}|B_{1}(v_{k})|.$

Thus, we have

$\displaystyle\rho\leq\frac{n}{\sum_{i=1}^{n}\sum_{j\in\mathcal{N}_{i}}v_{ij}\boldsymbol{1}\\{c(i)=c(j)\\}}\leq\frac{n}{\sum_{k=1}^{m}\sum_{u\in
B_{1}(v_{k})}\epsilon}=\frac{n}{\epsilon\sum_{k=1}^{m}|B_{1}(v_{k})|}\leq\frac{\kappa^{3}}{\epsilon},$

where the first inequality follows from the definition of $\rho$ in Eq (6),
the second inequality holds since we assume the weights satisfy $v_{ij}\geq 0$
and $\sum_{j\in\mathcal{N}_{i}}v_{ij}\geq\epsilon$, and the final inequality
is from the previous equation. This gives an upper bound for $\rho$.

To bound $\eta$, we have
$\eta=\sum_{k=1}^{m}{|C_{k}|^{2}}/{n^{2}}\leq\sum_{k=1}^{m}{\kappa(d+1)|C_{k}|}/{n^{2}}=\kappa(d+1)/n$
since $\max_{k\in[m]}|C_{k}|\leq\kappa(d+1)$. To bound $\delta$, we apply
Lemma 13 and obtain $\delta\leq\kappa(d+1)/n$. Combining the upper bounds for
$\rho$, $\eta$ and $\delta$ together and applying Proposition 4, the variance
of estimator $\tau$ is $O(k^{7}d/(np(p-1)))$.

∎

###  A.5 Proof of Theorem 7

###### Proof.

In a $(d,\kappa)$-cycle network, we call an edge $(i,j)\in E$ a Type-1 edge if
$j\in\\{(i\pm 1)\mod n,(i\pm 2)\mod n,...,(i\pm(\kappa-1))\mod n\\}$, and a
Type-2 edge if $j\in\\{(i\pm\kappa)\mod n,(i\pm 2\kappa)\mod n,...,(i\pm
d\kappa)\mod n\\}$. We say a cluster $\\{i_{1},i_{2},...,i_{l}\\}$ is
continuous if and only if it includes at least $l-1$ edges from the set
$\\{(j,(j+1)\mod n):1\leq j\leq n\\}$. Let $E^{1}$ and $E^{2}$ be the set of
Type-1 and Type-2 edges, respectively.

Consider a cluster $C$ of size $t$. Let $n_{k}^{C}$ denote the number of
Type-$k$ edges ($k=1,2$) in cluster $C$, i.e. $n_{k}^{C}=|\\{(i,j)\in E:i\in
C,j\in C;\;(i,j)\in E^{k}\\}|$, for $k\in\\{1,2\\}$. First, we bound
$n_{1}^{C}$ as follows:

  1. (1-a)

When $t\leq\kappa$, since the maximum number of edges in $C$ is $t(t-1)$ (when
$C$ is a clique), we have $n_{1}^{C}\leq t(t-1)$.

  2. (1-b)

When $\kappa+1\leq t\leq 2\kappa-1$,

$\displaystyle
n_{1}^{C}\leq(\kappa-1)+\kappa+...+\underbrace{(t-1)+...+(t-1)}_{2\kappa-t}+(t-2)+...+(\kappa-1)=(\kappa-1)(2t-\kappa).$

  3. (1-c)

When $t\geq 2\kappa$,

$\displaystyle
n_{1}^{C}\leq(\kappa-1)+\kappa+...+\underbrace{2(\kappa-1)+...2(\kappa-1)}_{t-2\kappa+2}+2\kappa-3+...+(\kappa-1)=(\kappa-1)(2t-\kappa).$

Similarly, for $n^{C}_{2}$, we have the following bounds:

  1. (2-a)

When $t\leq(d+1)\kappa$, we have $n_{2}^{C}\leq
t\lfloor\frac{t-1}{\kappa}\rfloor$.

  2. (2-b)

When $(d+1)\kappa+1\leq t\leq 2d\kappa+1$,

$\displaystyle n_{2}^{C}\leq$ $\displaystyle
d\kappa+(d+1)\kappa+...+\lfloor\frac{t-1}{\kappa}\rfloor\left(t-2\kappa(\lfloor\frac{t-1}{\kappa}\rfloor-d)\right)+(\lfloor\frac{t-1}{\kappa}\rfloor-1)\kappa+...+d\kappa$
$\displaystyle=$ $\displaystyle
t\lfloor\frac{t-1}{\kappa}\rfloor-(\lfloor\frac{t-1}{\kappa}\rfloor-d)(\lfloor\frac{t-1}{\kappa}\rfloor-d+1)\kappa.$

  3. (2-c)

When $t\geq 2d\kappa+2$,

$\displaystyle n_{2}^{C}\leq$ $\displaystyle
d\kappa+(d+1)\kappa+...+2d\left(t-2d\kappa\right)+(2d-1)\kappa+...+d\kappa=d(2t-\kappa(d+1)).$

Note that when $(d+1)\kappa+1\leq t\leq 2d\kappa+1$ (i.e., Case 2-b),

$\displaystyle
t\lfloor\frac{t-1}{\kappa}\rfloor-(\lfloor\frac{t-1}{\kappa}\rfloor-d)(\lfloor\frac{t-1}{\kappa}\rfloor-d+1)\kappa$
$\displaystyle\leq$ $\displaystyle
k(\lfloor\frac{t-1}{\kappa}\rfloor+1)\lfloor\frac{t-1}{\kappa}\rfloor-(\lfloor\frac{t-1}{\kappa}\rfloor-d)(\lfloor\frac{t-1}{\kappa}\rfloor-d+1)\kappa$
$\displaystyle=$ $\displaystyle\kappa
d(2\lfloor\frac{t-1}{\kappa}\rfloor-d+1)$ $\displaystyle\leq$ $\displaystyle
d(2t-\kappa(d+1)),$

so the bound in (2-c) also applies to (2-b).

To summarize,

$\displaystyle n_{1}^{C}+n_{2}^{C}\leq f(t)\ :=\
\left\\{\begin{array}[]{cl}t(t-1),&\text{if }1\leq t\leq\kappa\\\
(\kappa-1)(2t-\kappa)+t\lfloor\frac{t-1}{\kappa}\rfloor,&\text{if
}\kappa+1\leq t\leq\kappa(d+1)\\\
d(2t-\kappa(d+1))+(\kappa-1)(2t-\kappa),&\text{if }t\geq\kappa(d+1)+1.\\\
\end{array}\right.$

It’s easy to check that $f(t)$ is nonnegative and increasing on $t\geq 1$.
Suppose we have $m$ clusters, and $t_{j}$ is the size of the $j$th cluster.
Then by $n_{1}^{C}+n_{2}^{C}\leq f(t)$ and the Cauchy-Schwarz inequality,

$\displaystyle\rho^{2}\eta\geq\frac{\sum_{j=1}^{m}t_{j}^{2}}{n^{2}}\left(\frac{2n(d+\kappa-1)}{\sum_{i=j}^{m}f(t_{j})}\right)^{2}\geq
4(d+\kappa-1)^{2}\left(\sum_{j=1}^{m}\frac{f(t_{j})^{2}}{t_{j}^{2}}\right)^{-1}.$

Furthermore, we relax $t_{j}$ to continuous variables. Note that when $1\leq
t\leq\kappa$, $f(t)/t^{1.5}\leq t^{0.5}\leq\sqrt{\kappa}$. When $\kappa+1\leq
t\leq\kappa(d+1)$, we have

$\displaystyle f(t)/t^{1.5}\leq 2\kappa/\sqrt{t}+\sqrt{t}/\kappa\leq
2\kappa/\sqrt{\kappa+1}+\sqrt{(d+1)/\kappa}.$

When $\kappa(d+1)+1\leq t\leq n$, $f(t)/t^{1.5}\leq
2(d+\kappa-1)/\sqrt{t}<2(d+\kappa-1)/\sqrt{\kappa(d+1)}$. Thus,
$f(t)^{2}/t^{3}=O(\max\\{\kappa,d/\kappa\\})$. Then by Lemma 14,
$\max\sum_{i=j}^{m}{f(t_{j})^{2}}/{t_{j}^{2}}=O(\max\\{n\kappa,nd/\kappa\\})$,
and the proof is complete.

∎

###  A.6 Proof of Theorem 12

###### Proof.

Let $X_{i}=\frac{1}{\sqrt{n}d}(L_{i}-\operatorname{\mathbb{E}}[L_{i}])$, then
$\operatorname{\mathbb{E}}[X_{i}]=0$ and
$\operatorname{\mathbb{E}}[X_{i}^{4}]\leq\left(\frac{2}{\sqrt{n}p(1-p)}Y_{M}\right)^{4}<\infty$.
Recall that $B_{r}(v)$ is defined to be the set of vertices within $r$ hops of
a vertex $v$ in Definition 3. For two units $i$ and $j$, if $B_{2}(i)$ and
$B_{2}(j)$ are not both intersect with any clusters, then $X_{i}$ and $X_{j}$
are independent. Using the notation $D$ in Lemma 11 and under condition (1), a
unit is connected to at most $d$ clusters and each cluster is connected to at
most $2d+1$ nodes, thus $D\leq d(2d+1)$. Under condition (2), for unit $i$ and
any unit $j\notin B_{3}(i)$, $X_{i}$ and $X_{j}$ are independent, thus
$D\leq|B_{3}(i)|<d^{3}$. Apply Lemma 11 and the result follows.

∎

##  Appendix B Auxiliary Results

######  Lemma 13.

We have the following bound for $\delta$ (defined in Proposition 4):

$\delta\leq\frac{\max_{k\in[m]}|C_{k}|}{n}.$

###### Proof.

First, we prove the inequality below:

$\sum_{1\leq k\neq l\leq m}\left(\sum_{i\in
C_{k}}\sum_{i^{\prime}\in\mathcal{N}_{i}\cap
C_{l}}v_{ii^{\prime}}\right)\left(\sum_{j\in
C_{l}}\sum_{j^{\prime}\in\mathcal{N}_{j}\cap C_{k}}v_{jj^{\prime}}\right)\leq
n\max_{k\in[m]}|C_{k}|.$ (17)

By Eq (16) in the proof of Proposition 2 and Eq (1), we have

$\displaystyle\sum_{k\neq l}(\sum_{i\in
C_{k}}\sum_{i^{\prime}\in\mathcal{N}_{i}\cap C_{l}}v_{ii^{\prime}})(\sum_{j\in
C_{l}}\sum_{j^{\prime}\in\mathcal{N}_{j}\cap C_{k}}v_{jj^{\prime}})$
$\displaystyle=$
$\displaystyle\sum_{i,j}\left((1-x_{ij})(\sum_{i^{\prime}\in\mathcal{N}_{i}}v_{ii^{\prime}}x_{ji^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}v_{jj^{\prime}}x_{ij^{\prime}})\right)$
$\displaystyle\leq$
$\displaystyle\sum_{i,j}(\sum_{i^{\prime}\in\mathcal{N}_{i}}|v_{ii^{\prime}}|x_{ji^{\prime}})(\sum_{j^{\prime}\in\mathcal{N}_{j}}|v_{jj^{\prime}}|x_{ii^{\prime}})\quad\text{(by
taking the absolute value)}$ $\displaystyle\leq$
$\displaystyle\sum_{i,j}(\sum_{i^{\prime}\in\mathcal{N}_{i}}|v_{ii^{\prime}}|x_{ji^{\prime}})\quad\text{(because
}\sum_{i^{\prime}\in\mathcal{N}_{i}}|v_{ii^{\prime}}|\leq 1)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\sum_{i^{\prime}\in\mathcal{N}_{i}}|v_{ii^{\prime}}||C_{c(i^{\prime})}|$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n}(\max_{k\in[m]}|C_{k}|)\sum_{i^{\prime}\in\mathcal{N}_{i}}|v_{ii^{\prime}}|$
$\displaystyle\leq$ $\displaystyle n\max_{k\in[m]}|C_{k}|\quad\text{(because
}\sum_{i^{\prime}\in\mathcal{N}_{i}}|v_{ii^{\prime}}|\leq 1).$

Using Eq (17) and the definition of $\delta$, we have

$\delta=\frac{1}{n^{2}}\sum_{1\leq k\neq l\leq m}\left(\sum_{i\in
C_{k}}\sum_{i^{\prime}\in\mathcal{N}_{i}\cap
C_{l}}v_{ii^{\prime}}\right)\left(\sum_{j\in
C_{l}}\sum_{j^{\prime}\in\mathcal{N}_{j}\cap
C_{k}}v_{jj^{\prime}}\right)\leq\frac{\max_{k\in[m]}|C_{k}|}{n}.$

∎

######  Lemma 14.

For any function $f(x):[1,n]\to\mathbb{R}$, if there exists
$a:=\mathop{\max}\limits_{x\in[1,n]}f(x)/x$, then the optimal value of the
following optimization problem is bounded by

$\displaystyle\max\left\\{\sum_{j=1}^{m}f(t_{j}),\text{subject to
}m\in\mathbb{Z}^{+},\BFt\in[1,n]^{m},\sum_{j=1}^{m}t_{j}=n\right\\}\leq na.$

###### Proof.

The result follows from the following inequality:

$\sum_{j=1}^{m}f(t_{j})=\sum_{j=1}^{m}\frac{f(t_{j})}{t_{j}}t_{j}\leq
a\sum_{j=1}^{m}t_{j}=na.$

∎

######  Lemma 15.

For a graph $G(V,E)$ with the edge weights $\\{v_{ij}\\}_{(i,j)\in E}$ and the
maximum degree $d$, the sum of weights in a maximum weight matching is at
least $(\sum_{i\in V}\sum_{j\in\mathcal{N}_{i}}v_{ij})/{2d}$.

###### Proof.

Let $G^{\prime}(V^{\prime})$ be the subgraph of $G(V,E)$ induced by a subset
of vertices $V^{\prime}\subset V$ and $G^{\prime}(V^{\prime},E^{\prime})$ the
subgraph induced by $V^{\prime}\subset V$ and $E^{\prime}\subset E$. For
brevity of notations, we let $V(E)$ denote the subset of $V$ such that each
vertex in $V(E)$ is incident to at least one edge in $E$. We provide Algorithm
4 based on maximum matching.

Input: A graph $G(V,E)$

1 Initialize the clustering set $\mathbb{C}\leftarrow\\{\\}$

2 Initialize set $A\leftarrow E$

3 while  _$|A| >0$_ do

4 $U\leftarrow\\{u\in V|\texttt{degree}(u,A)=\max_{v\in
V}\texttt{degree}(v,A)\\}$

5 Find a maximum matching $M_{1}=\\{(v_{1},u_{1}),(v_{2},u_{2}),...\\}$ from
the subgraph $G^{\prime}(U)$

6 $M_{2}\leftarrow\\{\\}$

7 for  _$u\in U$_ do

8 if  _$u\in U/V(M_{1})$ and $\mathcal{N}_{u}\not\subset U$_ then

9 Choose one $u^{\prime}\in\mathcal{N}_{u}/U$ and let $M_{2}\leftarrow
M_{2}\cup\\{(u,u^{\prime})\\}$

10

11
$\mathbb{C}\leftarrow\mathbb{C}\cup\\{\texttt{edge\\_set\\_to\\_clustering}(M_{1}\cup
M_{2})\\}$

12 $A\leftarrow A/(M_{1}\cup M_{2})$

13 $U^{\prime}=U/V(M_{1}\cup M_{2})$

14 if  _$|U^{\prime}| >0$_ then

15 Find a maximum matching $M_{3}$ from the subgraph
$G^{\prime}(U,\\{(u^{\prime},v^{\prime})\in A|u^{\prime}\in
U^{\prime},v^{\prime}\in U\\})$

16
$\mathbb{C}\leftarrow\mathbb{C}\cup\\{\texttt{edge\\_set\\_to\\_clustering}(M_{3})\\}$

17 $A\leftarrow A/M_{3}$

18

19

Output: Randomly return one element from $\mathbb{C}$ with probability
$|\mathbb{C}|^{-1}$

Algorithm 4 Graph decomposition into matchings

The function $\texttt{edge\\_set\\_to\\_clustering}(E)$ turns an edge set $E$
into a clustering design. If $(u,v)\in E$, then $u$ and $v$ are in the same
cluster. If $u$ is not covered by $E$, the $u$ itself is a cluster. The idea
of this algorithm is to decompose the graph $G(V,E)$ into clustering set
$\mathbb{C}=\\{\BFC_{1},\BFC_{2},...\\}$, such that each edge is covered by
exactly one cluster $C^{k}_{j}$ from a specific clustering $\BFC_{k}$.

The set $A$ represents the uncovered edges. In line 4, we found a vertex set
$U$ with the largest degree. In line 5, we found a maximum matching $M_{1}$
from the subgraph $G^{\prime}(U)$, thus an unmatched vertex in $U$ cannot be
adjacent to another unmatched vertex. In lines 6 to 9, we found edge set
$M_{2}$ such that each vertex in $V(M_{1}\cup M_{2})\cap U$ has exactly one
edge from $M_{1}\cap M_{2}$ incident to it. Also, the edges covered by
clustering $\texttt{edge\\_set\\_to\\_clustering}(M_{1}\cup M_{2})$ is exactly
$M_{1}\cup M_{2}$. After constructing a clustering from $M_{1}$ and $M_{2}$ in
line 10, we found the set of vertex $U^{\prime}$ without incident to
$M_{1}\cup M_{2}$. Since the graph $G^{\prime}(U,\\{(u^{\prime},v^{\prime})\in
A|u^{\prime}\in U^{\prime},v^{\prime}\in U\\})$ is bipartite and every
$u^{\prime}\in U^{\prime}$ has the same degree, the maximum matching $M_{3}$
we found in line 14 is always a perfect matching by Hall’s marriage theorem.
Thus, remove $M_{1}$ ,$M_{2}$ and $M_{3}$ from $A$ will strictly decrease
$\max_{v\in V}\texttt{degree}(v,A)$. Since the maximum degree of graph
$G(V,E)$ is $d$, the algorithm will terminate after at most $d$ while loops.
Also, once an edge is covered by a clustering, we directly remove it from the
uncovered edge set $A$, making each edge is covered exactly once.

Algorithm 4 decomposes a graph with maximum degree $d$ to at most $2d$ graph
matchings, such that each edge in $E$ is covered exactly once. This implies
that a maximum weight matching under the weights
$\\{v_{i,j}\\}_{i,j\in[n],i\neq j}$ is at least $(\sum_{i\in
V}\sum_{j\in\mathcal{N}_{i}}v_{ij})/{2d}$. ∎

## References

  * Andreev and Räcke, (2004) Andreev, K. and Räcke, H. (2004).  Balanced graph partitioning.  In Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pages 120–124.
  * Aronow and Samii, (2017) Aronow, P. M. and Samii, C. (2017).  Estimating average causal effects under general interference, with application to a social network experiment.  The Annuals of Applied Statistics, 11(4):1912–1947.
  * Bojinov et al., (2023) Bojinov, I., Simchi-Levi, D., and Zhao, J. (2023).  Design and analysis of switchback experiments.  Management Science, 69(7):3759–3777.
  * Bramoullé et al., (2009) Bramoullé, Y., Djebbari, H., and Fortin, B. (2009).  Identification of peer effects through social networks.  Journal of econometrics, 150(1):41–55.
  * Brennan et al., (2022) Brennan, J., Mirrokni, V., and Pouget-Abadie, J. (2022).  Cluster randomized designs for one-sided bipartite experiments.  Advances in Neural Information Processing Systems, 35:37962–37974.
  * Candogan et al., (2023) Candogan, O., Chen, C., and Niazadeh, R. (2023).  Correlated cluster-based randomized experiments: Robust variance minimization.  Management Science.  (forthcoming).
  * Chin, (2019) Chin, A. (2019).  Regression adjustments for estimating the global treatment effect in experiments with interference.  Journal of Causal Inference, 7(2):20180026.
  * Eckles et al., (2016) Eckles, D., Karrer, B., and Ugander, J. (2016).  Design and analysis of experiments in networks: Reducing bias from interference.  Journal of Causal Inference, 5(1):20150021.
  * Galil, (1986) Galil, Z. (1986).  Efficient algorithms for finding maximum matching in graphs.  ACM Computing Surveys (CSUR), 18(1):23–38.
  * Halloran and Struchiner, (1995) Halloran, M. E. and Struchiner, C. J. (1995).  Causal inference in infectious diseases.  Epidemiology, 6(2):142–151.
  * Harshaw et al., (2023) Harshaw, C., Sävje, F., Eisenstat, D., Mirrokni, V., and Pouget-Abadie, J. (2023).  Design and analysis of bipartite experiments under a linear exposure-response model.  Electronic Journal of Statistics, 17(1):464–518.
  * Hudgens and Halloran, (2008) Hudgens, M. G. and Halloran, M. E. (2008).  Toward causal inference with interference.  Journal of the American Statistical Association, 103(482):832–842.
  * Imbens and Rubin, (2015) Imbens, G. W. and Rubin, D. B. (2015).  Causal inference in statistics, social, and biomedical sciences.  Cambridge University Press.
  * Johari et al., (2022) Johari, R., Li, H., Liskovich, I., and Weintraub, G. Y. (2022).  Experimental design in two-sided platforms: An analysis of bias.  Management Science, 68(10):7069–7089.
  * (15) Leung, M. P. (2022a).  Causal inference under approximate neighborhood interference.  Econometrica, 90(1):267–293.
  * (16) Leung, M. P. (2022b).  Rate-optimal cluster-randomized designs for spatial interference.  The Annals of Statistics, 50(5):3064–3087.
  * Li and Wager, (2022) Li, S. and Wager, S. (2022).  Network interference in micro-randomized trials.  arXiv preprint arXiv:2202.05356.
  * Manski, (2013) Manski, C. F. (2013).  Identification of treatment response with social interactions.  The Econometrics Journal, 16(1):S1–S23.
  * Paluck et al., (2016) Paluck, E. L., Shepherd, H., and Aronow, P. M. (2016).  Changing climates of conflict: A social network experiment in 56 schools.  Proceedings of the National Academy of Sciences, 113(3):566–571.
  * (20) Pouget-Abadie, J., Aydin, K., Schudy, W., Brodersen, K., and Mirrokni, V. (2019a).  Variance reduction in bipartite experiments through correlation clustering.  Advances in Neural Information Processing Systems, 32.
  * (21) Pouget-Abadie, J., Saint-Jacques, G., Saveski, M., Duan, W., Ghosh, S., Xu, Y., and Airoldi, E. M. (2019b).  Testing for arbitrary interference on experimentation platforms.  Biometrika, 106(4):929–940.
  * Ross, (2011) Ross, N. (2011).  Fundamentals of Stein’s method.  Probability Surveys, 8:210–293.
  * Saveski et al., (2017) Saveski, M., Pouget-Abadie, J., Saint-Jacques, G., Duan, W., Ghosh, S., Xu, Y., and Airoldi, E. M. (2017).  Detecting network effects: Randomizing over randomized experiments.  In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1027–1035.
  * Sävje, (2023) Sävje, F. (2023).  Causal inference with misspecified exposure mappings: separating definitions and assumptions.  Biometrika, page asad019.
  * Sävje et al., (2021) Sävje, F., Aronow, P., and Hudgens, M. (2021).  Average treatment effects in the presence of unknown interference.  Annals of statistics, 49(2):673.
  * Tchetgen and VanderWeele, (2012) Tchetgen, E. J. T. and VanderWeele, T. J. (2012).  On causal inference in the presence of interference.  Statistical methods in medical research, 21(1):55–75.
  * Toulis and Kao, (2013) Toulis, P. and Kao, E. (2013).  Estimation of causal peer influence effects.  In International conference on machine learning, pages 1489–1497. PMLR.
  * Ugander et al., (2013) Ugander, J., Karrer, B., Backstrom, L., and Kleinberg, J. (2013).  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.
  * Ugander and Yin, (2023) Ugander, J. and Yin, H. (2023).  Randomized graph cluster randomization.  Journal of Causal Inference, 11(1):20220014.