Year: 2020

Abstract:
Machine-learning (ML) algorithms or models, especially deep neural networks (DNNs), have shown significant promise in several areas. However, researchers have recently demonstrated that ML algorithms, especially DNNs, are vulnerable to adversarial examples (slightly perturbed samples that cause misclassification). The existence of adversarial examples has hindered the deployment of ML algorithms in safety-critical sectors, such as security. Several defenses for adversarial examples exist in the literature. One of the important classes of defenses are manifoldbased defenses, where a sample is “pulled back” into the data manifold before classifying. These defenses rely on the assumption that data lie in a manifold of a lower dimension than the input space. These defenses use a generative model to approximate the input distribution. In this paper, we investigate the following question: do the generative models used in manifold-based defenses need to be topology-aware? We suggest the answer is yes, and we provide theoretical and empirical evidence to support our claim.

heading: 1 INTRODUCTION
text: Machine-learning (ML) algorithms, especially deep-neural networks (DNNs), have had resounding success in several domains. However, adversarial examples have hindered their deployment in safety-critical domains, such as autonomous driving and malware detection. Adversarial examples are constructed by an adversary adding a small perturbation to a data-point so that it is misclassified. Several algorithms for constructing adversarial examples exist in the literature (Biggio et al., 2013; Szegedy et al., 2013; Goodfellow et al., 2014b; Kurakin et al., 2016a; Carlini & Wagner, 2017; Madry et al., 2017; Papernot et al., 2017). Numerous defenses for adversarial examples also have been explored (Kurakin et al., 2016b; Guo et al., 2017; Sinha et al., 2017; Song et al., 2017; Tramèr et al., 2017; Xie et al., 2017; Dhillon et al., 2018; Raghunathan et al., 2018; Cohen et al., 2019; Dubey et al., 2019).
In this paper, we focus on “manifold-based” defenses (Ilyas et al., 2017; Samangouei et al., 2018). The general idea in these defenses is to “pull back” the data point into the data manifold before classification. These defenses leverage the fact that, in several domains, natural data lies in a low-dimensional manifold (henceforth referred to as the manifold assumptions) (Zhu & Goldberg, 2009). The data distribution and hence actual manifold that the natural data lies in is usually unknown, so these defenses use a generative model to “approximate” the data distribution. Generative models attempt to learn to generate data according to the underlying data distribution. (The input to a generative model is usually random noise from a known distribution, such as Gaussian or uniform.) There are
various types of generative models in the literature, such as variational autoencoder (VAE) (Kingma & Welling, 2013), generative adversarial network (GAN) (Goodfellow et al., 2014a) and reversible generative models, e.g., real-valued non-volume preserving transform (Real NVP) (Dinh et al., 2016).
This paper addresses the following question:
Do manifold-based defenses need to be aware of the topology of the underlying data manifold?
In this paper, we suggest the answer to this question is yes. We demonstrate that if the generative model does not capture the topology of the underlying manifold, it can adversely affect these defenses. In these cases, the underlying generative model is being used as an approximation of the underlying manifold. We believe this opens a rich avenue for future work on using topology-aware generative models for defense to adversarial examples.
Contributions and Roadmap. We begin with a brief description of related work in Section 2. Section 3 provides the requisite mathematical background. Our main theoretical results are provided in Section 4. Informally, our result says that if the generative model is not topology-aware, it can lead to a ”topological mismatch” between the distribution induced by the generative model and the actual distribution. Section 5 describes our experimental verification of our theoretical results and investigates their ramifications on a manifold-based defenses called Invert-and-Classify (INC) (Ilyas et al., 2017; Samangouei et al., 2018).

heading: 2 RELATED WORK

heading: 2.1 GENERATIVE MODELS
text: As a method for sampling high-dimensional data, generative models find applications in various fields in applied math and engineering, e.g., image processing, reinforcement learning, etc. Methods for learning data-generating distribution with neural networks include well-known examples of Variational Autoencoders (VAEs) (Kingma & Welling, 2013) and variations of Generative Adversarial Networks (GANs) (Goodfellow et al., 2014a; Radford et al., 2015; Zhao et al., 2016).
These generative models learn how to map latent variables into generated samples. The VAE is a variational Bayesian approach, so it approximates a posterior distribution over latent vectors (given training samples) by a simpler variational distribution. Similar to other variational Bayesian methods, VAE tries to minimize the Kullback–Leibler divergence between the posterior distribution and the variational distribution by minimizing the reconstruction error of the autoencoder. GANs represent another approach to learning how to transform latent vectors into samples. Unlike other approaches, the GAN learns the target distribution by training two networks – generator and discriminator – simultaneously.
In addition to generating plausible samples, some generative models construct bijective relations between latent vector and generated samples, so that the probability density of the generated sample can be estimated. Due to their bijective nature, such generative models are called to be reversible. Some examples are normalizing flow (Rezende & Mohamed, 2015), Masked Autoregressive Flow (MAF) (Papamakarios et al., 2017), Real NVP (Dinh et al., 2016), and Glow (Kingma & Dhariwal, 2018).

heading: 2.2 APPLICATIONS OF GENERATIVE MODELS IN ADVERSARIAL MACHINE LEARNING
text: The DNN-based classifier has been shown to be vulnerable to adversarial attacks (Szegedy et al., 2013; Goodfellow et al., 2014b; Moosavi-Dezfooli et al., 2016; Papernot et al., 2016; Madry et al., 2017). Several hypothesis try explaining such vulnerability (Szegedy et al., 2013; Goodfellow et al., 2014b; Tanay & Griffin, 2016; Feinman et al., 2017), and one explanation is that the adversarial examples lie far away from the data manifold. This idea leads to defenses making use of the geometry learned from the dataset – by projecting the input to the nearest point in the data manifold.
To learn a manifold from a given dataset, generative models can be exploited. The main idea is to approximate the data-generating distribution with a generative model, to facilitate searching over data manifold by searching over the space of latent vectors. The term Invert-and-Classfy (INC) was coined to describe this type of defense (Ilyas et al., 2017), and different types of generative models were tried to detect adversarial examples (Ilyas et al., 2017; Song et al., 2017; Samangouei et al., 2018). Usually, the projection is done by searching the latent vector that minimizes the geometric
distance (Ilyas et al., 2017; Samangouei et al., 2018). However, despite the promising theoretical background, all of those methods are still vulnerable (Athalye et al., 2018; Ilyas et al., 2017).

heading: 3 BACKGROUND
text: We formally describe data generation, based on the well-known manifold assumption; data lies close to a manifold whose intrinsic dimension is much lower than that of the ambient space. In our model of data generation, we provide a formal definition of data-generating manifold M on which the data-generating distribution lies such that M conforms to the manifold assumption.

heading: 3.1 REQUIREMENTS
text: Real-world data tends to be noisy, so the data does not easily correspond to an underlying manifold. We first focus on an ideal case where data is generated solely from the manifold M without noise.
In the setting of classification with l labels, we consider manifolds M1, . . . ,Ml ⊂ Rn that correspond to the generation of data in each class i ∈ {1, . . . , l}, respectively. We assume those manifolds are pair-wise disjoint, i.e., Mi ∩Mj = ∅ for any i /= j.We set the data-generating manifold M as the disjoint union of those manifolds, M = ⊍li=1Mi. We assume M to be a compact Riemannian manifold with a volume measure dM induced by its Riemannian metric. When a density function pM defined on M satisfies some requirements, it is possible to compute probabilities over M via ∫x∈M pM(x)dM(x). We call such M equipped with pM an dM as a data-generating manifold. We refer to Appendix A and Appendix D.1 for details about definitions and requirements on pM .
In practice, data generation is affected by noise, so not all data lie on the data-generating manifold. Therefore, we incorporate the noise as an artifact of data-generation and extend the density pM on M to the density p on the entire Rn by assigning local noise densities on M . We consider a procedure that (1) samples a point xo from M first, and (2) adds a noise vector n to get an observed point x̂ = xo +n. Here, the noise n is a random vector sampled from a probability distribution, centered at xo, whose noise density function is νxo , satisfying νx(n) = νx(x̂ − x) = pM(x̂∣xo = x).

heading: 3.2 EXTENDING DENSITY
text: When M is equipped with a density function pM and a measure dM that we can integrate over M , we can compute the density after random noise is added as follows.
p(x̂) = ∫ x∈M νx(x̂ − x)p(x)dM(x) (1)
Since νx(x̂ − x) is a function on x when x̂ is fixed, computing this integration can be viewed as the computing expectation of a real-valued function defined on M . Computing such expectation has been explored in Pennec (1999). A demonstrative example is provided in Appendix B, and this extension is further discussed in Appendix D.2.

heading: 3.3 GENERATIVE MODELS
text: A generative model tries to find a statistical model for joint density p(x, y) (Ng & Jordan, 2002). We mainly discuss a specific type that learns a transform from one distribution DZ to another target distribution DX . Commonly, a latent vector z ∼ DZ is sampled from a simpler distribution, e.g., Gaussian, then a pre-trained deterministic function G maps to a sample x = G(z).
Specifically, we focus on reversible generative models to facilitate the comparison between the density of generated samples and the target density. In this approach, the dimensions of latent vectors are set to be the same as those of the samples to be generated. Also, for a given x, the density of x is estimated by the change of variable formula (equation (2) in Section 5.1).

heading: 3.4 INVERT AND CLASSIFY (INC) APPROACH FOR ROBUST CLASSIFICATION
text: As the data-generating manifold M contains class-wise disjoint manifolds, there is a classifier f on Rn separating these manifolds. If f separates the manifolds of M , any misclassified point should lie out of M . Therefore, to change a correct classification near a manifold, any adversary would pull a sample further out of the manifold. By projecting misclassified points to the nearest manifold, we may expect the classification to be corrected by the projection. The INC method (Ilyas et al., 2017; Samangouei et al., 2018) implements this using a generative model.
The main idea of INC is to invert the perturbed sample by projecting to the nearest point on the data-generating manifold. Ideally, the data-generating manifold M is accessible. For any point (x̂, y) with f(x̂) /= y, out-of-manifold perturbation is reduced by projecting x̂ to x∗ on M . The manifold M
is unknown in practice. However, as M is the data-generating manifold of DX , a generative model G for DX is trained to approximate M . Then, searching over M is replaced by searching over latent vectors of G. More details about INC implementations are described in Section 5.1.

heading: 4 TOPOLOGICAL PROPERTIES OF DATA FROM GENERATIVE MODELS
text: In this paper, we study the significance of differences in the topological properties of the latent vector distribution and the target distribution in learning generative models. Initial information about the topology of target distribution1 is crucial to the generative model performance. Specifically, if there is a difference in the number of connected components in the superlevel set between the target distribution and the distribution of the latent vector, then any continuous generative model G cannot approximate the target distribution properly (irrespective of the training method). Due to the space limit, all proofs are presented in Appendix C.

heading: 4.1 TOPOLOGY OF DISTRIBUTIONS BASED ON SUPERLEVEL SETS
text: The data-generating manifold is a geometric shape that corresponds to the distribution. However, this manifold is not accessible in most cases and we only have indirect access via the distribution extended from it. Therefore, we consider finding a shape from the extended density so that this “shape” successfully approximates the data-generating manifold.
λ-density superlevel set. We use the concept of λ-density superlevel set to capture geometric features of the density function. Simply put, for a density function p and a threshold λ > 0, the λ-density superlevel set Lp,λ is the inverse image p−1[λ,∞]. Our theoretical contribution is the conditional existence of a λ-density superlevel set reflecting the topology of the data-generating manifold under proper conditions on the noise density.
Assumptions on noise density. For a family of densities {νx}x∈M , we require the noise νx to satisfy a number of assumptions. These assumptions facilitate theoretical discussion about the superlevel set reflecting the data-generating manifold. In the following definition, we denote a Euclidean ball of radius δ centered at x by Bδ(x).
Definition 1. Let νx be a family of noise densities.
• λ is small-enough if Lνx,λ is nonempty for all x ∈M ,
• λ-bounding radius δx,λ ∶=min{δ ∣ Lνx,λ ⊆ Bδ(0)} is the smallest radius that Bδ(0) contains Lνx,λ. When maxx∈M δx,λ exists for some λ, we denote the maximum value as δλ.
• λ-guaranteeing radius x,λ ∶=max{ ∣ B (0) ⊆ Lνx,λ} is the largest radius that Lνx,λ contains B (0). When minx∈M x,λ exists for some λ, we denote the minimum value as λ.
Sufficient conditions for the existence of these radii are discussed in Appendix D.3. The properties of these radii are summarized in Lemma 1. (The proof follows from Definition 1). Lemma 1. Let νx be a family of noise densities and let λ be small-enough. Then,
∥x̂ − x ∥ > δλ Ô⇒ νx(x̂ − x) < λ ∥x̂ − x ∥ ≤ λ Ô⇒ νx(x̂ − x) ≥ λ
whenever δλ and λ exist.
Figure 1 shows an example of superlevel set Lx,λ of noise νx at a point x and its λ-bounding radius δx,λ and λ-guaranteeing radius x,λ.
1The term topology of distributions, refers to the topology of shapes that correspond to the distributions.
Finally, we define the continuous variation of noise densities νx over changes of x ∈ M . For the continuous variation, we require the continuity of both radii δx,λ and x,λ as real-valued functions of x ∈M for any fixed value of λ.
Definition 2 (Continuously varying radii). Noise densities νx have continuously varying radii if, for a fixed small-enough λ, both λ-bounding radius δx,λ and λ-guaranteeing radius x,λ are continuous functions of x ∈M .
When noise densities have continuously varying radii, with the compactness of M , we can apply the extreme value theorem to guarantee the existence of both δλ =maxx∈M δx,λ and λ =minx∈M x,λ.

heading: 4.2 MAIN THEOREM
text: Our main theorem establishes, under the assumptions on noise densities from Section 4.1, the existence of a λ such that,
• (Inclusion) The λ-density superlevel set Lp,λ includes the data-generating manifold M . • (Separation) The λ-density superlevel set Lp,λ consists of connected components such that
each component contains at most one manifold Mi.
Definition 3. Consider a data-generating manifold M with density function pM . For a radius > 0, we define ω to be the minimum (over x ∈M ) probability of sampling x′ ∈M in an -ball B (x).
ω ∶=min x∈M Pr x′∼pM
[x′ ∈ B (x)]
Definition 4 (Class-wise distance). Let (X,d) be a metric space and let M = ⊍li=1Mi be a datagenerating manifold in X . The class-wise distance dcw of M is defined as,
dcw = min i,j∈[l] i/=j min x∈Mi x′∈Mj
d(x,x′)
With the definitions above, we proved the following main theorem.
Theorem 1. Pick any small-enough threshold λ. Fix a value λ∗ ≤ ω λ and let δ∗ = δλ∗ be the λ∗bounding radius. If dcw of M is larger than 2δ∗, then the superlevel set Lp,λ∗ satisfies the following properties.
• Lp,λ∗ contains the data-generating manifold M .
• Each connected component of Lp,λ∗ contains at most one manifold Mi of class i.

heading: 4.3 APPLICATION TO THE GENERATIVE MODEL
text: We show an application of Theorem 1. We denote the target distribution byDX , the latent distribution byDZ , and the distribution ofG(z) where z ∼ DZ byDG(Z). Similarly, we denote the corresponding λ-density superlevel sets of densities by LXλ , L Z λ , and L G(Z) λ . We assume the generative model G to be continuous. Then, we get the following theorem regarding the difference between LXλ and L G(Z) λ , in the number of connected components. 2
Theorem 2. Let DZ be a mixture of nZ multivariate Gaussian distributions, and let the datagenerating manifold of DX contain nX components. Let G be a continuous generative model for DX using latent vectors from DZ . Let λ∗ be the threshold value from the Theorem 1. If nZ < nX , LXλ∗ and L G(Z) λ∗ do not agree on the number of connected components.
We can use this theorem to deduce the need for adequate information about the target distribution when training a generative model, especially if it is used for a security-critical application, e.g., INC.
Corollary 1. If Theorem 2 is satisfied, there is a point x̂ ∈ Rn such that x̂ /∈ LXλ∗ but x̂ ∈ L G(Z) λ∗ .
As a result, with density at least λ∗, G generates a point x̂ that is unlikely to be generated by the target distribution. Since INC is based on generations of G, the INC method can output an out-of-manifold point as a solution of optimization (12).
2In Appendix D.4, Theorem 2 is generalized for more topological properties.

heading: 5 EXPERIMENTAL RESULTS
text: In this section, we empirically demonstrate the consequence of the two theorems and explore their implication for the INC defense. Our main goals are to provide (1) empirical support for the applicability of Theorem 2 and Corollary 1 via toy datasets, and (2) the improvement in INC performance using a class-aware generative model. The main questions and the corresponding answers are shown below.
(Q1) Can we experimentally verify the results of section 4.3? Specifically, can we find cases that the superlevel sets of DX and DG(Z) have different numbers of connected components? (Q2) How does INC fail when the generative model is ignorant of topology information? (Q3) Does the class-aware generative model improve the INC performance?
(A1) Theorem 2 and Corollary 1 can be verified by plotting the λ-density superlevel set. Especially, we visualize the λ-density superlevel set of DG(Z) reflecting Theorem 2 and Corollary 1. (A2) When generative model is not trained with topology information, naive INC may fail. We found out two possible reasons regarding INC failure: (1) choice of a bad initial point and (2) out-of-manifold search due to non-separation of density superlevel set.
(A3) The performance of INC is improved by training generative models with topology information on the target distribution. We improved the average INC performance by decreasing the error induced by projection to 30% compared to the class-ignorant counterpart.
In the rest of this section, we provide a more detailed description of our experiments. First, we briefly describe the experimental setup in Section 5.1: datasets, latent vector distributions, training method, and INC implementation. Then, Sections 5.2-5.4 describe the experimental results regarding the findings summarized above. Section 5.5 contains an additional experiment illustrating the changes of decision boundaries by INC application.

heading: 5.1 EXPERIMENTAL SETUP
text: Datasets. For all experiments, we use three toy datasets in R2: two-moons, spirals, and circles. Table 1 summarizes the parameterizations3 of each data-generating manifold and Figure 2 shows the plots of the corresponding data-generating manifolds. To construct the training set, we first sample 1000 points uniformly from each manifold Mi, then each point is perturbed by isotropic Gaussian noise N (0, σ2I2) with σ = 0.05. Before the training, each training set is standardized by a preprocessing of Scikit-learn package. Latent vector distributions. For latent vector distributions DZ , we prepared three different mixtures of nZ Gaussian distributions with nZ ∈ {1,2,3}. When nZ = 1, we simply use N (0, I2). When nZ = 2,3, we arranged nZ Gaussian distributions along a circle of radius R = 2.5, so that i-th Gaussian has mean at µi = (−R sin ( 2πin ) ,R cos ( 2πi n
)) with σ = 0.5 for n = 2 and σ = 0.3 for n = 3. Then, the uniform mixtures of the arranged Gaussian are used as DZ . In Figure 3 (top row), we visualize the connected components corresponding to the latent vector distributions.
Training generative models. Our experiments mostly use the Tensorflow Probability (Dillon et al., 2017) library that contains the implementation of reversible generative models. Specifically, the Tensorflow Probability library contains an implementation of the Real NVP coupling layer that we used as a building block of our models. The default template provided by Tensorflow Probability
3The value T is from the reparameterization t = ln (s/ √ 2 + 1) for s ∈ [0,15] for uniform sampling.
library was used to construct each Real NVP coupling layer with two hidden layers of 128 units. Each model uses eight coupling layers that are followed by permutations exchanging two dimensions of R2 except for the last coupling layer.
We describe the details of the training procedure of the generative models used in the experiments. We prepared two different types of generative models: class-ignorant and class-aware.
The class-ignorant type is the usual Real NVP model. This model uses the empirical estimation of negative log-likelihood over a training batch {x1, . . . ,xm} as its training loss.
`ci = − 1
m
m ∑ t=1 log(pX(xt))
The density pX of DX is estimated by applying the change of variables formula,
pX(x) = pZ(z) ∣det( ∂G(z) ∂ zT )∣ −1
(2)
where pZ is the density of DZ and ∂G(z) ∂ zT is the Jacobian of G as a function from Rn to itself.
The class-aware type is the Real NVP model trained with information about the number of connected components, i.e. the number of class labels l. Using the number of labels, the densities pX and pZ can be decomposed as follows.
pX(x) = ∑ i∈{1,...,l} Pr[y = i] pX,i(x)
pZ(z) = ∑ i∈{1,...,l}
Pr[y = i] pZ,i(z) (3)
where pX,i(x) = pX(x ∣y = i) and each pZ,i is the i-th Gaussian component described above. Since Pr[y = i] is not generally known, the uniform distribution Pr[y = i] = 1
l is used, where l is the
number of classification labels.
The main idea is class-wise training, i.e., training each pX,i from each pZ,i. Applying the change of variables formula for each class i,
pX,i(x) = pZ,i(z) ∣det( ∂G(z) ∂ zT )∣ −1
(4)
Combining equations (3) and (4), we get the change of variables formula (2). We define the class-wise loss function `i for class-wise training as follows.
`i = − 1
mi
m ∑ t=1 1[yt = i] log(pX,i(xt))
where mi is the number of training samples in class i. Then, we train a generative model using the weighted sum of `i as the training loss function.
`ca = ∑ i∈{1,...,l} Pr[y = i] `i
Each model was trained for 30,000 iterations. For each iteration, a batch of 200 random samples was chosen from two-moons and circles dataset, and a batch of 300 random samples was chosen from the spirals dataset. For the choices of latent vector distribution, we chose the mixture of l − 1 Gaussians for the class-ignorant type, whereas we chose the mixture of l Gaussians for the class-aware type.

heading: 5.2 VISUAL VERIFICATION OF THEOREMS
text: The goal of this section is to verify Theorem 2 and the Corollary 1 by visualizing the superlevel set reflecting the statements. Figure 3 shows the λ-density superlevel sets of densities of DG(Z) using the same threshold λ = 0.01. The first row and the second row show the results from the class-ignorant version and those from the class-aware version, respectively. Each column corresponds to each dataset. All distributions are scaled for the standardization preprocessing before the training. In general, superlevel set components are separated when the generative model is class-aware. On the contrary, the class-ignorant generative models introduce connections between the components, as anticipated by Corollary 1. Due to this connection, the class-ignorant generative models contain fewer connected components in their superlevel sets; this verifies Theorem 2 for our choice of λ∗ = 0.01.

heading: 5.3 INC FAILURE DUE TO THE LACK OF INFORMATION ON THE DISTRIBUTION TOPOLOGY
text: We present how the non-separation of superlevel set components influences the performance of the INC. We provide two possible explanations of why the INC fails. First, the bad initialization causes a suboptimal solution on a manifold not-the-nearest to the input. Second, an artifact induced by the topological difference produces an out-of-manifold solution.
Figure 4 presents three visualized examples of INC with a class-ignorant generative model for twomoons. In each plot, the black dot is the given point x̂, and cyan dot is the initial point from choosing z randomly from the latent vector distribution – N (0, I2), and magenta dot is the final point output by INC. All intermediate points of the optimization are plotted with dots, changing colors gradually from cyan to magenta. The training set for two-moon used in the training procedure is plotted in gray.
Figure 4a is the INC optimization with an ideal start. The initial point lies in the same manifold as the manifold closest to x̂. Then, the INC optimization searches along the manifold, converging to a point close to x̂. Figure 4b shows a case in which INC fails because of a bad initialization. The initial point was chosen on a manifold not containing the desired solution, so the INC converged to a local optimum on the wrong manifold. Our class-aware INC performs manifold-wise initialization to circumvent this issue. Figure 4c shows that the INC failed due to an out-of-manifold search. The INC converged in a wrong manifold, and a nontrivial amount of intermediate points were out of manifold, resulting in an out-of-manifold solution (see Figure 3d).

heading: 5.4 INC IMPROVEMENT VIA CLASS-AWARE GENERATIVE MODEL
text: We demonstrate that INC performance is improved by using class-aware generative models. To measure the performance of the INC, 100 points are chosen uniformly from each manifold Mi. Then, each point x is perturbed by nx normal to the manifold at x, generating 200 adversarial points x̂ = x±rnx. For all datasets, r = 0.2 is used for perturbation size. We expect two types of INC to map x̂ back to the original point x, as x is the optimal solution to (11). We define the projection error of INC as ∥INC(x̂) − x ∥2, and collect the statistics of projection errors over all x̂.
Table 2 shows the projection error statistics for two types of INC. Each pair of columns show the results on the indicated dataset. For each pair, one column shows the error of the class-ignorant INC and the other column shows that of the class-aware counterpart. Numbers in each cell are averages and standard deviations (in parenthesis) of the projection error. For any dataset, the class-aware INC achieves lower projection errors. Histograms of the projection errors are provided in Appendix E.

heading: 5.5 ADDITIONAL EXPERIMENTS FOR THE INC PERFORMANCE.
text: Finally, we present experiments to demonstrate the effect of the superlevel set discrepancy on the INC performance. First, we begin with training support vector machines (SVMs) performing classification tasks for our target distributions. For training data, we randomly sampled 1000 training points from each data-generating manifold. The baseline SVMs were intentionally ill-trained by using the high kernel coefficient γ = 100. 4 After training SVMs, we formed other classifiers by applying INC to ill-trained SVMs To explain, for each dataset, we have four types of classifiers as follows.
(1) Ill-trained SVM: Baseline classifier (2) Ideal INC: Classifier with INC using a direct access to the data-generating manifolds (3) Class-ignorant INC: Classifier with INC using a topology-ignorant generative model (4) Class-aware INC: Classifier with INC with using a topology-aware generative model
We want to emphasize that direct access to the data-generating manifold is not possible in general. However, applying INC using direct access gives us an INC purely based on the geometry, so it is an ideal form of INC that should be approximated. Also, since the class-ignorant INC is affected by a bad choice of an initial point, we reduced the effect of bad initialization by sampling more initial points and taking the best solution among the projection results. For this number of initial choices, we
4In general, choosing an unnecessarily high kernel coefficient γ causes overfitting (Chaudhuri et al., 2017), inducing decision boundary close to the training data.
chose as many initial points as the number of manifolds, which was exactly the same as the number of initial points for the topology-aware INC model.
To demonstrate the improvement in the robustness of the model, we visualize the effect by depicting the decision boundary of each classifier. Specifically, we form a 300 × 300 grid on the domain of [−3,3]×[−3,3] and compute the classification result. The depicted decision boundaries are presented in Figure 5. Each row corresponds to each dataset: two moons, spirals, and circles, respectively. Each column corresponds to classifiers 1-4 described above, from the first column to the fourth column, respectively. From Figure 5, it is visually evident that the class-aware INC models provide more proper approximations to the ideal INC model compared to the class-ignorant INC models.

heading: 6 CONCLUSION
text: We theoretically and experimentally discussed the necessity of topology awareness in the training of generative models, especially in security-critical applications. A continuous generative model is sensitive to the topological mismatch between the latent vector distribution and the target distribution. Such mismatch leads to potential problems with manifold-based adversarial defenses utilizing generative models such as INC. We described two cases in which the INC failed: the bad initialization and the artifacts from the topological difference. We experimentally verified that topology-aware training effectively prevented these problems, thereby improving the effectiveness of generative models in manifold-based defense. After topology-aware training of generative models, the INC projection errors represented 30% of the errors of the topology-ignorant INC.

heading: 7 ACKNOWLEDGEMENT
text: Dr. Susmit Jha and Uyeong Jang’s internship at SRI International were supported in part by U.S. National Science Foundation (NSF) grants #1740079, #1750009, U.S. Army Research Laboratory Cooperative Research Agreement W911NF-17-2-0196, and DARPA Assured Autonomy under contract FA8750-19-C-0089. The views, opinions and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. This work is partially supported by Air Force Grant FA9550-18-10166, the National Science Foundation (NSF) Grants CCF-FMitF-1836978, SaTC-Frontiers-1804648 and CCF-1652140 and ARO grant number W911NF-17-1-0405.

heading: A MATHEMATICAL BACKGROUND
text: A.1 GENERAL TOPOLOGY
We introduce definitions and theorems related to general topology appeared in the paper. For more details, all the definitions and theorems can be found in Munkres (2000).
Definitions in general topology. We first provide the precise definitions of the terms we brought from the general topology. Definition 5 (Topological space). A topology on a set X is a collection T of subsets of X having the following properties.
1. ∅ and X are in T .
2. The union of the elements of any subcollection of T is in T .
3. The intersection of the elements of any finite subcollection of T is in T . A set X for which a topology T has been specified is called a topological space.
For example, a collection of all open sets in Rn is a topology, thus Rn is a topological space. If a topology can be constructed by taking arbitrary union and a finite number of intersections of a smaller collection B of subsets of X , we call B is a basis of the topology.
Pick a metric d in Rn and consider B a set of all open balls in Rn using the metric d. The topology of Rn can be constructed by taking B as a basis. When this construction is possible, metric d is said to induce the topology. Definition 6 (Metrizable space). If X is a topological space, X is said to be metrizable if there exists a metric d on the set X that induces the topology of X . A metric space is a metrizable space X together with a specific metric d that gives the topology of X .
Since Rn is equipped with Euclidean metric that induces its topology, Rn is metrizable.
Continuity and the extreme value theorem. Let X and Y be topological spaces. In the field of general topology, a function f ∶X → Y is said to be continuous, if for any subset V open in Y , its inverse image f−1(V ) is open in X . Moreover, if f is a continuous bijection whose inverse is also continuous, f is called a homeomorphism. The notion of homeomorphism is important as it always preserves topological property, e.g., connectedness, compactness, etc., and this will be used in the further generalization of Theorem 2.
Here, we only introduce the generalized statement of extreme value theorem. Theorem 3 (Extreme value theorem). Let f ∶X → Y be continuous, where Y is an ordered set. If X is compact, then there exist points x and x in X such that f(x) ≤ f(x) ≤ f(x) for every x ∈X .
Specifically, if a manifold M is a compact subset in Rn, we may use X =M and Y = R.
Normal space and Urysohn’s lemma. The Urysohn’s lemma was used to prove the Corollary 1. We first introduce the notion of normal space. Definition 7 (Normal space). Let X be a topological space that one-point sets in X are closed. Then, X is normal if for each pair A, B of disjoint closed sets of X , there exist disjoint open sets containing A and B, respectively.
Urysohn’s lemma is another equivalent condition for a space to be normal. Theorem 4 (Urysohn’s lemma). Let X be a normal topological space; let A and B be disjoint closed subsets in X . Let [a, b] be a closed interval in the real line. Then there exists a continuous map
f ∶X Ð→ [a, b]
such that f(x) = a for every x in A, and f(x) = b for every x in B.
To apply this lemma to Rn, we only need the following theorem. Theorem 5. Every metrizable space is normal.
Since Rn is metrizable, it is a normal space by Theorem 5. Therefore, we can apply Urysohn’s lemma to any pair of disjoint subsets in Rn, to show the existence of a continuous map f ∶X → [0,1].
A.2 DIFFERENTIAL GEOMETRY
We provide the definitions from differential geometry (Lee, 2003) used in the paper.
Manifold and tangent space. Formally, topological manifold is defined as follows. Definition 8 (Manifold). Suppose M is a topological space. We say M is a topological manifold of dimension k if it has the following properties.
1. For any pair of distinct points x1,x2 ∈M , there are disjoint open subsets U1, U2 ⊂M such that x1 ∈ U and x2 ∈ V .
2. There exists a countable basis for the topology of M .
3. Every point has a neighborhood U that is homeomorphic to an open subset Ũ of Rk.
There are different ways to define tangent space of k-dimensional manifold M . Informally, it can be understood as geometric tangent space to M ⊂ Rn at a point x ∈M , which is a collection of pairs (x,v) where v is a vector tangentially passing through x. Here we put a more formal definition of tangent space. Consider a vector space C∞(M), a set of smooth functions on M . Definition 9 (Tangent space). Let x be a point of a smooth manifoldM . A linear mapX ∶ C∞(M)→ R is called a derivation at x if it satisfies
X(fg) = f(x)Xg + g(x)Xf
for all f, g ∈ C∞(M).
The set of all derivations of C∞(M) at x forms a vector space called the tangent space to M at x, and is denoted by Tx(M).
Riemannian metric. As tangent space Tx(M) is a vector space for each x ∈M , we can consider a inner product gbfx defined on Tx(M). Definition 10 (Riemannian metric). A Riemannian metric g on a smooth manifold M is a smooth collection of inner products gx defined for each Tx(M). The condition for smoothness of g is that, for any smooth vector fields X , Y on M, the mapping x↦ gx(X ∣x,Y ∣x).
A manifold M equipped with a Riemannian metric g is called a Riemannian manifold.

heading: B EXAMPLES
text: Computing density pM over a Riemannian manifold M . This section presents example computations of the probability computations from Section D.1 and Section 3.2 As a concrete example of computing density over a manifold, we use the following simple manifolds, so called two-moons in R2.
M0 = {(x1, x2)∣ x1 = cos θx2 = sin θ for θ ∈ [0, π]}
M1 = {(x1, x2)∣ x1 = 1 − cos θx2 = 1 − sin θ + 12 for θ ∈ [0, π]}
We take M = M0 ∪M1 as our example manifold. Figure 6a shows the manifold of two-moons dataset plotted in different colors: M0 in red and M1 in blue.
First recall the following equation (equation (8) from the Section D.1).
∫ x∈M pM(x)dM(x) = ∫ u∈D
pM(X(u)) √ ∣det[gX(u)]∣du
where [gX(u)] is the k × k matrix representation of the inner product gX(u) at X(u) ∈M .
Especially, when a manifold in Rn is of dimension 1, i.e., parameterized curve γ ∶ [a, b]→ Rn, the integration (8) can be written in simpler way.
∫ x∈M
pM(x)dM(x) = ∫ b
t=a pM(γ(t))∥γ′(t)∥dt (5)
where γ′(t) is the n-dimensional velocity vector at t ∈ [a, b].
Let pM be a probability density function defined on M . As M is composed of two disjoint manifolds M0 and M1, we consider conditional densities p0, p1 as follows.
p0(x) = pM(x ∣x ∈M0) = pM ∣M0(x) Pr[x ∈M0]
p1(x) = pM(x ∣x ∈M1) = pM ∣M1(x) Pr[x ∈M1]
(6)
Here, pM ∣M0 and pM ∣M1 represent the density function pM with its domain restricted to M0 and M1, respectively. By our definition of data-generating manifolds, Pr[x ∈ Mi] corresponds to the probability of data generation for class i, i.e. Pr[y = i]. For a concrete example of such density, uniform density for each manifold Mi can be defined as pi(x) = 1π for all x ∈Mi.
Note that each manifold has parameterized curves in R2, γ0 ∶ θ ↦ (cos θ, sin θ) γ1 ∶ θ ↦ (1 − cos θ,1 − sin θ + 0.5)
with constant speed ∥γ′0(θ)∥ = ∥γ ′ 1(θ)∥ = 1 at all θ ∈ [0, π]. Therefore, from equation (5),
∫ x∈M0
pM ∣M0(x)dM0(x) = ∫ π
θ=0 pM(γ0(θ))dθ
∫ x∈M0
pM ∣M1(x)dM1(x) = ∫ π
θ=0 pM(γ1(θ))dθ
(7)
For any measurable subset A ⊆M , the probability for an event that x is in A can be computed as follows.
Pr[x ∈ A] =∫ x∈A⊆M pM(x)dM(x)
=∫ x∈A∩M0 pM ∣M0(x)dM0(x) + ∫ x∈A∩M1 pM ∣M1(x)dM1(x)
=∫ θ∈[0,π] γ0(θ)∈A pM ∣M0(γ0(θ))dθ + ∫ θ∈[0,π] γ1(θ)∈A pM ∣M1(γ1(θ))dθ (∵ (7))
=Pr[x ∈M0]∫ θ∈[0,π] γ0(θ)∈A p0(γ0(θ))dθ
+Pr[x ∈M1]∫ θ∈[0,π] γ1(θ)∈A p1(γ1(θ))dθ (∵ (6))
= 1 π ⎛ ⎝ Pr[x ∈M0]∫ θ∈[0,π]
γ0(θ)∈A 1dθ +Pr[x ∈M1]∫ θ∈[0,π] γ1(θ)∈A 1dθ
⎞ ⎠
We can briefly check all the requirements (R1), (R2), and (R3). The computation of Pr[x ∈ A] is based on (R1), so (R1) is satisfied trivially. Also, pM is a function defined only on M , thus (R2) is clear, i.e. supp(pM) = {x ∈ Rn ∣ p(x) > 0} ⊆ M . To check (R3), when A = Mi, computing this integration will result in the exact probability Pr[x ∈Mi] = Pr[y = i], so when A =M , computing the integration will result in Pr[y = 0] +Pr[y = 1] = 1, as desired in the requirements.
Extending density to Rn. We extend the domain to Rn for the example of two-moon. In Section 3, we defined the noise density function to satisfy the following requirement.
(R0) The translated noise density function, νx(x̂ − x), is the density of noise n = x̂ − x being chosen for a given x. Given xo = x, since adding noise n is the only way to generate x̂ by perturbing x0, p(x̂∣xo = x) is equal to νx(n).
Under a proper noise density function, We show an example construction of the density extended from M satisfying the requirement (R0). For simplicity, we choose isotropic Gaussian distribution, N (0, σ2I) with the standard deviation σ for each dimension as the noise density function νx for all x ∈M . Such noise density νx defined in Rn can be written as follows.
νx(nx) = 1√ 2πσ2 exp(−∥nx ∥ 2 2 2σ2 )
By putting nx = x̂ − x to density equation above,
p(x̂) = ∫ x∈M 1√ 2πσ2 exp(−∥x̂ − x ∥ 2 2 2σ2 )pM(x)dM(x)
Specifically, We assume an isotropic Gaussian distribution with σ = 0.05 as the noise density νx for all x ∈M .
By the equation (1), we have the following computation of density on x̂.
p(x̂) =∫ x∈M νx(x̂ − x)pM(x)dM(x)
=∫ x∈M0 νx(x̂ − x)pM ∣M0(x)dM0(x) + ∫ x∈M1 νx(x̂ − x)pM ∣M1(x)dM1(x) =∫ π
θ=0 νx(x̂ − x)pM ∣M0(γ0(θ))dθ + ∫
π
θ=0 νx(x̂ − x)pM ∣M1(γ1(θ))dθ (∵ (5))
=Pr[x ∈M0]∫ π
θ=0 νx(x̂ − x)p0(γ0(θ))dθ
+Pr[x ∈M1]∫ π
θ=0 νx(x̂ − x)p1(γ1(θ))dθ (∵ (6))
= 1 π √ 2πσ2 [Pr[x ∈M0]∫ π θ=0 exp(−∥x̂ − x ∥ 2 2 2σ2 )dθ
+Pr[x ∈M1]∫ π θ=0 exp(−∥x̂ − x ∥ 2 2 2σ2 )dθ]
We can also check that the requirement (R0) is satisfied by the construction; our construction (equation (1)) is based on (R0). The computed density is shown in Figure 6b.

heading: C PROOFS
text: In this section, we provide the proofs for statements that appeared in Section 4.
C.1 PROOF OF THEOREM 1
To begin with, pick a value λ such that the λ-density superlevel set Lνx,λ is nonempty for all x ∈M . As we use noise densities νx described in Section 4.1, it is safe to assume that both λ-bounding radius δλ =maxx∈M δx,λ and λ-guaranteeing radius λ =minx∈M x,λ exist.
Then, we can prove that, with a proper choice of threshold λ, the λ-density superlevel set includes the data-generating manifold.
Lemma 2. Assume that noise densities have radii in Definition 1 for all x ∈M and a small enough λ > 0. Then, for any x ∈M , the density p(x) is at least ω λ, i.e. p(x) ≥ ω λ, where = λ.
Proof. By Lemma 1,
x′ ∈ B (x) ⇐⇒ x ∈ B (x′) = B λ(x ′) (∵ = λ)
Ô⇒ νx′(x−x′) ≥ λ
Then, we can lower bound the density pM(x) as follows.
p(x) = ∫ x′∈M
νx′(x−x′)pM(x′)dM(x′)
≥ ∫ x′∈M∩B (x)
νx′(x−x′)pM(x′)dM(x′)
≥ λ∫ x′∈M∩B
pM(x′)dM(x′)
= λ Pr x′∈M
[x′ ∈ B (x)]
≥ ω λ
This lemma shows that the thresholding the extended density p with threshold λ∗ ≤ ω λ guarantees the superlevel set to include the entire manifold M . Corollary 2. For any threshold λ∗ ≤ ω λ, the corresponding λ∗-density superlevel set Lp,λ∗ of the extended density p includes the data-generating manifold M .
Similarly, we show that, with a proper choice of threshold λ, each connected component of λ-density superlevel set contains at most one manifold. Lemma 3. Assume a family of noise densities satisfies the assumptions of Section 4.1. Let λ > 0 be a value such that the λ-density superlevel set Lνx,λ is nonempty for any x ∈M . Also, let δ = δλ be the maximum λ-bounding radius over M . Then, for any x̂ /∈ Nδ(M), the extended density value is smaller than λ, i.e. p(x̂) < λ.
Proof. By Lemma 1,
x̂ /∈ Nδ(M) ⇐⇒ x̂ /∈ Bδ(x) = Bδλ(x) for any x ∈M (∵δ = δλ) Ô⇒ νx(x̂ − x) < λ for any x ∈M
Then, we can upper bound the density p(x̂) as follows.
p(x̂) = ∫ x∈M νx(x̂ − x)pM(x)dM(x)
< λ∫ x∈M pM(x)dM(x) (∵x̂ /∈ Nδλ(M)) = λ
This lemma says that the λ-density superlevel set is included by the δ-neighborhood Nδ(M) of the data-generating manifold M .
Now, we can deduce the following main result. Theorem 1. Pick any λ∗ ≤ ω λ threshold value satisfying the Corollary 2. If the class-wise distance of data-generating manifold is larger than 2δ∗ where δ∗ = δλ∗(the λ∗-bounding radius), then the superlevel set Lp,λ∗ satisfies the followings.
• Lp,λ∗ contains the data-generating manifold M .
• Each connected component of Lp,λ∗ contains at most one manifold Mi of class i.
Proof. The first property is a direct application of Corollary 2 for λ∗ = ω λ.
For the second property, since the class-wise distance of M is larger than 2δ∗, the δ∗-neighborhood of manifolds are pairwise disjoint, i.e. Nδ∗(Mi) ∩Nδ∗(Mj) = ∅ for each i /= j. Therefore, Nδ∗(M) has exactly k connected components Ni = Nδ∗(Mi)’s.
By Lemma 3, δ∗-neighborhood Nδ∗(M) contains the superlevel set Lp,λ∗ , thus each connected component of Lp,λ∗ is in exactly one of Ni’s. Since M is contained in Lp,λ∗ , each Mi is contained in some connected component C of Lp,λ∗ which is in Ni. Then, for any j /= i, Mj /⊂ C ⊂ Ni, since Mj is in Nj which is disjoint to Ni. Therefore, if a connected component C contains a manifold Mi, then it cannot contain any other manifold.
C.2 PROOFS FOR SECTION 4.3
Theorem 2. Let DZ be a mixture of nZ multivariate Gaussian distributions, and let DX be the target distribution from a data-generating manifold with nX manifolds. Let G be a continuous generative model for DX using latent vectors from DZ . Assume the Theorem 1 is satisfied, and let λ∗ be the threshold value from the Theorem 1. If nZ < nX , LXλ∗ and L G(Z) λ∗ do not agree on the number of connected components.
Proof. Since LXλ∗ is the results of Theorem 1, the number of connected components of L X λ∗ is at least nX .
However, since DZ is a mixture of Gaussians, for any value of λ (including the special case λ = λ∗), LZλ can never have more than nZ connected components. Since G is continuous, it preserves the number of connected components, thus LG(Z)λ∗ = G(L Z λ∗) has at most nZ connected components. As nZ < nX , LXλ∗ and L G(Z) λ∗ can never agree on the number of connected components.
Corollary 1. If Theorem 2 is satisfied, there is a point x̂ ∈ Rn such that x̂ /∈ LXλ∗ but x̂ ∈ L G(Z) λ∗ .
Proof. Since nZ < nX , there exists a connected components Ĉ of L G(Z) λ∗ containing at least two connected components of SXλ∗ . Without loss of generality, assume Ĉ contains exactly two connected components C and C ′. By definition, λ-superlevel set is a closed set, so C and C ′ are disjoint closed sets. In Euclidean space Rn, the Urysohn’s lemma tells us that for any disjoint pair of closed sets A,A′ in Rn, there is a continuous function f such that f ∣A(x) = 0 and f ∣A′(x) = 1 for any x ∈ Rn. Especially, when A = C and A′ = C ′, there exists a continuous function f such that,
• f(x) = 0 for all x in C
• f(x) = 1 for all x in C ′
Consider S = f−1( 1 2 ) which is a separating plane separating C and C ′. If Ĉ ∩ S = ∅, then Ĉ ∩ S = f−1[0, 1 2 ) and Ĉ ∩ S = f−1( 1 2 ,1] will be two open set in subspace Ĉ, whose union is Ĉ. This implies that Ĉ is disconnected, which is a contradiction. Therefore, Ĉ ∩ S should be nonempty, and any point x in Ĉ ∩ S is not in LXλ∗ .

heading: D FURTHER DISCUSSIONS
text: D.1 COMPUTING DENSITY OVER A DATA-GENERATING MANIFOLD
When M is a Riemannian manifold equipped with a Riemannian metric g, we can compute probabilities over M . There are two essential components of probability computation: (a) a density function pM and (b) a measure dM over M . We assume pM and dM to satisfy the followings.
(R1) For any measurable subset A ⊂M , i.e., Pr[x ∈ A] = ∫x∈A pM(x)dM(x). (R2) p is zero everywhere out of M , i.e., supp(pM) = {x ∈ Rn ∣ pM(x) > 0} ⊆M (R3) For any (x, y), x is sampled from Mi if and only if y = i, i.e. Pr[x ∈Mi] = Pr[y = i]
When equipped with such pM and dM , we call M as a data-generating manifold.
Probability over a Riemannian manifold. We show how to compute a probability of x being generated from a Riemannian manifold M . We assume a k-dimensional manifold M equipped with a Riemannian metric g, a family of inner products gx on tangent spaces TxM . In this case, g induces the volume measure dM for integration overM . IfM is parameterized by x =X(u) for u ∈D ⊆ Rk, the integration of a density function pM on M is as follows.
∫ x∈M pM(x)dM(x) = ∫ u∈D
pM(X(u)) √ ∣det[gX(u)]∣du (8)
where [gX(u)] is the k × k matrix representation of the inner product gX(u) at X(u) ∈M .
In Appendix B, a concrete example of this computation will be provided.
D.2 DENSITY EXTENSION OF THE SECTION 3.2
This section introduces some remaining discussions regarding our data-generating process from a data-generating manifold.
Relation to kernel density estimation. While this extension is computing the density of compound distribution, it can be interpreted as computing expectation over a family of locally defined densities. Such an expected value can be observed in previous approaches of density estimation. For example, if νx is isotropic Gaussian for each x, the above integration is equivalent to the kernel density estimation, with Gaussian kernel, over infinitely many points on M .
Observed property of the extended density. In Figure 6b in Appendix B, we can observe that the extended density achieved higher values near the data-generating manifold. We formalize this observation to discuss its implication to the INC approach.
Let d(x̂,M) to be the minimum distance from x̂ to the manifold M .
(C1) For any given x̂, let y∗ be the class label whose conditional density p(x̂∣y = y∗) dominates p(x̂∣y = i) for i /= y∗,
y∗ ∈ argmax i∈[l] p(x̂∣y = i) (9)
and let My∗ be the manifold corresponding to y∗. (C2) For y∗ satisfying (C1), we choose y∗ such that the distance of x̂ from the manifold
d(x̂,My∗) is the smallest.
If there are multiple y∗ satisfying both of (C1) and (C2), we expect the following property to be true for all of those y∗.
(P1) Consider the shortest line from x̂ to the manifold My∗ . As x̂ goes closer to My∗ along this line, x̂ should be more likely to be generated as the influence of noise decreases when moving away from the manifold. Therefore, we expect our density pM to have the following property.
x∗ ∈ arg min x∈My∗ d(x̂,x)
Ô⇒ p(x̂) ≤ p((1 − λ)x̂ + λx∗) for all λ ∈ [0,1] (10)
Actually, this provides another justification of INC. In reality, the density conditioned by the label is not available even after running a generative model, so finding y∗ with (C1) is relatively hard. If we only consider (C2) without filtering y∗ via (C1), we are finding a point x ∈ M achieving the minimum distance to x̂, which is the optimization (11) above. Then projecting x̂ to the x∗, i.e. the solution of the optimization 11, can be explained by 10; when λ = 1, p is the highest along the shortest line between x̂ and x∗.
D.3 SUFFICIENT CONDITIONS FOR THE EXISTENCE OF RADII
We discuss the sufficient conditions guaranteeing the existence of radii introduced in Definition 1. Those sufficient conditions are derived from natural intuition about the properties of distributions in most machine-learning contexts.
The first intuition is that the influence of noise should diminish as observed sample x̂ moves away from a source point xo. Therefore, we formalize the noise whose density decreases as the noise n = x̂ − xo gets bigger. We formalize boundedness of noise densities via the boundedness of their λ-density superlevel sets and continuity of noise density via the continuity of individual νx. Definition 11 (Center-peaked noise density). Noise density functions νx are center-peaked, if for any source point x ∈M and any noise vector n ∈ Rn with ∥n ∥ > 0, νx(n) < νx(λn) for all λ ∈ [0,1). Definition 12 (Bounded noise density). Noise density functions νx are bounded, if a λ-density superlevel set is nonempty, there is a radius δ by which the λ-density superlevel set is bounded, i.e., Lνx,λ ⊆ Bδ(0) where Bδ(0) is the closed ball of radius δ centered at 0. Definition 13 (Continuous noise density). Noise density functions νx are continuous, if νx is continuous in Rn, for any x ∈M .
Under the conditions above, the radii in Definition 1 always exist. Proposition 1. If noise densities νx are center-peaked, bounded, and continuous, any nonempty λ-density superlevel set Lνx,λ has both λ-bounding radius δx,λ and λ-guaranteeing radius x,λ.
Proof. Let νx be a center peaked, superlevel set bounded family of continuous noise densities. Since νx is continuous, superlevel set Lνx,λ = ν −1 x [λ,∞) is closed as an inverse image of νx. Therefore, its boundary ∂Lνx,λ is contained in Lνx,λ.
Because νx is superlevel set bounded, superlevel set Lνx,λ is bounded by a closed ball Bδ(0) with radius δ ≥ 0. Since νx is center peaked, a nonempty superlevel set Lνx,λ always contains 0 as the maximum is achieved at 0. Moreover, there exists a closed neighborhood ball B (0) with radius ≥ 0 contained in the superlevel set Lνx,λ. Now it is enough to show that the minimum of δ and the maximum of exist.
Since Lνx,λ is bounded, its boundary ∂Lνx,λ is also bounded. ∂Lνx,λ is closed and bounded, thus it is a compact set. Therefore, the Euclidean norm, as a continuous function, should achieve the maximum r and the minimum r on ∂Lνx,λ by the extreme value theorem. From the choice of δ and , we can get,
≤ r ≤ r ≤ δ
Therefore, we can find the minimum δx,λ = r and the maximum x,λ = r.
D.4 GENERALIZATION OF THE THEOREM 1
We try generalizing the Theorem 2 to handle more concepts in topology. Theorem 2 mainly uses a fact that the number of connected components of λ-density superlevel set is preserved by a continuous generative model G.
In algebraic topology, each connected component corresponds to a generator of 0-th homology group H0, and continuity of a function is enough to preserve each component. In general, generators of i-th homology group Hi for i > 0 are not preserved by a continuous map, so we need to restrict G further. By requiring G to be a homeomorphism, we can safely guarantee that all topological properties are preserved by G; therefore, we can generalize the Theorem 2 with a homeomorphic generative model G.
To generalize the proof of the Theorem 2, we first provide the sketch of the proof.
(1) λ∗-density superlevel set LZλ∗ of a mixture of nZ Gaussian distributions has at most nZ connected components.
(2) Since G is continuous, the number of connected components of LGλ∗(Z) = G(L Z λ∗) is same
to the number of connected components of LZλ∗ , so it is also at most nZ . (3) We choose λ∗ so that LXλ∗ is included in δ
∗-neighborhood of M . (4) By assumption on the class-wise distance of M , δ∗-neighborhood of M has exactly same
number of connected components to M , i.e., nX . Therefore LXλ∗ has at least nX connected components.
(5) By (2) and (4), we conclude that LGλ∗(Z) and L X λ∗ do not agree on the number of connected
components as long as nZ < nX .
In this proof, nZ corresponds to the maximal 0-th Betti number of LZλ∗ , i.e. the number of generators of H0(LZλ∗). If we keep using a mixture of Gaussians as latent vector distribution, all components of LZλ∗ are contractible, so we may use 0 as the maximal i-th Betti number.
Also, nX corresponds to the 0-th Betti number of M and it worked as the minimal 0-th Betti number of LXλ∗ . The condition on the class-wise distance of M is used to ensure nX to be a lower bound. Combining these observations, we can get the following generalized statement. Theorem 3. Let DZ be a mixture of multivariate Gaussian distributions, and let DX be the target distribution from data-generating manifold M . Let ni be the i-th Betti number of M .
Consider a generative model G is used to approximate DX using the latent vectors sampled from DZ . Assume that G is a homeomorphism from Rn to itself. Assume that data-generating manifold satisfies the conditions of the Theorem 1, and let λ∗ be the threshold value that LXλ∗ corresponds
to that superlevel set. Assume that for some j > 0, the homomorphism ι∗ induced by the inclusion ι ∶M → Nδ∗(M) is injective. 5
If 0 < nj , LXλ∗ and L G(Z) λ∗ do not agree on the number of connected component.
Proof. Since LXλ∗ is the results of Theorem 1, it includes M and is included by δ ∗-neighborhood Nδ∗(M) of M . Define inclusions ι1, ι2 as,
• ι1 ∶M → LXλ∗
• ι2 ∶ LXλ∗ → Nδ∗(M)
Clearly, ι = ι2 ○ ι1.
Let ι∗1 and ι ∗ 2 be induced homomorphisms of ι1 and ι2, resp. By the assumption, any generator [a] in Hj(M) is injectively mapped to a nonzero generator ι∗([a]) in Hj(Nδ∗(M)). Therefore, the j-th Betti number of Nδ∗(M) is equal to that of M , i.e. nj . Note that j-th Betti number is the rank of j-th homology group rank(Hj(Nδ∗(M))) Because ι∗2 is a homomorphism from Hj(LXλ∗) to Hj(Nδ∗(M)), rank(L X λ∗) ≥ rank(Hj(Nδ∗(M))). Therefore the j-th Betti number of LXλ∗ is at least nj . However, since DZ is a mixture of Gaussians, for any value of λ (including the special case λ = λ∗), LZλ does not have any generator of j-th homology group, so it has j-th Betti number 0 for all j > 0. Since G is homeomorphic, it preserves all the Betti numbers, thus LG(Z)λ∗ = G(L Z λ∗) has the same j-th Betti number. As 0 < nj , LXλ∗ and L G(Z) λ∗ can never agree on the number of connected components.
In Section 5.2, we see the Figure 3i from the circles dataset, which is a remarkable example that LGλ (Z) has the same number of connected components, but does not have any loop (non-contractible circle). This is empirical evidence of Theorem 3, so it is explained by mismatches in the topology of distributions. Each concentric circle has Z as its first homology group as circle contains exactly one generator. However, latent vector distribution always has a trivial first homology group, as any superlevel set of a mixture of Gaussians is a set of contractible connected components.
D.5 DETAILS OF INC IMPLEMENTATIONS IN THE SECTION 5
INC implementation. We start from introducing the optimization for the ideal INC projection when the data-generating manifold M is available.
x∗ = argmin x∈M d(x, x̂) (11)
where d is a metric defined on the domainX . If perfect classification onM is assumed (model is welltrained on M ) and x̂ is close enough to the manifold of correct label, classification f(x∗) is likely to be correct, since x∗ is likely to lie on the correct manifold. Since the data-generating manifold M is unknown, the INC approach runs the following optimization with before the classification.
x∗ = G(z∗) where z∗ = arg min z∼DZ d(G(z), x̂) (12)
where d is a metric defined on the domain X . When INC is implemented with a reversible generative model G, for any given x̂ ∈ Rn there exists a trivial solution z∗ = G−1(x̂) to the optimization (12), achieving d(G(z∗),x) = 0. This is even true for x̂ out of the manifold, resulting in the situation that the output x∗ = G(z∗) = x̂ is still out of the data-generating manifold.
To manage this problem, we add another term penalizing a low density of latent vector to the objective function. Thus, in our INC implementation, we solve the following optimization problem.
x∗ = G(z∗) where z∗ = arg min z∼DZ [d(G(z), x̂) + α(M − pZ(z))] (13)
5Any generator of the j-th homology group Hj(M) of M is mapped to a nonzero generators of the j-th homology group Hj(Nδ∗(M)) of δ∗-neighborhood of M .
where α is the regularization factor and M is the maximum possible value of the density pZ of the latent vector distribution. For the choice of regularization factor, we used the same value α = 1 during the entire experiment.
To solve each optimization problem, we used the built-in adam optimizer (Kingma & Ba, 2014) in Tensorflow package. For optimization parameters, we ran 100 iterations of adam optimizer using learning rate 0.01 with random sampling of z.
When implementing INC using a class-aware generative model, we used the following strategy to improve its robustness.
• As the class-aware generative model generates each manifold from each Gaussian component, we first sample initial points from each manifold by randomly choosing latent vectors z1, . . . ,zl from each Gaussian component. • We run INC for i-th manifold by solving the following optimization.
x∗i = G(z∗i ) where z∗i = arg min z∼DZ [d(G(z), x̂) + α(Mi − pZ,i(z))]
where Mi is the maximum value of i-th Gaussian component. The regularization term is designed to penalize z which is unlikely to be generated by i-th Gaussian component, so we only search in the range of i-th Gaussian component, i.e., i-th manifold. • We choose the final solution x∗i achieving the minimum d(x ∗ i , x̂), breaking ties randomly.
Since each search is performed only on each submanifold, the artifact observed in Section 5.3 never appears during the optimization process. Also, choosing initial points from each manifold prevents the initialization problem mentioned in Section 5.3.
D.6 DISCUSSION ABOUT THE LIMITATION OF TOPOLOGICAL INFORMATION
Given a sufficient number of connected components in the latent vector distribution, does the classaware training suggested in this paper result in a generative model that achieves manifold separation? For this question, the answer is no, and the manifold separation depends on other factors, e.g., alignment of latent vector distribution, choice of training parameter, etc.
Figure 7b shows the superlevel set of DG(Z) from a class-aware training to learn the two-moons dataset when latent vector distribution is a mixture of two Gaussian distributions aligned horizontally (Figure 7a). It is clear that in this case, the generative model induced a connection artifact even when the class-aware training was used.
We explain this by interpreting reversible generative models as dynamical systems (Weinan, 2017; Chen et al., 2018; Grathwohl et al., 2018; Zhang et al., 2018). To elaborate, a reversible generative
model can be viewed as a dynamical system moving the latent vector distribution to the target distribution continuously in time. When two Gaussian mixtures are aligned vertically, a reversible generative model is likely to learn how to move the upper (and lower) Gaussian distribution toward the upper moon (and the lower moon, respectively), without being affected by the entanglement of two moons. However, moving the left (and right) Gaussian distribution toward the left moon (and the right moon, respectively) continuously in time is required to avoid the entanglement of two moons during the transition. This case alludes that information about the topological properties may not be enough to learn a generative model separating manifolds, because it does not provide an understanding of information about how data-generating manifolds are aligned.

heading: E MORE EXPERIMENTAL RESULTS
text: We present more experimental results about the INC performance comparing topology-aware generative model to its topology-ignorant counterpart.
Histogram for projection error distributions in 5.4. Figure 8 presents the histogram of the projection errors distributed from 0 to the diameter of the distribution. Each row corresponds to each dataset, whereas the first column and the second column represent the results from the topologyignorant model and the topology-aware model, respectively. All histograms are normalized so that the sum of values adds up to 1. To explain, the y-axis of each histogram is the estimated probability that INC achieves the projection error on the x-axis. Not only can we observe the improved mean of projection errors in the histograms, but we can also check the reduced standard deviation, i.e., we get more consistent projection errors near the mean.

Review summaries:
This paper argues that defenses against adversarial attacks need to be stronger than they currently are. Defenses that use generative models assume that there exists a manifold of data that is modeled by a trained generative model that can be used to project any out-of-manifold data unto the manifold. However, this work argues that if the generative model does not model the topology of the manifold, it can still be fooled by an adversarial example. They argue that a generative model needs to be at least aware of the number of connected components of the data-generating manifold. If the number of connected components does not match, based on theorem 2, Corollary 1 argues that a generative model can generate an adversarial example that does not exist in the data-generating manifold.