# Generalized Spectral Clustering for Directed and Undirected Graphs

Harry Sevi  Matthieu Jonckheere  Argyris Kalogeratos

###### Abstract

Spectral clustering is a popular approach for clustering undirected graphs,
but its extension to directed graphs (digraphs) is much more challenging. A
typical workaround is to naively symmetrize the adjacency matrix of the
directed graph, which can however lead to discarding valuable information
carried by edge directionality. In this paper, we present a _generalized
spectral clustering_ framework that can address both directed and undirected
graphs. Our approach is based on the spectral relaxation of a new functional
that we introduce as the generalized Dirichlet energy of a graph function,
with respect to an arbitrary positive regularizing measure on the graph edges.
We also propose a practical parametrization of the regularizing measure
constructed from the iterated powers of the natural random walk on the graph.
We present theoretical arguments to explain the efficiency of our framework in
the challenging setting of unbalanced classes. Experiments using directed
$K$-NN graphs constructed from real datasets show that our graph partitioning
method performs consistently well in all cases, while outperforming existing
approaches in most of them.

Machine Learning, ICML

##  1 Introduction

Clustering is one of the most popular techniques in analyzing large datasets
and has widespread applications in machine learning, network analysis, and
biology. Typically, when viewing the data as a graph, the problem of
clustering is to partition the graph into several weakly interconnected
clusters. This notion is formalized as a discrete optimization problem aiming
to minimize a functional such as the graph cut or the normalized cut (Von
Luxburg, 2007; Shi & Malik, 2000). The spectral relaxation of this
minimization problem leads to finding the eigenvectors of a certain graph
Laplacian and using these as input features for the $k$-means algorithm. This
forms the backbone of spectral clustering.

Over the last three decades, spectral clustering has become one of the most
widely used clustering methods due to its simplicity, efficiency, and strong
theoretical background (Ng et al., 2002; Peng et al., 2015; Boedihardjo et
al., 2021). Unfortunately, although many graphs carry valuable information in
their directed edges, the vast majority of spectral clustering algorithms only
operate on undirected graphs. Typical examples of directed graphs (digraphs)
are social or content networks, as well as networks with flows (e.g. roads,
electrical networks, rivers). Another fundamental source of digraphs in data
processing comes from the representation of points clouds in $d$-dimensions
through, e.g. $K$-nearest neighbors ($K$-NN) graphs or other kernel-based
procedures.

Therefore, on the one hand, the information encoded in the edge directionality
of digraphs should be used. On the other hand, the extension of the spectral
clustering in the digraph setting is not straightforward. The adjacency matrix
of a digraph is non-symmetric. It thus seems to be no obvious definition of a
symmetric and real-valued graph Laplacian with a full set of real eigenvalues
that uniquely encodes any digraph. The commonly used approach for clustering
digraphs is to build a symmetrized adjacency matrix from the original non-
symmetric one, and then to apply spectral clustering techniques to the graph
Laplacian of it (Satuluri & Parthasarathy, 2011). As explained, this
potentially discards valuable information.

In an attempt to overcome this challenging problem, a slew of works has been
proposed in the last two decades. In (Zhou et al., 2005), they use the
Laplacian on digraphs defined in (Chung, 2005) to propose spectral clustering
on digraphs. In (Meilă & Pentney, 2007), they attack the clustering problem on
digraphs from the original asymmetric adjacency matrix of a given digraph
through the weighted cut formulation. In (Rohe et al., 2016), they propose a
novel spectral co-clustering on digraphs based on the singular value
decomposition of a modified adjacency matrix. In recent years, some clustering
approaches based on Hermitian operators on digraphs have been investigated
(Cucuringu et al., 2020; Laenen & Sun, 2020). Note that all the approaches
cited above are based on the construction of symmetric operators on digraphs.

In this paper, we present a unifying spectral clustering framework on directed
and undirected graphs based on the spectral relaxation of a novel energy
functional, which in turn allows us to generalize graph Laplacians. This
functional is termed _generalized Dirichlet energy_ (GDE) as it extends the
well-known notion of Dirichlet energy. In particular, GDE is defined with
respect to any positive regularizing measure and any Markov transition matrix.
We propose for practical use a parametrized family of such measures. The
resulting _generalized spectral clustering_ (GSC) approach extends standard
spectral clustering, usually applied on strongly connected digraphs (Zhou et
al., 2005; Palmer & Zheng, 2020), to any digraphs. More importantly, it
achieves that without involving the Pagerank’s teleporting random walk (Page
et al., 1999) as a surrogate of the natural random walk.

The rest of the paper is organized as follows. In Sec. 2, we present basic
concepts of graph theory and Markov chains. In Sec. 3, we introduce the
generalized Dirichlet energy and the new generalized graph Laplacians. In Sec.
4, we present the formulation of the GSC and an algorithmic scheme. In Sec. 5,
we provide theoretical results proving the efficiency of GSC in the
challenging setting of unbalanced clusters compared to classical spectral
clustering. Sec. 6 includes our extensive experimental study on a toy dataset
and various real-world UCI datasets. Technical proofs are provided in the
Appendix.

##  2 Preliminaries and background

Essential concepts. Let $\mathcal{G}=(\mathcal{V},\mathcal{E},w)$ be a
weighted directed graph (digraph) where $\mathcal{V}$ is the finite set of
$N=|\mathcal{V}|$ vertices, and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the finite set of edges.
Each edge $(x,y)$ is an ordered vertex pair representing the direction of a
link from vertex $x$ to vertex $y$.

Any function $\nu:\mathcal{V}\rightarrow\mathbb{R}_{+}$, associating a
nonnegative value to each graph vertex, can be regarded as a positive vertex
measure; respectively any function $q:\mathcal{E}\rightarrow\mathbb{R}_{+}$
can be regarded as a positive edge measure.

The edge weight function
$w:\mathcal{V}\times\mathcal{V}\rightarrow\mathbb{R}_{+}$ associates a
nonnegative real value to every vertex pair: $w(x,y)\geq 0$, iff
$(x,y)\in\mathcal{E}$, otherwise $w(x,y)=0$.

The graph $\mathcal{G}$ can be entirely represented by its weighted adjacency
matrix $\mathbf{W}=\\{w_{ij}\\}_{i,j=1}^{N}\in\mathbb{R}_{+}^{N\times N}$,
where $w_{ij}=w(x_{i},x_{j})$ is the weight of the edge $(x_{i},x_{j})$. We
define the out-degree and the in-degree of the $i$-th vertex by $\textstyle
d_{i}^{+}=\sum_{j=1}^{N}w_{ij}$ and $d_{i}^{-}=\sum_{j=1}^{N}w_{ji}$,
respectively. Also, the function $\operatorname{diag}(\nu)$ returns a square
diagonal matrix with the elements of the input vector $\nu$ in its diagonal.

Given a subset of vertices $S\subseteq\mathcal{V}$, we denote its complement
by $\bar{S}=\mathcal{V}\backslash S$. Also, we denote the characteristic
function of a set $S$ by
$\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}\in\\{0,1\\}^{N}$, which
gives $\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)=1$, iff $x\in S$,
and $\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)=0$ otherwise.

Consider a graph function ${f}$ mapping all of its vertices to an
$N$-dimensional complex column vector :

$f=[\,f(x)\,]_{x\in\mathcal{V}}^{{\mkern-1.5mu\mathsf{T}}}\in\mathbb{C}^{N}$.

We assume that graph functions are defined in $\ell^{2}(\mathcal{V},\nu)$,
which is the Hilbert space of functions defined over the vertex set
$\mathcal{V}$ of $\mathcal{G}$, endowed with the inner product, and $\nu$ is a
positive measure. Hence, for all $f,g\in\ell^{2}(\mathcal{V},\nu)$ it holds:

$\langle{f},{g}\rangle_{\nu}=\sum_{x\in\mathcal{V}}\overline{f(x)}g(x)\nu(x),$

where $\overline{f(x)}$ denotes the complex conjugate of $f(x)$.

What we call in short as random walk on a weighted graph $\mathcal{G}$, is
defined more formally as a natural random walk on the graph as a homogeneous
Markov chain $\mathcal{X}=(X_{t})_{t\geq 0}$ with a finite state space
$\mathcal{V}$, and with state transition probabilities proportional to the
edge weights.

The entries of the transition matrix
$\mathbf{P}=[\,p(x,y)\,]_{x,y\in\mathcal{V}}$ are defined by:

$p(x,y)=\mathbb{P}(X_{t+1}=y\,|\,X_{t}=x)=\frac{w(x,y)}{\sum_{z\in\mathcal{V}}w(x,z)}.$

For a directed and strongly connected $\mathcal{G}$, the random walk
$\mathcal{X}$ is irreducible. Under mild conditions, $\mathcal{X}$ is also
ergodic, and therefore as $t\rightarrow\infty$, the measures $p^{t}(x,\cdot)$,
$\forall x\in\mathcal{V}$, converge towards the _unique_ stationary
distribution denoted by the row vector $\pi\in\mathbb{R}_{+}^{N}$ (Brémaud,
2013). Within the undirected setting: $d_{i}^{+}=d_{i}^{-}=d_{i}$, where
$d\in\mathbb{R}_{+}^{N\times 1}$ is the vector of the vertex degrees;
moreover, the ergodic distribution is proportional to the vertex degree
distribution, i.e. $\pi\propto d$.

The emphasis of our presentation is put on digraphs, however, _our theoretical
framework applies to any type of graph with nonnegative weights_.

Dirichlet energy and graph Laplacians.

In the literature of Dirichlet forms (Saloff-Coste, 1997; Montenegro et al.,
2006) or harmonic analysis on graphs (Sevi et al., 2018), the definition of
the Dirichlet energy of a graph function $f$ is usually as follows.

######  Definition 2.1.

Dirichlet energy of a graph function. Let $\mathcal{X}$ be a random walk on a
digraph $\mathcal{G}$, with transition matrix $\mathbf{P}$. Let also be the
ergodic distribution $\pi$ of the random walk, and $\pi(x)$ referring to
vertex $x\in\mathcal{V}$. The Dirichlet energy of a graph function $f$ is
defined by:

$\mathcal{D}(f)=\sum_{x,y\in\mathcal{V}}\pi(x)p(x,y)|f(x)-f(y)|^{2}.$ (1)

This quantity can be also expressed in its quadratic form:

$\mathcal{D}(f)=2\,\langle
f,\mathbf{L}_{\textnormal{RW}}f\rangle_{\pi}=2\,\langle f,\mathbf{L}f\rangle.$

In this form, the Dirichlet energy reveals the random walk Laplacian
$\mathbf{L}_{\textnormal{RW}}$ and equivalently the unnormalized Laplacian
$\mathbf{L}$ on directed graphs (Chung, 2005; Sevi et al., 2018). These
matrices are formally defined as follows:

$\displaystyle\mathbf{L}_{\textnormal{RW}}$
$\displaystyle=\mathbf{I}-\frac{1}{2}(\mathbf{P+\Pi^{-1}P^{{\mkern-1.5mu\mathsf{T}}}\Pi}),$
(2) $\displaystyle\mathbf{L}$
$\displaystyle=\mathbf{\Pi}-\frac{1}{2}(\mathbf{\Pi
P+P^{{\mkern-1.5mu\mathsf{T}}}\Pi}),$ (3)

where $\mathbf{I}$ is the identity matrix of suitable size (here $N$), and
$\boldsymbol{\Pi}=\operatorname{diag}(\pi)$ is the diagonal matrix associated
with an ergodic measure $\pi$.

It is worth mentioning that $\mathbf{L}_{\textnormal{RW}}$ and $\mathbf{L}$ on
directed graphs, are the counterpart of the random walk Laplacian and
unnormalized Laplacian on undirected graphs. For undirected graphs it holds
$\boldsymbol{\Pi}\propto\mathbf{D}=\operatorname{diag}(d)$ and
$\mathbf{P}=\mathbf{D}^{-1}\mathbf{W}$; therefore, in that case the random
walk and unnormalized Laplacians become respectively:
$\mathbf{L}_{\textnormal{RW}}=\mathbf{I-P}$ and
$\mathbf{L}=\mathbf{D}-\mathbf{W}$.

##  3 Generalized Dirichet energy and Laplacians on graphs

We have seen in the previous section the conventional way certain concepts
appear in the literature. In this section, we introduce the generalized
Dirichlet energy (GDE), which is defined under an arbitrary positive measure
$q$ over the graph edges, and the associated generalized graph Laplacians.
These concepts constitute the foundation of our framework.

######  Definition 3.1.

Generalized Dirichlet Energy of a graph function. Let $q$ be an arbitrary
positive edge measure on a digraph $\mathcal{G}$, and
$\mathbf{Q}=\\{\,q(x,y)\,\\}_{x,y\in\mathcal{V}}$ the edge measure operator.
The generalized Dirichlet energy of a graph function ${f}$ associated with the
edge measure $q$ on $\mathcal{G}$ is expressed as:

$\mathcal{D}_{\mathbf{Q}}^{2}(f)=\sum_{x,y\in\mathcal{V}}q(x,y)|f(x)-f(y)|^{2}.$
(4)

The broad generality of this definition stems from the fact that it integrates
all the graph-related information into the arbitrary positive edge measure
$q$, thus its operator $\mathbf{Q}$. As can be noted, Definition 2.1 is a
particular case of our generalized form, as $\mathcal{D}_{\mathbf{Q}}^{2}(f)$
= $\mathcal{D}(f)$, when $q(x,y)=\pi(x)p(x,y)$. More generally, $q(x,y)$ can
be a function combining an arbitrary vertex measure $\nu$ and an edge measure
based on the transition matrix $\mathbf{P}=[\,p(x,y)\,]_{x,y\in\mathcal{V}}$
of the random walk $\mathcal{X}$ on $\mathcal{G}$. We refine accordingly the
GDE of a graph function ${f}$ associated with a random walk as:

$\mathcal{D}_{\nu,\mathbf{P}}^{2}(f)=\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)|f(x)-f(y)|^{2}.$
(5)

This formulation suggests that we can go further and derive interesting energy
functionals by replacing the stationary distribution $\pi$ of the random walk
with other more sophisticated or better adapted vertex measures for digraphs.
Note that, although $\nu$ can be an arbitrary measure, it is easy to see that
replacing it by its $\ell^{1}$-normalized counterpart
$\nu^{\prime}=\frac{\nu}{|\\!|\nu|\\!|_{1}}$ would merely scale the GDE of Eq.
(5) by $\frac{1}{|\\!|\nu|\\!|_{1}}$. Therefore, we could safely restrict
$\nu$ to be a probability vertex measure.

We are now ready to introduce the generalized graph Laplacians that rely on
the GDE of Eq. (5).

######  Definition 3.2.

Generalized graph Laplacians. Let $\mathcal{X}$ be a random walk on a digraph
$\mathcal{G}$, with transition matrix $\mathbf{P}$. Under an arbitrary
positive vertex measure $\nu$ on $\mathcal{G}$, consider the positive vertex
measure:

$\xi(y)=\sum_{x\in\mathcal{V}}\nu(x)p(x,y),\quad\forall y\in\mathcal{V}.$ (6)

Let be the diagonal matrices $\mathbf{N}=\operatorname{diag}(\nu)$ and
$\mathbf{\Xi}=\operatorname{diag}(\xi)$. The generalized random walk Laplacian
and the unnormalized generalized Laplacian on $\mathcal{G}$ are defined by:

$\mathbf{L}_{\textnormal{RW}}(\nu)=\mathbf{I-(I+N^{-1}\Xi)^{-1}(P+N^{-1}P^{{\mkern-1.5mu\mathsf{T}}}N)},$
(7)

$\mathbf{L}(\nu)=\mathbf{N+\Xi-(NP+P^{{\mkern-1.5mu\mathsf{T}}}N}).$ (8)

$\mathbf{L}_{\textnormal{RW}}(\nu)$ and $\mathbf{L}(\nu)$ extend the graph
Laplacians defined in Eq. (2) and Eq. (3). Moreover, $\mathbf{L}(\nu)$ has the
property of being self-adjoint in $\ell^{2}(\mathcal{V})$, i.e.
$\mathbf{L}(\nu)=\mathbf{L}(\nu)^{{\mkern-1.5mu\mathsf{T}}}$.

Next, we establish the connection between the GDE and the generalized random
walk Laplacian.

######  Proposition 3.1.

Let $\mathcal{X}$ be a random walk on a digraph $\mathcal{G}$, with transition
matrix $\mathbf{P}$. Let $\nu$ be an arbitrary positive vertex measure on
$\mathcal{G}$, and $\xi$ be the vertex measure defined by Eq. (6). The
generalized Dirichlet energy of a graph function $f$ and the generalized
random walk Laplacian $\mathbf{L}_{\textnormal{RW}}(\nu)$ of Eq. (7) are
associated as follows:

$\mathcal{D}_{\nu,\mathbf{P}}^{2}(f)=\langle{f},\mathbf{L}_{\textnormal{RW}}(\nu){f}\rangle_{\nu+\xi}.\,$

As we can appreciate, $\mathbf{L}_{\textnormal{RW}}(\nu)$ is self-adjoint in
$\ell^{2}(\mathcal{V},\nu+\xi)$.

Finally, we introduce the normalized GDE (also known as Rayleigh quotient) of
a graph function $f$:

$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\nu,\mathbf{P}}(f)=\frac{\mathcal{D}_{\nu,\mathbf{P}}^{2}(f)}{\|{f}\|_{\nu+\xi}^{2}}.$
(9)

Given a positive vertex measure $\mu$, we can introduce a parametrized vertex
measure $\nu_{t}$, $t\geq 0$, derived from the iterated powers of the natural
random walk on a given graph:

$\nu_{t}(x)={\textstyle\mu}^{{\mkern-1.5mu\mathsf{T}}}{\mathbf{P}}^{t}{\delta}_{x}\,,\quad\mu\in\mathbb{R}_{+}^{N}\,,$
(10)

where $\delta_{x}\in\\{0,1\\}^{N\times 1}$ is the vector output of the
Kronecker delta function at $x\in\mathcal{V}$. We can now derive the following
proposition for the ergodic setting.

######  Proposition 3.2.

Let $\mathcal{X}$ be an ergodic random walk on a digraph $\mathcal{G}$, whose
transition matrix is $\mathbf{P}$ with stationary distribution $\pi$. At
$t\rightarrow\infty$, we have:

$\lim_{t\to\infty}\mathcal{D}_{\nu_{t},\mathbf{P}}^{2}(f)=\mathcal{D}_{\pi,\mathbf{P}}^{2}(f).$

This interesting result indicates that, as $t\to\infty$, the GDE associated
with the transition matrix $\mathbf{P}$ of a graph function $f$, under a
parametrized vertex measure $\nu_{t}\\!$, coincides with the respective energy
of an ergodic random walk under the usual unnormalized Laplacian
$\mathbf{L}(\pi)$.

##  4 Generalized spectral clustering on graphs

This section presents our general spectral clustering formulation for any type
of graphs, which is based on the GDE and the generalized graph Laplacians.

###  4.1 Graph partitioning functional based on GDE

We commence with some reminders and additional preliminary concepts. Recall
that $\mathcal{G}$ is a digraph of $N=|\mathcal{V}|$ vertices, and
$\mathcal{X}=(X_{t})_{t\geq 0}$ is a natural random walk on $\mathcal{G}$,
with transition matrix $\mathbf{P}=[\,p(x,y)\,]_{x,y\in\mathcal{V}}$. In the
general setting, $\mathcal{X}$ may be transient, thus not having an ergodic
distribution. Let $\nu:\mathcal{V}\rightarrow\mathbb{R}_{+}$ be a vertex
measure, and $\nu(S)$ be its evaluation over a subset $S\subseteq\mathcal{V}$:
$\nu(S)=\sum_{x\in S}\nu(x)$.

Now, let $q:\mathcal{E}\rightarrow\mathbb{R}_{+}$ be a composite edge measure
such that $q(x,y)=\nu(x)p(x,y)$. Respectively, consider the edge measure
between two disjoint vertex subsets $S,U\subseteq\mathcal{V}$ by:

$\displaystyle q(S,U)$ $\displaystyle=\sum_{x\in S,y\in U}q(x,y)\ =\sum_{x\in
S,y\in U}\nu(x)p(x,y)$ $\displaystyle=\mathbb{P}(X_{t}\in S,X_{t+1}\in
U),\quad\text{for any }t\geq 0.$ (11)

$q(S,U)$ is a generic measure related to Markov chains (Sinclair, 1992; Levin
& Peres, 2017). In our setting, it quantifies the probability that the random
walk escapes from the set $S$ to $U$ in one step, when the starting vertex of
the walk is drawn according to the arbitrary vertex measure $\nu$. When
considering $U=\bar{S}$, this discussion becomes very interesting for graph
partitioning. In essence, $q(S,\bar{S})$ offers a _probabilistic point of view
over the graph cut_ between a set $S$ and the rest of the graph (Meilă & Shi,
2001).

######  Proposition 4.1.

Let $\mathcal{X}$ be a random walk on a digraph $\mathcal{G}$, with transition
matrix $\mathbf{P}$. Let $\nu$ be a positive vertex measure, and $q$ be a
positive edge measure, both on $\mathcal{G}$. Let $S\subseteq\mathcal{V}$ and
$\bar{S}=\mathcal{V}\backslash S$. Consider the characteristic function
$\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}$, associated with the set
$S$, as a graph function. The composite edge measure $q(S,\bar{S})$ and the
generalized Dirichlet energy
$\mathcal{D}_{\nu,\mathbf{P}}^{2}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}})$
are related as follows:

$q(S,\bar{S})+q(\bar{S},S)=\mathcal{D}_{\nu,\mathbf{P}}^{2}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}).$
(12)

To bring this discussion closer to the clustering setting, we can imagine
$\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}$ to be a _decision
function_ produced by some algorithm that aims to partition the graph into two
parts. In that sense, Eq. (12) offers a meaningful interpretation of the GDE
of any graph partitioning decision vector:
$\mathcal{D}_{\nu,\mathbf{P}}^{2}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}})$
quantifies how difficult it is for a random walk with transitions $q$ to
escape from $S$ and reach $\bar{S}$, or vice versa.

Note also the symmetricity , i.e.
$\mathcal{D}_{\nu,\mathbf{P}}^{2}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}})=\mathcal{D}_{\nu,\mathbf{P}}^{2}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{${\bar{S}}$}}})$.

The multiway graph partitioning problem aims to partition a digraph into a
given number of disjoint subgraphs, such that the edge density among them is
minimal. Given a $k$-partition of the graph vertices, denoted by
$\boldsymbol{V}=\\{V_{i}\\}_{i=1}^{k}$, where
$\bigcup_{i=1}^{k}\\!\\!V_{i}=\mathcal{V}$, then, under an arbitrary vertex
measure $\nu$, we define the _partition’s Dirichlet energy_ by:

$\mathcal{D}_{\nu,\mathbf{P}}^{2}(\boldsymbol{V})=\sum_{i=1}^{k}\mathcal{D}_{\nu,\mathbf{P}}^{2}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{i}$}}}).$
(13)

This makes concrete our interest in finding a $k$-partition of the digraph
$\mathcal{G}$ that has minimal GDE
$\mathcal{D}_{\nu,\mathbf{P}}^{2}(\boldsymbol{V})$. Let us rewrite the energy
of the $k$-partition as:

$\mathcal{D}_{\nu,\mathbf{P}}^{2}(\boldsymbol{V})=\textnormal{tr}(\mathbf{U}^{{\mkern-1.5mu\mathsf{T}}}\mathbf{L}(\nu)\mathbf{U}),$

where $\mathbf{U}=[\,u_{i}\,]_{i=1}^{k}\in\mathbb{R}^{N\times k}$ is a matrix
whose $i$-th column is
$u_{i}=\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{i}$}}}$. Therefore, the
_generalized Dirichlet graph partitioning problem_ can be formulated as:

$\min_{\boldsymbol{V}=\\{V_{1},...,V_{k}\\}}\textnormal{tr}(\mathbf{U}^{{\mkern-1.5mu\mathsf{T}}}\mathbf{L}(\nu)\mathbf{U})\quad\textnormal{s.t.}\>u_{i}=\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{i}$}}},\>\forall
i\in\\{1,...,k\\}.$

As mentioned earlier, the generalized Dirichlet graph partitioning problem is
NP-hard. We thus proceed as in spectral clustering, by relaxing the
combinatorial constraint of $\mathbf{U}$ and seeking instead a solution among
all matrices $\mathbf{U}$ with orthonormal columns. For a given arbitrary
measure $\nu$, the relaxed problem becomes:

$\min_{\mathbf{U}}\
\textnormal{tr}(\mathbf{U}^{{\mkern-1.5mu\mathsf{T}}}\mathbf{L}(\nu)\mathbf{U})\quad\textnormal{s.t}.\>\mathbf{U}^{{\mkern-1.5mu\mathsf{T}}}\mathbf{U}=\mathbf{I}_{k},$
(14)

whose solution $\mathbf{U}$ can be shown to be the eigenvectors corresponding
to the $k$ smallest eigenvalues of the unnormalized generalized Laplacian
$\mathbf{L}(\nu)$.

The novelty of our framework lies in the definition of a generalized Laplacian
associated with an arbitrary positive measure, and its connection to a general
formulation of spectral clustering. In the case where $\nu$ is the stationary
measure $\pi$, the spectral relaxation of the normalized Dirichlet energy Eq.
(9) leads to the approach for strongly connected digraphs proposed by (Zhou et
al., 2005).

###  4.2 The GSC algorithm

The framework we have presented so far led to Eq. (14), which relies on an
arbitrary positive vertex measure $\nu$ to compute a set of $k$ decision
functions
$\\{\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{i}$}}}\\}_{i=1}^{k}$ of
minimal GDE. Each $\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{i}$}}}$
indicates one of the $k$ pairwise disjoint vertex clusters versus the rest of
the graph.

To render our framework more flexible for practical use, we extend what was
previously described in Eq. (10) by introducing a parametrized vertex measure
$\nu$ derived from the iterated powers of the natural random walk on a graph.
Specifically, we consider three optional points of parametrization: i) the
number of iterations $t\in\mathbb{N}$ of the random walk, ii) a uniform mixing
parameter $\gamma\in[0,1]$ for the transition matrix, and iii) an exponent
$\alpha\in\mathbb{R}$. Therefore, at a given vertex $x$, the proposed measure
is given by:

$\nu_{(t,\gamma)}^{\alpha}(x)=\left({\textstyle\frac{1}{N}}\boldsymbol{1}_{N\times
1}^{{\mkern-1.5mu\mathsf{T}}}\tilde{\mathbf{P}}_{\\!\\!\gamma}^{t}{\delta}_{x}\right)^{\alpha},$
(15)

where $\boldsymbol{1}_{N\times 1}$ is the all-ones vector ,
$\delta_{x}\in\\{0,1\\}^{N\times 1}$ is the vector output of the Kronecker
delta function at $x\in\mathcal{V}$, and

$\tilde{\mathbf{P}}_{\\!\\!\gamma}=\gamma\mathbf{P}+(1-\gamma){\textstyle\frac{1}{N}}\boldsymbol{1}_{N\\!\times\\!N}\,,\quad\gamma\in[0,1].$
(16)

Note that $\tilde{\mathbf{P}}_{\\!\\!\gamma}$ is a dense matrix, since it is a
convex combination of the original transition matrix and a uniform edge
measure (in the form of a complete graph
$\frac{1}{N}\boldsymbol{1}_{N\\!\times\\!N}$). Moreover, $\lim_{\gamma\to
1}\tilde{\mathbf{P}}_{\\!\\!\gamma}=\mathbf{P}$. Interestingly,
$\tilde{\mathbf{P}}_{\\!\\!\gamma}$ makes us recall the teleporting random
walk (Page et al., 1999); this connection is discussed in Sec. 5.1.

Plugging $\nu_{(t,\gamma)}^{\alpha}$ to Eq. (5), gives us the expression of
the GDE of one decision function
$\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{i}$}}}$ (seen as a graph
function), under this new composite edge measure:

$\mathcal{D}_{\nu_{(t,\gamma)}^{\alpha}\\!,\mathbf{P}}^{2}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{i}$}}})=\langle\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{i}$}}},\mathbf{L}_{t,\gamma}^{(\alpha)}\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{i}$}}}\rangle.$
(17)

For a given $\alpha$, and for any $t\in\mathbb{N}$, our derived _generalized
spectral graph partitioning problem_ , associated with the GDE of all the
cluster-related decision functions, that we expressed earlier as
$\mathcal{D}_{\nu_{(t,\gamma)}^{\alpha}\\!,\mathbf{P}}^{2}(\boldsymbol{V})$,
is:

$\min_{\mathbf{U}}\
\textnormal{tr}(\mathbf{U}^{{\mkern-1.5mu\mathsf{T}}}\mathbf{L}_{t,\gamma}^{(\alpha)}\mathbf{U})\quad\textnormal{s.t}.\>\mathbf{U}^{{\mkern-1.5mu\mathsf{T}}}\mathbf{U}=\mathbf{I}_{k}.$
(18)

Simply put, the GSC algorithm employs the same optimization procedure (see
Alg. 1) as the classical spectral clustering. The novelty is that we rely on a
generalized graph Laplacian $\mathbf{L}_{t,\gamma}^{(\alpha)}$ and compute its
eigenvectors $\mathbf{U}_{t,\gamma}^{(\alpha)}\in\mathbb{R}^{N\times k}$.
Letting the random walk iteration (time) parameter vary, provides a set of
eigenmaps $\\{\mathbf{U}_{t,\gamma}^{(\alpha)}\\}_{t=1}^{t_{\max}}$, for each
of which we obtain a suggested graph $k$-partition using $k$-means. The
different partitions can be compared according to suitable quality metrics to
select the best one. It is also possible to obtain partitions of the same
quality, which means there exists a subset of generalized Laplacian whose
embeddings produce similar graph partitions results.

Algorithm 1 Generalized Spectral Clustering (GSC)

Input: $\mathbf{W}$: weighted adjacency matrix; $k$: number of clusters,
xxxxxx$\gamma$: the uniform mixing parameter (see Eq. (16));
xxxxxx$\alpha$: power (see Eq. (15)); $t_{\max}$: maximum number of power
xxxxxxiterations (representing time) to perform over the transition
xxxxxxmatrix of the natural random walk.
Output: $\\{\boldsymbol{V}^{(\alpha)}_{t,\gamma}\\}_{t=1}^{t_{\max}}$: the
graph $k$-partition for each time $t$.

1: for $t=0$ to $t_{\max}$ do

2: Compute the generalized Laplacian $\mathbf{L}_{t,\gamma}^{(\alpha)}$, see
Eq. (8).

3: Compute $\mathbf{U}_{t,\gamma}^{(\alpha)}\in\mathbb{R}^{N\times k}$ whose
columns are the eigenvectors corresponding to the $k$ smallest eigenvalues of
$\mathbf{L}_{t,\gamma}^{(\alpha)}$.

4: Consider each $x_{i}\in\mathbb{R}^{k}$, $i=1,...,N$, to be the embedding of
the $i$-th vertex, represented by the $i$-th row of
$\mathbf{U}_{t,\gamma}^{(\alpha)}$, and apply a clustering method ($k$-means)
to all these vectors.

5: Obtain the $k$-partition
$\boldsymbol{V}^{(\alpha)}_{t,\gamma}=\big{\\{}V_{j,t,\gamma}^{(\alpha)}\big{\\}}_{j=1}^{k}$
of the graph vertices based on the clustering result of Step 4.

6: end for

7: return $\\{\boldsymbol{V}^{(\alpha)}_{t,\gamma}\\}$, for all
$t\in[0,...,t_{\max}]$.

##  5 Discussion

###  5.1 Misconception about the use of teleporting random walk for non-
strongly connected digraphs

A frequently encountered misconception about how to deal with non-strongly
connected digraphs in graph machine learning tasks, such as spectral
clustering (Zhou et al., 2005) or node classification (Peach et al., 2020),
concerns the use of the teleporting random walk (Page et al., 1999). This
particular type of random walk is ergodic, however it is used as a substitute
for the natural random walk that is generally non-ergodic in the digraph
setting. In this sense, we realize that the teleporting random walk has been
seen mainly as a trick to overcome non-ergodicity and be consistent with the
standard ergodic theoretical framework.

Nevertheless, the use of the teleporting random walk as a direct proxy for the
natural random walk may potentially bring disadvantages. Firstly, introducing
teleportation, from any vertex to any other vertex, is equivalent to mixing
with an unweighted complete graph. Consequently, this may modify drastically
the graph topology and cause non-local perturbations to the random walk
dynamics. Secondly, teleportation imposes ergodicity despite that may not be
the case for the natural random walk on a given graph. Hence, the conclusions
drawn when using this approach may be questionable (Schaub et al., 2019).

In our framework, we rather propose to incorporate teleportation as a
regularizing measure of the GDE (see the involvement of
$\tilde{\mathbf{P}}_{\\!\\!\gamma}$ in Eq. (15)) without changing the
structure of the random walk itself (see that Eq. (18) minimizes
$\mathcal{D}_{\nu_{(t,\gamma)}^{\alpha}\\!,\mathbf{P}}^{2}(\boldsymbol{V})$
that still depends on the original $\mathbf{P}$).

###  5.2 Why using measure regularized graph operators: the special case of
unbalanced data

To explain why our generalized graph Laplacian operator can be instrumental to
improve the performance of vanilla spectral clustering (VSC), we consider a
toy model where the latter might fail depending on how unbalanced and
separable the data classes are, whereas a reasonably tuned regularized
operator will be successful.

We first analyze a mathematical caricature of a $K$-NN graph representing two
clusters, and we then provide a simple experimental validation on a toy
dataset. For simplicity, we consider an undirected graph (since the underlying
stationary measure is explicit there and leads to easy explicit computations),
but the argument could be generalized for directed graphs. Here, we use as
regularizing measure a simplified version of our proposal:
$\nu(x)=\pi(x)^{\alpha}$, where $\pi$ is the stationary measure proportional
to vertex degrees.

######  Proposition 5.1.

Consider a two-cluster graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ of
$|\mathcal{V}|=N$ vertices whose ground truth is indicated by the sets
$V_{1}^{*}$ and $V_{2}^{*}$ with cardinality $|V_{1}^{*}|=N_{1}^{*}$ and
$|V_{2}^{*}|=N_{2}^{*}$, respectively, such that $V_{1}^{*}\cup
V_{2}^{*}=\mathcal{V},V_{1}^{*}\cap V_{2}^{*}=\emptyset$. Given a set
$V\subset\mathcal{V}$, we define the internal frontier set of $V$ as

$\partial^{-}\mathcal{(}V)=\\{x\in
V:\exists\,y\in\bar{V}\,\textnormal{s.t}\,(x,y)\in\mathcal{E}\\}.$

Let $N_{1}=N_{1}^{*}-\big{|}\partial^{-}\mathcal{(}V_{1}^{*})\big{|}$ and
$N_{2}=N_{2}^{*}-\big{|}\partial^{-}\mathcal{(}V_{2}^{*})\big{|}$ be
respectively the interior points of $V_{1}^{*}$ and $V_{2}^{*}$. There is a
frontier of $c_{N}=c\,\omega_{N}$ points, such that
$N_{1}^{*}+N_{2}^{*}+c_{N}=N$. Assume further that the number of neighbors are
constant, equal to $\epsilon_{N}$ inside the clusters, and equal to
$\rho\,\epsilon_{N},\,\rho<1$, along the frontier (this amounts to a
separability assumption). We also assume that cutting inside the clusters
leads to a frontier of order $\omega_{N}$ points. In the case where this
latter is fulfilled, this leads to consider the subsets $V_{1}$ and $V_{2}$
with respectively $N_{1}$ and $N_{2}$ interior points such that
$N_{1}+N_{2}+\omega_{N}=N$. Simple computations lead to the following
property.

Assume ${\frac{\omega_{N}}{N}}\to 0$, ${\frac{N_{1}^{*}}{N}}\to b$,
$\frac{N_{2}^{*}}{N}\to 1-b$.

Then if $c>b$, there exists a non empty set $V\subset V_{2}^{*}$ such that:

$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}})>\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}}).$

On the other hand, if $\alpha>\frac{\log(b/c)}{\log(\rho)}$, then for all
$V\subset V_{2}^{*}$

$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}})<\
\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}}).$

We have hence shown that unbalanced data can reveal the inefficiency of the
usual VSC, and that this can be corrected by a sufficient regularization of
the measure. In Sec. 6.1 we validate this finding empirically using a relevant
toy dataset.

Note that there are prior works motivating the operator regularization (Qin &
Rohe, 2013; Amini et al., 2013; Zhang & Rohe, 2018), but they concern mainly
the stochastic block model and not specifically the problem of unbalanced
datasets. What we intended to stress in this subsection is that our
theoretical GDE-based framework offers a new viewpoint to see and analyze such
difficult data aspects.

(a) Ground truth

(b) $k$-means result

(c) VSC result

(d) GSC result

(e)
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\\!\alpha}\\!\\!,\\!\mathbf{P}}\\!(\\!\chi_{\raisebox{-0.73497pt}{\scalebox{0.6}{$V^{*}_{\\!1}$}}}\\!\\!)\textnormal{\,-vs-\,}\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\\!\alpha}\\!\\!,\\!\mathbf{P}}\\!(\\!\chi_{\raisebox{-0.73497pt}{\scalebox{0.6}{$V^{*}_{\\!1}\\!\cup\\!V$}}})$

Figure 1: Comparison of VSC and GSC on an easy synthetic toy dataset with
unbalanced classes. (a) Ground truth; (b) clustering result from $k$-means;
(c) VCS result; (d) the result of the proposed GSC; (e) comparison of the
quantity
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-0.94496pt}{\scalebox{0.6}{$V_{1}^{*}$}}})$
and
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-0.94496pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}}).$

##  6 Experiments

General setup. The experimental study concentrates on directed graphs
naturally arising when processing point clouds. We consider input data of the
form $X=\\{x_{i}\\}_{i=1}^{N}$, $\forall x_{i}\in\mathbb{R}^{d}$. Graph
construction is a core phase of the graph partitioning pipeline and can affect
the whole process. Based on $X$ and pairwise point instances, we need to
construct a generally sparse graph that is the first step towards representing
the data. There are several options for this step, with different levels of
sophistication and complexity. For instance, one could consider the simple yet
natural approach of truncating a distance measure to create edges only for
points that are sufficiently close to each other, e.g. via a $K$-NN or
$\varepsilon$-graph. Alternatively, one could also employ parametrized kernels
(e.g. an RBF) to create a similarity matrix.

Since the main focus of this work is on determining the right graph Laplacian
operator, we rather choose a simple graph construction approach. We construct
an unweighted directed $K$-NN graph that is represented by its non-symmetric
adjacency matrix $\mathbf{W}=\\{w_{ij}\\}_{i,j=1}^{N}$, with entries:

$w_{ij}=\mathds{1}\left\\{\frac{|x_{i}-x_{j}|^{2}}{\text{dist}_{K}(x_{i})^{2}}\leq
1\right\\}.$ (19)

In the above, $x_{i}\in\mathbb{R}^{d}$ represents the original coordinates of
the data point corresponding to the $i$-th vertex, $\text{dist}_{K}(x)$ is the
distance between $x$ and its $K$-th-NN, and
$\mathds{1}\\{\,\cdot\,\\}\in\\{0,1\\}$ is the indicator function that
evaluates the truth of the input condition. We always fix
$K=\lceil\log(N)\rceil$, which makes the constructed graphs relatively sparse
and not strongly connected.

###  6.1 Demonstration on a synthetic toy dataset

We first demonstrate empirically the insights discussed in Sec. 5.2. We
generate a point could $X=\\{x_{i}\\}_{i=1}^{N}$, $\forall
x_{i}\in\mathbb{R}^{2}$, of $N=330$ data points drawn independently for two
classes using two Gaussian distributions of different centers and same unit
variance: $V^{*}_{1}:x_{i1},x_{i2}\sim\mathcal{N}(-2,1)$ or
$V^{*}_{2}:x_{i1},x_{i2}\sim\mathcal{N}(2,1)$.

Let $N_{1}=30$ and $N_{2}=300$ be the number of points drawn from $V^{*}_{1}$
and $V^{*}_{2}$, respectively. Here $K=\lceil\log(N)\rceil=6$. Exclusively for
this case, we symmetrize the adjacency matrix $\mathbf{W}$ with
$\tilde{\mathbf{W}}=\frac{1}{2}(\mathbf{W}+\mathbf{W}^{{\mkern-1.5mu\mathsf{T}}})$,
in order to meet the conditions of the setting described in Sec. 5.2. Recall
that
$\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}}\in\\{0,1\\}^{N}$ is
the decision function deciding which vertices belong to the first cluster
$V^{*}_{1}$. Let us set respectively $\alpha_{\textnormal{th}}$ and
$\alpha_{\textnormal{xp}}$ the theoretical and experimental exponent $\alpha$
we are looking to determine.

Fig. 1(a) shows the ground truth data classes. Fig. 1(b) shows the clustering
result of the data obtained with $k$-means, which makes only one mistake w.r.t
the ground truth and confirms that this is an easy scenario. Fig. 1(c) shows
the clustering result obtained by VSC. We refer to the clusters obtained by
VSC as sets $V_{1}$ and $V_{2}$, respectively. As we can observe,
$V_{1}=V_{1}^{*}\cup V$ where $V\subset V_{2}^{*}$. Consequently, let us
define $\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup V$}}}$ the
decision function for the vertices belonging to $V_{1}$. Finally, Fig. 1(d)
shows the clustering result obtained by GSC based on the generalized Laplacian
$\mathbf{L}(\pi^{\alpha})$ (see Eq. (8)). As observed, VSC fails completely to
find the correct partition. On the other end, GSC recovers the same partition
as the results from $k$-means applied directly to the data. To put this result
in perspective to the toy model of Sec. 5.2, we compute the necessary
parameters to get $\alpha$. For ${b=\frac{N_{1}}{N}\approx{0.08}},\rho\approx
0.75,c\approx 0.29$, we obtain $\alpha_{\textnormal{th}}\approx 4.5$. In order
to validate $\alpha_{\textnormal{th}}$, we introduce Fig. 1(e) that compares
the values of the generalized normalized Dirichlet energies
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}})$
and
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}})$ associated respectively of the decision functions
$\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}}$ and
$\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup V$}}}$ for
increasing values of $\alpha$ (x-axis). We note that for $\alpha<2.5$,
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}})>\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}})$. From the spectral clustering perspective, this means to choosing
between the sets ${V_{1}^{*}}$ and ${V_{1}^{*}\cup V}$ which minimizes the
normalized Dirichlet energy, i.e.
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}})$. When $\alpha>2.5$,
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}})<\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}\\!,\mathbf{P}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}})$ which is the equivalent of choosing ${V_{1}^{*}}$. Consequently,
$\alpha_{\textnormal{xp}}\approx 2.5<\alpha_{\textnormal{th}}$. We are able
thus to recover a partition close to $V_{1}^{*}$, and this is what we achieve
with GSC in Fig. 1(d).

###  6.2 Results on benchmark datasets

This section reports the results of experiments we conducted to evaluate the
performance of the proposed GSC method on $11$ benchmark datasets from the UCI
repository (Dheeru & Karra Taniskidou, 2017). We use three variants of the GSC
method. The first one, denoted by $\textnormal{GSC}_{1}(\gamma=1,\alpha,t)$ is
associated with the GDE defined in Eq. (17) with $\alpha\in[0,\infty),t\geq 0$
and $\gamma=1$. The second one, denoted by
$\textnormal{GSC}_{2}(\gamma,\alpha,t)$ is also associated with the same GDE,
but uses with $\alpha\in[0,\infty),t\geq 0$ and $\gamma\in[0,1)$. The third
one, denoted by $\textnormal{GSC}_{3}(\gamma,\alpha,t)$ is the normalized
version of $\textnormal{GSC}_{2}(\gamma,\alpha,t)$ obtained thanks to Eq. (9).

GSC and all the competitors we mention below follow the spectral clustering
setting but use the eigenvectors of different graph operators to finally apply
$k$-means clustering (we report the best score out of $100$ restarts). To
ensure fair evaluations, we select for each method the optimal parameter
values, obtained through cross-validation over a grid search, yielding the
closest partition to the ground truth. The grid used for each parameter of GSC
is: $\alpha\in\\{0,0.1,...,1\\}$, $t\in\\{0,1,...,100\\}$, and
$\gamma\in\\{0,0.05,...,0.95\\}$.

Competitors. We compare against the following methods:
$\bullet$ $\textnormal{DSC}\\!+\\!(\gamma)$ (Zhou et al., 2005; Palmer &
Zheng, 2020) spectral clustering on strongly connected digraphs. To extend
this method to the graphs used in our experiments, we employ the teleporting
random walk (Page et al., 1999) defined in Eq. (16) endowed with the parameter
$\gamma\in[0,1)$. We use the same cross-validation for $\gamma$ as what
mentioned earlier for GSC.
$\bullet$ $\textnormal{DI-SIM}_{\textnormal{L}}(\tau)$ and $\textnormal{DI-
SIM}_{\textnormal{R}}(\tau)$ (Rohe et al., 2016) are two variants that are
based on the left and the right singular vectors, respectively, of a given
regularized and normalized operator whose regularization is denoted by the
parameter $\tau\geq 0$. We use cross-validation to search the optimal
parameter with a grid search over $\tau\in\\{1,2,...,20\\}$.
$\bullet$ $\textnormal{SC-SYM}_{1}$ and $\textnormal{SC-SYM}_{2}$, two
variants of the vanilla spectral clustering (Von Luxburg, 2007) based on the
unnormalized and the normalized graph Laplacian obtained from the
symmetrization of the adjacency matrix $\mathbf{W}$, respectively.

Table 1: Clustering performance (NMI) on UCI datasets with optimal parameters
in brackets.

Dataset $N$ $d$ $k$ $\textnormal{SC-SYM}_{1}$ $\textnormal{SC-SYM}_{2}$
$\textnormal{DI-SIM}_{\textnormal{L}}$ $\textnormal{DI-SIM}_{\textnormal{R}}$
$\textnormal{DSC}\\!+\\!(\gamma)$
$\textnormal{GSC}_{1}(\gamma\\!=\\!1,\alpha,t)$
$\textnormal{GSC}_{2}(\gamma,\alpha,t)$
$\textnormal{GSC}_{3}(\gamma,\alpha,t)$ Iris 150 3 4 80.58 80.58 74.98 (1)
66.57 (1) 68.63 (0.80) 90.11 (0.9,4) 90.11 (0.95,0.7,20) 90.11 (0.95,0.7,3)
Glass 214 9 6 38.59 38.92 38.95 (1) 36.41 (1) 39.72 (0.80) 45.73 (0.1,42)
45.96 (0.95,1,14) 38.56 (0.85, 0.1,73) Wine 178 13 3 86.33 86.33 83.66 (1)
85.62 (1) 91.09 (0.80) 86.33 (0.1,1) 86.33 (0.95,0.1,53) 91.09 (0.95,0.8,2)
WBDC 569 30 2 67.73 69.47 68.54 (2) 53.43 (1) 61.12 (0.10) 72.02 (1,5) 73.24
(0.95,0.8,3) 71.45 (0.95,0.3,8) Control Chart 600 60 6 81.17 81.17 82.94 (1)
77.72 (1) 79.45 (0.90) 85.62 (0.1,90) 82.79 (0.95,0.3,65) 82.82 (0.90,0.7,96)
Parkinson 185 22 2 21.96 19.13 28.89 (1) 27.36 (13) 25.82 (0.95) 32.65
(0.2,19) 36.08 (0.95,0.4,10) 31.93 (0.95,0.1,23) Vertebral 310 6 3 39.26 39.26
52.06 (2) 41.76 (2) 56.63 (0.80) 64.26 (1,5) 59.37 (0.95,1,1) 51.50
(0.85,1,15) Breast Tissue 106 9 6 54.03 54.43 54.04 (2) 49.33 (2) 51.64 (0.20)
56.66 (0.1,40) 58.64 (0.95,1,56) 56.40 (0.95,0.6,88) Seeds 210 7 3 73.90 73.90
76.29 (1) 73.06 (1) 74.80 (0.80) 80.10 (1,4) 80.10 (0.95,0.9,4) 80.10
(0.95,0.9,4) Image Seg. 2310 19 7 67.06 67.41 67.42 (1) 64.77 (1) 31.83 (0.99)
73.40 (0.2,50) 68.11 (0.95,1,64) 68.05 (0.95,0.1,56) Yeast 1484 8 10 30.58
31.11 31.37 (2) 28.89 (1) 27.50 (0.90) 37.46 (0.5,9) 35.59 (0.95,1,40) 31.70
(0.95,0.4,67) Average – – – 58.29 58.34 59.92 54.77 56.37 65.85 65.12 63.06

Table 2: Clustering performance (NMI) on UCI datasets with optimal parameters
in brackets using Calinski-Harabasz index.

Dataset $N$ $d$ $k$ $\textnormal{SC-SYM}_{1}$ $\textnormal{SC-SYM}_{2}$
$\textnormal{DI-SIM}_{\textnormal{L}}(\tau)$ $\textnormal{DI-
SIM}_{\textnormal{R}}(\tau)$ $\textnormal{DSC}\\!+\\!(\gamma)$
$\textnormal{GSC}_{1}(\gamma=1,\alpha,t)$ Iris 150 3 4 80.58 80.58 74.98 (1)
68.57 (1) 68.63 (0.85) 83.66 (0.2,31) Glass 214 9 6 38.59 38.92 37,39 (2)
35.87 (1) 36.58 (0.85) 43.15 (0.1,38) Wine 178 13 3 86.33 86.33 83.66 (1)
82.02 (1) 63.16 (0.85) 86.33 (0.1,28) WBDC 569 30 2 67.73 69.47 64.77 (1)
53.43 (1) 61.12 (0.10) 69.47 (0.1,46) Control Chart 600 60 6 81.17 81.17 82.94
(2) 77.44 (1) 79.45 (0.90) 85.62 (0.4,17) Parkinson 185 22 2 21.96 19.13 28.89
(2) 27.36 (13) 22.97 (0.30) 31.10 (0.1,45) Vertebral 310 6 3 39.26 39.26 45.89
(1) 39.62 (1) 54.24 (0.80) 51.83 (0.2,34) Breast Tissue 106 9 6 54.03 54.43
54.04 (2) 49.27 (1) 51.64 (0.20) 55.16 (0.1,24) Seeds 210 7 3 73.90 73.90
76.26 (1) 73.06 (1) 74.80 (0.80) 77.44 (0.8,2) Image Seg. 2310 19 7 67.06
67.41 67.42 (1) 64.77 (1) 31.46 (0.99) 69.60 (0.1,73) Yeast 1484 8 10 30.58
31.11 31.22 (1) 28.89 (1) 27.47 (0.90) 32.16 (0.2,2) Average – – – 58.29 58.34
58.86 54.57 51.95 62.32

Results. The obtained partitions are first evaluated by the normalized mutual
information (NMI) (Strehl & Ghosh, 2002) and the adjusted Rand index (ARI)
(Hubert & Arabie, 1985). Both are supervised cluster evaluation measures that
make use of the ground truth labels of the data. Also for both, larger values
are better. Tab. 1 summarizes the comparative results based on NMI, while the
ARI results are provided in the Appendix. In nearly all cases, we observe that
the proposed $\textnormal{GSC}_{1}$, $\textnormal{GSC}_{2}$ and
$\textnormal{GSC}_{3}$ outperform significantly the other methods and
$\textnormal{GSC}_{1}$ gives the best result in average. Our approach performs
much better than $\textnormal{SC-SYM}_{1}$ and $\textnormal{SC-SYM}_{2}$, or
VSC on the symmetric version of the directed $K$-NN graph. This allows us to
state that our GSC associated with the GDE of Eq. (17), defined with respect
to the vertex measure of Eq. (15), brings indeed real added value in the
spectral clustering problem. It also allows obtaining better graph embeddings.

The case related to the WINE dataset is interesting to analyze. The highest
NMI score is achieved by $\textnormal{DSC}\\!+\\!(\gamma)$, which outperforms
$\textnormal{GSC}_{1}$. Nevertheless, we remark that $\textnormal{GSC}_{3}$
also achieves the highest NMI score on this dataset. This indicates that using
the teleporting random walk as a regularizing measure is beneficial even
without affecting the graph topology, unlike what
$\textnormal{DSC}\\!+\\!(\gamma)$ does. Moreover,
$\textnormal{DSC}\\!+\\!(\gamma)$ gives on average results below the
symmetrized version, which suggests that $\textnormal{DSC}\\!+\\!(\gamma)$ can
also indeed deteriorate the spectral clustering performance by considering the
teleportation random walk instead of the natural one.

To further validate the efficiency of GSC, we also evaluated our framework
without using the ground truth labels as an input. For this setting, we
restrict the comparison of the proposed methods to $\textnormal{GSC}_{1}$.
Since our framework constructs a list of graph partitions, we use the
Calinski-Harabasz (CH) (Caliński & Harabasz, 1974) as a measure of the quality
of a partition of a dataset corresponding to the normalized ratio between the
overall inter-cluster variance and the overall intra-cluster variance. We
estimate the parameters $\alpha$ and $t$ that maximize the CH index, to select
a solution among all the obtained partitions. The results of the comparison
are shown in Tab. 2. As noticed, $\textnormal{GSC}_{1}$ outperforms
significantly the other methods in nearly all cases, and on average
outperforms significantly the other methods. Compared to the unsupervised
evaluation reported in Tab. 1, here the NMI of $\textnormal{GSC}_{1}$ stays
lower by few percent. This indicates that the fully unsupervised version
offers us comparable graph partition qualities to the case where we have the
ground truth.

##  7 Conclusion

We have proposed the _generalized spectral clustering_ (GSC) framework that
applies to both directed and undirected graphs. First, we introduced the
_generalized Dirichlet energy_ (GDE) associated with an arbitrary positive
edge measure, as an extension of the classical Dirichlet energy for graph
functions. Through the GDE formulation, we have proposed generalized Laplacian
operators on graphs associated with an arbitrary positive vertex measure. We
then provided a random walk interpretation of the GDE essential to our
framework. Our proposal comes with an algorithm for our framework, where the
vertex measure corresponds to the iterated powers of the natural random walk
on the graph. We demonstrated theoretically that our framework is efficient in
the unbalanced setting. Finally, numerical results showed that the GSC
approach outperforms existing approaches for directed graphs on several
datasets.

##  8 Acknowledgment

Harry Sevi and Argyris Kalogeratos were funded by the Industrial Analytics and
Machine Learning (IdAML) Chair hosted at ENS Paris-Saclay, University Paris-
Saclay. Matthieu Jonckheere was funded by the International Centre for
Mathematics and Computer Science (CIMI) in Toulouse.

## References

  * Amini et al. (2013) Amini, A. A., Chen, A., Bickel, P. J., and Levina, E.  Pseudo-likelihood methods for community detection in large sparse networks.  _Annals of Statistics_ , 41(4):2097–2122, 2013\.
  * Boedihardjo et al. (2021) Boedihardjo, M., Deng, S., and Strohmer, T.  A performance guarantee for spectral clustering.  _SIAM Journal on Mathematics of Data Science_ , 3(1):369–387, 2021.
  * Brémaud (2013) Brémaud, P.  _Markov chains: Gibbs fields, Monte Carlo simulation, and queues_ , volume 31.  Springer Science & Business Media, 2013.
  * Caliński & Harabasz (1974) Caliński, T. and Harabasz, J.  A dendrite method for cluster analysis.  _Communications in Statistics-theory and Methods_ , 3(1):1–27, 1974.
  * Chung (2005) Chung, F.  Laplacians and the cheeger inequality for directed graphs.  _Annals of Combinatorics_ , 9(1):1–19, 2005.
  * Cucuringu et al. (2020) Cucuringu, M., Li, H., Sun, H., and Zanetti, L.  Hermitian matrices for clustering directed graphs: insights and applications.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 983–992, 2020.
  * Dheeru & Karra Taniskidou (2017) Dheeru, D. and Karra Taniskidou, E.  UCI repository of machine learning databases.  _University of California, Irvine, School of Information and Computer Sciences_ , 2017.
  * Hubert & Arabie (1985) Hubert, L. and Arabie, P.  Comparing partitions.  _Journal of Classification_ , 2(1):193–218, 1985\.
  * Laenen & Sun (2020) Laenen, S. and Sun, H.  Higher-order spectral clustering of directed graphs.  _preprint arXiv:2011.05080_ , 2020.
  * Levin & Peres (2017) Levin, D. A. and Peres, Y.  _Markov chains and mixing times_ , volume 107.  American Mathematical Society, 2017.
  * Meilă & Pentney (2007) Meilă, M. and Pentney, W.  Clustering by weighted cuts in directed graphs.  In _Proceedings of the SIAM international Conference on Data Mining_ , pp. 135–144, 2007.
  * Meilă & Shi (2001) Meilă, M. and Shi, J.  A random walks view of spectral segmentation.  In _International Workshop on Artificial Intelligence and Statistics_ , pp. 203–208, 2001.
  * Montenegro et al. (2006) Montenegro, R., Tetali, P., et al.  Mathematical aspects of mixing times in markov chains.  _Foundations and Trends® in Theoretical Computer Science_ , 1(3):237–354, 2006.
  * Ng et al. (2002) Ng, A. Y., Jordan, M. I., and Weiss, Y.  On spectral clustering: Analysis and an algorithm.  In _Advances in Neural Information Processing Systems_ , pp. 849–856, 2002.
  * Page et al. (1999) Page, L., Brin, S., Motwani, R., and Winograd, T.  The pagerank citation ranking: Bringing order to the web.  Technical report, Stanford InfoLab, 1999.
  * Palmer & Zheng (2020) Palmer, W. R. and Zheng, T.  Spectral clustering for directed networks.  In _International Conference on Complex Networks and Their Applications_ , pp. 87–99. Springer, 2020.
  * Peach et al. (2020) Peach, R. L., Arnaudon, A., and Barahona, M.  Semi-supervised classification on graphs using explicit diffusion dynamics.  _Foundations of Data Science_ , 2(1):19–33, 2020\.
  * Peng et al. (2015) Peng, R., Sun, H., and Zanetti, L.  Partitioning well-clustered graphs: Spectral clustering works!  In _Conference on Learning Theory_ , pp. 1423–1455. PMLR, 2015\.
  * Qin & Rohe (2013) Qin, T. and Rohe, K.  Regularized spectral clustering under the degree-corrected stochastic blockmodel.  _preprint arXiv:1309.4111_ , 2013.
  * Rohe et al. (2016) Rohe, K., Qin, T., and Yu, B.  Co-clustering directed graphs to discover asymmetries and directional communities.  _Proceedings of the National Academy of Sciences_ , 113(45):12679–12684, 2016.
  * Saloff-Coste (1997) Saloff-Coste, L.  Lectures on finite markov chains.  In _Lectures on Probability Teory and Statistics_ , pp. 301–413. Springer, 1997.
  * Satuluri & Parthasarathy (2011) Satuluri, V. and Parthasarathy, S.  Symmetrizations for clustering directed graphs.  In _Proceedings of the International Conference on Extending Database Technology_ , pp. 343–354, 2011.
  * Schaub et al. (2019) Schaub, M. T., Delvenne, J.-C., Lambiotte, R., and Barahona, M.  Multiscale dynamical embeddings of complex networks.  _Physical Review E_ , 99(6):062308, 2019.
  * Sevi et al. (2018) Sevi, H., Rilling, G., and Borgnat, P.  Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets.  _preprint arXiv:1811.11636_ , 2018.
  * Shi & Malik (2000) Shi, J. and Malik, J.  Normalized cuts and image segmentation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 22(8):888–905, 2000.
  * Sinclair (1992) Sinclair, A.  Improved bounds for mixing rates of markov chains and multicommodity flow.  _Combinatorics, probability and Computing_ , 1(4):351–370, 1992.
  * Strehl & Ghosh (2002) Strehl, A. and Ghosh, J.  Cluster ensembles—a knowledge reuse framework for combining multiple partitions.  _Journal of Machine Learning Research_ , 3(Dec):583–617, 2002.
  * Von Luxburg (2007) Von Luxburg, U.  A tutorial on spectral clustering.  _Statistics and computing_ , 17(4):395–416, 2007\.
  * Zhang & Rohe (2018) Zhang, Y. and Rohe, K.  Understanding regularized spectral clustering via graph conductance.  _preprint arXiv:1806.01468_ , 2018.
  * Zhou et al. (2005) Zhou, D., Huang, J., and Schölkopf, B.  Learning from labeled and unlabeled data on a directed graph.  In _Proceedings of the International Conference on Machine learning_ , pp. 1036–1043, 2005.

##  Appendix A Technical proofs

See 3.1

###### Proof.

$\displaystyle\mathcal{D}_{\nu,\mathbf{P}}^{2}(f)$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)|f(x)-f(y)|^{2}$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)|f(x)|^{2}+\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)|f(y)|^{2}-2\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)|f(x)||f(y)|$
$\displaystyle=\langle{f},\mathbf{N}{f}\rangle+\langle{f},\boldsymbol{\Xi}{f}\rangle-\langle{f},(\mathbf{NP}+\mathbf{P}^{{\mkern-1.5mu\mathsf{T}}}\mathbf{N}){f}\rangle$
$\displaystyle=\langle{f},\big{(}\mathbf{N}+\boldsymbol{\Xi}-(\mathbf{NP}+\mathbf{P}^{{\mkern-1.5mu\mathsf{T}}}\mathbf{N})\big{)}{f}\rangle$
$\displaystyle=\langle{f},\mathbf{\big{(}I-(I+N^{-1}\Xi)^{-1}(P+N^{-1}P^{{\mkern-1.5mu\mathsf{T}}}N)\big{)}}{f}\rangle_{\nu+\xi}$
$\displaystyle=\langle{f},\mathbf{L}_{\textnormal{RW}}(\nu){f}\rangle_{\nu+\xi}.$

∎

See 4.1

###### Proof.

$\displaystyle q(S,\bar{S})$ $\displaystyle=\sum_{x\in
S,y\in\bar{S}}\nu(x)p(x,y)$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$\bar{S}$}}}(y)$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)(1-\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y))$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)-\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)$
$\displaystyle\Rightarrow\ q(S,\bar{S})$
$\displaystyle=\sum_{x\in\mathcal{V}}\nu(x)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)-\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)$
(20)

$\displaystyle q(\bar{S},S)$
$\displaystyle=\sum_{x\in\bar{S},y\in{S}}\nu(x)p(x,y)$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$\bar{S}$}}}(x)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)(1-\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x))\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)-\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)$
$\displaystyle\Rightarrow\ q(\bar{S},S)$
$\displaystyle=\sum_{y\in\mathcal{V}}\bigg{(}\sum_{x\in\mathcal{V}}\nu(x)p(x,y)\bigg{)}\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)-\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)$
(21)

$\displaystyle\mathcal{D}_{\nu,\mathbf{P}}^{2}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}})$
$\displaystyle=\sum_{(x,y)\in\mathcal{E}}\nu(x)p(x,y)|\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)-\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)|^{2}.$
$\displaystyle=\sum_{x\in\mathcal{V}}\nu(x)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)+\sum_{y\in\mathcal{V}}\bigg{(}\sum_{x\in\mathcal{V}}\nu(x)p(x,y)\bigg{)}\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)-2\sum_{x,y\in\mathcal{V}}\nu(x)p(x,y)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(x)\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$S$}}}(y)$
$\displaystyle\Rightarrow\eqref{eq:qssbar}+\eqref{eq:qsbarss}$

∎

See 3.2

###### Proof.

$\mathbf{P}$ admits the eigen-decomposition
$\mathbf{P}=\sum_{j=1}^{N}\lambda_{j}\phi_{j}\psi_{j}^{*}$ with
$1=|\lambda_{1}|>|\lambda_{2}|\geq|\lambda_{3}|\geq...\geq|\lambda_{N-1}|\geq-1$.
Let $\mu$ be a positive vertex measure such that
$\langle\mu,\phi_{1}\rangle=1$. The Dirichlet energy of a graph function $f$
with respect to the measure $\nu_{(t)}$ (see Eq. (10)) has the following
expression:

$\mathcal{D}_{\nu_{t}\\!,\mathbf{P}}^{2}(f)=\mathcal{D}_{\pi,\mathbf{P}}^{2}(f)+\langle{f},\mathbf{E}_{t}{f}\rangle=\langle{f},\big{(}\mathbf{L}(\pi)+\mathbf{E}_{t}\big{)}{f}\rangle,$

where

$\displaystyle\mathbf{E}_{t}$ $\displaystyle=\sum_{j\geq
2}c_{j,t}(\mu)\mathbf{Z}_{j},$ $\displaystyle\mathbf{L}(\pi)$
$\displaystyle=\boldsymbol{\Pi}-\frac{1}{2}(\boldsymbol{\Pi}\mathbf{P}+\mathbf{P}^{{\mkern-1.5mu\mathsf{T}}}\boldsymbol{\Pi}),$
$\displaystyle\mathbf{Z}_{j}$
$\displaystyle=\boldsymbol{\Psi}_{j}-\frac{1}{1+\lambda_{j}}(\boldsymbol{\Psi}_{j}\mathbf{P}+\mathbf{P}^{{\mkern-1.5mu\mathsf{T}}}\boldsymbol{\Psi}_{j})$
$\displaystyle\boldsymbol{\Psi}_{j}$
$\displaystyle=\operatorname{diag}(\psi_{j})$ $\displaystyle c_{j,t}(\mu)$
$\displaystyle=(1+\lambda_{j})\hat{\vartheta}_{j,t}(\mu)$
$\displaystyle\hat{\vartheta}_{j,t}(\mu)$
$\displaystyle=\langle\mu,\phi_{j}\rangle\lambda_{j}^{t}.$

$\displaystyle\nu_{t}(x)$
$\displaystyle=\mu^{{\mkern-1.5mu\mathsf{T}}}{\mathbf{P}}^{t}{\delta}_{x}$
$\displaystyle=\mu^{{\mkern-1.5mu\mathsf{T}}}\bigg{(}\sum_{j=1}^{N}\lambda_{j}^{t}\phi_{j}\psi_{j}^{*}\bigg{)}{\delta}_{x}$
$\displaystyle=\mu^{{\mkern-1.5mu\mathsf{T}}}\bigg{(}\phi_{1}\pi^{{\mkern-1.5mu\mathsf{T}}}+\sum_{j\geq
2}^{N}\lambda_{j}^{t}\phi_{j}\psi_{j}^{*}\bigg{)}{\delta}_{x}$
$\displaystyle=\langle\mu,\phi_{1}\rangle\pi(x)+\sum_{j\geq
2}^{N}\lambda_{j}^{t}\langle\phi_{j},\mu\rangle\psi_{j}(x)$
$\displaystyle\nu_{t}(x)$ $\displaystyle=\pi(x)+\sum_{j\geq
2}^{N}\lambda_{j}^{t}\langle\phi_{j},\mu\rangle\psi_{j}(x)$ (22)

Remplacing the explicit form of $\nu_{t}(x)$ from Eq. (22) in
$\mathcal{D}_{\nu_{t}\\!,\mathbf{P}}^{2}(f)$ yields :

$\displaystyle\mathcal{D}_{\nu_{t}\\!,\mathbf{P}}^{2}(f)$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\nu(x,t)p(x,y)|f(x)-f(y)|^{2},$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\bigg{(}\pi(x)+\sum_{j\geq
2}^{N}\lambda_{j}^{t}\langle\phi_{j},\mu\rangle\psi_{j}(x)\bigg{)}p(x,y)|f(x)-f(y)|^{2},$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\pi(x)p(x,y)|f(x)-f(y)|^{2}+\sum_{j\geq
2}^{N}\lambda_{j}^{t}\langle\phi_{j},\mu\rangle\bigg{(}\sum_{x,y\in\mathcal{V}}\psi_{j}(x)p(x,y)|f(x)-f(y)|^{2}\bigg{)},$
$\displaystyle\mathcal{D}_{\nu_{t}\\!,\mathbf{P}}^{2}(f)$
$\displaystyle=\mathcal{D}_{\pi,\mathbf{P}}^{2}(f)+\sum_{j\geq
2}^{N}\hat{\vartheta}_{j,t}(\mu)\mathcal{D}_{\psi_{j},\mathbf{P}}^{2}(f).$
(23) $\displaystyle\mathcal{D}_{\psi_{j},\mathbf{P}}^{2}(f)$
$\displaystyle=\sum_{x,y\in\mathcal{V}}\psi_{j}(x)p(x,y)|f(x)-f(y)|^{2}$ (24)
$\displaystyle=\sum_{x,y\in\mathcal{V}}\psi_{j}(x)p(x,y)|f(x)|^{2}+\sum_{x,y\in\mathcal{V}}\psi_{j}(x)p(x,y)|f(y)|^{2}-2\sum_{x,y\in\mathcal{V}}\psi_{j}(x)p(x,y)|f(x)||f(y)|$
$\displaystyle=\sum_{x\in\mathcal{V}}\psi_{j}(x)|f(x)|^{2}+\lambda_{j}\sum_{y\in\mathcal{V}}\psi_{j}(x)|f(y)|^{2}-2\sum_{x,y\in\mathcal{V}}\psi_{j}(x)p(x,y)|f(x)||f(y)|$
$\displaystyle=(1+\lambda_{j})\sum_{x\in\mathcal{V}}\psi_{j}(x)|f(x)|^{2}-2\sum_{x,y\in\mathcal{V}}\psi_{j}(x)p(x,y)|f(x)||f(y)|$
$\displaystyle=(1+\lambda_{j})\langle
f,\bigg{(}\boldsymbol{\Psi}_{j}-\frac{1}{(1+\lambda_{j})}(\boldsymbol{\Psi}_{j}\mathbf{P}+\mathbf{P}^{{\mkern-1.5mu\mathsf{T}}}\boldsymbol{\Psi}_{j})\bigg{)}f\rangle,$
$\displaystyle\mathcal{D}_{\psi_{j},\mathbf{P}}^{2}(f)$
$\displaystyle=(1+\lambda_{j})\langle f,\mathbf{Z}_{j}f\rangle.$ (25)

By putting Eq. (25) into Eq. (26), it yields

$\displaystyle\mathcal{D}_{\nu_{t}\\!,\mathbf{P}}^{2}(f)$
$\displaystyle=\mathcal{D}_{\pi,\mathbf{P}}^{2}(f)+\sum_{j\geq
2}^{N}\hat{\vartheta}_{j,t}(\mu)\mathcal{D}_{\psi_{j},\mathbf{P}}^{2}(f)$ (26)
$\displaystyle=\mathcal{D}_{\pi,\mathbf{P}}^{2}(f)+\sum_{j\geq
2}^{N}\hat{\vartheta}_{j,t}(\mu)(1+\lambda_{j})\langle
f,\mathbf{Z}_{j}f\rangle,$
$\displaystyle=\mathcal{D}_{\pi,\mathbf{P}}^{2}(f)+\sum_{j\geq
2}^{N}c_{j,t}(\mu)\langle f,\mathbf{Z}_{j}f\rangle$
$\displaystyle\mathcal{D}_{\nu_{t}\\!,\mathbf{P}}^{2}({f})$
$\displaystyle=\mathcal{D}_{\pi,\mathbf{P}}^{2}(f)+\langle{f},\mathbf{E}_{t}{f}\rangle.$
(27)

At $t\to\infty$, we have

$\lim_{t\to\infty}\mathbf{E}_{t}=0.$

Consequently, we have

$\lim_{t\to\infty}\mathcal{D}_{\nu_{t}\\!,\mathbf{P}}^{2}(f)=\mathcal{D}_{\pi,\mathbf{P}}^{2}(f).$

Therefore, this result indicates that the GDE of a graph function $f$,
associated with the transition matrix $\mathbf{P}$ and under a parametrized
measure $\nu_{t}\\!$, is the sum of a quadratic form involving the usual
unnormalized Laplacian $\mathbf{L}(\pi)$ and an operator $\mathbf{E}_{t}$ that
tends to $0$ as $t\to\infty$. ∎

See 5.1

###### Proof.

Given the assumption on our toy model graph:

$\displaystyle\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}})$
$\displaystyle=\frac{{c_{N}(\rho\epsilon_{N})^{\alpha}}}{N_{1}\epsilon_{N}^{\alpha}+o(N_{1}\epsilon_{N}^{\alpha})}=\frac{\omega_{N}}{N}{c\frac{\rho^{\alpha}}{a}}+o\Big{(}\frac{\omega_{N}}{N}\Big{)}.$
(28)

Now, with $V=F\cup H$, where $H\in V_{2}^{*}$ and $|V_{1}^{*}\cup
V|=\tilde{a}N+o(N)$:

$\displaystyle\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}})$
$\displaystyle={\frac{\omega_{N}(\epsilon_{N})^{\alpha}}{N\tilde{a}\epsilon_{N}^{\alpha}+o(N\epsilon_{N}^{\alpha})}}={\frac{\omega_{N}}{N}}{\frac{1}{\tilde{a}}}+o\Big{(}{\frac{\omega_{N}}{N}}\Big{)}.$
(29)

Hence if $c\rho>b$,
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}})<\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}})$
for some $V$, whereas if $c\rho^{\alpha}<b$,
$\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}\cup
V$}}})>\overline{\mathcal{D}^{2}}_{\\!\\!\\!\\!\\!\pi^{\alpha}}(\chi_{\raisebox{-1.04996pt}{\scalebox{0.6}{$V_{1}^{*}$}}})$,
$\forall V$. ∎

##  Appendix B Additional experimental results

Table 3: Clustering performance (ARI) on UCI datasets.

Dataset $N$ $d$ $k$ $\textnormal{SC-SYM}_{1}$ $\textnormal{SC-SYM}_{2}$
$\textnormal{DI-SIM}_{\textnormal{L}}$ $\textnormal{DI-SIM}_{\textnormal{R}}$
$\textnormal{DSC}\\!+\\!(\gamma)$ $\textnormal{GSC}_{1}(\gamma=1,\alpha,t)$
$\textnormal{GSC}_{2}(\gamma,\alpha,t)$
$\textnormal{GSC}_{3}(\gamma,\alpha,t)$ Iris 150 3 4 75.92 75.92 69.41(1)
58.44 (1) 52.96 (0.80) 92.22 (0.9,4) 92.22 (0.95,0.7,20) 92.22 (0.95,0.7,3)
Glass 214 9 6 23.12 24.80 22.05 (1) 18.89 (1) 20.93 (0.80) 28.00 (0.1,42)
28.01 (0.95,0.9,22) 26.85 (0.85,0.7,52) Wine 178 13 3 87.82 87.82 84.98 (1)
89.74 (1) 92.95 (0.80) 87.82 (0.1,1) 87.92 (0.95,0.1,53) 92.95 (0.95,0.8,2)
WBDC 569 30 2 76.69 77.30 77.95 (2) 57.75 (1) 64.58 (0.30) 80.48 (1,4) 81.12
(0.95,0.8,3) 78.56 (0.95,0.3,8) Control 600 60 6 62.25 62.25 66.79 (1) 59.83
(1) 60.04 (0.90) 71.91 (0.1,90) 64.77 (0.95,0.3,65) 64.78 (0.90.0.7,96)
Parkinson 185 22 2 35.42 32.91 28.90 (1) 24.82 (1) 24.82 (0.95) 42.26 (1,3)
43.73 (0.95,4,10) 40.28 (0.95,0.2, 60) Vertebral 310 6 3 29.70 29.70 38.85 (2)
31.03 (2) 54.64 (0.80) 63.14 (1,5) 58.40 (0.95,1,1) 38.56 (0.85,1,9) Breast
Tissue 106 9 6 36.96 38.41 41.94 (2) 30.60 (2) 21.76 (0.90) 41.01 (0.1,40)
38.02 (0.95,0.6,77) 44.69 (0.95,0.4,96) Seeds 210 7 3 78.46 78.46 81.09 (1)
74.41 (1) 77.64 (0.80) 83.52 (1,5) 83.52 (0.95,0.9,4) 83.52 (0.95,0.9,4) Image
Seg. 2310 19 7 47.83 51.75 50.83 (1) 36.54 (1) 08.89 (0.99) 52.15 (0.2,50)
61.17 (0.95,1,78) 55.81 (0.95,0.4,41) Yeast 1484 8 10 19.41 21.17 19.97 (2)
19.49 (2) 16.62 (0.90) 28.48 (0.5,9) 26.85 (0.95,0.9,93) 21.78 (0.95,0.4,19)
Average – – – 52.14 52.77 52.98 45.59 48.70 59.95 60.52 58.18