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 r hancock
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-04 07:21:33

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.

Main paper: 
 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 [7] , transportation networks [15] , protein compounds [29] , etc. One challenging arising in these studies is that the graph data has a nonlinear structure defined in an irregular non-Euclidean 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) [13] , for the irregular graph data. These are the so-called convolution-based Graph Neural Networks (GNNs) [31] and their related approaches [8] proposed for graph-based tasks, utilizing both graph features and topologies. For instance, the Higher-order Graph Convolutional Network (HiGCN) [6] 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 [21] has been proposed by combining the rotation-invariant graphs and the GNN to represent proteinprotein 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 a typical framework of representation learning, the classical Auto-Encoder [17] has been proposed to extract impressive results by reconstructing the input information. Especially, the Graph Auto-Encoder (GAE) [25] associated with the GNN model has further generalized the reconstruction ability for graph structures [10, 14] . Due to the extensibility, the GAEs 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) [4] 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 [24] , its decoder is retrofitted with the GNN and the re-masking operation. Based on the GraphMAE, the S2GAE [23] continues to adopt the masking strategy to improve the auto-encoder framework. To generate the cross-representation, the decoder is designed to capture the cross-correlation 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-emphasize the node features. For instance, the GraphMAE [4] 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 GAEs are usually proposed based on the GNNS, thus both 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 [16] , resulting in the notorious over-smoothing problem [1] and influence the performance of the GAEs.Contributions. The aim of this paper is to overcome the above challenging problems by proposing a 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 a coarsened node, transforming the original graph into a coarsened graph. Since the separated subgraphs 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 over-smoothing 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, we adopt 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 in effective hierarchical graph-level and node-level representations for either graph classification or node classification.Second, we propose a 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 2 reviews some related works. Section 3 gives the definition of the proposed model. Section 4 provides experimental evaluations. Section 5 gives conclusions. 
the graph neural network: 
 GNNs are widely employed for many real-world applications [12, 26, 30] , and have achieved a prominent success. The input data of GNNs is a graph, that is a kind of non-Euclidean 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 ∈ R n×d with d features, and the structure information is represented as the adjacent matrix A ∈ {0, 1} n×n . The GNN for each layer is defined asEQUATIONwhere Θ is the parameter set, and Z G is the graph embedding result for downstream tasks.The Graph Convolutional Network (GCN) [8] is a typical derivative model of GNNs, and generalizes the classical Convolutional Neural Network (CNN) [13] from the regular data to the irregular graphstructured data. One typical GCN model can be defined as the following layer-wise scheme, i.e.,EQUATIONwhere H (l) ∈ R n×d is the hidden embedding matrix for the l-th layer, W l ∈ R d×d is the trainable parameter matrix for the l-th layer, Ã = A + I is the adjacency matrix associated with the self loop, D = j Ãij is the degree matrix of Ã, and H (l+1) is the embedding matrix extracted for the next l + 1-th layer. The GCN model can effectively capture the global structural representations through the multiple stacked convolution layers defined by Eq.(2). Unfortunately, since the convolution operation depends on the node information propagation between adjacent nodes. The GNN suffers from the notorious over-smoothing problem, where the node representations of the graph tend to be similar when the GCN becomes deeper, e.g., the GNN with more than 5 convolution layers.The GAE is a powerful self-supervised framework for graph representation learning. Typical instances of GAEs include the DeepWalk [20] and the Node2Vec [2] , 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-Euclidean data [19] . As a self-supervised learning model, the aim of GAEs during the training process is the graph reconstruction [11] , that can 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 [24] 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 ∈ R n×d , 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 : Z → E , where E is the reconstructed edge set for the original edge set E. During the encoding and decoding processes, the VGAE obtains the conditional probability distributions q(Z | V, E) and p(E | Z) from the encoder and the decoder respectively, and the loss function isEQUATIONwhere KL[•] is the Kullback-Leibler divergence, E is the expection, and p(Z) is the Gaussian prior.On the other hand, the coarse-grained target contains the subgraph or the path structure. For example, the Heterogeneous Graph Masked Autoencoder (HGMA) [25] 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) [9] , 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) [34] 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) [37] 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 to 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 [11] . 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.1 also affects the feature learning for these GAE-based methods. Moreover, when the perturbation of the graph structure is conducted, the noise can also be propagated to the neighbor nodes through the edges. After several rounds of information passing, the generated graph representations may be noisy.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [No] Justification: This paper aims at overcoming the shortcomings existing in the Graph Autoencoders (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 no 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 a separate "Limitations" 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
the methodology: 
 To overcome the aforementioned challenges, we propose a novel (HC-GAE) model to learn effective graph representations. The framework of the proposed model is shown in Figure 1 . Similar to the classical GAEs, the HC-GAE model has two stages, including the encoder as 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 can be employed as 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 a family of loss function for the proposed HC-GAE model. Finally, we theoretically analyze the effectiveness of the proposed model. Coarsened Graph 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 is to generate separated subgraphs from the original graph, and the second process compresses the subgraphs into coarsened nodes of a coarsened graph.Figure 2 : The computational architecture for our proposed layer in the GNN encoder.Hard Assignment. For each l-th layer of the encoder, the input graph is denoted asG (l) = (X (l) , A (l) ), where X (l) ∈ R n (l) ×d (l)is the node feature matrix and A (l) ∈ R n (l) ×n (l) is the adjacent matrix. The number of nodes for G (l) is n (l) , and each node has d (l) features. Note that, G (l) can be either the original input sample graph when l = 1 or the coarsened graph when l > 1. For the assignment process, the graph G (l) is decomposed into a number of separated subgraphs, by assigning the n (l) nodes into n (l+1) clusters through the hard node assignment. To achieve this, we commence by computing the soft node assignment matrix S soft asEQUATIONwhere S soft ∈ R n (l) ×n (l+1) and n (l+1) < n (l) . To guarantee the separability of the resulting subgraphs, we need to assign each node into an unique cluster through a hard node assignment matrix S (l) ∈ {0, 1} n (l) ×n (l+1) , where each (i, j)-th entry of S (l) can be computed through S soft , i.e.,EQUATIONClearly, each i-th row of the hard assignment matrix S (l) selects the maximum element as 1 and the remaining elements as 0. As a result, the i-th node is only assigned to the j-th separated subgraphEQUATIONj ), where V (l) j consists of the nodes belonging to the j-th cluster and E (l) j remains the original edge connections between the nodes in V (l) j from the original input graph G (l) .Coarsening. The coarsening process compresses the separated subgraphs into coarsened nodes of the resulting coarsened graph. Given the feature and adjacency matrices X EQUATIONwhereW (l) j ∈ R d (l) ×d (l+1) (d (l) > d (l+1)) is the trainable weight matrix of the l-th layer, andZ (l) j ∈ R |V (l) j |×d (l+1) is the resulting local structural representation of G (l) j . To compress each subgraph G (l)j into a a coarsened node, we define a mapping vector s l j asEQUATIONwhereD (l) j ∈ R d (l)×1 is a trainable vector, and will play an important role in compressing each subgraph G (l) j into the node of the coarsened graph. After several local graph convolution operations on the separated subgraphs in the l-th layer, we aggregate these local information to further generate the coarsened graph, as the input graph G (l+1) for the next l + 1-th layer. To this end, for the original input graph G (l) , we collect the feature matrices Z (l) j of all j-th subgraphs G (l) j as the extracted node feature matrix Z (l) ∈ R n (l) ×d (l+1) , whose node sequences follow the original graph G (l) , i.e., each vertex feature vector of Z (l) is equal to that of the corresponding node in G (l) j . This is because each node of G (l) j essentially corresponds to an unique original node of G (l) . Given the hard assignment matrix S (l) defined by Eq.( 5) and the mapping vector s (l) j defined by Eq.( 7), we compute the feature matrix X (l+1) and the adjacent matrix A (l+1) of the resulting coarsened graph G (l+1) asEQUATIONandEQUATIONwhere is a concatenation operation, and the function Reorder reorders the sequences of [•] to follow the same node sequence of G (l) j . For the encoder, we set the greatest layer number as L, and the resulting coarsened graph G (L+1) = (X (L+1) , A (L+1) ) is the input graph for the decoder. Furthermore, we adopt a non-parameterized readout function (e.g., the MaxPooling and MeanPooling) to further embed X (L+1) as the graph-level representation for graph classification.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 3 , where the input is the retrieved graph and the output is the reconstructed graph.Reconstructed GraphFigure 3 : The illustration of our proposed layer in the GNN decoder.Reconstruction. For each l -th layer of the decoder, the input retrieved graph is denoted as G (l ) = (X (l ) , A (l ) ), where X (l ) ∈ R n (l ) ×d (l ) is the node feature matrix and A (l ) ∈ R n (l ) ×n (l ) is the adjacent matrix. Note that, when l = 1, G (l ) is essentially the resulting coarsened graph G (L) of the encoder. For the reconstruction process with G (l ) , we commence by computing the soft node assignment matrix S(l ) ∈ R n (l ) ×n (l +1) (i.e., the learnable node re-assignment matrix) as S(l ) = softmax(GNN l ,re (X (l ) , A (l ) )).Moreover, we further compute the node feature embedding of G (l ) asEQUATIONNote that, the associated graph convolution operations GNN l ,re and GNN l ,emb for Eq.( 10) and Eq.( 11) do not share the parameters. Specifically, the operation GNN l ,re generates a probabilistic distribution to expand the nodes of G (l ) to the corresponding nodes of the resulting reconstructed graph G (l +1) , and the operation GNN l ,emb extracts the new embeddings for G (l ) . With S(l ) and Z(l ) to hand, we compute the node feature matrix X (l +1) ∈ R n (l +1) ×d (l +1) and the adjacency matrix A (l +1) ∈ R n (l +1) ×n (l +1) for the reconstructed graph G (l +1) asEQUATIONand A (l +1) = S(l ) A (l ) S(l ) .(13) We employ G (l +1) as the input retrieved graph for the next l + 1-th layer, and set the greatest layer number as L (L equals to L of the encoder). The resulting graph G (L +1) = (X (L +1) , A (L +1) ) is the output of our HC-GAE, and X (L +1) is the node-level representations for node classification.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 L HC-GAE of HC-GAE includes two individual parts, and is defined asEQUATIONwhere L local is the local loss, L global is the global loss, and p(Z (l) ) is the Gaussian prior for the l-th layer. Specifically, L local aims at training the subgraph generation, that reserves the local information and avoids the over-smoothing problem for the GNN-based encoder. L global focuses on reconstructing the graph features and structures. The combination of L local and L global broadens the reconstruction requirement for multiple downstream tasks (i.e., the node and graph classification), since L local is a 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 A (•) ) rather than the node feature information (i.e., the feature matrix X (•) ) for the loss function L HC-GAE .(a) Why is the proposed HC-GAE model effective for multiple downstream tasks?As we mentioned in Section 1 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 [27] . 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, we utilize the hard node assignment to 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, we use the soft node assignment to reconstruct the 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 L global can either reconstruct the graph features or the topological structures, reducing the over-emphasizing on graph features. The local loss L local not only plays a role of regularization in L HC-GAE , but also captures the local information from the separated subgraphs, improving the generalization of the graph representations through the local information [35] .Unlike the hierarchical-based GNN methods [24, 33] , 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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 calculating 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 or the standard error of the mean. 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 as 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 didn't make it into the paper). 
experiments: 
 This section empirically evaluates the performance of the proposed HC-GAE2 for both node and graph classification on benchmark datasets, whose detailed statistical information are shown in Table 1 and Table 2 . Specifically, for the HC-GAE, we 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 decoder of the HC-GAE, we set their greatest layer numbers L and L as 3, and their node numbers for the 3 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 to compute classification accuracies, and follow the original setups for different baselines.Datasets and Baselines. For node classification, we employ five real-world datasets, i.e., Cora, CiteSeer, PubMed, Amazon-Computers and Coauthor-CS. Moreover, we compare the proposed model with six classical self-supervised models, i.e., DGI [28] , VGAE [24] , SSL-GCN [38] , GraphSage [3] , GraphMAE [4] , and S2GAE [23] . To fairly compare the proposed model and other baselines, we follow the previous study [5] to carry out 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 is 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. [22] ), two supervised GNN models (i.e., DGCNN [36] and D-iffPool [33] ), and four self-supervised GAE models (i.e., Graph2Vec [18] , InfoGCL [32] , Graph-MAE [4] , S2GAE [23] ). We employ the SVM associated with the resulting graph representations to compute the classification accuracies in Table 4 , following the previous study in [4] .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 to 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, i.e., the kernel computation is separated from the training of the SVM classifier. 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-GAE-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 to 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 it cannot extract the local information to enhance the effectiveness.  
conclusions: 
 In this paper, we have proposed a novel HC-GAE model to learn effective structural characteristics for either graph classification or node classification. During the encoding process, the HC-GAE has adopted the hard node assignment to decompose the input graph into a family of separated subgraphs, and compressed these subgraphs into coarsened nodes, resulting in a 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 over-smoothing 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 classification. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: This paper follows the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 do not think that this paper refers to this problem.Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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), fairness 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 not tied to particular applications, let alone deployments. However, if there is a 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 as 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 or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper is about graph auto-encoder. We do not think that this paper refers to this problem. 
licenses for existing assets: 
 Question: 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? Guidelines:• The answer NA means that the paper does not use 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 is used and, if 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • 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 is not available online, the authors are encouraged to reach out to the asset's creators. 
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 of 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as details about compensation (if any)?Answer: [NA] Justification: This paper is about graph auto-encoder. We do not think that this paper refers to this problem. 
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. 
 
 Appendix: 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 1 the contributions and scope are 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 in 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 it is clear that these goals are not attained by the paper.• 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 a best faith effort.• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to 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.• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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.The source code is available on https://github.com/JonathanGXu/HC-GAE 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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.

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?

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.
questions: questions: See the questions I asked in weakness.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: Although this paper introduces a novel graph representation learning method, but some problems still need to be addressed or be clearer.
1.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?
2.If the hard assignment can help the new model to reduce the over-smoothing problem, how about the soft-assignment?
3.Why the reconstructed features are effective for node classification? Why do not use the middle features?
4.Although this paper is clearly written, but the writing of Section 3 can be more polished.
questions: questions: See the weakness raised above.
limitations: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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.
1. Graph U-Nets
1. Mesh Variational Autoencoders with Edge Contraction Pooling
1. Masked Graph Auto-Encoder Constrained Graph Pooling
1. GRAPH AUTOENCODER FOR GRAPH COMPRESSION AND REPRESENTATION LEARNING
1. Multiresolution equivariant graph variational autoencoder
1. Hi-GMAE: Hierarchical Graph Masked Autoencoders

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).
questions: 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
4. 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]).
5. The authors are also encouraged to include experimental results on more datasets.
6. There is no sensitivity test on the hyper-parameters.

[1] Multi-task Self-supervised Graph Neural Networks Enable Stronger Task Generalization. In ICLR 2023.

[2] GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner. In WWW 2023.

[3] From Canonical Correlation Analysis to Self-supervised Graph Neural Networks. In NeurIPS 2021.

[4] Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination. In NeurIPS 2022

[5] SEGA: structural entropy guided anchor view for graph contrastive learning. In ICML 2023.
questions: questions: Please refer to "Weaknesses".
limitations: limitations: Please refer to "Weakness 2".

Comments: title: Replying to About out responses
About out responses
About our responses and the updated anonymous link for the CODE
About our responses
About our responses
The anonymized link for the code requested by the reviewer
comment: Thank you for the responses as well as the constructive suggestions.

After reading the new response from the review, we feel very strange and startled that the reviewer thinks he is not respected during the rebuttal stage. Maybe, there are some unnecessary misunderstandings between us, and we would like to explain in details and again show our respects to the reviewer. 

Please note, this does not mean that we entreat the acceptance for this paper. In fact, we also know this work still has some weaknesses, since this is the first work of a student who will start his PhD from this September. The other authors have published many top conferences and journals including nearly 30 TPAMI papers, thus we clearly understand the concerns raised by the reviewer, especially for the TOP conference like NIPS. By contrast, we just hope that the rebuttals can really help the student realize the drawbacks of his work, and know how to make this paper more polish in future.

First, we have expressed our appreciation for the reviewer's efforts on reviewing this paper. We also thanked the reviewer's suggestions at the beginning of each response. As summary, we also said that "please feel free to discuss with us". Thus, we trust that we have expressed our sincere respects to the reviewer.

Second, we have tried our best to answer each of the reviewer's concerns. Because some of the answers simultaneously correspond to more than one point, it just seems that there are only three answers. Specifically, A1 corresponds to the points 1 and 2 raised by the reviewer, A2 corresponds to the point 3 raised by the reviewer, and A3 corresponds the points 4-6 raised by the reviewer, respectively.

Third, as explained in the rebuttal, the aim of this paper is not only to utilize the hard node assignment. Moreover, the hard node assignment is not only used to construct the coarsened nodes. More specifically, we employ the hard node assignment to generate a number of separated subgraphs, and perform the subgraph convolution operation to interdict the node information propagation between different subgraphs, reducing the over-smoothing problem. As a result, this is entirely different from most of the existing works.

Fourth, thanks for correcting the mistake of the time complexity, and giving these new references. These will enlighten the student's future works. 

Finally, we thank the reviewer's new suggestions, and we have given our above responses to the new concerns raised by the reviewer. We hope our new response can eliminate the misunderstanding between us, and please trust that we are always appreciated with the reviewer's suggestions.

Thank you very much again for the responses.

Best Regards,

The authors
Thanks for your appreciation. We will update our paper, following the reviewer’s suggestions.

About Q&A2-1.
We think that the separated subgraph convolution has great potential for solving the over-smoothing problem. In future work, we will apply it to improve the GNN layers. Thanks for your advice about the separated subgraph convolution. It helps us recognize the worth of the proposed convolution operation. In this paper, we focus more on the graph representation learning and the multiple downstream tasks.

About Q&A2-2.
Node assignment is one of the key contributions mentioned in our paper, but not all. To explain in detail, we summarize our contributions as follows.
The first contribution of the proposed HC-GAE model is that it performs the subgraph convolution operation in each individual subgraph. Compared to the other hierarchical GAEs, our subgraph generation reduces the information propagation through edges, which is the main factor of the over-smoothing. On the other hand, we adopt the soft node assignment to reconstruct the original graph structure in the decoding. And the outputs of the decoder can be employed as the node-level representations. Since the HC-GAE is based on the hierarchical framework, it can effectively extract bidirectionally hierarchical structural features, training for multiple downstream tasks.
Second, we re-design the loss function to be suitable for our model on multiple downstream tasks. Since the HC-GAE generates the bidirectionally hierarchical structural features beyond the original GAEs, the traditional loss function might neglect their rich semantics in training. The existing hierarchical pool methods or un-pool methods hardly discuss the loss related to the bidirectionally hierarchical features. 
Last but not least, we realize the improvement of the hierarchical GAE performance. The results show that our model effectively learns the graph representations for multiple downstream tasks.
After reading the rebuttal, I feel that my concerns are not addressed.
1. I have listed 6 weak points in the review. However, the authors only give responses to 3 points.
2. I have listed some baselines, including references, but the authors did not use them. Those baselines are very fast to run.

Besides, the authors seem to be not familiar with this field
1. I still cannot understand the novelty. This method is just a combination of existing techniques. 
    1. There have been some surveys on Graph Pooling for Graph Neural Networks [1].
    2. "Hard node assignment" has been widely used in graph coarsening [2, 3, 4, 5, 6, 7, 9].
    3. "Simultaneously reconstruct both the topological structures and the node features" has been used in [7, 8, 10].
2. The complexity analysis is wrong. In graph neural networks, the adjacency matrices are implemented with sparse matrices, in order to reduce the complexity. Thus the complexity of the DiffPool is $O(|E| + |V| n_1)$ [7], where $|E|$ is the number of edges in the graph, $|V|$ is the number of nodes in the graph, and $n_1$ is the number of nodes after the first coarsening operation.


---

[1] Graph Pooling for Graph Neural Networks: Progress, Challenges, and
Opportunities. In IJCAI 2023.

[2] Training Large-Scale Graph Neural Networks Via Graph Plartial Pooling. IEEE Transactions on Big Data.

[3] Efficient Representation Learning of Subgraphs by Subgraph-To-Node Translation. ICLR 2022 workshop.

[4] CC-GNN:A Community and Contraction-based Graph Neural Network. In ICDM.

[5] SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks. NeurIPS 2022.

[6] SMGRL: A Scalable Multi-resolution Graph Representation Learning Framework. Arxiv

[7] GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding. In ICLR 2020.

[8] HARP: Hierarchical representation learning for networks. In AAAI 2018.

[9] Spectral Clustering with Graph Neural Networks for Graph Pooling. In ICML 2020.

[10] Graph U-Nets. In ICML 2019.
The responses address my concerns about this paper. Thus, I keep to recommend the acceptance and improve the score of this paper.
The authors’ responses seem reasonable for my questions. Please revise the paper as promised in the rebuttal.
Thank you for opening the codes. I will raise my score to 4.

However, I cannot still find a clear difference between the proposed and existing models.

About Q&A2-1. Separate subgraph convolution: If the separated subgraph convolution is the first novel contribution that makes a difference, why does the paper focus only on the auto-encoder? Why do the authors not apply this operation for the general GNN layers to reduce the over-smoothing effect? (e.g., separated subgraph GCN, separated subgraph GAT, ...). I cannot find a good reason why this paper is positioned as it is now.

About Q&A2-2. Node assignment: From what I understand from the responses and paper description so far, it is difficult to see clear contributions other than a 'combination' of hard and soft assignments. I think existing pool and un-pool methods have used at least one kind of operation in this paper.
Thanks for the author's response, but my concerns are not addressed.
Dear Reviewers,

Thanks for your efforts and the constructive suggestions for this paper. We have provided the response based on your comments. 

Please read our responses and feel free to discuss with us during the reviewer-author discussion stage, if you have any concerns for our response. 

Best Regards,

The authors
Dear Reviewers,

Thanks for your efforts and the constructive suggestions for this paper. We have provided the response based on your comments. 

Moreover, we have updated the code requested by the reviewer, please see the anonymous link: https://anonymous.4open.science/r/SSHPool-FB16.

Please read our responses and feel free to discuss with us during the reviewer-author discussion stage, if you have any concerns for our response. 

Best Regards,

The authors
Dear Reviewers,

Thanks for your efforts and the constructuve suggestions for this paper. We have provided the response based on your comments. 

Please read our responses and feel free to discuss with us during the reviewer-author discussion stage, if you have any concerns for our response. 

Best Regards,

The authors
Dear Reviewers,

Thanks for your efforts and the constructuve suggestions for this paper. We have provided the response based on your comments. 

Please read our responses and feel free to discuss with us during the reviewer-author discussion stage, if you have any concerns for our response. 

Best Regards,

The authors
The reviewers asked for code during the rebuttal stage, below is the anonymized link for the code.

https://anonymous.4open.science/r/HC-GAE-ECD7