GraphCroc: Cross-Correlation Autoencoder for Graph Structural Reconstruction

Authors: shijin  duan
ruyi  ding
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:46:48

Abstract: Graph-structured data is integral to many applications, prompting the development of various graph representation methods. Graph autoencoders (GAEs), in particular, reconstruct graph structures from node embeddings. Current GAE models primarily utilize self-correlation to represent graph structures and focus on node-level tasks, often overlooking multi-graph scenarios. Our theoretical analysis indicates that self-correlation generally falls short in accurately representing specific graph features such as islands, symmetrical structures, and directional edges, particularly in smaller or multiple graph contexts.To address these limitations, we introduce a cross-correlation mechanism that significantly enhances the GAE representational capabilities. Additionally, we propose the GraphCroc, a new GAE that supports flexible encoder architectures tailored for various downstream tasks and ensures robust structural reconstruction, through a mirrored encoding-decoding process. This model also tackles the challenge of representation bias during optimization by implementing a loss-balancing strategy. Both theoretical analysis and numerical evaluations demonstrate that our methodology significantly outperforms existing self-correlation-based GAEs in graph structure reconstruction.

Main paper: 
 introduction: 
 Graph-structured data captures the relationships between data points, effectively mirroring the interconnectivity observed in various real-world applications, such as web services [3] , recommendation systems [39] , and molecular structures [17, 18, 12] . Beyond the message passing through node connections [50] , the exploration of graph structure representation is equally critical [38, 15, 33, 19, 9] . This representation is extensively utilized in domains including recommendation systems, social network analysis, and drug discovery [42] , by leveraging the power of Graph Neural Networks (GNNs). Specifically with L layers in GNN, a node assimilates structural information from its L-hop neighborhood, embedding graph structure in node features.Graph autoencoders (GAEs) [19] have been developed to encode graph structures into node embeddings and decode these embeddings back into structural information, such as the adjacency matrix. This structural reconstruction process can be performed either sequentially along nodes [11, 22, 47] or in a global fashion [33] . While there has been significant advancement in both methods, most studies primarily focus on node tasks, which involve a single graph, such as link prediction [35] and node classification [15] , with decoding strategies typically reliant on "self-correlation". We define this term as the correlation of node pair from the same node embedding space. Given an n-node graph with embedding dimension d ′ on each node, its node embedding is Z ∈ R n×d ′ , thus the self-correlation is expressed as z T i z j between two nodes. Correspondingly, the "cross-correlation" depicts the node pair correlation as p T i q j , which are from two separate embedding spaces, P, Q ∈ R n×d ′ . However, studies are seldom evaluated under graph tasks, which represent graph structure on multiple graphs. The distinctiveness of each graph presents a significant challenge in accurately representing all graphs.In this work, we demonstrate the limitations of self-correlation in structure representation, such as accurately representing islands, topologically symmetric graphs, and directed graphs. Although these deficiencies may appear infrequently in large, undirected single graphs, they are prevalent and critical in smaller to moderately-sized multiple graphs, e.g., molecules [12] . Conversely, we establish that decoding based on cross-correlation can significantly mitigate these limitations, offering improvements in both undirected and directed graphs. Furthermore, the optimization of self-correlation-based GAE has to proceed in a restricted space. On the other hand, the cross-correlation can double the argument space that is not restricted during optimization. It makes the region of attraction smoother and easier to converge, indicating the superior representational ability of cross-correlation.Accordingly, we propose a novel GAE model, namely GraphCroc, which leverages cross-correlation to node embeddings and a U-Net-like encoding-decoding procedure. Previous GAE models carefully design the encoder for a faithful structure representation, yet keep the decoder as the straightforward node correlation computation. Differently, GraphCroc retains the freedom of encoder design, facilitating its architecture design for downstream tasks, rather than structure representation. We define the decoder as a mirrored architecture of the encoder, to gradually reconstruct the graph structure. The encoder shapes the down-sampling of GraphCroc, while the decoder half performs the up-sampling for structural reconstruction. In addition, regarding the unbalanced population of zeros and ones in graph structure, i.e., sparse adjacency matrix, we define loss balancing on node connections. We highlight our contributions as follows:• We analyze the representational capabilities of self-correlation within GAE encoding, highlighting its limitations. Furthermore, we elaborate how cross-correlation addresses these deficiencies, facilitating a smoother optimization process. • We propose GraphCroc, a cross-correlation-based GAE that integrates seamlessly with GNN architectures for graph tasks as its encoder, and structures a mirrored decoder. GraphCroc offers superior representational capabilities, especially for multiple graphs. • To the best of our knowledge, this is the first evaluation of structural reconstruction using GAE models on graph tasks. Besides, we assess the performance of our GraphCroc model integrated with other GAE strategies and on various downstream tasks. • We evaluate the potential of GraphCroc in domain-specific applications, such as whether a GAE focused on structural reconstruction could be an attack surface for edge poisoning attacks, given the effectiveness and stealth of adversarial attacks using AE in vision tasks. 
gae structural reconstruction analysis 2.1 preliminary: 
 Graph Neural Network As Graph Neural Networks (GNNs) have been defined in various ways, without loss of generality, we adopt the computing flow in [45] to define the graph structure and a general GNN model. A graph G = (V, E) comprises n nodes, each with a feature represented by a d-dimensional vector, resulting in a feature matrix X ∈ R n×d . The set of edges E is depicted by an adjacency matrix A ∈ {0, 1} n×n , which indicates the connections between nodes in G. A GNN model f (X, A) is utilized to summarize graph information for downstream tasks.The feed-forward propagation of the l-th layer in GNN f (•) isEQUATIONh l ∈ R n×d l is the input feature of the l-th layer, where h 1 = X and d l is the feature dimension of each node specified by each layer. Âl = A l + I is the adjacency matrix (self-loop added) of the input graph structure in each layer. Note that Âl will be consistent in the absented pooling layer scenario, such as the node classification task, yet it can vary along GNN layers in graph tasks due to the introduction of graph pooling layers [9] . Subsequently, we use the diagonal node degree matrix Dl of Âl to normalize the aggregation. For layer components, W l is the weight matrix and σ is the activation function in the l-th layer.The naïve GAE is proposed to reconstruct the adjacency matrix A of a graph G through node embedding Z:EQUATION) GAE first encodes the graph G through a general GNN model f (•) (a.k.a. inference model), resulting in node embeddings in the latent space Z ∈ R n×d ′ where d ′ is the latent vector dimension for each node. The generative model is non-parameterized, but the tensor product of the node embeddings. It measures the correlation between each node pairs, i.e., sigmoid(z T i z j ), normalized as the link probability by the logistic sigmoid function. Usually, the predicted connection can be defined as an indicator function I( Ãi,j ) = I( Ãi,j ≥ th), e.g., th = 0.5.With the same functionality, GAE has been improved with other enhancements, such as variational embedding [19] , MLP-based decoder [33] , masking on features [15] and edges [23] . Note that other correlation measurements in the decoder are also proposed, such as Euclidean distance between node embedding [26] , i.e., Ãi,j = sigmoid(C(1-∥z i -z j ∥ 2 2)), where C is a temperature hyperparameter. In general, they predict the connection between node pairs by measuring the similarity, such as inner product and L2-norm, from the same embedding space. Related work is discussed in Appendix A.To generalize the discussion, we set the representation capability of the encoder as unrestricted, i.e., allowing Z to be generated through any potentially optimal encoding method. On the decoding side, self-correlation is applied following Eq.2. We identify and discuss specific (sub)graph structures that are poorly addressed by current self-correlation methods:Islands (Non Self-Loop). Both the inner product and the L2-norm of a node embedding pair fail to accurately represent nodes without self-loops, whereEQUATION2 ) = C > 0, the predicted value I( Ãi,i ) defaults to 1 when threshold 0.5 is applied to the sigmoid output. This limitation underlies the common homophily assumption in previous research [42] , that all nodes contain self-loops; it treats self-loops as irrelevant to the graph's structure. However, there is a huge difference between the self-connection on one node and the inter-connection between nodes in some scenarios; for example, on heterophilous graphs [51] , nodes are prone to connect with other nodes that are dissimilar -such as fraudster detection. Topologically Symmetric Structures. If graph structure is symmetric along an axis or a central pivot, as demonstrated in Figure 1 , the self-correlation method cannot represent these structures as well.𝑋 1 𝑋 𝑙1 𝑋 𝑙2 𝑋 𝑟1 𝑋 𝑟2 𝑋 1 𝑋 2 𝑋 3 𝑋 4 𝑋 5 𝑋 6 𝑋 2Definition 2.1 (Topologically Symmetric Graph). A symmetric graph G = (V, E) has the structure and node features topologically symmetric either along a specific axis or around a central node. For an axisymmetric graph, the feature matrix is denoted as X = {X 1 , . . . , X n1 } ∪ {X l1 , . . . , X ln2 } ∪ {X r1 , . . . , X rn2 }, such that n 1 + 2n 2 = n. X i represents the node features on the axis, and for each paired node off the axis, X li = X ri . The connections are also symmetric, satisfying A li,: = A ri,: . In a centrosymmetric graph, the pivot node has feature X 1 , and other nodes share the same feature X 2 = . . . = X n-1 . Additionally, the adjacency relationships for these nodes are identical, with A i,: = A j,: for all i, j ∈ [2, n]. Lemma 2.2. Given an arbitrary topologically symmetric graph G = (V, E) and an encoder f (X, A), the self-correlation decoder output will always have I( Ãli,ri ) = 1.Proof. Due to the symmetry on graph G = (V, E) from the definition above, we have f (X i , A i,: ) = f (X j , A j,: ) for nodes i and j that are symmetric about the axis or pivot. Thus, we can derive z i = z j . For the prediction on link between i and j, we have Ãi,j = sigmoid(z T i z j ) = sigmoid(z T i z i ) ≥ 0.5. Similarly, for the L2-norm method, we have Ãi,j = sigmoid(C(1EQUATION2 )) = sigmoid(C) > 0.5. In both decoding methods, the decoder is prone to predict the edge between two symmetric as positive, I( Ãi,j ) = 1.Consequently, the self-correlation method will indicate a positive connection between two symmetric nodes, regardless of their real connection status on the graph G. Note that for variational GAE, Z is sampled from a Gaussian distribution whose mean and variance come from GNN models; thus it still follows the above lemma, even if randomness is involved during the encoding.Directed Graph. Another straightforward deficiency of the self-correlation method is that it always generates a symmetric adjacency matrix, Ã, which is not suitable for directed graphs that require an asymmetric adjacency matrix. This issue is also acknowledged in [20] , which proposes a solution involving dual encoding using the Weisfeiler-Leman (WL) algorithm [41] and node label coloring. However, this solution constrains the encoder to a dual-channel structure while maintaining the same decoding method as described in Eq. 2. This restriction can limit the flexibility of the encoder architecture, making it less adaptable for various downstream tasks.Furthermore, we conduct a theoretical analysis of the dimensional requirements of node embedding to represent graph structures using self-correlation, in Appendix B.Instead of self-correlation, we advocate cross-correlation to reconstruct the graph structure, denoted by Ã = sigmoid(P Q T ), where P, Q ∈ R n×d ′ . This approach allows us to decouple the variables involved in calculating the correlation, thus overcoming the inherent limitations of self-correlation.Expressing Islands. For each node i ∈ [1, n], the sign of p T i q i can be flexibly determined by p i and q i , allowing it to be either positive or negative. Consequently, the presence of an island can be effectively modeled using Ãi,j = sigmoid(p T i q i ) or sigmoid(C(1EQUATION)). This approach avoids the limitations associated with self-correlation, which restricts the sigmoid input to positive.Expressing Symmetric Structure. Cross-correlation is particularly effective in capturing topological symmetric structures. Given a node pair (i, j) that is topologically symmetric about an axis or pivot, for undirected graphs, we have p i = p j and q i = q j . However, since p i and q j (as well as p j and q i ) are not directly dependent on each other, the sign of p T i q j = p T j q i can be either positive or negative. Therefore, I( Ãi,j ) = I(sigmoid(p T i q j )) is able to yield 0 or 1, depending on the specific values of node embedding p i and q j . This flexibility can be supported by the L2-norm decoding as well.Expressing Directed Graph. A similar interpretation extends to the representation of directed graphs. For two nodes i and j, the directed edges can be defined by p T i q j for one direction and p T j q i for the other. Since these four latent vectors do not have explicit dependencies among them, the directions of the edges can be independently determined using cross-correlation, capturing the directional connections between nodes.In Appendix C, we further discuss and visualize how our cross-correlation approach represents these specific graph structures.We highlight the superiority of cross-correlation over self-correlation in the optimization process of GAE training. Considering the decoder optimization problem, where we aim to satisfy the constraints:EQUATIONfor each element in matrix A. This involves finding Z ∈ R n×d ′ or P, Q ∈ R n×d ′ that maximize the number of satisfied constraints. Additionally, for an undirected graph, the symmetry A i,j = A j,i imposes the requirement that I(sigmoid(p T i q j )) = I(sigmoid(p T j q i )), ensuring that both p T i q j and p T i q j should have the same sign. In the case of cross-correlation, where P and Q are independently determined, and all constraints can well align with the generation of P and Q. However, this is not the case in self-correlation, where z T i z j = z T j z i inherently overloads the symmetry constraint. For example, if A i,j = A j,i = 1, we only require p T i q j > 0 and p T j q i > 0 for cross-correlation, while they become restrictive as We apply PCA for dimension compression and the Savitzky-Golay filter to help trace visualization. We also set z i = p i ̸ = q i at the beginning of optimization to ensure that the traces of z i in (a) and p i in (b) start from the same point. (c) provides the BCE loss trace of this graph during training, showing that cross-correlation can lead the reconstruction to a better solution. (d) demonstrates the distribution of diagonal elements during training, i.e., z T i z i for self-correlation and p T i q i for cross-correlation. The results of other graphs are provided in Appendix G.2.z T i z j = z T j z i > 0 in self-correlation.Cross-correlation offers a broader argument space, providing more freedom to find solutions that satisfy the constraints for reconstructing A. By employing gradient method during optimization, this process can be understood as the trajectory of P and Q being unrestricted in the argument space R n×2d ′ , while the trajectory of Z is confined within a restricted space as R n×d ′ . Therefore, cross-correlation facilitates smoother and more efficient convergence during optimization. Note that this restriction comes from the nature of self-correlation and cross-correlation, which is interpreted as the space reduction. During optimization, we can first find (local) optimal P and Q, then apply (P Q T + QP T )/2 to interpret it as a symmetric matrix Ã, like ZZ T ; this procedure can still outperform direct optimization on ZZ T .Validation on PROTEINS Here, we make a quick validation of our discussion on a subset of PROTEINS [2] that is a graph task, in Figure 2 . By comparing Figure 2 (a) and (b), the trajectory of node embedding during training demonstrates the superiority of cross-correlation over self-correlation. As the node embeddings are evolving under self-correlation, they frequently change their direction; this indicates that the region of attraction between the start and end point is not smooth and may follow a restricted manifold, thus the embedding cannot well converge to the local minimum. On the other hand, the region of attraction under cross-correlation is much smoother and easy to guide the node embedding to a better solution. This can also be evidenced by the lower loss under cross-correlation in Figure 2(c ). Another concern of cross-correlation is that p T i q i cannot naturally satisfy A i,i = 1 while z T i z i in self-correlation is able to. Nevertheless, p T i q i can be encouraged to perform with positive sign, proved by Figure 2(d) , that all the diagonal element reconstruction p T i q i under cross-correlation can achieve positive sign at the end of training, leading toI(sigmoid(p T i q i )) = A i,i = 1.3 GraphCroc: Cross-Correlation-Based Graph Autoencoder Encoder Architecture Our work scales the normal single-graph representation to multi-graph for graph tasks, and we do not specify the encoder structure, but free it as the downstream tasks require. For graph tasks, the GNN model has a sequence of message passing layer and pooling layer to coarsen the graph to higher-level representation. In the end, a readout layer [8, 9, 31] is applied to summarize the graph representation to the latent space. We define the encoder as encoder (ours):EQUATIONwhere Z ′ ∈ R n ′ ×d ′ has a reduced number n ′ of node embeddings. Besides, we exclude the readout layer from the encoder, yet assign it to the start of downstream tasks.To separately produce two node embeddings, P and Q, we divide the decoding process into two parallel and self-governed decoders. Unlike [20] , we leave The decoder has two paths to generate the node embedding for cross-correlation; each decoder is a mirrored structure of the encoder. Each decoder layer accepts the node feature and graph structure information from the corresponding encoder layer. Notably, the GCN module shown on the right incorporates skip connections and normalization to improve performance. the encoder design to better suit specific downstream tasks, and focus primarily on the reconstruction challenges within the decoder design. Still with the latent vector Z = f (X, A) generated by the encoder, we define our decoder as follow:(𝑋, 𝐴) GCN Norm(A) GCN(X,A) LayerNorm 𝐴 ℎ GCN (ℎ 1 , 𝐴) (ℎ 2 , 𝐴′ 2 )decoder (ours): Ã = sigmoid(P Q T ), P = g 1 (Z, {A ′ , h ′ }), Q = g 2 (Z, {A ′ , h ′ }) (5)g 1 (•) and g 2 (•) are two individual GNNs with the same structure, which take as input the latent vectors Z, the adjacency matrix groups {A ′ } and node feature groups {h ′ } from the encoder (as discussed in Section 3). Here, {A ′ , h ′ } is required for graph tasks that involves pooling/unpooling. In Appendix D, we further discuss why the two embeddings, P and Q, in our decoder do not converge to each other, thereby preventing convergence to self-correlation decoding.Autoencoder Architecture In Figure 3 , we present the autoencoder architecture, GraphCroc. The design of the encoder/decoder pair is inspired by the Graph U-Net structure [9] , originally proposed for classification tasks. While the cross-correlation kernel remains unchanged, the encoder/decoder configuration can be tailored to various applications. Nevertheless, we utilize the Graph U-Net structure as a case study to demonstrate the effectiveness of cross-correlation.The GraphCroc architecture follows the encoder formulations from Eq. 4 for multiple graphs and the decoder from Eq.5. During the encoding process, the graph architecture A ′ is captured at each layer, which is then utilized in the corresponding unpooling layers to reconstruct the graph structure, as detailed in [9] . Additionally, skip connections enhance the model by capturing the node features h ′ at each encoder layer and integrating them -either through addition or concatenation -into the node features of the corresponding decoder layer. Importantly, we emphasize the significance of implementing layer normalization [1] following each GNN layer. Although often overlooked in previous GAE studies due to the typically small number of layers, layer normalization is crucial for regulating gradient propagation as the number of layers increases.The training on GAE is highly biased given the sparsity of the adjacency matrix. In practice, it is quite common that zero elements in A take the majority, e.g., around 90% in PROTEINS [2] . For a certain A and its estimation Ã, we denote the vanilla loss function asL = c0 i=1 L 0 i + c1 j=1 L 1 j, where in total c 0 zeros and c 1 ones in A, and L 0 /L 1 is their corresponding loss on each element. Since c 0 ≫ c 1 , the zero part dominates the loss function, inducing the decoder to predict zeros. Thus, we apply a scaling factor for each item:EQUATION)The derivation is provided in Appendix E. 4 EvaluationG A E V G A E E G N N o u r s ( S C ) D i G A E o u 
theory assumptions and proofs: 
 • 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: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). 
experimental setup: 
 Dataset We assess GraphCroc in various graph tasks. Specifically, we utilize datasets for molecule, scaling from small (PROTEINS [2] ) to large (Protein-Protein Interactions (PPI) [12] , and QM9 [29] ), for scientific collaboration (COLLAB [46] ), and for movie collaboration (IMDB-Binary [46] ). Further details on these datasets are provided in Appendix F.1.GraphCroc Structure During evaluation, our GraphCroc structure, especially the GCN layer number, is determined by the scale of graph. Assuming the average node number in a graph task is n, we set up an empirical layer number L as n • Π L i=1 (0.9 -i) = 2, so that the number of nodes can be smoothly reduced to two at the end of encoding [9] . Besides, we use node embedding dimension d ′ ≈ n, following analysis in Appendix B. Other detail is provided in Appendix F.2.Table 1 demonstrates the graph reconstruction capabilities of GAE models for multi-graph tasks by presenting ROC-AUC scores on adjacency matrix reconstruction. We compare our model against prevalent self-correlation kernels in GAEs and a cross-correlation method designed for directed graphs. Comparing the basic inner-product methods, GAE and VGAE [19] , the variational extension in VGAE does not obviously improve the performance over GAE in graph tasks. However, by enhancing the GAE architecture itself, i.e., using our GraphCroc architecture, the reconstruction efficacy is significantly increased; GraphCroc under self-correlation can achieve 3/5 second bests among all GAE models. This underscores the graph representation capability of the U-Net structure [9] . Additionally, the L2-norm decoding method generally outperforms the inner-product approach (GAE and VGAE), although it struggles with large graphs such as PPI, which requires too much GPU memory to be trained during our reproduction. On the other hand, the cross-correlation method (DiGAE) provides a consistent albeit modest representation across different graph sizes. This demonstrates the cross-correlation ability to represent multiple graphs in various scenarios. However, the GNN architecture limits its capability to capture enough structural information. By integrating the strengths of cross-correlation with the U-Net architecture, our GraphCroc GAE model consistently excels over other methods, offering significant advantages in all the graph tasks tested. Even on large graphs, such as PPI with over 2,000 nodes, GraphCroc can still achieve an AUC score over 0.98. To further demonstrate the effectiveness of the cross-correlation mechanism, we evaluate GAE models with alternative architectures under cross-correlation, in Appendix G.1. The reconstruction results for these architectures are consistent with those in Table 1 , though they exhibit slightly lower AUC compared to GraphCroc.While the AUC score indicates how well a model reconstructs edges, it does not measure the model's ability to exactly reconstruct a whole graph. To address this, we employ the Weisfeiler-Leman isomorphism test (WL-test) [41] , which assesses the structural equivalence between the original and reconstructed graphs. graphs, in the IMDB-B task. Our GraphCroc model significantly outperforms other GAE methods, while the self-correlation variant also delivers superior performance. Interestingly, while the L2-norm achieves a high AUC score, it is feeble to well reconstruct the entire graphs; this indicates there are some connection patterns in graph inherently hard to be captured by L2-norm representation. Other results of WL test are provided in Appendix G.3, which demonstrates similar observations as above.In Figure 5 , we select a representative graph from each of the PROTEINS, IMDB-B, and COLLAB tasks to visually compare the structural reconstruction from GAE models. It is evident that GraphCroc performs well in accurately recovering graph edges. GAE methods with inner-product and vanilla GNN architectures, such as GAE, VGAE, and DiGAE, tend to overpredict edge connections. Meanwhile, EGNN performs adequately within node clusters, but struggles with inter-cluster connections. This echos our discussion about the partial representation deficiency in L2-norm. To make cross-correlation more pronounced in our evaluation, the above experiments implement only the basic inner-product representation, i.e., sigmoid(P Q T ). In addition, previous studies have extensively explored data augmentation and training enhancements to optimize GAE models. Specifically, we examine the performance of GAE with cross-correlation applied to different training strategies in Figure 6 , using the PROTEINS dataset as a case study.We evaluate three other prevalent decoding enhancements to compare their performance with the standard inner-product decoding (baseline) under the cross-correlation method. The variational decoding [19] generates node embeddings from a Gaussian distribution, with mean/std determined by the decoder outputs. Although a similar final AUC was achieved, it falls short of the baseline on the PROTEINS task at early convergence. For the other two strategies, edge masking [35] and L2-norm representation [26] , they facilitate faster convergence during the initial training stages. However, we find that the enhancement of these strategies is highly dependent on graph tasks. Our further analysis on other graph tasks (Appendix G.4) demonstrates that the L2-norm and masking could converge to worse structural reconstructions than our baseline training. Therefore, we still advocate our training and representing methods for GAE models on various graph tasks.Table 2: Evaluation on graph classification tasks. We compare our model with other GNN methods, such as unsupervised learning (Infograph [34] ), contrastive learning (GraphCL [48] and In-foGCL [44] ), and generative learning (GraphMAE [15] , S2GAE [35] and StructMAE [25] ). The encoder of our model is extracted from GraphCroc, and is cascaded with a randomly-initialized 3-layer classifier. We train our models by only fine-tuning for 10 epochs or training for 100 epochs. The best results are in bold, and the second bests are underlined. Results are averaged on 5 runs. One common application of autoencoder models is leveraging their potent encoders for downstream tasks. We evaluate our GraphCroc model by employing its encoder in graph classification tasks, as summarized in Table 2 . Notably, generative approaches like GraphMAE, S2GAE, StructMAE, and our GAE model tend to surpass traditional unsupervised and contrastive learning methods.Although contrastive learning incorporates negative sampling, its effectiveness is limited in multigraph tasks. This finding corroborates the observations in Tab.4 of [44] , which indicate that while negative sampling substantially boosts performance in single-graph tasks (e.g., node classification), it has little impact on graph classification tasks. In contrast, GAE models deliver robust graph representations, particularly for small-to-moderate-sized graphs, enhancing their utility in graph classification. Furthermore, our GraphCroc model significantly outperforms self-correlation methods (GraphMAE and S2GAE) in representing graph structures, demonstrated in Table 1 , enabling the encoder to effectively capture the structural information of input graphs. Consequently, classifiers leveraging our encoder can achieve high performance with finetuning over only several epochs. Continued optimization of our classification models promises to further elevate their performance in graph classification tasks, surpassing other GAE-based models.Research in vision tasks demonstrates that manipulating the latent space with perturbations enables AE to produce adversarial examples with stealthiness and semanticity [6, 16, 32, 40, 43] . Given AE's success in vision domain, we raise the concern -whether a GAE can be utilized to generate adversarial graph structures by modifying the latent vectors? Current graph adversarial attacks directly modify the input of GNNs, highly inefficient due to the discreteness of graph structures [7, 37] . By directly conducting attacks in the latent space, GAE could be a potentially efficient attack surface. In Table 3 , we demonstrate the effect of small perturbations on the latent space using random noise injection, PGD [27] , and C&W adversarial noise injection [7] on graph classification tasks. We limit all attacks on the latent space with a maximum query number of 400 and report the classification accuracy of perturbed graphs and the number of edge changes. Note that we focus solely on the structure modification without changes on the node features. Our observations indicate that conducting adversarial attacks on the latent space of the graph autoencoder effectively reduces model accuracy, although it could yield significant edge changes. Compared to adversarial attacks on graph structures using discrete optimization methods, our latent attacks demonstrate comparable performance in terms of accuracy and can be performed in batches with high efficiency. Nevertheless, due to the discrete nature of graph structures, the distortion in edge changes is hard to be always controlled at a low level. Our evaluation of GraphCroc's latent space reveals a potential vulnerability, indicating that adversarial attacks on a graph autoencoder's latent space can provide efficient structural adversarial attacks. More detail on the adversarial attack with GAE is discussed in Appendix F.3. 
conclusion: 
 Graph autoencoders (GAEs) are increasingly effective in representing graph structures. In our research, we identify significant limitations in the self-correlation approach employed in the decoding processes of prevalent GAE models. Self-correlation inadequately represents certain graph structures and requires optimization within a constrained space. To address these deficiencies, we advocate crosscorrelation as the decoding kernel. We propose a novel GAE model, GraphCroc, which incorporates cross-correlation decoding and is built upon a U-Net architecture, enhancing the flexibility in GNN design. Our evaluations demonstrate that GraphCroc outperforms existing GAE methods in terms of graph structural reconstruction and downstream tasks. In addition, we propose the concern that well-performed GAEs could be a surface for adversarial attacks. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Our work does not have ethical or societal concern.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: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 a best faith effort.12. 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?Answer: [NA] Justification: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: [NA] Justification: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:Guidelines:• 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. 
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:Guidelines:• 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. 
 
 Appendix: Graph representation has been explored through various methods. Auto-regressive models [24, 49, 14] generate graph structures by sequentially querying the connectivity between node pairs, which can be computationally expensive for large graphs, e.g., n 2 queries required for the adjacency matrix. Similarly, diffusion-based graph models [21] construct graph structures through multiple steps, such as degree matrix reconstruction [5] . These methods primarily focus on graph generation, creating rational graph structures from random noisy node islands.In contrast, Graph Autoencoder (GAE) methods represent graph structures as node embeddings, designed to reconstruct the graph either sequentially [47, 22] or globally [33, 19, 15, 30, 20] . The very beginning graph structure representation is proposed in [19] with self-correlation (applied with Eq. 1 and 2) and further expresses the node embedding with a variational approach. Later, GAE has been widely explored with sequential and global generating methods. For the sequential GAE models, GraphRNN [47] proposes an autoregressive model, which generates graphs by summarizing a representative set of graphs and decomposes the graph generation into a sequence of node and edge formations. Similarly, [22] targets molecule generation and proposes to regard the graph structure as a parse tree from a context-free grammar, so that the VGAE can apply encoding and decoding to these parse trees. However, the sequential graph strategies usually are time-consuming or requiring expensive processing.On the other hand, the global methods, which directly encode the graph in latent space and decode to the entire graph structure, have better scalability on larger and complicated graph structures and can be time efficient. GraphVAE [33] follows the VGAE idea and proposes an autoencoder model that can generate the graph structure, node features, and edge attributes all at once. EGNN [30, 26] decodes the node embedding to graph structures by applying the L2-norm between embeddings. GraphMAE [15] applies the masking strategy and targets to reconstruct the node features of various scales of graphs, where its GAE architecture also follows the classical GAE model. DiGAE [20] lies in the structural reconstruction on directed graphs, and firstly proposes to use the cross-correlation to express the node connection from two embedding spaces. Although these methods are effective recover node connections on a single graph, and even some of them tried the reconstruction of whole graph on graph tasks, there is no explicit evaluation to demonstrate how the global GAE model perform when it generate graph structure once and on moderate to large graph tasks. Besides, previous work follows the self-correlation strategy, which has been proven less effective than cross-correlation on graph tasks, in our work.As the node embedding dimension d ′ is underexplored before, it is mostly regarded as a hyperparameter to set up in advance. On the other hand, d ′ highly effects the encoder representing ability, which is based on the graph scale. There is necessity to discuss the dimension requirement of node embeddings for a certain graph scale.Remark. We share a toy example to demonstrate how the d ′ design has an impact on the encoder ability. Assume an extreme case d ′ = 1, each node is represented by a scalar. The node embeddings(z i , z j , z k ) ∈ R 3 can never represent a connection set (A i,j , A i,k , A j,k ) = (0, 0, 0). Because if ∃(z i , z j , z k ) ∈ R 3 such that I( Ãi,j , Ãi,k ) = (0, 0), i.e., z i z j < 0 and z i z k < 0, then we must have sign(z j z k ) = sign(z j z 2 i z k ) = -1. This will always yield to I( Ãj,k ) = 0 ̸ = A j,k . The similar result can be directly observed when d ′ = 2 and there are four nodes, then ∄(z i , z j , z k , z l ) ∈ R 4 which can represent connection set (A i,j , A i,k , A i,l , A j,k , A j,l , A k,l ) = (0, 0, 0, 0, 0, 0). Lemma B.1. For self-correlation method in the decoder, to make the connection constraints always solvable on the n-node scenario, i.e., requiring z T i z j > 0 or z T i z j < 0 for each node pair, the node embedding dimension d ′ need to satisfy d ′ ≥ (n -1) at least. Proof. We first prove that for n nodes, there is always existing a connection case, such as no connection on all node pairs, that ∄{z} ∈ R n×d ′ can represent when d ′ < (n -1). We consider the case that A i,i = 1 and A i,j = 0 for all i, j ∈ [1, n], such as z T i z j < 0. When d ′ < (n -1), e.g., d ′ = (n -2), there will be at most (n -2) linearly independent node vectors. Assume the first (n -2) vectors z 1 to z n-2 are linearly independent, then we will always find a linear combination such that n-1 i=1 α i z i = 0, where vector α = {α 1 , ..., α n-1 } ̸ = 0. Here, we let the elements of α be grouped as positives, negatives, and zeros, as α + , α -, α 0 . Thus, we haven-1 i=1 α i z i = 0 ⇒ a∈α + a i z i = b∈α - -b j z j = w a)If both α + , α -are not empty, we do inner product on these two terms:0 < w T w = a∈α + a i z i T b∈α - -b j z j = -a i b j • z T i z j ≤ 0This causes conflict on the inequality. b) If one of α + and α -is empty, e.g., α -= ∅, we do inner product between the positive part and z n :0 = 0 T z n = a∈α + a i z T i z n < 0which also cause inequality conflict. Thus, the assumption on d ′ < (n -2) does not hold.Then, we prove that when d ′ = (n -1), there always exists {z} ∈ R n×d ′ to represent all the connections through the decoder. We use inductive method to prove it. It is straightforward that when n = 2, d ′ = 1 can satisfy the representation on any graph A ∈ {0, 1} 2×2 . Assuming d ′ = n -1 is a feasible configuration for an arbitrary n-node graph, we need to prove that d ′ = n is also sufficient for (n + 1)-node graph: We denote a satifiable node embedding from the n-node graph as Z = {z i } ∈ R n,n-1 . By extending it to d ′ = n for one more node coming, we specify the node embedding of the first n nodes as 1] ; this specification can still satisfy arbitrary inequality constraints between node pairs in the first n node. For the (n + 1)-th node, we need to find z ′ n+1 ∈ R n such that z ′T n+1 z ′ i satisfy arbitrary inequalities. Through the inductive method, it is also straightforward to prove that there exists Z with rank (n -1), thus our extension to one extra dimension will make rank({z ′ i }) = n for i = [1, n] . Therefore, we can always find a non-zero vector α such that z ′ n+1 = n i=1 α i z ′ i . For each constraint z ′T n+1 z ′ i being positive or negative (in total n constraints), we can reduce them to system of equations where the constants are scalars satisfying the constraints:z ′ i = [z i , 0] for i = [1, n -1] and z ′ n = [z n ,α 1 z ′T 1 z 1 + ... +α n z ′T n z 1 = c 1 ... α 1 z ′T 1 z n + ... +α n z ′T n z n = c n    n equations denoted as M α = C.Here, the vector α is solvable as long as rank(M ) = rank(M |C), which can be tuned by specifying C.Although this theoretical analysis indicates that the node embedding dimension should be large enough to ensure the graph structure reconstruction, we observed in experiments that the embedding dimension can usually be smaller (e.g., d ′ ≈ n/2) because the hard-to-solve structures are not common in graph tasks. Nevertheless, it provides a preterior node embedding dimension suggestion, and our evaluation widely adopts this lemma and takes d ′ ≈ n in all experiments.In Sec. 2.2 and 2.3, we explore the limitations of self-correlation and the effectiveness of crosscorrelation in expressing specific graph structures. Given that previous GAE research often evaluates undirected asymmetric graph structures, the evaluation on special graph structures is usually overlooked. Hereby we evaluate how our method GraphCroc and other GAE models perform on specific graph structures as aforementioned.Island (without self-loop) and symmetric graph structure. We generate 4 topologically symmetric graphs devoid of self-loops. Thus, the task is to have the evaluated GAE learn to reconstruct these graph structures and assess their performance. The visualization of their reconstruction is presentedGround Truth GraphCroc GraphCroc(SC) in Fig. 7 . The visualization clearly demonstrates that our GraphCroc model effectively reconstructs these specialized graph structures. For DiGAE which is also based on cross-correlation, it can also well reconstruct the special graph structures, further supporting our discussion in Sec. 2.3.In contrast, other self-correlation-based models tend to incorrectly predict connections between symmetric nodes and islands, and incorrectly introduce self-loops on nodes. Note that for EGNN, it does not predict positive edges between nodes, which seems not to follow our analysis in Sec. 2.2 with Euclidean encoding sigmoid(C(1 -∥z i -z j ∥ 2 )). This is because EGNN slightly improves this encoding to sigmoid(w∥z i -z j ∥ 2 + b), where w and b are learnable. Since no-self-loop nodes require sigmoid(w∥z i -z i ∥ 2 + b) = sigmoid(b) < 0.5, b is forced to be negative, inducing negative prediction on symmetric edges that have z i = z j under symmetric structures. Therefore, EGNN still cannot handle well the graph reconstruction on the special graph structures.Directed graph structure. We conduct an evaluation using datasets of directed graphs. We compare GraphCroc with DiGAE, as only cross-correlation-based methods are capable of expressing directional relationships between nodes. To construct the dataset, we sample subgraphs from the directed Cora_ML [28] and CiteSeer [10] datasets. Specifically, we randomly select 1,000 subgraphs. Of these, 800 subgraphs were used for training and 200 for testing. The results are detailed in Table 4 , where N represents the average number of nodes per graph: The difference between two latent embeddings (denoted as P and Q) is fundamental to crosscorrelation as opposed to self-correlation in which P = Q; therefore, it is necessary to make them not converge to each other. One method of explicitly controlling this divergence is by incorporating regularization terms into the loss function, such as cosine similarity (cos(P, Q)).Our decoder architecture inherently encourages differentiation between P and Q since they are derived from two separate branches of the decoder. This structure can allow P and Q to diverge adaptively in response to the specific needs of the graph tasks. If a graph cannot be well represented by self-correlation, our two-branch structure will encourage sufficient divergence on P and Q to suit structural reconstruction. To evaluate the differentiation between them, we compute their cosine similarity and present a histogram of these values for each graph task in Figure 8 . Across all tasks, the cosine similarity between the node embeddings under cross-correlation is generally low, typically below 0.6. This shows that our twobranch decoder effectively maintains the independence of the node embeddings, which are adaptively optimized for various graph tasks. Furthermore, this adaptive optimization underscores the superiority of cross-correlation in real-world applications, as evidenced by GraphCroc's superior performance in graph structural reconstruction compared to other methods (Table 1 ).We adopt binary cross-entropy (BCE) loss to evaluate reconstruction between prediction Ã = sigmoid(P Q T ) and ground truth A. Our loss balancing is based on an i.i.d. assumption between L 0 and L 1 , where the loss definition follows L(i, j) = BCE( Ãi,j , A i,j ) on the node pair (i, j).For a certain graph G, we assume there are c 0 zero elements and c 1 one elements in A, where c 0 ≫ c 1 . To balance the loss between zeros and ones, we apply scaling factors on each element loss:L( Ã, A) = α 0 c0 i=1 L 0 i + α 1 c1 j=1 L 1 j .The scaling has two targets: to keep the loss magnitude and to balance the zero/one influence. Thus, we construct the following linear equations:α 0 c 0 L 0 + α 1 c 1 L 1 = c 0 L 0 + c 1 L 1 α 0 c 0 L 0 = α 1 c 1 L 1 ⇒ α 0 = c 0 + c 1 2c 0 , α 1 = c 0 + c 1 2c 1The scaling factors α 0 and α 1 are derived.We provide the graph detail of graph tasks selected in our evaluation, in Table 5 . For IMDB-B and COLLAB without node features, we take the one-hot encoding of degree as the node features. We provide a three-layer GraphCroc to demonstrate the detailed data flow and the model structure, in Figure 9 . Besides, we list the detailed configuration of GraphCroc model and corresponding training setup for all graph tasks in Table 6 . The reconstruction results in Table 1 are not provided in average on multiple runs, because the reproduction on several experiments is too heavy loaded. For example, due to the large graph size, the default setting (vector dimension of 128 and layer number of 4) in EGNN when reproducing the PPI task will cause the out-of-memory issue on the 40GB A100 GPU. While reducing the dimension to 16 and the layer number to 3 allows model and data to fit just into GPU (38.40GB/40GB), this significantly simplified model fails to adequately learn the structure of the PPI graphs and performs poorly compared to other GAE methods. In addition, given that graph reconstruction must be conducted by graph and QM9 task has massive graphs, even one model training on QM9 will take over 2 GPU days.the dual-branch decoder, and the skip connections between the encoder and decoder. Furthermore, we explore how GraphCroc performs without skipping connections. The overall architecture and training configurations remain consistent with those outlined in Table 6 Overall, all architectures employing crosscorrelation effectively reconstruct graph structures, underscoring the significance of cross-correlation as a core contribution of our work. Given that training each model requires several hours, particularly for large datasets such as PPI and QM9, we do not fine-tune the hyperparameters much during model training. The results presented here may represent a lower bound of these architectures' potential performance. Therefore, we refrain from ranking these cross-correlation-based architectures due to their closely matched performance, and we adopt a conservative stance in our comparisons. Nevertheless, it is evident that most of these architectures (except GAT) generally surpass the performance of self-correlation models shown in Table 1 of our paper, highlighting the efficacy of cross-correlation in graph structural reconstruction.In Figure 10 , we demonstrate the converging trajectory of first tow nodes of eight other graphs during training, as an extension of Figure 2 . It aligns with the analysis in main paper that cross-correlation can provide a much smoother than self-correlation during the GAE training. In Figure 11 , we provide the WL-test results on graph tasks, PROTEINS, COLLAB, PPI, and QM9. Our GraphCroc can still outperform other GAE models in completely reconstructing the graphs in most tasks. Notably, all the methods cannot achieve the isomorphism on PPI reconstruction. This is because PPI only has two test graphs, while they have number of nodes 3324 and 2300, which are too large to be completely reconstructed. G A E V G A E E G N N o u r s ( S C ) D i G A E o uIn Figure 12 , we demonstrate more evaluations for GraphCroc on GAE strategies. The AUC score is further tested on IMDB-B, COLLAB, and PPI tasks. We find that the GAE training integrated with other enhancements, i.e., variational, edge masking, and L2-norm, performs distinctively on different graph tasks. They could underperform our baseline training strategy on certain tasks. We visualize more graph structure reconstruction results on graph tasks, in Figure 13 , 14, 15, and16.Figure 13 : The structure reconstruction visualization on PROTEINS task. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. 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. 


Decision: The reviewers unanimously recommend acceptance of the paper with varying degrees of strength. I agree with their assessment and am happy to accept this paper for publication at the NeurIPS conference. 

The reviews and the rebuttal have given rise to some interesting points and results that I encourage the authors to include in the camera-ready version. In particular, the experiments on directed graphs and different encoder architectures further the empirical evidence in favour of the proposed approach.

Reviews: review: paper_summary: paper_summary: This paper theoretically analyzes the limitations of existing graph autoencoders (GAE) in representing special graph features such as islands, symmetrical structures, and directional edges. To address this, the paper proposes a new GAE method, GraphCroc, which employs a cross-correlation mechanism that significantly enhances the representational capabilities of GAEs.
strength_weakness: strength_weakness: 1. In Table 1, the improvements of GraphCroc are evident only on two datasets.

2. While the proposed cross-correlation method performs better than the general self-correlation method on island, symmetric structures, and directed graphs, it would be beneficial to include more results in reconstruction visualization, particularly regarding island or directed edge reconstruction.

3. Some related works [1] need to be discussed.

[1] Liu, Chuang, et al. "Where to Mask: Structure-Guided Masking for Graph Masked Autoencoders." arXiv preprint arXiv:2404.15806 (2024).
questions: questions: 1. How about the performance of the proposed method on directed graphs?
limitations: limitations: NA
paper_summary: paper_summary: This paper proposed a method to address the limitations of existing graph autoencoder (GAE) models that primarily rely on self-correlation for graph structure representation. They claim existing GAE often fail to accurately represent complex structures like islands, symmetrical structures, and directional edges, particularly in smaller or multiple graph contexts. The proposed model, GraphCroc, introduces a cross-correlation mechanism that aims at enhancing the representational capabilities of GAEs. It employs a mirrored encoding-decoding process to ensure robust structural reconstruction and introduces a loss-balancing strategy to tackle representation bias during optimization.
strength_weakness: strength_weakness: 1. This paper lacks discussion on related works. There already exists some works trying to solve the graph autoencoder structure recovering issues. For example, including position encoding [1] or adding extra node labels [2]. How the proposed method is compared with these methods, from the perspective of effectiveness and efficiency?

[1] You, Jiaxuan, Rex Ying, and Jure Leskovec. "Position-aware graph neural networks." International conference on machine learning. PMLR, 2019.

[2] M. Zhang, P. Li, Y. Xia, K. Wang, and L. Jin, Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning, Advances in Neural Information Processing Systems (NeurIPS-21), 2021.

2. As the proposed method generate two latent embeddings, I wonder if there exists some techniques to control them to be different with each other? Otherwise I am concerned that whether the two embeddings could converge to each others.
questions: questions: see above weakness
limitations: limitations: N/A
paper_summary: paper_summary: This paper proposes a cross-correlation autoencoder for graph structural reconstruction. The authors first analyze the problems of existing self-correlation encoder. Then, a cross-correlation autoencoder is designed. Experimental results show the effectiveness of the cross-correlation autoencoder.
strength_weakness: strength_weakness: 1. The authors mention that the current self-correlation methods can not address specific (sub)graph structures. But this paper only presents an overall experimental performance. It is unclear how the proposed cross-correlation autoencoder performs given a specific graph structure. 

2. It is not clear whether the graph dataset used in the paper is a directed or undirected graph. Since the cross-correlation autoencoder can represent the directed graph effectively, it is suggested to consider the directed graph dataset.

3. More different architectures of the encoder and decoder should be employed to further verify the effectiveness of the cross-correlation mechanism.
questions: questions: see Weakness.
limitations: limitations: NA

Comments: title: Thanks for your recognition!
Thank you for your response
comment: Thank you for recognizing our work! We will include the discussion of related work and the divergence of latent embeddings in our camera-ready/revisions.
Thank the authors for their explanations, which have mostly addressed my concerns on the related works and divergence of two generated latent embeddings. I encourage the authors to include the discussion of related works into their camera ready/future revisions. Here I keep my positive scores.
Dear reviewer QrYC,

As the rebuttal discussion is about to close, we would like to confirm whether our rebuttal has adequately addressed your concerns. If there are any questions you would like to discuss, please let us know.
Dear reviewer Xxf1,

As the rebuttal discussion is about to close, we would like to confirm whether our rebuttal has adequately addressed your concerns. If there are any questions you would like to discuss, please let us know.
Dear reviewer Msno,

As the rebuttal discussion is about to close, we would like to confirm whether our rebuttal has adequately addressed your concerns. If there are any questions you would like to discuss, please let us know.
Dear reviewers,

Again we appreciate your time and effort in reviewing our paper. We hope that we have adequately addressed your concerns and would value your confirmation in this regard. We also look forward to your feedback on our rebuttal and are open to any further discussion you may have.

Best regards,

Authors