Nonparametric Subgraph Regression
Listen
Radio episode about this paper
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.
Yale University
econ.EM
Submitted: 2026-11-04
Updated: 2026-11-04
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 82/100
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…
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
Summary
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. p. 0 Nonparametric Subgraph Regression
Olivia Ding∗
Yale University
This version: November 6, 2026
(First version: May 17, 2024)
[Click here for the latest version]
Abstract
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.Where the paper says it
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! p. 1 The
results apply to any polyadic outcome that satisfies the moment conditions of Section 2, including
the trade, alliance, and risk-sharing outcomes above. In this setting, 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.Where the paper says it
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. (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
Conclusion
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. J., “Representations for partially exchangeable arrays of random variables,” Journal of Multivariate Analysis, 11, 581–598 Arcones, M. p. 3 , 2024), dyadic regression (Graham et al. , 2021), empirical
process theory for exchangeable arrays (Davezies et al. The proof combines
the covering argument of Hansen (2008) with a truncation argument for heavy-tailed outcomes. Bernstein’s inequality controls the Hájek projection, the exponential inequalities of Arcones and
Giné (1993) control the degenerate components of the Hoeffding decomposition, and a boundeddifferences inequality controls the component driven by the link shocks. convergence rates of Hansen (2008) for kernel estimators and of Chen and Christensen (2015) for
series estimators, and the sup-norm rates and uniform inference of Chen and Christensen (2018)
for nonparametric instrumental variables. The second studies estimation and inference with dyadic
and exchangeable array data. Subgraph frequencies of this kind are central to the analysis of network formation, where clustering
and transitivity are leading summaries of strategic and homophilous linking (Jackson, 2008; Mele,
∗Email: olivia. edu; I am grateful to Yuichi Kitamura, Xiaohong Chen, Tim Christensen, Ed Vytlacil,
P. Examples include the
method of moments based on subgraph counts (Bickel et al. , 2011) and structural models of network formation identified from subnetworks (Sheng, 2020). convergence rates of Hansen (2008) for kernel estimators and of Chen and Christensen (2015) for
series estimators, and the sup-norm rates and uniform inference of Chen and Christensen (2018)
for nonparametric instrumental variables. The second studies estimation and inference with dyadic
and exchangeable array data. convergence rates of Hansen (2008) for kernel estimators and of Chen and Christensen (2015) for
series estimators, and the sup-norm rates and uniform inference of Chen and Christensen (2018)
for nonparametric instrumental variables. The second studies estimation and inference with dyadic
and exchangeable array data. , 2024), dyadic regression (Graham et al. , 2021), empirical
process theory for exchangeable arrays (Davezies et al. Graham et al. (2021) establish minimax lower bounds and convergence
rates for dyadic regression but do not derive a limiting distribution. 2017; Sheng, 2020; Graham, 2020). This paper develops nonparametric regression methods for such
outcomes when they are observed on a single large network. convergence rates of Hansen (2008) for kernel estimators and of Chen and Christensen (2015) for
series estimators, and the sup-norm rates and uniform inference of Chen and Christensen (2018)
for nonparametric instrumental variables. The second studies estimation and inference with dyadic
and exchangeable array data. convergence rates of Hansen (2008) for kernel estimators and of Chen and Christensen (2015) for
series estimators, and the sup-norm rates and uniform inference of Chen and Christensen (2018)
for nonparametric instrumental variables. The second studies estimation and inference with dyadic
and exchangeable array data. (2021), this structure is referred to as polyadic dependence. It arises
under the exchangeable random graph models that underlie much of the econometrics of networks
(Aldous, 1981; Lovász and Szegedy, 2006; Graham, 2020; Kitamura and Laage, 2024). (2021), this structure is referred to as polyadic dependence. It arises
under the exchangeable random graph models that underlie much of the econometrics of networks
(Aldous, 1981; Lovász and Szegedy, 2006; Graham, 2020; Kitamura and Laage, 2024). (2021) observe for
dyads, the reason is that the Hájek projection of the estimator holds one agent’s covariates fixed
and averages over those of the other p − 1 agents. The same averaging improves the rate of partial
means and marginal integration estimators (Newey, 1994; Linton and Nielsen, 1995) and appears
in the analysis of conditional U-statistics (Stute, 1991). (2021) observe for
dyads, the reason is that the Hájek projection of the estimator holds one agent’s covariates fixed
and averages over those of the other p − 1 agents. The same averaging improves the rate of partial
means and marginal integration estimators (Newey, 1994; Linton and Nielsen, 1995) and appears
in the analysis of conditional U-statistics (Stute, 1991). (2021), this structure is referred to as polyadic dependence. It arises
under the exchangeable random graph models that underlie much of the econometrics of networks
(Aldous, 1981; Lovász and Szegedy, 2006; Graham, 2020; Kitamura and Laage, 2024). I decompose it into a U-statistic of order p in the agent primitives and a remainder that has mean
zero conditional on those primitives. Given the agent primitives, the remainder depends only on
the independent link shocks, so I bound it with McDiarmid’s bounded-differences inequality and a
count of the agents whose covariates fall in the support of the kernel. Nonparametric Subgraph Regression
Olivia Ding∗
Yale University
This version: November 6, 2026
(First version: May 17, 2024)
[Click here for the latest version]
Abstract
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. convergence rates of Hansen (2008) for kernel estimators and of Chen and Christensen (2015) for
series estimators, and the sup-norm rates and uniform inference of Chen and Christensen (2018)
for nonparametric instrumental variables. The second studies estimation and inference with dyadic
and exchangeable array data. Examples include the
method of moments based on subgraph counts (Bickel et al. , 2011) and structural models of network formation identified from subnetworks (Sheng, 2020). , 2021), empirical
process theory for exchangeable arrays (Davezies et al. , 2021), the bootstrap under multiway dependence (Menzel, 2021), and double machine learning with multiway clustering (Chiang et al. (2021) observe for
dyads, the reason is that the Hájek projection of the estimator holds one agent’s covariates fixed
and averages over those of the other p − 1 agents. The same averaging improves the rate of partial
means and marginal integration estimators (Newey, 1994; Linton and Nielsen, 1995) and appears
in the analysis of conditional U-statistics (Stute, 1991). Extending their lower bound to p ≥ 3 is
left for future work. The analysis faces technical challenges that do not arise in the dyadic case. Examples include the
method of moments based on subgraph counts (Bickel et al. , 2011) and structural models of network formation identified from subnetworks (Sheng, 2020). The first is the theory of nonparametric estimation. With independent observations, it includes the optimal rates of Stone (1980, 1982) and the textbook treatment in Tsybakov (2008).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Higher-order polyadic estimation for network data allows AI systems to estimate conditional probabilities of complex subgraph patterns, such as a triangle, given agent characteristics like age or income.
-
The uniform convergence rates in probability show that the estimator converges uniformly over regions expanding at a polynomial rate, ensuring reliable performance across diverse covariate settings.
-
Pointwise asymptotic normality at the rate (NhdX/N) to (NhdX/N) 1/2 allows for the construction of confidence intervals and hypothesis testing for subgraph probabilities.
-
The variance bound shows that the effective sample size is determined by N, not the number of tuples, providing a more accurate interpretation of data dependence in large networks.
-
The framework applies to any polyadic outcome satisfying moment conditions, enabling AI systems to analyze trade flows and risk-sharing arrangements beyond simple dyadic pairs.
Abstract
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.
Sources
- Minimax Risk and Uniform Convergence Rates for Nonparametric Dyadic Regression
- Estimating Stochastic Block Models in the Presence of Covariates
Related papers
- Stationarity with Occasionally Binding Constraints
- Backtesting High-Dimensional Expected Shortfall
- Higher-Order Neyman Orthogonality in Moment-Condition Models
- Online Bayesian Inference for a Dirichlet Process Mixture of Binary Logit Models
- Debiased Conditional Independence Tests for Causal Effects
- Sharp Testable Implications of Encouragement Designs