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.
114,255 characters · 44 sections · 98 citation commands
Post-selection inference for network structure 1
Network structure, as measured by the expected fraction or density of connections between two groups of agents, is used to explain a wide variety of economic phenomena. For example, elliott2014financial use transactions between financial institutions to characterize a core-periphery structure that influences a market's susceptibility to contagion. chetty2022socialI use Facebook friendships between households in poor and rich neighborhoods to measure cross-class social connectedness which predicts economic mobility. jarosch2024granular use worker transitions between Austrian firms to define market segments that determine firm market power. \looseness=-1
In practice, the groups used to define network structure are rarely fixed in advance. They are instead typically selected by agents, institutions, or the researcher in a data-dependent way. For example, elliott2014financial define the core to be the most densely connected institutions in the financial network.\footnote{elliott2014financial refer to soramaki2007topology, who use such a definition in Figure 2 of Section 4.} chetty2022socialI define groups based on neighborhoods, which households can choose using their social ties. jarosch2024granular apply a clustering algorithm to the network of worker transitions to define market segments.\looseness=-1
When the groups are selected, conventional inference procedures that ignore selection can lead researchers to overstate the evidence for a particular network structure and, in extreme cases, even hallucinate structures that do not exist at all. To see what can go wrong, consider Figure 1. This figure depicts an undirected and unweighted network with $97$ edges connecting $84$ nodes. A visual inspection of the network suggests a weak core-periphery structure with a densely-connected core of twelve blue square nodes and a sparsely-connected periphery of seventy-two orange circle nodes. For this network, the difference in the observed fraction of connections for the two groups is large: approximately $0.1$ for the core and $0.01$ for the periphery. Using a stochastic blockmodel for the distribution of network connections,\footnote{This model is used by elliott2014financial in their Section 4. See also Chapter 13.2.3 of jackson2008social.} a conventional 95% confidence interval for the density of connections between the blue squares is $[0.049,0.146]$. For the orange circles it is $[0.010,0.016]$. One might infer from these intervals that the density of connections between the blue squares is unlikely to be less than three times that of the orange circles, and conclude that the network has a statistically significant core-periphery structure. \looseness=-1
The problem with this conclusion is that the statistical model that generated Figure 1 does not have a core-periphery structure. In fact, the network is a draw from an Erdős--Rényi model where every pair of agents is connected with the same probability. It follows that the densities for the blue squares and orange circles are the same. The colors were selected by a spectral clustering algorithm rohe2011spectral and isolated nodes were not depicted. The apparent gap in densities between the two groups is simply a coincidence of idiosyncratic error accentuated by a graph drawing and network clustering algorithm.\footnote{We emphasize that this is not a model-misspecification issue. The Erdős--Rényi model is a special case of the stochastic blockmodel where all connection probabilities are equal. The problem comes from treating the data-selected groups as fixed. That selection can make the conventional inferential approximations invalid is known in the post-selection inference literature, see for instance potscher1991effects,leeb2003finite,leeb2005model.\looseness=-1} \looseness=-1
In this paper, we develop two confidence intervals for the density of connections between groups that are valid post-selection. We introduce the model and inference problem in Section 2. The model is a nonparametric version of a class of dyadic regression models popular in the economics literature. The inference problem is to use network data drawn from the model to infer the density of connections between two groups. The network data may be used to determine which agents belong to which group. As motivated above, and formalized by our Corollary 1 below, conventional inference procedures that do not account for group selection may be invalid. \looseness=-1
We describe our approach to post-selection inference in Section 3. Inference in our setting is complicated by the fact that, in practice, the economics literature takes a relatively exploratory approach to network structure, where groups may be based on demographics, choice data, a community detection or clustering algorithm, or a visual inspection of a graph drawing. In some extreme cases, the researchers are themselves unable to formally articulate exactly how the groups were chosen, which jackson2008social characterizes as an “I will know a community [structure] when I see it” approach in his Section 13.2.2. To accommodate such a wide variety of procedures for selecting groups that may be unstructured, ambiguously-defined, or aggresively data-mined, we recommend confidence intervals that simultaneously cover all nonvanishing group assignments. See Section 3.1.2 for a formal definition. Simultaneous coverage is a stringent requirement when compared to other approaches to post-selection inference (see our literature review in Section 1.2). However, as we argue in Section 3.1.3, it is the only way to ensure post-selection validity for arbitrary group selection rules.\looseness=-1
We derive two post-selection confidence intervals in Section 4. Our first interval follows a strategy of berk2013valid, which is to start with a conventional interval that does not account for selection and inflate its width until simultaneous coverage is achieved. The logic behind our second interval is, to our knowledge, new to the post-selection inference literature. It considers the empirical process defined by the estimation error indexed by the set of possible group assignments, and bounds the deviations of this process using a Talagrand-type concentration inequality due to klein2005concentration. \looseness=-1
While both intervals are easy to compute and scalable to large networks, they do not perform equally well. In particular, a key technical contribution of our paper is to derive an asymptotic lower bound for the width of any collection of intervals that is both simultaneously valid and contains the estimated density. We then find that, among our two intervals, only the width of the second generally attains this bound asymptotically up to a constant factor. This is our Proposition 4 in Section 4.3.2. By contrast, the width of the first interval can be made arbitrarily large relative to this lower bound. We show that the two intervals have a similar width when linking behavior is homogenous, as in an Erdős–Rényi model, but the first interval can be substantially wider for the kinds of sparse and degree-heterogeneous networks common in economic research. Corroborating simulation evidence can be found in Section 5. \looseness=-1
We demonstrate our two intervals with three empirical illustrations in Section 6. The first illustration studies the homophily structure of 100 collegiate Facebook networks and finds evidence for homophily on graduation year and student/faculty status, but not on gender or choice of major. The second illustration studies the hub-and-spoke structure of a trade network and finds that degree, eigenvector, and Bonacich centrality measures all produce robust evidence of a hub-and-spoke structure. The third illustration finds relatively little evidence for a disjoint market structure in a pseudo-employer worker-transition network. From this last illustration, we recommend that researchers exhibit some caution when using clustering algorithms to infer market segments in practice.\looseness=-1
Section 7 concludes. Proof of claims and other details can be found in the appendix.\looseness=-1
While, to our knowledge, our paper is the first to provide simultaneous coverage guarantees for the problem of inferring network structure, there is a large and active econometrics and statistics literature on simultaneous inference in other settings. Examples include post-model selection inference and uniform confidence bands for structural, density, or impulse response functions. See Chapter 9 of lehmann2006testing, reviews by chernozhukov2015valid,KuchibhotlaKolassaKuffner2022, and, for specific examples, working1929applications,scheffe1953method,tukey1953problem,gine2010confidence,hardle2010confidence,liu2010simultaneous,horowitz2011applied,lounici2011global,horowitz2012uniform,horowitz2017nonparametric,hall2013simple,berk2013valid,chernozhukov2014anti,belloni2015some,lee2017doubly,zhang2017simultaneous,chen2018optimal,freyberger2018uniform,kato2018uniform,bachoc2019valid,kato2019uniform,montiel2019simultaneous,bachoc2020uniformly,davezies2021empirical,frandsen2021partial,chiang2023inference,cattaneo2024uniform,mccloskey2024hybrid,chen2025adaptive,frandsen2025simultaneous. \looseness=-1
A technical complication that distinguishes our paper from this literature has to do with the size of the index set. In our setting, the number of possible group pairs grows exponentially with the number of agents. One consequence of this regime is that it is not computationally feasible to compute objects like the largest t-statistic or smallest p-value over the index set. Another consequence is that we do not know of any natural way to justify a confidence interval based on a Gaussian approximation or a bootstrap procedure.\footnote{For example, chernozhukov2022improved study Gaussian and bootstrap approximations for the maximum coordinate of a centered sample mean of $n$ independent $p$-dimensional random vectors, obtaining bounds that depend polynomially on $\log p$. In our setting, where $p$ is the size of the index set of possible group pairs, $p$ is exponential in the number of nodes, and these bounds do not yield a vanishing approximation error. Their Remark 2.2 indicates that some logarithmic dimension dependence is sharp in general.} This means that many popular algorithms for constructing simultaneous confidence intervals in the literature KuchibhotlaKolassaKuffner2022 are not justified in our setting.\looseness=-1
To deal with this complication, our intervals build on the finite sample concentration inequality literature. In particular, our second interval uses a Talagrand-type result due to klein2005concentration, combined with a novel bound building on alon2006approximating,gittens2009error, which does not restrict the cardinality of models being compared. In the literature, our use of Talagrand's inequality has some conceptual precedence in the work of lounici2011global, who consider a different problem of deconvolution density estimation. See Section 1.1 of chernozhukov2014anti for a discussion. \looseness=-1
One alternative to simultaneous coverage is conditional coverage, where coverage is guaranteed conditional on a selection event or for a specific group selection procedure. Examples include inference on ranks andrews2024inference,mogstad2024inference,petrou2024inference, inference after model selection fan2001variable,PoetscherLeeb2009,belloni2012sparse,BelloniChernozhukovHansen2014,Efron2014,Farrell2015,lee2016exact,markovic2017unifying,chen2023selective,gao2024selective,kelekidou2025high, and inference after sample splitting, data fission, or data thinning Moran1973,Cox1975,FanLv2008,MeinshausenMeierBuehlmann2009,RinaldoWassermanGSell2019,DiCiccioDiCiccioRomano2020,RitzwollerRomano2023,neufeld2024thinning,fava2025training,leiner2025fission. Hybrid approaches are considered by mccloskey2024hybrid,ZrnicFithian2024. Another alternative to simultaneous coverage is average coverage, where coverage is guaranteed in expectation over a distribution of selection events. See, for instance, ArmstrongKolesarPlagborgMoller2022,LiuMoonSchorfheide2023. Typically, simultaneous coverage implies conditional and average coverage, but the converse is not true KuchibhotlaKolassaKuffner2022. In addition, these alternatives typically require the researcher to specify and commit to a specific selection procedure or a distribution over selection events. A benefit of these alternatives, however, is that the associated intervals are potentially shorter. \looseness=-1
Our paper shares some similarities with, but is fundamentally different from, the literature that infers the parameters of a model with a latent group structure, sometimes called discrete heterogeneity. See, for instance, BonhommeManresa2015,SuShiPhillips2016,LuSu2017,BonhommeLamadonManresa2022,chetverikov2022spectral,MeleHaoCapePriebe2023,Jochmans2024,KitamuraLaage2024. What distinguishes our problem of inferring network structure from this literature is that, in our setting, we do not assume that the groups selected by the researcher are (or are approximations of) some latent heterogeneity that determines (and is identified from) the distribution of network connections. Another strand tests for the presence or number of communities in a network. See, for instance, bickel2016hypothesis,lei2016goodness,Auerbach2022testing. These papers do not consider our problem of post-selection inference for the density of connections between communities. \looseness=-1
We describe three settings in the literature where researchers conduct inference about network structure. These examples motivate our model and assumptions in Section 2, our focus on simultaneous coverage in Section 3, and our empirical illustrations in Section 6 below. \looseness=-1
Social networks are often thought to have a homophily structure where agents with similar socioeconomic characteristics such as gender, race, and income are densely connected and agents with different demographic characteristics are sparsely connected. The differences in densities amongst agents of different characteristics has been used to explain the adoption of social norms, social segregation, and economic mobility. See, for instance, marmaros2006friendships,currarini2009economic,goeree20101,golub2012homophily,zeltzer2020gender,chetty2022socialI,chetty2022socialII,michelman2022old. We later argue that because researchers often compare the densities associated with many characteristics, some of which are choices that are potentially shaped by the network, these densities are natural candidates for post-selection inference.\looseness=-1
Trade and production networks are often thought to have a core-periphery or hub-and-spoke structure where a small number of densely connected agents form the core of the network and a large number of sparsely connected agents form the periphery. The density of connections amongst core agents in a core-periphery structure has been used to explain aggregate fluctuations in economic output and a financial market's susceptibility to contagion. See, for instance, acemoglu2012network,acemoglu2015systemic,carvalho2014micro,elliott2014financial,jackson2024credit,PietrosantiRainone2023,buccheri2025realized. We later argue that because the core or hub agents are typically determined using the network connections, the resulting densities are naturally post-selection objects.\looseness=-1
Worker-flow networks are often used to define market segments that measure the degree of labor market competition between firms. These segments may be defined using firm characteristics such as industry and location, or constructed with a clustering algorithm. The density of worker transitions within and across these segments describe a market structure: firms in the same segment compete for workers, while firms in different segments do not. See, for instance, schmutte2014free,Nimczik2017,sorkin2018ranking,AbowdMcKinneySchmutte2019,berger2022labor,lamadon2022imperfect,jarosch2024granular,kline2024firm. We later argue that the problem of comparing market structures induced by different clustering algorithms is naturally a post-selection inference problem. \looseness=-1
Section 2.1 describes the model and Section 2.2 the post-selection inference problem. Section 2.3 revisits the three motivating examples of Section 1.3 above. \looseness=-1
A network is defined on two finite sets of agents. There is no restriction on how the two sets are related: the two sets could be identical, have no agents in common, have some but not all agents in common, etc. For $t \in \{1,2\}$ the $t$th set has $N_t$ agents indexed by $[N_t] := \{1,2,\ldots,N_t\}$. Ordered pairs of agents, containing one agent from each set, are indexed by $ij \in [N_1]\times [N_2]$. Every pair of agents $ij$ is endowed with a real-valued random variable $Y_{ij}$ that describes the strength of some social or economic relationship between them. For example, $Y_{ij}$ may describe whether two students are friends or the amount of trade between two regions. The $N_1 \times N_2$ dimensional adjacency matrix $Y$ contains $Y_{ij}$ as its $ij$th entry. When the relationship between two agents is not well-defined, we put a $0$ in the relevant entry of $Y$. For example, in the context of a social network, both sets may contain agent $i$, but it often does not make sense for $i$ to be friends with themself. In this case, we follow the convention that sets $Y_{ii} = 0$. This convention should not be interpreted as treating structurally impossible relationships as observed non-links. When the network includes relationships that are not well-defined, the density of connections should be normalized in a way that does not count them, see Remark 6 below. \looseness=-1
When the two sets of agents are identical, we say the network is unipartite. When they contain no agents in common we say it is bipartite. The network may also be directed or undirected. In a directed network, a pair of agents may be associated with two connections, one describing the connection in the direction from $i$ to $j$ and another describing the direction from $j$ to $i$. A convention in the literature is to represent unipartite directed networks with an asymmetric adjacency matrix where the $ij$th entry corresponds to one direction and the $ji$th entry corresponds to the other. In an undirected network, every pair of agents is associated with at most one connection, and a convention is to describe unipartite undirected networks with a symmetric adjacency matrix where both the $ij$th and $ji$th entries describe the connection between agents $i$ and $j$. In this paper, we follow the convention for directed but not undirected unipartite networks. For undirected unipartite networks with no loops we instead represent the network with an asymmetric upper diagonal adjacency matrix where the $ij$th entry describes the relationship between $i$ and $j$ if and only if $i < j$. The adjacency matrix contains $0$ in every entry where $i \geq j$. We adopt this convention because it helps simplify our notation. We do not believe it to be restrictive in practice. \looseness=-1
Finally, the network may be weighted, where the entries of $Y$ take values in $\mathbbm{R}$, or unweighted, where they take values in $\{0,1\}$. In the unweighted case, we follow a convention where a value of $1$ indicates that a relationship exists and a value of $0$ indicates that it does not exist or it is not well-defined. \looseness=-1
While the term “network structure” is ubiquitous in the network economics literature, we do not know of any previous work that gives a formal definition. To provide one, we assume that the entries of $Y$ are real-valued random variables, the variation of which is determined by latent variables such as agent characteristics, link covariates, taste shocks, etc. Some of this variation is “systematic.” It reflects social, economic, geographic, or institutional determinants of link formation that make some pairs of agents more likely to connect than others. The remaining variation is “idiosyncratic.” It reflects residual sources of variation such as idiosyncratic taste shocks, measurement error, or reporting error, not of interest to the researcher. Broadly speaking, when conducting inference about network structure, the goal of the researcher is to filter out the idiosyncratic and focus on the systematic variation. \looseness=-1
To formalize this intuition, we represent the systematic variation using the sigma-field $\mathcal{H}$. For each pair $ij$, we define $F_{ij}(y):=\mathbbm P(Y_{ij}\leq y\mid \mathcal H)$ to be the conditional distribution function of $Y_{ij}$ given $\mathcal H$. The $N_1\times N_2$ matrix $F$ contains $F_{ij}$ as its $ij$th entry. We call a generic matrix of conditional distribution functions $F$ a random graph model, and use $\mathcal F$ to denote the set of possible random graph models. Throughout the paper we work conditionally on $\mathcal H$ and often suppress this conditioning in our notation. Equivalently, one may view a fixed $F\in\mathcal F$ as a realized conditional law of the network. When we take suprema over $F\in\mathcal F$ below, we are taking suprema over possible realized conditional laws.\looseness=-1
The conditional mean of $Y_{ij}$ is denoted $\mu_{ij}:=\mathbbm E[Y_{ij}\mid\mathcal H]$, and the $N_1\times N_2$ matrix $\mu$ contains $\mu_{ij}$ as its $ij$th entry. Similarly, $\epsilon_{ij}:=Y_{ij}-\mu_{ij}$, $\sigma_{ij}:= \sqrt{\mathbbm E[\epsilon_{ij}^2\mid\mathcal H]}$, and $\epsilon$ and $\sigma$ are the corresponding matrices. By construction, $\mathbbm E[\epsilon_{ij}\mid\mathcal H]=0$. We sometimes call $\mu$ the conditional mean of $Y$ and $\sigma$ the conditional standard deviation of $Y$. \looseness=-1
We use the term network structure to refer to functions of the entries of the conditional mean matrix $\mu$. The problem of inferring network structure is that of conducting statistical inference on functions of the entries of $\mu$ using $Y$ as data. The idea behind this definition is that $\mu$ collects the systematic component of link formation after conditioning on $\mathcal H$, i.e. the social, economic, geographic, institutional, or latent forces that make some pairs more likely to connect than others. The entries of $\epsilon$ describe the residual variation of $Y$, such as taste shocks and other residual consequences of human indeterminacy.\looseness=-1
We impose two main restrictions on $\mathcal{F}$. The first restriction on $\mathcal{F}$ is that for every $F \in \mathcal{F}$, the support of $F_{ij}$ is contained in $[-B,B]$ for some finite $B$. The second restriction on $\mathcal{F}$ is that, conditional on $\mathcal H$, the entries of $Y$ are independent with conditional distributions $F$, conditional means $\mu$, and conditional standard deviations $\sigma$. Since the distributional objects in the paper are interpreted conditionally on $\mathcal H$, we often suppress this conditioning in the notation and refer to the entries of $\epsilon$ as independent.\looseness=-1
The following Assumption 1 summarizes our model with these two restrictions. \looseness=-1
We consider the bounded support condition to be relatively innocuous, since in many settings the network is unweighted and so the entries of $F$ have support $\{0,1\}$. A consequence of this assumption is that the entries of $\mu$ and $\sigma$ exist and are finite. We conjecture that it is possible to weaken this assumption to a tail bound, but leave such an extension to future work.\looseness=-1
Conditional independence is restrictive, but common in the literature that conducts inference on network structure, see Remark 4 below. The assumption is sometimes controversial because, in some settings, independent network connections are thought to rule out triadic closure, strategic complementarities, latent-space geometry, or other interdependencies that may drive network formation in practice. In our framework, however, the sigma-field $\mathcal{H}$ that defines $\mu$ is left unrestricted. As a result, the assumption does not rule out these sorts of interdependencies insofar as they define the network structure represented by $\mu$. We do rule out these interdependencies in $\epsilon$ once $\mathcal{H}$ has been fixed, however. \looseness=-1
Returning to the dyadic model in Remark 3, if $\{\eta_{ij}\}_{i\in[N_1],j\in[N_2]}$ has entries that are independent conditional on the sigma-field generated by $\{u_k,v_l,X_{kl}\}_{k\in[N_1],l\in[N_2]}$ (a common assumption in the literature), then the residuals $\{\epsilon_{ij}\}_{i\in[N_1],j\in[N_2]}$ are conditionally independent. In this case, the entries of $Y$ may be dependent unconditionally through $\mathcal H$, but our assumption is that the remaining variation around $\mu$ is conditionally independent.\looseness=-1
A similar conditioning argument appears in the exchangeable-network literature, which starts from the assumption that the matrix $Y$ is a finite subarray of an infinitely exchangeable population and then appeals to the Aldous--Hoover--Kallenberg representation theorem to justify the model $Y_{ij}=f(t,u_i,v_j,w_{ij})$, where $t$, $\{u_i\}_{i\in[N_1]}$, $\{v_j\}_{j\in[N_2]}$, and $\{w_{ij}\}_{i\in[N_1],j\in[N_2]}$ are mutually independent random variables with standard uniform marginal distributions.\footnote{For instance, Theorem 7.22 and Corollary 7.23 of kallenberg2006probabilistic. For undirected unipartite networks, the analogous representation replaces $(u_i,v_j)$ by $(u_i,u_j)$ and imposes symmetry. The assumption that the latent variables have uniform marginal distributions is without loss.} Examples include bickel2009nonparametric,davezies2021empirical,menzel2021bootstrap,chiang2023inference,cattaneo2024uniform,chiang2026gaussian. Setting $\mathcal{H} = \sigma\left(t, \{u_i\}_{i\in[N_1]}, \{v_j\}_{j\in[N_2]}\right)$, $\mu_{ij} = \mathbbm E[Y_{ij}\mid \mathcal{H}], and \epsilon_{ij}=Y_{ij}-\mu_{ij}$ gives a representation in which the entries of $\epsilon$ are conditionally independent. This literature often frames the resulting conditional independence as relatively unrestrictive because exchangeability is viewed as a mild restriction.\looseness=-1
In many exchangeable-network settings, it is natural to condition only on the global variable $t$ and conduct inference on $\mu_{ij} = \mathbbm E[Y_{ij}\mid t]$. This estimand may represent, for example, the average density of an exchangeable population. We do not consider such an estimand in our paper, however, because it integrates out the node-level heterogeneity that generates heterogeneous network structure. That is, under this definition of $\mathcal{H}$, every entry of $\mu$ is the same, so the network is homogeneous by construction and so cannot exhibit a homophily, core-periphery, etc. structure. \looseness=-1
Our post-selection coverage guarantee in Section 3 below is asymptotic in that it refers to the limit of a sequence of random graph models. The dimensions of the models diverge along the sequence. Formally, our asymptotic arguments refer to the infinite sequence $\{\mathcal{F}(n)\}_{n \in \mathbbm{N}}$ where for every $n \in \mathbbm{N}$, $\mathcal{F}(n)$ is the set of all random graph models in $\mathcal{F}$ whose dimensions both exceed $n$, i.e. if $(N_1(F),N_2(F))$ are the dimensions of a fixed random graph model $F$, then $\mathcal{F}(n) := \{F \in \mathcal{F}: \min(N_1(F),N_2(F)) \geq n\}$. Because $F$ is interpreted as a realized conditional law given $\mathcal H$, the conditioning sigma-field is also allowed to vary along the asymptotic sequence. In our notation going forward we suppress the $(n)$ and $(F)$ arguments, in addition to the dependence on $\mathcal{H}$, writing $\limsup_{F \in \mathcal{F}: N_1,N_2 \to \infty}$ instead of $\limsup_{n \to \infty}\sup_{F \in \mathcal{F}(n)}$, $\liminf_{F \in \mathcal{F}: N_1,N_2 \to \infty}$ instead of $\liminf_{n \to \infty}\inf_{F \in \mathcal{F}(n)}$, and $\lim_{F \in \mathcal{F}: N_1,N_2 \to \infty}$ when the two are equal. We also write $N_1,N_2 \to \infty$ instead of $n \to \infty$. \looseness=-1
Nearly every quantity we define in our paper is allowed to vary with $n$ along the sequence with three exceptions. The first exception is the uniform absolute bound on the support of the entries of $F$, given by $B$. The second exception is the confidence level, given by $\alpha$. The third variable is a uniform lower bound on the relative group sizes, given by $c$ in Section 3.1.1 below. In principle, one could amend our proofs to allow these quantities to also vary with $n$, however this would complicate the arguments and since, to our knowledge, doing so has no clear benefit, we do not pursue this in our paper. \looseness=-1
We focus on the expected fraction or density of connections between two groups of agents
where, for each $t \in \{1,2\}$ and $i \in [N_t]$, the variable $G_{i,t} \in \{0,1\}$ indicates whether agent $i$ from set $t$ belongs to group $t$ and $M_t := \sum_{i \in [N_t]}G_{i,t}$ is the number of agents in group $t$. The $N_t$ dimensional vector $G_t$ contains $G_{i,t}$ as its $i$th entry.\footnote{ Formally, $G_1$ and $G_2$ are random vectors defined on the same probability space as $Y$, and may be arbitrary measurable functions of $Y$. We assume that $M_1M_2 > 0$ with probability one. Our asymptotic theory below further restricts attention to group pairs with $M_t/N_t$ bounded away from $0$.} Many network structures are described using densities of the form of ((ref)). We illustrate this in the context of our three motivating examples in Section 2.3 below. \looseness=-1
The inference problem is to use the network data $Y$ to construct an asymptotic sequence of confidence intervals (indexed by $n \in \mathbbm{N}$ as in Section 2.1.4 above) for $\theta(G_1,G_2)$ that is uniformly (over $\mathcal{F}(n)$) asymptotically level $1-\alpha$. That is, for a fixed $\alpha \in (0,1)$, to specify a confidence interval $CI(G_1,G_2;\alpha) = [L(G_1,G_2;\alpha), U(G_1,G_2;\alpha)]$ such that
Condition ((ref)) follows Equation 11.8 in Definition 11.1.4 of lehmann2006testing.\footnote{The probability in ((ref)) may be read conditional on the sigma-field $\mathcal H$. Unconditional coverage then follows by iterated expectations.}\looseness=-1
Our only restriction on the groups $G_1$ and $G_2$ (introduced in Section 3.1.1 below) is that the relative group sizes $M_1/N_1$ and $M_2/N_2$ are assumed not to vanish as $N_1,N_2 \to \infty$. Aside from this restriction, the groups can be any collection of the two sets of agents. For example, the groups could be determined by sociodemographic characteristics of the agents such as age, race, or gender. They could describe agent choices such as place of residence, occupation, or political affiliation. They could also be the result of agent interactions over the network such as the diffusion of information or a strategic game played between neighbors. They could also be a binary treatment that is self-selected or assigned by a central planner. They could also be constructed by the researcher using a graph drawing, clustering, community detection, model selection or similar algorithm. Finally, the groups could be formed by combining two or more of the methods above. Our confidence intervals are designed to be used in all of these settings, as we discuss in Section 3 below. \looseness=-1
In these examples, the group assignments can depend on the network connections $Y$. A consequence of this is that a conventional confidence interval that ignores this dependence may fail to cover the parameter of interest at the desired level. We show this analytically as our Corollary 1 in Section 4.3.2 below. Confidence intervals that maintain coverage at the desired level are said to be valid post-selection.\looseness=-1
We revisit our model and assumptions in the context of our three motivating examples. To make out discussion concrete, we focus each example on a single paper from the literature. \looseness=-1
golub2012homophily study the effect of a network's homophily structure on consensus formation in a social network. In their Section 2, the authors suppose that the agents are assigned to types that determine the probability that they form connections. The types may depend on the agent demographic characteristics, socioeconomic status, or choices. For instance, the authors write “a type might consist of the 18-year-old female African Americans who have completed high school, live in a particular neighborhood, and do not smoke.” Network formation is given by a random graph model where the probability that two agents form a connection is determined by their type assignments and the connections are independent across agent pairs conditional on the type assignments, consistent with our Assumption 1. The homophily structure of the network depends on the density of connections between agents of different types, which is an example of our ((ref)). Selection is a concern in this example because researchers consider many possible groups, some of which are based on agent choices (like smoking) which may be informed by the network connections. \looseness=-1
elliott2014financial consider the impact of an interbank lending network's core-periphery structure on the fraction of organizations that would fail in the event of a shock to the assets of one bank in the market. In their Section 4, the authors suppose that the banks are either core or periphery institutions. The core institutions are a maximally connected subgraph of the network\footnote{Let $K$ be the largest positive integer such that there exists a subgraph on $K$ agents where every pair of agents is connected. Then a maximally connected subgraph is one such subgraph. elliott2014financial refer to soramaki2007topology who use this as the definition of the core.} and the remaining institutions make up the periphery. The authors focus their analysis on two parameters: the density of cross-holdings between core institutions and the density of cross-holdings between core and periphery institutions, which are examples of our ((ref)).\footnote{In the core-periphery model of elliott2014financial, there is no statistical uncertainty about which institutions are in the core and which are in the periphery. In Section 3 they do specify a stochastic network formation model where the network connections are independent and identically distributed Bernoulli random variables consistent with our Assumption 1. A more detailed econometric model of interbank lending that satisfies the assumption is specified by PietrosantiRainone2023 in their Section 3.1.2.} Selection is a concern in this example because the definition of the core depends on the network data. \looseness=-1
jarosch2024granular use data on the transitions of workers between firms to characterize the degree of labor market competition between firms. In their Section C.1, the authors specify a random graph model in which links are conditionally independent across firm pairs, consistent with our Assumption 1. In their Table A2, they compare the density of within-market transitions across nine alternative market definitions. They advocate for a definition where the market segments are recovered from a clustering algorithm. To support this choice, they show that the algorithm produces a market structure with a larger density of connections with segments, which is an example of our ((ref)). Selection is a concern in this example because the definition of the clustering algorithm depends on the network data. \looseness=-1
In this section, we propose a strategy for constructing confidence intervals for $\theta(G_1,G_2)$ that are valid post-selection in the sense of ((ref)). Our strategy is to specify a collection of intervals that, under certain regularity conditions, is simultaneously asymptotically level $1-\alpha$ over all group pairs whose relative sizes are bounded below by a fixed positive constant. We then report the interval from this collection corresponding to the selected group $(G_1,G_2)$. We show that the resulting interval will satisfy ((ref)) so long as the size of the selected groups do not vanish with probability approaching one. A key advantage of this simultaneous coverage approach is that the researcher does not need to specify a model for $(G_1,G_2)$ or even articulate how the groups were chosen. \looseness=-1
Section 3.1 defines our simultaneous inference condition. Section 3.2 motivates simultaneous inference in the context of our three motivating examples. \looseness=-1
We define the index set of permissible group assignments to be
where $g_{i,t}$ denotes the $i$th entry of the vector $g_{t}$ and $c \in (0,1/2]$ is an arbitrary constant. In words, $\mathcal{G}_c$ is the set of all group-pairs $(g_1,g_2)$ such that the count of agents in $g_1$ is not smaller than $cN_1$ and the count of agents in $g_2$ is not smaller than $cN_2$. We emphasize that the variable $c$ is fixed and is not allowed to vary along the asymptotic sequence of random graph models (see Section 2.1.4). It is, however, not necessary for the researcher to choose a particular value of $c$ to implement our confidence intervals as this constant does not explicitly appear in any of our constructions.\looseness=-1
We assume that there exists a $c > 0$ such that $\lim_{F \in \mathcal{F}: N_1, N_2 \to \infty}\mathbbm{P}\left((G_1,G_2) \not\in \mathcal{G}_c \right) = 0$, i.e. the selected groups $(G_1,G_2)$ are contained in $\mathcal{G}_c$ with probability approaching one. The condition $c > 0$ rules out groups whose relative sizes vanish. Such groups involve too few dyads for uniform consistent estimation in our framework. The condition $c \leq 1/2$ is used to ensure that the set of groups that contain half of the agents are in $\mathcal{G}_c$. It is not used in the proof of our coverage results, Propositions 1 and 2, only for our optimality results Propositions 3 and 4. We do not believe this second condition to be restrictive in practice.\looseness=-1
For any fixed $(g_1,g_2) \in \mathcal{G}_c$ and $\alpha \in (0,1)$, we define a confidence interval to be an interval $CI(g_1,g_2; \alpha) = \left[L(g_1,g_2;\alpha),U(g_1,g_2;\alpha)\right]$ that is determined by the entries of $Y$ where $L(g_1,g_2;\alpha) \leq U(g_1,g_2;\alpha)$ for any $(g_1,g_2)$ and $\alpha$. Each $L$ and $U$ are assumed to be measurable functions of $Y$, and we treat the collection of confidence intervals indexed by $\mathcal{G}_c$, $\{CI(g_1,g_2;\alpha)\}_{(g_1,g_2) \in \mathcal{G}_c}$, as a single measurable map from $Y$ to $(\mathbbm{R}^{2})^{\mathcal{G}_c}$. The variable $\alpha$ is fixed and is not allowed to vary along the asymptotic sequence of random graph models (see Section 2.1.4). We say that $\{CI(g_1,g_2;\alpha)\}_{(g_1,g_2) \in \mathcal{G}_c}$ is simultaneously (over $\mathcal{G}_c$) uniformly (over $\mathcal{F}$) asymptotically level $1-\alpha$ if
In words, the collection of confidence intervals $\{CI(g_1,g_2;\alpha)\}_{(g_1,g_2) \in \mathcal{G}_c}$ controls the family-wise error rate over the index set $\mathcal{G}_c$ uniformly over any asymptotic sequence of random graph models in $\mathcal{F}$ with dimensions diverging to infinity.\footnote{The probability in ((ref)) may be read conditional on the sigma-field $\mathcal H$. Unconditional coverage then follows by iterated expectations.}\looseness=-1
We measure the length of the individual interval $CI(g_1,g_2;\alpha)$ using the difference
and the width of the collection $\{CI(g_1,g_2;\alpha)\}_{(g_1,g_2) \in \mathcal{G}_c}$ using the supremum norm, i.e.
In words, the width of a collection of confidence intervals indexed by $\mathcal{G}_c$ is the maximum length of the intervals in the collection. The supremum norm is commonly used in the simultaneous inference literature cited in Section 1.2 above, since a single uncovered group is enough for the simultaneous event to fail. chen2025adaptive write that “the sup-norm provides a stronger, more informative sense in which the estimator is converging as it measures the maximal, rather than average, error over the support.”\looseness=-1
Any collection of intervals satisfying ((ref)) also satisfies ((ref)) if $\lim_{F \in \mathcal{F}: N_1, N_2 \to \infty}\mathbbm{P}\left((G_1,G_2) \not\in \mathcal{G}_c \right) = 0$. This is because
implies that
Since the argument does not depend on the selection rule, berk2013valid call confidence intervals that satisfy ((ref)) “universally valid post-selection.”\looseness=-1
We discuss the simultaneous inference condition in the context of our three motivating examples. \looseness=-1
We highlight two distinct selection concerns in this example. The first concern arises when researchers consider densities for a large number of groups. The second concern arises when the group membership depends on agent choices, which may be informed by social ties. For example, when characterizing the homophily structure of a social network between Caltech students, jackson2023dynamics consider a large class of group definitions based on gender, ethnicity, housing choice, major choice, and pairwise intersection of these identities in their Table 2 as well as “malleable characteristics” such as elicited risk preference, level of altruism, body mass index, academic performance, time spent sleeping, time spent working, or time spent playing video games in their Table 4.\footnote{In their Section 6, the authors write that the “observed similarity between individuals over malleable characteristics could be the outcome of either selection, assimilation, or both,” but our understanding of the authors' inference procedure, which they describe in their Section 3.3, is that it does not adjust for this selection. \looseness=-1} The authors do not provide an explanation for how they selected which characteristics to focus on, nor do they specify a model of how the malleable characteristics potentially depend on the students' network connections. A simultaneous coverage guarantee, along the lines of condition ((ref)) is the only strategy that we are aware of that is valid uniformly over selection rules under our maintained random graph model without further specifying the selection rule for the reported characteristics. \looseness=-1
We are concerned about selection in this example when the core or hub groups are defined using the network data. For example, elliott2014financial refer to soramaki2007topology who define the core of the US interbank Fedpayments system to be a maximally connected subgraph of banks. carvalho2014micro characterize hub nodes in the US sector-to-sector input network using statistics such as network degree (Figures 2 and 3) or Bonacich centrality (Figure 4). In principle, one could conduct post-selection inference in this setting by specifying a statistical model of network formation and analytically deriving the distribution of connections between the groups of nodes under the relevant selection rule. The validity of this approach, however, depends on the specific choice of network formation model and the definition of the core, and the required distribution theory may be difficult to derive in practice. We recommend a simultaneous coverage guarantee along the lines of condition ((ref)) for this setting because it does not require the researcher to commit to a selection rule and perform such derivations. \looseness=-1
We are concerned about selection in this example when the market segments are defined using the worker transition data. For example, Nimczik2017 and jarosch2024granular specify a stochastic blockmodel where the probability of a worker transition between two firms depends on a latent group assignment. The authors estimate these groups from the worker transition data by maximizing a penalized likelihood function. In principle, one could argue that the authors' inferential target are the densities associated with the latent groups that generated the data, which could justify conditional rather than simultaneous inference (see our literature review in Section 1.2). However, we do not think that this argument accurately describes the intent of jarosch2024granular, who write “[a]n important tuning parameter is the number of markets to consider, K. A higher number of labor markets increases the flexibility of the stochastic blockmodel to describe the data where in the limit of $K = N$ each firm represents its own market.” The idea that the procedure may recover a collection of group assignment with different properties, many of which may be considered by the researcher, suggests to us that their intent is not to commit to a specific latent group assignment ex ante. We recommend a simultaneous coverage guarantee along the lines of condition ((ref)) for this setting because it does not require the researcher to specify, justify, or consistently recover a particular group assignment.\looseness=-1
Section 4.1 describes our two confidence intervals. Section 4.2 states two additional assumptions. Our main results are in Section 4.3. \looseness=-1
We develop two confidence intervals. Our first interval builds on a proposal of berk2013valid, which is to start with a conventional interval (that covers the parameter of interest ((ref)) for a fixed group assignment) and then inflate the length of the interval until condition ((ref)) holds. Our second interval is derived by combining a Talagrand-like concentration inequality for the maximum of an empirical process with a novel bound building on alon2006approximating,gittens2009error. Our use of Talagrand's inequality has some conceptual precedence in the work of lounici2011global, who consider a different problem of deconvolution density estimation. \looseness=-1
The first interval we consider is
where $\hat{\theta}(g_1,g_2) = \frac{1}{m_1m_2}\sum_{i \in [N_1], j \in [N_2]}Y_{ij}g_{i,1}g_{j,2}$, $m_t=\sum_{i\in[N_t]}g_{i,t}$ for $t\in\{1,2\}$, $\sigma(g_1,g_2) := \sqrt{\frac{1}{m_1m_2}\sum_{i \in [N_1], j \in [N_2]}\sigma_{ij}^2g_{i,1}g_{j,2}}$, $\sigma(g_1,g_2)/\sqrt{m_1m_2}$ is the conditional standard deviation of $\hat{\theta}(g_1,g_2)$, $\hat{\sigma}(g_1,g_2)$ is a consistent estimator of $\sigma(g_1,g_2) $,\footnote{For now we assume that a consistent estimator exists. See Assumption 3(i) in Section 4.2 below. In Appendix Section B.2 below we propose a specific choice of $\hat{\sigma}(g_1,g_2)$ and provide sufficient conditions for it to satisfy Assumption 3(i).} $\alpha \in (0,1)$ is a fixed constant, and \looseness=-1
The logic behind the interval $CI_1$ follows berk2013valid and the formal argument is detailed in the proof of Proposition 1 in Appendix Section A.3 below. It starts with the conventional interval $CI_0(g_1,g_2;\alpha) = \hat{\theta}(g_1,g_2) \pm \left[K_0(\alpha) \times \hat{\sigma}(g_1,g_2)\right]/\sqrt{m_1m_2}$ where $K_0(\alpha)$ is the $1-\alpha/2$ quantile of a standard normal distribution. We show in our Corollary 1 of Section 4.3.2 below that the interval $CI_0$ does not satisfy the simultaneous inference condition ((ref)) and so is not necessarily valid post-selection (see our discussion in Section 3.1.3 above). To address this issue, the idea is to replace the critical value $K_0(\alpha)$ with one that is large enough to satisfy ((ref)). \looseness=-1
The second interval we consider is
where $\hat{\theta}(g_1,g_2) = \frac{1}{m_1m_2}\sum_{i \in [N_1], j \in [N_2]}Y_{ij}g_{i,1}g_{j,2}$, $m_t = \sum_{i \in [N_t]}g_{i,t}$ for $t \in \{1,2\}$, $\alpha \in (0,1)$ is a fixed constant, $K_2(\alpha) := \sqrt{-2\ln(\alpha)}$,
$\hat{\bar{\tau}}$ is a consistent estimator of $\bar{\tau}$ and $\hat{V}$ is a consistent estimator of $V$.\footnote{As before in Section 4.1.1, we assume for now that a consistent estimator exists. See Assumptions 3(ii) and 3(iii) in Section 4.2 below. In Appendix Section B.2 below we propose specific choices of $\hat{\bar{\tau}}$ and $\hat{V}$ and provide sufficient conditions for them to satisfy Assumptions 3(ii) and 3(iii).} As discussed in Section 2.1.2, these expectations are implcitly conditional on $\mathcal{H}$. \looseness=-1
The logic behind the interval $CI_2$ follows a combination of a version of Talagrand's inequality due to klein2005concentration (Lemma 8 in Section 8.2.2 below), Theorem 3 of gittens2009error (Lemma 4 in Appendix Section A.2.1), and a refinement of Lemma 3.1 of alon2006approximating (Lemmas 1 and 2 in Appendix Section A.2.1). While our use of Talagrand's inequality shares some conceptual similarities with a concentration argument that appears in the proof of Proposition 1 of lounici2011global, the main proof strategy, given in Appendix Section A.3, is, to our knowledge, original to our paper. \looseness=-1
In addition to Assumption 1 in Section 2.1.3, we state two additional conditions as our Assumptions 2 and 3 below. The conditions are asymptotic in the sense that they refer to a sequence of random graph models with diverging dimensions in the sense of Section 2.1.4. \looseness=-1
Our second assumption is a lower bound on the magnitude of the variation in the network connections. There is a weak version of the assumption, Assumption 2(w), and a strong version, Assumption 2(s).\looseness=-1
We consider Assumption 2(w), to be a mild condition that only rules out “ultra-sparse” networks. It is used to ensure that the coverage of our intervals is uniform in the sense of condition ((ref)) of Section 3.1.2 below.\footnote{See, for instance, Example 11.2.7 of lehmann2006testing for a explanation of how uniform coverage can fail without such a condition.} Recall from Section 2.1.4 that our asymptotic arguments refer to a sequence of models, where $N_1$ and $N_2$ are increasing along the sequence, and that the entries of $\sigma$ may change arbitrarily along this sequence. In particular, the entries of $\sigma$ may converge to $0$, which is used in the literature to model sparse networks. See, for example, bickel2009nonparametric. What Assumption 2(w) says is that, even if the entries of $\sigma$ are converging to $0$, the sum of the squared entries diverges. Intuitively, the condition says that “on average” the entries of $\sigma$ cannot vanish at the rate of $1/\sqrt{N_1N_2}$ or faster. For unweighted networks, this rules out sequences of networks with an almost surely bounded number of edges (i.e. networks where almost every agent has degree $0$). Such ultra-sparse regimes exist, but we do not believe them to be common in economic research, and so we do not think that this condition is restrictive in practice. \looseness=-1
Assumption 2(s) places more restrictions on the amount of variation in the matrix $\sigma$. Intuitively, it says that for any groups $(g_1,g_2) \in \mathcal{G}_c$ the average of the entries of $\sigma^2$ over the groups must be large relative to $\min(N_1,N_2)^{-1}$. For unweighted networks, this rules out sequences of networks where the agents have a bounded number of connections (i.e. the agent degrees do not grow with the dimensions of the matrix). Such “sparse” regimes exist and are not uncommon in the economics literature. As a result, we recommend that when researchers are working with sparse (but not ultra-sparse) networks, they use our $CI_2$ (whose justification relies only on Assumption 2(w)) rather than our $CI_1$ (whose justification relies on Assumption 2(s)). See Section 4.3 below for a discussion. \looseness=-1
Our third assumption is a high-level condition that says that $\hat{\sigma}(g_1,g_2)$, $\hat{V}$, and $\hat{\bar{\tau}}$ converge to their analogs $\sigma(g_1,g_2)$, $V$, and $\bar{\tau}$ as $N_1,N_2 \to \infty$.
Assumption 3(ii) says that the estimation error for $\hat{\bar{\tau}}$ vanishes relative to the magnitude of $\bar{\tau}$. Assumption 3(iii) says the estimation error for $\hat{V}$ vanishes relative to the magnitude of $V$. Assumption 3(i) says that the estimation error for $\hat{\sigma}(g_1,g_2)$ vanishes relative to the magnitude of $\sigma(g_1,g_2)$, uniformly over $(g_1,g_2) \in \mathcal{G}_c$. The probabilities are to be read conditional on the sigma-field $\mathcal H$ as defined Section 2.1.2. \looseness=-1
We state four propositions in this section. The first two propositions are in Section 4.3.1. Proposition 1 establishes that Assumptions 1, 2(s), and 3(i) are sufficient for $CI_1$ to satisfy ((ref)). Proposition 2 establishes that Assumptions 1, 2(w), 3(ii) and 3(iii) are sufficient for $CI_2$ to satisfy ((ref)). The second two propositions are in Section 4.3.2. They state that, under the assumptions maintained in Propositions 1 and 2, the widths of the intervals $CI_1$ and $CI_2$ are, in a certain sense, optimal up to a constant. Proofs are in Appendix Section A.3. \looseness=-1
Under Assumptions 1, 2(s), and 3(i), the confidence interval $CI_1$ satisfies the simultaneous inference condition ((ref)). That is, \looseness=-1
Under Assumptions 1, 2(w), 3(ii), and 3(iii), the confidence interval $CI_2$ satisfies the simultaneous inference condition ((ref)). That is, \looseness=-1
A key difference between the two results is that Proposition 1 requires the strong version of Assumption 2 while Proposition 2 only requires the weak version. \looseness=-1
The proof of Proposition 1 is in Appendix Section A.3. The main idea is to start with an interval that is marginally valid in the sense that it covers the parameter of interest at the desired level for a fixed group assignment. For this first step, we specify an interval based on a version of Bernstein's inequality, see Lemma 6 in Appendix Section A.2.2. We use Bernstein's inequality and not a normal approximation to construct this interval because we are not aware of any formal justification of the latter in our setting.\footnote{For example, chernozhukov2022improved study Gaussian and bootstrap approximations for the maximum coordinate of a centered sample mean of $n$ independent $p$-dimensional random vectors, obtaining bounds that depend polynomially on $\log p$. If one indexes a coordinate by each candidate group pair in $\mathcal G_c$, then $p$ is exponential in the number of nodes, and these bounds do not yield a vanishing approximation error. Their Remark 2.2 further indicates that some logarithmic dimension dependence is sharp in general.} We then inflate the width of the interval until ((ref)) is satisfied. While the resulting interval is conservative, we show in Proposition 3 that, under the same assumptions as in Proposition 1, the width of the interval is optimal up to a constant within the class of intervals that satisfy ((ref)) and have the conventional “point estimate plus or minus constant times standard error” shape that characterizes the berk2013valid approach. \looseness=-1
The proof of Proposition 2 is also in Appendix Section A.3. The main idea is to bound the maximum estimation error $\max_{(g_1,g_2) \in \mathcal{G}_c}\left|\hat{\theta}(g_1,g_2) - \theta(g_1,g_2)\right|$ using a version of Talagrand's inequality due to klein2005concentration, see Lemma 8 in Appendix Section A.2.2. This inequality bounds deviations of the maximum estimation error around its expectation. To bound the expectation, we adapt Lemma 3.1 of alon2006approximating and combine it with a bound derived from Theorem 3 of gittens2009error. These results are Lemmas 1, 2, and 4 in Appendix Section A.2.1. While the resulting interval is conservative, we show in Proposition 4 that, under the same assumptions as in Proposition 2, the width of the interval is optimal up to a constant within the class of intervals that satisfy ((ref)) and contain the point estimate $\hat{\theta}(g_1,g_2)$. \looseness=-1
Under Assumptions 1, 2(s), and 3(i), we find that our choice of $K_1(\alpha) := \sqrt{1.39(N_1+N_2) - 2\ln(\alpha/2)}$ is optimal up to a factor of $\sqrt{\frac{1}{11.12\pi}} > 1/6$. Specifically, \looseness=-1
The proof of Proposition 3 is in Appendix Section A.3. The main idea of the proof is to derive a lower bound on $\max_{(g_1,g_2) \in \mathcal{G}_c}\frac{\sqrt{m_1m_2}\,|\hat\theta(g_1,g_2)-\theta(g_1,g_2)|}{\hat\sigma(g_1,g_2)}$ such that, for some asymptotic sequence of models in $\mathcal{F}$, the lower bound converges in probability to $\sqrt{N_1+N_2}/\sqrt{8\pi}$. It follows that if $K/\sqrt{N_1+N_2}$ is less than $1/\sqrt{8\pi}$ then there exist an asymptotic sequence of models in $\mathcal{F}$ and groups $(g_1,g_2) \in \mathcal{G}_c$ such that, for any fixed $\alpha > 0$, the probability that $\theta(g_1,g_2)$ is contained in $I(g_1,g_2;\alpha)$ vanishes.\looseness=-1
A corollary of Proposition 3 is that, under Assumptions 1, 2(s), and 3(i), any interval that has the berk2013valid “point estimate plus or minus critical value times standard error” shape will not satisfy the simultaneous inference condition ((ref)), if the critical value diverges slower than $\sqrt{N_1+N_2}$. In particular, this applies to the conventional confidence interval $CI_0(g_1,g_2;\alpha) := \hat{\theta}(g_1,g_2) \pm \left[K_0(\alpha)\times \hat{\sigma}(g_1,g_2)\right]/\sqrt{m_1m_2}$ where $K_0(\alpha)$ is the $1-\alpha/2$ quantile of a standard normal distribution, i.e.\looseness=-1
Proposition 3 establishes that that the width of the interval $CI_1$ is optimal up to a constant only within a restricted class of intervals that have the conventional shape. By contrast, under Assumptions 1, 2(w), and 3(ii), the width of the interval $CI_2$ is optimal up to a constant factor (the constant may depend on $\alpha$) under the weaker restriction that the interval contains the point estimate. That is, \looseness=-1
Two key differences distinguish the content of Proposition 4 from that of Proposition 3. The first difference is that Proposition 4 applies to any interval that contains $\hat{\theta}(g_1,g_2)$, not just intervals of the form “point estimate plus or minus a critical value times a standard error.” The second difference is that the coverage probability of the interval is eventually below $1-\alpha$, not just for a subcollection of models, but for any asymptotic sequence in $\mathcal{F}$ (i.e. the left hand side has a “$\limsup$” instead of a “$\liminf$”). This conclusion is stronger than in Proposition 3 because it bounds the asymptotic coverage probability away from $1-\alpha$ uniformly over the model class, rather than merely constructing one unfavorable subclass. We say that $CI_2$ is uniformly “sup-norm rate optimal” since the width of the interval is measured using the sup-norm.\footnote{The requirement in Proposition 4 that each interval contains the estimated density $\hat{\theta}(g_1,g_2)$ cannot be dropped without weakening the conclusion. Specifically, for any fixed sequence of models, the collection of intervals that are degenerate at $\theta(g_1,g_2)$ satisfies ((ref)) and covers with probability one along that sequence, although the intervals will have zero coverage for any model with a different density, and so will not satisfy (ref). We suspect that the requirement can be dropped if the $\limsup$ in the conclusion is replaced with a $\liminf$ as in Proposition 3, but leave this to future work.}\looseness=-1
The proof of Proposition 4 is in Appendix Section A.3 below. The main idea of the proof builds on an argument described in the third paragraph of Section 4.2 of rudelson2007sampling. In their paper, the authors focus on the special case where the entries of $Y$ take value $1$ or $-1$ with equal probability and, for that model, derive a lower bound on a quantity that is similar in spirit to our maximum estimation error $\max_{(g_1,g_2) \in \mathcal{G}_c}|\hat{\theta}(g_1,g_2) - \theta(g_1,g_2)|$ using Khintchine's inequality. Our proof strategy is similar, but we do not require the entries of $Y$ have this specific distribution. To accomplish this, we use a version of Grothendieck's inequality due to krivine1979constantes as an alternative to Khintchine's inequality. These are the lower bounds in our Lemma 4 of Appendix Section A.2.1. \looseness=-1
Since Proposition 4 establishes that, under Assumptions 1, 2(w), and 3(ii), $CI_2$ is sup-norm rate optimal, it follows that, under these conditions, $CI_1$ is not, since the width of $CI_1$ will converge at a slower rate than that of $CI_2$ for any sequence of models satisfying Assumptions 1, 2(w), 3(i), 3(ii) and $\frac{\sqrt{N_1+N_2}||\sigma||_F}{\mathbbm{E}\left[\sum_{i \in [N_1]}\sqrt{\sum_{j \in [N_2]}\epsilon_{ij}^2} + \sum_{j \in [N_2]}\sqrt{\sum_{i \in [N_1]}\epsilon_{ij}^2}\right]} \to \infty$ as $N_1,N_2 \to \infty$.\footnote{See Remark 11 of Section 4.1.1 and Remark 12 of Section 4.1.2 above for the widths of these intervals.}\looseness=-1
To understand this last condition, write\ $a_i:=\left(\sum_{j\in[N_2]}\epsilon_{ij}^2\right)^{1/2}$ and $b_j:=\left(\sum_{i\in[N_1]}\epsilon_{ij}^2\right)^{1/2}$ so that $\|\sigma\|_F^2 = \sum_{i \in [N_1]} \mathbb E[a_i^2] = \sum_{j \in [N_2]} \mathbb E[b_j^2]$,
and the condition $\frac{\sqrt{N_1+N_2}||\sigma||_F}{\mathbbm{E}\left[\sum_{i \in [N_1]}\sqrt{\sum_{j \in [N_2]}\epsilon_{ij}^2} + \sum_{j \in [N_2]}\sqrt{\sum_{i \in [N_1]}\epsilon_{ij}^2}\right]} \to \infty$ is equivalent to \[ \frac{\sum_{i \in [N_1]}\mathbb E[a_i]+\sum_{j \in [N_2]}\mathbb E[b_j]}{\sqrt{\sum_{i \in [N_1]} \mathbb E[a_i^2]} + \sqrt{\sum_{j \in [N_2]} \mathbb E[b_j^2]}} = o\!\left(\sqrt{N_1+N_2}\right). \] Suppose the nondegenerate entries of $a_i$ and $b_j$ are all supported in $[\underline{s}, \overline{s}]$. Let $R_1 := \sum_{i \in [N_1]}\mathbbm{1}\{\mathbbm{E}\left[a_i^2\right] > 0\}$ and $R_2 := \sum_{j \in [N_2]}\mathbbm{1}\{\mathbbm{E}\left[b_j^2\right] > 0\}$. Then $\frac{\sum_{i \in [N_1]}\mathbb E[a_i]+\sum_{j \in [N_2]}\mathbb E[b_j]}{\sqrt{\sum_{i \in [N_1]} \mathbb E[a_i^2]} + \sqrt{\sum_{j \in [N_2]} \mathbb E[b_j^2]}} \leq \left(\sqrt{R_1}+\sqrt{R_2}\right)\frac{\overline{s}}{\underline{s}}$ which is $o(\sqrt{N_1+N_2})$ if $\overline{s}/\underline{s}$ is uniformly bounded and $\left(\sqrt{R_1}+\sqrt{R_2}\right) = o\left(\sqrt{N_1} + \sqrt{N_2}\right)$.\looseness=-1
In words, $CI_2$ improves on $CI_1$ when the variation in network connections is concentrated in a relatively small number of rows and columns of the adjacency matrix. Intuitively, the first interval satisfies ((ref)) by scaling the width of the conventional interval by a factor of $\sqrt{N_1+N_2}$. We demonstrated in Proposition 3 that this rate is generally necessary, however, it can be very conservative when many of the rows and columns of the adjacency matrix exhibit relatively little variation in the network connections. The second interval is based on a direct bound on the maximum post-selection estimation error and therefore adapts to this heterogeneity. This is why the two intervals have comparable widths in homogeneous networks, but $CI_1$ can be substantially wider in sparse or degree-heterogeneous networks.\looseness=-1
In this section, we provide corroborating simulation evidence for our findings in Section 4.3.2. Specifically, we find that the widths of the intervals $CI_1$ and $CI_2$ are similar in magnitude for networks drawn from an Erdős--Rényi model, but the width of $CI_2$ can be substantially smaller in magnitude for models with degree heterogeneity. Section 5.1 describes our models. Section 5.2 discusses the problem of estimating the variances. Section 5.3 contains the results. \looseness=-1
Our simulations focus on undirected unweighted networks with no loops. We denote the number of agents with $N$ and the $N \times N$ dimensional matrix $\mu$ describes the conditional probability that a pair of agents form a connection. Following the discussion in Section 2.1.1 and Remark 6 in Section 2.2, we take $\mu$ to be upper-diagonal and use the normalization $D = \sum_{i, j \in [N]}G_{i,1}G_{j,2}\mathbbm{1}\{i < j\}$ instead of $\frac{1}{M_1M_2}$. For $i < j$, we draw $Y_{ij}$ independently from a Bernoulli$(\mu_{ij})$ distribution. Because the purpose of the simulation is to compare the relative widths of $CI_1$ and $CI_2$, rather than study a particular group-selection rule, we focus on the full-network density by setting $G_{i,1} = G_{i,2} = 1$ for every $i,j \in [N]$. Other groups pairs in $\mathcal{G}_c$ would change the widths by at most a constant factor. For these groups, the parameter of interest is the density $\theta = D^{-1}\sum_{i<j}\mu_{ij}$ and the estimator is $\hat\theta = D^{-1}\sum_{i<j}Y_{ij}$. \looseness=-1
We consider four random graph models. The first model is a sparse Erdős--Rényi model where $\mu_{ij} = N^{-1}$ for every $i < j$. The second model is a deterministic core--periphery model where we first draw a subset $S$ of size $\lfloor\sqrt{N}\rfloor$ uniformly at random from $[N]$, and then define $\alpha_i = 0.5\mathbbm{1}\{i \in S\} + N^{-2}\mathbbm{1}\{i \not\in S\}$ and $\mu_{ij} = \alpha_i\alpha_j\mathbbm{1}\{i < j\}$. The third model is a fixed-effects core--periphery model which is the same as the previous model, except $\alpha_i = 0.5\mathbbm{1}\{i \in S\} + i^{-2}\mathbbm{1}\{i \not\in S\}$. The fourth model is a random-effects core--periphery model which is the same as the previous model except $\alpha_i = 0.5\mathbbm{1}\{i \in S\} + Z_i/T\mathbbm{1}\{i \not\in S\}$ where $Z_i = U_i^2$, $T = \sum_{\ell = 1}^{N}Z_\ell$, and $U_1,\ldots,U_N$ are independent with standard uniform marginal distributions. \looseness=-1
We compare the intervals associated with the different choices of $\hat{\sigma}(G_{1},G_{2})$, $\hat{\bar{\tau}}$, and $\hat{V}$. The first choice of estimators is a fixed-rank spectral estimator. We first set $K = 5$ and define $\hat{\mu} = \min\left(\max\left(\sum_{\ell = 1}^{K}\lambda_{\ell}u_{\ell}u_{\ell}^{T},0\right),1\right)$ where $\lambda_{1},\ldots,\lambda_{N}$ are the eigenvalues of $Y + Y^{T}$, ordered to be decreasing in absolute value, $u_1,\ldots,u_{N}$ are the associated eigenvectors, and the $min$ and $max$ functions are applies entrywise. We then define $\hat{\epsilon} = Y - \hat{\mu}$, $||\hat{\epsilon}||_F = \sqrt{\sum_{i < j}\hat{\epsilon}^2}$, $||\hat{\epsilon}||_{\dagger} = \sum_{i\in[N]}\sqrt{\sum_{j \in \{i+1,\ldots,N\}}\hat{\epsilon}^{2}_{ij}} + \sum_{ j \in [N]}\sqrt{\sum_{i \in [j-1]}\hat{\epsilon}^2_{ij}}$, $\hat{\sigma}(G_{1},G_{2}) = ||\hat{\epsilon}||_F/\sqrt{D}$, $\hat{\bar{\tau}} = 1.01||\hat{\epsilon}||_{\dagger} + 0.25||\hat{\epsilon}||_{F}$, and $\hat{V} = \sqrt{||\hat{\epsilon}||_{F}^2 + ||\hat{\epsilon}||_F + 4||\hat{\epsilon}||_{\dagger}}$. \looseness=-1
The second choice of estimators is those given in Remark 14 of Section 4.2 and Appendix Section B.1. That is, $\hat{\sigma}(G_1,G_2) = 2$, $\hat{\bar{\tau}} = 4.04N^{3/2} + 0.5N$, and $\hat{V} = \sqrt{16N^{3/2}+4N^2+2N}$. The third choice of estimators is those given in Appendix Section B.2.1. That is, the formula for the estimators is the same as in the first choice, except $K$ is the count of eigenvalues of $Y + Y^{T}$ that are larger in absolute value than $2.01\sqrt{N}$. This adaptive rule for $K$ follows the USVT strategy of chatterjee2015matrix.\looseness=-1
For each \(N\in\{100, 200, 500,1000\}\) and model described in Section 5.1, we perform the following procedure $R = 10,000$ times. We first construct the matrix $\mu$ and then draw $Y$ from $\mu$. We then compute the margin of error (half-lengths) of $CI_1$ and $CI_2$ for the three choices of variance estimators. Specifically, the margin of error of $CI_1$ is $\frac{\hat{\sigma}(G_1,G_2)K_1(\alpha)}{\sqrt{D}}$ and for $CI_2$ it is $\frac{\hat{\bar{\tau}}+\hat{V}K_2(\alpha)}{D}$. Throughout the simulations we set $\alpha = 0.05$.\looseness=-1
The results are in Table (ref). The four panels correspond to the four models described in Section 5.1. Within each panel, the rows index the number of agents \(N\), and the three column groups correspond to the three variance-estimation strategies described in Section 5.2. Each column group reports the average margin of error for \(CI_1\) ($MoE_1$), the average margin of error for \(CI_2\) ($MoE_2$), and the average ratio \(\mathrm{MoE}_2/\mathrm{MoE}_1\) (not the ratio of averages). \looseness=-1
The simulations corroborate the findings in Section 4.3.2. For the Erdős--Rényi model we find that the widths of $CI_1$ and $CI_2$ are similar in magnitude across the various choices of $N$ and estimators for the variance parameters. However, for the core-periphery models, the width of $CI_2$ is nearly three times smaller on average over the simulations than $CI_1$ for the first and third estimation strategies when $N = 1000$. The width of $CI_2$ is larger than that of $CI_1$ for the second estimation strategy. This result is expected because the conservative bounds in the second estimation strategy are homogeneous: they simply bound every element of $\epsilon^2$ and $\sigma^2$ by one. Consequently, the resulting $CI_2$ cannot adapt to degree heterogeneity as it does with the other two estimators. \looseness=-1
We demonstrate our confidence intervals in the context of the three motivating examples. \looseness=-1
We first study the homophily structure of the social networks in the Facebook100 dataset. The Facebook100 dataset contains friendship networks from 100 colleges and universities with characteristics such as gender, class year, major, high school, and residence. The data comes from nr. It is publicly available and can be obtained at \url{https://networkrepository.com/socfb.php}.
We conduct an exploratory analysis where, for each campus, we define groups by gender, class year, major, residence, student/faculty status, and then report point estimates and confidence intervals for thirty densities in Table (ref). The first column of the table reports the campus location, the second and third columns report the group labels, the fourth column reports the estimated density, and the last three columns report $CI_0$, $CI_1$, and $CI_2$. The rows of Table (ref) are sorted into panels based on the group categories. The groups in the first panel correspond to gender, the second panel to graduation year, the third panel to choice of major, the fourth panel to student/faculty status, and the fifth panel to dormitory assignment. \looseness=-1
Each panel shows a pair of density estimates and associated confidence intervals for three campuses. One corresponds to a “within” group density and the other corresponds to an “across” group density. For example, the first row shows the estimated density of Facebook connections between gender 1 and gender 2 at the University of Michigan. The second row shows the estimated density between users with gender 2. \looseness=-1
Some patterns emerge when comparing the density estimates across types, campuses, and groups. First, the estimates describe homophily in graduation year, major, student/faculty status, and dorm room assignment. They describe heterophily in gender (the density across gender is higher than within). Using the conventional interval $CI_0$, all of these differences are statistically significant (i.e. for every pair of density estimates, the associated $CI_0$ intervals do not overlap). Not all of these differences are statistically significant using the $CI_1$ interval. The differences by graduation year, student/faculty status, and the dorm room comparison for Rice survive. Those for gender, major, and the dorm room comparisons for Haverford and USC do not. None of these differences are statistically significant using $CI_2$. \looseness=-1
Our second demonstration uses data on bilateral trade flows for 238 countries and 6,180 products. The data comes from CEPII. It is publicly available and can be found at \url{https://www.cepii.fr/DATA_DOWNLOAD/baci/doc/baci_webpage.html}. See gaulier2010baci. We use the 2023 HS22 file, aggregate over all importing countries, and define a connection between an exporting country and a product if the country exports at least \$500 million in that product. \looseness=-1
We conduct an analysis of the hub-and-spoke structure of this bipartite network in the spirit of carvalho2014micro. In his analysis, Carvalho writes that production and trade networks contain hub sectors that can act as powerful conduits for shocks, and uses centrality measures such as degree and Bonacich centrality, to define the hub nodes. We use the methodology of our paper to assess the evidence in support of a hub-and-spoke structure in the trade data. \looseness=-1
The results can be found in Table (ref) below. The first column of the table reports the centrality measure used to define the groups, the second and third columns describe the combination of groups used in the density estimate, the fourth column provides the density estimate, and the remaining three columns give the intervals $CI_0$, $CI_1$, and $CI_2$. The panels of the table each correspond to one of the three centrality measures: degree, eigenvector, and Bonacich centrality, and the four rows in each panel correspond to the different combinations of the two groups. The hub groups are the countries or products in the top decile of centrality score, the non-hub groups are the remaining countries or products.\looseness=-1
The point estimates are nearly identical for the three centrality measures: the density of the hub nodes is approximately $0.25$, the density of the non-hub nodes is approximately $0.00$, and the density between the two groups is approximately $0.01$. Under $CI_0$, the hub-and-spoke structure is statistically significant in that the intervals for the hub-hub densities does not overlap with the other three. The same result is also found with our second interval $CI_2$, showing that the statistical significance result survives our simultaneous inference correction. We do not get the same result with the $CI_1$ interval, however, since in all three settings the lower bound on $CI_1$ for the hub-hub density is lower than the upper bound for $CI_1$ for the hub-non-hub and non-hub-hub densities. \looseness=-1
Our third demonstration uses a job-mobility network based on the Panel Study of Income Dynamics (PSID) following schmutte2014free. The data is publicly available and can be found at \url{https://psidonline.isr.umich.edu/}. The analysis is similar in spirit to that of jarosch2024granular, who cluster firms using Austrian worker-flow data to study market structure and wages, but with publicly available data. Following schmutte2014free, we construct a network of “pseudo-employers” defined by industry-occupations. We then construct a link between two pseudo-employers if there is a worker who transitions from one industry-occupation to the other. In the data, there are 45,905 person-year observations, 8,119 workers, 6,346 pseudo-employers, and 19,921 observed job transitions. The largest connected component contains 6,039 pseudo-employers and 13,714 edges.
Following schmutte2014free, we apply the Louvain algorithm to the largest connected component, yielding 28 communities, and then focus on the four largest communities, which contain 515, 489, 449, and 412 pseudo-employers, respectively. The resulting sample corresponds to schmutte2014free's Figure 1. We use the methodology of our paper to assess the evidence in support of a segmented market structure. The results of this analysis are in Table (ref).
Table 3 reports the densities of network connections within and across the four groups. The point estimates indicate that the estimated density of connections within markets is approximately 33 times higher than across markets. These differences are statistically significant under $CI_0$, in the sense that the lower bounds on the intervals for the within market density measures are all above the upper bounds on the across-market density measures. This difference does not survive any of our corrections for simultaneous inference, however. Specifically, all of our intervals $CI_1$ and $CI_2$ extend to $0$.
The reason why our $CI_1$ and $CI_2$ intervals are so wide in this case has to do with the fact that the density of the network is relatively sparse and the sizes of the communities are relatively small as a fraction of the total number of pseudo-employers. Specifically, the large connected component of $6039$ pseudo-employers is sparse, with a density of $0.0007$, and the four large components are relatively small (approximately $7\%$ of $6039$). In this setting, it is not unexpected that idiosyncratic error would lead some subgroups of agents of these sizes to exhibit fluctuations in densities on the order of magnitude of $0.001$. Based on this illustration, we recommend that researchers exhibit some caution when using clustering algorithms to infer market segments in practice.
This paper considers inference for the density of network connections between groups of agents, such as communities or markets. Such density measures are widely used to characterize stochastic network structure, but in practice the relevant groups are often selected using the network itself. We develop two confidence intervals that are universally valid post-selection, in the sense that they guarantee simultaneous coverage over all group pairs whose relative sizes are bounded away from zero. The first interval inflates the critical value of a conventional fixed-group interval. The second uses a Talagrand-type concentration inequality to control the maximum post-selection estimation error directly. Both intervals are simple to compute and scalable to large networks. The main theoretical distinction is that the Talagrand interval attains the optimal sup-norm rate, up to constants, while the inflated conventional interval can be substantially wider in sparse or degree-heterogeneous networks. These empirical illustrations show that post-selection correction can materially alter conclusions in practice.\looseness=-1