A Probabilistic Graph Coupling View of Dimension Reduction
Authors: Hugues Van Assel
Thibault Espinasse
Julien Chiquet
Franck Picard
Venue: NeurIPS 2022 Accept (2022)
Keywords: Dimension Reduction
Graphical Models
Random Graphs

Abstract: Most popular dimension reduction (DR) methods like t-SNE and UMAP are based on minimizing a cost between input and latent pairwise similarities. Though widely used, these approaches lack clear probabilistic foundations to enable a full understanding of their properties and limitations. To that extent, we introduce a unifying statistical framework based on the coupling of hidden graphs using cross entropy. These graphs induce a Markov random field dependency structure among the observations in both input and latent spaces. We show that existing pairwise similarity DR methods can be retrieved from our framework with particular choices of priors for the graphs. Moreover this reveals that these methods relying on shift-invariant kernels suffer from a statistical degeneracy that explains poor performances in conserving coarse-grain dependencies. New links are drawn with PCA which appears as a non-degenerate graph coupling model.

A Probabilistic Graph Coupling View of Dimension Reduction
Hugues Van Assel UMPA
Thibault Espinasse
Institut Camille Jordan Lyon
ENS Lyon
Inria Dracula espinasse@math univ-lyon1.
hugues van_ aew_aasseeeesssy
Julien Chiquet Agro INRAE
Franck Picard
LBMC, CNRS
ENS Lyon
julien. culien..hh.quet@nnaa.fff
franck. Tranck.picardenn--lynn.
Abstract
Most popular dimension reduction (DR) methods like t-SNE and UMAP are based on minimizing cost between input and latent pairwise similaritics. Though widely used, these approaches lack clear probabilistic foundations to enable a full understanding of their properties and limitations. To that exlent, we introduce a unifying statistical framework based on the coupling of hidden graphs using cross entropy. These graphs induce Markov random field dependency structure among the observations both input and latent spaces. We show that existing pairwise similarity DR methods retrieved from our framework with particular choices priors for the graphs. Morcover this reveals that these methods relying shift-invariant kernels suffer from a statistical degeneracy that explains poor performances in conserving coatse-grain dependencies. New links drawn with PCA which appears as a non-degenerate graph coupling model.
be
Introduction
Dimensionality reduction (DR) is of central importance when dealing with high- sigh-dimensional data 16 It mitigates the curse of dimensionality, allowing for greater statistical flexibility and less computational complexity. DR also enables visualization that can be of great practical interest for understanding and interpreting the structure of large datasets. Most seminal approaches include Principal Component Analysis (PCA) B1 multidimensionnll scaling 28 and more broadly kernel eigenmaps methods such as Isomap 4 Taplacian eigenmaps 5 and diffusion maps [2] These methods share the definition of pairwise similarity kernel that assigns a high value to close neighbors and the resolution of a spectral problem. They are well understood and unified in the kernel PCA framework [[6]]
In the past docade, the field has witnessed a major shift with the emergence of new class of methods. They are also based on pairwise similarities but these are not converted into inner products. Instead, they define pairwise similarity functions in both input and latent spaces and optimize a cost. between the two. Among such methods, the Stochastic Neighbor Embedding (SNE) algorithm [X its heavy-tailed symmetrized version t-SNE 8N or more recent approaches like LargeVis 3C and UMAP 30 are arguably the most used in practice. These will be referred to as SNE-like or neighbor embedding methods in what follows. They are increasingly popular and now considered as the state-of-art techniques in many fields
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

Their popularity is mainly due to their exceptional ability to preserve local structure, i.e. close points in the imput space have close embeddings, as shown empirically
27 19 11
They also demonstrate impressive performances in identifying clusters 3 20 However this is done at the expense of global structure, that these methods struggle in preserving 1
10
e.e. the relative large-scale distances between embedded points do not necessarily correspond to the original ones.
Due to a lack of clear probabilistic foundations, these properties remain mostly empirical. This gap between theory and practice detrimental as practitioners may rely on strategics that are not optimal for their use case. While recent software developments are making these methods more scalable X well-established probabilistic framework is becoming more prominent. In this work we define the generative probabilistic model that encompasses current embedding methods, while establishing new links with the well-sstallsheed PCA model.
3% 2 and further expanding their use, the need for
Outline. Consider X -X,,,.., TT) E R=xx, an input datasct that consists n vectors of dimension p. Our task is to embed X in lower dimensional space of dimension q < p (typically q = 2 for visualization), and we denote by - (2,,.., Zn) E Raxq the unknown embeddings. The rationale of framework is suppose that the observations X and Z are structured by two latent graphs with Wx and Wz standing for their 7-Square weight matrices. As the goal of DR propose to find the best low-dimensional representation Z of X such that Wx and Wz are close. To build a flexible and robust probabilistic framework, we consider random graphs distributed according to some predefined prior distributions. Our objective is to match the posterior distributions Wx and Wz. Note that as they share the same dimensionality the latter graphs can be casily compared unlike X and Z. The coupling is done with cross entropy critcrion, the minimization of which will be referred to as graph coupling.
preserve the input's structure in the latent space,
In this work, our main contributions are as follows.
We show that SNE, t-SNE, LargeVis and UMAP are all instances of graph coupling and characterized by different choices of prior for discrete latent structuring graphs (section 3) We demonstrate that such graphs essentially capture conditional inde- pendencies among rows through pairwise Markov Random Field (MRF) model which construction can be found in section 2
We uncover the intrinsic probabilistic property explaining why such methods perform poorly on conserving the large scale structure of the data a consequence of degeneracy of the MRF when shift invariant kernels are used (theorem D. Such degeneracy induces the loss of the relative positions of clusters corresponding to the connected components of the posterior latent graphs which distributions are identified (proposition D These findings are highlighted by new initialization of the embeddings that is empirically tested (section
We show that for Gaussian MRFs, when adapting graph coupling to precision matrices with suitable priors, PCA appears as a natural extension the coupling problem in its continuous version (theorem 2 Such model does not sulfer from the aforementioned degeneracy hence preserves the large-scale structure.
2 Shift-Invariant Pairwise MRF to Model Row Dependencies
We start by defining the distribution of the observations given graph. The latter takes the form a pairwise MRF model which as we show is improper (i.e. not integrable on xT*P) when shift-invariant kernels used. We consider fixed directed graph W Sw where:
Sw W Nax" (V(,)) E in] W. 0, WiJ S n)
Throughout, (F, F), Ag) denotes a measure space where B(F) is the Borel o-algebra on E and Äg is the Lebesgue measure on E.

---

2.1 Graph Laplacian Null Space
A central element in our construction is the graph Laplacian linear map, defined as follows, where S (R) is the set of positive semidefinite matrices.
Definition 1
The graph. Laplaciann operalor is the map L: 1 S4 (TR)
such that
WWa Exem Wa otherwise.
fi
for (i.5) E [m]?: L(W)
With an abuse of notation, let L L(W) where W w + WT. Let (C,, CR) be a partition of [n] (i.e. the set (1,2,...,1)) corresponding to the connected components (CCs) of W. As well known in spectral graph theory 1 the null space of L is spanned by the orthonormal vectors {Ur)re(m such that for r E [R], U, = (nr nr 1/2 LiEE,)
with iE|n]
n, n- = C., By the spectral theorem, Ung can be completed such that = UAUT where U = (UI,... Un) is orthogonal and A = diig((AA))e(n))) with 0 = X1 =
XR < AR+1 S ... S An. Tn the following, the data split into two parts: XM, the orthogonal projection of X on Sy (ker L) 6 R2, and Xc, the projection on Se = (ker L)* @ R2. For E [n], XM, = Er n, Lic, Exec, X₁ hence Xxr stands for the empirical means of X on CCs, thus modelling the CC positions, while X = X X is CC-wise centered, thus modeling the relative positions of the nodes within CCs. We now introduce the probability distribution of these variables.
2.2 Pairwise MRF and Shift-Invariances
In this work, the dependency structure among rows of the data is governed by a graph. The strength of the connection between two nodes given by a symmotric function k: R R+. We consider the following pairwise MRF unnormalized density function:
fx: (X, W)
II k(X, (x) (i.E
(1)
As we will see shortly, the above is at the heart of DR methods based on pairwise similarities. Note that as measures the similarity between couples of samples, fa will take high values if the rows of X vary smoothly on the graph W. Thus we can expect X; and X, to be close if there an edge between node i and node j in W. A key remark is that f& is kept invariant by translating XN. Namely for all X E R"xr, fa(X, W) fa (Xe, W). This invariance results in [a W) being non integrable on Rnxp, as we see with the following example.
Gaussian kernel. For a positive definite matrix Σ E S + (R), consider the Gaussian kernel k x e |لاl where Σ stands for the covariance among columns. One has:
log
= Σ W 1 = tr
(2)
(1)))(()²
by property of the graph Laplacian (definition D In this case, it is clear that due to the rank deficiency of L, fa(,, W) is only -sttentere In general DR settings one does not want to rely on Gaussian kernels only. A striking example is the use of the Student kernel in t-SNE RX Heavy-tailed kernels appear useful when the dimension of the embeddings is smaller than the intrinsic dimension of the data 20. Our contribution provides flexibility by extending the previous result to large class of kernels, stated in the following theorem.
Theorem 1 If k is Age Agv-intogelble and bounded above Xpy almostt everywhere then sa(, Aso- -integrable.
We refer to appendix where Cs (W) - fu(
A.I for the proof. We can now define a distribution on (Sc, B(Se))
W
JdSsa:
Pa(dX: ( ()dss(dXe)
(3)
3

---

Remark 1 Kernels may have node-specific bandwidths т, set during a pre-processing step, giving (X, W) =I k((x; ; Was, Note that such bandwidth does not affect the degeneracy of the distribution and theorem still holds.
Between-Rows Dependency Structure. By symmetry of k, reindexing gives: (x, W) [[ Histg (xx,-,,)",,, Hence distribution boils down to a pair- wise MRF model I with respect to the undirected graph W, C. playing the role of the partition function. Note that since f* (Equation D trivially factorize according to the cliques of W, the Hammersley- Clifford theorem ensures that the rows of X satisfy the local and global Markov properties with respect to W.
2.3 Uninformative Model for CC-wise Means
We showed that the MRF ① is only integrable on Sc, the definition of which depends on the connectivity structure of W. As we now demonstrate, the latter MRF can be seen as a limit of proper distributions on guxp, see e.g. 35 for a similar construction in the Gaussian case. We introduce the Borel function ( W): R
R2 for s > 0 such that for all X RR*x, fx(X, W) (x ar W). To allow fe to become arbitrarily hon-informative, we assume that for all W E Sw, (...) is -ittogrbeeee for all E E R2 and ( W) + almost
e->
everywhere. We now define the conditional distribution on (S B(S,)) as follows:
(W) = ((W))"((Xx,,. W)As, (dXMr)
(4)
where (W) f f(, W Widd Swr With this at hand, the joint conditional is defined as the product measure of 3 and 4 over the row axis, the integrability of which is ensured by the Fubini-Tonelli theorem. In the following we will use the compact notation CE(W) = CC for the joint normalizing constant.
Remark At the limát - O the above construction amounts to setting infinite variance on the distribution of the empirical means of X on CCs, thas loosing the inter-CC structure.
As an illustration, one can structure the CCs' relative positions according to Gaussian model with positive definite precision c0 E Sh (R), as it amounts to choosing f X
exp (- tr (E- X OU x)) such that: vee( (Xx)) ~ N N(,0 (EU A OU - 8 E where @ denotes the Kronecker product.
3 Graph Coupling as Unified Objective for Pairwise Similarity Methods
In this section, show that neighbor embedding methods can be recovered in the presented framework. They are obtained, for particular choices of graph priors, at the limit E + 0 when fcr becomes non informative and the CCs' relative positions are lost.
We now turn to the priors for W. Our methodology is similar that of constructing conjugate priors for distributions in the exponential family 34, notably we insert the cumulant function CE (i.e. normalizing constant of the conditional) as multivariate term of the prior. We consider different forms: binary (B), unitary out-degree (D) and n-edges (E), relying on an additional term (2) to constraint the topology of the graph. For a matrix A, Ai+ denotes E, Aij and A_ denotes Enj Aij. In the following, π plays the role of the edge's prior. The latter can be leveraged to incorporate some additional information about the dependency structure, for instance when a net work is observed 26
Definition Let π E R7X" E R4, a R, lo satisfies the assumptions of theorem and PE E,E For W E Sw we introduce:
(W; x ( (W(W)
II
W.
Tj
(1.])[n]]
where (o( =11, 1wys (w(W) II, = and 2g W) = lw =n II, (Wiy!)-1

---

When a = O, the above no longer depends on and k. We will use the compact notation Pr(W; π)) & : 0). Note that by W :T) we have the following simple Bernoulli (B) and multinomial (M) distributions, where matrix vector division is be understood as element-wise.
If P = = B, v(t,5) E [n| Wij A (Tty + m,))))
If = e [n], W, A
P = E, w M (n, क //
We now show that the posterior distribution of the graph given the observations takes simple form when the distribution of CC empirical means Xa diffusee i.e. when é - (a proof of the following result can be found in appendix A.2 In the following, @ stands for the Hadamard product and D for the convergence in distribution.
Proposition
Let E = & satisfies the assumplions of theorem with Kx = (k(X; (i))eE and P E (B, FJ. If W ( (,; then
W X Pp(:: Kx).
Remark For all W Sw, C (W) diveryes as + 0, hence the graph prior (definition is improper at the lémit. This compensates for the uninformative diffuse conditional and allows retrieve well-defined tractable posterior limit.
3.1 Retrieving Well Known DR Methods
We now provide a unified view of neighbor embedding objectives as a coupling between graph posterior distributions. To that extent we derive the cross entropy associated with the various graph priors at hand. In what follows, kg and k2 salisfy the assumptions of theorem | and denote by Kx and Kg the associated kernel matrices both graph priors we consider the parameters π = 1 and = 1. For (Px. Pz) E D.E, we introduce the cross entropy between the limit posteriors at - 0,
X and Z respectively. For
Herr, -P. (=Kxx) [log
[log P., (Wz Wx: Kz)]
defining a coupling criterion to be optimized with respect embedding coordinates Z. We now through each couple (Px, P2) such that supp (Px)) ) C supp (Pr,, for the cross-cntropy to be defined.
SNE. When Px = Py = D, the probability of the limit posterior graphs factorizes over the nodes and the cross-entropy between limit posteriors takes the form of the objective of SNE 17, where for E [n], P. = Kxi/Kx,tt and Q Kz,ú/ K Kz,t
Ho, = Σ p log Q
Symmetric-SNE. Choosing Px = D and Pz = E, define for (i,j) [n] Q
K2,j/KK,,t and PhP P.P + PP. The symmetry of QE yiclds:
Ha Σ Pg log Q
Σ P" O
and the symmetrized ivjective of 1-SNE
RN is recovered.
LargeVis. Now choosing Px D and Pz B, can also notice that Q8 (Kz + Kz ().s))) is symmetric. With this at hand the limit cross-entropy reads
HD.B - P log O + +(1 (1-P))) log (1 2
Σ P log Q +
P??) log Q
which is the objective of LargeVis 30
5

---

Table 1: Prior distributions for Wx and W associated with the pairwise similarity coupling DR algorithms. Grey-colored boxes are such that the cross-entropy undefined.
P2
P
B
D
B
UMAP
LARGEVIS
SNE
T-SNE
UMAP. Let us take Px = P2 = B and consider the symmetric thresholded graph
Wx Wx 212 By independence of the edges, Wx,s B [ where P
p + P - P f and p = (Kx,) Kx (x.)))(( Coupling Wx and We gives:
H B. = - Σ
PB log Q + (1 13
PD log 2
which is the loss function considered in UMAP 30 the construction of Wx being borrowed from section 3.1 of the paper.
Remark One can also consider HE,E F but as delailed in B8), this crilerion fails al posi- lioning oulliers and is therefore not considered. Interestingly, any other feasible combinalion of the presented priors relates to an existing method.
3.2 Interpretations
As we have seen in section 3.1 SNE-like methods can all be derived from the graph coupling framework. What characterizes cach of them is the choice of priors considered for the latent structuring graphs. To the best of our knowledge, the presenled framework the first that manages to unify all these DR algorithms. Such framework opens many perspect ives for improving upon current practices as we discuss section and section We now focus on few insights that our work provides about the empirical performances of these methods.
Repulsion & Attraction. Decomposing Her.r with Bayes' rule and simplifying constant terms one has the following optimization problem:
min ZEReXq
Σ
P. log (Z 2₁) log P(Z).
(15))(m]²
The first and second terms in eq. respectively summarize the attractive and repulsive forces of the objective. Recall from proposition [ that p the posterior expectation of W.. Hence in SNE-like methods, the attractive forces resume to pairwise MRF log likelihood with respect to graph posterior expectation given X. For instance k2 is the Gaussian kernel, this attractive term reads tr (Z L'Z) where L = Ew-P,, (: x | [L(W),, boiling down the objective of Laplacian eigenmaps the attractive forces resume to an unconstrained Laplacian eigenmaps objective. Such link, already noted in [7, easily unveiled in our framework. Moreover, one can notice that only this attractive term depends on X as the repulsion is given by the marginal term in 5 The latter reads PP IP(Z) E IP(Z, W) with P(Z, W) fa(Z, W)Z,, (W). Such penalty notably prevents a trivial solution, as 0, like any constant vector, a mode of fx W) for all W. Also note that the prior for Wx only conditions attraction while the prior for Wz only affects repulsion. In the present work we focus solely on deciphering the probabilistic model that accounts for neighbor embedding loss functions and refer to for quantitative study of attraction and repulsion in those methods.
5 Therefore, for Gaussian MRFs,
Global Structure Preservation. To gain intuition, consider that Wx is observed. As we showed in section 2.2 when one relies on shift invariant kernels, the positions of the CC means are taken from diffuse distribution. Since the above methods are all derived

---

from the limit posteriors at E - 0, XM and ZN have no influence on the coupling objective. Hence if two nodes belong to different CCs, their low dimensional pairwise distance will likely not be faithful. We can expect this phenomenon to persist when the expectation Wx is considered, especially when clusters are well distinguishable in X. This observation is central to understand the large scale deficiency of these methods. Note that this happens at the benefit of the local structure which is faithfully represented in low dimension, as discussed in section II In the following section we propose to mitigate the global structure deficiency with non-degenerate MRF models.
4 Towards Capturing Large-Scale Dependencies
In this section, we investigate the ability of graph coupling to faithfully represent global structure in low dimension. To gain intuition on the case where the distribution induced by the graph is not degenerate, we consider proper Gaussian graph coupling model and show its equivalence with PCA. We then provide a new initialization procedure alleviate the large scale deficiency of graph coupling when degenerate MRFs are used.
4.1 PCA as Graph Coupling
As we argue that the inability of SNE-like methods to reproduce the coarse-grain dependencies of the input in the latent space due to the degeneracy of the conditional (3). a natural solution would be to consider graphical models that are well defined and integrable on the entire definition spaces of X and Z. For simplicity, we consider the Gaussian model and leave the extension to other kernels for future works. Note that in this case integrability translates into the precision matrix being full-rank. As we see with the following, the natural extension of our framework to such models leads to well-established PCA algorithm. In the following, for a continuous variable 22, P(Oz = denotes its density.
Theorem 2 Let v 2 θx W(v, In) and θ ~ W(r p- q, In). Assume that Ox and O₂ structure the rows of respectively X and Z such that:
vec( (o(X) ~ NO O & Ip).
(6)
vee 2 0 N (0, 0z' @ lg)
(7)
Then the solution of the precision coupling problem:
min Ex [log P(O2 O Z)]
ZER
is PCA embedding of X with q components.
We now highlight the parallels with the previous construction done for neighbor embedding methods. First note that the multivariate Gaussian with full-rank precision is inherently pairwise MRF 35. When choosing the Gaussian kernel for neighbor embedding methods, we saw that the graph Laplacian Lx of Wx was playing the role of the among-row precision matrix, as we had X X|Wx ~ No L @ I)) (cquation 2p Rocall that the later always has a mull-space which is spanned by the CC indicator vectors of W (section 2.1 Here, the key difference that we impose full-rank constraint on the prccision O Concerning the priors, we choose the ones that are conjugate to the conditionals ( and 77,, as previously done when constructing the prior for neighbor embedding methods (definition 2 Hence in the full-rank setting, the prior simply amounts to Wishart distribution denoted by W.
The above theorem further highlights the flexibility and generality of the graph coupling framework. Unlike usual constructions of PCA or probabilistic PCA 37, in the above the linear relation between X and Z is recovered by solving the graph coupling problem and not explicitly stated beforchand. To the best of our knowledge, it is the first time such a link is uncovered between PCA and SNE-like methods. In contrast with the latter, PCA is well-known for its ability to preserve global structure while being significantly less efficient al identifying clusters [2] Therefore, as suspected in section 3.2 the degeneracy of the conditional distribution given the graph is key to determine the distance preservation properties of the embeddings. We propose section 4.2 to combine both graph coupling approaches to strike balance between global and local structure preservation.

---

4.2 Hierarchical Graph Coupling
The goal of this section is to show that global structure in SNE-like embeddings can be improved by structuring the CCs' positions. We consider the following hierarchical model for X, where Px= D, be satisfies the assumptions of theorem and Px 2 n:
Wx P
(: 11,,), xx ~ W(ux, Ix)
P. k.
WX ( [W), vec(Xx,)) N ( & 1p)
where Un are the cigenvectors associated to the Laplacian mull-space of W x- Given graph Wx, the idea is to structure the CCs' relative positions with a full-rank Gaussian model. The same model is considered for Wz, O2 and Z, choosing V/2 = Vx + q for the Wishart prior to satisfy the assumption of theorem 2 With this in place, we aim at providing a complete coupling objective, matching the pairs (Wx, Ox) and (Wz, z, Oz). The joint negalive cross-entropy can be decomposed as follows:
E ex) [log PPW2. θ2) = (Wx. xx) Z]]
wx log P(W, x 2 +
(8)
E Ox) x logg P( x W2 Wx. Z)
(9)
where 18 the usual coupling criterion of Wx and Wz capturing intra-CC variability while 19 is penalty resulting from the Gaussian structure on Sn Constructed as such, the above objective allows a trade-of between local and global structure preservation. Following current trends in DR [21, we propose to take care of the global structure first i.e. focusing on ( before 1 The difficulty of dealing with (9) lies the hierarchical construction of the graph and the Gaussian precision (see fig. We state the following result.
Corollary 1 Let Wx Sw, L= L(Wx) x) and Sh. (ker L) @ R2, then for all 0, given the above hierarchical model, the solution of the problem:
min ZEST M
Exxxx loO O Wx = Wx Z)
is PCA embedding of U U R X where Un the CCss membership vectors of W x-
Remark Note that while approzimates the objective of SNE-like methods when - the minimizer of g given by corollary 1 is stable for all e.
From this observation, we propose a sim- ple heuristic to minimize 9 that con- sists in computing a PCA embedding of (=px(:Kx) U X. The distribution of the connected components of the posterior of Wx being intractable, we resort to a Monte- Carlo estimation of the above expectation. The latter procedure called ccPCA aims at recovering the inter-CC structure that is fil- tered by SNE-like methods. ccPCA may then be used initialization for optimizing 8 which is done by running the DR met corresponding to the graph priors at hand (section b.1. This second step essentially consists refining the intra- CC structure.
Crade Momn Extreing
FTA siree
Figure 1: Left: MNIST t-SNE (perp 30) em- beddings initialized with i..d (0,11) 1) coordi- nates. Middle: using these t-SNE embeddings, mean coordinates for each digit are represented. Right: we compute matrix of mean input coordinates for each of the 10 digits and em- bed it using PCA. For t-SNE embeddings, the positions of clusters vary accross different runs and don't visually match the PCA embeddings of input mean vectors (right plot).
4.3 Experiments with ccPCA
Figure 1 shows that a t-SNE embedding balanced MNIST dataset 10000 samples [ with isotropic Gaussian initialization performs poorly in conserving the relative positions of clusters. As each digit cluster contains approximately 1000 points, with perplexity of 30, sampling edge across digit clusters in the graph posterior Pr, (:: xx) is very unlikely.
8

---

Top: MNIST embeddings produced by PCA, Laplacian eigenmaps, ccPCA and finally t-SNE launched after the previous three embeddings to improve the fine-grain structure. Bottom: mean coordinates for each digit using the embeddings of the first row. The color legend is the same as in fig. M parameters with the TSNE implementation
Figure 2:
t-SNE was trained during 1000 iterations using default
32
Recall that the perplexity value 35 corresponds to the approximate number of effective neighbors each point. Hence images of different digits are with very high probability in different CCs of the graph posterior and their CC-wise means are not coupled as discussed in section 3.2 To remedy this in practice, PCA or Laplacian eigenmaps are usually used as initialization 21
These strategies are tested (fig. 2 together with ccPCA. This shows that ccPCA manages to retrieve the digits that mostly support the large-scale variability measured by the peripheral positioning of digits (blue), (green), (pink) and 7 (grey) given by the right side of fig. [ Other perplexity values for ccPCA are explored in appendix B.2 while the experimental setup detailed in appendix B.1 In appendix B.3 we perform quantitative evaluations of ccPCA for both t-SNE and UMAP various datasets using K-ary neighborhood criteria. We find that using cPCCA as initialization is in general more reliable than PCA and Laplacian eigenmaps for preserving global structure using both t-SNE and UMAP.
Compared to PCA, ccPCA manages to aggregate points into clusters, thus filtering the intra-cluster variablity and focusing solely on the inter-cluster structure. Compared to Laplacian eigenmaps which performs well al identifying clusters but suffers from the same deficiency t-SNE for positioning them, ccPCA retains more of the coarse-grain structure. These observations support our unifying probabilistic framework and the theoretical results about the MRF degeneracy which are the leading contributions of this article. The ccPCA initialization appears as a first stepping stone towards more grounded DR methods based on the probabilistic model presented in this article.
5 Conclusion and Perspectives
In this work we shed a new light on most popular DR methods by showing that they can be unified within a common probabilistic model in the form of latent Markov Random Fields Graphs coupled by cross entropy. The definition of such model constitutes major step towards the understanding of common dimension reduction methods, particular their structure preservation properties as discussed in this article.
Our work offers many perspectives, among which the possibility enrich the probabilistic model with more suited graph priors. Currently considered priors are simply the ones that are conjugate to the MRF' thus they are mostly designed yield a tractable coupling objective. However they may not be optimal and could be modified to capture targeted features, e.g. communitics, in the input data, and give adapted representations space. The graph coupling approach could also be extended to more general latent structures governing the joint distribution of observations. Finally, the probabilistic model could be leveraged to tackle hyper-paramelle parameter calibration, especially kernel bandwidths that have great influence on the quality of the representations and are currently tuned using heuristics with unclear motivations.
the latent

---

Acknowledgments. The authors would like to thank the anonymous reviewers whose comments and questions helped improve the clarity of this manuscript, as well as Aurélien Garivier, Antoine Barrier and Floshi Poshi for helpful discussions. This work was supported by the Agence Nationale de la Recherche ANR-18-CE45-0023 SingleStat
References
[1] Friedrich Anders, Cristina Chiappini, Basilio Xavier Santiago, Gal Matijević, Anna B Queiroz, Marthias Steinmetz, and Guillaume Guiglion. Dissecting stellar chemical abundance space with f-sne. Astronomy 8 Astrophysics, 619:A125, 2018.
[2] Farzana Anowar, Samira Sadaoui, and Bassant Selim. Conceptual and empirical comparison of dimensionality reduction algorithms (PCA, KPCA, LDA, MDS, SVD, LLE, ISOMAP, LE, ICA, t-SNE). Computer Science Review, 40:100378, 2021.
3] Sanjeev Arora, Wei Hu, and Pravesh K Kothari. An analysis of the t-sne algorithm for data visualization. In Conference On Learning Theory, pages 1455-1462. PMLR, 2018.
[4] Mukund Balasubramanian, Eric Schwartz, Joshua B Tenenbaum, Vin de Silva, and John C Langford. The isomap algorithm and topological stability. Science, 295(5552):7-7, 2002.
[5] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373-13MM) 2003.
[6] Jan Niklas Böhm, Philipp Berens, and Dmitry Kobak. A unifying perspective on neighbor embeddings along the attractionrrepulsion spectrum. arXiv preprint 0l0:2007.08900. 2020.
[7] Miguel A Parreira-Perpinnnn The elastic embedding algorithm for dimensionality reduction. In 1CML, volume 10, pages 167 174. Citeseer, 2010.
[8] David M Chan, Roshan Rao, Forrest Huang, and John F Canny, t-sne-cuda: Gpu- accelerated t-sne and its applications to modern data. In 2018 30th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), pages 330-338. IEEE, 2018.
9 F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
[10] Peter Clifford. Markov random fields in statistics. Disorder in physical systems: volume in honour of John M. Hammersley, pages 19 32, 1990.
[11] Andy Coenen and Adam Pearce. Understanding umap. Google PAIR, 2019.
[12] Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21 21(1):5 ::55):3330 30, 2006.
[13] Gabor Csardi, Tamas Nepusz, et al. The igraph software package for complex network research. InterJournal, complez systems, 1695(5):1-9) 9, 2006.
[14] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):1411 142, 2012.
[15] David L Donoho. High-dimensional data analysis: The curses and blessings of dimen- sionality. AMS math challenges lecture, 1(2000):32, 2000.
[16] Jihun Ham, Daniel D Lee, Sebastian Mika, and Bernhard Schölkopf. A kernel view of the dimensionality reduction of manifolds. In Proceedings of the twenty-first international conference Machine learning, page 47, 2004.
[17] GeofTrey Hinton and Sam Roweis. Stochastic neighbor embedding. Tn NTPS, volume 15, pages 833 840. Citeseer, 2002.
10

---

[18] Geoffre E Hinton and Sam T. Roweis. Stochastic neighbor embedding, In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, pages 857-864. MIT Press, 2003.
[19] Dmitry Kobak and Philipp Berens. The art of using t-sne for singlo-cell transcriptomics. Nature commanications, 10(1):1-14, 2019.
[20] Dmitry Kobak, George Linderman, Stefan Steinerberger, Yuval Kluger, and Philipp Berens. Heavy-tailed kernels reveal a finer cluster structure in t-sne visualisations. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 124-139. Springer, 2019.
[21] Dmitry Kobak and George C Linderman. Initialization is critical for preserving global data structure in both t-sne and umap. Nature biotechnology, 39(2):156 157, 2021.
[22] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 and cifar-100 datasets. URl: hllps://wwo. cs. toronlo. edu/kriz/cijj cifor. hlml, 6(1):1, 2009.
[23]
Joseph B Kruskal. Multidimensional scaling. Number 11. Sage, 1978.
[24] Nadia S Kurd, Zhaoren He, Tiani L Louis, J Justin Milner, Kyla Omilusik, Wenhao Jin, Matthew S Tsai, Christella E Widjaja, Jad N Kanbar, Jocelyn G Olvera, et al. Early precursors and molecular determinants of tissue-resident memory cd8+ t lymphocytes revealed by single-cell maa sequencing. Science immunology, 5(47):eaaz6694, 2020.
[25] John A Lee, Diego H Peluffo-Ordóiezz and Michel Verleysen. Multi-scale similarities in stochastic neighbour embedding: Reducing dimensionality while preserving both local and global structure. Neurocomputing. (69:246-261) 2015.
[26] Tianxi Li, Cheng Qian, Elizaveta Levina, and Ji Zhu. High-dimensional gaussian graphical models on network-linked data. J. Mach. Learn. Res., 21:74 1, 2020.
[27] Wentian Li, Jane Cerise, Yaning Yang, and Henry Han. Application of t-sne to human genetic data. Journal of bioinformaties and computational biology, 15004):1750017, 2017.
[28] George C Linderman, Manas Rachh, Jeremy G Hoskins, Stefan Steinerberger, and Yuval Kluger. Fast interpolation based t-sne for improved visualization of single-cell rna-seq data. Nature methods, 16(3):243-244) 2019.
[29] George C LLndermaa and Stefan Steinerberger. Clustering with t-sne, provably. SIAM Journal on Mathematics of Data Science, 122):113 332, 2019.
[30] Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approx- imation and projection for dimension reduction. arXiv preprint arXiv: 1802. 1802.03426, 2018.
[31] Karl Pearson. Liii on lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin philosophical magazine and journal of science, 2(11):559-577 572, 1901.
[32] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825 2830, 2011.
[33] Nicola Pezzotti, Julian Thijssen, Alexander Mordvintsev, Thomas Höllt, Baldur Van Lew, Boudewijn PF Lelieveldt, Elmar Eiscmann, and Anna Vilanova. Gpgpu lincar com- plexity t-sne optimization. IEEE transactions on visualization and computer graphics, 26(1):1172-1188) 1181, 2019.
[34] Pavlin G Poličar, Martin Stražar, and Blaž Zupan. opentsne: a modular python library for t-sne dimensionality reduction and embedding. BioRriv, page 731877, 2019.
(35] Havard Rue and Leonhard Held. Gaussian Markve random fields: theory and applications. CRC press, 2005.
11

---

[36] Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. Visualizing large-scale and high-dimensional data. In Proceedings of the 25th international conference on world wide web, pages
2016.
[37] Michael E Tipping and Christopher M Bishop. Probabilistic principal component analysis. Journal of the Royal Statistical Society: Series (Statistical Methodology), 61(3):611-62) 12261,162,,1111 1999.
[88] L.J.P. van der Maaten and G.E. Hinton. Visualizing high-dimensional data using t-sne. Journal of Machine Learning Research, (nov):2579 2605, 2008. Pagination: 27.
[39] Martin J Wainwright and Michael Irwin Jordan. Graphical models, exponential families, and voriational inference. Now Publishers Inc, 2008
[40) Yingfan Wang, Haiyang Huang, Cynthia Rudin, and Yaron Shaposhnik. Understanding how dimension reduction tools work: an empirical approach to deciphering t-sne, umap, trimap, and pacmap for data, visualization. J Mach. Learn. Res, 22:1-73, 2021.
[41] Martin Wattenberg, Fernanda Viégas, and Ian Johnson. How to use t-sne effectively. Distill, 1110)=e2, 2016.
[42] Han Xiao, Kashif Rasul, and Roland Vollgraf. Pashion-mnist: novel image dalaset for benchmarking machine learning algorithms. arXiv preprint Xr:: 07747, 2017.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms
to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] appendix
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either the supplemental material or as a URL)? [Yos)
In appendix B
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In appendix
(c) Did you report error bars (e.g., with respect to the random seed after rumning experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In appendix B
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assots? [Yes]
(c) Did you include any new assets either the supplemental material or as
URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're feing/curating' [N/A]
(c) Did you discuss whether the data you are using /aangn/curaing contains personally
identifiable information or offensive content? [N/A]
5. Tf you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "bpS54CCo1cO", "reviewer": "Reviewer_V1Te", "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.", "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.\n\nIt 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.\n\nAnother 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.\n\nThe 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. \n", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe shift-invariant pairwise MRF is used to model the dependency of observations, which leads to the unifying cross entropy losses with different graph priors.\n\n2.\tVarious well-known and popularly used DR methods are recovered by the proposed framework.\n\n3.\tA new initialization method ccPCA to existing SNE-like methods is inspired by hierarchical graph coupling. \n\nWeaknesses:\n\n1.\tThe discussion on the pros and cons of existing SNE-like methods covered by the proposed framework with respect to graph priors is missing.\n\n2.\tThe new model motivated by the framework for balancing inter and intra structures are handled by a heuristic approach.\n\n3.\tVisual experiments with ccPCA focusing on the relative positioning of different digits using MNIST are subjective.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_P-axJFStC", "reviewer": "Reviewer_wgcv", "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.\n\nThis 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.\n\nFinally, 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.\n\nThe structure of the paper is as follows.\n- 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. \n- The authors define several options for the prior distribution P(W). \n- 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.\n- The authors show how each of several existing DR methods can be expressed using this framework. ", "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. \n\nThe 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", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nOriginality: 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.\n\nQuality: 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.\n\nSignificance: 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.\n\nNotes:\n\nOutline: 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. \n\nL30: Quote formatting errors. \n\nL86: I didn't understand the X_M, X_C split.\n\nL93: Symmetric how? k(x) = k(-x)?\n\nL100: k is overloaded as Gaussian kernel and general symmetric function. \n\nL102: 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. \n\nL109: 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. \n\nL153: What does the \\sim + \\models symbol denote? \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Y8vVOQpndGN", "reviewer": "Reviewer_54Sc", "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 \nformer 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. \n\nThe main theoretical contributions of the paper are:\n1) Identifying the previously mentioned approaches as special cases of a larger unifying statistical framework that is formulated using probabilistic graph coupling;\n2) Providing a theoretical explanation for the unsatisfactory performance at capturing global structure of the previous neighbour embedding methods;\n3) 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.\n\nExperiments 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.", "questions": "Suggestions:\n- 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.\n- 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. \n\nQuestions:\n- 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?\n- 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?\n", "limitations": "Yes. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BQmcU3Ys7zJ", "reviewer": "Reviewer_QqSP", "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. ", "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.\n> Though widely used, these approaches lack clear probabilistic foundations to enable a full understanding of their properties and limitations.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper presents an interesting view on popular dimensionality reduction techniques. Among its strengths I believe are:\n\n* Lays foundation for analyzing and understanding dimensionality reduction with MRF lens. Shows interesting analytical insights on existing works. \n* Provides recommendations for new ways to initialize, ccPCA, which has empirical advantages in the experiments\n\nWeaknesses of the paper include:\n* 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. \n* 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. \n* 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.\n\nTypos:\n30 - Quotation marks\n146 - edges -> edge's\n\nPossible related work:\nBayesian Distance Clustering. Leo L Duan, David B Dunson. https://arxiv.org/abs/1810.08537", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept