# Extremal results on $G$-free colorings of graphs

Yaser Rowshan1 1Y. Rowshan Department of Mathematics, Institute for Advanced
Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran
<EMAIL_ADDRESS>
###### Abstract.

Let $H=(V(H),E(H))$ be a graph. A $k$-coloring of $H$ is a mapping
$\pi:V(H)\longrightarrow\\{1,2,\ldots,k\\}$ so that each color class induces a
$K_{2}$-free subgraph. For a graph $G$ of order at least $2$, a $G$-free
$k$-coloring of $H$ is a mapping $\pi:V(H)\longrightarrow\\{1,2,\ldots,k\\}$
so that the subgraph of $H$ induced by each color class of $\pi$ is $G$-free,
i.e. contains no copy of $G$. The $G$-free chromatic number of $H$ is the
minimum number $k$ so that there is a $G$-free $k$-coloring of $H$, denoted by
$\chi_{G}(H)$. A graph $H$ is uniquely $k$-$G$-free colouring if
$\chi_{G}(H)=k$ and every $k$-$G$-free colouring of $H$ produces the same
color classes. A graph $H$ is minimal with respect to $G$-free, or $G$-free-
minimal, if for every edges of $E(H)$ we have
$\chi_{G}(H\setminus\\{e\\})=\chi_{G}(H)-1$. In this paper we give some bounds
and attribute about uniquely $k$-$G$-free colouring and $k$-$G$-free-minimal.

###### Key words and phrases:

Conditional Chromatic number, $G$-free coloring, uniquely $k$-$G$-free,
$G$-free minimal.

###### 2010 Mathematics Subject Classification:

05C15, 05C35.

##  1\. Introduction

All graphs $G$ considered in this paper are undirected, simple, and finite
graphs. For given graphs $G$, we denote its vertex set, edge set, maximum
degree, and minimum degree by $V(G)$, $E(G)$, $\Delta(G)$, and $\delta(G)$,
respectively. The number of vertices of $G$ is define by $|V(G)|$. For a
vertex $v\in V(G)$, we use $\deg_{G}{(v)}$ ($\deg{(v)}$) and $N_{G}(v)$ to
denote the degree and neighbors of $v$ in $G$, respectively.

The join of two graphs $G$ and $H$, define by $G\oplus H$, is a graph obtained
from $G$ and $H$ by joining each vertex of $G$ to all vertices of $H$. The
union of two graphs $G$ and $H$, define by $G\cup H$, is a graph obtained from
$G$ and $H$, where $V(G\cup H)=V(G)\cup V(H)$ and $E(G\cup H)=E(G)\cup E(H)$.
For convenience, we use $[n]$ instead of $\\{1,2,\ldots,n\\}$. A $k$-vertex
coloring of $H$ is a partition of $V(H)$ into $k$ color classes such that
vertices in the same class are not adjacent. Moreover, $H$ is called uniquely
vertex $k$-colorable if every $k$-coloring of it induces the same partition on
$V(H)$. Also, A graph $H$ is minimal with respect to $k$-vertex coloring of
$H$, if for every edges of $E(H)$ we have $\chi(H\setminus\\{e\\})=\chi(H)-1$.

Uniquely vertex $k$-colorable have been studied by Chartrand and Geller [9],
Aksionov [1], Harary, Hedetniemi, and Robinson [12], Bollobás [3, 4],
Borwiecki and Burchardt [5], Alishahi and Taherkhani [2], and Xu [15]. An
$(n,k)$-coloring of a $H$ corresponds to the partition of $V(H)$ into $n$
color classes, so that the induces a subgraph with each color class whose
maximum degree does not exceed $k$. A graph $H$ is uniquely $(n,k)$-colorable
if it is $(n,k)$-colorable and every $(n,k)$-coloring of $H$ produces the same
color classes. M. Frick and M. A. Henning show that the following results is
true.

######  Theorem 1.

[10] Suppose $H$ be a uniquely $(n,k)$-colorable graph, where $n\geq 2$ and
$k\geq 1$. Hence:

$|V(H)|\geq n(k+1)-1.$

######  Theorem 2.

[10] For each $n\geq 2$ and $k\geq 1$, there exists a uniquely
$(n,k)$-colorable graph with $n(k+1)-1$ member.

###  1.1. $G$-free coloring.

The conditional chromatic number $\chi(H,P)$ of $H$, is the smallest integer
$k$ for which there is a decomposition of $V(H)$ into $k$ color class say
$V_{1},\ldots,V_{k}$, so that $H[V_{i}]$ satisfies the property $P$, where
$P$, is a graphical property and $H[V_{i}]$ is a the induced subgraph on
$V_{i}$, for each $1\leq i\leq k$. This extension of graph coloring was
presented by Harary in 1985 [11]. Suppose that $\operatorname{\mathcal{G}}$ be
a families of graphs, when $P$ is the feature that a subgraph induced by each
color class does not contain each copy of members of
$\operatorname{\mathcal{G}}$, we write $\chi_{\operatorname{\mathcal{G}}}(H)$
instead of $\chi(H,P)$. In this regard, we say a graph $H$ has a
$\operatorname{\mathcal{G}}$-free $k$-coloring if there is a map
$\pi:V(H)\longrightarrow\\{1,2,\ldots,k\\}$ such that each color class
$V_{i}=\pi^{-1}{(i)}$ does not contain any members of
$\operatorname{\mathcal{G}}$. For simplicity of notation if
$\operatorname{\mathcal{G}}=\\{G\\}$, then we write $\chi_{G}(H)$ instead of
$\chi_{\operatorname{\mathcal{G}}}(H)$.

An ordinary $k$-coloring of $H$ can be viewed as
$\operatorname{\mathcal{G}}$-free $k$-coloring of a graph $H$ by taking
$\operatorname{\mathcal{G}}=\\{K_{2}\\}$. It was shown that for each graph
$H$, $\chi(H)\leq\Delta(H)+1$. The well-known Brooks theorem states that for
any connected graph $H$, $\chi(H)\leq\Delta(H)$ if $H$ is a connected and is
neither an odd $C_{n}$ nor a $K_{n}$, then $\chi(H)\leq\Delta$ [6]. One can
refer to [8, 14, 13, 7, 2] and it references for further studies

A graph $H$ is uniquely $k$-$G$-free colouring if $\chi_{G}(H)=k$ and every
$k$-$G$-free colouring of $H$ produces the same color classes, and a graph $H$
is minimal with respect to $G$-free, or $G$-free-minimal, if for every edges
of $E(H)$ we have $\chi_{G}(H\setminus\\{e\\})\leq\chi_{G}(H)-1$.

In this article we investigate some properties of uniquely $k$-$G$-free and
$G$-free-minimal coloring of graphs as follow:

######  Theorem 3.

Let $H$ and $G$ be two graph and $k\geq 1$ be a integers. Assume that $H$ is
uniquely $k$-$G$-free colourable graph, hence we have:

$|V(H)|\geq k|V(G)|-1.$

######  Theorem 4.

Let $G$ be a graph with $m$ vertices and $k\geq 1$ be an integers. Then:

  * I

: There exists a $k$-$G$-free colourable graph, with $km-1$ members where
$k-1$ class has $m$ member and one class has a $m-1$ member.

  * II

: If $m\geq 2\delta(G)-1$ and $\delta(G)=1$, then there exists a uniquely
$k$-$G$-free colourable graph with $km-1$ members and if $\delta\geq 2$ then
there exist many $k$-$G$-free colourable of a graph with $km-1$ members.

  * III

: If there exists a uniquely $k$-$G$-free colourable graph with $km-1$
members, then for each $i\geq 1$ there exists a uniquely $k$-$G$-free
colourable graph with $km+i-1$ members.

######  Theorem 5.

Let $H$ and $G$ be two graph and $k\geq 1$ be a integers. Assume that $H$ is
uniquely $k$-$G$-free colourable graph, $|V(G)|=m$, $\delta(G)=\delta$,
$|E(H)|=e_{1}$ and $|E(G)|=e_{2}$, hence:

$e_{1}\geq k(e_{2}-\delta+\frac{k+1}{2}(m\delta)).$

######  Theorem 6.

$H$ is $k$-$G$-free-minimal iff either $H$ is a graph $K_{(k-1)(m-1)+1}$ minus
the edges of a $1$-factor, when $k$ is even, or $H\cong H_{1}\oplus K_{1}$,
where $H_{1}$ is a graph $K_{(k-1)(m-1)}$ minus the edges of a $1$-factor,
when $k$ is odd, where $G$ be a such connected graph with $m$-members.

##  2\. Uniquely $G$-free graph

######  Definition 7.

A graph $H$ is uniquely $k$-$G$-free colouring if $\chi_{G}(H)=k$ and every
$k$-$G$-free colouring of $H$ produces the same color classes.

In this section we investigate some properties of uniquely $k$-$G$-free
coloring of graphs and give a lower bounds on the vertices of uniquely
$k$-$G$-free graphs $H$. In the following theorem we determine a lower bound
for the size of uniquely $k$-$G$-free coloring of $V(H)$.

######  Theorem 8.

Let $H$ and $G$ be two graph and $k\geq 1$ be a integers. Assume that $H$ is
uniquely $k$-$G$-free colourable graph (u-k-G-f), then:

$|V(H)|\geq k|V(G)|-1.$

###### Proof.

Assume that $|V(H)|=n$ and $|V(G)|=m$ and let $V_{1},V_{2},\ldots,V_{k}$ be a
uniquely $k$-partition of $V(H)$ where $H[V_{i}]$ is a $G$-free class. Now,
considering the following claim.

######  Claim 9.

$|V_{i}|\geq m-1$ for each $i\in[k]$.

###### Proof.

By contrary, suppose that there exist at least one $i$ say $i=1$, such that,
$|V_{1}|\leq m-2$. Set $v\in V_{2}$ and set $V^{\prime}_{1}=V_{1}\cup\\{v\\}$,
$V^{\prime}_{2}=V_{2}\setminus\\{v\\}$ and $V^{\prime}_{i}=V_{i}$ for $i\geq
3$, hence we have $H[V^{\prime}_{i}]$ is $G$-free, a contradiction. ∎

######  Claim 10.

For at must one $i$, we have $|V_{i}|=m-1$.

###### Proof.

By contrary, suppose that $|V_{1}|=|V_{2}|=m-1$. In this case set $v_{i}\in
V_{i}$ for $i=1,2$, and set
$V^{\prime}_{1}=(V_{1}\setminus\\{v_{1}\\})\cup\\{v_{2}\\}$,
$V^{\prime}_{2}=(V_{2}\setminus\\{v_{2}\\})\cup\\{v_{1}\\}$ and
$V^{\prime}_{i}=V_{i}$ for $i\geq 3$, hence we have $H[V^{\prime}_{i}]$ is
$G$-free, a contradiction again. ∎

Now by Claim $1,2$ we have $|V(H)|\geq k|V(G)|-1$ and the proof is complete. ∎

In the next theorem we establish that the bounds in Theorem 8 is best
possible. Also we show that if there exists a uniquely $k$-$G$-free colourable
graph with $km-1$ members, then for each $i\geq 1$ there exists a u-k-G-f with
$km+i-1$ members.

######  Theorem 11.

Let $G$ be a graph with $m$ vertices and $k\geq 1$ be an integers. Then:

  * I

: There exists a $k$-$G$-free colourable graph, with $km-1$ members where
$k-1$ class has $m$ member and one class has a $m-1$ member.

  * II

: If $m\geq 2\delta(G)-1$ and $\delta(G)=1$, then there exists a u-k-G-f with
$km-1$ members and if $\delta\geq 2$ then there exist many $k$-$G$-free
colourable of a graph with $km-1$ members.

  * III

: If there exists a u-k-G-f with $km-1$ members, then for each $i\geq 1$ there
exists a u-k-G-f with $km+i-1$ members.

###### Proof.

Suppose that $H_{i}$ for $i=1,2,\ldots,k+1$ be a graph, where $H_{i}\cong
K_{m-1}$ for each $i=1,2,\ldots,k$, and $H_{k+1}\cong K_{k-1}$ where
$V(H_{k+1})=\\{v_{1},v_{2},\ldots,v_{k-1}\\}$. For each $i=1,2,\ldots,k$
define $H^{\prime}_{i}=H_{i}\cup\\{v_{i}\\}$, so that $v_{i}$ is adjacent to
at most $\delta(G)-1$ vertices of $V(H_{i})$, and define
$H^{\prime}_{k}=H_{k}$. Set $H=\oplus_{i=1}^{i=k}H^{\prime}_{i}$. Hence, we
can say that $|V(H)|=km-1$. Since $|V(H^{\prime}_{i})|=m$ and
$|N_{H^{\prime}_{i}}(v_{i})|\leq\delta-1$, we can check that for each $i$,
$H^{\prime}_{i}$ is $G$-free, that is $\chi_{G}(H)\leq k$. Now we have the
following claim:

######  Claim 12.

$\chi_{G}(H)=k.$

###### Proof.

For $k=1$ its clearly, hence assume that $k\geq 2$. By contradiction assume
that $\chi_{G}(H)\leq k-1$, and let $V_{1},V_{2},\ldots,V_{k-1}$ be a
$(k-1)$-partition of $V(H)$ where $H[V_{i}]$ is a $G$-free class. Since
$H[\cup_{i=1}^{i=k}H_{i}]\cong K_{k(m-1)}$ we have $\omega(H)\geq k(m-1)$,
hence for at least one $i$ we have $|V_{i}\cap(\cup_{i=1}^{i=k}H_{i})\geq m$ a
contradiction. That is $\chi_{G}(H)\geq k$ and the proof is complete. ∎

Therefore by Claim 12 and by definition $H$ one can say that the part (I) is
true. To prove $(II)$, by Claim 12, assume that $V_{1},V_{2},\ldots,V_{k}$ be
a $k$-partition of $V(H)$, where $H[V_{i}]$ is a $G$-free for each $i\in[k]$
and $H$ is a graph constructed in part I. Hence, it easy to check that the
following claim is true.

######  Claim 13.

$|V_{i}\cap(\cup_{i=1}^{i=k}H_{i})|=m-1$ for each $i\in[k]$.

Therefore, by Claim 13 we have the claims as follow:

######  Claim 14.

$|V_{i}|\leq m$ for $i=1,2,\ldots,k$.

###### Proof.

By contrary, suppose that $|V_{i}|\geq m+1$ for at least one $i$, say $i=1$,
and assume that $\\{x_{1},x_{2},\ldots,x_{m+1}\\}\subseteq V_{1}$. Since
$H[V_{1}]$ is $G$-free, $\chi_{G}(H)=k$ and by Claim 13, we have
$|V_{1}\cap(\cup_{i=1}^{i=k}H_{i})|=m-1$. W.l.g let
$V_{1}\cap(\cup_{i=1}^{i=k}H_{i})=\\{x_{1},x_{2},\ldots,x_{m-1}\\}$, that is
$x_{m},x_{m+1}\in V(H_{k+1})$. W.l.g suppose that $x_{m}=v_{1}$ and
$x_{m+1}=v_{2}$. So, since $H[V_{i}]$ is $G$-free,
$|N_{H}(v_{i})\cap\\{x_{1},x_{2},\ldots,x_{m-1}\\}|\leq\delta-1$, that is
$|\\{x_{1},x_{2},\ldots,x_{m-1}\\}\cap V(H_{i})|\geq m-\delta$ for $i=1,2$. As
$m\geq 2\delta-1$ one can say that there exist at least one $i\in[2]$, say
$i=1$ so that $|N_{H}(v_{1})\cap\\{x_{1},x_{2},\ldots,x_{m-1}\\}|\geq\delta$,
a contradiction to
$|N_{H}(v_{i})\cap\\{x_{1},x_{2},\ldots,x_{m-1}\\}|\leq\delta-1$, that is the
assumption does not hold and the proof of claim is complete. ∎

Now since $n=km-1$ and by Claim 12, 13 and 14, let $|V_{i}|=m$ for
$i=1,2,\ldots,k-1$ and $|V_{k}|=m-1$. So, suppose that $\delta=1$ and consider
the following claim:

######  Claim 15.

The coloring provided is unique.

###### Proof.

Consider $V_{i^{\prime}}$. Since $|V_{i^{\prime}}|=m$ for each
$i^{\prime}\in[k-1]$ then $|V_{i^{\prime}}\cap(\cup_{i=1}^{i=k}H_{i})|=m-1$ by
Claim 13, and $|V_{i^{\prime}}\cap V(H_{k})|=1$ for each $i^{\prime}\in[k-1]$,
let $v_{i^{\prime}}\in V_{i^{\prime}}\cap V(H_{k})$ for each
$i^{\prime}\in[k-1]$. If there exists $i,j\in[k]$ where $|V_{i^{\prime}}\cap
V(H_{i})|\neq 0\neq|V_{i^{\prime}}\cap V(H_{j})|$, then one can check that
$\deg_{H[V_{i^{\prime}}]}(v_{i^{\prime}})\geq 1$, therefore $G\subseteq
H[V_{i^{\prime}}]$, a contradiction. Hence, $V_{i^{\prime}}=V(H_{i})$ for one
$i\in[k]$, so, w.l.g suppose that ${i^{\prime}}=i$ for each
$i^{\prime}\in[k-1]$. Now, as $H[V_{i^{\prime}}]$ is $G$-free and $\delta=1$,
we have $v_{i^{\prime}}=v_{i}$, otherwise $G\subseteq H[V_{i^{\prime}}]$ a
contradiction again. Hence it easy to check that
$V_{i^{\prime}}=V(H^{\prime}_{i})$ for each $i^{\prime}\in[k]$ and this
coloring is unique. ∎

Therefore by Claim by 15, if $\delta(G)=1$ then the coloring provided is
unique. Now, by considering $\delta(G)$ we have the following claim:

######  Claim 16.

If, $\delta(G)\geq 2$, then the coloring provided $H$ is not unique, where $H$
is a graph as define in part I.

###### Proof.

As $\chi_{G}(H)=k$, suppose that $V_{1},V_{2}\ldots,V_{k}$ be are coloring of
$V(H)$, where, $V_{i}=V(H_{i})$ for each $i=1,2,\ldots,k$, therefore,
$H[V_{i}]$ is $G$-free. Consider $V_{i}$, for $i=1,2$, as $v_{i}\in V_{i}$ and
$|N(v_{i})\cap V_{i}|=\delta-1$ for each $i\in\\{1,2\\}$ and $\delta\geq 2$,
w.l.g suppose that $v_{i}^{\prime}\in N(v_{i})\cap V_{i}$ for each
$i\in\\{1,2\\}$. Now, considering
$V^{\prime}_{1},V^{\prime}_{2}\ldots,V^{\prime}_{k}$ be are partition of
$V(H)$, where $V^{\prime}_{i}=V_{i}$ for each $i=3,4,\ldots,k$, and
$V^{\prime}_{1}=V_{1}\setminus\\{v^{\prime}_{1}\\}\cup\\{v^{\prime}_{2}\\}$
and
$V^{\prime}_{2}=V_{2}\setminus\\{v^{\prime}_{2}\\}\cup\\{v^{\prime}_{1}\\}$.
Therefore, by definition $H$, one can check that $v_{1}v^{\prime}_{2}\in
E(H)$, $v_{2}v^{\prime}_{1}\in E(H)$, and $|N(v_{i})\cap
V^{\prime}_{i}|=\delta-1$ for each $i=\\{1,2\\}$. Hence, as,
$V_{i}=V^{\prime}_{i}$, for each $i\geq 3$, and for $i=1,2$,
$|V_{i}^{\prime}|=m$, and $|N(v_{i})\cap V^{\prime}_{i}|=\delta-1$, we can say
that $H[V^{\prime}_{i}]$ is $G$-free. Hence, since $V_{i}\neq V^{\prime}_{i}$
for $i=1,2$, we have the coloring provided $H$ is not unique. ∎

Therefore by Claim 16, if $\delta(G)\geq 2$ then the coloring provided is not
unique and by considering any $v\in V_{i}$ and ,$v^{\prime}\in V_{j}$ for each
$i,j\in[k]$ we can say there exist many $k$-$G$-free colourable of a graphs
$H$ with $km-1$ members.

To prove (III), assume that $H$ be a u-k-G-f with $km-1$ members. Suppose that
$V_{1}$, $V_{2},\ldots,V_{k}$ be the partition of $V(H)$, so that $H[V_{i}]$
is $G$-free for each $i\in[k]$ and suppose that $|V_{k}|=m-1$. Therefore,
since $H$ be a u-k-G-f, one can say that $H[V_{i}\cup\\{v\\}]$ contain a copy
of $G$ say $G_{i}$ consist of $v$, for each $v\in V_{k}$ and each $i\leq k-1$.
W.l.g assume that $V^{\prime}_{i}=N(v)\cap G_{i}$. Set
$H^{\prime}=H\cup\\{u\\}$, where $u$ is adjacent to all vertices of
$V^{\prime}_{i}$, for each $i=1,2,\ldots,k-1$. Now, in $H^{\prime}$, for
$i=1,\ldots,k$ set $W_{i}$, so that $W_{i}=V_{i}$ for each $i\leq k-1$ and
$W_{k}=V_{k}\cup\\{u\\}$. As, $W_{i}=V_{i}$ for each $i\leq k-1$, $N(u)\cap
V_{k}=\emptyset$ and $H$ be a u-k-G-f, one can check that, $H^{\prime}$ be a
u-k-G-f graph with $km$ members. By this way it is easy to check that for each
$i\geq 1$ there exists a uniquely $k$-$G$-free colourable graph with $km+i-1$
members. ∎

Suppose that $H$ is uniquely $k$-$G$-free graph where $|E(H)|=e_{1}$ and
$|E(G)|=e_{2}$, in the following theorem we determine a lower bound for the
size of $E(H)$.

######  Theorem 17.

Let $H$ and $G$ be two graph and $k\geq 1$ be a integers. Suppose that $H$ is
u-k-G-f, where $|V(G)|=m$, $\delta(G)=\delta$, $|E(H)|=e_{1}$ and
$|E(G)|=e_{2}$, then:

$e_{1}\geq k(e_{2}-\delta+\frac{k+1}{2}(m\delta)).$

###### Proof.

Suppose that $|V(H)|=n$, $|V(G)|=m$ and let $V_{1},V_{2},\ldots,V_{k}$ be a
uniquely $k$-partition of $V(H)$ where $H[V_{i}]$ is a $G$-free class. As $H$
is u-k-G-f, one can say that for any $i\in\\{1,2,\ldots,k\\}$ and each $v\in
V_{i}$, we have $G\subseteq H[V_{j}\cup\\{v\\}]$, for each $j\neq i$, that is
$|E(H[V_{i}])|\geq e_{2}-\delta$ and $|N_{V_{j}}(v)|\geq\delta$. Therefore it
is easy to check that,
$e_{1}=\sum_{i=1}^{i=k}|E(H[V_{i}])+\sum_{i=1}^{i=k-1}e_{i_{j}}$ where
$e_{i_{j}}=\sum_{j=i+1}^{j=k}|E(H[V_{i},V_{j}])$ for each
$i\in\\{1,2,\ldots,k\\}$. It is easy to say that $e_{i_{j}}\geq(k-i)m\delta$
for each $i$. Hence, one can check that:

$e_{1}\geq
k(e_{2}-\delta)+\frac{k(k+1)}{2}(m\delta)=k(e_{2}-\delta+\frac{k+1}{2}(m\delta)).$

Which means that the proof is complete. ∎

In the next results we give some attribute about uniquely $k$-$G$-free
colouring. It is easy to check that the following results is true.

######  Corollary 18.

Let $H$ and $G$ be two graph and $k\geq 1$ be a integers. Assume that $H$ is
u-k-G-f where $|V(G)|=m$, $\delta(G)=\delta$, hence we have:

  * •

For each $t\leq k-1$, the subgraph induced on the union of any $t$ colour-
classes of the unique colouring is an uniquely $t$-$G$-free colourable graph.

  * •

Each vertex $v\in V(H)$ is adjacent with at least $\delta$ vertex in every
colour class other than the colour class containing $v$, which means that in
$H$, $\delta(H)\geq(k-1)\delta$.

######  Theorem 19.

Let $H$ and $G$ be two graph and $k\geq 1$ be a integers. Assume that $H$ is
u-k-G-f where $|V(G)|=m$, $\delta(G)=\delta$, hence:

If for a vertex $v$ of $H$ we have $\deg(v)=(k-1)\delta$ and the colour class
of $v$ contains more than $m$ vertex, then $H\setminus\\{v\\}$ is also u-k-
G-f.

###### Proof.

Suppose that $H$ be a u-k-G-f, and assume that $V_{1}$, $V_{2},\ldots,V_{k}$
be the partition of $V(H)$, so that $H[V_{i}]$ is $G$-free, $|V_{1}|=m+1$ and
there exist a vertex of $V_{1}$ say $v$ so that $\deg(v)=(k-1)\delta$. As $H$
be a u-k-G-f, one can say that $|N(v)\cap V_{i}|=\delta$ for each
$i\in\\{2,3,\ldots,k\\}$. Otherwise if there exist at least one $i$, so that
$|N(v)\cap V_{i}|\leq\delta-1$, then one can say that $H[V_{i}\cup\\{v\\}]$ is
a $G$-free class, hence set $V^{\prime}_{1}=V_{1}\setminus\\{v\\}$,
$V^{\prime}_{i}=V_{i}\cup\\{v\\}$ and $V^{\prime}_{j}=V_{j}$ for each
$j\in[k],j\neq 1,i$. Therefore, for each $i\in[k]$, $H[V^{\prime}_{i}]$ is
$G$-free, a contradiction. Now considering the following claim:

######  Claim 20.

$H^{\prime}=H\setminus\\{v\\}$ is u-k-G-f.

###### Proof.

As $|V_{1}|\geq m+1$, and $H$ be a u-k-G-f, one can say that
$H^{\prime}=H\setminus\\{v\\}$ is $k$-$G$-free colourable, by considering
$V_{1}\setminus\\{v\\}$, $V_{2},\ldots,V_{k}$. Now, by contrary suppose that
the coloring provided $H^{\prime}$ is not unique. Therefore as $H$ be a u-k-
G-f and the coloring provided $H^{\prime}$ is not unique, then there exist a
vertex $u$ of some $V_{i}(i\geq 2)$ say $u\in V_{i}$ so that
$V^{\prime}_{1}=V_{1}\cup\\{u\\}$, $V^{\prime}_{i}=V_{i}\setminus\\{u\\}$ and
$V^{\prime}_{j}=V_{j}$ for each $j\geq 2$ and $j\neq i$ be a new $k$-$G$-free
color class of $V(H^{\prime})$. W.l.g we may suppose that $i=2$. As $H$ be a
u-k-G-f, one can say that $uv\in E(H)$. Now as $uuv\in E(H)$ and $|N(v)\cap
V_{i}|=\delta$ for each $i\in\\{2,3,\ldots,k\\}$, one can check that
$V^{\prime}_{1}=(V_{1}\cup\\{u\\})\setminus\\{v\\}$,
$V^{\prime}_{2}=(V_{2}\setminus\\{u\\})\cup\\{v\\}$ and $V^{\prime}_{j}=V_{j}$
for each $j\geq 3$ be a new $k$-$G$-free color class of $V(H)$, a
contradiction. ∎

Hence, by Claim 20 the proof is complete. ∎

##  3\. $G$-free minimal

######  Definition 21.

A graph $H$ is vertex-minimal with respect to $G$-free, or $G$-free-vertex-
minimal for short, if for every vertex of $V(H)$,
$\chi_{G}(H\setminus\\{v\\})\leq\chi_{G}(H)-1$.

In this section we investigate some properties of $G$-free-vertex-minimal
(G-f-v-m) coloring of graphs and give some lower bounds on the vertices of
G-f-v-m graphs $H$. The following theorem establishes a lower bound for the
size of G-f-v-m coloring of $H$.

######  Theorem 22.

Let $H$ and $G$ be two graph and $k\geq 1$ be a integers. Assume that $H$ is
k-G-f-v-m graphs, then:

$|V(H)|\geq(k-1)(|V(G)|-1)+1.$

###### Proof.

Suppose that $|V(H)|=n$, $|V(G)|=m$ and let $V_{1},V_{2},\ldots,V_{k}$ denote
the partite sets of $V(H)$, so that $H[V_{i}]$ for each $i\in[k]$ is $G$-free
and $H[V_{i}]$ is a maximal $G$-free class of
$H\setminus(\cup^{j=i-1}_{j=1}V_{j})$ for each $i=i,\ldots,k$. As
$\chi_{G}(H)=k$, we can say that $|V_{k}|\geq 1$. Assume that $v\in V_{k}$.
Therefore by maximality $V_{i}$, one can say that $H[V_{i}\cup\\{v\\}]$ for
each $i\leq k-1$, contain a copy of $G$, that is $|V_{i}|\geq m-1$ for each
$1\leq i\leq k-1$. Hence:

$|V(H)|\geq(k-1)(|V(G)|-1)+1.$

∎

By Theorem 22 it is easy to say that the following results is true.

######  Theorem 23.

Let $H$ and $G$ be two graphs where $|V(H)|=(k-1)(|V(G)|-1)+1$ for some $k\geq
2$. If there exist a subsets of $V(H)$ say $S$, where $|S|\geq|V(G)|$, then:

$\chi_{G}(H)\leq k-1.$

By Theorem 23, one can say that $K_{(k-1)(|G|-1)+1}$ be a $k$-$G$-free graphs,
for each $G$. We shall now construct k-G-f-v-m graphs with order
$(k-1)(|V(G)|-1)+1$. Suppose that for $i=1,2,\ldots k-1$, $H_{i}$ denote a
$K_{(m-2)}$ and $H_{k}\cong K_{k}$, where $k\leq m-1$. Set
$H_{1}=\oplus_{i-1}^{i=k-1}H_{i}\cong K_{(k-1)(m-2)}$ and suppose that
$V(H_{k})=\\{v_{1},v_{2},\ldots,v_{k}\\}$. Let for each
$i\in\\{1,2,\ldots,k-1\\}$ denote a $H^{\prime}_{i}=H_{i}\cup\\{v_{i}\\}$,
where $v_{i}$ is adjacent to $m-3$ vertices of $V(H_{i})$ and
$H^{\prime}_{k}=\\{v_{k}\\}$, say $v_{i}w^{i}_{m-2}\notin E(H^{\prime})$,
where $w^{i}_{m-2}$ be a vertex of $H_{i}$ for each
$i\in\\{1,2,\ldots,k-1\\}$. Now, set $H^{*}=\oplus_{i-1}^{i=k}H^{\prime}_{i}$.
Not that $|V(H^{*})|=(k-1)(m-1)+1$ and $\delta(H^{*})=(k-1)(m-1)-1$. Assume
that $\operatorname{\mathcal{F}}$ denote a family of connected subgraph of
$K_{m}$ with $m$ vertices and minus the edges of a $tK_{2}$ where
$t=\frac{m}{2}$. Now, we have the following theorems:

######  Theorem 24.

For each $G\in\operatorname{\mathcal{F}}$, $H^{*}$ is $k$-$G$-free-vertex-
minimal.

###### Proof.

Since $k\leq m-1$, we can say that $H_{i}$ is $G$-free, that is
$\chi_{G}(H)\leq k$. As $H_{1}\cong K_{(k-1)(m-2)}\subseteq H^{*}$,
$|\omega(H^{*})|\geq(k-1)(m-2)$ and by denote $H^{*}$, we can check that
$|\omega(H^{*})|=(k-1)(m-2)+1$. W.l.g, suppose that
$V^{\prime}=\\{x_{1},\ldots,x_{(k-1)(m-2)}\\}\subseteq V(H^{*})$, where
$H^{*}[V^{\prime}]\cong K_{(k-1)(m-2)}$. Now, we have the claims as follow:

######  Claim 25.

For any $S$ subsets of $V(H^{*})$ with $m$ member, $G\subseteq H^{*}[S]$.

###### Proof.

Suppose that $S=\\{s_{1},\ldots,s_{m}\\}$. Consider $|S\cap V^{\prime}|$. If
$|S\cap V^{\prime}|\geq m-1$, then one can say that $K_{m}\setminus e\subseteq
H^{*}[S]$, therefore $G\subseteq H^{*}[S]$. Now, suppose that $|S\cap
V^{\prime}|\leq m-2$. Assume that $|\omega(H^{*}[S])|=t$, and w.l.g suppose
that $S^{\prime}=\\{s_{1},\ldots,s_{t}\\}\subseteq S$, where
$H^{*}[S^{\prime}]\cong K_{t}$. Consider $\overline{S^{\prime}}=S\setminus
S^{\prime}$. As $|\omega(H^{*}[S])|=t$, we can say that $|N_{H}(s)\cap
S^{\prime}|\leq t-1$ for each
$s\in\overline{S^{\prime}}=\\{s_{t+1},\ldots,s_{m}\\}$. As,
$\delta(H^{*})=(k-1)(m-1)-1$ and $H^{*}[S]\subseteq H^{*}$, we can say that
$|N_{H}(s)\cap S^{\prime}|=t-1$ for each $s\in S^{\prime}$ and
$H^{*}[\overline{S^{\prime}}]\cong K_{m-t}$, otherwise we can fined a vertex
of $S$ say $w$, so that $\deg_{H^{*}}(w)\leq(k-1)(m-1)-2$, a contradiction.
Since $|\omega(H^{*}[S])|=t$ and $H^{*}[\overline{S^{\prime}}]\cong K_{m-t}$,
$t\geq m-t$, that is $m\leq 2t$. Therefore we can check that
$H^{*}[S]\cong(K_{m}\setminus\frac{m-t}{2}K_{2})$. Now, as
$G\in\operatorname{\mathcal{F}}$ and $t\geq\frac{m}{2}$, we have $G\subseteq
K_{m}\setminus\frac{m}{2}K_{2}\subseteq H^{*}[S]$. ∎

Therefore, as $|V(H^{*})|=(k-1)(m-1)+1$ and by Claim 25 we can say that
$\chi_{G}(H)=k$. Assume that $v$ be any vertex of $V(H^{*})$, set
$H^{\prime\prime}=H^{*}\setminus\\{v\\}$. As
$|V(H^{\prime\prime})|=(k-1)(m-1)$, and $|G|=m$, we can decomposition of
$V(H^{\prime\prime})$ into $k-1$ class, where each class have $m-1$ member,
that is $\chi_{G}(H^{\prime\prime})\leq k-1$, which means that, $H^{*}$ is
k-G-f-v-m, and the proof of theorem is complete. ∎

As, $H^{*}$ is k-G-f-v-m, it is easy to say that, for each graps $G$ with $m$
vertices and each subgraphs $H$ of $K_{(k-1)(m-1)+1}$, such that
$H^{*}\subseteq H$, we have $H$ is k-G-f-v-m.

######  Definition 26.

A graph $H$ is minimal with respect to $G$-free, or $G$-free-minimal, if for
every edges of $E(H)$ we have $\chi_{G}(H\setminus\\{e\\})=\chi_{G}(H)-1$.

In this following results we investigate some properties of $G$-free-minimal
coloring of graphs and give a lower bounds on the vertices of $G$-free-minimal
graphs $H$. By argument similar to the proof of Theorem 22 in the following
theorem establishes a lower bound for the size of $G$-free-minimal coloring of
$H$.

######  Theorem 27.

Let $H$ and $G$ be two graph and $k\geq 1$ be a integers. Suppose that $H$ is
$k$-$G$-free-minimal graphs, then:

$|V(H)|\geq(k-1)(|V(G)|-1)+1.$

By Theorem 23, one can say that $K_{(k-1)(m-1)+1}$ be a $k$-$G$-free-minimal
graphs, for $G=K_{m}$. We shall now construct $k$-$G$-free-minimal graphs with
order $(k-1)(|V(G)|-1)+1$ for some graph $G$. Suppose that
$\operatorname{\mathbb{R}}$ denote a subgraphs of $K_{(k-1)(m-1)+1}$ minus the
edges of a $tK_{2}$, and $G$ denote a subgraphs of $K_{m}$ minus the edges of
a $tK_{2}$, where $t\leq\frac{m}{2}-1$. Now, we have the following theorems:

######  Theorem 28.

$\operatorname{\mathbb{R}}$ is $k$-$G$-free-minimal.

###### Proof.

As $|\operatorname{\mathbb{R}}|=(k-1)(m-1)+1$, we can say that
$\chi_{G}(\operatorname{\mathbb{R}})\leq k$. As, $\operatorname{\mathbb{R}}$
denote a subgraphs of $K_{(k-1)(m-1)+1}$ minus the edges of $tK_{2}$, assume
that $V(\operatorname{\mathbb{R}})=\\{v_{1},v_{2},\ldots,v_{(k-1)(m-1)+1}\\}$
and w.l.g suppose that $E(tK_{2})=\\{e_{1},e_{2},\ldots,e_{t}\\}$, where for
each $i\in\\{1,2,\ldots,t\\}$, $e_{i}=v_{i}v_{\frac{m}{2}+i}$. Set
$V_{1}=\\{v_{1},\ldots,v_{t}\\}$,
$V_{2}=\\{v_{\frac{m}{2}+1},\ldots,v_{\frac{m}{2}+t}\\}$ and
$V_{3}=V(\operatorname{\mathbb{R}})\setminus(V_{1}\cup V_{2})$. Now, to prove
$\chi_{G}(\operatorname{\mathbb{R}})=k$, by Claim 25 we can check that the
following claims is true:

######  Claim 29.

For any $S$ subsets of $V(\operatorname{\mathbb{R}})$ with $m$ member,
$G\subseteq\operatorname{\mathbb{R}}[S]$.

Therefore, as $|\operatorname{\mathbb{R}}|=(k-1)(m-1)+1$ by Claim 29 we can
say that $\chi_{G}(\operatorname{\mathbb{R}})=k$. Now, as
$|V(\operatorname{\mathbb{R}})|=(k-1)(m-1)+1$, assume that $v$ be any vertex
of $V(\operatorname{\mathbb{R}})$, set
$\operatorname{\mathbb{R}}^{\prime}=\operatorname{\mathbb{R}}\setminus\\{v\\}$.
As $|V(\operatorname{\mathbb{R}}^{\prime})|=(k-1)(m-1)$, and $|G|=m$, we can
decomposition of $V(\operatorname{\mathbb{R}}^{\prime})$ into $k-1$ class,
where each class have $m-1$ member, that is
$\chi_{G}(\operatorname{\mathbb{R}}^{\prime})=k-1$, which means that,
$\operatorname{\mathbb{R}}$ is $k$-$G$-free-vertex-minimal. Hence, to prove
$\operatorname{\mathbb{R}}$ is $k$-$G$-free-minimal, we most show that for any
edges of $E(\operatorname{\mathbb{R}})$, say $e$,
$\chi_{G}(\operatorname{\mathbb{R}}\setminus e)=k-1$. Now, to prove
$\chi_{G}(\operatorname{\mathbb{R}}\setminus e)=k-1$, we have the following
claim:

######  Claim 30.

For any edges of $E(\operatorname{\mathbb{R}})$, say $e$,
$\chi_{G}(\operatorname{\mathbb{R}}\setminus e)=k-1$.

###### Proof.

Suppose that $e=vv^{\prime}\in E(\operatorname{\mathbb{R}})$, now by
considering $v$ and $v^{\prime}$, we have three cases as follow:

Case 1: $v,v^{\prime}\in V_{i}$ for one $i,i\in\\{1,2\\}$. W.l.g we may
suppose that $v,v^{\prime}\in V_{1}$. Set $S=V_{1}\cup V_{2}$, one can say
that $|S|\geq m$, Now, as $v,v^{\prime}\in S$ and $vv^{\prime}\in
E(\operatorname{\mathbb{R}})$, we can check that $|N(x)\cap S|\leq d-3$, for
each $x\in\\{v,v^{\prime}\\}$, therefore $\operatorname{\mathbb{R}}[S]$ is
$G$-free. Now as, $|V(H)|=(k-1)(m-1)+1$, $|V(G)|=m$ and $|S|\geq m$, one can
say that $\chi_{G}(\operatorname{\mathbb{R}}\setminus e)=k-1$.

Case 2: $v\in V_{i}$ and $v^{\prime}\in V_{j}$, where $i\neq j$ and
$i,j\in\\{1,2\\}$. The proof is same as Case 1.

Case 1: $v,v\in V_{3}$. Set $S=V_{1}\cup V_{2}\cup\\{v,v^{\prime}\\}$, one can
say that $|S|\geq m$, Now, as $v,v^{\prime}\in S$ and $vv^{\prime}\in
E(\operatorname{\mathbb{R}})$, we can check that
$\operatorname{\mathbb{R}}[S]\cong K_{m}\setminus\frac{m}{2}K_{2}$, therefore
as $t\leq\frac{m}{2}-1$, $\operatorname{\mathbb{R}}[S]$ is $G$-free. Now as,
$|V(H)|=(k-1)(m-1)+1$, $|V(G)|=m$ and $|S|\geq m$, one can say that
$\chi_{G}(\operatorname{\mathbb{R}}\setminus e)=k-1$.

Therefore by Cases 1,2,3 we have the claim is true, which means that the proof
is complete. ∎

∎

Suppose that $H$ is a connected subgraphs of $K_{(k-1)(m-1)+1}$, and $G$
denote a subgraphs of $K_{m}$ minus the edges of a $\frac{m}{2}K_{2}$, where
$m$ is even and $\chi_{G}(H)=k$. Now, we have the following theorems:

######  Theorem 31.

$H$ is $k$-$G$-free-minimal iff either $H$ is a graph $K_{(k-1)(m-1)+1}$ minus
the edges of a $1$-factor, when $k$ is even, or $H\cong H_{1}\oplus K_{1}$,
where $H_{1}$ is a graph $K_{(k-1)(m-1)}$ minus the edges of a $1$-factor,
when $k$ is odd.

###### Proof.

Suppose that, either $H$ is a graph $K_{(k-1)(m-1)+1}$ minus the edges of a
$1$-factor, when $k$ is even, or $H\cong H_{1}\oplus K_{1}$, where $H_{1}$ is
a graph $K_{(k-1)(m-1)}$ minus the edges of a $1$-factor, when $k$ is odd. As
$\chi_{G}(H)=k$, suppose that $e$ be a arbitrary edges of $E(H)$. Therefore,
by definition $H$, one can check that $\delta(H\setminus e)=(k-1)(m-1)-3$,
that is there exists at least one vertex of $V(H)$, say $v$, so that
$\deg(v)=(k-1)(m-1)-3$, and w.l.g suppose that
$v^{\prime},v^{\prime\prime}\notin N(v)$. Now, suppose that $S$, be a subsete
of $V(H)$ with $m$, member, where $v,v^{\prime},v^{\prime\prime}\in S$. As
$v,v^{\prime},v^{\prime\prime}\in S$, and $G$ denote a subgraphs of $K_{m}$
minus the edges of a $\frac{m}{2}K_{2}$, one can check that $H[S]$ is a
$G$-free. Therefore, since $|V(H)|=(k-1)(m-1)+1$, $|V(G)|=m$, $|S|=m$, and
$H[S]$ is a $G$-free, it is easy to say that $\chi_{G}(H\setminus e)=k-1$,
which means that $H$ is $k$-$G$-free-minimal.

Suppose that $H$ is $k$-$G$-free-minimal, and $k$ is even. As $H$ is
$k$-$G$-free-minimal and $m,k$ is even, one can say that
$\delta(H)\geq(k-1)(m-1)-1$. Therefore, as $|V(H)|=(k-1)(m-1)+1$ and
$\delta(H)\geq(k-1)(m-1)-1$, one can check that $K_{(k-1)(m-1)+1}$ minus the
edges of a $1$-factor be a subgraph of $H$. Now, assume that
$H^{\prime}\subset H$, where $H^{\prime}$ is a graph $K_{(k-1)(m-1)+1}$ minus
the edges of a $1$-factor. So there exist at least two vertices of $V(H)$ say
$v,v^{\prime}$, so that $\delta(x)=(k-1)(m-1)$, for each
$x\in\\{v,v^{\prime}\\}$, that is $vv^{\prime}\in(H)$. Consider
$e=vv^{\prime}$, as $H^{\prime}\subset H$ and $e\notin E(H^{\prime})$, we have
$H^{\prime}\subseteq H\setminus e$. Which means that
$k=\chi_{G}(H^{\prime})\leq\chi_{G}(H\setminus e)=k-1$, a contradiction. For
the case that $k$ is add, as $k$ is add and $m$ is even, we have
$(k-1)(m-1)+1$ is add. As $H$ is $k$-$G$-free-minimal we can say that
$\delta(H)\geq(k-1)(m-1)-1$. Therefore, as, $|V(H)|=(k-1)(m-1)+1$,
$\delta(H)\geq(k-1)(m-1)-1$ and $(k-1)(m-1)+1$ is add, one can check that
$K_{(k-1)(m-1)+1}$ minus the edges of a $tK_{2}$ be a subgraph of $H$, where
$t=\frac{(k-1)(m-1)}{2}$. Hence, there exist a vertex of $V(H)$ say $v$ so
that $\deg(v)=(k-1)(m-1)$.

Now, assume that $H^{\prime}\subset H$, where $H^{\prime}$ is a graph
$K_{(k-1)(m-1)+1}$ minus the edges of $t^{\prime}K_{2}$ be a subgraph of
$H^{\prime}$, where $t^{\prime}=\frac{(k-1)(m-1)}{2}-1$. So there exist at
least three vertices of $V(H)$ say $v,v^{\prime},v^{\prime\prime}$, so that
$\delta(x)=(k-1)(m-1)$, for each $x\in\\{v,v^{\prime},v^{\prime\prime}\\}$,
that is $v^{\prime}v^{\prime\prime}\in(H)$. Consider
$e=v^{\prime}v^{\prime\prime}$, as $H^{\prime}\subset H$ and $e\notin
E(H^{\prime})$, we have $H^{\prime}\subseteq H\setminus e$. Which means that
$k=\chi_{G}(H^{\prime})\leq\chi_{G}(H\setminus e)=k-1$, a contradiction to $H$
is $k$-$G$-free-minimal.

Therefore in any case if $H$ is $k$-$G$-free-minimal then, either $H$ is a
graph $K_{(k-1)(m-1)+1}$ minus the edges of a $1$-factor, when $k$ is even, or
$H\cong H_{1}\oplus K_{1}$, where $H_{1}$ is a graph $K_{(k-1)(m-1)}$ minus
the edges of a $1$-factor, when $k$ is odd, which means that the proof is
complete.

∎

## References

  * [1] VA Aksionov.  On uniquely 3-colorable planar graphs.  Discrete Mathematics, 20:209–216, 1977.
  * [2] Meysam Alishahi and Ali Taherkhani.  Extremal g-free induced subgraphs of kneser graphs.  Journal of Combinatorial Theory, Series A, 159:269–282, 2018.
  * [3] B Bollobas.  Extremal graph theory, london math. s oc. monogr. 11, 1978.
  * [4] Béla Bollobás.  Uniquely colorable graphs.  Journal of Combinatorial Theory, Series B, 25(1):54–61, 1978.
  * [5] Mieczysław Borowiecki and Ewa Drgas-Burchardt.  Classes of chromatically unique graphs.  Discrete mathematics, 111(1-3):71–75, 1993.
  * [6] R. L. Brooks.  On colouring the nodes of a network.  Proc. Cambridge Philos. Soc., 37:194–197, 1941.
  * [7] Paul A Catlin and Hong-Jian Lai.  Vertex arboricity and maximum degree.  Discrete Mathematics, 141(1-3):37–46, 1995.
  * [8] G Chartrand, DP Geller, and S Hedetniemi.  A generalization of the chromatic number.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 64, pages 265–271. Cambridge University Press, 1968.
  * [9] Gary Chartrand and Dennis P Geller.  On uniquely colorable planar graphs.  Journal of Combinatorial Theory, 6(3):271–278, 1969.
  * [10] Marietjie Frick and Michael A Henning.  Extremal results on defective colorings of graphs.  Discrete mathematics, 126(1-3):151–158, 1994.
  * [11] Frank Harary.  Conditional colorability in graphs.  In Graphs and applications (Boulder, Colo., 1982), Wiley-Intersci. Publ., pages 127–136. Wiley, New York, 1985.
  * [12] Frank Harary, ST Hedetniemi, and RW Robinson.  Uniquely colorable graphs.  Journal of Combinatorial Theory, 6(3):264–270, 1969.
  * [13] Frank Harary and John Stanley Maybee.  Graphs and applications: proceedings of the first Colorado symposium on graph theory.  Wiley-Interscience, 1985.
  * [14] László Lovász.  On decomposition of graphs.  Studia Sci. Math. Hungar, 1(273):238, 1966.
  * [15] Xu Shaoji.  The size of uniquely colorable graphs.  Journal of Combinatorial Theory, Series B, 50(2):319–320, 1990\.


11institutetext: Aalto University, Finland 11email:
<EMAIL_ADDRESS>
22institutetext: Universitat Politècnica de Catalunya, Spain
22email<EMAIL_ADDRESS>
# Off-the-grid: Fast and Effective Hyperparameter Search for Kernel
Clustering††thanks: This work was supported by the Academy of Finland project
317085.

Bruno Ordozgoiti 11 Lluís A. Belanche Muñoz 22

###### Abstract

Kernel functions are a powerful tool to enhance the $k$-means clustering
algorithm via the kernel trick. It is known that the parameters of the chosen
kernel function can have a dramatic impact on the result. In supervised
settings, these can be tuned via cross-validation, but for clustering this is
not straightforward and heuristics are usually employed. In this paper we
study the impact of kernel parameters on kernel $k$-means. In particular, we
derive a lower bound, tight up to constant factors, below which the parameter
of the RBF kernel will render kernel $k$-means meaningless. We argue that grid
search can be ineffective for hyperparameter search in this context and
propose an alternative algorithm for this purpose. In addition, we offer an
efficient implementation based on fast approximate exponentiation with
provable quality guarantees. Our experimental results demonstrate the ability
of our method to efficiently reveal a rich and useful set of hyperparameter
values.

###### Keywords:

clustering kernels kernel k-means hyperparameter tuning grid search.

##  1 Introduction

Clustering, the task of partitioning a given data set into groups of similar
items, is one of the central topics in data analysis. Among the plethora of
existing techniques for this purpose, $k$-means clustering, along with Lloyd’s
algorithm [14], is one of the most popular and well-understood methods.
Despite its popularity, $k$-means has significant limitations, as it
implicitly makes strong assumptions about the shapes of the clusters. Numerous
alternative methods have been proposed to tackle challenges beyond the
capabilities of $k$-means [8, 15, 16, 13].

One of these involves the use of positive definite kernels [11], which enable
the computation of inner products between elements of a vector space after
mapping them to a different, high-dimensional space. In particular, kernels
enhance the capabilities of $k$-means by enabling the detection of clusters of
arbitrary shapes.

One drawback of kernel functions is that they usually involve hand-set
parameters, which must be fine-tuned to bring forth their full potential. A
common method to choose a value for these parameters is grid search. One
considers a set of values and then evaluates the performance of the algorithm
for each of them. A drawback is that one might either choose too small a set
and risk missing optimal values, or an overly big one, incurring excessive
—and possibly redundant— computational costs. Another way to set these values
is by heuristics and rules of thumb [19, 12], but these rarely apply to a wide
variety of data.

Our contribution in this paper is two-fold. First, we illustrate the impact of
kernel parameters in clustering by deriving a lower bound for the bandwidth
parameter of RBF kernels (section 4), below which Kernel $k$-means will be
rendered useless. We show this bound is tight. Next, we propose a method for
hyperparameter search. Our method specifically searches for values that will
produce different clusterings, and thus, unlike grid search, does not risk
carrying out redundant computations, so no processing time is wasted. We
combine methods for fast exponentiation with the properties of dyadic
rationals to design an algorithm that after
$\mathcal{O}\left(\log\left(\frac{|\log(b)|}{\epsilon}\right)\right)$
iterations —where $b$ is the minimum entry in the kernel matrix— provides a
$(1\pm\epsilon)$-approximation of the next meaningful hyperparmeter value to
inspect (sections 5 and 6). We validate our claims with a rich variety of
experiments (section 7).

##  2 Related work

Kernels have been a central subfield of machine learning since their first use
in conjunction with support vector machines [5]. Even though most efforts have
focused on their application to supervised learning methods, they have also
played a significant part in the development of clustering techniques [4, 16,
7]. In the seminal work by Ben-Hur et al. [4], the authors suggest to inspect
the results using varying values of $\sigma$, starting from the maximizer of
the pairwise squared distances $\|x-y\|^{2}$ over all pairs of data points. A
good choice might lie within a region that yields stable clusterings. It
should be noted that stability has been shown to have significant drawbacks
for choosing the number of clusters [3], so it would be interesting to
determine whether this applies to the kernel bandwidth as well. In the work
that introduced spectral clustering [16], Ng et al. rely on a result of their
own that guarantees that their algorithm will produce tight clusters if they
exist in the data. They then propose to test various values of $\sigma$ in
search for a clustering with this property. In [2] a generalized form of the
bandwidth parameter is learned based on data with known clustering. In [20] a
different value of $\sigma$ is computed for each point. The approach proposed
by the authors relies on the distance to the $k$-th neighbor. In [10], the
authors investigate the problem of kernel matrix diagonal dominance in
clustering, which is essentially a generalization of the problem we analyze in
the beginning of section 4. The heuristics they explore to alleviate the
problem either require the selection of a new hyperparameter, or heavily
modify the structure of the problem. The latter can even lead to the loss of
positive-definiteness of the kernel matrix, which results in algorithmic
oscillations and failure to converge. The mean distance to the $k$-th nearest
neighbour is also suggested as a heuristic by Von Luxburg [19].

##  3 Preliminaries

We consider a finite set of data points $X\subset\mathbb{R}^{d}$. We define a
$k$-partition of $X$ as a collection of $k$ non-empty subsets of $X$,
$\pi_{1},\dots,\pi_{k}$, satisfying $\bigcup_{i=1}^{k}\pi_{i}=X$ and
$\pi_{i}\cap\pi_{j}=\emptyset$ for $i,j=1,\dots,k$, $i\neq j$. We will refer
to each $\pi_{i}$ as a cluster and use $n_{i}=|\pi_{i}|$ to denote its
cardinality.

The $k$-means objective is to find a $k$-partition of $X$ so as to minimize

$\sum_{i=1}^{k}\sum_{x\in\pi_{i}}\|x-\bar{\pi}_{i}\|^{2},$ (1)

where $\bar{\pi}_{i}=n_{i}^{-1}\sum_{x\in\pi_{i}}x$ is the centroid of cluster
$\pi_{i}$ and $\|x\|$ denotes the $L_{2}$ norm in $\mathbb{R}^{d}$. Optimizing
this objective is known to be $\mathbf{NP}$-hard for $k=2$ [1]. A popular
heuristic is Lloyd’s algorithm [14], which repeatedly recomputes the centroid
of each cluster and reassigns points to the closest centroid.

####  3.0.1 Kernels:

Given a non-empty set $\mathcal{X}$, a symmetric function
$\kappa:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ such that for all
$n\in\mathbb{N}$ and every set $\\{x_{i}\\}_{i=1}^{n}\subset\mathcal{X}$, the
matrix $K=\left(\kappa(x_{i},x_{j})\right)_{ij}$ is positive definite, is
called a (strictly) positive definite (PD) kernel. The matrix $K$ is known as
the Gram matrix or Kernel matrix. Since PD kernels give rise to a PD Gram
matrix, they correspond to the computation of an inner product in some
implicit inner-product space. The representation of an object
$x\in\mathcal{X}$ in said space is often called feature space representation,
denoted as $\phi(x)$.

A number of kernels are routinely used in practice. Probably the most popular
one for the case $\mathcal{X}=\mathbb{R}^{d}$ is the Gaussian RBF kernel

$\kappa(x,y)=\exp\left(\frac{-\|x-y\|^{2}}{\sigma}\right),$

$\sigma>0$, (from here on, RBF kernel). The parameter $\sigma$ is commonly
referred to as bandwidth. We will use $\kappa_{\sigma}$ to denote the RBF
kernel function with bandwidth parameter $\sigma$ and $K_{\sigma}$ to denote
the corresponding kernel matrix.

Consider a data set $X$ and the $k$-partition $\pi_{1},\dots,\pi_{k}$. Let
$m_{i}$ denote the centroid of cluster $\pi_{i}$ in feature space, that is,

$m_{i}=\frac{1}{n_{i}}\sum_{x\in\pi_{i}}\phi(x).$

The application of kernels to the $k$-means objective (1) relies on the
following observation: even though we cannot in general express $m_{i}$
explicitly, it is possible to compute the necessary squared distances. For any
$x\in X$ and $i=1,\dots,k$,

$\displaystyle\|\phi(x)-m_{i}\|^{2}=\kappa(x,x)-\frac{2\sum_{y\in\pi_{i}}\kappa(x,y)}{n_{i}}+\frac{\sum_{y,z\in\pi_{i}}\kappa(y,z)}{n_{i}^{2}}.$
(2)

The application of Lloyd’s algorithm using this expression for the squared
distance is known as Kernel $k$-means. See [7] for an insightful analysis.
Kernel $k$-means always converges when the kernel matrix is positive
semidefinite. We will refer to the $k$-partition at convergence as the output
of Kernel $k$-means.

##  4 The use of the RBF kernel in Kernel $k$-means

RBF kernels are powerful but sensitive to the bandwidth parameter. In
particular, for sufficiently small $\sigma$, a support vector machine
classifier can fit any training set with no errors —or equivalently, it has
infinite VC dimension [18]—, but this will generally result in poor
generalization ability. In Kernel $k$-means, the result of an overly small
bandwidth will be that the algorithm will converge in the first iteration,
regardless of the current $k$-partition. The reason is that as $\sigma$
decreases, the value of $\kappa(x,y)$ for any two distinct points $x,y\in X$
decreases as well, to the point of becoming negligible. Therefore, the only
significant term in equation (2) for any $x$ will be $\kappa(x,x)$, which
means that the closest cluster to $x$ will be the one it is currently in. A
question arises naturally: how small does $\sigma$ have to be for the
algorithm to get stuck at the initial clustering? The following theorem
provides a lower bound, which is tight up to constant factors.

###### Theorem 4.1

Consider a data set $X\subset\mathbb{R}^{d}$, $|X|=n$. Let
$x,y=\operatorname*{arg\,min}_{x,y\in X}\|x-y\|^{2}$. If
$\sigma\leq\left(\log(3n)\right)^{-1}\|x-y\|^{2}$, then Kernel $k$-means will
make no cluster reassignments.

The proof is given in the supplementary material.

##### A tight example.

The next example shows that this result is tight up to constant factors.
Consider an instance with two clusters, $\pi_{1}$ and $\pi_{2}$, containing
$n_{1}$ and $n_{2}$ points respectively. For some point $y\in\pi_{2}$ it is
$\|x-y\|_{2}^{2}=\min_{a,b}\|a-b\|_{2}^{2}=\epsilon$ for all $x\in\pi_{1}$,
whereas for all $z\in\pi_{2},z\neq y$, it is $\|y-z\|_{2}^{2}=2\epsilon$.
Moreover, for all $w,z\in\pi_{1}$ it is $\|w-z\|_{2}^{2}=\epsilon$ and for all
$w,z\in\pi_{2},w,z\neq y$, it is $\|w-z\|_{2}^{2}=\epsilon$. Define
$n=n_{1}+n_{2}$ and consider $\sigma=\epsilon/\log(n/3)$. We know $y$ will
switch over to $\pi_{1}$ if
$\|\phi(y)-m_{1}\|_{2}^{2}<\|\phi(y)-m_{2}\|_{2}^{2}$, or equivalently,

$\frac{2}{n_{2}}<~{}\frac{2\sum_{x\in\pi_{1}}\kappa(y,x)}{n_{1}}-\frac{\sum_{w,z\in\pi_{1}}\kappa(w,z)}{n_{1}^{2}}-\frac{2\sum_{z\in\pi_{2},z\neq
y}\kappa(y,z)}{n_{2}}+\frac{\sum_{w,z\in\pi_{2}}\kappa(w,z)}{n_{2}^{2}}\\\
=6/n-1/n_{1}-\frac{3(n_{1}-1)}{nn_{1}}-\frac{2(n_{2}-1)}{n_{2}}\left(\frac{3}{n}\right)^{2}\\\
+1/n_{2}+\frac{3(n_{2}-1)(n_{2}-2)}{nn_{2}^{2}}+\frac{(n_{2}-1)}{n_{2}^{2}}\left(\frac{3}{n}\right)^{2}.$
(3)

The above inequality is verified when $n_{1}=n_{2}$ and $n$ is sufficiently
large. That is, there exists a family of instances where the kernel $k$-means
algorithm with the RBF kernel will make cluster reassignments with
$\sigma=\Omega\left(\frac{\|x-y\|_{2}^{2}}{\log(n)}\right)$, where
$\|x-y\|_{2}^{2}$ is minimal over all $x,y$ in the data set.

##  5 Optimizing bandwidth

As demonstrated above, the choice of bandwidth parameter is crucial when using
RBF kernels for clustering. For some choices of $\sigma$, the output of Kernel
$k$-means will be unchanged from the initial $k$-partition. In fact, for any
value of $\sigma$ the algorithm will converge at some point —provided that the
kernel matrix is positive semidefinite— and stop making changes. However, if
the chosen value is inadequate the output might still be of poor quality, so
it is often desirable to further refine $\sigma$ in order to obtain a better
result. We already know, by virtue of Theorem 4.1, a value of $\sigma$ such
that Kernel $k$-means will stop making changes. The following question arises
naturally. How big does $\sigma$ have to be in order to guarantee that Kernel
$k$-means will change the initial $k$-partition?, and more generally, once
Kernel $k$-means has converged, how much do we have to increase $\sigma$ to
ensure it will make new changes? We define this as the critical bandwidth
value.

###### Definition 1

(Critical bandwidth value) Let $X$ a data set. Suppose Kernel $k$-means
outputs a $k$-partition $P=(\pi_{1},\dots,\pi_{k})$ of $X$ when run using an
RBF kernel with bandwidth parameter $\sigma$. We define $S\subset\mathbb{R}$
to be the set satisfying the following: if Kernel $k$-means is initialized
with $k$-partition $P$ and run with $K_{\sigma^{\prime}}$, with
$\sigma^{\prime}\in S$, it will output a $k$-partition $P^{\prime}\neq P$,
that is, it will make changes. We define the critical bandwidth value with
respect to $(K_{\sigma},P)$ to be the infimum of $S$, or $\infty$ if
$S=\emptyset$.

In other words, the critical bandwidth value reveals the “minimal” value the
RBF kernel bandwidth needs to take so that Kernel $k$-means “snaps out” of
convergence and yields a new $k$-partition. Any value strictly larger than the
critical value will suffice. This concept is the cornerstone of our
contribution.

###  5.1 Finding the critical value

Possibly the most straightforward method to find a value of $\sigma$ —or
virtually any hyperparameter— is grid search. This consists in running the
clustering algorithm for a predetermined set of values of the hyperparameter
and choosing the one which provides the best performance, as measured by e.g.
objective function values or clustering quality indices [17]. This approach,
however, has significant disadvantages. If the set of values to test is too
small, one can fail to detect one that yields good performance; if it is too
large, running times can be prohibitive and some computations redundant.

Here we propose an alternative approach. Roughly, we proceed as follows.
First, we choose a sufficiently small value of $\sigma$ —e.g. guided by
Theorem 4.1— and run Kernel $k$-means. We then search for the critical
bandwidth value with respect to the current kernel matrix and $k$-partition
and rerun Kernel $k$-means until convergence. We can keep doing this until no
further changes are observed, to finally obtain a set of possible
hyperparameter choices. The question that arises now is how to find said value
efficiently. Next, we illustrate the fact that this value can be located using
optimization methods.

####  5.1.1 A first approach

Let $\kappa_{\sigma}$ denote the RBF kernel function parametrized by $\sigma$.
In a Kernel $k$-means iteration, a point $x$ is assigned to the cluster
$\pi_{i}$ which maximizes the proximity function $\delta$:

$\displaystyle\delta_{\sigma}(x,m_{i})=\frac{2\sum_{y\in\pi_{i}}\kappa_{\sigma}(x,y)}{n_{i}}-\frac{\sum_{y,z\in\pi_{i}}\kappa_{\sigma}(y,z)}{n_{i}^{2}}.$
(4)

Now, observe that if we change the value of the bandwidth parameter to
$\sigma^{\prime}$, the new value of the kernel for any pair of points $x,y$
can be computed as follows:

$\kappa_{\sigma^{\prime}}(x,y)=\kappa_{\sigma}(x,y)^{\sigma/{\sigma^{\prime}}},$

and we can thus compute the new proximity functions
$\delta_{\sigma^{\prime}}(x,m_{i})$ accordingly. For simplicity, we consider
the case of two clusters $\pi_{1},\pi_{2}$. Assume $x\in\pi_{1}$. $x$ will
switch over to $\pi_{2}$ when

$\displaystyle\delta_{\sigma^{\prime}}(x,m_{1})<\delta_{\sigma^{\prime}}(x,m_{2})\Leftrightarrow\delta_{\sigma^{\prime}}(x,m_{1})-\delta_{\sigma^{\prime}}(x,m_{2})<0.$

That is, we can find the value of $\sigma^{\prime}$ that will result in a
different clustering by finding a root of
$\delta_{\sigma^{\prime}}(x,m_{1})-\delta_{\sigma^{\prime}}(x,m_{2})$.

A useful observation is that $\kappa_{\sigma}(x,y)^{\sigma}$ is constant with
respect to $\sigma^{\prime}$. Therefore, we can easily derive
$\delta_{\sigma^{\prime}}(x,m_{1})-\delta_{\sigma^{\prime}}(x,m_{2})$ with
respect to $\sigma^{\prime}$. In particular, define
$g(x,\sigma^{\prime})=\delta_{\sigma^{\prime}}(x,m_{1})-\delta_{\sigma^{\prime}}(x,m_{2})$.
Then

$\frac{dg}{d\sigma^{\prime}}=\frac{2\sum_{y\in\pi_{2}}\log\left(\kappa_{\sigma}(x,y)^{\sigma}\right)\kappa_{\sigma}(x,y)^{\sigma/{\sigma^{\prime}}}}{\sigma^{\prime
2}n_{2}}-\frac{\sum_{y,z\in\pi_{2}}\log\left(\kappa_{\sigma}(y,z)^{\sigma}\right)\kappa_{\sigma}(y,z)^{\sigma/{\sigma^{\prime}}}}{\sigma^{\prime
2}n_{2}^{2}}\\\
-\frac{2\sum_{y\in\pi_{1}}\log\left(\kappa_{\sigma}(x,y)^{\sigma}\right)\kappa_{\sigma}(x,y)^{\sigma/{\sigma^{\prime}}}}{\sigma^{\prime
2}n_{1}}+\frac{\sum_{y,z\in\pi_{1}}\log\left(\kappa_{\sigma}(y,z)^{\sigma}\right)\kappa_{\sigma}(y,z)^{\sigma/{\sigma^{\prime}}}}{\sigma^{\prime
2}n_{1}^{2}}.$ (5)

This implies that we can use iterative root-finding algorithms, such as
Newton’s method, to efficiently find a root of the above function, that is,
the minimum value of $\sigma^{\prime}$ that will result in a clustering
change, or the critical bandwith value.

This approach, however, can be slow and numerically unstable. In the next
section we propose an alternative optimization method able to efficiently
locate the critical bandwidth value to arbitrary precision while overcoming
these drawbacks.

##  6 Fast and effective hyperparameter search

The approach outlined above has several drawbacks, namely (1) using an
iterative root-finding algorithm entails repeatedly recomputing the kernel
matrix, either directly or by element-wise exponentiation, which can be slow
in practice when dealing with large matrices and (2) the operations required
for the derivative of $g$ and the fractional computations can induce numerical
instability.

Here we propose an alternative approach to sidestep these issues. The proposed
method rests on the following fact: computing products and square roots of
real numbers can be much faster than computing powers with arbitrary exponents
[9]. Our method has the additional advantage of being numerically stable.

###  6.1 Dyadic rationals and fast approximate exponentiation

To develop an efficient method for hyperparameter search, we first propose an
algorithm for fast approximate exponentiation that only uses products and
square roots. This algorithm (Algorithm 1) forms the basis of our approach.

####  6.1.1 Exponentiation algorithm overview.

As hinted above, we wish to avoid computing element-wise powers of the kernel
matrix, and instead use element-wise products and square roots. To accomplish
this, suppose we want to compute the power $b^{p}$, for some arbitrary
positive reals $b$ and $p$. We first decompose $p$ as $p=z+f$, where $z$ is
the integral part and $f$ the decimal part of $p$. We then compute $b^{z}$ and
approximate $b^{f}$ as $b^{f^{\prime}}$ using two separate fast methods for
integral and rational exponents and finally return $b^{z}b^{f^{\prime}}\approx
b^{p}$.

To design our algorithm, we rely on two simple results. First, we make use of
the following recursive representation of a positive integer based on its
binary representation, which has long been employed in the design of fast
algorithms for power computation with integral exponents [9].

###### Lemma 1

Consider a number $n\in\mathbb{N}$, and let $b_{0}\dots b_{t}$, where
$t=\lfloor\log_{2}n\rfloor$, be its binary representation, i.e.
$n=\sum_{i=0}^{t}2^{t-i}b_{i}$. Then $n=n_{t}$, where

$\displaystyle n_{i}=\begin{cases}1&\mbox{ if }i=0\\\ 2n_{i-1}+b_{i}&\mbox{ if
}0<i\leq t\end{cases}$

Lemma 1 reveals how to compute a power of the form $b^{i}$, where $b$ is a
positive real number and $i$ is a natural number, using a small number of
products. In particular, this operation is carried out in lines 5 and 6 of
Algorithm 1.

The next result we rely on is a consequence of the properties of dyadic
rationals. Dyadic rationals are rational numbers of the form $n/2^{i}$, where
$n$ is an integer and $i$ is a natural number. It is well known that dyadic
rationals are dense in $\mathbb{R}$, that is, any real number can be
approximated arbitrarily well by a dyadic rational. The next result reveals
how to obtain such an approximation for numbers in the interval $(0,1)$, which
will be useful in our context.

###### Lemma 2

Let $a\in(0,1)$. There exists a sequence $(m_{i})$, with
$m_{i}\in\\{-1,1\\},i=1,\dots$ such that
$\lim_{t\rightarrow\infty}\sum_{i=1}^{t}m_{i}2^{-i}=a$.

###### Proof

Let $m_{1}=1$. Choose the $j$-th term of $(m_{i})$ (for $j>1$) to be $1$ if
$\sum_{i=1}^{j-1}m_{i}2^{-i}<a$, $-1$ if $\sum_{i=1}^{j-1}m_{i}2^{-i}>a$, $0$
otherwise. Clearly, $\left|a-\sum_{i=1}^{k}m_{i}2^{-i}\right|\leq 2^{-k}$.

The set of dyadic rationals is clearly closed under addition, and thus the
above series provides an approximation by means of a dyadic rational.

Now, suppose we want to approximately compute the power $b^{p}$, by an
approximation of $p$ to within an error of $2^{-j}$. The above result implies
that it suffices to compute $j$ operations, at each step either multiplying or
dividing by successive square roots of $b$. This is done in lines 8 through 15
of Algorithm 1.

Algorithm 1 Fast approximate exponentiation

Input: base $b$, exponent $p$, depth $i$

1: $z\leftarrow bin(\lfloor p\rfloor)[1:]$

2: $f\leftarrow p-\lfloor p\rfloor$

3: $b_{1}\leftarrow b$; $b_{2}\leftarrow b$

4: $j\leftarrow 1$

5: for $d$ in $z$ do

6: $b_{1}\leftarrow b_{1}^{2}b^{d}$

7: $n\leftarrow 1$; $d\leftarrow 2$

8: for $j=1,\dots,i$ do

9: $b\leftarrow\sqrt{b}$; $n\leftarrow 2n$; $d\leftarrow 2d$

10: if $n/d>f$ then

11: $n\leftarrow n-1$; $b_{2}\leftarrow b_{2}/b$

12: if $n/d<f$ then

13: $n\leftarrow n+1$; $b_{2}\leftarrow b_{2}b$

14: if $n/d=f$ then

15: $\j\leftarrow i+1$ // Exact exponent matched, so exit loop

16: Output $b_{1}\times b_{2}$

The following result characterizes the quality of the approximation achieved
by Algorithm 1, and the required number of operations.

###### Theorem 6.1

Algorithm 1 yields a $(1\pm\epsilon)-$approximation of $b^{p}$ after
performing
$\mathcal{O}\left(\log\left(\frac{|\log(b)|}{\epsilon}\right)\right)$
operations.

###### Proof

First, note that the algorithm computes at most $2i$ multiplications in the
first phase, and $i$ square roots or multiplications in the second.

Assume $b>1$. We treat the alternative later. By lemma 2, the output of
Algorithm 1 is bounded as follows

$\frac{b^{p}}{b^{1/2^{i}}}=b^{p-1/2^{i}}\leq r\leq
b^{p+1/2^{i}}=b^{p}b^{1/2^{i}}.$

Observe that $b^{p}b^{1/2^{i}}=b^{p}+b^{p}(b^{1/2^{i}}-1)$ and set
$\epsilon=b^{1/2^{i}}-1$. We thus have
$\frac{1}{2^{i}}=\frac{\log(1+\epsilon)}{\log(b)}$ and thus
$i=\mathcal{O}\left(\log\left(\frac{\log(b)}{\epsilon}\right)\right)$.
Similarly, we can write $b^{p}b^{-1/2^{i}}=b^{p}-b^{p}(1-b^{-1/2^{i}})$,
arriving at an equivalent result for the $1-\epsilon$ bound.

The analysis for the case $b<1$ is the same, but noting that the output is
bounded as $b^{p+1/2^{i}}\leq r\leq b^{p-1/2^{i}}$. The negative sign of
$\log(b)$ is cancelled out in the arithmetic. The case $b=1$ is obviously of
no interest. ∎

Algorithm 1 approximates a power computation by a dyadic rational
approximation $w/z$ of the exponent. Based on the principles behind Algorithm
1 we can design an efficient method to find the critical value of $\sigma$ for
Kernel $k$-means.

####  6.1.2 Finding the critical value.

Our algorithm for hyperparameter search is detailed as Algorithm 2. In the
pseudocode, $\circ$ and $/\circ$ denote element-wise multiplication and
division, respectively, and $\sqrt{K}$ is the element-wise square root of
matrix $K$.

In essence, our algorithm emulates Algorithm 1, using the kernel matrix
$K_{\sigma}$ as the basis of the power to compute, with some key differences.
The first difference is that instead of approximating a known exponent $p$, we
aim to approximate the unknown critical value of $\sigma$. Since this quantity
is unknown, instead of testing whether the current approximation is larger or
smaller than the target exponent, we query the Kernel $k$-means algorithm to
determine whether the current value will result in new changes. Note that this
amounts to running a single iteration of Kernel $k$-means. Later we show that
we can further optimize these queries.

The second observation is that we only ever need to compute exponents in the
interval $(0,1)$. This is because if we assume Kernel $k$-means to have
converged for the matrix $K_{\sigma}$, we know that the next value of $\sigma$
we seek is larger than the current one. Note that we can use our result from
Theorem 4.1 for a starting value of $\sigma$ without running an initial
execution of Kernel $k$-means.

By virtue of Theorem 6.1, Algorithm 2 thus finds an arbitrarily good
approximation of the critical bandwidth value, in the following sense:

###### Corollary 1

Suppose Kernel $k$-means has converged for $K_{\sigma}$, producing a
$k$-partition $P$, and let $\sigma^{\prime}$ be the critical bandwidth value
with respect to $(K_{\sigma},P)$. If we run Algorithm 2 with a depth value of
$i=\mathcal{O}\left(\log\left(\frac{|\log(b)|}{\epsilon}\right)\right)$ —where
$b$ is the minimum entry in the kernel matrix—, it will output a matrix
$K_{\rho}$ satisfying

$(1-\epsilon)K_{\sigma^{\prime}}\leq_{\circ}K_{\rho}\leq_{\circ}(1+\epsilon)K_{\sigma^{\prime}},$

where $\leq_{\circ}$ denotes element-wise inequality.

That is, it will output a good approximation of the “next” kernel matrix for
which Kernel $k$-means will make changes. Note that this result also
characterizes the computational complexity of our approach, as element-wise
operations take $\mathcal{O}(n^{2})$ computations. In addition, element-wise
operations are trivially parallelizable, so our method can scale to large
kernel matrices. Finally, note that even though $\log(b)$ is unbounded, after
a few iterations only very small entries, close to zero, would suffer
considerable relative error.

An advantage of the algorithm is that we can choose the maximum value of the
denominator in the rational approximation of the exponent (maximum depth $d$).
This provides a nice trade-off between speed and accuracy.

Algorithm 2 Hyperparameter search

Input: kernel matrix $K$, depth $i$, $k$-partition $P$ of $X$.

1: $K^{\prime}\leftarrow K$

2: $P^{\prime}\leftarrow P$

3: $j\leftarrow 1$

4: for $i=1,\dots,i$ do

5: $K^{\prime}\leftarrow\sqrt{K^{\prime}}$ //Element-wise square root

6: if $P^{\prime}\neq P$ then

7: $K\leftarrow K/\circ K^{\prime}$

8: else

9: $K\leftarrow K\circ K^{\prime}$

10: $P^{\prime}\leftarrow kkm(K)$ //Run Kernel $k$-means

11: Output $K$

###  6.2 Further optimizations

Our approach lends itself naturally to various optimizations. We discuss them
briefly here.

##### Hierarchical search.

Our algorithm enables a trade-off between running time and accuracy by means
of the depth parameter. The larger it is, the more precise the critical values
of $\sigma$ found. We argue that this parameter can be employed to improve
speed without significantly sacrificing accuracy. In particular, the algorithm
can be run with increasing depth values, constraining the search to promising
regions. For instance, we first set depth to 1, run the algorithm and pick the
two values of $\sigma$ that yield the best performance. We then increase the
depth value by 1 and run the algorithm again, setting the lower and upper
limits of our search to the two previously picked values of $\sigma$. This way
we first perform a coarse-grained search to identify a potentially good
interval for $\sigma$, and then increasingly refine the search.

##### Limiting checks.

As described above, the way our algorithm approximates the critical value of
$\sigma$ is by testing whether or not Kernel $k$-means will switch at least
one point from one cluster to another. Often, most points will not switch
clusters at the critical value. Thus, it is not necessary to compute the
proximity function (Equation (4)) for all point-cluster pairs, and we can
limit checks to those points most likely to change. To do this, we can employ
different heuristics. For instance, we can limit checks to points such that
the proximity function is close for different clusters. We can also limit
checks to those points that switch clusters the first time we observe a change
(line 6 of Algorithm 2).

###  6.3 Use with other kernels

Our approach is not limited to the RBF kernel. Obviously, any kernel that is
exponential in the parameters can be directly used with our method. This
includes the popular polynomial kernel, defined as
$\kappa(x,y)=(x^{T}y+c)^{d}$, for the optimization of the parameter $d$. We
can also benefit from the fact that any linear combination of kernels is also
a kernel, to accommodate a wider variety of kernel functions. To use our
algorithm with a linear combination of differently-parametrized kernels, it
suffices to store the kernel matrix separately for each term of the sum. As
currently described, our method only allows the optimization of one parameter
at a time, but it can be employed as a building block for more sophisticated
multiparameter optimization approaches.

##  7 Experiments

We conduct a series of numerical experiments to evaluate the performance of
the proposed algorithm. We mainly want to determine whether our method (1) can
reveal good value of $\sigma$ and (2) can do it efficiently. We compare it to
other approaches for hyperparameter search, which we now describe.

##### Baselines

We consider the following methods to choose the hyperparameter of the RBF
kernel111Some of these methods, as originally described, define the kernel as
$\kappa(x,y)=\exp(-\|x-y\|/(2\sigma^{2}))$. We take this difference into
account in our experimental setup..

MKNN: We set $\sigma$ to be the mean distance to the $k$-th nearest neighbour
as suggested by Von Luxburg [19] (the median yields similar results). We try
different values of $k$, namely $k=1,\dots 2(\log n+1)$.

GridSearch: We run the Kernel $k$-means algorithm with $\sigma$ taking values
in $\\{10^{i}:i=-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6\\}$

We refer to Algorithm 2 as OURS.

All methods, as well as Kernel $k$-means, were implemented using Python 3,
using matrix and vector operations whenever possible for efficiency222Source
code: https://github.com/justbruno/off-the-grid/.

##### Quality measures:

We consider the following functions to evaluate the quality of the clustering
results.

NMI (Normalized Mutual Information): We use a well-known clustering
performance index333Results for Adjusted Rand-Index were similar and are thus
omitted., which we now define. Given two indicator vectors $y$ and $z$, we
define

$\displaystyle{\rm{NMI}}(y,z)=\frac{2I(y,z)}{H(y)+H(z)}$ (6)

where
$I(y,z)=\sum_{i}\sum_{j}p(y=i,z=j)\log\left(\frac{p(y=i,z=i)}{p(y=i)p(z=i)}\right)$
denotes the mutual information of $y$ and $z$, and $H(y)=-\sum_{i}p(y=i)\log
p(y=i)$ denotes the entropy of $y$ [6] (we abuse notation and overload $y$ for
the vector and its entries). We use this index by taking $y$ to be the
indicator vector of ground-truth labels and $z$ to be the indicator vector of
the $k$-partition output by Kernel $k$-means.

${\rm c\mathchar 45\relax NNC}$: In addition, we propose our own clustering
cost function. Our goal is to measure the quality of the resulting
$k$-partition in a way that (1) arbitrarily shaped clusters are considered and
(2) is independent of the value of $\sigma$. Note that some well-known
clustering quality indices and cost functions, such as silhouette [17] and
normalized cuts [7], do not qualify.

We first introduce some notation. Given a data set $X$ and a point $x_{i}\in
X$, let $\nu_{j}(x_{i})$ be the $j$-th nearest neighbour of $x_{i}$ in $X$.
Given a $k$-partition of the data set $X$ into $k$ clusters, $c(x_{i})$
denotes the cluster $x_{i}$ is assigned to, i.e. $x_{i}\in c(x_{i})$.

We first define ${\rm NNC}(i,{c})$ to be the fraction of points among the
${c}$ nearest neighbours of $x_{i}$ which are not in the same cluster as
$x_{i}$.

$\displaystyle{\rm
NNC}(i,{c})=\frac{1}{{c}}\sum_{j=1}^{c}\mathbb{I}\\{c(x_{i})\neq
c(\nu_{j}(x_{i}))\\}.$

To measure the quality of a single cluster $\pi$, we take a weighted sum of
the above index for all ${c}$. We scale the value of ${\rm NNC}(i,{c})$ by
$\frac{1}{{c}}$ to reduce the penalty incurred by disagreements with further
neighbours.

$\displaystyle{\rm
NNC}_{cluster}(\pi)=\frac{1}{C\max\\{1,|\pi|)\\}}\sum_{i\in\pi}\sum_{{c}=1}^{n}\frac{1}{{c}}{\rm
NNC}(i,{c}).$

Here, $C=\log(n-1)+\gamma+\frac{1}{2n-2}$, where $\gamma$ is the Euler-
Mascheroni constant, ensures that the quantity is upper-bounded by 1 (note
that without this scaling factor, the sum for each point is tightly upper
bounded by a harmonic series).

We now define the cost function as

$\displaystyle{\rm c\mathchar 45\relax NNC}(P)=\frac{D+\sum_{\pi\in P}{\rm
NNC}_{cluster}(\pi)}{k}.$

Here, $P$ is the $k$-partition output by Kernel $k$-means, $k$ is the number
of clusters given to Kernel $k$-means and $D$ is the number of empty clusters.
We count empty clusters to penalize trivial solutions (e.g. a single cluster).

##### Datasets

: We employ a variety of publicly available
synthetic444http://cs.joensuu.fi/sipu/datasets and
real555https://archive.ics.uci.edu/ml/index.php data sets. Since we use
vanilla Kernel $k$-means, which requires handling the complete kernel matrix,
we employ data sets of limited size (up to $8\,000$ instances). However, our
method can in principle be employed with techniques for scalable kernel-based
algorithms. A summary of the data sets is given in Table 1. In the case of
real data sets, we scale the variables to unit-variance, as this enables a
much better performance of Kernel $k$-means in most cases.

Table 1: Summary of data set characteristics Dataset | Rows | Columns | Classes | Dataset | Rows | Columns | Classes
---|---|---|---|---|---|---|---
Aggr. | 788 | 2 | 7 | Spiral | 312 | 2 | 3
Compound | 399 | 2 | 6 | Audit | 775 | 23 | 2
D31 | 3100 | 2 | 31 | Derma. | 358 | 34 | 6
Flame | 240 | 2 | 2 | WDBC | 569 | 30 | 2
Jain | 373 | 2 | 2 | WiFi | 2000 | 7 | 4
Pathbased | 300 | 2 | 3 | Wine | 178 | 13 | 3
R15 | 600 | 2 | 15 |  MNIST (sampled) | 1k,2k,4k,8k | 784 | 10

###  7.1 Performance

In this section we report the performance of our method, as evaluated by our
quality measures, in comparison to the selected baselines. We proceed as
follows: we first choose a random initial $k$-partition, which we set as
starting point for all methods. To evaluate our method, we set the initial
value of $\sigma$ to be the 1st percentile of pairwise distances in the data
set. Note this is similar to our lower bound given in section 4, but a little
less stringent. We run Algorithm 2 with depth=1 and pick the value of $\sigma$
that corresponds to the best observed $k$-partition (as measured by ${\rm
c\mathchar 45\relax NNC}$), run Kernel $k$-means and rerun our method starting
from the resulting $k$-partition with depth$=2$. Note that this resembles the
hierarchical search described in section 6. For each method, we collect the
best value of NMI and ${\rm c\mathchar 45\relax NNC}$ among the produced
clusterings. We report the average over 50 runs, each with a different initial
$k$-partition. Results are shown in Table 2. Our method achieves better values
of both measures in most cases.

Table 2: Comparison of the different methods in terms of quality measures | NMI | ${\rm c\mathchar 45\relax NNC}$
---|---|---
Dataset | MKNN | GridSearch | OURS | MKNN | GridSearch | OURS
Aggr. | 0.690 | 0.864 | 0.872 | 0.255 | 0.210 | 0.203
Compound | 0.689 | 0.778 | 0.730 | 0.239 | 0.230 | 0.215
D31 | 0.810 | 0.931 | 0.951 | 0.356 | 0.332 | 0.316
Flame | 0.489 | 0.521 | 0.615 | 0.106 | 0.096 | 0.093
Jain | 0.229 | 0.361 | 0.353 | 0.116 | 0.062 | 0.062
Pathbased | 0.820 | 0.662 | 0.902 | 0.169 | 0.134 | 0.137
R15 | 0.922 | 0.954 | 0.979 | 0.302 | 0.300 | 0.274
Spiral | 0.187 | 0.145 | 0.239 | 0.175 | 0.155 | 0.151
Audit | 0.717 | 0.685 | 0.703 | 0.097 | 0.082 | 0.082
Derma. | 0.889 | 0.877 | 0.913 | 0.249 | 0.256 | 0.238
WDBC | 0.531 | 0.547 | 0.550 | 0.123 | 0.108 | 0.107
WiFi | 0.781 | 0.835 | 0.856 | 0.157 | 0.140 | 0.137
Wine | 0.923 | 0.913 | 0.923 | 0.143 | 0.142 | 0.143

###  7.2 Running times and Scalability

In this section we evaluate the efficiency of our method. We report the
average total running times in the previously described experiment for all
algorithms in Table 3. Our method generally sits between GridSearch and MKNN.
It performs significantly more iterations than the baselines, and thus better
running times could be obtained by limiting the number of inspected values if
necessary.

Table 3: Total running times in seconds | Time in seconds |  | Time in seconds
---|---|---|---
Dataset | MKNN | GridSearch | OURS | Dataset | MKNN | GridSearch | OURS
Aggr. | 0.824 | 0.486 | 0.617 | Spiral | 0.157 | 0.108 | 0.133
Compound | 0.200 | 0.146 | 0.172 | Audit | 0.578 | 0.467 | 1.111
D31 | 22.029 | 11.735 | 10.757 | Derma. | 0.152 | 0.106 | 0.100
Flame | 0.064 | 0.046 | 0.061 | WDBC | 0.325 | 0.204 | 0.213
Jain | 0.140 | 0.097 | 0.143 | WiFi | 7.095 | 3.520 | 4.402
Pathbased | 0.110 | 0.077 | 0.094 | Wine | 0.044 | 0.034 | 0.036
R15 | 0.475 | 0.329 | 0.406 |

To offer a finer running time comparison, as well as to evaluate scalability,
we run the algorithms on samples of MNIST 666http://yann.lecun.com/exdb/mnist/
and set the number of iterations to be the same for all methods. In
particular, we set it to 13, which is the number of values tested by
GridSearch. Figure 1 shows time taken per iteration, averaged over 50 runs. By
iteration we refer to the set of computations required to produce and test a
new value of the bandwidth parameter. The reason the running time of
GridSearch increases significantly at some point is that the first values of
$\sigma$ are too small and Kernel $k$-means converges after one iteration,
highlighting the wasteful nature of GridSearch. Our method benefits mostly
from being able to run a small number of iterations of Kernel $k$-means to
converge.

Figure 1: Running time per iteration for different samples of the MNIST data
set

###  7.3 Comparison with binary search

The reader might observe that our method resembles a form of binary search.
Thus, one might suspect that similar results could be obtained using a
conventional binary search algorithm, without going to the trouble of
implementing Algorithm 2. Here we illustrate why our algorithm is a vastly
superior alternative.

The setup is as follows: we initialize $\sigma$ to be the 1st percentile of
the squared pairwise distances and then run iterations of binary search with a
precision of $10^{-3}$ and Algorithm 2 with depth equal to $10$. We repeat the
experiment $10$ times and report average iteration time and absolute error of
the estimate of the critical value of $\sigma$. The results are shown in Table
4. Binary search was implemented efficiently, updating the kernel matrix with
fast matrix-vector operations.

Our method achieves a speedup of about 10x in all cases, and the error is
often smaller. Of course, the error can be controlled in both algorithms at
the expense of running time. A noteworthy difference between both methods (not
in favor of any of the two) is that binary search is designed to control
absolute error, while Algorithm 2 controls the relative error of the power
computation.

Table 4: Running times of our method and binary search. We report average iteration running times, speedup and mean relative error of the $\sigma$ estimate over 100 iterations | Iteration time in seconds | Speedup | Relative error: $\frac{\sigma_{\rm{true}}-\sigma_{\rm{estimated}}}{\sigma_{\rm{true}}}$
---|---|---|---
Dataset | BinarySearch | OURS | - | BinarySearch | OURS
Aggr. | 0.941 | 0.080 | 11.7x | $1.55\times 10^{-3}$ | $5.3\times 10^{-4}$
Audit | 0.793 | 0.069 | 11.5x | $8.341\times 10^{-2}$ | $5.8\times 10^{-4}$
Compound | 0.192 | 0.019 | 9.9x | $2.20\times 10^{-3}$ | $5.8\times 10^{-4}$
D31 | 15.740 | 1.148 | 13.7x | $3.95\times 10^{-3}$ | $4.8\times 10^{-}$
Derma. | 0.139 | 0.014 | 9.7x | $1.3\times 10^{-4}$ | $8.368\times 10^{-2}$
Flame | 0.063 | 0.007 | 9.1x | $5.1\times 10^{-3}$ | $5.6\times 10^{-4}$
Jain | 0.144 | 0.014 | 10.5x | $2.6\times 10^{-3}$ | $1.17\times 10^{-2}$
Pathbased | 0.096 | 0.010 | 9.7x | $1.98\times 10^{-3}$ | $5.9\times 10^{-4}$
R15 | 0.430 | 0.039 | 11.0x | $4.912\times 10^{-2}$ | $5.5\times 10^{-4}$
Spiral | 0.102 | 0.011 | 9.6x | $1.13\times 10^{-3}$ | $6.2\times 10^{-4}$
WDBC | 0.398 | 0.036 | 11.2x | $10^{-6}$ | $6.2\times 10^{-4}$
WiFi | 5.284 | 0.442 | 11.9x | $6\times 10^{-5}$ | $4.9\times 10^{-4}$
Wine | 0.042 | 0.005 | 7.7x | $2\times 10^{-5}$ | $5.7\times 10^{-4}$

##  8 Conclusion

In this paper we have addressed the problem of hyperparameter search in the
Kernel $k$-means context. Our contribution is two-fold. First, we have derived
a tight lower bound for the bandwidth parameter of RBF kernels, below which
Kernel $k$-means will be rendered useless. Second, we have proposed a method
to optimize kernel hyperparameters for Kernel $k$-means. We have proved that
our method approximates critical values of the hyperparameter to arbitary
precision in a small number of iterations. Unlike grid search or other
heuristics, our method does not test redundant hyperparameter values, that is,
values that result in the same clustering output, and thus no computation is
wasted.

Our experiments demonstrate how our approach enables the efficient evaluation
of a fine variety of hyperparameter values, revealing high-quality clustering
results at a moderate computational cost. In the future it would be
interesting to extend our method to other kernel-based clustering and
classification algorithms.

## References

  * [1] Aloise, D., Deshpande, A., Hansen, P., Popat, P.: Np-hardness of euclidean sum-of-squares clustering. Machine learning 75(2), 245–248 (2009)
  * [2] Bach, F.R., Jordan, M.I.: Learning spectral clustering. In: Advances in neural information processing systems. pp. 305–312 (2004)
  * [3] Ben-David, S., Von Luxburg, U., Pál, D.: A sober look at clustering stability. In: International Conference on Computational Learning Theory. pp. 5–19. Springer (2006)
  * [4] Ben-Hur, A., Horn, D., Siegelmann, H.T., Vapnik, V.: Support vector clustering. Journal of machine learning research 2(Dec), 125–137 (2001)
  * [5] Cortes, C., Vapnik, V.: Support-vector networks. Machine learning 20(3), 273–297 (1995)
  * [6] Cover, T.M., Thomas, J.A.: Elements of information theory. John Wiley & Sons (2012)
  * [7] Dhillon, I.S., Guan, Y., Kulis, B.: Kernel k-means: spectral clustering and normalized cuts. In: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 551–556. ACM (2004)
  * [8] Ester, M., Kriegel, H.P., Sander, J., Xu, X., et al.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Kdd. vol. 96, pp. 226–231 (1996)
  * [9] Gordon, D.M., et al.: A survey of fast exponentiation methods. J. Algorithms 27(1), 129–146 (1998)
  * [10] Greene, D., Cunningham, P.: Practical solutions to the problem of diagonal dominance in kernel document clustering. In: Proceedings of the 23rd international conference on Machine learning. pp. 377–384. ACM (2006)
  * [11] Hofmann, T., Schölkopf, B., Smola, A.J.: Kernel methods in machine learning. The annals of statistics pp. 1171–1220 (2008)
  * [12] Jaakkola, T.S., Diekhans, M., Haussler, D.: Using the fisher kernel method to detect remote protein homologies. In: ISMB. vol. 99, pp. 149–158 (1999)
  * [13] Jain, A.K.: Data clustering: 50 years beyond k-means. Pattern recognition letters 31(8), 651–666 (2010)
  * [14] Lloyd, S.: Least squares quantization in pcm. IEEE transactions on information theory 28(2), 129–137 (1982)
  * [15] Moon, T.K.: The expectation-maximization algorithm. IEEE Signal processing magazine 13(6), 47–60 (1996)
  * [16] Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Advances in neural information processing systems. pp. 849–856 (2002)
  * [17] Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of computational and applied mathematics 20, 53–65 (1987)
  * [18] Vapnik, V.: Estimation of dependences based on empirical data. Springer Science & Business Media (2006)
  * [19] Von Luxburg, U.: A tutorial on spectral clustering. Statistics and computing 17(4), 395–416 (2007)
  * [20] Zelnik-Manor, L., Perona, P.: Self-tuning spectral clustering. In: Advances in neural information processing systems. pp. 1601–1608 (2005)

## Appendix

###### Proof of Theorem 1

Consider the squared distance as written in Eq. (2). For the choice of
cluster, we can drop the constant term $\kappa(x,x)$ and compute

$\displaystyle\operatorname*{arg\,min}_{j}~{}-\frac{2\sum_{y\in\pi_{j}}\kappa(x,y)}{n_{j}}+\frac{\sum_{y,z\in\pi_{j}}\kappa(y,z)}{n_{j}^{2}}.$
(7)

If $x\in\pi_{j}$ we can write

$\displaystyle-\frac{2\sum_{y\in\pi_{j}}\kappa(x,y)}{n_{j}}+\frac{\sum_{y,z\in\pi_{j}}\kappa(y,z)}{n_{j}^{2}}$
(8) $\displaystyle=$
$\displaystyle-\frac{2\kappa(x,x)}{n_{j}}-\frac{2\sum_{y\in\pi_{j},y\neq
x}\kappa(x,y)}{n_{j}}+\frac{\sum_{y,z\in\pi_{j}}\kappa(y,z)}{n_{j}^{2}}.$ (9)

If $x\in\pi_{j}$ and $\|\phi(x)-m_{j}\|_{2}^{2}\leq\|\phi(x)-m_{i}\|_{2}^{2}$
for all $i\neq j$, then $a$ will remain in the same cluster. Considering (7)
and (8), we can write this condition as

$\displaystyle\frac{2\kappa(x,x)}{n_{j}}\geq$
$\displaystyle\frac{2\sum_{y\in\pi_{i}}\kappa(x,y)}{n_{i}}-\frac{\sum_{y,z\in\pi_{i}}\kappa(y,z)}{n_{i}^{2}}$
$\displaystyle-\frac{2\sum_{y\in\pi_{j},y\neq
x}\kappa(x,y)}{n_{j}}+\frac{\sum_{y,z\in\pi_{j}}\kappa(y,z)}{n_{j}^{2}}.$

Since $\kappa(x,y)\geq 0$ for any pair of points $x,y$, we can drop the
negative terms on the right-hand side to obtain the following, more
restrictive, condition:

$\displaystyle\frac{2\kappa(x,x)}{n_{j}}\geq\frac{2\sum_{y\in\pi_{i}}\kappa(x,y)}{n_{i}}+\frac{\sum_{y,z\in\pi_{j},y\neq
z}\kappa(y,z)+n_{j}}{n_{j}^{2}}$
$\displaystyle=\frac{2n_{j}^{2}\sum_{y\in\pi_{i}}\kappa(x,y)+n_{i}\left(\sum_{y,z\in\pi_{j},y\neq
z}\kappa(y,z)+n_{j}\right)}{n_{i}n^{2}_{j}}.$ (10)

Here we have used $\sum_{x\in\pi_{j}}\kappa(x,x)=n_{j}$. If we define
$\omega=\max_{x\neq y}\kappa(x,y)$, then the two following inequalities hold:

$\displaystyle n_{i}\omega\geq\sum_{y\in\pi_{i}}\kappa(x,y),$ $\displaystyle
n_{j}^{2}\omega\geq\sum_{y,z\in\pi_{j},y\neq z}\kappa(y,z)$

We can thus consider the following, more restrictive, condition (recall that
$\kappa(x,x)=1$):

$\displaystyle\frac{2\kappa(x,x)}{n_{j}}$
$\displaystyle\geq\frac{2n_{j}^{2}n_{i}\omega+n_{i}\left(n_{j}^{2}\omega+n_{j}\right)}{n_{i}n^{2}_{j}}=3\omega+\frac{1}{n_{j}}\Leftrightarrow\frac{1}{n_{j}}\geq
3\omega.$ (11)

Trivially, $\frac{1}{n}\geq 3\omega\Rightarrow\frac{1}{n_{j}}\geq 3\omega$.
Now, after minor computational efforts, it is

$\displaystyle\frac{1}{n}\geq 3\omega\Leftrightarrow-\log n\geq\log
3-\frac{\|x-y\|_{2}^{2}}{\sigma}\Leftrightarrow\frac{\|x-y\|_{2}^{2}}{\log
3n}\geq\sigma,$ (12)

where $x,y=\operatorname*{arg\,min}_{x.y\in X}\|x-y\|_{2}^{2}$. Therefore, we
have (12) $\Rightarrow$ (11) $\Rightarrow$ (10) $\Rightarrow$
$\|\phi(x)-m_{j}\|_{2}^{2}\leq\|\phi(x)-m_{i}\|_{2}^{2}$ for all $i\neq j$.
Since $x$ is an arbitrary element of $X$, (12) is a sufficient condition for
kernel $k$-means to make no changes. ∎