On Reconstructability of Graph Neural Networks

4. For the definition of context features, why are they defined in terms of labels? Do you assume that label information of every node is available both in training and testing? Also, for the sentence "the contextual features include both signal (label information) and noise..." on Page 5, does signal in this paper refer to label information? For the paragraph under Proposition 5, the authors mention "By contrast, GIN exploits \epsilon to preserve the central node’s identity, ...". What does "the central node's identity" mean in terms of contextual features discussed here?
   Yes. The signal refers to the label information. While it is hard to evaluate the correlation between the node features with the graph topology, most GNN frameworks [ICLR22, NeurIPS20] adopt the similar assumption to simplify the problem, but focus on the effect of the message passing process. Note that the node identity represents exactly its own contextual features.

[ICLR22] Is Homophily a Necessity for Graph Neural Networks?
[NeurIPS20] Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs.

5. The reason why GIN can approximate the 1-WL test is not only due to an irrational number \epsilon, but also the injectivity of the sum aggregation function. The proposed GRNN adds $\mathbf{w}_j$ before each $\mathbf{h}_j$? This changed form cannot preserve the injectivity of node features in the aggregation any more. Does this matter for GRNN?
   In the aspect of graph reconstructability, injective is not necessary for the GRNN. Since GIN is also a special case of GRNN, we can also set all w_i to 1 to preserve such property. However, without normalizing the aggregation weight, we require a larger embedding dimensionality to retrain the graph reconstructability as suggested by Corollary 3.

6. For the sentence "It is not feasible to distinguish the model capability in the real-world graph by GRR because each dataset contains one instance and thus only returns 1 or 0", what does this mean?
   Since it is difficult to investigate the impact of essential factors on graph reconstructability in a controlled manner with real graphs, we first present experimental results on synthetic graphs. GRR is defined as the portion of the graph that can be perfectly reconstructable given a set of graphs from GNN, which returns a boolean for each instance (0/1). To evaluate the level of graph reconstructability on a single large graph, especially for real networks, we employ the AUC score, which usually evaluates the performance of link prediction by ranking the value of the inner product between two node embeddings. Therefore, we adopt the AUC score as the metric to evaluate the model performance. Specifically, we train an additional logistic classifier to predict the probability of each edge between nodes and rank the results to derive the AUC score. When AUC is 1, the model can correctly distinguish linked and unlinked pairs, i.e., perfectly reconstructable, which is also proved in Proposition 7.

1. The notion of graph reconstructability discussed in this paper is very different from graph reconstruction and graph properties in graph theory. Basically, the key idea of recovering a graph in this paper is based on encoding node and edge information, while the other graph topological information/properties (such as cycles, cliques, paths, etc.) are not relevant. In other words, if we assign each node with a unique identity, and then store the identity of a node along with the identities of its neighboring nodes (i.e., edges incident to each node) into its node feature, then a graph can always be represented (or say reconstructed if using the term of this paper) from node features. This is kind of a neural version of representing a graph using adjacency lists. However, this doesn't mean that GNNs with such node features are powerful for representing/learning graph topological information (e.g., cycles, cliques, etc.) that are useful for graph-related tasks. Furthermore, adding such node identities and embedding into node features would lead to the loss of permutation invariance, which is an important property of GNNs when learning structures. For example, two isomorphic graphs where their nodes are assigned with different identity features would have different node representations and become non-isomorphic. Thus, the way of analyzing GNNs in terms of graph reconstructability proposed in the paper does not contribute much to the theoretical analysis of expressiveness of GNNs.
   Thanks for your advice. As we mentioned in the introduction, previous works analyze the expressive power of GNN via graph isomorphism test, i.e., GNN is able to distinguish between two graphs that have the same structure. However, little work studies exactly what information is encoded by popular embedding methods, and how this information correlates with performance in downstream learning tasks. We tackle this question by studying whether embeddings from GNN can be inverted to recover the complete graph topology used to generate the via various feature initialization schemes. Similar idea has been shown in [ICML21], which investigates whether the learned embedding is able to recover the origin graph under a skip-gram scheme. However, they do not investigate how different feature initialization affects the graph reconstructability. We believe that we are the first to analyze how the message passing process can effectively encode the graph topology in the node embedding , which is essential for many graph mining applications.

[ICML21] DeepWalking backwards: From embeddings back to graphs.

2. For Proposition 1, the only if part is unclear. Why is the condition on the inner product of the embeddings of linked and non-linked node pairs the only way to ensure that a model is graph reconstructable?
   Thanks, the inequality serves as the definition of graph reconstructability. It is natural to utilize the dot product to evaluate the constructability since in skin-gram objective in node embedding schemes could be summarized in various forms of matrix factorization over the Pairwise Mutual Information (PMI) Matrix, where the dot product of the node embedding also describes the node similarity. Based on Proposition 1, we can determine if the node embeddings learned by a GNN can reconstruct a graph using the inner product of embeddings for linked and unlinked node pairs. Note that a logistic classifier trained through gradient descent can be employed to extract this decision boundary.

3. What are $\tau_l$ and $\tau_u$ in the proofs of Proposition 2 and Proposition 3? Why is "-1" omitted in $\tau_l(D_i-1)$? When two nodes are linked, they have a probability $\tau_l$ with a common neighborhood. Otherwise, the unlinked pair has a probability $\tau_u$ with a common neighborhood. The assumption of the probabilities of linked nodes and unlinked nodes that have a common neighborhood is just a simple math trick to reduce the complexity of the equation. Actually, we can assign each node with different values of probabilities of common neighborhood and our theoretical results are also held. Since $\tau_l(D_i-1)$ is the left hand side of the inequality, i.e., $\tau_l(D_i)$ is always greater than $\tau_l(D_i-1)$, we omit -$1$ in Proposition 2.

1. It is not easy to directly interpret the experiment results, such as having no bolding for best results. Also to see the effectiveness of NORF, maybe adding an increase/decrease of performance compared to the IF(Identity Features) would be intuitive for readers to understand.
   Thanks for your comments. We will highlight the best experimental results. As shown in Tables 1 and 2, our nearly orthogonal random features (NORF) with contextual features (CF) achieve the best performance in most cases. Specifically, pure CF cannot retain the graph reconstrucatablility of the disassortative graph by 27.3% on average. Compared to identity features (IF), we should carefully select the self-weight ($\epsilon$). For example, the performance of GIN($\epsilon=1$) with IF significantly drops by at least 19.2% for both graphs.

2. The purpose of using a new measurement for the expressivity of GNNs was to maintain the topological information of the whole graph in a node embedding. However, the authors have placed link prediction experiments in the main paper, while placing node classification experiments in the appendix. The performance and meaningfulness of node classification experiments seems to be bigger, it would have been better to place node classification experiments in the section 6 experiments of the main paper.
   Thanks for your comments. We will move the experiment to the main paper. It is worth noting that we aim at answering the fundamental problem of GNN in this paper, i.e., when and how GNN can encode the graph topology in the node embedding via the idea of graph reconstructability. Therefore, in the link prediction, we highlight that NORF is able to preserve the structural similarity of nodes in all datasets. In contrast, the widely-adopted CF, i.e., node attributes, in most GNN relies on the assumption of graph homophily, indicating that we cannot reconstruct the original adjacency matrix from the original graph with CF. On the other hand, in node classification, CF are useful to predict the node labels through the message-passing process in GNN by considering the neighborhood features distribution because the connected node tends to have the same labels on the assortative graph. However, such a procedure would degrade the model performance on the disassortative graph. In contrast, identity features and NORF merely encode the node identity and are not disturbed by irrelevant (and even misleading) contextual information.

3. The paper suggests a new line of research for the expressivity of GNNs, replacing the WL-test. If a node embedding from a GNN has a high graph reconstructability, i.e., topological information of graph well maintained in node representation, doesn’t this also lead to a more expressive graph level representation? (Since most graph level representation is obtained by pooling all the nodes in the graph)
   Yes. We conduct further experiments with four GNN models, which investigate the expressiveness of GNNs in graph-level tasks. Overall, the GNN performance on graph classification has improved by 3.7% on average by adding the NORF with input features. The results support that GNN with a high graph reconstructability will also lead to better graph-level representation. | #datasets | MUTAG | PTC | PROTEINS | | ---- | ---- | ---- | ---- | | GIN [ICLR19] | 89.4 | 64.6 | 76.2 | | GIN + NORF | 91.2 | 65.7 | 77.1 | | DGCNN [AAAI20] | 85.8 | 58.6 | 75.5 | | DGCNN + NORF | 88.3 | 62.3 | 78.9 | | GSN [TPAMI22] | 92.2 | 68.2 | 76.6 | | GSN + NORF | 93.6 | 72.1 | 78.4 | | PPGNs [ICML19] | 90.6 | 66.2 | 77.2 | | PPGNs + NORF | 92.5 | 68.4 | 79.1 |

[ICLR19] How Powerful are Graph Neural Networks?
[AAAI20] An End-to-End Deep Learning Architecture for Graph Classification.
[TPAMI22] Improving graph neural network expressivity via subgraph isomorphism counting.
[ICML19] Provably Powerful Graph Networks.

1. For the graph-level tasks, the relationship of the graph reconstructability and expressivity of GNNs is not discussed nor evaluated. It has been shown that positional encoding (including identity features) can improve the expressivity of GNNs beyond 1-WL. However, this paper fails to provide further theoretical results of reconstructability and expressivity in GNNs, and no experiments empirically evaluates GRNNs against the state-of-the-art GNNs in graph prediction tasks. Hence, it is not straightforward how GNNs will benefit from improving the graph reconstructability in graph-level predictions. At least, I recommend to do more graph prediction experiments to compare GRNNs with other SOTA expressive GNN models. Yes. We conduct further experiments with four GNN models, which investigate the expressiveness of GNNs in graph classification. Overall, the GNN performance on graph classification has improved by 3.7% on average by adding the NORF with input features. The results support that GNN with a high graph reconstructability will also lead to better graph-level representation. | #datasets | MUTAG | PTC | PROTEINS | | ---- | ---- | ---- | ---- | | GIN [ICLR19] | 89.4 | 64.6 | 76.2 | | GIN + NORF | 91.2 | 65.7 | 77.1 | | DGCNN [AAAI20] | 85.8 | 58.6 | 75.5 | | DGCNN + NORF | 88.3 | 62.3 | 78.9 | | GSN [TPAMI22] | 92.2 | 68.2 | 76.6 | | GSN + NORF | 93.6 | 72.1 | 78.4 | | PPGNs [ICML19] | 90.6 | 66.2 | 77.2 | | PPGNs + NORF | 92.5 | 68.4 | 79.1 |

[ICLR19] How Powerful are Graph Neural Networks?
[AAAI20] An End-to-End Deep Learning Architecture for Graph Classification.
[TPAMI22] Improving graph neural network expressivity via subgraph isomorphism counting.
[ICML19] Provably Powerful Graph Networks.

2. Label features and NORFs essentially break node symmetries, which makes the graph reconstructability problem trivial.
   Indeed, the concept of symmetry-breaking offers an alternative perspective for comprehending our theoretical findings. As shown in the introduction, our objective is to explore the configuration of graph neural networks employing varied feature initialization methods to restore the original input graph. However, the features that lack symmetry do not align seamlessly with our theorem due to the intricate calibration required for the GNN's design, encompassing factors such as the self-embedding weight (\epsilon) and the aggregation weight (\mathbf{w}), both of which need to be meticulously configured based on the underlying graph structure, such as graph homophily and node degree. Consequently, we introduce NORF with GRNN to uphold the graph's reconstructability, thus alleviating the constraint imposed by the graph's structure.

3. The configurations of baseline models in link prediction and community detection are missed. For instance, [1] shows that SEAL can achieve a competitive results when using a GCN and the DRNL labeling trick, with an additional subgraph-level readout SortPooling. Then, how do CommDGI and SEAL implemented in this paper.
   We follow the original implementation for both SEAL and CommDGI. For SEAL [1], we concatenate the DRNLl with the contextual features and train the model by pairwise mutual information . For CommDGI [1], we employ the CF and jointly optimize modularity objective and community mutual information. The source code can be found here.

[1] https://github.com/muhanzhang/SEAL
[2] https://github.com/FDUDSDE/CommDGI/tree/main

5. A promising extension of the current theoretical results would be to investigate which graph structural properties we can reconstruct based on the computed node embeddings, even if we cannot reconstruct the entire node adjacency. E.g., can we count the number of paths, cycles or cliques? This might be particularly interesting in the context of social networks.
   Thanks. [SDM21] study on the power of positional encoding (random feature) to make the GNN strictly more powerful than the 1-WL test, they show that prove that GNN can distinguish any local structure with high probability in various graph ming problem, such as maximum matching and minimum dominating set problems. However, we focus on the reconstruction of the original graph from the learned embeddings. Moreover, we make the first attempt to study how to determine the embedding dimensionality of random features to preserve the orthogonality for providing a unique node identification (from $O(V)$ to $O(log (V)$)).

[SDM21] Random Features Strengthen Graph Neural Networks.

6. Can you explain the experimental setup for Fig. 1 in more detail? What is $\epsilon$ in Fig. 1b? What node features (IF, CF, NORF) are used in Fig. 1b-c?
   Thanks for pointing out this issue. Fig. 1b aims to verify the correctness of Proposition 4, i.e., with higher noise in the CF, a higher self-weight $\epsilon$ is required. We test the noise ratio ($sigma_0$) of CF in Fig 1b, the maximum node degree ($D_{max}$), and the dimensionality ($d$) of NORF in Fig 1b.

1. Novelty and related work: While the theoretical results for GCN and GIN as well as the proposed GRNN and NORF seem novel, there is little mention of or comparison to related work about reconstructing the graph topology from embeddings [1, 2]. On a similar note, there is no mention of subgraph GNNs or the concept of graph reconstruction (i.e., reconstructing a graph from its subgraphs) [3]. A more comprehensive discussion of the contribution and its placement in the current literature would be helpful in assessing its novelty and impact.
   As we stated in Appendix C.3, [1,2] investigate whether embedding methods learned by the skip-gram objective can reconstruct the original graph. The authors subsequently employ the embedding algorithm to solve several fundamental network mining tasks, including common edges, degree sequences, triangle counts, and community structure. This is because the skip-gram-based embedding schemes could be summarized in various forms of matrix factorization over the Pairwise Mutual Information (PMI) Matrix (Qiu et al., 2018). Nevertheless, they do not consider the node features (e.g., attributes or identity encoding) which serve as the carrier to pass the information in GNN. In addition, they do not study the impact of several graph properties, such as graph degree and homophily, for preserving the graph topology during the message passing processing in GNNs. In addition, we theoretically analyze the dimensionality of embedding and reduce the complexity from O(|V |) to O(log(|V |)), while retaining the reconstructability by properly designing the GNN and initial features. Compared to [3], the graph reconstruction conjecture states that an undirected edge unattributed graph can be fully recovered up to its isomorphism type given the multiset of its vertex-deleted subgraphs' isomorphism types. These works aim to investigate graph isomorphism through reconstructing the original graph using sampled subgraphs. In contrast, our idea explores the manifold of node embeddings, where connected nodes are probably more concentrated in the embedding space.

2. Theoretical results: The theoretical analysis would benefit from more rigorous/formal definitions, in particular when introducing novel concepts. Definition 1 defines graph reconstructability as "the ability of a model to predict the input adjacency matrix from the node features". One possible interpretation of this definition would be to have a machine learning model which learns to predict the adjacency matrix of a graph from (raw) node features (which, according to my current understanding of the paper, is not what graph reconstructability means).
   Yes. We aim to evaluate whether the GNN can learn to predict the adjacency matrix of a graph from (raw) node features.

3. Experiments: "By combining NORF and contextual features (which would be naturally used in applications), our GRNN achieved the best performance among baselines." For Table 1, this is only true for the Actor dataset. In general, the results of the baseline methods (GCN, GIN, GAT, SGC) seem comparable to GRNN.
   Yes, as stated in Theorem 3, these lines of message passing type GNNs are the special case of our GRNN. In our framework, we aim to provide a theoretical framework to describe when GNN is able to retain the reconstructability. It’s worth noting that GRNN is able to reduce the dimensionality of NORF by properly setting the self-weight and aggregation weight which can be verified in Table 6 in the Appendix C.

4. Proposition 1: Is the inequality on the inner products of linked/unlinked nodes an assumption/part of the definition?
   The inequality serves as the definition of graph reconstructability. It is natural to utilize the dot product to evaluate the constructability since in skip-gram objective in node embedding schemes could be summarized in various forms of matrix factorization over the Pairwise Mutual Information (PMI) Matrix, where the dot product of the node embedding also describes the node similarity. Based on Proposition 1, we can determine if the node embeddings learned by a GNN can reconstruct a graph using the inner product of embeddings for linked and unlinked node pairs. Note that a logistic classifier trained through gradient descent can be employed to extract this decision boundary.

5. Using identity features means that we lose permutation invariance; what about NORFs?
   Indeed, with NORF, GNN is not permutations invariant, but many positional encoding schemes [ICLR20,ICML19] also provide a unique representation for each node to derive a strictly more powerful GNN than WL-test.

[ICLR20] What graph neural networks cannot learn: depth vs width.
[ICML19] Relational pooling for graph representation.

Thank you for your response. My second question remains unaddressed:

Appendix A.3 uses notation which stems from Definition 6 in [4]. I have consulted [4] but could not find the definition, could you point me to the specific page?