Deep Graph-Level Clustering Using Pseudo-Label-Guided Mutual Information Maximization Network
Authors: Jinyu Cai
Yi Han
Wenzhong Guo
Jicong Fan
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph-level clustering
Graph representation learning
Deep learning
Unsupervised learning

Abstract: In this work, we study the problem of partitioning a set of graphs into different groups such that the graphs in the same group are similar while the graphs in different groups are dissimilar. This problem was rarely studied previously, although there have been a lot of work on node clustering and graph classification. The problem is challenging because it is difficult to measure the similarity or distance between graphs. One feasible approach is using graph kernels to compute a similarity matrix for the graphs and then performing spectral clustering, but the effectiveness of existing graph kernels in measuring the similarity between graphs is very limited. To solve the problem, we propose a novel method called Deep Graph-Level Clustering (DGLC). DGLC utilizes a graph isomorphism network to learn graph-level representations by maximizing the mutual information between the representations of entire graphs and substructures, under the regularization of a clustering module that ensures discriminative representations via pseudo labels. DGLC achieves graph-level representation learning and graph-level clustering in an end-to-end manner. The experimental results on six benchmark datasets of graphs show that our DGLC has state-of-the-art performance in comparison to many baselines.

Under review as a conference paper at ICLR 2023
DEEP GRAPH-LEVEL CLUSTERING USING PSEUDO- LABEL-GUIDED MUTUAL INFORMATION MAXIMIZA- TION NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
this work, we study the problem of partitioning a set of graphs into different groups such that the graphs in the same group are similar while the graphs in different groups are dissimilar. This problem was rarely studied previously, al- though there have been lot of work node clustering and graph classification. The problem challenging because it is difficult to measure the similarity or dis- tance between graphs. One feasible approach is using graph kernels compute a similarity matrix for the graphs and then performing spectral clustering, but the effectiveness of existing graph kernels in measuring the similarity between graphs is very limited. To solve the problem, we propose novel method called Deep Graph-Level Clustering (DGLC). DGLC utilizes a graph isomorphism network learn graph-level representations by maximizing the mutual information between the representations of entire graphs and substructures, under the regularization of a clustering module that ensures discriminative representations via pseudo labels. DGLC achieves graph-level representation learning and graph-level clustering end-to-end manner. The experimental results six benchmark datasets of graphs show that our DGLC has state-of-the-art performance in comparison to many baselines.
INTRODUCTION
Graph- data widely exist in real-world scenarios, such as social networks (Newman 2006) and molecular analysis (Gilmer et al., 2017). Compared to other data formats, graph data explicitly contain connections between data through the attributes of nodes and edges, which can provide rich structural information for many applications. In recent years, machine learning graph-structured data gains more and more attention. Many supervised and unsupervised learning methods have been proposed for graph- structrrd data in various applications.
The machine learning problems of graph-structured data can be organized into two categories: node- level learning and graph-level learning. In node-level learning, the samples the nodes in single
graph. Node-level learning mainly includes node classification (Li et al. 2017 Wu et al.
2021
Xu
al. [202I) and node clustering (Wang al. 2017 Pan & Kang 2021 Lin al.
202
Classical
node classification methods are often based on graph embedding Yan et al.
2006
Cai et al. 2018)
and graph regularization (Subramanya & Bilmes 2009 Bhagat et 2011).
while recent ad advances
are based on graph neural networks (GNN) (Kipf & Welling 2017 Xu et al.
2019; Wu et al. 2020)
Owing to the success of GNN in nodes classification, a few researchers have proposed
methods for nodes clustering (Wang et al., 2019 Bo et al. 2020 Zhu & Koniusz 202T).
Different from node-level learning. in graph-level learning. the samples are a set of graphs that can be organized into different groups. Classical methods for graph-level classification are often based on graph kernels (Vishwanathan et al. 2010 Yanardag Vishwanathan 2015) while recent advances are based on GNN (Wu et al. 2220 Rong et al. 2020). Researchers generally utilize various types
of GNN, e.g., graph convolutional networks (GCNs) (Kipf & Welling 2017) and graph isomorphism network (GIN) (Xu et al. 2019) to learn graph-level representations by aggregating inherent node
information and structural neighbor information in graphs, then they train a classifier based on the
learned graph-level representations (Zhang et al. 2018 Sun al. 2020) Wang al. 2021 Doshi

---

Under review as a conference paper at ICLR 2023
Nevertheless, collecting large amounts of labels for graph-level classification is costly in real-world, and the clustering on graph-level data is much more difficult than that on nodes and still remains an open issue. It thereby shows the importance of exploring graph-level clustering, namely partitioning a set of graphs into different groups such that the graphs in the same group similar while the graphs in different groups are dissimilar.
& Chepuri 2022
Previous research on graph-level clustering is very limited. The major reason is that it is difficult represent graphs as feature vectors or quantify the similarity between graphs in an unsupervised manner. An intuitive approach to graph-level clustering is to perform spectral clustering (Ng et al. 2001] over the similarity matrix produced by graph kernels (Kondor & Pan 2016 Du al. 2019 Togminalii et al., (219)) on graphs. Although there have been a few graph kernels such as random walk kernel (Gärtner et al. 2003) and Weisfeiler-Lehhie
kernel (Shervashidze et al. 2011), I), most of them rely on manual design that fails to provide desirable generalization capability for various types of graphs and produce satisfactory similarity matrices for spectral clustering, which will be demonstrated in Section 4.3
Another solution comes with the encouraging development GNNs. Some latest works such as GCNs (Kipf & Welling, 2017) and GIN (Xu et al., 2019) have been proven to be effective in learning node/graph-level representations for various downstream tasks, e.g., node clustering (Wang et al,
2017
Bo al. 2020 Liu et al. 2022) and graph classification (Sun et al. 2020 Sato et al.) 2021 You et al. 2021 thanks to the powerful generalization and representation learning capabi lity of deep neural networks. Therefore, it may be possible to achieve graph-level clustering by performing
classical clustering algorithms such as k-means (Hartigan & Wong] 1979) and spectral clustering
over the graph-level representations produced by various unsupervised graph representation learning
methods (Grover& & Leskovec, 2016 Narayanan et al. 2017 Adhikari et al. 2018: [Sun et al.) 2020)
Although the ffore-mentioned -Nsed unsupervised graph-level representation learning meth- ods have shown promising performance in terms of some down-stream tasks such as node clustering and graph classification, they do not guarantce generate effective features for the clustering tasks on entire graphs. In contrast, the graph-level clustering may benefit from an end-to-end framework that can learn ftustering-orientee rize our motivation here: 1) Graph-level clustering is an important problem but it is rarely studied, though there have been a lot works on graph-level classification and node-level clustering. 2) The performance of graph-kerneh followed by spectral clustering and two-stage methods (deep graph- level feature learning followed by k-means or spectral clustering) haven't been well explored. 3) An end-to-end deep learning based graph-level clustering method is expected outperform graph kernels and the two-stage methods because the feature learning is clustering-oriente propose novel graph clustering method called deep graph-level clustering (DGLC) in this paper. The proposed method is a fully unsupervised framework and yields the clustering-orieee graph- level representations via jointly optimizing two objectives: representation learning and clustering. The main contributions of this paper are summarized as follows.
features in the graph-level representation learning. We summa-
Therefore, we
We investigate the effectiveness of various graph kernels as well as unsupervised graph representation learning methods in the problem of graph-level clustering.
We propose an end-to-end graph-level clustering method. In the method, the clustering objective can guide the representation learning for entire graphs, which is demonstrated to be much more effective than those two-stage models in this paper.
We conduct extensive comparative experiments of graph-level clustering on six benchmark datasets. Our method is compared with five graph kernel methods and four outting-edge GNN representation learning methods, under the evaluation of three quantitative metrics and one qualitative (visualization) metric. Our method has state-of-the-art performance.
2 PRELIMINARIES
The notations used in this paper are shown in Table [ In the next two subsections, we briefly introduce graph kernels and GNN based graph-level representation learning methods. We will also illustrate how to apply them graph-level clustering.
2

---

Under review as a conference paper at ICLR 2023
Table 1: Notations for the main variables and parameters in this paper.
G
Graph set
G
Graph set in a minibatch
V
Node set
E
Edge set
X
Node features set
Neighhorhood set node
single graph
K
Number of GNN hidden layers
h
Learned feature for node in le-th GNN layer
at
Aggregated feature for node in 1-th GNN layer Mutual information estimator
(G)
Graph-level representaion
Jo.0
fe
Cluster projector
Cluster embedding
Number of clusters
Parameters of GNN
Parameters of mutual information estimator
Parameter of clustering network
2.1 GRAPH KERNELS
Graph kernels are techniques typically used in both supervised and unsupervised learning that ex- ploit graph topology. They aim to learn graph representation implicitly with predetermined graph sub-structures. For a graph G, after its sub-graphs }G.} are defined, the kernel is calculated accord- ing to the occurrences of the sub- sub-ggaaps of ). Namely, (Cy G,.) == F FG.. where Fe. desirable al., 2009). Random walk kernel (Vish-l wanathan et al. 2010), Shortest path kernel (Borgwardt & Kriegel 2005) ) to Subgraph matching ker- 2017 7 etc. For example, one of the most popular kernels is the Weisfeiler-Lehmar kernel (Shervashidze et al. 2011). It belongs to subtree kernel family and could scale up to large and labeled graphs. Weisteiler-Lehmae kernel built upon other base kernels through kernel to relabel the graph with not only the original label of each
denotes frequency. In recent years, much effort has been devoted to the identification sub-graphs ranging from Graphlet kernel (Shervashidze
nel (Kriege & Mutzel 2012), Pyramid match kernel (Nikolentzos
Peisfeierr-ehhmal test of isomorphism on graphs. The essen-
tial idea of Weisfeiler-Lehman vertex, but also the sorted set of labels of its neighbors (sub-tree structure). With runtime scaling only linearly in the number of edges of the graphs, Weisfeiler-Lehman kernel widely applied com- putational biology and social network analysis. However, Weisfeiler-Lehman kernel's 's hashing step is somewhat ad- ad-hoc, with performance varying from data to data (Kondor & Pan 2016). Another state-of- af-tth--rt algorithm is the shortest-path kernel (Borgwardt & Kriegel 2005 which is based on paths instead of conventional walks and cycles. By transforming the original graph into shortest- paths graph Ge,u. = (the number of occurrences of vertex and u connected by shortest-path e), avoids the high computational complexity of graph kernels based on walks, subtrees and cycles. In this paper, several graph kernels are selected as comparative models to test their efficiency on clus- tering. More specifically, we perform spectral clustering with the similarity matrices computed by graph kernels. One limitation is that existing graph kernels are not effective enough to quantify the similarity between graphs. In addition, most of them cannot take advantages of the nodes features and labels of graph. The related results and time complexity comparison can be found in Table 3 and Appendix A.5
2.2 UNSUPERVISED GRAPH-LEVER REPRESENTATION LEARNING
In recent years, GNN related models (Wu al. 2020 Zhou et al. 2020 have shown state-of-the-an
performance in many graph-data related tasks such as nodes cl classification
(Kipf & Welling 2017
Zhang et al., 2019) and graph classification (Zhang et al. 2018 Xu al. 2019: Sun et al. 2020). A number of graph representation learning methods have been proposed to handle the graph/node
classification and node clustering tasks. For example, Grover Leskoved (2016) proposed to learn low-dimensional mapping for nodes that maximally preserves the neighborhood information of nodes. Veličković al.] (2019) proposed learn node representations for node classification via maximizing the mutual information between the patch representations and summarized graph rep- resentations. Similarly, [Sun et al. (2020) utilized the mutual information maximization strategy and GIN (Xu et al.) (219) to learn graph representations for graph-level classifications, You et al. 2200 2021) took inspiration from the self-supervised learning to augment the graph data to con- struct positive/negative pairs, thereby learn effective graph representations with contrastive learning strategy (Chen et al. 2020).
It should be pointed out that existing graph representation learning methods rarely investigate the graph-level clustering task, as is far difficult than graph classification or node clustering. An intu- itive strategy is to perform k-means (Hartigan & Wong 1979) spectral clustering (Ng al. 2001)
3

---

Under review as a conference paper at ICLR 2023
on the learned graph-level representations given by those methods. Nevertheless, the clustering per- formance is not desirable as can be observed in Section 4.4] because the representations learned by those methods not guaranteed to be suitable or effective for graph-level clustering. There- fore, we present our DGLC method to investigate the way to learn clustering-oriented graph-level representations, of which the learning is guided by explicit clustering objective.
METHODOLOGY
3.1 PROBLEM FORMULATION
Given a set of n graphs, i.., 9 := {G1, Gi.iG,,,.,GG Gn}. where the i-th graph G, = (V,, E,) has node features X, {xx Joev, and X' == (2,,X...... X,). The graph-level clustering aims to partition the set & into a few non-overlapped groups, i..., G (()) (g( G(e) and (() for any & j. such that the graphs in the same group are similar while the graphs in different groups are dissimilar, without using any label information.
Since the original graph data may not have graph-level feature vectors or they often contain redun- dant and distracting information, more effective way is to perform clustering in latent space given by some representation learning methods. Therefore, we propose to learn latent representations and conduct clustering simultaneously, where the representation learning and clustering facilitate each other. We formalize the objective function for graph-level clustering as follows
L( 0)
+ Lejo (X.,))
(1)
In ( L, denotes the representation learning objective that aims to map the input data X, G into latent space via deep graph neural network with parameters Φ. Lej0 denotes the clustering objective on the representations 9o (X, x. 9) and associated with deep neural network with parameters 0 that may also contain the cluster centers or assignments. Note that there could be trade-off parameter between T.p and T. but we just ignore for convenience. We see that the objective L(Ø, 0) does not only learn cluster-oriented representations, but also directly produces clustering results. So there is no need to perform k-means or spectral clustering after the pure representation learning like those two-step models mentioned in Section 2.2
3.2 LEARNING GRAPH-LEVEL REPRESENTATIONS
To learn effective representations of the graphs, we take advantages of GNN (Kipf & Welling 2017; Xu al. 2019 Wu al. (020). GNN leverages the node information and structural information to learn representations for node or graph. GNN aggregates the neighboring information of each node itself iteratively, thus the learned features could capture both the inherent node information and its neighbors' information. Specifically, the learned feature h. for node v in the k-th layer can be formulated as follows
h (k) COMBINE (K)
(h(-- (k-1) h!*))
COMBINE()) (h(K-1) AGGREGATE(()) ((b((-)) : (())))))
where (R) denotes the aggregated neighbor features k-th layer, .V(v) is the neighborhood set of node v. Particularly, the initial representation h is set as the node features of v, i.e., x,, is worth noting that more global information could be obtained as the layer deepens, while some more gener- alized information would be possessed in the earlier layers (Xu et al. 2019). Therefore, considering the information from various depths of the network would help us get more powerful representa- tions for graph-level clustering tasks. Following the idea, concatenate the representation learned at each layer as
h CONCAT (Ih. (1)))) )
(10)
(3)
where h is concatenated representation for node and h is the representation learned in k-th layer. After that, utilize READOUT function obtain the graph-level representation, i.e.,
H a (G,) READOUT((H)))
4

---

Under review as a conference paper at ICLR 2023
where [Gy] denotes the number of nodes in Gj. Therefore, for the given graph dataset G == {G₃ G) in a batch, H₂(G) E I can be regarded as the learned graph-level representations, where ny number of graphs in batch, d, is the dimension of each hidden layer of GNN and K is the number of GNN layers. Note that we use the sum readout strategy in this work.
As the graph-level clustering is an unsupervised learning task, it important to learn more rep- resentative features in unsupervised manner. We follow (Hjelm et al.] (219) [Snn et al., (020) to achieve this by maximizing the mutual information between the representations of entire graphs and substructure, since it has been demonstrated as powerful unsupervised graph representation learning technique. Specifically, for the given graph datasets in batch G that follows an empirical probability distribution I' on the original data space, the estimator f of the mutual information (MI) over the global and local pairs is defined follows:
3. arg max
Σ GCG
E iEG
(h's Hg)G)) A -ip d.
G
where G is the number of nodes in G, i denotes single node in G. To.y can be parameterized by diseriminator network T with parameter vh. By using Sensen-Shannor MI estimator Nowozin et al. 2016), To.v can be formulated as:
e (h's (G); H (G))
(G)) Eel-sp(- (s); H Hs)s))) Exxelsp(TT. (hi, Hz(s))),, (6)
where s denotes the input (positive) sample, and s' denotes the negative sample from the distribution that is identical to distribution IP. Particularly, the combinations of global (graph-level) and local (node-level) representations in batch used to produce negative samples. sp(y) log(1 + e") indicates the softplus function. Note that we maximize the MI between graph-level and node- level representations, which facilitates graph-level representations as possible that is shared between node-level representations. It is intuitive that performing k-means or spectral clustering directly on the graph-level representations learned seems to be an applicable way, but it often tends to be trivial solution because the representations learned in this way solely are not guaranteed to be applicable for the graph-level clustering task that we focus this work.
contain much information
3.3 END-TO-END GRAPH-LEVEL CLUSTERING
To capture more suitable representations for graph-level clustering, we attempt to learn cluster- oriented representations by introducing an explicit clustering objective. Specifically, we propose clustering network connected with the graph-level features in the representation learning network described above. Then the graph-level features will projected to the cluster embedding in the low-dimensional latent space, which can be formalized as follows:
2; (H. (G,()))
where z, denotes the learned cluster embedding for graph Gj, and fo is the MLP-baser clustering projector with network parameter 0. Let (G) E xdd be the cluster embeddings in a batch, where d, is the dimension of cluster embedding layer. Subsequently, we take inspiration from (Van der Maaten & Hinton 2008 Xie et al. 2016) to define the graph-level cluster assignment
distribution Q based on Zo.e ( G)) as follows:
(1
11l) 2j 2j M. 112
Ozt 0.0 =
D
(8)
where Zj is the j-th column of Z (G), is the number of clusters. 14, is the t-th cluster center that can be initialized by k-means, and Qytlo. is the graph-level cluster assignment indicating the probability that graph Gj belongs to cluster f.. Next, we further define an auxiliary refined cluster assignment distribution / to emphasizes those assignments with high confidence in Q as follows:
2//0.0 ΣØ= 9itlo.0
Pjt
(9)
(93 0.8) Σド 9)4)o.0)
5

---

Under review as a conference paper at ICLR 2023
where P encourages pronounced gap between assignments with high and low probability in Q and can be regarded as pseudo labels for guiding the optimization of Q. Therefore, we can define the clustering objective by minimizing the KL-divergence between P and Q as follows:
Lejo, = (L(PII()
= Σ j=1
Pst log Pjt
(10)
4ftlo.0
Lejo aims force Q to approximate P. i.e. let guide the optimization of Q that the high confident assignment can be emphasized, which can also be regarded as a self-training strategy. By jointly optimizing Eq. and [O can construct an end-to-end deep graph-level clustering framework that simultaneously implements graph-level representation learning and clustering. The overall objective of DGLC in terms of minibatch optimization is follows
Lbacte ( 0,
L. vi (h's Ha (G)
Pje log
Pjt
(11)
45t/0.0
IEG
Tr
Lejo.
EXPERIMENTS
In this section, we evaluate the proposed method in comparison with several state-of-the-art com- petitors in graph-level clustering task. We first introduce the datasets and baseline methods used in the experiment and describe the detailed settings of network and parameters. Then, we demonstrate the effectiveness of our method through comprehensive experimental analysis.
4.1 DATASET DESCRIPTION AND BASELINE METHODS
Dataset: We use six well-known graph datasets in the experiment, including MUTAG] PTC-MR PTC-MM BZR ENZYMES C We summarize the information each dataset in Table More detailed information of each dataset refers the Appendix A.I
Table 2: Information of the six benchmark datasets.
Dataset name
Number of graphs
Range of nodes
Average nodes
Range of edges
Average edges
Classes
MUTAG
188
[10-28]
17.93
[20 66]
19.79
PTC-MR
344
[2 64]
14.29
[2- 142]
14.69
PTC-MM
336
[2 64]
13.97
[2 142]
14.32
2
BZR
405
[13-
35.75
[26 120]
38.36
2
ENZYMES
600
[26126) 126]
32.63
[2-298] 298]
62.14
6
COX2
467
[32-56]
41.22
[68 118]
43.45
2
Baseline methods: We compare our method with six state-of-the-ar graph kernel methods includ-
ing Random walk kernel (RW) /Vishwanathan et al. 2010), Ceisseiler-Lehmaal kernel (WL) (Sher-
vashidze et al. 2011), Optimal assignment based WL kernel (WL-OA) (Kriege et al.) 2016)) Shortest path kernel (SP) (Borgwardt & Kriegel| 20055). Lovasz-theta kernel (LT) (Johansson et 2014).
Graphlet kernel (GK) (Shervashidze et al. 2009). and four unsupervised graph-level representa- tion learning methods including InfoGraph (Sun et al. 2020). Gromov-Wasserser Wasserstein factorization (GWF) (Xu et al., (2022). Graph contrastive learning (GraphCL) (You et al. 2020). and Joint aug- mentation optimization (JOAO) (You et 202T)

---

Under review as a conference paper at ICLR 2023
4.2 EXPERIMENTAL SETTINGS
For the graph kernel methods we used, they are all normalized with the base graph kernel to be Vertex Histogram kernel if needed, then we directly perform spectral clustering (Ng et al. 2001] on the the similarity matrices produced by them to obtain the clustering results. Note that we also include the k- means (Hartigan & Wong 1979) performance of several graph kernels the Appendix [A.6] While for the unsupervised graph-level representation learning methods, we perform k-means (Hartigan Wong 1979) and spectral clustering on the learned graph-level representations. Particularly, for GWF (Xu al. 2022) not only follow the original paper to perform k-means, but also perform spectral clustering to evaluate its clustering performance.
To provide fair comparison in our experiment, we use exactly the same network architecture as our competitors of unsupervised graph representation learning (Sun et al. 2020; You et al., 2020 2021). i.c.. utilizing the Graph isomorphism network (GIN) (Xu et al. 2019) the backbone GNN. The cluster projector is constructed with a two-layer MLP-based fully connecco network. We use Adam the optimizer, the learning rate is chosen from [10-3 10-6, 61. the batch-size is set to 128 and the total running epoch is set to 20. Moreover, there are three important our method, i.e., the layer numbers of GNN, the hidden dimension dn of each GNN layer and the dimension de of the clustering layer. We evaluate the influence of different values of them on the graph-level clustering performance Appendix AA.3 due the limitation of the paper length.
in
To evaluate the clustering performance, we consider three popular metrics including clustering ac- curacy (ACC), normalized mutual information (NMI) and adjusted rand index (ARI). The detailed definition of the three metrics refer to the Appendix A.2 We utilize Pytorch Geometric (Fey & Lenssen 2019) and GraKeL. (Siglidis et al.) 2020) libraries to implement our method and other baseline methods. Note that we run all experiments 10 times with NVIDIA Tesla A100 GPU and AMD EPYC 7532 CPU, and report their means and standard deviations.
4.3 EXPERIMENTAL RESULTS
We compare the proposed DGLC method with 13 baselines and state-of-the-art methods on the six popular benchmarks. The experimental results are shown in Table 35 from which we have the following observations.
Table 3: Clustering performance (ACC, NMI, ARI) on MUTAG and PTC-MR. The best result is highlighted in bold.
MUTAG
PTC-MR
Method
ACC
NMI
ARI
ACC
NMI
ARI
Graph kernel followed by spectral clustering (SC)
RW Vishwanathan al./ [2010]-SC
77.65++0.00
30.81
30.26+0.00
56098=0.00
0.63+00.0
1.25+0.00
W1. Shervasiizze a 2011
+SC
73.40++0.00
14.50+0.00
21.20+0.00
52.91-0.00
0.23+0000
0..00
W1 Kriee et al. S016
67.55++0.00 19.64+0.00
11.40+0.00
59.30=0.00
1.77++000
2.95+0.00
SP Borgwardl Kregell
2005
+SC
72.87+00.00 10.2440.00
15.95+00000
56.69=0.00
1.04+0.00
0.50+0.00
Johansson et a 201
+SC
56.60:14.88
3.39
-0.62-+0.63
55.17=1.32
0.40=10.5
0.19+0.52
GK GK Shervashidze ot al.
2009
+SC
67.02++0.00
1.74++0.00
1.04++0.00
56.40=0.00
1.32++.000
0.31+0.00
Unsupervised graph representation learning followed by k-means (KM) und SC
InfoGraph KKM
77.95::1.41 35.22:1..47 30.95:13.03
54.79=:0.68
0.49:10.3
0.28:1.21
InfoGraph 2020
+SC
72,58++4.83 28.68++4.93
19.85+55.11
56.10=0.33
1.50++.226
0.20++0.13
GWF et
+KM
66.94+7.68 12.46+9.31
13.32+10.53
56.33-3.52
1.09+0.88
1.65+1.50
GWF
2022
+SC
73.92++4.30 18.35++..85
24.48+4.69
55.32=4.03
0.89+0.84
1.49+1.44
GraphCL
2020
+KM
77.07+:121 35.69422.3
28.9942.65
54.33=:0.76
1.15#0.55
0.16:0.29
GraphCL You al.
2020
+SC
73.22:12.66 32.19:12.05
23.4412.45
56.13=0.42
1.3110.30
1.1710.24
JOAO You et al.
2021
KKM
79.20:1072
36.32.13.03
33.74.1.65
56.39=0.18
0.5310.21
0.4110.01
JOAO You et al.
2021
+SC
70.7242.85
27.7311.23
17.1241..3
56.16=0.22
1.0340.33 0.1910.11
DGLC(Ours)
84.68.10.89 35.7542.51 47.0112.64
60.93-0.57
2.98-10.43 4.29-1..2
First, graph kernel based graph-level clustering approaches are effective on only few datasets, while achieving mediocre clustering performances on most datasets. For example, RW kernel performs well MUTAG and PTC-MR, but mediocre PTC-MM and BZR. While the opposite results

---

Under review as a conference paper at ICLR 2023
Table 4: Clustering performance (ACC, NMI, ART) PTC-MM and BZR. The best result is high- lighted in bold.
PTC-MM
BZR
Method
ACC
NMI
ARI
ACC
NMI
ARI
Graph kernel followed by spectral clustering (SC)
RW Vishwanathan et al.
2010+SC
60.711:0.00
0.97400.00
2.91:0.000
64.69::0.00 0.00+10.00
-0.15+0.00
Whervasashidz el al. 2011 +SC
62.20:1:.00
1.50+0.00 3.87+00.00
75.56+0.00
0.50+0.00
3.76:00.00
WL OA(Kriege et al. SSC
63.39:10.00 4.59100000
2.26::0.00
69.63:1:.00
5,6010.00
-8.67.0.000
SP Borgwardt & Kriegel 2005
+SC
62.20:10.00 163310.00
0.73+10.00
79.51 4.1340.00
3.97:10.00
1.T (Johanson et al.
2014
+SC
61.19+0.88
0.73+0.55 1.09+1.06
78.35+0.35
0.69+0.28
1,12+1.03
GK GK Shervashidze et al.
2009
+SC
62.20+00.00 1.63++0.00 0.73++0.0
61.23+33.6
1.061.221
3.13+3.74
Unsupervised graph representation learning followed by k-means (KM) and SC
InfoGiraph Sun et al.
2020)
+KM
61.48+1.00 2.35++0.83 3.61+1.45
63.62+22441
1.59+0.95
1.39+1144
InfoGraph ei al.
2020
+SC
6..9 2.12:10.99 4.5510.83
73.5342.66
3.6612.52
5.0413.12
GWF et al. 2022
+KM
53.37=3.118 0.30110.77
0.3811
53.0010.31
3.42:10.55
-0.76110.5
GWF et 2022
+SC
53.02=#1.66 0.36:10.28 0.211:0.9
52.76:10.80
3.4
-0.71=0.32
GraphCL et
2020
KKM
58.93:+0.74 0.27:10.15 0.60
71.43+4.09
1.04
3.07
GraphCL You
2020
+SC
62.09:10.56 2.141:0.43 3.36:1..7
12.8811.66
1.90:10.38
3,47::0.59
JOAO You ci 2021
+KM
59.04+00552
0.21+0.14 0.98+00.41
72.6444.26
1.37++1114 4.01+3..9
JOAO
2021
+SC
62.41+0.80
2.00+0.78 4.28+1.34
72.98+1.59
2.75+1.30 5.62+3.74
DGLCC(Ours)
63.30 2.70+0..45 5.53+0061
80.98:+0.00 9.79++0.2 20.53-+1.84
Table 5: Clustering performance (ACC, NMI, ARI) ENZYMES and COX2. highlighted in bold.
The best result is
ENZYMES
COX2
Method
ACC
NMI
ACC
NMI
ARI
Graph kernel followed by spectral clustering (SC)
RW Vishwanatnnn al.
2010
17.00++0.00
0.66++0.00
0.25++000
51.31 0.70=0000
00.92+0.00
WL Shervashidze et al.
TSC
21.00::0.00
3.09:+0.00
1.48+0.00
50.54=0.00
0.51=0.00
-0.40=0.00
(K-eeeKnege el al. 2SI6]4SC
20.00+10.00
1.35:+:0.00
0.32+0.00
50.75=0.00
0.51=0000 -0.37=10.00
SP Borgward & Kriegel, 2005
+SC
22,00=+0.00 2.57++0.00
1.69+00.00
52.03-0.00
0.13=0.00 0.01+00.00
LT Johansson et al. 2014
+SC
17.00:1.099
0.42:10.11 0.0010.000
77.52=0.59
0.26=0.34 0.17
GK Shervashidze cf al.
2009
+SC
17.07+0.13 0.80+0.25 0.00++0000
66.
0.02+00.00 0.08++0.17
U
Unsupervised graph representation learning followed by k-means (KM) and SC
InfoGraph Sun et _
KKM
22.06:10.98 2.40+t:.45 1.25+10.52
56.74=3.04 3.30-
0.17=00.10
InfoGraph Sun et all
20200 2020+SC
23.75++0.50 4.64++0.65 2.23++0.41
70.37-2.01
3.56=0.99 1.92+1.67
GWF et al.
2022
+KM
28.55110.20 6.02:10.55 3.1610.20
57.60-4.11 1.50=0.13
2.88
GWF a..
2022
+SC
25.66:11.57
5.241 1.7810.61
58.83-4.46 1.1620.41
1.45
GraphCL You et al.
2020
21.50++0.22 1.55++0.12 0.90+0.09
68.88-0.59
1.05=0.21
0.44-+0.57
GraphCL You
4SC
25.28
4.75::0.36 2.03:10.26
75.01=2.12 1.24=0.37
2.39+2.28
JOAO You 202T
21.66::0.77
1.60#1.001 0,94:10.22
70.56-2.03
1.19=0.34
0.44-10.43
JOAO You al.
+SC
24.65
4.8510.37 2.0710.18
76.46=0.61
1.43=0.77 2.35+2.49
DGL.C(Ours)
17.08 6.39+1.09 2.86+0.80)
78.28 0.17 2.38-0.99 6.79++..7
are observed on LT kernel. This is because graph kernels are mainly based on hand-crafted design and are not suitable for arbitrary datasets in practice. Second, the unsupervised graph representation learning methods show potential in handling graph-level clustering, For example. JOAO obtains en- couraging performance on MUTAG, BZR and COX2. GWF achieves state-of-the-ar performance on ENZYMES. Although such methods achieve promising graph-level clustering performance in many cases, they still suffer from the undesirable graph-level representations learned for clustering, i... their representation learning do not explicitly optimize for the clustering task. Third, the pro- posed DGLC method outperforms both types of the above solutions with a large margin in most cases. For example, DGLC outperforms the runner-up with 5.48% and 13.27% advantages MU- TAG in terms ACC and ARI, and with 1.47%, 5.66% and 14.91% advantages on BZR in terms of ACC, NMI, and ARI. This fully demonstrates the effectiveness of method. Compared with
8

---

Under review as a conference paper at ICLR 2023
graph kernel based approaches, DGLC is general for different types of graph data. Compared with the latest unsupervised graph representation learning approaches, DGLC has a clear clustering objective in the optimization and thus tends to learn ctutering-orientie graph-level representations and achieves state-of-the-a performance.
4.4 QUALITATIVE STUDY
In this section, conduct qualitative study to provide visual comparison for the graph-level clustering. Specifically, we compare our method with several state-of-the-art unsupervised graph representation learning methods including InfoGraph, GWF, GrahCI. and JOAO by utilizing SNE (Van der Maaten & Hinton] 2008) and visualize their learned graph-level representations on MUTAG and ENZYMES. The visualization results are shown in Figure T
We can observe that
InfoGraph
(b) GWF
(c) GraphCL
(d) JoAo
(e) DGLC
(a) InfoGraph
(b) GWF
GraphCL
(d) JOAO
(c) DGLC
Figure 1: t-SNE visualization of the learned graph-level representations of our methods and other unsupervised graph representation learning methods. The first row is the visualization for MUTAG, while the second row is for ENZYMES.
compared with other methods, DGLC CC explicitly reveals more compact intra-class structure and more distinct inter-class discrepancy. For example, the learned representations of the two classes in MU- TAG are more separated our method compared others. Besides, we can find that InfoGraph, GraphCL and JOAO fail to capture good clustering structure for ENZYMES, while GWF and ours do. In general, the visualization results of the learned graph-level representations also support the effectiveness of our method.
4.5 PARAMETER SENSITIVITY ANALYSIS AND ABLATION STUDY
To evaluate the robustness of DGLC and the effectiveness of each component, we conduct the param- eter sensitivity analysis and ablation study. Please see Appendix A.3 and A.4 for the experimental results and discussions due the limitation of the paper length.
4.6 COMPUTATIONAL TIME COMPARISON
We also demonstrate the time efficiency of DGLC by comparing the running time with several graph kernels and unsupervised graph representation learning baselines. Please see Appendix A.5 for the experimental results and discussions due to the limitation of the paper length.
5 CONCLUSION
This work has studied the problem of graph-level clustering and proposed an end-to-end deep graph- level clustering method based deep graph neural network. The proposed DGLC method leverages the powerful representation learning capability of GIN and defines an explicit clustering objective to help learn cluster-favor representations for graph-level clustering. We compared the proposed method with two types of baselines, one is based on graph kernels followed by spectral clustering and the other is based on graph-level representation learning followed by k-means and spectral clustering. The experiments on six graph datasets have showed that our method has much higher clustering accuracy than the baselines.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B Aditya Prakash. Sub2vec: Feature learn- ing for subgraphs. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 170-182. Springer, 2018.
Smriti Bhagat, Graham Cormode, and S Muthukrishnan. Node classification in social networks. In Social Network Data Analytics, pp. 115-148. Springer, 2011.
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. Proceedings of The Web Conference 2020. pp. 1400-1410, 2020.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. In Proceedings of the IEEE International Conference on Data Mining, pp. 8-pp. IEEE, 2005.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Transactions on Knowledge and Data Engineering, 3009):1616-1677 2018.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the International Conference on Machine Learning, pp. 1597-1607. PMLR, 2020.
Siddhant Doshi and Sundeep Prabhakar Chepuri. Graph neural networks with parallel neighborhood aggregations for graph classification. IEEE Transactions on Signal Processing, pp. 1-14, 2022.
Simon Du. Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in Neural Information Processing Systems, 32, 2019.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.0244 2019.
Thomas Gärtner, Peter Flach, and Stefan Wrobel, On graph kernels: Hardness results and efficient alternatives. In Learning Theory and Kernel Machines, pp. 129-143. Springer, 2003,
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neu- ral message passing for quantum chemistry. In Proceedings of the International Conference on Machine Learming. pp. 1263-1273 PMLR, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 855-864, 2016.
John Hartigan and Manchek A Wong. Algorithm as 136: k-means clustering algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), 2801)1100-108, 1979.
Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchilee Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In Proceedings of the International Conference on Learning Representations, 2019.
Fredrik Johansson, Vinay Jethava, Devdatt Dubhashi, and Chiranjib Bhattacharyya. Global graph kernels using geometric embeddings. Proceedings of the International Conference on Machine Learning, pp. 694-702. PMLR, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. Proceedings of the International Conference on Learning Representations, 2017.
Risi Kondor and Horace Pan. The multiscale laplacian graph kernel. Advances in Neural Information Processing Systems, 29, 2016.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. arXiv preprint arXiv: /206. 6483, 2012.
10

---

Under review as a conference paper at ICLR 2023
Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. On valid optimal assignment kernels and applications to graph classification. Advances in Neural Information Processing Systems, 29, 2016.
Junying Li, Deng Cai, and Xiaofei He. Learning graph-level representation for drug discovery. arXiv preprint (ttv:/770.03355 2017.
Zhiping Lin, Zhao Kang, Lizong Zhang, and Ling Tian. Multi-view attributed graph clustering.
IEEE Transactions on Knowledge and Data Engineering, 2021.
Yue Liu, Wenxuan Tu, Sihang Zhou, Xinwang Liu, Linxuan Song, Xihong Yang, and En Zhu. Deep graph clustering via dual correlation reduction. In Proceedings of the AAAI Conference Artificial Intelligence, 2022.
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint 1707.00000 2017.
Mark EJ Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577-8588 2006.
Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems, 14, 2001.
Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Matching node embed- dings for graph similarity. In Thirty-first AAAI conference on artificial intelligence, 2017.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. Advances in Neural Information Processing Systems, 29, 2016.
Erlin Pan and Zhao Kang. Multi-view contrastive graph clustering, Advances in Neural Information Processing Systems,
2021.
Yu Rong, Tingyang Xu, Junzhou Huang, Wenbing Huang, Hong Cheng, Yao Ma, Yiqi Wang, Tyler Derr, Lingfei Wu, and Tengfei Ma. Deep graph learning: Foundations, advances and applications. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 3555-3556 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341. SIAM, 2021.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Proceedings of the Artificial Intelligence and Statistics, pp. 488-495. PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-ehhman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. Grakel: A graph kernel library in python. Journal of Machine Learning Research, 21(54):1-5, 2020.
Amarnag Subramanya and Jeff Bilmes. Entropic graph regularization in non-parann non-parametric semi- supervised classification. Advances in Neural Information Processing Systems, 22, 2009.
Fan-Yun Sun, Jordon Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. Proceed- ings of the International Conference on Learning Representations, 2020.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-Lópzz, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-Iehmar graph kernels. Advances in Neural Information Processing Sys- fems, 32, 2019.
11

---

Under review as a conference paper at ICLR 2023
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research,
2205,, 2008.
Petar Veličković, William Fedus, William Hamilton, Pictro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In Proceedings of the International Conference on Learning Repre- sentations, 2019.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201-1242, 2010.
Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginalized graph autoencoder for graph clustering. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 889-898, 2017.
Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. Attributed graph clustering: a deep attentional embedding approach. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 3670-3676, 2019.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, pp. 3663-3674, 2021.
Bang Wu, Xiangwen Yang. Shirui Pan, and Xingliang Yuan. Adapting membership inference tacks to gnn for graph classification: Approaches and implications. In Proceedings of the IEEE International Conference on Data Mining, pp. 1421-1426. IEEE, 2021.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2020.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In Proceedings of the International Conference on Machine Learning, pp. 478-487. PMLR, 2016.
Dongkuan Xu, Wei Cheng. Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information- aware graph contrastive learning. Advances in Neural Information Processing Systems, 34:30414- 30425, 2021.
Hongteng Xu, Jiachang Liu, Dixin Luo, and Lawrence Carin. Representing graphs via gromov- wasserstein factorization. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? Proceedings the International Conference on Learning Representations, 2019.
Shuicheng Yan, Dong Xu, Benyu Zhang, Hong-Jiang Zhang, Qiang Yang, and Stephen Lin. Graph embedding and extensions: A general framework for dimensionality reduction. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 29(1):40-51, 51, 2006.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1365-1374, 2015.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 11.5812-58233 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning auto- mated. In Proceedings of the International Conference on Machine Learning, pp. 12121-12132.
PMLR, 2021.
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heteroge- neous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 793-803, 2019.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference on Artificial Intelli- gence, volume 32, 2018.
12

---

Under review as a conference paper at ICLR 2023
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In Proceedings of the International Conference on Learning Representations, 2021.
A APPENDIX
A.1 DETAILED INFORMATION OF DATASET
We provide the detailed information of six graph datasets used in our experiment here:
MUTAG is compound dataset that contains 188 compounds, which are grouped into categories based on the mutagenic effect of them to a bacterium. Note molecules possess natural graph structure, where they are expressed by average 17.93 nodes (for atoms) and 19.79 edges (for chemical bonds).
PTC-MR and PTC-MM are the subset of PTC dataset, which is a compound dataset that divided into 2 categories based the carcinogenicity rodents. Note that PTC-MR tains 344 compounds with average 14.29 nodes and 14.69 edges, while PTC-MM contains 336 compounds with average 13.97 ndoes and 14.32 edges, respectively.
BZR is the ligand dataset for benzodiazepine receptor, which divided into classes according to the activity and inactivity of compounds. Note that BZR contains 405 graphs in total with average 35.75 nodes and 38.36 edges per graph.
ENZYMES contains 600 protein data for 6 classes of enzymes, with 100 proteins per class. Each protein data can be represented as a graph with average 32.63 nodes and 62. 14 edges.
COX2 consists of 467 inhibitor for cyclooxygenase-2 and are divided into classes based on whether the compounds are active or inactive. Note that each graph in this dataset is with average 41. 22 nodes and 43.45 edges.
A.2 DEFINITION OF THREE CLUSTERING METRICS
In this section, we introduce three clustering metrics used in this paper, with yy and ûز denoting the true labels and the predicted labels for graph G, respectively.
Clustering accuracy (ACC): ACC is expressed as the comparison of the true labels and predicted labels leveraged on sample size n, which is defined as follows:
ACC = E 8 (1950s) where 5(x, y) = {
if = otherwise
(12)
Normalized mutual information (NMI): NMI score scales the mutual information scores by some generalized mean of entropy of true label set l and cluster label set C. It can be formalized as follows:
7(2: NMI(2,C) = (H - H(C))/2
(13)
where I(9; = H()) + H(C) (S2, C) denotes the mutual information between and C, and (--) is the information entropy.
Adjusted rand index (ARI): ARI score is an adjusted score of Rand index (RI) for chance. RI is also similarity measure by considering all pairs of samples and counting pairs that are assigned in
13

---

Under review as a conference paper at ICLR 2023
the same or different clusters in the predicted and true labels. ARI can be formalized follows:
(RI
Expected RI)
ARI
(max RI)
Expected RT)
Eij
Σ
a
n
(14)
2
2
2
2
Σ,
ai 2
+
Σj
hi 7/2
Σ,
ag 2
Σ,
b
/ 2
2
Di=ı Rig. Rij denotes an entry from the contingency table of cluster i and class j. r and are numbers of clusters and classes.
where Ei= Rijs b,
Note that ACC and NMI range from [0, 1]. while ART ranges from [-1,1]. The higher values of ACC, NMI and ARI represent the better clustering performance.
A.3 PARAMETER SENSITIVITY ANALYSIS
We analyze the sensitivity of DGLC the hyperparameters, i.e., the hidden dimension da of GNN layers, the embedding dimension d2 of clustering layer and the number of GNN layers. Here we take MUTAG and PTC-MR datasets as the example to evaluate the influence of the change of d, and d₂ values. Specifically, we select the values of d, in [16, 32.... 256] and d, in [5, 10, .0.....300 30], the
results are shown Figure We can observe that the accuracy on both datasets are relatively stable, showing little fluctuation when parameters vary. In contrast, NMI and ARI are of high performance when the selection of parameters are moderate. In general, DGLC shows robust performance against the two parameters. Nevertheless, recommend to choose d, from 10 to 25 and d,, from 32 to 128 to obtain better clustering performance in practice. Except for the ones mentioned above, we further conduct the sensitivity analysis the number of GNN hidden layers PTC-MR and BZR). We vary the number of GNN hidden layers in [2, 3, 10]. The experimental results are shown in Figure 3 could be that PTC-MR is quite stable for all three metrics. For MUTAG and BZR, whereas, DGLC shows better performance when setting the number of GNN hidden layers and 5. In general, DGLC obtains relatively stable performance different numbers of GNN layers, despite fluctuations at some specific fetch values.
three datasets (MUTAG,
MUTAL ACE
MUFAG NM1
MUTAG AR
0.4
20
50
16
16
124
124
255
MUTAG
(b) MUTAG NMI
(c) MUTAG ARI
0.53
8.6
ALC
8m
0.02
8xC
52
32
(d) PTC-MR ACC
(c) PTC-MR NMI
(c) PTC-MR ARI
Figure 2: Sensitivity analysis of accuracy, NMI and ARI regarding the dimension d, of GNN hidden layers and the embedding dimension d, of clustering layer on MUTAG and PTC-MR datasets.
14

---

Under review as a conference paper at ICLR 2023
01
08
63
(a) MUTAG
PTC-MR
(c) BZR
Figure 3: Sensitivity analysis of ACC, NMI and ARI regarding the number of GNN hidden layers on MUTAG, PTC-MR and BZR datasets
A.4 ABLATION STUDY
In this section, we conduct experiments to evaluate the influence of each proposed strategy our method. Specifically, we construct four degradation models of our method by respectively removing some components of it. There are:
D We remove the clustering loss and joint training strategy of DGLC and evaluate the model by performing k-means on the learned graph-level representations, i.e. the model can be regarded InfoGraph in this way.
DGT.C.a: We keep the clustering loss and joint training strategy while directly using k- means to produce the clustering results instead of producing the clustering labels with the cluster label assignment Q.
DGLCas: We degrade DGLC two-stage model, i.e., train the model by respec- tively optimizing the graph representation learning objective and clustering objective. The clustering results still obtained from the graph-level cluster assignment in the second training stage.
Table 6: Clustering performance (ACC, NMI, ARI) on MUTAG and BZR. The best result high-
lighted in bold.
MUTAG
BZR
Method
ACC
NMI
ARI
ACC
NMI
ARI
DGLCa1
1..95
35.22+3.47
30.95+3.03
63.6242.41
1.59+0.95
1.39-1.444
DGLCa2
80.50+2.34
32.52+3.65
37.16+5.55
66.6113.14
1,98#1.29
4.32+2.54
DGLCas
81.48+2.31
30.89+3.98
38.3446.61
73.8742.58
2.9242.30
5.35
DGLC
84.6810.89
35.75+2.51
47.0112.64
80.9810.60
9.7910092
20.53
We run experiments on MUTAG and BZR to evaluate their performance. Table 6 summarizes the experimental results, from which we have the following observations:
Both DGLCaz and DGLC,a significantly outperform DGLC,,, which fully suggests that learning flustering-orientee representations would benefit graph-level clustering.
Producing clustering results from the graph-level cluster assignment Q is reasonable as the clustering performance degrades when directly performing k-means on the learned cluster embeddings.
Joint training with representation learning and clustering objectives yields better clustering performance. For example, DGLC outperforms DGLC,ss by 3.20%, 4.86%, 8.67% in terms of ACC, NMI and ARI on MUTAG.
15

---

Under review as a conference paper at ICLR 2023
A.5 COMPUTATIONAL TIME COMPARISON
In this section, we compare the proposed DGLC with some baseline methods to demonstrate its effi- ciency in time consuming. Specifically, for graph kernels, we select RW VWVisshwanathan al. 2010).
WL/Shervashidze et al. (01TT) SP(Borgwardi & Kriegel 2005) and LT@Johansson et al. (014) as
our competitors. For unsupervised graph representation learning methods, we select GWF (Xu al. 2022) and InfoGraph (Sun et al. 2020). Note that we run 20 epochs for GWF, InfoGraph and DGLC for fair comparison. [able[]|shwws the running times of each method on six benchmark datasets used in this paper. We can see that RW, LT and GWF are quite time consuming, especially on datasets like ENZYMES and COX2 that contain numerous nodes and edges. In contrast, WL, SP, InfoGraph and DGLC are much more efficient compared with them and have comparable time efficiency.
Table 7: Running time comparison (in seconds) on the six benchmark graph datasets.
Method
MUTAG PTC-MR
BZR
PTC-MM ENZYMES
COX2
WVisswaannnnnnn et al.
2010'+SC
12.29
29.29
76.34
25.44
2346.51
2457.56
(SShersvas et al.
2011
+SC
2.19
4.97
9.57
7.15
13.43
10.65
SP
Borgwardi & Kregell
20055
+SC
3.60
5.38
25.49
5.08
53.75
32.39
Johhnsssonn et al.
2014
+SC
88.28
160.86
860.70
552.66
9117.17
6016.26
InfoGraph Sun et al.
2020
+KM
9.23
10.96
23.42
11.48
29.37
28.99
InfoGraph Sun
2020
+SC
35.96
96.60
165.48
101.2
313.70
300.84
GWF et al.
2022
+KM
477.48
830.26
2480.76
803.81
3668.92
2945.12
GWF(XU et 2022
+SC
566.41
911.37
2591.73
896.44
3954.87
3132.67
DGLC
10.16
12.12
25.66
12.84
31.87
30.50
A.6
k-MEANS PERFORMANCE OF GRAPH KERNELS
Here provide m-manss performance of some Graph kernels, including. RW (Viswwanntna al.
2010
Whhevvvvas et al., 2011), WL-OA (rriege et al. (2016), and SP(Borgwardt & Kriegel
2005
The experimental results shown in Table 9 10 and the proposed DGLC method
outperforms them significantly.
Table 8: Clustering performance (ACC, NMI, ARI) on MUTAG and PTC-MR. The best result is highlighted in bold.
MUTAG
PTC-MR
Method
ACC
NMI
ARI
ACC
NMI
ARI
Graph kernel followed k-means (KM)
RW
Vishwanathan al.
2010|KKM
77.66=0.00
30.82+00.0
30.26+0.000
51.16:#0.00
0.19=0000
-0.55+0.00
WL
Shervashidze et al.
2011
KKM
73.94=10.00
15.51+10.00
22.25:10.00
57.56:10.00 1.10:1.00
1.89:10.00
WL
Krieeee et al. 2016 KKM
73.94110.00
16.92:10.00
22.42:10.00
05.81
0.59+0.00
0.99:0.000
SP
Borgwardt & Kriegel
2005 KM
76.06=0.00 15.38+0.00 25.11110.00
59.30=10.00
1.87+0.00
2.73+0.00
DGLC(Ours)
84.68=0.89 35.75-12.51 47.0112.64
60.93
2.98110.33 4.29-0.52
A.7 EXPERIMENT ON LARGE-SCALE DATASET
To validate the effectiveness of the proposed method on large-scale graph datasets, we supplement two more datasets in our experiment. Specifically, we choose NCI1, NC1109, and COLLAB datasets to conduct experiment, the detail information of the three datasets are shown in Table [1] The experiment results are shown in Table 12 and Table [3 We can see that almost graph kernels show low efficiency and bad clustering performance when handling large-scale datasets, some of them too time consuming. While the proposed DGLC method shows superiority compared with graph kernels and graph representation learning methods. DGLC obtain the best clustering performance in most cases. Besides, the experiment on COLLAB, which contains 3 classes, also demonstrates the effectiveness of the proposed DGLC method in processing datasets containing more than 2 classes.
16

---

Under review as a conference paper at ICLR 2023
Table 9: Clustering performance (ACC, NMI, ARI) on PTC-MM and BZR. The best result is high- lighted bold.
PTC-MM
BZR
Method
ACC
NMI
ARI
ACC
NMI
ARI
Graph kernel followed by k-means (KM)
R
Vishwanathan
2010
55.06=00.00
0.02++0.00
0.00=0.000
58.52++0.00
0.19+00.00
-1.55++0.00
WL Shervashidze et al.
201T +KM
58.63:10.00
0,8210.00
2.15=0.00
68. 1510.00
0,9810.00 5.1710.00
Kriieee ul.
2016 +KM
58.0440.00
0.81+4.000
1.93=0.00
67.9040.00
2.17=0.00 -6.78+0..0
SP Borgwardt & Kriegel,
2005 KKM
61.01+10.00
0.85+0000
2.67=0.00
65.4341.000
0.27+00.00 2.364:0.00
DGLC(Ours)
63.30::081
2.70-0.45
5.53=0.61
80.98:10.60 9.79-10.2 20.43
Table 10: Clustering performance (ACC, NMI, ARI) ENZYMES and COX2. The best result is highlighted in bold.
ENZYMES
COX2
Method
ACC
NMI
ARI
ACC
NMI
ARI
Graph kernel followed by k-means (KM)
RW Vishwanathan et al.
2010+*KM
23.17::0.00
2.50:10.00
1.7410.00 53.96:00.00
0.60:10.00
-1.68
WL
Shervashidze
2011
KKM
21.50=10.00 2.18+0.00
0.96=0.00 50.96=00.00
0.541:000
-0.33
WL-
WL
OA ul.
2016|+KM
20.83:10.00 1.68:0.00
0.55
50.75400.00
0.51+00.00
-0.37
SP
Borgwardt
Kriegel
2005 +KM
22.17+0.000
2.79+0.00 1.70++0.00
52.03+0.00
0.13+0.00
0.01+0000
DGLC(Ours)
27.08:1149 6.39111.09 0.80 78.28-0.17 2.38:10.99 6.79113.37
Table 11: Information of the three large-scale datasets.
Dataset name
Number of graphs
Average nodes
Average edges
Classes
NCII
4, 1
29.87 14.29 2457.78
32.30
2
NCI109
4,127
14.69
2
COLLAB
5,000
74.49
3
Table 12: Clustering performance (ACC, NMI, ARD) on NCII and NCI109. The best result is highlighted in bold. N/A denotes the results are unavailable (out of memory or the running time over 24 hours).
NCII
NC1109
Method
ACC
NMI
ARI
ACC
NMI
ARI
Graph kernel followed by spectral clustering (SC)
RW
Vishwanathan et al.
2010
+SC
N/A
N/A
N/A
N/A
N/A
N/
Shervashidze et al.
2011
50.05
0.00+10.00
0.00+10.00
50.39=0.00
0.01=0.00 0.00-1.000
SP Borgwardt & Kriegel.
2005
+SC
50.10.10.00
0.10:10.00 0.00100000
52.26-0.00 0.33-0.00 0.1910.00
LT Johansson al.
2014 SSC
N/A
N/A
N/A
50.47-0.29 0.01-0.01 -0.01
U Unsupervised graph representation learning followed by k-means (KM)
and SC
InfoGraph Sun et al.
2020
54.1112.15 1.18 0.85+1087
54.38=1.85 1.25=0.74 0.89-10.88
InfoGraph Sun et al.
2020
+SC
54,87+1.68
0.93+:0.56 1.04:1.76
54.67=1.93 1.08=0.52
1.00=1.80
GraphCL You et al.
2020
+KM
55.37+11.6 0.47:+0.28
0.99++0.22
55.37=1.68 1.79-0.93
1.11
GraphCI. You al.
2SC
55.93++.224 0.61+0.63
1.08+00799
56.29-2.22
2.12+1.16
2.48+22.9
JOAO You et al.
202
KM
51.12:1..77 0.43:10.18
0.0510003
56.20=0.58
1.73-0.72
1.54
JOAO You et al.
202
+SC
51.48-42.98 0.88+11.22 0.40+11.7
56.30-0.85
4.61=10.43
1.8140.44
DGLC(Ours)
57.69442.31 2.50-10.89 2.39
56.36-2.31
1.94-10.9
1.81+1.38
17

---

Under review as a conference paper at ICLR 2023
Table 13: Clustering performance (ACC, NMI, ARI) on COLLAB. The best result is highlighted in bold. N/A denotes the results are unavailable (out of memory or the running time over 24 hours).
COLLAB
Method
ACC
NMI
ARI
Graph kernel followed by spectral clustering (SC)
RVViswaann et al. 2010)+SC
N/A
N/A
N/A
Shervvsssed et al.
201T +SC
53.20=10.00
1.96:10.00
0.53:10.00
Borgwaard & Kriegel 20005
4SC
48.72:10.00
17.91:10.00
13.93:10.00
LT Johansson et al. DSC
N/A
N/A
N/A
Unsupervised graph representation learning followed by k-means (KM) and SC
InfoGraph SSn Sun et al.
20M0)+KM
59.64
14.40+22.33
6.61 2.22
InfoGraph Sun al. SSC
60.92++2.49
15.37++3.28
9.33++3.45
GraphCL You et al.
2KM
58.02++1.22
17.81+1.94
11.33+00.56
GraphCL You et al.
20C0)+SC
57.83+0.61
1..9
10.10:0..65
JOAO You et al.
2021
58.34
18.73:12.62
11.06:11.79
JOAO You et al.
2021 +SC
57.8440.88
17.12+2.11
10.55+0.84
DGLC(Ours))
61.15
19.98
12.17+2..3
18


Reviews:
[{"review_id": "gjk9wwABZtb", "reviewer": "Reviewer_RqLm", "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": "This paper mainly tackles the graph-level clustering problem by proposing a novel method called Deep Graph-Level Clustering (DGLC) to learn graph-level representations and maximize the mutual information between the representations of entire graphs and substructures. Specifically, a clustering objective is proposed to guide the representation learning for the graph via pseudo labels. In addition, the authors analyze the effectiveness of graph kernel-based methods and unsupervised graph representation learning methods.", "summary_of_the_review": "This paper mainly tackles the graph-level clustering problem by proposing a novel method called Deep Graph-Level Clustering (DGLC). Despite a few grammar mistakes and typos, the presentation of this paper is good as most parts of the paper are easy to follow. The novelty of this paper is limited. The proposed method simply combines DEC[1] and InfoGraph [2]. In addition, the motivation of the proposed method is not strong enough. The authors mainly focus on discussing the challenges of the graph kernel-based methods and unsupervised learning-based methods on graph-level clustering problems, while the other existing methods, such as InfoGraph, have already addressed most of these challenges (it’s difficult and ineffective to measure the similarity between graphs for graph kernel-based methods and some existing methods do not utilize the label information to better represent graphs in latent space). In the experiment, the results show the effectiveness of the proposed method over SOTA methods, and the data sets and the code are publicly available.\nIn the experiment, the authors categorize InfoGraph as an unsupervised method, but InfoGraph consists of a supervised loss term considering the label information. It is a little bit unfair to measure the performance of InfoGraph in the unsupervised setting by simply removing the supervised loss term. In addition, the proposed method is similar to InfoGraph, and the main difference is that DGLC benefits from the joint training strategy, while InfoGraph doesn’t. In Table 7, the authors show the running time of the proposed method and SOTA methods. Why does InfoGraph+KM take more time than DGLC? DGLC and InfoGraph both share the same graph-level representation learning strategy, while InfoGraph does not have the clustering module during the training (if KM or SC is only used after the training stage is over) and DGLC consists of a clustering module at the training stage. It seems that the running time of InfoGraph should be smaller than DGLC. \nIn the experiment, the numbers of graphs in all data sets are too small. The authors should experiment on some large graph data sets, such as RDT-M5K data set or QM9 data set.\nOne minor question: How do you get the negative sample s' in equation 6?\n\n\n[1] Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In Proceedings of the International Conference on Machine Learning, pp. 478–487. PMLR, 2016.\n[2] Fan-Yun Sun, Jordon Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semisupervised graph-level representation learning via mutual information maximization. In Proceedings of the International Conference on Learning Representations, 2020.\n", "strength_and_weaknesses": "Strength:\n1.\tThe experimental results show the effectiveness of the proposed method over SOTA methods.\n2.\tThe paper is well-organized. The presentation of this paper is good, and most parts of the paper are easy to follow.\n3.\tThe datasets are publicly available, and the proposed method is easy to implement.\nWeakness:\n1.\tThe novelty of this paper is limited. The proposed method simply combines DEC[1] and InfoGraph [2].\n2.\tSome grammar mistakes and typos should be corrected, such as in the first paragraph on page 6, “which is also can also be regarded as a self-training strategy” and the missing conjunction ‘and’ in the sentence below equation 2.\n3.\tThe motivation of the proposed method is not strong enough.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "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": "8rpIX45ECe", "reviewer": "Reviewer_jD5G", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "In this paper, the authors aim to solve the measurement problem of graph-level clustering, and proposes an end-to-end method to jointly optimize graph representation and clustering, and the clustering goal can guide the learning of the entire graph, which is more effective than two stages.", "summary_of_the_review": "The motivation for this paper is that graph-level similarity is difficult to measure, and the solution is to map to a low-dimensional space (represented by a graph) and then measure similarity through an MLP layer, which lacks innovation. In addition, the proposed graph clustering method lacks novelty, and the related work does not summarize the previous graph clustering work, and the experiment is relatively insufficient.", "strength_and_weaknesses": "Strength: An end-to-end method is proposed to jointly optimize the two modules of graph representation and clustering. \nWeaknesses: \n(1) The motivation of this paper is that the similarity of the graph level is difficult to measure, which is a very common question that most people have asked. The proposed measurement method is not novel, and the only thing is to reduce the dimensionality of the feature.\n(2) As far as I know, there are many works on graph clustering before, which are not mentioned in the related works of this article.\n(3) The graph representation module of the proposed method is the previous work, and the clustering module is also the previous DEC clustering method. It's more like putting together previous work, which is not innovative enough. \n(4) In the experimental part, there is no graph-level clustering work for comparison. Some of the methods compared in this paper are graph representation and k-means or SC, so whether other graph representation methods plus the clustering method proposed in this paper (that is, DEC) are better than the effect of this paper.", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "3rPMQRf7QB", "reviewer": "Reviewer_vbKc", "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": "The paper proposes a new end-to-end deep learning method for graph clustering. The goal is to partition a set of graphs according to the similarities of their structures, while learning a graph-level representations. Mutual information theory is exploited in order to maximize within cluster similarities, while penalizing the between clusters similarity\t", "summary_of_the_review": "Overall, I don't see major flows in the paper. The proposed method brings an innovative component, while the experiments could benefit from improvements. ", "strength_and_weaknesses": "The method is well supported by a solid theoretical foundation. While not being an entirely novel idea, the method efficiently combines different elements resulting in an innovative approach. I think the experiments could be more comprehensive. Some general comments are given below.\n\t\n- The authors could better elucidate the contribution of the node label type in their approach. While they mention the label information is not used in the clustering, it would be useful to compare the impact of categorical vs continuous node labels. This is relevant both on the theoretical and experimental side. From the experimental perspective, they chose kernels which cannot handle the continuous node labels, making the comparison not fully fair with the deep learning approaches. \n\n- Only using datasets with 2 classes is quite limiting. Those data are typically used for classification, and I believe 2 classes are not enough to assess the potential of clustering based methods, since the granularity and differences among the classes itself are limited\n\n- Some benchmark datasets as well as methods are missing. On the graph kernels side, NCI1 and NCI109 datasets should a least be included. Furthermore, optimal assignment based kernels could also be integrated in the comparison. Additionally, many graph kernels also provide a feature representation, therefore one could also use k-means on these  for a fair comparison. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject