Normalized Space Alignment: A Versatile Metric for Representation Space Discrepancy Minimization

Thank you very much for taking the time to review our work. We address your concerns below:

Can authors explain why it is important to compare the similarity of representations in graph neural networks?

Response: The embedding of complicated metric spaces into simpler spaces has been investigated for a long time. Among the "complicated" metric spaces, graphs have been particular challenging because of impossibility results on isometric embeddings (no matter how many target dimensions) and bounds on distortions of their embedding into Euclidean spaces [1][2]. Coupled with their abstraction ability and wide-ranging applications, this makes the study of the geometry of graph representations especially interesting. NSA as a similarity measure is domain agnostic but demonstrating its capability to extract meaningful insights from intricate networks like GNNs will also establish its utility in simpler domains, like images and text processing. We expand upon this in Concern 1 of the common response and in Section 5 of the revised manuscript.

Is NSA sensitive to the removal of low variance principal components from representations?

It is highly likely that as a Representation Similarity Matrix based measure, NSA suffers from the same issues as CKA and it is not sensitive to the removal of low variance/unimportant principal components. We have not conduced experiments to confirm this claim but plan to do so in a future work.

I understand NSA can measure the differences of normalized point-to-point distances in two representations. However, in the definition of Section 3.1, the point structure within representations seems to be not considered. I wonder if there exists a situation where the NSA of two representations is small but the two representations have totally different point structures.

Response: We have expanded on the definition of NSA in Section 3.1 to show how it is capable of measuring point-wise discrepancies along with a global measure of the dissimilarity between two spaces. We also present new experiments with point-wise NSA in Section 6 (Figure 5 (a)) where we show that NSA can quantify the discrepancy in the relative position of individual points. In our practical tests, we have not encountered a case where the NSA is small but the two representations have completely different point structures. The opposite could be true in the case where the input data lies in a lower manifold dimension compared to its representation dimension. Then the NSA would be large but the two representations (original dimension vs flattened or unfolded manifold dimension) would be very similar. In these situations NSA can be used to minimize the geodesic distance if we know the manifold dimension of the data. We discuss this scenario in Section 4.3 of the paper and present new experiments along with a solution to overcome these situations.

Why NSA only slightly outperforms or performs worse than previous methods in some cases in Table 1?

Response: NSA provides the ideal tradeoff between structure preservation and computational efficiency. NSA is outperformed by PCA in Triplet Accuracy of Cluster Centers. PCA excels at this with its simplicity and focus on linear variance. NSA is also barely outperformed by RTD-AE in RTD as RTD-AE directly minimizes the Representation Topology Divergence between the original and the latent space as part of their training. PCA is strictly a dimensionality reduction technique and cannot be used with mini batching as a loss function. RTD is extremely inefficient in its computational complexity and we present the difference in epoch time for training in Table 3 in Appendix J. RTD-AE takes 10x the time to finish an epoch compared to NSA-AE and is limited to batch sizes under 400 due to its high complexity. We discuss the difference in complexities in Section 3.4 of the revised manuscript. Additionally, the datasets we use for the dimensionality reduction tests are popular benchmark datasets and most existing techniques get high performance when trained on these datasets. We present a more challenging task in Section 4.2 where we train the models to preserve the inter node relationships necessary to perform link prediction. Here we observe NSA-AE outperforming even RTD-AE.

"CKA" in paragraph 1 of Section 2 seems to be in the wrong font. The font size of the text in most figures, especially in Figure 2 is too small.

We have fixed these errors. Thank you for bringing them to our notice

Please let us know if you have any additional concerns that we can address. If not, would you kindly consider raising your score? Once again, thank you for your review.

[1] On lipschitz embedding of finite metric spaces in Hilbert space by Jean Bourgain, Israel Journal of Mathematics. [2] The Geometry of Graphs and Some of Its Algorithmic Applications by Linial, N. and London, E. and Rabinovich, Y. , Proceedings of the 35th Annual Symposium on Foundations of Computer Science

Thank you very much for taking the time to write a detailed review. Your feedback has been extremely useful in updating our work. We address your points of concern below:

While I see the contribution favourably, there are major weaknesses precluding the presentation of the paper in its current form. The primary one is a missing analysis of fundamental properties. While I appreciate the broad range of different applications, this invariably means that some depth is lost and analyses are relatively superficial.

Response: We extend the definition of NSA to show that it can measure point-wise discrepancies. All properties necessary establish its viability as a similarity metric (including its invariance to global isometries) and loss function are proven in Appendix B and C. We also move any speculative results to the appendix (Refer to Summary of Revisions Point 3) and expand on both the autoencoder experiments and the adversarial analysis with more results to cement NSA’s viability as a representation similarity measure. The primary objective of this paper is intended to be the introduction of NSA and a showcase of its versatility. We intend on building on NSA and exploring its potential in-depth in future works.

Introducing a new measure and then showing its utility requires a more in-depth view of data, though. For instance, when introducing the latent representations in Table 1, readers are only shown the actual scores, but the primary assumption is that the scores actually capture the relevant properties of the data. Phrased somewhat hyperbolically: I believe that NSA can be calculated as described, but I do not understand whether it measures something 'interesting.' The fact that it correlates with performance metrics is relevant, but immediately suggests a more detailed comparison scenario, for instance in the form of an early stopping criterion or regularisation term.

Response: Thank you for your feedback. We address this in Concern 2 and Concern 3 of the common response. Additionally, we discuss the viability of NSA as an early stopping criterion in Section 5.2 where we show that NSA stabilization correlates with test accuracy convergence.

I'd suggest to shorten the RTD explanation or substantially extend it. Currently, it makes use of jargon like , 'barcode,' and Vietoris--Rips filtrations that are not sufficiently explained (I am familiar with the work and I believe that a deep dive into topological methods is not required). To simplify the notation, I'd either use the actual Euclidean norm in the definition of NSA or write x and 0 as vectors.

We have taken your feedback into consideration and simplified the explanation of RTD, we have also improved on the notation of NSA in the definition

The autoencoders experiment is somewhat out of place since the introduction sets up a paper on GNNs. Given the broad scope of NSA, I think it might be best to stay with the autoencoder comparison, using data with a known ground truth. This could take the form of building confidence by starting with simple toy examples like a 'Swiss Roll' or other data sets and showing that NSA matches the intuition.

Response: We restructure the paper to reduce the focus on GNNs and address this shortcoming in Concern 1 of the common response. We expand on the autoencoder experiments and move any speculative results with GNNs to the appendix. We also present the results of using NSA-AE on the Swiss Roll dataset. NSA can be used to minimize geodesic distances if the manifold dimension of the original representation space is known. We exploit this information to flatten a swiss roll with NSA-AE. The results are presented in Section 4.3 and in Figure 1 of the revised manuscript.

Thank you for taking the time to review our work. We address all your concerns below:

The proposed pseudometric does not make any sense to me. One clear issue with it is the fact that it is not invariant to permutation between the vectors in the point cloud. This is a huge issue, in my mind, as there is no reason to assume the vectors are aligned so it is greatly impacted by a random permutation between them. The authors also don't give any sufficient motivation for this metric, besides the fact that it satisfies some basic properties like triangle inequality.

Response: Thank you for taking the time to review our work. NSA is a representation similarity measure and measures the discrepancy between two representation spaces. A permutation between the vectors in a point cloud would result in a loss of the one-to-one mapping that NSA requires and would fundamentally change the representation space and the relationships between the points of this space, thus representation similarity measures like NSA or CKA cannot be invariant to this type of permutation. NSA as a similarity measure is invariant to global isometries.

NSA along with other Representation Similarity measures [1] are invariant to scaling, translation or rotation transformations on the representation spaces as they only compare the discrepancy between the relative positions of data in their own embedding spaces. Representation Similarity Measures are well motivated through several popular previous works like CCA [2], CKA [3], RSA [4] and RTD [5]. We provide proofs in Appendix A that NSA satisfies all the conditions to qualify as a pseudometric. Appendix B provides the proofs to demonstrate that it is invariant to isometries and satisfies the conditions necessary to qualify as a similarity index, as proposed by [3]. Appendix C proves that NSA is continuous and differentiable, allowing us to use it as a minimization objective.

NSA is motivated by the need to fill a gap in existing similarity measure research. Current measures fall into one of the two categories: 1) They can quantify the discrepancy between two representation spaces but are not differentiable and cannot be used as a minimization objective in neural network training. 2) Measures that are differentiable [5] are very computationally expensive and cannot be employed in practical scenarios for large scale neural network training. NSA is differentiable and its complexity is quadratic in the number of points, facilitating its use as a minimization objective in any training paradigm that necessitates the alignment of embedding spaces such as dimensionality reduction, adversarial training, link prediction, knowledge transfer or distillation and semantic similarity among others without a significant loss in training efficiency. We present results that show NSA not only preserves representation structure (Section 4) but the aligned embeddings are effective in downstream tasks like link prediction (Section 4.2) and semantic similarity (Appendix M). We also show in Table 3 that NSA is over 10x faster than its closest competitor (RTD) while being used as an additional loss term. All of these experiments serve to showcase the versatility of NSA and its ability to serve in practical training scenarios.

[1] Similarity of Neural Network Models: A Survey of Functional and Representational Measures by Klabunde, Max and Schumacher, Tobias and Strohmaier, Markus and Lemmerich, Florian, arXiv 2023. [2] SVCCA: Singular Vector Canonical Correlation Analysis for Deep Learning Dynamics and Interpretability by Raghu, Maithra and Gilmer, Justin and Yosinski, Jason and Sohl-Dickstein, Jascha NeurIPS 2017. [3] Similarity of Neural Network Representations Revisited by Simon Kornblith, Mohammad Norouzi, Honglak Lee and Geoffrey E. Hinton. [4] Representational similarity analysis - connecting the branches of systems neuroscience by Kriegeskorte, Nikolaus and Mur, Marieke and Bandettini, Peter, Frontiers in Systems Neuroscience 2008. [5] Representation Topology Divergence: A Method for Comparing Neural Network Representations by Barannikov, Serguei and Trofimov, Ilya and Balabin, Nikita and Burnaev, Evgeny. ICML 2022.

Thank you very much for taking the time to review our work. We will address your concerns below:

The authors posit that the Normalized Space Alignment (NSA) technique is structure-preserving, yet there is a noticeable gap in addressing the underlying data's graph structure. NSA primarily focuses on measuring distances between two point clouds, neglecting the crucial graph edges. This oversight brings its capability to preserve graph structure into question. Moreover, although the paper intends to underscore NSA's unique potential in the context of Graph Neural Networks, the actual exploration of these capabilities is missing.

NSA belongs to the class of similarity indices just like Centered kernel alignment and Representation Topology Divergence. NSA measures the discrepancy between two embedding spaces. As a similarity index it is capable only of measuring how dissimilar two embedding spaces are. As a minimization objective, it is capable of aligning one embedding space to another (parent or ideal) embedding space. Scenarios where embedding space alignment is of paramount importance would be knowledge transfer, distillation, dimensionality reduction, robust training and model interpretability among others. We address the issue of the paper being too focused on GNNs in Concern 1 of the common response. Another reason for the paper utilizing GNNs in its empirical analysis is that exploration of GNN’s embedding capabilities are largely missing from previous literature.

Lack of Downstream Task Evaluation: Given that NSA is proposed as a loss function, it is critical to evaluate its effectiveness in downstream tasks. Unfortunately, the paper lacks such evaluations. Insights into how the latent embeddings from an autoencoder, shaped by NSA, could enhance downstream task performance are notably missing.

We present additional experiments to validate NSA-AE’s downstream task performance in section 4.2 and appendix M. Please refer to Concern 2 of the common response for additional details.

Dataset Limitations: The paper’s conclusions are drawn from experiments conducted solely on the Amazon Computers dataset for node classification. Different graph datasets possess varied properties and can elicit diverse behaviors, making it imperative to extend the analysis to a broader set of datasets for more robust and convincing results.

We choose to train our models on the Amazon Computer Dataset as it has the ideal tradeoff between downstream task accuracy and dataset size. GNNs are almost always shallow as the benchmark datasets currently available and utilized by the research community are very small. Training a 2 layer GNN on these datasets would not show a strong linear correlation across layers that we wanted to demonstrate with NSA. The larger datasets have very poor performance with popular GNN architectures, often not reaching convergence. Since all our empirical analysis relies on the assumption that representation spaces stabilize as they converge (Figure 3), a poor performing dataset cannot be used for our experiments.

We extend our experiments to 4 additional datasets to demonstrate NSA’s robustness. We utilize the Cora, Citeseer, Pubmed and Flickr datasets and showcase their results on the sanity tests, cross architecture tests and cross downstream task tests in Appendix Q.

Inconsistency in Data Analysis: There is a puzzling contrast between the paper’s stated focus on Graph Neural Networks (and graph data) and the NSA-AE analysis, which is not applied to graph datasets.

Thank you for bringing this shortcoming to our attention. We address this in Concern 1 of the common response and have made the necessary revisions in our manuscript to improve the flow of the content in the paper.

Adversarial Attack Analysis Shortcomings: The attempt to correlate NSA values with misclassification rates, aiming to use NSA as a metric for evaluating GNN resilience, lacks conviction. NSA values exhibit significant variability across different GNN architectures, and potentially across various graph datasets. The observed discrepancy, where GCN shows the highest misclassification rate while GCN-SVD has the highest NSA value, further complicates any straightforward interpretation based on NSA values alone.

Thank you for your feedback. We address this in Concern 3 of the common response and present additional experiments in Section 6 to help interpret the initial results better. We have also improved the writing in this section to help with readability.

Concern 1: Why is NSA focused on Graph Neural Networks? The switch from GNNs to autoencoders seems out of place. Why use GNNs to evaluate NSA if you do not explore the correlation with graph structure?

Response: We appreciate your queries regarding our focus on Graph Neural Networks (GNNs) and the transition to autoencoders in our study. Initially, we chose GNNs due to the representation challenges in embedding graph structures into simpler spaces, a topic of significant interest in recent research. Graphs have been particularly challenging because of impossibility results on isometric embeddings (no matter how many target dimensions) and bounds on distortions of their embedding into Euclidean spaces [1][2]. GNNs, with their inherent complexity, provided a robust testing ground for NSA. NSA is designed to measure 'dissimilarity' between two embedding spaces as long as a one to one mapping exists between the points in both embedding spaces, regardless of their originating architecture or dimensionality. This flexibility allows NSA to be applicable across various domains, and not only limited to GNNs.

Our initial focus on GNNs aimed to demonstrate NSA's capability to extract meaningful insights from intricate neural networks, thus establishing its utility in simpler domains, like image or text processing. Previous literature on similarity indices is also focused on convolutional neural networks and regular neural networks, leaving GNN embedding capabilities largely unexplored. However, we acknowledge that the paper's initial version may have overly emphasized GNNs, potentially obscuring NSA's broader applicability.

In response to your feedback, we have revised the manuscript to clarify NSA's versatility. We have restructured the content to introduce NSA as a domain-agnostic similarity metric initially, followed by its validation through autoencoder experiments. The latter part of the paper now focuses on empirically analyzing NSA's effectiveness, using GNNs as a case study to illustrate its performance rather than as the primary subject of investigation. These changes aim to present a more balanced view, highlighting NSA's general applicability rather than suggesting it is specific to GNNs

Concern 2: Autoencoder results are not convincing enough. A Downstream task evaluation of the embeddings obtained from NSA would help prove its viability.

Response: We concur that maintaining structural consistency between the original and latent embedding spaces in our autoencoder doesn't intrinsically validate the utility of the latent embeddings. Specifically, in tasks where preserving semantic relationships and the relative positions of data points is critical, traditional dimensionality reduction might not suffice. This concern is particularly relevant in applications like semantic text similarity search, link prediction, facial recognition, and knowledge transfer tasks.

To address this, we have extended our evaluation to include experiments where the NSA-AE's performance is tested in practical scenarios. We trained NSA-AE using embeddings from a link prediction model, then assessed the latent embeddings' efficacy in preserving global structural information. The results, presented in Table 2 of the main text, show NSA-AE outperforming both a basic autoencoder and RTD-AE in retaining this crucial information.

Furthermore, we evaluated NSA-AE on semantic textual similarity tasks. Here, we reduced word embeddings from a word2vec model and compared the correlation between similarities derived from the original and latent embeddings using the Semantic Textual Similarity Multi EN dataset. These findings, detailed in Appendix M, further substantiate the practical utility of NSA-AE's latent embeddings.

The results that we present in the revised manuscript effectively address your concerns regarding the utility of embeddings obtained from NSA, particularly in the contexts we tested. Our intention was to demonstrate NSA’s applicability and effectiveness in specific scenarios, like semantic textual similarity and link prediction tasks. Looking forward, we recognize the potential of exploring NSA’s utility in broader domains, such as knowledge distillation and adversarial training. However, these areas represent a substantial expansion of our current scope and necessitate significant additional research. We are keen on undertaking this endeavor and plan to present our findings in future work. Our goal is to continually expand the understanding and applicability of NSA, and we value the guidance your feedback has provided in steering our research in this direction.

[1] On lipschitz embedding of finite metric spaces in Hilbert space by Jean Bourgain, Israel Journal of Mathematics. [2] The Geometry of Graphs and Some of Its Algorithmic Applications by Linial, N. and London, E. and Rabinovich, Y. , Proceedings of the 35th Annual Symposium on Foundations of Computer Science