Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
76,458 characters · 24 sections · 64 citation commands
Quasi-randomization tests for network interference
\abstract{ Network interference amounts to the treatment status of one unit affecting the potential outcome of other units in the population. Testing for spillover effects in this setting makes the null hypothesis non-sharp. An interesting approach to tackling the non-sharp nature of the null hypothesis in this setup is constructing conditional randomization tests such that the null is sharp on the restricted population. In randomized experiments, conditional randomized tests hold finite sample validity and are assumption-lean. In this paper, we incorporate the network amongst the population as a random variable instead of being fixed. We propose a new approach that builds a conditional quasi-randomization test. To build the (non-sharp) null distribution of no spillover effects, we use random graph null models. We show that our method is exactly valid in finite samples under mild assumptions. Our method displays enhanced power over state-of-the-art methods, with a substantial improvement in cluster randomized trials. We illustrate our methodology to test for interference in a weather insurance adoption experiment run in rural China.\\[8pt]}
A common assumption in causal inference is that of the Stable Unit Treatment Value Assumption (SUTVA). SUTVA assumes no dependence of a unit's outcome on another unit's treatment status. While this allows for unbiased treatment effect estimation and valid inferential strategies, there are many experimental and observational settings where interference between units takes place (cox1958planning). There are multiple pathways via which interference can take place in the population. It can result from the spread of treatment amongst the population units, the respective outcomes of treated units affecting the outcomes of others, or a combination of both. For example, the spread of a contagious disease depends on the number of infected people in the population (halloran1995causal). Thus, the estimation of any preventive measures taken will be challenged because of a likely SUTVA violation. Consider a population-level policy evaluation program, like an insurance product campaign (cai2015social). Due to social network ties in the population, information dissemination is a plausible interference mechanism that can occur and affect the evaluated estimates. Similar phenomena can be seen amongst experiments run on social media networks, like LinkedIn, or online marketplaces like eBay, owing to the interconnected nature of these platforms (pouget2019testing, blake2014marketplace). The total treatment effect, in such cases, can be decomposed into two effects, one of the direct effects and the other of spillover effects (sobel2006randomized).
The classical method for testing treatment effects is the “Fisher Randomization Test" or FRT (fisher1936design). FRT is used to test for a sharp null hypothesis of no treatment effect for all units in the population. The test exploits the imputability of counterfactuals under the null. Imputation enables the determination of the randomization null distribution of a test statistic of choice. If one were to test for spillover effects, it would render the null non-sharp, leading to imputability issues for the test statistic. There is a growing body of literature that addresses this issue by considering a fixed subset of units in the population and treatment assignment vector, called `focal units', such that on these focal units the null is sharp (aronow_estimating_2017, athey2018exact, toulis2019randomization). Such conditional randomization tests also lead to valid exact p-values, as with the Fisher Randomization Test. toulis2019randomization builds a permutation test under clustered interference. aronow_estimating_2017 and athey2018exact generalize the above for a given network and evaluate a range of non-sharp null hypotheses for testing. puelz2022graph presents a graph-theoretic approach to constructing the conditioning mechanism of selecting the focal units and the corresponding treatment assignment vectors for which the null is sharp. While the above considers the problem of testing for interference in an experimental setting, the literature on testing for spillover effects in an observational setting is still in its infancy.
This paper considers the network to be coming from a distribution itself. This idea expands upon the setup considered in the current methods, where the network is taken to be fixed. We draw a parallel here to estimating the probability of unit treatment assignment via propensity scores in the case of observational studies. The propensity of two nodes in a network being connected can be considered a function of their network characteristics, covariates, or both. This leads us to think of these linkages as coming from a generating process with an associated probability distribution. The current methods are based on strict randomization inference with no distributional assumptions for either the network or the potential outcomes, achieving a generalization of the Fisher Randomization Test. This allows for the widespread validity of the methods proposed. Since the experimenter cannot randomize this network, we explore how to incorporate appropriate stochastic assumptions on the network in the context of a conditional randomization test.
We assume that a given vector of sufficient statistics characterizes the network data-generating process and can thus be represented as an exponential random graph model. We first take the degree sequence of the graph as a sufficient statistic. Proposed in newman2001random, random graphs with arbitrary degree distribution represent real-world social networks closely owing to their ability to capture heterogeneity in degree. This assists us in building a quasi-randomization test based on the network distribution by randomizing over graphs from this generating process. We show that, conditional on the observed treatment, a test statistic's (quasi) randomization distribution leads to valid p-values. We then generalize the model to a vector of sufficient statistics and present a method that works for any set of such network statistics.
Model-based approaches with distribution assumptions on outcome model function have been previously considered in the literature for identifying and estimating peer effects (manski1993identification, manski2013identification, bowers2013reasoning, toulis2013estimation, blume2015linear). More recently, li2022random and leung2020treatment proposed estimation strategies for spillover effects under a distributional assumption on the network formation model. The inferential methods for the proposed estimation procedures involve asymptotic approximations (imbens2004confidence). Such large sample normal approximations of confidence interval conform to a Neymanian perspective.
In line with Fisherian procedures, our first contribution is to extend the random graph interference model into the potential outcome framework. We generalize and define sharp/non-sharp null hypotheses for random graph models. Building upon this, we develop a randomization-based test for a given random graph model. This leads to finite sample validity of the p-value obtained.
As a second contribution, we show that randomization tests based on network-generating processes lead to imputable test statistics under the null, conditional on the treatment assignment and network covariates. This overcomes a technical challenge in randomization methods based on random treatment assignment, where the null of no spillover effects is tested only upon the focal units (athey2018exact). In contrast, our method tests for a stricter class of nulls with no spillover effects on the given population.
Another hurdle the current methodologies face is low power. Determination of the conditional randomization distribution given a conditioning mechanism is not straightforward. The restriction of fixed focal units in the randomization null reduces the sample space of possible treatment assignment vectors in the null. It can lead to an enormous loss of power or render the null degenerate completely. A burgeoning literature set focuses on improving current methods by incorporating design-based techniques for selecting conditioning mechanisms (puelz2022graph, basse2019randomization). We show how incorporating information about network generation into the methodology can aid in power.
Our methods are also computationally feasible. We suggest that sufficient network statistics can characterize the random graph model. We first take a single sufficient statistic as the network's degree sequence and build a permutation test by generating the null over the set of graphs with the same degree sequence as the observed graph. Random graph generation of a prescribed degree sequence admits fast and efficient polynomial time algorithms for large graphs (viger2005efficient, fosdick2018configuring). Thus, we obtain valid randomization tests via the permutation of edges of the graph in a manner that preserves the degree sequence. We then present a method for a general exponential random graph model characterized by an arbitrary set of network statistics and build a permutation test by generating degree-preserving graphs in the same isomorphism class under the null. This is closely related to the literature on the random graph null model used in network analysis with applications in protein structure discovery and community detection among many (milenkovic2009optimized, sah2014exploring).
To illustrate our method, we re-analyze a randomized experiment in rural China where rice crop farmers are informed about a weather insurance product (cai2015social). The hypothesis is that farmers with a higher proportion of informed neighbors display an enhanced adoption rate. We display our methodology on a subset of the original experiment performed and obtain significant information spillover among the farmers.
Consider a population $\mathbb{P} = \{1,2,..., N\}$ where $N$ is the total number of units in the population. Consider a vector $Z \in {\mathbb{Z}}^N$ where each element in the vector indicates treatment assigned to the corresponding indexed unit in the population. Here, $\mathbb{Z}$ represents the set of possible treatments to which the population units can be exposed. We take $\mathbb{Z}=\{0,1\}$ for this article. Hence, any treatment assignment vector is an N-dimensional binary vector. We consider the population $\mathbb{P}$ to be connected via an undirected graph $G = (\mathbb{P},E)$ where $E \subseteq \mathbb{P}\times\mathbb{P}$. For distinct units $i$ and $j$ such that $(i,j) \in E$ represents a connection between the two units. With some slight abuse of notation, we also represent the graph's adjacency matrix by $G$. Thus, $G$ is an $N \times N$ binary matrix. Here, for some $i$ and $j$, $G_{ii} = 0$ and $G_{ij} = G_{ji}$ owing to $G$ being a undirected graph with no self-loops. If $G_{ij} = 1$, then we say unit $i$ and $j$ are neighbours. This can also be denoted by $i \in \mathcal{N}_{G}(j)$ or vice-versa. Here, $\mathcal{N}_{G}(i)$ represents all the neighbors of unit $i$ in graph $G$. We may write $\mathcal{N}(i)$ if the graph is clear in context. We define the total number of unit neighbors $i$ as the degree of $i$. This is denoted by $deg(i)$ and equals $|N(i)|$. We denote the distance between two units $i$ and $j$ as $dist(i,j)$. It is defined as the shortest path length between the two units. By convention, we take $dist(i, i) = 0$ and $dist(i,j) = \infty$ if no path exists between the two distinct units. Consider $\mathbb{P'}\subseteq \mathbb{P}$. We denote $G[\mathbb{P'}]$ as the sub-graph induced by $\mathbb{P'}$. That is, $G[\mathbb{P'}]=(\mathbb{P'},E')$ where $E' = \{(i,j)\in\mathbb{P'}\times\mathbb{P'}|\:(i,j)\in E\}$.
Each unit $i$ in the population is `characterized' by a set of pre-treatment or covariate vectors given by $X_i$, where $X_i$ is an m-dimensional vector. $X_i$ is fixed and influences the outcome via the network's potential outcome function or formation. Let $X$ denote the $ N\times M$ matrix where each row corresponds to the respective unit's covariate vector. Consider the treatment vector to be drawn from a probability distribution $P_{X}(Z, G): \{0,1\}^N\times \{0,1\}^{N\times N} \rightarrow [0,1]$. We define the conditional probability distribution $P(Z|G): \{0,1\}^N \rightarrow [0,1] \subset \mathbb{R}$ as $P_{Z|G}$. Let $Z_{obs}$ be the realized treatment drawn from the treatment assignment distribution $P_{Z|G}$. Consider the graph $G$ to be coming from the marginal probability distribution $P(G): \{0,1\}^{N \times N} \rightarrow [0,1] \subset \mathbb{R}$, denoted as $P_{G}$. We denote the observed sample from the distribution $P_G$ to be $G_{obs}$. We define the potential outcome function $Y:\{0,1\}^N \times \{0,1\}^{N \times N} \rightarrow \mathbb{R}^N$ as a real-valued function that takes treatment assignment and network adjacency matrix as arguments. We will consider $Y$ to be fixed, and each element $i$ of an image in $Y(Z, G)$, $Y_i(Z, G)$, denotes the outcome of the $i^{th}$ unit in the population under the treatment assignment $Z$ and network assignment $G$. We denote the corresponding potential outcome as $Y_{obs}$ that is, $Y_{obs} = Y(Z_{obs}, G_{obs})$. We note that the potential outcome function implicitly contains information in $X$ and can be written as $Y_{X}(Z, G)$. For the remainder of the article, we will use the notation $Y(Z, G)$ for readability unless deemed necessary.
The assignment mechanism defines the joint probability distribution of treatment assignment vectors given covariates and potential outcomes, denoted by $P(Z|X, Y(0), Y(1))$. The following are three key assumptions that are considered in the causal inference literature for assignment mechanism: (i) individualistic assignment, which restricts the treatment assignment of a unit to its covariates and outcomes (ii) probabilistic assignment, which assumes non-integer probabilities of treatment assignment to units (iii) unconfoundedness assumption, which restricts the dependence of the probability assignment of units to only covariates, and not the potential outcome (imbens2015causal). Given a well-defined potential outcome function, the individualistic assignment mechanism assumption constitutes Stable Unit Treatment Value Assumption (SUTVA). We argue that the underlying network structure among the population is an implicit form of treatment. Hence, we generalize the treatment to a bivariate treatment assignment vector $(Z, G)$. We assume that the joint treatment assignment is unconfounded; that is,
We formally define the standard sharp null hypothesis of no (direct) treatment effect when the population is not interconnected.
The above-stated null hypothesis imposes specified restrictions on the potential outcome function. Extending this to our setup, we get the following definition of the sharp null hypothesis.
We now define a test statistic that will be used for testing such null hypotheses. Following our setup, we will use the joint treatment assignment, $(Z, G)$, for the rest of the article.
Under the sharp null, given an observed outcome, $Y_{obs}$, we can impute the outcome function $Y$ for all treatment assignments. This is not possible when the null hypothesis is non-sharp. We formally define the non-sharp null hypothesis below.
Here, the subset restriction, denoted by $\textbf{Z}\times\textbf{G}:= \textbf{Z}_i\times\textbf{G}_i$, on treatment assignment is chosen by the null hypothesis of interest. We elaborate further using the testing null of no spillover effects example below. Consider the null hypothesis of no spillover effects if the distance between two units is at least k. \\
Note the non-imputability of the potential outcome function under the null considered above for different treatment assignments. Precisely, given $(Z_{obs}, G_{obs})$, we can compute potential outcomes for treatment assignments in the restriction set defined above. The null is not sharp since the restriction set is a strict subset of the treatment assignment space.
In this paper, we are concerned with testing first-order spillover effects. We take $k=1$ in Example (ref) and state the null hypothesis of no spillover effects below.
The treatment $G$ is unrestricted here, fixing the graph covariates. We claim that the null hypothesis, in the above, encodes no spillover effects (see Remark (ref)). We now describe the spillover mechanism as a component in the potential outcome function $Y(Z, G)$. In the following example, $Y(Z, G)$ is linearly separable into two components, one of direct effect and another of spillover effect, as stated below.
We restate the null hypothesis of no spillover effects, as described in Hypothesis (ref).
This approach of defining non-sharp nulls of spillovers in the literature is through the use of exposure functions (aronow_estimating_2017, toulis2019randomization, puelz2022graph). The exposure functions are functions of the treatment assignment vector, $Z$, such that restriction sets can be created on $Z$ by partitioning $Z$ on the range of the exposure function. We can define an exposure function in the above Example (ref):
We obtain the setup described in the literature, given a fixed $G$, using the above-described exposure function as a restriction set. The setup assumes a spillover mechanism via an exposure function. Since we consider the graph underlying the population to be random, we define restrictions on the joint treatment assignment in Hypothesis (ref). A spillover mechanism, if it exists, will be captured in the potential outcome function. We describe the currently proposed method in the literature of a conditional-randomization test procedure to obtain valid p-values using `focal units' (puelz2022graph).\\[5pt] Procedure 0: Consider $F$ as a subset of units and treatment assignment $Z$ such that a test statistic $T(Z|F)$ is imputable under the null.
The above-stated procedure holds finite-sample validity. The conditioning mechanism $F$, termed as focal units, is drawn from $P(F|Z_{obs})$, which the analyst should determine. We consider the random selection method as the conditioning mechanism to obtain the focal units. Procedure 0 tests for deviation from the null hypothesis of no spillover effect on focal units. This ensures the imputability of the test statistic $T(Z|F)$. We require the test statistic to be imputable to obtain its sampling distribution under the null, even though we observe only one treatment assignment vector. Below, we define the imputability of a test statistic for the joint treatment assignment.
The choice of a (imputable) test statistic is not unique, though, and different test statistics can lead to different powers of the test. This is determined by the test statistic's responsiveness to the null hypothesis.
We present the quasi-randomization test for the sharp null of no spillover effects. Our main idea is to generate the null sampling distribution of a test statistic by randomizing over the network-generating process. Intuitively, the underlying network structure also contains information about the spillover effect. This can also be seen in Hypothesis (ref) where the network variable $G$ is unrestricted in the, otherwise, non-sharp null keeping the network covariates fixed. Fixing direct treatment assignment and network covariates leads to the imputability of a test statistic of choice. To strictly generalize the conditional randomization test over focal units (athey2018exact), one can randomize over the network distribution of $G_{F^{c}}$, that is, over the non-focal units in the population. One feature of this generalization is that it ensures the network characteristics of the focal units remain fixed. One can, then, also randomize over the joint treatment assignment vector $(Z, G)$. This expands the state-of-the-art methods over the bivariate treatment assignment vector. The following method focuses on the conditional treatment assignment distribution of $G|Z$. We formally define the conditional test statistic, $T_c$, below and show its imputability under the null Hypothesis (ref).
We state our proposed quasi-randomization testing procedure below. The procedure assumes the knowledge of the network-generating process $P(G|G_{X})$. An elaborate consideration of the network distribution will be presented in Section (ref). \\[2pt] Procedure 1: Let $(Z_{obs}, G_{obs}, Y_{obs})$ be the observed joint treatment assignment and its corresponding outcome. Consider a test statistic $T(Z, G, Y_{obs})$.
The following theorem proves the finite sample validity of Procedure 1.
A crucial component of the proof is identifying the conditional distribution $P(G|Z, G_{X})$ for the validity of Procedure 1. This is contingent upon the experimental design, and different experimental designs will lead to different conditional randomization distributions. We compare this with the state-of-the-art methodology presented in Section (ref) where the null randomization distribution comes from $P(Z|F)$. Here, $F$ represents focal units. A common problem faced in the literature is the loss of power when implementing the methods in cluster randomized experiments. In a cluster-randomized experiment, the population is classified into clusters where treatments are assigned at the cluster level. If a cluster is treated, all units in that cluster receive the treatment or vice versa. Fixing the treatment assignment of units in the conditioning mechanism might render the null randomization distribution $P(Z|F)$ degenerate, given the restricted span of cluster treatment assignment space. For example, assume there is a focal unit in every cluster. Then, conditioning on the observed treatment of focal units, we obtain $Z|F =\{Z_{obs}\}$ since all the unit treatment assignments can be deterministically imputed by the treatment assignment of the focal unit in that cluster. This reduction in the support of the conditional distribution leads to either degeneracy or enormous loss of power. To get over this, our methodology captures the null distribution by randomizing over the conditional distribution $G|(Z, G_{X})$, where the null distribution admits ample support. We discuss this in Sections (ref) and (ref), where we identify the null randomization distribution under different experimental designs.
Here, we discuss how Procedure 1 can be implemented in different experimental designs. A change in experimental design corresponds to a change in (direct) treatment assignment mechanism. Thus, correctly identifying the distribution $P(G|Z)$ (and $P(G|Z, G_{X})$) is important to ensure the validity of Procedure 1. We find $P(G|Z)$ for two experimental designs, completely randomized experiments and cluster randomized experiments.
Consider a random sample of units of size $N_t$ from $\mathbb{P}$, which are selected in the treatment group. Let $N_t$ be fixed. Thus, the remaining units are in the control group. Let $N_c = N-N_t$ be the size of the units in the control group.
We remark that $G \!\perp\!\!\!\perp Z$ by design. Hence, for completely randomized experiments, $P(G|Z) = P(G).$ Since $P(G)$ is not identified by design, we will explore random graph models in Section (ref).
Consider the following partition of the population $\mathbb{P}$ into clusters $\{C_1,C_2,....,C_k\}$. That is, $ C_i \cap C_j = \emptyset \forall i\neq j \in [k],\ \ \cup_{i=1}^{k} C_i = \mathbb{P}.$ Given such a partition, treatment assignment is done at the cluster level instead of the unit level. Following ugander2013graph, we perform a Bernoulli experiment at the cluster level. Thus, we obtain $W_i \sim Bernoulli(p),\ \ Z_j = \sum_{i=1}^{k} W_i\cdot \mathcal{I}(j \in C_i).$ Here, $p$ is the probability that a cluster receives treatment, and the experiment is performed on a given cluster partition of the population. The cluster formation is part of the design of the experiment and is fixed. The experimenter can form these clusters based on the structure of the underlying network. Benchmark graph clustering algorithms can be used to obtain the cluster partition, which depends on graph characteristics such as modularity, cuts, and other related quantities (newman2006modularity). We use $\epsilon$-net clustering to obtain the cluster partition of the network, previously considered in eckles2017design and ugander2013graph. We describe the $\epsilon$-net clustering in detail in Supplementary material (ref). While we present a deterministic version of the clustering procedure, it should be noted that any other algorithm, such as a different selection rule and the resultant $\epsilon$-net cluster output, corresponds to a change in experimental design. Unlike completely randomized experiments, in cluster randomized experiments, $G \not\!\perp\!\!\!\perp Z$. So,
Here, we can see that identifying a null randomization distribution becomes challenging in the case of graph cluster randomization experiments. We propose a new approach that considers sufficient statistics of the random graph model to build a permutation test.
Identification of null randomization distribution $P(G|Z, G_{X})$ involves knowledge of the distribution of the network-generating process, which is not identified by the design of the experiment. To this end, we explore random graph models to model $P(G)$. As discussed in the previous section, identifying the null randomization distribution becomes challenging in cluster-randomized experiments. This challenge is overcome in our proposed methodology, which is a conditional permutation test. We discuss this in Section (ref).
This section describes various random graph models based on which $P(G)$ can be modeled. The Erdős-Rényi random graph model has been studied widely, owing to exact computations of desirable graph properties. We present the model formally in Supplementary material (ref). However, the Erdős-Rényi random graph model does not represent most real-world networks, such as social networks, supply-chain networks, and scientific collaboration networks, among many others. We look at a generalization of Erdős-Rényi random graph better at modeling such real-world networks, proposed by newman2002random, in Section (ref).
To represent more realistic degree distributions observed in real life, newman2001random considered characterizing the random graph by its degree distribution. We formulate the model below.
A key feature of random graphs with arbitrary degree distribution is their ability to capture a large class of degree distributions. This generalizes the Erdős-Rényi random graph model and, at the same time, ensures tractability of important structural graph properties (newman2002random). To deploy Procedure 1, we must identify $P(G)$. This involves estimating $(p_1,p_2,...,p_N)$ with a single realization of the graph, and we cannot directly implement Procedure 1 without estimating $P(G)$. In the case of random graphs with arbitrary degree distribution, it is proven that we can estimate the parameters of the random graph with just one realization, but with some uncertainty (chatterjee2011random). However, there might be other relational dependencies characterizing the formation of the network that are not captured by random graphs with arbitrary degree distribution. For example, the phenomena of transitivity are not captured in this model, where two nodes have higher chances of being connected if they have a common connecting node.
The state-of-the-art method for characterizing random graph formation of social networks is through the exponential random graph model or ERGM (snijders2006new). It is a generalization of the random graphs with arbitrary degree distribution, where the characterization of the distribution of the random graph is through a set of given sufficient statistics. This could also contain information about covariates to capture homophily in the network formation process. In this article, we consider the random graph formation free of covariates.
Common sufficient statistics used in the literature for the characterization of social networks include the number of edges, the number of triangles, and the number of stars of different sizes, say stars of size two or stars of size three (robins2007introduction). It is important to carefully choose the model as an ill-posed ERGM can lead to near degeneracy (chatterjee2013estimating, schweinberger2020exponential). As with random graphs with arbitrary degree distribution, estimating ERGM is fraught with challenges, given just a single realization.
Owing to estimation issues of the null distribution, we propose a new method that does not involve such estimations and reduces to a simple permutation test. In our proposed methodology, we first consider the sufficient statistics of the random graph distribution as the degree sequence and develop a method conditioning on the sufficient statistic. We then generalize the method to a set of arbitrary sufficient statistics. We use the symmetric nature of the $P(G)$ via an equivalence relation and build a conditional permutation test, as described below.
Here, we present our main result, which proposes obtaining a conditional randomization test without estimating the distribution. Our main idea is to identify a sufficient statistic for the random graph model, which is the degree sequence in the case of random graphs with arbitrary degree distribution, and condition on this sufficient statistic. We sample the null distribution over all the graphs with the same degree sequence as the observed graph. We obtain a permutation test using the equiprobability of the event set of all the graphs with the same degree sequence. We now formally present the definitions below and proceed to state and prove the finite sample validity of the proposed method.
We define the degree sequence of a graph $G = (V, E)$.
Not all $D \in \mathbb{W}^N$ can be a valid degree sequence. For example, consider $D = \{1,2\}$ as a candidate for a degree sequence for a graph of size $2$. We remark that the maximum degree of a node in the graph is at most $(N-1)$. Since no vertex in a graph of size two can have a degree of more than 1, $D$ is not a valid degree sequence. Note that graphs with the same degree sequence are not necessarily isomorphic graphs. This implies that the graph's vertices cannot be permuted to obtain the other graph with edges preserved (see Figure (ref)).
The converse holds. Consider a set of distinct graphs with the number of units fixed to $N$ and a degree sequence of the graphs fixed to a valid degree sequence $D$. Then, this set of all graphs with degree sequence $D$ will form an equivalence class, and we can partition the space of all random graphs with this equivalence relation. We define this below.
It is a quick check that $d$ defines an equivalence relation. Hence, we can partition the support of $P(G)$, where each part represents an equivalence class of $D$.
Procedure 2: Let $(Z_{obs}, G_{obs}, Y_{obs})$ be the joint treatment assignment vector and its corresponding outcome. Consider a test statistic $T_c(G|Z_{obs}) := T(Z_{obs},G,Y_{obs})$.
As a corollary, we can substitute any subclass of the degree sequence equivalence class in Procedure 2, and the finite-sample validity of the Procedure is retained. For example, we can take the equivalence class to be all the graphs isomorphic to the observed graph, or automorphic to the observed graph in the second step of Procedure 2. We present results for both these Procedures in Section (ref).\\ We emphasize that generating graphs with a given degree sequence admits a polynomial-time algorithm. Given fixed parameters like the maximum degree of the graph, one can use state-of-the-art algorithms to efficiently sample graphs with a given degree sequence uniformly from the space of all the graphs with the same degree sequence (arman2021fast). It has been shown that the size of this equivalence class can be exponentially large (barvinok2013number). It should be noted that one should use a uniform sampler to avoid introducing any bias in the null distribution attributed to sampling. We can also overcome this by effectively taking many samples to approximate the null distribution.\\
We generalize the above method to a class of exponential random graph models where the sufficient statistics of the model are permutation invariant. We can take the graph covariate vector, $G_{X}$, to be the same set of statistics. To sample graphs from $G|G_{X}$, we can condition on the graph automorphism class and generate the null cases from this class. One caveat is that the size of an automorphic graph class may not be large depending on the symmetry of the graph observed (erdos1963asymmetric). To overcome this, we explore sampling approximate automorphic graphs. We fix the graph covariate to be the degree of a unit, and sample isomorphic graphs that preserve the degree sequence for the null cases. To achieve more generality, one can specify the graph covariate vector of interest and explore advanced graph sampling or rejection sampling techniques. We formally present the results below.
A graph is considered isomorphic to another graph if a one-to-one correspondence between the vertices of the two graphs preserves the edges between the graphs. Below, we present an equivalence condition for the same.
We note that graph isomorphism defines an equivalence relation. The permutation matrix comprises row binary vectors indexed by the one-to-one correspondence between the vertices of the graphs. We now define a class of exponential random graph models based on the permutation invariance property of its sufficient statistic.
Many sufficient statistics used in real-life social network modeling follow this property. As discussed, some graph statistics include the number of triangles, degree sequence, and number of stars of size two, and they are permutation invariant. We model the data-generating process as an exponential random graph with a permutation invariance property and present a permutation testing procedure.\\[2pt] Procedure 3: Let $(Z_{obs}, G_{obs}, Y_{obs})$ be the joint treatment assignment vector and its corresponding outcome. Consider a test statistic $T_c(G|Z_{obs}) := T(Z_{obs},G,Y_{obs})$.
The choice of the test statistic is not unique, and the validity of the proposed test is upheld for any choice of test statistic. Test statistics capture departures from the null distribution, and better-suited test statistics in responding to deviations from the null will improve the power of the test. Here, we propose a variation of the Has-Treated-Neighbour test statistic considered in athey2018exact. This looks at the difference in average treatment effect amongst control units with at least one treated neighbor and control units with only control units as neighbors. Let $T_{I_c}(G|Z_{obs}) =$
The above test statistic considers the spillover on the control units from the treated. Under the null of no spillover effect for all the units regardless of direct treatment status, one can also define the above test statistic for the treated units. Similarly, let $T_{I_t}(G|Z_{obs})$ equals
We now define the test statistic, denoted by $T_I(G|Z_{obs})$, for testing the spillover effect for all the units. It will be a weighted average of the two test statistics defined above.
It should be noted that the above test statistics can only be defined if the sub-populations under consideration are non-empty. For example, if no control unit exists with all neighbors in control or the number of such units is few, we deal with either a definition or a power issue. Thus, we propose a generalization of the above-stated test statistic for robustness. We look at the difference in average treatment effect among control units with a greater than 0.75 quantile of the proportion of treated units and control units with a less than 0.25 quantile of the proportion of treated units. Let $T_{quant_c}(G|Z_{obs}) =$
Here, $p_{0.25}$ and $p_{0.75}$ represent the first and the third quartile of the vector
$P_{0.25}$ and $P_{0.75}$ represent the set of elements in $P$ in the first and third quartile, respectively. In a similar fashion to the test statistic $T_I(G|Z_{obs})$, we define the above for treated units and take a weighted average for the two test statistics to obtain $T_{quant}(G|Z_{obs})$.
We remark that one can potentially improve the test statistic with the knowledge of appropriate covariates or nodal attributes. This can be incorporated by considering regression-adjusted test statistics taking residuals for the potential outcome (rosenbaum_observational_2002). One can also build test statistics based on models for interference structures. For example, parametric test statistics can be constructed of the linear-in-means model of interference proposed by manski1993identification. We also consider more test statistics, given that the choice is not unique, and different test statistics would differ in their power. We take the test statistic proposed in bond201261, which takes the difference between the average over all the edges where the neighbor is a treated or control unit.
We present Monte Carlo simulations to validate our proposed testing procedure. We consider two test statistics, one that is based on the quantile of the proportion of treated neighbors in the simulations and another that is weighted by treated neighbors (first proposed in bond201261), as discussed in Section (ref). The following subsection will describe the data-generating process and the general setup. We conduct the simulation study for two experimental designs, namely, completely randomized experiments and cluster randomized experiments. As a robustness check, we repeat the study for two network-generating processes.
We now present the data-generating process considered in the simulations. Our potential outcome function is linearly separable into direct treatment effect and spillover effect. The spillover mechanism is a function of the unit's neighbors' direct treatment assignment. The potential outcome function also has an additive heterogeneous effect coming from a network-based property, free of a direct treatment assignment vector. We propose the mechanism to be contingent upon the proportion of treated neighbors.
We note that $\epsilon_i$ can be viewed as the baseline level of outcomes for all the units if they were untreated. Without loss of generality, we take the mean of the normal distribution to be zero, but it can be arbitrarily chosen. We first present the setup for a completely randomized experiment. The treatment assignment vector is chosen by randomly sampling $N_t$ units out of $N$ units and assigning them treatment (that is, $Z_i = 1$ for all $i$ corresponding to units in the random sample). We state that $N_t$ is fixed and pre-determined by the experimenter. In the performed simulations, we have $599$ total units and $300$ treated units in the model in one case. We study the setup for two generating processes: small-world networks and the stochastic block model. Both models exhibit a high degree of clustering, characterized by the clustering coefficient. The clustering coefficient is the number of connections in a randomly chosen node and its neighborhood relative to the total number of connections possible. Consider a regular graph where all the nodes have the same cardinality of connections. Let us denote the number of connections a unit has in a regular graph by $K$. Such graphs have a high clustering coefficient, but the distance between two nodes in such graphs is also high. The average distance between two nodes in real-life networks is low (amaral2000classes). To obtain a graph with a high degree of clustering but a low average path length, one can rewire the edges of a $K$-regular graph with some probability, say $p$. This parametrization characterizes a small-world network. The higher the rewiring probability, the lower the average path length. Another class of random graph models that achieves the same property of a high clustering coefficient but a low average path length is that of the stochastic block model. Consider a graph of size $N$ with a partition of nodes. The size of the parts are $\{n_1,n_2,...,n_K\}$. These parts represent clusters in the graph, and we can model a random graph using them by defining the probability of an edge between nodes within a part and between two parts. Hence, we obtain a probability (symmetric) matrix of size $K\times K$. Note that because we also want a high degree of community structure in the graph, the diagonal elements of the probability matrix are typically higher than the off-diagonal elements. The probability matrix is also called the preference matrix in the literature. We also have a coefficient of network dependence in the potential outcome model, denoted by $\beta_{\text{deg}}$. We take $\beta_{\text{deg}} = 0$ in Table (ref) for a comparative study with the state-of-the-art literature (athey2018exact). We now define the setup for the simulation study:
The null distribution was generated by sampling 1000 graphs with the same (labelled) degree sequence as the observed graph, and degree-preserving isomorphic to the observed graph in a second option. {
}
\footnotetext[1]{We reported the number presented in athey2018exact. We obtained a rejection rate of 0.073 in our replication.} \footnotetext[2]{We obtain the same rejection rate in our replication as reported in athey2015exact.} The p-value is calculated as the sample proportion of times the imputed test statistic for the sampled graph realizations is more than the observed test statistic. We reject the null hypothesis if the p-value obtained is less than the chosen significance level of 0.05. We replicated the above-described setup 4000 times and calculated the proportion of times we rejected the null. We present this result, namely rejection rate, in the Table (ref). For robustness, we perform the simulations for two network-generating processes. We obtain the rejection rates for the same setup for the procedure proposed by athey2018exact. We implement random focal vertex selection and show our results for the Edge-Level-Contrast test statistic (athey2018exact). We label this test as `Conditional Focal Test'.
We then perform the simulations for a cluster-randomized experimental setup. We present the results in Table (ref). The total number of units in the simulation is the same as before, that is, 599. We obtain the clusters in the graph by implementing the epsilon-net clustering algorithm, described in Algorithm 1 (Supplementary material (ref)). We take epsilon to be equal to 3. This implies all the clusters contain units less than three hops away from each other, whereas the between-cluster distance is at least three hops for any two units. We take the probability of treating a cluster to be 0.5. We implemented a Bernoulli trial at the cluster level. Under Procedure 3, the null distribution is approximated by taking 1000 samples of graphs isomorphic to the original graph, such that the corresponding subgraphs on treated units and controlled units remain isomorphic and the labelled degree sequence remains preserved. This is obtained by considering permutations where treated units can be mapped only to treated units (thus, control units can only be mapped to control units), and mapping only occurs amongst two units with the same degree. We replicated this setup 4000 times and calculated the proportion of times the proposed test rejected the null. We label Procedure 3 as `Block Isomorphism Permutation Test' in Table (ref). This was performed for the two network-generating processes as before. {
}
For robustness, we also perform simulations for the setup where there is a dependence of the potential outcome function on the graph, devoid of direct treatment assignment. For this, we set $\beta_{\text{deg}}=0.4$, installing a positive correlation with the degree of the unit and its corresponding potential outcome. We present the results in Table (ref). The simulations are replicated for both the completely randomized experiment and the cluster randomized experiment. The procedures deployed are the degree-preserving isomorphism permutation test and the degree-preserving block isomorphism permutation test. The rest of the setup remains the same as before. {
}
We see that our proposed methods have type 1 error controlled appropriately. This corresponds to rows with $\tau_{spill}$ equal to zero in Tables (ref), (ref), and (ref). When $\tau_{spill}$ equals 0.4, our method performs with competitive power compared to existing methods in the literature (athey2018exact). We highlight the $\tau_{direct}$ equal to 4 and $\tau_{spill}$ equal to 0.4, where our method significantly improves. The significance of the setup lies in its resemblance to many naturally occurring settings, where the direct effect is meaningfully more than the spillover effect (for example, see cai2015social). We see in Table (ref) that our proposed method boosts power when the clustering of the network-generating process increases, as with the stochastic block model. This contrasts with the method proposed by athey2018exact, where the method does not retain power. In Supplementary material (ref), we add more insights on the performance of the $T_{bond}$ test statistic as observed in Table (ref).
An interesting result is in the case of cluster-randomized experiments, where a higher degree of clustering shows a drop in power. This can be observed when comparing the power values of the small-world network to the stochastic block model. This may be attributed to a reduction of sample space of imputed values of the test statistic. Hence, a higher degree of clustering increases the cluster sizes, restricting the direct treatment assignment. For instance, an observed graph in the case of the small-world network had 16 clusters, compared to 11 clusters in the case of the stochastic block model.
We also perform the simulation study for cluster randomized experiments for the methods proposed in athey2018exact and puelz2022graph. As discussed in Section (ref), we encounter the degenerate null distribution and do not present the corresponding results. This is more prominent in the method proposed by athey2018exact, compared with puelz2022graph. Since puelz2022graph considers the experiment's design when selecting focal units, we see more robustness of the biclique test (puelz2022graph) where degenerate null distributions are reduced in frequency. Overall, our method is more robust to degeneracy and performs well in terms of power in our simulations. We also see that the $T_{bond}$ test statistic performs slightly better than the $T_{quant}$ test statistic in some cluster-randomized setups. This may be attributed to $T_{bond}$ being weighted by treated numbers in the graph instead of the corresponding quantile-based weights in $T_{quant}$ and the heterogeneity of the clustered assignment setup. We emphasize that $T_{bond}$ in conjunction with our methodology continues to be valid regardless of the size of the direct effect. The method proposed by bond201261 does not work for settings with non-zero direct effects (Refer athey2018exact for an elaborate discussion). Our method also retains the same power with graphical confoundedness of the potential outcome function, as shown in Table (ref) where $\beta_{\text{deg}}$ = 0.4.
We re-analyze a field experiment conducted in rural China on rice crop farmers studying neighborhood interference effects (cai2015social). The research motive behind the experiment was to see if social networks among the farmers have any influence on weather insurance adoption. The experiment involved intensive training sessions to promote crop insurance products to farmers against extreme weather. A primary goal of the experiment was to identify if there is information dissemination in the farmers' community and, if so, what mechanisms drive these information exchanges. These are important questions to be answered in this setting, as they are consequential to government policy action. A deeper understanding of insurance product adoption via social network mechanisms helps devise a more cost-effective government policy campaign to enhance product adoption among the target community. An important reason to study interference in such a setup is to avoid biased estimates and accurately evaluate policy performance measures.
We discuss the experimental design setup by the researchers. Researchers hypothesize that access to better information about weather insurance products would increase the adoption of the product in the rice farmers' community. To capture access to information differentially as treatment and control, two types of information sessions were created: simple sessions of 20 minutes, which provided an introduction to the insurance contract, and intensive sessions of 45 minutes that covered the insurance contract in much more detail, including explaining to them what the benefits are of taking up insurance. To capture information dissemination across the social network, these sessions were conducted in two rounds with a gap of 3 days. The idea behind this setup is to allow the farmers some time to discuss the insurance product among themselves. The interference effect is identified by examining whether households in round 2 with more friends who received intensive sessions in round 1 displayed an enhanced insurance take-up rate. Second-round participants were further randomized into three groups. After the round 2 sessions, the first group was given no additional information, the second group was told about the overall take-up rate in the previous round, and the third group was told in detail about who purchased the product and who did not. The randomization of the second group was done to derive the primary information diffusion mechanism. For illustration purposes, we do not analyze this part of the experiment.
There were 4902 households across 47 different villages in the experiment. A village's social network is known and assumed to be independent between two distinct villages. Each household is randomized among the 4 different groups: (i) Receiving a simple session in Round 1, (ii) Receiving an intensive session in Round 1, (iii) Receiving a simple session in Round 2, (iv) Receiving an intensive session in Round 2. After the session ends, the households decide to purchase insurance. This is captured as a binary outcome variable of the model, with 1 indicating a purchase decision made and 0 when no purchase is made. Under the assumption that no information diffusion can occur between participant households of Round 1 because of the immediate purchase decision the household had to make, we can assume there are no edges among the household participants in Round 1.
In our analysis, we take all the households receiving simple sessions under the control group and intensive sessions under the treated group. Since spillover can only occur from the treated group of Round 1 to the control group of Round 2, we only consider the network structure amongst these two groups in our study. This includes network structure among households in Round 1 and Round 2 only. Our analysis was run on 433 households of randomly chosen villages in the experiment, of which 222 were in the treated group. We ran our proposed Procedure 2, the degree permutation test, and approximated the null distribution by taking 10,000 samples of graphs with the same degree sequence as the observed graph. We obtained a p-value of 0.0002, which indicates the presence of interference.
We develop a new methodology to test for the non-sharp null hypothesis of no spillover effect in an experimental setup. Our proposed method assumes natural distributional conditions in the network-generating process to build a quasi-randomization test. While promising, several open problems remain. Incorporating covariates or nodal attribute information to characterize the random graph null model better may help enhance the power of the test and is an interesting direction for future work. The possibilities of incorporating advanced graph theoretic sampling techniques, and their effect on power, are another interesting line of pursuit. We also assume fully and correctly specified information about the given network. Analyzing the random graph null models under partial information and network misspecification is another exciting avenue for future work. Finally, our focus in this paper has been on randomized experiments exclusively. Since the sampling of null distribution is based on quasi-randomization of the network-generating process, a natural and essential extension is to study random graph null testing procedures in observational studies.\\
We thank Avi Feller, Fabrizia Mealli, Panos Toulis, ACIC 2024 conference participants, and the Tom Ten Have Award committee for their encouragement and feedback. We also thank Sai Sriramya Gorripati, Parshuram Hotkar, Sumit Kunnumkal, and ISB seminar participants for their enthusiasm and comments. We gratefully acknowledge Hemanth Kumar and the ISB Institute of Data Science for providing cluster access. The IMS 2024 ICSDS Student Travel Award partially supported Supriya Tiwari’s research. Pallavi Basu’s research is partially supported by the SERB MATRICS award MTR/2022/000073.
The Supplementary Material contains proofs, additional simulation results, and algorithmic details.