Publicación:

Cayley–Menger curvature: a geometric approach to discrete curvature on graphs via local simplex embedding

Resumen

We introduce a discrete curvature measure for graphs based on the Cayley-Menger determinant, which we term Cayley-Menger curvature (κCM). For each node, we construct local tetrahedra from its nearest neighbors under the effective resistance metric, compute the Cayley-Menger determinant to embed them in Euclidean space, and extract the circumradius as a proxy for local curvature. Unlike κFR and κOR, which assign signed curvature values, κCM is strictly positive by construction and is best interpreted as a measure of local geometric compactness with curvature-like behavior, complementary to—rather than a replacement for—signed discrete curvatures. We validate κCM on graphs with analytically known geometric properties—lattices, trees, complete graphs, and cycles—and demonstrate that it produces curvature values consistent with expected flat, hyperbolic, and spherical geometries. Comparison with Forman-Ricci (κFR) and Ollivier-Ricci (κOR) curvatures across a battery of benchmark networks reveals that κCM captures geometric information that is largely independent of these established measures (Spearman |ρ| ⩽ 0.47 in most cases, while κFR and κOR correlate at ρ > 0.7). As a demonstration of practical utility, we show that κCM alone outperforms both κFR and κOR as a feature for community detection in stochastic block models, achieving an order-of-magnitude improvement in Adjusted Rand Index over κFR and κOR used alone, though we note that absolute ARI values remain moderate and the baseline clustering method (Ward linkage) was chosen for simplicity rather than performance; the result demonstrates discriminative power of the κCM feature, not a claim about state-of-the-art community detection. Scalability benchmarks confirm that κCM computes faster than κOR for graphs up to n = 5000 nodes. These results establish the Cayley-Menger curvature as a complementary tool in the discrete curvature toolkit, offering direct geometric interpretability grounded in distance geometry