Technical Summary: Post-selection Inference for Network Structure

1. Problem Statement

Researchers frequently characterize social and economic networks by measuring the density of connections between specific groups of agents (e.g., communities, markets, or core-periphery structures). A critical issue arises because these groups are rarely fixed a priori; they are typically selected based on the network data itself using clustering algorithms, centrality measures, or visual inspection.

Conventional inference procedures that treat these data-selected groups as fixed fail to account for the selection process. This leads to invalid confidence intervals that overstate the evidence for specific network structures. As demonstrated in the paper's motivating example, an Erdős–Rényi random graph (which has no inherent structure) can appear to have a statistically significant core-periphery structure when groups are selected via spectral clustering, simply due to idiosyncratic noise amplified by the selection algorithm.

The paper addresses the problem of constructing confidence intervals for the expected fraction (density) of connections between two groups, $\theta(G_1, G_2)$, that remain valid even when the groups $(G_1, G_2)$ are selected in a data-dependent manner.

2. Methodology and Model

2.1 Model Setup

The authors define a network on two sets of agents with dimensions $N_1$ and $N_2$. The network is represented by an adjacency matrix $Y$ where entries $Y_{ij}$ are real-valued random variables. The model assumes:

• Conditional Independence: Conditional on a sigma-field $\mathcal{H}$ (representing latent heterogeneity, agent characteristics, or link covariates), the entries of $Y$ are independent but not necessarily identically distributed.
• Bounded Support: The entries of $Y$ are bounded within $[-B, B]$.
• Network Structure: The "structure" is defined as the conditional mean matrix $\mu = E[Y|\mathcal{H}]$. The goal is to infer functions of $\mu$, specifically the group density:
  $$\theta(G_1, G_2) = \frac{1}{M_1 M_2} \sum_{i \in [N_1], j \in [N_2]} \mu_{ij} G_{i,1} G_{j,2}$$
  where $G_{t}$ is a binary vector indicating group membership and $M_t$ is the group size.

2.2 The Inference Challenge

The groups $G_1$ and $G_2$ are random vectors that may depend on $Y$. The paper argues that to ensure validity for arbitrary selection rules, one must achieve simultaneous coverage over the entire index set of permissible group assignments $\mathcal{G}_c$ (where group sizes are bounded away from zero).

• Requirement: The collection of intervals $\{CI(g_1, g_2; \alpha)\}_{(g_1, g_2) \in \mathcal{G}_c}$ must satisfy:
  $$\liminf_{N_1, N_2 \to \infty} P\left( \bigcap_{(g_1, g_2) \in \mathcal{G}_c} \{ \theta(g_1, g_2) \in CI(g_1, g_2; \alpha) \} \right) \geq 1 - \alpha$$
• Implication: If simultaneous coverage is achieved, then for any data-dependent selection rule $(G_1, G_2)$, the resulting interval is valid post-selection.

3. Proposed Confidence Intervals

The paper develops two distinct confidence intervals, both scalable to large networks but differing in their theoretical properties and construction.

3.1 First Interval (Berk et al. Strategy)

This interval follows the strategy of Berk et al. (2013) for post-selection inference.

• Construction: It starts with a conventional interval based on a point estimate $\hat{\theta}$ and a standard error, then inflates the critical value to ensure simultaneous coverage.
• Formula:
  $$CI_1(g_1, g_2; \alpha) = \hat{\theta}(g_1, g_2) \pm \frac{K_1(\alpha) \hat{\sigma}(g_1, g_2)}{\sqrt{m_1 m_2}}$$
  where $K_1(\alpha) \approx \sqrt{1.39(N_1 + N_2) - 2\ln(\alpha/2)}$.
• Assumptions: Requires a "strong" assumption on the variance (Assumption 2(s)), which implies that the average variance over any group pair does not vanish too quickly.
• Performance: While valid, the width of this interval can be substantially wider than necessary, particularly in sparse or degree-heterogeneous networks, because it scales with $\sqrt{N_1 + N_2}$.

3.2 Second Interval (Talagrand-type Concentration)

This interval utilizes a novel application of concentration inequalities for empirical processes.

• Construction: It bounds the maximum estimation error $\max_{(g_1, g_2)} |\hat{\theta} - \theta|$ directly using a Talagrand-type inequality (Klein and Rio, 2005) combined with bounds on matrix norms (Alon and Naor, 2006; Gittens and Tropp, 2009).
• Formula:
  $$CI_2(g_1, g_2; \alpha) = \hat{\theta}(g_1, g_2) \pm \frac{\hat{\bar{\tau}} + K_2(\alpha)\hat{V}}{m_1 m_2}$$
  where $\bar{\tau}$ and $V$ are quantities derived from the expected norms of the error matrix $\epsilon$.
• Assumptions: Requires only a "weak" assumption on the variance (Assumption 2(w)), which rules out only "ultra-sparse" networks.
• Performance: This interval adapts to the heterogeneity of the network. It is shown to be asymptotically optimal in terms of width (up to a constant factor) for a broader class of intervals.

4. Key Results and Contributions

4.1 Validity

Both intervals are proven to be universally valid post-selection. They guarantee simultaneous coverage over all group pairs with non-vanishing relative sizes, regardless of how the groups were selected (e.g., via clustering, centrality, or visual inspection).

4.2 Optimality and Width

A central technical contribution is the derivation of an asymptotic lower bound for the width of any simultaneously valid confidence interval containing the point estimate.

• Proposition 3: Shows that the first interval ($CI_1$) is optimal up to a constant only within the restricted class of intervals that follow the "point estimate $\pm$ critical value $\times$ standard error" form.
• Proposition 4: Shows that the second interval ($CI_2$) achieves the optimal sup-norm rate up to a constant factor for any interval containing the point estimate.
• Comparison: In homogeneous networks (e.g., Erdős–Rényi), the widths of $CI_1$ and $CI_2$ are comparable. However, in sparse or degree-heterogeneous networks (common in economic research), $CI_1$ can be substantially wider than $CI_2$ because $CI_1$ fails to adapt to the concentration of variation in specific rows/columns of the adjacency matrix.

4.3 Empirical Illustrations

The paper demonstrates the practical impact of post-selection correction using three datasets:

1. Social Capital (Facebook100): Analysis of homophily. While conventional intervals suggest significant homophily across many dimensions (gender, major, etc.), the corrected intervals ($CI_1$ and $CI_2$) show that evidence for homophily in gender and major disappears, while evidence for graduation year and student/faculty status remains robust.
2. Shock Propagation (Trade Network): Analysis of hub-and-spoke structures. Evidence for a hub-and-spoke structure (using degree, eigenvector, and Bonacich centrality) survives the correction, indicating robust structural features in trade networks.
3. Market Competition (Worker Transitions): Analysis of disjoint market segments. Conventional intervals suggest strong evidence for disjoint markets. However, after correction, the intervals extend to zero, indicating that the apparent segmentation may be an artifact of the clustering algorithm and idiosyncratic noise rather than a true structural feature.

5. Significance and Claims

The paper claims to be the first to provide simultaneous coverage guarantees for the specific problem of inferring network structure where groups are data-dependent.

• Universality: The proposed method does not require the researcher to specify a model for the group selection process or commit to a specific selection rule. It is valid for "I will know a community when I see it" approaches.
• Scalability: Both intervals are computationally simple and scalable to large networks, avoiding the intractability of computing maximum t-statistics over exponentially many group pairs.
• Practical Necessity: The empirical illustrations demonstrate that failing to account for selection can lead to "hallucinated" structures (e.g., false market segments) or overstated evidence. The paper concludes that researchers should exercise caution when using clustering algorithms to infer market segments without post-selection correction.
• Methodological Advancement: By establishing that the Talagrand-based interval ($CI_2$) is rate-optimal and adapts to network sparsity, the paper provides a superior alternative to traditional "inflation" methods for heterogeneous networks.