CS Paper Radar

An Approach to Study the Structural Consistency of Triangle Badness Functions and Distance Metrics

Bowen Liu, Yizhou Wang, Lingqian Meng

cs.CG math.MGstat.AP ·submitted 2026-08-24 13:55 UTC · v1

Abstract

Triangle-based measures, commonly referred to as badness functions, are widely employed to quantify the extent to which a distance matrix deviates from an ideal geometric configuration. Different formulations of these functions may capture distinct facets of local non-uniformity, and their behavior is often influenced by the underlying distance metric chosen for evaluation. In practical settings, although a canonical badness function may be conceptually preferred, factors such as computational cost, algorithmic constraints, or data-specific characteristics frequently necessitate the adoption of modified versions-for instance, approximate forms or alternatives defined under different distance metrics. This gives rise to a central question: to what degree do these variants retain the structural consistency properties of their original counterparts? To address this issue, we develop a systematic correlation-based framework for evaluating structural consistency. As an illustrative instantiation of this framework, we compute badness sequences from a set of representative distance matrices alongside randomly generated triangle configurations, which are designed to cover variants that may arise under diverse practical scenarios. We then assess pairwise similarities among these sequences using four correlation coefficients. The experimental outcomes indicate that certain badness variants exhibit a notably high degree of structural consistency, whereas others reveal complementary behavioral patterns; moreover, the choice of distance metric exerts a considerable influence on the observed trends. These findings offer practical insights for the informed selection of distance metrics and triangle badness function variants in tasks including geometric reconstruction, triangulation, and structural analysis of pairwise distance data.

Comment
18 pages, 11 tables. Main text in English; includes computational experiments on biological, astronomical, and materials datasets

Closest papers

Nearest neighbours by meaning across the whole index.

What Converges in the Platonic Representation Hypothesis? Structure over Geometry

cs.LG cs.CVmath.AT ·2026-09-23 ·Junwon You, Mihyun Jang, Sangwoo Mo, Jae-Hun Jung
similarity 0.58
Abstract · 33 pages, 12 figures, 6 tables

The Platonic Representation Hypothesis suggests that increasingly capable models converge toward shared representations. Recent work narrows this claim to shared local neighborhood relationships, finding that capacity-dependent trends in several global similarity measures largely disappear after calibration. We challenge this interpretation by showing that prior local-global comparisons confound structural scale (local versus global) with what is compared: relational structure, defined by which samples are related, versus metric geometry, characterized by quantitative relations such as distances, similarities, or correlations. To disentangle these factors, we construct a controlled $2\times2$ framework that evaluates both relational structure and metric geometry at local and global scales. We introduce $H_0$ skeleton overlap as a global counterpart to mutual $k$-nearest neighbors, together with matched distance-aware variants. Across vision-language models, relational structure exhibits robust representational convergence at both scales after calibration, whereas increasingly stringent distance agreement substantially weakens alignment and progressively flattens the capacity-dependent trend. We further extend the analysis beyond ambient Euclidean geometry by evaluating distance agreement under a Riemannian metric approximation and recover the same structure-geometry pattern. The pattern is also reproduced in video-text representations. Together, these results show that relational convergence extends beyond local neighborhoods to global spanning structure, whereas metric geometry exhibits substantially weaker convergence.

0.41

A Fixed-Radius Distance-Band Benchmark for Dimensionality-Reduction Fidelity

cs.LG ·2026-08-22 ·Yoshio Takaeda
benchmarkposition similarity 0.51
Abstract · 20 pages, 13 figures. Code and data: https://doi.org/10.5281/zenodo.21380823

Dimensionality-reduction (DR) methods are routinely judged by how well each point's k nearest neighbors survive the 2-D embedding (recall@k, trustworthiness, continuity). We argue this family is a biased measure of distance fidelity: its per-point variable radius and hard inclusion threshold favor neighbor-graph methods (t-SNE, UMAP) and penalize methods that preserve absolute distances. We instead score DR fidelity with a fixed-radius distance-band Shepard rho: the Spearman correlation between high-D and 2-D pairwise distances, restricted to cumulative distance bands so that near and global structure are reported separately, with every point judged on the same absolute radius. On synthetic datasets with known ground-truth geometry (non-uniform density, dense clusters, a closed-loop transition, off-subspace outliers, imbalanced two-population data) at realistic noise (SNR=1, D=768, N=1000), we benchmark eight methods -- PCA, Isomap, t-SNE, UMAP, PyMDE, PCC, DREAMS, and the closed-source toorPIA -- and show that (i) high global Shepard rho can coexist with a ~93x collapse of within-cluster scale, invisible to rank-based scores but obvious in a value-based over-compression metric; (ii) recall@k and the fixed-radius band disagree systematically, in the direction the bias predicts; (iii) a membership-restricted Shepard rho resolves single-point and minority-population questions that many-pair statistics cannot -- questions on which even DREAMS, a recent local-plus-global hybrid, fails silently. A supplementary out-of-sample (addplot) test asks whether a never-seen anomaly lands outside the normal region and whether its direction identifies its source. All metrics are computed exactly on all pairwise distances, independently of any method's internals, and every number is reproducible offline: the closed-source method's output coordinates (not its algorithm) are committed to the artifact.

0.48

Towards Generalizable 3D Anomaly Detection via Relational Inconsistency Modeling

cs.CV ·2026-09-28 ·KunHo Heo, SuYeon Kim, Hayoung Lee, Chanse Oh, MyeongAh Cho
top venuecode/data similarity 0.51
Abstract · Accepted by NeurIPS 2026. Code: https://github.com/VisualScienceLab-KHU/GRIM

3D anomaly detection (3DAD) aims to identify defective regions in point cloud data, serving as a critical component in industrial inspection systems. Existing methods are normality-centered -- learning the distribution of normal samples and treating deviations as anomalies -- without explicitly modeling what constitutes a defect. This leads to ambiguous decision boundaries with increased false positives and negatives, particularly in unified and cross-domain settings where diverse normal distributions further blur the boundaries. We propose a relational inconsistency modeling framework that characterizes defects as violations of geometric consistency among neighboring structures. Our approach learns category-agnostic defect cues through pseudo-anomalies designed as controlled relational violations, instantiated by two key modules: Edge-aware Graph Refinement (EGR) for encoding geometric relationships among local regions, and Cluster-Deviation Modeling (CDM) for identifying regions that are relationally incompatible within their structural peer group. Extensive experiments on Anomaly-ShapeNet and Real3D-AD demonstrate consistent improvements over prior state-of-the-art methods in both in-domain and cross-domain settings, validating the effectiveness of learning an explicit, relation-based defect criterion for 3D anomaly detection. Project page: https://visualsciencelab-khu.github.io/GRIM_project/.

0.48

Implementation Guidelines for Data Quality Metrics

cs.DB cs.LG ·2026-10-07 ·Philipp Jung, Katinka Becker, Felix Biessmann, Valerie Restat, Martin Seyferth +2 more
code/data similarity 0.51
Abstract · 14 pages, 7 figures, 5 tables. Submitted to EDBT 2027

Despite decades of data quality (DQ) research, a gap remains between DQ dimensions, such as accuracy or completeness, which the literature defines in textual form, and DQ tools, which typically implement low-level checks that are not aligned with these dimensions. ISO/IEC 25024 and ISO/IEC 5259 attempt to bridge this gap by defining DQ metrics for each dimension. However, these DQ metrics are hardly used, because the standards leave open how to implement them: for example, the metric for syntactic accuracy counts syntactically accurate values, but does not state how to decide that a value is syntactically accurate. This simply moves the problem to another level without solving it. As a result, DQ assessment currently cannot build on the standards. In this paper, we make the ISO DQ metrics executable. We classify all data-level metrics of both standards into (i) generalizable metrics that need no input beyond the data, (ii) parameterized metrics whose parameters can be learned from clean reference data or set by an expert, and (iii) non-generalizable metrics that need qualitative judgment and cannot be automated. For the metrics that can be automated, i.e., categories (i) and (ii), we propose implementation guidelines that resolve what the standards leave open. We realize the guidelines in dqmeasure, an open-source library of 20 metrics that learns these parameters from reference data instead of relying on manually defined rules. Our experiments on real-world and synthetic datasets show that the metric scores decrease monotonically with an increasing number of injected errors, decline together with downstream ML performance, and scale linearly with the number of rows, which enables automated DQ monitoring based on the standards.

0.28

Dimension Thresholds for Relative-Error Representations of Finite Metrics in Pseudo-Euclidean Spaces

cs.CG math.MG ·2026-10-16 ·Nikita Muravya, Aleksandr Bespalov, Anna Vozianova
theory similarity 0.51
Abstract

A finite metric space with $N$ points admits an exact representation in a pseudo-Euclidean space of dimension at most $N-1$. We study the minimum dimension required for relative-error approximation of squared distances. Our main result gives an upper bound for arbitrary metrics in terms of local distance ratios: for $4/5<\varepsilon<1$, dimension $O((N/k)\log N+kρ_k^4\log N/(\varepsilon-4/5)^2)$ suffices, where $ρ_k$ is the largest ratio, over all points, between the distance to the $k$th closest point (counting the point itself) and the nearest-neighbour distance. The proof combines a low-rank landmark approximation with a sparse correction controlled by its factorization norm. For metrics with distances in $[1,Φ]$, where $Φ\ge5$ is fixed, the worst-case dimension is $Θ(N)$ for $0<\varepsilon<4/5$, lies between $Ω(\sqrt N)$ and $O(\sqrt N\log N)$ for $4/5<\varepsilon<12/13$, and is $Θ(\log N)$ for $\varepsilon>(Φ^2-1)/(Φ^2+1)$. For $Φ>5$, an intermediate range remains without matching bounds. Sign-pattern counting yields the $Ω(\sqrt N)$ lower bound for $4/5<\varepsilon<12/13$, while Hadamard matrices give explicit linear lower bounds for $\varepsilon<4/5$ via a known approximate-rank estimate. We also construct configurations with null squared intervals whose minimum representation dimension remains $N-1$ for every $\varepsilon<1$. Finally, for every fixed $0<\varepsilon<3/5$, we show that the quadratic dependence on the parameter $C$ in the dimension bound derived from Deng et al.'s pseudo-Euclidean Johnson-Lindenstrauss lemma is necessary up to a logarithmic factor.

0.22

Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein

cs.DM cs.CCmath.CO ·2026-10-12 ·Jens Breitung, Timo Gervens, Julius Pörzgen
similarity 0.51
Abstract

We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.

0.52

The Stretch Factor of Planar Delaunay Triangulations Is Nearly Determined

cs.CG ·2026-09-07 ·Guanlin Mo, Kangke Cheng, Hu Ding
theory similarity 0.50
Abstract · 67 pages, 14 figures, 8 tables. Substantially revised: the upper bound is improved from 1.65 to 1.5949, and the title has changed. Verificat…

The Delaunay triangulation is a classical geometric structure on a finite set of points in the plane. Its stretch factor is the largest ratio of the shortest-path distance along its edges to the Euclidean distance between the same two points. Determining the worst-case stretch factor of planar Delaunay triangulations is a long-standing open problem. We prove a uniform upper bound of 1.5949, improving the previous bound of 1.998 and narrowing the gap to the best known lower bound of 1.5932 from 0.4048 to less than 0.0017, nearly pinpointing the worst-case stretch factor. A central difficulty is that the line segment between two points may cross arbitrarily many triangles. Our progress accounting framework addresses this by converting the global bound into a family of local inequalities, each involving only a fixed number of real parameters regardless of the number of triangles crossed. Two further geometric lemmas make computer-assisted verification tractable: the pencil lemma decomposes each local transition into two geometrically independent stages, reducing verification over infinitely many possible next disks to a single differential condition; and the corner lemmas handle degenerate boundary cases where direct verification would fail. With these reductions, the proof ends with a finite verification of an explicit potential in exact rational arithmetic and outward-rounded interval arithmetic. Numerous geometric network constructions use the Delaunay stretch factor as a black box, so the tighter bound directly improves stretch-factor guarantees for a range of downstream applications, including bounded-degree plane spanners and low-weight spanners.

0.29

Elicited Adaptation: Auditable Localized Fairness via Pairwise Queries

cs.LG ·2026-11-15 ·Shrey Shah
similarity 0.50
Abstract

How much must a predictor's scores change when a community's elicited fairness standard changes? Similarity and tolerance judgments define protected comparisons and acceptable score gaps. We study minimum uniform score movement on a fixed pool of $n$ profiles. For scores satisfying a source standard, we characterize the exact cost of retaining that standard during adaptation: runs of consecutive target constraints along shortest paths determine the optimal amplification factor. Its sharp worst case is $\lfloor n/2\rfloor$, and a full cost curve describes finite target-only repair budgets. Committing before the target is known can cost $n-1$ times the worst repair after revelation, even within one fixed convex ball of two-dimensional Mahalanobis metrics. Positive edge-budget floors cap both factors; bounded geometry also limits the commitment cost. At two interior targets of the construction attaining the $n-1$ bound, similarity queries alone yield a feasible $2$-approximate repair for tolerance $\eps\le1/[2(n-1)]$, reducing movement relative to common repair by a factor linear in $n$. Feasible $(1+α)$-optimal repair on this family has worst-case tolerance-query complexity $Θ(α^{-2}n^2\log(1/δ))$ under a fixed-slope logistic model. The analysis separates the information needed for a substantial adaptation benefit from the precision needed for nearly optimal movement. Elicitation studies and training comparisons examine tolerance choice and the relation between numerical compliance and predictive utility.

0.23