{'fraction_non_alphanumeric': 0.0423782652565492, 'fraction_numerical': 0.009417392279233156, 'mean_word_length': 4.431296935254719, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Markov-Lipschitz Deep Learning

In this paper, we propose a novel framework, called Markov-Lipschitz deep learning (MLDL), for manifold learning and data generation. It enhances layer-wise transformations of neural networks by optimizing isometry (geometry-preserving) and stability of the mappings. A prior constraint of locally isometric smoothness (LIS) is imposed across-layers and encoded via a Markov random field (MRF)-Gibbs distribution, and consequently layer-wise vector transformations are replaced by LIS-constrained metric homeomorphisms. These lead to the best possible solutions as measured by locally geometric distortion and locally bi-Lipschitz continuity. Extensive experiments, comparisons and ablation study demonstrate significant advantages of MLDL for manifold learning and data generation.


Introduction
The manifold assumption hypothesizes that data of a meaningful pattern lives in a low dimensional manifold embedded in a higher dimensional space (Belkin & Niyogi, 2003;Fefferman et al., 2016). We wish to develop a nonlinear dimensionality reduction (NLDR) mapping to transform the data from the input data space to a latent space where we can the Euclidean metric to facilitate pattern analysis. There are numerous literature on manifold learning for NLDR, including classic algorithms ISOMAP [28] using multidimensional scaling (MDS) , LLE [27], which are further developed with local MDS in [7,10,22]. Preserving local geometric structure is a key to its success.
Geometric deep learning (GDL) [5] attempts to generalize deep neural models to non-Euclidean domains such as graphs and manifolds. Topological data analysis (TDA) [30] integrates applied topology and computational geometry in a way that is insensitive to the particular metric chosen, such as using persistent homology [16,6,23]. GDL is more interested in manifold and embedding learning based on local geometry whereas TDA is more about the global topology.
The Lipschitz continuity theory is a tool for analyzing the stability of mappings from one metric space to another in which the Lipschitz constant may be used as a measure of instability. Recent years have seen interest in using Lipschitz continuity to improve neural networks in generalization [3,1], robustness against adversarial attacks [31,8], and generative modeling [35,25]. Supporting this research are efficient algorithms for estimation of the Lipschitz constant [29,33,19]. For local neighborhood-based manifold learning, we believe local Lipschitz continuity is more interesting.
The Markov random field (MRF) theory is a tool for modeling data with respect to a local neighborhood system [13,4]. Incorporation of MRF priors into the maximum a posteriori (MAP) estimation gives rise to a principled approach of MAP-MRF for developing a variety of statistical models. Among these are surface reconstruction, image denoising and inexact Bayesian shape matching [11,20]. In recent year, MRFs have been used in deep neural networks [26,17,2,32,12].
In this paper, we develop a novel deep learning framework, called Markov-Lipschitz deep learning (MLDL), for manifold learning, NLDR, and data generation. The motivations are the following: First, we believe that layer-wise vector transformations should be enhanced by metric homeomorphisms to make the neural transformations better behaved. Second, while manifold learning relies on local geometry structures of data samples with respect to neighborhood arXiv:2006.08256v2 [cs.LG] 21 Jun 2020 systems at various levels, such structures may be modeled by Markov random fields (MRFs) locally and equivalently by MRF-Gibbs distributions globally; this probability modeling also makes it possible to formulate deep learning in a principled way such as the MAP estimation using Bayesian statistics. Third, it is desirable to impose a local geometry preserving or isometric constraint on layer-wise neural homeomorphisms for purposes of both manifold learning and network stability and robustness; this may be done through locally bi-Lipschitz continuity encoded into losses or the energy function of the MRF-Gibbs distribution. The main contributions, to the best of our knowledge, are summarized below: (1) Proposing the MLDL framework that imposes the prior constraint of locally isometric smoothness (LIS) on cross-layer homeomorphic transformations and encodes the LIS into an MRF-Gibbs prior distribution. This results in MLDL neural networks optimized in terms of not only local geometry preservation as measured by a geometric distortion metric, but also homeomorphic regularity as measured by the locally bi-Lipschitz constant.
(2) Proposing two instances of MLDL-based neural networks: the Markov-Lipschitz Encoder (ML-Enc) for manifold learning, and the Markov-Lipschitz AutoEncoder (ML-AE) for manifold data generation. Note that the ML-Enc uses the LIP constraint to formulate the main loss terms and the reconstruction term of the ML-AE plays an assistive role in manifold learning and NLDR.
(3) Proposing an auxiliary term for manifold learning. The use of this term effectively helps prevent MLDL training from falling into a bad local optimum (failure in manifold unfolding).
(4) Providing extensive experiments, with self-and comparative evaluations and ablation study. The results clearly demonstrate significant advantages of MLDL over existing methods in terms of optimized locally geometric distortion and locally bi-Lipschitz continuity.
The rest of the paper is organized as follows: Section 2 outlines the MLDL network structure and introduces related preliminaries. Section 3 presents the key ideas of Markov-Lipschitz deep learning (MLDL) and the two MLDL neural networks (ML-Enc and ML-AE). Section 4 presents extensive experiments. Section 5 makes conclusions. More details of experiments can be found in Appendix.

MLDL structure and homeomorphisms
The structure of MLDL networks is outlined in Fig. 1. There, the ML-Encoder, composed of a cascade of L locally homeomorphic transformations, is aimed for manifold and embedding learning, and the corresponding L-layer ML-Decoder for reconstruction and data generation. The proposed MLDL also supports supervised and semi-supervised tasks and classification (not developed in this paper). In this work, locally restricted constraints are modeled by MRFs and the LIS constraint is imposed across network layers; these lead to desired properties of local geometry preserving and locally bi-Lipschitz continuity. In the following, we introduce preliminaries of MRFs in connection to neural networks and describes MLDL concepts of local homeomorphisms.

MRFs on neural networks
MRF on data samples. Let X = {x 1 , . . . , x M } be a set of samples on a manifold M X embedded in R N , with X ⊂ M X ⊂ R N , and d X be a metric on X so that (X, d X ) is a metric space. Let S := {1, . . . , M } be the set of indices. The neighborhood of x i can be defined by its k-nearest neighbors or the r-ball centered at x i . Let N i = {j ∈ S| x j ∈ B r (x i )} be the index of the neighbors of x i and N = {N i | ∀i ∈ S} be the neighborhood system. The tangent subspace T x (M X ) of the manifold at any x ⊂ M X is locally isomorphic to the Euclidean space of dim(M X ). While the above specifications are for the input (layer), they apply to another space after a C 0 -continuous transformation. In this paper, we use the Euclidean metric for every space; when we write a pair (i, j) ∈ S × S , it is limited by j ∈ N i , unless specified otherwise.
X is said to be an MRF on S with respect to N if the Markovian condition p( {i}} and X Ni = {x j |j ∈ N i }, and the positivity condition p(X) > 0 (∀X) are satisfied. The joint distribution of an MRF can be formulated according to a theorem of MRF-Gibbs equivalence [13,4,11]. The theorem states that X is an MRF on S with respect to N if and only if its joint distribution P (X) is a Gibbs distribution with respect to N .
A Gibbs distribution (GD) of X is featured by two things: (1) it belongs to the exponential family; (2) its energy function is defined on given cliques. A clique consists of either a single node {i} or a pair of neighboring nodes {i, j}. Let's denote the respective set by C 1 = {{i} | i ∈ S} and C 2 {{i, j} | j ∈ N i , i ∈ S} and the collection of all given cliques by C = C 1 ∪ C 2 . A GD of X with respect to N is of the following form is the energy composed of clique potentials V c (X), T is a global parameter called the temperature and Ξ the normalizing constant.
MRF on network layers. Consider an L-layer neural network such as the ML encoder in Fig. 1. Let X = X (0) , X (1) , . . . , X (L) and S L = {0, . . . , L}. Note that X (0) = X is the input data and all the other X (l) (for l > 0) are part of the solution after transformations. X is an MRF on S L if the above two conditions are satisfied. Let Λ L = {(l, l )|l < l , l ∈ S L } be the set of all cross-layer (undirected) links, which we call super-cliques, and Λ ⊆ Λ L be a subset under consideration. Underlying Λ is a neighborhood system N L independent of the input data. In the MLDL framework, the prior LIS constraint is encoded into cross-layer super-clique potentials which are then summed over all λ = (l, l ) ∈ Λ into the energy function of a for the MRF-Gibbs prior distribution Although not developed in this paper, imposition of prior knowledge via a MRF-Gibbs prior distribution can provide a tool for formulating deep learning of neural networks in a principled way such as maximum a posteriori (MAP) estimation.

Local homeomorphisms
Transformation between graphs. Manifold learning is associated with local geometric structure of data defined by a neighborhood system. It can be done by analyzing the graph G (X, D, N ), in which D = [d(x i , x j )] is the distance matrix providing quantitative information about local neighborhood. The data generation process is assumed to be a local homeomorphism (a mapping from one manifold to another) transforming latent variables Z ⊂ M Z ⊂ R n to the corresponding observed data X ⊂ M X ⊂ R N , with n < N , where M Z and M X are the manifold in the respective space. The objective of manifold learning is to find the inverse local homeomorphism Cascade of local homeomorphisms. Based on that the tangent space of a manifold is locally isomorphic to an Euclidean metric space, we could decompose a highly nonlinear Φ into a cascade of L less nonlinear, locally isometric homeomorphisms Φ = φ (L) • · · · • φ (2) • Φ (1) . This leads to MLDL neural networks of the following form in which X (0) = X is the input data, φ (l) the nonlinear transformation at layer l ∈ {0, . . . , L}, X (l) ⊂ R N l the output of φ (l) , N (l) the neighborhood system, and D (l) = [d l (x i (l) ,x j (l) )] the distance matrix given metric d l . The layer-wise transformation can be written as in which W (l) is the weight matrix to be learned, D (l) is used for locality restriction, and the product W (l) X (l) is followed by a nonlinear activation σ. Note that between any two layers l and l is an effective compositional homeomorphism φ (l,l ) : X (l) → X (l ) . We can define a loss function of W to measure the quality of Φ.
For the manifold learning purpose, the cascade unfolds M X in the input space, stage by stage, into M Z in a latent space to best preserve the local geometric structure of M X . In other words, given

Markov-Lipschitz neural networks
In this section, we develop the key ideas of the MLDL framework for manifold learning and data generation. MLDL differs from other deep learning methods in that it imposes the prior constraint of locally isometric smoothness (LIS) across-layers (as orange-colored arcs and dashed lines in Fig. 1) and this helps preserve the local geometric structure of data and stabilize neural networks.

Isometry and Lipschitz optimality
The core of MLDL is the imposition of the prior LIS constraint across-layers and encoding the prior into an MRF-Gibbs distribution. MLDL requires that the overall homeomorphism Φ : X → Z (and moreover their layered components) should satisfy the LIS constraint, that is, distance metrics be preserved locally, as far as possible. Such a Φ can be learned by minimizing the following loss (1) L lis measures the distortion in geometric distance and reaches the lower bound of zero when the isometry constraint is completely satisfied. Φ is said to be locally Lipschitz if for all j ∈ N i there exists K > 0 with A Lipschitz mapping or homeomorphism with a smaller K tends to generalize better [3,1], be more robust to adversarial attacks [31,8], and more stable in generative model learning [35,25]. It is locally bi-Lipschitz if for all j ∈ N i there exists K ≥ 1 with Bi-Lipschitz continuity is important for achieving invertible, bijective mappings between manifolds.
Expected consequences. We expect that imposing the LIS prior constraint and minimizing L lis should result in good locally bi-Lipschitz continuity conditions, with K = 1 being the best possible bi-Lipschitz constant. This would not only well preserve local geometric structure of data but also improve stability and robustness of resulting MLDL neural networks. Our extensive experiments on MLDL neural networks validate that resulting values of K are indeed lower than those obtained with compared networks, proving that the use of the LIS prior constraint leads to decent Lipschitz conditions for stability and robustness.

Markov-Lipschitz encoder
The LIS imposes the prior constraint of smoothness on metrics of local homeomorphisms across different network layers, to optimize homeomorphic regularity. We use the Markov-Lipschitz Encoder (ML-Enc), aimed for manifold learning and NLDR types of tasks, to illustrate how.
Changes in neighborhood systems across-layers. Every layer l has its own neighborhood system and clique set C (l) 2 . They are allowed to change across-layers to cater for admissible geometric deformations caused by the nonlinearity of φ (l,l ) : X (l) → X (l ) . Also, to take such changes into consideration in computing cross-layer LIS losses, we take the set union C (l,l ) 2 2 . Cross-layer set unions can also be defined for clique sets of triplets {i, j, k} as C (l,l ) 3 Cross-layer LIS loss. The LIS constraint of Equ. (1) and (2) could be imposed across any two layers. Given cross-layer super-clique λ = (l, l ) ∈ Λ for the network and data sample clique c = {i, j} ∈ C (λ) 2 , the clique potentials due to the LIS constraint are defined as Summing the potentials up gives rise to the energy function in which α (λ) are weights. Given the network architecture, the transform Φ is parameterized by W , thus minimizing L lis (W ) gives rise to the optimal W * for Φ.
The weights α (λ) determine how the LIS constraint should be imposed across-layers. An important goal of manifild and embedding learning is that the Euclidean metric can well describe distances between entities in the latent space Z = X (L) . We wish as the layer goes closer and closer to L, the Euclidean metric makes more and more sense in a larger and larger scope (neighborhood). This may set a guideline for manually setting α (λ) . In the future, these hyperparameters should be part of learnables.
It is interesting to compare the LIS proposed in this paper with the differential smoothness defined by Equ. (3) and (4) in [14]. There, transformations in feedforward networks and residual networks are studied based on principles of Riemannian geometry; vectors at successive layers are assumed of equal dimensionality and cross-layer changes are infinitesimal in order to define the differential smoothness. In contrast, in MLDL, metrics between vectors, rather than the vectors themselves, are coped with and this allows arbitrary changes in the dimensionality across-layers, making the MLDL framework practically applicable to dimensionality reduction and manifold data generation.
Cross-layer angular loss. While the LIS impose the distance-preserving constraint, it may be useful to also impose angle-preserving constraint defined on triplet cliques in which A(·, ·, ·) is the angle function. The corresponding energy function is in which β (λ) are weights. The angle term is related to the isometry term but in a nonlinear way.
LIS as prior constraint. The homeomorphic regularity loss L reg (W ) = L lis (W ) consists of the isometric loss as the main term, measuring the geometric distortion and homeomorphic (ir)regularity. When the angular loss is added, it becomes L reg (W ) = L lis (W ) + L ang (W ). Note that the ML-Enc works without the need for the reconstruction loss as in the ML-AE.
As mentioned earlier, only X (0) = X is the given input data and the other X (l) (for l > 0) are part of the solution. Therefore, although L reg (W ) looks dependent on X (l) , it should be considered as imposing constraint on the solution X (l) (for l > 0) while X (0) is fixed and used in the ML-Enc learning. It corresponds to the energy function in the prior MRF-Gibbs distribution, regardless of whatever the input data X (0) = X is. In the future, we will be investigating connections between this formulation and the posterior distribution p(Φ|X, W ).
Push-Away loss. This loss is introduced as an auxiliary cross-layer term to avoid deadlocks (knotting, bending) during the training. It is defined as in which π[·] ∈ {0, 1} is the indicator function. This term encourages pairwise cliques that are non-neighbors at layer l, c = {i, j} ∈ C (l) 2 , but whose distance at layer l is however smaller than a bound B, to push away from each other at layer l . This term is imposed from the beginning of the training and as the training progresses, its influence is gradually decreased to zero. We find empirically that this continuation method significantly helps prevent the training from falling into a bad local optimum. We will investigate mechanisms behind in the future.
ML-Enc loss function. The ML-Enc learns an NLDR transformation Φ : R N → R n through manifold learning. The final objective function is the isometric loss, with the transit, auxiliary push-away loss added to help avoid falling into a bad minimum. Adding L lis (W ) and the optional L ang (W ) for optimizing homeomorphic regularity L reg (W ) = L lis (W ) + L ang (W ) and the auxiliary L push (W ), we obtain the total lose for ML-Enc as in which µ gradually decreases from a starting value to 0.

Markov-Lipschitz AutoEncoder
The Markov-Lipschitz AutoEncoder (ML-AE) has two purposes: (1) helping regularize ML-Enc based manifold learning and (2) enabling manifold data generation. It is constructed by appending an ML decoder (ML-Dec) to ML-Enc in network structure and by adding reconstruction loss. The ML-Dec implements the inverse of ML-Enc and is entirely symmetric to the ML-Enc in its structure (see Fig. 1). In addition to the standard reconstruction loss ML-AE loss function. The overall reconstruction loss is the sum of those between corresponding layers of ML-Enc and ML-Dec in which γ l are weights. The total loss for the ML-AE loss is then The learned ML-Dec part of the ML-AE can be used for manifold reconstruction and generation. If the ML-AE is used for manifold and embedding learning only, L rec (W ) may be considered as a regularzer in addition to L lis .

Experiments
The purpose of the experiments is to evaluate the ML-Enc and ML-AE in their ability to preserve local geometry of manifolds and to achieve good stability and robustness in terms of relevant evaluation metrics.
Data sets. The Swiss Roll and S-Curve data, generated by the sklearn library [24], are used for the experiments. The data sets are normalized with the scaling factor of 1/20 for the Swiss Roll and 1/2 for the S-Curve. Seven methods for manifold learning are compared: ML-Enc (this paper), HLLE [9], MLLE and LTSA [34], ISOMAP [28], LLE [27] and t-SNE [21]; Four autoencoder methods are compared for manifold learning, reconstruction and data generation: ML-AE (this paper), AE [15], VAE [18], and TopoAE [23]. Due to the page limitation, the main body of the paper presents only main results with the Swiss Roll; more detailed results are presented in Appendix.
Evaluation metrics include the following. Every set of experiments is run 10 times, each with a data set generated using a random seed in {0, 1, · · · , 9}. Every final metric to be shown in performance tables is the average of the 10 results. When a run is unsuccessful in unfolding the input manifold data, the resulting averaged statistics of metrics are not very meaningful so the numbers will be shown in gray color in the following tables of evaluation metrics.
The Euclidean distance metric is used for all layers (d l ); it is normalized as d l = d l / √ n l for a space of dimensionality n l . The Neighborhood is defined by the r-ball scheme with r = 0.23. Push-away bound is set to B = 3 . Minibatch size is chosen according to the type and size of data. Activation function: LeakyReLU is used. Continuation on µ: µ starts from 0.8 and decreases linearly to the minimum 0 for epochs from 500 to 1000. Epochs: 3000 epochs are run for all results. The implementation is based on the PyTorch library running on Ubuntu 18.04 on NVIDIA v100 GPU.
Embedding quality. Table 1    Robustness to sparsity and noise.  Generalization to unseen data. The ML-Enc trained with 800 points can generalize well to unseen data in unfolding a modified version of the same manifold to the corresponding version of embedding. The test is done as follows: First, a set of 8000 points of the Swiss Roll manifold are generated; the data set is modified by removing, from the generated 8000 points of the manifold, the shape of a diamonds, square, pentagram or five-ring, respectively, creating 4 test sets.
Each point of a test set is transformed independently by the trained ML-Enc to obtain an embedding. We can see from each of the resulting embeddings in Fig. 3 that the unseen manifold data sets are well unfolded by the ML-Enc and the removed shapes are kept very well, illustrating that the learned ML-Enc has a good ability to generalize to unseen data. Since LLE-based, LTSA and ISOMAP algorithms do not possess such a generalization ability, the ML-Enc is compared with the encoder parts of the AE based algorithms. Unfortunately, AE and VAE failed altogether for the Swiss Roll data sets.
Manifold reconstruction. Table 3 compares the 9 quality metrics (all being the averages of 10 runs), including the mean reconstruction error (MRE), for the 4 autoencoders with the Swiss Roll (800 points) data. The MPE in the table is the average of the MPE's at layers 4 and 4 and the other metrics are calculated between the input and output layers of the AE's. While the other 3 autoencoders fail to unfold the manifold data sets (hence their metrics do not make much sense), the ML-AE produces good quality results especially in terms of the isometry and Lipschitz related metrics. The resulting metrics also suggest that K-max could be used as an indicator of success/failure in manifold unfolding. Manifold data generation. The ML-Dec part of the trained ML-AE can be used to generate new data of the learned manifold, mapping from random samples in the latent space to points in the higher-dimensional ambient space. The Fig. 4 shows manifold data reconstruction and generation using ML-AE, for which cases AE and VAE failed to unfold. In the learning phase, the ML-AE performs manifold learning for NLDR and then reconstruction, taking (a) the training data in the ambient space as input, output (b) embedding in the learned latent space, and then reconstruct back (c) in the ambient data space. In the generation phase, the ML-Dec takes (d) random input samples in the latent space, and maps the samples to the manifold (e) in the ambient data space.

Ablation study
This evaluate effects of the loss terms in the ML-AE on the 9 performance metrics, with the Swiss Roll (800 points) data: (A) the isometric loss L lis , (B) the angular loss L ang and (C) the push-away loss L push . Table 4 shows the results calculated between layers 0 and 0', and Table 5 shows the results calculated between layers 0 and 5. After analyzing the results, we can conclude: (1) the isometric term (A) is the most important factor for achieving the results of excellence; (2) the push-away term (C), applied with decreasing weight and diminishing on convergence, helps unfold manifolds especially with challenging input; (3) the angular term (B) has little added value. Note, however, metric numbers for the unsuccessful cases do not make much sense for comparison. Overall, the "AC" combination is the best algorithm of all. More ablation studies are provided in Appendix A.5.

Conclusions
The proposed MLDL framework imposes the cross-layer LIS prior constraint to optimize neural transformations in terms of local geometry preservation and local bi-Lipschitz constants. Extensive experiments with manifold learning, reconstruction and generation consistently demonstrate that the MLDL networks (ML-Enc and ML-AE) well preserve local geometry for manifold learning and data generation and achieve excellent local bi-Lipschitz constants, advancing deep learning techniques. The main ideas of MLDL are general and effective enough and are potentially applicable to a wide range of neural networks for improving representation learning, data generation and network stability and robustness.

A.2 ML-Enc manifold learning with S-Curve
The
The ablation results are shown in the table below, where the metric numbers are calculated between layers l = 0 and l = 0 : Evaluation metrics with different corresponding-layer schemes for ML-AE The results demonstrate that M10 outperforms the other three schemes in all metrics except for one K-max. When compared with incremental and equal weight scheme (M8 and M9), decreasing the corresponding-layer weight for the LIS constraint as the layer number becomes bigger can result in the greater performance gain, since the closer the data is to the input layer in the Encoder, the more authentic and reliable it is.
The ablation study shows that the use of the LIS constraint in MLDL has accomplished its promises and suggests further investgation into automatic learning of optimal links and weights for the LIS.

A.6 Comparing manifold learning results by visualization
The following show visualization of ML-Enc manifold learning results for 10 Swiss Roll and 10 S-Curve datasets. Such datasets are generated with a random seed in {0, 1, · · · , 9} . In these figures, a symbol √ or × represents a success or failure in unfolding the manifold. From these results, we can see that the ML-Enc not only has the highest success rate, but also best maintains the true aspect ratio.