# Node Regression on Latent Position Random Graphs via Local Averaging

arXiv: https://arxiv.org/abs/2410.21987 · HTML: https://mlsanity.com/paper/2410.21987/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 44 references that are in the map.
- First posted on arXiv 29 Oct 2024.

## Builds on (most cited first, 20 of 20)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Graph-based Semi-supervised Learning: A Comprehensive Review](https://mlsanity.com/paper/2102.13303/) (2021)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [Prediction models for network-linked data](https://mlsanity.com/paper/1602.01192/) (2016)
- [Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs](https://mlsanity.com/paper/2304.11140/) (2023)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regression](https://mlsanity.com/paper/2311.00140/) (2023)
- [Sparse random graphs: regularization and concentration of the Laplacian](https://mlsanity.com/paper/1502.03049/) (2015)
- [Near-Perfect Recovery in the One-Dimensional Latent Space Model](https://mlsanity.com/paper/2006.04351/) (2020)
- [Community detection in sparse latent space models](https://mlsanity.com/paper/2008.01375/) (2020)
- [Reconstruction of Random Geometric Graphs: Breaking the Omega(r) distortion barrier](https://mlsanity.com/paper/2107.14323/) (2021)
- [Nonparametric regression on random geometric graphs sampled from submanifolds](https://mlsanity.com/paper/2405.20909/) (2024)

## Abstract (arXiv)

Node regression consists in predicting the value of a graph label at a node, given observations at the other nodes. To gain some insight into the performance of various estimators for this task, we perform a theoretical study in a context where the graph is random. Specifically, we assume that the graph is generated by a Latent Position Model, where each node of the graph has a latent position, and the probability that two nodes are connected depend on the distance between the latent positions of the two nodes. In this context, we begin by studying the simplest possible estimator for graph regression, which consists in averaging the value of the label at all neighboring nodes. We show that in Latent Position Models this estimator tends to a Nadaraya Watson estimator in the latent space, and that its rate of convergence is in fact the same. One issue with this standard estimator is that it averages over a region consisting of all neighbors of a node, and that depending on the graph model this may be too much or too little. An alternative consists in first estimating the true distances between the latent positions, then injecting these estimated distances into a classical Nadaraya Watson estimator. This enables averaging in regions either smaller or larger than the typical graph neighborhood. We show that this method can achieve standard nonparametric rates in certain instances even when the graph neighborhood is too large or too small.