Nonparametric Subgraph Regression
summary
The gist
Estimation and inference on a single large network are challenging due to dependence among observations This paper studies nonparametric regression for outcomes defined on groups of p agents…
In short
This paper develops a nonparametric regression method for outcomes defined on groups of $p$ agents, like whether three agents form a triangle in a network. It addresses the challenge of dependence among observations in large networks by adapting kernel estimators. The results establish convergence rates and asymptotic normality for estimating these group-level probabilities.
Key concepts
- Polyadic Outcome
- This refers to an outcome $Y_{ip}$ defined on ordered tuples of $p$ agents, such as the indicator that three specific agents form a triangle. The goal is to estimate the expected value of this outcome given the covariates for those specific $p$ agents.
- Polyadic Dependence
- Outcomes defined on different groups of agents are independent if they share no agents. However, outcomes sharing one or more agents are dependent because those shared agents influence the characteristics of both groups, complicating standard regression techniques.
- Kernel Estimator
- The authors study a kernel estimator analogous to the Nadaraya-Watson method for subgraphs. They establish variance bounds and convergence rates for this estimator, showing how accurately it can estimate the conditional probability of a subgraph's formation.
- Convergence Rates
- The paper provides specific mathematical rates at which the estimator converges. It shows that the numerator converges uniformly in probability over regions expanding polynomially, and the pointwise asymptotic normality is achieved at a rate dependent on $N$ and $d_X$, the dimension of individual agent covariates.
Terminology used across episodes
This episode discusses
- Nonparametric Subgraph Regression · Paper Radio
- Minimax Risk and Uniform Convergence Rates for Nonparametric Dyadic Regression
- Estimating Stochastic Block Models in the Presence of Covariates
The paper
Nonparametric Subgraph Regression · Read on arXiv
Yale University
Estimation and inference on a single large network are challenging due to dependence among observations. This paper studies nonparametric regression for outcomes defined on groups of p agents, such as the indicator that three agents in a network form a triangle. Outcomes on groups that share an agent may be dependent, while outcomes on disjoint groups are independent. I call this problem subgraph regression; it nests dyadic regression as the special case p=2. Its leading application concerns subgraphs of a network, but the methods apply to any outcome defined on groups of agents. I establish a variance bound, uniform convergence rates in probability, and pointwise asymptotic normality for the subgraph analogue of the Nadaraya-Watson kernel regression estimator. The setting differs from regression with i.i.d. data in two ways: (i) the number of observations, of order N p, overstates the effective sample size, which is N, and (ii) the rate of convergence depends on the dimension of the covariates of a single agent rather than of all p agents, which mitigates the curse of dimensionality.
Transcript
Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.
Ruth: We're looking at the paper: "Nonparametric Subgraph Regression".
Warren: Here's the gist of the paper. Estimation and inference on a single large network are challenging due to dependence among observations This paper studies nonparametric regression for outcomes defined on groups of p agents, such as the indicator that three agents in a network form a triangle The leading application concerns subgraphs of a network, but the methods apply to any outcome defined on groups of agents The results deliver two lessons, both of which extend those of Graham et al.
Ruth: (2021) from dyads to groups of any size Model Setup and Dependence Structure The setting involves observing a vector of covariates Xi for N agents and a polyadic outcome Yip for every ordered p-tuple ip=(i1,..., ip) The object of interest is the regression function m(w) = E
Yip Xip = w: , where Xip stacks the covariates of the p agents Outcomes on disjoint tuples are independent, but those on tuples that share an agent are generally dependent through the characteristics of the agents they share, a structure referred to as polyadic dependence This complicates estimation and inference in two ways: first, the N!/(N − p)!
Warren: observed outcomes contain far less information than an independent sample of the same size Second, standard tools for nonparametric regression with dependent data do not apply Kernel Estimator and Convergence Rates The authors study the subgraph analogue of the Nadaraya-Watson kernel regression estimator They establish a variance bound of order (NhdX N)−1 for the kernel numerator Furthermore, they show that the kernel numerator converges uniformly in probability at the rate (ln N/(NhdX N))−1/2 over a region that expands at a polynomial rate Finally, they establish pointwise asymptotic normality of the estimator at the rate (NhdX N)−1/2 Key Findings and Implications The results deliver two lessons, both of which extend those of Graham et al.
Ruth: (2021) from dyads to groups of any size First, the relevant sample size is the number of agents, N, not the number of tuples, which is of order Np Second, the convergence rate depends on dX, the dimension of a single agent’s covariates rather than on pdX This means the optimal uniform rate would be (ln N/N)β/(2β+pdX), but the obtained rate is that of a dX-dimensional problem Theoretical Contributions The paper contributes to three literatures: first, the theory of nonparametric estimation, including optimal rates for weakly dependent observations second, studies of estimation and inference with dyadic and exchangeable array data third, uses subgraph frequencies to learn about network formation This paper establishes a variance bound, uniform convergence rates in probability, and pointwise asymptotic normality for the subgraph analogue of the Nadaraya-Watson kernel regression estimator The framework nests dyadic regression Its leading application is the conditional probability that a group of agents forms a given subgraph, such as a triangle Two questions remain open regarding the minimax lower bound for p ≥ 3 and consistent variance estimation References Aldous, D.
Title and authors: Ruth: Let's talk about the title and the folks who wrote this, "Nonparametric Subgraph Regression." It immediately tells you the scope is about estimating regression functions where the outcome depends on groups of agents in a network.
Warren: The authors are Olivia Ding from Yale University, so we’re looking at someone with strong theoretical grounding in this area.
Iris: From what I see, their goal is to develop methods that handle this dependence structure when you observe outcomes for p agents at once.
Ruth: It's important to understand the core challenge they set up: outcomes on groups that share an agent can be dependent, while outcomes on completely separate groups are independent.
Warren: So, if you’re trying to estimate the probability of a specific pattern forming across several agents, you have to account for that overlap dependence.
Iris: Right. The paper sets up the regression function m(w) as the expected value of that polyadic outcome given the covariates for those p agents.
Ruth: And they explicitly state this nests dyadic regression as a special case when p equals two, which is where things get familiar.
Warren: So, they are building on existing work but trying to generalize it past just pairs, which is a significant step for network analysis.
Iris: They are showing that these methods apply to any polyadic outcome as long as it meets certain moment conditions in Section two of the paper <ref:2611.07240#pg1>.
The paper's summary: Ruth: Moving on to what they actually found, the summary of "Nonparametric Subgraph Regression" highlights how they tackle this dependence problem. They develop a kernel regression estimator analogous to the Nadaraya-Watson method for subgraphs.
Warren: That kernel estimator is what they establish bounds on—they find a variance bound of order one over N times d X.
Iris: That variance bound means that the effective sample size isn't just the number of tuples, which is order N to the power of p, but rather it's actually determined by N, the number of agents.
Ruth: That’s a key insight because it tells us that even though we observe many tuples, we don't get as much information as if those observations were totally independent.
Warren: And they show convergence in probability at a rate related to the logarithm of N divided by N times d X, which is quite specific.
Iris: They also prove pointwise asymptotic normality for the estimator itself, and they state this happens at a rate of one over the square root of that same term, N times d X.
Ruth: So, to put it plainly, they’ve got a variance control, a uniform convergence rate for probability, and an asymptotic normality result.
Warren: It seems like they are providing the rigorous machinery needed to trust these estimators when applied to real network data.
The paper's improvements: Iris: The paper highlights two major lessons that extend previous work on dyadic regression to groups of any size. First, they show the relevant sample size is N, not the number of tuples, which is order N to the power of p.
Ruth: That’s a big shift because it formalizes that dependence between overlapping observations makes inference less precise than just counting all possible tuples.
Warren: And second, they point out that the convergence rate depends on d X, which is the dimension of a single agent's covariates, rather than on p d X, which would be what you might expect from a naive count of variables.
Iris: That means their optimal uniform rate would naturally be something like the logarithm of N divided by N raised to the power of beta divided by two plus p d X over two, but they prove they get a rate tied only to d X.
Ruth: So, the practical implication is that if you’re working with many agents and high-dimensional covariates for each agent, the complexity scales differently than you might guess from just counting the groups.
Warren: It suggests that focusing on how well you model the individual agent characteristics rather than just counting all possible group outcomes is where the efficiency gains are found.
Iris: This moves us toward a more tractable framework for analyzing complex social structures in networks, moving beyond simple pair analysis.
Conclusion: Ruth: So, to wrap up on "Nonparametric Subgraph Regression," they establish the variance bound, the uniform convergence rates, and that pointwise asymptotic normality at the rate of one over square root of N times d X.
Warren: The main implication for me is that we now have a rigorous way to handle these group outcomes without being overwhelmed by the sheer number of potential tuples.
Iris: From my econometric view, it solidifies the theoretical foundation for using these estimators reliably in complex settings, providing a framework where we can actually construct confidence intervals and do hypothesis testing.
Ruth: It’s a big step because it takes what was previously studied in dyadic regression and generalizes it to any group size p, which is a huge extension of the field.
Warren: It opens the door for applying this to things like estimating conditional probabilities of complex subgraph patterns, such as triangles, given agent characteristics like age or income.
Iris: The paper leaves two open questions: first, what’s the true minimax lower bound for when p is greater than two? And second, how do we figure out the variance consistently?
Ruth: That's where the next wave of research needs to go if we want to push this framework further. It sets a very high bar for how we handle dependence in large network data.
More episodes
- Daily Summary for 2026-11-19
- 2608.21274-Recommendation Quality and the Concentration of Consumption: Experimental Evidence from Netflix
- 2408.02757-A nonparametric test for diurnal variation in spot correlation processes
- 2306.16393-High-Dimensional Canonical Correlation Analysis
- 2605.17299-Geometric Brownian motion with intermittent entries and exits
- 2607.04753-Fooling Yourself: how narratives shape beliefs
- 2408.14671-Inference on Treatment Effects with Repeatedly Mismeasured High-Dimensional Controls
- 2201.06898-Difference-in-Differences Estimators for Treatments Continuously Distributed at Every Period
- 2501.15307-Influence Functions: A Unified Differentiation-Based Framework
- The day in conversation for 2026-11-19