Clustering for directed graphs using parametrized random walk diffusion kernels
Authors: Harry Sevi
Matthieu Jonckheere
Argyris Kalogeratos
Venue: Submitted to ICLR 2023 (2023)
Keywords: clustering
diffusion geometry
parametrized random walks
directed graphs

Abstract: Clustering based on the random walk operator has been proven effective for undirected graphs, but its generalization to directed graphs (digraphs) is much more challenging. Although the random walk operator is well-defined for digraphs, in most cases such graphs are not strongly connected, and hence the associated random walks are not irreducible, which is a crucial property for clustering that exists naturally in the undirected setting. To remedy this, the usual workaround is to either naively symmetrize the adjacency matrix or to replace the natural random walk operator by the teleporting random walk operator, but this can lead to the loss of valuable information carried by edge directionality. In this paper, we introduce a new clustering framework,  the Parametrized Random Walk Diffusion Kernel Clustering (P-RWDKC), which is suitable for handling both directed and undirected graphs. Our framework is based on the diffusion geometry and the generalized spectral clustering framework. Accordingly, we propose an algorithm that automatically reveals the cluster structure at a given scale, by considering the random walk dynamics associated with a parametrized kernel operator, and by estimating its critical diffusion time. Experiments on $K$-NN graphs constructed from real-world datasets and real-world graphs show that our clustering approach performs well in all tested cases, and outperforms existing approaches in most of them. 

Under review as a conference paper at ICLR 2023
CLUSTERING FOR DIRECTED GRAPHS
USING
PARAMETRIZED RANDOM WALK DIFFUSION KERNELS
Anonymous authors Paper under double-blind review
ABSTRACT
Clustering based on the random walk operator has been proven effective for undi- rected graphs, but its generalization to directed graphs (digraphs) is much more challenging. Although the random walk operator is well-defined for digraphs, in most cases such digraphs are not strongly connected, and hence the associated random walks exists naturally in the undirected setting. To remedy this, the usual workaround is to either naively symmetrize the adjacency matrix or to replace the natural ran- dom walk operator by the Pagerank random walk operator, but this can lead to the loss of valuable information carried by the graph directionality and edge den- sity. In this paper, we introduce new clustering framework, the Parametrized Random Walk Diffission Kernel Clustering (P-RWDKC), which is suitable for handling both directed and undirected graphs. P-RWDKC is based on the dif- fusion geometry (Coifiman & Lafon 2006) and the generalized spectral clustering framework (Sevi et al.) 2022). Accordingly,
irreducible, which is a crucial property for clustering that
propose algorithm that auto- matically reveals the cluster structure at a given scale, by considering the random walk dynamics associated with a parametrized graph operator, and by estimating its critical diffusion time. Experiments on K-NN graphs constructed from real- world datasets and real-world graphs, show that most of the tested cases our clustering approach has superior performance compared to existing approaches.
INTRODUCTION
Clustering is fundamental unsupervised learning task whose aim is to analyze and reveal the clus- ter structure of unlabeled datasets, and has widespread applications in machine learning. network analysis, biology, and other fields (Kiselev et al. 2017, McFee & Ellis 2014). Clustering for data represented as a graph has been formulated in various ways. A well-establ lished one consists in min- imizing functional of the graph-cut (Von Luxburg 2007 Shi & Malik 2000p, leading to the spec- tral clustering (SC) framework and various algorithms. SC IS simple and effective, but has important limitations (Nalerr & Galun 2006) that make it unreliable in number of non-rare data regimes. Overcoming these limitations is where the focus of the machine learning community is (Tremblay
al. 2016 Zhang & Rohe 2018 Dall' Amico al. 2021 Sevi et al. 2022).
A well-studied clustering approach for high-dimensional data, which is of particular interest for this work, is using the operator associated with a random walk (or, in other terms, with Markov chain), called random walk operator. MMila & Shij (200T) viewed the pairwise similarities between datapoints as edge flows of a Markov chain and proposed an ergodic random walk interpretation of the spectral clustering. However, and beyond SC. the first to conceive the idea of turning the distance matrix between high-dimensional data into Markov process were Tishby Slonim (2000). More specifically, they proposed to examine the decay of mutual information during the relaxation of the Markov process. During the relaxation procedure, the clusters emerge as quasi-stable structures, and then they get extracted using the information bottleneck method (Tishby et al. 2000). Azran & Ghahramani (2006) proposed to estimate the number of data clusters by estimating the diffusion time of the random walk operator that reveals the most significant cluster structure. Lin & Cohen (2010) proposed then to find a fow-dimensional embedding of the data using the truncated power iteration of random walk operator derived from the pairwise similarity matrix.

---

Under review as a conference paper at ICLR 2023
Clustering high- dimenssonaii data using a random walk operator through the lens of the diffusion geometry (Coifman & Lafon 2006; Coifman et al.] (0055 has also been investigated. Nadler et al.) (2006) proposed unifying probabilistic diffusion framework based on the probabilistic interpreta- tion of SC and dimensionality reduction algorithms using the eigenvectors of the normalized graph Laplacian. Given the pairwise similarity matrix built from high-dimensional data points, they de- fined a distance function between any two points based on the random walk on the graph called the diffusion distance (Coifmmn & Lafon 2006; Pons & Latapy 2005) and showed that the low- dimensional representation of the data by the first few eigenvectors of the corresponding random walk operator is optimal under a certain criterion. Recently, an unsupervised clustering methodol- ogy has been proposed based on the diffusion geometry framework (Maggioni & Murphy [019] MMurphy& & Polk] 2022), where it has been demonstrated how the diffusion time of the random walk operator can be exploited to successfully cluster datasets for which k-means, spectral clustering, or density-based clustering methods fail.
Although there has been a constant development of clustering approaches which are based on the random walk operator, all such efforts (like those mentioned above) have been proposed for undi- rected graphs. Moreover, the motivation of most of them is to run forward the random walk to avoid the costly eigendecomposition of the graph Laplacian. The extension of clustering approaches based on the random walk operator digraphs is much more subtle and challenging. As presented earlier, random walk-based clustering approaches rely either on the eigenvectors of the random walk oper- ator or on its iterated powers. In the directed setting, the random walk is well-defined, but is not reversible in general like in the undirected case (Levin & Peres 2017). Consequently, the associated eigenvectors are possibly complex, which makes their interpretation and use difficult in the context of clustering. A possible workaround would be to consider the approach based on the iterated pow- ers of the random walk operator which would allow one to obtain a real-valued embedding and thus avoid the use of complex eigenvectors.
However, second much more subtle and problematic bottleneck arises: the random walk's irre- ducibility. While in the undirected case, the random walk is irreducible, i.e. any graph vertex can be reached from any other vertex, this is not the case in general for random walks on digraphs. To overcome the irreducibility issue, either symmetrization procedure is usually employed in the case where the digraph is derived by a KNNN graph construction or the original random walk operator is replaced by the operator of the Pagerank teleporting random walk (Page et al. 1999). For these two workarounds, valuable information can potentially be discarded. To address this problem, we present new clustering algorithm based on the diffusion geometry framework, which is suitable for any digraph, either obtained by K-NN constructions or by real digraphs representing asymmet- ric relationships between vertices (c.g. citation graphs). Our approach stems from a new type of graph Laplacians (Sevi et al. 2022) that is parametrized by an arbitrary vertex measure, capable of encoding digraph information, and from which we derive a random walk operator. Besides, we can exploit the necessary diffusion time of this parametrized random walk to successfully reveal clusters at different scales.
This work is part of the main line of work on edge density-based clustering on digraphs that seeks clusters characterized by high intra-cluster and low inter-cluster edge densities, and has produced several methods in the last two decades /hhou et al.] (2005): Meilå & Pentney (2007) : /atuluri &
Parthasarathy 2011)) ; Rohe ct al. 2016); Palmer & Zheng (2020): Sevi et al. (2022] Klus & Djurd-
jevac Conrad 2023 Lately, there have been proposed approaches Cucuringu et al. 2020) : Laenen
& Sun (2020 : Coste & Stephan (021): Hayashi et al. (2022). which are called flow-based and
whose objective is opposite to the traditional density- based graph clustering fieitp.int.
The contribution of this work is manifold: i) We propose a new similarity kernel operator, which term random walk diffusion kernel (RWDK), that derives directly from the original definition of the diffusion distance, This latter allows us to theoretically justify the use of the random walk operator as fundamental graph operator for clustering. ii) We generalize this kernel by proposing the use of a parametrized random walk operator, which allows us to extend the diffusion distance to digraphs. iii) From there, we present our clustering algorithm on digraphs, the parametrized random walk diffusion kernel clustering, based on the parametrized RWDK operator considered as a data embedding. iv) We propose a general method for estimating the diffusion time that best reveals a given number of clusters. Finally, we show that our approach is efficient on both synthetic and real-world datasets, as it outperforms existing methods most of the tested cases.
2

---

Under review as a conference paper at ICLR 2023
2 BACKGROUND
Graph theory and graph functions. Let G = (V, E, w) be a weighted directed graph (digraph), where V is the finite set of N = |/ vertices, and & [ V V is the finite set of edges. Each edge (1, is an ordered vertex pair indicating the direction of a link from vertex to vertex j. With little abuse of notation
sometimes use E V implying vertex index E [1,.,,N The edge weight function w : :V x V + 1 associates a nonnegative real value to every vertex pair: w(i,)) > O, iff (i,5) E E, otherwise w(i, j) O. A digraph & is represented by weighted adjacency matrix W = [w(i,j)) E XXN, where w(i.j) is the weight of the edge (i,j). We define the out- degree and the in-degree of the i-th vertex by dout, = Σラ= w(i,j) and dm,t Σj= w(j. i), respectively. Also, the function D2 diag(v)
square diagonal matrix with the elements of the input vector y in its diagonal. Consider a graph function f mapping all of its vertices to an N- dimensional vector: f = [f( Miey RR.. We assume that graph functions are defined in e (V, v), which is the Hilbert space of functions, defined over the vertex set V/ of G, endowed with the inner product associated with an arbitrary positive measure v. Let ö, E {0. 1] N be the vector output of the Kronecker delta function at E V. Any function v : V + R2, associating nonnegative value to each graph vertex, can be regarded as positive vertex measure.
Random walk fundamentals. What we call in short a random walk on a weighted graph G, is defined more formally as a natural random walk on the graph, which a homogeneous Markov chain X' = (X+)120 with a finite state space V, and with state transition probabilities proportional to the edge weights. The entries of the transition matrix P = [p(i, Jvi,ev are defined by:
w(i.j)
p(i.j) = P(X++1 = xj i) = ExEV w(i,
Algebraically, the transition matrix P E R can be expressed as P D W. D our D don (respectively, Din = Da, Jwhose spectrum sp(P) E [-1, 1]. For a strongly connected digraph G. the random walk X' is irreducible. If, in addition, the irreducible random walk X' admits the aperiodicity condition, then X' is ergodic, and therefore as t + oc, the probability measures Pr *) o P for all V. converge toward unique stationary distribution denoted by the row vector R. (Brémaud 2013). A random walk X' with stationary distribution π and transition matrix P is called reversible if ())
out
7 (j)p(i,,)) i), for all i,j E V. Within the undirected setting: dout, dm, d, where II-N11 is the vector of the vertex degrees, also and D = diag(d) is a square diagonal matrix with the elements of the input vector d in its diagonal. Moreover, the stationary distribution proportional the vertex degree distribution, i.e. π x d.
Parametrized graph Laplacians. A notable example of parametrized operators that we use later, the generalized graph Laplacian from (Svi et al. (2022). which a new type of graph operators for (but not restricted to) digraphs. Relevant theoretical background is provided in Appendix 1.44I
Definition 2.1. Generalized graph Laplacians (Sevi et al. 2022). Lei P be the transition matrix of random walk a digraph G. Under arbilrary positive verlex measure on G, consider the positive vertex measure & = PP. Let also the diagonal matrices D,, = diag(v). Dg = diag(E) and Du+s diag(v + E). Then, can define three generalized Laplacians of G as follows:
generalized random walk Laplacian:
LRw,(v) (v) = (D.+e)) 'DD D2)
(1)
unnormalized generalized Laplacian:
L(v) = Duts - (D,P+P'D.)
(2)
normalized generalized Laplacian:
((v)= = D -11221 (,,("L(0)DD111
D,1/2 -1/2
V+c
Lgw,(w). L(y and ((y) are parametrized by an arbitrary vertex measure has the modeling capacity to encode the graph directionality and edge density using the random walk dynamics of the original digraph. When the transition matrix P is irreducible and the vertex measure is the ergodic measure o, they correspond to the directed graph Laplacians in Chung (2055)
3 PARAMETRIZED RANDOM WALK OPERATOR ON GRAPHS
In this section, we introduce the parametrized random walk operator that we propose, and we show how it is derived from the generalized graph Laplacian (presented at the end of Sec. 2
3

---

Under review as a conference paper at ICLR 2023
Definition 3.1. Parametrized random walk operator (P-RW). Let P be the transition matrix of random walk on a digraph G. Under an arbitrary positive vertex measure v on G, consider the positive vertex measure & = P. Let also the diagonal matrices D, diag(v), D diag(E) and D diag(v + .). Finally, let Xy be the random walk on G with the associated random walk operator (transition matrix) (v) defined by:
P (w)) (Du+e) (D,P++
It is easy to verify that P(v)) is transition matrix (see Appendix A.1.2 and that there is the following relation with generalized random walk Laplacian.
Definition 3.2. Relation between (vw and (()) Let P be the transition matrix of random walk on a digraph G. Under an arbitrary positive vertex measure v on G. The generalized random walk Laplacian and the parametrized random walk on G are related as follows:
Lgw,(v) P
As stated in Sevi et al. 2022), the generalized random walk Laplacian, LRw.(v) (v): is self-adjoint in (V C). Consequently, the generalized random walk ((v) is also self-adjoint in (V,, v-+E), and the associated random walk X, is ergodic (under the aperiodicity condition) and admits the ergodic distribution Te. Therefore, ((v) is a random walk operator parameterized by a vertex measure that encodes the random walk dynamic of the original digraph.
4 DIFFUSION GEOMETRY FOR DIGRAPHS
In this section, we review the concept of diffusion geometry (Coifman & Lafon 2006). and we show: i) how its core feature, the diffusion distance, be expressed as a Mahalanobis distance involving a specific kernel matrix, which we call Random Walk Diffusion Kernel (RWDK); ii) how the SC's diagonalization step can be thought of as a function applied to the spectrum of the Laplacian and the conceptual connection with the RWDK, and iii) accordingly clustering algorithm.
4.1 THE DIFFUSION DISTANCE AS A MAHALANOBIS DISTANCE
The seminal work by (Coifmaan & Lafon 2006) introduced the diffusion geometry framework, which uses diffusion processes as basic tool to find meaningful geometric descriptions for dataset. The framework can provide different geometric representations of the dataset by iterating the Markov transition matrix, which is equivalent to running forward the random walk. The key element of the diffusion geometry the diffusion distance (Coifman & Lafon 2006 Pons & Latapy 2005) defined as follows. We provide relevant theoretical background in Appendix A.4.2
Definition 4.1. Diffusion distance. Let P be the transition matrix of a reversible random walk on undirected graph G, with ergodic distribution
Let also [| (f, D,D'" f), with
D diag(T), be the e-norm of a graph function f induced by the measure /. The diffusion distance at time N between the vertices and j is defined by:
d( I|p.(i, +) peli, )]3
(5)
As noted [Coifman Lafon 2006), the diffusion distance emphasizes the cluster structure, present. Next, we show that the diffusion distance can be seen Mahalanobis distance.
Proposition 4.1. Diffusion distance as a Mahalanobis distance. Let be the transition matrix of reversible random walk on undirected graph G. with an ergodic distribution The diffusion distance (i, between vertices and j. at a given time E N, can be expressed as the following Mahalanobis distance:
((ii = (5, 5,) K,, -6),
where the similarity positive definite kernel matrix K2 is defined by:
K - =
The diffusion distance reveals similarity kernel matrix K, that call Random Walk Diffusion Kernel (RWDK), which is simply a power of the transition matrix normalized by the vertex degrees. Consequently, using the diffusion distance d? is equivalent using the RWDK matrix K,,
4

---

Under review as a conference paper at ICLR 2023
4.2 RANDOM WALK DIFFUSION KERNEL, NORMALIZED GRAPH LAPLACIAN AND SPECTRAL CLUSTERING
Spectral clustering (SC) is one of the most widely used clustering methods due its simplicity,
efficiency, and strong theoretical foundation (Shi & Malik 2000; Ng et al.] 2002 Von Luxburg, 2007 Peng et al. 2015 Boedihardjo et al. 2021). Given a fixed number of clusters k, SC consists of three main steps: 1) construct the graph Laplacian matrix; ii) compute the eigenvectors associated with the i smallest eigenvectors of the Laplacian matrix and store them as columns in a matrix; iii) apply k-means on the rows of the latter matrix, which are regarded as embedded representations of the datapoints. We aim to highlight how the SC's second step and the RWDK do have similar characteristics. Let us consider the normalized graph Laplacian matrix L (Chung & Graham| 1997)
with eigendecooppsiiion L = E}= " d ordered eigenvalues 0 S 01 S ..- ON 2 and eigenvectors { Computing the eigenvectors associated to the & smallest eigenvalues of L amounts to applying a function fi on the spectrum matrix of & such that f1 = 1 if x S OR. and (x) 0 otherwise, namely H = (C) Σラ= 0. Thanks to the relation L selecting the & smallest eigenvalues of L is thus equivalent to selecting the k largest eigenvalues of P. namely H f1(C) D fi (I - PJD 2. On the other hand, the RWDK K, corresponds to applying a function f2(2,, t) = 2t on the spectrum matrix of P. As t - co, As É increases, (2(P
f2 + .1', and consequently K, = (2 1)D + jir(D)) becomes smoother because f2 acts as a soft truncation of the spectrum matrix of P, which preserves those eigenvectors of P that associated with the largest eigenvalues. However, as increases, fi acts as a hard truncation of the spectrum matrix of L. which preserves the & eigenvectors associated with the lowest ones up 9g. Consequently, the RWDK K, is an adaptive alternative H, and the aim is to determine the iteration time that best reveals the l: clusters the user looks for.
4.3 PARAMETRIZED RANDOM WALK KERNEL CLUSTERING
We have shown that the diffusion distance oi is directly related to the RWDK and that for a given diffusion time f, the RWDK is an alternative to computing the eigenvectors of the graph Laplacian. However, the original diffusion distance defined in Eq. was settled in the undirected setting w.r.t a transition matrix associated with a reversible random walk. For an arbitrary transition matrix P and an arbitrary measure 14, the diffusion distance between vertices and j. at a given diffusion time f, is indeed defined as the weighted Euclidean distance between the rows of P df j. = [p, (i,+) - Pe(j, ))(2,
(6: - 5,) (t,))) - 6z). We have established the last expression in Sec it suggests that one can see the diffusion distance
Mahalanobis distance involving
similarity kernel ((t,.) = P'D',,P')) with Dj = diag(u).
By breaking down this way diK = DD' (see Eq. 6 P needs to be the transition matrix of a reversible random walk with stationary measure æ, and the vertex measure needs to be f = 1/n. This is the reason why the original diffusion distance formulation was only used in the undirected setting. Now, the advantage of the parametrized random walk operator we use, is that it is also reversible transition matrix for digraphs, and hence enables naturally the extension of the diffusion distance for digraphs.
Definition 4.2. Parametrized diffusson distance. Let X be a random walk on digraph G, with transition matrix P. Let v be an arbitrary positive vertex measure on G. and & be the vertex measure defined by & = vT TPP Define the diagonal matrices D, = diag(v) and D diag(E). On G, let N, be a random walk associated with the random walk operator (w) parametrized by an arbitrary measure v defined in Eq. and ergodic measure T.. Let (t, = 6, (.P)t,, be the conditional probability vector given the vertex i at the diffusion time I. The parametrized diffassion distance between the vertices i and j. at a given diffasion time I, is defined by:
de., = Ilpt, x) (t, *) x)] (ō. - T,)TK (c.))(8: - -5))
with K (t,,)) is the parametrized random walk diffusion kernel (P-RWDK) defined as:
((,,)) =P P V+E
(8)
Finally, the normalized generalized Laplacian Liv) and the parametrized random walk operator P(v) related in the same manner the normalized Laplacian relates to the random walk operator (see
5

---

Under review as a conference paper at ICLR 2023
Algorithm Parametrized Random Walk Diffusion Kernel Clustering (P-RWDKC)
Input: W < RN*A; adjacency matrix, k: number of clusters, D: vertex measure, lg: diffusion time
Output: Vizi graph d-partition for diffusion time tu
1: Compute the parametrized random walk operator P..). sec Eq.
2: Compute the parametrized random walk diffusion kernel K (ta.e)) see Eq. 8
3: Consider each 2; E _= = I,....y N. to be the embeddling of the i-th vertex. represented by the i-th row
of K ()a,o), and apply clustering method (e.g. k-means) all these vectors asking for & clusters
4: Obtain the k-partition Vi_= {Via]
of the graph vertices based on clustering result Step 3
5: return Via
See 4.2 and therefore we can write: (v) D - (()) u+f Consequently, the same 24
1/2
approach of Sec is also valid in this setting. Once we have defined the parameterized diffusion distance df (t..). we are in position to present the novel parametrized random walk diffusion kernel clustering (P-RWDKC) for both undirected and directed graphs (Alg. which is based the parametrized RWDK (t,2).
5 THE P-RWDKC METHOD IN PRACTICE
In the previous section, described novel and simple clustering algorithm for digraphs based on an operator that is parametrized by an arbitrary vertex measure v, and a its diffusion up to time To render our algorithm more flexible for practical use, two important aspects points need to be addressed: i) the design of the vertex measure ii) the estimation of the diffusion time.
5.1 DESIGNING THE VERTEX MEASURE
Designing the vertex measure is of the major aspects of P-RWDKC as aim to capture with the random walk dynamics of the original digraph in our parametrized random walk operator. To do so, we propose vertex measure derived from the iterated powers of random walk consisting of the forward and backward digraph's 's flow information. Specifically, the proposed vertex measure can be parametrized by three parameters E,, 7 [0, 1), a E and is formally given by:
Ve (t) (1v 1 Pxo6,,)
where 1 Nx1 is the all-ones vector, recall that 8; {0, Nx is the vector returned by the Kronecker delta function at i E V, and
P, = P + Pin
(10)
where Pin = D D---- WT and Poun =
oul W (recall that D Dan,. and Din DD,,).
The three parameters have easy-to-see role, and their use optional
set them values that neutralize their effect (i.e. t = 1, a = 1, 7 = 0.5). The random walk iteration parameter t controls the diffusion time, 7 controls the mixing between Pour (forward information) and Pin (backward information), and a controls the re-weighting of the vertex measure, Plugging ((,)) to Eq. 4 yields the following expression for the parametrized random walk P ((R..)) and hence the P-RWDK ((taraa.,)) Note that in our implementation, use P, (I P.)P instead of P,,.
The choice of the vertex measure can have a significant influence on the clustering performance. Intuitively, one would be interested to see how "concentrated" are the measure's 's configurations that lead to good clusterings. When the problem easy seell-separated clusters), the influence of the vertex measure is very limited and multiple different measure parametrizations may lead to good clustering (and many different algorithms may do the same). On the other hand, in difficult cases (clusters that are intricate and/or imbalanced and/or sparse) the vertex measure will be key to reach- ing high clustering performance, and maybe more "concentrated" in region of good parametriza- tions in R-N. We can also see the impact of the measure by considering that vanilla SC can perform arbitrarily badly. This has been partially studied theoretically in Sevi et al. (002 and also shown empirically in experimental results in Sec.

---

Under review as a conference paper at ICLR 2023
5.2 DETERMINING THE APPROPRIATE DIFFUSION TIME IN THE UNSUPERVISED SETTING
For a known number of clusters k, we aim at determining the best diffusion time la for the P- RWDKC algorithm. As we work in an unsupervised setting, and hence lacking ground truth, de- termining the right diffusion time is challenging (Shan & Daubechies) (022). Our main insights to
deal with this matter are derived from the concepts of diffusion geometry (Coifiman & Lafon 2006),
the theory of nearly uncoupled Markov chains (Tifenbach] 2011: Sharpe & Wales 2021) and the
metastability of Markov chains (Landim Xu 2015).
As stated in (Coifman & Lafon 2006), assuming that the graph has clusters and/or a multi-scale structure, the random walk diffusion reveals clusters at key moments of the diffusion at the course of time. The emergence of clusters can be understood through the prism of metastability theory: for given cluster structure, there is critical time-scale when an irreducible random walk becomes nearly reducible, diffusing only inside clusters. Typically, this means to observe approximatcly that, at that diffusion time, our operator enjoys high intra-cluster compactness and high inter-cluster separation. Cluster validity indexes can be employed for measuring the ratio of the former to the latter of the quantities José-Gareía & Gómez- criterion (CH; also known as Variance ratio criterion) (Caliñski & Harabasz) 1974). which computes the ratio between the distance of the cluster centroids to the global centroid, and the distance of the datapoints of each cluster its cluster centroid.
2021). Here, we propose the use of the Salinski-Haraband
To compute this variance criterion, we propose two types of distances between data points, either the Euclidean distance between original data points, or a distance between their embedded rep- resentations, which in the context of this work means to consider the rows of a reference graph operator. Given the set of N datapoints X = { EN } partitioned into clusters, denoted by V = [V)) we denote by μ4 [V5] Σx.ev, æ; the centroid of cluster j. by f N Ex.ex I the centroid of X, and by d(æ;, Xi) the pairwise distance used for two datapoints Fi, B. E X. Thus, the CH criterion endowed with a given distance d is defined by:
CH(X, V) N ΣØ= [Vy] d(Hs), 14)
ンド= Exrev, E d( m4g)
In the standard case, where we consider multidimensional data vectors, X = {x1, xN E Rd the usual CH criterion endowed with the Euclidean distance d(ar,, 22y) = ||æe; - -xyl 2 is usually used. However, there are many reasons that the usual CH criterion may be either not directly applicable (c.g. when the input is only graph and no point cloud), or inefficient (e.g. when the clusters of the input point cloud are non-convex or nested, and the Euclidean distance cannot help distinguishing them). For this reason, as part of our framework, we propose extend the CH criterion for this setting, based on the Kullback-Leeie Leibler divergence as a distance Van Erven & Harremos (2014).
Definition 5.1. Probability Density-based
Hariabss- (DCH) criterion. Let G (V.8 E)
be a digraph with cardinality [V| = N. Let P be the transition matrix of a random walk on G. The digraph G is partitioned into k clusters denoted by V =\Vi) Let p(i,+) 6. P be the conditional probability vector given the vertex that we consider as the representation of the vertex i. We define as reference data representation X {pli,*) +) R Ji=1 the set of conditional prob- ability vectors associated with the vertices of G. Let denote by ft, [V,] centroid of cluster j. and μ divergence between two discrete probability distributions, p and q. is defined as Dxi q) Ey P(v) log ply) density-based Calinski-Harabasz (DCH) criterion endowed with the Kullback-Leible divergence DKL (p.q) q), defined by:
2 Epti,tev, p(i,)) the
p(i,)) the centroid of X. The Kullback-Leinn
a(u) s.t. q(y) # O. Given a set of datapoints X and a partition V, the probability
N K Σラ= |V,] DKL (Ht p))
DCH(X,V)
1: EØ=1 Epti,nev, DKL (xi(pii (1,))
We thus estimate the diffusion time in practice by evaluating the CH or DCH criterion for the parti- tions associated with the dyadic powers of the parametric random walk p? with v = 1 (the uniform measure) and j E J/} with J = 15. Since the purpose is to estimate the diffusion time, taking the vertex measure equal to a uniform measure is sufficient for this situation. We summarize this procedure in Alg. 2
7

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Estimating the random walk diffusion time 1*
Input: Reference representation X: W: adjacency matrix; k: number of clusters: J: number of iterations
Output: t": the estimated diffusion time that best reveals clusters
I: Set
for the vertex measure
Compute the parametrized random walk operator P()), see Eq.
3: for J = 0 do
4: Apply k-means on (m)
5: Obtain the k-partition V = (Vg.so==1 of the graph vertices based on the clustering result of Step 4.
6: end for
7: Select j'= argmax CH(X, V,) (or (CH((,, V.)). jE(0....J}
8: return t" 2¹
EXPERIMENTS
Setup and competitors. In this section, we demonstrate the effectiveness of our approach both on digraphs obtained from high-dimensional data through graph construction procedures, and real- world graphs. When dealing with high-dimensional data, we use the K K-nearest neighbor (K-NN) graph construction with K [log(N)J. which produces (relatively) sparse and non-strongly con- nected digraphs. A resulting K-NN graph is unweighted, directed, and represented by its non- symmetric adjacency matrix W {wi, Ji.j-1, with entries Waj 1 [1| æz 1l2 I (istx((;)) In the latter, 24, FT E RRd stand for the original coordinates of the datapoints corresponding to the vertices i and j. distx (I) is the Euclidean distance between z and its K-th nearest neighbor, and {{-e E {0, 1] is the indicator function that evaluates the truth of the input condition.
Our clustering method, denoted by P-RWDKC(a, 7, 4, (a), is endowed with the parameters 2 0, Y E [0. 1], and t, ta 2 0. The search grid used for each parameter is: a E 00.0.1..... 1}, e {0, 1, ..., 100). and y 00,0.1..... .... 1.. Finally, the diffusion time parameter tu E (20 ...., 2 with J = 15, is estimated using Alg. For each method, we apply k-means clustering over the obtained embeddings (we report the best score out of 100 restarts). We select for each method the optimal parameter values obtained through cross-validation over a grid search, yielding the closest partition the ground truth. The obtained partitions are evaluated by the normalized mutual infor- mation (NMI) Strchl & Ghosh (2002). which is a popular supervised cluster evaluation index. NMI corresponds to a normalization of the mutual information between the predicted cluster assignments and the ground truth labels. This metric is symmetric and invariant to label permutations.
In the experiments we compare with the following methods:
DSC + (7) (houu et al. 2005) is a SC method on digraphs based on the Pagerank random walk (Page et al. 1999) endowed with the parameter 7 E 1).
D (T) and DI-SIMR (r) (Rohe 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 т 0. We use cross-validation to search the optimal
parameter with a grid search over T E 21.2,.... 20..
SC-SYM, and SC-SYM, are SC variants (Von Luxburg 2007) based on the unnormalized and the normalized graph Laplacians obtained from the symmetrization of the adjacency matrix W. PIC(ta) (Lin & Cohen| 2010) is the clustering approach based on the power iteration of the random walk operator. We use the random walk operator derived from the original adjacency matrix W of the graph. The diffusion time t. is estimated using Alg. [
RSC(T) QQin & Rohe 2013 Zhang & Rohe 2018) is the regularized SC proposed to deal with sparse graphs parametrized by T 2 O. We use cross-validation with grid search over 7 E {1, 2, ..., 20} to tune this parameter. The method applies only to undirected graphs. For di- graphs, we had to symmetrize the adjacency matrix of the original digraph.
Multi-scale synthetic Gaussians. Here we test the our approach at revealing clusters at differ- ent scales thanks to the accurate estimation of the diffusion time. We generate one instance of a point cloud in 2²2 of N 300 data points drawn independently from the following mixture of six Gaussian distributions Σi= a,Viu, of I) with weights a; (note: Σ, 0; 1). Specifically,
o, = 0.5, a; = 1/6, Vi and μI = (-3, -2), H2 = (0, -2), AA = (-1, 1), μ = (4, -2), μs = (7, 22. /46 (5, 1). The resulting data exhibit multi-scale structure, they can be seen as either
8

---

Under review as a conference paper at ICLR 2023
Table I: Clustering performance (NMI) on UCI datasets with optimal parameters in parentheses.
DATASET
d
SC-SYM; SC-SYM, (1M (I-SIM)(T) DSC+(t)
PIC(ta)
P. P-RWDKC(a, 7.
IRIS
150 4
80.58
80.58
74.9% (1)
66.57 (1)
68.63 (0.80)
78.32 (32)
90.11 (0.4,1149.32)
GLASS
214
38.59
38.92
38.95
36.41
39.72 (0.80)
42.79 (128)
44.39 (
WINE
178 13
86.33
86.33
83.66 (1)
85.62 (1)
91.09 (0.80)
86.33 (4)
86.50 (0.7.0.21.32)
WBDC
569
30
67.73
69.47
68.54 (2)
53.43 (1)
61.12
64.77 (8)
73.90 (0..0)
CONTROL
81.17
82.94
79.45
(32)
(0...)))..32)
PARKINSON
185 22
21.96
19.13
28.89 (1)
(133
25.82
28.89
36.08 (1.0.3.52.2)
VERTEBRAL
310
39.26
39.26
$2.06
42)
56.63 (0.80)
(9)
62.40
(..3.088.48))
BREAST TISSUE
106
54.03
54.43
$4.04 (2)
49,33
51.64 (0.20)
$4.18 (32)
60.43 (0.5.1.39.16)
SHEDS
210
7
73.90
73,90
76.29 (1)
73.06
74,80 (0.80)
70.79 (32)
78.95
110,0.44844,8
IMAGE SEG.
2310
19
67.06
67.41
67.42 (1)
64.77 (1)
31.83 (0.99) 69.58 (2
72.19 (0.8. 2.06)56)
YEAST
1484
8
10
30.58
31.11
31.37 (2)
28.89 (1)
27.50 (0.90)
32.62 (16)
34.05
(0.7.0.6.51.16)
AVERAGE
588.22
58.34
59.92
54.77
56.37
60.01
containing the 6 original Gaussian clusters, or having 2 clusters where each of them is made up of 3 smaller clusters. Figs, [ and [I show the ground truth data classes for the two scales. Figs. and Id] show the respective clustering results obtained by P-RWDKC with vertex measure and estimated diffusion times td. 64 and tdd = 128. The results are quite consistent with the ground truth of each case, hence provide evidence that approach can reveal multi-scale clusters.
1
Real-world data. In this section, we conduct experiments on graphs created from sigh-dimessional real-world data. We show that P-RWDKC has superior performance compared to existing methods in nearly all tested cases. Note that, to further validate the efficiency of P-RWDKC, we run additional experiments several real-world graphs, which are provided in Appendix
Here we report results on 11 benchmark datasets from the UCI repository (Dheeru & Karra Taniski- dou 2017). We compare against DSC+, SC-SYM, and SC-SYM2, DI-SIM, and PIC. Tab. sum- marizes the comparative results based on NMI. In nearly all cases, the proposed P-RWDKC out- performs significantly the other methods on average. Our approach performs better than SC-SYM, and SC-SYM2. Moreover, our approach performs better on average than DSC+, This allows us to state that P-RWDKC, associated with the suitable vertex measure from Eq. 9 brings indeed real added value to the clustering problem. Furthermore, P-RWDKC outperforms PIC. Consequently, the RWDK operator produces better graph embeddings than the original random walk operator de- fined the directed K -NN graphs because the parametrized random walk is irreducible compared to the random walk used in PIC that is not and thanks to the digraph information encoded into the vertex measure. We have to mention that for each dataset, the parameters reported in approach are not necessarily unique as several combinations parameters may yield the same clustering performance (see Sec. 5.1
CONCLUSION
We have proposed the parametrized random walk diffusion kernel clustering (P-RWDKC) that ap- plies to both directed and undirected graphs. First, we introduced the parametrized random walk (P-RW) operator. We then show that the diffusion distance, is a Mahalanobis distance involving a special kernel matrix, called random walk diffusion kernel (RWDK), which is simply a power of the transition matrix (normalized by the vertex degrees). From this, we show that the RWDK is an al- ternative to the eigendecomposition step of the spectral clustering pipeline. We extend the diffusion geometry framework to digraphs by combining RWDK and P-RW. The P-RWDKC clustering algo- rithm stems from analysis. Finally, demonstrated empirically, with extensive experiments several datasets, that P-RWDKC outperforms existing approaches for digraphs.
(a) Ground truth
(b) 6 clusters result
(c) Ground truth II
(d) 2 clusters result
Figure Comparison between ground truth classes at different scales and the result P-RWDKC on synthetic toy-case. (a),() Small-scale: ground truth with 6 clusters and the P-RWDKC's result. (c),(d Large-
scale: ground truth with 2 clusters and the finding of P-RWDKC.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the International Workshop on Link discovery, pp. 36 36-43, 2005.
Arik Azran and Zoubin Ghahramani, A new approach to data driven clustering, In Proceedings of the International Conference on Machine Learning, pp. 57-64, 2006.
March Boedihardjo, Shaofeng Deng, and Thomas Strohmer, A performance guarantee for spectral clustering. SIAM Journal on Mathematics of Data Science, 311::369-387, 2021.
Aleksandar Bojchevski and Stephan Günnemann. Deep Gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. Preprint arXiv:1707.03815 2017.
Pierre Brémaud. Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31. Springer Science & Business Media, 2013.
Tadeusz Caliñski and Jerzy Harabasz. A dendrite method for cluster analysis. Communications in Statistics-theory and Methods, 3(1):1-27, 1974.
Fan Chung. Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics, (1):1-19, 2005.
Fan RK Chung and Fan Chung Graham, Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
Ronald Coifman, Stephane Lafon, Ann Lee, Mauro Maggioni, Boaz Nadler, Frederick Warner, and Steven W Zucker. Geometric diffusions tool for harmonic analysis and structure def- inition of data: Diffusion maps. Proceedings of the National Academy of Sciences, 102(21): 7426-7431, 2005.
Simon Coste and Ludovic Stephan. A simpler spectral approach for clustering directed networks. preprint arXiv:2 102.03188, 2021.
Mihai Cucuringu, Huan Li, He Sun, and Luca Zanetti. Hermitian matrices for clustering directed graphs: insights and applications. In International Conference on Artificial Intelligence and Statistics, pp. 983-992, 2020.
Lorenzo Dall' Amico, Romain Couillet, and Nicolas Tremblay, A unified framework for spectral clustering sparse graphs. Mach. Learn. Res., 22:217-1, 2021.
Lorenzo Dall' Amico, Romain Couillet, and Nicolas Tremblay. Optimal laplacian regularization for sparse spectral community detection, In IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3237-3241, 2020.
Dheeru and Karra Taniskidou. UCI repository of learnin learning databases. University of California, Irvine, School of Information and Computer Sciences, 2017.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks.
Proceedings of the National Academy of Sciences, 99(12):7811-7826 2002.
Maxim Goldberg and Seonja Kim. Some remarks on diffusion distances. Journal of Applied Mathematics, 2010, 2010.
Maxim J Goldberg and Seonja Kim. An efficient tree-based computation of metric comparable to a natural diffusion distance. Applied and Computational Harmonic Analysis, 33(2))261-281, 2012.
Koby Hayashi, Sinan G Aksoy, and Haesun Park. kymmerrmeetric adjacency matrices for clustering directed graphs. Preprint arXiv:2203.01388 2022.
10

---

Under review as a conference paper at ICLR 2023
Adán Aaré-Garcia and Wilfrido Gómez-Flores. A survey of cluster validity indices for automatic data clustering using differential evolution. In Proceedings of the Genetic and Evolutionary Com- putation Conference, pp. 31--322, 2021.
Vladimir Yu Kiselev, Kristina Kirschner, Michael T Schaub, Tallulah Andrews, Andrew Yiu, Tamir Chandra, Kedar N Natarajan, Wolf Reik, Mauricio Barahona, Anthony R Green, et al. Sc3: consensus clustering of single-cell rnasseq data. Nature methods, 14(5):883-46,, 2017.
Stefan Klus and Nataša Djurdjevac Conrad. Koopman- based spectral clustering of directed and time-evolving graphs. Journal of Nonlinear Science, 33(1):1-22) 2023.
Steinar Laenen and He Sun. Higher-order spectral clustering of directed graphs. preprint wwXiv:2011.0508/ 2020.
Claudio Landim and Tiecheng Xu. Metastability finite state Markov chains: a recursive procedure to identiff slow variables for model reduction. Preprint 151.v:152..06597,, 2015.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Society, 2017.
Frank Lin and William W Cohen. Power iteration clustering. In Proceedings of the International Conference on Machine Learning, 2010.
Mauro Maggioni and James M Murphy, Learning by unsupervised nonlinear diffusion. J. Mach. 2019.
Learn. Res.,
Brian McFee and Dan Ellis. Analyzing song structure with spectral clustering. In ISMIR, pp. 405- 410. Citeseer, 2014.
Marina Meilä and William Pentney, Clustering by weighted cuts in directed graphs. In Proceedings of the SIAM International Conference Data Mining, pp. 135-144, 2007.
Marina Meilä and Jianbo Shi. A random walks view of spectral segmentation. In International Workshop on Artificial Intelligence and Statistics, pp. 203-208, 2001.
Ravi Montenegro, Prasad Tetali, et al. Mathematical aspects of mixing times in Markov chains. Foundations and Trends@ in Theoretical Computer Science, 1(3):237-354 2006.
James M Murphy and Sam Polk. A multiscale environment for learning by diffusion. Applied and Computational Harmonic Analysis, 57:58-100 2022.
Boaz Nadler and Meirav Galun. Fundamental limitations of spectral clustering. Advances in Neural Information Processing Systems, 2006.
Boaz Nadler, Stephane Lafon, Ronald R. Coifman, and loannis G Kevrekidis. Diffusion maps, spec- tral clustering and eigenfunctions of Fokker-Planck operators. In Advances in Neural Information Processing Systems, 2006.
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems, 2002.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The Pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
William R Palmer and Tian Zheng. Spectral clustering for directed networks. In International Conference on Complex Networks and Their Applications, pp. 87-99. Springer, 2020.
Richard Peng. He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! In Conference Learning Theory, pp. 1423-1455, 2015.
Pascal Pons and Matthieu Latapy. Computing communities in large networks using random walks. In International symposium on computer and information sciences, pp. 284-293. Springer, 2005.
Tai Qin and Karl Rohe. Regularized spectral clustering under the degree-corrected stochastic block- model. preprint 130 //109 /11, 2013.
11

---

Under review as a conference paper at ICLR 2023
Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4):1878 1915, 2011.
Karl Rohe, Tai Qin, and Bin Yu. Co-clustering directed graphs to discover asymmetries and direc- tional communities. Proceedings of the National Academy of Sciences, 1679452)1 2016.
Venu Satuluri and Srinivasan Parthasarathy. Symmetrizations for clustering directed graphs. In Proceedings of the International Conference on Extending Database Technology, pp. 343-354, 2011.
Harry Sevi, Matthieu Jonckheere, and Argyris Kalogeratos. Generalized spectral clustering for directed and undirected graphs. Preprint arXiv:2203.0322. 2022.
Shan Shan and Ingrid Daubechies. Diffusion maps: Using the semigroup property for parameter tuning. Preprint arXiv:2203.022. 220.002877. 2022.
Daniel Sharpe and David Wales. Nearly reducible finite Markov chains: Theory and algorithms.
The Journal of Chemical Physics, 155(14)) 140901, 2021.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions
Pattern Analysis and Machine Intelligence, 22(8):888-90) 2000.
Alexander Strehl and Joydeep Ghosh. Cluster ensembles-a knowledge reuse framework for com-
bining multiple partitions. Journal of Machine Learning Research, 3(Dec):583-617, 2002.
Ryan M Tifenbach. A combinatorial approach to nearly uncoupled Markov chains. PhD thesis, National University of Ireland Maynooth, 2011.
Naftali Tishby and Noam Slonim. Data clustering by Markovian relaxation and the information bottleneck method. Advances in Neural Information Processing Systems, 2000.
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method.
Preprint arXiv physics/0000057, 2000.
Nicolas Tremblay, Gilles Puy, Rémi Gribonval, and Pierre Vandergheynst. Compressive spectral clustering. In Proceedings of the International Conference on Machine Learning, pp. 1002-1011, 2016.
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. Transactions Information Theory, 60(7):3797-388) 2014.
JEEE
Ulrike Von Luxburg. A tutorial spectral clustering. Statistics and Computing, 17(4):395 2007.
Wayne W Zachary. An information flow model for conflict and fission in small groups Journal of anthropological research, 33(4):552-473 1977.
Yilin Zhang and Karl Rohe. Understanding regularized spectral clustering via graph conductance. preprint 1rXiv:1806.01 2018
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning from labeled and unlabeled data on a directed graph. In Proceedings of the International Conference on Machine Learning, pp. 1036-1043, 2005.
12

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 PROOFS
A.1.1 PROOF PROPOSITION 4.1
Proposition A.1. Let X be a random walk on an undirected graph with transition matrix P and ergodic distribution The transition matrix P admits the following eigendcomposition P DD, VT. The diffusion distance between vertices i and J. de (1,j) at a given time t E can be written as the following Mahalanobis distance
(i (5)-,,) K, -5);
where the similarity positive definite kernel matrix K₁ is defined by
K: = =
(11)
Proof.
d((1,) llp((E, *) Pe x)1l
-I(PP))(8; - -6,
(1 (6; ((-),)) 'P' ( 65).
By setting K, = P'D_-'(F (P*),, using the eigendecomposition of P and the fact that P is self-adjoint in (2VV, n), we have
K, P'D, "T (P')T
&D D D DD TT
+DD T ( v = I), ( D v)
.DD n D
K, = D
A.1.2 SUPPLEMENTARY PROOFS
Proposition A.2. P(v) a transition matrix and reversible.
Proof. We have the following equality
(w)) = [I "PP
= (D, (D.PP+PD. +PD),.
As result, need to show that (D, DD,)) -DD,P + P,D,,) is transition matrix, i.e. we show that
M
Pw) ViEY
Σ
P
(w)
Σ
(D, +De) -DDD))(((,PPPP] ig
j=1
M
M
Σ
D. + De)
DD.P + DT)kk
==1
M
P P(m)aa = (D, + De)
DDPP+P'D..)
(12)
13

---

Under review as a conference paper at ICLR 2023
M
1
I M
D.P + D'D
D Da) kj
P bR (Du)aj
M
Σ D
Σ (P')
(P'), (D.),)
j=1
Σ (1)(11)) + Σ v()p(i.)
M4 Σ
DDP + D'D,,; = v(1) + E(1), ViEV
1=1
Using Eq.
12. we finally obtain Σ/= P ( =.
A.2 EXPERIMENTS ON WORLD GRAPH BENCHMARKS
Most of the real-world graphs are sparse with heterogeneous degrees with high variance of the degree. As a result, spectral clustering mostly fails for these graphs Zhang & Rohe (2018); Rohe ctt al. (20IT); Dall' Amico al. (2020), To avoid numerical issues due the high variance degree, we proposed slight modification of the parametrized random walk operator (transition matrix)
(v) (D; + D2) "D, W + DD)
(13)
with { = vT W and the vertex measure E = [",,...,NN] defined by iz D;d,!! Vi E V.
We report the results of experiments that evaluate the performance of the proposed P-RWDKC method on 4 real-world networks. Among these, 2 are directed (Political blogs, Cora) and 2 are undirected (Karate Club, College Football). For all networks, the number of clusters considered known. Moreover, when necessary, clustering is performed on the largest connected component of graph. We compare against SC-SYM, RSC, and PIC.
Tab. summarizes the comparative results according to the NMI index. In all cases, the proposed P-RWDKC outperforms the other methods, and when looking at the overall average performance the difference is significant. Our approach performs significantly better than SC-SYM,. This is caused by a mixed effect of the symmetrization of the digraph as well as the hard truncation phenomenon discussed in Sec. 4.2 RSC is competitive against our method. Nevertheless, the adjacency matrix involved in RSC is dense and clearly modified, which can have deleterious impact compared to method (e.g. see the results on Cora).
Table 2: Clustering performance (NMJ) on real-world datasets with optimal parameters in parentheses.
DATASET
SC-SYM;
RSC(r)
PIC((2)
|-RWDKK(o, 7.1,
POLITICAL BLOGS AADAICC & GLANCE
2005
1222
1.74
73:25 (0.2)
57.37 (8)
75.53 (1.
CORA BOICHEVSKI Call Ni MANN
2485
7
17.10
36.07 (2:5) 7,86 (4)
$2.03 (0.0.9.72.8)
(2.9)
(0.7.0.17.2)
KARATE CLUB (ZACHKRY 1977
34
73.24
83.72 (1.7) 83.72
83.72 (0.0.1.1)
AVERAGE
30.51
$5.96
49.23
60.65
A.3 ALTERNATIVE FOR THE DESIGN OF THE VERTEX MEASURE
In Sec. Sec.55. we presented a design for the vertex measure be used by P-RWDKC. Here we discuss an alternative design. As before, the vertex measure can be parametrized by three parameters (L N, E [0, 1], ER) and is formally given by:
(a (x11)
(14)
where x x1 is the all-ones vector, 8, 13 is the vector output of the Kronecker delta function at E V. and
Py D. W
D, diag W,
(15)
14

---

Under review as a conference paper at ICLR 2023
Table 3: Clustering performance (NMI) on UCI datasets with optimal parameters in parentheses.
DATASET
N
d
SC--SYM
SC-SYM,
DI SIM, [T)
DI (T) DSC+
PIC(
P-RWDK (d)
IRIS
150
4
3
80.58
80.58
74.98 (1)
66.57 (1)
68.63 (0.80) 78.32 (32)
90.11 (0.6.4)
GLASS
214
9
6
38.59
38.92
38.95 (1)
36.41 (1)
39.72 (0.80) 42.79 (128)
42.89 (0.5.256)
WINE
178
3
86.33
86.33
83.66
85.62 (1)
91.09 (0.80) 86.33
84.73 (0.32)
WBDC
569
2 67.73
69.47
68.54 (2)
71.72 (1)43
61.12 (0.10) 64.77 (8)
71.32 (1.2)
CONTROL CHART
600
6 81.17
81.17
82.94
79.45 (0.90)
82.79 (32)
84.22 (0.6.32)
PARKINSON
185
22
2
21.96
19.13
28.89 (1)
27.36(13)
25.82 (0.95) 28.89 (2)
36.08 (0.5,4)
VERTEBRAL
310
6
3
39.26
39.26
52.06
41.76
56.63 (0.80) 49.13
59.57 (0.1.4)
BREAST TISSUE
106
9
6
54.03
54.43
54.04 (2)
49.33 (2)
51.64 (0.20) 54.18 (32)
55.29 (0.6,16)
SEEDS
210
7
73.90
74.89
73.06
74.80
(32)
75.52
IMAGE SEG.
2310
19
7
67.06
67.41
67.42 (1)
64.77 (1)
31.83 (0.99)
69.58 (2!4)
70.70 (0.5,64)
31.11
31.37 (2)
28.89 (1)
(0.90)
(16)
(0.1.16)
AVERAGE
588.29
58.34
59.92
54.77
56.37
60.01
63.92
where W,, is defined by
W, = - ( 7 y [0.1]
(16)
The random walk iteration parameter & controls the random walk diffusion, 7 controls the influence between the original adjacency W (forward information) and its transpose W (backward informa- tion), and controls the re-weighting of the vertex measure.
A.3.1 VERTEX MEASURE WHEN 7 = 1/2 AND - 00
In the setting where, 7 = 2 and + oc, we are able to characterize explicitly the vertex measure. Indeed, W,, becomes symmetric, the associated random walk is thus ergodic, lime 6, P 1/2, Vi and the parametrized vertex measure defined in Eq. 14 becomes Vi (1) = (T1/2 for any vertex i.
A.3.2 ADDITIONAL EXPERIMENTS
In this section, we demonstrate the effectiveness of our approach based on the same setting described in Sec. 6 using the vertex measure in A.3.1 Tabs. and summarize the comparative results based on NMI. Similarly to the results from Sec. 6 we observe that the proposed P-RWDKC outper- forms significantly the other methods in nearly all cases. The P-RWDKC, associated with the vertex measure defined in Sec. A.3.I Ittyss freedom. The main takeway to consider is that the construction of this kernel and the design of the vertex measures are the key elements to creating relevant embedding for clustering graphs.
stays competitive against P-RWDKC from Sec. with less degree of
To further evaluate the P-RWDKC framework, instead of using the ground truth and cross-valiin validation, here we choose the parameter values that optimize the Salinski-Harabass (CH). We first compute the set of candidate partitions, one for each (a, t.)) combination Then we select as best the model with the highest CH and compute its NMI. We operate in the same way for the methods that have parameters (i.e. all but SC-SYM, SC-SYM,, and PIC whose results are the same as in Tabs. and 5 The comparative results are shown in Tabs labs.[andd] and 6 Notice that P-RWDK WKC outperforms significantly the other methods in nearly all cases (see also the average performance in the last row of the table.). Compared Tab. 3 here the NMI of P-RWDKC stays just a little lower. This indicates that the unsupervised tuning of the model parameters offers comparable graph partition quality to the previous case where applied cross-validatte validation using the ground truth.
the considered parameter grid.
15

---

Under review as a conference paper at ICLR 2023
Table 4: Clustering performance (NMI) UCI datasets with estimated parameters (shown in parentheses) according to the CH (or DCH) index.
DATASET
k] SC- SYM, SC-SYM,
DI (F)
(T)
DSC+(11)
PIC(ts)
P. P.RWDK(o, 4.)
TRIS
150
3
80.58
80.58
74.98 (1)
66.37 (1)
68.63 (0.80) 78.32 (32)
90.11 (0.6.4)
GLASS
214
9
6
38.59
38.92
37.39
35.87 (1)
36.58 (0.80) 42.79 (128)
42.13 (0.3.25))
WINE
178
3
86.33
86.33
83.66 (1)
85.62 (1)
91.09 (0.80) 86.33 (4)
84.73 (0. 9.32)
WBDC
569
2 67.73
69.47
68.54 (2)
53.43
64.77 (0.10
70.24 (0.5.2)
CONTROL CHART
600
60
6
81.17
81.17
82.94 (2)
(1)
79.45 (0.90) 82.79 (32)
83.19 (0. 2..2.)
PARKINSON
185
2
21.96
19.13
27.36 (1)
22.97
36.08
VERTEBRAL
310
6
3
39.26
39.26
(2)
(9)62(1)
54.24 (0.80) 49.13 (8)
59.34 (0.3.4)
BREAST TISSUE
106
54.03
54.43
54.04 (2)
49.27 (2)
51.64 (0.20)
54.18 (32)
54,90 (0.2,16)
SEEDS
210
7
3
73.90
73.90
74.89 (1)
73.06 (1)
74,80 (0.80) 70.79 (32)
74.89 (0.1.8)
7
67.06
67.41
64.77 (1)
31.46 (0.99)
(244)
(0.1,64)
YEAST
1484
8
10
30.58
31,11
31,22 (1)
28.89 (1)
27.47 (0.90)
32.62 (16)
33.60 (0,16)
AVERAGE
58.29
58.34
58.82
54.57
51.95
60.01
63.45
Table 5: Clustering performance (NMI) on real-world datasets with optimal parameters in parentheses.
SC-CCM RSC(r)
PIC(ts)
P-RWDKC(a,Ad
POLITICAL BLOGS ADAMIC & GLANCE 2005
1222
2
1.74
73.25 (0.2)
$7.37 (8) 74.02 (0.1.32)
CORA [BoJCHEVSKE GUNNEMANN 2017
2485
7
17.10
36.07 (2.5)
7.86 (4)
49.71 (0.2.16)
COLLEGE FOOTBALL (GIRAAN & NEWNAN 2002
115
12
29.97
30.79 (2.9)
29.98 (2)
30.79 (0.9.2)
KAKATE CLUB (ZACHARY
34
2
73.24
83.72 (1.7)
(1)72
83.72 (0.1)
A.4 THEORETICAL BACKGROUND
A.4.1 BACKGROUND ON GENERALIZED GRAPH LAPLACIANS
The generalized graph Laplacians proposed in Sevi et (022 are the generalization of the usual
graph Laplacians found in the literature Chung & Graham (1997); Chung 2005). These operators stem directly from a functional termed as generalized Dirichler energy (GDE) expressed in the following definition.
Definition A.1. Let X be a random walk on digraph G, with transition matrix P. Let u be an arbitrary positive vertex measure on G. The generalized Dirichlet energy of graph function f is defined by
Dep(()=
Σ (()))(e F.VEV
(17)
This functional extends the well-known notion of Dirichlet energy Montenegro et al. (2006) which originally restricted to any ergodic random walk associated with its transition matrix and its sta- tionary measure. In particular, the GDE is defined with respect to any positive regularizing measure and any Markov transition matrix without the requirement of any specific property. As mentioned earlier, the generalized graph Laplacians stems from the GDE by the following relation
(S) = (S. (Rw(w))) = (S, L(v))-
which means that the quadratic form of D2 (fp((() involves the unnormalized generalized graph Lapla- cian. important to mention that the GDE stems directly from the random walk point of view of the graph partitioning proposed in Sevi et al. (2022).
A.4.2 BACKGROUND ON DIFFUSION GEOMETRY
The seminal work by (Coifaan et al. 2005 Coifman & Lafon 2006 introduced the diffusion ge- ometry framework, which uses diffusion processes as basic tool to find meaningful geometric descriptions for data. This general framework leads to efficient multi-scale analysis of datasets for which we have a Heisenberg location principle relating localization in data to localization in the spectrum. The framework can provide different geometric representations of the dataset by iterating the Markov transition matrix, which is equivalent to running forward the random walk. The key element of the diffusion geometry is the diffusion distance Coifman & Lafon (006); Pons & Lat- aayy (2005): Coifman et al.] (2005) which captures the structure encoded in P as a data-dependent distance metric between points and whose the original definition is the following.
16

---

Under review as a conference paper at ICLR 2023
Table 6: Clustering performance (NMI) on real-world datasets with estimated parameters (shown in parenthe- ses) according to the CH (or DCH)) index.
DATASET
N
&|] SC-SMM; RSC(r)
PIC(t.)
P-RWDKC(a,ta)
POLITICAL BLOGS
73.25 (0.2)
(8)
(0,32)
CORA [BoJCHEVSK] GUNNEMANN 2017
2485
7
17.10
30.65 (0.5)
7.86 (4)
49.71
(0.2,16)
FOOTBALL NEWMAN
(0.9.2)
KARATE CLUB (ZACHRY 1911
34 2
73.24
83.72 (1.7) 83.72 (1)
83.72 (0.1)
Definition A.2. Diffusion distance. Let P be the transition matrix reversible random walk on an undirected graph G, with an ergodic distribution w. Given graph function f. 11/1 1/x is the (2-orrm induced by the measure 1/TT defined by |/Alli/ (J, The diffusion distance at time E N between the vertices and j is defined by:
(i.j) |lp pe pr(i,+)lB/s
Notably, diffusion distances are data-depnndent, allowing the detection of nonlinear structure in data at different scales Coifman et al. (2005). The diffusion distance at time t can be considered as the Euclidean distance between rows of P potentially weighted by measure (in the original definition by 1/T)) which takes into account the (empirical) local density of the points. For a finite time 4, if each cluster a cluster of G is highly-connected, and well-separated from other clusters, hen (i +) will be nearly equal to Pr (j. +) for any pair of points i and j in the same cluster, implying a low diffusion distance between points within the same cluster. Conversely, if i and j are in distinct clusters, Pe(E, *) is expected to be very different from pe(j. Since then, some variants of the diffusion distance notion have been proposed Goldberg Kim 2010 2012).
We now introduce the notion of diffusion map main concept of the diffusion geometry frame- work.
Definition A.3. Diffusion map. Let X be a random walk on an undirected graph G - -V, EV,E), E).VV N with transition matrix P and ergodic distribution The transition matrix P admits the following eigendecomposttion P = DD , + where + = [61, 02, ... ...,., Qnl the eigenbasis and D diag (A) is the diagonal matrix of eigenvalues. The diffusion map at time t is defined by
(1) = (1f (g
(i))
Diffusion maps and diffusion distances are related by the following relation Coifman & Lafon (006))
(i. () = (1) 3.12
which means that the diffusion map V embeds the data into Euclidean space in which the Fu- clidean distance is equal to the diffusion distance df, We note that this relationship only exists if the diffusion distance is the original form proposed in Coifman Lafon (2006), i.c. if the random walk with transition matrix P is reversible and if the Euclidean distance is weighted by 1/x.
17


Reviews:
[{"review_id": "_k9QETz3YS", "reviewer": "Reviewer_pmG1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel directed graph clustering method. which is mainly based on the so-called “diffusion geometry” from the diffusion maps/manifold learning/nonlinear dim reduction literature, and a generalized spectral clustering approach. To be more specific, the authors revisited the diffusion distance under the undirected setting by formulating it as Mahalanobis distance, based on which they constructed the random walk diffusion kernel (RWDK) and then showed the conceptual connection between RWDK clustering and the eigendecomposition of the classical spectral clustering method. Next, the authors proposed their directed graph clustering algorithm, namely parametrized random walk diffusion kernel (P-RWDK) clustering. This new method is a generalization on the aforementioned RWDK for clustering directed graphs and is obtained by replacing the random walk Laplacian with a parametrized random walk operator (P-RW).\n\nFor applying the proposed new algorithm, the authors provide a design on the parametrized random walk operator as well as using Calinski–Harabasz criterion for determining the diffusion time.  The authors performed experiments on multiple datasets (digraphs obtained from high-dimensional data using graph construction procedures, and real-world graphs) and demonstrated the effectiveness of their approach by comparing it with several other popular clustering algorithms.\n\nMain Contributions:\n- Under the undirected graph setting, the authors provide a new interpretation on the diffusion distance, and show the equivalence of the diffusion distance and the proposed random walk diffusion kernel (power of the transition matrix normalized by the vertex degrees).\n- They also introduced a generalized random walk diffusion kernel by replacing the random walk Laplacian with the parameterized random walk operator, which might inspire other studies on diffusion geometry of directed graphs.\n- Based on the above analysis, the authors design a new algorithm for digraph clustering as well as principled methods for fine-tuning the optimal algorithm parameters.\n- The authors perform experiments on both synthetic and real-world data to compare their algorithm performance with others.\n", "summary_of_the_review": "Interesting method, with good theoretical support, strong performance on numerical experiments, though the set of baselines could be expanded.", "strength_and_weaknesses": " Strengths:\n- The proposed clustering algorithm is symmetrization free, which avoids loss of the edge direction information. This has been the typical approach in the directed graph literature, and only very recently methods have been proposed which bypass this step\n- The authors provide theoretical background for understanding and motivating their algorithm construction.\n- This approach is simple, efficient and performs very well in experiments.\n\nWeakness:\n- Some part of the writing is not very well detailed:\nOn one hand, some important explanations/intuitions can only be found in cited references, for example, the conceptual explanation of the generalized random walk operator in Sevi et al. (2022); the diffusion distance in Coifman & Lafon (2006).  It would be better to add further notions and intuition in this paper, either main text or appendix.  \n\nThere are also a number of important definitions, such as $l^2(V, v)$, delta function, the norm in the diffusion distance, etc, that can only be found in the two cited, which makes reading uneasy for the reader. On the other hand, for proposition 3.1 and its proof, the conclusion itself is clear already and the following proof is not  necessary.\n\n- There are not sufficient discussions in Section 4.3, where the authors first formally introduce the parametrized diffusion distance and random walk diffusion kernel, which are the key components in their algorithm. It is not straightforward to see why one can extend the RWDK to the parameterized one without any restriction. For example, RWDK clustering and the spectral cluster have similar characteristics. Does this still hold for the parameterized version, i.e., P-RWDK?\n\n- The algorithm requires a vertex measure as input for constructing the generalized random walk operator. There is not sufficient discussion about whether/how the choice of vertex measure influences the clustering performance, theoretically or empirically. For example, how bad the algorithm could perform on an arbitrarily chosen vertex measure?\n\n- It would have been good to compare/contrast with some other very recent lines of work from this digraph literature\n\n    x Higher-order spectral clustering of directed graphs, Steinar Laenen, He Sun (NeurIPS 2020)  \n    x Hermitian matrices for clustering directed graphs: insights and applications, Mihai Cucuringu, Huan Li, He Sun, Luca Zanetti (AISTATS 2020)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MlnmFLsJjM", "reviewer": "Reviewer_xrEQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a framework for clustering, namely the Parametrized Random Walk Diffusion Kernel Clustering (P-RWDKC), for clustering directed graphs. This is based on a “parametrized random walk operator” $P_{(\\nu)}$ that is derived from the “generalized random walk Laplacian” operator of (Sevi et al.,2022), and using which a similarity kernel matrix $K_{t,\\nu}$ is derived.  The matrix $K_{t,\\nu}$ captures the pairwise diffusion distances between the vertices. The idea is to consider the rows of $ K_{t,\\nu}$ as the embedding of the vertices, and so k-means clustering can be applied on the rows to estimate the underlying clustering. The proposed approach is tested on a synthetic example for clustering a mixture of Gaussians and also on several real datasets. The results on real data indicate that the proposed approach typically performs better than some other existing approaches. ", "summary_of_the_review": "The proposed approach seems to show promising results for clustering real-world directed graphs. However, I believe the technical novelty is a bit limited. The literature review and comparisons with related methods is also incomplete. More experiments on synthetic random generative models (such as directed SBM) are needed to understand the usefulness of the proposed approach as compared to the state-of-the-art methods. I have elaborated on these points in the \"Weaknesses\" section. ", "strength_and_weaknesses": "Pros:  The paper has the following strengths.\n\n•  The paper is well written overall, and the main ideas of the approach are outlined cleanly.\n\n•  The experiment results on real data are promising as the proposed algorithm typically leads to better NMI scores than some of the existing approaches.\n\nCons: The paper has the following weaknesses.\n\n• I feel that the technical novelty in the paper is quite limited. The parametrized random walk operator $P_{(\\nu)}$ follows directly from the “generalized random walk Laplacian” operator $L_{RW, (\\nu)}$ of (Sevi et al.,2022) since $P_{(\\nu)} = I - L_{RW, (\\nu)}$. This relation is currently stated in the form of Proposition 3.1, but this is a bit strange to me as there is nothing to prove here. The similarity kernel operator $K_{t,\\nu}$ is obtained by taking the power of $P_{(\\nu)}$ and subsequently normalizing it. However, this is quite similar to clustering approaches for undirected graphs which perform spectral clustering on the “the power of the adjacency matrix followed by an entry-wise truncation” (See for e.g. [1]). In essence, it is well-known that pre-processing a graph matrix (such as the adjacency) by taking a suitably high power of it (the exponent can be thought of as a regularizer term) leads to more robust clustering performance. So, I do not see new insight with regards to the proposed approach.\n\n• The literature review is incomplete as there are many missing references for clustering directed graphs, see for e.g. [2,3,4,5] and reference therein. Therefore, I am not sure if the experiments are actually comparing with the state of the art for this problem. Additionally, I think it would have been beneficial to have more extensive experiments for synthetic examples – for e.g., on random generative models such as the directed Stochastic Block Model (SBM) (see [2]). Since the ground-truth is known, this would provide a clean framework for comparing the performance of the algorithms across different types of inputs (varying community sizes, noise levels, number of clusters etc.). The experiment results at the moment are incomplete in this sense.\n\n• There also exist theoretical results for clustering directed graphs under a directed SBM generative model (e,g, [2]). In that sense, I believe it would have been interesting to provide some theoretical justification for the proposed approach on such a generative model.  \n\nFurther comments:\n\n• In Proposition 4.1, the notation $D_{\\lambda}, D_d$ has not been defined, I think.\n\n• As mentioned above, Proposition 3.1 should really be a Definition since there is nothing to prove here.\n\n• The choice of the vertex measure $\\nu$ and the diffusion time $t^*$ are based on heuristics at the moment. I think it is natural to run some experiments on synthetic examples generated by a directed SBM, for different choices of the tuning parameters (e.g., through a grid search), and then to check whether the best \"global\" value is close to that returned by the heuristic (or maybe just the corresponding NMI values could compared).\n\nReferences:\n\n[1] Abbe et al., Graph Powering and Spectral Robustness, SIAM J. MATH. DATA SCI, Vol. 2, No. 1, pp. 132–157. \n\n[2] Cucuringu et al., Hermitian matrices for clustering directed graphs: insights and applications, AISTATS, PMLR 108:983-992, 2020.\n\n[3] Laenen and Sun, Higher-order spectral clustering of directed graphs. In NIPS'20, 941–951.\n\n[4] Gong et al., Directed network Laplacians and random graph models, R. Soc. open sci., 2021.\n\n[5] Hayashi et al., Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs, arxiv: 2203.01388, 2022\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KvjI_YCMXid", "reviewer": "Reviewer_kddm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper concerns the clustering of directed graphs, using random walk diffusion. The main hurdle is that the digraphs considered may not be strongly connected, so the classical theory of irreducible random walks does not apply. To address this problem, the authors suggest to use a different random walk operator\n$$P = D_{\\nu + \\xi}^{-1}(D_\\nu P + P^\\top D_\\nu)$$\nwhere $\\nu$ can be chosen almost arbitrarily. This random walk is reversible and irreducible, hence the main hurdle is lifted. The authors also present a parametrizable family of choices for $\\nu$, that are based on the original random walk matrix $P$.\n\nAnother aspect of the paper is information geometry. The authors show that a particular choice of distance for diffusion walks can be represented as a so-called Mahalanobis distance, with a given kernel $K$. This kernel can thus be used as an embedding for clustering. Additionally, they show how to measure the clustering of $P$ in a self-supervised way, and provide a stopping criterion based on this measure.", "summary_of_the_review": "see above", "strength_and_weaknesses": "The paper is quite clear and enjoyable to read, and the presented algorithms are intuitive and clearly motivated. The main procedure seems to have a better performance than SOTA algorithms, and the example setting is interestingly chosen to show the possibilities of herarchical clustering.\n\nMy main concern is on the novelty of the paper: although interesting, this is simply a new embedding for k-means clustering, and as (nicely) explained in the paper it fits into the framework of other clustering algorithms. It is also unclear whether the benefits come from the choice of $P$, or the use of $K$ instead of spectral clustering.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5i0_XDxrCnM", "reviewer": "Reviewer_rHPo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper under review studies the clustering problem on directed graphs using random walks. First, let us recall the clustering problem on undirected graphs using random walks. The setup here is rather well-studied. You just perform a suitably long walk at a random vertex within the cluster. Using spectral methods, you recover a good approximation to the cluster by running the k-means-like algorithm on the Feidler embedding of the vertices. In the directed land, the spectral analysis immediately falls apart. But this is the least of our problems. A more serious problem is that the random walks on directed graphs may no longer be irreducible. To address this challenge, this paper develops a \"random-walk diffusion-kernel-based\" clustering approach.\n\nInspired by ideas from diffusion geometry, the paper defines a notion of parameterized diffusion distance at time t between every pair of vertices in the directed graph G. This is defined to be the Euclidean length of the difference in t-step probability vectors from u and v (in l_2(\\pi_v)), Here, $\\pi$ is the stationary distribution of parameterized diffusions on G (where parameterized diffusions are deliberately defined to have a stationary distribution). The clustering algorithm proceeds by running a k-means procedure on the spectral embedding found using the properties of this novel diffusion operator.", "summary_of_the_review": "Overall, my feeling about this work is positive. Though, since the paper does not provide more theoretical details on the quality of the clusters returned by the novel diffusion process the paper considers, I am not able to fully recommend an accept verdict.", "strength_and_weaknesses": "The theoretical strength of this work lies in realizing that we can define a (somewhat) natural diffusion kernel for directed graphs which is obtained by combining a \"parameterized random walk operator\" together with the notion of diffusion distance on undirected graphs. Though, at the same time, the paper does not present any algorithmic application which can benefit from this primitive. Having *not thought* much about it, I am not yet able to clearly compare the quality of clusters obtained from this procedure with the quality of clusters you would get from ACL algorithm which considers page rank walk on directed graphs. \n\nAs for the experimental side, I am fairly convinced (thanks to the included tables) that the algorithm presented in the paper does against its competitors. Though, I would request the authors to add a one-liner explaining what the NMI index ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject