Adversarial Examples Target Topological Holes in Deep Networks

It is currently unclear why adversarial examples are easy to construct for deep networks that are otherwise successful with respect to their training domain. However, it is suspected that these adversarial examples lie within some small perturbation from the network's decision boundaries or exist in low-density regions with respect to the training distribution. Using persistent homology, we find that deep networks effectively have ``holes'' in their activation graphs, making them blind to regions of the input space that can be exploited by adversarial examples. These holes are effectively dense in the input space, making it easy to find a perturbed image that can be misclassified. By studying the topology of network activation, we find global patterns in the form of activation subgraphs which can both reliably determine whether an example is adversarial and can recover the true category of the example well above chance, implying that semantic information about the input is embedded globally via the activation pattern in deep networks.


Introduction
Sophisticated machine learning systems with impressive performance can be induced to make errors on inputs that are surprisingly similar to examples the learned system handles correctly (Gilmer et al., 2018a;Serban & Poll, 2018), termed adversarial examples. Adversarial examples have become an important issue in machine learning research due to the potential risks to security and robustness of machine learning systems, spawning efforts to design optimization procedures with robustness guarantees (Kolter & Wong, 2018;J.D. et al., 2018), and theoretical work on the robustness and the cost landscape . Despite the intense research, there is substantial controversy about why adversarial attacks work, with hypotheses ranging from optimization, to generic properties of deep networks (e.g. the linearity hypothesis, to intrinsic characterizations of the data manifold (Serban & Poll, 2018)).
Recently, Gilmer et al (Gilmer et al., 2018b) have shown that adversarial examples are close in input space to correctly classified points, suggesting a complex manifold geometry for non-adversarial examples in the input space that might result from approximating the input distribution by a limited set of training examples. Alternatively, complex manifold structure could be created through the interaction between network topology and the input data distribution. Deep feedforward networks apply a composition of functions on the input that transform the input through a sequence of homomorphisms. This sequence of transformations has the potential to induce a complex partition structure on the input space, including "holes" where class-critical information can be lost. Here we explore this possibility using methods from topological data analysis to analyze the structure of network activations due to adversarial examples. We show that topological analyses may be used to both identify adversarial examples and extract the correct labels from the subgraph structure of the learned network's activations.

Related Work
Various defense methods for adversarial examples have been proposed, such as defensive distillation (Papernot et al., 2016), feature squeezing (Xu et al., 2017), gradient masking or obfuscated gradient (Buckman et al., 2018;Ma et al., 2018;Samangouei et al., 2018), and adversarial training (Madry et al., 2017). Recent works have also focused on the detection of adversarial examples as a substitute for outright robustness. These methods look to classify adversarial examples based on features extracted from different layers of a deep network. Recent detection schemes include classifiers based on activation geometry via k-nearest neighbors (Katzir & Elovici, 2018), a detector based on the PCA projection of filters (Li & Li, 2017), or a learning framework that covers unexplored space in vulnerable models (Rouhani et al., 2018).
In addition to the numerous defense methods that have recently been proposed, recent insights have emerged, providing progress towards a fundamental understanding of adversarial examples. Most notably, Katz et al. (Katz et al., 2017) and Weng et al. (Weng et al., 2018)  LG] 28 Jan 2019 that computing a provably secure region of the input space is approximately computationally hard. Mahloujifar et al. (Mahloujifar et al., 2018) explain the prevalence of adversarial examples by making a connection to the "concentration of measure" in metric spaces. Recently, Zhange et al. (Zhang et al., 2019) found that adversaries are more dense sufficiently far from the manifold of training data.

Persistent Homology
Persistent homology provides a method for computing topological features of a space across arbitrarily many resolutions of the space. The topological features that persist across multiple spatial scales may be interpreted as being "true" topological features of the space under study. The decomposition, or filtration, of the space corresponds to a choice of metric between points in the space. In the discrete setting, the space is typically represented by a simplicial complex with the filtration describing how the space is constructed based on the chosen metric.

SIMPLICIAL HOMOLOGY
Let K be a simplicial complex. Under Z 2 coefficients, a p-chain is a subset of p-simplices of K. The set of p-chains, together with addition, forms a free abelian group C p called the p-th chain group of K. The boundary ∂ p (σ) of a ksimplex σ is the set of its (p − 1)-faces, and that of a pchain is the addition of the boundaries of its simplices. The boundary operator defines a homomorphism ∂ p : C p → C p−1 .
Define a p-cycle to be a p-chain with empty boundary and a p-boundary to be a p-chain in the image of ∂ p+1 . The collection of p-cycles and p-boundaries are called the pth cycle group Z p = ker ∂ p and the p-th boundary group B p = im ∂ p+1 , respectively. Both are subgroups of C p . The p-th homology group is the quotient group H p (K) = Z p /B p . Elements of H p are the homology classes α+B p = {α + b | b ∈ B p } for p-cycles α. We refer to α as the generating cycle of the homology class [α] = α + B p . Two p-cycles α and γ are homologous if [α] = [γ], that is, α + γ ∈ B p is the boundary of some (p + 1)-chain.
The rank of H p is called the p-th Betti number of K, denoted by β p . A basis of H p is a minimal set of homology classes that generates H p . A set of p-cycles A = {α 1 , α 2 , . . . , α n } generates H p , if the set of generators {[α i ]} forms a basis for H p where |A| = β p .

PERSISTENT HOMOLOGY
Let K be a simplicial complex. A filtration is a nested sequence of subcomplexes ∅ = K 0 ⊂ K 1 ⊂ · · · ⊂ K n = K. In other words, the filtration is a description of how we want to construct K by adding arbitrary-sized chunks at a time. With persistent homology, we are interested in the topological evolution of K as it is deconstructed, which is expressed by the corresponding sequence of homology groups. Since K i ⊂ K i−1 , the inclusion of each subcomplex into the larger complex induces a homomorphism between homology groups, f p : H p (K i−1 ) → H p (K i ). The nested sequences of complexes shown above thus corresponds to a sequence of homology groups connected by homomorphisms, There exists this sequence of homology groups for each dimension p. The filtration defines a partial ordering on the simplices with σ ⊂ K i − K i−1 preceding τ ⊂ K j − K j−1 if i < j. This extends to a total ordering for appropriate choice for how simplices are ordered for each K i − K i−1 .
The rank of im f p is the number of p-dimensional homology classes that are born at or before K i and are still alive at K j . We can encode each h ∈ im f p as a point in the half plane where the x-axis encodes the level in the filtration i where h first has a preimage in H p (K i ), and the y-axis encodes the earliest level in the filtration j where the image of h in H p (K j ) is trivial. This half-plane representation is called a persistence diagram, denoted Dgm(f p ).
For two functions f p and g p , we can compare their persistence diagrams using the Wasserstein distance which is defined as the q-th root of the infimum, over all matchings between the points, of the sum of q-th powers of the distance between matchings: where q is a positive, real number. In the limit for q going to infinity, we get the bottleneck distance which is the length of the longest edge in the best matching. Persistence diagrams are stable with respect to the bottleneck distance (Cohen-Steiner et al., 2007).

Neural Network Topology
By viewing a neural network as an undirected graph-a topological space-we can use persistent homology to investigate its invariant topological properties across all edge weight resolutions. We consider only forward architectures in this construction, but a similar approach may be used to investigate more complex architectures with, for example, recurrent structure.
There are two ways to construct a graph representation of a neural network. These are the static network consisting of (possibly trained) weight matrices connecting each layer's nodes to the next layer's, and the induced network consisting of this same structure augmented by the activation functions and an input applied to the neural network. In this paper, we are concerned with the latter induced graphical structure, but both structures may be used to provide insight into the function of neural networks. Fix a feedforward neural network architecture with L layers. Let G I = (V, E, φ) be the network's graphical representation induced by input I. Here V is the set of nodes in the network including input, hidden, and output nodes, E is the set of edges between nodes, and φ : E → R is a function assigning weights to edges. G I is a multipartite graph where each node in a given layer may share an edge only with the previous and next layers' nodes. In other words, Define h l ∈ R |V l | to be the activation values for each node in layer l. Define h l u to be the u'th entry in vector h l . For notational simplicity, we will drop the layer l superscript when the layer is obvious. Let W l be the weight matrix connecting the node set V l to V l+1 . This weight matrix is either the true weight matrix if layer l is fully-connected, or if l is a convolutional layer, the unrolled filter matrix described below. Let the entry in W l corresponding to the v'th row and u'th column be denoted by w l u→v . Again, we will drop this layer superscript unless otherwise necessary. With this information, we define the edge weighting for We use the absolute value of the hidden activation times the corresponding weight parameter to align the ordering of simplices in the filtration with the corresponding relationship to network semantics where (high activation or high suppression) are more important to classification decisions, whereas activation values close to 0 are negligible in their semantic role.
The filtration of G I is defined via filtration on φ. We have N = |E| values of φ which can be ordered by ≥ such that max is defined by adding the corresponding edge (1-simplex) and vertices (0-simplices) of each ω i into the graph. In other words, G I 0 is the graph consisting of only the highest weight edge (the 1-simplex given by max E φ) along with the vertices (0-simplices) connected by that edge, G I 1 is the (potentially disjoint) graph consisting of the previously described edge and vertices along with the edge and vertices associated to ω 1 , etc.
The intuition for constructing the input-induced graph from a neural network is as follows. For each fully-connected layer, we connect each hidden node of layer l to each hidden node in layer l + 1 with an edge. The weight of this edge is the activation value of the hidden node multiplied by the corresponding element in weight matrix W l . The graphical construction for convolutional layers is similar but requires slightly more preprocessing. For each incoming channel, unroll the convolution operation into a (sparse) matrix multiplication operation. This multiplication operation operation then induces a graphical representation like in the fully-connected case. Because this operation is sparse, most of the edges have weight 0, indicating a stride of the filter whose preimage did not include that neuron. This sparsity can be easily filtered out as it does not affect the persistence calculation. Although not discussed in the paper, other forward architecture layer options like max pooling or bias weights can be translated to this graphical construction.

Persistent Subgraphs
With a filtration on G I , we can compute its persistent homology. We say a homology class α is born at G I i if it is not in the image of the map induced by the inclusion We call j −i the lifetime or persistence of the topological feature generated by α. The filtration on G I induces the sequence of homology groups The lifetime of a feature born at level i in the filtration and dying at level j in the filtration is precisely the rank of the persistent homology group H i,j p (G I ). For each dimension p, these persistent topological features can be represented as vectors in the half-plane via a persistence diagram ( Figure  2) where more persistent features are located farther off the diagonal, while features that may be considered topological noise are associated to points near or along the diagonal.
We are interested in zero-dimensional (p = 0) topological information within this paper. Higher-dimensional topological features like holes and voids can be analyzed using a similar formulation, but the interpretation of these features with respect to neural network classification performance is less clear. By contrast, zero-dimensional topological features in this network space correspond to connected components, with the homology sequence describing how various components are created and merged with larger structures across various weight scales within the filtration. As we will see, these connected components capture important semantic information within the feature space of the neural network.
Each α homology feature represents an equivalence class of some non-boundary cycle, so we can only pick a representative subgraph for a particular persistent connected component. However, because each of a typical neural network's (non-zero) weights are unique, we are nearly guaranteed that each equivalence class will contain only one element, namely the generator itself. In fact, a trained network that reliably contains non-trivial equivalence classes would only be optimal in a domain with high symmetry in input space. With stochastic weight updates and random initialization, the probability of encountering such a network is extremely low. If such a network is encountered, the persistent subgraphs corresponding to these generators can still be captured through the representative, but information on the number of connected components represented by this symmetric feature in input space is lost.
With identification of the nodes and edges associated with each simplex in the filtration, we can reconstruct the subgraphs within the neural network that represent these persistent topological features. Let A I = {α 1 , α 2 , . . . α n } be the set of 0-cycle generators for H 0 (G I ). Each α i is a simplicial complex that may be represented as some subgraph of G I . Equivalently, and under a slight abuse of notation,

Origins of Holes in Network Activations
One of the critical reasons for introducing the induced graph network topology is that it reveals holes in network sensitivity to the input space. Local holes arise from input activations being mapping into the kernel (null-space) of a neuron in the network, and these holes can propagate through subsequent processing layers. In general, activations mapped into a null-space at a layer i create deaths of a subgraph feature. An analysis of topological persistence under function composition shows that the kernels of mappings generally stably persist with respect to the bottleneck distance under function composition (Cohen-Steiner et al., 2009). Thus, activations mapping into a null-space at a node-level can create persistent loss of information that can be adversarially exploited (by perturbing class-diagnostic image features into local null-spaces). However, persistence diagrams over the induced network graph capture these holes in the birth-death structure.
The general conclusion that holes persist can be better appreciated by examining the conditions under which it fails. At a layer i − 1 the vector of activations a across nodes k in the layer span a space X i−1 . A local hole is created if a is in the null-space of a downstream neuron u in layer i, h u = 0. The zero component will be propagated to subsequent layers unless compensated for. Let f v represent the activation function (ReLU, Sigmoid, identity, etc.) applied to each hidden node v in layer i + 1. The activation value for node v is where w u→v is the weight parameter learned by the network connecting node u to node v. In this case, the edge weighting φ(u, v) goes to zero, which removes the edge. For a to survive along some other edge, there needs to be other neurons u which collectively span ker u. Unless each layer's mapping is injective, this is not possible to guarantee.
Although holes are likely to persist for topological reasons, the conditions for holes to be "covered over" could be created as a byproduct of network optimization. Experiments show that the essential characteristics predicted do in fact occur and can be used to both identify and classify adversarial examples.

Experiments
We implement the ideas provided in the previous sections using four neural network architectures of reasonable size across two datasets. We see that our topological approach is useful in analyzing the global activation graph of neural networks and can be used to both detect and recover from adversarial inputs.
We train four architectures on the MNIST and Fashion MNIST datasets. All networks are trained for 20 epochs on each dataset using stochastic gradient descent with learning rate 0.01. The first architecture is a simple three-layer linear network with layer sizes 784x256, 256x50, and 50x10. We refer to this network as the FFF network. The second architecture is a three layer network consisting of a single convolutional layer with 5, 5x5 filters and ReLU activations followed by two fully-connected layers of size 2880x50 and 50x10 also with ReLU activations. We refer to this network as the CFF-Relu network. The third architecture is identical to the previous but substitutes sigmoid for ReLU activations. We refer to this network as the CFF-Sigmoid network. The final network is a two-layer convolutional network followed by two fully-connected layers. The first convolutional layer has 3, 5x5 filters. The second convolutional layer consists of 3, 3x3 filters. The fully-connected layers are of size 1452x256 and 256x10. All layers of this network use ReLU activations. We call this the CCFF-Relu network.

Adversaries
For each network and dataset combination, we create a set of adversaries based off of the test set of each dataset. We create adversaries through four different methods. The first set of adversaries were created using box-constrained L-BFGS as in (Szegedy et al., 2013) to minimize the distance between the image and the adversarial as well as the crossentropy between the predictions for the adversarial and the target class. We set = 10 −5 . The second adversarial algorithm is the L 2 version of the Carlini Wagner adversaries described in (Carlini & Wagner, 2017) which we refer to as C&W L 2 . The third adversarial generation algorithm is the Projected Gradient Descent Attack as described in (Madry et al., 2017) with = 0.001 and step size 0.01. We refer to this algorithm as PGD. The final adversarial generation algorithm consists of the repeated addition of Gaussian noise to the original image until it is misclassified by the network.

Subgraph Spectra
If adversaries do exploit holes in deep network activation graphs, we would expect to see artifacts of this within the structure of persistent subgraphs induced by adversaries when compared to the subgraphs of unaltered inputs. In particular, the initial fragmentation of the subgraph structure leaves room for adversarial examples to further fragment the network activations, resulting in changes in the final layer predictions. We expect that fragmentation will be diagnostic for adversarial inputs. By analyzing the subgraph connectivity using spectral methods, we will see below that the structure of the persistent subgraphs differs significantly both between unaltered and adversarial inputs and across architectures.
Recall from Section 2.1 that for each image I fed into the network, persistent homology provides us with a set of generators A I = {α 1 , α 2 , . . . α n } where each α i may be represented as a subgraph of G I .
For each dataset and network, we take the first 2,000 images of the test sets and create a corresponding adversary for each method described in Section 4.1, leaving us with 2,000 adversarial and 2,000 unaltered test images. We then feed each of these images into their respective network-capturing the hidden activations and parameters-and compute each image's induced persistent subgraphs A I as described in Section 2 along with their persistence diagrams. We then take the graph union S I = αi∈A I α i across all generating subgraphs, leaving us with a single graph object S I for each input. Unioned subgraphs for the top ten and bottom ten most persistent subgraphs for the CFF-Relu network can be seen in Figure 3.
Persistent subgraphs represent the paths of highest activation flow through the network induced by a given input, potentially spanning multiple layers. One may also view the induced persistent subgraphs as partial transformations performed by the neural network on the input. Inspired by this idea, we assess the connectivity structure of these subgraphs by computing the weighted graph Laplacian matrix for each S I and compute its eigenvalues. The graph Laplacian yields critical information about the connectivity structure of the subgraphs. Fully connected subgraphs are dominated by a few large eigenvalues, while highly fragmented graphs have many small eigenvalues more similar in value. The mean of the subgraph eigenvalues is a simple measure of this structure. We compute the expected value of the average Laplacian subgraph eigenvalue across adversarial and unaltered inputs, as well as the size of the subgraphs (Fragment Size) given by the number of vertices in the subgraph. These results are shown in Table 1 for each dataset and adversarial algorithm.
We hypothesized that adversarial examples would be more likely to map to holes, which predicts smaller average eigenvalues, higher variance in eigenvalues across exemplars, and a larger number of distinct subgraphs. As is evident from Table 1, these predictions are confirmed.

Subgraph Classification
We can see from Figure 4 that even when restricted to only information within the persistence diagram (number of generators and their lifetimes), persistent homology still captures information about the input through the network activation graph. We see even for the more sophisticated C&W L 2 attack a nearly linear relationship between L ∞ distance in image space and Wasserstein distance between persistence diagrams, implying that persistent homology is able to capture information about the input space from the activation graph, even when the network itself misclassifies the input. In this section, we make use of this observation by vectorizing each persistent subgraph S I and training a classifier to predict the true class of an input I given each S I .
As in Section 4.2, we create a set of adversaries from 2,000 test images for each adversary generation algorithm, dataset, and network architecture. Fix a network architecture, dataset, and adversary generation method. Let U be the set of unaltered images and A the set of adversarial images. Also define U = {S I | I ∈ U} as the set of persistent subgraphs computed from each unaltered image. Let Λ = {S I | I ∈ A} be the persistent subgraphs for each adversarial image. Define U train ⊂ U as a training subset of unaltered induced subgraphs. Let N = |U train | be the size of the training set. Each training set image has a corresponding class label representing the true class of the input image.
We create a simple one-hot edge occupancy vectorization for the entire training set U train , where each unique edge in U train is represented by a dimension in the vectorization, and induced subgraphs S I train ∈ U train have value 1 along a dimension if they contain that edge. Let We train a simple one-versus-one Support Vector Machine (SVM) (Cortes & Vapnik, 1995) with linear kernel. Using this classifier, we perform two classification tasks. For the first, we investigate the extent to which these subgraphs represent class-specific information encoded by the network activation structure. For this, we segment U into training and test sets U train and U test , and compute the associated vectorization X train . We then vectorize the test set according to the edges corresponding to the dimensions of X train , resulting in matrix X test . For each dataset, architecture, and adversarial generation method, we train an SVM to predict the class of each input represented by X test . The mean accuracy across 10-fold cross-validation is reported in Table  2.
For the second classification task, we are interested in the extent to which the network activation structure is able to retain information about adversarial inputs, despite misclassification. We take U train = U and take A to be the test set. We again vectorize the subgraphs through the training edge set. For each dataset, architecture, and adversary method, we train an SVM to predict the class of the input based only off of the persistent subgraph information. The accuracy of the original network on U, the accuracy of the SVM in recovering the true class from an adversarial input (Recovery Accuracy) and percentage of inputs classified by the SVM as being of the class of the accuracy (Adversary Retention Rate) are shown in Table 3. All networks have Network Accuracy of 0% on their adversary test set A.
As expected, the persistent subgraphs capture information about the input that is otherwise obfuscated by adversarial alterations in the original image that change the activation structure enough to cause the network to misclassify. The Recovery Accuracy follows from our observations in 4. Gaussian Noise and L-BFGS are the least precise adversarial generation methods of the group, meaning they generate adversaries with larger differences between the original input and the adversary than PGD and C&W L 2 . We see that more sophisticated adversarial algorithms that produce images that are not noticeably different than the original image are more likely to be recoverable using persistent subgraphs than algorithms that distort the image more severely.
Also note that the Subgraph SVM classification method performs better than the original FFF-Relu network when classifying unaltered images. In this scenario, the original network acts as a "feature preprocessor" for the Subgraph SVM. It is likely that adding more layers-thus adding more capacity-to the network would shrink this disparity between the Network Accuracy and Subgraph SVM Accuracy.

Discussion
We have shown that persistent homology is a useful tool for analyzing the activation structure of deep networks, providing a way to both detect strucutral changes introduced by adversarial inputs and to recover the correct class of the input despite its adversarial nature.  robustness focus primarily on training procedures (adversarial training, normalization, compression, label smoothing).
Here we show that neural network architectures themselves are inherently susceptible to adversarial attacks based on the prevalence of holes in activation space that are readily exploited by adversaries to change the classification decisions of the network. Our ability to diagnose and correctly classify adversarial examples from the activations structure alone is surprising, but opens new possibilities and principles for designing robust neural systems.
Exploring other architectures and robustness procedures would be an important avenue of further research related to adversarial targeting of holes in network activation space. For example, how might adversarial training affect the subgraph structure of the networks? We anticipate that a network with adversarial training would admit fewer holes. However, the kernel space of any given neuron is quite large, so to what extent these holes may be filled through adversarial training is an open question. Our results im-ply architectural decisions that compress the kernel space of each hidden node may be better suited to maximize adversarial robustness. We expect networks like ResNet (He et al., 2016) with multiple connections between layers to be more robust to adversaries than their counterparts without pass-through connections.
However, our analysis in its current state faces many limitations. Computing persistent homology for a deep network requires one to capture the activation record across layers and to reconstruct this information within the filtration. A 100x10 fully-connected layer has potentially 1,110 simplices, and a similarly-sized convolutional layer with numerous channels can be even larger. Expectedly, this approach scales neither in memory nor computation. Better sampling strategies over the network and filtration could solve some of these computational limitations. For example, replacing our full network simplicial complex by a variant of the Witness Complex (De Silva & Carlsson, 2004) could reduce memory and computational burdens significantly. As well, computing the entire subgraph structure is likely overkill for most practical applications. In Section 4.3, the networks with ReLU activations reached an equivalent Recovery Accuracy using only the union of the top 3 generators.

Conclusion
The brittleness of machine learning systems to adversarial attacks poses major challenges for security and robustness of large scale systems. Here we show that susceptibility to adversarial attack is partly attributable to the network architecture per se. Using persistent homology we show that adversarial examples map into topological holes in the induced network graph, both explaining which examples are adversarial and providing new methods to correctly classify them using the same network, because class information is still embedded in higher-order information contained in the activation subgraphs. These results provide new principles for understanding adversarial attacks and the possibility of improved architectures and meta-learning approaches to robust, interpretable, and safe learning.