Research map / Learning theory and algorithms / Matrix and tensor methods
MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MetricEmbedding, a tropical (max-plus) inner-product network trained with AdamW to output metric-compliant distance matrices for the metric nearness problem, and a MetricPlug similarity plugin for graph contrastive learning.
Problem
Metric nearness: restoring a noisy, missing, or inconsistent non-metric distance matrix to the closest metric-compliant matrix, where enforcing O(N^3) triangle inequality constraints is computationally expensive and does not scale.
Approach
Uses the max-plus tropical inner product of non-negative learnable factor matrices, with ReLU and max-based bias, so the output is guaranteed to satisfy the triangle inequality by construction; the matrix is fit by gradient descent on a Frobenius loss rather than by iterative constraint projection.
Key results
- At N=100, MetricEmbedding took 0.69 s versus 14.80 s for HLWB and 12.09 s for TRF, with 0% triangle violations (TRF 4.71%).
- At N=1000, MetricEmbedding took 26.73 s, while HLWB and TRF exceeded 2000 s; PAF took 1619.68 s.
- On Cora with MetricPlug, test accuracy was 79.4% versus 76.5% for cosine similarity in GRACE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MetricEmbedding instead of HLWB | Metric nearness optimization · Synthetic complete graph, N=100 | Computation Time (s): 14.80 -> 0.69 | Helped |
| Use MetricEmbedding instead of TRF | Metric nearness optimization · Synthetic complete graph, N=100 | Computation Time (s): 12.09 -> 0.69 | Helped |
| Use MetricEmbedding instead of PAF | Metric nearness optimization · Synthetic complete graph, N=500 | Computation Time (s): 266 -> 16.39 | Helped |
| Use MetricEmbedding instead of HLWB | Metric nearness optimization · Synthetic complete graph, N=1000 | Computation Time (s): >2000 -> 26.73 | Helped |
| Use MetricEmbedding instead of TRF | Metric nearness optimization · Synthetic complete graph, N=1000 | Triangle Inequality Violations (%): 4.85% -> 0% | Helped |
| Use MetricEmbedding instead of HLWB | Metric nearness optimization · Synthetic complete graph, N=1000 | NMSE (Ratio): 0.068 -> 0.136 | Hurt |
| Replace cosine similarity with tropical MetricPlug similarity | GRACE graph contrastive learning · Cora validation | Accuracy (%): 77.4 -> 79.2 | Helped |
| Replace cosine similarity with tropical MetricPlug similarity | GRACE graph contrastive learning · Cora test | Accuracy (%): 76.5 -> 79.4 | Helped |
| Increase latent dimension from 3 to 10 (ablation) | MetricEmbedding · Prediction performance | NMSE: 95.28% -> 88.33% | Helped |
| Increase model depth from 1 to 3 layers (ablation) | MetricEmbedding · Prediction performance | NMSE: 95.28% -> 76.31% | Helped |
| Increase update percentage from 20% to 100% (ablation) | MetricEmbedding online updates · Online prediction | Prediction error: 88.32% to 67.33% | Helped |
Surprising findings
- NMSE of MetricEmbedding (0.136 at N=1000) is higher than the baselines (about 0.058 to 0.072), so speed comes with a larger approximation error.
Limitations
- Approximation error (NMSE) is higher than the baselines in the reported table.
- Scalability claims to 1e5 points are reported without a detailed table.
- Evaluation uses only synthetic complete graphs plus one Cora experiment.
Experimental setup
Datasets: synthetic complete-graph distance matrices (U(0,1) edge weights) Cora
Benchmarks: synthetic complete-graph metric nearness (N=100, 500, 1000) Cora node classification
Metrics: computation time (s) NMSE triangle inequality violation rate (%) validation and test accuracy
Baselines: TRF HLWB PAF GRACE with cosine similarity GRACE with Manhattan, Euclidean, Hamming similarity
Builds on: Bregman projection / triangle fixing (TRF) Project and Forget (PAF) HLWB projection multilayer perceptron
Closest papers by meaning
- Metric Nearness Made Practical (AAAI 2023 · similarity 0.90)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.87)
- Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization (NeurIPS 2024 · similarity 0.86)
- Fully Dynamic Embedding into $\ell_p$ Spaces (ICML 2025 · similarity 0.85)
- Joint Metric Space Embedding by Unbalanced Optimal Transport with Gromov–Wasserstein Marginal Penalization (ICML 2025 · similarity 0.85)
- Metric Space Magnitude for Evaluating the Diversity of Latent Representations (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.