Nonparametric Subgraph Regression

arXiv:2611.07240 · econ.EM · Submitted 2026-11-04 · Read on arXiv

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

Where the paper says it

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.

(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! p. 1

Where the paper says it

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.

/(N − p)! 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. (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

Where the paper says it

, 2024), dyadic regression (Graham et al. , 2021), empirical process theory for exchangeable arrays (Davezies et al.

A. and E. Giné (1993), “Limit theorems for U-processes,” The Annals of Probability, 21, 1494–1542 Aronow, P. p. 1
Where the paper says it

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.

M., C. Samii, and V. A. Assenova (2015), “Cluster-robust variance estimation for dyadic data,” Political Analysis, 23, 564–577 Bickel, P. p. 3
Where the paper says it

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.

J., A. Chen, and E. p. 0
Where the paper says it

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.

Levina (2011), “The method of moments and degree distributions for network models,” The Annals of Statistics, 39, 2280–2301 Cattaneo, M. p. 3
Where the paper says it

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).

D., Y. Feng, and W. G. Underwood (2024), “Uniform inference for kernel density estimators with dyadic data,” Journal of the American Statistical Association, 119, 2695–2708 Chen, X. p. 3
Where the paper says it

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.

and T. M. Christensen (2015), “Optimal uniform convergence rates and asymptotic normality for series estimators under weak dependence and weak conditions,” Journal of Econometrics, 188, 447–465 Davezies, L. p. 3
Where the paper says it

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.

, X. D’Haultfœuille, and Y. Guyonvarch (2021), “Empirical process results for exchangeable arrays,” The Annals of Statistics, 49, 845–862 Graham, B. p. 3
Where the paper says it

, 2024), dyadic regression (Graham et al. , 2021), empirical process theory for exchangeable arrays (Davezies et al.

S., F. Niu, and J. L. Powell (2021), “Minimax risk and uniform convergence rates for nonparametric dyadic regression,” NBER Working Paper 28548, National Bureau of Economic Research, arXiv:2012. p. 2
Where the paper says it

Graham et al. (2021) establish minimax lower bounds and convergence rates for dyadic regression but do not derive a limiting distribution.

08444 Graham, B. p. 1
Where the paper says it

2017; Sheng, 2020; Graham, 2020). This paper develops nonparametric regression methods for such outcomes when they are observed on a single large network.

S., F. Niu, and J. L. Powell (2021), “Kernel density estimation for undirected dyadic data,” Journal of Econometrics, 240, 105336 Hansen, B. p. 3
Where the paper says it

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.

E., “Uniform convergence rates for kernel estimation with dependent data,” Econometric Theory, 24, 726–748 Jackson, M. p. 3
Where the paper says it

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.

O., Social and Economic Networks, Princeton: Princeton University Press Kitamura, Y. p. 1
Where the paper says it

(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).

and L. Laage (2024), “Estimating stochastic block models in the presence of covariates,” Working paper, arXiv:2402. p. 1
Where the paper says it

(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).

16322 Linton, O. p. 2
Where the paper says it

(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).

and J. P. Nielsen (1995), “A kernel method of estimating structured nonparametric regression based on marginal integration,” Biometrika, 82, 93–100 Lovász, L. p. 2
Where the paper says it

(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).

and B. Szegedy (2006), “Limits of dense graph sequences,” Journal of Combinatorial Theory, Series B, 96, 933–957 McDiarmid, C. p. 1
Where the paper says it

(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).

, “On the method of bounded differences,” in Surveys in Combinatorics, 1989, ed. p. 2
Where the paper says it

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.

by J. Siemons, Cambridge: Cambridge University Press, vol. p. 0
Where the paper says it

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.

141 of London Mathematical Society Lecture Note Series, 148–188 Mele, A. p. 3
Where the paper says it

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.

, “A structural model of dense network formation,” Econometrica, 85, 825–850 Menzel, K. p. 3
Where the paper says it

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).

, “Bootstrap with cluster-dependence in two or more dimensions,” Econometrica, 89, 2143–2188 Newey, W. p. 3
Where the paper says it

, 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.

K., “Kernel estimation of partial means and a general variance estimator,” Econometric Theory, 10, 233–253 Poast, P. p. 2
Where the paper says it

(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).

, “(Mis)using dyadic data to analyze multilateral events,” Political Analysis, 18, 403–425 Sheng, S. p. 2
Where the paper says it

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.

, “A structural econometric analysis of network formation games through subnetworks,” Econometrica, 88, 1829–1858 Stone, C. p. 3
Where the paper says it

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).

J., “Optimal rates of convergence for nonparametric estimators,” The Annals of Statistics, 8, 1348–1360 Tsybakov, A. p. 2
Where the paper says it

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).

B.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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

Related papers