# Dual Graphs of Polyhedral Decompositions for the Detection of Adversarial Attacks

arXiv: https://arxiv.org/abs/2211.13305 · HTML: https://mlsanity.com/paper/2211.13305/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 39 references that are in the map.
- First posted on arXiv 23 Nov 2022.

## Builds on (most cited first, 29 of 29)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Adversarial Examples Are Not Bugs, They Are Features](https://mlsanity.com/paper/1905.02175/) (2019)
- [On Evaluating Adversarial Robustness](https://mlsanity.com/paper/1902.06705/) (2019)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [MagNet: a Two-Pronged Defense against Adversarial Examples](https://mlsanity.com/paper/1705.09064/) (2017)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Disentangling Adversarial Robustness and Generalization](https://mlsanity.com/paper/1812.00740/) (2018)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [Understanding Adversarial Attacks on Deep Learning Based Medical Image Analysis Systems](https://mlsanity.com/paper/1907.10456/) (2019)
- [Metric Learning for Adversarial Robustness](https://mlsanity.com/paper/1909.00900/) (2019)
- [Universal Adversarial Attack on Attention and the Resulting Dataset DAmageNet](https://mlsanity.com/paper/2001.06325/) (2020)
- [Dual Manifold Adversarial Robustness: Defense against Lp and non-Lp Adversarial Attacks](https://mlsanity.com/paper/2009.02470/) (2020)
- [A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance](https://mlsanity.com/paper/1901.10861/) (2019)
- [Detecting and Diagnosing Adversarial Images with Class-Conditional Capsule Reconstructions](https://mlsanity.com/paper/1907.02957/) (2019)
- [Reachable Set Estimation and Safety Verification for Piecewise Linear Systems with Neural Network Controllers](https://mlsanity.com/paper/1802.06981/) (2018)
- [A Framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networks](https://mlsanity.com/paper/1806.01918/) (2018)
- [Traversing the Local Polytopes of ReLU Neural Networks: A Unified Approach for Network Verification](https://mlsanity.com/paper/2111.08922/) (2021)
- [Reachability Analysis for Feed-Forward Neural Networks using Face Lattices](https://mlsanity.com/paper/2003.01226/) (2020)
- [Adversarial Examples Detection and Analysis with Layer-wise Autoencoders](https://mlsanity.com/paper/2006.10013/) (2020)
- [Locally Linear Attributes of ReLU Neural Networks](https://mlsanity.com/paper/2012.01940/) (2020)
- [Utilizing Network Properties to Detect Erroneous Inputs](https://mlsanity.com/paper/2002.12520/) (2020)
- [Examining the Proximity of Adversarial Examples to Class Manifolds in Deep Networks](https://mlsanity.com/paper/2204.05764/) (2022)

## Built on by (most cited first, 2 of 2)

- [Hamming Similarity and Graph Laplacians for Class Partitioning and Adversarial Image Detection](https://mlsanity.com/paper/2305.01808/) (2023)
- [Characterizing the Discrete Geometry of ReLU Networks](https://mlsanity.com/paper/2606.07728/) (2026)

## Abstract (arXiv)

Previous work has shown that a neural network with the rectified linear unit (ReLU) activation function leads to a convex polyhedral decomposition of the input space. These decompositions can be represented by a dual graph with vertices corresponding to polyhedra and edges corresponding to polyhedra sharing a facet, which is a subgraph of a Hamming graph. This paper illustrates how one can utilize the dual graph to detect and analyze adversarial attacks in the context of digital images. When an image passes through a network containing ReLU nodes, the firing or non-firing at a node can be encoded as a bit (1 for ReLU activation, 0 for ReLU non-activation). The sequence of all bit activations identifies the image with a bit vector, which identifies it with a polyhedron in the decomposition and, in turn, identifies it with a vertex in the dual graph. We identify ReLU bits that are discriminators between non-adversarial and adversarial images and examine how well collections of these discriminators can ensemble vote to build an adversarial image detector. Specifically, we examine the similarities and differences of ReLU bit vectors for adversarial images, and their non-adversarial counterparts, using a pre-trained ResNet-50 architecture. While this paper focuses on adversarial digital images, ResNet-50 architecture, and the ReLU activation function, our methods extend to other network architectures, activation functions, and types of datasets.