HC-GAE: The Hierarchical Cluster-based Graph Auto-Encoder for Graph Representation Learning
Authors: Lu Bai
Zhuo Xu
Lixin Cui
Ming Li
Yue Wang
Edwin Hancock
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Auto-encoder
Graph Neural Networks
Primary area: graph_neural_networks

Abstract: Graph Auto-Encoders (GAEs) are powerful tools for graph representation learning. In this paper, we develop a novel Hierarchical Cluster-based GAE (HC-GAE), that can learn effective structural characteristics for graph data analysis. To this end, during the encoding process, we commence by utilizing the hard node assignment to decompose a sample graph into a family of separated subgraphs. We compress each subgraph into a coarsened node, transforming the original graph into a coarsened graph. On the other hand, during the decoding process, we adopt the soft node assignment to reconstruct the original graph structure by expanding the coarsened nodes. By hierarchically performing the above compressing procedure during the decoding process as well as the expanding procedure during the decoding process, the proposed HC-GAE can effectively extract bidirectionally hierarchical structural features of the original sample graph. Furthermore, we re-design the loss function that can integrate the information from either the encoder or the decoder. Since the associated graph convolution operation of the proposed HC-GAE is restricted in each individual separated subgraph and cannot propagate the node information between different subgraphs, the proposed HC-GAE can significantly reduce the over-smoothing problem arising in the classical convolution-based GAEs. The proposed HC-GAE can generate effective representations for either node classification or graph classification, and the experiments demonstrate the effectiveness on real-world datasets.

HC-GAE: The Hierarchical Cluster-based Graph Auto-Encoder for Graph Representation Learning
Lu Bail.2, Zhuo Xu', Lixin Cui Ming Li4.5, Yue Wang", Edwin R. Hancock
School of Artificial Intelligence, Beijing Normal University. Beijing 100875, China Engineering Research Center of Intelligent Technology and Educational Application, Ministry of Education, Beijing Normal University, Beijing 100875, China School of Information, Central University of Finance and Economics, Beijing 100081, China "Zhejiang Institute of Optoelectronicss, Jinhua 321004, China ZZejjaan Key Laboratory of Intelligent Education Technology and Application, Zhejiang Normal University, Jinhua 321004, China Department of Computer Science, University of York, York YO10 5GH, United Kingdom
Abstract
Graph Auto-Encoders (GAFs) are powerful tools for graph representation learning. In this paper, we develop a novel Hierarchical Cluster-based GAE (HC-GAE), that can learn effective structural characteristies for graph data analysis. To this end, during the encoding process, we commence by utilizing the hard node assignment to decompose sample graph into family of separated subgraphs. We compress each subgraph into a coarsened node, transforming the original graph into a coarsened graph. On the other hand, during the decoding process, adopt the soft node assignment to reconstruct the original graph structure by expanding the coarsened nodes. By hierarchically performing the above compressing procedure during the decoding process as well as the expanding procedure during the decoding effectively extract bidirectionally hierarchical
process, the proposed HC-GAE structural features of the original sample graph. Furthermore, we re-design the loss function that can integrate the information from either the encoder the decoder. Since the associated graph convolution operation of the proposed HC-GAE is restricted in each individual separated subgraph and cannot propagate the node information between different subgraphs, the proposed HC-GAE can significantly reduce the over- weo-hhng problem arising in the classical convolution- based GAEs. The proposed HC-GAE can generate effective representations for either node classification or graph classification, and the experiments demonstrate the effectiveness on real-world datasets.
Introduction
In real-world applications, graph structure data has been widely used for characterizing pairwise relationships among the components of complex systems. With the recent rapid development of deep learning, the graph representation learning approaches relying on neural networks are introduced for the analysis of various graph data, e.g., social networks [12), transportation networks 200), protein compounds [34], 3D shape 2 5) etc. One challenging arising in these studies is that the graph data has a nonlinear structure defined in irregular non-Eude -ucluiiid space, and it is hard to directly employ traditional neural networks to learn graph representations.
To overcome the above problem, there have been increasing interests to further generalize traditional neural networks, especially the Convolutional Neural Network (CNN) [8]. for the irregular graph
*Corresponding Author: cuilixin@@e. @cufe.cdu.cn
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

data. These are the so-called convolution-basee Graph Neural Networks (GNNs) [4] and their related approaches [33] proposed for graph-baset tasks, utilizing both graph features and topologies. For
instance, the Higher-order Graph Convolutional Network (HiGCN) [1] has been developed based on the higher-order interactions to recognize intrinsic features across varying topological scales. Its effective expressiveness makes it capable for various graph-based tasks. The DeepRank-GNN [26] has been proposed by combining the rotation-invariant graphs and the GNN to represent protein- protein complexes. Because the GNN models can extract graph representations with more semantic learning under supervised conditions, researchers have focused more on seeking a self-supervised framework associated with the GNNs to accomplish representation learning.
As typical framework of representation learning, the classical Auto-Encoder [22] has been proposed to extract impressive results by reconstructing the input information. Especially, the Graph Auto- Encoder (GAE) 30 associated with the GNN model has further generalized the reconstruction ability for graph structures 15 19].
Due to the extensibility, the GAFs have been developed as a family of classical models for self-supervised representation learning. and there are adequate derivation models belonging to GAEs. For instance, the Self-Supervised Masked Graph Autoencoders (GraphMAE) [9] focusing on the feature reconstruction adopts a masking strategy and the scaled cosine error in the training model. Compared to the traditional GAE approach like VGAE [29]. its decoder is retrofitted with the GNN and the re-masking operation. Based on the GraphMAE. the S2GAE [28)
continues to adopt the masking strategy to improve the auto-encoder framework. To generate the cross-eppresentation the decoder is designed to capture the croos-correlattinn of nodes.
Challenges. Although the classical GAE-based methods achieve the effective performance for graph representation learning, they still have some significant challenging problems summarized as follows.
(a) The limitation for multiple downstream tasks: Generally, the representations extracted from the GAES can be divided into several categories, including the node-level representations for node classification, the graph-level representations for graph classification, etc. Specifically, it is difficult for the GAES to generate universal representations for multiple downstream tasks simultaneously. This is because the GAEs tend to over wver-empasiize the node features. For instance, the GraphMAE [9] focuses more on the node feature reconstruction, resulting in topological missing and weakening the the structure information reconstruction. This is harmful for the graph- level representation learning.
(b) The over-smoothing problem: the decoder and encoder modules of the GAES are defined associated with a number of stacked graph convolution operations, that rely on the node information propagation between adjacent nodes. When the GAE becomes deeper, the node features tend to be similar or indistinguishable after multiple rounds of information passing (21). resulting in the notorious over-smoothing problem (6) and influence the performance of the GAES.
The GAES usually proposed based on the GNNS, thus both
Contributions. The aim of this paper is overcome the above challenging problems by proposing novel HC-GAE model. Overall, the main contributions are threefold.
First, we propose a novel Hierarchical Cluster- based GAE (HC-GAE) for graph representation learning. Specifically, for the encoding process, we adopt the hard node assignment to decompose a sample graph into a family of separated subgraphs. We perform the graph convolution operation for each subgraph to further extract node features and compress the nodes belonging to each subgraph into coarsened node, transforming the original graph into a coarsened graph. Since the separated sub- graphs are isolated from each other, the convolution operation cannot propagate the node information between different subgraphs. The proposed HC-GAE can in turn reduce the werrsmoothing problem arising in the classical GAEs. Moreover, since the effect of the graph structure perturbation is limited within each subgraph, the required convolution operation performed on each subgraph can strengthen the robustness of the encoder for the proposed HC-GAE. As a result, the outputs of the encoder can be employed as the graph-level representations. On the other hand, for the decoding process, the soft node assignment to reconstruct the original graph structure by expanding each coarsened node into all retrieved nodes probabilistically. Thus, the outputs of the decoder can be employed as the node-level representations. Since the HC-GAE is defined by hierarchically performing the above compressing procedure during the decoding process as well as the expanding procedure during the decoding process, the proposed HC-GAE can effectively extract bidirectionally hierarchical structural features of the original sample graph, resulting effective hierarchical graph-level and node-level representations for either graph classification or node classification.
adopt
2

---

Second, we propose new loss function for training the proposed HC-GAE model. For calculating the complete loss value, we integrate the local loss from the subgraphs in the encoding operation and the global loss from the reconstructed graphs in the decoding operation. The global loss can capture the information from both the structure and the feature reconstruction processes. The combination of these two pretext tasks broadens the strict requirement causing the topological closeness. In addition, to avoid the over-fitting problem, we add the local loss as the regularization in our loss function.
Third, we empirically evaluate the performance of the proposed HC-GAE model on both node and graph classification tasks, demonstrating the effectiveness of the proposed model.
This paper organizes as follows. Section[Zreviews some related works. Section gives the definition of the proposed model. Section 4 provides experimental evaluations. Section 5 gives conclusions.
2 Related Works
2.1 The Graph Neural Network
GNNs are widely employed for many real-world applications [16 31 35 prominent success. The input data of GNNs is graph, that is a kind of non-Fuclidean data and contains nodes and edges. With the complex structures of the graphs, GNNs aim to leverage the information passing mechanism among nodes for graph embedding learning. The procedure of the information passing can be divided into aggregating, combining and readout. Specifically, given an input sample graph G(V, E¹) with the node set V ([V]= - n) and the edge set E, the node information is represented as the feature matrix X E IR" with d features, and the structure information is represented as the adjacent matrix A E (0, 1) 1 The GNN for each layer is defined as
and have achieved a
Za = GNN
(1)
where θ is the parameter set, and Zg is the graph embedding result for downstream tasks.
The Graph Convolutional Network (GCN) 13 is typical derivative model of GNNs, and generalizes the classical Convolutional Neural Network (CNN) [18] from the regular data to the irregular graph- structured data. One typical GCN model can be defined as the following layer-wise scheme, i.e.,
H ReLU AD- 1 HOWO),
where H()) E IRaxd is the hidden embedding matrix for the I-th layer, W E Raddd is the trainable parameter matrix for the I-th layer, Å = A + is the adjacency matrix associated with the self loop, D == E, A. is the degree matrix of Å, and И (I+1) is the embedding matrix extracted for the next ++ 1-th layer. The GCN model can effectively capture the global structural representations through the multiple stacked convolution layers defined by Eq. Unfortunately, since the convolution operation depends on the node information propagation between adjacent nodes. The GNN suffers from
similar when the GCN becomes deeper, e.g., the GNN with more than 5 convolution layers.
2.2 The Graph Auto-Encoder
The GAE is powerful self-supervised framework for graph representation learning. Typical instances of GAEs include the DeepWalk (25) and the Vec [7]. where the encoders usually play an important role for learning the latent representations of vertices. By associating with the convolution operations of GNNs, the encoders of GAEs are able to cope with the non-Fuclidean data (24). As a self-supervised learning model, the aim of GAES during the training process is the graph reconstruction (17), that be categorized into the fine-grained and the coarse-grained targets.
Specifically, the fine-grained target contains either nodes or edges. For instance, the Variational Graph Auto-Encoder (VGAE) model (29) adopts two stages, i.e. the encoder and the decoder, to accomplish the representation learning. For an input graph G(V, E), the goal of VGAE is to embed the graph through the encoder function f: V E > Z Ruxdd that maps the original node feature matrix of the node set V to the embedding matrix Z. Then, the decoder reconstructs the graph through the function g : 7 > F', where F.' the reconstructed edge set for the original edge set F.. During the encoding and decoding processes, the VGAE obtains the conditional probability distributions
3

---

q(Z V. E) and p( E"| Z from the encoder and the decoder respectively, and the loss function is -= KL V, ()) E, [logp( E Z)],
(3)
where [L[:] is the Kullback-Leibler divergence, E is the expection, and (2) is the Gaussian prior.
On the other hand, the coarse-grained target contains the subgraph the path structure. For example, the Heterogeneous Graph Masked Autoencoder (HGMA) [30] adopts the dynamic masking strategy to mask the nodes and the edges on the paths, and then reconstruct the path. Similar approaches also include the Masked Graph Autoencoder (MaskGAE) [4), that aims to reconstruct the masked edges and the node degrees jointly. Recently, some researchers have noted that the combination of the Graph Contrastive Learning (GCL) (38) and the GAE framework can further capture the complex interdependency residing on graphs. Under this scenario, the Self-supervised Learning for Graph Anomaly Detection (SL-GAD) 41 has been developed to obtain double subgraphs through the graph view sampling, and then respectively reconstructs them in two decoders for constrastive learning.
Although the above GAE methods significantly improve the performance of the graph representation learning, they still suffer from some common drawbacks. First, these GAE methods usually have superior performance for node classification, but have poor performance for graph classification. This is due the fact that these methods only focus on the node feature reconstruction and ignore the global graph structure reconstruction, resulting in topological missing. Thus, these methods tends to be elusive for multiple downstream tasks (17). Second, since the decoder and the encoder of these GAE methods usually employ the GNN models (i.e.. the associated graph convolution operation) to extract the node feature information. The over-smoothing problem of GNNs mentioned in Section [2. also affects the feature learning for these GAE-based methods. Moreover, when the perturbation of the graph structure is conducted, the noise also be propagated the neighbor nodes through the edges. After several rounds of information passing, the generated graph representations may be noisy.
3 The Methodology
To overcome the aforementioned challenges, propose novel (HC-GAE) model learn effective graph representations. The framework of the proposed model is shown in Figure T Similar to the classical GAEs, the HC-GAE model has two stages, including the encoder well as the decoder. During the encoding process, the encoder can layer-wisely compress each sample graph into a series of coarsened graphs, and the results of the encoder be employed the graph-level representations for graph classification. During the decoding process, the decoder can reconstruct the structure of the original sample graph, and outputs the node-level representations for node classification. In the following subsections, we commence by introducing the encoder and decoder of the proposed HC-GAE model. Moreover, we define family of loss function for the proposed HC-GAE model. Finally, we theoretically analyze the effectiveness of the proposed model.
Encoder
Decoder
Node level oppessenaation
Coarsened Groph
Graph level
representation
Encoding
Decoding
Figure 1: The architecture of our proposed HC-GAE model.
3.1 The GNN Encoder associated with the Hard Node Assignment
The first module of the proposed HC-GAE model is the encoder, that consists of multiple GNN layers and adopts the hierarchical computational architecture to compress the original input graph into a series coarsened graphs with shrinking sizes. Details of this GNN-based encoder are shown in Figure 2 where each layer includes the node assignment and coarsening processes. The first process to generate separated subgraphs from the original graph, and the second process compresses the subgraphs into coarsened nodes of coarsened graph.

---

Subgraph
Coarsened
Input Graph
Graph
Subgraphs
Assignment
Coarsening
Figure 2:
The computational architecture for our proposed layer in the GNN encoder.
Hard Assignment. For each 1-th layer of the encoder, the input graph is denoted G (X(), A where ( E (8* is the node feature matrix and A [ X is the adjacent matrix. The number of nodes for G is R(()), and each node has d(t features. Note that, G can be either the original input sample graph when = 1 or the coarsened graph when > 1. For the assignment process, the graph G is decomposed into number of separated subgraphs, by assigning the n() nodes into R((+1) clusters through the hard node assignment. To achieve this, we commence by computing the soft node assignment matrix Ssoft as
softmax (NN((X)) AO)) softmax(X*)
if if 1
Ssoft
(4)
where Saoft RR (* and n((+1) < π()) To guarantee the separability of the resulting subgraphs, we need to assign each node into unique cluster through hard node assignment matrix s(t) E {0, ), where each (i.j)-tt entry of 5(() can be computed through Swoft i.e.,
xm
{
if Saott (intt(i,)) max (1,)) VjEn--
(1,5)
(5)
otherwise
Clearly, each i-th row of the hard assignment matrix 5(1) selects the maximum element as and the remaining elements O. As result, the i-th node is only assigned to the j-th separated subgraph a (v,00 ),)), where v consists of the nodes belonging to the j-th cluster and E remains the
original edge connections between the nodes in Vi from the original input graph GO),
Coarsening. The coarsening process compresses the separated subgraphs into coarsened nodes of the resulting coarsened graph. Given the feature and adjacency matrices x!" and A of the subgraph
G we first adopt local graph convolution operation to extract the local structural information as - =
(6)
where w/(0 E Rdo (dn) > d(+1)) is the trainable weight matrix of the (-th layer, and (1) pxdann is the resulting local structural representation of G0D To compress each subgraph (()) into a a coarsened node, we define a mapping vector s). as (x)) ())))))))
= softmax(A4 (A x0
where D R is trainable vector, and will play an important role in compressing each subgraph ا. into the node of the coarsened graph. After several local graph convolution operations on the separated subgraphs in the 1-th layer, we aggregate these local information to further generate the coarsened graph, as the input graph ((+1) for the next / + 1-th layer. To this end, for the original input graph G(O, collect the feature matrices Z of all j-th subgraphs G as the extracted node feature matrix ( E ( xd whose node sequences follow the original graph G i.e., each vertex feature vector of (1) is equal to that of the corresponding node in G/)) This is because each
5

---

node of G essentially corresponds an unique original node of GO, Given the hard assignment
matrix S0)) defined by 5 and the mapping vector s) ( defined by Eq. 7 compute the feature
matrix ( and the adjacent matrix A (1+1) the resulting coarsened graph G(++1) as
x((+1) Reorder
n:-1
|200
(8)
j=1
and
A 5 5()
(9)
where is concatenation operation, and the function Reorder reorders the sequences of [:] to follow the same node sequence of G!)), For the encoder, we set the greatest layer number as L, and the resulting coarsened graph G(L+1) (x(++),, A(L+1)) is the input graph for the decoder. Furthermore, we adopt non connonnranen con-paameterized readout function (e.g., the MaxPooling and MeanPooling)
to further embed X(++1) as the graph-level representation for graph classification.
3.2 The GNN Decoder associated with the Soft Node Assignment
The second module of the proposed HC-GAE model is the decoder, that aims to reconstruct the structure of the original input sample graph, by expanding the each coarsened node into retrieved nodes probabilistically through the soft node assignment. Similar to the encoder, the decoder also consists of multiple GNN-based layers. Details of each decoder layer are shown in Figure where the input is the retrieved graph and the output is the reconstructed graph.
Retrieved Graph
Reconstructed
Graph
Figure 3: The illustration of our proposed layer in the GNN decoder.
Reconstruction. For each 1'tth layer of the decoder, the input retrieved graph is denoted as G'(t)) (X'(), A where x²(() (R" Xder is the node feature matrix and A'(()) E Re is the adjacent matrix. Note that, when I' G*(() essentially the resulting coarsened graph ( of the encoder. For the reconstruction process with G'll', we commence by computing the soft node assignment matrix 5(') E (B(())"((+)) (i.e., the learnable node re-assignment matrix) as
5((") softmax (GNN,,,,,, ,'"""))
(10)
Moreover, we further compute the node feature embedding of G"(l") as
7 GNN .mmb emm (1" A
(11)
Note that, the associated graph convolution operations GNN, and GNN for Eq, 10 and [T. do not share the parameters. Specifically, the operation GNNr generates probabilistic distribution expand the nodes of G*(!) the corresponding nodes of the resulting reconstructed graph (*(++1), and the operation GNN; emb extracts the new embeddings for G*(l", With 5('") and ((') to hand, we compute the node feature matrix (1(++1) E 1) xd and the adjacency matrix (1(+1) E " Xmar+1) for the reconstructed graph (*((++ as
x11++1) =5('' 2(')
(12)
and
A'1++1) = 3(0) (0")0(())))) g(").
(13)
We employ G*((++) as the input retrieved graph for the next + 1-th layer, and set the greatest layer number L' (L' equals to L of the encoder). The resulting graph (*(+++1) = (1'(+++)) 4'(1'+1))
is the output of our HC-GAE, and ('(++1) is the node-level representations for node classification.

---

3.3 The Loss Function
The proposed HC-GAE model consists of the encoder focusing on compressing the graph structural information and the decoder aiming at reconstructing the original graph structure. Therefore, the loss function LHC-GAB GAA of HC-GAE includes two individual parts, and defined as
B(44))
Dlocal ΣEP
Σ
(L(a(Z)))
|x ".).4))))((((
1=1
j=1
(14)
Cglobal = Σ
a loollo wonn)loog(xxeeeee (X A
1=1
CHC-GAE= = Clocal + Lglobal,
where Llocal is the local loss, Lglobal is the global loss, and p(Z() is the Gaussian prior for the I-th layer. Specifically, Liocal aims at training the subgraph generation, that reserves the local information and avoids the over-smoothing problem for the GNN-based encoder. Lglobal focuses on reconstructing the graph features and structures. The combination of Liocal and Lylobal broadens the reconstruction requirement for multiple downstream tasks (i.e., the node and graph classification), since Liocal is regularization for the loss and can strengthen the graph representations associated with the additional local information for the proposed HC-GAE model. Note that, for the node classification, we only need to reconstruct the structure information (i.e., the adjacency matrix AC) rather than the node feature information (i.e., the feature matrix X() for the loss function LHC-GAE-
3.4 Discussions
(a) Why is the proposed HC-GAE model effective for multiple downstream tasks?
As mentioned in Section D and 2.2 most existing GAE methods tend to over-emphasize the graph feature reconstruction, not only ignoring the topological structure information but also aggravating the over-fitting problem for the graph features [32]. Thus, these GAE methods are usually employed for node classification, and have poor performance for graph classification. To overcome this shortcoming, the proposed HC-GAE model adopt the following schemes. First, the HC-GAE adopts the node assignment strategy to improve the encoding and decoding performance. Specifically, for the encoder, utilize the hard node assignment decompose the input graph into separated subgraphs to extract local structural information, and this can reduce the redundancy for the graph-level representation learning. On the other hand, for the decoder, original graph structure, and employ the associated node features of the reconstructed graph as the node-level representations. The combination of these assignment strategies guarantees that the HC-GAE can effectively learn multi-level representations for various downstream tasks. Second, the loss function of the HC-GAE consists of both the local and global loss. The global loss Lylobal can either reconstruct the graph features or the topological structures, reducing the werremmpassizing on graph features. The local loss Llocal not only plays a role of regularization LHC-GAE- but also captures the local information from the separated subgraphs, improving the generalization of the graph representations through the local information [39
the soft node assignment reconstruct the
(b) Why does the proposed HC-GAE model reduce the over-smoothing problem?
Unlike the sherarchical-basee GNN methods 229. 37), during the encoding process, we perform the local graph convolution operation within each individual separated subgraph. Thus, the information can not be propagated to other subgraphs, significantly reducing the over-smoothing problem.
4 Experiments
This section empirically evaluates the performance of the proposed HC-GAF for both node and graph classification on benchmark datasets, whose detailed statistical information are shown Table and Table 2 Specifically, for the HC-GAE, select the Adam optimizer to train the parameters, and set the epoch, hidden dimension and dropout as 50, 128 and 0.5, respectively. For the encoder and
'The source code is available httppp///ggtaab..cco///oaaaaaaaa

---

Table 1: Datasets for node classification
Datasets
Cora
CiteSeer
PubMed
Compulers
CS
Nodes
2708
3312
19717
13752
18333
Edges
$429
4660
44338
245861
81894
Features
1433
3703
6805
Classes
7
6
10
15
Table 2: Datasets for graph classification
Datasets
IMDB-B
IMDB-M
PROTEINS
COLLAB
MUTAG
Graphs
1500
5000
Nodes(mean)
19.77
13
39.06
74.49
17.93
Edges(mean)
96.53
65.94
72.82
2457.78
19.79
Classes
3
decoder of the HC-GAE, we set their greatest layer numbers L and L' as 3, and their node numbers for the layers as {128, 64, 32) and {32, 64, 128]. Moreover, we set the batch size and the learning rate as 1024 and 1e 2 for node classification, and 64 and 5e - 4 for graph classification. For either the proposed HC-GAE or the alternative baselines, we adopt the 10-fold cross validation compute classification accuracies, and follow the original setups for different baselines.
4.1 Node Classification
Datasets and Baselines. For node classification, we employ five real-world datasets, i.e., Cora, CiteSeer, PubMed, Amazon-Compiln and Coauthor-CS CS. Moreover, we compare the proposed model with six classical self-supervise models, i.c., DGI [33), VGAE 229. SSL-GCN [42). GraphSage [8), GraphMAE 191, and S2GAE [28]. To fairly compare the proposed model and other baselines, we follow the previous study [10] to carry the related experiments, and utilize the SVM classifier to
predict the node labels, and the classification accuracies are shown in Table 3
Results. Clearly, the proposed HC-GAE outperforms most of the baselines. Only the accuracy of the GraphMAE a little higher than our model. The reasons for the effectiveness are twofold. First, the HC-GAE model is defined based on a bidirectionally hierarchical computational architecture, and can extract more effective node feature information to compress and reconstruct the original sample graph structures. Second, the HC-GAE can significantly reduce the over-smoothing problem.
Table 3: Node classification performance based on accuracy. A.R. is the average rank.
Datasets
Cora
CireSeer
PabMed
Computers
CS
A.R.
DGI
05.41=0.34
74.51=0.31
85.95=0.60
84.68=0.39
91.354:0300
VGAB
83.60+t0.52
63.37=1.21
78.23+:163
87.21=0.26
89.79+10.09
5.2
SSL-
57.29.10.13
59.57
75.06.10.37
80.49-0.100
84.711.0.95
GmphSaage
14.30:1:.844
15.20=2.15
81.96:10.74
87.05=0.25
89.74.10.11
5.6
GraphMAE
85.45:+0.40
72.48=0.77
85.74:0.144
88.04=0.61
93.47:20.04
3.0
S2GAE
86.15:::025
74.60=0.06
86.91:10.28
90.94=0.08
91.70-1-0.08
HC-GAE
87.97:40.10
7..29=0009
87.56-10.38
91.07=0.14
92.28-+0.07
1.2
4.2 Graph Classification
Datasets and Baselines. For graph classification, we adopt five standard graph datasets, i.e., IMDB- B. IMDB-M, PROTEINS, COLLAB and MUTAG. Moreover, we compare the proposed model
with a graph kernel (i.e., WLSK (2). two supervised GNN models (i.e., DGCNN 40 and D-
iffPool 37 and four self-supervised GAE models (i.e., Graph2Vec [23], InfoGCL 36 Graph-
MAE 9. S2GAE (28). We employ the SVM associated with the resulting graph representations to compute the classification accuracies in Table 4
following the previous study in 9
Results. Clearly, the proposed HC-GAE model outperforms most of the alternative baselines. Only accuracy of the S2GAE on the COLLAB dataset is a little higher than the proposed HC-GAE. The effectiveness of the HC-GAE are due the following reasons. First, the alternative GAE-based models (e.g., the GraphMAE) focuses on the graph feature reconstruction rather than the topological structure information. Thus these models are only effective for node classification and have poor performance for graph classification. By contrast, the HC-GAE can simultaneously focus on either the node feature or the structure information. Second, most of the alternative deep learning baselines are essentially GNN-based methods, that usually suffers from the over-smoothing problem. By contrast, the proposed HC-GAE can significantly reduce the over-smoothing through the local graph convolution within separated subgraphs of limited sizes. Third, unlike the proposed HC-GAE that is

---

a deep learning method, the alternative WLSK kernel cannot provide an end-to-end learning manner, ie.. the kernel computation separated from the training of the SVM classifier.
Table Graph classification performance based on accuracy. A.R. the average rank,
Datasets
IMDE--B
IMDB-M
PROTEINS
COLLAB
MUTAG
A. R.R.
DGCNN
67.45-40.83
46.33=0.73
73:214:0.34
NIA
15.83=11.66
6.25
DittPool
72.6::3.9
47.2=1.8
75.1+3.55
78.922.3
85.0+10.3
5.20
Graph2Vec
71.10=0.54
50,44=0.87
73.30+22.05
N/A
83,15-9.225
5.75
InfoGCL
75.10
51.40=0.80
NIA
80.00=
91.20=
3,50
GraphMAE
75.52=00.66
51.63=0.52
15.30:20.39
80.32::0:46
18.19
3.20
S2GAE
75.76.10.62
51.79-0.36
76.37:10.43
81.02:10.53
10,76
2,00
HC-GAE
7..72:10.0
1..90=1.47
78.13--1.77
80.41:10.02
92.78-11.17
4.3
Ablation Study
To analyze the effectiveness of the proposed HC-GAE one step further, we replace the the hard assignment strategy of the encoder with the soft assignment strategy, and perform the same setups for graph classification. We denoted the proposed model with the soft assignment as HC-GAE-SE. Under this scenario, the encoder of the HC-GAB-SE cannot decompose the graph into separated subgraphs and cannot employ the local graph convolution operation to extract the feature information, since each node will be assigned all clusters with different weights. The experimental comparisons are shown in Figure 4 Obviously. the performance of the HC-GAE-SE is lower than the proposed HC-GAE on any dataset. The reasons are twofold. First, unlike the proposed HC-GAE, the HC-GAE- SE cannot avoid the influence of the over-smoothing problem, without the local convolution within the separated subgraphs. Second, the loss function of the proposed HC-GAE relies on the local graph information through the separated subgraphs. However, this is not available for the HC-GAE-SE, thus cannot extract the local information to enhance the effectiveness.
100
80
40
BHC-GAE SE
#HC-GAE
Figure 4: The ablation experiments on graph classification task.
5 Conclusions
In this paper, we have proposed a novel HC-GAE model learn effective structural characteristics for either graph classification or node classification. During the encoding process, the HC-GAE has adopted the hard node assignment decompose the input graph into family of separated subgraphs, and compressed these subgraphs into coarsened nodes, resulting in coarsened graph. During the decoding process, the HC-GAE has employed the soft node assignment to reconstruct the original graph structure, by expanding the coarsened graph of the encoder. The proposed HC-GAE can not only extract hierarchical structural features of the original graph, but also reduce the notorious smothhng problem arising in most classical GAEs, by restricting the convolution operation within each separated subgraphs during the encoding process. Experiments have demonstrated that the proposed HC-GAE has superior performance for both node and graph elassification.
Our future work is to employ the structurally aligned (sub)structures, that have been successfully explored in our previous works [4] [5] for the proposed HC-GAE model. This will naturally result new Sonsitive-Alignee HC-GAE models to guarantee the consistency between the structural correspondence information as well as the spatial position over all graphs. Finally, we will also use the
operator of hypergraphs [ [ associated with the proposed HC-AGE model, resulting in novel hypergraph-basee HC-GAE models.

---

Acknowledgments
This work is supported by the National Natural Science Foundation of China under Grants T2122020, 61602535 and 61976235. Ming Li acknowledged the supports from the National Natural Science Foundation of China (No. U21A20473, No. 62172370) and the Jinhua Science and Technology Plan (No. 2023-3-003a). This work is also supported in part by the Program for Innovation Research in the Central University of Finance and Economics, and the Emerging Interdisciplinary Project of CUFE.
References
[1] L. Bai, P. Ren, and E. R. Hancock. A hypergraph kernel from isomorphism tests. In Proceedings of the International Conference on Pattern Recognition (ICPR), pages 3880-3885, 2014.
[2] L. Bai, Z. Zhang, C. Wang, X. Bai, and E. R. Hancock. A graph kernel based on the jensen- shannon representation alignment. In Q. Yang and M. Wooldridge, editors, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages
2015.
[3] L. Bai, F. Escolano, and E. R. Hancock. besth-based hypergraph complexity traces from directed line graphs. Pattern Recognition, 54:229-240, 2016.
[4] L. Bai, Y. Jiao, L. Cui, L. Rossi, Y. Wang, P. S. Yu, and E. R. Hancock. Learning graph convolutional networks based on quantum vertex information propagation. IEEE Transactions on Knowledge and Data Engineering, 35(2):1747-1760, 2023.
[5] L. Cui, L. Bai, X. Bai, Y. Wang. and E. R. Hancock. Learning aligned vertex convolutional networks for graph classification. IEEE Transactions on Neural Networks and Learning Systems, 35(4):4423-443) 2024.
[6] J. H. Giraldo, K. Skianis, T. Bouwmans, and F. D. Malliaros. On the trade- off between over- smoothing and over- squashing in deep graph neural networks. In Proceedings of the ACM International Conference Information and Knowledge Management (CIKM), pages 566-576, 2023.
[7] A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 855 864, 2016.
[8] W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. pages 1024 1034, 2017.
[9] Z. Hou, X. Liu, Y. Cen, Y. Dong, H. Yang, C. Wang, and Tang. Graphmae: Self-supervised masked graph gutoencoders. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 594-604, 2022.
[10] W. Hu, M. Fey, M. Zitnik, Dong, H. Ren, Liu, M. Catasta, and J. Leskovee. Open graph benchmark: Datasets for machine learning graphs. 2020.
[11] Y. Huang, Y. Zeng. Q Wu, and L. Lü. Higher-order graph convolutional network with flower- petals laplacians on simplicial complexes. arXiv preprint arXiv:2309.1297. 2023.
[12] W. Ju, Y. Gu, X. Luo, Y. Wang. H. Yuan, H. Zhong, and M. Zhang. Unsupervised graph-level representation learning with hierarchical contrasts. Neural Networks, 158:359-366 0388999368,,0 2023.
[13] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 11016669909077 2016.
[14] J. Li. R. Wu, W. Sun, L. Chen, S. Tian, L. Zhu, C. Meng, Z. Zheng, and W. Wang. Maskgae: Masked graph modeling meets graph autoencoders. arXiv preprint arXiv:2205.1005: 9:13, 2022.
[15] J. Li, X. Fu, S. Zhu, H. Peng. S. Wang, Q. Sun, P. S. Yu, and L. He. A robust and generalized framework for adversarial graph embedding. IEEE Transactions on Knowledge and Data Engineering, 35(11):11004-1100 2023.
10

---

[16] J. Li, H. Shomer, H. Mao, S. Zeng, Y. Ma, N. Shah, J. Tang, and D. Yin. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. 2023.
[17] J. Li, R. Wu, W. Sun, L. Chen, S. Tian, L. Zhu, C. Meng, Z. Zheng, and W. Wang. What's behind the mask: Understanding masked graph modeling for graph autoencoders. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 1268 1009-1179,,200 2023.
[18] Z. Li, F. Liu, W. Yang, S. Peng, and J. Zhou. A survey of convolutional neural networks: Analysis, applications, and prospects. IEEE Transactions on Neural Networks and Learning Systems, 33(12)16999-7019 2022.
[19] Y. Liu, X. Yang, S. Zhou, X. Liu, Z. Wang. Liang, W. Tu, L. Li, J. Duan, and C. Chen. Hard sample aware network for contrastive deep graph clustering. In Proceedings of the AAAI conference on artificial intelligence (AAAI), volume 37, pages 8914 8922, 2023.
[20] Z. Liu, Y. Chen, F. Xia, J. Bian, B. Zhu, G. Shen, and X. Kong. Tap: Traffic accident profiling via multi-task spatio-temporal graph representation learning. ACM Transactions on Knowledge Discovery from Data, 17(4):1-25, 2023.
[21] D. P. P. Mesquita, A. H. S. Jr., and S. Kaski. Rethinking pooling in graph neural networks. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
[22] U. Michelucci. An introduction to autoencoders. arXiv preprint arXiv:2201 2022.
[23] A. Narayanan, M. Chandramohan, R. Venkatesan, L. Chen, Y. Liu, and S. Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv: /707.00000 2017.
[24] E. Pan and Z. Kang. Beyond homophily: Reconstructing structure for graph-agnostic clustering. In Proceedings of the International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 26868-26877, 2023.
[25] B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: online learning of social representations. In The ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 701-710, 2014.
[26] M. Réau, N. Renaud, L. C. Xue, and A. M. Bonvin. Deeprank-gnn: A graph neural network framework learn patterns in protein-protein interfaces. Bioinformatics, 39(b)bbtc77,9 2023.
[27] N. Shervashidze. S. V. N. Vishwanathan, T. Petri, K. Mchlhorn, and K. M. Borgwardt. Effi- cient graphlet kernels for large graph comparison. In D. A. V. Dyk and M. Welling, editors, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume of JMLR Proceedings, pages 488 495, 2009.
[28] Q. Tan, N. Liu, X. Huang, S.-H. Choi, L. Li, R. Chen, and X. Hu. S2gae: Self-supervised graph autoencoders are generalizable learners with graph masking. In Proceedings of the ACM International Conference on Web Search and Data Mining (KDD), pages 787-795, 2023.
[29] N. K. Thomas and M. Welling. Variational graph auto-encoders. iv: 161 1.07308, 2(10), 2016.
arXiv preprint arX-
[30] Y. Tian, K. Dong, C. Zhang, C. Zhang, and N. V. Chawla. Heterogeneous graph masked autoen- coders. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 37, pages 9000, 2023.
[31] V. Vasudevan, M. Bassenne, M. T. Islam, and L. Xing. Image classification using graph neural network and multiscale wavelet superpixels. Pattern Recognition Letters, 166:89-96, 2023.
[32] P. Veličković, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio, and R. D. Hjelm. Deep graph infomax. arXiv preprint arXiv: 10341, 2018.
[33] Velickovie, W. Fedus, W. L. Hamilton, Liò, Y. Bengio, and D. Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
11

---

[34] L. Wang, H. Liu, Y. Liu, J. Kurtin, and S. Ji. Learning hierarchical protein representations via complete 3d graph networks. In Proceedings of the International Conference on Learning Representations (ICI.R), 2023.
[35] L. Wei, H. Zhao, Z. He, and Q Yao. Neural architecture search for gnn-based graph classification. ACM Transactions on Information Systems, 42(1):1-29, 2023.
[36] D. Xu, W. Cheng, D. Luo, H. Chen, and X. Zhang. Infogel: Information-aware graph contrastive learning. pages 30414-30422 2021.
[37] Z. Ying, You, Morris, Ren, W. Hamilton, and J. Leskovec. Hierarchical graph representation learning with differentiable pooling, pages 4805-4815, 2018.
[38] Y. You, T. Chen, Y. Sui, T. Chen, Z. Wang, and Y. Shen. Graph contrastive learning with augmentations. 2020.
[39] Y. You, T. Chen, Z. Wang, and Y. Shen. When does self-supervision help graph convolutional networks? In Proceedings of the International Conference Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 10871-10880, 2020.
[40] M. Zhang, Z. Cui, M. Neumann, and Y. Chen, An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 32, 2018.
[41] Y. Zheng, M. Jin, Y. Liu, L. Chi, K. T. Phan, and Y.-P. P. Chen. Generative and contrastive self self--sue learning for graph anomaly detection. IEEE Transactions on Knowledge and Data Engineering. 32(12):12200- 12233, 2021.
[42] Q Zhu, B. Du, and P. Yan. Self-supervised training of graph convolutional networks. arXiv preprint arXiv:2006. 02380, 2020.
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract has directly pointed out the main contribution of this paper.
Moreover, in Section the contributions and scope also clearly stated.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [No]
Justification: This paper aims at overcoming the shorteomings existing in the Graph Auto- encoders (GAEs) and the Graph Neural Networks (GNNs). Therefore, this paper does not refer to any limitations of the proposed work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "L.imiations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: This paper provides the assumptions and proof for our proposed model. The details are shown in Section and Section 3.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The details of our proposed model are shown in Section 3. And the experimen- tal settings are shown in the Appendix. All these guarantee the that the experiment can be reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
cases, in which
14

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The dataset are from benchmarks. But we will have some further extension works based on this paper. Thus, the code is nod provided at this moment, but will be available in future.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.ca cc/ public/guides stteleese/ooeSSumissssiooooooooo
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
llaaps.cc/public/guidee wet.guddeeeooeeiiiieeee htt.uuummssioooooololllo ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide the required information in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
We provide the required information Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yss]
Justification:
We provide the required information in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that cttpc/////c///ttccscssieeeeellll
didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https:
Answer: [Yes]
Justification:
This paper follows the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is about graph auto-encoder. We not think that this paper refers to this problem.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
16

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper is about graph auto-encoder. We do not think that this paper refers to this problem.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The alternative methods for comparisons are based on the open resource.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: This paper is about graph auto-encoder. We do not think that this paper refers to this problem.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper is about graph auto-encoder. We do not think that this paper refers this problem.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper is about graph auto-encoder. We do not think that this paper refers to this problem.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
18

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19


Reviews:
[{"review_id": "3eVGjxXvWC", "reviewer": "Reviewer_DgD7", "summary": "The authors propose a new GNN-based representation learning method (HC-GAE), that can abstract effective local node features and global graph features. These features can be used for both node and graph classification. The new HC-GAE method consists of two main computational modules, they are the encoder associated with the hard node assignment, and the decoder associated with the soft assignment. Moreover, the deep representation in the middle layer can be seen as the global graph features, and the output in the last layer can be seen as the local node features. All these features encapsulate bidirectionally hierarchical structural features of the original sample graph based on the hierarchical strategy. Finally, the authors also propose a new loss function for integrating the information from either the encoder or the decoder.", "questions": "See the questions I asked in weakness.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of this work seems novel and interesting for me, performing the local convolution operation within the separated subgraphs through the hard node assignment not only addresses the over-smoothing problem, but also forms hierarchical representation for the graphs.  \n2. The descriptions are clear, the experiments demonstrate the effectiveness, and the new model is technical sound.", "weaknesses": "Overall, the writing is easy to understand, but I see minor typos or grammar mistakes in Section 3 and 4. I didn’t check these in details, the authors should carefully correct them for the final manuscript.\n\nI feel a little strange for the loss function. Because the function tends to minimize the differences of either the structures or the node features between the input (for encoder) and the output (decoder). As I see, if the authors use the output for the node classification, why you do not directly use the original input node features? Or, foe the node classification you eliminate the effects from the node features for the loss function. This is not very clear.\n\nAppendix B, what do you mean for Ghazan? I didn’t see any explanation of this word. Is it a kind of alternative method or others?\n\nThe authors discuss some theoretical advantages of the proposed method in Sec 3.4. But they don’t discuss any reason about why the proposed method performs well in Sec 4. They just simply show the accuracies are better. Some more analysis is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: I feel a little strange for the loss function. Because the function tends to minimize the differences of either the structures or the node features between the input (for encoder) and the output (decoder). As I see, if the authors use the output for the node classification, why you do not directly use the original input node features? Or, foe the node classification you eliminate the effects from the node features for the loss function. This is not very clear.\n\nA1: We are sorry that we didn’t explain the loss function for more details. For graph classification, the proposed model needs to simultaneously reconstruct the topological structures (i.e., the adjacency matrices) and the node feature information (i.e., the node feature matrices). On the other hand, for the node classification, we only need to reconstruct the structure information. We will explain these more clear in the manuscript. \n\nQ2: Appendix B, what do you mean for Ghazan? I didn’t see any explanation of this word. Is it a kind of alternative method or others?\n\nA2: We are sorry for the typos, in fact we should use the HC-GAE. We will correct this problem.\n\n\nQ3: The authors discuss some theoretical advantages of the proposed method in Sec 3.4. But they don’t discuss any reason about why the proposed method performs well in Sec 4. They just simply show the accuracies are better. Some more analysis is needed.\n\nA3: Thanks for the constructive suggestion. The theoretical reasons for the effectiveness are twofold. First,  the proposed HC-GAE is based on the new subgraph convolution framework. Specifically, we propose to employ the hard node assignment to assign the nodes into separated clusters, resulting in separated subgraphs. The convolution operation is performed within each individual subgraphs, and the node information cannot be propagated between different subgraphs, this can thus significantly reduce the over-smoothing problem and improve the performance. Second, the proposed HC-GAE can simultaneously reconstruct both the topological structures and the node features through the hierarchical strategy associated with the node assignment operation. Moreover, it will not drop any node information, reducing the topological information loss, effectively extracting bidirectionally hierarchical structural features of the original sample graph. We will add these theoretical discussion in the manuscript associated with the classification accuracies, following the the reviewer’s suggestion.", "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": "", "extra_scores": {}}, {"review_id": "7DKQIzcz1C", "reviewer": "Reviewer_94wD", "summary": "This paper develops a novel GAEs, namely the Hierarchical Cluster-based GAE (HC-GAE) model, to learn effective features for either node classification or graph classification. To extract the  bidirectionally hierarchical structural features of the original graph, this paper first utilize the hard node assignment to transform the original graph into a family of coarsened graphs, and then utilize the soft assignment to reconstruct the original graph. During the encoding process the convolution operation is restricted within each separated subgraph, so this HC-GAE can address the shortcoming of over-smoothing problem. This new model has superior performance on both node classification or graph classification tasks.", "questions": "See the weakness raised above.", "limitations": "yes", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.The idea of this work is interesting, and the bidirectionally hierarchical structure learning based on the adaptive node assignment seems novel to me.\n2.The proposed HC-GAE model is flexible for either node classification or graph classification. \n3.The paper is clearly written and easy to follow, and the experimental results also demonstrate the effectiveness of the new HC-GAE model.", "weaknesses": "Although this paper introduces a novel graph representation learning method, but some problems still need to be addressed or be clearer.\n1.Why the HC-GAE model utilizes the hard and soft assignment for the encoder and decoder respectively? As I see, the author can only use any of these assignment strategies, right?\n2.If the hard assignment can help the new model to reduce the over-smoothing problem, how about the soft-assignment?\n3.Why the reconstructed features are effective for node classification? Why do not use the middle features?\n4.Although this paper is clearly written, but the writing of Section 3 can be more polished.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Although this paper introduces a novel graph representation learning method, but some problems still need to be addressed or be clearer. \n\nQ1: Why the HC-GAE model utilizes the hard and soft assignment for the encoder and decoder respectively? As I see, the author can only use any of these assignment strategies, right? \nA1: One key innovation of the proposed HC-GAE model is that it performs the subgraph convolution operation in each individual subgraph, so that the node information can only be propagated in a separated subgraph, significantly reducing the over-smoothing problem. To eliminate the structural connection between different subgraphs, each node of the original input sample graph need to be assigned to an unique cluster. The soft assignment will assign each node to multiple clusters associated with different probabilities, thus it cannot help us to reduce the over-smoothing problem. \n\n\nQ2: If the hard assignment can help the new model to reduce the over-smoothing problem, how about the soft-assignment? \nA2: Thanks for the suggestion. The reason is similar to the above problem. The soft assignment cannot guarantee that each node will be assigned into the same cluster, so that one node information may be existed in all other subgraphs, so that we cannot restrict the node information propagate in an individual separated subgraph. In other words, each node can still propagate its information to all other nodes. With the model architecture becomes deeper, the over-smoothing problem will appear. \n\nQ3: Why the reconstructed features are effective for node classification? Why do not use the middle features? \nA3: Sorry that we didn’t explain this in details. The proposed HC-GAE model is one kind of the hierarchical structure-based GNN methods, that can hierarchically constructs the series of coarsened graphs with shrinking sizes. Thus, the size of the coarsened graph in the middle layer is smaller than the original graph, i.e., many nodes of the original graph are compressed as the coarsened node. Clearly, the coarsened nodes are not suitable for the classification of original nodes.  \n\n\nQ4: Although this paper is clearly written, but the writing of Section 3 can be more polished.\nA4: Thanks for the suggestion. We will further revise this section.", "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": "", "extra_scores": {}}, {"review_id": "wFpvlRxsbm", "reviewer": "Reviewer_Udb8", "summary": "The paper presents a Hierarchical Cluster-based Graph Auto-Encoder (HC-GAE) for improved graph representation learning. HC-GAE uses hard node assignment for encoding and soft node assignment for decoding; thus, it enables hierarchical compression and expansion of graphs. The authors argue their method can reduce the over-smoothing effect by limiting message-passing to individual subgraphs. HC-GAE effectively improves performance in node and graph classification tasks on real-world datasets.", "questions": "- I think “compressing procedure during the decoding process (line 9 – 10)” should be “compressing procedure during the encoding process”. Is it a typo?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and includes all the necessary details. The proposed model solves a significant problem in the graph representation community and numerical results are promising.", "weaknesses": "The code should be released at the review stage to check reproducibility. Especially for empirical work, releasing codes is a prerequisite for acceptance to me.\n\nThe proposed HC-GAE is similar to existing models that employ graph auto-encoders with hierarchical (multi-level, multiresolution) pooling (or coarsening). The authors should include a discussion comparing HC-GAE with these models, both qualitatively and quantitatively. Without this discussion, the paper's claim of novelty cannot be highlighted.\n1. Graph U-Nets\n1. Mesh Variational Autoencoders with Edge Contraction Pooling\n1. Masked Graph Auto-Encoder Constrained Graph Pooling\n1. GRAPH AUTOENCODER FOR GRAPH COMPRESSION AND REPRESENTATION LEARNING\n1. Multiresolution equivariant graph variational autoencoder\n1. Hi-GMAE: Hierarchical Graph Masked Autoencoders\n\nIt is unclear whether the over-smoothing effect does not exist in HC-GAE truly, as there are no experimental results against the number of layers. If GNN is applied to the coarsened graph, message-passing between coarsened nodes will occur, potentially leading to over-smoothing. To support their argument, the authors should empirically validate the claim that HC-GAE reduces over-smoothing (i.e., how performance varies by the number of layers).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1:The code should be released at the review stage to check reproducibility. Especially for empirical work, releasing codes is a prerequisite for acceptance to me.\n\nA1: Thanks for the constructive suggestion. We have provided a demo to the reviewer, please see the official comment with the anonymized link, and this follows the request of policy of the Reviewing/Discussion process. The reviewer can also use other standard datasets we raised in the manuscript with our code. We trust that this can help the reviewer demonstrate the reproducibility for the proposed method. Please feel free to discuss with us for the code during the discussion stage. Moreover, we promise that we will also release our code on the Github after the review process.\n\nQ2: The proposed HC-GAE is similar to existing models that employ graph auto-encoders with hierarchical (multi-level, multiresolution) pooling (or coarsening). The authors should include a discussion comparing HC-GAE with these models, both qualitatively and quantitatively. Without this discussion, the paper's claim of novelty cannot be highlighted. E.g., 1) Graph U-Nets; 2) Mesh Variational Autoencoders with Edge Contraction Pooling; 3) Masked Graph Auto-Encoder Constrained Graph Pooling; 4) GRAPH AUTOENCODER FOR GRAPH COMPRESSION AND REPRESENTATION LEARNING; 5) Multiresolution equivariant graph variational autoencoder; 6) Hi-GMAE: Hierarchical Graph Masked Autoencoders\n\n\nA2：Thanks for the constructive suggestion. Although some existing Hierarchical GAE methods also employ the auto-encoder with the hierarchical pooling, there are still some important theoretical differences between the proposed HC-GAE and these alternative methods. \n\nFirst, unlike these alternative Hierarchical GAE methods, the proposed HC-GAE not only hierarchically constructs the series of coarsened graphs with shrinking sizes, but is also defined by associating with the separated subgraph convolution operations during the hierarchical pooling process. Thus, unlike these alternative methods relaying on the global convolution over the whole graph structure, the proposed HC-GAE can naturally restrict the information propagation in each individual separated subgraph, significantly reducing the over-smoothing problem. Second, the alternative Hierarchical GAE methods are essentially based on the node drop pooling (i.e., the masking strategy), that focuses more on the node feature reconstruction, resulting in topological missing and weakening the structure information reconstruction. By contrast, the proposed HC-GAE needs to simultaneously reconstruct both the topological structures and the node features through the hierarchical pooling strategy associated with the node assignment operation. Thus, the proposed HC-GAE can effectively extract bidirectionally hierarchical structural features of the original sample graph, in terms of either the adjacency matrices (i.e., the topological information) or the node feature matrix (i.e., the node representation). We will cite the references suggested by the reviewer, and add the above discussions in the manuscript, making the paper more polish.   \n\nFurthermore, to empirically demonstrate the effectiveness, we will also compare the proposed HC-GAE model with the alternative Hierarchical GAE suggested by the reviewer. As a preliminary evaluation, we have collected several models suggested by the reviewers, the results are shown as follows and our method can significantly outperform the alternative methods. Note that, more experiments are performing now, and we will add the new experimental results as well as the above theoretical discussions in the final manuscript, making this paper more polish.  \n\nTable 1. The experimental results (node classification); the datasets are Cora, CiteSeer, and PubMed.\nThe results for Graph U-Nets\tare 84.4 ± 0.6, 73.2 ± 0.5, and 79.6 ± 0.2;\nfor Hi-GMAE\tare 86.4 ± 0.5, 74.5 ± 0.8, and 85.3 ± 0.2;\nfor ours(HC-GAE) are 88.0±0.1, 75.3±0.1, 87.6 ± 0.4.\n\nTable 2. The experimental results (graph classification), the datasets are PROTEINS and COLLAB.\nThe results for Graph U-Nets\tare 77.68\tand 77.56;\nfor Hi-GMAE are 76.63 and 82.16;\nfor ours(HC-GAE)\tare 78.13\tand 80.41.\n\nQ3: It is unclear whether the over-smoothing effect does not exist in HC-GAE truly, as there are no experimental results against the number of layers. If GNN is applied to the coarsened graph, message-passing between coarsened nodes will occur, potentially leading to over-smoothing. To support their argument, the authors should empirically validate the claim that HC-GAE reduces over-smoothing (i.e., how performance varies by the number of layers).\n\nA3: Thanks for the constructive suggestion. Through the theoretical viewpoint, the definition of the  proposed HC-GAE associated the separated subgraph convolution operation, and the node information can not be propagated to other individual subgraphs, significantly reducing the over-smoothing problem. For the empirical viewpoint, we have select three alternative methods that we have evaluated and suggested by the reviewer, we evaluate how the classification accuracies vary with number of layers. We find that the proposed HC-GAE can significantly outperform these alternative methods, especially with more than 3 layers for either the encoder or the decoder. We will add these new results in the final manuscript, making the experiment and the statement more self-contained.", "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": "", "extra_scores": {}}, {"review_id": "jmyeyBcZcI", "reviewer": "Reviewer_M4BE", "summary": "This paper proposes a novel Hierarchical Cluster-based Graph Auto-encoder (HC-GAE) for unsupervised graph representation learning. HC-GAE can reduce the over-smoothing problem and generalize to multiple downstream tasks.", "questions": "Please refer to \"Weaknesses\".", "limitations": "Please refer to \"Weakness 2\".", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "1. The motivation is clear and easy to understand.\n2. The proposed method seems to be simple and effective.\n3. This paper is easy to follow.", "weaknesses": "1. The novelty is limited. (1) Both the motivations are not novel. Over-smoothing is a classic problem on GNNs and has been discussed for many years. Multi-task ability has also been discussed in previous literature [1], which has much better multi-task performance than the proposed method. (2) The method is not very novel either. The method is just a combination of existing methods (DiffPool, VGAE) with simple modification.\n2. One of the motivations of this paper is to enhance the performance of GAEs for multiple downstream tasks, and the authors also emphasize it for the proposed method. Thus the authors are encouraged to conduct experiments on link prediction task, which is also very important in graph learning and very different from node classification and graph classification. If HC-GAE  is not designed for this task or cannot perform well on it, the authors should discuss the limitation on downstream tasks and highlight the discussion.\n3. The loss function requires to compute multiple KL-divergence, and may require a lot of time to compute. The authors are encouraged to analyze the time and space complexity, and also conduct experiments to show the computational cost.\n4. The baselines are not enough and kind of old. The authors are encouraged to include more recent baselines, including auto-encoder based methods (e.g., GraphMAE2 [2]) and contrastive learning based methods (e.g., CCA-SSG [3], GGD [4] and [5]).\n5. The authors are also encouraged to include experimental results on more datasets.\n6. There is no sensitivity test on the hyper-parameters.\n\n[1] Multi-task Self-supervised Graph Neural Networks Enable Stronger Task Generalization. In ICLR 2023.\n\n[2] GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner. In WWW 2023.\n\n[3] From Canonical Correlation Analysis to Self-supervised Graph Neural Networks. In NeurIPS 2021.\n\n[4] Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination. In NeurIPS 2022\n\n[5] SEGA: structural entropy guided anchor view for graph contrastive learning. In ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: Both the motivations are not novel. Over-smoothing is a classic problem and Multi-task ability has also been discussed. The authors are encouraged to conduct experiments on link prediction task, and discuss the limitation on downstream tasks.\n\nA1: We would like to further explain and emphasize the motivation and the contribution of this work. First of all, the reviewer is correct that the over-smoothing problem is a very classical problem. But it still seriously influences most of the GNN-based methods by now, so that it has been discussed for many years until now, indicating that the over-smoothing is always an important issue for the development of novel GNN-based methods. \n\nOn the other hand, the DiffPool and the GAE are both popular methods after 2018. Specifically, the DiffPool can be seen as a kind of Hierarchical Pooling methods that rely on constructing the original graph as the hierarchical pyramid-like structures, for the purpose of extracting meaningful structural characteristics of the original graph. These hierarchical structures are formed by gradually compressing the nodes into a number of corresponding clusters based on the node features, that are extracted through the GNN model, i.e., the node features are computed by performing the graph convolution operation. The GAE also needs to extract the node features through the graph convolution operation for either the decoder and encoder. Since, the required graph operations for both the DiffPool and VGAE models suffer from the over-smoothing problem, these two classical methods still have theoretical drawbacks.\n\nTo overcome the above drawbacks, the novel contributions of this work are twofold. First, unlike the DiffPool that relies on the graph operation over the global graph structure, the proposed HC-GAE is based on the new subgraph convolution framework. Specifically, we propose to employ the hard node assignment to assign the nodes into separated clusters, resulting in separated subgraphs. The convolution operation is performed within each individual subgraphs, and the node information cannot be propagated between different subgraphs, this can thus significantly reduce the over-smoothing problem and improve the performance. Second, unlike some classical GAE-based methods (also see R#3-Q2&A2), the proposed HC-GAE can simultaneously reconstruct both the topological structures and the node features through the hierarchical strategy associated with the node assignment operation, i.e., the hard node assignment for the encoder and the soft node assignment for the decoder. Moreover, unlike some Hierarchical GAE methods (also see R#3-Q2&A2) that essentially rely on the node drop pooling (i.e., the masking strategy) and focus more on the node feature reconstruction, the proposed HC-GAE will not drop any node information, reducing the topological information loss, effectively extracting bidirectionally hierarchical structural features of the original sample graph.\n\nIn summary, both the proposed HC-GAE and the DiffPool belong to the kind of the hierarchical strategy-based GNN methods, but they are still theoretically different in terms of the detailed definition and motivation. Moreover, the proposed HC-GAE is also different from the classical GAE methods, and can significantly overcome their drawbacks. We will follow the review’s suggestion and add these statement in the manuscript, making the manuscript more polish.   \n\nFor the link prediction problem, we thank the reviewer’s constructive suggestion. This enlightens our future work, and we will discuss this in the conclusion as future works.    \n\nQ2: The authors are encouraged to analyze the time and space complexity.\n\nA2: Thanks for the suggestion. We have briefly analyzed the complexity as follows.\n\nFor the encoding and decoding process, given the input graph with node set $V$ and edge set $E$, the proposed model requires the storage complexity of $\\mathcal{O}(\\frac{1}{\\mu}\\|V\\|^2)$ where each cluster has $\\mu$ nodes. By contrast, the DiffPool needs $\\mathcal{O}(\\|V\\|^2)$. For the time complexity, if we set the layer as $k$, the proposed model requires $\\mathcal{O}(k\\mu\\log\\frac{\\|V\\|^2}{\\mu})$. Clearly, the proposed model has the similar time and space complexity with the DiffPool.\n\nFurthermore, we will following the reviewer’s suggestion and generate a family toy sample graphs with increasing sizes (e.g., from 50, 100, 150 t0 5000), and evaluate how time and space complexity varies with the increasing sizes, demonstrating the efficiency. \n\nQ3: The baselines are not enough and kind of old. The authors are encouraged to include more recent baselines, including auto-encoder based methods.\n\nA3: Thank you for the constructive suggestion. In fact, for the current experiments, we have compared the proposed model with some methods published in recent 3 years. For the node classification, these methods include: S2GAE (WSDM 2023), GraphMAE (KDD 2022). For the graph classification, these methods include: S2GAE (WSDM 2023), GraphMAE (KDD 2022), InfoGCL (NIPS 2021). To make the experiments more convincing, we have also compared the proposed method with the newest methods published in 2024, and the results are shown as follows. More experiments will be evaluated during the review stage, and please feel free to discuss with us for the experiment. Finally, we will also do some sensitivity test on the hyper-parameters, following the reviewer’s suggestion. \n\nTable 1. The experiments for node classification. For the datasets Cora, CiteSeer and PubMed, the results for Graph U-Nets (2024) are 84.4 ± 0.60, 73.2 ± 0.50, and 79.6 ± 0.20; for Hi-GMAE (2024) are 86.4 ± 0.50, 74.5 ± 0.80, and 85.3 ± 0.20; for Ours (HC-GAE)\tare 88.0 ± 0.10, 75.3 ± 0.10, and 87.6 ± 0.40.\n\nTable 2. The experiments for graph classification. For the datasets PROTEINS and COLLAB, the results for Graph U-Nets (2024) are 77.68 and\t77.56; for Hi-GMAE (2024) are 76.63 and 82.16; for ours (HC-GAE) are 78.13 and 80.41.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper appears solid enough to be above the NeurIPS bar. The paper targets a crucial problem in GNNs (over-smoothing), proposing a sufficiently innovative, strongly performant, and flexible (both in node and graph classification) solution. 

Overall, this looks like a valid contribution to the field; I recommend acceptance, although the authors are strongly advised to implement the suggestions of the reviewers in the final version.

**Note to SAC** I will add a summary of the paper once the final decision has been taken.
Decision: Accept (poster)