Extremal event graphs: A (stable) tool for analyzing noisy time series data

Figure 1.  Schematic for Comparing Collections of Time Series Using Extremal Event DAGs. Each dataset consists of collections of time series. Extremal event DAGs are computed for both datasets. Each vertex corresponds to a local extremum of one of the time series in the dataset. Vertices highlighted in blue correspond to local extrema in the blue time series while vertices highlighted in green correspond to local extrema in the green time series. Vertices and directed edges capture the order of local extrema, and weights signify the robustness of extremal orderings. To compute a distance between extremal event DAGs, an extremal event supergraph is computed using a modified version of the edit distance. The extremal event supergraph has doubly weighted vertices and edges. The weight in the first component is associated to extremal event DAG 1 and the weight in the second component is associated to extremal event DAG 2. Datasets 1 and 2 differ by only a few perturbations and the resulting extremal event DAG distance is equal to 1.29

Figure 2.  The $ \varepsilon $-extremal intervals at $ t_3 $ and $ t_4 $. The $ \varepsilon $-extremal interval at $ t_3 $ is the connected component of $ (f+\varepsilon)^{-1}(f(t_3)-\varepsilon, \infty) $ that contains $ t_3 $ (Case 2). The $ \varepsilon $-extremal interval at $ t_4 $ is the connected component of $ (f-\varepsilon)^{-1}(-\infty, f(t_4)+\varepsilon) $ that contains $ t_4 $ (Case 1)

Figure 3.  Left. A function, $ f:[t_1, t_5]\rightarrow \mathbb{R} $. Right. Persistence diagram of $ f $, $ D(f) $ obtained from a sublevel set filtration of $ f $. The set $ D(f) $ is $ \{(f(t_1), \infty), (f(t_3), f(t_2)), (f(t_5), f(t_4))\} $. The first coordinate of each point in $ D(f) $ is the height of a local minimum, while the second coordinate is the height of a local maximum or $ \infty $

Figure 4.  Top. A continuous function $ f $ and its persistence diagram from a sublevel set filtration. In this example, $ {\rm{pers}}_f(t_1) = \max(f)-f(t_1) $, $ {\rm{pers}}_f(t_3) = f(t_2)-f(t_3) $, and $ {\rm{pers}}_f(t_5) = f(t_4)-f(t_5) $. Bottom. $ -f $ and its persistence diagram from a sublevel set filtration. Now we can compute the persistence of the local maxmima of $ f $ as $ {\rm{pers}}_f(t_4) = f(t_4)-\min(f) $ and $ {\rm{pers}}_f(t_2) = f(t_2)-f(t_3) $

Figure 5.  Extremal Event DAG for $ \sin(x):[0, 2\pi]\rightarrow \mathbb{R} $ and $ \cos(x):[0, 2\pi]\rightarrow \mathbb{R} $. The vertices on the left and highlighted in blue represent the local extrema of $ \sin(x) $ while the vertices on the right and highlighted in green represent the local extrema of $ \cos(x) $. The vertices highlighted in blue from top to bottom correspond to the local extrema of $ \sin(x) $ in ascending order by domain coordinate. For example, the top blue vertex with label and weight $ (\min, .5) $ corresponds to the local extremum $ (0, 0) $, the second blue vertex $ (\max, 1) $ corresponds to the local extremum $ (\frac{\pi}{2}, 1) $, etc. Similarly the green vertices correspond to the local extrema of $ \cos(x) $ in ascending order by domain coordinate. Directed edges indicate the ordering of the domain coordinates of the local extrema. The vertex weights are the node lives of the corresponding local extrema while the edge weights are computed using Theorem 3.3

Figure 6.  Time Series Data and Corresponding Extremal Event DAGs. We consider two datasets consisting of two functions, $ \frac{1}{2}\sin(x) $ and $ \frac{1}{2}\cos(x) $ over $ [0, 2\pi] $ with some added noise. In Figure 6a and Figure 6b, we label the blue curve as "sine" and green curve as "cosine". Figure 6c is the extremal event DAG for Dataset 1 while Figure 6d is extremal event DAG for Dataset 2

Figure 7.  Extracting Sine Backbones from Extremal Event DAG 1 and Extremal Event DAG 2. Figure 7a illustrates the backbone where each node corresponds to a local extremum of the sine labeled curve from Dataset 1 (see Figure 6a). Mathematically, this backbone is the sequence $ (\min, 0.25) $, $ (\max, 0.5) $, $ (\min, 0.5) $, $ (\max, 0.016) $, $ (\min, 0.016) $, $ (\max, 0.25) $. Figure 7b illustrates the backbone where each node corresponds to a local extremum of the sine labeled curve from Dataset 2 (see Figure 6b). Mathematically, this backbone is the sequence $ (\min, 0.25) $, $ (\max, 0.042) $, $ (\min, 0.042) $, $ (\max, 0.5) $, $ (\min, 0.5) $, $ (\max, 0.25) $

Figure 8.  Two Possible Alignments of Sine Backbones. We consider the backbones shown in Figure 7. Call these $ {\textbf{x}} $ and $ {\textbf{y}} $ respectively. The top row consists of nodes from $ {\textbf{x}} $ while the bottom row consists of nodes from $ {\textbf{y}} $. Figure 8a gives an alignment, $ \alpha_1: \{1, 2, \dots, 6\} \rightarrow \tilde{{\textbf{x}}} \times \tilde{{\textbf{x}}} $ of the two backbones where $ \alpha_1(i) = (x_i, y_i) $. Figure 8b gives an alignment $ \alpha_2: \{1, 2, \dots, 8\}\rightarrow \tilde{{\textbf{x}}} \times \tilde{{\textbf{y}}} $ where $ \alpha_2(1) = (x_1, y_1), $ $ \alpha_2(2) = ({\textbf{0}}, y_2), $ $ \alpha_2(3) = ({\textbf{0}}, y_3), $ $ \alpha_2(4) = (x_2, y_4), $ $ \alpha_2(5) = (x_3, y_5), $ $ \alpha_2(6) = (x_4, {\textbf{0}}), $ $ \alpha_2(7) = (x_5, {\textbf{0}}), $ and $ \alpha_2(8) = (x_6, y_6) $

Figure 9.  Extremal event supergraph of (extremal event) DAG 1 and DAG 2 from Figure 6. The nodes on the left represent the optimal alignment between the sine backbones in DAG 1 and DAG 2. The nodes on the right represent to the optimal alignment between the cosine backbones in DAG 1 and DAG 2. The node weights are listed on the node where the upper node weight comes from the weight function for DAG 1 and the lower node weight comes from the weight function for DAG 2. The blue node in the extremal event supergraph comes from aligning the blue node in DAG 2 with an insertion. The green node in the extremal event supergraph comes from aligning the green nodes in DAG 1 and DAG 2. For readability, we present only one edge weight pair, associated to the bold edge. The edge weight on the left is equal to zero since the blue node in DAG 2 is aligned with an insertion. The edge weight on the right is equal to 0.042 which is the edge weight between the blue and green node in DAG 2

Figure 10.  Moving Between Local Minima, Persistence Diagrams, and Backbone Nodes. The local minimum, $ (s, f(s)) $ in light blue corresponds to the point $ (f(s), f(r)) \in D(f) $ and $ ({\text{min}}, \frac{1}{2}{\rm{pers}}_f(s)) \in B(f) $

Figure 11.  Construction of Direct Alignment. In Figure 11a, $ f $ is the black function while $ f' $ is the pink function. The black labeled ticks denote the domain coordinates of the local extrema of $ f $ and the pink labeled ticks denote the domain coordinates of the local extrema of $ f' $. The $ \varepsilon $-extremal intervals for the local extrema of $ f $ are illustrated. Since any two points in $ D(f) $ where one is not a diagonal point, have a distance of at least $ \varepsilon $, and $ f'\in N_{\varepsilon}(f) $, we have $ f' $ is very close to $ f $. Applying the Direct Alignment Lemma, we get pairings of points in $ D(f) $ and $ D(f') $ as shown in Figure 11b. From the pairings in $ D(f) $ and $ D(f') $, we get pairings of nodes with the label "min" that preserve order. The preservation of order comes from how the $ \varepsilon $-extremal intervals for minima of $ f $ are disjoint. We apply an analogous process to pair nodes with the label "max". The alignment that is constructed in the Direct Alignment Lemma for $ f $ and $ f' $ is shown in Figure 11c

Figure 12.  Nested $ \varepsilon $-extremal intervals. We see that $ \varphi_{\varepsilon}^{f_i}(t) \subset \varphi_{\varepsilon+\varepsilon_{i, j}}^{f'_i}(t') $

Figure 13.  Extremal Event DAG Distances in Experiment 3. The red bar is $ d_{ED}({\rm{DAG}}(\mathcal{D}_1), {\rm{DAG}}(\mathcal{D}_2)) $, the distance between the two yeast datasets without any scrambling of genes

Figure 14.  Histograms from Plasmodium falciparum experiments. The reference strain was 3D7 for all experiments. The distribution of baseline extremal event DAG distances is shown in blue for each graph and the distribution of extremal event DAG distances is shown in purple. In all three plots, the extremal event DAG distances are smaller than the corresponding baseline distances. Performing a paired t-test to the blue and purple distributions with a null hypothesis that the distributions are the same in all three plots resulted in a $ p $-value below machine precision

Figure 15.  Histograms from mouse experiments. The reference cell line was liver for all experiments. The distribution of baseline extremal event DAG distances is shown in blue for each graph and the distribution of extremal event DAG distances is shown in purple. In all three plots, we see the extremal event DAG distances are smaller than the corresponding baseline distances. Performing a paired t-test to the blue and purple distributions with a null hypothesis that the distributions are the same in all three plots resulted in a $ p $-value below machine precision

Figure 16.  Geometric Arguments for Lemma A.10. In Figure 16a, $ \frac{1}{2}{{\rm{pers}}}_{f'}(t')>\frac{1}{2}((f(t)+7\varepsilon) -(f(t)+\varepsilon)) = 3\varepsilon>\varepsilon. $ In Figure 16b, $ \frac{1}{2}|{{\rm{pers}}}_{f'}(t')-{{\rm{pers}}}_{f}(s)|>\frac{1}{2}|(\zeta_f(s)-f(s))-(\zeta_f(s)-(f(s)-2\varepsilon))| = \varepsilon $

Figure 17.  Backtracking in alignment matrix of sine backbones. Consider the backbones $ {\textbf{x}} $ and $ {\textbf{y}} $ from Figure 7. The path $ p:\{1, 2, \ldots, 7\} \rightarrow \tilde{{\textbf{x}}}\times\tilde{{\textbf{y}}} $, constructed from backtracking is illustrated through the black arrows and purple highlighted entries. In particular, $ p(1) = {\textbf{mat}}[7, 7] = 0.115 $ and $ p(9) = {\textbf{mat}}[1, 1] = 0 $