Matrix tri-factorization over the tropical semiring
Amra Omanović Polona Oblak Tomaž Curk
Tropical semiring has proven successful in several research areas, including
optimal control, bioinformatics, discrete event systems, or solving a decision
problem. In previous studies, a matrix two-factorization algorithm based on the
tropical semiring has been applied to investigate bipartite and tripartite
networks. Tri-factorization algorithms based on standard linear algebra are
used for solving tasks such as data fusion, co-clustering, matrix completion,
community detection, and more. However, there is currently no tropical matrix
tri-factorization approach, which would allow for the analysis of multipartite
networks with a high number of parts. To address this, we propose the
triFastSTMF algorithm, which performs tri-factorization over the tropical
semiring. We apply it to analyze a four-partition network structure and recover
the edge lengths of the network. We show that triFastSTMF performs similarly to
Fast-NMTF in terms of approximation and prediction performance when fitted on
the whole network. When trained on a specific subnetwork and used to predict
the whole network, triFastSTMF outperforms Fast-NMTF by several orders of
magnitude smaller error. The robustness of triFastSTMF is due to tropical
operations, which are less prone to predict large values compared to standard
operations.