Volume Doubling Condition and a Local Poincaré Inequality on Unweighted Random Geometric Graphs
This provides theoretical foundations for analyzing random geometric graphs in machine learning and data science, but it is incremental as it extends known results to specific graph types.
The paper tackles the problem of establishing fundamental measure-metric properties, specifically a volume doubling condition and a local Poincaré inequality, for unweighted random geometric graphs with vertices sampled from a regular submanifold, showing these hold with high probability under certain regularity conditions.
The aim of this paper is to establish two fundamental measure-metric properties of particular random geometric graphs. We consider $\varepsilon$-neighborhood graphs whose vertices are drawn independently and identically distributed from a common distribution defined on a regular submanifold of $\mathbb{R}^K$. We show that a volume doubling condition (VD) and local Poincaré inequality (LPI) hold for the random geometric graph (with high probability, and uniformly over all shortest path distance balls in a certain radius range) under suitable regularity conditions of the underlying submanifold and the sampling distribution.