MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Authors: Muyang Cao
Jiajun Yu
Xin Du
Gang Pan
Wei Wang
Venue: ICML 2025 poster (2025)
Keywords: metric nearness problem
metric
triangle inequality
tropical inner product
Primary area: general_machine_learning
TL;DR: We propose MetricEmbedding, which accelerates the Metric Nearness Problem using tropical inner product, achieving up to 60× faster computation and significantly reducing memory usage while preserving metric properties in large-scale matrices

Abstract: The Metric Nearness Problem involves restoring a non-metric matrix to its closest metric-compliant form, addressing issues such as noise, missing values, and data inconsistencies. Ensuring metric properties, particularly the  $O(N^3)$ triangle inequality constraints, presents significant computational challenges, especially in large-scale scenarios where traditional methods suffer from high time and space complexity. We propose a novel solution based on the tropical inner product (max-plus operation), which we prove satisfies the triangle inequality for non-negative real matrices. By transforming the problem into a continuous optimization task, our method directly minimizes the distance to the target matrix. This approach not only restores metric properties but also generates metric-preserving embeddings, enabling real-time updates and reducing computational and storage overhead for downstream tasks. Experimental results demonstrate that our method achieves up to 60× speed improvements over state-of-the-art approaches, and efficiently scales from $1e4 \times 1e4$ to $1e5 \times 1e5$ matrices with significantly lower memory usage.

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Muyang Cao 12 Jiajun Yu" 12
Xin Du 3 Gang Pan
Wei Wang 45
Abstract
ties dies-specifically, non-negativity, symmetry, and the trian- gle inequality (Randic et al., 1994). The triangle inequality ensures that for any three points, the direct distance between two points does not exceed the sum of the distances through an intermediary point (Sra et al., 2004; Brickell et al., 2008). These properties are crucial for maintaining the accuracy and stability of downstream applications (Roth et al., 2002: Elkan, 2003: Hussain, 2018).
The Metric Nearness Problem involves restoring a non-metric matrix to its closest metric-compliant form, addressing issues such as noise, missing values, and data inconsistencies. Ensuring met- ric properties, particularly the ((N)) triangle in- equality constraints, presents significant compu- tational challenges, especially in large-scale sce- narios where traditional methods suffer from high time and space complexity. We propose novel solution based on the tropical inner product (max- plus operation), which we prove satisfies the trian- gle inequality for non-negative real matrices. By transforming the problem into continuous opti- mization task, our method directly minimizes the distance to the target matrix. This approach not only restores metric properties but also generates metric- pretrippreerrinnggg embeddings, enabling real-time updates and reducing computational and storage overhead for downstream tasks. Experimental re- sults demonstrate that our method achieves up to 60x speed improvements over state-of-the- -hrt---rrttttttte ap- proaches, and efficiently scales from le4 1e4 to le5 * 1e5 matrices with significantly lower mem- ory usage.
However, real-world distance matrices often deviate from ideal metric properties due to noise, measurement errors, missing data, and structural inconsistencies. Such devia- tions can disrupt downstream tasks, leading to unreliable predictions and degraded performance (Indyk, 1999; Russell & Norvig, 2016; Yu et al., 2023). For example, in clustering, an algorithm typically assigns an object to its nearest clus- ter centroid based on given distance function (Hartigan et al., 1979; Jain & Dubes, 1988; Park & Jun, 2009). If the distance matrix violates the triangle incquality, objects assigned to the same cluster may appear far apart, leading to unstable clustering. Similar issues arise in shortest- path computations, and recommender systems, where violations of metric properties cause inconsistencies in similarity and ranking.
To address these inconsistencies, the Metric Nearness Prob- lem (MNP) seeks to transform given distance matrix into the closest metric-compliant matrix while preserving as much original information as possible (Brickell et al., 2008). The primary challenge lies in satisfying the O(N3) triangle inequality constraints while maintaining computational effi- ciency. Traditional approaches rely iterative projection methods, such the Bregman projection algorithm (Brick- ell et al., 2008: Sonthalia & Gilbert, 2022) and the HLWB projection algorithm (Li et al., 2023), or learning-bant based methods that approximate a valid distance metric. However, these methods face high computational cost, poor scalability, and limited real-time adaptability, which hinder large-scale applications needing efficient metric corrections.
1. Introduction
Distance matrices fundamental in various machine learn ing and optimization tasks, including clustering, K-nearest neighbors (KNN), and recommender systems (Jain et al., 1999; Cover & Hart, 2006; Peterson, 2009; Lü et al., 2012; Piao & Breslin, 2016). Among them, commonly used matrices such as shortest path distance matrices and Eu- clidean distance matrices must adhere metric proper-
"College Computer Science and Technology, Zhejiang Uni- versity 'Shanghai Innovation Institute "Shool of Software Tech- nology, Zhejiang University* The Hong Kong University of Sci- ence and Technology (Guangzhou)) The Hong Kong Univer- sity of Science and Technology. Correspondence to: Xin Du <xindu @ www.eduu.nn>... Wei Wang <weiwes @ hus..hk>.
In this paper, we introduce tropical inner products into Eu- clidean space by defining a novel tropical inner product between matrices (or vectors). This construction provides a theoretical foundation for linking tropical algebra to metric matrices, filling a key gap in the literature. Most importantly, we prove that the tropical inner product of two non-negative
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

MetricEmbeddingg Accelerate Metric Nearness by Tropical Inner Product
matrices satisfies the triangle inequality, ensuring that it can be used to construct valid metric matrices.
rieEmbedd,ng, a network structure built with tropical inner product, capable of predicting a metric matrix that is sufficiently close to a target distance matrix. It has advantages in scalability, real-time prediction, and computational efficiency.
Building on this, we establish the Tropical Algebra-mente metric representation theorem(TA, TA-metric representation theorem), which reveals the representational space of the tropical in- ner product of non-negative matrices and its relationship with metric matrices. This result formally characterizes the representational capacity of tropical inner products in metric space. Additionally, we derive series of theoretical insights into the relationship between tropical inner prod- uets and metric matrices, including the relationship between shottest-path distances and tropical inner product.
3.
We propose method based on the tropical inner prod- uct, where no changes are needed in the network struc- ture except for adding a layer to guarantee that the network output satisfies the triangle inequality or met- ric properties. This approach holds significant potential for metric learning and contrastive learning tasks.
2. Preliminary
Leveraging this theoretical framework, we propose Met- rieEmded,ing, a novel approach based on tropical inner products and gradient descent for solving the Metric Near- ness Problem (MNP). Specifically, we designed a Met- ricEmbedding architecture based solely on the max-TA inner product, with each network's 's parameters aimed at approximating a target matrix. This distinguishes it from traditional MLP(Cybenko, 1989) and other similar deep neural network architectures, including the min-max man-mux-plus LLuo & Fan, 2021). I.nstaddd of learning latent dis- tributions, our model directly approximates target met- ric matrix using parameterized tropical algebra operations. Furthermore, we enhance deep learning architectures by integrating ReLU activation and tropical inner products, en- suring that the output satisfies the triangle inequality. This enables applications in metric learning and contrastive learn- ing.
Tropical Inner Product and Matrix Multiplication
Tropical algebra replaces traditional operations with tropi- cal ones (Maslov, 1985; Cuninghame- -Green, 2012). In the Max- Semiring, addition is the maximum (mmax) and multiplication is standard addition (+) (Maragos et al., 2021). The Min- Tropical Semiring is its dual, with addi- tion as the minimum (#min) and multiplication remaining standard addition (8) (Joswig, 2021).
Formally, the Max-Tropical Semiring is defined as (R U {-o0), maxx @). where @max denotes the maximum oper- ation and @ is standard addition, while the Min- Tropical Semiring is defined as (R U {oo), @ain: 8), where Smin denotes the minimum operation.
Here, We adapt tropical operations to define the tropical in- ner product in Euclidean space. Let R" denote the Euclidean space of dimension n. For two vectors:
Our approach also introduces key improvements in compu- tational efficiency and scalability. By modifying the loss function, our method flexibly adapts to different problem formulations, supports mini-batch optimization, and scales efficiently to large datasets. Additionally, we develop an online prediction mechanism, making our model suitable for real-time applications. Experimental results demonstrate that method achieves up to 60x speed improvements over sfate-of-the-art approaches, while efficiently scaling from 10ah x 10a to 10y x 10t matrices with significantly lower memory usage.
u = (u1, W2,
un) and v = (uI, 02 02...., Up) E ER"
the tropical inner product is defined as:
(u, D) Bres
max (u, + +e), 15i5n
where Pmax denotes tropical addition (maximum) and @ denotes standard addition. This product computes the maxi- mum sum of corresponding elements from the two vectors.
This concept extends naturally to matrices. Given two ma- trices A E gaxm and B E "x,,, the tropical matrix inner product (or tropical matrix multiplication) is defined as:
The contributions of this paper can be summarized as fol- lows:
1. We introduce the tropical inner product into Euclidean space and establish theoretical framework that con- nects tropical inner products and metric matrices. Our key result, the TA-metric representation theorem, re- veals the representational space of the tropical inner product of neg-negetive matrices and its relationship with metric matrices, providing novel and principled way to construct metric matrices.
C A O max B E R
where @mux denotes the tropical multiplication using the maximum operation. Each element C(i,j) of the resulting matrix C is computed using tropical operations as follows:
CL. = max (Ar, + BR.s).
ISkSm
2. Based on this theoretical findings, we propose Met-
Alternatively, the tropical matrix product can be defindd
2

---

MetricEmbeddingg Accelerate Metric Nearness by Tropical Inner Product
using the minimum operation, denoted mii- where:
other theorems in the Appendix B.
C min (Ar,s + BR.)). 15k5m
Theorem 1:
If matrix A E RNNN satisfies the triangle inequality, and matrix B E RNXN satisfies the triangle inequality, then the matrix C' = A+ B RNXN also satisfies the triangle inequality.
As shown in Appendix A, in both cases, tropical matrix multiplication computes the maximum or minimum "path" sum from row i of matrix A to column j of matrix B. con- sidering all possible intermediate paths through index k.
Theorem If matrix E RNNN a metric matrix, then for any positive constant a, aA is also a metric matrix.
Metric Nearness Problem
Theorem 3: If matrix A satisfies the triangle inequality, then the matrix A + A = B, and after setting the diagonal elements of B to 0, the resulting matrix satisfies the metric properties.
A metric matrix M E N must satisfy the following conditions for all i,j, k E (1.2...., N NJ: Myj 2 0:Symmetry: Ma = Triangee Inequality: Mij I M,x + Maj for all j. k. set My represents the space of all valid metric matrices of size N x N, where each matrix M My satisfies the conditions of metric, i.e. non-negativity, symmetry, and the triangle inequality (Sra et al., 2004; Brickell et al., 2008; Li et al., 2023).
Theorem 4: and are both x metric matrices, then the element-wise maximum of A and B, denoted as max (A, B), also a metric matrix.
Theorem 5: Let A E RNNK and B E RKXN be non- negative matrices, and let C = A Omax B. Then for any i,j,k k E NJ, wehave Cik + Cuj 2 Céj.
On the other hand, non-metric matrices may not satisfy the triangle inequality or symmetry, and they may contain nega- tive values or inconsistent entries, making them unsuitable for tasks that depend on metrie structures, such clustering or optimization (Brickell et al., 2008).
Proof: By definition, C. = max, (Air + Brz). Assume that when r 8, equality holds, i.e., C2j Ais + Buj- Aia S Ais + Baa S Cik max, (Air + Brx) and Baj S
ARs + Baj S Ckj mar,(Asr + B,5), we have:
Given a distance matrix D NRN,,, the goal of the Met- ric Nearness problem is to find metric matrix M E MN. such that M minimizes the difference from D under some "closeness' metric, while satisfying the properties of a met- ric matrix (Sra et al., 2004; Brickell et al., 2008; Sonthalia & Gilbert, 2022; Li et al., 2023). The problem can be for- mulated as:
Ci S Cik + Ckj-
the tropical inner product satisfies the triangle inequality.
Theorem 6: Let A be a non-negative matrix of size N x K. Define B = A mmax AT as the tropical inner product of A with its transpose. Let Boff he the matrix obtained by setting the diagonal elements of B to zero. Then, Ball is a metric matrix.
M arg min | O (X D)Ilp
XEMN
where My denotes the set of all valid N x N metric matri- ces, W is a symmetric weight matrix, indicating the trust level in the entries of D, O represents element-wise multi- plication, p is the norm used to measure the "closeness" of the matrices.
Theorem 7: Let A N and B E R be non- negative matrices, where k > N M. Then, there exist matrices A' E Nx and B' E RR XN with k < N * M, such that:
A' @max B' A mmax B.
The goal of this optimization problem is to find metric matrix M that is the closest to D in terms of the weighted p-norm difference.
Theorem 8: max- TA- Representation Theorem
Let Q denote the set of all matrices produced by tropical inner products of non-negative matrices:
Additionally, let B E N be a square matrix. We define Boff E TR X as the matrix obtained by setting the diagonal elements of B to zero, i.e., Boll B dBag(B) where diag(B B) represents the diagonal matrix consisting of the diagonal elements of B.
Ω = M M =
(X O max Y off X.YERNA BNK]]
where [X Omax YT )iy = max (it + Y,K).
Let V C R NxN be the set of matrices D satisfying:
20
3. Methods
Da 0 Vi E (1,2,
3.1. TA-metric Representation Theorem
In this subsection, we investigate the relationship between tropical operations and metric matrices, The proof and the
Di S mink Dia + mink Dkas Vi.j E
[1,2, N}.
3

---

MetricEmbeddingg Accelerate Metric Nearness by Tropical Inner Product
Then, S = V. The set of matrices generated via the tropical inner product (with diagonals removed) from non-negative matrices constitutes specific subset of the set of non- negative matrices with zero diagonals that satisfy the tri- angle inequality.
based tropical algebra, progressively building richer rep- resentations of the target matrix to overcome the limitations of single-matrix modeling. By using tropical inner products (mmax) and tropical addition (@), MetricEmbedding pre- serves the metric properties and allows the model to capture more intricate patterns, effectively balancing expressiveness with computational efficiency.
Besides any matrix D E V also satisfies the standard trian- gle inequality,
The architecture of MetricEmbeddingg can be formalized as follows: 0 ((Wo Omaz W1) @ b1) -b--)) Omar W&) e by Where:
Dij S Dik + DDj Vi,j, E 1..2....N
as a consequence of the combination of the two conditions above.
Wo E xxd is the learnable input matrix, where N is the number samples and dg is the number of features. Unlike traditional MLPs, where the input is a fixed vector derived from the input data, Wo is treated learnable non-negative matrix.
3.2. Optimization Strategy: MetricFmmbedding
In this work, we propose MetricEmbedding for solving the Metric Nearness Problem, aiming optimize the non- negative matrix A such that the tropical inner product (A mmx y closely approximates the target matrix D, while preserving essential metric properties like the trian- gle inequality, as established in Theorems 5,6. For conve- nience in discussion, we set the optimization objective as the squared Frobenius norm between (A @maz A )off and D:
Vi f1, k), W; R20 dd:-xx;; are the non- negative weight matrices, connecting layer i- to layer i. ensuring the output matrix remains non-negative.
Vi E (1.2....,A))
E I8%, are the non-negative bias terms each layer, These bias terms serve as optional adjustments shift the output of each layer while maintaining the local structural properties of the data.
max denotes the max- tro-iclpical inner product. This op- eration preserves the local structure of the output at each layer.
min [I(A Omax yo -D1?
Here, A E R xox is the matrix to optimize, where N is the number of data points and k is a hyperparameter control- ling the model's expressiveness. D E IR N is the target distance matrix.
@ denotes tropical addition (element-wise maximum operation), similar to the addition operation in MLPs, but replacing addition with the element-wise maxi- mum, ensuring the preservation of the local structural features of the output.
Inspired by tropical rank (Guillon et al., 2015) and stud- ies on matrix factorization complexity (Shitov, 2014), and based on the analysis of Theorem 7, we observe that in- creasing the parameter & can indeed enhance the expressive power of the model when constructing tropical algebraic representations. However, the marginal gains diminish as k increases. At the same time, larger model capacity may introduce optimization challenges such as gradient sparsity. Therefore, in practical modeling, trade-off must be made between expressive power and computational efficiency. Ac- cording Theorem 8, although the tropical inner product space is subset of metric space, it still possesses sufficient expressive capability to capture essential metric properties. This ensures that the generated matrix retains desirable met- ric characteristics while maintaining high computational efficiency. Based on this, our model design emphasizes the efficient approximation of the target matrix D, while also controlling resource consumption during training and inference.
Mad
Traditional
Motrellibbeddngg
Figure I. Comparison between MLP and MetricEmbeddingg MLP ReLU activation and standard matrix multiplication, while MetricEEbeedding removes ReLU, replaces matrix multiplication with max- aax-trapical inner product, and modifies the bias addition max operation.
To further improve the modeling capacity for complex struc- tures, MetricEmbeddinng draws inspiration from multilayer perceptrons (MLPs) (Cybenko, 1989) and other deep neu- ral network architectures. It adopts a multi-layer structure
The training procedure for MetricEmbedding follows the typical neural network optimization pipeline, with some key modifications. The weight matrices Wo, Wi...., Wa and

---

MetricEmbeddingg Accelerate Metric Nearness by Tropical Inner Product
Algorithm 1 Training Procedure for MetricEimbedding threshold
3.3. Troptical innerproduct for Metric Learning
Input: Target matrix D, AdamW thrshiler
Traditional metrie learning relies on Euclidean distance or cosine similarityBerrtintto et al., 2016; Schroff et al., 2015; Kaya & Bilge, 2019), but these metrics struggle with captur- ing complex, non-linear relationships and may fail to satisfy the triangle inequality, which could negatively affect the performance of tasks such as contrastive Maaming(Khosse et al., 2020; Chen et al., 2020). overcome these limita- tions, we introduce MetricPlug, plugin that leverages tropical innerproduct to extend traditional metrics. Our ap- proach ensures that the output satisfies metric properties and enables learning of more diverse metric relationships.
Output: Optimized weight matrices Wo. Wi...., Wa
Optimized bias vectors b b....., Final output matrix O Initialize:
Initialize weight matrices Wo, Wi...., Wa with Gaus- sian distribution.
Initialize bias vectors bı,... by randomly.
Training Loop:
while Convergence criteria not met do
Initialize the A = Wo
Forward Pass:
for layer i 1...... do
Once the embeddings are obtained from the neural net- work, we apply the ReLU activation function to ensure all elements are non-negative, which is a common requirement in metric learning, After applying the ReLU activation func- tion to the embeddings A, the distance between any two points and j in the learned space can be computed using the tropical inner product. The distance matrix is computed as:
| Compute A, = A Omax W; @ b; end
Loss Calculation:
Compute the loss = (A mmax A A7) f D11
Backpropagation:
Compute gradients of L with respect to W; and 6; for each layer.
Parameter Update:
O (ReLU(A) O Re)U(A)?) off
Use AdamW optimizer to update W; and by based on the computed gradients.
According to theorem 6, this ensures that the output matrix satisfies the metric properties, particularly non oon-eeatiivtty and the triangle inequality.
Regularization:
for layer i 1...d d do
| Apply non-negativity constraints: W; 2 0, 0 2 O. end
For pair of embedding matrices A and B (both of size N x K), the tropical distance between them is computed as:
Check for Convergence:
If L. change between iterations is smaller than the threshold, break the loop.
O (ReLU(A) @max ReLU(B)") off
end
This is submatrix of the larger tropical matrix RELU(A) (eLU
ReLU(A) O Omax
1' ) which is a valid
ReLU(B)
biases bi...., by are initialized using values drawn from up Gaussian distribution, where the mean is set to 22=2 with μD being the mean of the target matrix D and d representing the number of layers. The input matrix Wo is initialized as a learnable non-negative matrix. During training. X is prop- agated through the network, where tropical inner products and tropical addition applied at each layer. The loss is calculated the Frobenius norm of the difference between (O @max Oafofl and the target matrix D. Gradients of the loss are computed through backpropagation and the param- eters are updated using AdamW. To maintain the matrix's 's metric properties, nog-negatyvyty constraints are enforced on each parameter after every update.
metric matrix and preserves the metric properties required for distance computations.
The tropical distance matrix O can be used in the same way as a traditional distance matrix for downstream tasks. For example, it can be used to compute the pairwise distances be- tween data points, where Oiy represents the tropical distance between points and j. This matrix can then be utilized in clustering, retrieval, or other metric-based tasks, simi- lar how Euclidean or cosine distance matrices are used. Additionally, O preserves the metric properties, ensuring consistency in the relationship between data points.
3.4. Method Analysis
Through this approach, MeuricEmbedding leverages trop- ical algebra to ensure that the learned matrix adheres to essential metric properties, while maintaining high compu- tational efficiency. By incorporating multi-layer architec- ture, MetricEmbedding captures complex structural patterns and balances expressiveness with robustness, overcoming the limitations of single-matri representations.
As summarized in Appendix C, MetricEmbeediing signif- icantly outperforms traditional methods in both time and space complexity. While methods such as TRF (Brickell et al., 2008) and PAF(Sonthalia & Gilbert, 2022) suffer from cubic time and space complexity (O(n²), MetricEm- bedding reduces the time complexity to O(n2k) and the
5

---

MetricEmbeddingg Accelerate Metric Nearness by Tropical Inner Product
space complexity O(n²), where n denotes the number of points and & is the embedding dimension. This improve- ment allows it to efficiently handle large-scale tasks, even when dealing with massive datasets that would overwhelm traditional matrix-based approaches.
Computation Time (s): The time required compute
the metric for the given matrix.
Prediction Accuracy: We use the normalized mean squared error (NMSE) as the measure of nearness, de- fined as:
NMSE = | - Dell?
One of the key advantages of MetricEmbedding lies in its use of tropical inner products maintain the triangular in- equality structure. This not only reduces the computational cost but also enables the algorithm to process larger matrices. More importantly, tropical inner product operations-baat on max and addition-art are naturally suitable for parallel com- putation on GPUs, which brings substantial performance gains. This parallelism makes MetricEibbedding particu- larly effective for large-scale data. By combining tropical algebra with mini-batch processing, MetricEmbeddingg effi- ciently performs large-scale matrix computations, making it well-suited for environments with limited memory re- sources.
|
where is the result obtained by applying different methods to process Do, as in previous work (Li et al., 2023).
Triangle Inequality Violations ( (%): The percentage of triangle inequality violations after fixed number of iterations. For convenience, the violation ratio is count of violated incqualiries
computed as
N²
The experiments are con- ducted a machine with RTX 4090D GPU (24GB) and 32 vCPUs (Intel Xeon Platinum 8474C), running Linux-based operating system.
Experimental Environment:
Furthermore, the flexibility of MetricEmbeddiing allows for more adaptable weight updates. By calculating the loss function and applying gradient descent, it offers dynamic approach modifying results, unlike static methods. This flexibility is further enhanced by its support for online learn- ing, enabling the algorithm to update continuously in real- time applications without needing to retrain from scratch. Such adaptability makes MetricEmmeddiing ideal for scenar- ios with evolving datasets, like recommendation systems or path optimization tasks.
Hyperparameters: For MetricEmbeddingg the learning rate is set to 0.001 using the Adam optimizer. The model is initialized as described earlier. We use Python implementa- tions of TRF and HLWB, and the Julia implementation of PAF. All methods are evaluated based on their convergence time.
4.2. Performance evaluation
As shown in Table 1, our method (MetricEmbeddding) out- performs TRF and HLWB in terms of computational effi- ciency, significantly reducing computation time even for large datasets. For instance, when N = 100, MetricEmbed-- ding takes only 0.069 seconds, compared to 12.09 seconds for TRF and 1 14.80 seconds for HLWB. As the number of nodes increases, this time difference becomes even more pro- nounced, demonstrating our method's ss superior scalability. In terms of error rates, MetricEmneddingg performs similarly to TRF.HLWB and PAF, maintaining low error rate (e.g.. 0.084 for N = 100), while offering a substantial reduc- tion in computation time. Furthermore, MetricEmbeedingg consistently adheres to metric properties, with no triangle inequality violations, unlike TRF, which shows violations exceeding 4% on larger datasets. These results highlight the optimal balance between accuracy, computational efficiency, and metric preservation that MetricEmbedding achieves.
4. Experiment
4.1. Experimental Setup
Datasets: The experiment uses synthetic data generated from a complete graph. The graph contains nodes of sizes 100, 500, 1000, with edge weights sampled from a uniform distribution U (0, 1) followngg the data generation strategy outlined in the previous work (Li et al., 2023).
Baselines: We compare method with three well- established algorithms:
TRF:
Efficient triangle fixing algorithm based on an it- erative projection method, a classic algorithm (Brickell et al., 2008).
HLWB: Efficient algorithm based HLWB projec- tions, well-regarded method for metric nearness(Li
We tested the scalability of our approach, and although the computing platforms were not identical, the results highlight its superiority. Compared to TRF (Brickell et al., 2008) and PAF (Sonthalia & Gilbert, 2022), HLWB (Li et al., 2023) has lower space complexity of O allowing to han- dle larger matrices (e.g., over 10,000 points). However, its
et al., 2023).
PAF: Project and Forget-an active set method for effi- ciently solving the metric nearness baoblem(Sonthalll & Gilbert, 2022).
Evaluation Metrics: The following metrics are used to evaluate the performance of the methods:
'The recently open-sourced Python implementation of HLWB may offer improved runtime performance.
6

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Table Comparison of Methods: Ours, TRF, HLWB, and PAF for Different Matrix Sizes. The table compares computation time, NMSE,
and triangle inequality violations for four methods: Ours, TRF, HLWB, and PAF
Matrix Size (N)
Method
Computation Time (s)
NMSE (Ratio)
Triangle Inequality Violations ( (%)
100
Ours
0.69
0.084
0%
HLWB
14.80
0.072
0%
TRF
12.09
0.059
4.71 %
PAF
21.844
0.071
0%
500
Ours
16.39
0.099
0%
HLWB
1291.61
0.069
0%
TRF
1120.73
0.058
4.53%
PAF
266
0.069
0%
1000
Ours
26.73
0.136
0%
HLWB
>2000
0.068
0%
TRF
2000
0.058
4.85%
PAF
1619.68
0.068
0%
Rates Belore
Mler
(30% to 50%) and noise levels (0.3 to 0.5). In the follow- ing figures, the notation "M30" represents a missing rate of 30%, "N0.3" represents Gaussian noise with a mean of 0.3, and similarly for other values. We applied missing data handling by randomly selecting data points and then used the MetricEmbeedding model for recovery. Hyperparameter settings are the same as in Section 4.1. We evaluate the reconstruction quality using the Normalized Mean Squared Error (NMSE) defined in Section 4.2, which we refer to as the error rate.
Retrem
55.15
Alter
49:35
37.15
Emt
$3.05
33
24.57
15.28
Consitionn
As shown Figure 2, the model performs reasonably well in both scenarios. Specifically, for both missing data and noisy data, the model significantly reduces the error and maintains low recovery error even in cases with high noise or high missing rates. These experimental results validate the effectiveness of the proposed algorithm in these complex scenarios.
Figure Performance comparison the model under different missing rates and noise levels. "M30" indicates missing rate of 30%, "NO.3" indicates Gaussian noise with a mean 0.3, and similarly for other values.
time complexity limits its ability to scale. In contrast, our method achieves both optimal space complexity (O(N2)) and time complexity (O(N²k)), enabling it to efficiently handle much larger matrices. It can solve problems of size 2 100, 000 points within hours, significantly outperform- ing HLWB, which can only handle matrices up to 10,000 points. This demonstrates the scalability and efficiency of approach for scale problems.
4.4. Online Update Capability
To validate MetricEmbedding's online update capability, we incrementally fed new data and measured both update speed and prediction accuracy by varying the percentage of point pairs used for updates (from 20% 100%).TT T. its online learning ability, new data generated specifically for testing purposes.As shown in figure 3, The prediction error, defined as ||A showed that the error stabilized data was added, improving from 88.32% to 67.33% as the update percentage increased. These results demon- strate MetricEEmeedding' ability to maintain high accuracy and efficiency with relatively few updates, while handling complex relationships and preserving the underlying met- ric structure, even with noisy or multi-source data. Unlike traditional methods like PAF, which struggle with general- ization, MetricEmbeddinng's multi-layer structure and tropi-
||||
4.3. Robustness Test
In this work, we evaluate the performance of the model in recovering incomplete matrices and matrices with noise, fo- cusing on the impact of missing data and noise interference on recovery accuracy. In this experiment, we first computed the Euclidean distances between the points, generating the original distance matrix. simulate incomplete data and noise interference, we introduced different missing rates

---

MetricEmbeddling Accelerate Metric Nearness by Tropical Inner Product
cal operations enable it to adaptively capture higher-order interactions, making it well-suited for dynamic tasks such as multi-source data alignment, recommendation systems, and metric learning.
Table 2. MetricEmmbeddlngg Performance Across Different Distance Matrices
Distance Matrix
Number of Points
Error ( (%)
Euclidean
100 points
2.49%
Oniino Update Capobility, Evtor
Fuclidean
1000 points
2.61 %
I+: one Nato
Manhattan
100 points
3.76%
Manhattan
1000 points
3.81%
Hamming
100 points
8.88%
Hamming
1000 points 9.05%
Cosine similarity
100 points
8.89%
Cosine similarity
1000 points
9.33%
Shortest-path
100 points
6.13%
Shortest-path
1000 points
2.42%
Figure 3. Online Update Capability; Error Rate at Various Update
was trained to predict distance matrices using embeddings of size = 3. are summarized in the following table: These results demonstrate that MetricEmbeddinng efficiently generates accurate embeddings for large and diverse dis- tance matrices, significantly reducing the computational cost of storing and querying distances. With space com- plexity of ((Nk), where N is the number of points and k is the embedding dimension, MetricEmbeddding outper- forms traditional methods that require O(N2) storage. The model's ability to reconstruct the full distance matrix with only O(N2k) complexity makes it highly scalable for large datasets. These characteristics make MetricEmbedding an ideal solution for applications like clustering and recommen- dation systems, where fast and scalable distance computa- tions are crucial.
Percentages
4.5. Effeec of Model Parameters and Latent Dimension (k) on Prediction Performance
We investigated the impact of model complexity, focusing on the latent dimension (k) and the number of layers (D) in the MetricEmbeddding model. We evaluate the model perfor- mance using the normalized mean squared error (NMSE). Increasing k improves model performance, as seen in the reduction of error from 95.2 95.28% to 88.33% when & increases from 3 to 10. Moreover, increasing the model depth (D) en- hances expressiveness, with error decreasing from 95.28% to 76.31 % as the number of layers increases from 1 to 3. These results demonstrate a trade-off between model com- plexity and accuracy, where higher k and deeper models lead to better performance but with increased computational costs. Despite this, MetricEmbeddingg maintains strong scal- ability, effectively handling high-dimensions data and com- plex relationships, making it suitable for real-time and large- scale applications.Detaile result in Appendix D.
4.7. Graph Contrastive Learning with MetricPlug
To evaluate the effectiveness of the MetricPlug method pro- posed in Section 3.3, we conducted an experiment based on graph contrastive learning- an unsupervised framework that learns node representations using contrastive loss. Specifi- cally, we used the approach from GRACE (Zhu et al., 2020), which involves perturbing edges to generate augmented views. Unlike traditional methods that use cosine or Fu- clidean similarity metrics, we replaced them with Metric- Plug, which uses the tropical inner product to calculate node pair similarity. The evaluation task focuses on node classification.
4.6. MetricEmmeddding for Distance Embedding
We assess MetricEmbeddding' ability to generate distance embeddings, crucial for applications like clustering and recommendation systems. Unlike MDS(Carroll & Arabic, 1998) and PCA(Abdi & Williams, 2010), our method en- sures that the recovered embeddings still satisfy the triangle inequality and maintain the properties of a metric. How- ever, we do not directly compare with these methods. In- stead, we conduct tests on datasets with different types of distance metrics, including Manhattan(Malkauttanr
We used the Cora dataset, which contains 2708 nodes, and followed the standard data split used in GCN (Kipf & Welling, 2017). We compared our MetricPlug method with existing methods based on cosine, Hamming, Euclidean, and Manhattan distances.
1980), 2013), Cosine similarity(Li & Han, 2013)and shortest-patt (SP) distances(Potamias et al., 2009), to demonstrate the robustness and versatility of our approach. The results of the experiments, where the model
We utilized the aropout_adj function in PyG to ran- domly perturb edges with a perturbation ratio of 0.1 to generate augmented views. The configuration used a learn-
8

---

MetricEmbeddingg Accelerate Metric Nearness by Tropical Inner Product
ing rate of 0.01, 1000 epochs, with hidden and projection dimensions set to 64. Accuracy was the evaluation metric. The results are summarized in the table below:
for large-scale tasks, overcoming many of the limitations of previous methods.
Beyond the foundational approaches, other aspects of the metric repair problem have also received considerable atten- tion. Gilbert and Jain (Gilbert & Jain, 2017) introduced the sparse metric repair problem, proposing several algorithms to enforce metric consistency with minimal modifications. Fan et al. (Fan et al., 2020) extended this framework to graph structures and proposed model for generalized met- ric repair that is suitable for settings with partially observed or incomplete data. Fan, Raichel, and Van Buskirk (Fan et al., 2018) proved that the increase-only and general vari- ants of the Metric Violation Distance (MVD) problem are NP-complete, and developed approximation algorithms for these cases. Additionally, from a fitting perspective, Cohen- Addad et al. (Cohen-Addad et al., 2022) studied how to approximate arbitrary distance data using tree-metric struc- tures, and proposed algorithms with constant-facton guar- antees, applicable in clustering and phylogenetic analysis. In addition, Laub et al. (Schölkopf et al., 2007) showed through psychophysical experiments that human similarity judgments often violate metric properties, suggesting that non-metricity in real-world data may stem from perceptual cognitive limitations.
Table Comparison of different similarity metries on the Cora dataset. MetriePlug achieves the best performance.
Method
Validation Acc(% (
Test Acc( %))
Cosine
77.4
76.5
Manhattan
79.0
79.2
Euclidean
78.2
79.0
Hamming
78.8
79.0
MMerricPuug
79.2
79.4
As shown in the table 3, the MetricPlug outperforms other distance-based methods, achieving the best results on both validation and test sets.
5. Related work
The Metric Nearness Problem aims to find a distance matrix that satisfies metric constraints while minimizing distortion from a dissimilarity matrix(Sra et al., 2004). A naive ap- proach uses QP, LP, or convex programming. but its high computational cost makes it impractical for large-scale prob- lems. Exploiting triangle inequalities is key to improving ef- ficiency.Sra et al. improved this by introducing the Triangle- Fixing (TF) algorithm, which has Onz²) complexity, but it still faced scalability issues (Sra et al., 2004). Brickell et al. extended this work with Bregman projections, enhancing convergence properties, yet their iterative process remained computationally expensive(Briikell et al., 2008).
6. Conclusion
In this paper, we address the Metric Nearness Problem by introducing a novel theoretical framework that connects trop- ical inner products with metric matrices. The TA-metric rep- resentation theorem reveals that tropical inner products can represent matrices satisfying the triangle inequality. Based on this, we propose MetricEmbedddigg, network archi- tecture that efficiently predicts metric matrices, offering improvements in computational efficiency, scalability, and real-time prediction. Experimental results demonstrate that our method achieves up to 60x speedup over -tate-of-the-art approaches, while handling larger matrices with lower mem- ory usage. In addition, we propose MetricPlug, a tropical inner product- based method for efficiently computing dis- tance matrices that satisfy metric properties while capturing complex relationships beyond traditional metrics. Its effec- tiveness validated through experiments within a graph contrastive learning framework.
Sonthalia and Gilbert's Project and Forget (PAF) algo- rithm(Sonthalia & Gilbert, 2022) offered linear convergence and a more dynamic approach to handling constraints, but it remains limited by the need for fixed input formats and struggles with real-time updates. Other methods, such as DeepNorm(Pitis et al., 2020), apply neural networks to map noisy matrices to valid distance matrices. While these ap- proaches offer greater flexibility, they depend heavily on the quality of input data and still face challenges in terms of scalability. Additionally, isometrically embeddable matrices combined with the HLWB projection algorithm([.i et al., 2023) have improved scalability and convergence. However, these methods still face challenges in handling large-scale data and require significant computational resources, mak- ing them less effective in real-world complex scenarios.
A Acknowledgement
This work was supported in part by the National Key Research and Development Program of China (No. 2024YDLN0005). W. Wang was supported by Guang- dong Provincial Key Lab of Integrated Communica- tion, Sensing and Computation for Ubiquitous Intemet of Things (No.202381212100077, A032023003100934)
Our approach, MebricEmbedding, leverages tropical algebra to ensure that metric properties are preserved while improv- ing computational efficiency. By eliminating the need for complex projections and enabling real-time updates, Met- ricEmdedding provides a more scalable and flexible solution
9

---

MetricEmbeddingg Accelerate Metric Nearness by Tropical Inner Product
Guangzhou Municipal Science and Technology Project (No. 2023A0310003, 2023A03J0113 and 2024A03J0621), In addition, we thank Dr Linshan Jiang's comment and help on this work.
Cuninghame-Greeen, R. A. Minimax algebra, volume 166.
Springer Science & Business Media, 2012.
Cybenko, G. Approximation by superpositions of a sig- moidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Impact Statement
Danielsson, P.-E. Euclidean distance mapping. Computer Graphics and image processing, 14(3):227-248, 1980.
Our research introduces a novel theoretical and compu- tational framework based on the tropical inner product, opening avenues for metric learning. The proposed MetricFmbedding architecture demonstrates strong perfor- mance in scalability, efficiency, and real-time prediction, with broad application prospects. Meanwhile, the Metric- Plug method shows promise in advancing contrastive and metric learning. Besides, we do not think ourwork will have bad impact on ethical aspects and futuresocietal conse- quences.
Elkan, C. Using the triangle inequality accelerate k- means. In Proceedings of the 20th international con- ference on Machine Learning (ICML-03), pp. 147-153, 2003.
Fan, C., Raichel, B., and Buskirk, G. V. Metric viola- tion distance: Hardness and approximation. Algorith- mica, 84: 1441 1465, 2018. URL https://api. semanticschole org http://oopsSI:::11ee00
References
Fan, C., Gilbert, A. C., Raichel, B., Sonthalia, R., and Van Buskirk, G. Generalized Metric Repair on Graphs. In Albers, S. (cd.). 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), volume 162 of Leibniz International Proceedings in Informatics (LIPles), pp. 25:1-
Abdi, H. and Williams, J. Principal component analysis. Wiley interdisciplinary reviews: computational statistics, 2(4))433-44) 459, 2010.
Bertinetto, L., Valmadre, J., Henriques, J. F., Vedaldi, A., and Torr, P. H. Fully-convolutional siamese networks for object tracking. In Computer Vision-ECCV 2016
25:22, Dagstuhl, Germany, 2020. Schloss Dagstuhl Leibniz-Zentrun für Informatik. ISBN 978-3-95977- 150-4. doi: 10.2200LIPII.SSSAT222222222
Workshops: Amsterdam, The Netherlands, October 8-10
URL
and 15-16, 2016, Proceedings, Part II 14, pp. 850-865. Springer, 2016.
https://orrgs..aassthh...eeeeeee wwtp::hhh..eeeeeeeeeeeeeeeee www.dd/e/eniiiieeeeee document /10. 4230 LIPICS. SWAT 2020.22
Brickell, J., Dhillon, I. S., Sra, S., and Tropp. J. A. The met- ric nearness problem. SIAM Journal on Matrix Analysis and Applications, 30(1):375-30) -37657--,,220 2008.
Gilbert, A. C. and Jain, If ain't broke, don't 't fix it: Sparse metric repair. In 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 612-619, 2017. doi: 10.1109/ALLERTON 2017.8262793.
Carroll, J. D. and Arabie, P. Multidimensional scaling. Measurement, judgment and decision making, pp. 179- 250, 1998.
Guillon, P., Izhakian, Z., Mairesse, J., and Merlet, G. The ultimate rank of tropical matrices. Journal of Algebra, 437:222-248, 2015.
Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual rep- resentations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Hartigan, J. A., Wong, M. A., et al. A k-means clustering algorithm. Applied statistics, 28(1):100-108, 1979.
Cohen-Addad, V., Das, D., Kipouridis, E., Parotsidis, N., and Thorup, M. Fitting distances by tree metrics min- imizing the total eттоr within a constant factor. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 668-479, 2022. doi: 10.1 109/0OCS52999 2000444
Hussain, L. Detecting epileptic seizure with different fea- ture extracting strategies using robust machine learning classification techniques by applying advance parameter optimization approach. Cognitive neurodynamics, 12(3): 271-294, 2018
Indyk. P. Sublinear time algorithms for metric space prob- lems. In Proceedings of the thirty-first annual ACM sym- posium on Theory of computing, pp. 428-434, 1999.
Cover, T. and Hart, P. Nearest neighbor pattern classifi- cation. IEEE Trans. Inf. Theor, 13(1):21-22 Septem- ber 2006. ISSN 0018-9448. doi: 10.1109/TTT.1967. 1053964. URL https: ot0.....//000..1///1
Jain, A. K. and Dubes, R. C. Algorithms for clustering data. Prentice-Hall Hall, Inc., 1988.
1967. 1643964.
10

---

MetricEmbeddingg Accelerate Metric Nearness by Tropical Inner Product
Jain, A. K., Murty, M. N., and Flynn, P. J. Data
Peterson, L. E. K-nearest neighbor. Scholarpedia, 4(2): 1883, 2009.
clustering: review. ACM Comput. Surv, 31(3): 264-323, September 1999. ISSN 0360-0300.
doi:
10.1145/331499.3315000 URL https: /tt...ro////oooooo 10. 10.11455/334999.3155444
Piao, G. and Breslin, J. G. Mcasuring semantic distance for linked open data-enabled recommender systems. In Pro- ceedings of the 31 Annual ACM Symposium on Applied Computing, pp. 315-320, 2016.
Joswig, M. Essentials of tropical combinatorics, volume 219. American Mathematical Society, 2021.
Pitis. S., Chan, H., Jamali, K., and Ba, J. An inductive bias for distances: Neural nets that respect the triangle inequality, arXiv preprint arXIv:2002.058255 2020.
Kaya, M. and Bilge, H. S. Deep metric learning: survey. Symmetry, 1 11(9): 1066, 2019.
Potamias, M., Bonchi, F., Castillo, C., and Gionis, A. Fast shortest path distance estimation large networks. In Pruceedings of the 18th ACM conference on Information and knowledge management, pp. 867-876, 2009.
Khosla, P., Teterwak, P., Wang, C., Samaa, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. Supervised contrastive learning. Advances in neural information processing systems, 33: 1 8661-18673, 2020.
Randic, M., Kleiner, A. F. and De Alba, L. M. Dis- tance/distance matrixes. Journal of chemical information and computer sciences, 34(2):277-286, 1994.
Kipf. T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2017.
Roth, V., Laub, J., Müller, K.-R., and Buhmann, J. Going metric: Denoising pairwise data. Advances in Neural Information Processing Systems, 15, 2002.
Li, B. and Han, L. Distance weighted cosine similarity measure for text classification. In Intelligent Data Engi- neering and Automated Learning- -DEALL 2013: 14th In- ternational Conference, IDEAL 2013, Hefei, China, Octo- ber 20-23. 2013. Proceedings 14, pp. 611-618. Springer, 2013.
Russell, S.J. and Norvig, P. P.Attfficall intelligence: modern approach. Pearson, 2016.
Schroff, F., Kalenichenko, D., and Philbin, Facenet:
Li, W.. Yu, F., and Ma, Z. Metric nearness made practi- cal. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 8648-8656, 2023.
unified embedding for face recognition and clustering. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 815-823, 2015.
Lü, L.,, Medo, M., Yeung, C. H., Zhang, Y.-C., Zhang, Z.-K., and Zhou, T. Recommender systems. Physics reports, 519(1):1-49) 2012.
Schölkopf, B., Platt, J., and Hofmann, T. Inducing Metric Violations in Human Similarity Judgements, pp. 777-784. 2007.
Luo, Y. and Fan, S. Min-max-plus neural networks. arXiv preprint 1 2021.
Shitov, Y. The complexity tropical matrix factorization.
Advances in Mathematics, 254:138-156, 2014.
Sonthalia, R. and Gilbert, A. C. Project and forget: Solv- ing large-scale metric constrained problems. Journal of Machine Learning Research, 23(326): 2022.
Malkauthekar, M. Analysis of euclidean distance and man- hattan distance measure in face recognition. In Third International Conference Computational Intelligence and Information Technology (CHT 2013), pp. 503-507. IET, 2013.
Sra, S., Tropp. J., and Dhillon, I. Triangle fixing algorithms for the metric nearness problem. Advances in Neural Information Processing Systems, 17, 2004.
Maragos, P., Charisopoulos, V., and Theodosis, E. Tropical geometry and machine learning. Proceedings of the IEEF, 109(5):728-755 2021.
Yu, F. Bao, R., Mao, J., and Li, W. Highly-efficient robinson-foo foulds distance estimation with matrix correc- tion. In ECAI 2023, pp. 2914-2921, IOS Press, 2023.
Maslov, V. P. On a new superposition principle for opti- mization problem. Séminaire Équations aux dérivées par- tielles ( (Polytechnique) dit aussi" Séminaire Goulaouic- Schwartz", , pp. 1-14, 1985.
Zhu, Y., Xu, Y., Yu, F., Liu, Q.. Wu, S., and Wang. L. Deep Graph Contrastive Representation Learning. In ICML Workshop Graph Representation Learning and Be- yond, 2020. URL http: : / /arxiv. www./bgg/////eoooeo...oeeee a006 04131.
Park, H.-S. and Jun, C.-H. A simple and fast algorithm for k-medoids clustering. Expert systems with applications, 36(2):333-3344 2009. 2009.

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
A. Hierarchical Graph and Tropical Inner Product
A.1. three levels graph and Tropical Inner Product
Consider graph divided into three levels:
Vi is the first set of nodes in the graph,
1/2 is the second set of nodes in the graph,
3/3 is the third set of nodes in the graph.
We have two matrices:
Matrix 1: Represents the edge weights from V to V2, where the element E denotes the edge weight from node E Vi node j E V2,
Matrix 2: Represents the edge weights from V2 to V3, where the element Eg denotes the edge weight from node E V/ to node j E V3.
If we perform the tropical inner product of Matrix and Matrix 2, i.c.
C1 E1 max E2, C2 = E1 Omin E2
then C1 and C2 are new matrices that represent the paths from nodes in V11 to nodes in V3. Specifically, each element Ci in matrix C represents the path weight from node i E V1 to node E Vg. where C₁ corresponds to the maximum path weight (using the max operation) and C2 corresponds to the shortest path weight (using the min operation).
A.2. Multi-layer Graph Extension
Consider graph consisting of multiple layers, where each layer's node set represented as V1, V2, Va,..., VR. Each matrix represents the edge weights from one layer to the next:
Matrix 1: Represents the edge weights from Vi to V2,
Matrix 2: Represents the edge weights from 1/2 to V3,
Matrix (k-1): Represents the edge weights from Vg-1 to Vj-
Assume we have k layers, corresponding to matrices E,, E2,.... Ex-1. By performing consecutive tropical inner products, we can compute the path information from V1 to V/.
First, we perform the tropical inner product between Ej and Eg to obtain a new matrix C1:
C Omin E2
Each element Cıÿ in matrix C1 represents the minimum path weight from node E Vi node E V3- Next, we perform the tropical inner product between Ci and Eg, obtaining matrix C2:
C2 = C1 O Es
Each element C.y in matrix C2 represents the minimum path weight from node E V12 node j E V4. By continuing this process, we multiply matrix C2 by E₁ obtain matrix O3:
C C2 O Ea
This process is repeated until all layers have been considered. The final matrix Ct-1 will contain the path information from V1 to Va.
Each element Ciy in matrix Cj represents the minimum path weight from node E V1 to node j E The same applies for the maximum path weight when the tropical inner product defined based on the max-plus operation.
12

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
B. Additional Proofs and Theoretical Framework
Theorem I: matrix A E IR N satisfies the triangle inequality, and matrix B E RR XN satisfies the triangle inequality, then the matrix C' A + B NNxN also satisfies the triangle inequality.
Proof: For any indices i, k, since A and B satisfy the triangle inequality, have:
Aij + Asu 2 Ask
Bij Byr Z Bik-
Adding these inequalities:
Ag + Ass Bug + Byg Aux Bik-
This implies:
Cij + Cys 2 Cik-
Thus, A B satisfies the triangle inequality.
Theorem 2: If A metric matrix, then for any positive constant a, aA also a metric matrix.
Proof: Since A satisfies the triangle inequality Ask + Auj Aij. multiplying both sides by 0 preserves the inequality:
aAs + aAAs 2 aAg.
Thus, aA satisfies the triangle inequality, is symmetric, and has diagonal elements equal to zero. Hence, aA is metric matrix.
Theorem 3: If a matrix A satisfies the triangle inequality, then the matrix + AT = B, and after setting the diagonal elements of to 0, the resulting matrix satisfies the metric properties.
Proof: By Theorem 1, A + A satisfies the triangle inequality and is symmetric. Setting its diagonal elements 0 preserves the triangle inequality, and the matrix remains symmetric. Thus, the modified matrix B satisfies the conditions for metric matrix.
thus, we just need to care the relationship between tropical algebra and triangle inequality.
Theorem 4: If A and B are both N x N metric matrices, then the element-wise maximum of A and B, denoted as max(A, B), is also a metric matrix.
Proof: Suppose A and B are metric matrices, meaning that for all i, k. we have:
Ask + Arj 2 Asj.
Bu + Buj 2 Bij.
Let C max(A, B). For any i, k, we have:
Cak + Ckj max(AAu> Bik)) + max(Akz: Buj).
By the properties of the maximum function, this implies:
Cak + Ckj 2 max( AA + Akj, Bik + BBy) 2 max(Aij, Biy).
Hence, Cik + Ckj 2 Cij. proving that C' is a metric matrix.
generalization of Theorem 5: Let A N and B KR be non-negative matrices, and let C A @max B. For any i E (1,...NN.AA N).
(l...., min mNn..., M)}, and j E {1,..., M, M). we have:
Cak + Ckj 2 Cij-
This inequality defines the tropical triangle inequality for matrices. Specifically, when N M, this becomes the tropical triangle inequality for square matrices.
Proof: By definition, Cj (Air + Brÿ). Assume that when r = equality holds, i.e., Ci Ais + Baj- Then:
Ais < Ais + Bas S Cik max (Aix(Air + Bra).
13

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
and
Baj S Ass + Baj S Ckj max(Akr + Brz)-
Thus, we have:
Ciyy S Cik + Ckj-
Therefore, the tropical inner product satisfies the tropical triangle inequality.
Theorem 6: Let A be non-negative matrix size x K. Define B A max A the tropical inner product of A with its transpose. Let Boff be the matrix obtained by setting the diagonal elements of B zero. Then, B is metric matrix.
Proof: From Theorem 5, we know that A Omax A satisfies the triangle inequality. Now, we will prove that B is symmetric and satisfies the properties of metric matrix.
Symmetry: For any j, we have:
Bi = max(Ais + +.7) = max(Aix + Aba))
By max (Axt
Afi) max (Ajz ) Axx)
so Bij = By:. Therefore, B is symmetric.
2. diagonal elements: Since Bolf is obtained by setting the diagonal elements of B zero, it follows that:
D
0 for all i.
Therefore, Boft is symmetric matrix with zero diagonal elements and satisfies the properties of metric matrix.
Theorem 7: Let A E NN and B E Rx M be non-negative matrices, where k > N * M. Then, there exist matrices A' E Nik' xk' and B' E Ik''N, xN with k < N * M, such that:
A' @max B' = A mmxx B.
Proof: Consider the matrix C' = A mmax B, where C' E N The (i,j)-th element of C' is given by:
Cij max Asx + Bkz).
Let (k) denote the index set for which the equality Cū Au + Buj holds. Since the maximum is taken over k, the set {k} can contain at most N M distinct indices, there at most N M possible unique combinations of rows of A and columns of B.
Thus, we can construct new matrices A' and B' by retaining only the corresponding k-th columns A and the k-th rows of B, respectively. Specifically, A' E R xx and E I2* xM are defined by selecting the relevant columns and rows corresponding to the set (k), where < N M. By this construction, it follows that:
A' Omax B' A Omax B,
proving the result.
Theorem 8: max-TA-metric Representation Theorem
Let Ω denote the set of all matrices produced by tropical inner products of non-negative matrices:
Ω = M M (X Omaz Y''joo X, Y E R xxX
R20
where (X Oman YT bij max (x j.
Let V C R20
N be the set of matrices D satisfying:
D 0 Vi (1, 2, ....,N.. N).
14

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Di S mink +
dk mink
D Vi,j E (1,2,...,,)) N..
Then, Ω = w. The set of matrices generated via the tropical inner product (with diagonals removed) from non non-negative matrices constitutes a specific subset of the set of non-negative matrices with zero diagonals that satisfy the triangle inequality.
Proof:
1. For any M& S2there exist non-negative matrices X, Y R such that:
Mij = max (Xi Yx)) for i i Ma = O. &
For the case where i = j. we have M, = O, and
My S min Mi,, + min M
ki
For the other chooe, some k such that:
Mi = X + Yzk-
For any p.q E {l...., n with # and q # j. we have:
N Yg Mig.
Xpk + Ysk. I Mpj.
Adding the two inequalities gives:
Mig + Mpj Z Xik + Yju Mij.
Thus, for any P.q E (1....,m) n) with p # and q * j. follows that
min Mip + min Mai 2 Mij- psz
Therefore, we conclude that M E V.
2. For any matrix M V, we provide a constructive proof in the appendix, showing that there exist matrices X, Y Nxx² such that: 20
M (X Omax o)
For any and j. we can construct two matrices X and Y such that:
t(i.j) = N - 1)+ Xa(i) + Y)(())) = Mij-
To ensure Múj Xata,) + Yusa, we further require that for any A + i, we have Xk.((.)) 0, and for any A + have (i.((s))= 0. Additionally, we need to ensure the following inequalities:
vk jj.
Xasa) Mik.
Vk #i
(gslt.)) Maj-
Since M satisfies the inequality
min Man + min Mras 2 My, kidt b2ff
conclude that such matrices Y and Z exist.
Specifically, we set:
X min(min MR Ma.)) 2 0, Y)(()) Mi, Xi 2 0.
kij
15

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Thus, find matrices X and Y such that M (X Qmax yT and we conclude that:
MEΩ
Conclusion: Thus, Q 4
Theorem Lemin-TA-metrie Representation Theorem Let Q be the set of all results of the min-tropical inner product (using max-plus operation) of two non-negative matrices (excluding the diagonal elements), and let d be the set of all non-negative matrices that satisfy the triangle inequality (excluding the diagonal elements). Then, & C Z.
Firstly, the min- propial Inner Product of Two Non-negative Matrices Does Not Satisfy the Triangle Inequality:
Consider the non-negative matrices A and B:
0.1
0.9
0.5
0
0
0.9
0
0
0.1
1
0
0
0.5
When Ask Bus O, show that the tropical inner product may not satisfy the triangle inequality. Consider the following terms:
For some values of A and B, we have:
C12 + C23 < C13.
Thus, the tropical inner product Omin does not always satisfy the triangle inequality in this case. general, the relation
min(A, + Brx) + min(A ( + B,j) ž mA.. + Brj)
shows that the triangle inequality does not hold universally for the min- pron-tro inner product.
Next, Consider a Metric Matrix C' E t:
Now, for matrix C belonging to the set C which satisfies the triangle inequality, we have the following important results:
A minn A A
Proof:
For any i.j. k. by the metric properties of A, we know that:
Ask + Aus 2 Ais-
Thus, for any k. the following holds:
min(As + Auj) 2 Aij.
Furthermore, when & = i, utilizing the property A;; = we obtain:
min(As + Akr) = Auj.
k
Therefore, we conclude:
A Oiin = A.
Additionally, if A is a symmetric matrix (AT A), we also have:
A @min AT = A.
This result shows that the min-tropical inner product of a matrix with itself yields the original matrix, and the symmetry of the matrix further confirms the consistency of the operation under the min-tropical product. This property holds for all metric matrices in B, meaning that the min-tropical inner product preserves the structure metric matrices that satisfy the triangle inequality.
Conclusion:
16

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Theorem 10: The tropical inner product of metric matrix with itself satisfies the triangle inequality.
Proof: When using the min-sum operation, shown in Theorem 9, the tropical inner product of matrix with itself yields the matrix itself, which naturally satisfies the triangle inequality.
When using the max-sum operation, the tropical inner product of two non-negative matrices satisfies the triangle inequality. However, the diagonal elements of the resulting matrix may not necessarily be zero, but the matrix still satisfies the triangle inequality.
Theorem 11 Let A be non-negative matrix of dimension m and be non-negative matrix of dimension p. Define the following operation for any i.
dy min A min Baj:
where the minimum is taken over index 8, i.e., for each pair j, we compute the minimum value of Ais for all 8 (with 8 E {1.2...., n.), and similarly for Bay (with s E (1,2..... n.))
Then, for any j, k, we have the following inequality:
dik + dej 2 dij.
Proof: By the definition of dey, we have:
di = min(Ais) + min B.j).
Now, consider du + daz:
di + daj = min(Ais) + min(Bax) + min(Aus) + min (Ba)).
By the non-negativity of the matrices A and B, we have:
du daj 2 min(A() min(Baj) dej-
Thus, the triangle inequality holds, proving the result.
Theorem 12:
Let A be non-negative matrix of dimension n, B be non-negative matrix of dimension x p, and O be matrix of appropriate dimension. Then, the operation A @min O Omin B satisfies the triangle inequality.
Proof: By definition, we have:
Cjj min (Ai,s + 0 B,2,k) min(Ais) min mmin(Bxs)) Bxx)- s1,82
This relation satisfies the conditions for the triangle inequality. We can further prove it using layered graph method.
Theorem 13:
Let G(E, V) an undirected graph with the following properties:
There are negative-weight cycles,
There are no self-loops,
All edge weights are non-negative
There is at most one edge between any two nodes,
The graph is connected, i.c., there exists at least one path between any pair of nodes.
Let A be the adjacency matrix of G, defined as follows:
if j.
Aii, ýl
Giiji
if there is edge between and
Oc
otherwise.
17

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Now, define the recurrence relation for A
A = A Omin A
where Omin denotes the min-tropical matrix multiplication(iinsum sumi. Then, under tropical matrix multiplication, the matrix A AN-1 (the matrix obtained after applying tropical matrix multiplication N - 2 times) satisfies the triangle inequality. In particular, A represents the shortest path distance matrix for the graph G.
Proof
As shown in A.2 before, The tropical minimum operation (min-sum) computes the shortest path and weight sum between N points the left and N points on the right. The matrix A,, represents the shortest path weight sum between points and through at most k edges. Since the graph G has N nodes, the shortest path between any two points will not exceed N edges. Therefore, A ji gives the shortest path distance matrix for the graph.
jl
For an undirected graph, the shortest path distances naturally satisfy the triangle inequality, making the matrix metric matrix. For directed graph, this can ensured by taking A AN-1,, + (AN-1)², which satisfies the metric properties.
where Omin denotes the min-tropical matrix multiplication (min-sum). Then, under tropical matrix multiplication, the matrix AN-1 (the matrix obtained after applying tropical matrix multiplication N - 2 times) satisfies the triangle inequality. In particular, A represents the shortest path distance matrix for the graph G.
By combining this theorem, we can further accelerate the algorithm for the complete graph. By combining tropical matrix decomposition techniques, we are able to achieve an O(KN2, approximation algorithm. That is, for a complete matrix A of dimension x N, we approximate as B BT, where B is of dimension x K and K is a constant much smaller than N. Specifically, it can be written as
(B Omin B²y (B" Omin By
By using the fast exponentiation algorithm, the computation can be performed in O log N). while the N x KKKK K matrix has a complexity of ONN*², and the N @ K x N has complexity of O(N2k). Therefore, the overall computational complexity is O(kN2).
Theorem 14: Any non-negative real matrix, under the tropical inner product (either the min or max operation), will satisfy the triangle inequality after a finite number of powers.
Proof: In the case of the Omin operation, by Theorem 11, it is known that the matrix will satisfy the triangle inequality after at most N - powers. This is because the shortest path between any two nodes in a graph with N nodes cannot exceed N edges, as discussed in the proof of Theorem 1. Hence, after most N powers, the matrix will represent the shortest path distances and satisfy the triangle inequality.
In the case of the @maz operation, described in Theorem 5, the tropical inner product of two non nen-negative matrices automatically satisfies the triangle inequality. Therefore, under the Omax operation, the tropical inner product of any two matrices satisfies the triangle inequality.
Thus, regardless of whether the operation is Omin or @max a finite number powers (at most N - 1) will yield a matrix that satisfies the triangle inequality. By making a slight adjustment, this matrix can further be made to satisfy the properties of metric matrix.
18

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
C. Supplementary Details on Metric Embedding
Table 4. Comparison of Computational Complexity, Scalability, and Execution Platform
Method
Time Complexity
Space Complexity
Scalability
DeepNorm
Suitable for small-scale problems, runs on GPU Suitable for small-scale problems, runs on CPU Limited to small datasets, runs on CPU Suitable for medium-scale data, Highly scalable, supports real-time updates, run GPU
TRF Algorithm
(nn)
(
PAF Algorithm
(nn))
(
HLWB Algorithm
O(n))
(n
CPU
Tropical (Normal)
O(n-k)
(n
C.1. Method Analysis
Leveraging tropical algebra, MetricEmbeddingg ensures the learned matrix adheres fundamental metric properties, such as the triangle inequality. Unlike methods like HLWB projections (Li et al., 2023), which rely linear constraints complex projections, MetricEmbeddingg's tropical operations inherently preserve these properties. This guarantees the correctness and robustness of the solution. In contrast, methods like TRF(Brickell et al.. 2008) may violate metric properties during optimization, as they do not maintain metric consistency throughout the process.
As shown in Table 4, The tropical algebra operations MetricNN provide significant computational efficiency, even for large matrices, addressing the limitations of traditional approaches like the TRF (Brickell al., 2008), which exhibits Onn)) space complexity. MebricEmbedding reduces memory cost Onn²), making it highly scalable and efficient for large-scale datasets. Additionally, its support for minibatch processing and dynamic point-pai weight updates ensures that it can handle large matrices with high fffciency-feeturee that many existing methods, such as PAF (Sonthalia & Gilbert, 2022), cannot accommodate due to their reliance on fixed input formats and limited parallelization.
C.2. Minibatch-Basel Metric Embedding
Here, we present a minibatch-based implementation of MetricEmbeddding As shown in algorithm2,.copprrd to the standard MebricEmbedding, the main modification is the integration of minibatch processing into the model, allowing it to overcome the limitation of storing O(N2) pairwise values. This enables the method to handle larger-scale data, with the minimum space complexity reduced to O(Nk).
19

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Algorithm 2 Minibatch Training Procedure for MetricEmbeddding
Input: Target matrix D, batch size B, AdamW optimizer, threshold
Output: Optimized weight matrices Wo, Wi...., Wa Optimized bias vectors bi b1...-, bd
Final output matrix approximation from minibatches Initialize:
Initialize weight matrices Wo. Wi,..., Wa with Gaussian distribution.
Initialize bias vectors bı,-..,b by randomly.
Split D into minibatches, each containing randomly sampled point pairs (i,j).
Training Loop:
while Convergence criteria not met do for each minibatch B containing pairs (i,j) do
Forward Pass:
Extract relevant rows o6 W for batch processing.
Initialize the output for batch: Ag" ( w w(
for layer .1..... Compute batch-wise embedding:
4 A maxx Wi b
A
1 O max Wi o b
end Loss Calculation:
Compute loss only for batch elements:
L= Σ [1 Omax (A Dis
(i.)EB
Backpropagation:
Compute gradients of L. with respect Wi and by using only batch data.
Parameter Update:
Use AdamW optimizer to update Wi and by based on computed gradients.
Regularization:
for layer I = 1..... do
Apply non-negativity constraints: Wi 0, by 0.
end end
Check for Convergence:
If L change between iterations is smaller than the threshold, break the loop.
end
20

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Table Comparison Space Complexity, Time Complexity, and Max Problem Note: Data for TRE, PAF, and HLWB were taken from the respective studies: (Li et al., 2023).
Algorithm
Largest Size (n)
CPLEX
300
MOSEK
< 300
(Rr(Brickell et al., 2008)
< 2, 000
PAF(Sonthalia & Gilbert, 2022)
~ 3, 000
DeepNorm(Pitss et al., 2020)
< 1,500
HLWB(Li et al., 2023)
10, 000
Tropical
> 100,000
D. Experiment
D.1. Comparison of Scalability with Existing Methods
We tested the scalability of our approach on a variety of problem sizes, and while the computing platforms were not identical, the results consistently highlight the superiority of our method. Specifically, compared to the TRF method (Brickell et al., 2008) and the PAF algorithm (Sonthalia & Gilbert, 2022). HLWB (Li et al., 2023) offers a lower space complexity of O(N3), enabling to handle matrices with over 10,000 points. However, HLWB's s time complexity remains a bottleneck, restricting its scalability larger datasets.
In contrast, method achieves both optimal space complexity (O(N2) and time complexity (O(N2k)), allowing it to efficiently scale to much larger matrices. Our approach can solve problems with sizes large as 100,000 points within 12 hours, demonstrating significant performance improvement over HLWB, which can only handle matrices up to 10,000 points. By adopting a minibatch-basee approach, our method can even handle data at the scale 10 10 Although optimization performance may be limited by the problem size, our method can at least provide a solution that strictly satisfies the triangle inequality.Thie This improvement underscores the scalability and efficiency of our approach, even for very large-scale problems that are common real-world applications.
Table 5 summarizes the comparison between our method and existing approaches. The empirical results clearly demonstrate the advantages of our approach, making it an ideal solution for large-scale metric optimization problems.
D.2. Online Update Capability
To validate the online update capability of MetricEmbeddingg incrementally fed new data into the model and evaluated the update speed and prediction accuracy by varying the percentage of point pairs used for updates (from 20% to 100%). To better emphasize the model's online learning ability, we specifically generated a new dataset with the following data generation strategy:
Data Distribution: A distance matrix with significant variation was generated by intentionally clustering most of the points in one region, while a few points were placed far from this region. This distribution ensures that there is a larger variation in distances between points, which increases the challenge the online learning task.
Data Generation Process:
The majority of points (50 points) are clustered around the coordinates (50, 50), with the distribution following standard normal distribution and a standard deviation of 5 to ensure they are concentrated near the center.
- few points (10 points) are distributed away from the clustered region (around coordinates (200, 200)), with their distribution also following a standard normal distribution and a standard deviation of 20, enhancing the distance differences between these points and the center.
Distance Matrix Calculation: The Euclidean distances between these points were computed, and a distance matrix was generated for use in subsequent experiments.
21

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Table 6. NMSE and Triangle Inequality Violation Ratio at different update percentages
Update (%)
NMSE
TIV Ratio
20
0.8832
30
0.8388
40
0.8028
50
0.7728
0
60
0.7476
0
70
0.7257
0
80
0.7058
0
90
0.6935
100
0.6773
By using this data generation strategy, we ensured that the distance differences between point pairs in the experiment were significant, which posed a greater challenge for the online learning task and tested the model's ability to adapt to varying levels of input data. The following table presents the normalized mean square error (NMSE) and the triangle inequality violation raVio(TIV Ratio) at different update percentages:
The table above presents the experimental results of the MetricEmmeedding model at various update percentages. focusing on two key performance metrics: Normalized Mean Square Error (NMSE) and Triangle Inequality Violation Ratio (TIV Ratio).
Normalized Mean Square Error (NMSE): The NMSE values progressively decrease as the update percentage increases. At the 20% update level, the NMSE is 0.8832, and it improves as more data is added. By the 100% update level, the NMSE reaches 0.6773, indicating that the model's performance improves as it adapts to more data. This trend shows that the model's ability to make accurate predictions increases with the number of updates, demonstrating its capacity to learn and adapt new data in an online learning setting.
Triangle Inequality Violation Ratio (TIV Ratio): Notably, the TTV Ratio remains at O for all update percentages. This indicates that the model consistently satisfies the triangle inequality throughout the updates, which is critical property for distance-basee models. The absence of violations suggests that the model is stable and maintains consistent mathematical properties even as new data is introduced.
The results validate the online update capability of the MetriiEmbe model. As the update percentage increases, the NMSE improves, showing the model's 'ss ability adapt new data while maintaining its geometric properties, evidenced by the consistent TIV Ratio. This demonstrates the model's stability and reliability in dynamic environments requiring real-time adaptation. Compared to traditional methods like HLWB(Li al., 2023), which often require full retraining with each new data batch, MetricEmbedding offers significant flexibility. While methods like HLWB are computationally expensive and tine-consuming, MetricEmbedding allows incremental updates, making it far more efficient and scalable for real-time applications. Its ability to adapt online without retraining makes ideal for dynamic tasks, such as online recommendations or real-time data analytics, where constant adaptation is crucial. MetricEmbedding outperforms traditional methods efficiency and adaptability for online learning tasks.
D.3. Effect of Model Parameters and Latent Dimension (k) on Prediction Performance
We conducted a preliminary investigation into how model complexity, specifically the number of layers (D) and the latent
dimension (k), affects the performance of the MetricEmbeddiing model. Here, represents the dimension of the predicted matrix A, which has a shape of N x k, where N the number of data points. The results show that as the model depth (D) and parameter dimensions (k) increase, the performance fluctuates. Specifically, for larger values of k (e.g., k 10), the model's s expressiveness improves, but at the cost of higher computational costs. On the other hand, reducing k (e.g. == 3) leads to a higher accuracy for smaller models, which suggests balance between model complexity and performance.
As shown table 7,despite the increased computational overhead, MetricEmbeddingg demonstrates superior scalability, handling complex, high-ding digh-diimnsional data more efficiently compared to traditional methods. This highlights the model's capacity to capture more non-linear relationships, making suitable for real-time applications and large-scale datasets.
22

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Table Impact model depth (D) and dimensionality (k) matrix on accuracy.
D (Depth)
(Dimension of A)
Error rate (%)
10
88.33
10
76.78
10
75.73
95.28
85.28
76.31
The edge weights used in the tests were generated as follows:
Wij [1000 X X e²
where u ~ (O, 1) is drawn from a uniform distribution and ~ (0, 1) is drawn from a normal distribution. These edge weights were then used as the measurement matrix D..
D.4. Metric Distance Matrix Embedding
We conducted tests on various metric distances, including Euclidean distance, Manhattan distance, cosine similarity, Hamming distance, and shortest-path (SP) distance. We tested with two different numbers of points, N = 100 and N = 1000, and generated corresponding distance matrices for each metric. The error rates for the different metrics are shown in Table2.
The results generally satisfactory, with all error rates consistently below 10%. Additionally, we randomly generated graph and modeled its shortest-por distance matrix, achieving minimal error rate of 2.42%.
These experimental results demonstrate that by optimizing the tropical inner product between two matrices, we can effectively represent distance matrices, making it feasible to use them in deep learning applications as a replacement for traditional Euclidean distance or other distance calculation methods. Moreover, SPdistance Embedding is a compression technique applied the SPdistance matrix using MetricEmbedding, which generates set of N matrices. This method has space complexity of (NN)), with indexing between two points requiring only O(k) complexity. Reconstructing the entire distance matrix for the graph takes O(N2 complexity. Compared to traditional compression algorithms, approach guarantees that the resulting matrix satisfies the triangle inequality. Furthermore, by applying matrix decomposition to the embedded matrices, we can significantly reduce storage costs.
Data Generation: The distance matrices used for testing were generated as follows:
Euclidean distance: A set of random points in 10-dimensional space was generated, and the Euclidean distance between each pair of points was computed. The Euclidean distance dg(x, y) is given by:
dg y) = Σ (x. y1)
where and are the vectors, and d is the dimensionality (in this case, 10).
Manhattan distance: Similar to the Euclidean case, but using the Manhattan (or LI) distance formula to compute the distances between pairs points. The Manhattan distance d (x, y) is defined as:
d y)
x
yal
Hamming distance: Random binary vectors of length 10 were generated. The Hamming distance dh (z,2))) v) between two binary vectors and is the number of positions which the corresponding elements different:
dh ( = Σ I Vil
mm1
23

---

MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
Cosine similarity distance: Random vectors were generated, and the cosine similarity between each pair of vectors computed. The cosine distance (x, y) is derived from the cosine similarity cos y) as:
do(z, = 1 2
Shortest-path distance: A random graph was generated using the Erdōs-Rényí model and edge probability of 0.1. To ensure the graph was connected, the generation process was repeated until connected graph was obtained. The graph was then used to compute the shortest path between all pairs of nodes using floyd algorithm.
24


Reviews:
[{"review_id": "K6h5SKUbpa", "reviewer": "Reviewer_eADx", "summary": "The authors propose the use of tropical algebra to frame the metric nearest problem within a continuous optimization framework. They first demonstrate that the set of non-negative matrices satisfying the triangle inequality can be fully represented using a combination of tropical algebraic representations. They then propose an MLP based on tropical algebraic operations, which they optimize using RMSprop to solve for the nearest valid metric distance matrix to the original matrix.\n\n## Post-Rebuttal update:\nHaving reviewed the authors' responses to both my own review as well as that of other reviewers, I retain my original rating and would be happy to recommend this work for acceptance to the main conference.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:but one can also easily optimize over multiple starting matrices A in parallel as another means of avoiding local minima.**\n\nA1:Thanks for your valuable suggestion. We conducted experiments using the proposed strategy with a single-layer model, and indeed observed further performance improvements over the baseline approach. \nIn our experiments, we constructed a set of non-metric matrices using the MNIST dataset, following the approach described in [1].\nWe fixed the number of model iterations to **1000**. Under this configuration:\nThe convergence error improved from 0.0583 to **0.0536**.\nThe improved model required **3.58 seconds**, compared to **0.97 seconds** for the original method.\nThis demonstrates a clear **trade-off between convergence quality and computational cost**.\n\n**Q2：I don't think I saw any evidence supporting the purported downstream task benefits of MetricPlug as proposed in section 3.3, specifically compared to existing approaches.**\n\nA2: We conducted additional experiments on real-world tasks to demonstrate the applicability of our approach, specifically MetricPlug as described in Section 3.3. \n\n- **Task Definition:**  \n We applied graph contrastive learning, an unsupervised method for learning node representations using contrastive loss. Specifically, we used the approach from GRACE [2], which involves perturbing edges to generate augmented views. Unlike traditional methods that use cosine or Euclidean similarity metrics, we replaced them with MetricPlug, which uses the tropical inner product to calculate node pair similarity, satisfying the triangle inequality. The evaluation task focuses on node classification.\n\n- **Dataset and Baseline:**  \n  We used the Cora dataset, which contains 2708 nodes, and follows the standard data split used in GCN [3]. We compared our MetricPlug method with existing methods based on cosine, Hamming, Euclidean, and Manhattan distances.\n\n- **Experiment Settings:**  \nWe utilized the dropout_adj function in PyG to randomly perturb edges with a perturbation ratio of 0.1 to generate augmented views. The configuration used a learning rate of 0.01, 1000 epochs, with hidden and projection dimensions set to 64. Accuracy was the evaluation metric. The results are summarized below:\n\n| Method     | Validation Accuracy (%) | Test Accuracy (%) |\n|------------|-------------------------|-------------------|\n| Cosine     | 77.4                    | 76.5              |\n| Manhattan  | 79.0                    | 79.2              |\n| Euclidean  | 78.2                    | 79.0              |\n| Hamming    | 78.8                    | 79.0              |\n| MetricPlug   | **79.2**                 | **79.4**          |\n\nAs shown in the table, the MetricPlug method outperforms other distance-based methods, achieving the best results on both validation and test sets.\n\n**Q3：Can the miniabatch-based algorithm in appendix C.2 guarantee the triangle inequality property at a global scale across all pairs i,j? Or only up to its maximum output shape?\nThe answer to the first question is **affirmative**.**\n\nOur proposed minibatch-based training method guarantees that, in any iteration, the model's predictions satisfy the triangle inequality for all index pairs \\( (i, j) \\). Specifically, as long as the two matrices involved in the final Tropical inner product are constrained to be non-negative, the resulting matrix—obtained via Tropical inner product—will satisfy the triangle inequality for any pair \\( (i, j) \\).\n\nAlthough the minibatch algorithm only updates a subset of the model's weights based on the current batch, we explicitly enforce non-negativity constraints on all model parameters throughout training. As a result, regardless of the update stage, the forward pass of the model will always produce a full matrix \\( H \\) whose entries satisfy the triangle inequality across all index pairs \\( (i, j) \\).\n\n**For example**, consider a \\(1000 \\times 1000\\) matrix with a batch size of 16. In a single iteration, the model only computes the values for those 16 selected positions and updates the weights based on the corresponding loss. However, since all weights remain non-negative due to the imposed constraints, the full \\(1000 \\times 1000\\) matrix outputted by the model at this point will still satisfy the triangle inequality for any pair \\( (i, j) \\). This property is guaranteed by **Theorem 6**.\n\nOther cases follow by the same reasoning.\n\n**Q4：Some of the math notation can be cleaned up a bit.**\n\nA4:Thank you very much for pointing out this issue. We will address and correct it in the subsequent version of the manuscript\n\n[1] Li W, et al. Metric nearness made practical. AAAI2023\n\n[2] Zhu, Y et al. Deep graph contrastive representation learning. ArXiv.  \n\n[3] Kipf, T. N et al. Semi-Supervised Classification with Graph Convolutional Networks. ICLR2016.", "claims_and_evidence": "- Optimizing through an MLP-like structure is preferable to directly optimizing over a single starting matrix and avoids local minima\n  - There are certainly scale-related benefits to using the MLP-like structure, specifically the mini-batch setup, but one can also easily optimize over multiple starting matrices A in parallel as another means of avoiding local minima.\n- I don't think I saw any evidence supporting the purported downstream task benefits of MetricPlug as proposed in section 3.3, specifically compared to existing approaches.", "methods_and_evaluation_criteria": "The proposed evaluation is sufficient for demonstrating the soundness of their technique. However I think what remains to be demonstrated is downstream task impact, as the authors claim existing methods may struggle to accurately capture complex relationships for contrastive learning setups.", "theoretical_claims": "I went through the theorems but did not carefully validate each proof.", "experimental_designs_or_analyses": "No issues in existing proposed experiments and analysis", "relation_to_broader_scientific_literature": "The authors compare against TRF and HLWB, which appear to be the most recent and likely state of the art solutions to the metric nearness problem. Unfortunately I am not intricately familiar with the prior literature on this topic, so I cannot comment on any other prior works.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n- Appears to be a theoretically sound and practical approach to the metric nearness problem -- specifically so at larger scales\n- Proposed solution is fairly simple to implement\nWeaknesses:\n- Claims of downstream task impact need to be validated", "other_comments_or_suggestions": "Some of the math notation can be cleaned up a bit. \n- For example, it's a bit confusing to have A be set of matrix pairs in theorem 8, while also representing individual matrices in other theorems.\n- X in L209 column 2 has not been previously defined\n- The font for superscripts and subscripts such as off, max, min, is inconsistent.", "questions_for_authors": "- Can the miniabatch-based algorithm in appendix C.2 guarantee the triangle inequality property at a global scale across all pairs i,j? Or only up to its maximum output shape?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n20nVGi0AL", "reviewer": "Reviewer_MWLk", "summary": "The paper introduces MetricEmbedding, a novel approach using the ropical inner product (max-plus operation) to efficiently solve the Metric Nearness Problem (MNP) while ensuring metric properties like the triangle inequality. The authors showed the equivalence (up to diagonal elements) between the class of non-negative distance matrices and the set of matrices resulting from the tropical inner product of non-negative matrices. Using this observation, the authors proposed  a continuous optimization task to efficiently solve the Metric Nearness Problem (MNP). The proposed method has been shown to significantly reduce computational complexity, achieving up to 1000× speed improvements over traditional approaches while scaling to large matrices (10^5 \\times 10^5) with lower memory usage. Experimental results demonstrate its effectiveness in restoring metric properties, handling noisy and incomplete data, on synthetic datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1：Please clarify whether the proposed training procedure for MetricEmbedding is guaranteed to achieve a plausible minimum and under which conditions.**\n\nA1：The short answer is **no**, because it is a **non-convex** optimization problem. Nevertheless, our algorithm is guaranteed to converge to a local minimum, as we solve the problem using a gradient descent approach.\n\nWe prove this by the following: \n\n(1) consider one layer case， \n$\n\\min_X \\| X \\odot_{\\max} X^T - Y \\|_F^2\n$\nLet:\n$\nA = [[1,3,3],[3,1,3][3,3,1]], \nB = [[3,1,1][1,3,1][1,1,3]]\n$\nTaking \\(\\alpha = \\frac{1}{2}\\), then:\nf(\\frac{1}{2}A + \\frac{1}{2}B) > \\frac{1}{2}f(A) + \\frac{1}{2}f(B)\nThis violates convexity, proving that even in a single-layer case, the problem is **non-convex**.\n(2) Now consider the general multi-layer formulation，We can instead set all parameters of the network to zero except for those in the first layer, keeping the form consistent with the one-layer result described above.\nThen the entire deep network reduces to the form \\( W_0 \\), and we recover exactly the same objective as in the single-layer case.\n\n**end of proof**\n\nSince global optima are hard to attain in non-convex problems, we instead focus on finding **good local optima**. Our approach achieves a **balance between optimization space and efficiency**.\n\nThe original problem is defined under standard metric constraints (triangle inequality and zero diagonals). Our method introduces a stricter condition (**Theorem 8 bullet point 3 **), which defines a narrower solution space we refer to as the **tropical metric space**.\n\nWhile existing methods like HLWB optimize over the general metric space, our approach is more effective when the optimal solution lies close to this constrained space. However, we currently lack a formal proof of convergence.\n\nTo encourage convergence to good local minima, we adopt several practical strategies:\n- Initialize outputs around the mean of the target matrix \\(D\\), ensuring triangle inequality via a constructed matrix \\(M\\).\n- Add controlled randomness for better optimization dynamics.\n- Use **parallel optimization** to avoid poor local minima, which significantly improves results.\n\n\n**Q2:Lack of evaluation on non-synthetic datasets makes it unclear how applicable the method is for real world applications.**\n\nA2: Thanks for your feedback. To address your concern about the real-world applicability of our method, we conducted additional experiments on the MNIST dataset and a real graph dataset.\n\nTo further validate our method for **metric matrix recovery**, we tested it on MNIST using two non-metric cases: noisy Euclidean distances  following [1] and naturally non-metric cosine similarities following.\n### Noisy Euclidean Distance (MNIST)\n\n| N   | Method    | Used Time (s) | Result       | Violation |\n|------|-----------|----------------|--------------|-----------|\n| 100  | HLWB      | 35.04          | 0.052        | 0         |\n| 100  | Tropical  | 0.53           | 0.063        | 0         |\n### Cosine Similarity Distance (MNIST)\n\n| N   | Method    | Used Time (s) | Result        | Violation |\n|------|-----------|----------------|---------------|-----------|\n| 100  | HLWB      | 109.11         | 3.50e-06       | 0         |\n| 100  | Tropical  | 0.51           | 0.004          | 0         |\n\n## Experiments on a Real Graph Dataset\n\nTo further validate the practicality of our approach, we applied **MetricPlug** (Section 3.3) to a real-world graph learning task.\n\n### Task Setup  \nWe used graph contrastive learning (based on GRACE [2]) for node classification, replacing standard similarity metrics with **MetricPlug** using the tropical inner product.\n\n### Dataset and Baselines  \nWe experimented on the Cora dataset (2,708 nodes), with train/val/test splits following GCN [3]. MetricPlug was compared against cosine, Hamming, Euclidean, and Manhattan distances.\n\n### Experimental Settings  \nWe used PyG’s `dropout_adj` to perturb edges (ratio = 0.1) for data augmentation. Training was run for 1,000 epochs with a learning rate of 0.01 and 64-dimensional hidden/projection layers. Accuracy was used for evaluation.\n\n| Method       | Validation Accuracy (%) | Test Accuracy (%) |\n|--------------|-------------------------|-------------------|\n| Cosine       | 77.4                    | 76.5              |\n| Manhattan    | 79.0                    | 79.2              |\n| Euclidean    | 78.2                    | 79.0              |\n| MetricPlug   | **79.2**                 | **79.4**          |\nMetricPlug outperformed other methods in both validation and test accuracy.\n[1] Li W, et al. Metric nearness made practical. AAAI2023\n[2] Zhu, Y. Deep graph contrastive representation learning. arXiv.  \n[3] Kipf, T. N. Semi-Supervised Classification with Graph Convolutional Networks. ICLR2016.", "claims_and_evidence": "Most claims are clear and convincing, namely, the investigation of the the relationship between tropical operations and metric matrices, presented in Section 3.1 and Appendix A.\nThe optimization strategy proposed in Section 3.2. potentially requires further theoretical evidence for its ability to achieve plausible minimum for the proposed optimization problem. Specifically, in Algorithm 1 - \"Training Procedure for MetricEmbedding\", and the accompanying text, the authors propose a two-step parameter update: an RMSProp step followed by changing W_i, b_i to be non-negative. It is unclear whether the proposed approach is guaranteed to achieve a plausible minimum and under which conditions.", "methods_and_evaluation_criteria": "The method was evaluated on synthetic datasets (per Section 4.1.). The metrics used to evaluate the performance make sense for MNP.\nLack of evaluation on non-synthetic datasets makes it unclear how applicable the method is for real world applications.", "theoretical_claims": "I checked the theorems and proofs in Section 3.1 and Appendix A, for correctness.\nSee the description in the \"Claims And Evidence\" section above for an open question about convergence guarantees for the proposed optimization algorithm.", "experimental_designs_or_analyses": "The experiments were performed using synthetic dataset. The experiments look sound and provide extensive evaluation of the proposed method. See my comment about lack of experiments with real world data, in the \"Methods And Evaluation Criteria\" section.", "relation_to_broader_scientific_literature": "I cannot comment because the paper is not in my area of expertise.", "essential_references_not_discussed": "I cannot comment because the paper is not in my area of expertise.", "other_strengths_and_weaknesses": "Strengths.\n* The paper is very clearly written and easy to follow.\n* Most claims have supporting proofs.\n* Experiments validate significant improvement achieved by the proposed method over state of the art approaches, with comparable or better accuracy.", "other_comments_or_suggestions": "See the above.", "questions_for_authors": "Please clarify whether the proposed training procedure for MetricEmbedding is guaranteed to achieve a plausible minimum and under which conditions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NT89iCVt6v", "reviewer": "Reviewer_pa67", "summary": "This paper considers the problem of metric nearness and proposes a new method for solving the problem. In particular, they define a tropical neural network that uses tropical operations instead of regular operations, a new loss function to be used to train the model, and then experimental results validating their model.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:Undefined error rate in Sec 4.3**\n\nA1:Thank you for pointing this out. We agree that the evaluation metric in Section 4.3 should be clarified.\n\nAll experiments in Section 4.3 use **Normalized Mean Squared Error (NMSE)**, as defined in Section 4.2, to measure reconstruction quality. Specifically, we:\n\n- Compute the ground-truth distance matrix using pairwise Euclidean distances;\n- Apply noise or masking to simulate degradation;\n- Use NMSE to quantify both pre- and post-recovery error;\n- Set missing entries to zero to ensure consistent NMSE calculation.\n\nFor example, in the M30 setting, NMSE drops from 35.50% (before recovery) to 13.85% (after), showing a clear performance gain. \n\nOur method leverages the assumption that mildly corrupted metric-consistent matrices retain latent structure, and that enforcing metric constraints during recovery improves reconstruction accuracy.\n\n**Q2:Data handling ambiguity (Sec 4.4)**\n\nA2:Thank you for your comment. Section 4.4 demonstrates the **online update capability** of our method—an aspect largely overlooked in prior work.\n\nWe simulate an online setting where the model is incrementally updated as new data arrives, without access to future entries. Starting from a partially observed distance matrix (e.g., 20% revealed), we iteratively expose 20% new entries at each timestep. The model is updated using only these newly observed entries.\n\nThis setup respects causality and highlights our method’s ability to **refine predictions progressively**. Traditional convex optimization methods require full data access and incur high computational costs (e.g., \\(O(N^3)\\)), making them impractical for real-time updates.\n\nIn contrast, our method uses **efficient, localized gradient-based updates** via backpropagation, avoiding full retraining. As demonstrated in our experiments, this approach achieves **10×–1000× speedups** over baseline methods while maintaining or improving accuracy. These properties make our method well-suited for **real-time applications** that demand continuous adaptation.\n\n**Q3:Error undefined, metric mismatch (Sec 4.6)**\n\nThank you for your comment. \n\nRegarding the evaluation metric in Section 4.6, we again adopt the Normalized Mean Squared Error (NMSE) to quantify how well the compressed representation preserves the original distances. \n\nRegarding the assumption about metric nearness, we agree that the closest metric under a given norm is not necessarily of the same type as the one used to generate the original distances (e.g., Euclidean, cosine, etc.). However, the goal of this experiment is not to recover the exact generating metric, but rather to demonstrate that our method can serve as a general-purpose, low-rank, metric-preserving approximation of distance matrices. Specifically A fully specified distance matrix typically requires $O(n^2)$ parameters.  Our method seeks to compress this representation to  O(nk) parameters, while:\n\n- (a) Guaranteeing that the reconstructed matrix satisfies the metric properties, and\n\n- (b) Maintaining low computational complexity, suitable for large-scale applications.\n\nTraditional methods such as SVD or spectral decomposition offer low-rank approximations but do not guarantee metric validity, and \noften incur $ O(n^3)$ complexity. In contrast, our method can be viewed as a tropical analogue of SVD, which: \n- Operates in a multiplication-free space,\n- Enforces metric constraints by design, \n- And achieves efficient approximation using only O(n·k) parameters.\nIn this experiment, we evaluate performance in a controlled setting where the original distance matrices are generated using known distance functions .  Our method does not assume knowledge of the underlying metric but still achieves high-fidelity reconstructions, as evidenced by low NMSE and strong performance in downstream tasks (e.g., 0.79 accuracy on the Cora dataset). \n\n**Q4:Uncovered case: bullet 3 violation (Sec 4.2)**\n\nA4：Thank you for your comment. We will revise **Theorem 8** to clarify that satisfying both **Bullet 2** and **Bullet 3** implies the **triangle inequality**.\n\nOur experiments deliberately use matrices with heavily violated metric properties—e.g., **99.7%** of entries in the graph-t1 dataset (\\(N=1000\\)) violate **Bullet 3**. \n\nQ5: Unnecessary Theorems 1–4 \n\nA5: Thank you. We agree that Theorems 1–4 are standard and will streamline or move them to the appendix to improve clarity without losing completeness.\n\nQ6: Essential References Not Discussed \n\nA6: Thank you for the suggestion. We have reviewed references [A–I] and will revise the related sections accordingly. Detailed updates will be provided in the next rebuttal stage.\n\nQ7:PAF\n\nFor \\(N = 2000\\), our method (Tropical) achieves an NMSE of **0.18** in **34s** with **0 violations**, while PAF yields a lower NMSE (**0.068**) but takes **3133.91s**, produces **3.7e7 violations**, and fails to converge—highlighting our method’s superior efficiency, and suitability for large-scale applications.", "claims_and_evidence": "The main contributions of the paper are \n\n1. Theorem 8. \n\nI think this claim has sufficient evidence. The proof from skimming seems correct to me. \n\n2. Empirically, testing their new method. \n\nThere is quite a bit of evidence for this claim; however, I think there could be more evidence, particularly explicit comparisons against Project and Forget.", "methods_and_evaluation_criteria": "The paper should benchmark against Project and Forget. \n\nOne particular dataset that could be added is the case are metrics where bullet point 3 (Page 3 Line 156 right col) is violated.", "theoretical_claims": "I skimmed the proofs. They look okay. \n\nHowever, I do not think Theorems 1,2,3,4 need to be presented. These are quite standard.", "experimental_designs_or_analyses": "The experimental design is valid for section 4.2. Except there is a case where the paper does not test that should be tested. Specifically, metrics where bullet point 3 (Page 3 Line 156 right col) is violated. \n\nFor the experiment in section 4.3, error rate is not defined. Hence makes the experiement difficult to understand. \n\nThe experiment in section 4.4 does not make sense. How is the new data fed in? Is the original matrix masked and the mask is then slowly changed? Also if $d(a,b)$ is masked. Can $d(a,c)$ be visible to the method earlier. When testing, why should the trained network have any information about the new data?\n\nSection 4.5 is okay\n\nSection 4.6 error rate is again not defined. Additionally, metrix nearness finds the closest metrix. There is no reason to assume that the closest metric is of the same type as the metric that was used to create the corrupted matrix.", "relation_to_broader_scientific_literature": "The metric nearness problem is an important problem, and solutions to it help design robust and theoretically justified data analysis techniques. \n\nHowever, solving the problem is quite computationally intensive. Hence advances in making solving the problem more tractable are important. Additionally, the paper uses neural networks. This makes it more tractable to integrate into the broader framework.", "essential_references_not_discussed": "The paper does a good work of providing references for the $\\ell_2$ version of the metric nearness problem. That is when the loss function is the squared distance. However, if the paper chooses to do so, I think it could improve the paper to connect to broader literature for the $\\ell_0$ version of the problem. I provide the necessary papers here [A,B,C,D]. \n\nAdditionally, in relation to the downgrade of the performance when it is not a metrix (Line 19 Right Col). The experiments in the introduction are nice conrete examples [B,E]\n\nThere also have been targeted works, where the target is a tree metrix [G] and Euclidean metric [H]. There also have been older work that tried fixing the metric [I]  \n\n[A] A. C. Gilbert and L. Jain. If it ain’t broke, don’t fix it: Sparse metric repair. In 2017 55th Annual Allerton\nConference on Communication, Control, and Computing (Allerton), pages 612–619, Oct 2017.\n\n[B] Chenglin Fan, Anna C .Gilbert, Benjamin Raichel, Rishi Sonthalia, and Gregory Van Buskirk. Generalized metric repair on graphs. In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22-24, 2020, Tórshavn, Faroe Islands, volume 162 of LIPIcs, pages 25:1–25:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.\n\n[C] Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, and Arnaud de Mesmay. Fitting metrics and ultrametrics with minimum disagreements. In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 301–311. IEEE, 2022\n\n[D] Chenglin Fan, Benjamin Raichel, and Gregory Van Buskirk. Metric Violation Distance: Hardness and Approximation. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 196–209, 2018.\n\n[E] Anna C. Gilbert and Rishi Sonthalia. Unsupervised metric learning in presence of missing data. 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 313– 321, 2018.\n\n[G] Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, and Mikkel Thorup. Fitting distances by tree metrics minimizing the total error within a constant factor. In 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 468–479. IEEE, 2021.\n\n[H] Rishi Sonthalia, Greg Van Buskirk, Benjamin Raichel, and Anna C. Gilbert. How can classical mul- tidimensional scaling go wrong? In Advances in Neural Information Processing Systems (NeurIPS), pages 12304–12315, 2021.\n\n[I] Julian Laub,Klaus-Rober tMüller,Felix A Wichmann, and Jakob H Macke. Inducing metric violations in human similarity judgements. In Advances in neural information processing systems, pages 777–784, 2007.", "other_strengths_and_weaknesses": "The main weakness for me are sections 4.3, 4.4 and 4.6. If the authors clarify the concerns there. I am happy to increase my score.", "other_comments_or_suggestions": "There are some typos such as missing spaces.", "questions_for_authors": "Please see the experimental design section. I have a variety of questions about Section 4.3, 4.4 and 4.6", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper initially received ratings of (3, 3, 2). After the rebuttal, the reviewers updated their ratings to (3, 4, 3), all of which were positive. 
According to the reviewers' feedback, the rebuttal effectively addressed their concerns regarding several key areas, such as the evidence supporting the claimed benefits of MetricPlug for downstream tasks, whether the mini-batch algorithm guarantees the triangle inequality property, and the lack of evaluations on non-synthetic datasets. 

Since all reviewers expressed positive feedback, the area chair recommends a "weak accept" if there is room in the program. The authors are encouraged to include the discussion and additional experiments in their revision.
Decision: Accept (poster)