Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a novel principled view of dimensionality reduction using probabilistic graph coupling that allows to retrieve several modern approaches such as SNE, t-SNE, UMAP and LargeVis, and more classical ones such as PCA and its kernelized variants. The 
former list of methods performs exceptionally well in identifying local dependency structure among variables at the expense of losing global structural information, identifying which has been more suited to PCA-based approaches so far. 

The main theoretical contributions of the paper are:
1) Identifying the previously mentioned approaches as special cases of a larger unifying statistical framework that is formulated using probabilistic graph coupling;
2) Providing a theoretical explanation for the unsatisfactory performance at capturing global structure of the previous neighbour embedding methods;
3) Proposing a hierachical extension for neighbour embeddings, which allows to better represent the inter-cluster structure effectively leading to a novel regularized loss function, which contains an additional penalty term with respect to the global structure. In practice, the two cross-entropy terms corresponding to the local / global structure are minimized separately with solving for the global structure first, hence this effectively leads to a new initialization called ccPCA for neighbour embeddings.

Experiments are conducted on MNIST to demonstrate the previously mentioned drawbacks of these methods, that demonstrate the value of the new initialization procedure with further experiments reported in the experiments that overall demonstrate the usefulness of the proposed initialization.
strengths_and_weaknesses: This is a very interesting theoretical paper, which sheds new light on existing dimensionality reduction techniques. The paper does a good job at citing related work in detail, and the presentation of the theory is nicely structured. Maybe one drawback is that the theory is very dense in maths, and at the same time, the paper draws from a wide range of areas (which is a benefit of course), but this makes the formulation quite difficult to follow until the end, while the experiments are mostly squeezed into the last page / appendix. Overall the paper could be interesting for a wide range of audience due to the overarching popularity of the investigated methods, but the presentation may limit the accessibility. On the experiments' side, the main empirical contribution is investigating the new theoretically motivated initialization scheme, which shows superior performance compared to previous heuristic approaches. 
questions: Suggestions:
- Some notation was left undefined (e.g. $\otimes$, $\mathcal{S}_{++}^n$, on page 7 $\mathcal{W}$) , while others were defined in a cluttered manner. My suggestion would be to have a notation paragraph at the beginning of Section 2 that readers can refer to.
- It is unfortunate that the bulk of the experiments are deferred to the Appendix, as the empirical contribution could also be useful for practitioners. I think, at least for me, it would help the reading experience to move some non-central parts of the theoretical exposition into the appendix to ease the exposition in lieu of further experiments. 

Questions:
- The authors mentioned that kernelized variants of PCA can also be recovered as part of the framework. Is this something that's implicitly included in the current theory, or is this a generalization that is left to future work?
- In the conclusion it is mentioned that the proposed framework could support hyperparameter learning for the proposed approaches, such as the bandwidth for kernel based methods. This could be quite useful as the current heuristic approaches for unsupervised learning can be quite lacking. Is this something the authors have experimented with, or if any suggested approaches could be mentioned to highlight some future work direction?

limitations: Yes.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper introduces a new dimensionality reduction technique by formulating a generative probabilistic model that can be used to describe popular techniques such as t-SNE, UMAP, etc. Specifically by, showing that they are all graph coupling with different priors for discrete latent structuring graphs. The authors present theoretical results describing the behavior of such models and also empirical results with a newly proposed initialization method. 
strengths_and_weaknesses: This paper presents an interesting view on popular dimensionality reduction techniques. Among its strengths I believe are:

* Lays foundation for analyzing and understanding dimensionality reduction with MRF lens. Shows interesting analytical insights on existing works. 
* Provides recommendations for new ways to initialize, ccPCA, which has empirical advantages in the experiments

Weaknesses of the paper include:
* Perhaps I am misguided, but when I think about dimensionality reduction, i think most about its empirical benefits and use cases. I would have expected and liked the paper to describe more about technical details of experiments and run experiments that give the reader a full sense of what kinds of datasets certain methods work well on and on what datasets they do not. 
* This could be achieved by describing properties of the datasets in ways that a practitioner could analyze about their own data. I'm also greatly curious about things like hyperparameter sensitivity and tuning, more about efficiency, scaling and the like. 
* I'm also thirsting to understand more about whether the improved performance can be traced back to parts of the improved initialization. I.e. how does initialization quality relate to end quality for points. Apologies if I have missed this.

Typos:
30 - Quotation marks
146 - edges -> edge's

Possible related work:
Bayesian Distance Clustering. Leo L Duan, David B Dunson. https://arxiv.org/abs/1810.08537
questions: * In the abstract the below statement is made. Why are probabilistic foundations required for such a full understanding? These approaches such as UMAP do have foundations with technical substance as I understand. I assume what is meant is that the kind of limitations and properties presented in this paper are not possible with with UMAP / t-SNE presentation as is.
> Though widely used, these approaches lack clear probabilistic foundations to enable a full understanding of their properties and limitations.
limitations: Yes
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Authors of this paper introduce a unifying statistical framework based on coupling of hidden graphs through pairwise MRF using cross entropy which explains several existing dimension reduction methods with respect to different graph priors. With the above framework, authors further propose to mitigate the global structure deficiency with a new initialization method called ccPCA to existing SNE-like methods.
strengths_and_weaknesses: Strengths:

1.	The shift-invariant pairwise MRF is used to model the dependency of observations, which leads to the unifying cross entropy losses with different graph priors.

2.	Various well-known and popularly used DR methods are recovered by the proposed framework.

3.	A new initialization method ccPCA to existing SNE-like methods is inspired by hierarchical graph coupling. 

Weaknesses:

1.	The discussion on the pros and cons of existing SNE-like methods covered by the proposed framework with respect to graph priors is missing.

2.	The new model motivated by the framework for balancing inter and intra structures are handled by a heuristic approach.

3.	Visual experiments with ccPCA focusing on the relative positioning of different digits using MNIST are subjective.

questions: In many places of the manuscript, authors mentioned the assumptions of theorem 1. It will be better to describe these assumptions in detail and clarify in what situations these assumptions can be satisfied.

It is interesting to see a unified probabilistic framework to cover SNE-like methods associated to different graph priors shown in section 3.1. However, the most attracting point might be even better to use the identified differences (graph priors) to analyze the pros and cons of SNE-like methods. This will provide valuable guidance for the users of SNE-like methods. Unfortunately, this type of discussion is missing.

Another direction of the unified framework is to inspire new models. Authors did this in section 4 to enrich SNE-like method by faithfully representing global structure in low dimensional space. It is expected that the new model can be addressed, but a heuristic two-step approach is used. Although the connection between PCA and the subproblem of the new model is presented, additional concerns come up too like inefficiency of Monte-Carlo estimation for W_x and suboptimality of two-step approach with early stopping as stated in the caption of Figure 2.

The experiments in section 4.3 can be improved significantly. The visual results shown on MNIST dataset are rather subjective without the true positions of different digits. Authors might conduct experiments on some simulated data with true global structure to valid the hypothesis. Moreover, the mean coordinates can be less accurate to reflect the shape of clusters due to the nonlinearity of SNE-like methods. A better way to demonstrate the differences between compared methods is preferred. 

limitations: Yes
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors define a generative probabilistic model for a dimensionality reduction (DR) problem that generalizes neighbor embedding methods such as t-SNE and UMAP. To embed the observations, X, into the embeddings, Z, their latent graph structures are coupled to be close. More specifically, the authors define conditional distributions of observations and embeddings latent graphs given associated kernel matrices on observations and embeddings respectively, and the cross-entropy between these two posteriors is minimized with respect to the embedding.

This cross-entropy objective takes various forms according to the graph priors used in observation and embedding latent graph conditional distributions; each existing neighbor embedding methods objectives corresponds to one of these forms. Since kernel matrices on observations and embeddings are shift-invariant in these methods, the relative positioning of observation clusters is not preserved in the embedding space. Then, the authors link PCA with cross-entropy objective when the Gaussian model is used as a kernel matrix which is well-defined and addresses the problem of preserving large-scale dependencies between different clusters. Furthermore, the hierarchical graph coupling is proposed to preserve the positioning of clusters, as well as their local structures, called ccPCA.

Finally, the authors perform an experiment on the MNIST dataset to demonstrate the performance of ccPCA compared to other large-scale preserving embedding methods, PCA and Laplacian eigenmaps, and the benefit of initialization of t-SNE with the embeddings from such methods.

The structure of the paper is as follows.
- The authors define a distribution P(X|W) defining the distribution of points X based on a Markov Random Field (MRF) weighted graph W. The potentials of this MRF are defined as $f(X_i,X_j) = k(X_i-X_j)^{W_{ij}}$, for a similarity kernel k. 
- The authors define several options for the prior distribution P(W). 
- The authors consider the posterior distribution P(W|X). They propose that a dimensionality reduction (DR) algorithm that converts X to Z can be understood to be optimizing X( P(W_X|X) , P(W_Z|Z) ), where X() is the cross entropy.
- The authors show how each of several existing DR methods can be expressed using this framework. 
strengths_and_weaknesses: Clarity: I found the manuscript very difficult to follow. As written, the manuscript requires significant background I lack, particularly in measure theory. This is a shame because I think these results are important and thus the interested readership of this paper could be much broader than those who can current understand it. I think this could largely be alleviated with a better Outline section (see below). As is, the outline is too brief such that I wasn't able to understand the main idea until after spending hours trying to decipher the main sections. However, apart from this, all definitions and concepts are presented in a reasonable flow and all notations are clearly defined and used in the manuscript.

Originality: The paper includes a novel statistical view on dimensionality reduction approaches that explains their degeneracy, and has the potential to modify them to capture specified features and helps more reasonable hyper-parameter tuning.

Quality: The proposed theoretical perspective for neighbor embedding methods is very strong and insightful. The connection between cross-entropy objectives and SNE-based method objectives provides an insight into their differences and applications. I was not able to check the proofs.

Significance: This novel view of dimensionality reduction methods enables proposing the solutions for preserving large-scale dependencies. These DR methods are very widely used, so the significance is high. One limitation is that this view is not very intuitive, so may or may not yield insight into how to improve these methods.

Notes:

Outline: I couldn't tell what the posterior distribution was over. What kind of mathematical objects are W_X and W_Z? How are X/Z and W_X/W_Z related? There is no mention of a similarity kernel at all. 

L30: Quote formatting errors. 

L86: I didn't understand the X_M, X_C split.

L93: Symmetric how? k(x) = k(-x)?

L100: k is overloaded as Gaussian kernel and general symmetric function. 

L102: I am assuming "integrable" on L97 refers to the fact that \int f_k (X,W) dx is finite. I am not familiar with the concept of lambda-integrable. 

L109: C_k is not defined. I'm assuming this is the partition function defined by k,W. The difference between C (connected component) and \mathcal{C} (partition function) is confusing. 

L153: What does the \sim + \models symbol denote? 


questions: In the experiments section, the similarity of cluster positioning from different methods with the PCA of cluster means is shown visually, however, the differences between them are not clear. Quantitative measures such as the similarity between clusters' distance matrices would show the goodness of methods in preserving the large-scale dependencies more clearly. 

The extension of graph laplacian to the Wishart prior for a link to PCA is not very clear. More intuition on the mentioned key difference, Wishart distribution imposes full-rank constraint, with a graph laplacian would be helpful to better understand the connection between PCA and neighbor embedding methods.
limitations: NA
review_title: null

Meta-review: metareview: This paper aims to develop a statistical framework for developing a more rigorous understanding of well known methods such as t-sne and UMAP. There was consensus among the reviewers that the proposed framework makes considerable progress in understanding the mentioned methods. 
confidence: Less certain
Decision: Accept