A Quantum-inspired Entropic Kernel for Multiple Financial Time Series Analysis

1 Introduction

Network representations are powerful tools to analyze the financial market that can be considered as a time-varying complex system consisting of multiple co-evolving financial time series [Zhang and Small, 2006; Nicolis et al., 2005; Shimada et al., 2008; Silva et al., 2015], e.g., the stock market with the trade price. This is based on the idea that the structure of the so-called time-varying financial networks [Bullmore and Sporns, 2009] inferred from the corresponding time series of the system can represent richer physical interactions between system entities than the original individual time series. One main objective of existing approaches is to detect the extreme financial events that can significantly influence the network structures [Bai et al., 2020].

In machine learning, graph kernels have been widely employed for analyzing structured data represented by graphs or networks [Xu et al., 2018]. The main advantage of employing graph kernels is that they can offer us an effective way of mapping the network structures into a high dimensional space so that the standard kernel machinery for vectorial data is applicable to the network analysis. Most existing graph kernels are based on the idea of decomposing graphs or networks into substructures and then measuring pairs of isomorphic substructures [Haussler, 1999], e.g., graph kernels based on counting pairs of isomorphic a) paths [Borgwardt and Kriegel, 2005], b) walks [Kashima et al., 2003], and c) subgraphs [Bai et al., 2015b] or subtrees [Shervashidze et al., 2009]. Unfortunately, directly adopting these graph kernels to analyze the time-varying financial networks inferred from original vectorial time series tends to be elusive. This is because these financial network structures are by nature complete weighted graphs [Ye et al., 2015; Bai et al., 2020], where each vertex represents an individual time series of a stock and is adjacent to all remainder vertices, and each edge represents the interaction (e.g., the correlation or distance) between a pair of coevolving financial time series. It is difficult to decompose a complete weighted graph into the required substructures, and thus influences the effectiveness of most existing graph kernels for financial network analysis.

∗Corresponding Author

One way to address the aforementioned problem is to construct sparse structures of the original time-varying financial networks. With this scenario, Cui et al. [Cui et al., 2018] have used the well-known threshold-based approach to preserve the weighted edges falling into the larger 10% of the weights, and employed the classical graph kernels associated with the resulting sparse structures for financial network analysis. Bai et al. [Bai et al., 2020] have abstracted the minimum or maximum spanning trees associated with the commute time matrix of the original complete weighted financial networks, and developed a novel quantum graph kernel over the spanning trees of the financial networks. Although, both

kernels for time-varying financial network analysis, their required sparse structures also lead to significant information loss. Since many weighted edges of the original complete weighted financial networks are discarded. In summary, analyzing time-varying financial networks associated with graph kernels still remains challenges.

The aim of this paper is to overcome the aforementioned problems by developing a new kernel measure between timevarying networks for multiple co-evolving financial time series analysis. Overall, the main contributions are threefold.

First, for a family of time-varying financial networks, we commence by computing the average mixing matrix [Godsil, 2013] to summarize the time-averaged behaviour of continuous-time quantum walks (CTQW) evolved on the network structures. The reason of using the CTQW is that it not only accommodates complete weighted graphs, but also better reflects richer financial network characteristics than the classical random walks [Bai et al., 2015a] (see details in Section II-A). We show how the average mixing matrix of the CTQW allows to compute a quantum-based entropy for each vertex of the financial networks and represents the original networks as quantum entropy time series.

Second, with each pair of time-varying financial networks to hand, we define a Quantum-inspired Entropic Kernel between their quantum entropy time series through the classical dynamic time warping framework. The proposed kernel not only accommodates the complete weighted graphs through the entropy time series, but also bridges the gap between graph kernels and the classical dynamic time warping framework for time series analysis (see details in Section III-B).

Third, we perform the proposed kernel on time-varying financial networks abstracted from multiple co-evolving financial time series of New York Stock Exchange (NYSE) database. Experiments demonstrate that the proposed approach can effectively discriminate the abrupt structural changes in terms of the extreme financial events.

2 Preliminary Concepts

In this section, we briefly review some preliminary concepts.

2.1 The Average MixingMatrix of the CTQW

The continuous-time quantum walk (CTQW) is the quantum analogue of the classical continuous-time random walk (CTRW) [Farhi and Gutmann, 1998]. The CTQW models a Markovian diffusion process over the vertices of a graph through their transition information. Assume a sample graph is G(V,E), where V is the vertex set and E is the edge set. Similar to the classical CTRW, the state space of the CTQW is the vertex set V and its state at time t is a complex linear combination of the basis states |u⟩, i.e., |ψ(t)⟩ = ∑u∈V αu(t) |u⟩, where αu(t) ∈ C and |ψ(t)⟩ ∈ C|V | are the amplitude and both complex. Furthermore, αu(t)α∗u (t) indicates the probability of the CTQW visiting vertex u at time t. ∑u∈V αu(t)α∗u (t) = 1 and αu(t)α∗u (t) ∈ [0, 1], for all u ∈ V , t ∈ R+. Unlike the classical CTRW, the CTQW evolves based on the Schr¨odinger equation

where H denotes the system Hamiltonian. In this work, we employ the adjacency matrix as the Hamiltonian. When a CTQW evolves on the sample graph G(V, E), the behaviour of the walk at time t can be summarized using the mixing matrix [Godsil, 2013]

where ◦ denotes the Schur-Hadamard product of two matrices, i.e., [A ◦ B]uv = AuvBuv. Since U is unitary, M(t) is a doubly stochastic matrix and each entry M(t)uv indicates the probability of the CTQW visiting vertex v at time t when the walk initially starts from vertex u. However, QM(t) cannot converge, because U(t) is also normpreserving. To overcome this problem, we can enforce convergence by taking a time average. Specifically, we take the Ces`aro mean and define the average mixing matrix as Q = limT→∞ ∫ T 0 QM(t)dt, where each entry Quv of the average mixing matrix Q represents the average probability for a CTQW to visit vertex v starting from vertex u, and Q is still a doubly stochastic matrix. Godsil [Godsil, 2013] has indicated that the entries of Q are rational numbers. We can easily compute Q from the spectrum of the Hamiltonian H that can be the adjacency matrix A of G. Let λ1, . . . , λ|V | represent the |V | distinct eigenvalues of H and Pj be the matrix representation of the orthogonal projection on the eigenspace associated with the λj , i.e., H = ∑|V | j=1 λjPj . Then, we rewrite the average mixing matrix Q as

Remarks. The CTQW has been successfully employed to develop novel approaches in machine learning and data mining [Bai et al., 2014; Bai et al., 2016], because of the richer structure than their classical counterparts. The reason of utilizing the CTQW in this work is that the state vector of the CTQW is complex-valued and its evolution is governed by a time-varying unitary matrix. By contrast, the state vector of the classical CTRW is real-valued and its evolution is governed by a doubly stochastic matrix. As a result, the behaviour of the CTQW is significantly different from their classical counterpart and possesses a number of important properties. For instance, the CTQW allows interference to take place, and thus reduces the tottering problem arising in the classical CTRW. Furthermore, since the evolution of the CTQW is not dominated by the low frequency components of the Laplacian spectrum, it has better ability to distinguish different graph structures. Finally, the CTQW can accommodate the complete weighted graph, since the Hamiltonian of the CTQW can be the complete weighted adjacency matrix.

2.2 The Dynamic TimeWarping Framework

We review the global alignment kernel based on the dynamic time warping framework proposed in [Cuturi, 2011]. Let T be a set of discrete time series that take values in a space X. For a pair of discrete time series P = (p1, . . . , pm) ∈ T and Q = (q1, . . . , qn) ∈ T with lengths m and n respectively, the alignment π between P and Q is defined as a pair of increasing integral vectors (πp, πq) of length l ≤ m+ n - 1, where 1 = πp(1) ≤ · · · ≤ πp(l) = m and 1 = πq(1) ≤ · · · ≤ πq(l) = n such that (πp, πq) is assumed to have unitary increments and no simultaneous repetitions. Note that, for P and Q, each of their elements can be an observation vector with fixed dimensions at a time step. For any index 1 ≤ i ≤ l - 1, the increment vector of π = (πp, πq) satisfies

Within the framework of the classical dynamic time warping [Cuturi, 2011], the coordinates πp and πq of the alignment π define the warping function. Assume A(m, n) corresponds to a set of all possible alignments between P and Q, Cuturi [Cuturi, 2011] has proposed a dynamic time warping inspired kernel, namely the Global Alignment Kernel, by considering all the possible alignments in A(m, n). The kernel is defined as

where DP,Q(π) is the alignment cost given by

and is defined through a local divergence φ that quantifies the discrepancy between each pair of elements pi ∈ P and qi ∈ Q. In general, φ is defined as the squared Euclidean distance. Note that, the kernel kGA measures the quality of both the optimal alignment and all other alignments π ∈ A(m, n), thus it is positive definite. Moreover, kGA provides richer statistical measures of similarity by encapsulating the overall spectrum of the alignment costs {DP,Q(π), π ∈ A(m, n)}.

Remarks. The dynamic time warping based Global Alignment Kernel kGA is a powerful tool for analyzing vectorial time series [Mikalsen et al., 2018; Jain, 2019]. To extend kGA into graph kernel domains, Bai et al. [Bai et al., 2018] have developed a nested graph kernel by measuring kGA between the depth-based complexity traces of graphs [Bai and Hancock, 2014]. Specifically, the complexity trace of each graph is computed by measuring the entropies on a family of K-layer expansion subgraphs rooted at its centroid vertex. Although, the nested graph kernel outperforms local substructure based graph kernels [Johansson et al., 2014] on graph classification tasks. Unfortunately, the financial networks are by nature complete weighted graphs and it is difficult to decompose such graphs into required expansion subgraphs rooted at the centroid vertex. Thus, directly preforming the dynamic time warping inspired graph kernel for timevarying financial networks still remains challenges.

3 Kernels for Time-varying Networks

In this section, we propose a Quantum-inspired Entropic Kernel between time-varying networks for multiple co-evolving financial time series analysis. We commence by characterizing each financial network as a discrete quantum entropy time series through the CTQW. Moreover, we define the new kernel associated with the entropy time series, in terms of the classical dynamic time warping framework [Cuturi, 2011].

3.1 The QuantumEntropy Time Series

We introduce how to characterize each financial network structure as the quantum entropy time series through the CTQW. Assume G = {G1, . . . , Gp, . . . , Gq, . . . , GT} denotes a family of time-varying financial networks extracted from a complex financial system S with a specific set of N coevolving financial time series, i.e., the system has a fixed number of components (e.g., stocks) co-evolving with time. Gp(Vp, Ep, Ap) is the sample network extracted from the system at time step p. For Gp, each individual vertex v ∈ Vp represents a corresponding time series of a different stock (e.g., the stock price), each edge e ∈ Ep represents the interaction (e.g., distances or correlations) between a pair of time series, and Ap is the interaction based weighted adjacency matrix. This is a popular way of modelling the multiple co-evolving financial time series as network structures [Silva et al., 2015; Bai et al., 2020]. Note that, since the vertices of each financial network Gp ∈ G correspond to the same N components of the system S, all the networks in G have the same vertex set, whereas the edge sets Et are quite different with time t.

Specifically, for each financial network Gp(Vp,Ep,Ap) from G at time p, we first compute the average matrix matrix Qp associated with the CTQW evolved on Gp. For each i-th vertex vi ∈ Vp, the i-th row of Qp gives the time-averaged probability distribution Pi for the CTQW to visit vertices v1, . . . , vN ∈ V (|Vp| = N) starting from vi, i.e.,

where Pi(vj) = Qpi,j is the time-averaged probability of the CTQW visiting vj from vi. The quantum based Shannon entropy [Bai et al., 2016] of vertex vi can be defined as

As a result, the entropy characteristic vector of Gp associated with the entropies over all its vertices can be defined as

where HS(vi) is the quantum Shannon entropy of the i-th vertex vi of Gp associated with the time-averaged probability distribution residing on the i-th row of Qp.

We move a time interval of w time steps over all the timevarying networks of the financial system S to construct a time-varying quantum entropy time series for each network Gp at time p. In this work, we set the value of w as 28. Specifically, for each network Gp, we compute its quantum entropy time series St associated with its time window as

where each column Es of Sp is the entropy characteristic vector of each network Gs ∈ G at time s and is defined by Eq.(9). s ∈ {p-w+1, p-w+2, . . . , p}. Obviously, the quantum entropy time series Sp of Gp encapsulates a family of w time-varying entropy characteristic vectors from Gp-w+1 at time p-w+1 to Gp at time t.

3.2 The Quantum-inspired Entropic Kernel

We develop a new kernel for analyzing time-varying financial networks based on the classical dynamic time warping framework. For a pair of time-varying networks Gp ∈ G and Gq ∈ G at time p and q respectively, we commence by computing their associated quantum entropy time series as

and

based on the definition in Section 3.1. The proposed Quantum Inspired Entropic Kernel kQEK between Gp and Gq is

where kGA is the dynamic time warping inspired Global Alignment Kernel (GAK) defined in Eq.(5), π is the warping alignment between the entropy time series of Gp and Gq, A(w, w) is all possible alignments and Dp,q(π) refers to the alignment cost obtained via Eq.(6). Note that, the proposed kernel kQEK is positive definite. This is because kQEK is based on the positive definite kernel kGA.

Remarks. Although the proposed kernel kQEK is related to the general principles of the GAK kernel. The proposed kernel kQEK still possesses two theoretical differences with the GAK kernel. First, the original GAK kernel is only developed for vectorial time series and thus cannot capture structural relationships between time series. By contrast, the proposed kernel kQEK is explicitly proposed for time-varying financial networks that encapsulate physical interactions between pairs of time series. Second, unlike the GAK kernel, the proposed kernel kQEK is defined based on the quantum entropy time series that is developed through the average mixing matrix of the CTQW. As we have stated in Section 2.1, the CTQW can accommodate the complete weighted graph and better distinguish different network structures in terms of the low frequency components of its Laplacian spectrum. Thus, the proposed kernel kQEK can not only reflect the physical interactions between the original vectorial financial time series, but also capture richer structure information than the GAK kernel associated with the original time series. On the other hand, as we have stated, the state-of-the-art graph kernels mentioned in Section 1 and Section 2.2 cannot directly accommodate complete weighted graphs. Thus, it is difficult to directly perform these graph kernels on the complete weighted financial networks, unless one transforms these networks into sparse versions. By contrast, the proposed kernel kQEK can encapsulate the whole structural information residing on all weighted edges. In summary, the proposed kernel kQEK bridges the gap between state-of-the-art graph kernels and the classical dynamic time warping framework for time-varying networks, providing an effective way to analyze multiple coevolving financial time series.

Time Complexity. For a pair of networks each having n vertices, computing the kernel kQEK associated with a time interval of w steps requires time complexity O(n3 +w2 ). Because, computing the entropy time series relies on the spectral decomposition of CTQWs, thus has time complexity O(n3 ). Computing all possible alignments between the entropy time First Eigenvalue series over w time steps has time complexity O(w2 ). Thus, kQEK has a polynomial time complexity O(n3 + w2 ).

4 Experiments of Time Series Analysis

We establish a NYSE dataset that consists of a series of timevarying financial networks based on the New York Stock Exchange (NYSE) database [Silva et al., 2015; Ye et al., 2015]. The NYSE database encapsulates 347 stocks and their associated daily prices over 6004 trading days from January 1986 to February 2011, i.e., the market system has 347 co-evolving time series in terms of the daily stock prices. The prices are all corrected from the Yahoo financial dataset (http://finance.yahoo.com). To extract the network representations, we use a time window of 28 days and move this window along time to obtain a sequence (from day 29 to day 6004) in which each temporal window contains a time series of the daily return stock prices over a period of 28 days. To represent trades between different stocks as a network, for each window we compute the Euclidean distance between the time series of each pair of stocks as their connection (edge) weight, following the same setting in [Bai et al., 2020]. It has been empirically shown that the financial networks associated with the Euclidean distance are more effective than those associated with the Pearson correlation. Clearly, this operation yields a time-varying financial network with a fixed number of 347 vertices and varying edge weights for each of the 5976

trading days. Each network is a complete weighted graph.

4.1 Kernel Embeddings from kPCA

We evaluate the performance of the proposed Quantuminspired Entropic Kernel (QEK) on time-varying networks of the NYSE dataset. Specifically, we analyze whether the proposed QEK kernel can distinguish the structural changes of the network evolution with time. Furthermore, we also compare the proposed QEK kernel with three state-of-theart kernel methods, that is, the dynamic time warping inspired Global Alignment Kernel (GAK) for original vectorial time series [Cuturi, 2011] and two graph kernels for timevarying financial networks. The graph kernels for comparisons include the Weisfeiler-Lehman Subtree Kernel (WLSK) [Shervashidze et al., 2009], and the Discrete-time Quantum Walk Kernel (DTQK) [Bai et al., 2020]. For the GAK kernel, we also utilize a time window of 28 days for each trading day. For the WLSK kernel, since it can only accommodate undirected and unweighted graphs, we transform each original network into a minimum spanning tree and ignore the weights on the preserved edges, following the same setting in the work [Bai et al., 2020]. Since the DTQK kernel can accommodate edge weights, we straightforwardly perform this kernel on the original financial networks. We perform kernel Principle Component Analysis (kPCA) [Witten et al., 2011] on the kernel matrices associated with different kernels, and

(a) Enron Incident for QEK

(b) Enron Incident for GAK

embed the financial networks or the original time series into a vectorial pattern space. We visualize the embedding results using the first three principal components in Fig.1(a), Fig.1(b), Fig.1(c), and Fig.1(d) respectively.

Fig.1 exhibits the paths of the time-varying financial networks (or the original vectorial time series) in different kernel spaces, and the color bar of each subfigure indicates the date in the time series. We observe that the embeddings from the proposed QEK kernel exhibit a better manifold structure. Moreover, only the proposed QEK kernel generates a clear time-varying trajectory and the neighboring networks with time are close together in the embedding principal space. By contrast, the alternative methods hardly result in a trajectory and their embeddings tend to distribute as clusters. To further demonstrate the effectiveness of the QEK kernel, we compare the distance stress (DS) of the network embeddings from different kernels. Specifically, the DS is defined as

where t = 2, 3, . . . , n, xt is the network embedding vector at time t, and xtn is the nearest network embedding vector of xt in the pattern space. For each embedding vector xt at time t, if the nearest embedding vector is always the embedding vector at last time step (i.e., xt-1), the value of DS will be 1. In other words, the DS value nearer to 1 indicates the better performance of the embeddings to form a clear time-varying trajectory. The DS value of each kernel is shown in Table 1. Clearly, only the DS value of the proposed QEK kernel is nearer to 1, indicating the better performance of preserving the ordinal arrangement of the time-varying networks.

To take our study one step further, we explore the embeddings during different periods of three well-known financial events, i.e., the Black Monday period (from 15th Jun 1987 to 17th Feb 1988), the Dot-com Bubble period (from 3rd Jan 1995 to 31st Dec 2001), and the Enron Incident period (from 16th Oct 2001 to 11th Mar 2002). For differen kernels, Fig.2 corresponds to the Dot-com Bubble period and Fig.3 to the Enron Incident period. Due to the limit space, we do not exhibit the embeddings for Black Monday. However, we will observe the similar phenomenon with Fig.2 and Fig.3. These figures indicate that the Black Monday (17th Oct, 1987), the Dot-com Bubble Burst (13rd Mar, 2000) and the Enron Incident period are all crucial financial events, significantly influencing the structural time-varying evolution of the financial networks or the original vectorial financial time series. Excluding the GAK kernel, the embedding points of the remaining kernels before and after these events are well separated into distinct clusters, and the points corresponding to the crucial events are midway between the clusters.

To place our analysis of the kernel embedding clusters on a more quantitative footing, for each kernel we select the kernel embedding points of 100 trading days around each financial crisis, i.e., we select embedding points of 50 trading days before and after each crisis date respectively. We apply the K-means method to the kernel embeddings of 100 trading days for each kernel to explore whether the clusters can be correctly separated in terms of the trading days before and after each financial crisis. We calculate the Rand Index for the resulting clusters and the Rand indicating each kernel is listed in Table 2. The results indicate that the embedding points associated with the proposed QEK kernel can produce the best clusters, i.e., the embedding points before and after the financial crisis are separated better than other kernels.

4.2 Evaluations of the Kernel Matrix

Based on the earlier evaluation, we find that the DTQK kernel is the most competitive kernel with the proposed QEK kernel. To further reveal the effectiveness of the proposed QEK kernel, we visualize the kernel matrices of both the kernels.

Due to the limited space, we only compute the kernel matrices between the networks belonging to the Dot-com Bubble period, and the period encapsulate 100 trading days. In fact, we will observe similar phenomenons if we compute the kernel matrices for other financial event periods. Specifically, the kernel matrices are visualized in Fig.4, where both the x-axis and y-axis represent the time steps. Note that, to compare the two kernels in the same scaled Hilbert space, we consider the normalized version of both the kernels as

where kn is the normalized kernel, and k is either the EDTWK or the WLSK kernel. As a result, the kernel values are all bounded between 0 to 1, and the colour bar beside each subfigure indicates the kernel value of the kernel matrix. Fig.4 indicates that the kernel values tend to decrease when the elements of the kernel matrix are far away from the matrix trace. This is because such elements are computed between time-varying networks having long time spans and there are more structure changes when the network evolves with a long time variation. Thus, both the QEK and DTQK kernels reflect structural evolutions of financial networks with time. However, on the other hand, the kernel value of the DTQK kernel tends to drop down more quickly when the element is a little far from the trace. By contrast, the kernel value of the QEK kernel tend to decrease more slowly when the element gets farer away from the trace. This observation explains why only the proposed QEK kernel can form a clear trajectory with time variation and generate better clusters before and after financial crisis, i.e., the proposed QEK kernel can better distinguish and understand the structural changes of the network structures evolving with a long time period.

5 Conclusion

In this paper, we have developed a new Quantum-inspired Entropic Kernel for time-varying complex networks. The proposed kernel bridges the gap between graph kernels and the classical dynamic time warping framework for time series analysis. Experimental analysis of NYSE financial time series demonstrates the effectiveness of the new kernel.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant no. 61976235 and 61602535), the Program for Innovation Research in Central University of Finance and Economics, the Youth Talent Development Support Program by Central University of Finance and Economics (No. QYP1908) and the Foundation of State Key Laboratory of Cognitive Intelligence (Grant No. COGOSC20190002), iFLYTEK, China. Corresponding Author: Lixin Cui (cuilixin@cufe.edu.cn). The fourth author Yuhang Jiao mainly participated partial discussions for this work.