Hideitsu Hino

NeurIPS Conference 2025 Conference Paper

An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph

• Tam Le
• Truyen Nguyen
• Hideitsu Hino
• Kenji Fukumizu

We investigate optimal transport (OT) for measures on graph metric spaces with different total masses. To mitigate the limitations of traditional $L^p$ geometry, Orlicz-Wasserstein (OW) and generalized Sobolev transport (GST) employ \emph{Orlicz geometric structure}, leveraging convex functions to capture nuanced geometric relationships and remarkably contribute to advance certain machine learning approaches. However, both OW and GST are restricted to measures with equal total mass, limiting their applicability to real-world scenarios where mass variation is common, and input measures may have noisy supports, or outliers. To address unbalanced measures, OW can either incorporate mass constraints or marginal discrepancy penalization, but this leads to a more complex two-level optimization problem. Additionally, GST provides a scalable yet rigid framework, which poses significant challenges to extend GST to accommodate nonnegative measures. To tackle these challenges, in this work we revisit the entropy partial transport (EPT) problem. By exploiting Caffarelli \& McCann's insights, we develop a novel variant of EPT endowed with Orlicz geometric structure, called \emph{Orlicz-EPT}. We establish theoretical background to solve Orlicz-EPT using a binary search algorithmic approach. Especially, by leveraging the dual EPT and the underlying graph structure, we formulate a novel regularization approach that leads to the proposed \emph{Orlicz-Sobolev transport} (OST). Notably, we demonstrate that OST can be efficiently computed by simply solving a univariate optimization problem, in stark contrast to the intensive computation needed for Orlicz-EPT. Building on this, we derive geometric structures for OST and draw its connections to other transport distances. We empirically illustrate that OST is several-order faster than Orlicz-EPT. Furthermore, we show preliminary evidence on the advantages of OST for measures on a graph in document classification and topological data analysis.

ICLR Conference 2025 Conference Paper

Difference-of-submodular Bregman Divergence

• Masanari Kimura
• Takahiro Kawashima
• Tasuku Soma
• Hideitsu Hino

The Bregman divergence, which is generated from a convex function, is commonly used as a pseudo-distance for comparing vectors or functions in continuous spaces. In contrast, defining an analog of the Bregman divergence for discrete spaces is nontrivial. Iyer & Bilmes (2012b) considered Bregman divergences on discrete domains using submodular functions as generating functions, the discrete analogs of convex functions. In this paper, we further generalize this framework to cases where the generating function is neither submodular nor supermodular, thus increasing the flexibility and representational capacity of the resulting divergence, which we term the difference-of-submodular Bregman divergence. Additionally, we introduce a learnable form of this divergence using permutation-invariant neural networks (NNs) and demonstrate through experiments that it effectively captures key structural properties in discrete data. As a result, the proposed method significantly improves the performance of existing methods on tasks such as clustering and set retrieval problems. This work addresses the challenge of defining meaningful divergences in discrete settings and provides a new tool for tasks requiring structure-preserving distance measures.

TMLR Journal 2025 Journal Article

Dynamics of the accelerated t-SNE

• Kyoichi Iwasaki
• Hideitsu Hino

This paper investigates the dynamics of t-Stochastic Neighbor Embedding (t-SNE), a popular tool for visualizing complex datasets in exploratory data analysis, optimized by the Nesterov’s accelerated gradient method. Building on the foundational work that connects t-SNE with spectral clustering and dynamical systems, we extend the analysis to include accelerated dynamics which is not addressed in the previous work, revealing the emergence of Bessel and modified Bessel functions as a novel aspect of the algorithm’s behavior characterizing the temporal evolution of the accelerated t-SNE. Because the ordinary differential equation corresponding to the optimization process under consideration has a closed-form solution, by performing eigenvalue decomposition of the data’s adjacency matrix as a pre-processing step, we can obtain low-dimensional embeddings at any point in time without performing sequential optimization. This advancement not only enhances the practical utility of t-SNE but also contributes to a deeper understanding of its underlying dynamics.

ICML Conference 2025 Conference Paper

Scalable Sobolev IPM for Probability Measures on a Graph

• Tam Le
• Truyen Nguyen
• Hideitsu Hino
• Kenji Fukumizu

We investigate the Sobolev IPM problem for probability measures supported on a graph metric space. Sobolev IPM is an important instance of integral probability metrics (IPM), and is obtained by constraining a critic function within a unit ball defined by the Sobolev norm. In particular, it has been used to compare probability measures and is crucial for several theoretical works in machine learning. However, to our knowledge, there are no efficient algorithmic approaches to compute Sobolev IPM effectively, which hinders its practical applications. In this work, we establish a relation between Sobolev norm and weighted $L^p$-norm, and leverage it to propose a novel regularization for Sobolev IPM. By exploiting the graph structure, we demonstrate that the regularized Sobolev IPM provides a closed-form expression for fast computation. This advancement addresses long-standing computational challenges, and paves the way to apply Sobolev IPM for practical applications, even in large-scale settings. Additionally, the regularized Sobolev IPM is negative definite. Utilizing this property, we design positive-definite kernels upon the regularized Sobolev IPM, and provide preliminary evidences of their advantages for comparing probability measures on a given graph for document classification and topological data analysis.

TMLR Journal 2025 Journal Article

Tree Structure for the Categorical Wasserstein Weisfeiler-Lehman Graph Kernel

• Keishi Sando
• Tam Le
• Hideitsu Hino

The Wasserstein Weisfeiler-Lehman~(WWL) graph kernel is a popular and efficient approach, utilized in various kernel-dependent machine learning frameworks for practical applications with graph data. It incorporates optimal transport geometry into the Weisfeiler-Lehman graph kernel, to mitigate the information loss inherent in aggregation strategies of graph kernels. While the WWL graph kernel demonstrates superior performance in many applications, it suffers a drawback in its computational complexity, i.e., at least $\mathcal{O}(n_{1} n_{2})$, where $n_{1}, n_{2}$ denote the number of vertices in the input graphs. Consequently, it hinders the practical applicability of the WWL graph kernel, especially in large-scale settings. In this paper, we propose the \emph{Tree Wasserstein Weisfeiler-Lehman}~(TWWL) algorithm, which leverages a \emph{tree structure} to scale up the exact computation of the WWL graph kernel for graph data with categorical node labels. In particular, the computational complexity of the TWWL algorithm is $\mathcal{O}(n_{1} + n_{2})$, which enables its application to large-scale graphs. Numerical experiments demonstrate that the performance of the proposed algorithm compares favorably with baseline kernels, while its computation is several orders of magnitude faster than the classic WWL graph kernel. This paves the way for applications in large-scale datasets where the WWL kernel is computationally prohibitive.

TMLR Journal 2024 Journal Article

A Short Survey on Importance Weighting for Machine Learning

• Masanari Kimura
• Hideitsu Hino

Importance weighting is a fundamental procedure in statistics and machine learning that weights the objective function or probability distribution based on the importance of the instance in some sense. The simplicity and usefulness of the idea has led to many applications of importance weighting. For example, it is known that supervised learning under an assumption about the difference between the training and test distributions, called distribution shift, can guarantee statistically desirable properties through importance weighting by their density ratio. This survey summarizes the broad applications of importance weighting in machine learning and related research.

TMLR Journal 2023 Journal Article

Minorization-Maximization for Learning Determinantal Point Processes

• Takahiro Kawashima
• Hideitsu Hino

A determinantal point process (DPP) is a powerful probabilistic model that generates diverse random subsets from a ground set. Since a DPP is characterized by a positive definite kernel, a DPP on a finite ground set can be parameterized by a kernel matrix. Recently, DPPs have gained attention in the machine learning community and have been applied to various practical problems; however, there is still room for further research on the learning of DPPs. In this paper, we propose a simple learning rule for full-rank DPPs based on a minorization-maximization (MM) algorithm, which monotonically increases the likelihood in each iteration. We show that our minorizer of the MM algorithm provides a tighter lower-bound compared to an existing method locally. We also generalize the algorithm for further acceleration. In our experiments on both synthetic and real-world datasets, our method outperforms existing methods in most settings. Our code is available at https://github.com/ISMHinoLab/DPPMMEstimation.

AAAI Conference 2021 Conference Paper

Bayesian Dynamic Mode Decomposition with Variational Matrix Factorization

• Takahiro Kawashima
• Hayaru Shouno
• Hideitsu Hino

Dynamic mode decomposition (DMD) and its extensions are data-driven methods that have substantially contributed to our understanding of dynamical systems. However, because DMD and most of its extensions are deterministic, it is difficult to treat probabilistic representations of parameters and predictions. In this work, we propose a novel formulation of a Bayesian DMD model. Our Bayesian DMD model is consistent with the procedure of standard DMD, which is to first determine the subspace of observations, and then compute the modes on that subspace. Variational matrix factorization makes it possible to realize a fully-Bayesian scheme of DMD. Moreover, we derive a Bayesian DMD model for incomplete data, which demonstrates the advantage of probabilistic modeling. Finally, both of nonlinear simulated and real-world datasets are used to illustrate the potential of the proposed method.

UAI Conference 2011 Conference Paper

New Probabilistic Bounds on Eigenvalues and Eigenvectors of Random Kernel Matrices

• Nima Reyhani
• Hideitsu Hino
• Ricardo Vigário