GrEASE: Generalizable Spectral Embedding with an Application to UMAP

Comment: The term "eigenvector separation" is unknown and undefined.

Response: The term "eigenvector separation" is a key concept in the paper and was clearly defined in lines 44-45 at the beginning of the document. Additionally, this term is used in the literature (see e.g., [1]).

Comment: I don't believe the authors claim that SE is used in GNNs and GCNs.

Response: In the paper, we support the claim that SE is used in GNNs and GCNs with citations to three papers [5]-[7]. For brevity, we summarize the use of SE in these methods: Eigen-GNN [5] integrates SE with GNNs to reduce the feature-centricity of modern GNNs and enable learning on the graph structure domain; [6] uses SE to construct globally consistent anisotropic kernels for GNNs, enabling graph convolutions based on topologically-derived directional flows; [7] utilizes SE to design fast localized GCNs.

Comment: The Grassmann Score is left completely undefined and I have no idea how one calculates it.

Response: As referred in lines 419-420, the Grassmann Score is formally define in App. D, which also includes the method for calculating GS.

Comment: I strongly disagree with the statement line 315, that the complexity is linear in the number of samples. Also, I think Fig. 2 is comparing apples and oranges.

Response: We disagree with the author's statement. Line 315 is supported by Figure 2b and a detailed discussion in Appendix C. In Appendix C, we provide a quick complexity analysis, including training time, and demonstrate that the complexity is linear with respect to the number of samples. Figure 2b includes a simple empirical experiment comparing GrEASE's complexity to non-parametric SE implementations, which also supports linear complexity. Of course, GrEASE's times account for both training and inference on all inputs. The non-parametric methods, lacking GPU support, were run on CPU with multiple jobs. The technical details (e.g., number of jobs, batch sizes, etc.) are provided in Appendix G.

Comment: if one wished to approximate the Fiedler vector, then this is a well-studied problem and there are fast methods for doing it such as [8].

Response: It seems that the cited paper only enables fast approximation of the Fiedler vector, without supporting generalization to test samples. This is a special case of the "Generalizable and Eigenvector Separation" paragraph in the Related Work section (Sec. 2). In contrast, GrEASE enables generalizable Fiedler vector approximation, as discussed in Section 4.4 and empirically demonstrated in Section 5.1.

[1] D. Pfau et. al. , “Spectral inference networks: Unifying deep and spectral learning,” ICLR, 2019.

[2] I. Gemp et. al, “Eigengame: Pca as a nash equilibrium,” ICLR, 2021.

[3] Z. Deng et. al, “Neuralef: Deconstructing kernels by deep neural networks,” ICML, 2022.

[4] Z. Chen et. al, “Specnet2: Orthogonalization-free spectral embedding by neural networks,” MSML, 2022.

[5] Z. Zhang et. al, “Eigen-gnn: A graph structure preserving plug-in for gnns,” IEEE, 2021.

[6] D. Beaini et. al, “Directional graph networks,” ICML, 2021.

[7] M. Defferrard et. al, “Convolutional neural networks on graphs with fast localized spectral filtering,” NeurIPS, 2016.

[8] P. Macgregor, “Fast and simple spectral clustering in theory and practice,” NeurIPS, 2023.

Thank you for finding our work's goal important and relevant, and encouraging the use of our proposed evaluation metric - Grassmann Score. We address you concerns below.

Questions

Comment 1: What happens if we use SpectralNet outputs as the input to Parametric UMAP (rather than GrEASE outputs)? I suspect that this will perform equivalently to NUMAP and would require thorough, reproducible experiments to convince me otherwise. If SpectralNet and GrEASE perform the same as an input to UMAP, this would contradict the primary motivation of the paper that the eigenvector separation is indeed necessary.

Response: NUMAP heavily relies on GrEASE's ability to output the separated eigenvectors. A key architectural feature of NUMAP is the residual connections, which bias the NUMAP embeddings to stay close to the 2-dimensional SE. The second step of NUMAP involves learning the embedding from the $\ell$-dimensional SE ($\ell > 2$). GrEASE plays a crucial role in enabling the effective use of these residual connections, as without it, NUMAP embeddings would not be biased toward preserving the graph's global structure.

Comment 2: How do GrEASE and SpectralNet outputs differ? How do they compare to standard Laplacian Eigenmaps/spectral embeddings?

Response: This is extensively shown in Sec. 5.

Comment 3: How does GrEASE help in getting generalizable diffusion maps? This is completely unclear to me.

Response: GrEASE enables the output of both eigenvalues and eigenvectors, which is not possible with SpectralNet. This allows for the multiplication of each eigenvector by its corresponding eigenvalue, resulting in the Diffusion Maps embedding.

Weaknesses

Comment: Unless I am missing something, this paper's primary technical contribution is to apply a change-of-basis to the output of SpectralNet. I fail to see how the eigenvector separation is cause for any concern, and why this is something that need to be remedied.

Response: Eigenvector separation (achieved by the change-of-basis operation) is crucial for various applications of SE, such as the Fiedler vector, eigenvalues approximation, and Diffusion Maps, which are discussed in Section 4.4. Specifically, we focus on SE application to visualization, via NUMAP. NUMAP relies substantially on the eigenvectors separation for its residual connections, which are designed to bias NUMAP embeddings towards the 2-dimensional SE (learned from $\ell$-dimensional SE). Previous works have explored (infeasible) solutions to the eigenvector separation challenge (e.g., [1]-[4]).

Additionally, change of basis is the key of many important algorithms in machine learning (e.g., PCA, CCA, Fourier transform, Wavelet transform). Solving the eigenvector separation problem is, by definition, a change of basis operation. Hence, we disagree with the reviewer claim that a change-of-basis is not enough of a contribution.

Comment: The authors used Grassmann Score to measure distance between the Laplacian vectors and the identified vectors.

Response: We would like to emphasize that the Grassmann Score is not intended to evaluate the quality of eigenvector separation and was not used or presented as such in the paper. Instead, the Grassmann Score is suitable for assessing graph-based dimensionality reduction methods, where the objective is to preserve the graphical structure of the representations.

Thank you for finding our work extensive and promising for future work to rely on. We address you concerns below.

Questions

Comment 1: Why is outputting the basis relevant? The authors give a few citations, but it would be good to highlight that in their own words.

Response: Eigenvector separation is crucial for various applications of SE, such as the Fiedler vector, eigenvalues approximation, and Diffusion Maps, which are discussed in Section 4.4. Specifically, we focus on SE application to visualization, via NUMAP. NUMAP relies substantially on the eigenvectors separation for its residual connections, which are designed to bias NUMAP embeddings towards the 2-dimensional SE (learned from $\ell$-dimensional SE). Previous works have explored (infeasible) solutions to the eigenvector separation challenge (e.g., [1]-[4]).

Comment 2: Why are the visualizations in 5b only compared to parametric UMAP? It would be good to see how other approaches fare on the data.

Response: As of today, UMAP is the most popular visualization technique, and thus it serves as our baseline. The only parametric version of UMAP we are familiar with is Parametric UMAP, which we use for comparison with NUMAP.

Comment 3: Please make sure that the scatter plot visualizations have a 1:1 aspect ratio. They look very distorted in e.g. Fig. 7, I am unsure whether this is then also distorted in the main body figures.

Response: This is only relevant to Fig. 7. Thank you for pointing this out.

Comment 4: The embeddings in Fig. 4 are not labeled.

Response: Fig. 4 is dedicated to understanding of Grassmann Score (GS). Specifically, it compares four embeddings using KNN, Silhouette and GS. The embedding methods used to create these embedding are not relevant to the analysis.

Comment 5: Since the authors talk a lot about scalability, it would be nice to see some large-scale real-world datasets

Response: We present results on relatively large-scale datasets (CIFAR10 and KMNIST) in Sec. 5.1, where computing the ground-truth SE is feasible. Additionally, we conduct a scalability experiment in Sec. 5.2 to assess the runtime performance on large-scale datasets.

Comment 6: What is meant by UMAPs contrastive loss (l. 343)? UMAP uses a binary cross-entropy loss.

Response: We view binary cross-entropy loss as a contrastive loss, in the sense that it aims to bring paired points closer while pushing other random points apart. That is, for instance, different from the SE objective, which seeks to bring similar points closer while enforcing identity covariance.

Comment 7: It would be good to make the evaluation more consistent. Sometimes only GS and kNN are reported, and sometimes the silhouette score. It would be beneficial to include all of the metrics and summarize them in one place.

Response: The evaluation metrics used are KNN and GS, which are summarized in Tab. 1. The Silhouette scores are included in Fig. 4 solely to highlight its insufficiency in capturing global structure preservation in dimensionality reduction.

Weaknesses

Comment: It is unclear how NUMAP can have more scalability than parametric UMAP (which only does the first part), which the authors claim in their introduction.

Response: First, we did not claim that NUMAP can have more scalability than P. UMAP. However, it is important to note that their scalability is comparable, in the sense that there is no dataset size that Parametric UMAP can handle which NUMAP cannot.

Comment: The choice of using the Grassmann score seems unusual. Why are other approaches like correlation between high-dimensional and low-dimensional points not considered?

Response: We are not familiar with this evaluation metric and are unsure of its meaning or how it is computed. As discussed in detail in Section 4.5, we used the Grassmann Score because popular evaluation metrics (e.g., kNN and Silhouette) fail to capture global structure preservation, whereas the Grassmann Score does.

[1] D. Pfau et. al. , “Spectral inference networks: Unifying deep and spectral learning,” ICLR, 2019.

[2] I. Gemp et. al, “Eigengame: Pca as a nash equilibrium,” ICLR, 2021.

[3] Z. Deng et. al, “Neuralef: Deconstructing kernels by deep neural networks,” ICML, 2022.

[4] Z. Chen et. al, “Specnet2: Orthogonalization-free spectral embedding by neural networks,” MSML, 2022.

Thank you for finding our work creative and rigorous, and encouraging the use of our proposed evaluation metric - Grassmann Score. We address you concerns below.

Comment 1: Minimising $R_L(U)$ is actually a Grassmann manifold optimization problem. The paper could elaborates on this further. Lemma 1 is in fact an explicit fact on the Grassman manifold.

Response: Thank you for the reference. Lemma 1 is a key part of the motivation behind our approach, and for the sake of conciseness, we provide our own proof.

Comment 2: Between Line 249 and 251, not sure why suddenly talk about Laplace-Beltrami operator. In the paper context, Laplacian matrix is sufficient enough.

Response: The Laplace-Beltrami operator gives rise to the generalization of spectral embedding (SE). Specifically, the out-of-sample extension we seek corresponds to the leading eigenfunctions of the Laplace-Beltrami operator. While the Laplacian matrix operates solely on the training samples, the Laplace-Beltrami operator acts on the manifold (the distribution), allowing us to extend beyond the given matrix.

Comment 3: In line 262, can you please more specifc on the meaning of "it becomes apparent that the SE was seldom attained."?

Response: As defined in lines 172-173, the SE is the basis of the leading eigenvectors of the corresponding Laplacian matrix. Let us focus on the bottom-right histogram in Fig. 2a, which shows the distances between the true 3rd eigenvector and the predictions from SpectralNet and GrEASE. While GrEASE consistently achieves near-zero distances to the ground truth (left bin), SpectralNet does not - its distances are spread across the entire range from 0 to 1.

Comment 4: I would like to see an exact definition of the separation of the eigenvectors.

Response: See lines 44-45.

Comment 5: In line 294, why you say "Q is a property of ..."?

Response: $Q$ is manifested through the parameters of the trained network. Namely, assuming convergence to global minima, $F_{\theta}(x_i) = v_iQ$ for all $1\leq i \leq n$, where $v_i$ is the $i$th row of $V$.

Comment 6: Line 298: Can you give a proof that the eigenvalues of $\tilde{\Lambda}$ are the eigenvalues of L", particularly when $\tilde{\Lambda}$ comes from the average of batch operations?

Response: The proof is immediate from the equation in the bottom of page 5, by definition of $\tilde{\Lambda}$. We cannot guarantee the convergence of the average of batches. However, assuming convergence to global minima, $F_{\theta}(x_i) = v_iQ$ for all $1\leq i \leq n$, where $v_i$ is the $i$th row of $V$. That is, computing $\tilde{\Lambda}$ on a single sample would be sufficient. Since global convergence does not occur in practice, we average over multiple batches to mitigate the noise. Our experiments demonstrate the effectiveness of this method.

Comment 7: Can algorithm 2 be moved into the main text?

Response: Due to space limitations, we place Alg. 2 in the appendix.

Comment 8: In Algorithm 1 (line 754), which Sec. 3.2. I did not find out loss function.

Response: The loss function is the Rayleigh Quotient, as defined in the Sec 3.2. For brevity, we will add there the loss explicitly: $L_{\text{spectralnet}}(X, \theta) = \frac{1}{m^2}R_L\big(F_{\theta}(X)\big)$.

Comment 9: Algorithm 2 is not clearly defined. After getting Q, how is this converted to the algorithm output $F_{\theta}$? Do you mean $F_{\theta} = VQ$, while V comes from the network output?

Response: This is explained in lines 309-311. We will add it to algorithm 2. The idea is that we obtain $F_{\theta}$, which, assuming convergence to global minima, satisfies $F_{\theta}(X) = VQ$. After computing $Q^T$, we can multiply these representations by $Q^T$ to get the SE $F_{\theta}(X)Q^T = VQQ^T = V$

Thank you for your review. We address you concerns below.

Comment 1: As shown in introduction, the main contribution seems to add the post-processing step of the SpectralNet. It still needs to rely on SpectralNet to solve the generalizability and scalability problems. Although it can be extended to UMAP, the contribution is not enough.

Response: As outlined in the introduction, our two primary contributions are (1) a significant post-processing procedure and (2) NUMAP, a novel extension of GrEASE to UMAP visualization. We would like to re-emphasize the importance of eigenvector separation in GrEASE, as it underpins various SE applications. For instance, in Section 4.4, we discuss applications like the Fiedler vector, eigenvalues approximation, and Diffusion Maps. In our work, we focus particularly on the application of SE for visualization, which is achieved through NUMAP. NUMAP relies substantially on the eigenvectors separation for its residual connections, which are designed to bias NUMAP embeddings towards the 2-dimensional SE (learned from $\ell$-dimensional SE). Previous works have explored (infeasible) solutions to the eigenvector separation challenge (e.g., [1]-[4]).

Comment 2: The spectral embedding is a representation learning method. Thus, the authors could discuss the extension of the proposed method on main representation learning such as GNN or transformer.

Response: GNNs and transformers represent specific examples within the broad range of SE applications, and we see these as promising directions for future research. In this work, however, we focused on the UMAP extension of SE, and thoroughly presented NUMAP.

Comment 3: In section 4.1, what are matrix Q and V? What is the dimension of V? Is it a QR decomposition of U? The authors should discuss this equation and motivation in more detail.

Response: The matrices are clearly defined in the section (see lines 220 and 224), and we restate them here for clarity: given $n$ samples, $V\in\mathbb{R}^{n\times k}$ is the matrix constructed of the first $k$ eigenvectors of the Laplacian, $Q\in\mathbb{R}^{k\times k}$ is an arbitrary orthogonal matrix, and $U := VQ$ is an arbitrary rotation of $V$ (i.e., different from $V$, but its columns span the same space).

Comment 4: In section 4.2, why does the proposed method solve the k+1 eigenfunctions at first, instead of directly solving k eigenfunctions?

Response: As explained in the Sec. 3 (lines 172-173), SE is defined by the leading eigenvectors (i.e., excluding the first trivial eigenvector). Thus, GrEASE first computes the space spanned by the first $k+1$ eigenvectors, and the excludes the first, thereby outputting the leading $k$. SpectralNet, in contrast, lacks this capability.

Comment 5: In line 453, what is the true vector? And how to obtain them for evaluation?

Response: The "true vector" refers to the eigenvector computed using a well-studied non-parametric method (specifically, we used LOBPCG [5]), and used as the ground truth. These are used as baselines, although they lack the generalization capabilities.

Comment 6: The representation learning method generally is evaluated on downstream tasks. Thus, the authors should add experiments about this like SpectralNet evaluated on clustering.

Response: We focus on the downstream task of visualization, and present experiments on the UMAP extension in Sec. 5.3.

Comment 7: In Table 4, the batch size is so large. Thus, I'm concerned about the stability of the model. The authors should analyze this convergence.

Response: This approach is standard in graph-based methods (e.g., [6]), as the batches must be representative. It is well-established that this does not affect the scalability or convergence of the method.

Comment 8: There are some typo errors including missing definitions of the symbols and missing sequence numbers of the equations.

Response: Thank you for pointing this out.

[1] D. Pfau et. al. , “Spectral inference networks: Unifying deep and spectral learning,” ICLR, 2019.

[2] I. Gemp et. al, “Eigengame: Pca as a nash equilibrium,” ICLR, 2021.

[3] Z. Deng et. al, “Neuralef: Deconstructing kernels by deep neural networks,” ICML, 2022.

[4] Z. Chen et. al, “Specnet2: Orthogonalization-free spectral embedding by neural networks,” MSML, 2022.

[5] P. Benner and T. Mach, “Locally optimal block preconditioned conjugate gradient method for hierarchical matrices,” PAMM, 2011.

[6] U. Shaham et. al, “Spectralnet: Spectral clustering using deep neural networks,”, ICLR, 2018.