text:
\section{Introduction}

Let $\Omega\subset\R^N$ be a bounded domain with smooth boundary and $f:\R\to\R$ be a $C^1$ function with $f(-t)=-f(t)$. Consider the following problem
$$
\left\{
\begin{array}{rcl} -\Delta u&=&f(u),~  \mbox{in}~~ \Omega, \\[0.2cm]
\mathcal{B}u&=&0,~\mbox{on}~~ \partial \Omega,
\end{array}
\right. \eqno (P)
$$
when $N\geq 4$, $\mathcal{B}u=u$ and $f(t)=|t|^{\frac{4}{N-2}}+\lambda t$, Br\'ezis-Niremberg \cite{BN} proved that $(P)$ admits a non-trivial positive solution, provided $0<f'(0)<\lambda_1(\Omega)$, where $\lambda_1(\Omega)$ is the first eigenvalue of $(-\Delta,H_0^1(\Omega))$. In \cite{CSS}, Cerami-Solimini-Struwe proved that if $N\geq 6$, problem $(P)$ admits a solution with changes sign. Using this, they also proved that when $n\geq 7$ and $\Omega$ is a ball, $(P)$ admits infinitely many radial solution which change sign.

Comte and Knaap \cite{CK} obtained infinitely many non-radial solutions that change sign
for $(P)$ on a ball with Neumann boundary condition $\mathcal{B}u=\frac{\partial u}{\partial\nu}$, for every $\lambda\in\R$. They obtained such solutions by cutting the unit ball into angular sectors. This approach was used by Cao-Han \cite{CH}, where the authors dealt with
the scalar problem $(P)$ involving lower-order perturbation and by de Morais Filho et al. \cite{MMF}  to obtain multiplicity results for a class of critical elliptic systems
related to the Br\'ezis-Nirenberg problem with the Neumann boundary condition on a ball.

When $N=2$, the notion of ``critical growth'' is not given by the Sobolev imbedding, but by the {\it Trudinger-Moser inequality} (see \cite{T} and \cite{M}), which claims that for any  $ u \in H^{1}_0(\Omega)$,
\begin{equation} \label{X0}
\int_{\Omega}
e^{\alpha u^2}dx
< +\infty, \,\,\,\, \mbox{ for every }\,\,\alpha >0.
\end{equation}
Moreover, there exists a positive constant $C=C(\alpha,|\Omega|)$ such that
\begin{equation} \label{X1}
\sup_{||u||_{H_0^{1}(\Omega)} \leq 1} \int_{\Omega} e^{\alpha u^2} dx \leq C , \,\,\,\,\,\,\, \forall \, \alpha  \leq 4 \pi .
\end{equation}

Motivated by inequality in $(\ref{X1})$, we say that the nonlinearity $f$ has exponential critical growth if $f$ behaves like $e^{\alpha_0s^2}$, as $|s|\to\infty$, for some $\alpha_0>0$. More precisely,
$$
\lim_{|s|\to\infty}\dfrac{|f(s)|}{e^{\alpha s^2}}=0,~~\forall\alpha>\alpha_0~~\mbox{and}~~\lim_{|s|\to\infty}\dfrac{|f(s)|}{e^{\alpha s^2}}=+\infty~~\forall\alpha<\alpha_0.
$$
In this case, Adimurthi \cite{Ad} proved that $(P)$ admits a positive solution, provided that $\displaystyle\lim_{t\to\infty}tf(t)e^{\alpha t^2}=+\infty$ (See also Figueiredo-Miyagaki-Ruf \cite{DOR} for a more weaker condition). In \cite{AY}, Adimurthi-Yadava proved that $(P)$ has a solution that changes sign, and when $\Omega$ is a ball in $\R^2$, $(P)$ has infinitely many radial solutions that change sign. Inspired in \cite{CK}, this paper is concerned with the existence of infinitely many non-radial sign changing solutions for $(P)$ when $f$ has exponential critical growth and $\Omega$ is a ball in $\R^2$. Our main result complements the studies made in $\cite{CK}$ and \cite{MMF}, because we consider the case where $f$ has critical exponential growth in $\R^2$. It is important to notice that in both studies mentioned above was
considered the Neumann boundary condition in order that the Pohozaev identity (see \cite{P}) ensures that the problem $(P)$ with the
Dirichlet boundary condition, has no solutions for $\lambda<0$ and $N\geq 3$. Since the Pohozaev identity is not available in dimension two, in our case we can use the Dirichlet boundary condition.

Here we suppose the following assumptions
\begin{enumerate}

\item[$(f_1)$] There is $C>0$ such that
$$
|f(s)|\leq Ce^{4\pi |s|^2}\ \ \mbox{for all}\ \ s\in\R;
$$

\item[$(f_2)$] $\displaystyle\lim_{s\rightarrow
0}\dfrac{f(s)}{s}=0$;

\item[$(H_1)$] There are $s_0>0$ and $M>0$ such that
$$
0< F(s):=\int_0^{s}f(t)dt\leq M|f(s)|,~ \mbox{for all}\ \|s|\geq s_0.
$$

\item[$(H_2)$] $0<F(s)\leq\dfrac{1}{2}f(s)s,\ \ \mbox{for all}\ \ s\in\R\setminus\{0\}.$

\item[$(H_3)$] $\displaystyle\lim_{s\to\infty} sf(s)e^{-4\pi s^2}=+\infty$
\end{enumerate}

Our main  result is the following:

\begin{theorem}\label{sb}
Let $f$ be an odd and continuous function satisfying $(f_1)-(f_2)$ and $(H_1)-(H_3)$. Then, problem $(P)$ has infinitely many sign-changing solutions.
\end{theorem}

\section{ Notation and auxiliary results}
For each $m\in\mathbb{N}$, we define
$$
A_m=\left\{x=(x_1,x_2)\in B:~~
cos\left(\dfrac{\pi}{2^m}\right)|x_1|<sen\left(\dfrac{\pi}{2^m}\right)x_2\right\}.
$$
So $A_1$ is a half-ball, $A_2$ an angular sector of angle $\pi/2$, and $A_3$ an angular sector of angle $\pi/4$ and so on (see figure \ref{dddd}).

\begin{figure}[!htb]
\begin{center}
\includegraphics[scale=0.3]{dddd}
\end{center}
\caption{Angular sector $A_m$.}
\label{dddd}
\end{figure}

Using the above notation, we consider the following auxiliary Dirichlet problem
$$
\left\{
\begin{array}{rcl} -\Delta u&=&f(u),~  \mbox{in}~~ A_m, \\[0.2cm]
u&=&0,~\mbox{on}~~ \partial A_m,
\end{array}
\right. \eqno (P)_m
$$
We will use the Mountain Pass Theorem to obtain a positive solution of $(P)_m$. Using this solution together with an anti-symmetric principle, we construct a sign-changing solution of problem $(P)$.

According to Figueiredo, Miyagaki and Ruf \cite{DOR}, to obtain a positive solution of $(P)_m$ it is sufficient to assume that the limit in $(H_3)$ verifies
$$
(H_3)'~~~\lim_{s\to+\infty}sf(s)e^{-4\pi s^2}\geq\beta>\dfrac{1}{2\pi d_m^2},
$$
where $d_m$ is the radius of the largest open ball contained in $A_m$. The hypothesis $ (H_3) $ was initially considered in Adimurthi \cite{Ad}. This hypothesis will be fundamental to ensure not only the existence but also the multiplicity of sign-changing solutions. As we will see bellow, assuming $(H_3)$ in place of $(H_3)'$, we have the existence of positive solution of $(P)_m$, for every $m\in\mathbb{N}$. This is the content of the next result.

\begin{theorem}\label{th1}
Under the assumptions $(f_1)-(f_2)$ and $(H_1)-(H_3)$, problem $(P)_m$ has a positive solution, for every $m\in\mathbb{N}$.
\end{theorem}

\section{Proof of Theorem \ref{th1}.}

Since we are interested in positive solutions to the problem $(P)_m$, we assume that
$$
f(s)=0,~~~\forall s\leq 0.
$$

Associated with problem $(P)_m$, we have the functional $I: H_0^1(A_m)\to\R$ given by
$$
I(u)=\dfrac{1}{2}\int_{A_m}|\nabla u|^2-\int_{A_m}F(u).
$$
In our case, $\partial A_m$ is not of class $C^1$. However, the functional
$I$ is well defined. In fact, for each $u\in H_0^1(A_m)$, let us consider
$u^{*}\in H_0^1(B)$ the zero extension of $u$ in $B$ defined by
$$
u^{*}(x)=\left\{
\begin{array}{cc}
u(x),& \mbox{if}~~~x\in A_m\\
0,& \mbox{if}~~~x\in B\setminus A_m.
\end{array}
\right.
$$
Clearly
$$
\|u\|_{A_m}=\|u^{*}\|_{B}.
$$
Then, from $(f_1)$ and the Trudinger-Moser inequality (\ref{X0})
$$
\left|\int_{A_m}F(u)\right|=\left|\int_{B}F(u^{*})\right|\leq
\int_{B}|F(u^{*})|\leq C\int_{B}e^{4\pi|u^{*}|^2}<\infty.
$$
Moreover, using a standard argument we can prove that the functional $I$ is of class $C^1$ with
$$
I'(u)v=\int_{A_m}\nabla u\nabla v-\int_{A_m}f(u)v,~~~\forall u,v\in
H_0^1(A_m).
$$
Therefore, critical points of $I$ are precisely the weak solutions of $(P_m)$.

The next lemma ensures that the functional $I$ has the mountain pass geometry.

\begin{lemma}\label{mpg}

\begin{enumerate}

\item[$(a)$] There exist $r,\rho>0$ such that
$$
I(u)\geq\rho>0,~~ \mbox{for all}~~\|u\|_{A_m}=r.
$$
\item[$(b)$] There is $e\in H_0^1(A_m)$ such that
$$
\|e\|_{A_m}>r~~~\mbox{and}~~~ I(e)<0.
$$
\end{enumerate}

\end{lemma}

\noindent{\bf Proof.} Using the definition of $I$ and the growth of $f$, we obtain
$$
I(u)\geq\dfrac{1}{2}\int_{A_m}|\nabla
u|^2-\dfrac{\epsilon}{2}\int_{A_m}|u|^2-C\int_{A_m}|u|^qe^{\beta|u|^2},
$$
or equivalently,
$$
I(u)\geq\dfrac{1}{2}\int_{B}|\nabla
u^{*}|^2-\dfrac{\epsilon}{2}\int_{B}|u^{*}|^2-C\int_{B}|u^{*}|^qe^{\beta|u^{*}|^2}.
$$
By the Poincaré inequality,
$$
I(u)\geq\dfrac{1}{2}\int_{B}|\nabla
u^{*}|^2-\dfrac{\epsilon}{2\lambda_1}\int_{B}|\nabla
u^{*}|^2-C\int_{B}|u^{*}|^qe^{\beta|u^{*}|^2},
$$
where $\lambda_1$ is the first eigenvalue of $(-\Delta, H_0^1(B))$.
Fixing $\epsilon>0$ sufficiently small, we have
$C_1:=\dfrac{1}{2}-\dfrac{\epsilon}{2\lambda_1}>0$, from where it follows that
$$
I(u)\geq C_1\int_{B}|\nabla
u^{*}|^2-C\int_B|u^{*}|^qe^{\beta|u^{*}|^2}.
$$
Notice that, from Trudinger-Moser inequality (\ref{X1})
$$
e^{\beta|u^{*}|^2}\in L^2(B)
$$
and by continuous embedding
$$
|u^{*}|^q\in L^2(B).
$$
Since $H_0^1(B)\hookrightarrow L^{2q}(B)$ for all $q\geq 1$, by H\"older inequality
$$
\begin{array}{rl}
\displaystyle\int_B|u^{*}|^qe^{\beta|u^{*}|^2}&\leq\left(\displaystyle\int_B|u^{*}|^{2q}\right)^{1/2}\left(e^{2\beta|u^{*}|^2}\right)^{1/2}\\[0.3cm]
&\leq |u^{*}|_{2q,B}^q\left(\displaystyle\int_B e^{2\beta|u^{*}|^2}\right)^{1/2}\\[0.3cm]
&\leq C\|u^{*}\|_B^q\left(\displaystyle\int_B
e^{2\beta|u^{*}|^2}\right)^{1/2}.
\end{array}
$$

We claim that for $r>0$ small enough, we have
$$
\sup_{\|u^{*}\|_B=r}\int_Be^{2\beta|u^{*}|^2}<\infty.
$$
In fact, note that
$$
\int_Be^{2\beta|u^{*}|^2}=\int_Be^{2\beta\|u^{*}\|_B^2\left(\frac{|u^{*}|}{\|u^{*}\|_B}\right)^2}.
$$
Choosing $0<r\approx 0$ such that $\alpha:=2\beta r^2<4\pi$ and using the Trudinger-Moser inequality (\ref{X1}),
$$
\sup_{\|u^{*}\|_B=r}\int_Be^{2\beta |u^{*}|^2}\leq\sup_{\|v\|_B\leq
1}\int_Be^{\alpha|v|^2}<\infty.
$$
Thus,
$$
I(u)\geq C_1\|u^{*}\|_B^2-C_2\|u^{*}\|_B^q.
$$
Fixing $q>2$, we derive
$$
I(u)\geq C_1r^2-C_2r^q:=\rho>0,
$$
for $r=\|u\|_{A_m}=\|u^{*}\|_B$ small enough, which shows that the item $(a)$ holds.

To prove $(b)$, first notice that

\noindent{\bf Claim 1.} For each $\epsilon>0$, there exists $\overline{s}_\epsilon>0$ such that
$$
F(s)\leq\epsilon f(s)s,~\mbox{for all}~ x\in A_m,~|s|\geq \overline{s}_\epsilon.
$$
In fact, from hypothesis $(H_1)$
$$
\left|\dfrac{F(s)}{sf(s)}\right|\leq\dfrac{M}{|s|},~\forall |s|\geq s_0.
$$
For $p>2$, the claim $1$ with $\epsilon=1/p>0$, guarantees the existence of $\overline{s}_\epsilon>0$ such that
$$
pF(s)\leq f(s)s,~\forall s\geq \overline{s}_\epsilon,
$$
which implies the existence of constant $C_1,C_2>0$ verifying
$$
F(s)\geq C_1|s|^{p}-C_2,~\forall s\geq 0.
$$
Thus, fixing $\varphi\in C_0^\infty(A_m)$ with $\varphi\geq 0$ and
$\varphi\neq 0$. For $t\geq 0$, we have
$$
\begin{array}{rl}
\displaystyle\int_{A_m}F(t\varphi)&\geq\displaystyle\int_{A_m}\left(C_1|t\varphi|^{p}-C_2\right)\\[0.3cm]
&\geq C_1|t|^{p}\displaystyle\int_{A_m}|\varphi|-C_2|A_m|,
\end{array}
$$
from where it follows that
\begin{equation}\label{4.1}
\int_{A_m}F(t\varphi)\geq C_3|t|^{p}-C_4.
\end{equation}
From $(\ref{4.1})$, if $t\geq 0$,
$$
I(t\varphi)\leq
\dfrac{t^2}{2}\|\varphi\|_{A_m}^2-C_3|t|^{p}+C_4.
$$
Since $p>2$,
$$
I(t\varphi)\to-\infty,~~~\mbox{as}~~~t\to +\infty.
$$
Fixing $t_0\approx+\infty$ and let $e=t_0\varphi$, we get
$$
\|e\|_{A_m}\geq r~~~\mbox{and}~~~I(e)<0.~~\hbox{\fim}
$$

The next lemma is crucial to prove that the energy functional $I$ satisfies the Palais-Smale condition and its proof can be found in \cite{DOR}.
\begin{lemma}\label{1.6}
Let $\Omega\subset\R^N$ be a bounded domain and $(u_n)$ be a sequence of functions in $L^1(\Omega)$ such that $u_n$ converging to $u\in L^1(\Omega)$ in $L^1(\Omega)$. Assume that $f(u_n(x))$ and $f(u(x))$ are also $L^1$ functions. If
$$
\int_\Omega|f(u_n)u_n|\leq C,~~~\mbox{para todo}~~~n\in\mathbb{N},
$$
then $f(u_n)$ converges in $L^1(\Omega)$ to $f(u)$.

\end{lemma}

\begin{lemma}\label{ld}
The functional $I$ satifies $(PS)_d$ condition, for all
$d\in(0,1/2)$.
\end{lemma}

\noindent {\bf Proof.} Let $d<1/2$ and $(u_n)$ be a $(PS)_d$ sequence for the functional $I$, i.e.,
$$
I(u_n)\to d~~~ \mbox{and}~~~I'(u_n)\to 0, ~\mbox{as}~ n\to+\infty.
$$
For each $n\in\mathbb{N}$, let us define $\epsilon_n=\displaystyle\sup_{\|v\|\geq 1}\{|I'(u_n)v|\}$, then
$$
|I'(u_n)v|\leq \epsilon_n\|v\|_m,
$$
for all $v\in H_0^1(A_m)$, where $\epsilon_n=o_n(1)$. Thus
\begin{equation}\label{d1}
\dfrac{1}{2}\int_{A_m}|\nabla u_n|^2-\int_{A_m}F(u_n)=d+o_n(1),~~~\forall n\in\mathbb{N}
\end{equation}
and
\begin{equation}\label{d2}
\left|\int_{A_m}\nabla u_n\nabla v-\int_{A_m}f(u_n)v\right|\leq\|v\|_m\epsilon_n,~~ \forall n\in\mathbb{N},~~v\in H_0^1(A_m).
\end{equation}
From $(\ref{d1})$ and Claim $1$, for any $\epsilon>0$, there is $n_0\in\mathbb{N}$ such that
$$
\dfrac{1}{2}\|u_n\|_m^2=\dfrac{1}{2}\int_{A_m}|\nabla u_n|^2\leq\epsilon+d+\int_{A_m}F(u_n)\leq C_\epsilon+\epsilon\int_{A_m}f(u_n)u_n,
$$
for all $n\geq n_0$. Using $(\ref{d2})$ with $v=u_n$, we get
$$
\left(\dfrac{1}{2}-\epsilon\right)\|u_n\|^2_m\leq C_\epsilon+\epsilon\|u_n\|_m,~\forall n\geq n_0.
$$
Thus, the sequence $(u_n)$ is bounded. Since $H_0^1(A_m)$ be a reflexive Banach space, there exits $u\in H_0^1(A_m)$ such that, for some subsequence,
$$
u_n\rightharpoonup u~~~\mbox{in}~~~ H_0^1(A_m).
$$
Furthermore, from compact embedding,
$$
u_n\to u~~~\mbox{in}~~~ L^q(A_m),~q\geq 1
$$
and
$$
u_n(x)\to u(x)~~~\mbox{a.e. in}~~~ A_m.
$$
On the other hand, using $(\ref{d2})$ with $v=u_n$, we get
$$
-\epsilon_n\|u_n\|_m\leq\int_{A_m}|\nabla u_n|^2-\int_{A_m}f(u_n)u_n,
$$
which implies
$$
\int_{A_m}f(u_n)u_n\leq\|u_n\|_m^2-\epsilon_n\|u_n\|_m\leq C, ~~\forall n\in\mathbb{N}.
$$
From Lemma \ref{1.6}, $f(u_n)\to f(u)$ in $L^1(A_m)$. Then, there is $h\in L^1(A_m)$ such that
$$
|f(u_n(x))|\leq h(x),~\mbox{a.e. in}~ A_m,
$$
and from $(H_1)$,
$$
|F(u_n)|\leq M h(x),~\mbox{a.e. in}~ A_m.
$$
Furthermore,
$$
F(u_n(x))\to F(u(x))~~\mbox{a.e. in}~~ A_m.
$$
Consequently, by the Lebesgue's dominated convergence,
$$
\int_{A_m}F(u_n)-\int_{A_m}F(u)=o_n(1).
$$
Thus, from $(\ref{d1})$,
$$
\dfrac{1}{2}\|u_n\|_m^2-\int_{A_m}F(u)-d=o_n(1),
$$
which implies,
\begin{equation}\label{d3}
\lim_{n\to\infty}\|u_n\|_m^2=2\left(d+\int_{A_m}F(u)\right).
\end{equation}
Using again $(\ref{d2})$ with $v=u_n$, we obtain
$$
\left|\|u_n\|_m^2-\int_{A_m}f(u_n)u_n\right|\leq o_n(1),
$$
from where we derive
$$
\begin{array}{lll}
\left|\displaystyle\int_{A_m}f(u_n)u_n-2\left(d+\displaystyle\int_{A_m}F(u)\right)\right|&\leq
\left|\|u_n\|_m^2-\displaystyle\int_{A_m}f(u_n)u_n\right|\\[0.3cm]
&+\left|\|u_n\|_m^2-2\left(d+\displaystyle\int_{A_m}F(u)\right)\right|.
\end{array}
$$
Then,
$$
\lim_{n\to\infty}\int_{A_m}f(u_n)u_n=2\left(d+\int_{A_m}F(u)\right).
$$
Furthermore, from $(H_2)$,
$$
\begin{array}{ll}
2\displaystyle\int_{A_m}F(u)&\leq 2\displaystyle\lim_{n\to\infty}\displaystyle\int_{A_m}F(u_n)\\[0.3cm]
&\leq\displaystyle\lim_{n\to\infty}\displaystyle\int_{A_m}f(u_n)u_n=2d+2\displaystyle\int_{A_m}F(u),
\end{array}
$$
which implies that $d\geq 0$.

\noindent{\bf Claim 2.} For any $v\in H_0^{1}(A_m)$,
$$
\int_{A_m}\nabla u\nabla v=\int_{A_m}f(u)v.
$$
In fact, let us fix $v\in H_0^{1}(A_m)$ and notice that
$$
\begin{array}{ll}
\left|\displaystyle\int_{A_m}\!\!\!\nabla u\nabla v-\displaystyle\int_{A_m}\!\!\!f(u)v\right|\!\!\!&\leq\left|\displaystyle\int_{A_m}\!\!\!\nabla u_n\nabla v-\displaystyle\int_{A_m}\!\!\!\nabla u\nabla v\right|+\left|\displaystyle\int_{A_m}\!\!\!f(u_n)v-\displaystyle\int_{A_m}\!\!\!f(u)v\right|\\[0.3cm]
&+\left|\displaystyle\int_{A_m}\!\!\!\nabla u_n\nabla v-\displaystyle\int_{A_m}\!\!\!f(u_n)v\right|.
\end{array}
$$
Using Lemma \ref{1.6}, the weak convergence $u_n\rightharpoonup u$ in $H_0^1(A_m)$ and the estimate in $(\ref{d2})$, we derive
$$
\left|\int_{A_m}\nabla u\nabla v-\int_{A_m}f(u) v\right|\leq o_n(1)+\|v\|o_n(1),
$$
and the proof of Claim 2 is complete.

Notice that from $(H_2)$ and Claim 2,
$$
J(u)\geq\dfrac{1}{2}\int_{A_m}|\nabla u|^2-\dfrac{1}{2}\int_{A_m}f(u)u=0.
$$

Now, We split the proof into three cases:

\noindent{\bf Case 1.} The level $d=0$. By the lower semicontinuity of the norm,
$$
\|u\|_m\leq\liminf_{n\to\infty}\|u_n\|_m,
$$
then
$$
\dfrac{1}{2}\|u\|_m^2\leq\dfrac{1}{2}\|u_n\|_m^2.
$$
Using $(\ref{d3})$,
$$
0\leq I(u)\leq\dfrac{1}{2}\liminf\|u_n\|^2-\int_{A_m}F(u),
$$
which implies
$$
0\leq I(u)\leq\int_{A_m}F(u)-\int_{A_m}F(u)=0,
$$
from where $I(u)=0$, or equivalently,
$$
\|u\|_m^2=2\int_{A_m}F(u).
$$
Using again $(\ref{d3})$, we derive
$$
\|u_n\|_m^2-\|u\|_m^2=o_n(1),
$$
since $H_0^1(A_m)$ be a Hilbert espace,
$$
u_n\to u~~\mbox{in}~~ H_0^1(A_m).
$$
Therefore, $I$ verifies the Palais-Smale at the level $d=0$.

\noindent{\bf Case 2.} The level $d\neq 0$ and the weak limit $u\equiv 0$.

We will show that this can not occur for a Palais-Smale sequence.

\noindent{\bf Claim 3.} There are $q>1$ and a constant $C>0$ such that
$$
\int_{A_m}|f(u_n)|^q<C,~\forall n\in\mathbb{N}.
$$
In fact, from $(\ref{d3})$, for each $\epsilon>0$
$$
\|u_n\|_m^2\leq 2d+\epsilon, ~\forall n\geq n_0,
$$
for some $n_0\in\mathbb{N}$. Furthermore, from $(f_1)$,
$$
\int_{A_m}|f(u_n)|^q\leq C\int_{A_m}e^{4\pi qu_n^2}=C\int_{B}e^{4\pi\|u_n^{*}\|^2(\frac{u_n}{\|u_n^{*}\|})^2}.
$$
By the Trudinger-Moser inequality (\ref{X1}), the last integral in the equality above is bounded if $4\pi q\|u_n^{*}\|^2<4\pi$ and this occur if we take $q>1$ suficiently close to $1$ and $\epsilon$ small enough, because $d<1/2$, which proves the claim.

Then, using $(\ref{d2})$ with $v=u_n$, we obtain
$$
\left|\int_{A_m}|\nabla u_n|^2-\int_{A_m}f(u_n)u_n \right|\leq\epsilon_n\|u_n\|_m\leq \epsilon_nC,~ \forall n\in\mathbb{N}.
$$
Thus,
\begin{equation}\label{d4}
\|u_n\|_m^2\leq o_n(1)+\int_{A_m}f(u_n)u_n,~ \forall n\in\mathbb{N}.
\end{equation}
Furthermore, from H\"older inequality, we can estimate the integral above as follows
$$
\int_{A_m}f(u_n)u_n\leq\left(\int_{A_m}|f(u_n)|^q\right)^{1/q}\left(\int_{A_m}|u_n|^{q'}\right)^{1/q'},~\forall n\in\mathbb{N},
$$
and since $u_n\to 0$ in $L^{q'}(A_m)$,
$$
\int_{A_m}f(u_n)u_n=o_n(1).
$$
Then, from $(\ref{d4})$,
\begin{equation}\label{vivo}
\|u_n\|_m^2\to 0,~\mbox{as}~n\to\infty,
\end{equation}
which contradicts $(\ref{d3})$, because
$$
\|u_n\|_m^2\to 2d\neq 0,~\mbox{as}~n\to\infty,
$$
proving that $d\neq 0$ and $u=0$ does not occur.

\noindent{\bf Case 3.} The level $d\neq 0$ and the weak limit $u\neq 0$. Since
$$
I(u)=\dfrac{1}{2}\|u\|_m^2-\int_{A_m}\!\!\!F(u)\leq\liminf_{n}\left(\dfrac{1}{2}\|u_n\|_m^2-\int_{A_m}\!\!\!F(u_n)\right)=d.
$$
we have $I(u)\leq d$.

\noindent{\bf Claim 4.} $I(u)=d$.

In fact, suppose by contradiction that $I(u)<d$, from definition of $I$,
\begin{equation}\label{d5}
\|u\|_m^2<2\left(d+\int_{A_m}\!\!\!F(u)\right).
\end{equation}
On the other hand, if we consider the functions
$$
v_n=\dfrac{u_n^{*}}{\|u_n^{*}\|},~ n\in\mathbb{N}
$$
and
$$
v=u^{*}\left[2\left(d+\int_{B}\!\!F(u^{*})\right)\right]^{-1/2},
$$
we have  $\|v_n\|_B=1$ e $\|v\|_B<1$. Furthermore, since
$$
\int_B\!\!\!\nabla v_n\nabla \varphi=\|u_n\|^{-1}\!\!\!\int_{A_m}\!\!\!\nabla u_n\nabla\varphi\to\left[2\left(d+\!\!\int_B\!\!F(u^{*})\right)\right]^{-1/2}\!\!\!\int_B\!\!\nabla u\nabla \varphi=\int_B\!\!\!\nabla v\nabla\varphi,
$$
for every $\varphi\in C_0^\infty(B)$, i.e.,
$$
\int_B\nabla v_n\nabla\varphi-\int_B\nabla v\nabla\varphi=o_n(1),
$$
we have
$$
v_n\rightharpoonup v~~\mbox{in}~~H_0^1(B).
$$

\begin{claim}\label{viv35} There are $q>1$ and $n_0\in\mathbb{N}$ such that
$$
\int_{A_m}|f(u_n)|^q<C,~\forall n\geq n_0.
$$
\end{claim}

To prove this, we need the following result due to P.L. Lions \cite{L}.

\begin{proposition}\label{c2}
Let $(u_n)$ be a sequence in $H_0^1(\Omega)$ such that $|\nabla u_n|_2=1$ for all $n\in\mathbb{N}$. Furthermore, suppose that $u_n\rightharpoonup u$ in $H_0^1(\Omega)$ with $|\nabla u|_2<1$. If $u\neq 0$, then for each $1<p<\dfrac{1}{1-|\nabla u|_2^2}$, we have
$$
\sup_{n\in\mathbb{N}}\int_{\Omega}e^{4\pi pu_n^2}<\infty.
$$
\end{proposition}

From hypothesis $(f_1)$,
\begin{equation}\label{viv31}
\int_{A_m}|f(u_n)|^q\leq C\int_{A_m}e^{4\pi q u_n^2}=C\int_Be^{4\pi q\|u_n^{*}\|^2v_n^2}.
\end{equation}
The last integral in the above expression  is bounded. In fact, by Proposition \ref{c2}, it is suffices to prove that there are $q,~p>1$ and $n_0\in\mathbb{N}$ such that
\begin{equation}\label{viv30}
 q\|u_n^{*}\|^2\leq p<\dfrac{1}{1-\|v\|^2},~~\forall n\geq n_0.
\end{equation}
To prove that (\ref{viv30}) occur, notice that $I(u)\geq 0$ and $d<1/2$, which implies that
$$
2<\dfrac{1}{d-I(u)},
$$
from where it follows that
$$
2\left(d+\int_BF(u^{*})\right)<\dfrac{d+\displaystyle\int_BF(u^{*})}{d-I(u)}=\dfrac{1}{1-\|v\|_B^2}.
$$
Thus, for $q>1$ sufficiently close to $1$,
$$
2q\left(d+\int_BF(u)\right)<\dfrac{1}{1-\|v\|_B^2}.
$$
From $(\ref{d3})$, there are $p>1$ and $n_0\in\mathbb{N}$ such that
$$
q\|u_n^{*}\|^2\leq p<\dfrac{1}{1-\|v\|_B^2},~\forall n\geq n_0.
$$
Thus, (\ref{viv30}) occur. Therefore, Claim \ref{viv35} holds.

Now, we will show that $u_n\to u$ in $H_0^1(A_m)$. First, notice that from H\"older inequality and (\ref{viv35}),
$$
\int_{A_m}\!\!\!f(u_n)(u_n-u)\leq\int_{A_m}\!\!\!\left(|f(u_n)|^q\right)^{1/q}\left(\int_{A_m}|u_n-u|^{q'}\right)^{1/q'}\leq C|u_n-u|_{q',A_m},
$$
where $1/q+1/q'=1$. Since $u_n\to u$ in $L^{q'}(A_m)$,
\begin{equation}\label{viv40}
\int_{A_m}\!\!\!f(u_n)(u_n-u)=o_n(1).
\end{equation}
Using $(\ref{d2})$ with $v=u_n-u$ and (\ref{viv40}), we obtain $\langle u_n-u,u_n\rangle=o_n(1)$, and since $u_n\rightharpoonup u$ in $H_0^1(A_m)$,
$$
\|u_n-u\|_m^2=\langle u_n-u,u_n\rangle-\langle u_n-u,u\rangle=o_n(1).
$$
Then, $\|u_n\|_m^2\to\|u\|_m^2$ and this together with $(\ref{d3})$ contradicts $(\ref{d5})$. Which proves that $I(u)=d$, i.e.,
$$
\|u\|_m^2=2\left(d+\int_{A_m}\!\!\!F(u)\right).
$$
Furthermore, from $(\ref{d3})$, $\|u_n\|_m\to\|u\|_m$ as $n\to \infty$. Therefore
$$
u_n\to u~~\mbox{em}~~ H_0^1(A_m).~\hbox{\fim}
$$

From Lemma \ref{mpg} and the Mountain pass Theorem without compactness conditions (see \cite{W}), there is a $(PS)_{c_m}$ sequence $(u_n)\subset
H_0^1(A_m)$ such that
$$
I(u_n)\to c_m~~~\mbox{and}~~~I'(u_n)\to 0,
$$
where
$$
c_m=\inf_{\gamma\in\Gamma}\max_{t\in[0,1]} I(\gamma(t))
$$
and
$$
\Gamma=\{\gamma\in C([0,1],H_0^1(A_m)):~ \gamma(0)=0~ \mbox{and}~I(\gamma(1))<0\}.
$$
To conclude the proof of existence of positive solution for $(P)_m$, it remains to show that $c_m\in(-\infty,1/2)$. For this, we introduce the following Moser's functions (see \cite{M}):
$$
\overline{w}_n(x)=\dfrac{1}{\sqrt{2\pi}}\left\{
\begin{array}{cc}
\left(ln(n)\right)^{1/2},& 0\leq|x|\leq 1/n\\[0.3cm]
\dfrac{ln\dfrac{1}{|x|}}{\left(ln(n)\right)^{1/2}},& 1/n\leq|x|\leq 1\\[0.7cm]
0,&|x|\geq 1
\end{array}\right.
$$
Let $d_m>0$ and $x_m\in A_m$ such that $B_{d_m}(x_m)\subset A_m$ and define
$$
w_n(x)=\overline{w}_n\left(\dfrac{x-x_m}{d_m}\right),
$$
we have $w_n\in H_0^1(A_m)$, $\|w_n\|_{A_m}=1$ and $supp~ w_n\subset
B_{d_m}(x_m)$.

We claim that the exists $n\in\mathbb{N}$ such that
$$
\max_{t\geq 0}I(tw_n)<\dfrac{1}{2}.
$$
In fact, suppose by contradition that this is not the case. Then, there exist $t_n>0$ such that
\begin{equation}\label{e1}
\max_{t\geq 0}I(tw_n)=I(t_nw_n)\geq \dfrac{1}{2}.
\end{equation}
It follows from $(\ref{e1})$ and $(H_1)$ that
\begin{equation}\label{e2}
t_n^2\geq 1.
\end{equation}
Furthermore, $\dfrac{d}{dt}I(tw_n)\left|_{t=t_n}\right.=0$, i.e.,
\begin{equation}\label{e5}
t_n^2=\int_{A_m}f(t_nw_n)t_nw_n,
\end{equation}
which implies that
\begin{equation}\label{e3}
t_n^2\geq\int_{B_{d_m/n}(x_m)}f(t_nw_n)t_nw_n.
\end{equation}
In what follows, we fix a positive constant $\beta_m$ verifying
\begin{equation}\label{eq7}
\beta_m>\dfrac{1}{2\pi d_m^2}.
\end{equation}
From $(H_3)$, there exists $s_m=s_m(\beta_m)>0$ such that
\begin{equation}\label{bm}
f(s)s\geq\beta_m e^{4\pi s^2},~\forall s\geq s_m.
\end{equation}
Using $(\ref{bm})$ in $(\ref{e3})$ and the definition of $w_n$ in $B_{d_m/n}(0)$, we obtain
\begin{equation}
t_n^2\geq \beta_m\pi \dfrac{d_m^2}{n^2}e^{2t_n^2ln(n)}
\end{equation}
for $n$ large enough, or equivalently,
\begin{equation}\label{1}
t_n^2\geq \beta_m\pi d_m^2e^{2ln(n)(t_n^2-1)},
\end{equation}
it implies that the sequence $(t_n)$ is bounded. Moreover, from $(\ref{1})$ and
$(\ref{e2})$,
$$
t_n^2\to 1,~\mbox{as}~ n\to \infty.
$$
Now, let us define
$$
C_n=\{x\in B_{d_m}(x_m):t_nw_n(x)\geq s_m\}
$$
and
$$
D_n=B_{d_m}(x_m)\setminus C_n.
$$
With the above notations and using $(\ref{e5})$,
$$
t_n^2\geq\int_{B_{d_m/n}(x_m)}f(t_nw_n)t_nw_n=\int_{C_n}f(t_nw_n)t_nw_n+\int_{D_n}f(t_nw_n)t_nw_n
$$
and by $(\ref{bm})$,
$$
t_n^2\geq\int_{D_n}f(t_nw_n)t_nw_n+\beta_m\int_{C_n}e^{4\pi
t_n^2w_n^2}
$$
or equivalently,
\begin{equation}\label{e2.2}
t_n^2\geq\int_{D_n}f(t_nw_n)t_nw_n+\beta_m\int_{B_{d_m}(x_m)}e^{4\pi
t_n^2w_n^2}-\beta_m\int_{D_n}e^{4\pi t_n^2w_n^2}.
\end{equation}

Notice that
$$
w_n(x)\to 0 ~~\mbox{a.e. in}~~ B_{d_m}(x_m),
$$
$$
\chi_{D_n}(x)\to 1~~\mbox{a.e. in}~~ B_{d_m}(x_m)
$$
and
$$
e^{4\pi t_n^2w_n^2}\chi_{D_n}\leq e^{4\pi t_n^2s_m^2}\in L^1(B_{d_m}(x_m)).
$$
Then, by Lebesgue's dominated convergence
\begin{equation}\label{e2.1}
\lim_n\int_{D_n}e^{4\pi t_n^2w_n^2}=\lim_n\int_{B_{d_m}(x_m)}e^{4\pi
t_n^2w_n^2}\chi_{D_n}=\int_{B_{d_m}(x_m)}1=\pi d_m^2.
\end{equation}
Furthermore,
$$
f(t_nw_n)t_nw_n\chi_{D_n}\leq Ct_nw_ne^{4\pi t_n^2w_n^2}\leq Cs_m
e^{4\pi s_m^2}\in L^1(B_{d_m}(x_m))
$$
and
$$
f(t_nw_n(x))t_nw_n(x)\chi_{D_n}(x)\to 0~~\mbox{a.e. in}~~B_{d_m}(x_m).
$$
Thus, using again Lebesgue's dominated convergence,
\begin{equation}\label{e1.1}
\lim_n\int_{D_n}f(t_nw_n)t_nw_n=0
\end{equation}
Passing to the limit $n\to\infty$ in $(\ref{e2.2})$ and using
$(\ref{e2.1})$ and $(\ref{e1.1})$,
$$
1\geq\beta_m\lim_n\int_{B_{d_m}(x_m)}e^{4\pi t_n^2w_n^2}-\beta_m\pi
d_m^2.
$$
Since $t_n^2\geq 1$, we get
\begin{equation}\label{e2.3}
1\geq\beta_m\lim_n\left[\int_{B_{d_m}(x_m)}e^{4\pi w_n^2}\right]-\beta_m\pi
d_m^2.
\end{equation}
On the other hand, since
$$
\int_{B_{d_m}(x_m)}e^{4\pi
w_n^2}=d_m^2\int_{B_1(0)}e^{4\pi\overline{w}_n^2}=d_m^2\left\{\dfrac{\pi}{n^2}e^{4\pi\frac{1}{2\pi}ln(n)}+2\pi\int_{1/n}^1e^{4\pi\frac{1}{2\pi}\frac{[ln(1/r)]^2}{ln(n)}}rdr\right\},
$$
making a changing of variables $s=ln(1/r)/ln(n)$,
$$
\int_{B_{d_m}(x_m)}e^{4\pi
w_n^2}=\pi d_m^2+2\pi
d_m^2ln(n)\int_0^1e^{2s^2ln(n)-2sln(n)},
$$
and since
$$
\lim_{n\to\infty}\left[ 2ln(n)\int_0^1e^{2ln(n)(s^2-s)}ds\right]=2,
$$
we have
$$
\lim_{n\to\infty}\int_{B_{d_m}(x_m)}e^{4\pi w_n^2}=\pi d_m^2+2\pi d_m^2=3\pi d_m^2.
$$
Using the last limit in $(\ref{e2.3})$, we get
$$
1\geq 3\beta_m\pi d_m^2-\beta\pi d_m^2=2\beta\pi d_m^2,
$$
from where we derive
$$
\beta_m\leq\dfrac{1}{2\pi d_m^2},
$$
which contradicts the choice of $\beta_m$ in $(\ref{eq7})$. Then,
$$
\max_{t\geq 0}I(tw_n)<\dfrac{1}{2},
$$
proving that $c_m<1/2$, for any $m\in\mathbb{N}$ fixed arbitrarily. \fim

\section{Proof of Theorem \ref{sb}.}

To  proof Theorem\ref{sb}, we will use the following proposition.
\begin{proposition}\label{p4u}
Let $A$ be an angular sector contained on the positive semiplane of $\R^2$ such that one of its boundary lies in $x_2$ axis, and denote such boundary of $A$ by $B_0=\{x=(x_1,x_2)\in A:~ x_2=0\}$. Consider $A'$ the reflection $A$ with respect to $x_2$ axis. Suppose that $u$ is a solution of the following problem:
$$
\left\{
\begin{array}{cl}
-\Delta u=f(u),& \mbox{ in }~~ A, \\[0.2cm]
u=0,&\mbox{on}~~ B_0,
\end{array}
\right.\leqno{(P)}
$$
where $f$ is a real, continuous and odd function. Then, the function $\tilde{u}$ such that $\tilde{u}= u$ in $A$  and $\tilde{u}$ is antisymmetric
with respect to $x_2$ axis,
$$
\tilde{u}(x_1,x_2)=\left\{
\begin{array}{ll}
u(x_1,x_2),&\mbox{in}~~A\\[0.2cm]
-u(x_1,-x_2),&\mbox{in}~~A'\\[0.2cm]
0,&\mbox{on}~~B_0
\end{array}
\right.
$$
satisfies
$$
-\Delta \tilde{u}=f(\tilde{u})~~~\mbox{in}~~~A\cup A'.
$$
\end{proposition}

\noindent{\bf Proof.} Since $u$ be a solution of $(P)$, we have
$$
\int_{A}\nabla u\nabla
\varphi=\int_{A}f(u)\varphi,~~\forall \varphi\in
C^\infty_c(A).
$$
we want to prove that
$$
\int_{A\cup A'}\nabla \tilde{u}\nabla
\phi=\int_{A\cup A'}f(\tilde{u})\phi,~\forall \phi\in
C^\infty_0(A\cup A').
$$
For any $\phi\in C^\infty_0(A\cup A')$,
$$
\int_{A\cup A'}f(\tilde{u})\phi=\int_{A}f(u(x_1,x_2))\phi(x_1,x_2)+\int_{A'}f(-u(x_1,-x_2))\phi(x_1,x_2).
$$
Since $f$ be an odd function,
$$
\begin{array}{ll} \displaystyle\int_{A\cup A'}f(\tilde{u})\phi
&=\displaystyle\int_{A}f(u(x_1,x_2))\phi(x_1,x_2)+\int_{A'}f(-u(x_1,-x_2))\phi(x_1,x_2)\\[0.3cm]
&=\displaystyle\int_{A}f(u(x_1,x_2))\phi(x_1,x_2)-\int_{A'}f(u(x_1,-x_2))\phi(x_1,x_2)\\[0.3cm]
&=\displaystyle\int_{A}f(u(x_1,x_2))\phi(x_1,x_2)-\int_{A}f(u(x_1,x_2))\phi(x_1,-x_2).
\end{array}
$$
Thus
\begin{equation}\label{e11}
\int_{A\cup A'}f(\tilde{u})\phi=\int_{A}f(u)\psi,
\end{equation}
where $\psi(x_1,x_2)=\phi(x_1,x_2)-\phi(x_1,-x_2)$. On the other hand,
$$
\begin{array}{ll}
\displaystyle\int_{A\cup A'}\nabla\tilde{u}\nabla\phi
&=\displaystyle\int_{A}\nabla u(x_1,x_2)\nabla\phi(x_1,x_2)-\int_{A'}\nabla u(x_1,-x_2)\nabla\phi(x_1,x_2)\\[0.3cm]
&=\displaystyle\int_{A}\nabla u(x_1,x_2)\nabla\phi(x_1,x_2)-\int_{A}\nabla u(x_1,x_2)\nabla (\phi(x_1,-x_2))\\[0.3cm]
&=\displaystyle\int_{A}\nabla u(x_1,x_2)\nabla(\phi(x_1,x_2)-\phi(x_1,-x_2)).
\end{array}
$$
Then,
\begin{equation}\label{e12}
\int_{A\cup A' }\nabla\tilde{u}\nabla\phi=\int_{A}\nabla
u\nabla\psi.
\end{equation}
The function $\psi$ does not in general belong to $C^\infty_0(A)$. Therefore, $\psi$ can not be used as a function
test (in the definition of weak solution on $H^1(A)$). On the other hand, if we consider the sequence of functions $(\eta_k)$ in $C^{\infty}(\R)$, definided by
$$
\eta_k(t)=\eta(kt),~t\in\R,~k\in\mathbb{N},
$$
where $\eta\in C^\infty(\R)$ is a function such that
$$
\eta(t)=\left\{
\begin{array}{ll}
0, & \mbox{if}~~t<1/2,\\
1, & \mbox{if}~~t>1.
\end{array}
\right.
$$
Then
$$
\varphi_k(x_1,x_2):=\eta_k(x_2)\psi(x_1,x_2)\in C^\infty_0(A),
$$
which implies that
\begin{equation}\label{e14}
\int_{A}\nabla
u\nabla\varphi_k=\int_{A}f(u)\varphi_k,~k\in\mathbb{N}.
\end{equation}
From (\ref{e11}), (\ref{e12}) and (\ref{e14}), we can conclude de proof, in view of the following limits
$$
(I)~~~~~~~~\int_{A}\nabla u\nabla\varphi_k\rightarrow
\int_{A}\nabla u\nabla\psi
$$
e
$$
(II)~~~~~~~~\int_{A}f(u)\varphi_k\rightarrow \int_{A}f(u)\psi,
$$
as $k\rightarrow \infty$ occur. To see that $(I)$ occur, notice that
$$
\int_{A}\nabla u\nabla\varphi_k=\int_{A}\eta_k\nabla u\nabla \psi+\int_{A}\dfrac{\partial u}{\partial x_2}k\eta'(kx_2)\psi.
$$
Clearly,
$$
\int_{A}\eta_k\nabla u\nabla \psi\to\int_{A}\nabla u\nabla \psi,~\mbox{as}~~k\to\infty.
$$
Assim, resta mostrar que
\begin{equation}\label{stR}
\int_{A}\dfrac{\partial u}{\partial x_2}k\eta'(kx_2)\psi\to 0~~\mbox{as}~~k\to\infty.
\end{equation}
In fact,
$$
\left|\int_{A}\dfrac{\partial u}{\partial x_2}k\eta'(kx_2)\psi\right|\leq kMC\int_{0<x_2<1/k}\left|\dfrac{\partial u}{\partial x_2}\right|x_2\leq MC\int_{0<x_2<1/k}\left|\dfrac{\partial u}{\partial x_2}\right|,
$$
where $C=\displaystyle\sup_{t\in[0,1]}|\eta'(t)|$ and $M>0$ is such that
$$
|\psi(x_1,x_2)|\leq M|x_2|,~ \forall (x_1,x_2)\in A\cup A',
$$
and since
$$
\int_{0<x_2<1/k}\left|\dfrac{\partial u}{\partial x_2}\right|\to 0,~~\mbox{as}~~k\to\infty,
$$
the limit in (\ref{stR}) occur. The item $(II)$ is an imediatly consequence of the Lebesgue's dominated convergence.

Now, for each $m\in\mathbb{N}$, we apply the Proposition \ref{p4u} to the solution $u$ of problem $(P)_m$. Let $A_m'$ be the reflection of $A_m$ in one of its sides. On $A_m\cup A_m'$, wecan the define the function $\tilde{u}$ such that $\tilde{u}=u$ on $A_m$, and $\tilde{u}$ is antisymmetric with respect to the side of reflection. Now, let $A_m''$ be the reflection of $A_m\cup A_m'$ in one of its sides and
$\tilde{\tilde{u}}$ the function defined on $A_m\cup A_m'\cup A_m''$
such that $\tilde{\tilde{u}}=\tilde{u}$ on $A_m\cup A_m'$ and
$\tilde{\tilde{u}}$ is antisymmetric with respect to the side of reflection.Repetindo este procedimento, após um número finito de reflexões. Repeating this procedure, after finite steps, we finally obtain a function defined on the whole unit ball $B$,  denoted by $u_m$. Clearly, $u_m$ satisfies the Dirichlet condition on the boundary $\partial B$. That is, $u_m$ is a sign-changing solution of problem $(P)$. Since for every $m\in\mathbb{N}$, problem $(P)_m$ admits a positive solution, hence there exist infinitely many differents sign-changing solutions, and the proof of Theorem  \ref{sb} is complete. \fim

\vspace{0.5cm}

\noindent {\bf Remark.} In figure $\ref{ddd}$, we represent the signal of three solutions, corresponding to the cases $m=1,~ m=2~\mbox{and}~ m=3$, respectively. The blue color represents the regions where the solutions are negative and the red color, the regions where the solutions are positive.

\begin{figure}[!htb]
\begin{center}
\includegraphics[scale=0.25]{ddd}
\end{center}
\caption{Signal of solutions}
\label{ddd}
\end{figure}

We show in Figure $3$ the profile of solution for the case $m=2$.

\begin{figure}[!htb]
\begin{center}
\includegraphics[scale=0.8]{a22}
\end{center}
\caption{Case $m=2$}
\end{figure}

\begin{remark} It is possible to make a version of Theorem \ref{sb} with Neumann boundary condition using the same arguments that we used here, but we have to work with another version of Trudinger-Moser inequality in $H^1(\Omega)$ due to Adimurthi-Yadava \cite{AYa}, which says that if $\Omega$ is a bounded domain with smooth boundary, then for any $u\in H^1(\Omega)$,
\begin{equation} \label{X02}
\int_{\Omega}
e^{\alpha u^2}< +\infty, \,\,\,\, \mbox{ for all }\,\,\alpha >0.
\end{equation}
Furthermore, there exists a positive constant $C=C(\alpha,|\Omega|)$ such that
\begin{equation} \label{X11}
\sup_{||u||_{H^{1}(\Omega)} \leq 1} \int_{\Omega} e^{\alpha u^2} \leq C , \,\,\,\,\,\,\, \forall \, \alpha  \leq 2 \pi .
\end{equation}

\end{remark}
\vspace{0.3 cm}

\noindent \textbf{Acknowledgments.}  The author would like to thank professor Claudianor O. Alves for his excellent advices during the graduate school of him.

redpajama_set_name: RedPajamaArXiv


text:
\section{Introduction}
$k$ Nearest Neighbors ($k$NN) \cite{cover1967nearest, wu2008top, samanthula2015k, xie2016robust} is one of the most popular classification algorithms and has been widely used in many fields, such as intrusion detection \cite{liao2002use}, gene classification \cite{li2001gene}, semiconductor fault detection \cite{he2007fault}, very large database manipulation \cite{kolahdouzan2004voronoi},  nuclear magnetic resonance spectral interpretation \cite{kowalski1972k} and the prediction of basal area diameter \cite{maltamo1998methods}, because it is simple but effective, and can generally obtain good results in many tasks. One main drawback of the traditional $k$NN is that it does not take the manifold distribution information into account and this can cause bias which results in bad performance. It becomes even worse when there are only a very small amount of labeled samples available. To address this, an example is shown in figure \ref{USData}(a), in which there are two one-dimensional manifolds (the outer arch and the interior reflected \emph{S}) which correspond to two classes, respectively. Each class has only 3 labeled samples, indicated by the colored triangles and circles. Black dots are unlabeled samples. Figure \ref{USData}(b) - (d) show the 1NN, 2NN and 3NN classification results produced by the traditional $k$NN, respectively. We can see that although the data have apparent manifold distribution, the traditional $k$NN incorrectly classifies many samples due to ignoring the manifold information.

 \begin{figure}[H]
  \centering

   \subfigure[Toy manifold data set]{
   \includegraphics[width=0.4\textwidth]{US.png}}
   \subfigure[$k$=1]{
   \includegraphics[width=0.4\textwidth]{US_KNN1.png}}

   \subfigure[$k$=2]{
   \includegraphics[width=0.4\textwidth]{US_KNN2.png}}
  \subfigure[$k$=3]{
  \includegraphics[width=0.4\textwidth]{US_KNN3.png}}
  \caption{Results of traditional $k$NN classification with $k$=1, 2, 3 on manifold distributed data, in which the colored shapes (red triangles and green dots) are labeled samples and the black dots are unlabeled samples.}
  \label{USData}
\end{figure}

To improve the performance of the traditional $k$NN, some new $k$NN algorithms have been proposed. Hastie et. al. \cite{hastie1996discriminant} proposed an adaptive $k$NN algorithm which computes a local metric for each sample and uses Mahalanobis distance to find the nearest neighbors of a query point. Hechenbichler and Schliep \cite{hechenbichler2004weighted} introduced a weight scheme to attach different importance to the nearest neighbors with respect to their distances to the query point. To reduce the effect of unbalanced training set sizes of different classes, Tan \cite{tan2005neighbor} used  different weights for different classes regarding  the number of labeled samples in each class. There are also some other improvements and weight schemes for different tasks \cite{li2003improved,cost1993weighted,nene1997simple,weinberger2009distance,dudani1976distance,han2001text,gao2016reverse}.

However, none of these new $k$NN algorithms takes manifold structure into consideration explicitly. For high-dimensional data, such as face images, documents and video sequences, the nearest neighbors of a point found by traditional $k$NN algorithms can be very far in terms of  the geodesic distance between them, because the dimension of the underlying manifold is usually much lower than  that of the data space \cite{roweis2000nonlinear,tenenbaum2000global, beyer1999nearest}.  There have also been attempts to make $k$NN adaptive to manifold data. In Turaga and Chellappa's paper \cite{turaga2010nearest}, geodesic distance is used to directly replace standard Euclidean distance in traditional $k$NN, but geodesic distance can be computed with good accuracy only if the manifold is sampled with sufficient points. Furthermore, geodesic distance  tends to be very sensitive to short-circuit phenomenon. Li \cite{ma2010local} proposed a weighted manifold $k$NN using Local Linear Embedding (LLE) techniques, but LLE tends to be unstable due to local changes on the manifold. Percus and Olivier \cite{percus1998scaling} studied the general $k^\text{th}$ nearest neighbor distance metric on close manifold, but their method needs to know exactly the analytical form of the manifold and thus is unsuitable for most real-world applications.

In this paper, we propose a novel graph-based $k$NN algorithm which can effectively handle both traditional Gaussian distributed data and nonlinear manifold distributed data. To do so, we first present a manifold similarity measure method, the constrained tired random walk, and then we modify the traditional $k$NN algorithm to adopt the new measuring method. To deal with online situations, we also propose a new algorithm to handle sequential samples based on a local neighborhood reconstruction method. Experimental results on both synthetic and real-world data sets are presented to demonstrate the validity of the proposed method.

The remainder of this paper is organized as follows: Section 2 reviews the tired random walk model. Section 3  presents a new constrained tired walk random walk model and Section 4 describes the graph-based $k$NN algorithm. Section 5 proposes a sequential algorithm for online samples. The simulation and comparison results are presented in Section 6, followed by conclusions in Section 7.
\section{ Review of tired random walk}
Assume a  training set ${{\mathcal{X}}_{T}}=\left\{ {{x}_{1}},{{x}_{2}},...,{{x}_{l-1}},{{x}_{l}} \right\}\subset {{\mathbb{R}}^{d}}$  contains $l$ labeled samples and the class label of ${{x}_{i}}$ is ${{y}_{i}}$ , ${{y}_{i}}\in \left\{ 1,2,...,C \right\}; i=1...l$, where $d$ is feature length and $C$ is class number. There are also $n-l$ unlabeled samples to be classified, ${{\mathcal{X}}_{U}}=\left\{ {{x}_{1}},{{x}_{2}},...,{{x}_{n-l}} \right\}$.  Denote $\mathcal{X}={{\mathcal{X}}_{T}}\cup {{\mathcal{X}}_{U}}=\left\{ {{x}_{1}},{{x}_{2}},...,{{x}_{n}} \right\}$ and $y=(y_1,y_2,...,y_l)$. We also use $X$ for the sample matrix, whose columns are the samples in $\mathcal{X}$.  We use $\left\| \cdot  \right\|$ to denote  the Frobenius norm.

In differential geometry studies, a manifold can be defined from an intrinsic or extrinsic point of view \cite{spivak1970comprehensive, boothby2003introduction}. But in data processing studies, such as dimension reduction \cite{chahooki2014shape, petraglia2015dimensional, nowakowska2016dimensionality} and manifold learning \cite{vincent2002manifold, bengio2005non, vemulapalli2013kernel}, it is helpful to consider a manifold as a distribution which is embedded in a higher Euclidean space, i.e. adopting an extrinsic view in its ambient space. Borrowing the concept of \emph{intrinsic dimension} from \cite{camastra2016intrinsic},  we  give a formal definition of a manifold data set as follows.\\
\emph{\textbf{Definition}: A data set is considered to be manifold distributed if its intrinsic dimension is less than its data space dimension.}\\
For more information on the intrinsic dimensions of a data set and how it can be estimated from data samples, we refer readers to  \cite{camastra2016intrinsic, petraglia2015dimensional}. To determine whether a data set has manifold distribution, one can simply estimate its intrinsic dimension and compare it with the data space dimension, i.e. the length of a sample vector.

Similarity measure is an important factor while processing manifold distributed data, because on manifolds traditional distance metrics  (such as Euclidean distance) are not a proper measure \cite{yu2014semantic,  yi2016online, yu2016density}. Recent studies have also proved that classical random walk is not a useful measure for large sample  cases or high-dimensional data because it does not take any global properties of the data into account \cite{luxburg2010getting}. The tired random walk (TRW) model was proposed in Tu's paper \cite{tu2014novel} and has been demonstrated to be an effective measure of nonlinear manifold \cite{wang2015characterizing,yin2015self}, because it takes global geometrical structure information into consideration.

Recall that  on a  weighted undirected graph,  the classical random walk transition matrix is $P={{D}^{-1}}W$, where $W$ is the graph adjacency matrix and $D$ is a diagonal matrix with entries ${{D}_{ii}}=\sum\nolimits_{j=1}^{n}{{{W}_{ij}}}$.  Now imagine that a tired random walker walks continuously through edges in a graph, but it becomes more tired after each walk and finally stops after all energy is exhausted, i.e. the transition probability of the random walk reduces with a fixed ratio (e.g. 0.01) after each walk and finally approaches 0. After $t$ steps the tired random walk transition probability matrix becomes ${{(0.01P)}^{t}}$.  Now considering figure \ref{TRWGraph}, the tired random walker starts from vertex ${i}$ and its destination is vertex ${j}$ on the graph, walking with a strength reduction rate $\alpha \in (0,1)$. Then it may walk through any path that connects vertices ${i}$ and ${j}$, with an arbitrary number of steps before its strength is used up. For example, the tired random walker can walk through path $i \rightarrow A\rightarrow j$, or $i \rightarrow B\rightarrow j$. It can also walk through $i \rightarrow B \rightarrow C  \rightarrow j$,  or even $i \rightarrow B \rightarrow C  \rightarrow B \rightarrow j$, because while at vertex $C$, the probability of walking to $B$ is much larger than that to $j$.  But all these walking paths reflect the underlying geometrical structure of the graph, hence the distribution of the data. Therefore,  a good similarity measure between vertex $i$ to $j$  should  take (globally) all  possible paths and an arbitrary number of  steps  (can potentially be infinite) into consideration, rather than only considering (locally) a single path or a single step as the classical random walk \cite{luxburg2010getting} does. This makes a fundamental difference between the \emph{tired random walk} and \emph{classical random walk} and entitles the tired random walk to be more robust and effective, especially for manifold distributed data, as will be demonstrated in the experimental section.  Mathematically, the accumulated transition probability of the tired random walk between vertex $i$ and $j$ is ${{{(P_{TRW})}}_{ij}}={{\left[ \sum\nolimits_{t=0}^{\infty }{{{(\alpha P)}^{t}}} \right]}_{ij}}$. For all vertices, the accumulated transition probability matrix becomes ${P_{TRW}}=\sum\nolimits_{t=0}^{\infty }{{{(\alpha P)}^{t}}}$. As the eigenvalue of $P$ is in $[-1,\ 1]$ and $\alpha \in (0,1)$, the series converges and the tired random walk matrix is
\begin{equation} \label{PTRWEquation}
{{P}_{TRW}}=\sum\nolimits_{t=0}^{\infty }{{{\left( \alpha P \right)}^{t}}}={{\left( I-\alpha P \right)}^{-1}}
\end{equation}

 \begin{figure}[H]
  \centering
   \includegraphics[width=0.5\textwidth]{TRWGraph.png}
  \caption{Tired random walk on weighted undirected graph.}
  \label{TRWGraph}
\end{figure}
 Because ${{P}_{TRW}}$ takes all the possible paths into account, it captures the global geometrical structure information of the underlying manifold and thus is demonstrated to be more effective and robust to describe manifold similarity.
\section{A constrained tired random walk model}

In this section, we further extend the model into a constrained situation. For classification purposes, we find that labeled samples provide not only  class distribution information, but also constraint information, i.e., samples which have the same class labels are must-link pairs and samples which have different class labels are cannot-link pairs. In most of the existing supervised learning algorithms, only  class information is utilized but  constraint information is discarded. Here we include  constraint information into the TRW model by modifying the weights of graph edges between the labeled samples, because constraint information has been demonstrated to be useful for performance improvement \cite{tu2015posterior, gong2014semi, fu2015local, zhou2015semi}. Class information will be utilized in the next section for the proposed new $k$NN algorithm.

We first construct an $R$-level nearest-neighbor strengthened tree for each labeled sample ${{x}_{i}}\in {{\mathcal{X}}_{T}}$ as follows:
\begin{enumerate}[(i).]
  \item Set ${{x}_{i}}$ as the first level node (tree root node, $r=0$) and its $k$ nearest neighbors as the second level  nodes.
  \item For each node in level $r-1$, set its nearest neighbors  as its level $r$ descendants. If any node in level $r$  appears in its ancestor level, remove it from  level $r$.
  \item	If $r<R$, go to (ii).
\end{enumerate}
where $R$ is a user-specified parameter to define the depth of the tree.  Then for each pair of samples $\left( {{x}_{i}},{{x}_{j}} \right)$, the corresponding graph edge weight is set according to the rules in Table \ref{ConstrainedGraph}.
 \begin{table}[ht
\caption{Constrained graph construction}
\label{ConstrainedGraph}
\centering
\footnotesize
\begin{tabular}{ll}
\toprule \hline
Steps & \\ \hline
1 &	${{W}_{ij}}=1$ if ${{x}_{i}},{{x}_{j}}\in {{\mathcal{X}}_{T}}$  and have same class label.\\
2 & ${{W}_{ij}}=0$ if ${{x}_{i}},{{x}_{j}}\in {{\mathcal{X}}_{T}}$ and have different class labels. \\
3 &${{W}_{ij}}=\exp \left( -{{{\left\| {{x}_{i}}-{{x}_{j}} \right\|}^{2}}}/{2{{\sigma }^{2}}}\; \right)$ if at least one of ${{x}_{i}}$, ${{x}_{j}}$ is unlabeled. \\
4 &${{W}_{ij}}=(1+\theta _{ij}^{r}){{W}_{ij}},1\le r\le R$, if ${{x}_{i}}$ is a node in level $r-1$  and ${{x}_{j}}$ \\
 &is a child of $x_i$ in level $r$ in the strengthened tree. \\ \hline \bottomrule
\end{tabular}
\end{table}
$\sigma $ is the Gaussian kernel width parameter and $\theta$ is the strengthening parameter. Note that for the Gaussian kernel, step 1 is equivalent to merging the two same-label samples together (0 distance between them) and step 2 is equivalent to separating  the two different-label samples from each other to infinitely far (infinite distance between them). The connections from a labeled sample to its nearest neighbors are strengthened by ${{\theta }_{ij}}$ in step 4. This can spread the 'hard' constraints in steps 1 and  2 to farther neighborhoods on the graph in a form of \emph{soft} constraints and thus causes these constraints to have a wider influence. The motivation of constructing the strengthened tree is inspired by the neural network reservoir structure analysis techniques, in which information has been shown to spread out from input neurons to interior neurons in the reservoir following a tree-structure path \cite{tu2016mapping}.

The selection of parameter $\theta$ is based the following conditions
\begin{itemize}
\item the strengthened weight  should be positive and less than the weight of the must-link constraint.
\item  the strengthening effect should be positive and decays along the strengthened tree level.
\end{itemize}
Mathematically, the conditions are
\begin{equation}
\left\{ \begin{aligned}
  & 0<{{W}_{ij}}+{{\theta }_{ij}}{{W}_{ij}}<1 \\
 & 0<\theta _{ij}^{r+1}<\theta _{ij}^{r} \\
\end{aligned} \right.
\end{equation}
As a result, $\theta$ should be
\begin{equation}
0<{{\theta }_{ij}}<\min \left( \frac{1-{{W}_{ij}}}{{{W}_{ij}}},1 \right)=\bar{\theta }
\end{equation}
In all our experiments, we used a single value of $\theta=0.1\bar{\theta }$, which
gives good results for both synthetic and real-world data.
\section{A new graph-based $k$NN classification algorithm on nonlinear manifold}

Here we present a graph-based $k$NN algorithm for nonlinear manifold data  classification. The procedure of the algorithm is summarized in Table \ref{GraphKNN}.
 \begin{table}[ht
\caption{A graph-based $k$NN algorithm}
\label{GraphKNN}
\centering
\footnotesize
\begin{tabular}{ll}
\toprule \hline
Steps & \\ \hline
1 &Input $\mathcal{X}={{\mathcal{X}}_{T}}\cup {{\mathcal{X}}_{U}}$, $y$ and $k$. \\
2 &Construct a constrained graph according to Table \ref{ConstrainedGraph} \\
3 &Compute the ${P}_{TRW}$ using equation (\ref{PTRWEquation}) \\
4 &Evaluate samples' similarity according to equation (\ref{PTRW}) \\
5 &Find nearest neighbors of an unlabeled sample using equation (\ref{FindNN}) \\
6 &Determine the class label according to equation (\ref{KNNClassification}) \\ \hline  \bottomrule
\end{tabular}
\end{table}

Specifically, given ${{P}_{TRW}}$ matrix, the TRW weight between sample ${{x}_{i}}$ and ${{x}_{j}}$ is defined as
\begin{equation} \label{PTRW}
\bar w_{ij}=w({{x}_{i}},{{x}_{j}})=\frac{{{({{P}_{TRW}})}_{ij}}+{{({{P}_{TRW}})}_{ji}}}{2}
\end{equation}
Note that while the similarity measure defined by matrix $P_{TRW}$ between two samples is not necessarily symmetric ( $P$ is not symmetric and thus its matrix series $P_{TRW}$ is also not symmetric), the weight defined in equation (\ref{PTRW}) is indeed a symmetric measure. For each unlabeled sample $x\in {{\mathcal{X}}_{U}}$, we could find its $k\le l$ nearest  neighbors  from ${{\mathcal{X}}_{T}}$ by
\begin{equation}\label{FindNN}
{{x}_{i}}=\underset{{{x}_{j}}\in {{\mathcal{X}}_{T}}}{\mathop{\arg \max }}\,w(x,{{x}_{j}})
\end{equation}
Instead of counting the number of labeled samples from each class in the classical $k$NN, we sum  the TRW weights of the labeled samples of each class and the class label of the unlabeled sample $x$ is determined by
\begin{equation}\label{KNNClassification}
y=\underset{c=1,2,...,C}{\mathop{\arg \max }}\,\sum\nolimits_{i=1}^{k}{w(x,{{x}_{i}})I({{y}_{i}}=c)}
\end{equation}

It is worth mentioning that because the proposed semi-supervised m$k$NN  utilizes class label information only in the classifying stage and it uses the same $k$ value equally for all classes, m$k$NN naturally lacks  the so-called class bias problem in many semi-supervised algorithms (such as \cite{zhu2003semi, liu2010large,tu2013experimental,  ji2014automatic}) that is due to the influence of unbalanced labeled samples of each class in $\mathcal{X}_T$ and needs to be re-balanced by various weighting schemes \cite{wang2013semi, zhu2003semi}. Furthermore, with the algorithm described in the next section, m$k$NN immediately becomes  a supervised  classifier and enjoys the advantages of both semi-supervised learning (classifying abundant unlabeled samples with only a tiny number of labeled samples) and supervised learning (classifying new samples immediately without repeating the whole learning process).

\section{A sequential method to handle online  samples}
For one single unlabeled sample, if we compute its TRW weights using equation (\ref{PTRWEquation}) and (\ref{PTRW}), we have to add it to $\mathcal{X}$ and recompute the matrix ${{P}_{TRW}}$. As a result, the computational cost for \emph{one} sample is too high. Actually this is the so-called transductive learning problem\footnote{Transductive learning is an opposite concept to inductive learning. Inductive learning means the learning algorithm, such as SVM, learns a model explicitly in  data space that partitions the data space into several different regions. Then the model  can be applied directly to unseen samples to obtain the class labels. On the other side, transductive learning does not build any model. It performs one-time learning only on a fixed data set.Whenever the data set changes (for example, existing samples are changed or new samples are added.), the whole learning process has to be repeated again to assign new class labels.},  a common drawback of many existing algorithms \cite{joachims1999transductive,joachims2003transductive,collobert2006large,goldberg2010transduction}. To attack this problem, we propose a new method based on rapid neighborhood reconstruction, in which a local neighborhood is first constructed in sample space and then the TRW weights can be reconstructed in the same local neighborhood with very trivial computational cost.

Given a new sample $x$, it has been shown that $x$ can be well reconstructed by its nearest neighbors on the manifold if there are sufficient data points sampled from the manifold \cite{roweis2000nonlinear, chen2013nonnegative, tao2015local}. Thus, it is also reasonable to assume that the neighborhood relationships, hence the weights of sample $x$  in equation (\ref{PTRW}), have the same geometrical distribution as the sample distribution. So, to compute the weights of $x$ without explicitly recomputing matrix $P_{TRW}$ in equation (\ref{PTRW}), we first find $x$'s $k$ nearest neighbors\footnote{One should note that finding nearest neighbors in $\mathcal{X}$ is quite different from that in $\mathcal{X}_T$. The former is the basis of many nearest-neighbor operations (such as constructing nearest-neighbor graph in \cite{tenenbaum2000global, roweis2000nonlinear} and the $R$-level strengthened tree in Section 3 of this paper) and the latter is the basis of the classical $k$NN classifier. Because $\mathcal{X}$ contains many instances, which are  sampled densely from the underlying data distribution, an instances's local neighborhood in $\mathcal{X}$ is usually very small  and thus Euclidean distance is still valid in this small range for that any manifold can be locally well approximated by Euclidean space \cite{boothby2003introduction}.  However, instances in $\mathcal{X}_T$ are very few and usually not densely sampled from the manifold and \emph{nearest neighbors }in $\mathcal{X}_T$ can be very far. Thus Euclidean distance is no longer suitable for measuring the closeness of the points in $\mathcal{X}_T$. This is why we need other new similarity (or closeness) measure methods, which is one of the main contributions of this paper.} in $\mathcal{X}$, written as $X_{k}$ which contains these $k$ nearest neighbors in its columns, and then minimize the local reconstruction error by solving the following constraint quadratic optimization problem
\begin{equation}
\begin{aligned}\label{OptWeight}
  & \min {{\left\| x-X_{k}z \right\|}^{2}} \\
 & s.t.\,\,\,z\ge 0;{{z}^{T}}e=1 \\
\end{aligned}
\end{equation}
where $e$ is a vector with all entries being 1. Note that the entries of $z$ are nonnegative and the sum of all entries must be 1, so $z$ is expected to be sparse \cite{liu2010large}. Problem (\ref{OptWeight}) is a constrained quadratic optimization problem and can be solved very efficiently with many publicly available toolboxes. We use the OPTI optimization toolbox\footnote{OPTI TOOLBOX: http://www.i2c2.aut.ac.nz/Wiki/OPTI/} to solve this. After obtaining the optimal $z$, the TRW weights between $x$ and its nearest labeled samples in ${{X}_{k}}$ can be computed by solving the following optimization problem
\begin{equation}\label{ReconstructWeight}
\begin{aligned}
  & \min {{\left\| \bar w-\bar W_{k}^{T}z \right\|}^{2}} \\
 & s.t.\quad \bar w\ge 0 \\
\end{aligned}
\end{equation}
where ${{\bar W}_{k}}=(\bar w_1, \bar w_2,...,\bar w_k)$ and $\bar w_i$ contains  the weights between sample $x_i$ in $X_{k}$ and its $k$ nearest neighbors in $X$.

This process is illustrated in Figure \ref{IllustrationExample}. Figure \ref{IllustrationExample}(a) corresponds to equation (\ref{OptWeight}) which computes $z$ and Figure \ref{IllustrationExample}(b) corresponds to equation (\ref{ReconstructWeight}) which computes $\bar w$.
 \begin{figure}[H]
  \centering
   \subfigure[Computing reconstruction weight $z$ using equation (\ref{OptWeight})]{
   \includegraphics[width=0.45\textwidth]{Illustration.png}}
 \subfigure[Computing TRW weight $\bar w$ using equation (\ref{ReconstructWeight})]{
   \includegraphics[width=0.45\textwidth]{Illustration2.png}}
  \caption{The process of computing sequential TRW weight.}
  \label{IllustrationExample}
\end{figure}

It is easy to see that the optimal solution of problem (\ref{ReconstructWeight}) is simply the result of a nonnegative projection operation
\begin{equation}
\bar w=\text{max}(0, \bar W_{k}^{T}z)= \bar W_{k}^{T}z
\end{equation}
The second equation holds because both $\bar W_{k}$ and $z$ are nonnegative and therefore their multiplication result is also nonnegative.

One should note that with this sequential learning strategy, the proposed m$k$NN can be treated as an inductive classifier, whose model consists of both the $P_{TRW}$ matrix and the data samples that have been classified so far. Whenever a new sample arrives, the model can quickly give its class label by the three  steps in Table \ref{SKNN}, without repeating the whole learning process in Table \ref{GraphKNN}.

 \begin{table}[ht
\caption{The procedure of sequential manifold $k$NN algorithm}
\label{SKNN}
\centering
\footnotesize
\begin{tabular}{ll}
\toprule \hline
Steps & \\ \hline
1 &Input $\mathcal{X}={{\mathcal{X}}_{T}}\cup {{\mathcal{X}}_{U}}$, $P_{TRW}$, $x$ and $k$. \\
2 &Find $x$'s  $k$ nearest neighbors in $\mathcal{X}$  \\
3 &Use equations (\ref{OptWeight}) and  (\ref{ReconstructWeight}) to compute its TRW weights \\
4 &Use  equation (\ref{KNNClassification}) to classify it \\ \hline  \bottomrule
\end{tabular}
\end{table}

\section{Experimental results}
In this section, we report the experimental results on both the synthetic data sets and real-world data sets. The comparison algorithms include traditional $k$ nearest neighbors ($k$NN), the weighted $k$ nearest neighbors (w$k$NN) and the geodesic $k$NN (g$k$NN) proposed by Pavan and Rama\cite{turaga2010nearest}, as well as  our manifold $k$ nearest neighbors (m$k$NN).  For $k$NN and w$k$NN, the only parameter is $k$. For g$k$NN and m$k$NN, there is one more parameter for each, i.e. the number of nearest neighbors for computing geodesic distance in g$k$NN and the kernel width $\sigma $ in m$k$NN. We tune these two parameters by grid-search and choose their values to produce the minimal 2-fold cross validation error rate.
\subsection{	Experimental results on synthetic data sets}
We first conduct experiments on three synthetic data sets shown in Figure \ref{SynDataSet} to demonstrate the superiority of  $mk\text{NN}$ over other $k\text{NN}$ algorithms. For each data set in Figure \ref{SynDataSet}, the three red triangles and the three green dots are the labeled samples of the two classes, respectively. Note that all  three data sets contain some ambiguous points (or bridging points) in the gap between two classes, making the classification even more challenging. Experimental results on these data sets are shown in Figures \ref{ResultTwoCircle} to \ref{Resultknot}.
 \begin{figure}[H]
  \centering

   \subfigure[data set 1]{
   \includegraphics[width=0.3\textwidth]{TwoCircle.png}}
   \subfigure[data set 2]{
   \includegraphics[width=0.3\textwidth]{circlerub.png}}
   \subfigure[data set 3]{
   \includegraphics[width=0.3\textwidth]{knot.png}}
  \caption{Three synthetic data sets, in which the colored shapes are labeled samples and the black dots are unlabeled samples}
  \label{SynDataSet}
\end{figure}

 \begin{figure}[H]
  \centering
  \subfigure[$k$NN]{
   \includegraphics[width=0.4\textwidth]{TwoCircleKNN.png}}
   \subfigure[w$k$NN]{
   \includegraphics[width=0.4\textwidth]{TwoCircleWKNN.png}}

    \subfigure[g$k$NN]{
   \includegraphics[width=0.4\textwidth]{TwoCircleGKNN.png}}
    \subfigure[m$k$NN]{
   \includegraphics[width=0.4\textwidth]{TwoCircleMKNN.png}}
  \caption{Experimental results on synthetic data sets. (a)-(d): results of $k$NN, w$k$NN, g$k$NN and m$k$NN on data set 1.}
  \label{ResultTwoCircle}
\end{figure}

 \begin{figure}[H]
  \centering

   \subfigure[$k$NN]{
   \includegraphics[width=0.43\textwidth]{circlerubKNN.png}}
   \subfigure[w$k$NN]{
   \includegraphics[width=0.43\textwidth]{circlerubWKNN.png}}

    \subfigure[g$k$NN]{
   \includegraphics[width=0.43\textwidth]{circlerubGKNN.png}}
    \subfigure[m$k$NN]{
   \includegraphics[width=0.43\textwidth]{circlerubMKNN.png}}
    \caption{Experimental results on synthetic data sets. (a)-(d): results of $k$NN, w$k$NN, g$k$NN and m$k$NN on data set 2.}
    \label{Resultcirclerub}
\end{figure}
 \begin{figure}[H]
  \centering

   \subfigure[$k$NN]{
   \includegraphics[width=0.43\textwidth]{knotKNN.png}}
   \subfigure[w$k$NN]{
   \includegraphics[width=0.43\textwidth]{knotWKNN.png}}

    \subfigure[g$k$NN]{
   \includegraphics[width=0.43\textwidth]{knotGKNN.png}}
    \subfigure[m$k$NN]{
   \includegraphics[width=0.43\textwidth]{knotMKNN.png}}
    \caption{Experimental results on synthetic data sets. (a)-(d): results of $k$NN, w$k$NN, g$k$NN and m$k$NN on data set 3.}
    \label{Resultknot}
\end{figure}
From these results, we can see that because $k$NN uses Euclidean distance to determine the class label and Euclidean distance is not a proper similarity measure on the manifold, the results given by traditional $k$NN are quite erroneous. By introducing a weight scheme, w$k$NN can perform better than $k$NN, but the improvement is still quite limited. g$k$NN has much better results because geodesic distance on the manifold is a valid similarity measure. However, as mentioned in Section 1, graph distance tends to be sensitive to short-circuit phenomenon (i.e. the noise points lying between the two classes), thus g$k$NN still misclassifies many samples due to the existence of noisy points. In contrast, m$k$NN achieves the best results, because TRW takes all the possible graph paths into consideration, thus it embodies the global geometrical structure information of the manifold and can be much more effective and robust to noisy points.

Figure \ref{SynDatasets_MeanErr} plots the mean error rate of each algorithm over 10 runs  on these data sets, as $k$ changes from 1 to 10. In each run, $k$ labeled samples are randomly selected from each class and the rest of the samples in the data set are treated as unlabeled samples to form the testing set.
 \begin{figure}[H]
   \subfigure[Dataset 1]{
   \includegraphics[width=0.31\textwidth]{TwoCircleMeanErr.png}}
   \subfigure[Dataset 2]{
   \includegraphics[width=0.31\textwidth]{knotMeanErr.png}}
   \subfigure[Dataset 3]{
   \includegraphics[width=0.31\textwidth]{circlerubMeanErr.png}}
  \caption{Experimental results on synthetic data sets. Mean error rate on the ordinate and $k$ on the abscissa.}
  \label{SynDatasets_MeanErr}
\end{figure}
From the results in Figure \ref{SynDatasets_MeanErr} we can see that m$k$NN performs significantly better than other version of $k$NN algorithms. It is interesting to note that on these manifold distributed data sets, while the mean error rates of $k$NN and w$k$NN have no obvious reduction as $k$ increases, the mean error rates of g$k$NN and m$k$NN decrease quickly. This indicates that g$k$NN and m$k$NN are able to exploit the information contained in the labeled samples in a more "efficient" way, because they take the manifold structure information into account. Again, m$k$NN achieves the lowest error rate.

In order to demonstrate the effectiveness of the weight reconstruction method, we run the algorithm on these data sets to reconstruct each sample and its TRW weight using its $k$ nearest neighbours with equation (1.7) and (1.8), respectively. The relative mean square error (RMSE) of the reconstruction result is computed by
$$RMSE(T,R)=\frac{{{\left\| T-R \right\|}^{2}}}{{{\left\| T \right\|}^{2}}}\times 100\%$$
where $T$ is the ground truth and $R$ is the reconstructed result. The results are shown in Table \ref{ReconstructRMSE}.
\begin{table}[h]
\centering
\footnotesize
\caption{Reconstruction error of the synthetic data sets (\%).}
\label{ReconstructRMSE}
\begin{tabular}{ c c c c c} \toprule \hline
                                                                                & data set 1      & data set 2      &data set 3     &     \\ \cmidrule(r){2-4}
\emph{RMSE($X$, $\hat X$)}                                  & 0.0724             & 0.2734              &0.1606       &\\ \cmidrule(r){2-4}
\emph{RMSE($P_{TRW}$, $\hat P_{TRW}$)}      & 0.5075               & 1.0524                &1.9061          & \\ \hline \bottomrule
\end{tabular}

\end{table}
From these results we can see that the reconstruction method in equation (\ref{OptWeight}) and (\ref{ReconstructWeight}) can produce a very accurate approximation to the true samples and weights, respectively, on nonlinear manifold data sets.

\subsection{Experimental results on real-world data sets}
We also conduct experiments on six real-world data sets from the UCI data repository, which contains real application data collected in various fields and is widely used to test  the performance of different machine learning algorithms\footnote{UC Irvine Machine Learning Repository: http://archive.ics.uci.edu/ml/.}.  The information on these six data sets is listed in Table \ref{DataInfo} ($n$: number of samples; $d$: feature dimension; $C$: class number).

\begin{table}[h]
\centering
\footnotesize
\caption{Information on the experimental data sets.}
\label{DataInfo}
\begin{tabular}{ c c c c c c c} \toprule \hline
      & usps      & segmentation      &banknote      &pendigits     & multifeature         &statlog    \\ \cmidrule(r){2-7}
\emph{n}   & 9298      & 2086      &1348      &10992     & 2000         &6435    \\ \cmidrule(r){2-7}
\emph{d}   & 256      & 19   &4  &16     & 649           & 36  \\ \cmidrule(r){2-7}
\emph{C}   & 10      & 6   &2  &10     &10            &6  \\ \hline \bottomrule
\end{tabular}

\end{table}
On each data set, we let $k$ change from 1 to 10. For each $k$, we run each algorithm 10 times, with a training set containing $k$ labeled samples randomly selected from each class and a testing set containing all the rest samples. The final error rate is the mean of the 10 error rates and is shown in Figure \ref{RealWorldResults}.

From Figure \ref{RealWorldResults}, we can see that the proposed m$k$NN outperforms the other algorithms in terms of both  the accuracy and stability of  performance. The error curves of m$k$NN decrease much more quickly than that the other algorithms, which indicates that m$k$NN is able to utilize fewer labeled samples to achieve better accuracy. This is very important in applications where there is a very small amount of labeled samples available, because labeled samples are usually more expensive to obtain, i.e. they need to be annotated by human with expert knowledge and/or special equipment and take a lot of time.  Therefore, it is of great practical value that a classifier is capable of accurately classifying abundant unlabeled samples, given only a small number of labeled samples.

From Figure \ref{RealWorldResults}, we can also conclude that: (1) by introducing a weight scheme in the traditional $k$NN algorithm,  weighted $k$NN (w$k$NN) can generally outperform traditional $k$NN; (2) the performance of geodesic $k$NN (g$k$NN) has a relative large improvement to both $k$NN and weighted $k$NN for most cases, because geodesic distance is a valid measure on manifold; (3) the manifold $k$NN (m$k$NN) almost always achieves the smallest error rate, because the constrained TRW is a more effective and robust measure of the global geometrical structure on manifold and, meanwhile, m$k$NN can take both the class information and constraint information into account.
 \begin{figure}[H]
  \subfigure[usps]{
   \includegraphics[width=0.47\textwidth]{usps_gkNN.png}}
   \subfigure[segmentation]{
   \includegraphics[width=0.47\textwidth]{segmentation_gkNN.png}}

   \subfigure[banknote]{
   \includegraphics[width=0.47\textwidth]{banknote_gkNN.png}}
   \subfigure[pendigits]{
   \includegraphics[width=0.47\textwidth]{pendigits_gkNN.png}}

   \subfigure[multifeature]{
   \includegraphics[width=0.47\textwidth]{multifeature_gkNN.png}}
   \subfigure[satlog]{
   \includegraphics[width=0.47\textwidth]{satlog_landsat_gkNN.png}}
  \caption{Experimental results on six real-world data sets. Mean error rate on the ordinate and $k$ on the abscissa.}
  \label{RealWorldResults}
\end{figure}
\subsection{Experimental results of the comparison with other traditional supervised classifiers}
 We  conduct experiments to compare the performance of the proposed manifold $k$NN algorithm with other popular supervised classifiers on the six real-world data sets. The baseline algorithms are: Support Vector Machine (SVM)\footnote{For SVM we use the libsvm toolbox: \url{https://www.csie.ntu.edu.tw/~cjlin/libsvm/}. Other algorithms we use MATAB toolbox.}, Artificial Neural Networks (ANN), Naive Bayes (NB) and Decision Tree (DT). The configurations of the baseline algorithms are: radial basis kernel for SVM; three-layer  networks trained with back-propagation for ANN; kernel smoothing density estimation for NB; binary classification tree and merging-pruning strategy according to validation error for DT. We adopt a grid-search strategy to tune the parameters of each algorithm and the parameters are set to  produce the lowest 2-fold cross validation error rate.

 To examine the capability of classifying plenty of unlabeled samples with only a few labeled samples, we randomly choose three  labeled samples from each class to form the training set and the remaining samples are treated as unlabeled samples to form the testing set. Each algorithm runs 10 times and the final result is the average of these 10 error rates.  The experimental results (mean error $\pm$ standard deviation) are shown in Table \ref{TabResultRealXU}.
\begin{table}[h]
\caption{Experimental results on real-world data sets (error rate: \%)}
\label{TabResultRealXU}
\footnotesize
\centering
\settowidth \rotheadsize{\theadfont Second multilined}
\begin{tabular}{l c c c c c}\\
\toprule \hline
{} &SVM &ANN &NB & DT& m$k$NN \\ \cmidrule(r){2-6}
usps &77.35$\pm$4.6 & 40.96$\pm$4.3 & 34.73$\pm$4.9 & 73.96$\pm$8.4 & \textbf{19.37$\pm$3.9} \\ \cmidrule(r){2-6}
segmentation &66.54$\pm$8.7 &42.54$\pm$3.8 &50.83$\pm$4.3&49.55$\pm$2.6&\textbf{24.18$\pm$4.5} \\ \cmidrule(r){2-6}
banknote &70.01$\pm$14.7 &23.03$\pm$6.2 &28.37$\pm$7.8&44.43$\pm$0.4&\textbf{9.73$\pm$6.9}\\ \cmidrule(r){2-6}
pendigits &49.41$\pm$12.3 &44.02$\pm$27.4 &42.36$\pm$6.2&80.83$\pm$11.3 &\textbf{12.51$\pm$2.3}\\ \cmidrule(r){2-6}
multifeature &82.89$\pm$6.4 &50.53$\pm$24.2 &26.89$\pm$2.9&76.14$\pm$2.9&\textbf{15.36$\pm$2.3} \\ \cmidrule(r){2-6}
satlog &57.26$\pm$17.1 &30.15$\pm$4.9 &28.81$\pm$5.9&72.55$\pm$13.5&\textbf{21.07$\pm$8.0} \\
\hline \bottomrule\\
\end{tabular}
\end{table}

From these results, we can see that m$k$NN  significantly outperform  these traditional supervised classifiers, given only three labeled samples per class. Similar to traditional $k$NN, traditional supervised classifiers are incapable of exploiting the manifold structure information of the underlying data distribution, thus their accuracies are very low while the labeled sample number is very small. Furthermore, when the labeled samples are randomly selected, their positions vary greatly in data space. Sometime they are not uniformly distributed and thus cannot well cover the whole data distribution. As a result, the performance of traditional classifiers also varies greatly. In contrast, because m$k$NN adopts tired random walk to measure manifold similarity which reflects the global geometrical  information of the underlying manifold structure and is robust to local changes. \cite{tu2014novel}, it can achieve much better results.

To further investigate the performance of these algorithms under the condition of providing different number of training samples, we carry out experiments with different training set sizes. For each data set, we let $k$ varies from 1 to 40 ($k=1, 3, ..., 39$) and randomly choose $k$ labeled samples from each class to form the training set. The rest of the data set are treated as unlabeled samples to test each algorithm's performance. For each $k$, every algorithm runs 10 times on each data set.  The mean error rate and standard deviation of the 10-run results are shown in Figures \ref{RealWorldResults_mean} and \ref{RealWorldResults_std}, respectively.

From Figure \ref{RealWorldResults_mean} we can see that while the labeled sample number is small, the error rates of the traditional algorithms are very large (as also indicated in Table \ref{TabResultRealXU} which contains the results of the three labeled samples per class). As the number of labeled sample increases, the error rates decrease. This trend becomes slower after 15 labeled samples per class. The proposed m$k$NN achieves the lowest error rate for both situations of small and large number of labeled samples. The improvement is especially obvious and significant when the labeled samples number is small. From Figure \ref{RealWorldResults_std}, we can also see that the performance of m$k$NN is also relatively steady for most cases. One should note that on the left of each plot in Figure \ref{RealWorldResults_std}, the small standard deviation values of decision tree (DT) and SVM are due to the fact that their error rates are always very high in each run (e.g. the error rates of SVM on data set \emph{usps} concentrate closely around 95).
 \begin{figure}[H]
  \subfigure[usps]{
   \includegraphics[width=0.47\textwidth]{usps_all2.png}}
   \subfigure[segmentation]{
   \includegraphics[width=0.47\textwidth]{segmentation2.png}}

   \subfigure[banknote]{
   \includegraphics[width=0.47\textwidth]{banknote2.png}}
   \subfigure[pendigits]{
   \includegraphics[width=0.47\textwidth]{pendigit2.png}}

   \subfigure[multifeature]{
   \includegraphics[width=0.47\textwidth]{multifeature.png}}
   \subfigure[satlog]{
   \includegraphics[width=0.47\textwidth]{satlog2.png}}
  \caption{Experimental results on six real-world data sets. Mean error rate on the ordinate and  labeled samples number per class  on the abscissa.}\label{RealWorldResults_mean}
\end{figure}

 \begin{figure}[H]
  \subfigure[usps]{
   \includegraphics[width=0.47\textwidth]{usps_std.png}}
   \subfigure[segmentation]{
   \includegraphics[width=0.47\textwidth]{segmentation_std.png}}

   \subfigure[banknote]{
   \includegraphics[width=0.47\textwidth]{banknote_std.png}}
   \subfigure[pendigits]{
   \includegraphics[width=0.47\textwidth]{pendigit_std.png}}

   \subfigure[multifeature]{
   \includegraphics[width=0.47\textwidth]{multifeature_std.png}}
   \subfigure[satlog]{
   \includegraphics[width=0.47\textwidth]{satlog_std.png}}
  \caption{Experimental results on six real-world data sets. Standard deviation of error rates on the ordinate and labeled samples number per  class on the abscissa.}\label{RealWorldResults_std}
\end{figure}

\subsection{Experimental results of time complexity}
To examine the effectiveness and efficiency of the proposed sequential learning strategy in Section 5, we conduct experiments on  three real-world data sets \emph{banknote,satlog} and $pendigits$ to show the difference of m$k$NN's performance with and without sequential learning algorithm. Each data set is divided into three subsets: training set, validation set and online set. The training set is fixed to contain 10 labeled samples per class. We conduct 10 experiments, with the online set size changes from 100 to 1000 with step size 100. The validation set contains the rest of the samples. First, m$k$NN  runs on training set and validation set to learn the class distribution. Thereafter, at each time a sample is drawn from the online set as a new coming sample. For sequential m$k$NN, the previous learning result is used  to classify the new sample according to  equation (\ref{OptWeight}) and equation (\ref{ReconstructWeight}). For standard m$k$NN, the new sample is added to the validation set and the whole learning process is repeated to classify the new sample. The experimental results\footnote{The configuration of our computer: 16GB RAM, double-core 3.7GHz Intel Xeon CPU and MATLAB 2015 academic version.} are shown in Figure \ref{SeqExperiment}.

From these results, we can see that while the classification accuracy of standard m$k$NN and sequential m$k$NN are comparable, the time cost of sequential m$k$NN reduces dramatically for online classification (e.g., for \emph{satlog} data set, to classify 1000 sequentially coming samples, standard m$k$NN takes about 9100 seconds but sequential m$k$NN uses only about 14 seconds to achieve a similar result). Therefore, the sequential algorithm has great merit in solving the online classification problem and can be potentially applied to a wide range of transductive learning algorithms to make them inductive.

We also conduct experiments to compare the time complexity of all the baseline algorithms with the proposed m$k$NN on these three data sets. Each data set is split  into \emph{training} and \emph{testing} parts three times independently, with splitting ratios 10\%, 25\% and 50\%, respectively. For each split, every  algorithm runs 10 times and the mean time cost is recorded. Table \ref{TimeCostExperiment} shows the experimental results (the second column shows the splitting ratio).

 \begin{figure}[H]
  \subfigure[Satlog data set]{
   \includegraphics[width=0.45\textwidth]{satlog_sq_time_log.png}
   \includegraphics[width=0.45\textwidth]{satlog_sq_err.png}}

   \subfigure[Banknote data set]{
      \includegraphics[width=0.45\textwidth]{banknote_sq_time_log.png}
   \includegraphics[width=0.45\textwidth]{banknote_sq_err.png}}

   \subfigure[Pendigits data set]{
      \includegraphics[width=0.45\textwidth]{pendigits_sq_time_log.png}
   \includegraphics[width=0.45\textwidth]{pendigits_sq_err.png}}
    \caption{Experimental results of the comparison between standard m$k$NN and sequential m$k$NN to classify online samples real-world data sets.}\label{SeqExperiment}
\end{figure}

\begin{table}[ht]
\caption{Comparison of overall time for training and testing on three data sets (sec)}
\label{TimeCostExperiment}
\centering
\renewcommand\arraystretch{0.4}
\footnotesize
\begin{tabular*}{0.93\textwidth}{@{}ccrrrrrrrr}\toprule \midrule
data     &  (\%)     & SVM     &DT     &ANN        &NB   &$k$NN & w$k$NN & g$k$NN &m$k$NN\\ \midrule \midrule
           &10          &0.01     &0.14    & 0.23      &0.09       &0.03          &0.02        &1.23      &0.19    \\ \cmidrule(r){3-10}
banknote&25       &0.01     &0.19    & 0.24      &0.09        &0.04         &0.03        &1.23    &0.20    \\  \cmidrule(r){3-10}
           &50          &0.02     &0.29    & 0.27      &0.08        &0.05        &0.05         &1.26     &0.20   \\ \midrule
           &10          &0.47     & 0.43    & 0.59      &7.14       &0.13         &0.14        &31.99    &6.01    \\ \cmidrule(r){3-10}
satlog  &25          &1.78     &1.16    & 1.58      &7.56         &0.24         &0.29      &32.55    &6.08    \\  \cmidrule(r){3-10}
           &50         &5.12     &3.11    & 4.01     &7.61           &0.31         &0.40      &32.82     &6.30    \\ \midrule
           &10         &0.44     &0.78    & 0.70      &8.70          &0.22         &0.28      &149.14   &25.27   \\ \cmidrule(r){3-10}
pendigits&25         &0.86     &2.28    & 2.65      &8.46        &0.41         &0.59      &146.89   &26.11    \\  \cmidrule(r){3-10}
           &50         &1.55     &6.09   & 5.06      &6.93           &0.54         &0.80       &145.71    &25.35    \\ \midrule  \bottomrule
\end{tabular*}
\end{table}

From this table we can see that the algorithms fall into two categories according to their time costs: one category contains SVM, DT, ANN, $k$NN and w$k$NN, whose time costs are closely related with the training data set size. Another category includes NB, g$k$NN and m$k$NN, whose time costs depend more upon the overall data set size.   SVM, $k$NN and w$k$NN are generally faster than others. Although m$k$NN is the second slowest one,  it is still much faster than g$k$NN and its overall time does not prolong as the training set size increases.  It should be mentioned that although the classification accuracy of m$k$NN is much better than  $k$NN and other traditional supervised classifiers,  the computational complexity of m$k$NN is also higher ($O(n^3)$) than traditional $k$NN ($O(n)$). Directly computing   $P_{TRW}$ matrix is time cost, since it is not   symmetrical, positive definite matrix and thus a LU decomposition has to be used. One way to speed-up matrix inverse is to convert  $P_{TRW}$ to a symmetrical, positive definite matrix and then adopt the Cholesky decomposition, whose computational cost is just a half of the LU decomposition \cite{golub2012matrix}. Noting that  ${{P}_{TRW}}={{\left( I-\alpha {{D}^{-1}}W \right)}^{-1}}={{D}^{1/2}}{{\left( I-\alpha {{D}^{-1/2}}W{{D}^{-1/2}} \right)}^{-1}}{{D}^{-1/2}}={{D}^{1/2}}{{R}^{-1}}{{D}^{-1/2}}$, where $R=I-\alpha {{D}^{-1/2}}W{{D}^{-1/2}}$ is  a symmetrical, positive definite matrix\footnote{$R$ is apparently symmetrical because $W$ is symmetrical (Let $W=(W+W^T)/2$ if $W$ is not symmetrical). We prove its positive definiteness. Because the spectral radius of $P_{TRW}$ is in (0, 1) and $P_{TRW}$ is similar to $R^{-1}$, so spectral radius of $R^{-1}$ is in (0, 1). So all eigenvalues of $R$ are positive. Therefore $R$ is a positive definite, symmetrical matrix.}, we can first  inverse matrix $R$ using Cholesky decomposition and then compute $P_{TRW}$ with very small computational cost. Our following work will be focused on  the further reduction of computational complexity.
\section{Conclusions}
In this paper we proposed a new $k$ nearest-neighbor algorithm, m$k$NN, to classify nonlinear manifold distributed data as well as traditional Gaussian distributed data, given a very small amount of labeled samples. We also presented an algorithm to attack the problem of high computational cost for classifying  online data with m$k$NN and other transductive algorithms. The superiority of the m$k$NN has been demonstrated by substantial experiments on both synthetic data sets and real-world data sets.  Given the widespread appearance of manifold structures in real-world problems and the popularity of the traditional $k$NN algorithm, the proposed manifold version $k$NN shows promising potential for classifying manifold-distributed data.

\textbf{Acknowledgements}: The authors wish to thank the anonymous reviewers for reading the entire manuscript and offering many useful suggestions. This research is partly supported by NSFC, China (No: 61572315) and 973 Plan,China (No. 2015CB856004). The research is also partly supported by YangFan Project (Grant No. 14YF1411000) of Shanghai Municipal Science and Technology Commission, the Innovation Program (Grant No. 14YZ131) and the Excellent Youth Scholars (Grant No. sdl15101) of Shanghai Municipal Education Commission, the Science Research Foundation of Shanghai University of Electric Power (Grant No. K2014-032).

\bibliographystyle{elsarticle-harv}