Dissecting graph measures performance for node clustering in LFR parameter space
Authors: Vladimir Ivashkin
Pavel Chebotarev
Venue:  (2021)
Keywords: graph theory
graph measures
kernel k-means
clustering

Abstract: Graph measures can be used for graph node clustering using metric clustering algorithms. There are multiple measures applicable to this task, and which one performs better is an open question. We study the performance of 25 graph measures on generated graphs with different parameters. While usually measure comparisons are limited to general measure ranking on a particular dataset, we aim to explore the performance of various measures depending on graph features. Using an LFR generator, we create a dataset of ~7500 graphs covering the whole LFR parameter space. For each graph, we assess the quality of clustering with k-means algorithm for every considered measure. We determine the best measure for every area of the parameter space. We find that the parameter space consists of distinct zones where one particular measure is the best. We analyze the geometry of the resulting zones and describe it with simple criteria. Given particular graph parameters, this allows us to choose the best measure to use for clustering.

Under review as a conference paper at ICLR 2021
DISSECTING GRAPH MEASURES PERFORMANCE FOR NODE CLUSTERING IN LFR PARAMETER SPACE
Anonymous authors Paper under double-blind review
ABSTRACT
Graph measures can be used for graph node clustering using metric clustering al- gorithms. There are multiple measures applicable to this task, and which one per- forms better an open question. We study the performance of 25 graph measures on generated graphs with different parameters. While usually measure compar- isons are limited to general measure ranking on a particular dataset, we aim explore the performance of various measures depending on graph features. Using LFR graph generator, we create dataset of 7500 graphs covering the whole LFR parameter space. For each graph, we assess the quality of clustering with k-means algorithm for every considered measure. We determine the best measure for every area of the parameter space. We find that the parameter space consists of distinct zones where one particular measure the best. We analyze the geometry of the resulting zones and describe it with simple criteria. Given particular graph parameters, this allows us to choose the best measure to use for clustering.
INTRODUCTION
Graph node clustering is one of the central tasks in graph structure analysis. It provides a partition of nodes into disjoint clusters, which are groups of nodes that are characterized by strong mutual connections. It can be of practical use for graphs representing real-life systems, such as social networks or industrial processes. Clustering allows to infer some information about the system: the nodes of the same cluster are highly similar, while the nodes of different clusters are dissimilar, The technique can be applied without any labeled data to extract important insights about a network.
There are different approaches to clustering, including ones based on modularity optimization (New- man & Girvan 2004. Blondel et al.) 2008), label propagation algorithm (Raghavan et al. 2007 Bar- ber & Clark| 2009). Markov cluster process (Van Dongen 2000 Enright et al. 2002), and spectral clustering (Von Luxburg 2007). In this work, we use different approach based choosing closeness measure on a graph, which allows one to use any metric clustering algorithm (e.g.. Yen
eet al. 2009).
The choice of the measure significantly affects the quality of clustering. Classical measures are the Shortest Path (Buckley & Harary) 1990) and the Commute Time (Göbel & Jagers 1974) distances. The former is the minimum number of edges in a path between a given pair of nodes. The latter is the expected number of steps from one node the other and back in random walk on the graph. There is a number of other measures, including recent ones (e.g., [Estrada & Silver] 2017] [acobsen & Tien 2018), many of them are parametric. Despite the fact that graph measures are compatible with any metric algorithm, in this paper we restrict ourselves to the kernel k-means algorithm (e.g., Fouss et al. 2016).
We base our research on generated set of graphs. There are various algorithms to generate graphs with community structures. The well-known ones are the Stochastic Block Model (Holland et al., 1983) and Lancichinetii-oortaatt Radicchi benchmark (Lancichinetti et al., 2008) (here- after, LFR). The first one is an extension the Erdös-Rényi model with different intra- and in- tercluster probabilities of edge creation. The second one involves power law distributions of node degrees and community sizes. There are other generation models, e.g., Naive Scale-free Cluster- ing (Pasta & Zaidi 2017). We choose the LFR model: although it misses some key properties of real graphs, like diameter or the clustering coefficient, this model has been proven to be effective in meta-learning (Prokhorenkoval 2019.

---

Under review as a conference paper at ICLR 2021
There are lot of measure benchmarking studies considering node classification and clustering for both generated graphs and real-workd datasets (Fouss et al., 2012; Sommer et al. 2016 2017 Avrachenkov et al. 2017:Ivashkin
Ivashkin & Chebotarev
Guex al. |0
Aynulin [0 b
Courtain et al. 2020 Leleux et |l.|)000)) etc. Despite a large number of experimental results, theo- retical results still matter of the future. One of the most interesting theoretical results graph measures is the work by Luxburg et al. (2010). where some unattractive features of the Commute Time distance on large graphs were explained theoretically, and a reasonable amendment was pro- posed to fix the problem. Beyond the complexity of such proofs, there is still very little empirical understanding of what effects need to be proven. Our empirical work has two main differences from the previous ones. First, we consider large number of graph measures, which for the first time gives fairly complete picture. Second, unlike these studies concluding with a global leaderboard, we are looking for the leading measures for each set of the LFR parameters.
We aim to explore the performance of of the 25 most popular measures in the graph clustering prob- lem a set of generated graphs with various parameters. We assess the quality of clustering with every considered measure and determine the best measure for every region of the graph parameter space.
Our contributions are as follows:
We generate dataset of 7500 graphs covering all parameter space of LFR generator;
We consider a broad set of measures and rank measures by clustering performance on this dataset;
We find the regions of certain measure leadership the graph parameter space;
We determine the graph features that are responsible for measure leadership;
We check the applicability of the results on real-world graphs.
Our framework for clustering with graph measures as well as collected dataset are available on link _ottttt______ available during blind bline_review
2 DEFINITIONS
2.1 KERNEL k-MEANS
The original k- t-means algorithm (Lloyd 1982, MacQueen et al. 1967) clusters objects in Euclidean space. requires coordinates the objects determine the distances between them and centroids. The algorithm can be generalized to use the degree of closeness between the objects without defining a particular space. This technique called the kernel trick, usually it is used to bring non-linearity to linear algorithms. The algorithm that uses the kernel trick is called kernel k-means (see, e.g., Fouss et al., 2016). For graph node clustering scenario, we can use graph measures as kernels for the kernel k-means.
Initially, the number of clusters known and we need to set initial state of centroids. The results of the clustering with k-means very sensitive it. Usually, the algorithm runs several times with different initial states (trials) and chooses the best trial. There are different approaches to the initial- ization; we consider three of them: random data points, k-means++ (Arthur & Vassilvitskii 2006). and random partition. We combine all these strategies to reduce the impact of the initialization strategy on the result.
2.2 CLOSENESS MEASURES
For given graph G, (GG is the set of its vertices and A is its adjacency matrix. A measure on G function k: V(G) x V(G) - R, which gets two nodes and returns closeness (bigger means closer) or distance (bigger means farther).
A kernel graph is graph nodes' closeness measure that has inner product representation. Any symmetric positive semidefinite matrix an inner product matrix (also called Gram matrix). A kernel matrix K is square matrix that contains similarities for all pairs of nodes in graph.
2

---

Under review as a conference paper at ICLR 2021
To use kernel l-- k-means, we need kernels. Despite that not all closeness measures consider Gram matrices, we treat them as kernels. The applicability of this approach was confirmed in Fouss et al. (2016). For the list of measures bellow, we use the word "kernel" only for the measures that satisty the strict definition of kernel.
Classical measures are Shortest Path distance (Buckley & Harary distance (Göbel & Jagers, 1974) (CT). SP is the minimum number of edges in a path between a given pair of nodes. CT is the expected lengths of random walks between two nodes. SP and CT are defined as distances, so we need to transform them into similarities to use as kernels. We apply the following distance to closeness transformation (Chebotarev Shamis 1998a Borg Groenen 2005):
1990) (SP) and Commute Time
K HDH; = - P./n,
where D is distance matrix, E is the matrix of ones, I is the identity matrix, and n is the number of nodes.
In this paper, examine 25 graph measures (or, more exactly, 25 parametric families of measures). We present these measures grouped by type similarly to (Avrachenkov et al.) (0177:
Adjacency Matrix based kernels and measures.
Katz kernel: K-Katz (T aA1)_1, 0 < < <p- where p is the spectral radius of
A. (Katz) 1953) (also known as Walk proximity (Chebotarev & Shamis) 1998b) or
von Neumann diffusion kernel (Kandola al., 2003 Shawe-Taylor & Cristianini et
al. 2.04)).
Communicability kernel KCoom expm(L.A), 0. where expm means matrix
exponential (Fouss et al. 2006 Estrada & Hatano 2007 2008).
Douule Factorial closeness: KP -k= A 0 Estrada Silver 2017).
Laplacian Matrix D AA based kernels and measures, where D Diag A 1) the degree matrix of G, Diag(x) is the diagonal matrix with vector x on the main diagonal.
Forest kernel: K = (T + IT. -1.)-1 > 0 (also known as Regularized Laplacian
kernel) (Chebotarev & Shamis 1995).
Heat kernel: KHeat expm tL), > 0 (Chung Yau 1998
Normalized Heat kernel: NH expm( (-t)) -= D LDD 3 0 Chung. 1997).
Abssorption kernel: K-bbs (LA + 1)-1,t>
t> 0 Jacobsen & Tien 2018).
Markov Matrix P = D-1 A based kernels and measures.
Personalized PageRank closeness: KPPR 1999).
(I- < a Page et al,
Modified Personalized PageRank: KMMPP (I - aP) = aA)-
0 a < (Kirkland & Neumann, 2012).
-PageRank heat closeness: KHPR expm( expm(-i(T-- P)), t 0 (Chung 2007
RRnddoiized Shortest Path distance. Using P and the matrix of the SP distances C first get Z (Yen et al.
2008
W Po Poeep((888) - (1 (1-W)-
Then S = (Z(CoW)Z) Z; Č= - (S). and finally, DRSP (C+ CT) /2. Here and + are element-wist multiplication and division. Kernel version KRSSP can be obtained with equation
-Fee Energy distance. Using Z from equation
Zh Diag -1; +
log hh; DFE = (Φ + 1/2 (Kivimāki et al. 2014). Kernel version F:F can be obtained with equation
Sigmoid Commute Time kernels.
Sigmoid Commute Time kernel:
KS0 SCT = - /st(KK(T) { 1> 0,
(3)
where is element-wise sigmoid function (xx 1/(1 + e- Yen al.
2007
3

---

Under review as a conference paper at ICLR 2021
Table Short names of considered kernels and other measures.
Short name
Plain
Logarithmic
Family
measure
measure
Full name
Adjacency matrix
Katz
logKatz
Katz kernel
based kernels
Comm
logComm
Communicability kernel
DF
logDF
Double Factorial closeness
For
logFor
Forest kernel
Laplacian based kernels
Heat
logHeat
Heat kernel
NHeat
logNHeat
Normalized Heat kernel
Abs
logAbs
Absorption kernel
Markov matrix based kernels and measures
PPR
logPPR
Personalized PageRank closeness
MPPR
logMPPR
Modified Personalized PageRank
HPR
logHPR
PageRank heat closeness
RSP
Randomized Shortest Path kernel
FE
Free Energy kernel
Sigmoid
SCT
Sigmoid Commute Time kernel
Commute Time
SCCT
Sigmoid Corrected Commute Time kernel
SP-CT
linear combination of SP and CT
Sigmoid Corrected Commate Time kernel. First of all, need the Corrected Com- mute Time kernel (Luxburg et al. 2010):
dd
KCT HD M(T M) MD H: =
D
vol(G)
where is the centering matrix = E/n, d is the vector of diagonal elements of D and vol(G' is the sum of all clements of A. Then, apply equation replacing KCT with ROCCT to obtain 5SCCT
Occasionally, element-wise logarithm is applied the resulting kernel matrix (Chebotarey 2013 Ivashkin & Chebotarey] 20166). We apply it to almost all investigated measures and consider the re- sulting measures separately from their plain versions (see Table []. For some measures, like Forest kernel, this is well-known practice [Chebotarev] 2013), while for others, like Double Factorial close- ness, this transformation, to the best of our knowledge, applied for the first time. The considered measures and their short names are summarized in Table
3 DATASET
We collected a paired dataset of graphs and the corresponding results of clustering with each measure mentioned in Table In this section, we describe the graph generator, the sampling strategy, the calculated graph features, and the pipeline for the measure score calculation.
(LFR) graph generator. It generates non-weighted graphs with ground truth non-overlapping communities. The model has mandatory parameters: the number of nodes n (n 0), the power law exponent for the degree distribution Ti (71 > 1), the power law exponent for the community size distribution T2 (T2 1), the fraction of intra-communic edges incident each node μ (0 < μ < 1), and either minimum degree (min degree) or average degree (avg degree). There are also extra parameters: maximum degree (max degree), minimum community size (min community), maximum community size (max community). Not the whole LFR parameter space corresponds to common real-world graphs; most of such graphs are described with тı E [1, 4] and μ < 0.5 (c.g., Fotouhi et al. 2019). However, there is also an interesting case of bipartite/muttipartteliiii
We use
graphs with μ 0.5. Moreover, many of the datasets studied in Section have TI > 4. Our choice to consider the entire parameter space to cover all theoretical and practical cases.
For the generation, we consider 10 < n < 1500. is impossible to generate a dataset with a uniform distribution of all L.R parameters, because 7i and 72 parameters located rays. We transform
4

---

It is Under review as a conference paper at ICLR 2021
250
200
250
200
150
150
150
100
50
50
0
250
500
750
1000
1250
1500
10
100
10
100
H
avg degree
modularity
800
250
200
600
150
400
100
200
200
0.0
0.2
0.4
0.6
0.8
1.0
100 1000
-0.50
-0.25 0.00
0.25
0.50 0.75
Figure 1: Distribution of graph features in the dataset
Ti and to 11- i 1,2 to bring their scope to the [0, 1] interval. In this case, "realistic" settings with T1 E [1,4] take up 50% of the variable range. Also, as avg degree feature limited by the of a particular graph, we decided to replace it with density (avg not dependent on n and belongs to [0, 1]. Using all these considerations, we collected our dataset by uniformly sampling parameters for LFR generator from the set [n, नi. 72, μ., density] and generating graphs with these parameters. Additionally, we filter out all disconnected graphs.
In total, generated 7396 graphs. It is worth noting that the generator fails for some sets of parameters, so the resulting dataset is not uniform (see Fig. IT.. In our study, non-uniformity is not very important issue, because we interested in local effects, not global leadership. Moreover, true uniformity for LFR parameter space is impossible, due to the unlimited scope of parameters.
For research, choose minimum set of the features that describe particular properties of graphs and are not interchangeable.
The LFR parameters be divided in three groups by the graph properties they reflect:
LFR parameters 10, faul, 2ou2, mea, etc.
measure parameter I [0
The size of the graph and the com- munities: Tı, min community, max community;
LFR
measure (Katz, Forest etc.)
graph & ground truth partition
The density and uniformity of the node degrees distribution: T2, min de- gree, avg degree, max degree. As avg degree depends on it is dis- tributed exponentially, so we use log(avg degree) instead;
Rehustece
initialization strategy
k-means (several trials)
(k-means+++ etc.)
Vtran
choosing criteria (inertia, modularity)
The cluster separability: μ.. As μ parameter considers only the ratio between the number of inter-cluster edges and the number of nodes but ig- nores overall density, we modu- larity (Newman & Girvan] 2004) as more appropriate measure for cluster separability.
Mpsed
ARI sczure
Measuring ARI clustering score for particular graph, measure, and measure parameter
Figure 2:
Thus, the defined set of features [n, T1, T2, avg degree, modularity] enough to consider all graph properties mentioned above. Although modularity is widely used measure, it suffers from reso- lution limit problems (Fortunato Barthelemy) (2077.. We acknowledge that this may cause some limitations in approach, which should be the topic of further research.
5

---

Under review as a conference paper at ICLR 2021
The overall leaderboard. The win percentage is calculated among all 7396 graphs in the dataset. The ARI column shows the mean ARI across the dataset.
Table 2:
Measure
Rank
Wins, %
ARI
#
Measure
Rank
Wins, %
ARI
SCCT
4.7
56.0
0.58
14
DF
11.0
8.1
0.28
2
NHeat
6.9
25.2
0.40
15
logAbs
12.1
15.9
0.33
RSP
7.7
22.4
0.42
16
logComm
12.6
15.5
0.23
4
SCT
8.4
19.5
0.40
17
logFor
13.0
12.7
0.22
Comm
8.4
15.8
0.36
18
HeatPR
13.4
12.5
0.22
6
logNHeat
8.8
18.0
0.37
19
logHeat
13.6
11.9
0.21
SP-CT
9.0
20.4
0.41
20
Heat
14.7
11.2
0.19
8
logHeatPR
9.2
18.0
0.37
21
logDF
14.8
11.1
0.18
9
FE
9.5
19.3
0.39
22
PPR
16.7
4.0
0.13
10
Katz
9.8
7.7
0.32
23
Abs
18.6
3.7
0.08
11
logKatz
9.9
18.1
0.35
24
For
19.3
2.8
0.07
12
logPPR
10.0
17.5
0.35
25
ModifPPR
20.5
1.7
0.05
13
logModifPPR
10.5
17.3
0.35
For every generated graph, we calculate the top ARI score for every measure (Hubert & Arabie 1985). We choose ARI as a clustering score which is both popular and unbiased (Gösgens et al, 2019 As soon as every measure has parameter, we perform clustering for range of parameter values (we transform the parameter to become in the [0, 1] interval and then choose 16 values linearly spaced from 0 to 1). For each value, run 6 6 + trials of k-means (6 trials for each of three initialization methods).
Fig. 2 shows the pipeline we use to calculate ARI score for given LFR parameter set, measure, and a measure parameter. Measure parameters are not the subject of our experiments, so for every measure we just take the result of the measure with the value of the parameter that gives the best ARI score.
Because the need iterate over graphs, measures, parameter values, and initializations, the task is computationally difficult. The total computation time was 20 days on 18 CPU cores and 6 GPUs.
4 RESULTS
4.1 GLOBAL LEADERSHIP LFR SPACE
We rank the measures by their ARI score every graph of the dataset. The rank is defined as the position of the measure this list, averaged over the dataset (see Table 2). It is important to note that the global leadership does not give comprehensive advice which measure is better to use, because for a particular graph, the global leader can perform worse than the others. Here we consider the entire LFR space, not just zone corresponding common real-world graphs, so the ranking may differ from those obtained for restricted settings.
As SCCT is the winner for both ranking and percentage of wins, can say for sure that is the global winner for the LFR space graphs. Other measures still can be leaders in some zones of the feature space.
4.2 FEATURE IMPORTANCE, STUDY
First of all, we find out which graph features are important for the choice of the best measure and which not. To do that, method finds new basis the feature space to classify dataset in the best way. also shows how many components of basis required to fit the majority of data.
Linear Discriminant Analysis (Mika al. 1999) (LDA). This
Fig. Sa shows that the first two components take about 90% of the explained variance. Fig. shows that these components include only 71, avg degree, and modularity. The fact that is not used means that the size of the graph as well as the density are not of primary importance for choosing the best measure. So is 72 measuring the diversity of cluster sizes.

---

Under review as a conference paper at ICLR 2021
70
1.0
Percent Explained Variance
0
0.8
0.6
40
20
avg degree
0.2
modularity
0.0
Component
Component
(a) Explained variance.
(b) Features contribution L.DA components.
Figure 3: The results of LDA components.
Fig. shows the point cloud projected the space of the main components of LDA. We see confirmation that the measures are indeed zoned, but the areas are quite noisy. To detect the zones of measure leadership, we need know the leadership on average every area of space, rather than the wins in particular points. To define the local measure leadership in the whole space, we need introduce a filtering algorithm that for every point of the space returns the measure leadership depending on the closest data points. As the choice of measure is actually dependent only on three features, we can limit our feature space to [TI, avg degree, modularity).
Katz
FE
logKatz
PPR
For
logPPR
lagFor
Modi
Comm
ladifPR
logComm
HeatPR
Component
Heat
lagHeatPR
logHeat
DF
NHHeat
logDF
logNHHeat
Abss
SCT
logAbs
SCCT
RSP
Component
Figure 4: The dataset projected on the two main components of LDA; the point color represents the winning measure for each graph
4.3 GAUSSIAN FILTER IN FEATURE SPACE
Using filter in the feature space, we can suppress the noise and find actual zones of leadership for the measures. We use the Gaussian filter with scale parameter σ.. For every given point of the space, it takes the data points that are closer than 30 and averages ARIs of the chosen points with weight e- -dis?/2s /20 This allows to give larger weights to closer points. If there are less than three data points inside the sphere with a 30 radius, the filter returns nothing, allowing to ignore the points with insufficient data.
Before applying the filter, we prepare the dataset. First, we only take the points with only one winning measure, because multiple winners confuse the filter. Then normalize the standard

---

Under review as a conference paper at ICLR 2021
deviation of every feature distribution to one. Finally, cut off the long tail of distant data points. The resulting number of graphs is 5201.
To choose o, apply the filter with different and look the number of connected components the feature space. The needed a should be large enough to suppress the noise, however, it should not suppress small zones. Guided by this heuristic, choose 0.5.
Table 3: The leaderboard of measure wins after filtering with o = 0.5
logComm
logNHeat
SCCT
NHeat
Comm
logDF
logFor
RSP
Abs
SCT
FE
Measure Wins
4283
441
268
78
64
56
3
3
2
After filtering with 0.5, the leaderboard of measure wins is changed (see Table 3 Only six measures keep their positions: SCCT, NHeat, logComm, Comm, logDF, and RSP. This means that these measures do have zones leadership, otherwise they would be filtered out. We can plot the entire feature space colored by the leadership zones of the measures (Fig. 5 As the resulting space 3D, we show slices of by each of the three coordinates.
D.9.266)
12 4.57
n:145.64 644
08.4 23.31
12.A 128
873
SCCT
303
logComm
HogDr
(a) Slices by Ti.
degres: 7.2)
avg degres: 25]
avp degres:
ang dog [82,
avg degress (268. 874)
302-
SCCT
NHeat
Comm
logComm
RSP
logDF
madutart
medula ky
moduarit
modalalty
nodubility
(b) Slices by avg degree.
modilarty: (0.05,
modularity 14.2),
modilariyy 10.24. 0.201
medidaby: 10.20, 051
medidaityy (0.51 0
SCCT
NHeat
Comm
logComm
2
R.R. R aNg degree
B 3wg degres
2 avg degree
logDF
093 degiee
avg degiree
(c) Slices by modularity.
The feature space [Ti, avg degree, modularity] divided into the leadership zones of six measures. The yellow points represent the positions of real-world datasets under study the space.
Figure 5:
REAL-WORLD DATASETS
Even though LFR lacks some characteristies of real-world graphs, there is evidence that the optimal parameter of the Louvain clustering for real graph is close to the parameter for L.R graphs gen-
8

---

Under review as a conference paper at ICLR 2021
erated from the features of real one (Prokhorenkova 2019). So, there is a chance that the learned space might be helpful for choosing measures in the wild.
For evaluation, ball (Newman & Girvan 2004), Karate club Zachary 1977p. Newsgroups (9 subsets, weights are binarized with threshold 0.1) (Yen et al. 2007), Political blogs (Adamic & Glance 2005). Political
use 29 graphs of standard datasets: Dolphins Lusseau et al. 2003), Foot-
books (Newman 2006), SocioPatterns Primary school day (2 graphs) (Stehlé et al. (011). II, Cora (11 subsets) (McCallum al. 2000), Eu-core (Leskovec et al. 2007), EuroSIS (WebAtlas 2009). The parameters of these graphs are marked in Fig. 5 For each graph, we found the best ART for every measure (iterating over the measure parameter value). Now we can check the quality of measure choice, based on the found LFR data. The result of LFR recommendation is the measure that is chosen for the set of parameters corresponding to the dataset hand.
Table 4: Mean ART of the LFR recommended strategies for datasets. Top6 stands for the set of measures that have their zones in the LFR parameter space.
Strategy Always take SCCT
Mean ARI
0.61
Based on LFR space, top6 measures
0.62
Based on LFR space, all measures Upper bound
0.62
0.64
The best measures on the considered datasets are SCCT (by the mean ARI) and SCT (by the rank). This is pretty similar to the results obtained for LFR. Moreover, Spearman correlation between the ranks of measures for the datasets and for the corresponding LFR recommendations is 0.90.
Let us use "always take SCCT" as our baseline strategy. In Table + we compare it with strategies based the LFR space. We obtain LFR recommendation using Ann as a well-proven method for meta-learning. Since each graph is unique, the result of Inn can be very noisy, thus we use 5nn.
Table 4 shows that the recommendation approach slightly beats the baseline. Reducing the number of measures from 25 to 6 do not drop the quality. However, this quality increase is not enough to draw confident conclusions about the advantages of the method. Using this fact and the fact that the ranks on datasets and recommendations are highly correlated, we conclude that the meta- learning procedure is adequate to give robust recommendation, but not precise enough to beat the baseline confidently. This may be due to the fact that that the nodes of real graphs were not labeled systematically since they were created in the wild. A larger dataset could help separate the signal from the noise and pinpoint where the limits of the method are. At least, the good news is that the conclusions made on the LFR basis do not contradict the results obtained on the datasets.
CONCLUSIONS
In this work, have shown that the global leadership of measures does not provide comprehensive knowledge about graph measures. We demonstrated that among 25 measures, SCCT is the best measure for the LFR graphs both by winning rate and ranking. However, there are also smaller confident zones of leadership for NHeat, Comm, logComm, logDF, and RSP.
Our results do not contradict those of other experimental works and rather expand them by pro- viding new findings. LogComm was first introduced in Ivashkin & Chebotarev (2016) and won in the competitions on graphs generated with a fixed set of SBM parameters. This study confirms its leadership. but only for certain type of graphs. Another interesting finding is logDF, which unexpectedly shows good performance for the graphs with low modularity and low average degree.
This study is based on the LFR benchmark data. An attempt to apply the results real data gives the quality slightly above the baseline. However, there is strong correlation between the ranking of measures for datasets and the ranking of LFR recommendation, which indicates that the leading measures are the same, while the recommendations are not precise enough.
It can be noted that our study is insensitive to the non-uniformity of the generated dataset. While manipulations with this dataset may affect the global leaderboard, they cannot change the local leadership studied in this work.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Lada A. Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd International Workshop on Link Discovery, pp. 36-43, 2005.
David Arthur and Sergei Vassilvitskii. k-means+4; The advantages of careful seeding. Technical report, Stanford University, 2006.
Konstantin Avrachenkov, Pavel Chebotarev, and Dmytro Rubanov. Kernels on graphs as proximity measures. In International Workshop Algorithms and Models for the Web-Graph, pp. 27-41.
Springer, 2017.
Rinat Aynulin. Efficiency of transformations of proximity measures for graph clustering. In Inter- national Workshop on Algorithms and Models for the Web-Graph, pp. 16-29. Springer, 2019a.
Rinat Aynulin. Impact of network topology efficiency of proximity measures for community detection. In International Conference on Complex Networks and Their Applications, pp. 188- 197. Springer, 2019b.
Michael J. Barber and John W. Clark. Detecting network communities by propagating labels under constraints. Physical Review E, 80(2):026129, 2009.
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10088, 2008.
Ingwer Borg and Patrick Groenen. Modern Multidimmensionl Scaling: Theory and Applications. Springer Science Business Media, 2005.
Fred Buckley and Frank Harary. Distance in Graphs. Addison-Wesley, 1990.
Pavel Chebotarev. Studying new classes of graph metrics. In International Conference on Geometric Science of Information, pp. 207-214. Springer, 2013.
Pavel Chebotarev and Elena Shamis. On the proximity measure for graph vertices provided by the inverse Laplacian characteristic matrix. Abstracts of the Conference "Linear Algebra and its Applications" ", pp. 6-7, Manchester, UK, 1995. University of Manchester.
Pavel Chebotarev and Elena Shamis. On a duality between metrics and E-proximities. Automation and Remote Control, 59(4)6608 662))2 1998a.
Pavel Chebotarev and Elena Shamis. On proximity measures for graph vertices. Automation and Remote Control, 14:3:)44431159) 1998b.
Fan Chung. The heat kernel as the pagerank of a graph. Proceedings of the National Academy of Sciences, 104(50):17355-9744) 2007.
Fan Chung and Shing-Tung Yau. Coverings, heat kernlss and spanning trees. Journal Combina- torics, 6:163-184, 1998.
Fan R. K. Chung. Spectral Graph Theory, volume 92, American Mathematical Soc., 1997.
Sylvain Courtain, Pierre Leleux, Ilkka Kivimäki, Guillaume Guex, and Marco Saerens. Randomized shortest paths with net flows and capacity constraints. Information Sciences, 2020. To appear.
Anton J. Enright, Stijn Van Dongen, and Christos A. Ouzounis. An efficient algorithm for large-scale detection of protein families. Nucleic Acids Research, 30(7):175--15544 2002.
Ernesto Estrada and Naomichi Hatano. Statistical- approach to subgraph centrality in complex networks. Chemical Physics Letters, 439(1-3):247-551, 2007. 2007.
Ernesto Estrada and Naomichi Hatano. Communicability in complex networks. Physical Review E, 77(3):036111 2008.
Ernesto Estrada and Grant Silver. Accounting for the role of long walks on networks via a new matrix function. Journal of Mathematical Analysis and Applications, 449(2):1581-166) 2017.
10

---

Under review as a conference paper at ICLR 2021
Santo Fortunato and Mare Barthelemy. Resolution limit in community detection. Proceedings of the National Academy of Sciences, (04(1))36-41, 2007.
Babak Fotouhi, Naghmeh Momeni, Benjamin Allen, and Martin A Nowak. Evolution of cooperation large networks with community structure. Journal of the Royal Society Interface, 16(152): 20180677, 2019.
Francois Fouss, Luh Yen, Alain Pirotte, and Marco Saerens. An experimental investigation of graph kernels on collaborative recommendation task. In Sixth International Conference on Data Min- ing (ICDM 066, pp. 863-868. IEEE, 2006.
François Fouss, Kevin Francoisse, Luh Yen, Alain Pirotte, and Marco Saerens, An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classifi- cation. Neural Networks, 31 31:53-72, 2012.
François Fouss, Marco Saerens, and Masashi Shimbo. Algorithms and Models for Network Data and Link Analysis. Cambridge University Press, 2016.
Göbel and A. A. Jagers. Random walks on graphs. Stochastic Processes and Their Applications, 2(4):311-336, 1974.
Martijn Gösgens, Liudmila Prokhorenkova, and Alexey Tikhonov. Systematic analysis of cluster similarity indices: Towards bias-free cluster validation. arXiv preprint vrXiv:1911.04773 2019.
Guillaume Guex, Ilkka Kivimäki, and Marco Saerens. Randomized optimal transport on graph:
framework and new distance measures. arXiv preprint (mXiv:1806.03232 2018.
Guillaume Guex, Sylvain Courtain, and Marco Saerens. Covariance and correlation kernels on graph in the generalized sag-of-patht formalism. arXiv preprint arXiv:1902.0300) 2019.
Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Nenworks, 5(2):109-13) 137, 1983.
Lawrence Hubert and Phipps Arabie. Comparing iinitions. of Classification, 2(1):193-2188 1985.
Vladimir Ivashkin and Pavel Chebotarev. Do logarithmic proximity measures outperform plain ones in graph clustering? In International Conference Network Analysis, pp. 87-105. Springer, 2016.
Karly A. Jacobsen and Joseph H. Tien. A generalized inverse for graphs with absorption. Linear Algebra and its Applications, 537:118-1477 2018.
Jaz Kandola, Nello Cristianini, and John Shawe-Taylor. Learning semantic similarity, In Advances in Neural Information Processing Systems, pp. 673-680, 2003.
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-43, 1953.
Stephen Kirkland and Michael Neumann. Group Inverses of M-matrices and Their Applications. CRC Press, 2012.
Ilkka Kivimäki, Masashi Shimbo, and Marco Saerens. Developments in the theory of randomized shortest paths with comparison graph node distances. Physicu A: Statistical Mechanics and its Applications, 393:600-616, 2014.
Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing com- munity detection algorithms. Physical Review E, 7864):046110 2008
Pierre Leleux, Sylvain Courtain, Guillaume Guex, and Marco Saerens. Sparse randomized shortest paths routing with tsallis divergence regularization. arXiv preprint arXiv:2007.00419 2020.
Jure Leskovee, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1, Art. 2):1-41, 2007.
11

---

Under review as a conference paper at ICLR 2021
Stuart Lloyd. Least squares quantization in pem. IEEE Transactions Information Theory, 28(2): 129-137, 1982.
David Lusseau, Karsten Schneider, Oliver J. Boisseau, Patti Haase, Elisabeth Slooten, and Steve M. Dawson. The bottlenose dolphin community of doubtful sound features large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 54(4):396 2003.
Ulrike V. Luxburg, Agnes Radl, and Matthias Hein. Getting lost in space: Large sample analysis of the resistance distance. In Advances in Neural Information Processing Systems, pp. 2622-26633 2630, 2010.
James MacQueen et al. Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol- ume 14, pp. 281-297. Oakland, CA, USA, 1967.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):227-163, 2000.
Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhard Scholkopf, and Klaus-Robert Mullers.
Fisher discriminant analysis with kernels. In Neural Networks for Signal Processing IX: Proceed- ings of the 1999 IEEE Signal Processing Society Workshop, pp. 41-48. IEEE, 1999.
Mark J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):577-8882, 2006.
Mark E. J. Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical Review F, 69(2):0261 13, 2004.
Lawrence Page, Sergey Brin, Rujeev Motwani, and Terry Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Muhammad Qasim Pasta and Faraz. Zaidi. Topology of complex networks and performance limita- tions of community detection algorithms. IEEE Access, 5:10901-10914 2017.
Liudmila Prokhorenkova. Using synthetic networks for parameter tuning in community detection. In International Workshop on Algorithms and Models for the Web-Graph, pp. 1-15. Springer, 2019.
Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3):036106, 2007.
John Shawe-Taylor and Nello Cristianini et al. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004.
Felix Sommer, François Fouss, and Marco Saerens. Comparison of graph node distances on clus- tering tasks. In International Conference Artificial Neural Networks, pp. 192-201. Springer, 2016.
Felix Sommer, François Fouss, and Marco Sacrens. Modularity-driven kernel k-means for commu- nity detection. In International Conference on Artificial Neural Networks, pp. 423 Springer, 2017.
Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Dean-François Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne Régis, and Bruno Lina et al. High-resolution measurements of face-to-face contact patterns a primary school. PloS One, 6(8)e231 16, 2011.
Stijn Marinus Van Dongen. Graph Clustering by Flow Smulation. PhD thesis, Utrecht University, 2000.
Ulrike Von Luxburg. A tutorial spectral clustering. Statistics and Computing, 17(4):395-416, 2007.
WebAtlas. Eurosis webmapping, 2009. URL /ww.:////////....eeeeetaaee http://ww..ebttla..ff/eeeeeee eurosis/
12

---

Under review as a conference paper at ICLR 2021
Luh Yen, Francois Fouss, Christine Decaestecker, Pascal Francq. and Marco Saerens. Graph nodes clustering based on the commute-timg kernel. In Pacific-Asia Conference on Knowledge Discov- ery and Data Mining, pp- 1037-1045. Springer, 2007.
Luh Yen, Marco Saerens, Amin Mantrach, and Masashi Shimbo. A family of dissimilarity mea- sures between nodes generalizing both the shortest-path and the commute-time distances. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785-795 2008.
Luh Yen, Francois Fouss, Christine Decaestecker, Pascal Francq, and Marco Saerens. Graph nodes clustering with the sigmoid commute-time kernel: A comparative study. Data Knowledge Engineering, 68(3):338--33 2009.
Wayne W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4):452-473, 1977.
13


Reviews:
[{"review_id": "yA_F5WmNcS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tests performance of different node similarity measures when used in K-means for clustering LFR graphs. It provides recommendations for which measure is more appropriate for different parameter spaces. \n\nIt is easy to read paper and well organized. A rich set of graph similarity measures is studied. \nThere are however critical issues with the design of the experiments. First, the space of parameters considered is very unrealistic and hence most experiments and recommendations are not applicable. This makes, for example, most of the space in figure 6, irrelevant. For instance the exponent of the degree distribution is between 2 and 3 for most real world networks. This goes up to 100 in the experiments. Where did you use the transformed [0,1] version?\nThe average degree is much smaller whereas graphs are usually much larger than the setting here. A negative modularity is result of poor parameter choices, and generally, signifies there is no cluster structure in the graph. Generally, given this is focused on studying the space of LFR graphs, one expects more careful understanding of what there parameters mean. On a minor point, LFR is not using preferential attachment mechanism and is achieving power-law degree distribution by directly sampling degrees and using configuration model. \nI suggest fixing the parameter settings and making sure the modularity is at least 0.1 for all the graphs. The common link prediction measures, e.g. number of common neighbours, could also be added as simple baselines, as well as more recent embedding based models where k-means could be applied directly in the embedded space. Another possibility is to also include another clustering measure, say a density based one. The motivation needs to be expanded. What justifies going n square when a graph based clustering could do the same job? Also in the results, using ranking is good, but the actual numbers are also meaningful. It is hard to see if these methods are recovering anything meaningful when only the relative performance is reported. Basically, if the ARI is too small, which means no correlation between results and the ground-truth, you can still have a ranking of all the close to zero numbers. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "rQ5mjcmKv31", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n1. No good reasons to choose settings of evaluation, particularly kernel k-means and LFR. \n\n2. I think this paper may think about something very obvious. The setting is kernel k-means, and if the similarity measure is given as some kernel, it might be more clearly shown what kernel is good under what condition, under kernel k-means.  In other words, we may find some connection between a kernel and the condition of data generation under the kernel k-means already before doing some experiments.  I think this type of investigation is missing in this paper.\n\n3. So what is the reason why SCCT is the best and/or why highly-ranked methods are so? I think that would be simply connected to the scheme of data generation of LFR or another feature in generating data or noise. I think this point might be obvious but might become some good contribution, while just data generation and comparison would not be something people can say contribution.\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "pV6GmG90MmX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Using 7500 LFR-generated graphs as a benchmarks suite, the authors compare 25 graph clustering measures, determining the best measure for every area of the parameter space. The paper is well written, mathematically sound and interesting, and definitely useful to the graph theory community. However, as acknowledged by the authors, the study is limited by the structure of the benchmark suites, which is restricted to networks that can be generated by LFR rules. Overall, I rate it as a weak accept.\n\nPros:\n- the analysis is clear and grounded, with a sufficient level of mathematical details\n- the authors point out a clear winner out of the set of compared metrics\n\nCons:\n- the amount of novelty in the manuscript is limited \n- the benchmark suite is very specific, and no real world example (that would have added great value to the submission) is provided\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "89WhVX3KfR4", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper deals with the problem of community detection on graphs, examining the impact of graph measures. To do so, the paper proposes an experimental framework where clustering is achieved using the kernel k-means algorithm, and the performance of graph measures is examined on various instances of artificially generated graphs using the LFR benchmark. The overall approach is empirical, supported mainly by the experimental results. The main observations concern the consistent behavior of particular graph measures across multiple settings of the dataset.\n\nStrong points:\n\n-- The paper addresses an important problem in network analysis, which also concerns practitioners in a wide range of disciplines.\n\n-- Various graph measures are considered in the evaluation. This is very interesting, since, in my view, some of them are not very well-known among the graph clustering / community detection communities.\n\n-- The paper is well-structured and well-written. Most of the concepts, including the experimental framework, are clearly presented.\n\n\nWeak points:\n\n--- My main concern about the paper has to do with the consistency of the proposed evaluation framework under different evaluation criteria and graph data beyond the LFR benchmark. Firstly, as the paper also mentions, focusing only on LFR graphs can definitely reveal important properties of algorithms, but limits the generalization of the observations in the case where other generators might be used (e.g., SBM) or even real-world graphs. Besides, the argument made in the paper that the LFR benchmark generates graphs similar to real-world ones is not very accurate. LFR focuses on the clustering structure as well as on the degree distribution but might miss other key properties including graph diameter or the number of triangles (or the clustering coefficient). Is there any evidence that could support the observations of the paper in the case of real graphs? \n\n--- A closely related point has to do with the observation that real-world graphs do not have a clear clustering structure, i.e., well-defined cuts. Focusing only LFR graphs might not be enough to capture such instances. \n\n--- The modularity criterion is used to evaluate the quality of communities, which overall is a widely used criterion. Nevertheless, modularity has been shown to be prawn to the particular structure of the communities (e.g., resolution limit). How is this taken into account in the evaluation of the communities?\n\n--- Another point is that the paper is purely empirical. Definitely, this is a good starting point, especially when the focus is on experimental settings that have not been used before. Nevertheless, despite the interesting observations, I would expect to have a (theoretical) justification or some reasoning of why SCCT performs well on LFR graphs, or for instance why PPR which is a widely used measure, shows poor behavior.\n\n--- In the paper, all graph measures are considered as kernels. How valid is this argument? Why not just using the pure k-means for graph measures which are not kernels? \n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies various graph measures in depth.  The paper was reviewed by three expert reviewers who complemented the ease of understanding because of clear writing. But they also expressed concerns for limited novelty, theoretical justification, and unrealistic setting. The authors are encouraged to continue research, taking into consideration the detailed comments provided by the reviewers.
Decision: Reject