Normalized Space Alignment: A Versatile Metric for Representation Analysis

## Abstract

Abstract We introduce a manifold analysis technique for neural network representations. Normalized Space Alignment (NSA) compares pairwise distances between two point clouds derived from the same source and having the same size, while potentially possessing differing dimensionalities. NSA can act as both an analytical tool and a differentiable loss function, providing a robust means of comparing and aligning representations across different layers and models. It satisfies the criteria necessary for both a similarity metric and a neural network loss function. We showcase NSA’s versatility by illustrating its utility as a representation space analysis metric, a structure-preserving loss function, and a robustness analysis tool. NSA is not only computationally efficient but it can also approximate the global structural discrepancy during mini-batching, facilitating its use in a wide variety of neural network training paradigms.

## 1 Introduction

Deep learning and representation learning have rapidly emerged as cornerstones of modern artificial intelligence, revolutionizing how machines interpret complex data. At the heart of this evolution is the ability of deep learning models to learn efficient representations from vast amounts of unstructured data, transforming it into a format where patterns become discernible and actionable. As these models delve deeper into learning intricate structures and relationships within data, the necessity for advanced metrics that can accurately assess and preserve the integrity of these learned representations becomes increasingly evident. The ability to preserve and align the representation structure of models would enhance the performance, interpretability and robustness  (Finn et al., ) of these models.

Despite the significant advancements achieved through representation learning in understanding complex datasets, the challenge of precisely maintaining the structural integrity of representation spaces remains. Current methodologies excel at optimizing the relative positions of embeddings (Chen et al., ; Schroff et al., ), yet they often overlook the challenge of preserving exact structural relationships to improve the performance, interpretability, and robustness of neural networks. A similarity index that is computationally efficient and differentiable would not only empower practitioners to navigate high-dimensional spaces with ease but also facilitate the seamless integration of similarity-based techniques into gradient-based optimization pipelines.

We present a distance preserving structural similarity index called “Normalized Space Alignment (NSA).” NSA measures both the global and the local discrepancy in structure between two spaces while ensuring computational efficiency. The compared representations can lie in different dimensional spaces provided there is a one to one mapping between the points. Globally, NSA measures the average discrepancy in pairwise distances; locally, it measures the average discrepancy in Local Intrinsic Dimensionality (Houle, ) of each point.

While manifold learning (Tenenbaum et al., ; Islam et al., ; Fefferman et al., ; Genovese et al., ) has become integral to deep learning, when applied to deep learning, they encounter three primary challenges (Psenka et al., ): (1) the lack of an explicit projection map between the original data and its corresponding low-dimensional representation, making adaptation to unseen data difficult; (2) the inability to scale to large datasets due to computational constraints; and (3) the extensive parameter tuning required, along with the need for a predefined understanding of the data. NSA aims to address these challenges while offering versatility in deep learning applications.

In line with previous works that introduce and theoretically establish similarity indices (Kornblith et al., ; Barannikov et al., ; Chen et al., ), we adopt a breadth-first approach in this paper. Rather than focusing on a specific application, we present NSA’s broad applicability across various use cases, establishing its viability in a wide range of scenarios. Future work can explore NSA’s impact in greater depth within specialized fields. Our contributions are summarized below:

- •
NSA is proposed as a differentiable and efficiently computable index. NSA’s quadratic computational complexity (in the number of points) is much better than some of the existing measures (e.g., cubic in the number of simplices for RTD (Barannikov et al., )). NSA is shown to be a viable loss function and its computation over mini-batches of the data is proven to be representative of the global NSA value.
- •
NSA’s viability as a similarity index is evaluated in Section 4.1 and as a loss function in Section 4.2. It can be used as a supplementary loss in autoencoders for dimensionality reduction. Results on several datasets and downstream task analyses show that NSA preserves structural characteristics and semantic relationships of the original data better compared to previous works.
- •
NSA is used to analyse perturbations that result from adversarial attacks on GNNs(Section 4.4). NSA shows a high correlation with misclassification rate across varying perturbation rates and can also provide insights on node vulnerability and the inner workings of popular defense methods. Simple tests with NSA can provide insights on par with other works that review and investigate the robustness of Neural Networks (Mujkanovic et al., ; Jin et al., ).

## 2 Related Work

Early proposed measures of Structural Similarity Indices were based on variants of “Canonical Correlation Analysis (CCA)” (Morcos et al., ; Raghu et al., ). “Centered Kernel Alignment (CKA)” (Kornblith et al., ) utilizes a Representational Similarity Matrix (RSM) with mean-centered representations and a linear kernel to measure structural similarity. But it was shown to lack sensitivity to certain representational changes (Ding et al., ) and not satisfy the triangle inequality (Williams et al., ). Barannikov et al. () proposed “Representation Topology Divergence (RTD),” to measure the dissimilarity in multi-scale topology between two point clouds of equal size with a one-to-one point correspondence. RTD has better correlation with model prediction disagreements than CKA but its high computational complexity and limited practicality for larger sample sizes constrain its wider application. Recently, Chen et al. () proposed a filter subspace based similarity measure which can compare neural network similarity by utilising the weights from the convolutional filter of CNNs. Although not strictly a feature representation based similarity measure, it is capable of evaluating neural network similarity more efficiently than CKA or CCA.

Besides RTD and CKA, multiple other similarity indices have been proposed. Alignment based measures (Ding et al., ; Williams et al., ; Li et al., ; Hamilton et al., ; Wang et al., ) aim to compare pairs of representation spaces directly. Representational Similarity Matrix based measures (Shahbazi et al., ; Kriegeskorte et al., ; Kornblith et al., ; Székely et al., ; Tang et al., ; May et al., ; Boix-Adsera et al., ; Chen et al., ) generate an RSM that describes the similarity between representations of each instance in order to avoid measuring representations directly. This helps overcome the dimensionality limitation, allowing RSM based measures to compute similarity regardless of what dimension the two spaces lie in. Neighborhood based measures (Schumacher et al., ; Hamilton et al., ) compare the nearest neighbors of instances in the representation space by looking at the consistency in the k-nearest neighbors of each instance in the representation space. Topology based measures (Khrulkov & Oseledets, ; Tsitsulin et al., ; Barannikov et al., ) are motivated by the manifold hypothesis. These measures aim to approximate the manifold of the representation space in terms of discrete topological structures such as graphs of simplicial complexes (Goodfellow et al., ). Previous works are either incapable of comparing spaces across dimensions, do not satisfy one or more of the invariance conditions required to be an effective similarity index, have high computational complexity, cannot satisfy the conditions necessary to be a pseudometric or are not differentiable.

## 3 Normalized Space Alignment

NSA comprises of two distinct but complementary components: Local NSA (LNSA) and Global NSA (GNSA). LNSA focuses on preserving the local neighborhoods of points, leveraging Local Intrinsic Dimensionality to ensure nuanced neighborhood consistency. In contrast, GNSA extends this analysis to a broader scale, aiming to maintain relative discrepancies between points across the entire representation space. Together, these components provide a multifaceted understanding of representation spaces. As a similarity index (Kornblith et al., ), NSA does not distinguish between two point clouds that belong to the same $E(n)$ symmetry group.

### 3.1 Local Normalized Space Alignment (LNSA)

LNSA focuses on the alignment of local neighborhoods of individual points within a dataset. This approach is grounded in the extensive research on Local Intrinsic Dimensionality (LID) (Bailey et al., ; Houle, ; Tsitsulin et al., ; Camastra & Staiano, ). Prior to defining LNSA, we provide a foundational overview of LID, setting the stage for a comprehensive understanding of how LNSA leverages these principles to achieve precise alignment in local representation spaces.

#### 3.1.1 Local Intrinsic Dimensionality

Given a point cloud $X=\set{\vec{x}_{1},\ldots,\vec{x}_{N}}\subseteq\mathbb{R}^{n}$, we say $X$ has intrinsic dimensionality $m$ if all points of $X$ lie in an $m$-dimensional manifold (Fukunaga, ). LID is intuitively defined to find the lowest dimensional manifold containing a local neighbor of a point of importance. Houle () formally defined local intrinsic dimensionality as follows:

###### Definition 3.1 .

Given a point cloud $X\subseteq\mathbb{R}^{n}$ and a point of interest $\vec{x}\in X$. Let $R_{\vec{x}}$ be the random variable denoting distances of all points from $\vec{x}$ and $F_{\vec{x}}(\cdot)$ be the cumulative distribution function of $R_{\vec{x}}$. Let $F_{\vec{x}}$ be continuous and differentiable, then the LID of $\vec{x}$ is

$$ $\mathsf{IntrDim}_{X}(\vec{x})=\lim_{\begin{subarray}{c}\varepsilon\to 0\\ r\to 0\end{subarray}}\frac{F_{\vec{x}}((1+\varepsilon)r)-F_{\vec{x}}(r)}{ \varepsilon F_{\vec{x}}(r)}.$ (1) $$

In practice, we estimate the LID of a point using the distances to its $k$ nearest neighbours. Amsaleg et al. () defined the Maximum Likelihood Estimator for LID and defined $\mathsf{lid}$ of $\vec{x}_{i}\in X$ as:

$$ $\mathsf{lid}(i,X)=-\left(\frac{1}{k}\sum_{\begin{subarray}{c}i_{j}:\\ (i_{1},\ldots,i_{k})\leftarrow{k}NN_{X}(i)\end{subarray}}\log\frac{d(\vec{x}_{ i},\vec{x}_{i_{j}})}{d(\vec{x}_{i},\vec{x}_{i_{k}})}\right)^{-1},$ (2) $$

where $(i_{1},\ldots,i_{k})\leftarrow{k}NN_{X}(i)$ denotes that the $k$ nearest neighbours of $\vec{x}_{i}$ in $X$ are $(\vec{x}_{i_{1}},\ldots,\vec{x}_{i_{k}})$. $d(\cdot,\cdot)$ is a differentiable distance measure between two vectors.

When aligning two points in different spaces to ensure they have similar local structures, the objective extends beyond merely matching their local dimensions. It also involves ensuring that both points share the same neighbors. To achieve this we have to identify the same $k$ points near some point $i$ in space $X$ and $Y$. Hence we define the notion of approximate dimensionality ($\mathsf{AD}$) of a point $\vec{x}_{i}$ with respect to any $k$ tuple $(\vec{x}_{i_{1}},\ldots,\vec{x}_{i_{k}})$ as:

$$ $\mathsf{AD}_{X}({i,(i_{1},\ldots,i_{k})})=-\left(\frac{1}{k}\sum_{j=1}^{k}\log \frac{d(\vec{x}_{i},\vec{x}_{i_{j}})}{d(\vec{x}_{i},\vec{x}_{i_{k}})}\right)^{ -1}.$ (3) $$

The measure $\mathsf{lid}$ is then defined as:
$\mathsf{lid}(i,X)=\mathsf{AD}_{X}({i,{k}NN_{X}(i)}).$

Levina & Bickel () defined the intrinsic dimensionality of a space as the average LID of all its points. This was later corrected by MacKay & Ghahramani () to be the reciprocal of the average reciprocal of LID of each point. Formally defined as:

$$ $\mathsf{IntrDim}(X)=\left(\frac{1}{|X|}\sum_{\vec{x}_{i}\in X}\mathsf{lid}(i,X )^{-1}\right)^{-1}.$ (4) $$

MacKay & Ghahramani () showed that performing aggregation operations on the reciprocals of the LIDs of each point yields much better approximations.

###### Definition 3.1 .

#### 3.1.2 Definition

To define Local NSA ($\mathsf{LNSA}$) using LID, we start with the premise that closely structured point clouds should have similar dimensional manifolds in their local neighborhoods. Formally, for two point clouds $X$ and $Y$, and considering the $k$ nearest neighbours of the $i^{th}$ point in $X$ indexed as $i_{1},\ldots,i_{k}$, we examine the manifold dimensions in $Y$ that contain $i,i_{1},\ldots,i_{k}$. This leads to the concept of "Symmetric $\mathsf{lid}$" defined as:

$$ $\overline{\mathsf{lid}}_{X}(i,Y)=\mathsf{AD}_{Y}({i,{k}NN_{X}(i)}).$ (5) $$

We notice that the mean discrepancy of the reciprocals of the LID is strongly correlated with the local structure being preserved, this is similar to MacKay & Ghahramani () where they show that taking a mean of reciprocals of the LID is correlated to the intrinsic dimensionality of the whole space. Hence we define $\mathsf{LNSA}$ of $X$ with respect to $Y$ as:

$$ $\mathsf{LNSA}_{Y}(X)=N^{-1}\sum_{1\leq i\leq N}\left(\mathsf{lid}(i,Y)^{-1}- \overline{\mathsf{lid}}_{Y}(i,X)^{-1}\right)^{2}.$ (6) $$

Further, we can symmetricise this term to get the premetric $\mathsf{LNSA}^{\mathsf{metric}}$ as:

$$ $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}_{X}(Y)+\mathsf{LNSA}_{Y}(X).$ (7) $$

When using $\mathsf{NSA}$-based loss functions, we use $\mathsf{LNSA}$ whereas when using $\mathsf{NSA}$-based similarity indices, we use $\mathsf{LNSA}^{\mathsf{metric}}$.

#### 3.1.3 Analytical Properties

We show that $\mathsf{LNSA}^{\mathsf{metric}}$ is a premetric by proving the necessary properties in Appendix E: $\bullet$ $\mathsf{LNSA}^{\mathsf{metric}}(X,X)=0$, $\bullet$ Symmetry, $\bullet$ Non-negativity.

$\mathsf{LNSA}$ is shown to satisfy the necessary conditions of Invariance to Isotropic Scaling, Invariance to Orthogonal Transformation, and (Not) Invariance to Invertible Linear Transformation as proposed by Kornblith et al. () for a similarity index. These condition are proved in Appendix F and ensure that the similarity index is unaffected by rotation or scaling of the representation space.

### 3.2 Global Normalized Space Alignment (GNSA)

GlobalNSA is a similarity index based on Representational Similarity Matrices (RSMs) (Klabunde et al., ). Given a representation $\mathbf{R}:N\times D$, all RSM based measures generate a matrix of instance wise similarities $D\in\mathbf{R}^{N\times N}$ where $D_{i,j}:=d(R_{i},R_{j})$. Given two representations $\mathbf{R}$ and $\mathbf{R^{\prime}}$, two corresponding RSMs are generated. GlobalNSA is calculated by subtracting the pairwise similarities between the two spaces and averaging these discrepancies to produce a single value that reflects the global difference between the two representation spaces. We present the motivation behind GlobalNSA and how RSMs capture global discrepancy in Appendix D.3.

#### 3.2.1 Definition

The $\mathsf{GNSA}$ between two point clouds $X=\{\vec{x_{1}},\ldots,\vec{x_{N}}\}$ and $Y=\{\vec{y_{1}},\ldots,\vec{y_{N}}\}$ is computed as:

$$ $\mathsf{GNSA}(X,Y,i)=\frac{1}{N}\sum_{1\leq j\leq N}\left|\frac{d(\vec{x_{i}}, \vec{x_{j}})}{\max\limits_{\vec{x}\in X}{d(\vec{x},\vec{0})}}-\frac{d(\vec{y_{ i}},\vec{y_{j}})}{\max\limits_{\vec{y}\in Y}{d(\vec{y},\vec{0})}}\right|.$ (8) $$

$$ $\mathsf{GNSA}(X,Y)=\frac{1}{N}\sum_{1\leq i\leq N}\mathsf{GNSA}(X,Y,i).$ (9) $$

Throughout the paper, we use $d(\cdot,\cdot)$ to denote the euclidean distance (unless specified otherwise).

#### 3.2.2 Analytical Properties

We show that $\mathsf{GNSA}$ is a pseudometric by proving the necessary properties in the Appendix B: $\bullet$ $\mathsf{GNSA}(X,X)=0$, $\bullet$ Symmetry, $\bullet$ Non-negativity, $\bullet$ Triangle Inequality.
$\mathsf{GNSA}$ is proven to be a similarity index by satisfying the three established criteria in Appendix C.

### 3.3 Putting it all together

We utilize $\mathsf{GNSA}$ for our empirical analysis as it performs well when comparing entire representation spaces. When using NSA as a structure-preserving loss function, we calculate the final NSA Loss through a weighted sum of local and global NSA, allowing us to adjust the emphasis between local and global perspectives. One could prioritize local neighborhood preservation, such as in classifiers with tightly clustered data, or emphasize global structure, as needed in link prediction models for densely interconnected graphs. Hence, NSA is defined as:

$$ $\mathsf{NSA}=l*\mathsf{LNSA}+g*\mathsf{GNSA}.$ (10) $$

Only GNSA is used during empirical analysis while both GNSA and LNSA are used during dimensionality reduction. We present ablation studies on how the two components affect performance, quantifying the difference and visualizing it in Appendix Q.

#### 3.3.1 Complexity Analysis

$\mathsf{LNSA}$’s computational complexity is $O(N^{2}D+kND)$ (^2^22The time complexity of computing the $k$-nearest neighbours of each point is $O(N^{2}D+N^{2}\log{k})$ since it takes $O(N^{2}D)$ time to find all pairwise distances and finding $k$ minimum elements of $N$ lists of size $N$ can be done in $O(N^{2}\log{k})$ using min-heaps of size $k$. Since $D>>\log{k}$ in most cases, we write the total time complexity as $O(N^{2}D)$.) and $\mathsf{GNSA}$’s complexity is $O(N^{2}D)$ where $N$ is the number of data points, $k$ is the number of nearest neighbours considered in $\mathsf{LNSA}$ and $D$ is $\max(D(R),D(R^{\prime}))$ with $R$ and $R^{\prime}$ being the two representation spaces and $D(\cdot)$ the dimensionality of the space. Hence, overall NSA has complexity of $O(N^{2}D+kND)$. Empirically, we find that computing NSA on a GPU scales quadratically up to a very high batch size (Appendix I). CKA has similar complexity to NSA while RTD has a complexity of $O(N^{2}D+R^{3})$, where $R$ is the number of simplices (in practice $R>>N$). Running times of NSA-AE are given in Appendix L. NSA-AE is several times faster than RTD-AE and it can run on much larger batch sizes.

## 4 Applications

NSA serves a dual purpose, acting not only as a similarity index to compare structural discrepancies in representation spaces, but also as a structure preserving loss function. This enables a wide range of applications where NSA could potentially be useful. We first validate NSA’s viability as a similarity index using the tests proposed by (Ding et al., ). We then present experiments in two broad domains; dimensionality reduction and adversarial attack analysis. Additional experiments on cross-layer analysis (Appendix U and Appendix J), convergence prediction (Appendix V) and manifold approximation (Appendix T) are presented in the appendix.

### 4.1 Analyzing Representation Spaces

We evaluate the performance of our structural similarity index using statistical tests proposed by Kornblith et al. () and further refined by Ding et al. (). These tests are based on two fundamental intuitions: (1) a good structural similarity index should show high similarity between architecturally identical neural networks with different weight initializations, and (2) it should be sensitive to the removal of high variance principal components from the data. These initial tests are essential for validating the effectiveness of a similarity index.

#### 4.1.1 Specificity Test

A structural similarity index is expected to assign small distances between corresponding layers of neural networks that differ only in their initialization seed. To test this, we trained two ResNet-18 models on the CIFAR-10 dataset, each with a different weight initialization. After training, we extracted intermediate embeddings from each layer during an evaluation pass over the entire dataset. Using a subset of data points(^3^33We set the subset size to 4000 for NSA and use the recommended subset size of 400 over 10 trials for RTD), we computed the similarity between these embeddings using NSA, CKA, and RTD.

Figure: Figure 1: Specificity (Left) and Sensitivity (Right) Tests. Left (from top to bottom): CKA’, RTD and NSA pairwise distances between each layer of two differently initialized networks. Right: Dissimilarities between a layer’s representation and its low-rank approximation. Principal components are deleted in order of least variance.
Refer to caption: x1.png

Our results indicate that NSA exhibits the smallest drop in similarity between corresponding layers of networks with different initializations. Both RTD and CKA show a significant decrease in similarity, particularly in the later layers. NSA, on the other hand, maintains a strong layer-wise pattern, closely resembling the ideal expected pattern observed when comparing a model against itself. Ideally, the minimum similarity value should be observed where the layers match. RTD fails to achieve this pattern in the last two layers, while CKA fails in layer five.

#### 4.1.2 Sensitivity Test

An effective structural similarity index should be robust to the removal of low variance principal components and sensitive to the removal of high variance principal components. Previous studies have shown that CKA is insensitive to the removal of principal components until the most significant ones are removed. We conducted a sensitivity test with our ResNet-18 models trained on CIFAR-10, following a similar experimental setup to that used by Ding et al. ().

For each index, we set the dissimilarity score to be above the detectable threshold if it exceeds the dissimilarity score between representations from different random initializations. The results on the first and last layer, shown in Figure 1, demonstrate that NSA is more sensitive to the removal of high variance principal components compared to RTD and CKA, with an average detection threshold of 90.25%, compared to 96% for RTD and 99% for CKA.

### 4.2 NSA as a Loss Function

The viability of NSA as a loss function is established by demonstrating its non-negativity, nullity and continuity, and by developing a differentiation scheme. Proofs for all four properties are presented in Appendix D and G. We also demonstrate that the expectation of NSA over a minibatch is equal to the NSA of the whole dataset, cementing its feasibility as a loss function in Appendix H.

#### 4.2.1 Convergence of Global NSA in mini batching

Neural networks are often trained on mini batches, which means that at any step a global structure preserving loss will only have access to a subset of the data. It is vital that a structure preserving loss function like $\mathsf{GNSA}$ converge to its global measure when used as a loss function. Similarity indices usually have a high computation cost, therefore most similarity indices work with a sample of the data and show that the value computed on the sample is a good approximation of the global value. Additionally, for a loss function, the expectation is that the mean of the losses from the mini-batches converges to the true loss over the entire dataset. This principle underlies stochastic gradient descent (SGD) and its variants, which are foundational to training neural networks. SGD assumes that the expected value of the gradients calculated on the mini-batches converges to the true gradient over the entire dataset, and a similar concept applies to the expectation of the loss. In Lemma H.1 we prove theoretically that in expectation, $\mathsf{GNSA}$ over a minibatch is equal to $\mathsf{GNSA}$ of the whole dataset.

Figure 2 shows that $\mathsf{GNSA}$ over a number of trials approximates the $\mathsf{GNSA}$ of the entire dataset while RTD fails to do so. Here, we use the output embeddings of two GCN models with the exact same architecture but different initializations trained on node classification on the Cora dataset. The output embedding is the output of the last layer before softmax is applied to get the classification vectors. We compare the convergences with a batch size of 200 and 500.

While LNSA does not exhibit formal convergence under mini-batching, it intuitively demonstrates favorable behavior in such settings. LNSA’s design, which relies on nearest-neighbor computations to assess structural preservation within local neighborhoods, ensures that these neighborhoods are typically preserved in expectation. This is because the sampling process in mini-batching generally retains a sufficient number of neighboring points in each batch. By appropriately adjusting the number of nearest neighbors considered in each mini-batch, LNSA is able to approximate the structural consistency of local representations, ensuring that the loss function remains representative of the global structure on a local scale.

Figure: (a)
Refer to caption: extracted/5978749/figures/subset_metrics/subset_NSA_2.png

#### 4.2.2 Defining NSA-AE: Autoencoder using NSA

To evaluate the efficacy of NSA as a structural discrepancy minimization metric, we take inspiration from TopoAE Moor et al. () and RTD-AE Trofimov et al. (), and use NSA as loss function in autoencoders for dimensionality reduction. A normal autoencoder minimizes the MSE loss between the original $X$ and reconstructed embedding $\hat{X}$. We add NSA-Loss as an additional loss term that aims to minimize the discrepancy in representation structure between the original embedding space $X$ and the latent embedding space $Z$. The autoencoder is built as a compression autoencoder where the encoder attempts to reduce the original data to a latent dimension and the decoder attempts to reconstruct the original embedding. Since NSA can be used in autoencoders with mini-batch training, NSA-AE runs almost as fast as a regular autoencoder. We compare the performance of NSA-AE against PCA, UMAP, a regular autoencoder, TopoAE and RTD-AE on four real world datasets.

The performance of NSA-AE is evaluated on the structural and topological similarity between the input data $X$ and the latent data $Z$. We use the following evaluation metrics: (1) linear correlation of pairwise distances, (2) triplet distance ranking accuracy (Wang et al., ), (3) RTD (Barannikov et al., ), (4) GNSA, (5) LNSA and (6) kNN-Consistency. As seen in Table 1, NSA-AE has better structural similarity between the original data and the latent data compared to the other models. NSA-AE achieves MSE and running times similar to a normal autoencoder while previous works are several times slower, as presented in Appendix L. We also present the hyperparameters used along with dataset statistics in Appendices M and P.

**Table 1: Autoencoder results. L.C = Linear Correlation, T.A. = Triplet distance ranking accuracy, RTD = Representation Topology Divergence, GNSA = GlobalNSA, LNSA@100 = LocalNSA on 100 nearest neighbors, kNN C @ 100 = 100 nearest neighbors consistency. NSA-AE outperforms or almost matches all other approaches on all the evaluation metrics. RTD-AE, which explicitly minimizes on RTD occasionally has lower LID and kNN-C.**
|  |  | Quality measure |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset | Method | L. C. $\uparrow$ | T. A. $\uparrow$ | RTD $\downarrow$ | GNSA $\downarrow$ | LNSA @ 100 $\downarrow$ | kNN-C @ 100 $\uparrow$ |
| MNIST | PCA | 0.910 | $0.871\pm 0.008$ | $6.69\pm 0.21$ | $0.0817\pm 0.0025$ | $0.0267\pm 0.00$ | 0.584 |
|  | UMAP | 0.424 | $0.620\pm 0.013$ | $18.06\pm 0.48$ | $0.2305\pm 0.0031$ | $1.0353\pm 0.02$ | 0.353 |
|  | AE | 0.801 | $0.778\pm 0.007$ | $7.47\pm 0.20$ | $0.0571\pm 0.0011$ | $0.0529\pm 0.00$ | 0.619 |
|  | TopoAE | 0.765 | $0.771\pm 0.010$ | $6.16\pm 0.23$ | $0.0477\pm 0.0011$ | $0.0335\pm 0.00$ | 0.631 |
|  | RTD-AE | 0.837 | $0.811\pm 0.004$ | $4.26\pm 0.14$ | $0.1694\pm 0.0024$ | $0.0133\pm 0.00$ | $\mathbf{0.709}$ |
|  | NSA-AE | $\mathbf{0.947}$ | $\mathbf{0.886\pm 0.005}$ | $\mathbf{4.29\pm 0.11}$ | $\mathbf{0.0222\pm 0.00}$ | $\mathbf{0.0123\pm 0.00}$ | 0.634 |
| F-MNIST | PCA | 0.978 | $\mathbf{0.951\pm 0.006}$ | $5.91\pm 0.12$ | $0.1722\pm 0.0038$ | $0.0566\pm 0.00$ | 0.513 |
|  | UMAP | 0.592 | $0.734\pm 0.012$ | $12.16\pm 0.39$ | $0.1420\pm 0.0011$ | $0.6738\pm 0.01$ | 0.365 |
|  | AE | 0.872 | $0.850\pm 0.008$ | $5.60\pm 0.21$ | $0.0527\pm 0.0028$ | $0.0515\pm 0.00$ | 0.614 |
|  | TopoAE | 0.875 | $0.854\pm 0.009$ | $4.27\pm 0.15$ | $0.111\pm 0.0027$ | $0.0291\pm 0.00$ | 0.601 |
|  | RTD-AE | 0.949 | $0.902\pm 0.004$ | $3.05\pm 0.12$ | $0.0349\pm 0.0015$ | $\mathbf{0.0104\pm 0.00}$ | $\mathbf{0.661}$ |
|  | NSA-AE | $\mathbf{0.985}$ | $0.939\pm 0.003$ | $\mathbf{2.78\pm 0.09}$ | $\mathbf{0.0114\pm 0.00}$ | $0.0133\pm 0.00$ | 0.633 |
| CIFAR-10 | PCA | 0.972 | $0.926\pm 0.009$ | $4.99\pm 0.16$ | $0.1809\pm 0.0046$ | $0.0175\pm 0.00$ | 0.432 |
|  | UMAP | 0.756 | $0.786\pm 0.010$ | $12.21\pm 0.22$ | $0.1316\pm 0.0026$ | $0.2880\pm 0.00$ | 0.119 |
|  | AE | 0.834 | $0.836\pm 0.006$ | $4.07\pm 0.28$ | $0.0616\pm 0.0019$ | $0.0224\pm 0.00$ | 0.349 |
|  | TopoAE | 0.889 | $0.854\pm 0.007$ | $3.89\pm 0.11$ | $0.0625\pm 0.0014$ | $0.0277\pm 0.00$ | 0.360 |
|  | RTD-AE | 0.971 | $0.922\pm 0.002$ | $\mathbf{2.95\pm 0.08}$ | $0.0113\pm 0.0003$ | $0.0124\pm 0.00$ | 0.416 |
|  | NSA-AE | $\mathbf{0.985}$ | $\mathbf{0.941\pm 0.003}$ | $3.04\pm 0.16$ | $\mathbf{0.0086\pm 0.00}$ | $\mathbf{0.0103\pm 0.00}$ | $\mathbf{0.437}$ |
| COIL-20 | PCA | 0.966 | $\mathbf{0.932\pm 0.005}$ | $6.49\pm 0.23$ | $0.2204\pm 0.0$ | $0.2000\pm 0.00$ | 0.801 |
|  | UMAP | 0.274 | $0.567\pm 0.016$ | $15.50\pm 0.67$ | $0.1104\pm 0.0$ | $3.3023\pm 0.00$ | 0.569 |
|  | AE | 0.850 | $0.836\pm 0.008$ | $9.57\pm 0.27$ | $0.0758\pm 0.0$ | $0.5678\pm 0.00$ | 0.683 |
|  | TopoAE | 0.804 | $0.805\pm 0.011$ | $7.33\pm 0.21$ | $0.0676\pm 0.0$ | $0.1044\pm 0.00$ | 0.654 |
|  | RTD-AE | 0.908 | $0.871\pm 0.005$ | $5.89\pm 0.10$ | $0.0523\pm 0.0$ | $0.0496\pm 0.00$ | 0.761 |
|  | NSA-AE | $\mathbf{0.976}$ | $0.919\pm 0.005$ | $\mathbf{3.55\pm 0.18}$ | $\mathbf{0.0139\pm 0.00}$ | $\mathbf{0.0085\pm 0.00}$ | $\mathbf{0.809}$ |

### 4.3 Downstream Task Analysis on Link Prediction

We demonstrate that NSA-AE effectively preserves the structural integrity between the original data and the latent space. However, it is imperative to note that such preservation does not inherently ensure the utility of the resultant latent embeddings. Metrics like NSA, which focus on exact structure preservation, excel in scenarios where the preservation of semantic relationships between data points holds paramount importance.

Link prediction is an ideal task to demonstrate NSA’s structure preserving ability. Successful link prediction mandates a global consistency within the embedding space, necessitating that nodes with likely connections are proximate while dissimilar nodes are distant. Any form of clustering or localized alterations to the representation structure can disrupt node interrelationships. In our study, we employ a Graph Convolutional Network (GCN) to train link prediction models across four distinct graph datasets. The original GCN embedding space encompasses 256 dimensions. This space is subsequently processed through NSA-AE, resulting in a reduced-dimensional representation. The latent embeddings are then tested on their ability to predict the existence of links between nodes. Notably, the latent embeddings produced by NSA-AE exhibit superior performance when compared to both a conventional autoencoder and RTD-AE as shown in Table 2. Additionally, we demonstrate that NSA can work at scale by working with the Word2Vec dataset. We present results showcasing the effectiveness of semantic textual similarity matching using Word2Vec embeddings in the Appendix K.

**Table 2: Downstream task analysis with Link Prediction. The output embeddings from a GCN trained on link prediction are utilized. Latent embeddings are obtained at various dimensions and ROC-AUC scores are calculated on the latent embeddings obtained after reducing the dimensionality of the original output embeddings. NSA-AE outperforms both a regular autoencoder and RTD-AE across almost all datasets and all latent dimensions.**
|  |  | Dataset |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Method | Latent Dim | Amazon Comp | Cora | Citeseer | Pubmed |
|  | 128 | 50.478 | 50.0 | 50.0 | 51.17 |
| AE | 64 | 50.56 | 50.0 | 50.0 | 50.03 |
|  | 32 | 59.63 | 49.84 | 49.80 | 52.78 |
|  | 128 | 94.63 | 86.52 | 90.54 | 91.80 |
| RTD-AE | 64 | 91.63 | 82.38 | 89.23 | 97.26 |
|  | 32 | 88.34 | 83.13 | 57.18 | 87.05 |
|  | 128 | 95.75 | 97.83 | 97.91 | 97.37 |
| NSA-AE | 64 | 94.60 | 97.89 | 98.38 | 96.97 |
|  | 32 | 95.76 | 97.68 | 96.11 | 97.66 |

### 4.4 Analyzing Adversarial Attacks

Figure: (a)
Refer to caption: x7.png

Figure: (a)
Refer to caption: x9.png

Adversarial attacks have become a critical area of concern across various domains in machine learning, from computer vision to natural language processing and graph-based data. These attacks exploit vulnerabilities in model architectures, to introduce subtle perturbations in the model’s representation space to drastically alter its predictions. A structural discrepancy analysis term like NSA can help analyze and identify vulnerabilities in these networks. By comparing the underlying structure of data representations before and after an attack, NSA allows us to quantitatively assess how adversarial perturbations impact the model’s predictions, regardless of the architecture being employed. For our study, we applied NSA in the context of GNNs, but the method can be equally effective in analyzing the robustness of other architectures, such as CNNs or transformers, under adversarial conditions.

In this experimental study, we subjected five distinct GNN architectures to both poisoning and evasion adversarial attacks using projected gradient descent Metattack (Xu et al., ; Mujkanovic et al., ). We use a GCN along with four robust GNN variants; SVD-GCN (Entezari et al., ), GNNGuard (Zhang & Zitnik, ), GRAND (Chamberlain et al., ) and ProGNN (Jin et al., ). To assess the vulnerability of these architectures, we manipulated the initial adjacency matrices by introducing perturbations ranging from 5% to 25%. The objective was to gauge the impact of these perturbations on the misclassification rates of the GNN models and to see if NSA shows a strong correlation to the misclassification rates over different perturbation rates.

NSA was computed at each stage by comparing the clean graph’s output representations with those from the perturbed graph. Our experiments revealed that NSA’s variation over different perturbation rates mirrors the misclassification trends of various GNN architectures during poisoning attacks and NSA’s ranking of architecture vulnerability is in line with previous works (Jin et al., ; Mujkanovic et al., ).

However, in evasion attacks, SVD-GCN stood out with its NSA scores significantly deviating from its misclassification rates. To further explore such anomalies, NSA can also be used to measure node-level discrepancies. Figure 4 examines the boundary nodes of different GNN architectures. Post-attack, SVD-GCN showed a substantial increase in boundary nodes—defined by low classification confidence and proximity to the decision boundary—accompanied by a general decline in classification confidence. This surge, coupled with SVD-GCN’s highest pointwise NSA values among all tested architectures, potentially accounts for its high NSA scores and heightened vulnerability despite appearing to be robust when evaluated only using accuracy based metrics. It is also this vulnerability in structure, that is exploited by Mujkanovic et al. () with adaptive adversarial attacks, to cause a catastrophic failure in SVD-GCN. This detailed analysis underpins our assertion that NSA, through simple empirical analyses, can unveil concealed weaknesses in defense methods not immediately apparent from conventional metrics.

## 5 Conclusion and Limitations

We have demonstrated that the proposed measure of NSA is simple, efficient, and useful across many aspects of analysis and synthesis of representation spaces: robustness across initializations, convergence across epochs, autoencoders, adversarial attacks, and transfer learning. Its computational efficiency and the ability to converge to its global value in mini batches allow it to be useful in many applications and generalizations where scalability is desired.

While NSA demonstrates substantial benefits in various applications, certain limitations must be acknowledged to provide a comprehensive understanding of its scope and potential areas for future improvements. The choice of Euclidean distance as the primary metric for NSA may not be optimal in high-dimensional spaces due to the curse of dimensionality (Bellman, ). Despite this, Euclidean distance remains prevalent in various domains, including contrastive (Chen et al., ) or triplet losses (Schroff et al., ), style transfer (Johnson et al., ) and similarity indices. NSA’s versatility across different applications is a significant strength, yet it is not a universal solution suitable for all scenarios without modification. Effective deployment of NSA often requires careful tuning of parameters and integration with other loss functions to suit specific tasks. Finally, NSA is primarily a structural similarity metric, which means that it focuses on preserving the geometrical configuration of data points rather than their functional equivalency. This focus can lead to scenarios where NSA indicates significant differences between datasets that are functionally similar but structurally distinct.

## Appendix A Appendix

## Appendix B Proofs for GNSA as a pseudometric

###### Lemma B.1 (Identity) .

Let $X$ be a point cloud over some space, then $\mathsf{GNSA}(X,X)=0$.

###### Proof.

Let $X=\{x_{1},\ldots,x_{N}\}$. Let $\max_{x\in X}(d(x,0))=D$. Then

$$ $\mathsf{GNSA}(X,X)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\frac{d(x_{i},x_ {j})}{D}-\frac{d(x_{i},x_{j})}{D}\right|.$ $$

Simplifying, we get

$$ $\mathsf{GNSA}(X,X)=\frac{1}{N^{2}D}\sum_{1\leq i,j\leq N}\left|d(x_{i},x_{j})- d(x_{i},x_{j})\right|=0.$ $$

∎

###### Lemma B.2 (Symmetry) .

Let $X,Y$ be two point clouds of the same size, then $\mathsf{GNSA}(X,Y)=\mathsf{GNSA}(Y,X)$.

###### Proof.

Let $X=\{x_{1},\ldots,x_{N}\}$ and $Y=\{y_{1},\ldots,y_{N}\}$. Let $\max_{x\in X}(d(x,0))=D_{X}$ and $\max_{y\in Y}(d(y,0))=D_{Y}$. Then

$$ $\mathsf{GNSA}(X,Y)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\frac{d(x_{i},x_ {j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right|.$ $$

Since $|a-b|=|b-a|$,

$$ $\mathsf{GNSA}(X,Y)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\frac{d(y_{i},y_ {j})}{D_{Y}}-\frac{d(x_{i},x_{j})}{D_{X}}\right|.$ $$

Hence, $\mathsf{GNSA}(X,Y)=\mathsf{GNSA}(Y,X)$.
∎

###### Lemma B.3 (Non-negativity) .

Let $X,Y$ be two point clouds of the same size, then $\mathsf{GNSA}(X,Y)\geq 0$.

###### Proof.

Let $X=\{x_{1},\ldots,x_{N}\}$ and $Y=\{y_{1},\ldots,y_{N}\}$. Let $\max_{x\in X}(d(x,0))=D_{X}$ and $\max_{y\in Y}(d(y,0))=D_{Y}$. Then

$$ $\mathsf{GNSA}(X,Y)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\frac{d(x_{i},x_ {j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right|.$ $$

Since, for all $i,j$,

$$ $\left|\frac{d(x_{i},x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right|\geq 0,$ $$

we get $\mathsf{GNSA}(X,Y)\geq 0$.
∎

###### Lemma B.4 (Triangle inequality) .

Let $X,Y$ and $Z$ be three point clouds of the same size, then $\mathsf{GNSA}(X,Z)\leq\mathsf{GNSA}(X,Y)+\mathsf{GNSA}(Y,Z)$.

###### Proof.

Let $X=\{x_{1},\ldots,x_{N}\}$, $Y=\{y_{1},\ldots,y_{N}\}$ and $Z=\{z_{1},\ldots,z_{N}\}$. Let $\max_{x\in X}(d(x,0))=D_{X}$, $\max_{y\in Y}(d(y,0))=D_{Y}$ and $\max_{z\in Z}(d(z,0))=D_{Z}$. Then

$$ $\mathsf{GNSA}(X,Z)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\frac{d(x_{i},x_ {j})}{D_{X}}-\frac{d(z_{i},z_{j})}{D_{Z}}\right|.$ $$

For each $i,j$, add and subtract $\frac{d(y_{i},y_{j})}{D_{Y}}$, then

$$ $\mathsf{GNSA}(X,Z)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\left(\frac{d(x_ {i},x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right)+\left(\frac{d(y_{i},y_{ j})}{D_{Y}}-\frac{d(z_{i},z_{j})}{D_{Z}}\right)\right|.$ $$

Since $|a+b|\leq|a|+|b|$,

$$ $\mathsf{GNSA}(X,Z)\leq\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left(\left|\frac{d (x_{i},x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right|+\left|\frac{d(y_{i}, y_{j})}{D_{Y}}-\frac{d(z_{i},z_{j})}{D_{Z}}\right|\right).$ $$

Hence,

$$ $\mathsf{GNSA}(X,Z)\leq\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\frac{d(x_{i} ,x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right|+\frac{1}{N^{2}}\sum_{1\leq i ,j\leq N}\left|\frac{d(y_{i},y_{j})}{D_{Y}}-\frac{d(z_{i},z_{j})}{D_{Z}}\right|,$ $$

or $\mathsf{GNSA}(X,Z)\leq\mathsf{GNSA}(X,Y)+\mathsf{GNSA}(Y,Z)$.
∎

From Lemma B.1, Lemma B.2, Lemma B.3 and Lemma B.4, we see that $\mathsf{GNSA}$ is a psuedometric over the space of point clouds.

###### Lemma B.1 (Identity) .

###### Proof.

###### Lemma B.2 (Symmetry) .

###### Proof.

###### Lemma B.3 (Non-negativity) .

###### Proof.

###### Lemma B.4 (Triangle inequality) .

###### Proof.

## Appendix C Proofs for GNSA as a similarity metric

### C.1 Invariance to Isotropic Scaling

###### Lemma C.1 (Invariance to Isotropic scaling in the first coordinate) .

Let $X$ and $Y$ be two point clouds of the same size. Let $c\in\mathbf{R}$ and $c\neq 0$, $X_{c}$ be the point cloud with each point in $X$ scaled by a factor of $c$, then $\mathsf{GNSA}(X,Y)=\mathsf{GNSA}(X_{c},Y)$.

###### Proof.

Let $X=\{x_{1},\ldots,x_{N}\}$ and $Y=\{y_{1},\ldots,y_{N}\}$, then $X_{c}=\{cx_{1},\ldots,cx_{N}\}$. Let $\max_{x\in X}(d(x,0))=D_{X}$, $\max_{y\in Y}(d(y,0))=D_{Y}$ and $\max_{x\in X_{c}}(d(x,0))=D_{X_{c}}$. Since, each point in $X_{c}$ is the $c$ times each point in $X$. Then, we can write $D_{X_{c}}=\max_{x\in X}(d(cx,0))$. Since, for any two points, $x_{1}$ and $x_{2}$, $d(cx_{1},cx_{2})=|c|d(x_{1},x_{2})$, then $D_{X_{c}}=|c|\max_{x\in X}(d(x,0))$. Hence, $D_{x_{c}}=|c|D_{X}$.
From the definition of $\mathsf{GNSA}$,

$$ $\mathsf{GNSA}(X_{c},Y)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\left(\frac{ d(cx_{i},cx_{j})}{D_{X_{c}}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right)\right|.$ $$

Again, using $d(cx_{i},cx_{j})=|c|d(x_{i},x_{j})$ and $D_{X_{c}}=|c|D_{X}$,

$$ $\mathsf{GNSA}(X_{c},Y)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\left(\frac{ |c|d(x_{i},x_{j})}{|c|D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right)\right|.$ $$

Simplifying,

$$ $\mathsf{GNSA}(X_{c},Y)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\left(\frac{ d(x_{i},x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right)\right|.$ $$

Hence, $\mathsf{GNSA}(X_{c},Y)=\mathsf{GNSA}(X,Y)$.
∎

By Lemma B.2, we can see that this gives us invariance to isotropic scaling in the second coordinate as well.

###### Lemma C.2 (Invariance to Isotropic scaling in the second coordinate) .

Let $X$ and $Y$ be two point clouds of the same size. Let $c\in\mathbf{R}$ and $c\neq 0$, $Y_{c}$ be the point cloud with each point in $Y$ scaled by a factor of $c$, then $\mathsf{GNSA}(X,Y)=\mathsf{GNSA}(X,Y_{c})$.

Combining Lemma C.1 and Lemma C.2, we get the required lemma.

###### Lemma C.3 (Invariance to Isotropic scaling) .

Let $X$ and $Y$ be two point clouds of the same size. Let $c_{1},c_{2}\in\mathbf{R}$, $c_{1}\neq 0$ and $c_{2}\neq 0$, $X_{c_{1}}$ be the point cloud with each point in $X$ scaled by a factor of $c_{1}$ and $Y_{c_{2}}$ be the point cloud with each point in $Y$ scaled by a factor of $c_{2}$, then $\mathsf{GNSA}(X,Y)=\mathsf{GNSA}(X_{c_{1}},Y_{c_{2}})$.

###### Lemma C.1 (Invariance to Isotropic scaling in the first coordinate) .

###### Proof.

###### Lemma C.2 (Invariance to Isotropic scaling in the second coordinate) .

###### Lemma C.3 (Invariance to Isotropic scaling) .

### C.2 Invariance to Orthogonal transformation

###### Lemma C.4 (Invariance to Orthogonal transformation in the first coordinate) .

Let $X$ and $Y$ be two point clouds of the same size. Let $U$ be an orthogonal transformation on the point space of $X$, $X_{U}$ be the point cloud with each point in $X$ transformed using $U$, then $\mathsf{GNSA}(X,Y)=\mathsf{GNSA}(X_{U},Y)$.

###### Proof.

Let $X=\{x_{1},\ldots,x_{N}\}$ and $Y=\{y_{1},\ldots,y_{N}\}$, then $X_{U}=\{Ux_{1},\ldots,Ux_{N}\}$. Let $\max_{x\in X}(d(x,0))=D_{X}$, $\max_{y\in Y}(d(y,0))=D_{Y}$ and $\max_{x\in X_{U}}(d(x,0))=D_{X_{U}}$. Since, each point in $X_{U}$ is the $U$ times each point in $X$. Then, we can write $D_{X_{U}}=\max_{x\in X}(d(Ux,0))$. Since, for any two points, $x_{1}$ and $x_{2}$, $d(Ux_{1},x_{2})=d(x_{1},U^{T}x_{2})$, and $U^{T}0=0$, then $D_{X_{c}}=\max_{x\in X}(d(x,0))$. Hence, $D_{x_{c}}=D_{X}$.
From the definition of $\mathsf{GNSA}$,

$$ $\mathsf{GNSA}(X_{U},Y)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\left(\frac{ d(Ux_{i},Ux_{j})}{D_{X_{c}}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right)\right|.$ $$

Again, using $d(Ux_{i},Ux_{j})=d(x_{i},U^{T}Ux_{j})$, and $U^{T}U=I$,

$$ $\mathsf{GNSA}(X_{U},Y)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\left(\frac{ d(x_{i},x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right)\right|.$ $$

Hence, $\mathsf{GNSA}(X_{U},Y)=\mathsf{GNSA}(X,Y)$.
∎

By Lemma B.2, we get invariance to orthogonal transformation in the second coordinate too and combining, we get the required lemma.

###### Lemma C.5 (Invariance to Orthogonal transformation) .

Let $X$ and $Y$ be two point clouds of the same size. Let $U_{1}$ be an orthogonal transformation on the point space of $X$, $X_{U_{1}}$ be the point cloud with each point in $X$ transformed using $U_{1}$. Similarly, let $U_{2}$ be an orthogonal transformation on the point space of $Y$, $Y_{U_{2}}$ be the point cloud with each point in $Y$ transformed using $U_{2}$, then $\mathsf{GNSA}(X,Y)=\mathsf{GNSA}(X_{U_{1}},Y_{U_{2}})$.

###### Lemma C.4 (Invariance to Orthogonal transformation in the first coordinate) .

###### Proof.

###### Lemma C.5 (Invariance to Orthogonal transformation) .

### C.3 Not Invariant under Invertible Linear Transformation (ILT)

We can easily see this with a counter example. Let $X=\{(1,0,0),(0,1,0),(0,0,1)\}$. Let $Y=\{(1,1,0),(1,0,1),(0,1,1)\}$. Define $A$ to be an invertible linear map such that $A(1,0,0)=(2,0,0)$, $A(0,1,0)=(0,1,0)$ and $A(0,0,1)=(0,0,1)$. Let $X_{A}$ be the point cloud with each point in $X$ transformed using $A$. Then from some calculation, we can see that $\mathsf{GNSA}(X,Y)=0$ but $\mathsf{GNSA}(X_{A},Y)=\frac{1}{9}$. Hence, we can see that $\mathsf{GNSA}$ is not invariant under Invertible Linear Transformations.

## Appendix D Proofs for GNSA as a Loss Function

### D.1 Differentiability of GNSA

To derive the sub-gradient $\frac{\partial\mathsf{GNSA}(X,Y)}{\partial x_{i}}$, we first define the following notation.
Let $\mathbb{I}:\{T,F\}\to\{0,1\}$ be a function that takes as input some condition and outputs 0 0 or $1$ such that $\mathbb{I}(T)=1$ and $\mathbb{I}(F)=0$.
Let $D_{X}=\max_{x\in X}(d(x,0))$. Then it is easy to see that

$$ $\frac{\partial D_{X}}{\partial{x_{i}}}=\frac{x_{i}}{d(x_{i},0)}\mathbb{I}\{ \operatorname*{arg\,max}_{x\in X}(d(x,0))=i\}.$ $$

Also, notice that $\frac{\partial d(x_{i},x_{j})}{x_{i}}=\frac{x_{i}-x_{j}}{d(x_{i},x_{j})},$
and that for $j\neq i$ and $k\neq i$,
$\frac{\partial d(x_{j},x_{k})}{x_{i}}=0.$

Let $m_{X}^{i,j}=\frac{d(x_{i},x_{j})}{D_{X}}$ and $m_{Y}^{i,j}=\frac{d(y_{i},y_{j})}{D_{Y}}$.
Hence, combining, we get

$$ $\frac{\partial m_{X}^{j,k}}{\partial x_{i}}=\frac{\frac{\partial d(x_{j},x_{k} )}{\partial x_{i}}}{D_{X}}-\frac{d(x_{j},x_{k})\frac{\partial D_{X}}{\partial x _{i}}}{(D_{X})^{2}},\text{ where these partial differentials are derived above.}$ $$

Lastly, notice that $\frac{\partial\left|m^{j,k}_{X}-m^{j,k}_{Y}\right|}{\partial m_{X}^{j,k}}=(-1)
^{\mathbb{I}(m^{j,k}_{Y}>m^{j,k}_{X})}.$

Combining all the above, we get

$$ $\displaystyle\frac{\partial\mathsf{GNSA}(X,Y)}{\partial x_{i}}$ $\displaystyle=\frac{1}{N^{2}}\sum_{1\leq j,k\leq N}\frac{\partial\left|m^{j,k} _{X}-m^{j,k}_{Y}\right|}{\partial m_{X}^{j,k}}\frac{\partial m_{X}^{j,k}}{ \partial x_{i}}$ $\displaystyle=\frac{1}{N^{2}}\sum_{1\leq j,k\leq N}(-1)^{\mathbb{I}(m^{j,k}_{Y }>m^{j,k}_{X})}\frac{\partial m_{X}^{j,k}}{\partial x_{i}}.$ $$

Sub-gradients $\frac{\partial\mathsf{GNSA}(X,Y)}{\partial y_{i}}$ can be similarly derived.

### D.2 Continuity

We prove the continuity of $\mathsf{GNSA}$ by showing that $\mathsf{GNSA}$ is a composition of continuous functions (Carothers, , Theorem 5.10). Let

$$ $f_{i,j}(X,Y)=\left|\frac{d(x_{i},x_{j})}{\max_{x\in X}(d(x,0))}-\frac{d(y_{i}, y_{j})}{\max_{y\in Y}(d(y,0))}\right|.$ $$

$$ $\text{It's easy to see that}\qquad\mathsf{GNSA}(X,Y)=\frac{1}{N^{2}}\sum_{1 \leq i,j\leq N}f_{i,j}(X,Y).$ $$

Since a sum of continuous functions is continuous, all we need to show is that $f_{i,j}(X,Y)$ is continuous for all $1\leq i,j\leq N$. This is easy to see because $f_{i,j}(X,Y)$ can be seen as a composition of $d(\cdot,\cdot)$ and $\max(\cdot)$, along with the algebraic operations of subtraction, division and taking the absolute value. All the above operations are continuous everywhere(^4^44Note that division is not continuous when the denominator goes to zero. Since, the denominators are $\max_{x\in X}(d(x,0))$ and $\max_{y\in Y}(d(y,0))$, as long as neither of the representations is all zero, the denominator does not go to zero.), we get that their composition is also continuous everywhere. Hence, $\mathsf{GNSA}(\cdot,\cdot)$ is continuous.

### D.3 Motivation for GNSA

The global part of NSA is inspired by Representational Similarity Matrix (RSM)-Based Measures (Klabunde et al., ). RSMs describe the similarity of the representation of each instance to all other instances within a given representation. The elements of the RSM $S_{i,j}$ can be defined using a valid distance or similarity function, formally: $S_{i,j}:=s(R_{i},R_{j})$.

The motivation behind RSM-based measures is to capture the relational structure in the data. By comparing the pairwise similarities of instances within two different representations, RSM-based measures provide insights into how the internal structure of representations changes. RSMs are invariant to orthogonal transformations, which means they retain their structure under rotations and reflections. When using euclidean distance as a similarity function, the RSM is invariant under euclidean group $E(n)$, assuming translations.

One might think that the most intuitive approach to compare RSMs is to use a matrix norm. This method works well when the data is similarly scaled, as it is zero when the data is identical and larger when the data is dissimilar. However, it is not invariant to scaling, which can cause issues if the data is not similarly scaled. To ensure the data is on a similar scale, we first normalize the data using the normalization function:

$$ $R_{norm}=\frac{R}{2*max(||x_{i}||)}$ $$

Where $x_{i}$ is the point farthest from the origin in the space. One of the primary reasons for our metric’s effectiveness is this normalization scheme. Although other normalizations are possible, NSA performs best when we normalize the space $X$ by twice the distance between the origin of the space and the farthest point in the space. This ensures that all the points are within a unit sphere in $N$ dimensions where $N$ is the dimensionality of the space. The origin of the space is the point in $\mathbb{R}^{N}$ around which all points belonging to $X$ are centered.

Most popular similarity measures, such as CKA(Kornblith et al., ) and RTD(Barannikov et al., ) also generate a similarity matrix. GNSA is simple in its implementation, but our choice of distance function and unique normalization scheme make GNSA a pseudometric, a similarity index and a valid, differentiable loss function.

### D.4 Improving Robustness of NSA

Formally, NSA is normalized by the point that is furthest away from the origin for the representation space. In practice, NSA yields more robust results and exhibits reduced susceptibility to outliers when distances are normalized relative to a quantile of the distances from the origin (e.g., 0.98 quantile). This quantile-based approach ensures that the distances are adjusted proportionally, taking into account the spread of values among the points with respect to their distances from the origin. It also ensures that any outliers do not affect the rescaling of the point cloud to the unit space.

## Appendix E Proofs for LNSA as a premetric

###### Lemma E.1 (Identity) .

Let $X$ be a point cloud over some space, then $\mathsf{LNSA}^{\mathsf{metric}}(X,X)=0$.

###### Proof.

Let $X=\{\vec{x}_{1},\ldots,\vec{x}_{N}\}$. Hence, we see that

$$ $\mathsf{LNSA}^{\mathsf{metric}}(X,X)=\mathsf{LNSA}_{X}(X)+\mathsf{LNSA}_{X}(X) =2\mathsf{LNSA}_{X}(X).$ $$

We show that $\mathsf{LNSA}_{X}(X)=0$. We see that

$$ $\mathsf{LNSA}_{X}(X)=\frac{1}{N}\sum_{1\leq i\leq N}\left(\mathsf{lid}(i,X)^{- 1}-\overline{\mathsf{lid}}_{X}(i,X)^{-1}\right)^{2}.$ $$

Note that

$$ $\overline{\mathsf{lid}}_{X}(i,X)=\mathsf{AD}_{X}({i,{k}NN_{X}(i)})=\mathsf{lid }(i,X).$ $$

Hence we get

$$ $\mathsf{LNSA}_{X}(X)=\frac{1}{N}\sum_{1\leq i\leq N}\left(\mathsf{lid}(i,X)^{- 1}-\mathsf{lid}(i,X)^{-1}\right)^{2}=0.$ $$

And hence we have

$$ $\mathsf{LNSA}^{\mathsf{metric}}(X,X)=2\mathsf{LNSA}_{X}(X)=0.$ $$

∎

###### Lemma E.2 (Symmetry) .

Let $X,Y$ be two point clouds of the same size, then $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}^{\mathsf{metric}}(Y,X)$.

###### Proof.

Let $X=\{x_{1},\ldots,x_{N}\}$ and $Y=\{y_{1},\ldots,y_{N}\}$. Then

$$ $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}_{X}(Y)+\mathsf{LNSA}_{Y}(X) =\mathsf{LNSA}^{\mathsf{metric}}(Y,X).$ $$

Hence,

$$ $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}^{\mathsf{metric}}(Y,X).$ $$

∎

###### Lemma E.3 (Non-negativity) .

Let $X,Y$ be two point clouds of the same size, then $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)\geq 0$.

###### Proof.

Let $X=\{x_{1},\ldots,x_{N}\}$ and $Y=\{y_{1},\ldots,y_{N}\}$. Note that

$$ $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}_{X}(Y)+\mathsf{LNSA}_{Y}(X),$ $$

and

$$ $\mathsf{LNSA}_{X}(Y)=\frac{1}{N}\sum_{1\leq i\leq N}\left(\mathsf{lid}(i,X)^{- 1}-\overline{\mathsf{lid}}_{X}(i,Y)^{-1}\right)^{2}.$ $$

Since, for all $i$, $\left(\mathsf{lid}(i,X)^{-1}-\overline{\mathsf{lid}}_{X}(i,Y)^{-1}\right)^{2}\geq
0$, hence we get $\mathsf{LNSA}_{X}(Y)\geq 0$. Similarly, $\mathsf{LNSA}_{Y}(X)\geq 0$ and hence, $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)\geq 0$.
∎

From Lemma E.1, Lemma E.2 and Lemma E.3, we see that $\mathsf{LNSA}^{\mathsf{metric}}$ is a premetric over the space of point clouds.

###### Lemma E.1 (Identity) .

###### Proof.

###### Lemma E.2 (Symmetry) .

###### Proof.

###### Lemma E.3 (Non-negativity) .

###### Proof.

## Appendix F Proofs for LNSA as a similarity metric

### F.1 Invariance to Isotropic Scaling

###### Lemma F.1 (Invariance to Isotropic scaling in the first coordinate) .

Let $X$ and $Y$ be two point clouds of the same size. Let $c\in\mathbf{R}$ and $c\neq 0$, $X_{c}$ be the point cloud with each point in $X$ scaled by a factor of $c$, then $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}^{\mathsf{metric}}(X_{c},Y)$.

###### Proof.

Let $X=\{\vec{x}_{1},\ldots,\vec{x}_{N}\}$ and $Y=\{\vec{y}_{1},\ldots,\vec{y}_{N}\}$, then $X_{c}=\{c\vec{x}_{1},\ldots,c\vec{x}_{N}\}$. We show that $\mathsf{AD}_{X_{c}}({i,(i_{1},\ldots,i_{k})})=\mathsf{AD}_{X}({i,(i_{1},\ldots
,i_{k})})$. Note that

$$ $\mathsf{AD}_{X_{c}}({i,(i_{1},\ldots,i_{k})})=-\left(\frac{1}{k}\sum_{j=1}^{k} \log\left(\frac{d(c\vec{x}_{i},c\vec{x}_{i_{j}})}{d(c\vec{x}_{i},c\vec{x}_{i_{ k}})}\right)\right)^{-1}.$ $$

Since, $\frac{d(c\vec{x}_{i},c\vec{x}_{i_{j}})}{d(c\vec{x}_{i},c\vec{x}_{i_{k}})}=
\frac{cd(\vec{x}_{i},\vec{x}_{i_{j}})}{cd(\vec{x}_{i},\vec{x}_{i_{k}})}=\frac{
d(\vec{x}_{i},\vec{x}_{i_{j}})}{d(\vec{x}_{i},\vec{x}_{i_{k}})}$. Hence,

$$ $\mathsf{AD}_{X_{c}}({i,(i_{1},\ldots,i_{k})})=-\left(\frac{1}{k}\sum_{j=1}^{k} \log\left(\frac{d(\vec{x}_{i},\vec{x}_{i_{j}})}{d(\vec{x}_{i},\vec{x}_{i_{k}}) }\right)\right)^{-1}.$ $$

Hence, $\mathsf{AD}_{X_{c}}({i,(i_{1},\ldots,i_{k})})=\mathsf{AD}_{X}({i,(i_{1},\ldots
,i_{k})})$. Hence, we get $\mathsf{lid}(\cdot,X_{c})=\mathsf{lid}(\cdot,X)$. Also note that since ${k}NN_{X_{c}}(\cdot)={k}NN_{X}(\cdot)$, we have that $\overline{\mathsf{lid}}_{X_{c}}(\cdot,Y)=\overline{\mathsf{lid}}_{X}(\cdot,Y)$. Hence, we get $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}^{\mathsf{metric}}(X_{c},Y)$.
∎

By Lemma E.2, we can see that this gives us invariance to isotropic scaling in the second coordinate as well.

###### Lemma F.2 (Invariance to Isotropic scaling in the second coordinate) .

Let $X$ and $Y$ be two point clouds of the same size. Let $c\in\mathbf{R}$ and $c\neq 0$, $Y_{c}$ be the point cloud with each point in $Y$ scaled by a factor of $c$, then $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}^{\mathsf{metric}}(X,Y_{c})$.

Combining Lemma F.1 and Lemma F.2, we get the required lemma.

###### Lemma F.3 (Invariance to Isotropic scaling) .

Let $X$ and $Y$ be two point clouds of the same size. Let $c_{1},c_{2}\in\mathbf{R}$, $c_{1}\neq 0$ and $c_{2}\neq 0$, $X_{c_{1}}$ be the point cloud with each point in $X$ scaled by a factor of $c_{1}$ and $Y_{c_{2}}$ be the point cloud with each point in $Y$ scaled by a factor of $c_{2}$, then $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}^{\mathsf{metric}}(X_{c_{1}}
,Y_{c_{2}})$.

###### Lemma F.1 (Invariance to Isotropic scaling in the first coordinate) .

###### Proof.

###### Lemma F.2 (Invariance to Isotropic scaling in the second coordinate) .

###### Lemma F.3 (Invariance to Isotropic scaling) .

### F.2 Invariance to Orthogonal transformation

###### Lemma F.4 (Invariance to Orthogonal transformation in the first coordinate) .

Let $X$ and $Y$ be two point clouds of the same size. Let $U$ be an orthogonal transformation on the point space of $X$, $X_{U}$ be the point cloud with each point in $X$ transformed using $U$, then $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}^{\mathsf{metric}}(X_{U},Y)$.

###### Proof.

Let $X=\{\vec{x}_{1},\ldots,\vec{x}_{N}\}$ and $Y=\{\vec{y}_{1},\ldots,\vec{y}_{N}\}$, then $X_{U}=\{U\vec{x}_{1},\ldots,U\vec{x}_{N}\}$. We show that $\mathsf{AD}_{X_{U}}({i,(i_{1},\ldots,i_{k})})=\mathsf{AD}_{X}({i,(i_{1},\ldots
,i_{k})})$. Note that

$$ $\mathsf{AD}_{X_{c}}({i,(i_{1},\ldots,i_{k})})=-\left(\frac{1}{k}\sum_{j=1}^{k} \log\left(\frac{d(U\vec{x}_{i},U\vec{x}_{i_{j}})}{d(U\vec{x}_{i},U\vec{x}_{i_{ k}})}\right)\right)^{-1}.$ $$

Since, $\frac{d(U\vec{x}_{i},U\vec{x}_{i_{j}})}{d(U\vec{x}_{i},U\vec{x}_{i_{k}})}=
\frac{d(U^{T}U\vec{x}_{i},\vec{x}_{i_{j}})}{d(U^{T}U\vec{x}_{i},\vec{x}_{i_{k}
})}=\frac{d(\vec{x}_{i},\vec{x}_{i_{j}})}{d(\vec{x}_{i},\vec{x}_{i_{k}})}$. Hence,

$$ $\mathsf{AD}_{X_{c}}({i,(i_{1},\ldots,i_{k})})=-\left(\frac{1}{k}\sum_{j=1}^{k} \log\left(\frac{d(\vec{x}_{i},\vec{x}_{i_{j}})}{d(\vec{x}_{i},\vec{x}_{i_{k}}) }\right)\right)^{-1}.$ $$

Hence, $\mathsf{AD}_{X_{U}}({i,(i_{1},\ldots,i_{k})})=\mathsf{AD}_{X}({i,(i_{1},\ldots
,i_{k})})$. Hence, we get $\mathsf{lid}(\cdot,X_{U})=\mathsf{lid}(\cdot,X)$. Also note that since ${k}NN_{X_{U}}(\cdot)={k}NN_{X}(\cdot)$, we have that $\overline{\mathsf{lid}}_{X_{U}}(\cdot,Y)=\overline{\mathsf{lid}}_{X}(\cdot,Y)$. Hence, we get $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}^{\mathsf{metric}}(X_{U},Y)$.
∎

By Lemma E.2, we get invariance to orthogonal transformation in the second coordinate too and combining, we get the required lemma.

###### Lemma F.5 (Invariance to Orthogonal transformation) .

Let $X$ and $Y$ be two point clouds of the same size. Let $U_{1}$ be an orthogonal transformation on the point space of $X$, $X_{U_{1}}$ be the point cloud with each point in $X$ transformed using $U_{1}$. Similarly, let $U_{2}$ be an orthogonal transformation on the point space of $Y$, $Y_{U_{2}}$ be the point cloud with each point in $Y$ transformed using $U_{2}$, then $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=\mathsf{LNSA}^{\mathsf{metric}}(X_{U_{1}}
,Y_{U_{2}})$.

###### Lemma F.4 (Invariance to Orthogonal transformation in the first coordinate) .

###### Proof.

###### Lemma F.5 (Invariance to Orthogonal transformation) .

### F.3 Not Invariant under Invertible Linear Transformation (ILT)

We can easily see this with a counter example. Let $X=\{(1,0,0),(0,1,0),(0,0,1)\}$. Let $Y=\{(1,1,0),(1,0,1),(0,1,1)\}$. Define $A$ as an invertible linear map such that $A(1,0,0)=(2,0,0)$, $A(0,1,0)=(0,1,0)$ and $A(0,0,1)=(0,0,1)$. Let $X_{A}$ be the point cloud with each point in $X$ transformed using $A$. Then from some calculations we can see that $\mathsf{LNSA}^{\mathsf{metric}}(X,Y)=0$ but $\mathsf{LNSA}^{\mathsf{metric}}(X_{A},Y)=\frac{1}{12}\left(\log(5)-\log(2)
\right)^{2}$. Hence, we can see that $\mathsf{GNSA}$ is not invariant under Invertible Linear Transformations.

## Appendix G Proofs for LNSA as a Loss Function

### G.1 Differentiability of LNSA

To derive the sub-gradient $\frac{\partial\mathsf{LNSA}_{Y}(X)}{\partial x_{i}}$, we first define the following notation.

Let

$$ $f_{j,Y}(X)=\left(\mathsf{lid}(j,Y)^{-1}-\overline{\mathsf{lid}}_{Y}(j,X)^{-1} \right)^{2}.$ $$

$$ $\text{Using this, }\qquad\mathsf{LNSA}_{Y}(X)=\frac{1}{N}\sum_{1\leq j\leq N}f _{j,Y}(X).$ $$

Hence,

$$ $\frac{\partial\mathsf{LNSA}_{Y}(X)}{\partial x_{i}}=\frac{1}{N}\sum_{1\leq j \leq N}\frac{\partial f_{j,Y}(X)}{\partial\vec{x}_{i}}.$ $$

Note that $\mathsf{lid}(j,Y)^{-1}$ is constant with respect to $\vec{x}_{i}$, hence,

$$ $\frac{\partial f_{j,Y}(X)}{\partial\vec{x}_{i}}=-2\left(\mathsf{lid}(j,Y)^{-1} -\overline{\mathsf{lid}}_{Y}(j,X)^{-1}\right)\frac{\partial\overline{\mathsf{ lid}}_{Y}(j,X)^{-1}}{\partial\vec{x}_{i}}.$ $$

To compute $\frac{\partial\overline{\mathsf{lid}}_{Y}(j,X)^{-1}}{\partial\vec{x}_{i}}$, we divide this into the four cases below:

- •
$i=j$: Let ${k}NN_{Y}(i)=(i_{1},\cdot,i_{k})$, then $\overline{\mathsf{lid}}_{Y}(i,X)^{-1}=\sum_{l=1}^{k}\log\left(\frac{d(\vec{x}_
{i},\vec{x}_{i_{l}})}{d(\vec{x}_{i},\vec{x}_{i_{k}})}\right)$. Hence,
$\frac{\partial\overline{\mathsf{lid}}_{Y}(i,X)^{-1}}{\partial\vec{x}_{i}}=\sum
_{l=1}^{k}\left(\frac{1}{d(\vec{x}_{i},\vec{x}_{i_{l}})}\frac{\partial d(\vec{
x}_{i},\vec{x}_{i_{l}})}{\partial\vec{x}_{i}}-\frac{1}{d(\vec{x}_{i},\vec{x}_{
i_{k}})}\frac{\partial d(\vec{x}_{i},\vec{x}_{i_{k}})}{\partial\vec{x}_{i}}
\right).$
- •
$j\in{k}NN_{Y}(i)$ and $j$ is not the last element of ${k}NN_{Y}(i)$: Let ${k}NN_{Y}(i)=(i_{1},\cdot,i_{k})$, then $\overline{\mathsf{lid}}_{Y}(i,X)^{-1}=\sum_{l=1}^{k}\log\left(\frac{d(\vec{x}_
{i},\vec{x}_{i_{l}})}{d(\vec{x}_{i},\vec{x}_{i_{k}})}\right)$. Hence,
$\frac{\partial\overline{\mathsf{lid}}_{Y}(i,X)^{-1}}{\partial\vec{x}_{i}}=
\frac{1}{d(\vec{x}_{i},\vec{x}_{j})}\frac{\partial d(\vec{x}_{i},\vec{x}_{j})}
{\partial\vec{x}_{i}}.$
- •
$j\in{k}NN_{Y}(i)$ and $j$ is the last element of ${k}NN_{Y}(i)$: Let ${k}NN_{Y}(i)=(i_{1},\cdot,i_{k})$, then $\overline{\mathsf{lid}}_{Y}(i,X)^{-1}=\sum_{l=1}^{k}\log\left(\frac{d(\vec{x}_
{i},\vec{x}_{i_{l}})}{d(\vec{x}_{i},\vec{x}_{i_{k}})}\right)$. Hence,
$\frac{\partial\overline{\mathsf{lid}}_{Y}(i,X)^{-1}}{\partial\vec{x}_{i}}=(1-k
)\left(\frac{1}{d(\vec{x}_{i},\vec{x}_{j})}\frac{\partial d(\vec{x}_{i},\vec{x
}_{j})}{\partial\vec{x}_{i}}\right).$
- •
$j\not\in{k}NN_{Y}(i)$ and $j\neq i$: Then
$\frac{\partial\overline{\mathsf{lid}}_{Y}(i,X)^{-1}}{\partial\vec{x}_{i}}=0.$

Hence, combining the above, we have the sub-gradients of $\mathsf{LNSA}_{Y}(X)$.

### G.2 Continuity

We prove the continuity of $\mathsf{LNSA}^{\mathsf{metric}}$ by showing that $\mathsf{LNSA}^{\mathsf{metric}}$ is a composition of continuous functions (Carothers, , Theorem 5.10). Let

$$ $f_{i,Y}(X)=\left(\mathsf{lid}(i,Y)^{-1}-\overline{\mathsf{lid}}_{Y}(i,X)^{-1} \right)^{2}.$ $$

$$ $\text{Using this,}\qquad\mathsf{LNSA}_{Y}(X)=\frac{1}{N}\sum_{1\leq i\leq N}f_ {i,Y}(X).$ $$

Since a sum of continuous functions is continuous, all we need to show is that $f_{i,Y}(X)$ is continuous for all $1\leq i\leq N$. Let ${k}NN_{Y}(i)=(i_{1},\cdot,i_{k})$, then note that

$$ $f_{i,Y}(X)=\left(\sum^{k}_{l=1}\left(\log\left(\frac{d(\vec{x}_{i},\vec{x}_{i_ {l}})}{d(\vec{x}_{i},\vec{x}_{i_{k}})}\right)-\log\left(\frac{d(\vec{y}_{i}, \vec{y}_{i_{l}})}{d(\vec{y}_{i},\vec{y}_{i_{k}})}\right)\right)\right)^{2},$ $$

hence can be seen as a composition of $d(\cdot,\cdot)$ and $\log(\cdot)$, along with the algebraic operations of addition, subtraction, multiplication and division. All the above operations are continuous everywhere(^5^55Note that division is not continuous when the denominator goes to zero. Since, the denominators are $(d(\vec{x}_{i},\vec{x}_{i_{k}}))$, as long as all $k$ neighbours of a point are not zero distance away, the denominator does not go to zero.), we get that their composition is also continuous everywhere. Hence, $\mathsf{LNSA}_{Y}(\cdot)$ is continuous.

## Appendix H Convergence of subset GNSA

Here, we prove that $\mathsf{GNSA}$ adapts well to minibatching and hence can be used as a loss term. In particular, Lemma H.1 proves theoretically that in expectation, $\mathsf{GNSA}$ over a minibatch is equal to $\mathsf{GNSA}$ of the whole dataset. This supplements the results presented in Figure 2. The experiment is run on the output embeddings of a GCN trained on node classification for the Cora Dataset. We compare the convergence with a batch size of 200 and 500.

###### Lemma H.1 (Subset GNSA convergence) .

Let $X,Y$ be two point clouds of the same size $N$ such that $X=\{x_{1},\ldots,x_{N}\}$ and $Y=\{y_{1},\ldots,y_{N}\}$. Let $\tilde{X}$ be some randomly sampled $s$ sized subsets of $X$ (for some $s\leq N$). Define $\tilde{Y}\subset Y$ as $y_{i}\in\tilde{Y}$ iff $x_{i}\in\tilde{X}$. Then the following holds true

$$ $\mathop{\mathbb{E}}_{\begin{subarray}{c}\tilde{X},\tilde{Y}\end{subarray}} \left[\mathsf{GNSA}(\tilde{X},\tilde{Y})\right]=\mathsf{GNSA}(X,Y).$ $$

###### Proof.

Let $\max_{x\in X}(d(x,0))=D_{X}$ and $\max_{y\in Y}(d(y,0))=D_{Y}$. Then

$$ $\mathsf{GNSA}(X,Y)=\frac{1}{N^{2}}\sum_{1\leq i,j\leq N}\left|\frac{d(x_{i},x_ {j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right|.$ $$

Define $\mathbb{I}_{\tilde{X}}\left(x_{i}\right)$ as

$$ $\mathbb{I}_{\tilde{X}}\left(x_{i}\right)=\begin{cases}1\text{ if }x_{i}\in \tilde{X},\\ 0\text{ otherwise.}\end{cases}$ $$

Then we can see that

$$ $\mathsf{GNSA}(\tilde{X},\tilde{Y})=\frac{1}{s^{2}}\sum_{1\leq i,j\leq N}\left| \frac{d(x_{i},x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right|\mathbb{I}_{ \tilde{X}}\left(x_{i}\right)\mathbb{I}_{\tilde{X}}\left(x_{j}\right).$ $$

Hence, taking expectation over $\tilde{X},\tilde{Y}$, we get

$$ $\mathop{\mathbb{E}}_{\begin{subarray}{c}\tilde{X},\tilde{Y}\end{subarray}} \left[\mathsf{GNSA}(\tilde{X},\tilde{Y})\right]=\frac{1}{s^{2}}\mathop{\mathbb {E}}_{\begin{subarray}{c}\tilde{X},\tilde{Y}\end{subarray}}\left[\sum_{1\leq i ,j\leq N}\left|\frac{d(x_{i},x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right |\mathbb{I}_{\tilde{X}}\left(x_{i}\right)\mathbb{I}_{\tilde{X}}\left(x_{j} \right)\right].$ $$

By linearity of expectation, we get

$$ $\mathop{\mathbb{E}}_{\begin{subarray}{c}\tilde{X},\tilde{Y}\end{subarray}} \left[\mathsf{GNSA}(\tilde{X},\tilde{Y})\right]=\frac{1}{s^{2}}\sum_{1\leq i,j \leq N}\left|\frac{d(x_{i},x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right| \mathop{\mathbb{E}}_{\begin{subarray}{c}\tilde{X},\tilde{Y}\end{subarray}} \left[\mathbb{I}_{\tilde{X}}\left(x_{i}\right)\mathbb{I}_{\tilde{X}}\left(x_{j }\right)\right].$ $$

Assuming $s>>1$, each $x_{i}$ is independently in $\tilde{X}$ with probability $s/N$, hence, we get

$$ $\mathop{\mathbb{E}}_{\begin{subarray}{c}\tilde{X},\tilde{Y}\end{subarray}} \left[\mathsf{GNSA}(\tilde{X},\tilde{Y})\right]=\frac{1}{s^{2}}\sum_{1\leq i,j \leq N}\left|\frac{d(x_{i},x_{j})}{D_{X}}-\frac{d(y_{i},y_{j})}{D_{Y}}\right| \frac{s}{N}\frac{s}{N}.$ $$

Hence, we have

$$ $\mathop{\mathbb{E}}_{\begin{subarray}{c}\tilde{X},\tilde{Y}\end{subarray}} \left[\mathsf{GNSA}(\tilde{X},\tilde{Y})\right]=\mathsf{GNSA}(X,Y).$ $$

∎

###### Lemma H.1 (Subset GNSA convergence) .

###### Proof.

## Appendix I NSA running time over increasing batch sizes

Theoretically, NSA is quadratic in the number of points as we need to calculate pairwise distances. But since we use torch functions and the data is loaded on the GPU, empirical running times are significantly lower. Figure 5(a) presents the running time of GlobalNSA and Figure 5(a) presents the running time of NSA (Global and Local combined) on two embedding spaces of very high dimensionality ( 200,000). We notice that even when we get to a very high batch size (5000), the running time scaling is nearly linear. It is worth noting that these running times are higher as the dimensionality is very high, in most practical scenarios, your embeddings would lie in a lower dimension.

Figure: (a)
Refer to caption: extracted/5978749/figures/runtime_analysis/GPU_Runtime_2.png

## Appendix J Are GNNs Task Specific Learners?

We use NSA to investigate whether representations produced by GNNs are specific to the downstream task. For this, we explored the similarity of representations of different GNN architectures when trained on the same task versus their similarity when trained on different downstream tasks.

### J.1 Cross Architecture Tests on the Same Downstream Task

Figure: (a) GCN vs CGCN
Refer to caption: extracted/5978749/figures/GNN_analysis/Amazon/cross_arch_tests/NC/GCN_CGCN_NSA_heatmap.png

We tested layerwise representational similarity on the task of node classification (on the Amazon Computers Dataset) across different GNN architectures: GCN, ClusterGCN (CGCN), GraphSAGE, and GAT. Just like in the sanity tests, models that are similar in architecture or training paradigms have a higher layerwise similarity: this implies that the highest similarity is between GCN and ClusterGCN that differ only in their training paradigms. We also observe (a less pronounced) linear relationship between the other pairs of architectures. These results are shown in Figure 6.

### J.2 Architecture Tests on Different Downstream Tasks

Figure: Figure 7: Effect of Downstream Task on Representations Achieved by the Same Architecture (Amazon Computers Dataset). The layerwise dissimilarity of four GNN architectures is compared on two different downstream tasks: Node Classification and Link Prediction. There is no observable correlation across layers suggesting that the GNNs generate different representation spaces for the same dataset on different downstream tasks.
Refer to caption: extracted/5978749/figures/GNN_analysis/Amazon/cross_task_tests/GCN_NSA_heatmap.png

We conducted experiments with different downstream tasks to assess layerwise similarity between two models, both of which shared structural identity except for disparities in their final layers. Specifically, we employed node classification and link prediction as the two downstream tasks for our investigations. We present our findings in Figure 7. They reveal that there is little relationship across layers for any of the four architectures.

The results presented in this section indicate that that different GNN architectures have similar representation spaces when trained on the same downstream task and conversely, similar architectures have different representation spaces when trained on different downstream tasks. Extending this idea further, it should be possible to train Graph Neural Networks to conform to a task specific representation template. This structural template will be agnostic of GNN architectures and provide a high degree of functional similarity. If we train GNNs to minimize discrepancy loss with such a task specific template, we could train more directly and without adding downstream layers of tasks.

## Appendix K Downstream Task Analysis with the STS Dataset

We assess the performance of embeddings derived from NSA-AE in the context of the Semantic Text Similarity (STS) Task. We employ Google’s Word2Vec word vectors as the initial dataset, processing these 300-dimensional vectors through both a standard autoencoder and the NSA-Autoencoder to achieve reduced dimensions of 128 and 64. The efficacy of these dimensionality-reduced embeddings is then evaluated using the STS Multi EN dataset (Cer et al., ). This evaluation aims to determine if the word vectors, once dimensionally reduced, maintain their alignment, as evidenced by a strong positive correlation in similarity scores on the STS dataset. The comparative results, as detailed in Table 3, demonstrate that the NSA-Autoencoder outperforms the traditional autoencoder in preserving semantic accuracy at both 128 and 64 dimensions.

**Table 3: Pearson Correlation between the similarities output from the original embeddings and the similarities output from the reduced embeddings. NSA-AE shows a much higher correlation with the similarity outputs obtained by evaluating the original word2vec embeddings on the STS multi EN dataset**
| Latent Dimension | Basic AutoEncoder | NSA AutoEncoder |
| --- | --- | --- |
| 128 | -0.518 | 0.7632 |
| 64 | 0.567 | 0.7619 |

## Appendix L Running Time and Reconstruction Loss for Autoencoder

We show that using NSA along with Mean Squared Error in an autoencoder does not significantly compromise the model’s ability to reconstruct the original embedding. Additionally, NSA-AE is more efficient than RTD-AE and Topo-AE. The results are presented in Table 4

**Table 4: Reconstruction Loss and Time Per Epoch for different Autoencoder architectures. All architectures were trained for 250 epochs with the auxiliary loss (TopoLoss, RTD, NSA) kicking in after 60 epochs.**
|  |  | Metric |  |  |
| --- | --- | --- | --- | --- |
| Dataset | Method | Time per epoch | Train MSE | Test MSE |
| MNIST | AE | 2.344 | 7.64e-3 | 8.62e-3 |
|  | TopoAE | 39.168 | 6.89e-3 | 8.16e-3 |
|  | RTD-AE | 51.608 | 9.36e-3 | 1.07e-2 |
|  | NSA-AE | 5.816 | 8.75e-3 | 1.00e-2 |
| F-MNIST | AE | 6.436 | 8.99e-03 | 9.79e-03 |
|  | TopoAE | 37.26 | 8.94-03 | 9.83e-03 |
|  | RTD-AE | 59.94 | 1.12e-02 | 1.24e-02 |
|  | NSA-AE | 5.764 | 9.49e-03 | 1.04e-02 |
| CIFAR-10 | AE | 5.16 | 1.56e-02 | 1.65e-02 |
|  | TopoAE | 58.664 | 1.54e-02 | 1.68e-02 |
|  | RTD-AE | 56.172 | 1.60e-02 | 1.91e-02 |
|  | NSA-AE | 6.996 | 1.58e-02 | 1.71e-02 |
| COIL-20 | AE | 2.012 | 1.67e-02 | - |
|  | TopoAE | 4.876 | 1.09e-02 | - |
|  | RTD-AE | 16.404 | 1.90e-02 | - |
|  | NSA-AE | 8.716 | 1.80e-02 | - |

## Appendix M Autoencoder hyperparameters

The hyperparameter setup for all the autoencoder architectures is detailed in Table 5. All autoencoder architectures are trained using pytorch-lightning and the input data is normalized using a MinMaxScaler.

**Table 5: Autoencoder Hyperparameters. All four architectures used the same hyperparameters. To ensure similarity of testing conditions we replicate the hyperparameter setup from Trofimov et al. ()**
| Dataset Name | Batch Size | LR | Hidden Dim | Layers | Epochs | Metric Start Epoch |
| --- | --- | --- | --- | --- | --- | --- |
| MNIST | 256 | $10^{-}4$ | 512 | 3 | 250 | 60 |
| F-MNIST | 256 | $10^{-}4$ | 512 | 3 | 250 | 60 |
| CIFAR-10 | 256 | $10^{-}4$ | 512 | 3 | 250 | 60 |
| COIL-20 | 256 | $10^{-}4$ | 512 | 3 | 250 | 60 |

## Appendix N GNN hyperparameters

The hyperparameter setup for all the GNN architectures is detailed in Table 6

**Table 6: GNN Architecture Information**
| Architecture | Layers | Hidden Dim | LR | Epochs | Additional Info |
| --- | --- | --- | --- | --- | --- |
| GCN | 4 | 128 | 0.001 | 200 | - |
| GraphSAGE | 4 | 128 | 0.001 | 200 | Mean Aggregation |
| GAT | 4 | 128 | 0.001 | 200 | 8 heads with Hid Dim 8 each |
| CGCN | 4 | 128 | 0.001 | 200 | 8 subgraphs |

## Appendix O GNN metrics

The test accuracy for node classification and the ROC AUC value for link prediction is detailed in Table 7

**Table 7: GNN Metric Data on Amazon Computer Dataset. Test Accuracy is for Node Classification and ROC AUC Score is for Link Prediction**
| Architecture | Accuracy (NC) | ROC AUC (LP) |
| --- | --- | --- |
| GCN | 0.8257 | 0.8638 |
| GraphSAGE | 0.8800 | 0.8068 |
| GAT | 0.8273 | 0.7997 |
| CGCN | 0.8200 | 0.8716 |

## Appendix P Datasets

We report the statistics of the datasets used for the empirical analysis of GNNs in Table 8. We report the exact statistics of the autoencoder datasets in Table 9.

### P.1 Graph Datasets

The Amazon computers dataset is a subset of the Amazon co-purchase graph (Shchur et al., ). The nodes represent products on amazon and the edges indicate that two products are frequently bought together. The node features are the product reviews encoded in bag-of-words format. The class labels represent the product category. We also use the Flickr, Cora, Citeseer and Pubmed dataset in additional experiments.

**Table 8: Dataset Statistics for Graph**
| Dataset | Amazon Computer | Flickr | Cora | Citeseer | Pubmed |
| --- | --- | --- | --- | --- | --- |
| Number of Nodes | 13752 | 89250 | 2708 | 3327 | 19717 |
| Number of Edges | 491722 | 899756 | 10556 | 9104 | 88648 |
| Average Degree | 35.76 | 10.08 | 3.90 | 2.74 | 4.50 |
| Node Features | 767 | 500 | 1433 | 3703 | 500 |
| Labels | 10 | 7 | 7 | 6 | 3 |

### P.2 AutoEncoder Datasets

Four diverse real-world datasets were utilized for our experiments: MNIST (LeCun et al., ), Fashion-MNIST (F-MNIST) (Xiao et al., ), COIL-20 (Nene et al., ), and CIFAR-10 (Krizhevsky & Hinton, ), to comprehensively evaluate the performance of our autoencoder model. MNIST, comprising 28x28 grayscale images of handwritten digits, serves as a foundational benchmark for image classification and feature extraction tasks. Fashion-MNIST extends this by offering a similar format but with 10 classes of clothing items, making it an ideal choice for fashion-related image analysis. COIL-20 presents a unique challenge, with 20 object categories, where each category consists of 72 128x128 color images captured from varying viewpoints, offering a more complex 3D object recognition scenario.

**Table 9: Dataset Statistics for AE**
| Dataset | Classes | Train Size | Test Size | Image Size | Data Type |
| --- | --- | --- | --- | --- | --- |
| MNIST | 10 | 60,000 | 10,000 | 28x28 (784) | Grayscale |
| Fashion-MNIST (F-MNIST) | 10 | 60,000 | 10,000 | 28x28 (784) | Grayscale |
| COIL-20 | 20 | 1,440 | - | 128x128 (16384) | Color |
| CIFAR-10 | 10 | 60,000 | 10,000 | 32x32*3 (3072) | Color |

## Appendix Q Ablation Study

**Table 10: Autoencoder results. NSA-AE outperforms or almost matches all other approaches on all the evaluation metrics. RTD-AE, which explicitly minimizes on RTD has a slightly lower RTD value while PCA has marginally higher Triplet Ranking Accuracy on Cluster Centers.**
|  |  | Quality measure |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset | Method | L. C. | T. A. | RTD | T. A. C.C | NSA | LID-NSA | kNN-C |
| MNIST | GNSA-AE | $0.942$ | $0.885\pm 0.006$ | $5.44\pm 0.12$ | $0.944\pm 0.230$ | $\mathbf{0.0198\pm 0.0001}$ | $0.0342\pm 0.00$ | 0.616 |
|  | LNSA-AE | 0.819 | $0.794\pm 0.007$ | $7.39\pm 0.21$ | $0.832\pm 0.374$ | $0.0548\pm 0.00$ | $0.0373\pm 0.00$ | 0.607 |
|  | NSA-AE | $\mathbf{0.947}$ | $\mathbf{0.886\pm 0.005}$ | $\mathbf{4.29\pm 0.11}$ | $\mathbf{0.946\pm 0.226}$ | $0.0222\pm 0.00$ | $\mathbf{0.0123\pm 0.00}$ | 0.634 |
| F-MNIST | GNSA-AE | $\mathbf{0.987}$ | $\mathbf{0.952}\pm\mathbf{0.002}$ | $4.11\pm 0.21$ | $0.992\pm 0.089$ | $\mathbf{0.0091}\pm\mathbf{0.0001}$ | $0.0350\pm 0.00$ | 0.592 |
|  | LNSA-AE | 0.887 | $0.859\pm 0.006$ | $5.41\pm 0.18$ | $0.952\pm 0.214$ | $0.0488\pm 0.00$ | $0.0470\pm 0.00$ | 0.608 |
|  | NSA-AE | 0.9854 | $0.939\pm 0.003$ | $\mathbf{2.78\pm 0.09}$ | $\mathbf{0.992\pm 0.089}$ | $0.0114\pm 0.00$ | $\mathbf{0.0133\pm 0.00}$ | 0.633 |
| CIFAR-10 | GNSA-AE | $\mathbf{0.985}$ | $0.936\pm 0.004$ | $3.07\pm 0.11$ | $0.984\pm 0.125$ | $\mathbf{0.0077\pm 0.0001}$ | $0.0122\pm 0.00$ | 0.453 |
|  | LNSA-AE | 0.8616 | $0.849\pm 0.006$ | $4.02\pm 0.28$ | $0.936\pm 0.245$ | $0.0624\pm 0.00$ | $0.0220\pm 0.00$ | 0.359 |
|  | NSA-AE | 0.985 | $\mathbf{0.941\pm 0.003}$ | $\mathbf{3.04\pm 0.16}$ | $\mathbf{0.984\pm 0.125}$ | $\mathbf{0.0086\pm 0.00}$ | $\mathbf{0.0103\pm 0.00}$ | 0.437 |
| COIL-20 | GNSA-AE | $0.955$ | $0.919\pm 0.004$ | $7.46\pm 0.23$ | $0.939\pm 0.240$ | $0.0157\pm 0.0$ | $0.3427\pm 0.00$ | 0.721 |
|  | LNSA-AE | $0.848$ | $0.838\pm 0.007$ | $9.74\pm 0.26$ | $0.887\pm 0.316$ | $0.0672\pm 0.00$ | $0.5810\pm 0.00$ | 0.703 |
|  | NSA-AE | $\mathbf{0.976}$ | $\mathbf{0.919\pm 0.005}$ | $\mathbf{3.55\pm 0.18}$ | $\mathbf{0.962\pm 0.191}$ | $\mathbf{0.0139\pm 0.00}$ | $\mathbf{0.0085\pm 0.00}$ | $\mathbf{0.809}$ |

NSA consists of two parts, GlobalNSA and LocalNSA. These two components work well together and are capable of working individually too. LocalNSA makes locally optimal decisions but it could run into a problem when the global structure needs to be preserved. Figure 8 shows a scenario where LocalNSA would not obtain a high k-NN consistency between two representation spaces. This could potentially explain the low kNN consistency when minimizing with just LocalNSA in Table 10. LocalNSA’s inability to preserve global structure becomes especially prevalent in our LinkPrediction tests in Table 11. We intend on further improving LocalNSA and coming up with better preprocessing schemes to optimize its performence.
In practice, GNSA works well and performs competitively even when used without LNSA. LNSA provides a noticeable improvement but requires dataset specific fine tuning to find the optimal hyperparameter set up.

Figure: Figure 8: Illustration showing why LocalNSA might not maintain neighborhood consistency when used without GlobalNSA. The objective is to minimize the structural discrepancy between the reference space X (top) and generated space Y (mid-bottom). LocalNSA aims to minimize the difference in distances for the k-nearest neighbors of the $i^{th}$ point in X space (in yellow). If a random initialization causes an unknown point (in red) to move close to the $i^{th}$ point in Y space, LocalNSA will not move it out, instead focusing on bringing the 5 NNs of X close to i in Y causing a drop in neighborhood consistency $Y_{L}$ (left-bottom). Using GlobalNSA with LocalNSA alleviates this issue as GlobalNSA pushes point 4 away in the $Y_{GL}$ (right-bottom) .
Refer to caption: extracted/5978749/figures/icml_diagram.jpeg

**Table 11: Downstream task analysis with Link Prediction. The output embeddings from a GCN trained on link prediction are passed through all 3 autoencoder architectures. Latent embeddings are obtained at various dimensions and ROC-AUC scores are calculated on the latent embeddings. Using both LNSA and GNSA gives the best performance.**
|  |  | Dataset |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Method | Latent Dim | Amazon Comp | Cora | Citeseer | Pubmed |
|  | 128 | 95.74 | 96.04 | 97.18 | 97.31 |
| G-NSA-AE | 64 | 95.90 | 95.54 | 96.85 | 96.40 |
|  | 32 | 96.01 | 95.37 | 94.25 | 97.53 |
|  | 128 | 76.82 | 50.01 | 50.13 | 93.03 |
| L-NSA-AE | 64 | 74.24 | 50.69 | 50.25 | 93.64 |
|  | 32 | 80.67 | 55.44 | 51.43 | 95.69 |
|  | 128 | 95.75 | 97.83 | 97.91 | 97.37 |
| NSA-AE | 64 | 94.60 | 97.89 | 98.38 | 96.97 |
|  | 32 | 95.76 | 97.68 | 96.11 | 97.66 |

### Q.1 Visualizing The Effect with Spheres Dataset

We use the Spheres dataset (Moor et al., ), reducing the original 100 dimension data to 2 dimensions to visually observe the effect that different scaling factors for GNSA and LNSA have. The model is trained on a batch size of 200 and with no rescaling applied to the Spheres dataset. Additionally, NSA is the only loss applied here while in the autoencoder experiments, we also use MSE loss to contain the latent space. We observe that neither LNSA or GNSA do a perfect job when working individually. LNSA seems to work best with a scaling factor of 0.5 or 1 while GNSA starts exhibiting stable behavior when $g>5$.

Figure: Figure 9: Illustrating the effect that different values of land g have on convergence on the Spheres Dataset.
Refer to caption: extracted/5978749/figures/spheres/spheres_ablation.png

## Appendix R Visualizing the latent embeddings from Autoencoders

We use t-SNE(van der Maaten & Hinton, ) to reduce the latent embeddings obtained from all 4 datasets used in Table 1 to reduce their dimension from 16 to 3. The results are presented in Figure 10. We observe that t-SNE generates similar clusters across all three architectures; the basic Autoencoder, RTD-Autoencoder and NSA-Autoencoder.
It is important to note that the observation of similar clustering patterns between AE and NSA-AE embeddings in t-SNE plots does not necessarily indicate identical representation structures in the original high-dimensional latent spaces. This is because t-SNE’s emphasis on local similarities can result in visually analogous clusters even when the global structures or the exact nature of the representations differ significantly between the two methods. NSA-AE’s latent space captures the exact structure of the input representation space significantly better than a normal AE, preserving the data’s geometric and topological properties. This is demonstrated by NSA-AE’s latent embeddings having superior accuracy in downstream tests where exact structure preservation is vital (Section 4.3 and Appendix K).

Figure: (a) F-MNIST on AE
Refer to caption: extracted/5978749/figures/tSNE_results/Basic_AutoEncoder_FMNIST_tSNE.jpg

## Appendix S Reproducibility Statement

Our code is anonymously available at [https://anonymous.4open.science/r/NSA-B1EF](https://anonymous.4open.science/r/NSA-B1EF). The code includes notebooks with instructions to reproduce all the experiments presented in this paper. Hyperparameter setups are available in Appendices M, N and P. Detailed instructions are given in the README and in the notebooks. All the code was run on a conda environment with a single NVIDIA V100 GPU.

## Appendix T Approximating the manifold of a representation space

Incorporating a structure-preserving metric with MSE, NSA-AE maintains the Euclidean distances between data points as it compresses the data into a lower-dimensional space. High-dimensional data typically resides in a lower-dimensional manifold  (Goodfellow et al., ), where the Euclidean distance approximates the geodesic distance. Utilizing this approximation allows NSA-AE to unfold complex datasets to their manifold dimensions, providing a clearer interpretation of underlying data relationships that are often obscured in higher dimensional ambient spaces.

Our experiments with the Swiss Roll dataset illustrate the effectiveness of this approach. Figure 11(b) and 11(c) from our results display the outcomes of dimensionality reduction when prioritizing Euclidean distances versus geodesic distances. Preserving the geodesic distances lets us construct a more accurate representation of the Swiss Roll’s original manifold structure. Conversely, in cases where the manifold dimension of the input data remains unknown, the latent dimension at which NSA minimization becomes optimal inherently corresponds to the manifold dimension of the data. This observation underscores the practical significance of understanding the manifold dimension when leveraging NSA for dimensionality reduction within an autoencoder framework.

We also present results on dimensionality reduction for the Spheres Dataset from Moor et al. (). We show that you can use NSA-AE to reduce the 100 dimension dataset to 3 or even 2 dimensions and still preserve the structure of the representation space in Figure 12. While manifold learning techniques such as ISOMAP (Tenenbaum et al., ) and MDS (Kruskal, ) are also capable of unfolding complex datasets and preserving geodesic distances, they require access to the entire dataset for computation. This necessitates significant computational resources, particularly for large datasets. In contrast, NSA is able to achieve the same result while operating on mini-batches, making it substantially more computationally efficient and scalable.

Figure: (a)
Refer to caption: extracted/5978749/figures/swissroll/original3d.png

Figure: (a)
Refer to caption: x12.png

## Appendix U Empirical Analysis on Additional Datasets

Empirical analysis of intermediate representations with similarity measures can help uncover the intricate workings of various neural network architectures. When two networks that are structurally identical but trained from different initial conditions are compared, we expect that, for each layer’s intermediate representation, the most similar representation in the other model should be the corresponding layer that matches in structure. We can also perform cross-layer analysis and cross-downstream task analysis of the intermediate representations of a neural network to help uncover learning patterns of a network. We use 4 different GNN architectures; GCN (Kipf & Welling, ), GraphSAGE (Hamilton et al., ), ClusterGCN (Chiang et al., ) and Graph Attention Network (GAT) (Veličković et al., ). We evaluate with Sanity Tests, Cross Architecture Tests, Downstream Task tests and Convergence Tests. We utilize the Amazon Computers Dataset (Shchur et al., ), Cora (McCallum et al., ), Citeseer (Giles et al., ), Pubmed (Sen et al., ) and Flickr (Zeng et al., ) Datasets for our experiments.

### U.1 Initialization Sanity Tests

The sanity test compares the intermediate representations obtained from each layer of the Graph Neural Network against all the other layers of another GNN with the exact same architecture but trained with a different initialization. we expect that, for each layer’s intermediate representation, the most similar intermediate representation in the other model should be the corresponding layer that matches in structure. We only demonstrate the performance of NSA for both Node Classification and Link Prediction.

Figure: Figure 13: Sanity Tests for Link Prediction on 3 datasets. The heatmaps show layer-wise dissimilarity values for two different initialization of the same dataset on four different GNN architectures.
Refer to caption: extracted/5978749/figures/GNN_analysis/Amazon/sanity_tests/LP/GCN_NSA_heatmap.png

Figure: Figure 14: Sanity Tests for Node Classification on all 4 datasets. The heatmaps show layer-wise dissimilarity values for two different initialization of the same dataset on four GNN architectures.
Refer to caption: extracted/5978749/figures/GNN_analysis/Amazon/sanity_tests/NC/GCN_NSA_heatmap.png

### U.2 Cross Architecture Tests on Node Classification

In this section we evaluate the similarity in representations across architectures for the Amazon Computers dataset and the three Planetoid datasets; Cora, Citeseer and Pubmed on Node Classification.

Figure: (a) GCN vs ClusterGCN
Refer to caption: extracted/5978749/figures/GNN_analysis/Amazon/cross_arch_tests/NC/GCN_CGCN_NSA_heatmap.png

Figure: (a) GCN vs ClusterGCN
Refer to caption: extracted/5978749/figures/GNN_analysis/Cora/cross_arch_tests/NC/GCN_CGCN_NSA_heatmap.png

Figure: (a) GCN vs ClusterGCN
Refer to caption: extracted/5978749/figures/GNN_analysis/Citeseer/cross_arch_tests/NC/GCN_CGCN_NSA_heatmap.png

Figure: (a) GCN vs ClusterGCN
Refer to caption: extracted/5978749/figures/GNN_analysis/Pubmed/cross_arch_tests/NC/GCN_CGCN_NSA_heatmap.png

### U.3 Cross Architecture Tests on Link Prediction

In this section we evaluate the similarity in representations across architectures for the Amazon Computers dataset and the three Planetoid datasets; Cora, Citeseer and Pubmed on Link Prediction.

Figure: (a) GCN vs ClusterGCN
Refer to caption: extracted/5978749/figures/GNN_analysis/Amazon/cross_arch_tests/LP/GCN_CGCN_NSA_heatmap.png

Figure: (a) GCN vs ClusterGCN
Refer to caption: extracted/5978749/figures/GNN_analysis/Cora/cross_arch_tests/LP/GCN_CGCN_NSA_heatmap.png

Figure: (a) GCN vs ClusterGCN
Refer to caption: extracted/5978749/figures/GNN_analysis/Citeseer/cross_arch_tests/LP/GCN_CGCN_NSA_heatmap.png

Figure: (a) GCN vs ClusterGCN
Refer to caption: extracted/5978749/figures/GNN_analysis/Pubmed/cross_arch_tests/LP/GCN_CGCN_NSA_heatmap.png

### U.4 Cross Downstream Task Tests

We perform cross downstream task tests where we compare the layerwise intermediate representations between two models of the same architecture type but trained on different tasks. The two tasks we use are Node Classification and Link Prediction. The size of the intermediate embeddings is the same between the two models (Node Classification model vs Link Prediction model) except for the last layer. Since NSA is agnostic to the dimension of the embedding, we can compare all the layers regardless of their dimensionality. Just like the previous experiments, we test on the Amazon Computers Dataset and the three Planetoid Datasets. We observe that there is no strong correlation as we go further down the layers between the two models. The highest relative similarity is in the early layers and as we get to the final layers the similarity is almost non existent.

Figure: Figure 23: Cross Downstream Task Tests with NSA on the Amazon, Cora, Citeseer and Pubmed Datasets
Refer to caption: extracted/5978749/figures/GNN_analysis/Amazon/cross_task_tests/GCN_NSA_heatmap.png

## Appendix V Convergence Tests

As a neural network starts converging, the representation structure of the data stops changing significantly and the loss stops dropping drastically. Ideally, a similarity index should be capable of capturing this change. We examine epoch-wise convergence by comparing representations between the current and final epochs. We observe that NSA starts dropping to low values as the test accuracy stops increasing significantly. This shows that NSA can be used to help approximate convergence and even potentially be used as an early stopping measure during neural network training, stopping the weight updates once the structure of your intermediate representations stabilize. We show results for all 4 architectures on node classification and link prediction. Link Prediction models were trained for 200 epochs and show similar patterns to the ones observed with node classification. All convergence tests are performed with NSA only. We show the convergence tests on all 4 architectures on Node Classification in Figure 25 and on Link Prediction in Figure 24 .

Figure: (a) GCN LP Epochwise Convergence Heatmap
Refer to caption: extracted/5978749/figures/GNN_analysis/Amazon/convergence_tests/LP/GCN_NSA_heatmap.png

Figure: (a) GCN NC Epochwise Convergence Heatmap
Refer to caption: extracted/5978749/figures/GNN_analysis/Amazon/convergence_tests/NC/GCN_NSA_heatmap.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: 1) How does NSA perform in extremely high-dimensional spaces where Euclidean distance is known to be problematic? Are there alternative distance metrics that could be integrated into NSA?
2) How sensitive is NSA to parameter settings, and what are the best practices for tuning it in different applications (e.g., adversarial robustness vs. dimensionality reduction)?
3) Given the versatility of NSA, do you envision any specific areas where its application would be limited or challenging?
soundness: 3
strengths: 1) NSA can be used both as a loss function and a similarity metric across different applications 
2) NSA is designed to work efficiently in large-scale applications with a quadratic complexity that is better than some existing methods 
3) It is also effective in preserving structural characteristics and identifying vulnerabilities in neural networks, even under adversarial attacks
4) the paper provides a thorough analysis with multiple experiments and comparisons to other methods like RTD, CKA validating NSA's effectiveness
summary: The paper introduces Normalized Space Alignment(NSA), a new manifold analysis technique designed to compare neural network representations; NSA compares pairwise distances between point clouds from the same data source but with different dimensionalities. NSA is proposed as both a differentiable loss function and a similarity metric, and it is computationally efficient. The paper demonstrated the NSA's versatility in representation analysis, structure-preserving tasks, and robustness testing against adversarial attacks.
weaknesses: 1) The reliance on Euclidean distance as a primary metric may limit performance in high dimensional spaces due to curse of dimensionality 
2) NSA is versatile but may not require careful tuning and modifications to work effectively in specific scenarios
3) The limitations of NSA are not explored beyond high-dimensionality issue

---

confidence: 4
contribution: 3
initial_rating: 3
presentation: 3
questions: __Figure 1:__ assuming the values being plotted are means, how many tests were performed? What are their standard deviations? This is especially important since the data is being subsampled for the computations, and training seeds will produce different networks.

__Figure 3:__ same questions here with regards to whether the curves represent means. Stating how many repetitions and the standard deviations is important to understand the significance of these curves.

__Lines 324--328__: I had trouble understanding the sensitivity test. Although the notion of testing robustness to the removal of principal components makes perfect sense to me, it was not clear how the plots in Fig. 1 demonstrated, e.g., that "NSA is more sensitive to the removal of high variance PCs compared to RTD and CKA". Moreover, I'm not sure how to interpret the values for "detection threshold", especially since the values in the main text are different than those in the figure. What are the "baselines" mentioned in the plots' legends?

__Line 435:__ "the latent embeddings are then tested on their ability to predict the existence of links between nodes". How exactly are they tested on this? Are they used as inputs in another GCN? This wasn't clear to me.

In lines 197, 199, 272, surely the authors mean dissimilarity, not similarity (since they compute distances)? There are more instances throughout the paper where these metrics are called "similarities".

__Line 497:__ "We used a GCN along with four __robust__ GNN variants...". Why robust? Robust to what exactly?

__Line 500:__ "by introducing perturbations ranging from 5% to 25%". These percentages are w.r.t. what exactly? And what is the nature of these perturbations? Removing/changing links, nodes, or both?

__Minor points:__

- I found no pointer to Figure 3 in the main text.

- Line 493: "we applied NSA in the context of GNNs, but the method __can__ be equally effective in analyzing the robustness of other architectures". I recommend changing __can__ to "might", or "could", unless the authors have actually tested this empirically.

- Line 503: I recommend saying "the __original__ graph" instead of "the _clean_ graph".
soundness: 2
strengths: - NSA introduces a new approach for representation alignment with applications in dimensionality reduction, structure-preserving autoencoders, and robustness analysis, highlighting its adaptability to multiple tasks.

- Its quadratic computational complexity improves on the cubic complexity of alternative metrics like RTD, making it suitable for large datasets and mini-batch processing in training.

- NSA is evaluated across multiple tasks and datasets, and compared with established metrics (CKA and RTD).
summary: The paper introduces Normalized Space Alignment (NSA), a novel metric to analyze neural network representations. NSA compares two point clouds (representing data structures within neural networks) by preserving both global and local structures, regardless of differing dimensionalities. It can be used to preserve representation structures in tasks such as suitable for diverse tasks such as dimensionality reduction, adversarial robustness assessment, and cross-layer representation analysis. NSA’s main advantage is its ability to efficiently preserve global and local structure across different dimensional spaces. The authors showcase NSA’s versatility by applying it across various tasks, demonstrating its computational efficiency and robustness, particularly in mini-batch processing.
weaknesses: __Figure 1__: all 3 plots in the left column are the same.

__Specificity assumptions:__ In section 4.1.1, the authors expect that the same layers of two networks trained on the same data and differing only in the initial weights should have high structural similarity. However, the actual layer in which similar features are learned may vary, particularly in ResNets (due to their residual connections). This is a well-known phenomenon: residual connections allow networks to adapt flexibly, enabling the model to skip certain layers or distribute features across them depending on initial weights and learning dynamics. See:

[1] Veit, A., Wilber, M. J., & Belongie, S. (2016). Residual networks behave like ensembles of relatively shallow networks. Advances in neural information processing systems, 29.

Thus, instead of showing a single example result in Figure 1, the authors would make a stronger case if they (i) reported the average across multiple instances of the same networks; and (ii) used multiple architectures and datasets.

__Equation 6__: for the units of LNSA to make sense, you should take the inverse again, after computing the mean of the inverses. That's what MacKay and Ghahramani actually do -- notice the -1 power in the formulas for their estimators ($\hat{m}^{-1}$). You can also check this on the source code they provided. In their Fig. 2, the best curves are: "the inverse of the average of the inverse m-hats (orange), and our preferred maximum likelihood estimator (which is just equation (7) again."

Having said that, I don't think you should compute the individual residuals using the Lid inverses. The residuals should keep their units of "dimension". How do the authors justify this?

__GNSA:__ I see a problem with this dissimilarity in that it can produce large values if the geometry of the manifold changes but the topology stays the same. A classic example where this would happen is for the "swiss roll" dataset (https://scikit-learn.org/1.5/auto_examples/manifold/plot_swissroll.html): the GNSA value comparing the original roll and its unrolled counterpart would be very large since, although the first several nearest neighbors of a point $i$ would not change their distances much, points that are far away (following along the spiral) would become considerably farther after flattening the roll. I believe this would lead to large GNSA even though the two manifolds are topologically identical. Have the authors considered this? If they agree, I suggest a more thorough discussion on strengths and weaknesses of GNSA.

__Lack of ground truth__: I believe this study would greatly benefit from using toy datasets that provide some ground truth to verify the efficacy of the method proposed. E.g., Gaussian clusters of various dimensionalities, the 1-D spiral, the 2-D S-curve, a plane with a hole; these have been classically used in the manifold learning literature. Here are a couple examples of recent papers that use interesting toy datasets as ground truth for comparing low-dimensional embeddings and dimensionality:

[2] Wang, Yingfan, et al. (2021) "Understanding how dimension reduction tools work: an empirical approach to deciphering t-SNE, UMAP, TriMAP, and PaCMAP for data visualization." Journal of Machine Learning Research 22.201: 1-73.

[3] Dyballa, L., & Zucker, S. W. (2023). IAN: Iterated Adaptive Neighborhoods for manifold learning and dimensionality estimation. Neural Computation, 35(3), 453-524.

It would be informative to have some simple, intuitive examples that could be directly visualized in 2 or 3 dimensions. Such datasets could be perturbed in ways that _did_ change their topology and structural relationships vs. others that _did not_, the goal being to check whether the values produced by LNSA and GNSA would reflect the truth.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Why an access to the source code was not provided for reproducibility check purposes?
soundness: 2
strengths: -The paper addresses an interesting problem of constructing a reasonable measure of dissimilarity of two data representations of the same dataset. 

-Different experiments are described in order to empirically validate the method, although no source code is provided making reproducibility check difficult.
summary: The paper introduces a method (NSA) for comparing two data representations of the same dataset. NSA is a weighted sum with some tuned weights of GNSA which essentially compares the pairwise euclidian distances in the two representations of the same points, and of LNSA which is a local dissimilarity measure, based on k-NN graph. Experiments are described in order to empirically validate the expected properties of the method, although no access to the source code is provided.
weaknesses: 1.Dependence on Euclidean distance in high-dimensional spaces. NSA uses essentially the comparison of Euclidean distances as its measure of structural similarity. This choice can be suboptimal in high-dimensional spaces due to the "curse of dimensionality," which makes Euclidean distances less informative and can lead to unreliable similarity measurements.

2.An access to the source code is not provided making the paper results reproducibility check difficult.

3.Lack of universality without parameter tuning. NSA's performance across different tasks relies heavily on parameter tuning and specific integration with other loss functions.  The choice of k in the construction of k-nn graph is essential in the definition of LNSA. The weights in front of the local and global parts of NSA clearly lead to drastically different results depending on their values. 

4.No thorough guidance is provided for the choices and tuning of these hyperparameters. For example how to do 'appropriately adjusting the number of nearest neighbors considered in each mini-batch' on line 366 remains unspecified.

5.High computational complexity for large datasets. Despite claims of efficiency, NSA has a quadratic computational complexity concerning the number of data points, \( O(N^2 D + kND) \). This can become prohibitively expensive as the dataset size grows.

6.The method's focus on structural preservation might make it less effective in scenarios where functional similarity is more relevant, limiting its applicability.

7.Absence of interpretability mechanisms for practical applications. Although NSA provides a structural similarity measure, it lacks interpretability features that could make its outputs more useful in real-world applications. For instance, it does not offer insights into which specific features or dimensions contribute most to the observed structural discrepancies.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Specific comments:
* Doesn’t the computation of GNSA depend on the specific order of the point clouds? For example, comparing a_i and b_i only make sense if these below to the same datapoint, otherwise you’re comparing random elements. 
* In Sec 4.1 you claim that “a good structural similarity index should show high similarity between architecturally identical neural networks with different weight initializations”.  However, different initializations produce different models and there is no reason to assume that these should have the same structures. Also, in Figure 1 all the plots on the left are exactly the same. If this is not a typo, then I also don’t believe that the experiment shows what it is claimed. Additionally, the results here should be compared to the classical methods for comparing representations like Alaa et al, How Faithful is your Synthetic Data? Sample-level Metrics for Evaluating and Auditing Generative Models, Kynkäänniemi et al,  Improved precision and recall metric for assessing generative models, NeurIPS 2019, Poklukar et al, Delaunay Component Analysis, ICLR 2022, Khrulkov et al, Geometry score: A method for comparing generative adversarial networks, ICML 2018, etc, which are also missing from the related work.
* Please add details in 4.2.1. on how GSNA is even calculated. What is X and what is Y? 
* In Sec 4.3., I do not understand why an AE is used on top of the produced embeddings. In my view, a baseline should be the classification accuracy on the embeddings of the GCN or alternatively of a NSA-GCN trained model but not of a frozen GCN model with an AE attached to it. Also, as mentioned above, this experiment lacks comparison to any SOTA graph based methods which makes the applicability questionable.
soundness: 3
strengths: * Good background section on LID.
* Good applicability of the method.
summary: The authors introduce the Normalized Space Alignment (NSA) method for comparing two point clouds, which is based on comparing pairwise distances. The NSA consists of the local NSA, defined through the Local Intrinsic Dimensionality, and the global NSA, defined through Representational Similarity Matrices. The final NSA is defined as the weighted sum of global and local NSA. The experimental section includes experiments where NSA is used to analyze representations, as a loss in AE and for detection of adversarial attacks.
weaknesses: General concerns:
* Despite a wide range of applications presented in the experimental section, the paper lacks comparison to relevant existing methods to really showcase the efficiency. For example, in the link prediction and adversarial attacks experiments, the method should be compared to the relevant baselines from the respective fields to be able to fairly judge the efficiency of the method.
* Datasets used in the experiments are small and basic, and the generalization of the method is questionable. How does the method behave for large sets and more complicated cases?
* No ablation studies are provided. For example, the method relies on the k nearest neighbors selection and I believe that the choice of k does influence the results. No experiments are provided on the robustness of k, neither is mentioned what k is actually used in the experiments. There is also no info on the balancing parameters l and g, and no ablation studies on the influence of these.
* The definition of GNSA depends on the choice of the origin. For example, given two point clouds X and Y, the translated point clouds will have the same structure but not the same GSNA score which is problematic. Of course one could resolve this with selecting a different origin but that is not feasible in practice. 
* Figures are not well readable.

Meta-review: The authors propose normalized space alignment (NSA) as an analysis technique for neural network representations. NSA combines the global NSA (GNSA) which compares the pairwise Euclidean distances in the two representations, and local NSA (LNSA) which measures dissimilarity from k-NN graph. The proposed NSA can be applied as an analytical tool and a loss function. The authors evaluate the proposed method on various datasets for these aforementioned tasks.

Although the Reviewers think the proposed approach is interesting, the Reviewers raised concerns on the choice of Euclidean distance in GNSA (for such manifold analysis technique), sensitivity of the k-NN graph in LNSA, scalability for large datasets. The Reviewers also raised concerns on the evaluation without ground truth for manifold analysis task. Additionally, the Reviewers also question about empirical evidences on the advantages of the proposed approach in applications, it is better to compare the proposed approach with recent baselines for the corresponding tasks. Overall, we think that the submission is not ready for publication yet. The authors may consider the Reviewers' comments to improve the submission

Decision: Reject