The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
83,027 characters
Network Synthetic Interventions: A Causal Framework for Panel Data Under Network Interference
\maketitle
\ifarxiv
\begin{abstract}
\else
\ABSTRACT{
\fi
We propose a generalization of the synthetic controls and synthetic interventions methodology to incorporate network interference.
We consider the estimation of unit-specific potential outcomes from panel data in the presence of spillover across units and unobserved confounding.
Key to our approach is a novel latent factor model that takes into account network interference and generalizes the factor models typically used in panel data settings.
We propose an estimator, \emph{Network Synthetic Interventions} (NSI), and show that it consistently estimates the mean outcomes for a unit under an arbitrary set of counterfactual treatments for the network.
We further establish that the estimator is asymptotically normal.
We furnish two validity tests for whether the NSI estimator reliably generalizes to produce accurate counterfactual estimates.
We provide a novel graph-based experiment design that guarantees the NSI estimator produces accurate counterfactual estimates, and also analyze the sample complexity of the proposed design.
We conclude with simulations that corroborate our theoretical findings.
\ifarxiv
\end{abstract}
\else
}
\fi
\section{Introduction}\label{sec:intro}
There is growing interest in the identification and estimation of causal effects in the context of spillover on networks, in which the outcomes of a unit are affected by the treatments assigned to other units, known as the unit’s ``neighbors.''
Here, a unit could be an individual, customer cohort, or region, and correspondingly, treatments could be recommendations, discounts, or legislation.
For example, whether an individual gets COVID-19 is a function of not only the individual’s vaccination status but also the vaccination status of that individual’s social network.
In the setting of e-commerce, the number of goods sold of a particular product is a function of not only whether that product gets a discount, but the discount level of other products that are substitutes or complements of it.
That is, there is \emph{network interference}.
In this work, we focus on network inference with {\em panel data}, a ubiquitous manner in which data is structured, where we collect multiple measurements of different units, and each unit can undergo a different sequence of treatments.
See Figure \ref{fig:panel_data_intro} for an example of panel data and the type of causal question we are interested in.
Causal inference with panel data has recently received significant attention, and a popular class of estimators in such settings are known as \emph{matching estimators}, where one represents the outcomes of one unit as some combination of other units to answer counterfactual questions.
Such estimators have been very popular in practice due to their flexibility and simplicity in addition to the fact that they provide valid causal estimates under unobserved confounding with appropriate assumptions.
Some examples of matching estimators with panel data include Difference-in-Differences (DiD) \citep{bertrand2004much}, Synthetic Controls (SC) \citep{abadie2021using}, and variants thereof.
However, such matching estimators rely on the Stable Unit Treatment Value Assumption (SUTVA), which implies that there is no spillover across units, i.e., the treatment applied to one unit does not affect the outcomes of other units.
Failing to account for spillovers can lead to
biased estimates.
We propose a novel latent factor model---which is a generalization of models studied in the panel data literature---that accounts for network interference.
Given this model, we establish an identification result where the counterfactual potential outcome for a given unit and its neighbors can be written as a linear combination of the observed outcomes of a carefully selected set of other units.
This identification result leads to a natural estimator, which we call \emph{Network Synthetic Interventions (NSI)}, a simple two-step procedure, that estimates the mean counterfactual potential outcome for a given unit.
We then show that, given our latent factor model, the NSI estimator is finite-sample consistent and asymptotically normal under suitable conditions.
NSI and our analysis of it can be viewed as a generalization of the Synthetic Interventions \citep{agarwal2020synthetic} and, in turn, Synthetic Controls frameworks to account for network interference.
\begin{figure*}[t]
\centering
\includegraphics[width=\textwidth]{images/panel_data_1.pdf}
\caption{
Panel data setting illustrated via an online retail example.
Each row corresponds to a product (or unit).
Each column corresponds to a week (or measurement).
A discount (the treatment) is applied to each product each week.
In this work, we ask questions of the form:
Given every product's sales numbers across time and under various discounts,
what would the sales numbers (i.e., potential outcomes)
have been for a specific unit, like Product \#2, under a different set of end-of-year discounts?}
\label{fig:panel_data_intro}
\end{figure*}
We furnish two validity tests that verify whether the treatment assignment pattern and the observed data have enough variation such that valid counterfactual estimates can be produced.
Motivated by these tests, we provide a novel graph-based experiment design.
To explain the efficacy of the experiment design and the NSI estimator, we consider the setting of a regular network graph with degree $d \geq 2$.
We show that the proposed experiment design requires only $O(d^3)$ training samples in order to guarantee that the training data has enough variation such that it is possible
to generalize to a given target counterfactual treatment.
Further, NSI obtains an estimate within error $\varepsilon$ with high probability under the proposed experiment design when $O\big({\sf poly}(d) / \varepsilon^4\big)$ training samples per unit are available.
This is a significant improvement over the $O({\sf exp}(d) / \varepsilon^2)$ training samples that a naive procedure would require.
We conclude with simulations showing that NSI is robust to spillovers under which existing estimators are biased.
\subsection{Related work}\label{sec:related_work}
The literature on causal inference with network interference or spillover effect has mostly considered the setting of a single measurement per unit, whether in the setting of a randomized experiment or an observational study.
Under fully arbitrary interference, it has been shown that it is impossible to estimate any desired causal estimands as the model is not identifiable \citep{Manski13, AronowSamii17, BasseAiroldi17, karwa2018systematic}.
Subsequently, various models have been proposed in the literature that impose restrictions on the exposure functions \citep{Manski13, AronowSamii17, viviano2020experimental, auerbach2021local, li2021causal}, interference neighborhoods \citep{UganderKarrerBackstromKleinberg13, bargagli2020heterogeneous, SussmanAiroldi17, pmlr-v115-bhattacharya20a}, parametric structure \citep{ToulisKao13, BasseAiroldi15, cai2015social, GuiXuBhasinHan15,EcklesKarrerUgander17}, two-sided platforms \citep{johari2022experimental, bajari2021multiple} or a combination of these, each leading to a different solution concept.
A comprehensive review on network interference models is given by \cite{de2017econometrics}.
In this work, we focus on network interference that is additive across the neighbors, referred to in the literature as the joint assumptions of neighborhood interference, additivity of main effects, or additivity of interference effects \citep{SussmanAiroldi17, yu2022graph, cortez2022exploiting, cortez2022graph}.
Distinct to our work is that we consider a {\em panel data} setting in which there are multiple measurements (e.g., a time series) for each unit.
The potential outcomes function is thus also dependent on both the unit and the measurement.
Additionally, we allow for the estimation of unit-specific counterfactuals under {\em multiple treatments}, whereas the existing literature has largely focused on binary treatments.
Key to our approach is a novel latent factor model that takes into account network interference and is a generalization of the factor models typically used in panel data settings.
Previous work has focused on causal estimands that capture population-level effects, such as the average direct treatment effect (the average difference in outcomes if only one unit and none of its neighbors get treated \citep{BasseAiroldi15, JagadeesanPillaiVolfovsky17, SavjeAronowHudgens17, SussmanAiroldi17, leung2019causal, ma2021causal}) and the average total treatment effect (the average difference in outcomes if all units get treated versus if they do not \citep{UganderKarrerBackstromKleinberg13, EcklesKarrerUgander17, chin2019regression, yu2022graph, cortez2022exploiting, cortez2022graph}).
Alternately there has been some literature that focuses on hypothesis testing for the presence of network interference \citep{Aronow12, BowersFredricksonPanagopoulos12,AtheyEcklesImbens17,PougetAbadieSaveskiSaintJacquesDuanXuGhoshAiroldi17,saveski2017detecting}; these results do not immediately extend to estimation as they are based on randomization inference with a fixed network size, and focus on testing the sharp null hypotheses.
While a majority of the literature focuses on randomized experiments, there is a growing interest in the literature to account for network interference when analyzing observational studies.
The existing literature generally assumes partial interference, where the network consists of many disconnected sub-communities \citep{TchetgenVanderWeele12, perez2014assessing, liu2016inverse, DiTraglia2020, vazquez-bare2022}.
Without this strong clustering condition, other works impose strong parametric assumptions on the potential outcomes function, assuming that the potential outcomes only depend on a known statistic of the neighborhood treatment, e.g. the number or fraction of treated \citep{verbitsky2012causal, chin2019regression, ogburn2017causal}.
This reduces estimation to a regression task under requirements of sufficient diversity in the treatments.
\cite{belloni2022neighborhood} also consider a setting in which the exposure mapping is known
but allow the ``radius'' of interference to vary across units, then learn this radius from data to devise a doubly robust estimator.
\citet{forastiere2021identification} consider a general exposure mapping model alongside an inverse propensity weighted estimator, but the estimator has high variance when the exposure mapping is complex.
\cite{de2018recovering} and \cite{de2019identifying} derive identification conditions when the observational panel data contains no information about the social ties (i.e., network).
Further, building on recent works in panel data \citep{agarwal2020synthetic, causalmatrixcompletion}, we allow for unobserved confounding in treatment assignment as long as there exist low-rank latent factors that mediate the unobserved confounding, i.e., there is ``selection on latent factors''.
\section{Setup \& Model}\label{sec:setup}
We begin with some notation.
Let $[X] \defeq \{1,\dots, X\}$ for any positive integer $X$.
For vector $\ba \in [D]^N$ and set $S \subseteq [N]$,
let $\ba_S \in [D]^{|S|}$ denote the vector containing the elements of $\ba$ indexed by $S$ and $a_i \in [D]$ denote the $i$-th element of $\ba$.
Let $\bbI_x$ denote the $x \times x$ identity matrix and $\otimes$ denote the Kronecker product.
Let $\ind(\cdot)$ denote the indicator function.
Let $\norm{\cdot}_{\psi_2}$ denote the Orlicz norm.
Let $O_p$ denote a probabilistic version of big-$O$ notation and $\tilde{\Omega}$ denote the variation on big-$\Omega$ notation that ignores logarithmic terms (see Appendix \ref{app:preliminaries} for precise definitions).
For sets of indices $S_1 \subseteq [m_1]$ and $S_2 \subseteq [m_2]$ and a matrix $\Pi \in \bbR^{m_1 \times m_2}$, let $\Pi[S_1, S_2] \in \bbR^{|S_1| \times |S_2|}$ denote the submatrix corresponding to the rows indexed by $S_1$ and columns index by $S_2$.
We use ``$\col$'' as a shorthand for all indices such that $\Pi[\col, S_2] \in \bbR^{m_1 \times |S_2|}$ and $\Pi[S_1, \col] \in \bbR^{|S_1| \times m_2}$.
Let $\cX^*$ denote the $*$-product space, where its length is not pre-determined.
Let $\Pi^+$ denote the pseudo-inverse of $\Pi$.
\subsection{Setup}
\begin{figure*}[t]
\centering
\includegraphics[width=\textwidth]{fig_network}
\caption{Example of spillover effects and how they can be captured via a graph network.
On the left, suppose that an online retailer presents similar products alongside one another.
Then, the sale of one product (e.g., orange sunglasses) is affected by the discounts applied to similar products; in this case, other sunglasses.
On the right, spillover is often modeled via a network graph $\cG$, in which the treatments applied to the neighbors $\cN(n)$ of a unit $n$ may affect the potential outcomes of $n$.
}
\label{fig:network_example}
\end{figure*}
Consider $N \geq 1$ units, $D \geq 1$ treatments, and $T \geq 1$ measurements of interest.
We denote the potential outcome for a given unit $n$ and measurement $t$ by the real-valued random variable $Y^{(\bintv)}_{t,n}$,
where $\bintv \in [D]^{N}$ denotes the vector of treatments over \emph{all} $N$ units.
This definition allows for spillover effects because the potential outcome for a given unit is a function of the treatment assignment of all units.
To model spillover across units, we use a network graph.
Let $\cG = ([N] , \cE)$ denote a graph over the $N$ units, where $\cE \subseteq [N] \times [N]$ denotes the edges of the graph.
Throughout, we assume that $\cG$ is {\em fixed} and {\em known}.
Let $\cN(n)$ denote the neighbors of unit $n \in [N]$ with respect to $\cG$
such that $j \in \cN(n) \iff (j, n) \in \cE$.
For simplicity of notation, let self-edges be included, i.e., $(n, n) \in \cE$ for all $n \in [N]$.
We assume that the network graph $\cG$ captures spillover effects in the following way.
\begin{assumption}[Stable Neighborhood Treatment Value Assumption (SNTVA)]\label{assumption:network_sutva}
The potential outcome of measurement $t \in [T]$ for unit $n \in [N]$ under treatments $\bintv \in [D]^{N}$ is given by
\begin{align*}
Y^{(\bintv)}_{t, n} = Y^{(\bintv_{\cN(n)})}_{t, n},
\end{align*}
where $\bintv_{\cN(n)} \in [D]^{|\cN(n)|}$ denotes the treatments assigned to the units in $n$'s neighborhood $\cN(n)$ for measurement $t$.
That is, the potential outcome of unit $n$ depends on its neighbors' treatments but does not depend the treatment of any other
unit $j \in [N] \setminus \cN(n)$.
\end{assumption}
See Figure \ref{fig:network_example} for an example of spillover and its network representation.
Several prior works on network interference also assume SNTVA, e.g., as the \emph{Neighborhood Interference Assumption (NIA)}
\citep{sussman2017elements}.
It can be viewed as a particular instantiation of exposure mappings, as defined by \cite{aronow2017estimating}, and effective treatment functions (e.g., under the constant treatment response assumption) \citep{Manski13}.
\begin{remark}
SNTVA only captures first-order spillover effects, i.e., assumes that the potential outcome of unit $n$ is only affected by the treatments of its \emph{immediate} neighbors.
One could capture higher-order spillover effects by adding edges to $\cG$.
The trade-off is that, as the number of edges in $\cG$ increases, the estimation bounds for the NSI estimator in Section \ref{sec:results} get correspondingly weaker.
\end{remark}
\begin{remark}
Although we assume $\cG$ is an undirected graph, our results can be adapted for directed graphs
by changing the definition of $\cN(i)$.
When $\cG$ is directed, $j \in \cN(i)$ if and only if $(j, i) \in \cE$.
\end{remark}
\subsection{Network latent-factor model} \label{sec:lf_model}
In this section, we introduce the model that we use to develop our estimator and formal results.
\begin{assumption}\label{asm:model}
Let the potential outcome of measurement $t \in [T]$ for unit $n \in [N]$ under graph $\cG$ and treatments $\ba \in [D]^N$ be given by:
\begin{equation}
\begin{aligned}
Y^{(\bintv_{\cN(n)})}_{t, n}
&=
\left< \bu_{n, n} , \bw_{t , a_n} \right>
+
\sum_{j \in \cN(n) \setminus n} \left< \bu_{j, n} , \bw_{t , a_j} \right> + \epsilon_{t, n}^{(\ba_{\cN(n)})} ,
\end{aligned}
\label{eq:full_model}
\end{equation}
where $\bu_{\cdot , \cdot} \in \bbR^r$ and $\bw_{\cdot , \cdot} \in \bbR^r$ represent latent (unobserved) factors;
$\epsilon_{t, n}^{(\ba_{\cN(n)})}$ represents additive, idiosyncratic shocks,
and $r$ is the ``rank'' or model complexity.
Further, we assume that $\bbE \big[ \epsilon_{t , i}^{(\ba_{\cN(i)})} \, | \, \LF \big] = 0 $, where
$\LF \defeq \big\{ \bu_{j , i} , \bw_{t, a} : i, j \in [N] \, , \, t \in [T], \text{ and } a \in [D] \big\}.$
\end{assumption}
We make several remarks.
First, we note that Assumption \ref{asm:model} automatically satisfies Assumption \ref{assumption:network_sutva}.
Second, the latent factor $\bu_{j, n}$ captures the effect in the potential outcome $Y^{(\bintv_{\cN(n)})}_{t, n} $ due to the interaction between node $n$ and its neighbour $j$;
analogously $\bw_{t , a_j}$ captures the effect due to the treatment that neighbor $j$ receives (i.e., $a_j$) for measurement $t$.
Specifically, their effect is captured through the inner product $\left< \bu_{j, n} , \bw_{t , a_j} \right>$.
In this sense, the spillover effect of different neighbors in \eqref{eq:full_model} is additive.
Lastly, \eqref{eq:full_model} can be equivalently written as
\begin{gather}
Y_{t, n}^{(\ba)} = Y_{t , n}^{(\ba_{\cN(n)})}
= \left< \tilde{\bu}_{n, \cN(n)} , \tilde{\bw}_{t, {\bintv_{\cN(n)}}} \right> + \epsilon_{t , n}^{(\ba_{\cN(n)})} ,
\label{eq:abbrev_model}
\end{gather}
where
\ifarxiv
\begin{align*}
\tilde{\bu}_{n, \cN(n)}
&\defeq [
\bu_{\cN_1(n), n}^\top \, , \,
\hdots \, , \,
\bu_{\cN_{|\cN(n)|}(n), i}^\top
]^\top ,
\\
\tilde{\bw}_{t , \ba_{\cN(n)}}
&\defeq [
\bw_{t, a_{\cN_1(n)}}^\top \, , \,
\hdots \, , \,
\bw_{t, a_{\cN_{|\cN(n)|}(n)}}^\top
]^\top .
\end{align*}
\else
$ \tilde{\bu}_{n, \cN(n)}
\defeq [
\bu_{\cN_1(n), n}^\top \, , \,
\hdots \, , \,
\bu_{\cN_{|\cN(n)|}(n), i}^\top
]^\top $ and
$ \tilde{\bw}_{t , \ba_{\cN(n)}}
\defeq [
\bw_{t, a_{\cN_1(n)}}^\top \, , \,
\hdots \, , \,
\bw_{t, a_{\cN_{|\cN(n)|}(n)}}^\top
]^\top$.
\fi
Here, $\cN_i(n)$ refers to $i$-th neighbor of $n$.
\eqref{eq:abbrev_model} is reminiscent of classical interactive fixed effects models studied in the literature.
Indeed, we can think of $\tilde{\bu}_{n, \cN(n)} \in \mathbb{R}^{r |\cN(n)|}$ and $\tilde{\bw}_{t, a_{\cN(n)}} \in \mathbb{R}^{r |\cN(n)|}$ as the \emph{network-adjusted} latent factors
and $r |\cN(n)| \in \bbN_{> 0}$ as denoting the \emph{network-adjusted} ``rank'' (note that $r|\cN(n)|$ is actually an upper bound on the model's rank, but we will refer to it as the network-adjusted rank for convenience).
\subsection{Examples of latent-factor model}
We discuss how examples of latent factor models
previously studied in the literature are captured by the model we propose in Assumption \ref{asm:model}.
Further, we discuss how additive non-linear latent factor models can be approximated by the linear additive model we propose.
\begin{example}\label{ex:f_no_spillover}
Consider a setting with \emph{no spillover effects}, i.e., $\cN(n) = \{ n \}$ for all $n \in [N]$.
Then, the latent factor model in \eqref{eq:full_model} reduces to
\begin{align}\label{eq:no_int_model}
Y_{t, n}^{(\ba)} = Y_{t, n}^{(a_n)}
&= \langle \bu_{n, n} , \bw_{t , a_n} \rangle + \epsilon_{t, n}^{(a_n)},
\end{align}
This recovers the model considered in \citep{agarwal2020synthetic}.
As explained in \citep{agarwal2020synthetic}, this also captures the models considered in \citep{abadie2021using} and \citep{arkhangelsky2019synthetic}.
\end{example}
\begin{example}\label{ex:linear_model}
There are several prior works that assume that network interference is additive.
For instance, consider the model proposed by \citet{yu2022graph} in which $D = 2$, i.e., the treatments are binary, denoted by $\{0, 1\}$, and
\begin{align}
Y_{n}^{(\ba)} =
Y_{n}^{(\ba_{\cN(n)})}
&= u_{0,n} + u_{n,n} a_n + \sum_{j \in \cN(n) \setminus n} u_{j, n} a_j + \epsilon_{n}^{(\ba_{\cN(n)})}, \label{eq:yu_model}
\end{align}
where $u_{0,n}, u_{n, n}, u_{j, n}, \epsilon_{n}^{(\ba_{\cN(n)})} \in \Rb$.
One can verify that \eqref{eq:yu_model} can be recovered from \eqref{eq:full_model} by taking $r = 1$; $T = 1$ (i.e., no index $t$); $w_{a} = a$; and there is an auxiliary node $0$ for which $a_0 = 1$ and $0 \in \cN(n)$ for all $n \in [N]$.
That is, both our model \eqref{eq:full_model} and \eqref{eq:yu_model} assume that spillover is additive,
and in order to exploit the structure across measurements $t$ that exists in panel data, we extend \eqref{eq:yu_model} by: (i) allowing for multiple measurements $t$, and (ii) assuming that $u_{j, n} a_j$ in \eqref{eq:yu_model} has the measurement-dependent latent-factor representation $\left< \bu_{j, n}, \bw_{t , a_j} \right>$.
These repeated measurements are exactly what lets us create personalized counterfactual trajectories per units and implicitly correct for unobserved confounding.
\end{example}
\begin{example}\label{ex:f_spillover}
Consider a setting where network interference is additive but the effect of the latent factors is {\em non-linear}.
Precisely, consider the following variation of \eqref{eq:full_model}:
\begin{equation}
\begin{aligned}
Y_{t, n}^{(\ba)}
=
Y_{t, n}^{(\ba_{\cN(n)})}
&=
h(\bu_{n, n} , \bw_{t , a_n})
+
\sum_{j \in \cN(n) \setminus n} g(\bu_{j, n} , \bw_{t , a_j}) + \epsilon_{t, n}^{(\ba_{\cN(n)})} ,
\end{aligned}
\label{eq:nl_full_model}
\end{equation}
where $h, g: \bbR^r \times \bbR^r \to \bbR$ are potentially non-linear functions.
If the latent factors take value in a bounded domain, say ${\cal C} \subset \bbR^r$, and $h, g$ are Lipschitz continuous (or more generally {\em smooth}), then it can be argued that (see Theorem 1 by \citet{shah2020sample} for example) for any given $\delta > 0$, there is some $r' = r'(\delta)$ large enough and choice of functions $\{ \phi_k, \psi_k, \phi'_k, \psi'_k : \bbR^r \to \bbR, ~k\leq r' \}$ such that
\ifarxiv
\begin{align*}
&\Big| h(\bu, \bw) - \sum_{k=1}^{r'} \phi_k(\bu)\psi_k(\bw) \Big| \leq \delta ,
\\
&\Big| g(\bu, \bw) - \sum_{k=1}^{r'} \phi'_k(\bu)\psi'_k(\bw) \Big| \leq \delta ,
\end{align*}
\else
$
\Big| h(\bu, \bw) - \sum_{k=1}^{r'} \phi_k(\bu)\psi_k(\bw) \Big| \leq \delta$
and
$\Big| g(\bu, \bw) - \sum_{k=1}^{r'} \phi'_k(\bu)\psi'_k(\bw) \Big| \leq \delta
$
\fi
for all $\bu, \bw \in {\cal C}$. Then, by setting
$\tilde{\bu} = [\phi_k(\bu): k \leq r']$,
$\tilde{\bw} = [\psi_k(\bu): k \leq r']$,
$\tilde{\bu}' = [\phi'_k(\bu): k \leq r']$,
$\tilde{\bw}' = [\psi'_k(\bu): k \leq r']$,
it follows that \eqref{eq:nl_full_model} is pointwise $\delta$-approximated as a linear latent factor model as given in \eqref{eq:full_model}, with $\bu, \bw$ appropriately replaced by
$\tilde{\bu}, \tilde{\bw}, \tilde{\bu}',$ and $\tilde{\bw}'$.
\end{example}
\subsection{Target causal estimand}
\begin{figure*}[t]
\centering
\includegraphics[width=1\textwidth]{images/target_estimand_2.pdf}
\caption{
Illustration of our setup and target causal estimand.
On the top-left is an example $N \times T$ treatment matrix $A$,
split into the training and prediction measurements $\cT_\pre$ and $\cT_{\post}$.
On the top-right is the corresponding observation matrix $Z$,
i.e., the $(n, t)$-th element of $Z$ is the outcome of unit $n$ at measurement $t$ under treatments $\ba^t$.
The bottom-left gives the counterfactual treatment matrix, i.e., the treatments during $\cT_\pre$ remain intact and the counterfactual prediction treatment is given by $\tilde{\ba}$.
Lastly, on the bottom-right are the potential outcomes of interest under $\tilde{\ba}$.
The target causal estimand is the average of potential outcomes of a specific unit under $\tilde{\ba}$ across $\cT_\post$.
}
\label{fig:panel_data}
\end{figure*}
Recall that we consider the panel data setting in which we observe $T$ measurements (e.g., a time series) for every unit.
Let $a^t_n \in [D]$ denote the treatment assignment for unit $n$ at measurement $t$;
$\ba^t \in [D]^N$ denote the vector of treatment assignments for all $N$ units at $t$;
and $A \defeq [ \ba^{1}, \ba^{2}, \hdots, \ba^{T} ] \in [D]^{N \times T}$ denote the sequence of treatment assignments across all $N$ units and $T$ measurements.
Note that the treatment assignments $A$ are observed, and the potential outcome $Y_{t,n}^{(\ba^t)}$ is observed for every unit $n \in [N]$ and measurement $t \in [T]$.
We denote the \emph{observed} outcomes for unit $n$ at measurement $t$ by $Z_{t,n} = Y^{(\ba^{t})}_{t,n}$ for all $t \in [T]$ and the matrix of observations by $Z \in \bbR^{T \times N}$.
To define the target causal estimand of interest, let $\cT_{\post} \subseteq [T]$ refer to a subset of measurements for which we would like to make counterfactual predictions; let $T_{\post} = |\cT_{\post}| \leq T$.
To simplify notation, we assume without loss of generality that the treatment assignments are fixed across the measurements in $\cT_{\post}$, i.e., $A[:, t] = \ba^\post \in [D]^N$ for all $t \in \cT_\post$ (see Remark \ref{rem:const_pred_treatment}).
For any given unit $n$ and target treatment assignment $\tilde{\ba} \in [D]^N$, our goal is to estimate the individual potential outcome averaged over the prediction period:
\begin{align}
\IPO{n} & = \frac{1}{T_{\post}} \sum_{t \in \cT_{\post}} \Ex\Big[Y^{(\tilde{\ba}_{\cN(n)} )}_{t , n} \mid \LF \Big],\label{eq:estimand}
\end{align}
using observations $Z$,
where we condition on the latent factors, $\LF$.
Under Assumption \ref{assumption:network_sutva}, the outcome of unit $n$ depends only on the treatments applied to $\cN(n)$, i.e., on $\tilde{\ba}_{\cN(n)}$ rather than the
entire $\tilde{\ba}$.
See Figure \ref{fig:panel_data} for an illustration of our target causal estimand and observation pattern.
Note that our results are given for any $T_\post \geq 1$.
That is, we show identifiability and finite-sample consistency even for point estimates (i.e., for $T_\post = 1$).
\begin{remark}\label{rem:const_pred_treatment}
Our assumption $A[:, t] = \ba^\post \in [D]^N$ for all $t \in \cT_\post$ is without loss of generality.
First, our work does not allow for spillover across measurements, i.e., $Y_{t,n}^{(\ba)}$ does not depend on treatments other than those assigned at $t$.
We can therefore extract measurements in $\cT_{\post}$ that share the same treatment $\ba^\post$, i.e., we can redefine the prediction set as $\cT_\post'$ so that $\ba^t = \ba^\post$ for all $t \in \cT_\post'$.
We can repeat this for all unique prediction treatments and apply NSI separately to each.
Further, we note that our consistency and normality results allow for $T_\post = 1$, and so our results go through even if we have a different target prediction treatment for every measurement in $\cT_{\post}$.
\end{remark}
\section{Network Synthetic Interventions (NSI) Estimator}\label{sec:estimator}
We now describe our estimator for the estimand of interest \eqref{eq:estimand}, which we term {\em Network Synthetic Intervention} (NSI).
It can be seen as a natural extension of the Synthetic
Interventions (SI) estimator \citep{agarwal2020synthetic}, which is itself a generalization of Synthetic Controls (SC) \citep{abadie2021using} estimator, to settings in which there is \emph{network interference}.
For the remainder of this work, we fix the unit $n$ and counterfactual treatment assignment $\cfA$ of interest.
\subsection{Donor set}
To define the NSI estimator, we introduce some necessary concepts.
First, let $\cT_{\pre} \subset [T]$ denote a subset of the measurements known as {\em training} measurements.
Without loss of generality, let $\cT_{\pre} \coloneqq \{1, 2, \hdots, T_{\pre}\}$, $\cT_{\post} \coloneqq \{T_{\pre} + 1, \dots, T\}$, $T_{\pre} \defeq |\cT_{\pre}|$, and $T_{\post} \defeq |\cT_{\post}|$.
We note that $\cT_{\pre}$ does not need to be $[T] \backslash \cT_{\post}$ but we keep it as such to simplify the exposition.
Recall that $A \in [D]^{N \times T}$ denotes the treatment assignments to the various units over time.
Let $A^\pre \defeq A[: , \cT_{\pre}]$ and $A^\pre_n \defeq A[\cN(n) , \cT_{\pre}]$.
Next, we introduce the notion of a ``donor set."
\begin{definition}[Donors]\label{def:node_donors}
For a given unit $n \in [N]$ and counterfactual treatment assignment $\cfAn \in [D]^{|\cN(n)|}$, we consider $i \in [N] \setminus \{n\}$ a ``donor unit'' if the following conditions hold:
\begin{enumerate}
\item $|\hspace{1pt} \cN(i)| = | \hspace{1pt} \cN(n) |$, i.e., donor unit $i$ has the same number of neighbors as unit $n$.
\item There exists a permutation $\pi_i : [\cN(i)] \to [\cN(i)]$ such that:
\begin{enumerate}
\item $A[\pi_i(\cN(i)),\cT_{\pre}] = A[\cN(n),\cT_{\pre}]$, i.e., the training treatment assignment of donor unit $i$ and its neighbors match that of unit $n$ and its neighbors, once permuted by $\pi_i$.
\item $\ba^\post_{\pi_i(\cN(i))} = \cfAn$, i.e., the prediction treatment assignment of donor unit $i$ and its neighbors matches the target counterfactual treatment assignment $\cfAn$, once permuted by $\pi_i$.
\end{enumerate}
\end{enumerate}
\end{definition}
For the remainder of this work, we fix the unit $n$ and counterfactual treatments $\cfAn$ of interest and let $\cI^{(n)} \subset [N] \setminus \{ n \}$ denote the corresponding set of donors.
One can think of the donor set $\cI^{(n)}$ as units whose \emph{observed} outcomes can be used to estimate the unobserved \emph{potential} outcome of unit $n$ under the counterfactual treatments of interest.
\subsection{NSI Estimation procedure}\label{sec:estimation_proc}
Recall that $Z \in \bbR^{T \times N}$ denotes the matrix of observations.
We define
$\bz_{\pre, n} \defeq Z[\cT_{\pre}, n] \in \bbR^{T_{\pre}}$,
$Z_{\pre, \cI^{(n)}} \defeq Z[\cT_{\pre}, \cI^{(n)}] \in \bbR^{T_{\pre} \times | \cI^{(n)} |} $, and
$Z_{\post, \cI^{(n)}} \defeq
Z[\cT_{\post}, \cI^{(n)}]\in \bbR^{T_{\post} \times | \cI^{(n)} |}$.
NSI takes in one hyperparameter $\kappa \in [\min(T_{\pre}, |\cI^{(n)}|)]$ and proceeds in two steps, as follows.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\emph{1. Point estimate}.
Let $\{(\hat{s}_\ell, \hat{\boldsymbol{\mu}}_\ell, \hat{\boldsymbol{\nu}}_\ell)\}_{\ell = 1}^{\min(T_\pre, |\cI^{(n)}|)}$ denote the set of singular values, left singular vectors, and right singular vectors for the observed matrix $Z_{\pre, \cI^{(n)}}$, where $\hat{s}_1 \geq \hat{s}_2 \geq \hdots \geq \hat{s}_{\min(T_\pre, |\cI^{(n)}|)} \geq 0$.
The NSI estimator produced a point estimate as follows:
\begin{align}\label{eq:NSI_estimator_point}
\hIPO{n} &= \frac{1}{T_{\post}} {\bf 1}^T
Z_{\post, \cI^{(n)}} ~\hat{\bbE} [ Z_{\pre, \cI^{(n)}} | \LF , \cO]^+ \bz_{\pre, n}.
\end{align}
For the given hyperparameter $\kappa$,
$
\hat{\bbE} [ Z_{\pre, \cI^{(n)}} | \LF , \cO]^+
= \sum_{\ell = 1}^\kappa \frac{1}{\hat{s}_\ell}
\hat{\boldsymbol{\nu}}_\ell
\hat{\boldsymbol{\mu}}_\ell^\top,
$
can be viewed as an estimate of $\bbE [ Z_{\pre, \cI^{(n)}} | \LF , \cO]$ that is obtained via hard singular value thresholding, where only the top $\kappa$ components are preserved.
This estimator, which begins with singular value thresholding, has been shown to be equivalent to principal component regression \citep{PCR_1, PCR_2}.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\emph{2. Confidence interval}.
Let $\hat{\boldsymbol{\alpha}} = \hat{\bbE} [ Z_{\pre, \cI^{(n)}} | \LF , \cO]^+ \bz_{\pre, n}$.
Then, the $\textsc{CI}$-percent confidence interval can be constructed as:
\begin{align*}
\IPO{n}
&\in
\left[
\hIPO{n}
\pm
\frac{\Phi^{-1}(\textsc{CI}/100) \hat{\sigma} \norm{\hat{\boldsymbol{\alpha}}}_2}
{\sqrt{T_{\post}}}
\right],
\end{align*}
where $\Phi$ denotes the cumulative distribution function (CDF) of the standard normal distribution, $\Phi^{-1}$ is the inverse CDF, and
\ifarxiv
$$\hat{\sigma}^2
=
\frac{1}{T_{\pre}}
\norm{
\bz_{\pre, n} - Z_{\pre, \cI^{(n)}} \hat{\boldsymbol{\alpha}}
}_2^2 ,$$
which can be interpreted as the in-sample prediction error of the NSI estimator.
\else
$\hat{\sigma}^2
=
\frac{1}{T_{\pre}}
\norm{
\bz_{\pre, n} - Z_{\pre, \cI^{(n)}} \hat{\boldsymbol{\alpha}}
}_2^2$, which can be interpreted as the in-sample prediction error of the NSI estimator.
\fi
\subsection{Discussion of NSI}\label{sec:discussion_NSI}
We briefly provide intuition for the NSI estimator,
then compare it to the traditional Synthetic Control \citep{abadie2021using} and Synthetic Interventions \citep{agarwal2020synthetic} estimators.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
{\bf NSI linearly combines donor outcomes.}\label{sec:linear_comb}
NSI begins by finding units, called ``donors,'' whose outcomes can be used to estimate the potential outcomes of unit $n$.
In Section \ref{sec:results}, under suitable assumptions, we establish that the expected potential outcome of unit $n$ can be expressed as a linear combination of the expected outcomes of the donor units, i.e.,
\begin{align}
\Ex[Y_{t, n}^{(\tilde{\ba})}] &= \sum_{j \in \cI^{(n)}} \alpha_j \cdot
\Ex[Y_{t, j}^{(\ba)}],
\label{eq:NSI_linear}
\end{align}
where $\alpha_j \in \bbR$ (note that $\alpha_j$ can be negative).
NSI can be viewed as a method for estimating the coefficients $\{ \alpha_j \}$.
More precisely, recall that $\hat{\boldsymbol{\alpha}} = \hat{\bbE} [ Z_{\pre, \cI^{(n)}} | \LF , \cO]^+ \bz_{\pre, n}$.
Then, the NSI estimator \eqref{eq:NSI_estimator_point} can be rewritten as
\ifarxiv
$$
\hIPO{n} = \frac{1}{T_{\post}} \sum_{t \in \cT_{\post}} \sum_{j \in \cI^{(n)}} \hat{\alpha}_j Z[t, j],
$$
\else
$
\hIPO{n} = \frac{1}{T_{\post}} \sum_{t \in \cT_{\post}} \sum_{j \in \cI^{(n)}} \hat{\alpha}_j Z[t, j],
$
\fi
which is precisely what would follow from expressing the target causal estimand \eqref{eq:estimand} using \eqref{eq:NSI_linear}.
\ifarxiv
\\
\else
\medskip
\fi
\begin{figure*}[t]
\centering
\includegraphics[width=\textwidth]{donor_ring_graph_2}
\caption{One of the main differences between the NSI estimator and previous estimators (such as SC and SI) is the choice of donors. To illustrate this point, consider a unit $n$ whose target treatment is $2$, as given in the left panel.
Suppose that $\cG$ is a ring graph and the prediction treatments are assigned as given in the middle and right panels.
Then, under SC and SI, there are 7 units (with green borders) whose prediction treatments match unit $n$'s target treatment (middle panel).
Under NSI, however, the donor requirements are stricter.
Specifically, NSI looks at the target treatment $(1, 2, 1)$ across all neighbors $\cN(n)$, as given in the left panel.
The only units $j$ that could be considered as potential donors must have neighborhood $\cN(j)$ that receive prediction treatments $(1, 2, 1)$ subject to permutation (recall Definition \ref{def:node_donors}).
As shown on the right, only 4 units (with green borders) meet this requirement. }
\label{fig:nsi_donors_ring}
\end{figure*}
\noindent
{\bf Comparing NSI to SI \& SC: Choosing donors appropriately.}
NSI is a generalization of SI and SC.
The key difference between SC/SI and NSI is the choice of donor units.
In SC/SI, a valid donor unit only needs to undergo the same training and prediction treatments as the training and target prediction treatments of $n$.
In NSI, there are more stringent requirements on donors, as given by Definition \ref{def:node_donors} and illustrated in Figure \ref{fig:nsi_donors_ring}.
These more stringent requirements on how donors are chosen are how NSI removes the bias that SI and SC suffer from when there is spillover.
Under the appropriate choice of donors, the way that the linear model \eqref{eq:NSI_linear} is learned can depend on modeling assumptions.
NSI uses principal component regression (PCR), which is motivated by \cite{agarwal2020synthetic}).
However, other estimators, such as convex regression \citep{abadie2021using} and variants thereof can also be used.
In Section \ref{sec:results}, we detail the conditions under which PCR produces consistent and asymptotically normal estimates.
\section{Formal results} \label{sec:results}
In this section, we provide formal results for the NSI estimator.
We characterize conditions under which $\IPO{n}$ can be identified.
We then establish that NSI provides a consistent estimate of $\IPO{n}$ and its estimation error is asymptotically normal, justifying the confidence interval given in Step 3 of Section \ref{sec:estimation_proc}.
As before, we restrict our attention to a specific unit $n$ and target counterfactual treatment assignment $\cfAn$.
All proofs are given in Appendices \ref{app:helpers}-\ref{app:proofs}.
\subsection{Identification Result}\label{sec:id}
We now discuss the key assumptions we make about the intervention assignments $A$.
We begin with an assumption on the treatment assignment.
\begin{assumption}[Conditional exogeneity]\label{asm:conditional_exo}
For all $n \in [N]$, $t \in [T]$, and $\ba \in [D]^N$, we have that $Y^{(\ba_{\cN(n)})}_{n, t} \perp \cO \, | \, \LF$.
\end{assumption}
Given Assumption \ref{asm:model}, this conditional independence is equivalent to assuming that $\epsilon_{t, n}^{(\ba_{\cN(n)})} \perp \cO \, | \, \LF $.
Similar conditions of ``selection on latent factors'' have been considered in the literature (see \citep{agarwal2020synthetic}
and discussion therein).
In this work, we analogously require ``selection on network-adjusted latent factors.''
We make two additional assumptions, as follows.
\begin{assumption}[Linear span inclusion]\label{asm:linear_span}
Given a unit $n \in [N]$ and counterfactual treatments $\cfAn \in [D]^{|\cN(n)|}$ of interest, consider the donor set $\cI^{(n)}$.
We assume the treatment assignment $A$ is such that $\cI^{(n)}$ is non-empty and that $\tilde{\mathbf{u}}_{n, \cN(n)}$ lies in the linear span of $\{\tilde{\mathbf{u}}_{i, \pi_i( \cN(i))}\}_{i \in \cI^{(n)}}$, where $\{ \pi_i \}_{i \in \cI^{(n)}}$ is defined in Definition \ref{def:node_donors}.
That is, there exists $\boldsymbol{\lambda} \in \bbR^{|\cI^{(n)}|}$ such that
\begin{align*}
\tilde{\mathbf{u}}_{n, \cN(n)} = \sum_{i \in \cI^{(n)} } \lambda_{i} \tilde{\mathbf{u}}_{i, \pi_k( \cN(i))}.
\end{align*}
\end{assumption}
\begin{assumption}[Subspace inclusion] \label{asm:subspace_inclusion}
Assume that the rowspace of $\bbE \big[ Z_{\post, \cI^{(n)} } \big| \, \LF, \cO \big]$
lies within the rowspace of $\bbE \big[ Z_{\pre, \cI^{(n)} } \big| \, \LF, \cO \big]$.
\end{assumption}
We discuss Assumptions \ref{asm:linear_span}-\ref{asm:subspace_inclusion} in Sections \ref{sec:assumptions} and \ref{sec:validity_test}.
We show that NSI's confidence interval indicates the degree to which Assumption \ref{asm:linear_span} holds, and we provide a way to test for Assumption \ref{asm:subspace_inclusion} in Section \ref{sec:validity_test}.
Before stating our identification result,
we first recall identifiability for an arbitrary estimation problem of interest.
In the definition below, $P_\theta \in \cP$ refers to data distribution under model parameters $\theta$, i.e., $P_\theta$ describes how the data behaves under model $\theta$.
\begin{definition}[Identifiability]\label{def:identifiability}
Let $\theta \in \Theta$ denote the ground-truth model parameters and $\cP = \{ P_{\theta'} : \theta' \in \Theta \}$ denote the set of possible data distributions.
Let $f : \Theta \rightarrow \bbR$ denote the estimand of interest and $P_\theta \in \cP$ denote the data generating distribution parameterized by $\theta$.
Then, $f(\theta)$ is \emph{identifiable} if there exists a function $g : \cP \rightarrow \bbR$ such that $f(\theta) = g(P_\theta)$,
i.e., the estimand can be written as a function of the data distribution.
\end{definition}
Identifiability implies that if $f(\theta) \neq f(\theta')$, then
$g(P_\theta) \neq g(P_{\theta'})$; otherwise, $f(\theta) = g(P_\theta) = g(P_{\theta'}) = f(\theta')$.
In other words, the estimand is identifiable if we can compute it \emph{exactly} when given access to the full data distribution, which is necessary for estimation from (noisy) data to be possible.
In our setting, $\theta = \LF$ denotes the latent factors and $f(\theta) = \IPO{n}$ is the target causal estimand, which we note can be written solely as a function of the latent factors.
Recall that the quantities $(A, \cG, \cT_{\pre}, \cT_\post)$ are observed and known.
Let $P_{\theta}$ denote the joint distribution over the matrices of observed outcomes $Z[\cT_\pre,:]$ and $Z[\cT_\post,:]$.
Note that, by Assumption \ref{asm:model}, the distribution of $Z[\cT_\pre,:]$ and $Z[\cT_\post,:]$ is given by the latent factors $\LF$, the treatment assignment $A$, and the random variables $\epsilon_{t, n}^{(\ba_{\cN(n)})}$.
We now show that $\IPO{n}$ is identifiable under \eqref{eq:full_model} and Assumptions \ref{asm:model}-\ref{asm:subspace_inclusion}.
\begin{theorem}[Identification]\label{thm:ID}
If Assumptions \ref{assumption:network_sutva}-\ref{asm:subspace_inclusion} hold, then
\begin{align} \label{eq:ITE_identif}
\IPO{n} = \frac{1}{T_{\post}} {\bf 1}^T_{T_\post} ~\bbE [ Z_{\post, \cI^{(n)}} \, | \, \LF, \cO ] ~\bbE [ Z_{\pre, \cI^{(n)}} | \LF , \cO]^+ ~\bbE [ \bz_{\pre, n} | \LF , \cO],
\end{align}
where ${\bf 1}_{T_\post}$ is the all ones vector of length ${T_\post}$, and the set $\cI^{(n)}$ is defined in Definition \ref{def:node_donors}.
This implies that $\IPO{n}$ is identifiable by Definition \ref{def:identifiability}.
\end{theorem}
Under Definition \ref{def:identifiability}, $g$ is given by \eqref{eq:ITE_identif}.
Note only the first moments of $P_\theta = P_{\LF}$ are needed.
NSI estimates $\IPO{n}$ by replacing the expectations in \eqref{eq:ITE_identif} with the corresponding empirically observed quantities and smoothing out the pseudoinverse using hard singular value thresholding as given by \eqref{eq:NSI_estimator_point}.
For the purposes of the analysis, we denote
\begin{align}\label{eq:linear_coeff}
\boldsymbol{\alpha} = \bbE [ Z_{\pre, \cI^{(n)}} | \LF , \cO]^+ \bbE [ \bz_{\pre, n} | \LF , \cO].
\end{align}
\subsection{Consistency and asymptotic normality}\label{sec:thm_consistency}
Next, we give conditions under which the NSI estimator achieves finite-sample consistency and asymptotic normality.
Let $r_{\pre} \in [ r |\cN(n)| ]$ be the rank of $\bbE \big[ Z_{\pre, \cI^{(n)}} | \, \LF , \cO \big]$, $s_1 \geq \hdots \geq s_{r_{\pre}} \geq 0$ denote its singular values, and $R_{\pre} \in \bbR^{|\cI^{(n)}| \times r_{\pre}}$ denote its right singular vectors.
\begin{assumption}[Sub-Gaussian noise] \label{asm:subG_noise}
Conditioned on $\LF$, we assume that, for all $i \in [N]$, $t \in [T]$, and $\ba \in [D]^N$, $\epsilon^{( \ba_{\cN(i)})}_{t, i}$ are independent, sub-Gaussian random variables with $\text{Var}( \epsilon^{(\ba_{\cN(i)})}_{t, i} | \LF) = \sigma^2$ and that $\bnorm{ \epsilon^{(\ba_{\cN(i)})}_{t, i} | \, LF}_{\psi_2} \leq \xi \sigma$ for some constant $\xi > 0$.
\end{assumption}
\begin{assumption}[Boundedness] \label{asm:bounded}
We assume that
$\bbE \big[Y^{(\ba_{\cN(j)})}_{t, i} \big| \, \LF \big] \in [-1, 1]$ for all $i \in [N]$, $t \in [T]$.
\end{assumption}
\begin{assumption}[Well-balanced spectrum] \label{asm:rank_balanced_singular_vals}
For parameters $\xi', \xi'' > 0$,
we assume $s_{r_{\pre}} / s_1 \geq \xi'$ and $\bnorm{\bbE \big[ Z_{\pre, \cI^{(n)} } \big| \, \LF, \cO \big] }_F^2 \geq \xi'' T_{\pre} |\cI^{(n)}| $, where $\cI^{(n)}$ is defined in Definition \ref{def:node_donors}.
\end{assumption}
In Section \ref{sec:experimental_proc}, we prove that in the setting of $d$-regular graphs and where the latent factors are sampled independently from a Gaussian distribution, the parameters $\xi'$ and $\xi''$ are inverse polynomials of $r$ and $d$.
\begin{assumption}[Sufficient number of components]\label{asm:components}
We assume that $\kappa = r_{\pre}$, where $\kappa$ is defined in Section \ref{sec:estimator} and $r_{\pre} \leq r | \cN(n)|$.
\end{assumption}
The following results establish that NSI is consistent and asymptotically normal.
\begin{theorem}[Finite-sample consistency]
\label{thm:finite_sample_consistency}
Let Assumptions \ref{assumption:network_sutva}-\ref{asm:components} hold.
Then,
\begin{align*}
&\left|
\hIPO{n} - \IPO{n}
\right|
\\
& \hspace{20pt}
= O_P \left(
\log( T_\pre | \cI^{(n)} | )
\left(
\frac{r_\pre^{3/4}}{(\xi''')^{3/2} T_\pre^{1/4} }
+
\frac{r_\pre^2}{(\xi''')^4 }
{\max} \left(
\frac{1}{\sqrt{T_\pre}} ,
\frac{1}{ \sqrt{| \cI^{(n)} | } } ,
\frac{ \sqrt{| \cI^{(n)} | } }{T_\pre^{3/2}}
\right)
\right)
\right) ,
\end{align*}
where $\xi''' = \xi' \sqrt{\xi''}$ and $\xi' , \xi''$ are defined in Assumption \ref{asm:rank_balanced_singular_vals}.
\end{theorem}
Theorem \ref{thm:finite_sample_consistency} indicates that, under the stated conditions,
NSI is consistent.
Specifically,
for fixed $r$, $d$, and $r_{\pre} \leq r (d+1)$,
the estimation error of NSI approaches $0$ as the number of training measurements $T_\pre$ and number of donors $|\cI^{(n)}|$ grow if $T_\pre = \omega(| \cI^{(n)} |^{1/3})$.
Importantly,
the number of prediction measurements $T_\post$ need not grow in order for NSI's estimation error to decay to $0$.
Let $\Delta = \hat{\boldsymbol{\alpha}} - \boldsymbol{\alpha}$, the estimation error of learning the linear weights that represent the outcomes of the target units in terms of the donor units (see \eqref{eq:linear_coeff}).
The following result establishes a general result that as long as $\Delta$ is decaying sufficiently quickly for any linear estimator (it does not have to be via principal component regression as we do), the NSI estimator is asymptotically normal.
While Theorem \ref{thm:finite_sample_consistency} allows NSI to produce the point estimate in Step 1 of Section \ref{sec:estimator}, Theorem \ref{thm:asym_normality} justifies the confidence interval provided in Step 2.
\begin{theorem}[Asymptotic normality]\label{thm:asym_normality}
Suppose Assumptions \ref{assumption:network_sutva}-\ref{asm:components} hold.
Suppose
\ifarxiv
$$\norm{\Delta}_2 = o_P \left(\min \left(
\frac{\sigma \norm{\boldsymbol{\alpha}}_2}{\sqrt{T_\post | \cI^{(n)} |}} ,
\sqrt{\frac{\norm{\boldsymbol{\alpha}}_2}{\sigma}}
\right) \right).$$
\else
$\norm{\Delta}_2 = o_P \left(\min \left(
\frac{\sigma \norm{\boldsymbol{\alpha}}_2}{\sqrt{T_\post | \cI^{(n)} |}} ,
\sqrt{\frac{\norm{\boldsymbol{\alpha}}_2}{\sigma}}
\right) \right)$.
\fi
Then, conditioned on $\LF$ and $\cO$,
\begin{align*}
\frac{\sqrt{T_{\post}}}{\sigma \norm{\balphaperp}_2}
\left(
\IPO{n}
-
\hIPO{n}
\right)
\stackrel{d}{\rightarrow}
\cN(0, 1) ,
\end{align*}
as $T_{\pre}, T_{\post}, |\cI^{(n)}| \rightarrow \infty$.
Moreover, the $\hat{\sigma}$ used to construct the NSI confidence interval in Step 3 of Section \ref{sec:estimation_proc} satisfies:
\begin{align*}
| \hat{\sigma}^2 - \sigma^2 |
=
O_p \left(
\frac{r_{\pre}}{\sqrt{T_{\pre}}}
+
\frac{r_{\pre}^{2}
{\log(T_{\pre} |\cI^{(n)}|)}}{(\xi''')^4 \min(T_{\pre}, |\cI^{(n)}| )}
\right),
\end{align*}
where $\xi''' = \xi' \sqrt{\xi''}$ and $\xi' , \xi''$ are defined in Assumption \ref{asm:rank_balanced_singular_vals}.
\end{theorem}
\subsection{Assumptions \ref{asm:linear_span}, \ref{asm:subspace_inclusion}, and \ref{asm:components}}\label{sec:assumptions}
The key enabling conditions for Theorems \ref{thm:ID}-\ref{thm:asym_normality} are Assumptions \ref{asm:linear_span}, \ref{asm:subspace_inclusion}, and \ref{asm:components}.
In this section, we discuss these assumptions further.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
{\bf Assumption \ref{asm:linear_span}.}
Recall from Section \ref{sec:discussion_NSI} that NSI can be interpreted as linearly combining the potential outcomes of donors under appropriately chosen coefficients, denoted by $\hat{\boldsymbol{\alpha}}$.
The key enabling condition that makes linearly combining donor outcomes valid under our model \eqref{eq:full_model} is Assumption \ref{asm:linear_span}.
The extent to which Assumption \ref{asm:linear_span} holds can be examined in two ways.
First, recall that $\hat{\sigma}^2 = \frac{1}{T_{\pre}} \norm{ \bz_{\pre, n} - Z_{\pre, \cI^{(n)}} \hat{\boldsymbol{\alpha}} }_2^2$ is a measure of how well NSI's linear fit explains the training data.
Recall further that the coefficients $\hat{\boldsymbol{\alpha}}$ are estimates of the coefficients $\boldsymbol{\alpha}$ that are used to combine donor outcomes.
As such, $\hat{\sigma}^2$ can be viewed as a statistic for Assumption \ref{asm:linear_span}, where a large $\hat{\sigma}^2$ suggests Assumption \ref{asm:linear_span} does not hold.
Since NSI's confidence interval scales with $\hat{\sigma}$ (see Step 2 of \ref{sec:estimation_proc}), how well Assumption \ref{asm:linear_span} holds is captured by NSI's confidence interval.
Second, since Assumption \ref{asm:linear_span} requires that unit $n$'s $\tilde{\bu}$-latent factor is contained in the span of the donors' $\tilde{\bu}$-latent factors and $\tilde{\bu}_{n, \cN(n)} \in \bbR^{r |\cN(n)|}$, at least
$r |\cN(n)|$ donors are needed.
Suppose, for example, that all units' $\tilde{\bu}$-latent factors are drawn i.i.d. from a multivariate Gaussian.
Then, Assumption \ref{asm:linear_span} holds almost surely if and only if there are at least $r |\cN(n)|$ donors (cf. Lemma \ref{lem:linear_span_gaussian}).
Given an estimate $\bar{r}$ of $r$, one can therefore perform a simple sanity check that $|\cI^{(n)}| \geq \bar{r}|\cN(n)|$.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
{\bf Assumption \ref{asm:subspace_inclusion}.}
This condition ensures that the linear coefficients that NSI learns from the training observations generalize to the prediction task.
In Section \ref{asm:subspace_inclusion}, we provide two validity tests to verify whether Assumption \ref{asm:subspace_inclusion} holds, i.e., whether the observations are sufficiently rich such that a generalizable model can be learned.
To motivate the need for such tests, below we provide a simple example where Assumption \ref{asm:subspace_inclusion} does not hold.
Suppose that $D = 2$ (the treatments are binary).
Let
\begin{alignat*}{3}
B^{\pre, n}
&=
\Big[\,
\Ind(A[\cN(n), \cT_\pre] = 1)
\, ,
\quad
\Ind(A[\cN(n), \cT_\pre] = 2)
\,
\Big]
\in \{0, 1\}^{ |\cN(n)| \times 2 { T_\pre}}.
\nonumber
\end{alignat*}
Intuitively, $B_{\pre, n}$ is an indicator matrix that tracks the training treatment assignment over $\cN(n)$.
\begin{proposition}\label{prop:SIA_linear_independence}
Suppose Assumption \ref{asm:model} holds.
Unless $\text{colrank}( B^{\pre, n} ) =| \cN(n) |$, there exist latent factors $\LF$ and target treatment assignments under which Assumption \ref{asm:subspace_inclusion} cannot hold.
\end{proposition}
Proposition \ref{prop:SIA_linear_independence} shows that the diversity of treatment assignments (as captured by $B^{\pre, n} $) affects the feasibility of Assumption \ref{asm:subspace_inclusion}.
We unpack this relationship in detail in the next section.
Before doing so, we present a negative example in which Assumption \ref{asm:subspace_inclusion} does not hold.
\begin{example}
Suppose $\ba^t= \mathbf{1}_N$ for all $t \in \cT_{\pre}$.
As such, $B^{\pre, n} = [ [1]_{|\cN(n)| \times T_\pre} \, , \, [0]_{|\cN(n)| \times T_\pre} ]$ and $\text{colrank}(B^{\pre, n} ) = 1 < |\cN(n)|$.
One can show that Assumption \ref{asm:subspace_inclusion} does \emph{not} hold unless $\tilde{\ba}_{\cN(n)} = \mathbf{1}$ or $\mathbf{2}$.
The reason Assumption \ref{asm:subspace_inclusion} does not hold is that all of $n$'s neighbors have only been observed under the \emph{same} treatment.
As such, there is no way for NSI to estimate the potential outcome of $n$ under $\tilde{\ba}_{\cN(n)}^\top= [2, 1, 1, \hdots]$, for example, where only the first neighbor is treated.
It is impossible for NSI (or any estimator, for that matter) to disentangle the spillover of the first neighbor from that of any other neighbor because the training measurements only contain data in which all neighbors receive the same treatment.
The validity tests in Section \ref{asm:subspace_inclusion} provide a way of testing for whether the treatment assignment and the observations during the training period are rich enough.
\end{example}
\medskip
{
\noindent
{\bf Assumption \ref{asm:components}.}
This condition requires that the number of components used by NSI, given by $\kappa$ matches the rank $r_\pre$ of $\bbE[ Z_{\pre, \cI^{(n)}} | \LF, A ]$.
Since $\bbE[ Z_{\pre, \cI^{(n)}} | \LF, A ]$ is unknown in practice,
one must estimate $r_\pre$,
which can be done by applying an elbow point (or knee point) method to the spectrum of the observed matrix $Z_{\pre, \cI^{(n)}}$ \citep{zack1977automatic, satopaa2011finding}.
There are other heuristics for setting $\kappa$, such as the universal thresholding method given in \citep{chatterjee2015matrix}.
Alternatively, suppose we have an estimate $\bar{r}$ of the model ``rank'' $r$, defined in Section \ref{sec:setup}.
By our model \eqref{eq:full_model},
$r_\pre$ is upper bounded by $r | \cN(n) |$,
which suggests that one can use the heuristic $\kappa = \bar{r} |\cN(n)|$.
It also suggests that
one should always set $\kappa$ to be at least $|\cN(n)|$,
assuming that $r \geq 1$.
}
\section{Validity tests}\label{sec:validity_test}
We present two validity tests for Assumption \ref{asm:subspace_inclusion}, one of the key enabling assumptions of Theorems \ref{thm:finite_sample_consistency} and \ref{thm:asym_normality}.
The first test can be performed \emph{before} any data is collected.
It tests for whether the treatment assignment in the training period is diverse enough relative to the target treatment assignment in the prediction period.
The second test can be performed only \emph{after} the data is collected and, as such, is a relatively stronger test.
Proofs for this section can be found in Appendix \ref{app:proofs_tests}.
\subsection{Validity test \#1: Pre-Data Collection}
The first test can be run \emph{before} the prediction samples are collected.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\textbf{TrainingTreatmentTest.}
This test takes in one hyperparameter $\bar{r} \in \bbN_{> 0}$, which is an estimate of the model ``rank'' $r$ (see Section \ref{sec:lf_model}).
If one does not have a good estimate, $\bar{r}$ can also be an upper bound on $r$.
In order to run this test, we first define several ``masking'' matrices.
For a given treatment $a \in [D]$, let $B^{\pre}(a) \in \{0, 1\}^{N \times T_{\pre}}$ and $\bb^{\post}(a) \in \{0, 1\}^{N}$ be defined such that their $(i, t)$-th elements are
$
B_{i t}^{\pre}(a) = \Ind(A^{\pre}_{i t} = a)$
and
$
\tilde{b}_{i}^{\post}(a) = \Ind(\tilde{a}_i = a) .
$
That is, the $(i, t)$-th entry of $B^{\pre}(a)$ is $1$ if and only if unit $i$ at measurement $t$ receives treatment $a$ under the training treatments $A^{\pre}$.
Similarly, the $i$-th entry of $\tilde{\bb}^{\post}(a)$ is $1$ if and only if unit $i$ is assigned the target counterfactual treatment $a$ under $\tilde{\ba}$.
Let $B^{\pre}$ and $\tilde{B}^{\post}$ be the concatenated matrices across different treatments:
\begin{align*}
B^{\pre} &= [B^{\pre}(1) , B^{\pre}(2) , \hdots, B^{\pre}(D)]
\in \{0, 1\}^{N \times T_{\pre} D}, \\
\tilde{B}^{\post} &= [\tilde{\bb}^{\post}(1) , \tilde{\bb}^{\post}(2) , \hdots, \tilde{\bb}^{\post}(D)]
\in \{0, 1\}^{N \times D}.
\end{align*}
For the hyperparameter $\bar{r}$, the NSI estimator passes the \textsc{TrainingTreatmentTest} if
\begin{enumerate}
\item $\text{columnspace}(\tilde{B}^{\post} [\cN(n), : ] ) \subseteq \text{columnspace}(B^{\pre}[\cN(n), : ])$, and
\item for every $t \in \cT_{\pre}$, the treatment $A[\cN(n), t]$ is repeated at least $\bar{r} D$ times in training;
\end{enumerate}
otherwise, it fails.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\textbf{Connecting the \textsc{TrainingTreatmentTest} to Assumption \ref{asm:subspace_inclusion}.}
The following result formalizes the relationship between the test and Assumption \ref{asm:subspace_inclusion} under a natural data generating process.
\begin{proposition}\label{prop:SIA_rowspace}
Suppose Assumption \ref{asm:model} holds and $\bar{r} = r$.
Suppose that $u_{k, n, \ell} \iid p_u$ and $w_{t, a, \ell} \iid p_w$ for all $k, n \in [N]$, $t \in [T]$,
$a \in [D]$, and $\ell \in [r]$,
where $p_u$ and $p_w$ are continuous and { non-degenerate (i.e., the support of $p_u$ or $p_w$ does not have dimension less than $r$)}.
If \textsc{TrainingTreatmentTest} is passed,
Assumption \ref{asm:subspace_inclusion} holds {almost surely} for any $n$ and target treatment $\tilde{\ba}_{\cN(n)}$ of interest.
\end{proposition}
As such, \textsc{TrainingTreatmentTest} tests whether Assumption \ref{asm:subspace_inclusion} can hold under the training treatments for the given target treatment of interest.
Intuitively, it requires that the training treatments are sufficiently diverse relative to $\tilde{\ba}_{\cN(n)}$.
In Section \ref{sec:experimental_proc}, we provide an experiment design that guarantees \textsc{TrainingTreatmentTest} is passed for any $n$ and $\tilde{\ba}_{\cN(n)}$.
Note that the i.i.d. condition in Proposition \ref{prop:SIA_rowspace} can be relaxed,
as long as the latent factors are always drawn from non-degenerate distributions.
The condition on latent factors ensures that there is enough variation across units and time such that we can isolate the role that training treatment assignments plays in Assumption \ref{asm:subspace_inclusion} from the role that latent factors play.
\subsection{Validity test \#2: Post-Data Collection}
We now furnish a data-driven check for Assumption \ref{asm:subspace_inclusion} that we call the \textsc{SubspaceInclusionTest}.
This test can be run only \emph{after} the training and prediction samples are collected as opposed to the \textsc{TrainingTreatmentTest} test, which can be run beforehand.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\textbf{SubspaceInclusionTest.}
The test takes in three hyperparameters: $\kappa$, $\kappa'$, and $\gamma$.
Note that we overload $\kappa$ (which also appears in Section \ref{sec:estimator}) because both instances refer to an estimate of the rank of $\bbE[Z_{\pre, \cI^{(n)}}]$.
Similarly, let $\kappa'$ denote the estimated rank of $\bbE[Z_{\post, \cI^{(n)}}]$, respectively. (Refer to Appendix \ref{app:preliminaries} for various approaches to selecting parameters
$\kappa$ and $\kappa'$.)
The third $\gamma \in (0, 1)$ is a tunable parameter,
where a smaller $\gamma$ results in a stricter test.
Let $\hat{R}_{\pre} \in \bbR^{|\cI^{(n)}| \times \kappa}$
and $\hat{R}_{\post} \in \bbR^{|\cI^{(n)}| \times \kappa'}$
denote the matrices constructed from the top $\kappa$ right singular vectors of $Z_{\pre, \cI^{(n)}}$ and
the top $\kappa'$ right singular vectors of $Z_{\post, \cI^{(n)}}$,
respectively.
Let
\begin{align*}
\hat{\beta} &= \norm{ (\mathbb{I}_{|\cI^{(n)}|} - \hat{R}_{\pre} \hat{R}_{\pre}^\top ) \hat{R}_{\post} }_F^2 .
\end{align*}
Then,
the NSI estimator passes the \textsc{SubspaceInclusionTest} if $\hat{\beta} \leq (1 - \gamma) \kappa'$;
otherwise, it fails.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\textbf{SubspaceInclusionTest is a data-driven check for Assumption \ref{asm:subspace_inclusion}.}
Let ${R}_{\post}$ and ${R}_{\pre}$ denote the matrices constructed from the right singular vectors of $\bbE \big[ Z_{\pre, \cI^{(n)} } \big| \, \LF, \cO \big]$ and $\bbE \big[ Z_{\post, \cI^{(n)} } \big| \, \LF, \cO \big]$, respectively.
Then, Assumption \ref{asm:subspace_inclusion} can equivalently be stated as requiring that $\text{columnspace} (R_{\post}) \subseteq \text{columnspace}(R_{\pre})$.
Although one cannot directly test for Assumption \ref{asm:subspace_inclusion} since both $\bbE \big[ Z_{\pre, \cI^{(n)} } \big| \, \LF, \cO \big]$ and $\bbE \big[ Z_{\post, \cI^{(n)} } \big| \, \LF, \cO \big]$ are not observable due to noise, we now show that \textsc{SubspaceInclusionTest} is a sample-based test for Assumption \ref{asm:subspace_inclusion} using $\hat{R}_\post$ and $\hat{R}_\pre$.
Recall that \textsc{SubspaceInclusionTest} fails if
$ \hat{\beta} = \norm{ (\mathbb{I} - \hat{R}_{\pre} \hat{R}_{\pre}^\top ) \hat{R}_{\post} }_F^2 \geq (1 - \gamma) \kappa',$
where $\hat{R}_{\pre}$ and $\hat{R}_{\post}$ contain the top $\kappa$ and $\kappa'$ right singular vectors of $Z_{\pre, \cI^{(n)}}$ and $Z_{\post, \cI^{(n)}}$, respectively.
This can be viewed as a test for Assumption \ref{asm:subspace_inclusion} since smaller values of $\hat{\beta}$ indicate the extent to which $\text{columnspace} (\hat{R}_{\post}) \subseteq \text{columnspace}(\hat{R}_{\pre})$.
Indeed, suppose that $R_{\pre} = \hat{R}_{\pre}$, $R_{\post} = \hat{R}_{\post}$, and Assumption \ref{asm:subspace_inclusion} holds; then, $\hat{\beta} = 0$.
As the span of $\hat{R}_{\post}$ moves outside of the span of $\hat{R}_{\pre}$, $\hat{\beta}$ increases.
Since $\hat{\beta} = \norm{ (\mathbb{I} - {R}_{\pre} {R}_{\pre}^\top ) {R}_{\post} }_F^2$ is always upper bounded by $r_{\post}$, which is estimated by $\kappa'$, we use the threshold $(1 - \gamma) \kappa'$ such that the test fails if $\hat{\beta} \geq (1 - \gamma) \kappa'$.
A formal analysis of this test remains important future work.
\begin{remark}
The equivalence between Assumption \ref{asm:subspace_inclusion} and $\text{columnspace} (R_{\post}) \subseteq \text{columnspace}(R_{\pre})$ implies that \textsc{LatentFactorTest} would supersede \textsc{TrainingTreatmentTest} \emph{if} $R_{\pre}$ and $R_{\post}$ are known exactly and the prediction samples are already collected.
However, \textsc{TrainingTreatmentTest} remains useful for two reasons.
First, it can be run even before measurements are collected as it only requires the treatment assignment pattern.
Second, \textsc{LatentFactorTest} requires estimating $R_{\pre}$ and $R_{\post}$, which \textsc{TrainingTreatmentTest} does not.
\end{remark}
\section{NSI's sample complexity: Experiment design} \label{sec:experimental_proc}
In this section, we propose an experiment design based on graph coloring, under which we can precisely answer the question of how should $T, N$ scale to enable the estimation of $\IPO{n}$ within $\varepsilon \in (0,1)$?
Proofs for this section can be found in Appendix \ref{app:proofs_exp}.
\subsection{Graph coloring-based experiment design}\label{sec:exp_procedure}
\begin{figure*}[t]
\centering
\includegraphics[width=\textwidth]{exp_design_3}
\caption{Illustration of experiment design.
Consider a unit $n$ and network graph $\cG$ (top left).
The experiment design generates the two-hop graph $\cG'$ by connecting every unit to its two-hop neighbors,
which translates to adding edges,
as given by the purple dotted lines (top center).
Next, color $\cG'$ such that no units that are adjacent in $\cG'$ share a color (top right).
This coloring is used to generate the training treatment assignments.
Specifically, consider $D = 2$.
Then, during each $\bar{T}$ training measurements,
every unit receives the control treatment $1$, except units of a specific color.
}
\label{fig:exp_design}
\end{figure*}
We begin by describing the experiment design.
The design assumes access to a subroutine $\textsc{TwoHopColoring}(\cG)$ that outputs $\textsc{NumColors}, \textsc{Coloring}$ and proceeds in two steps: (1) Construct the graph $\cG' = ([N], \cE')$ such that $(i, j) \in \cE \implies (i, j) \in \cE'$ and $(i, j) , (j, k) \in \cE \implies (i, k) \in \cE'$.
That is, $\cG'$ is constructed by taking $\cG$ and adding edges between every node and its two-hop neighbors.
(2) Perform a coloring on $\cG'$ by
labeling the vertices in a graph such that no two adjacent vertices receive the same color,
greedily adding colors whenever an existing color cannot be used.
(Under a color, vertices of the same color form an independent set of $\cG'$.)
Let $\textsc{NumColors}$ denote the number of colors required to color $\cG'$.
Let $\textsc{Coloring} \in [\textsc{NumColors}]^N$ denote the colors assigned to each node (or unit).
As before,
let $\bar{r} \in \bbN_{> 0}$ denote an estimate (or, alternatively, an upper bound) of the model ``rank'' $r$.
Then, the experiment design procedure proceeds as follows.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\emph{Step 1}.
Let $\textsc{NumColors}, \textsc{Coloring} = \textsc{TwoHopColoring}(\cG)$.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\emph{Step 2}.
Divide the colors into $T' = \lceil \frac{\textsc{NumColors}}{D - 1} \rceil$ disjoint sets $\{ \textsc{Colors}_\ell : \ell = 0, 1, \hdots, T' - 1 \}$
such that $\textsc{Colors}_1$ contains the first $D - 1$ colors,
$\textsc{Colors}_2$ contains the next $D - 1$ colors, and so on.
\noindent
\emph{Step 3}.
Then, for $\ell = 0, 1, \hdots, T' - 1$,
let $\bc^\ell \in [D]^N$ denote a treatment vector such that
\begin{align*}
a_i^\ell &=
\begin{cases}
\textsc{Coloring}_i \, \text{mod} (D - 1) + 2 , & \text{if } \textsc{Coloring}_i \in \textsc{Colors}_\ell ,
\\
1 , & \text{otherwise.}
\end{cases}
\end{align*}
The intuition behind $\bc^\ell$ is as follows.
Since $\textsc{Colors}_\ell$ contains at most $D - 1$ colors,
each color in $\textsc{Colors}_\ell$ can be associated with a different treatment in $\{ 2, 3, \hdots, D\}$.
Units with one of those colors receive the corresponding treatment.
That is, any unit $i$ for which $\textsc{Coloring}_i \in \textsc{Colors}_\ell$
is assigned the corresponding treatment in $\{ 2, 3, \hdots, D\}$.
All other units receive treatment $1$.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\emph{Step 4}.
Let $\cT_{\pre}$ be divided into disjoint sets $\{ \cT^\ell_{\pre} : \ell = 0, 1, \hdots, T' - 1 \}$,
each of length $\bar{T} \geq \bar{r} D$ such that $T_{\pre} = \bar{T} T'$.
Then,
let
$A^{\pre} \in [D]^{N \times T_{\pre}}$ be defined such that,
$
A^{\pre}[:, t] = \bc^{\ell} \quad \forall t \in \cT^\ell_{\pre}
$
for all $\ell = 0, 1, \hdots, T' - 1$.
For the remainder of this work, we assume $\bar{T} = \bar{r} D$ unless otherwise stated.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\emph{Step 5}.
Let the prediction treatment of each unit be assigned i.i.d. uniformly at random from the $D$ possible treatments,
i.e.,
$a^\post_i \iid \text{Unif}(D)$ for all $i \in [N]$.
\ifarxiv
\\
\else
\medskip
\fi
\noindent{\bf Discussion of experiment design.}
The experiment design described above uses the graph coloring over the two-hop version of $\cG$ to assign treatments.
The training measurements are divided into $T'$ disjoint sets---that we will call ``periods''---denoted by $\cT^\ell_\pre$ for $\ell = 0, 1, \hdots, T' - 1$.
The treatment assignment during each period remains constant, i.e., for any $\ell$,
$\ba^t = \bc^\ell$ for all $t \in \cT^\ell_\pre$.
The experiment design ensures several important properties hold.
First, all nodes that receive the same color also receive the same treatment at any $t \in \cT_\pre$.
Second,
nodes that receive the same color have to be at least three hops away from one another,
which ensures that, for any neighborhood $\cN(n)$ of an arbitrary node $n$,
no two nodes receive the same non-control treatment at any given $t \in \cT_\pre$.
Third, each node receives the control treatment $1$ for every period,
except for one period during which it receives a non-control treatment.
The non-control treatment that a node receives is given by $ \textsc{Coloring}_i \, \text{mod} (D - 1) + 2$, where $\textsc{Coloring}_i$ denotes the color assigned to unit $i$.
Lastly, each period has length $\bar{T} \geq \bar{r} D$.
We show that these properties are important to proving Lemma \ref{lem:training_treatments_test_passes} in the next section.
See \citet{jensen2011graph} for further information on graph colorings.
\subsection{Theoretical guarantees on experiment design}
We present two results.
The first establishes that the graph-theoretic experiment design described in Section \ref{sec:exp_procedure} guarantees that \textsc{TrainingTreatmentTest} is passed.
\begin{lemma}\label{lem:training_treatments_test_passes}
Suppose Assumption
\ref{asm:model} holds.
If the training treatments $A^{\pre}$ are assigned as in Section \ref{sec:exp_procedure},
then \textsc{TrainingTreatmentTest} is passed for any unit $n$ and treatments $\cfAn$.
\end{lemma}
Importantly, Lemma \ref{lem:training_treatments_test_passes} gives a guarantee for \emph{any} unit $n$ and counterfactual treatments $\cfAn$ of interest, i.e., for all $N D^d$ possible estimands of interest.
That is, the experiment design in Section \ref{sec:exp_procedure} can be used to ensure that \textsc{TrainingTreatmentTest} is passed for any target estimand of interest.
{Moreover, the experiment design can be applied to any graph of interest (and any valid two-hop coloring, as described in Section \ref{sec:exp_procedure}).}
In Appendix \ref{app:tailor_exp_design}, we discuss how one can adapt our experiment design to be less stringent if one is interested in a \emph{specific} choice of $n$ and $\cfAn$.
The next result shows that the number of training measurements required under the graph-theoretic experiment design is $O(d^2)$,
where $d$ denotes the maximum degree of $\cG$.
\begin{lemma}\label{lem:treatment_schedule_complexity}
The number of training measurements required by the experimental procedure in Section \ref{sec:exp_procedure} is
$T_{\pre} = \bar{r} D \lceil \frac{\textsc{NumColors}}{D - 1} \rceil$, where
$\textsc{NumColors} \leq \text{Degree}(\cG') + 1$.
As a result, $T_{\pre} \leq \frac{\bar{r} D (d^2 + D)}{D - 1}$.
\end{lemma}
By Lemma \ref{lem:treatment_schedule_complexity}, the experiment design requires $T_\pre = O(d^2)$ training measurements.
Since
$r|\cN(n)| = r d$ donors are needed for a given $n$ and $\tilde{\ba}_{\cN(n)}$ of interest (as discussed in Section \ref{sec:assumptions}),
this result shows that one needs $O(d^3)$ training samples under the experiment design to guarantee that \textsc{TrainingTreatmentTest} passes for a given unit and target treatment of interest.
That is, with $O(d^3)$ training samples,
there is enough variation in the training data such that it is possible to generalize to the training data to a given target counterfactual treatment of interest.
\subsection{Data requirement: Generative example}
In this section,
we examine how much data is needed for the NSI estimator to get within $\varepsilon$ accuracy,
using regular graphs as an illustrative setting.
\begin{assumption}\label{asm:regular_graph}
$\cG$ is a $d$-regular graph.
\end{assumption}
\begin{assumption}\label{asm:unif_lf}
Assume that each $u_{j, i, k} \iid \text{Unif}\hspace{1pt}(-\frac{1}{\sqrt{r d}} , \frac{1}{\sqrt{r d}})$ for all $j, i \in [N]$ and $k \in [r]$.
Further, each $w_{t, a, k} \iid \text{Unif}\hspace{1pt}( - \frac{1}{\sqrt{r d}}, \frac{1}{\sqrt{r d}})$ for all $t \in [T]$, $a \in [D]$, and $k \in [r]$.
\end{assumption}
\begin{proposition}\label{prop:reg_error}
Suppose $\bar{r} = r$.
Suppose Assumptions \ref{asm:model}, \ref{asm:conditional_exo},
\ref{asm:subG_noise},
\ref{asm:bounded},
\ref{asm:components},
\ref{asm:regular_graph},
and
\ref{asm:unif_lf},
hold.
Suppose that there are at least $\frac{r D (d^2 + D)}{D - 1}$ training measurements assigned according to the experiment design in Section \ref{sec:experimental_proc} and $N = \Omega \left( r^2 d^2 D^{2d + 2} \right)$ units.
Then, there is a set of units $E$ such that $|E| = N - \Theta(\sqrt{N})$
and a method of choosing donors (i.e., units that satisfy Definition \ref{def:node_donors}) such that, for all $n \in E$,
\begin{align*}
&\left|
\hIPO{n} - \IPO{n}
\right|
\\
&\hspace{20pt}= O_P \left(
r^6 d^{10}
\log \left( \frac{ T_\pre N }{D^{d+1}} \right)
{\max} \left(
\frac{1}{T_\pre^{1/4}} ,
\frac{ {D^{(d + 1)/2}} }{ N^{1/4} } ,
{\frac{ N^{1/4} }{ D^{(d+1)/2} T_\pre^{3/2}}}
\right)
\right),
\end{align*}
\end{proposition}
For a $d$-regular graph, Proposition \ref{prop:reg_error} suggests that to achieve error of order $\varepsilon$ with high probability, NSI needs $T_\pre = \tilde{\Omega} \left( \frac{ r^{24} d^{40} }{\varepsilon^4} \right)$.
To understand whether the sample complexity is reasonable, consider a naive alternative.
For a given unit $n$, there are $D^{|\cN(n)|}$ possible counterfactual treatments that could be applied to the neighborhood $\cN(n)$.
Suppose that we do not impose any structure on the potential outcomes,
i.e., we do not assume \eqref{eq:full_model}.
Then, to learn how unit $n$ behaves under every possible neighborhood treatment, one would naively need at least one observation per $D^{|\cN(n)|} \leq D^{d+1}$ possible treatments.
This naive approach would require $\Omega(D^d)$ samples in order to estimate the potential outcome for a given $n$ and any $\cfAn$ of interest.
Moreover, to achieve an error of $\varepsilon$, at least $\frac{1}{\varepsilon^2}$ samples are needed per treatment, which implies $T_\pre = \Omega\left(\frac{D^d}{\varepsilon^2}\right)$ under a naive approach.
\section{Simulations} \label{sec:experiments}
In this section,
we present simulation results illustrating the behavior of the NSI estimator and compare it to two related estimators.
Let $\cG$ be a regular graph with degree $d$, and let the treatments be binary, i.e., $D = 2$.
In each of the experiments below,
we indicate the graph degree.
Let the training treatments be assigned according to the experiment design in Section \ref{sec:experimental_proc}.
Further experiments and details are given in Appendix \ref{app:simulations}.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\textbf{Predictions}.
Note that the NSI estimator \eqref{eq:NSI_estimator_point} can be adapted to produce pointwise estimates
$$\widehat{\bbE} \Big[ Y_{t, n}^{(\tilde{\ba}_{\cN(n)})} \Big] = Z[t, \cI^{(n)}] \hat{\bbE}[Z_{\pre, \cI^{(n)}} | \LF , A ]^+ \bz_{\pre, n} ,$$
such that $\hIPO{n} = \frac{1}{T_\post} \sum_{t \in \cT_\post} \widehat{\bbE} \big[ Y_{t, n}^{(\tilde{\ba}_{\cN(n)})} \big]$.
Under this observation,
Figure \ref{fig:NSI}(a) shows an example of the pointwise estimates given by NSI for an example unit $n$.
Consider the bottom plot.
The solid line gives the ground truth potential outcomes for unit $n$ across measurements $t \in [200]$.
The pointwise estimates produced by NSI
are marked by asterisks $*$, with the 95 percent confidence interval in gray.
The measurements to the left of the vertical line (i.e., in blue and green) correspond to the training set $\cT_{\pre}$ while those to the right (i.e., in red and orange) correspond to the prediction set $\cT_{\post}$.
The top plot gives the spectrum $\{\hat{s}_\ell\}_{\ell=1}^{q}$ produced in Step 1 of Section \ref{sec:estimation_proc}, where the vertical line marks the hard singular value threshold $\kappa$ that is used in Step 1.
In Figure \ref{fig:NSI}(a), $\cG$ is a ring graph ($d = 2$) with $N = 1000$ units, $\epsilon^{(\bc_{\cN(i)})}_{\tau, i} \sim \cN(0, 0.1)$, and $r = 2$.
\begin{figure*}[t]
\centering
\begin{subfigure}[b]{0.31\textwidth}
\centering
\includegraphics[width=\textwidth]{../images/NSI_ring_8.pdf}
\caption{NSI estimates}
\label{fig:y equals x}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.328\textwidth}
\centering
\includegraphics[width=\textwidth]{../images/ring_experiments_mse_across_noise_0.3162_fig1b-sep23.pdf}
\caption{Residuals of NSI estimator}
\label{fig:three sin x}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.334\textwidth}
\centering
\includegraphics[width=\textwidth]{../images/MSE_across_degree_noise_2.pdf}
\caption{MSE for regular graphs}
\label{fig:five over x}
\end{subfigure}
\caption{Simulation results illustrating the performance of the NSI estimator.
(a) considers a specific unit $n$ and counterfactual $\cfAn$ of interest.
The top plots the spectrum produced in Step 1 of NSI (see Section \ref{sec:estimation_proc}).
The bottom visualizes the pointwise estimates
\ifarxiv \else $\widehat{\bbE} \big[ Y_{t, n}^{(\tilde{\ba}_{\cN(n)})} \big]$ \fi produced by NSI for all measurements $t$ in asterisks $*$ with the 95 percent confidence interval in gray. The ground truth potential outcomes \ifarxiv \else ${\bbE} \big[ Y_{t, n}^{(\tilde{\ba}_{\cN(n)})} \big]$\fi are given by the solid lines.
(b) plots the residuals $(\hIPO{n} - \IPO{n})$ across 500 simulations.
(c) plots the MSE across different hyperparameters.
Each group of bars gives the MSE for regular graphs of degree $2$, $4$, and $6$,
as indicated on the $x$-axis.
Within each group of bars,
the left (blue) bars are for $N = 1000$, $T_{\pre} = 100$, and $T_{\post} = 50$;
the middle (red) bars for $N = 1000$ and $T_{\pre} = T_{\post} = 50$;
and the right (yellow) bars for $N = 500$ and $T_{\pre} = T_{\post} = 50$.
}
\label{fig:NSI}
\end{figure*}
As shown in the bottom plot of Figure \ref{fig:NSI}(a), the predictions closely match the ground-truth values.
As shown on top, $6$ components are used to construct the estimates.
Since the network-adjusted rank is $6 $ ($r = 2$ and $|\cN(n)| = 3$),
the fact that NSI uses $6$ components explains why its estimates are fairly accurate.
We provide similar plots for other units and target treatments in Appendix \ref{app:simulations}.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\textbf{Consistency and asymptotic normality}.
Figure \ref{fig:NSI}(b) verifies that the NSI estimates are consistent and asymptotically normal.
Specifically, we let $\cG$ be a ring graph (i.e., $d = 2$) with $N = 1000$ units,
$\epsilon^{(\bc_{\cN(i)})}_{\tau, i} \sim \cN(0, 0.1)$, and $r = 2$.
For each simulation, we randomly generate the potential outcomes of all units under \eqref{eq:full_model} (see Appendix \ref{app:simulations} for details).
We run 500 simulations,
then compute the NSI residuals $(\hIPO{n} - \IPO{n})$ for all units $n \in [N]$ and across all possible counterfactual treatments for each $n$.
That is, we use NSI to estimate $\IPO{n}$ for $\tilde{\ba}_{\cN(n)} = (1, 0, 0)$,
$\tilde{\ba}_{\cN(n)} = (0, 1, 0)$, $\tilde{\ba}_{\cN(n)} = (1, 1, 0)$, and so on.
Figure \ref{fig:NSI}(b) gives a histogram of the NSI residuals.
A Gaussian distribution is fit to the residuals and given by the red line.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\textbf{MSE trends}.
Figure \ref{fig:NSI}(c) summarizes the performance of NSI across different parameters.
The performance is given by the mean-squared error (MSE) across the prediction measurements $\cT_{\post}$, averaged across $50$ units.
Each group of bars gives the MSE for regular graphs of degree $2$, $4$, and $6$,
as indicated on the $x$-axis.
Within each group of bars,
the left (blue) bars are for $N = 1000$, $T_{\pre} = 100$, and $T_{\post} = 50$;
the middle (red) bars for $N = 1000$ and $T_{\pre} = T_{\post} = 50$;
and the right (yellow) bars for $N = 500$ and $T_{\pre} = T_{\post} = 50$.
Each bar is the average of $200$ simulations with $\epsilon^{(\bc_{\cN(i)})}_{\tau, i} \sim \cN(0, 0.1)$, and $r = 2$.
As expected, the MSE increases with degree ({because, holding $N$ fixed, a higher degree leads to fewer valid donors}), fewer nodes ({which also leads to fewer valid donors}), and fewer training measurements.
\ifarxiv
\\
\else
\medskip
\fi
\noindent
\textbf{Comparing to other estimators}.
We also compare the NSI estimator to two others: the SI estimator \citep{agarwal2020synthetic} and a baseline estimator.
The SI estimator is similar to NSI, but SI assumes that there is no spillover and therefore does not account for network interference.
The baseline estimator finds donor units that satisfy Definition \ref{def:node_donors}, then averages the donor units' observed outcomes.
We compare the estimators for a ring graph (details given in Appendix \ref{app:simulations}).
We compare
the estimators for a ring graph under the same parameters as those used in Figure \ref{fig:NSI}(b) averaging
across $200$ simulations, $50$ units, and all possible counterfactual treatments.
The MSEs and R-squared values for the NSI estimator, SI estimator, and baseline estimators are, respectively, \textbf{(0.1174, 0.8735)}, \textbf{(0.2310, 0.8149)}, and \textbf{(3.398, -2.957)}.
Both the NSI and baseline estimators use donor sets that contain, on average, 41 units. The SI estimator uses donor sets with, on average, 166 units.
As such,
even though the SI estimator has more donors,
the performance of NSI is better than that of SI, which is better than that of the baseline estimator.
\section{Conclusion and future work}
There is rising interest in estimating unit-specific potential outcomes.
In this work,
we consider the estimation of unit-specific potential outcomes in the presence of spillover,
i.e., the treatment assigned to one unit affects the outcome of another unit.
We focus on the panel data setting and model spillover as network interference.
As our main contribution, we provide an estimator that we call Network Synthetic Interventions (NSI).
In addition to producing point estimates,
NSI provides confidence intervals.
We show that, under a low-rank latent-factor model and suitable conditions,
the NSI estimates are consistent and asymptotically normal.
We provide two validity tests that determine whether key conditions hold.
We find that obtaining good estimates under spillover requires that the data is rich enough.
To this end,
we provide an experiment design.
There are many paths for future work.
Although the method that we provide comes with strong performance guarantees,
it has strict data requirements, as discussed in Section \ref{sec:assumptions}.
One path for future work would be to explore whether these requirements can be relaxed.
Second, we explore unit-specific potential outcome estimation.
If such fine-grained estimates are not needed,
one could examine whether NSI and its data requirements can be improved for coarser estimands of interest.
Finally, one compelling path for future work would be to test NSI on real-world datasets.
\section*{Acknowledgments}
The authors gratefully acknowledge funding from the MIT-IBM project on Causal Representation, the
National Science Foundation (NSF) grant CNS-1955997,
and the
Air Force Research Laboratory (AFOSR) grant FA9550-23-1-0301.
\bibliography{bib.bib}{}
\bibliographystyle{apalike}
\newpage
\begin{center}
{ \LARGE \bf Appendix}
\end{center}