# Label Propagation Through Optimal Transport

Mourad El Hamri  LIPN, CNRS UMR 7030
La Maison des Sciences Numériques
Université Sorbonne Paris Nord
<EMAIL_ADDRESS>Younès Bennani  LIPN, CNRS UMR 7030
La Maison des Sciences Numériques
Université Sorbonne Paris Nord
<EMAIL_ADDRESS>Issam Falih  LIMOS, CNRS UMR 6158
La Maison des Sciences Numériques
Université Clermont Auvergne
<EMAIL_ADDRESS>
###### Abstract

In this paper, we tackle the transductive semi-supervised learning problem
that aims to obtain label predictions for the given unlabeled data points
according to Vapnik’s principle. Our proposed approach is based on optimal
transport, a mathematical theory that has been successfully used to address
various machine learning problems, and is starting to attract renewed interest
in semi-supervised learning community. The proposed approach, Optimal
Transport Propagation (OTP), performs in an incremental process, label
propagation through the edges of a complete bipartite edge-weighted graph,
whose affinity matrix is constructed from the optimal transport plan between
empirical measures defined on labeled and unlabeled data. OTP ensures a high
degree of predictions certitude by controlling the propagation process using a
certainty score based on Shannon’s entropy. We also provide a convergence
analysis of our algorithm. Experiments task show the superiority of the
proposed approach over the state-of-the-art. We make our code publicly
available. 111Code is available at: https://github.com/MouradElHamri/OTP

###### Index Terms:

Optimal Transport, Semi-supervised Learning, Label Propagation

##  I Introduction

Deep learning models have achieved state-of-the-art performance on a broad
spectrum of learning tasks, and are becoming increasingly popular in various
application domains [18], such as image classification and speech recognition,
where a large amount of labeled data is available. However, for many tasks, it
is often prohibitively expensive to collect a large high quality labeled
dataset due to lack of time, resources, or other factors, while unlabeled data
is cheap and abundant. Medicine is the best illustration of this scenario,
where measurement require expensive machinery and labels are the result of a
labor and expensive expert-assisted time-consuming analysis.

In conjunction with transfer learning (TL), semi-supervised learning (SSL)
constitute an attractive approach towards addressing the lack of massive
labeled datasets. It seeks to largely alleviate the need for labeled samples
by providing a means to jointly leverage unlabeled instances. Graph-based
semi-supervised approaches are one of the most widely used classes of semi-
supervised learning methods, due to their performance and to more and more
real graph datasets. The problem is to predict the label of all the unlabeled
vertices in the graph based only on a small subset of labeled vertices.
A popular graph-based semi-supervised learning method is to use label
propagation, this latter has shown good performances in different machine
learning applications over the past few years, such as social network analysis
[4] [35], natural language processing [2], and image segmentation [7].

Most existing label propagation algorithms essentially estimate a data
labeling on a fully connected graph constructed by connecting similar samples.
The fully connected graph leads typically to a complete labeling for both
unlabeled and labeled (re-labeling) samples, which may be interesting under
the presence of label noise assumption. Otherwise, it is necessary to add a
regularization term to the corresponding objective function in order to
penalize predicted labels that do not match the correct ones [32]. The main
existing label propagation approaches can be divided into two categories,
methods in the first category such as [37][36], capture information on a
bilateral level, and methods in the second category as [34], capture
information on a local level. First category approaches use a Gaussian kernel
with a free parameter $\sigma$ to compute the pairwise relationships between
data points, which has some drawbacks, since it is hard to determine the
optimal value of $\sigma$ if only very few labeled instances are available
[36], and the labeling is very sensitive to the parameter $\sigma$ in the
Gaussian kernel [34]. Instead of the pairwise relationships, which has the
disadvantage that only the pairwise relations between the instances are taken
into account, second category approaches use the local neighborhood
information which assumes that each data point can be optimally reconstructed
using a linear combination of its neighbors, which has also many
inconveniences, since the optimal number of instances constituting the linear
neighborhood must be determined in advance, and even a small variation of its
value could make the labeling results very different, without forgetting that
the linearity assumption is mainly for computational convenience [34].
Furthermore, approaches in both categories are unable to capture the
underlying geometry of the entire input space and the different interactions
that may occur between labeled and unlabeled data points in a global level,
and they have another major disadvantage, that of inferring simultaneously all
the pseudo-labels by hard assignment, while neglecting the different certainty
degree of each prediction. An efficient label propagation approach capable of
addressing all these points has not yet been reported.
One of the paradigms used to capture the underlying geometry of the data is
grounded on the theory of optimal transport [33] [28]. Optimal transport
provides a powerful means with many attractive theoretical properties for
comparing probability measures in a Lagrangian framework, that make many
machine learning fields, rely on it to model tasks, compute solutions, and
provide theoretical analysis of the algorithms, such as domain adaptation
[10][9][26][27], clustering [17][6][5], generative models [21] and more
recently semi-supervised learning [30] [31].

In this paper, we address the existing issues of label propagation methods
described above by proposing a principally new approach based on optimal
transport that efficiently solves the transductive semi-supervised learning
and allows the control of the predictions certainty. We construct an uncommon
graph for semi-supervised learning: A complete bipartite edge-weighted graph,
to avoid adding a regularization term in the corresponding objective function
to penalize predicted labels that do not match the correct ones. In order to
benefit from all the geometrical information available in the input space, the
affinity matrix of this graph is inferred from the optimal transport plan
between empirical measures defined on labeled and unlabeled data points.
Furthermore, to take advantage from the reliance of semi-supervised methods to
the amount of prior information, we adopt an incremental process to propagate
labels through the vertices of the graph, this will allow us to enrich the
labeled set with new samples at each iteration, and then, to label the still
unlabeled instances with a high certainty. In order to reinforce the certitude
of the predictions, we incorporate a certainty score that controls the
incremental propagation process. We also provide a convergence analysis for
the proposed approach, to show that it requires a finite number of iterations
to converge. To the best of our knowledge, the proposed approach is the first
optimal transport method for label propagation task.

The rest of this paper is organized as follows: in Section 2, we present an
overview of transductive semi-supervised learning. Section 3 details optimal
transport problem and its entropic regularized version. In Section 4, we
present the proposed OTP method. In Section 5, we provide comparisons to
state-of-art methods on seven benchmark datasets.

##  II Transductive Semi-supervised Learning

In traditional machine learning, a distinction has usually been made between
two major tasks: Supervised and unsupervised learning. Conceptually, semi-
supervised learning (SSL) [38] is situated between them. The aim of semi-
supervised learning is to use the abundant amount of unlabeled samples, as
well as a typically smaller set of labeled instances, to improve the
performance that can be obtained either by discarding the unlabeled data and
doing classification (supervised learning) or by discarding the available
labels and doing clustering (unsupervised learning).

Semi-supervised learning makes use of four kind of assumption to utilize the
underlying unstructured data. Smoothness assumption: For two data points
$x,x^{{}^{\prime}}$ that are close in the input space $\mathcal{X}$, the
corresponding labels $y,y^{{}^{\prime}}$ should be the same. Low-density
assumption: The decision boundary should preferably pass through low-density
regions in the input space $\mathcal{X}$. Manifold assumption: The high-
dimensional input space $\mathcal{X}$ is constituted of multiple lower-
dimensional substructures known as manifolds and samples lying on the same
manifold should have the same label. Cluster assumption: Data points belonging
to the same cluster are likely to have the same label.

According to its objective, semi-supervised learning, can be categorized into
two sub-paradigms: Transductive and Inductive semi-supervised learning [32].
Transductive semi-supervised learning is exclusively interested with obtaining
label predictions for the given unlabeled data points. However, inductive
semi-supervised learning seeks to infer a good classifier that can estimate
efficiently the label for any instance in the input space, even for previously
unseen data points.

In transductive semi-supervised learning settings, we have a finite ordered
set of $l$ labeled examples $\\{(x_{1},y_{1}),...,(x_{l},y_{l})\\}$. Each
example $(x_{i},y_{i})$ of this set consists of an data point $x_{i}$ from a
given input space $\mathcal{X}$, and its corresponding label
$y_{i}\in\mathcal{Y}=\\{c_{1},...,c_{K}\\}$, where $\mathcal{Y}$ is a discrete
label set composed by $K$ classes. In conjunction with labeled samples, we
also have access to a larger collection of $u$ data points
$\\{x_{l+1},...,x_{u}\\}$, whose labels are unknown. In the remainder, we
denote with $X_{L}$ and $X_{U}$ respectively the collection of labeled and
unlabeled data points, and with $Y_{L}$ the labels corresponding to $X_{L}$.
Transductive semi-supervised learning aims to infer directly the labels
$Y_{U}$ of the unlabeled instances using all the samples in $X=X_{L}\cup
X_{U}$ and labels $Y_{L}$ [8]. The goal of transductive semi-supervised
learning makes it by essence a perfect illustration of Vapnik’s principle:
When trying to solve some problem, one should not solve a more difficult
problem as an intermediate step. Thus instead of inferring a classifier over
the input space and evaluating it on the unlabeled points, Vapnik’s principle
suggests naturally, to propagate information through direct connections
between data points, which can be achieved using a graph based method, namely
label propagation.

Label propagation approaches typically involve two phases: A graph
construction phase where each instance is represented by a vertex, similar
vertices are then connected to each other by edges, thereafter, the edges are
weighted to indicate the degree of similarity between the vertices. The edges
weights are denoted by an affinity matrix. Second phase is label propagation,
where the already constructed graph in the first phase is used to spread
labels through its edges, from labeled vertices to unlabeled ones.

##  III Optimal Transport

In this section we present key concepts of optimal transport and its entropic
regularized version.

Optimal transport [33][28] is the branch of mathematics that seeks to
transform a probability measure into another one while minimizing the total
cost of transportation. We owe the first formulation of the optimal transport
problem to the French mathematician Gaspard Monge [22]: Let
$(\mathcal{X},\mu)$ and $(\mathcal{Y},\nu)$ be two probability spaces, $c$ a
positive cost function over $\mathcal{X}\times\mathcal{Y}$, which represents
the work needed to transport a unit of mass from $x\in\mathcal{X}$ to
$y\in\mathcal{Y}$. The problem asks to find a measurable transport map
$\mathcal{T}:\mathcal{X}\to\mathcal{Y}$ such that:

$(\mathcal{M})\,\,\,\,\,\,\underset{\mathcal{T}}{\inf}\\{\int_{\mathcal{X}}c(x,\mathcal{T}(x))d\mu(x)|\mathcal{T}\\#\mu=\nu\\},$
(1)

where $\mathcal{T}\\#\mu$ stands for the image measure of $\mu$ by
$\mathcal{T}$. The problem $(\mathcal{M})$ is not symmetrical, and may not
admit a solution, it is the case when $\mu$ is a Dirac mass and $\nu$ is not.

A convex relaxation of the original problem was suggested by the Soviet
mathematician and economist Leonid Kantorovitch [15], this formulation allows
mass splitting and it guarantees to have a solution under very general
assumptions.

$(\mathcal{MK})\,\,\,\,\,\,\underset{\gamma}{\inf}\\{\,\int_{\mathcal{X}\times\mathcal{Y}}\,c(x,y)\,d\gamma(x,y)\,|\,\gamma\in\Pi(\mu,\nu)\,\\},$
(2)

where $\Pi(\mu,\nu)$ is the set of transport plans, constituted of all joint
probability measures $\gamma$ on $\mathcal{X}\times\mathcal{Y}$ with marginals
$\mu$ and $\nu$:
$\Pi(\mu,\nu)=\\{\gamma\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})|\pi_{1}\\#\gamma=\mu$
and $\pi_{2}\\#\gamma=\nu$}. ${\pi}_{1}$ and ${\pi}_{2}$ stand for the
projection maps:

$\begin{aligned} \pi_{1}\colon\mathcal{X}\times\mathcal{Y}&\to\mathcal{X}\\\
(x,y)&\mapsto x\end{aligned}\quad\text{and}\quad\begin{aligned}
\pi_{2}\colon\mathcal{X}\times\mathcal{Y}&\to\mathcal{Y}.\\\ (x,y)&\mapsto
y\end{aligned}$

When $\mathcal{X}=\mathcal{Y}$ is a metric space equipped with a distance $d$,
it is natural to use it as a cost function, e.g. $c(x,y)=d(x,y)^{p}$ for
$p\in{\left[1\,,+\infty\right[}$. In such case, the problem $(\mathcal{MK})$
defines a metric between probability measures over $\mathcal{X}$, called the
$p$-Wasserstein distance, defined as follows,
$\forall\mu,\nu\in\mathcal{P}(\mathcal{X})$:

$\mathrm{W}_{p}(\mu,\nu)=\underset{\gamma\in\Pi(\mu,\nu)}{\inf}(\int_{\mathcal{X}^{2}}d^{p}(x,y)\,d\gamma(x,y))^{1/p},$
(3)

Wasserstein distance has an intuitive formulation as well as the ability to
capture the underlying geometry of the measures by relying on the metric $d$.
Wasserstein distance metrize weak convergence, and it allows comparison
between probability measures, even when the supports of the measures do not
overlap. These attractive properties make it an ideal candidate for learning
problems.

In the discrete version of the optimal transport problem, i.e. when $\mu$ and
$\nu$ are only available through discrete samples
$X=(x_{1},...,x_{n})\subset\mathcal{X}$ and
$Y=(y_{1},...,y_{m})\subset\mathcal{Y}$, the empirical distributions can be
taken to be discrete measure: $\mu=\sum_{i=1}^{n}a_{i}\delta_{x_{i}}$ and
$\nu=\sum_{j=1}^{m}b_{j}\delta_{y_{j}}$, where $a=(a_{1},...,a_{n})$ and
$b=(b_{1},...,b_{m})$ are vectors in the probability simplex $\sum_{n}$ and
$\sum_{m}$ respectively, where: $\sum_{k}=\\{u\in\mathbb{R}^{k}\,|\,\forall
i\leq k,\,u_{i}\geq 0\,\,\text{and}\,\sum_{i=1}^{k}u_{i}=1\\}$. The cost
function only needs to be specified for every pair $(x_{i},y_{j})\in X\times
Y$ yielding a cost matrix $C\in\mathcal{M}_{n\times m}(\mathbb{R}^{+})$. The
optimal transport problem becomes then a linear program [3], parametrized by
the cost matrix $C$ and the transportation polytope
$U(a,b)=\\{\gamma\in\mathcal{M}_{n\times m}(\mathbb{R}^{+})\,|\,\gamma
1_{m}=a\,\,\text{and}\,\,\gamma^{\mathbf{T}}1_{n}=b\\}$, which acts as a
feasible set. Thus, solving this linear program consists of finding a plan
$\gamma^{*}$ that realizes:

$(\mathcal{D}_{\mathcal{MK}})\,\,\,\,\,\,\underset{\gamma\in
U(a,b)}{\min}\langle{\gamma},{C}\rangle_{F},$ (4)

where $\langle.,.\rangle_{F}$ is the Frobenius dot product.

If $n=m$, and, $\mu$ and $\nu$ are uniform measures,
$U(\mathbf{1}_{n}/n,\mathbf{1}_{n}/n)$ is then the Birkhoff polytope of size
$n$, and the solutions of $(\mathcal{D}_{\mathcal{MK}})$ are permutation
matrices.

Discrete optimal transport is a linear program, and thus can be solved exactly
in $\mathcal{O}(n^{3}log(n))$ when comparing two discrete measures of $n$
points with interior point methods [24], which is a heavy computational price
tag. Alternatively, one can consider an entropic regularized version of the
problem, which allows a very fast computation of the transport plan.

In [11], Cuturi proposed to add an entropic regularization term to the
expression of the discrete optimal transport problem. The regularized version
of the discrete optimal transport reads:

$\underset{\gamma\in
U(a,b)}{\min}\langle{\gamma},{C}\rangle_{F}-\varepsilon\mathcal{H}(\gamma),$
(5)

where
$\mathcal{H}(\gamma)=-\sum_{i=1}^{n}\sum_{j=1}^{m}\gamma_{ij}(\log(\gamma_{ij})-1)$
is the entropy of $\gamma$.

Since the function $\mathcal{H}$ is 1-strongly concave: Its Hessian is
$\partial^{2}\mathcal{H}(\gamma)=-diag(\frac{1}{\gamma_{ij}})$ and
$\gamma_{ij}\leq 1.$ Then, the objective of the regularized optimal transport
is an $\varepsilon$-strongly convex function, thus the regularized problem has
a unique optimal solution. The solution of the regularized optimal transport
problem has the form ${\gamma_{\varepsilon}^{*}}=diag(u)Kdiag(v)$, where $u$
and $v$ are the exponential scaling of the dual variables corresponding to
each marginal constraint, and $K$ is the exponential scaling of the cost
matrix $C$. The variables $(u,v)$ must therefore satisfy:
$u\odot(Kv)=a\,\,\,and\,\,\,v\odot(K^{\mathbf{T}}u)=b$, where $\odot$
corresponds to entrywise multiplication of vectors. This problem is known in
the numerical analysis community as the matrix scaling problem [23], and can
be solved efficiently via an iterative procedure: The Sinkhorn-Knopp algorithm
[16], which iteratively update
$u^{(l+1)}=\frac{a}{Kv^{(l)}},\,\,\,\text{and}\,\,\,v^{(l+1)}=\frac{b}{K^{\mathbf{T}}u^{(l+1)}},$
initialized with an arbitrary positive vector $v^{(0)}=1_{m}$.

For a small regularization $\varepsilon$, the unique solution
$\gamma_{\varepsilon}^{*}$ of the regularized problem converges with respect
to the weak topology to the optimal solution with maximal entropy within the
set of all optimal solutions of $(\mathcal{D}_{\mathcal{MK}})$ [25].

##  IV OPTIMAL TRANSPORT PROPAGATION : OTP

In this section, we introduce the proposed OTP approach. The main underlying
idea behind OTP is to use the optimal transport plan between the empirical
measures defined on labeled and unlabeled instances in order to construct an
improved affinity matrix, and then, to use it to propagate labels from labeled
to unlabeled data points in an incremental process ensuring prediction
certainty.

###  IV-A Problem setup

Let $X=\\{x_{1},...,x_{l+u}\\}$ be a set of $l+u$ data points in the input
space $\mathbb{R}^{d}$ and $\mathcal{C}=\\{c_{1},...,c_{K}\\}$ a discrete
label set consisting of $K$ classes. The first $l$ points denoted by
$X_{L}=\\{x_{1},...,x_{l}\\}$ are labeled according to
$Y_{L}=\\{y_{1},...,y_{l}\\}$, where $y_{i}\in\mathcal{C}$ for every
$i\in\\{1,...,l\\}$, and the remaining samples denoted by
$X_{U}=\\{x_{l+1},...,x_{l+u}\\}$ are unlabeled. Usually $l\ll u$. The aim of
label propagation algorithms is to infer the unknown labels $Y_{U}$ using all
the data points in $X=X_{L}\cup X_{U}$ and labels $Y_{L}$.

To use an appropriate formulation to the paradigm of optimal transport, the
empirical distribution of $X_{L}$ and $X_{U}$ must be expressed respectively
using discrete measures as:

$\mu=\sum_{i=1}^{l}a_{i}\delta_{x_{i}}\,\,\,\,\text{and}\,\,\,\,\nu=\sum_{j=l+1}^{l+u}b_{j}\delta_{x_{j}},$
(6)

Under the assumption that $X_{L}$ and $X_{U}$ are a collection of independent
and identically distributed data points, the weights of all instances in each
sample are naturally set to be equal:

$a_{i}=\frac{1}{l},\forall
i\in\\{1,...,l\\}\,\text{and}\,b_{j}=\frac{1}{u},\forall
j\in\\{l+1,...,l+u\\},$ (7)

###  IV-B Proposed approach

Label propagation algorithms are often graph-based methods, typically
consisting of two phases, the first one is the graph construction and the
second is the label propagation phase, where we spread labels from the labeled
vertices of the graph already constructed in the first phase, to unlabeled
ones.

1st phase: The main underlying idea of the first phase is the use of a
complete bipartite edge-weighted graph [1]
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W})$, where $\mathcal{V}=X$ is
the vertex set, that can be divided into two disjoint and independent sets
$\mathcal{L}=X_{L}$ and $\mathcal{U}=X_{U}$,
$\mathcal{E}\subset\\{\mathcal{L}\times\mathcal{U}\\}$ is the edge set, and
$\mathcal{W}\in\mathcal{M}_{l,u}(\mathbb{R}^{+})$ is the affinity matrix to
denote the edges weights. The weight $w_{i,j}$ on edge $e_{i,j}\in\mathcal{E}$
reflects the degree of similarity between $x_{i}\in\mathcal{L}$ and
$x_{j}\in\mathcal{U}$. We propose to infer the affinity matrix $\mathcal{W}$
from the optimal transport plan between the measures $\mu$ and $\nu$. The
intuition behind the use of this uncommon type of graph in semi-supervised
learning, is to exploit its ability to assign labels only for instances in
$\mathcal{U}$, without modifying the labels of samples in $\mathcal{L}$, which
makes it very attractive for label propagation tasks outside the label noise
assumption, i.e. there is no need to add any regularization term to the
objective function of the label propagation algorithm in order to penalize
predicted labels that do not match the correct ones in $\mathcal{L}$.

To measure quantitatively the similarity between vertices, we need to use some
distance over the input space $\mathbb{R}^{d}$. Let
$C\in\mathcal{M}_{l,u}(\mathbb{R}^{+})$ denotes the matrix of squared
euclidean distances between vertices in $\mathcal{L}$ and $\mathcal{U}$,
defined as follows:

$c_{i,j}=\lVert
x_{i}-x_{j}\rVert^{2},\,\,\,\forall(x_{i},x_{j})\in\mathcal{L}\times\mathcal{U},$
(8)

In order to construct an affinity matrix $\mathcal{W}$ that captures the
underlying geometry of the whole data $X$ in the input space and all the
interactions between labeled and unlabeled data in a global vision, instead of
the pairwise relationships that perform in a bilateral level or the local
neighborhood information and to avoid the use of a Gaussian kernel, a natural
choice is to rely on the optimal transport theory. Since optimal transport
suffers from a computational burden, we can overcome this issue by using its
entropic regularized version, in the following way:

$\gamma^{*}_{\varepsilon}=\underset{\gamma\in
U(a,b)}{argmin}\,\,\langle{\gamma},{C}\rangle_{F}-\varepsilon\mathcal{H}(\gamma),$
(9)

The optimal transport plan $\gamma^{*}_{\varepsilon}$ provides us the weights
of associations between vertices in $\mathcal{L}$ and $\mathcal{U}$, thus,
$\gamma^{*}_{\varepsilon}$ can be interpreted in our context as a similarity
matrix between the two parts $\mathcal{L}$ and $\mathcal{U}$ of the graph
$\mathcal{G}$: Similar labeled and unlabeled vertices correspond to higher
value in $\gamma^{*}_{\varepsilon}$.

To have a class probability interpretation, we column-normalize the matrix
$\gamma^{*}_{\varepsilon}$, it will give a non-square left-stochastic affinity
matrix $\mathcal{W}$, defined as follows:

$w_{i,j}=\frac{\gamma^{*}_{\varepsilon_{i,j}}}{\sum_{i}\gamma^{*}_{\varepsilon_{i,j}}},\,\,\,\forall
i,j\in\\{1,...,l\\}\times\\{l+1,...,l+u\\},$ (10)

where $w_{i,j},\,\,\,\forall i,j\in\\{1,...,l\\}\times\\{l+1,...,l+u\\}$ is
then, the probability of jumping from the vertex $x_{i}\in\mathcal{L}$ to
$x_{j}\in\mathcal{U}$.

2nd phase: Our intuition is to use the affinity matrix $\mathcal{W}$ in the
second phase to identify labeled data points who should spread their labels to
similar unlabeled instances. We suggest to use an incremental process to label
the points in $\mathcal{U}$. We suggest also to provide with each pseudo-label
a certainty score that measures the certitude of the prediction, and to use it
in order to control the incremental label propagation process.

First, we need to construct a label matrix
$U\in\mathcal{M}_{u,K}(\mathbb{R}^{+})$, to denotes the probability of each
unlabeled data point $x_{j}$, $j\in\\{l+1,...,l+u\\}$ to belong to a class
$c_{k}$, $k\in\\{1,...,K\\}$. For a harmonious construction of the label
matrix $U$ with the information coming from the optimal transport plan
$\gamma^{*}_{\varepsilon}$, we propose to define the probability of an
unlabeled data point $x_{j}$ to belong to a class $c_{k}$ as the sum of its
similarity with the representatives of this class:

$u_{j,k}=\sum_{i/x_{i}\in c_{k}}w_{i,j},\forall
j,k\in\\{l+1,...,l+u\\}\times\\{1,...,K\\},$ (11)

The matrix $U$ is a non-square right-stochastic matrix, and can be interpreted
as a vector-valued function $U:X_{U}\rightarrow\sum_{K}$, which assigns a
stochastic vector $U_{j}\in\sum_{K}$ to each unlabeled data point $x_{j}$,
$j\in\\{l+1,...,l+u\\}$.

Traditional label propagation approaches infer simultaneously all the pseudo-
labels by hard assignment, without worrying about the fact that these label
predictions do not have the same degree of certainty. This issue, as mentioned
by [14], can degrade significantly the performance of the label propagation
approaches. To prevent this, we suggest to associate a certainty score $s_{j}$
with the label prediction of each $x_{j},j\in\\{l+1,...,l+u\\}$. The proposed
certainty score $s_{j}$ is defined in the following way:

$s_{j}=1-\frac{H(Z_{j})}{log_{2}(K)},\,\,\,\,\,\forall j\in\\{l+1,...,l+u\\},$
(12)

where $Z_{j}:\mathcal{C}\rightarrow\mathbb{R}$ is a real-valued random
variable, defined by $Z_{j}(c_{k})=k$, to associate a numerical value $k$ to
the potential label prediction result $c_{k}$. The probability distribution of
the random variable $Z_{j}$ is encoded in the stochastic vector $U_{j}$:

$\mathbb{P}(Z_{j}=c_{k})=u_{j,k},\,\,\,\,\,\,\forall
j,k\in\\{l+1,...,l+u\\}\times\\{1,...,K\\}$

$H$ is an uncertainty measure, which we suggest to take equal to Shannon’s
entropy [29], defined by:

$H(Z_{j})=-\sum_{k}u_{j,k}\log_{2}(u_{j,k})$,

we divide $H$ by $log_{2}(K)$ to normalize it between $0$ and $1$.

To control the certainty of the propagation process, we define a confidence
threshold $\alpha\in[0,1]$, and for each unlabeled data point $x_{j}$, we make
a comparison between $\alpha$ and $s_{j}$. If the score $s_{j}$ is greater
than $\alpha$, we assign to $x_{j}$ a pseudo-label $\hat{y_{j}}$, in the
following way:

$\hat{y_{j}}=\underset{c_{k}\in\mathcal{C}}{argmax}\,u_{j,k},\,\,\forall
j\in\\{l+1,...,l+u\\},$ (13)

Thus, the unlabeled instance $x_{j}$ will belong to the class $c_{k}$ with the
highest class-probability $u_{j,k}$, in other words, to the class whose
representatives possess the highest similarity with it. Otherwise, we do not
give any label to the point $x_{j}$.

The process above corresponds to one iteration of the proposed incremental
approach. At each of its iterations, $X_{L}$ is enriched with new instances,
and the number of data points in $X_{U}$ is reduced. This modification of
$X_{L}$, $Y_{L}$ and $X_{U}$ resulting from the incremental approach is of
major importance in the context of label propagation, since, the effectiveness
of a label propagation algorithm depends on the amount of prior information,
thus, increasing the size of $X_{L}$ at each iteration, will similarly
increase the performance of the proposed approach, and will make it possible
to label the points still in $X_{U}$ with a high degree of certainty at the
next iterations. We repeat the same whole procedure at each iteration until
convergence, here convergence means that all the data initially in $X_{U}$ are
labeled during this incremental process. The proposed algorithm, named OTP, is
formally summarized in Algorithm $1$:

Parameters : $\varepsilon,\alpha$

Input : $X_{L},X_{U},Y_{L}$

while  _not converged_ do

Compute the cost matrix $C$ by Eq(8)

Solve the optimal transport problem in Eq(9)

Compute the affinity matrix $\mathcal{W}$ by Eq(10)

Get the label matrix $U$ by Eq(11)

for  _$x_{j}\in X_{U}$_ do

Compute the certainty score $s_{j}$ by Eq(12)

if  _$s_{j} >\alpha$_ then

Get the pseudo label $\hat{y_{j}}$ by Eq(13)

Inject $x_{j}$ in $X_{L}$

Inject $\hat{y_{j}}$ in $Y_{L}$

else

Maintain $x_{j}$ in $X_{U}$

end if

end for

end while

return _$Y_{U}$_

Algorithm 1 OTP Figure 1: Overview of OTP. We initiate an incremental approach
where at each iteration, we construct a complete bipartite edge-weighted graph
based on the optimal transport plan between the distribution of labeled
instances and unlabeled ones. Then, we propagate labels through the edges of
the graph. Triangles markers correspond to the labeled instances and circles
correspond to the unlabeled data which are gradually pseudo-labeled by OTP.
The class is color-coded.

###  IV-C Convergence analysis

As mentioned earlier, the convergence of OTP means that all the samples
initially in $X_{U}$ are labeled during the incremental process. In order to
analyze the convergence of the proposed approach, we suggest to express the
evolution of $X_{L}$ and $X_{U}$ respectively as follows: Let $m_{t}$ be the
size of $X_{L}$ and $n_{t}$ be the size of $X_{U}$ at an iteration $t$, then
the evolution of the two sets can be expressed using the following dynamical
systems:

$\begin{cases}m_{t}=m_{t-1}+\zeta_{t}\\\
m_{0}=l\end{cases},\quad\begin{cases}n_{t}=n_{t-1}-\zeta_{t}\\\
n_{0}=u\end{cases}$ (14)

where $\zeta_{t}$ is the number of instances in $X_{U}$ that have been labeled
during the iteration $t$.

Theoretically, OTP must converge at the iteration $\tau$, where :
$m_{\tau}=m_{0}+\sum_{t=1}^{\tau}\zeta_{t}=m_{0}+u=l+u$, which corresponds
also to $n_{\tau}=n_{0}-\sum_{t=1}^{\tau}\zeta_{t}=n_{0}-u=u-u=0$.

The convergence analysis of our approach corresponds to showing that the
iteration $\tau$ will be reached in a finite number of intermediate
iterations. To achieve this objective, a suitable choice of $\alpha$ must be
made to allow us to label a large amount $\zeta_{t}$ of instances in $X_{U}$
at each iteration $t$. However, the following scenario can be encountered in
some intermediate iterations: Suppose that at an iteration $t$, we still have
$h$ unlabeled instances in $X_{U}$, whose certainty score $s_{j}$ is lower
than the threshold $\alpha$, which means that none of these instances can be
labeled at this iteration. To overcome this issue, one can think to decrease
the value of the threshold $\alpha$ to allow only to the point with the
greatest certainty score among the $h$ unlabeled instances, to be labeled, and
then to move from $X_{U}$ to $X_{L}$. This can be achieved as follows:

$\alpha\leftarrow\alpha-\min_{x_{j}\in[X_{U}]_{t}}(\alpha-s_{j}),$ (15)

where $[X_{U}]_{t}$ is the set of the $h$ points constituting $X_{U}$ at the
intermediate iteration $t$. Certainly, decreasing sharply the value of
$\alpha$ will allow us to label many other instances instead of just the data
point with the highest certainty score, however, this gain in terms of the
number of points labeled at the same iteration will be paid out in terms of
its predictions certainty. Our intuition behind the modification of $\alpha$
in the way above is as follows: Since moving an instance from $X_{L}$ to
$X_{U}$, can radically change the optimal transport plan between the new
distributions $\mu$ and $\nu$, and subsequently the certainty scores in the
next iteration, we can try to restore the initial value of $\alpha$ and
continue to label the other samples with the same degree of certainty as
before. If the same scenario is repeated in a future iteration, we can use the
same technique of decreasing $\alpha$ to label a new point, and so on until
convergence. This reasoning shows that the proposed algorithm needs
effectively a finite number of iterations to converge.

##  V EXPERIMENTAL RESULTS

In this section, we provide empirical experimentation for the proposed
algorithm.

###  V-A Datasets

The experiment was designed to evaluate the proposed approach on seven
benchmark datasets. Details of these datasets appear in the following table:

TABLE I: Experimental datasets Datasets | #Instances | #Features | #Classes
---|---|---|---
Iris | 150 | 4 | 3
Heart | 270 | 13 | 2
Ionosphere | 351 | 34 | 2
Dermatology | 366 | 33 | 6
Waveform | 5000 | 21 | 3
Digits | 5620 | 64 | 10
MNIST | 10000 | 784 | 10

###  V-B Evaluation indices

In order to evaluate the performance of our approach, two evaluation measures
were employed: The normalized mutual information [12], and the adjusted rand
index [13]. These two evaluation indices seek to measure the similarity
between two partitions on a dataset. Given a dataset $D$ with $N$ instances
and two partitions of these samples, namely the ground-truth partition
$P=\\{p_{1},p_{2},...,p_{K}\\}$ and the partition resulting from the label
propagation
$P^{{}^{\prime}}=\\{p_{1}^{{}^{\prime}},p_{2}^{{}^{\prime}},...,p_{K}^{{}^{\prime}}\\}$.
Let $n_{ij}=|p_{i}^{{}^{\prime}}\cap p_{j}|$ be the number of common nodes of
groups $p_{i}^{{}^{\prime}}$ and $p_{j}$, $b_{i}=\sum_{j=1}^{N}n_{ij}$ and
$d_{j}=\sum_{i=1}^{N}n_{ij}$.

The normalized mutual information is defined as :

NMI =
$\frac{2\sum_{i}\sum_{j}n_{ij}\log\frac{n_{ij}N}{b_{i}d_{j}}}{-\sum_{i}b_{i}\log\frac{b_{i}}{N}-\sum_{j}d_{j}\log\frac{d_{j}}{N}}$

The adjusted rand index is defined as :

ARI =
$\frac{\sum_{ij}\binom{n_{ij}}{2}-[\sum_{i}\binom{b_{i}}{2}\sum_{j}\binom{d_{j}}{2}]/\binom{N}{2}}{\frac{1}{2}[\sum_{i}\binom{b_{i}}{2}+\sum_{j}\binom{d_{j}}{2}]-[\sum_{i}\binom{b_{i}}{2}\sum_{j}\binom{d_{j}}{2}]/\binom{N}{2}}$

If the label propagation partition is close to the true partition, then its
NMI and ARI values are close to 1.

###  V-C Experimental protocol

The proposed algorithm were compared with three label propagation approaches,
including LP [36] and LS [37], which are the classical label propagation
algorithms, LNP [34], which is another label propagation algorithm with an
improved affinity matrix, and with CNMF[19] which is an NMF based constrained
clustering method and PLCC [20] which is a $k$-means based partition level
constrained clustering method. To compare the seven approaches, their related
parameters were specified as follows: Each of the compared algorithms LP, LS
and NLP, require a Gaussian function with a free parameter $\sigma$ to be
determined in order to built their affinity matrix. In the comparisons, each
of these three algorithms was tested with different values of $\sigma$, and
its best value corresponding to the highest NMI and ARI values on each dataset
was selected. The number of clusters $k$ was set equal to the true number of
classes on each dataset for CNMF and PLCC. The performance of a label
propagation approach depends on the available amount of prior information.
Thus, in the experiment, the amount of prior information data was set to 5,
15, 25, and 35 percent of the total number of samples in the datasets. The
performance of a label propagation approach depends also on the quality of
prior information. Therefore, in the experiment, given the amount of prior
information, all the six compared algorithms were run with $10$ different sets
of prior information to compute the average results for NMI and ARI on each
dataset. The comparison present also the average performances of each approach
over all the datasets.

###  V-D Experimental results

The following tables list the performance of the six approaches on all the
datasets. Experiments confirm that the prior information is able to improve
the labeling effectiveness, in fact, given a dataset, all the label
propagation and the partition level constrained clustering algorithms show a
growth in their performance with respect to both NMI and ARI, in parallel with
the increase of the amount of prior information. Furthermore, the tables show
that the proposed approach is clearly more accurate than LP, LS, NLP, CNMF,
and PLCC on all the tested datasets. The tables also present the average
results of each algorithm, which confirm that the proposed label propagation
approach based on optimal transport outperforms the other methods on all the
datasets, followed by LS, LP, NLP, PLCC and then CNMF, in that order.

This results are mainly attributed to the capacity of OTP to capture mush more
information than the other methods thanks to the enhanced affinity matrix
constructed by optimal transport. It is also worth noting that, the
performance of OTP lies in the fact that the incremental process take
advantage of

TABLE II: NMI values for Transductive Semi-supervised methods Datasets | Percent | LP | LS | LNP | CNMF | PLCC | OTP
---|---|---|---|---|---|---|---
| 5% | 0.7302 | 0.7354 | 0.6729 | 0.4561 | 0.5187 | 0.7372
| 15% | 0.8412 | 0.8442 | 0.7534 | 0.5274 | 0.5835 | 0.8447
Iris | 25% | 0.8584 | 0.8621 | 0.8269 | 0.5717 | 0.6489 | 0.8667
| 35% | 0.8621 | 0.8649 | 0.8314 | 0.6198 | 0.7067 | 0.8852
| 5% | 0.0991 | 0.1037 | 0.0721 | 0.0439 | 0.0828 | 0.1394
| 15% | 0.1519 | 0.1575 | 0.1091 | 0.1163 | 0.1390 | 0.2181
Heart | 25% | 0.2291 | 0.2472 | 0.1432 | 0.1858 | 0.2021 | 0.3683
| 35% | 0.3313 | 0.3546 | 0.2718 | 0.3087 | 0.3191 | 0.4374
| 5% | 0.2837 | 0.2895 | 0.2510 | 0.1329 | 0.2157 | 0.3786
| 15% | 0.3502 | 0.3535 | 0.3256 | 0.2278 | 0.3007 | 0.4676
Ionosphere | 25% | 0.3848 | 0.3911 | 0.3572 | 0.2605 | 0.3356 | 0.5000
| 35% | 0.3972 | 0.4014 | 0.3725 | 0.2892 | 0.3529 | 0.5383
| 5% | 0.7927 | 0.8054 | 0.7785 | 0.5197 | 0.6665 | 0.8159
| 15% | 0.8770 | 0.8779 | 0.8349 | 0.5531 | 0.6991 | 0.8935
Dermatology | 25% | 0.8932 | 0.8932 | 0.8692 | 0.6238 | 0.7201 | 0.9033
| 35% | 0.9128 | 0.9128 | 0.8959 | 0.6703 | 0.7732 | 0.9164
| 5% | 0.4102 | 0.4184 | 0.3981 | 0.1829 | 0.2761 | 0.4493
| 15% | 0.4950 | 0.5009 | 0.4628 | 0.2453 | 0.3191 | 0.5256
Waveform | 25% | 0.5124 | 0.5192 | 0.4763 | 0.2619 | 0.3307 | 0.5319
| 35% | 0.5192 | 0.5229 | 0.4807 | 0.2792 | 0.3391 | 0.5421
| 5% | 0.8319 | 0.8319 | 0.7850 | 0.1471 | 0.6798 | 0.8571
| 15% | 0.9150 | 0.9150 | 0.8891 | 0.1617 | 0.7412 | 0.9290
Digits | 25% | 0.9443 | 0.9443 | 0.9268 | 0.2435 | 0.7801 | 0.9489
| 35% | 0.9570 | 0.9570 | 0.9318 | 0.3174 | 0.7956 | 0.9607
| 5% | 0.7429 | 0.7436 | 0.7005 | 0.1037 | 0.5616 | 0.7581
| 15% | 0.8019 | 0.8028 | 0.7759 | 0.2452 | 0.6329 | 0.8177
MNIST | 25% | 0.8389 | 0.8367 | 0.7931 | 0.2912 | 0.6506 | 0.8442
| 35% | 0.8542 | 0.8599 | 0.8136 | 0.3201 | 0.6711 | 0.8730
ALL Datasets | Average | 0.6363 | 0.6409 | 0.5999 | 0.3180 | 0.5015 | 0.6767
TABLE III: ARI values for Transductive Semi-supervised methods Datasets | Percent | LP | LS | LNP | CNMF | PLCC | OTP
---|---|---|---|---|---|---|---
| 5% | 0.7481 | 0.7428 | 0.7062 | 0.4165 | 0.4725 | 0.7582
| 15% | 0.8453 | 0.8492 | 0.7861 | 0.4986 | 0.5403 | 0.8621
Iris | 25% | 0.8680 | 0.8704 | 0.8321 | 0.5215 | 0.6029 | 0.8884
| 35% | 0.8754 | 0.8783 | 0.8424 | 0.5791 | 0.6471 | 0.9027
| 5% | 0.1385 | 0.1120 | 0.0892 | 0.0938 | 0.1108 | 0.1694
| 15% | 0.2110 | 0.2190 | 0.1562 | 0.1492 | 0.1979 | 0.2475
Heart | 25% | 0.3176 | 0.2955 | 0.2283 | 0.2201 | 0.2593 | 0.4162
| 35% | 0.4163 | 0.4464 | 0.3688 | 0.3350 | 0.3728 | 0.5030
| 5% | 0.3081 | 0.3124 | 0.2828 | 0.1625 | 0.2752 | 0.5089
| 15% | 0.4221 | 0.4248 | 0.3998 | 0.2541 | 0.3491 | 0.5723
Ionosphere | 25% | 0.4606 | 0.4673 | 0.4324 | 0.3005 | 0.3491 | 0.5927
| 35% | 0.4650 | 0.4702 | 0.4418 | 0.3217 | 0.3902 | 0.6281
| 5% | 0.7834 | 0.8121 | 0.7808 | 0.5360 | 0.6826 | 0.8289
| 15% | 0.8807 | 0.8813 | 0.8438 | 0.5725 | 0.7174 | 0.8996
Dermatology | 25% | 0.8972 | 0.8972 | 0.8751 | 0.6401 | 0.7486 | 0.9093
| 35% | 0.9146 | 0.9146 | 0.9007 | 0.6935 | 0.7910 | 0.9218
| 5% | 0.4728 | 0.4771 | 0.4494 | 0.2201 | 0.3025 | 0.5084
| 15% | 0.5639 | 0.5678 | 0.5163 | 0.2819 | 0.3486 | 0.5945
Waveform | 25% | 0.5819 | 0.5864 | 0.5279 | 0.3059 | 0.3618 | 0.6031
| 35% | 0.5870 | 0.5880 | 0.5342 | 0.3242 | 0.3745 | 0.6182
| 5% | 0.8290 | 0.8290 | 0.7964 | 0.0982 | 0.6169 | 0.8684
| 15% | 0.9126 | 0.9127 | 0.8993 | 0.1174 | 0.6931 | 0.9306
Digits | 25% | 0.9432 | 0.9432 | 0.9287 | 0.1834 | 0.7306 | 0.9508
| 35% | 0.9567 | 0.9567 | 0.9407 | 0.2587 | 0.7294 | 0.9621
| 5% | 0.7510 | 0.7523 | 0.7106 | 0.0539 | 0.4518 | 0.7763
| 15% | 0.7930 | 0.7944 | 0.7697 | 0.0970 | 0.5692 | 0.8393
MNIST | 25% | 0.8487 | 0.8466 | 0.8152 | 0.1193 | 0.5927 | 0.8685
| 35% | 0.8721 | 0.8777 | 0.8438 | 0.1452 | 0.6201 | 0.8935
ALL Datasets | Average | 0.6665 | 0.6687 | 0.5467 | 0.2674 | 0.4963 | 0.7151

the dependency of label propagation algorithms on the amount of prior
information, then the enrichment of the labeled set at each iteration with new
instances, allows to the unlabeled samples to be labeled with a high degree of
certainty at next iterations. We can also explain the improvement provided by
our approach to its ability to control the certitude of the label predictions
thanks to the certainty score used, which allows to data points to be labeled
only if they have a high degree of prediction certainty.

##  VI CONCLUSION

In this paper we proposed OTP, a novel method dealing with transductive semi-
supervised learning notably label propagation problem. Our method is
principally different from other label propagation methods and consists in
inferring an improved affinity matrix from the optimal transport plan between
labeled and unlabeled instances. An incremental procedure was used to take
advantage of the dependency of label propagation methods to the amount of
prior information, and a certainty score was incorporated to assure the
certainty of predictions during the label propagation process. Experiments
have shown that OTP approach outperforms current state-of-the-art methods. In
the future, we plan to extend OTP to inductive settings and to use the pseudo-
labels inferred by OTP with the initial labeled data to train a CNN model in a
deep semi-supervised manner for computer vision tasks.

## References

  * [1] Armen S Asratian, Tristan MJ Denley, and Roland Häggkvist.  Bipartite graphs and their applications, volume 131.  Cambridge university press, 1998.
  * [2] Edoardo Barba, Luigi Procopio, Niccolo Campolungo, Tommaso Pasini, and Roberto Navigli.  Mulan: Multilingual label propagation for word sense disambiguation.  In Proc. of IJCAI, pages 3837–3844, 2020.
  * [3] Dimitris Bertsimas and John N Tsitsiklis.  Introduction to linear optimization, volume 6.  Athena Scientific Belmont, MA, 1997.
  * [4] Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna.  Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks.  In Proceedings of the 20th international conference on World wide web, pages 587–596, 2011.
  * [5] Fatima Ezzahraa Ben Bouazza, Younès Bennani, Guénaël Cabanes, and Abdelfettah Touzani.  Collaborative clustering through optimal transport.  In International Conference on Artificial Neural Networks, pages 873–885. Springer, 2020.
  * [6] Fatima Ezzahraa Ben Bouazza, Younès Bennani, Mourad El Hamri, Guénaël Cabanes, Basarab Matei, and Abdelfettah Touzani.  Multi-view clustering through optimal transport.  Aust. J. Intell. Inf. Process. Syst., 15(3):1–9, 2019.
  * [7] Fabricio Breve.  Interactive image segmentation using label propagation through complex networks.  Expert Systems With Applications, 123:18–33, 2019.
  * [8] Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien.  Semi-supervised learning (chapelle, o. et al., eds.; 2006)[book reviews].  IEEE Transactions on Neural Networks, 20(3):542–542, 2009.
  * [9] Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy.  Joint distribution optimal transportation for domain adaptation.  In Advances in Neural Information Processing Systems, 2017.
  * [10] Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamonjy.  Optimal transport for domain adaptation.  IEEE transactions on pattern analysis and machine intelligence, 39(9):1853–1865, 2016.
  * [11] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In Advances in neural information processing systems, pages 2292–2300, 2013.
  * [12] Byron E Dom.  An information-theoretic external cluster-validity measure.  2012\.
  * [13] Lawrence Hubert and Phipps Arabie.  Comparing partitions.  Journal of classification, 2(1):193–218, 1985.
  * [14] Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum.  Label propagation for deep semi-supervised learning.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5070–5079, 2019.
  * [15] Leonid Vitalievich Kantorovich.  On the translocation of masses.  In Dokl. Akad. Nauk. USSR (NS), volume 37, pages 199–201, 1942\.
  * [16] Philip A Knight.  The sinkhorn–knopp algorithm: convergence and applications.  SIAM Journal on Matrix Analysis and Applications, 30(1):261–275, 2008.
  * [17] Charlotte Laclau, Ievgen Redko, Basarab Matei, Younes Bennani, and Vincent Brault.  Co-clustering through optimal transport.  arXiv preprint arXiv:1705.06189, 2017.
  * [18] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 521(7553):436–444, 2015.
  * [19] Haifeng Liu and Zhaohui Wu.  Non-negative matrix factorization with constraints.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, 2010.
  * [20] Hongfu Liu, Zhiqiang Tao, and Yun Fu.  Partition level constrained clustering.  IEEE transactions on pattern analysis and machine intelligence, 40(10):2469–2483, 2017.
  * [21] SC Martin Arjovsky and Leon Bottou.  Wasserstein generative adversarial networks.  In Proceedings of the 34 th International Conference on Machine Learning, Sydney, Australia, 2017.
  * [22] Gaspard Monge.  Mémoire sur la théorie des déblais et des remblais.  Histoire de l’Académie Royale des Sciences de Paris, 1781.
  * [23] Arkadi Nemirovski and Uriel Rothblum.  On complexity of matrix scaling.  Linear Algebra and its Applications, 302:435–460, 1999.
  * [24] Ofir Pele and Michael Werman.  Fast and robust earth mover’s distances.  In 2009 IEEE 12th International Conference on Computer Vision, pages 460–467. IEEE, 2009.
  * [25] Gabriel Peyré, Marco Cuturi, et al.  Computational optimal transport: With applications to data science.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * [26] Ievgen Redko, Nicolas Courty, Rémi Flamary, and Devis Tuia.  Optimal transport for multi-source domain adaptation under target shift.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 849–858. PMLR, 2019.
  * [27] Ievgen Redko, Amaury Habrard, and Marc Sebban.  Theoretical analysis of domain adaptation with optimal transport.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 737–753. Springer, 2017.
  * [28] Filippo Santambrogio.  Optimal transport for applied mathematicians.  Birkäuser, NY, 55(58-63):94, 2015.
  * [29] Claude Elwood Shannon.  A mathematical theory of communication.  ACM SIGMOBILE mobile computing and communications review, 5(1):3–55, 2001.
  * [30] Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher.  Wasserstein propagation for semi-supervised learning.  In International Conference on Machine Learning, pages 306–314, 2014.
  * [31] Fariborz Taherkhani, Ali Dabouei, Sobhan Soleymani, Jeremy Dawson, and Nasser M Nasrabadi.  Transporting labels via hierarchical optimal transport for semi-supervised learning.  In European Conference on Computer Vision, pages 509–526. Springer, 2020.
  * [32] Jesper E Van Engelen and Holger H Hoos.  A survey on semi-supervised learning.  Machine Learning, 109(2):373–440, 2020.
  * [33] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer Science & Business Media, 2008.
  * [34] Fei Wang and Changshui Zhang.  Label propagation through linear neighborhoods.  IEEE Transactions on Knowledge and Data Engineering, 20(1):55–67, 2007.
  * [35] Xian-Kun Zhang, Jing Ren, Chen Song, Jia Jia, and Qian Zhang.  Label propagation algorithm for community detection based on node importance and label influence.  Physics Letters A, 381(33):2691–2698, 2017.
  * [36] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf.  Learning with local and global consistency.  Advances in neural information processing systems, 16:321–328, 2003\.
  * [37] Xiaojin Zhu and Zoubin Ghahramani.  Learning from labeled and unlabeled data with label propagation.  2002\.
  * [38] Xiaojin Jerry Zhu.  Semi-supervised learning literature survey.  Technical report, University of Wisconsin-Madison Department of Computer Sciences, 2005.