Node Regression on Latent Position Random Graphs via Local Averaging
Martin Gjorgjevski (PHD Student - GIPSA-lab)
| When |
Feb 25, 2025
from 01:00 to 02:00 |
|---|---|
| Where | M7 101 |
| Attendees |
Martin Gjorgjevski |
| Add event to calendar |
vCal
iCal
|
Martin Gjorgjevski
Title: Node Regression on Latent Position Random Graphs via Local Averaging
Abstract: 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 regres-
sion, 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.
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 regres-
sion, 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.
Keywords: generalization bounds, graph machine learning, random graphs, nonpara-
metric statistics, kernel regression
metric statistics, kernel regression
Website: https://www.linkedin.com/in/martin-gjorgjevski-01a0ab229/?originalSubdomain=fr
In Room M7 101, 1st floor, Monod campus, ENSL.