7 papers
Supervised Tree-Wasserstein Distance
Yuki Takezawa, Ryoma Sato, Makoto Yamada
To measure the similarity of documents, the Wasserstein distance is a powerful tool, but it requires a high computational cost. Recently, for fast computation of the Wasserstein di…
Fast Unbalanced Optimal Transport on a Tree
Ryoma Sato, Makoto Yamada, Hisashi Kashima
This study examines the time complexities of the unbalanced optimal transport problems from an algorithmic perspective for the first time. We reveal which problems in unbalanced op…
A Survey on The Expressive Power of Graph Neural Networks
Ryoma Sato
Graph neural networks (GNNs) are effective machine learning models for various graph learning problems. Despite their empirical successes, the theoretical limitations of GNNs have…
Random Features Strengthen Graph Neural Networks
Ryoma Sato, Makoto Yamada, Hisashi Kashima
Graph neural networks (GNNs) are powerful machine learning models for various graph learning tasks. Recently, the limitations of the expressive power of various GNN models have bee…
Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces
Ryoma Sato, Marco Cuturi, Makoto Yamada +1
Comparing two probability measures supported on heterogeneous spaces is an increasingly important problem in machine learning. Such problems arise when comparing for instance two p…
Approximation Ratios of Graph Neural Networks for Combinatorial Problems
Ryoma Sato, Makoto Yamada, Hisashi Kashima
In this paper, from a theoretical perspective, we study how powerful graph neural networks (GNNs) can be for learning approximation algorithms for combinatorial problems. To this e…