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.
26,175 characters · 10 sections · 41 citation commands
1 Recovering Network Structure from Aggregated Relational Data using Penalized Regression
Social network data can be expensive to collect. A complete network census can be prohibitively costly and, for this reason, often only obtainable for small populations. breza2017using propose a simple alternative, which is to collect aggregated relational data (ARD). ARD consists of responses to questions of the form “How many of your friends have trait $k$?”, which breza2017using argue can be substantially cheaper to collect than a full network census. They propose a Bayesian estimation procedure for recovering the structure of the social network from ARD under a specific latent space model of network formation hrh2002,mccormick2015latent.
We think that the idea of using ARD as a substitute for network data is an important step to reduce financial barriers to empirical research in network economics. The purpose of our paper is to broaden the applicability of ARD. We show that tools from the high-dimensional statistics literature can be employed to recover the network structure using ARD without imposing a particular parametric model of network formation such as the latent space model. Our estimator can be computed in seconds for samples with hundreds of observations using an accelerated gradient descent algorithm due to ji2009accelerated. We provide easy-to-use code in Python and R and an example that walks through its use at {\tt \href{https://github.com/mpleung/ARD}{https://github.com/mpleung/ARD}}.
Our estimator is motivated by the observation that the task of recovering a network from ARD can be written as a high-dimensional linear regression problem. Without any assumptions on the network, this problem is ill-posed. Our strategy for network recovery is based on the assumption that the latent social network has a low-dimensional structure, namely that its distribution has low effective rank.\footnote{In this paper, a random network with low effective rank is one in which the ratio of the nuclear norm to the Frobenius norm of the expected adjacency matrix is close to 1. See Section (ref) for a formal motivation.} This assumption is inherent in many models used to describe social networks in the statistics and economics literature. Examples include the latent space models used by breza2017using, stochastic blockmodels holland1983stochastic, and degree heterogeneity models graham2017econometric.
When a network has low effective rank, we show that the distribution of network links may be recovered from ARD using a nuclear-norm penalty wainwright2015high. We derive a finite-sample bound on the mean squared error of our estimator for the distribution of network links by adapting arguments from negahban2011estimation. The bound implies that the mean squared error of the estimator is decreasing in the number of traits used in the ARD and increasing in the effective rank of the network. This result can be found in Section (ref) and is, to our knowledge, original.
Our paper makes two main contributions to the empirical literature on network estimation. The first contribution is highlighting this connection between the ARD problem and the nuclear-norm penalization literature. Other recent applications of nuclear-norm penalization in economics include athey2018matrix, beyhum2019square, and moon2018nuclear, although the underlying structure of their estimation problems differ from the ARD network recovery problem in important ways. The second contribution is to demonstrate how to implement the nuclear-norm penalization in practice to a general audience. In service of this second contribution, we have tried to make the exposition of this paper and the supporting materials as nontechnical as possible.
Following breza2017using, we consider a population of $N_2$ agents connected in a network. The ideal but infeasible network census is conducted by interviewing every pair of agents $i, j \in \{1, \ldots, N_2\}$ and asking if they have a social connection, which requires $N_{2}^{2}$ questions. The innovation of breza2017using is to instead collect ARD. To collect ARD, the authors first identify a set of $K$ traits. Traits include characteristics like whether an agent has been arrested, remarried, vaccinated, etc. The authors then conduct two surveys. The first survey is a census of all $N_2$ agents and the authors ask the agents to report their traits. The second survey is conducted with a subsample of $N_{1}$ agents ($N_1 \leq N_2$) and the authors ask the agents to report the number of connections they have to agents in the population with each trait. That is, they ask agents how many friends they have who have been arrested, how many friends they have who have been remarried, how many friends they have who have been vaccinated, etc. This alternative to the full network census only requires $(N_{1}+N_{2})K$ questions where $K < N_{1}$ and is easier to implement logistically.
Let $g_{ij}^{*}$ be an indicator for whether agents $i$ and $j$ would report a link if interviewed. Mathematically, ARD is represented by
where for a collection of $K$ traits, $y_{ki}$ measures the number of agent $i$'s connections that have trait $k$ and $w_{kj}$ is an indicator for whether agent $j$ has trait $k$. The goal is to use the ARD $y_{ki}$ and trait data $w_{kj}$ to learn about the network links, $g^{*}_{ij}$.
A key assumption is that the interviewed agents use precisely the relationships of interest $g_{ij}^*$ to construct their responses to the ARD $y_{ki}$. That is, when asked “How many of your friends have trait $k$?” respondents count exactly those connections given by $g^*_{ij}$.
Let the matrix $Y$ denote the $K\times N_{1}$ collection of ARD $y_{ki}$, $W$ denote the $K \times N_{2}$ collection of traits $w_{kj}$, and $G^{*}$ denote the $N_{2} \times N_{1}$ collection of links $g^{*}_{ij}$. Equation (ref) can be written in matrix form
The problem of recovering $G^{*}$ from $Y$ and $W$ can be viewed as that of finding an $N_{2} \times N_{1}$ matrix $G$ that minimizes the squared-loss
Since it is not generally possible to learn about the existence of a link between two agents that were both not interviewed about ARD in this setting, we take $G$ to be $N_{2}\times N_{1}$ and not $N_{2}\times N_{2}$. breza2017using essentially impute the links of agents not surveyed for ARD, which is also straightforward to do here \citep*[see for instance][]{chatterjee2015matrix}.
If the $N_{2} \times N_{2}$ matrix $W'W$ has full rank, then there exists a unique solution to ((ref))
and $G^{*}$ can be perfectly recovered. Of course, the assumption that $W'W$ is full rank requires that the number of traits used in the ARD survey exceeds the size of the population ($K \geq N_{2}$), which defeats the whole point of using ARD as a low-cost alternative to a network census. When $W'W$ is not invertible, ((ref)) is ill-posed, and $G^{*}$ cannot in general be recovered using $Y$ and $W$ without additional information.
Our idea is to exploit the fact that many network formation models of interest, including the latent space model of breza2017using, produce networks that have an underlying low-dimensional structure in the sense that the expected adjacency matrix has {\bf low effective rank}. The next subsection explains this observation. Then in Section (ref), we propose a new estimator by adding a penalty to the objective function (ref) that allows us to exploit the low-dimensional structure and learn about $G^{*}$.
Loosely speaking, the premise of the high-dimensional regression literature is that it is often possible to recover the parameters of a model like ((ref)) by solving a version of a problem like ((ref)) if the minimizer is known to have a certain low-dimensional structure. For instance, if $G^{*}$ is a sparse matrix (i.e. very few pairs of agents would report a connection if interviewed) then the network may be recovered using the LASSO, elastic net, or a related technology. Recent examples in network economics include barigozzi2018nets,belloni2016quantile,de2018recovering,manresa2013estimating,roseidentification.
breza2017using do not assume $G^{*}$ is sparse. They instead specify the link formation rule
where $\nu_{i}$ is agent $i$'s random effect and $z_{i}$ is agent $i$'s position on the surface of the $p$-sphere (both distributed iid with von Mises-Fisher marginals on the hypersphere), $\eta_{ij}$ is an iid mean-zero logistic error, and $\zeta$ is a scalar. This model has a low-dimensional structure, as discussed formally below. To see this intuitively, note that the model admits a random utility interpretation in which the expected transferable utility $i$ and $j$ receive from forming a link is given by
and two agents only form a link if the realized utility exceeds $1/2$. The expected utility matrix $U^{*}$ formed from the $N_{2}\times N_{1}$ collection of $u_{ij}^{*}$ has rank $p+2$ because $z_i$ is $p$-dimensional, while $\nu_i$ is 1-dimensional. Note that breza2017using suggest choosing $p=2$ in practice. The important observation is that this rank is low relative to the sample size $N_1$. It is this low-dimensional structure that our proposed methodology exploits. For a more formal discussion of this low-dimensional structure, see Section (ref).
Unfortunately, a low-rank structure does not typically allow us to recover $G^*$ from $Y$ and $W$ exactly. However, it is still possible to learn about the distribution of $G^{*}$ by adding a nuclear-norm penalty to the least-squares objective (ref). Intuitively, the nuclear-norm penalty encourages the solution to have low rank, analogous to how the $\ell_1$ penalty for LASSO encourages sparse solutions wainwright2015high. We note that the distribution of network links is exactly what is recovered by breza2017using, and we echo their motivation that in many applications recovering the distribution of $G^{*}$ is sufficient to address the research question at hand.
First we define the estimand of interest, the distribution of $G^*$. We assume $G^*$ is realized according to the following nonparametric model of network formation, which substantially generalizes (ref):
where $\eta_{ij}$ is iid with unknown marginal distribution $F_{\eta}$, $\{\alpha_i\}_{i=1}^n$ are unknown vector-valued agent fixed effects, and $f$ is an unknown function. Let $m_{ij}^{*} = E[g_{ij}^*] = F_{\eta}(f(\alpha_{i},\alpha_{j}))$ and $M^{*}$ be the $N_{2} \times N_{1}$ matrix with $ij$th entry $m_{ij}^{*}$. The entries of the matrix $M^{*}$ describe the conditional probability that two agents would report a link if surveyed in a network census given their fixed effects. The entries of the matrix $M^{*}$ parametrize the distribution of $G^{*}$ and are our object of interest.
To estimate $M^*$, we propose the followng penalized version of (ref)
$\lambda$ is a tuning parameter to be chosen by the researcher, $\sigma_t(M)$ is the $t$th singular value of $M$, and $\mathcal{M}$ is a set of matrices.\footnote{For example, $\mathcal{M}$ might be the set of all matrices, in which case we allow for directed and self-links. Alternatively, it might be the set of symmetric matrices with zeros on the diagonal, in which case $\hat M$ is the distribution of an undirected network with no self-links.} The {\em nuclear norm} $||M||_{nuc}$ is large relative to the Frobenius norm $||M||_F$ when the rank of $M$ is large. Hence, adding the nuclear norm penalty encourages the solution $\hat M$ to have low rank. In practice, we recommend choosing the penalty parameter
Details for computing $\hat M$ are given in the next subsection.
As discussed in Section (ref), in large samples, $\hat M$ closely approximates $M^*$ under certain conditions. The estimate can therefore be used to simulate the distribution of $G^{*}$, used as an input into a second stage model, or used to estimate various network statistics based on $G^{*}$ such as the degree distribution or clustering coefficient. We refer the reader to breza2017using for specific applications in development economics.
The nuclear norm penalized problem (ref) can be rewritten as a semidefinite programming problem and solved using tools that are standard in the optimization literature boyd2004convex.\footnote{More precisely, this is the case for the unconstrained problem where $\mathcal{M}$ is the set of all matrices.} In practice this formulation is usually computationally intractable. We instead use a fast accelerated gradient descent (AGD) algorithm due to ji2009accelerated, which is also used in the simulations of negahban2011estimation. We modify the output of the algorithm to impose the (optional) constraint that the network is undirected with no self-links.\footnote{The approximation guarantees in ji2009accelerated are for the unconstrained problem, but our simulations in Section (ref) show that our modification to impose the constraint performs well in practice.} A complete description of the algorithm can be found in Appendix (ref).
In our simulations in Section (ref), the algorithm rapidly computes $\hat M$ for populations with hundreds of agents. For example, when $N_1=N_2=500$, it computes an estimate for the latent space model (Example (ref)) in about five seconds on a laptop with a 2.6 GHz processor and 8 GB RAM. The Bayesian estimation procedure of breza2017using can be computationally costly if the dimension of the latent space or the number of Markov chain draws required for the convergence of the MCMC algorithm is large. The AGD algorithm proposed here does not depend on these parameters.
The basic idea behind our estimator (ref) is that the nuclear-norm penalty encourages the solution to have a nuclear norm $||\hat M||_{nuc}$ close to its Frobenius norm $||\hat M||_F$, which yields a matrix with small effective rank. Under certain conditions, $\hat M$ will closely approximate $M^*$. This is shown formally in Proposition (ref) of Appendix (ref), whose proof applies a result due to negahban2011estimation.
Before discussing the proposition, let us define what we mean by effective rank. Recall that the {\em rank} of $M^{*}$ is given by the number of nonzero singular values of $M^{*}$. The {\em effective rank} of $M^{*}$ is the squared ratio of its nuclear norm to its Frobenius norm. Formally, let $\sigma_{t}(M^{*})$ be the $t$th singular value of $M^{*}$ for $t \in \{1, \dots, N_1\}$. Then the effective rank of $M^{*}$ is given by
This ratio gives a measure of matrix rank because the numerator is always larger than the denominator and the two are only similar in magnitude when most of the spectral values of $M^{*}$ are close to zero. That is, $ER(M^{*})$ is only close to $1$ when $M^{*}$ is well-approximated by a low-rank matrix.
For many popular choices of $F_{\eta}$ and $f$, $M^{*}$ has small effective rank when $\alpha_{i}$ is relatively low-dimensional. In such cases, it is possible to estimate $M^*$ using $Y$ and $W$ using our proposed estimator. We next provide three examples popular in practice, which also form the basis of our simulations in Section (ref). To simplify the exposition, we take $N_{1} =N_{2} = n$.
Simulation evidence given in Table (ref) shows that the effective ranks of networks generated from the three examples are small.
We adapt arguments from negahban2011estimation to derive a finite-sample bound on the mean-squared error of $\hat{M}$. This can be found in Appendix (ref). In large samples and under certain assumptions, the bound can be well approximated by the following simple relationship
where $C$ is a constant. That is, the mean squared error is eventually bounded by the ratio of the effective rank of $M^{*}$ over the number of traits used to construct the ARD.
This bound matches the analogous (but fundamentally different) result for the matrix regression of negahban2011estimation (see their discussion after Corollary 3) and their intuition is as follows. If $M^{*}$ has rank $R$ then it can be described with $(N_{1}+N_{2})R$ parameters. To learn these parameters, ARD contains exactly $N_{1}K$ observations. Supposing $N_{2}/N_{1}$ is bounded, the ratio of the two gives our effective sample size which is, intuitively, the number of observations available to estimate each parameter. It is this ratio that fundamentally determines our bound. To be clear, we expect a similar rate of convergence for any procedure that uses the $N_{1}\times K$ dimensional ARD to learn the $N_{2}\times R$ parameters of a latent space model.
We remark that the optimal mean squared error for $\hat{M}$ when $G^*$ is observed (i.e. $K = N_{2}$) is on the order of $\frac{\ln(N_{2})}{N_{2}}$ gao2015rate. It seems reasonable to us that convergence at a $K$ rate instead of a $N_{2}$ rate is the price to pay for using the relatively low-dimensional ARD to substitute for high-dimensional network data.
If the goal of the researcher is to use $\hat{M}$ as a substitute for $M$ in a second-stage estimation procedure (for example, to construct estimates of network statistics to include in a linear regression model), then it may be the case that $K$ need not be taken to be too large for the estimation error of these network statistics around their population analogs to be unimportant. This is the premise of the literature on semiparametric estimation powell1994estimation. In the simulations below we consider $K = \sqrt{N_1}$ which is consistent with choosing an ARD survey with about ten traits to recover the structure of a network with 100 agents. Note that the villages in banerjee2013diffusion contain 223 households on average. In the cost savings exercise in section 4 of breza2017using, they consider a 30 percent sample, which corresponds to $N_1 \approx 67$. Consequently, we would only survey about $K = 8$ traits in practice in this setting.
We compute $\hat{M}$ for the three models for $M^*$ from Examples (ref)--(ref), which take $N_1=N_2=n$. We construct $W$ as a $K\times n$ matrix of iid Bernoulli$(0.5)$ random variables, where $K$ equals $\sqrt{n}$ rounded to the nearest integer, following the discussion in the previous subsection. Table (ref) displays the mean-squared error $n^{-2} \sum_{i=1}^n \sum_{j=1}^n (M_{ij}^* - \hat M_{ij})^2$. Even for relatively small values of $n$ and $K$ this error is close to zero and generally decreases with the network size $n$.
Our purpose in writing this paper is to illustrate how nuclear-norm penalized least squares can be used to recover the structure of a latent network using ARD. We adapt arguments from negahban2011estimation and demonstrate how in many cases the distribution of network links can be recovered in a nonparametric frequentist framework. We agree with breza2017using that there are many open econometric and practical questions about how ARD ought to be collected and how to formally estimate and make inferences about the underlying parameters of a network formation model. We also think this is an important area for future econometric work.