Independent-Set Design of Experiments for Estimating Treatment and Spillover Effects under Network Interference

Consider a set of $n$ experimental units, labeled with $i=1,\dots,n$. Each of them is assigned with a treatment $Z_{i}\in\{0,1\}$, for which we denote $Z_{i}=1$ for treated, $Z_{i}=0$ for control, and $\bm{Z}:=(Z_{1},\dots,Z_{n})$ for the full treatment vector. Under Rubin’s framework of potential outcomes (Imbens and Rubin,, 2015), we assume $Y_{i}(\bm{Z})$ is the potential outcome of unit $i$ that would be observed if the units were assigned with the treatment vector $\bm{Z}$. We say ”unit $i$ is interfered by unit $j$” when $Y_{i}$ depends on $Z_{j}$, for $i\neq j$. All the pairwise interference relationships can be represented by a graph $\mathcal{G}=(V,E)$, where $V=\{1,\dots,n\}$ is the vertex set, and $(i,j)\in E$ if units $i$ and $j$ interfere with each other. Here, we assume all pairwise interference is symmetric such that $\mathcal{G}$ can be reduced to an undirected graph with each undirected edge representing the original bi-directed edges. The left panel in Figure 1 shows a diagram of 12 units and 18 interfering pairs.

Given the graph $\mathcal{G}$, we write the unit $i$’s potential outcome as $Y_{i}(Z_{i},\bm{Z}_{\mathcal{N}_{i}})$, where $\mathcal{N}_{i}:=\{j\in V:(i,j)\in E\}$ is the neighbor of unit $i$, and $\bm{Z}_{\mathcal{N}_{i}}:=(Z_{j})_{j\in\mathcal{N}_{i}}$ is the neighbor treatment (sub-)vector. Following Forastiere et al., (2021); Cai et al., (2022), we further assume that $Y_{i}$ depends on unit $i$’s neighbor through the proportion of treated neighbors, which is defined by

Assumption 1 assumes the interference on the proportion of treated neighbor assumption. In this paper, we simply write $Y_{i}(Z_{i},\rho_{i}):\{0,1\}\times[0,1]\rightarrow\mathbb{R}$ as the potential outcome of unit $i$.

Furthermore, for any two tuples $(z,\rho),(z^{\prime},\rho^{\prime})\in\{0,1\}\times[0,1]$, we define the unit-level causal effect as $\tau_{i}(z,\rho,z^{\prime},\rho^{\prime}):=Y_{i}(z,\rho)-Y_{i}(z^{\prime},\rho^{\prime})$, with certain special cases defined as

The direct effect measures the marginal effect of $z_{i}$ under a given level of interference. The indirect effect relates to the effect of interference and is often called “spillover effect”. The total treatment effect measures the change in outcome when all units are treated vs all units are control. Note that the total treatment effect can be decomposed as a combination of direct and indirect effects such that $\tau_{i}^{(t)}=\tau_{i}^{(d)}(0)+\tau_{i}^{(i)}(1,1,0)$.

Experimenters are usually interested in the population-level average effects, which are defined as $\bar{\tau}(z,\rho,z^{\prime},\rho^{\prime}):=n^{-1}\sum_{i=1}^{n}\tau_{i}(z,\rho,z^{\prime},\rho^{\prime})$. The average direct / spillover / total treatment effect are defined in a similar way. The average total treatment effect $\bar{\tau}^{(t)}$ is of particular interest because it measures the average change in outcomes when all units are assigned to treatment. Further discussions on causal effects under interference can be found in Forastiere et al., (2021).

We disentangle the unit-level treatments and the interference by partitioning the units $V$ into two sets $V_{I}$ and $V_{A}$. Let $\mathcal{G}_{I}=(V_{I},E_{I})$ be the sub-graph of $\mathcal{G}$ by restricting it to the vertex set $V_{I}$, and $\mathcal{G}_{A}=(V_{A},E_{A})$ be the sub-graph by restricting to $V_{A}$. Specifically, we require $\mathcal{G}_{I}$ to be a null graph such that $E_{I}=\varnothing$, or equivalently, $V_{I}$ is an independent set of $\mathcal{G}$. We call the counterpart $V_{A}$ as the auxiliary set. The middle panel in Figure 1 gives one such partition for the interference graph in the left panel. We will later see that the two sets play different roles in the inference.

Denote the treatment vectors on the independent set $V_{I}$ and on the auxiliary set $V_{A}$ by $\bm{Z}_{I}$ and $\bm{Z}_{A}$, correspondingly. Define the $|V_{I}|\times|V_{A}|$ interference matrix $\bm{\Gamma}$ between $V_{I}$ and $V_{A}$ by $[\bm{\Gamma}]_{ij}:=d_{i}^{-1}\mathbb{I}\{(i,j)\in E\}$, for all $i\in V_{I},j\in V_{A}$, where $d_{i}$ is the degree of unit $i$ in $\mathcal{G}$, and $\mathbb{I}\{\cdot\}$ is the indicator function. The interference vector on independent set $\bm{\rho}_{I}:=(\rho_{i})_{i\in V_{I}}$ is given by $\bm{\rho}_{I}=\bm{\Gamma}\bm{Z}_{A}$. Because $\bm{\Gamma}$ is a constant matrix when the graph $\mathcal{G}$ is observed, $\bm{\rho}_{I}$ is determined by the treatment vector $\bm{Z}_{A}$ of the auxiliary set. If we restrict our estimation to the independent set $V_{I}$, the unit-level treatments $\bm{Z}_{I}$ and the interference $\bm{\rho}_{I}$ can be separately controlled through $\bm{Z}_{I}$ and $\bm{Z}_{A}$, respectively. We call such a design ”independent set design”, which partitions the dataset into the independent set and the auxiliary set, controls the treatment and interference separately, and constructs an estimator based on the observed outcomes from the independent set.

The assignments for $\bm{Z}_{I}$ and $\bm{Z}_{A}$ can be designed to accomplish different causal inference goals. For example, to estimate the average direct effect $\bar{\tau}^{(d)}(\rho)$, one can assign $\bm{Z}_{I}$ by completely randomized design and optimize $\bm{Z}_{A}$ by minimizing $\|\bm{\Gamma}\bm{Z}_{A}-\rho\|_{1}$. To estimate the average indirect effect $\bar{\tau}(z,1,0)$, one can assign $Z_{i}=z$ for all $i\in V_{I}$ and optimize $\bm{Z}_{A}$ by maximizing $\mathrm{Var}[\bm{\Gamma}\bm{Z}_{A}]$. To estimate the average total treatment effect, one can optimize $\bm{Z}_{A}$ by maximizing $\mathrm{Var}[\bm{\Gamma}\bm{Z}_{A}]$ and let $Z_{i}=\bm{1}_{\{\rho_{i}>0.5\}}$ for all $i\in V_{I}$. In the right panel of Figure 1, we provide one such assignment of $\bm{Z}_{I}$ and $\bm{Z}_{A}$ for estimating the total treatment effect. We will discuss the implementations for different causal inference tasks in the next sections.

Two aspects are compromised in order to improve the data quality of the independent set. The first one is the sample size. Independent set design restricts the estimation to use only observations of the independent set, which is usually a fraction of the dataset, but of higher quality in estimation. The second aspect that is compromised is the bias from representativity of the independent set, because the average effect on the independent set is not necessarily identical to the one on the whole dataset. The unbiasedness is achieved when we assume the observed interference graph is random and is unconfounded with the potential outcomes. We discuss the assumptions in Section 4.1.

Before proceeding to different design implementations, we first give a greedy algorithm of finding a locally largest independent set in Algorithm 1. The independent set of a graph is not unique in general — any subset of an independent set is another independent set. For inference purposes, one would expect the variance of the estimator scales as $O(|V_{I}|^{-1})$. Therefore, the goal is to find the largest independent set, which is known as NP-hard (Robson,, 1986). In practice, we adopt the fast greedy algorithm that can find the local largest independent set in linear time.

In this section, we assume the two sets $V_{I}$ and $V_{A}$ have been obtained through the aforementioned greedy algorithm, and discuss the designs of the assignments on $\bm{Z}_{I}$ and $\bm{Z}_{A}$ for different inference tasks. For simplicity, we denote their sizes $|V_{I}|$ and $|V_{A}|$ by $n_{I}$ and $n_{A}$, respectively. Next, we discuss the estimations of direct treatment effect and spillover effect separately.

We first list a few more assumptions that are necessary for subsequent analysis.

In Assumption 2, we assume the sample units are i.i.d. from a super-population such that both $V_{I}$ and $V$ can be viewed as representative finite samples. Furthermore, if we denote $\bar{\tau}_{I}$ as the average causal effects on the independent set $V_{I}$, then under Assumption 2, we have $\mathbb{E}[\bar{\tau}_{I}]=\mathbb{E}[\bar{\tau}]$, which gives the unbiasedness of average causal effect on $V_{I}$ with respect to the (full) sample average effects.

Furthermore, we assume the network formation is independent of the potential outcomes in Assumption 3. Note that the greedy algorithm of finding the independent set in Algorithm 1, and the optimizations of $\bm{Z}_{A}$ as in (2) and (4) are not node-symmetric — vertices with different degrees have different probabilities of being assigned to $V_{I}$. It gives rise to the selection bias of the set $V_{I}$. By assuming the network unconfoundedness, the selection bias from a single sample is averaged if we consider multiple repetitions of sampling and network randomization.

The first question at hand is how large the set $V_{I}$ we can find from a random graph $\mathcal{G}$. There always exists such a graph that one can hardly find a large independent set (for example, the complete graph). Due to the randomness of graph $\mathcal{G}$, we can show such extreme cases occur with a negligible probability as $n\rightarrow\infty$. We consider the Erdös-Rényi random graph where each pair of units forms an edge with probability $p=s/n$ independently. The random graph has an expected average degree of $pn=s$. Note that most networks of interest (e.g. social networks) are connected and sparse networks. Therefore, we assume $s=o(n)$ for sparsity and assume $s=\Omega(\log n)$ for connectivity. Theorem 1 gives a lower bound on the size of the independent set $V_{I}$ resulting from Algorithm 1.

Note that Algorithm 1 is a greedy approximation in finding the locally largest independent set. Dani and Moore, (2011) discussed the size of the globally largest independent set for random graphs. The resulting independent set has a similar order of size compared to the globally optimal one. In the egocentric design (Saint-Jacques et al.,, 2019), the number of ego-clusters is upper bounded by $n/(s+1)$, which is smaller than ours by a factor of $\log s$.

In this section, we analyze the performance of the causal estimators for the tasks discussed in Section 3.3, and provide additional insights into the optimizations in (2) and (4).

First, we examine the performance of estimating average spillover effects for different designs. We run experiments on 50 Erdös-Rényi random graphs (Erdős and Rényi,, 1959) with $n=60,p=0.1$, and estimate the spillover effects. The potential outcomes are randomly generated by $Y_{i}(Z_{i},\rho_{i})=\alpha+\beta Z_{i}+\gamma\rho_{i}+U+\epsilon_{i},\ \forall i\in V$, and we let baseline $\alpha=1$, treatment parameter $\beta=20$, interference parameter $\gamma=5,10,15,20$, $U\sim\mathrm{Unif}(0,1)$ and $\epsilon_{i}\sim N(0,0.5)$.

Results are displayed in Figure 2. Independent set design outperforms all other methods to estimate the average spillover effects. At different levels of interference, IS design shows the lowest bias and variance. We notice that IS design is more stable than the other methods, the variance of IS design stabilizes at a very low level as spillover effects increase.

To introduce diversity, we run experiments on distinct random graphs: Erdös-Rényi (Erdős and Rényi,, 1959) $G(n,p)$ , Barabási–Albert (Barabási and Albert,, 1999) $G(n,m)$ and small-world (Watts and Strogatz,, 1998) $G(n,p)$. The potential outcomes are based on $Y_{i}(Z_{i},\rho_{i})=\alpha_{i}+\beta Z_{i}+\gamma\rho_{i}+\epsilon_{i},\ \forall i\in V$, and $\alpha_{i}=1,\beta=20,\gamma=10.$ $\epsilon_{i}\sim N(0,0.5)$. Each configuration is run 2,000 times. The results of estimating spillover effects are summarized in Tables 2. As shown in Tables 2, IS design outperforms all other methods on distinct settings and achieves the lowest bias and variance.

We next implement IS design to estimate average direct effects and evaluate the performance under various settings. Here, the potential outcomes are randomly generated according to $Y_{i}(Z_{i},\rho_{i})=\alpha_{i}+\beta Z_{i}+\gamma\rho_{i}+\epsilon_{i},\ \forall i\in V$, and we have $\alpha_{i}=1,\beta=20,\gamma=10$. $\epsilon_{i}\sim N(0,0.5)$. We run experiments 2,000 times and record the bias and variance of estimators. Table 3 shows the results of estimating average direct effects. In the presence of spillover effects, IS design achieves the best performance (the lowest bias and variance). When SUTVA is violated, network interference impairs the performance of conventional approaches. In this case, estimators in classical designs are biased to estimate average direct effects. In contrast, IS design could mitigate the spillover effects and improve performance by controlling treatment assignments on the auxiliary set.