Antimodes and Graphical Anomaly Exploration via Adaptive Depth Quantile Functions

As said above, one of the advantages of the DQF approach is to provide a methodology for the visual exploration of geometric structure in data (including outliers, clusters, etc.) in any dimension, and even for non-Euclidean data via the kernel-trick. It turns out, however, that important insight can be gained by studying the DQF in dimension one, which also has the benefit of providing a gentle introduction to the DQF approach.

We first introduce the so-called depth functions. For $d=1$, the random subsets (cones) considered by the DQF approach are simply half-infinite intervals induced by a random split point $S$. For a probability measure $F$, we use the shorthand $F(x)=F((-\infty,x]),x\in{\mathbb{R}}$ to denote the distribution function. Given a point $x\in{\mathbb{R}}$, and a realization $s$ of $S$, define

where we notice, for instance when $s\geq x$, $d_{x}(s)$ is the Tukey depth of $x$ with respect to $F$ restricted to $(-\infty,s]$. Similarly, $d_{x}(s)$ also is the Tukey depth of $x$ in case $s<x,$ but this time for $F$ restricted to $[s,\infty).$ So, while the notion of centrality used by the DQF approach is Tukey’s (1975) data depth, it is with respect to an improper distribution, as we don’t rescale the mass on the subset.

Clearly, $d_{x}(s)$ is non-decreasing when $s$ moves away from $x$ in either direction, and the values for $s$ on the boundaries of the support of $F$ (which could be $\pm\infty$) are both equal to the global Tukey depth ${\rm TD}(x,F)$. Figure 2 shows functions $d_{x}(s)$ for a variety of $x$ values on a grid with $F$ admitting a symmetric density on $[0,1]$ comprised of two isosceles triangles.

The random variable $S\sim G$ induces a distribution on $d_{x}(S)$, and the corresponding quantile function,

is the object of interest, where, for a distribution $G$ and a measurable set $A$, we let $G(A)$ denote the probability content of $A$ under $G$. The parameter $\delta$ can be thought of as measuring the scale at which information is extracted.

Empirical versions are obtained by replacing $F$ with the empirical distribution $F_{n}$ based on the observations $X_{1},\ldots,X_{n},$ i.e. with

where we again use the shorthand $F_{n}(x)=F_{n}((-\infty,x]).$ Let

(note that $G$ is the (marginal) distribution of $S$, so that $G(\widehat{d}_{x}(S)\leq t)$ depends on the data).

The following lemma addresses the median property and the zero interval property of the DQF. The median property is related to the concept of an antimode, while the presence of a zero interval is closely related to anomaly detection, as will be discussed further below. Figure 3 below illustrates the assertions of the lemma geometrically.

The zero interval property expressed in (6) also holds in the multivariate case (see Lemma 2.2). It is quite important in the context of anomaly detection, as it provides an explanation for the empirical observation that the behavior of the DQF for small values of $\delta$ has a discriminatory effect in the context of anomaly detection. One of the situations in which this is of particular interest is when the anchor point $x$ is chosen as the midpoint between two observations, which might fall outside the support of $F$. All of this will be discussed in detail below.

The statement directly follows from the representation of $q_{x}(\delta)$ given in (5) by assuming that $F$ is not constant in a neighborhood of $x$.

The above results, more precisely, (6) and Corollary 2.1, show that the DQF is informative at both large and small scales, i.e. for large and small values of $\delta$, motivating the usefulness of the entire function in examining a data set. An analogous property for the case $d\geq 2$ can be found in Chandler and Polonik (2021). This property is in contrast to other multi-scale methods, such as the mode tree (Minnotte and Scott, 1993), which transitions from $n$ modes to 1 (thus no information on either extreme), or a multi-scale version of the shorth which we discuss and explore in section 3.

As localization is an important aspect of the DQF for small values of $\delta$, one finds that half-spaces as our random subsets will not suffice. Rather, we consider subsets of the data space formed by spherically symmetric cones with opening angle $\alpha$ strictly less than $\pi/4$ (the angle between a point on the surface of the cone and the axis of symmetry). We use spherical cones to not privilege any particular direction in our space beyond the specified axis of symmetry for the cone. The question is then how to put a distribution over cones in order to compute quantile functions.

First we discuss the construction of the empirical version of the DQF. For any two points in the data set, say $x_{i}$ and $x_{j}$, let $\ell_{ij}$ denote the line passing through them, and consider spherically symmetric cones $C_{ij}(s)$ with $\ell_{ij}$ as axis of symmetry, $s$ as the tip located on $\ell_{ij}$, and a fixed opening angle $\alpha$, which is a tuning parameter. Select a point $m_{ij}$ on that line as the “anchor point.” The choice of $m_{ij}$ might depend on the specific application considered. In our applications, we choose $m_{ij}=\frac{x_{i}+x_{j}}{2}$, the midpoint, but it could also be $x_{i}$, or $x_{j}$, as we are using in the one-dimensional case discussed above. See section 4.1 for discussion of this choice. The orientation of the cone $C_{ij}(s)$ is such that $m_{ij}$ is contained inside. In other words, the orientation of the cones flips depending on which side of $m_{ij}$ the tip lies.

Given any such cone $C_{ij}(s)$, split the cone into two parts $A_{ij}(s)$ and $B_{ij}(s)=C_{ij}(s)\setminus A_{ij}(s)$ with $A_{ij}(s)$ being the “top part” of the cone, obtained by cutting $C_{ij}(s)$ along a hyperplane orthogonal to $\ell_{ij}$ passing through $m_{ij}$. We sometimes also call these two type of sets $A$-sets (cones themselves) and $B$-sets (frustums). The base of $A_{x,y}(s)$ (or the top of $B_{x,y}(s)$) is considered to be part of $A_{x,y}(s)$ but not of $B_{x,y}(s)$. Then, the measure of centrality of $m_{ij}$ that we are using is the depth

Equivalently, one can think of constructing $\hat{d}_{ij}(s)$ by projecting the data lying inside the cone $C_{ij}(s)$ onto $\ell_{ij}.$ Then $\hat{d}_{ij}(s)$ is the one dimensional Tukey depth of $m_{ij}$ among these projections, again with respect to the improper empirical (sub)distribution.

Finally, we choose the tip randomly according to a distribution $G_{ij}(s)$ along the axis of symmetry $\ell_{ij}$. (Choosing $G_{ij}$ is discussed in 2.3.) The DQF $\hat{q}_{ij}(\delta)$ is then defined as the quantile function of the distribution of the random depths with respect to $G_{ij}(s)$, i.e.

where, for a measurable set $D\subset\ell_{ij}$ we let $G(D)$ denote the $G$-measure of $D$. Note that $G_{ij}(s:\hat{d}_{ij}(s)\leq t)$ depends on all of the data. One might use different approaches to reduce the total number of functions $\hat{q}_{ij}(\delta)$ to consider. A natural approach is to use averaging: For each data point $x_{i},$ average the functions $\hat{q}_{ij}(\delta)$ over $j\neq i$, i.e. for each $x_{i}$, we consider

More robust approaches include Winsorized averages, truncated averages, etc. A slightly different summary is to consider normalized averages of the DQFs of the form

These normalized averages embed the global behavior of the DQF at all $\delta$ values and focus solely on the shape of the DQF.

Population versions of the empirical depth functions $\hat{d}_{ij}(s)$ and the corresponding empirical DQFs are defined as follows. For $x,y\in{\mathbb{R}}^{d}$, let $\ell_{x,y}$ denote the line passing through both $x$ and $y$. For $s\in\ell_{x,y}$ let $C_{x,y}(s)$ denote the spherically symmetric cone in ${\mathbb{R}}^{d}$ with tip $s$ containing the anchor point, say $m_{x,y}=\frac{x+y}{2},$ with axis of symmetry given by $\ell_{x,y}$, and with opening angle given by the tuning parameter $\alpha$. The hyperplane through $m_{x,y}$ perpendicular to $u$ again divides $C_{x,y}(s)$ into two sets, a cone $A_{x,y}(s)$ and a frustum $B_{x,y}(s),$ where for definiteness, the intersection of the hyperplane and the cone (the base of $A_{x,y}(s)$ or the top of $B_{x,y}(s)$) is considered to be part of $A_{x,y}(s)$ but not of $B_{x,y}(s)$. Then,

Similar to the empirical version, $d_{x,y}(s)$ is the one-dimensional Tukey depth of the (sub)distribution obtained by projecting the mass of the cone $C_{x,y}(s)$ onto the axis of symmetry $\ell_{x,y}$. Figure 4 illustrates this for a two-dimensional bi-modal density.

Again, choosing the tip randomly on the line $\ell_{x,y}$ according to $S\sim G=G_{x,y}$ results in a random variable $d_{x,y}(S)$ whose quantile function is the DQF $q_{x,y}(\delta)$. Formally,

The empirical average $\overline{q}_{i}(\delta)$ corresponds to

and similarly $\tilde{q}_{x}(\delta)=\frac{\overline{q}_{x}(\delta)}{\overline{q}_{x}(1)}$ is the normalized expected DQF. As already mentioned, a result for $d\geq 2$, analogous to Corollary 2.1 can be found in Chandler and Polonik (2021). The flatness of the DQF for anchor points lying outside the support of $F$, i.e. a result analogous to the last assertion of Lemma 2.1, also holds for $d\geq 2,$ as shown in Lemma 2.2.

We use the following setting: For a given distribution $F$ on ${\mathbb{R}}^{d}$ with compact support (for simplicity) and $x,y\in{\mathbb{R}}^{d}$, let $[a_{x,y},b_{x,y}]\subseteq\ell_{x,y}$ denote the range of the push-forward distribution on $\ell_{x,y}$ obtained by the projection map $\pi_{x,y}(z)$, which is the orthogonal projection of $z\in{\mathbb{R}}^{d}$ onto $\ell_{x,y}.$ We assume $\|b_{x,y}-a_{x,y}\|>0$. Let $G_{x,y}$ denote a continuous distribution on $[a_{x,y},b_{x,y}]$. This is a distribution on the “one-dimensional interval” of length $\|b_{x,y}-a_{x,y}\|$. Also, we represent $\ell_{x,y}$ as $\ell_{x,y}=\{z\in{\mathbb{R}}^{d}:\,z=m_{x,y}+tu_{x,y},t\in{\mathbb{R}}\}$, where $m_{x,y}$ is the anchor point, and $u_{x,y}\in S^{d-1}$ is the unit vector giving the direction of $\ell_{x,y}.$

Geometrically, the quantity $t^{+}_{x,y}+t^{-}_{x,y}=\|s^{+}_{x,y}-s^{-}_{x,y}\|$ is the sum of the heights of two cones $A_{x,y}(s^{+}_{x,y}),A_{x,y}(s^{-}_{x,y})$, see Figure 5. Note that the two cones point in opposite directions, and by definition of $t^{+}_{x,y}$ and $t^{-}_{x,y}$, they are chosen such that they give the largest spherically symmetric cones under consideration that do not intersect with the support of $F.$ Also note that the two cones belong to the same anchor point that is lying between the bases of these two cones.

Suppose that the support of $F$ has a hole and the anchor point $m_{x,y}$ lies in this hole (think of $m_{x,y}$ as the midpoint between $x$ and $y$), then the $G_{x,y}$-measure of the combined heights, $\delta_{x,y}=G_{x,y}([s^{-}_{x,y},s^{+}_{x,y}]),$ measures some aspects of the geometry of the hole. Moreover, if, for a given $x$, there is a high probability that a randomly chosen $y$ is such that the corresponding anchor point lies off the support of $F$, then $\overline{q}_{x}(\delta)$ will also be small for a range of small values of $\delta.$ (Recall also that everything depends on the opening angle of the cones as well.)

Also note that Lemma 2.2 is a generalization of the one-dimensional case presented in the last part of Lemma 2.1. In this one-dimensional case there is of course no need to consider pairs since there is only one axis. For further discussion of the population version and theoretical properties of the corresponding estimators, see Chandler and Polonik (2021).

In order to pronounce the discriminatory effect of the (near) zero intervals of the DQFs that has been discussed above (cf. type 1 zero intervals), we now introduce the adaptive DQF. The adaptation of the DQF approach is achieved via the function $G_{x,y}$, which is one of the “tuning parameters.” Again the discussion is presented in the population setting.

The formal results presented above, i.e., Lemma 2.1, Corollary 2.1 and Lemma 2.2 provide important insights into the role of the distribution $G_{x,y}$ in the context of anomaly detection. Consider depth quantile functions $q_{x,y}(\delta)$ with base points $m_{x,y}$. Our results imply that, for points $x$ such that $m_{x,y}$ is close to an antimode, or even falls outside the support, $q_{x,y}$ will tend to exhibit a (near) zero interval for values of $\delta$ close to zero. On the other hand, if $m_{x,y}$ lies in the bulk of the data, then the slope of $q_{x,y}$ for small $\delta$ will tend to be large. This interpretation is mainly motivated by the magnitude of $f(m_{x,y})$. However, our results tell us that one actually should consider the magnitude of the ratio $\frac{f}{g}(m_{x,y})$ instead. The goal of adaptation now is to attempt to choose $G_{x,y}$ depending on $m_{x,y}$ in order to pronounce the discriminatory effect of the DQF described above, where we have type 1 anomalies in mind, i.e. $g_{x,y}$ should be (relatively) large for anomalous points $x$ and (relatively) small for non-anomalous points near $m_{x,y}$. To put it differently, the concentration of $G_{x,y}$ about $m_{x,y}$ should be pronounced when $x$ is an anomalous point.

Adaptive uniform distributions. Here we propose to choose $G_{x,y}$ as the uniform distribution on $\ell_{x,y}$ over the range $[a_{x,y},b_{x,y}]$ of the push-forward distribution under the projection of $F$ onto $\ell_{x,y}.$ In practice, we of course use the empirical analog (projecting the empirical distribution onto $\ell_{x,y}$). This choice can be motivated as follows:

Consider again a contamination model on ${\mathbb{R}}^{d}$ of the form $(1-\epsilon)P+\epsilon Q,$ where $\epsilon>0$ is “small”, with $P$ a uniform distribution on the support $S_{P}$, and $S_{Q}\cap S_{P}=\emptyset.$ Suppose we use $\frac{x+y}{2}$ as the anchor point. For $X\sim P$ and $y\in S_{Q}$, the gap between $S_{P}$ and $y$ is measured by $\delta_{X,y}$, the length of the zero-interval of $q_{X,y}$ from Lemma 2.2. Notice, however, that the same physical gap (Hausdorff distance between $S_{Q}$ and $S_{P}$) can lead to different distributions of $\delta_{X,y}$, depending on where $S_{Q}$ is located under an adaptive choice of $G_{x,y}$. For instance, suppose that $S_{P}$ is an elongated ellipsoid, and $S_{Q}$ is a ball with Hausdorff distance to $S_{P}$ being a given positive value. Then, using a similar rational as described above, we can see from Lemma 2.2 that with this adaptive choice of $G_{x,y}$, the values of $\delta_{x,y}$ will tend to be smaller if $S_{Q}$ is located along the main axis of $S_{P}$ than if it is located along one of the minor axis. The reason is that the range of the corresponding push-forward distributions tends to be larger in the former case, and $\delta_{X,y}$ is the physical length of the gap divided by the range. In this latter case, this will lead to small values of the averaged DQF, $\overline{q}_{y}(\delta),y\in S_{Q}$ for a larger range of $\delta$. The rational for this adaptive choice is similar to that of Mahalonobis distance, as a point at a fixed distance from $S_{P}$ in the direction of a minor axis is arguably more of an anomaly than one along the main axis. The same rational holds if we have a non-uniform distribution on $S_{P}$.

Adaptive normal distributions: An adaptive choice for $G_{x,y}$ showing a strong performance in our simulation studies is a normal distribution on $\ell_{x,y}$ with mean $m_{x,y}$ chosen as the midpoint, and variance equal to a robust estimate of the variance of the push-forward distribution of the projection of $F$ onto $\ell_{x,y}$, such as a Windsorized variance. The heuristic idea is that for an anomalous point $x$ and the previous model, removing the extreme points (Windsorizing) means removing outliers, which then will result in a variance estimate that is smaller for anomalous points than for non-anomalous points. The above discussion then shows that this leads to a longer (near) zero interval, which enhances the anomaly detection performance based on the DQF plots. As an extreme case, consider data living on a plane with an anomalous observation $x$ living off of it, and suppose that $y$ is such that $\ell_{x,y}$ is orthogonal to the plane. By using a robust measure of spread, $G_{x,y}$ will be degenerate (the pushforward distribution is simply two points, one with mass $\frac{1}{n}$) and thus $q_{x}(\delta)=0$ for all $\delta$. In less extreme situations, the parallels to Mahalonobis distance discussed above also hold for this choice of base distribution.

Of course non-normal choices are also possible, including distributions with heavier tails such as $t$-distributions, etc.

Non-adaptive $G_{x,y}$: For $G_{x,y}=G$, altering the base distribution from uniform simply amounts to a non-linear rescaling of the horizontal axis in the DQF plot, and accordingly only uniform base distributions were considered in Chandler and Polonik (2021). Considering the above motivation for adaptation, one can imagine the non-anomalous support $C$ being a sufficiently curved manifold such that midpoints of non-anomalous pairs of points also tend to live outside the support $C$ and anomalous observations do not have non-anomalous projections. In such cases, Windsorizing will not have the above stated benefit. Even without clear geometric adaptivity, the functions are still likely to reflect the difference in geometry between anomalous and non-anomalous points, though visually the discriminatory information may exist away from $\delta=0$ (see Figures 1 and 8), further motivating consideration of the entire function.

In the following we refer to a DQF approach with an adaptive choice of the distribution $G_{x,y}$ as the “adaptive DQF” (aDQF). We will make the actual choice of $G_{x,y}$ clear when presenting our numerical studies.

Similar to the distribution $G_{x,y}$, the choice of the opening angle of the cones influences the shape of the aDQFs, and a good choice will depend on the underlying geometry and also on the dimension. As for the dimension, for a spherical cone in ${\mathbb{R}}^{d}$ with a given height $h$ and radius of the base $r,$ it is straightforward to see that in order for the volume of this cone not to tend to zero as $d\to\infty$, one needs $r=O(\sqrt{d})$. This knowledge is of limited use, however, as, for instance, the data often lies on a lower dimensional manifold. For practical application everything will depend on the constant $c$ when choosing $r=c\sqrt{d}$, and again a good choice of $c$ will depend on the underlying geometry.

Now, while a certain robustness to the choice of $\alpha$ has been observed in our numerical studies, a more refined study of the aDQF plots indicates subtle, but (at least visually) important differences for different angles. Our recommendation here is to consider a few choices of $\alpha$ at once and to compare the resulting plots. Computationally, this does not pose a huge burden, because in order to determine whether a point $w$ falls inside a cone with tip $s$ and axis of symmetry $\ell_{x,y}$, all we need to determine is the angle between $\ell_{x,y}$ and $\overline{sw}$. Then one simply compares this angle to the opening angle. Accordingly, the standard output of the R package presents the aDQF at three different values of $\alpha$.

In low dimensional situations, using the observations themselves as anchor points may make sense. For instance, this would be beneficial in trying to detect the hole in a bivariate “rotated” version of (7). However, as the dimension of the data increases, issues related to the curse of dimensionality arise. A particularly salient one for the current method is that the fraction of points living on the boundary of the convex hull increases in dimension (Rényi and Sulanke, 1963). Points living on this boundary will tend to have very small half space depth. As half space depth underlies the construction of the depth quantile functions, in high dimensions the DQF for a large quantity of points will have nearly identical behavior, which empirically has been seen to be functions that only take on the values 0 and $1/n$. Thus, the ability to recognize anomalous observations is hampered. This provides rational for using $m_{ij}=\frac{x_{i}+x_{j}}{2}$ as our anchor points. Beyond having the aforementioned benefit of relating to antimodes for anomalous observations, these points are very likely to live in the interior of the convex hull and thus return informative (a)DQFs. Each observation is then associated with the averaged (a)DQF over midpoints formed between itself and other observations. Considering midpoints has the additional benefit of reducing the computational complexity of the algorithm, from $n(n-1)$ comparisons when the observations themselves are the “anchor points” to ${n\choose 2}$ when using midpoints. In the applications that follow, the averaged (a)DQFs are based on a random sample of 50 pairs rather than all pairs of points, further reducing the computational burden of the method.

A common feature of high dimensional data is the so-called manifold hypothesis (Fefferman, et al. 2016) that posits that the data often lives (at least approximately) on a manifold of much lower dimension than the $d$-dimensional ambient space. This fact is often exploited by dimension reduction algorithms, either linear (for instance, principal component analysis) or non-linear (for instance, Isomap by Tenenbaum, et al. 2000). Certainly an observation far in the tails of the point cloud might be considered anomalous, and this is the higher dimensional analog of what the box plot is designed to detect. Considering a definition of an outlier as an observation that is generated according to a different mechanism from the rest of the data set, such a point may lie off of the manifold, despite otherwise living “near” the point cloud (with respect to the ambient space).

A particular benefit of the DQF approach is adaptivity to sparsity. Suppose that the non-anomalous data lives in a $d^{\prime}$ dimensional affine subspace of the ambient space with dimension $d$, $d^{\prime}<d$. For any two non-anomalous points, the line $\ell_{ij}$ will also live in this subspace, and the intersection of our $d$-dimensional cones with this subspace will be cones of dimension $d^{\prime}$. In other words, the DQF approach will behave as if we had done appropriate dimension reduction beforehand.

In the following empirical studies, we use midpoints as anchor points, i.e. $m_{ij}=\frac{x_{i}+x_{j}}{2}.$ The aDQF uses a normal base distribution, centered at $m_{ij}$ with variance proportional to the $(\frac{n-6}{n})100\%$-Windsorized variance of the projected (onto $\ell_{ij}$) data. In the Euclidean case, the data is first $z$-scaled.

While the DQF approach results in a functional representation of each observation, a particularly informative region of these functions is for $\delta$ small, particularly the range of $\delta$ for which $\bar{q}(\delta)$ is 0. Considering the zero interval of the (a)DQFs means to look for “large distance gaps,” measured by $\delta_{x,y}$ (see Lemma 2.2). Of course, Lemma 2.1 also makes clear that $\delta$ small is related to the underlying density, resulting in somewhat of a unification of the two standard types of outliers, those far from the bulk of the data and those lying in low-density regions, even in the case of micro-clusters. To explore the sense in which the DQF approach to measuring distance gaps can facilitate anomaly detection, we contrast the DQF approach to stray (Talagala et al, 2021), an extension of the HDoutliers algorithm (Wilkinson, 2017), a well-studied and popular anomaly detection method based on the distribution of the $k$-nearest neighbors distances, specifically for anomalies defined by large distance gaps. We note that for an underlying manifold structure, an outlier lying off the manifold may have a small distance gap with respect to Euclidean distance in the ambient space, but a large distance gap with respect to a Mahalanobis-type distance with respect to the distribution on the manifold. We argue that the DQF approach, and particularly the aDQF, is sensitive to this type of anomaly and implicitly recognizes the large distance gap relative to a notion of distance based on the underlying geometry without the need for manifold learning.

Given that the (a)DQF only requires computing distances between observations, any object data for which a kernel function is defined can be visualized by using the corresponding Reproducing Kernel Hilbert Space (RKHS) geometry via the (a)DQF. Here we consider three such examples.

In each of the following examples, the data itself can be visualized, unlike the previous Euclidean data settings. However, the (a)DQF, guided by Lemma 2.2, provides a visualization that structures the data according to its outlyingness, facilitating identification that may be difficult when observing the raw data. We begin by consider Example 1 from Nagy and Hlubinka (2017). We generate 100 functions of the form $X(t)=A+B\arctan(x)+G(t)$, with $A\sim N(0,4)$, $B\sim{\rm Exp}(1)$ and $G(t)$ a zero-centered Gaussian process with covariance function $k(s,t)=0.2e^{\frac{-|s-t|}{0.3}}$, $0<s,t<1$. These constitute the non-anomalous observations, while a $101^{st}$ observation generated as $Y(t)=1-2\arctan(t)+G(t)$ forms the anomaly, off the manifold bounded by $B=0$. Figure 10 shows both the raw data and the aDQF based $L_{2}$-inner product.

The second example is the shape classification task studied in Reininghaus et al. (2015), where we analyze 21 surface meshes of bodies in different poses, in particular the first 21 observations of the SHREC 2014 synthetic data set. The first 20 correspond to one body, while the $21^{st}$ corresponds to a different body, which we regard as an outlier.

The approach to compare these surface meshes consists of various steps that we now briefly indicate. The first step is to construct the so-called Heat Kernel Signature (HKS) for each of the surface meshes. The HKS is a function of the eigenvalues and eigenvectors of the estimated Laplace-Beltrami operator (see Sun et al., 2009). One can think of the HKS as a piece-wise linear function on the surface mesh, whose values reflect certain geometric aspects of the surface. This piece-wise linear function is constructed by first defining function values $h_{t}(v_{i})$ on all the vertices $v_{i},i=1,\ldots,N$ (where $t$ is a tuning parameter), and then finding the function value at each face $f_{j}$ of the mesh as $h_{t}(f_{j})=\max_{v_{i}\in f_{j}}h_{t}(v_{i})$. The values $h_{t}(v_{i})$ have the form $h_{t}(v_{i})=\sum_{k=1}^{N}e^{-\lambda_{k}t}\phi_{ik},$ where $\phi_{i}=(\phi_{i1},\ldots,\phi_{iN})$ is the $i$-th eigenvector of a normalized graph Laplacian. For more details we refer to Belkin et al. (2008). Comparing these functions directly is not possible, because they live on different surfaces. Thus, certain features of these functions are extracted. This is accomplished by constructing a persistence diagram for each of the HKSs, using their (lower) level set filtration. We refer to Chazal and Michel (2021) or Wasserman (2018) for introductions to persistent homology, including persistence diagrams. In a nutshell, these persistence diagrams measure the number of topological features of the level sets of the HKSs along with their significance (persistence), which in turn is related to the heights of the critical points of the functions. In particular, it is not a single level set that is considered, but the entire filtration of level sets. Persistence diagrams are multisets of 2-dimensional points, and thus one is faced with comparing such 2-dimensional point sets. To this end, one can use the kernel trick to implicitly map the persistence diagram into a RKHS and use the corresponding RKHS geometry in our DQF approach. The kernel we are using is the persistence scale-space kernel (PSSK) $k_{\sigma}$ of Reininghaus et al. (2015). Based on this we construct the Gram matrix on which the aDQF is based, with the resulting aDQF plot shown in Figure 11, which provided stronger visual evidence than the non-adaptive DQF.

Our third example in this subsection is considering gerrymandering. We follow the techniques of Duchin, et al. (2021) to compute a persistence diagram based on a graph representation of districting maps filtered by Republican vote percentage in the 2012 Pennsylvania Senate election. Again one can think of these persistence diagrams being constructed by first constructing a function over each potential districting map. This is accomplished by associating each districting map with a graph (vertices are the districts; edges are placed between vertices if the districts physically share a part of their boundary). Then, a function is constructed over this graph, by defining a function value at each vertex (district), which is given by the portion of Republican votes (based on counts of precincts at a given election). Then, as in our previous example, one constructs a persistence diagram for this function by again using its level set filtration. This is done for both the 2011 map invalidated by the Supreme Court for partisan gerrymandering as well as random maps generated according to the ReCom algorithm (Deford, et al. 2021). The idea is that these randomly chosen districting maps constitute a representative sample of maps, and they are being used to answer the question of whether the gerrymandered map is an anomaly.

In our analysis, the aDQFs were again computed using the kernel trick via PSSK, resulting in a visualization of the extent at which the 2011 map is anomalous, see Figure 12.