GraphCroc: Cross-Correlation Autoencoder for Graph Structural Reconstruction
Authors: Shijin Duan
Ruyi Ding
Jiaxing He
Aidong Adam Ding
Yunsi Fei
Xiaolin Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Network
Graph Representation
Auto-Encoder
Primary area: graph_neural_networks

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.

GraphCroc: Cross-Correlation Autoencoder for Graph Structural Reconstruction
Shijin Duan" Ruyi Ding" Jiaxing He Aidong Adam Ding Yunsi Fei Xiaolin Xu Northeastern University
sduan. s, ding.rup he. jiaxi, a. ding, y y.fei, x.xi/@northeastemm.co
Abstract
Graph- Graph-structured data 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 celf-correlation represent graph structures and focus node-level tasks, often overlooking multi- 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 multiple graph contexts. To address these limitations, introduce cross-correlation mechanism that significantly enhances the GAE representational capabilities. Additionally, we propose the GraphCroc, new GAE that supports flexible encoder architectures tailored for various downstream tasks and ensures robust structural reconstruction, through mirrored encoding-dccoding process. This model also tackles the challenge of representation bias during optimization by implementing loss-balee boss-balancing strategy. Both theoretical analysis and numerical evaluations demonstrate that our methodology significantly outperforms existing celf-correlation-baree based GAEs in graph structure reconstruction. Our code is available in https: thub. com/ duan/ Caaaaa//rrppCooero
1 Introduction
Graph-structured data captures the relationships between data points, effectively mirroring the inter- connectivity observed 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
[
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 node features.
Graph autoencoders (GAFs) have been developed to encode graph structures into node embed- dings and decode these embeddings back into structural information, such as the adjacency matrix. This structural reconstruction process can be performed either sequentially along nodes [1] 22 47 or in 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 [5], 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 E Raxd', thus the self-correlation is expressed as 2! 2j between two nodes. Correspondingly. the "cross-correlation" depicts the node pair
"equal contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

correlation as p 9j. which are from two separate embedding spaces, P. E Rnxd', However, studies are seldom evaluated under graph tasks, which represent graph structure on multiple graphs. The distinctiveness of each graph presents 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 [2]. Conversely, we establish that de- coding based on cross-come pross-correlation can significantly mitigate these limitations, offering improvements in both undirected and directed graphs. Furthermore, the optimization of cefff-orrelationbbeeee based GAE has to proceed in restricted space. On the other hand, the cross- cros-ccoreeatton 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 GraphCroe, which leverages cross-correlation 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, GraphCroe retains the freedom of encoder design, facili- tating 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- wwwn-samplin 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, high- lighting its limitations. Furthermore, we elaborate how cross-correlation addresses these deficiencies, facilitating a smoother optimization process.
We propose GraphCroc, a cross-corrclation-bee based GAE that integrates seamlessly with GNN architectures for graph tasks as its encoder, and structures 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.
2 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 general GNN model. A graph G (V. E) comprises n nodes, each with a feature represented by d-dimensional vector, resulting in feature matrix X Raad The set of edges E is depicted by an adjacency matrix A E {0, 1} __x", which indicates the connections between nodes in G. A GNN model fXX, A) is utilized to summarize graph information for downstream tasks.
The feed-forward propagation of the I-th layer in GNN f(-) is
h = (0 (D. A,D, [DD,'',,," hw
(I)
h E Rx is the input feature of the (-th layer, where h1 X and di is the feature dimension of each node specified by each layer. A, = A, + I is the adjacency matrix (self-loop added) of the input graph structure in each layer. Note that A, will be consistent in the absented pooling layer scenario, such as the node classification task, yet 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

---

Dj of A to normalize the aggregation. For layer components, Wi is the weight matrix and a is the activation function the (-th layer.
Graph Autoencoder The naive GAE is proposed to reconstruct the adjacency matrix of a graph G through node embedding Z:
encoder: Z 2 2ZZ])) f(x,A), decoder: = (AAZ)) sigmoid(ZZ")
GAE first encodes the graph G through general GNN model f()) (a.k.a. inference model), resulting in node embeddings in the latent space Z E Rxndd' 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? 2j), normalized as the link probability by the logistic sigmoid function. Usually, the predicted connection can be defined as an indicator function ( I[AA,, 2 th). c.g., th 0.5.
With the same functionality, GAE has been improved with other enhancements, such as variational embedding [9], MLP-based decoder [33], masking on features [1] and edges (23) Note that other correlation measurements in the decoder are also proposed, such as Euclidean distance between node
embedding (26). i.e., Å. = sigmoid C(1 - || 2ÿ =r1īي) 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
2.2 Deficiencies of Self-Correlation on Graph Structure Representation
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, We identify and discuss specific (sub)graph structures that
self-correlation is applied following Eq 2
are poorly addressed by current self-correlation methods:
Islands (Non Self-Loop). Both the inner product and the 1.2-norm of a node embedding pair fail to accurately represent nodes without self-loops, where Ar,; 0. Given that x 2; 0 and C|1-||2 - 2112) = C > O, the predicted value I I(A,,s) defaults to when threshold 0.5 is applicd 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 's structure. However, there is huge difference between the self-connection between nodes in some scenarios; for example, on heterophilous graphs [51], nodes are prone to connect with other nodes that are dissimilar such fraudster detection.
one node and the inter-connection
Topologically Symmetric Structures. If graph structure is symmet- ric along an axis or central pivot, as demonstrated in Figure [ the self-correlation method cannot represent these structures as well.
X2
XTL
Definition 2.1 (Topologically Symmetric Graph). A symmetric graph G = E) has the structure and node features topologically symmetric either along specific axis around a central node. For an axisymmetric graph, the feature matrix denoted as X (XI,.... Xx,, U (Xi...., Xina] U {Xri...., Xrng J. such that n1 + 2m2 = n. X, represents the node features on the axis, and for each paired node off the axis, X = Xri. The connections are also symmetric, satisfying Au.: Ari.. In a centrosymmetric graph, the pivot node has feature X1, and other nodes share the same feature X² the adjacency relationships for these nodes are identical, with A,,: = A3, for all i, E [2,
Two examples of the topological symmetric graphs. The left graph is axis- symmetric; the right graph is centrosymmetric.
Figure 1:
Xn-1- Additionally,
Lemma 2.2. Given an arbitrary topologically symmetric graph G = (V, E) and an encoder f(X,A). the corf-correlation decoder output will always have I( (A =
Proof. Due the symmetry on graph G - (V, E) from the definition above, we have s(X,,
f(X,, Aj.)) for nodes and j that are symmetric about the axis or pivot. Thus, we can derive z = Zj.
For the prediction on link between i and j. we have A. sigmoid = 2;)) sigmoid( - 2,) 2 0.5. Similarly, for the 1.2-norm method, we have A., sigmoid(C(1 || 2)13) sigmoid C(1
|| =)1)) = sig > 0.5. In both decoding methods, the decoder is prone to predict the edge between two symmetric positive, I(Aig) =
3

---

Consequently, the corflccorelation method will indicate 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 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, A, which is not suitable for directed graphs that require an asymmetric adjacency matrix. This issue is also acknowledged in (20). which proposes 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 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
2.3 Our Cross-Correlation Approach for Better Structural Representation
Instead of self-correlation, we advocate cross-correlation reconstruct the graph structure, denoted by Á (emmoid(PQ") where P. Q R=xd", This approach allows to decouple the variables involved calculating the correlation, thus overcoming the inherent limitations of corf-coore
2.3.1 How Does Cross-Correlation Mitigate Deficiencies of Ceff-Correlatio?
Expressing Islands. For each node E nI.. the sign of p qi can be flexibly determined by p; and qi, allowing it to be either positive negative. Consequently, the presence of an island can be effectively modeled using Atj sigmoid(p} q:) or sigmoid avoids the limitations associated with self-correlation, which restricts the sigmoid input to positive.
||p. - 9u 2)) This approach
Expressing Symmetric Structure. Cross-correlation is particularly effective in capturing topological symmetric structures. Given a node pair (i.j) that topologically symmetric about an axis or pivot, for undirected graphs, we have p; Pj and q: qj- However, since p; and gj (as well Pj and q)) are not directly dependent each other, the sign of Ft 9j- p q: can be either positive or negative. Therefore, I(AA,)) = I(simmoid(p; q;)) is able to yield or 1, depending on the specific values of node embedding p; and Qy- This flexibility can be supported by the L2-norm decoding well.
Expressing Directed Graph. A similar interpretation extends to the representation of directed graphs. For two nodes and j, the directed edges can be defined by r Oj for one direction and p q: for the other. Since these four latent vectors do not have explicit dependencies among them, the directions of the edges can 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.
2.3.2 Pross-Correlation Provides Smoother Optimization Trace
We highlight the superiority of cross-correlation over seff-correlation in the optimization process of GAE training. Considering the decoder optimization problem, where we aim to satisfy the constraints:
(self-correlation) Z(sigmoid( =!" 25)) = A..j. (cross-correlation) I(sigmoid(p) (5)) A (3)
for each element in matrix A. This involves finding e Ruxd' or P,Q E x that maximize the number of satisfied constraints. Additionally, for undirected graph, the symmetry Ar, A3. imposes the requirement that I (ssigmoid 4;)) I(sigmoid(p) q:)), ensuring that both p qj and p. 9j should have the same sign.
In the case of cross-correlation, where P and Q are independently determined, and all constraints well align with the generation of P and Q. However, this is not the in self-correlation, where 2! 2j 2 inherently overloads the symmetry constraint. For example, if A. = Aj = 1, only require po 9; 0 and p. 9: 0 for cross-correlaton,, while they become restrictive as

---

Node (nn) Node 2 126)
Nade 1 Node (sx)
sel-ccrelatton
wilkorrelaiion
2.5
cressccrrelation Awilt
10
cous-tordaation
BCE Less
0.8-
Dim.
Dim.
0-
4.
60
20
200
Dim.
Reration
(4) Vrajectory under sef-cor. decoding [b) Trajectiry under cross-cor. decoding
[41 Loss evar lerratoos
(4) Diagonal value dia. ever lieraiion
Figure 2: Training comparison between self-correlation and cross-correlation on PROTEINS subset (64 graphs). In (a) and (b), we demonstrate the trajectory of the first two node embeddings in the first graph during training iteration, where the star mark is the end-point of training. We apply PCA for dimension compression and the Savitzky-Golay filter to help trace visualization. We also set 2 ===1 P: A q at the beginning of optimization to ensure that the traces of z; in (a) and p: 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.c., 2 2 for self-correlation and P. q: for cors-correlltton. The results of other graphs are provided in Appendix G.2
of 2 -- =2 0 in self-correlation. Cross-correlation offers broader argument space, providing more freedom to find solutions that satisfy the constraints for reconstructing A. By employing gradient method during optimization, this process be understood as the trajectory of P and Q being unrestricted in the argument space R2nxdd" while the trajectory of Z is confined within restricted space as "R=xd'_ 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, can first find (local) optimal P and Q, then apply (PQ" + QPT) 2 interpret it symmetrie matrix A, like Zz"; this procedure can still outperform direct optimization on ZZT.
Validation on PROTEINS Here, we make a quick validation our discussion on subset of PROTEINS (2) that is 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 not smooth and may follow 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 c). Another concern of cross-correlation is that pi qi cannot naturally satisfy A,, = while of 2; in self-correlation is able to. Nevertheless, pf y can be encouraged to perform with positive sign, proved by Figure 2 d). that all the diagonal element reconstruction pi q: under cross-correlation can achieve positive sign the end of training, leading to I(sigmoid(p) (:))) = A 1.
3 GraphCroc: Cross-Correeation-Baane 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 as the downstream tasks require. For graph tasks, the GNN model has sequence of message passing layer and pooling layer to coarsen the graph to higher-level representation. the end, a readout layer [8] 9 31] is applied to summarize the graph representation the latent space. We define the encoder as
encoder (ours): Z' = (Z'GG) f(X,A)
where Z'
'R xdd 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.
Two- Way Decoder for Cooss-Correlatin To separately produce two node embeddings, P and Q, divide the decoding process into two parallel and self-governed decoders. Unlike [20]. we leave
5

---

(X.A)
A)
(fzz A'2)
(he A'
Downstream tasks
GCN
GCN
GCN
GCN Pooling
h
Pooling
Norm(AA
Encoder Decoder
GCN
GONIX.A)
Linear
Unpooling
| GCN
O
Unpooling
GCN
signoid(PQ")
LayerNorm
Unpooting GON
Linear
Unpooling GCN
Og
(KL.AA))
Figure 3: GraphCroc architecture. The encoder is generally demonstrated as a L 1-layer GNN. The decoder has two paths to generate the node embedding for cross-correlation; each decoder is 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 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:
decoder (ours): À (igmoid(PQ")) P- (2,
Q - 92( (A',
(5)
(+)+) and (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 Section 3p. Here, (A', h') 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 each other, thereby preventing convergence ceff-correlation decoding.
Autoencoder Architecture In Figure 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 case study demonstrate the effectiveness of cross-correlation.
The GraphCroc architecture follows the encoder formulations from Eq, 4 for multiple graphs and the decoder from Eq 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, 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, of implementing layer normalization [1] following each GNN layer. Although often overlooked in previous GAE studies due the typically small number of layers, layer normalization is crucial for regulating gradient propagation as the number of layers increases.
emphasize the significance
Loss Balancing 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 A, we denote the vanilla loss function as - C. + L), where in total 6n zeros and ei ones A, and / is their corresponding loss on each element. Since co > C1, the zero part dominates the loss function, inducing the decoder to predict zeros. Thus, we apply scaling factor for each item:
((A, A) -
a1
j
ag
=
Co +
01
Cu + C1
(6)
2co
2c1
1=1
The derivation is provided in Appendix
E

---

Table I: The AUC score of reconstructing the adjacency matrix in graph tasks. We reproduce the most representative global GAE methods with different decoding strategies. The self-correlation methods include naive GAE, variational GAE [19]. L2-norm (EGNN) (30, and our GraphCroc under self-correlation; the cross- correlation methods include directed representation (DiGAE) [20]
0.6-
WL-test
and our GraphCroc. The best results are bold, and the second bests are underlined.
0.2
Self-Correlaton EGNN
Conss-oorclltion GraphCrm
GAF
VGAE
EGNN
oursiSC)
DIGAE
ours
GAF
VGAF
GraphCree(CC)
DiGAF
PROTEINS
0.4750
0.4764
0,9608
0,9781
0.7577
0.9958
IMDB-B
0.7556
0.7105
0.9873
0,9892
0.7500
0.9992
Figure 4: WL-test results on differ-
Collah
0,7885
0.7946
0,9947
0,9926
0.7973
0.9989
PPI
0.6330
0.6239
0.9764
0.8364
0,9831
ent GAE methods, in the IMDB-B
QM9
0.5376
0,4852
0.9984
0.9967
0.7791
0,9987
task.
Out memory during training, see Appendix
4 Evaluation
4.1
Experimental Setup
We assess GraphCroc in various graph tasks. Specifically, we utilize datasets for molecule. scaling from small (PROTEINS (2) to large (Protein-Protees Interactions (PPI) [12), and QM9 29 for scientific collaboration (COLLAB 46]). and for movie collaboration LIMDB-Binary (46
Dataset
Further details on these datasets are provided in Appendix F.
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. II (0.9 i) 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
4.2 GraphCroc on Structural Reconstruction
Table I 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 [9) 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 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-correlatin 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 capability to capture enough structural information. By integrating the strengths of cross- cooss-ooreelation 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 PPI with over 2,000 nodes, GraphCroc still achieve 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. The reconstruction results for these architectures are consistent with those in Table [ though they exhibit slightly lower AUC compared to GraphCroc.
While the AUC score indicates how well model reconstructs edges, does not measure the model's ability to exactly reconstruct whole graph. To address this, we employ the Weisfeiler- Leman isomorphism test (WL.ttest)[41) which assesses the structural equivalence between the original and reconstructed graphs. Figure presents normalized WL-test results, i.c., the pass rates across all test
7

---

Ground Truth
GraphCroc
GAE
VGAE
EGNN
DIGAE
PROTEINS
COLLAB MADER
Figure 5: The reconstruction visualization. Other reconstructions are provided in Appendix G.S
graphs, in the IMDB-B task. Our GraphCroe 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 well reconstruct the entire graphs; this indicates there 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 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-produs and vanilla GNN architectures, such as GAE, VGAE, and DiGAE, tend to overpredict edge connections. Mean- while, EGNN performs adequately within node clusters, but struggles with inter-cluster connections. This echos our discussion about the partial representation deficiency in L2-norm.
4.3 GraphCroc on Other GAE Strategies
To make cross-correlation more pronounced our evaluation, the above experiments implement only the basic inner-product representation. i.c. sigmoid PQ""). In addition, previous stud- ies have extensively explored data augmentation and training enhancements to optimize GAE models. Specifically, we exam- ine the performance of GAE with cross- cross-correlation applied to different training strategies in Figure using the PROTEINS dataset case study.
1.00
0.95
RDC-AlIC
0.90
baselina
0.85
varlational
masking
L2-norm
We evaluate three other prevalent decoding enhancements 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 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 highly dependent on graph tasks. Our further analysis on other graph tasks (Appendix G.4) demonstrates that the 1.2-norm and masking could converge worse structural reconstructions than our baseline training. Therefore, still advocate our training and representing methods for GAE models various graph tasks.
50
100
150
200
Epoch
Figure 6: The AUC score of test- ing graphs in PROTEINS task, with different decoding methods.

---

Table 2: Evaluation on graph classification tasks. We compare our model with other GNN meth-
ods, such as unsupervised learning (Infograph (34). contrastive learning (GraphCL 48 and In-
foGCL [.), 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-initialzzed
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.
Infograph
GraphCL
InfoGCL
GraphMAB
S2GAE
StrucIMAE
ours (10-epoch)
ours (100-epoch)
PROTEINS
74.44
74.39
75.30
76.37
75.97
73,9911.02
79.09
IMDB-B
73.03
71.14
75.10
75.52
75.76
75.52
76.69 76.6941.02 41.02
78.75 1.35
COLLAB
70.65
71.36
80.00
80.32
81.02
80.53
81.70
+2.20
4.4 GraphCroc on Graph Classification Tasks
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 multi- graph 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 mmall-to-moodrrate-ssizee 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 I 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 D-E--ased models.
4.5
GAE Attack Surface Analysis
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 us- ing random noise injection, PGD (27), and C&W adversarial noise injection (7) on graph classification tasks. We limit all at- tacks the latent space with a maximum query number of 400 and report the classi- fication 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 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 's latent space reveals potential vulnerability, indicating that adversarial attacks on graph autoencoder's latent space can provide efficient structural adversarial attacks. More detail on the adversarial attack with GAE is discussed in Appendix F3
Table 3: Accuracy and modified edges for adversarial attack, leveraging latent perturbation on GAE. A lower accuracy indicates that the latent perturbation can better pass to the reconstructed graph. A higher percentage of modified edges indicates larger attack cost.
Clean
Random
PGD 27 Zedge
C&W
Acc.
Zodge
Acc.
Acc.
Aedge
IMDB-M PROTEINS
55.3
53.5
4.79%
45.7
24.5%
39.7
17.4%
82.5
77.1
5.01%
57.4
5.63%
41.7
23.7%
COLLAB
81.3
70.0
5.90%
28.8
35.9%
27.3
8.29%

---

Conclusion
Graph autoencoders (GAEs) are increasingly effective in representing graph structures. In our research, we identify sigmificant 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 constrained space. To address these deficiencies, we advocate cross- correlation as the decoding kernel. We propose a novel GAE model, GraphCroc, which incorporates cross-correlation decoding and is built upon 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 surface for adversarial attacks.
Acknowledgments and Disclosure of Funding
We thank Shaolei Ren from UC Riverside for the valuable discussions that helped shape this work. This work is supported part by the U.S. National Science Foundation under Grants OAC-2319962, CNS-2239672, CNS-2153690, CNS-2326597, CNS-2247892, and SaTC-1929300.
References
[1] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450 2016.
[2] Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex J Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 2[6supp[_)::47-1556 2005.
[3] Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. Graph structure in the web. Computer networks, 33(1-6):309-320, 2000.
[4] Nicholas Carlini and David Wagner. Adversarial examples not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 3-14, 2017.
[5] Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. arXiv preprint arXiv:2305.0411,, 2023.
[6] Antonia Creswell, Anil A Bharath, and Biswa Sengupta. Latentpoison-aaderraaii attacks on the latent space. arXiv preprint arXiv: 1it.:7711022799 2017.
[7] Hanjun Dai. Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song, Adversarial attack on graph structured data. In International conference on machine learning, pages 1115-1124. PMLR, 2018
[8] Michaël Defferraad, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[9] Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference machine learning, pages 2083-2092. PMLR, 2019.
[10] Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference Digital libraries, pages 89-98, 1998.
(11) Rafael Gómez-Bombarelli, Jennifer N Wei, David Duvenaud, José Miguel Hernández-L.ode Benjamín Sänchez-Lengelingg Dennis Sheberla, Jorge eguilera-Iparragiinn Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven contimuous representation of molecules. ACS central science, 4(2):268-2) 2766682-6,776 2018.
[12) Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
10

---

[13] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[14] Xu Han, Xiaohui Chen, Francisco JR Ruiz, and Li-Ping Liu. Fitting autoregressive graph generative models through maximum likelihood estimation. Journal of Machine Learning Research, 24(97):1-300 2023.
[15] Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang. Chunjie Wang. and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages
2022.
[16] Surgan Jandial, Puneet Mangla, Sakshi Varshney, and Vineeth Balasubramanian. Advgan++: Harnessing latent layers for adversary generation. Proceedings of the IEEF/CVF International Conference Computer Vision Workshops, pages 0-0, 2019.
[17] Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aides aided molecular design. 30:595-608. 2016.
[18] John A Keith, Valentin Vassilev-Galindo, Bingqing Cheng, Stefan Chmicla, Michael Gastegger, KlburtRobert Muller, and Alexandre Tkatchenko. Combining machine learning and computa- tional chemistry for predictive insights into chemical systems. Chemical reviews, 121(16)98816 9872, 2021.
[19] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 1611v::611.00300.. 2016.
[20] Georgios Kollias, Vasileios Kalantzis, Tsuyoshi Idé, Aurélie Lozano, and Naoki Abe. Directed graph auto-encoders. In Proceedings the AAAI conference on artificial intelligence, volume 36, pages 2211-7219,202
[21] Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation. In International conference on machine learning, pages 17391-17408. PMLR, 2023.
[22] Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoencoder. In International conference on machine learning, pages 1945-1954. PMLR, 2017.
[23] Jintang Li, Ruofan WU, Wangbin Sun, Liang Chen, Sheng Tian, Liang Zhu, Changhua Meng, Zibin Zheng, and Weiqiang Wang. What's behind the mask: Understanding masked graph modeling for graph autoencoders. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1268-1279 2023.
[24] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. Advances in neural information processing systems, 32, 2019.
[25] Chuang Liu, Yuyao Wang, Yibing Zhan, Xueqi Ma, Dapeng Tao, Jia Wu, and Wenbin Hu. Where to mask: Structure-guidee masking for graph masked autoencoders. arXiv preprint 24K4::2604.1880 2024.
[26] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. Advances in Neural Information Processing Systems, 32, 2019.
[27] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 700.00683, 2017.
[28] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163,
2000.
[29] Lars Ruddigkeit, Ruud Van Deursen, Lorenz C Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database gdb- 17. Journal of chemical information and modeling, 52(1 12 01224-287277 2012.

---

[30] Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling, E (n) equivariant graph neural networks. International conference on machine learning, pages 9323-992999 -3332. PMLR, 2021.
[31 Simon Schaefer, Daniel Gehrig, and Davide Scaramuzza. Aegnn: Asynchronous event-based graph neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 12371-12381, 2022.
[32] Nitish Shukla and Sudipta Banerjee. Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 730-739, 2023.
Generating adversarial attacks in the latent space. In
[33] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning-CCANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part 27, pages 412-422. Springer, 2018.
[34] Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. arXiv preprint arXiv: 1908. 01000, 2019.
[35] Qiaoyu Tan, Ninghao Liu, Xiao Huang. Soo-Hyun Choi, Li, Rui Chen, and Xia Hu. S2gae: self-supervised graph autoencoders are generalizable learners with graph masking. In Pro- ceedings of the sixteenth ACM international conference on web search and data mining, pages 787-795, 2023.
[36] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, (050(20):00-48555) 2017.
[37] Xingchen Wan, Henry Kenlay, Robin Ru, Amo Blaas, Michael A Osborne, and Xiaowen Dong. Adversarial attacks graph classifiers via bayesian optimisation. Advances in Neural Information Processing Systems, 34:6983-69999 2021.
[38] Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginalized graph autoencoder for graph clustering. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 889-898, 2017.
[39] Shoujin Wang, Liang Hu, Yan Wang. Xiangnan He, Quan Z Sheng, Mehmet A Orgun, Longbing Cao, Francesco Ricci, and Philip S Yu. Graph learning based recommender systems: A review. arXiv preprint 2 2021.
[40] Shuo Wang, Shangyu Chen, Tianle Chen, Surya Nepal, Carsten Rudolph, and Marthie Grobler. Generating semantic adversarial examples via feature manipulation in latent space. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[41] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
[42] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1) (211:44200 24, 2020.
[43] Chaowei Xiao, Bo Li, Jun- Yan Zhu, Warren He, Mingyan Liu, and Dawn Song, Generating adversarial examples with adversarial networks. arXiv preprini 1rXiv:1801.02611 2018.
[44] Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information-awwree graph contrastive learning. Advances in Neural Information Processing Systems, 34:30414-30425 2021.
[45] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: #xXiv/8100000266 2018
[46] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
12

---

[47] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrmn: Generat- ing realistic graphs with deep auto-regressive models. In International conference on machine learning, pages 3708-5711 PMIR, 2018.
[48] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33:5812-558 5823, 2020.
[49] Chengxi Zang and Fei Wang. Moflow: invertible flow model for generating molecular graphs. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 617-626, 2020.
[50] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
[51] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference artificial intelligence, volume 35, pages 11168-11176, 2021.
13

---

A Related Work
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² queries required for the adjacency matrix. Similarly, diffusion-based graph models [1] construct graph structures through multiple steps, such as degree matrix reconstruction []. 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 [2] globally [33 19 15 30 20). The
very beginning graph structure representation is proposed in [19] with self-correlation (applied with
Eq. 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 parse tree from 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 B3 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. GraphMAR [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 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.
B Dimension Requirement to Well Represent Graph Structure
As the node embedding dimension d' is underexplored before, it is mostly regarded as hyperpa- rameter 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 toy example to demonstrate how the d' design has an impact on the encoder ability. Assume an extreme case d' 1, each node represented by scalar. The node embeddings (2i, zj, 2x) 3 can never represent connection set (Ai,g Ai,,, Aj,s) = (0, 0, 0). Because if (0, 0), i.c., 242 < 0 and 2424 0, then must have 1. This will always yield to I(Ar,)) can be directly observed when d' 2 and there are four nodes, then M(2 2j, zk, 21) E R2 which can represent connection set (Ai,j, Ar,., A Aj.,, Aja, Ac.)) = (0, 0, 0, 0,0.
3(2,, 2g. 2x. E a such that j(A...
sign( (z)zk) sign( 2, 2f 2
* Aj,a- The similar result
Lemma 1. For self-correlation method in the decoder, to make the connection constraints always solvable on the n-node scenario, i.e., requiring z! 24 > 0 or 2 2j < ffr each node pair, the node embedding dimension d' need to satisfy d' 2 (n-1) 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 ][x) E Raaxd' can represent when d' < (n 11). We consider the case that A d' (n - 2), there will be at most (n - 2) linearly independent node vectors. Assume the first (n- 2) vectors to 2 are linearly independent, then we will always find a lincar combination
and Ar,; = 0 for all i,j E [1, such as =f²2, < 0. When d' < (n 1 1), e.g.,
14

---

such that Σi=1 0;2; 0, where vector a fai. an- # O. Here, we let the elements of a be grouped as positives, negatives, and zeros, as a a.. Thus, we have
0:4 - -0
Σ
0
by2 w
acart
bEar
a) If both at,
xtt a are not empty, we do inner product on these two terms:
0 < u
Σ
Σ byzj
0:4
aaca!
DEO
Σ
a.by
2
2j S
This causes conflict on the inequality. If one of a and a is empty, e.g., a 0, we do inner product between the positive part and Zn:
0 0" Zz
Σ OEat
az om <
which 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) E R to represent all the connections through the decoder. We use inductive method to prove it. is straightforward that when = 2, d' = 1 can satisfy the representation any graph A E {0, 1]2x2, Assuming d' = feasible configuration for an arbitrary n-node graph, we need to prove that d' = n is also sufficient for (n + -ood graph: We denote satifiable node embedding from the n-node graph as Z = {2;} Ra By extending it to = n for one more node coming, we specify the node embedding of the first n nodes 2 [2,, 0] for i [1, n - 1] and 2/2 [Zn 1]; this specification can still satisfy arbitrary inequality constraints between node pairs the first n node. For the (n + 1)-th node, need to find 2/ E IR" such that 2 2 satisfy arbitrary incqualities. Through the inductive method, it is also straightforward to prove that there exists with rank (n - 1), thus our extension
always find a non-zero vector such that 2 Ei= 242z For each constraint = being positive or negative (in total n constraints), we can reduce them to system of equations where the constants are scalars satisfying the constraints:
extra dimension will make rank([=())
for = 1,,n. Therefore,
a1 21
ta, IT =
equations
2121 2T 2n+ +a, 2n = Cn
denoted as Ma C. Here, the vector is solvable as long 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 experiments that the embedding dimension can usually be smaller (c.g.. d' z n/2) because the hard-to-son 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' zs in all experiments.
C Specific Graph Structure Representation
In Sec. 2.2 and 2.3 we explore the limitations of self-correlation and the effectiveness of cross- correlation in expressing specific graph structures. Given that previous GAE research often evaluates undirected asymmetric graph structures, the evaluation on special graph structures is usually over- looked. Hereby we evaluate how method GraphCroc and other GAE models perform 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 presented
15

---

Ground Truth GraphCroc
GraphCroc(SC)
VGAE
EGNN
DIGAE
Figure The graph reconstruction visualization of different models on graphs with symmetric structure and lon-seef-loope nodes.
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-biie based models tend to incorrectly predict connections between symmetric nodes and islands, and incorrectly introduce self-loops on nodes. Note that for EGNN, does predict positive edges between nodes, which seems not follow analysis in Sec. 2.2 with Euclidean encoding DggmoidC((1
2| 2)]l²)). This is because EGNN slightly improves this encoding to sigmoid (w/ 2 2y + b). where or and are learnable. Since no-self-loop nodes require sigmoid( w|| z; 2 + b) = sigmoid(b) < 0.5, is forced to be negative, inducing negative prediction on symmetric edges that have 2; 2j 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, only cross-coreelation-aseeee methods are capable expressing direc- tional relationships between nodes. To construct the dataset, we sample subgraphs from the directed
Cora ML (28) and CiteSeer [1O] 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 where N represents the average number of nodes per graph:
Table 4: The AUC score of reconstructing the adjacency matrix in directed graph tasks.
Cora_ML(N = 41) Cora_ = 77) CiteSeer(NV Ñ 16)
DiGAE
0.6879
0.8296
0.9083
GraphCroc
0.9946
0.9996
0.9999
Our GraphCroc model can well reconstruct the directed graph structure with almost perfect prediction, which significantly outperforms the DiGAE model. This advantage comes from the expressive model architecture of our proposed U-Net-like model.
D Node Embedding Divergence in GraphCroc Decoder
The difference between two latent embeddings (denoted as P and Q) is fundamental cross- correlation as opposed to self-correlation in which P= Q; therefore, is necessary to make them 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) Q)).
Our decoder architecture inherently encourages differentiation between P and Q since they derived from two separate branches of the decoder. This structure can allow P and Q to di- verge adaptively in response to the specific needs of the graph tasks. If graph cannot be well
16

---

represented by self-correlation. our two woo-brncc structure will encourage sufficient divergence on and to suit structural reconstruction. To evaluate the differentiation between them, we compute their cosine similarity and present histogram of these values for each graph task in Figure g Across all tasks, the cosine similarity be- tween the node embeddings under cross-correlation is gen- erally low, typically below 0.6. This shows that our two- branch decoder effectively maintains the independence of the node embeddings, which are adaptively optimized for various graph tasks. Furthermore, this adaptive opti- mization 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
Collab
Hist. of Cosine Similarit
25
IMDB-B
PPI
PROTEINS
QM9
-0.2
0.4 Cosine Similarity
Figure 8: The histogram of cosine similarity between node embeddings P and Q under cross-correlation, applying GraphCroc graph tasks.
E Loss Balancing Derivation
We adopt binary cross-entropy (BCE) loss to evaluate reconstruction between prediction Á = (ig") and ground truth A. Our loss balancing is based an i..d. assumption between Lo and L1, where the loss definition follows [(i,j) BCF(Á,,, Ai.z) the node pair (i. For a certain graph G. we assume there are co zero elements and с₁ one elements in A, where Co > c₁. To balance the loss between zeros and ones, we apply scaling factors on each element loss: L( A) ag E C. + Σド= CJ. The scaling has two targets: keep the loss magnitude and to balance the zero/one influence. Thus, construct the following linear equations:
CncoC + aaccL' = co t. ancoL CiqL
Co + C1
Co +
3 00
an
2co
201
The scaling factors ag and a1 derived.
F
Supplementary Experimental Setup
F.1
Dataset
We provide the graph detail graph tasks selected in our evaluation, in Table For IMDB-B and COLLAB without node features, we take the one-hot encoding of degree the node features.
Table 5: The dataset configuration of selected graph tasks.
graphs
nodes (avg)
edges (avg)
# features
classes/tasks
PROTHINS
1,113
39.1
145.6
3
IMDB-B
1.000
19.8
193.1
0
2
COLLAB
5,000
74.5
4914.4
0
3
PPI
22
2245.3
61.318.4
50
121
QM9
130,831
37.3
11
19
F.2 Other Experimental Setup Information
We provide 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 [ are not provided in average on multiple runs, because the reproduction on several experiments 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 A 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.
17

---

(X.4)
(b..4'))
(g.44g)
GON
GCN
Pooking
GDN
Pooling
(0,1A)
ND0
Linear
Noa
(',),''))
(A4
(A2 (,4')
Figure The archtecture example of our GraphCroc model, with 3-layer encoder/decoder.
Table 6:
The architecture and training configuration of GraphCroc selected graph tasks.
training config.
input dim.
embedding dim.
layers
pooling rate
(opt., Ir, epochs)
PROTEINS
3
128
[. 0.900.8, 0.7, 0.6, O.S,
(AdamW, 1e-3, 200)
IMDB-B
135
[. 0.9.0.8. 0.7. 0.6, 0.5,
(AdamW, 1e-3, 200)
COLLAB
400
128
09,08,8, 0.7, 0.6,
04,
(AdamW, 1e-3, 200)
PPI
50
1024
11
[-. 0.5, 0.5, 0.5, 0.5, 0.5. 0.5, 0.5. 0.5, 0.5.
(AdumW, le-3, 200)
QM9
11
32
[-. 0.9, 0.8, 0.7, 0.6,
(AdamW, 1e-3, 100)
F33 Adversarial Attack on GraphCroc
In Section 4.5 we evaluate the GAE performance as an adversarial attack surface. Specifically, given a pretrained encoder 4 G') which encodes the graph into a latent space and a downstream classifier (() for the graph classification task, we aim to generate a perturbed latent representation Z' and leverage reconstructor θ to rebuild the graph structure G' = (X, A'). The goal of the adversarial structure to cause the encoder and downstream classifier to misclassify the graph, i... (()(G")) * where is the original label, and the only difference between G' and G' is the adjacency matrix A. We assess two gradient-based adversarial attacks on latent space.
Projected Gradient Descent (PGD) 27 PGD iteratively perturbs the input to maximize the classification loss of f(Z):
5,+1 Proj Proi (fe sign(V,,
Carlini & Wagner (C&W) W) C&W finds adversarial latent vectors by solving an optimization problem:
arg min |0]] + (max f()), ma)) -k))
Here, f()), denotes the logits output of the classifier for the true class y. and confidence parameter that controls the confidence of the misclassification. This optimization can be solved with gradient descent. Hence, the final adversarial graph structure will be = (X, O + 8*)). enhance the performance of adversarial perturbation, we fine-tune the reconstructor O during the adversarial attack. Specifically, to ensure the effectiveness optimize @ by minimizing the distance between the perturbed latent representation and the latent space of the reconstructed graph structure:
reconstructed adversarial example,
o arg min -x(
G Supplementary Experiment Results
G.1 Structural Reconstruction of Cross-Correlation on Other Architectures
In addition to the GCN kernel used in our GraphCroc model, we extend our analysis to include other widely used graph architectures such as GraphSAGE [33, GAT (36), and GIN 45 To incorporate these architectures into the cross-correlation framework, we replace the GCN module with corresponding operations while preserving the overarching structure, which includes the encoder,
18

---

the Qual-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 of our paper. The results, presented in Table 7 follow the format of Table T in our paper, providing a clear comparison across different architectures.
Overall, all architectures employing cross- correlation effectively reconstruct graph structures, underscoring the significance of corseloornl 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 lower bound of these archi- tectures' potential performance. Therefore, we refrain from ranking these cross-correlation-bas architectures due to their closely matched performance, and adopt a conservative stance in our comparisons. Nevertheless, it is evident that most these architectures (except GAT) generally surpass the performance of self-corre ceff-correlation models shown in Table of our paper, highlighting the efficacy of cross correlaorol in graph structural reconstruction.
Table 7: The AUC score of reconstructing the adjacency matrix in graph tasks, under different architectures in the cross-correlation framework.
Dataset
GraphSAGE
GAT
GraphCroc'
GraphCroe
PROTHINS
0.9898
0.9629
0.9927
0.9934
0:9958
0.9992
Collab
0.9985
0.9627
0.9954
0.9976
0,9989
PPI
0.9774
0.9236
0.9467
0.9447
0.9831
QM9
0.9972
0.9978
0.9974
0.9966
0.9987
without skip connection
G.2 Node Trajectory during Training
In Figure I0 we demonstrate the converging trajectory of first tow nodes of eight other graphs during training, an extension of Figure It aligns with the analysis in main paper that cross-correlation can provide a much smoother than self-correlation during the GAE training.
2
No & Sty1
Rode pu
:3
Rode ln)
Rods lo!! Rods tcu
1.5
Rode Sui
Rode
Dm2
2.0
-2.2
Gragh Figectrry auficat (NM
Dtr,
Dmn,3
Preeddyy under adtor
2km
3.0
Node 1.5
Rode 1p1)
Rode
hods L.sl
2.0
0mm
-22
Graph #2: Eigectory under sefioo HMO and creas-zr (9210
Crazh dic Piceedayy under adtioon Jutt and creas cot 11g1t1
Nere
Reds Uni
Dm
Brags Faeety under selor (M6) a6i (1650IM no. 01317)
Grack Taedtry usde setion Jefts and cross coe 21911
1.5
3.5
Node2
Rodez
-1.0
Gragh NT: Eigecorr under sefocr (1a0) and craas-zer (1g3))
Grach Tagedtrry under aatiaar
Figure 10: The trajectory of the first two nodes of eight graph samples during training.
19

---

G.3 WL-Test Results
In Figure 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.
PROTEINS
COLLAB
0.20
0.3
WL WL-test
0.15-
WL-test
0.2
0.10
0.00
GAE
VGAE
EGNN
aurs(SC)
DIGAE
ours
GAE
VGAE
EGNN
aurs(SC)
DiGAE
ours
(a)
(b)
PPI
QM9
0.10
0.04
0.08
0.02
WL-test
WL-test
0.06
0.00
0.04
-0.0
0004
0.00
GAE
VGAE
EGNN
ours(SC)
DIGAE
aurs
GAE
VGAE
EGNN
ours(SC]
DIGAE
ours
(c)
(d)
Figure 11: The WL-test results on PROTEINS, COLLAB, PPI, and QM9. "ours" refers to GraphCroc.
G.4 GraphCroc on Other GAE Strategies
In Figure 12 we demonstrate more evaluations for GraphCroc on GAE strategies. The AUC score is further tested IMDB-B, COLLAB, and PPI tasks. We find that the GAE training integrated with other enhancements, i.e., variational, edge masking, and 1.2-norm, performs distinctively on different graph tasks. They could underperform our baseline training strategy on certain tasks.
AUC IMDB-B
AUC COLLAB
1.0
PPI
0.9
0.95
0.95
(OC-AUC
ROC
ROC-AUC AUC
0.8
0.7
baseline
baseline
0.85
vartational
0.85
varlational
vartational
masking
masking
0.5
L2-nomm
L2-norm
L2-1orm
50
100
150
200
50
100
150
200
50
100 Epoch
150
200
Epoch
Fpach
(a)
(b)
Figure 12: The supplementary AUC scores other graph tasks, with different decoding methods.
G.5
Reconstruction Visualization
We visualize more graph structure reconstruction results graph tasks, in Figure B 14
20

---

Ground Truth
GraphCroc
VGAE
EGNN
DIGAE
Figure 13: The structure reconstruction visualization on PROTEINS task.
Ground Truth
GraphCroc
GAE
VGAE
EGNN
DIGAE
Figure 14: The structure reconstruction visualization on IMDB-E B task.
21

---

Ground Truth
GraphCroc
GAE
VGAE
EGNN
DIGAE
Figure 15: The structure reconstruction visualization COLLAB task.
Ground Truth
GraphCroc
GAE
VGAE
EGNN
DIGAE
Figure 16: The structure reconstruction visualization on QM9 task.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly indicate our contribution on cross-correlation decoding and a novel GAE model, in [Abstract] and [Introduction].
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
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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Our approach still requires GAE training by graph, thus time-consuming on large graph number tasks, such as QM9 [in Appendix [:2.. Further, we observe adversarial attack based on GAE model could require noticible edge distortion in some cases [in
Justification:
Evaluation 4.5
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
23

---

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

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide sample code along with submission, and will open source full codes after acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
publitc/guudee//odeSattmn http:///uuuuaeeeoeeeeeaaaasasaaa oow.ssoboioiiioooooooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips //ips.cc/
guides/ PwoddSSumiissiooooo.....oooooooo
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
See answer to Q4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: We provide error bars when possible [in Table and explain when impossible [in Appendix F2
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
25

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We run our model training on an A100 GPU with 40GB [in Appendix F2 and the time of model training is also mentioned.
F2
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate 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 (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Our work does not have ethical or societal concern.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
26

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include 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.
27

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According 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.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
28

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
29


Reviews:
[{"review_id": "ZjrWIOhtku", "reviewer": "Reviewer_Msno", "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.", "questions": "1. How about the performance of the proposed method on directed graphs?", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper clearly shows the limitations of existing GAEs through theoretical analysis.\n\n2. The experimental results demonstrate the advantages of the proposed method in structural reconstruction and graph classification tasks.\n\n3. The paper is easy to follow.", "weaknesses": "1. In Table 1, the improvements of GraphCroc are evident only on two datasets.\n\n2. 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.\n\n3. Some related works [1] need to be discussed.\n\n[1] Liu, Chuang, et al. \"Where to Mask: Structure-Guided Masking for Graph Masked Autoencoders.\" arXiv preprint arXiv:2404.15806 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In Table 1, the improvements of GraphCroc are evident only on two datasets.\n\nAUC is widely used to evaluate graph structural reconstruction tasks in GAE, due to its unbiased performance on positive and negative edges. Thus, we adopt this metric to assess the adjacency matrix reconstruction in our work. GraphCroc exhibits only marginal improvements on Collab and QM9 graph tasks compared to EGNN [1]. This can be attributed to the good representation capabilities of EGNN on certain graph tasks. Specifically, EGNN achieves AUC over 0.99 on these tasks, nearing perfect prediction (AUC=1), thus leaving minimal room for improvement by GraphCroc. However, Table 1 also illustrates the significant advancements of GraphCroc over EGNN on other graph tasks like PROTEINS and IMDB-B. Moreover, EGNN was not successfully applied to the PPI task due to the out-of-memory issue (on a 40GB A100 GPU), whereas GraphCroc operates within a mere 3GB of memory, as we measured. This demonstrates not only the generality of GraphCroc in handling various real-world tasks but also its efficiency in implementation. Additionally, the core of our paper focuses on the cross-correlation mechanism, which inherently offers greater expressiveness than self-correlation models like EGNN.\n\n*Note:* Regarding the performance, we have some further comments. Observing the self-correlation models, both EGNN and GraphCroc(SC) can achieve good AUC scores, only slightly lower than our proposed cross-correlation-based GraphCroc, yet GAE and VGAE have poor performance. This is because GAE/VGAE [2] was proposed early and has a simple architecture, while EGNN and GraphCroc(SC) (U-Net-like architecture [3]) are more complicated and have more powerful representation ability on graph structures, outperforming normal GAE/VGAE methods. On the other hand, *common graph tasks are usually asymmetric*, and *self-loops are overlooked* in previous works, which is why even the self-correlation-based EGNN and GraphCroc(SC) can still perform well on these graphs reconstruction. Nevertheless, cross-correlation can still boost the graph structural reconstruction on these graphs, as evidenced by the best performance of our GraphCroc on all graph tasks.\n\n[1] E (n) equivariant graph neural networks, ICML'21;\n\n[2] Variational graph auto-encoders, NeurIPS'16;\n\n[3] Graph u-nets, ICML'19.\n\n> More results in reconstruction visualization for specific graph structures, such as island, symmetric structures, and directed graphs.\n\nIn Sec.2.2 and 2.3, we explore the limitations of self-correlation and the effectiveness of cross-correlation in expressing specific graph structures. Given that previous GAE research often evaluates undirected asymmetric graph structures, we similarly provide the evaluation of graph structural reconstruction for common real-world graph tasks (Table 1). Additionally, we agree that it would be highly beneficial to include clear visualizations demonstrating how various encoding methods succeed or fail in reconstructing specific graph structures.\n\n**island (without self-loop) and symmetric graph structure:** We generate 4 topologically symmetric graphs devoid of self-loops. We task the evaluated models with learning to reconstruct these graph structures and assess their performance. The visualization of their reconstruction is presented in `Fig. 1` of our rebuttal PDF file. 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 proving our discussion in Sec.2.2 and 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))$) [4]. 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. \n\n**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 and CiteSeer datasets. Specifically, we randomly select 1,000 subgraphs. Of these, 800 subgraphs were used for training and 200 for testing. The results are detailed below, where $\\bar{N}$ represents the average number of nodes per graph:\n\n|          | Cora_ML ($\\bar{N}=41$) | Cora_ML ($\\bar{N}=77$) | CiteSeer ($\\bar{N}=16$) |\n|---|:-:|:-:|:-:|\n| GraphCroc| 0.9946  | 0.9996  | 0.9999  |\n| DiGAE    | 0.6870  | 0.8296  | 0.9083  |\n\nOur GraphCroc can well reconstruct the directed graph structure with almost perfect prediction, which significantly outperforms the DiGAE model. This advantage comes from the expressive model architecture of our proposed U-Net-like model.\n\n[4] Graph normalizing flows, NeurIPS'19.\n\n> Related work discussion: \"Where to Mask: Structure-Guided Masking for Graph Masked Autoencoders.\" IJCAI'24.\n\nThanks for your suggestion about the related work. This work addresses node importance in graph construction and proposes a structure-based masking strategy. This strategy guides the masking on GAE with more rationality, and is well evaluated based on the standard GraphMAE. We will give a discussion of this work and include its performance on graph classification tasks in Table 2 of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wozjB4vJhN", "reviewer": "Reviewer_Xxf1", "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.", "questions": "see above weakness", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea to introduce two latent space for reconstructing the graph structure is \"simple and intuitive\". \n\n2. The writing is clear and easy to follow.\n\n3. The experimental results are sound.", "weaknesses": "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?\n\n[1] You, Jiaxuan, Rex Ying, and Jure Leskovec. \"Position-aware graph neural networks.\" International conference on machine learning. PMLR, 2019.\n\n[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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 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 or adding extra node labels. How the proposed method is compared with these methods, from the perspective of effectiveness and efficiency?\n\nThank you for your suggestion. The first referenced paper incorporates positional information into node embeddings, whereas the second paper explores the effectiveness of the labeling trick by adding labels to nodes of interest. Before delving into comparisons, it is necessary to highlight a shared point across these studies and ours: **all approaches try to introduce asymmetry into node embeddings, to effectively represent node connections in symmetric/isomorphic graph structures**. In our work, this is achieved through cross-correlation and the application of two-set node embeddings. This shared point is also applied in the DiGAE approach [5], although it is not explicitly discussed in their work, given their focus on representing asymmetric directed graphs. This commonality makes these methods all theoretically effective for representing special graph structures, such as symmetric nodes; yet this effectiveness is limited to their application scenarios.\n\nOur GraphCroc model is designed to represent the entire graph all at once, directly outputting the complete predicted adjacency matrix rather than individual predicted edges. This makes GraphCroc particularly suited for per-graph downstream tasks such as graph classification. In contrast, the labeling trick is designed for link prediction, where only specific node pairs or subsets are labeled, creating asymmetry between these nodes and others. Labeling must be conducted either pair-by-pair or subset-by-subset to maintain this asymmetry, which is a critical aspect of the labeling trick's approach. If all nodes were labeled to reconstruct all edges, distinctions would be needed between specific node labels to break down symmetry effectively. However, GraphCroc offers an easier approach, reconstructing the graph structure in one go without the need for repeated generation of node embeddings for different node pairs. This efficiency makes GraphCroc more effective for whole-graph reconstruction, while the labeling trick remains better suited for tasks focusing on link prediction between selected node pairs.\n\nPosition Encoding (PGNN) is also evaluated in link prediction tasks. However, PGNN has the potential to be applied to structural reconstruction across the entire graph, provided the selected anchor set facilitates asymmetric message aggregation. Regarding efficiency, PGNN's process must regenerate the anchor set of the newly structured graph after each pooling layer, due to the dynamic nature of graph structures in GNN tasks, which can lead to notable inefficiencies. In contrast, GraphCroc does not need preprocessing on the graph structure, but dynamically adjusts asymmetry through the parameters of its decoder during training; thus, GraphCroc offers greater efficiency and adaptability. Furthermore, the asymmetry in PGNN is predetermined by the anchor set selection and remains static throughout training, making it dependent on initial anchor choices. This contrasts with GraphCroc's more flexible and adaptive approach to handling graph structure representations.\n\nIn conclusion, a significant application difference is that GraphCroc encodes the entire graph in a latent embedding suitable for downstream tasks, allowing the inclusion of graph pooling layers. However, both position encoding and the labeling trick primarily focus on node-level embeddings, preserving the graph's original structure, with downstream tasks limited to node classification and link prediction.\n\n[5] Directed graph auto-encoders, AAAI'22.\n\n\n>  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.\n\nThe difference between two latent embeddings (denoted as $P, Q$) is fundamental to cross-correlation 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)$).\n\nHowever, 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-correlatin, our two-branch structure will encourage sufficient divergence on $P$ and $Q$ to suit structural reconstruction. To evaluate the differentiation between $P$ and $Q$, we compute their cosine similarity and present a histogram of these values for each graph task in `Fig. 2` of our rebuttal PDF file. Across all tasks, the cosine similarity between the node embeddings under cross-correlation is generally low, typically below 0.6. This shows that our two-branch 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 of our paper).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JVFBYcSJ2e", "reviewer": "Reviewer_QrYC", "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.", "questions": "see Weakness.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The motivation is clear and the cross-correlation autoencoder is reasonable.\n2. The paper is well-written and easy to follow.\n3. The experiments are comprehensive.", "weaknesses": "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. \n\n2. 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.\n\n3. More different architectures of the encoder and decoder should be employed to further verify the effectiveness of the cross-correlation mechanism.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Evaluate the proposed cross-correlation autoencoder given specific graph structures, e.g., islands and symmetric structures.\n\nIn Sec.2.2 and 2.3, we explore the limitations of self-correlation and the capabilities of cross-correlation in accurately representing specific graph structures, such as non self-loop, symmetric structures, and directed edges. In the evaluation, we follow previous GAE research to apply our proposed GraphCroc on common real-world graph tasks (Table 1), which are undirected asymmetric graph structures. Additionally, we present a comparison of how various models reconstruct specific graph structures in `Fig. 1` of our rebuttal PDF file. Specifically, we randomly generate 4 graphs where each graph is *topologically symmetric* and contains *no self-loop*. These graphs are then used to evaluate the performance of different GAE models. The visualizations clearly illustrate that our GraphCroc model proficiently reconstructs these graph structures. For DiGAE which is also based on cross-correlation, it can well reconstruct the special graph structures, further proving our discussion in Sec.2.2 and 2.3. \n\nIn contrast, other models often erroneously predict connections between symmetric nodes and introduce unwanted self-loops, highlighting the superior representation ability of cross-correlation in handling these specialized scenarios. 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))$, $C>0$) [6]. 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 which have $z_i=z_j$ under symmetric sturctures; alternatively, we can also regard it as the naive Euclidean encoding but with $C<0$. Therefore, EGNN still cannot handle well the graph reconstruction on the special graph structures.\n\n[6] Graph normalizing flows, NeurIPS'19.\n\n> Evaluation on direction graphs.\n\nMost graph reconstruction research is evaluated on undirected tasks, so for a fair and comprehensive comparison, we also utilize undirected graphs. Additionally, structural reconstruction on directed graphs has gained focus recently in the DiGAE work (AAAI'22). Hereby, we further investigate GraphCroc's performance on directed graph datasets. We compare GraphCroc with DiGAE, given that only cross-correlation-based methods can effectively capture directional relationships between nodes. To construct the dataset, we sample subgraphs from the directed Cora and Citeseer datasets. We randomly selected 1,000 subgraphs, using 800 for training and 200 for testing. The results are shown below ($\\bar{N}$ represents the average number of nodes per graph):\n\n|| cora ($\\bar{N}=41$) | cora ($\\bar{N}=77$) | cite ($\\bar{N}=16$) |\n|-|:-:|:-:|:-:|\n| GraphCroc| 0.9946  | 0.9996  | 0.9999  |\n| DiGAE    | 0.6870  | 0.8296  | 0.9083  |\n\nOur GraphCroc can well reconstruct the directed graph structure with almost perfect prediction, which significantly outperforms the DiGAE model. This advantage comes from the expressive ability of our proposed U-Net-like architecture.\n> More different architectures of the encoder and decoder should be employed to further verify the effectiveness of the cross-correlation mechanism.\n\nThank you for your suggestion of further evaluation on cross-correlation across different GNN architectures. In addition to the GCN kernel used in our GraphCroc model, we extend our analysis to include other widely used graph architectures such as GraphSAGE [7], GAT [8], and GIN [9]. To incorporate these architectures into the cross-correlation framework, we replace the GCN module with corresponding operations while preserving the overarching structure, which includes the encoder, 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 5 of our paper, except for the QM9 dataset, where we limit the training to 20 epochs due to its large size and the limited time frame for our rebuttal. The results, presented below, follow the format of Table 1 in our paper, providing a clear comparison across different architectures:\n\n| | GraphSAGE| GAT| GIN|GraphCroc(w/o skip connection)| GraphCroc|\n|-|:-:|:-:|:-:|:-:|:-:|\n| PROTEINS | 0.9898   | 0.9629  | 0.9927  |  0.9934 | 0.9958 |\n| IMDB-B   | 0.9984   | 0.9687  | 0.9980  |  0.9975 | 0.9992 |\n| Collab   | 0.9985   | 0.9627  | 0.9954  |  0.9976 | 0.9989 |\n| PPI      | 0.9774   | 0.9236  | 0.9467  |  0.9447 | 0.9831 |\n| QM9      | 0.9972   | 0.9978  | 0.9974  |  0.9966 | 0.9987 |\n\nOverall, all architectures employing cross-correlation 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 did 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.\n\n[7] Inductive representation learning on large graphs, NeurIPS'17;\n\n[8] Graph attention networks, ICLR'18;\n\n[9] How powerful are graph neural networks?, ArXiv'18.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the time and effort the reviewers have spent in providing valuable feedback! We are grateful for the reviewers' recognition of our clear writing, reasonable motivation, and sound experiments. Graph structural reconstruction is a pivotal application for graph autoencoders (GAEs), and we hope that our research offers a novel perspective on graph representation and proves beneficial to the community.

In response to your comments, we address all identified weaknesses and questions. We welcome further feedback and are eager to engage in discussions regarding the paper's content. Additionally, following suggestions for enhanced visualizations, we include new figures in our rebuttal and attach them in the PDF file below. References to these figures are highlighted, e.g., `Fig. 1`. All responses to reviewers' comments will be reflected in our paper's final version.

Meta-review: 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.
Decision: Accept (poster)