Entropic Dynamic Time Warping Kernels for Co-Evolving Financial Time Series Analysis.

Network representations are powerful tools to modeling the dynamic time-varying financial complex systems consisting of multiple co-evolving financial time series, e.g., stock prices. In this work, we develop a novel framework to compute the kernel-based similarity measure between dynamic time-varying financial networks. Specifically, we explore whether the proposed kernel can be employed to understand the structural evolution of the financial networks with time associated with standard kernel machines. For a set of time-varying financial networks with each vertex representing the individual time series of a different stock and each edge between a pair of time series representing the absolute value of their Pearson correlation, our start point is to compute the commute time (CT) matrix associated with the weighted adjacency matrix of the network structures, where each element of the matrix can be seen as the enhanced correlation value between pairwise stocks. For each network, we show how the CT matrix allows us to identify a reliable set of dominant correlated time series as well as an associated dominant probability distribution of the stock belonging to this set. Furthermore, we represent each original network as a discrete dominant Shannon entropy time series computed from the dominant probability distribution. With the dominant entropy time series for each pair of financial networks to hand, we develop an entropic dynamic time warping kernels through the classical dynamic time warping framework, for analyzing the financial time-varying networks. We show that the proposed kernel bridges the gap between graph kernels and the classical dynamic time warping framework for multiple financial time series analysis. Experiments on time-varying networks extracted through New York Stock Exchange (NYSE) database demonstrate that the effectiveness of the proposed method.

Graph Motif Entropy for Understanding Time-Evolving Networks.

The structure of networks can be efficiently represented using motifs, which are those subgraphs that recur most frequently. One route to understanding the motif structure of a network is to study the distribution of subgraphs using statistical mechanics. In this article, we address the use of motifs as network primitives using the cluster expansion from statistical physics. By mapping the network motifs to clusters in the gas model, we derive the partition function for a network, and this allows us to calculate global thermodynamic quantities, such as energy and entropy. We present analytical expressions for the number of certain types of motifs, and compute their associated entropy. We conduct numerical experiments for synthetic and real-world data sets and evaluate the qualitative and quantitative characterizations of the motif entropy derived from the partition function. We find that the motif entropy for real-world networks, such as financial stock market networks, is sensitive to the variance in network structure. This is in line with recent evidence that network motifs can be regarded as basic elements with well-defined information-processing functions.

Regionwise Generative Adversarial Image Inpainting for Large Missing Areas.

Recently, deep neural networks have achieved promising performance for in-filling large missing regions in image inpainting tasks. They have usually adopted the standard convolutional architecture over the corrupted image, leading to meaningless contents, such as color discrepancy, blur, and other artifacts. Moreover, most inpainting approaches cannot handle well the case of a large contiguous missing area. To address these problems, we propose a generic inpainting framework capable of handling incomplete images with both contiguous and discontiguous large missing areas. We pose this in an adversarial manner, deploying regionwise operations in both the generator and discriminator to separately handle the different types of regions, namely, existing regions and missing ones. Moreover, a correlation loss is introduced to capture the nonlocal correlations between different patches, and thus, guide the generator to obtain more information during inference. With the help of regionwise generative adversarial mechanism, our framework can restore semantically reasonable and visually realistic images for both discontiguous and contiguous large missing areas. Extensive experiments on three widely used datasets for image inpainting task have been conducted, and both qualitative and quantitative experimental results demonstrate that the proposed model significantly outperforms the state-of-the-art approaches, on the large contiguous and discontiguous missing areas.

Two-Level Graph Neural Network.

Graph neural networks (GNNs) are recently proposed neural network structures for the processing of graph-structured data. Due to their employed neighbor aggregation strategy, existing GNNs focus on capturing node-level information and neglect high-level information. Existing GNNs, therefore, suffer from representational limitations caused by the local permutation invariance (LPI) problem. To overcome these limitations and enrich the features captured by GNNs, we propose a novel GNN framework, referred to as the two-level GNN (TL-GNN). This merges subgraph-level information with node-level information. Moreover, we provide a mathematical analysis of the LPI problem, which demonstrates that subgraph-level information is beneficial to overcoming the problems associated with LPI. A subgraph counting method based on the dynamic programming algorithm is also proposed, and this has the time complexity of O(n³), where n is the number of nodes of a graph. Experiments show that TL-GNN outperforms existing GNNs and achieves state-of-the-art performance.

Learning Backtrackless Aligned-Spatial Graph Convolutional Networks for Graph Classification.

In this paper, we develop a novel backtrackless aligned-spatial graph convolutional network (BASGCN) model to learn effective features for graph classification. Our idea is to transform arbitrary-sized graphs into fixed-sized backtrackless aligned grid structures and define a new spatial graph convolution operation associated with the grid structures. We show that the proposed BASGCN model not only reduces the problems of information loss and imprecise information representation arising in existing spatially-based graph convolutional network (GCN) models, but also bridges the theoretical gap between traditional convolutional neural network (CNN) models and spatially-based GCN models. Furthermore, the proposed BASGCN model can both adaptively discriminate the importance between specified vertices during the convolution process and reduce the notorious tottering problem of existing spatially-based GCNs related to the Weisfeiler-Lehman algorithm, explaining the effectiveness of the proposed model. Experiments on standard graph datasets demonstrate the effectiveness of the proposed model.

Uncalibrated, Two Source Photo-Polarimetric Stereo.

In this paper we present methods for estimating shape from polarisation and shading information, i.e. photo-polarimetric shape estimation, under varying, but unknown, illumination, i.e. in an uncalibrated scenario. We propose several alternative photo-polarimetric constraints that depend upon the partial derivatives of the surface and show how to express them in a unified system of partial differential equations of which previous work is a special case. By careful combination and manipulation of the constraints, we show how to eliminate non-linearities such that a discrete version of the problem can be solved using linear least squares. We derive a minimal, combinatorial approach for two source illumination estimation which we use with RANSAC for robust light direction and intensity estimation. We also introduce a new method for estimating a polarisation image from multichannel data and provide methods for estimating albedo and refractive index. We evaluate lighting, shape, albedo and refractive index estimation methods on both synthetic and real-world data showing improvements over existing state-of-the-art.

Learning Aligned Vertex Convolutional Networks for Graph Classification.

Graph convolutional networks (GCNs) are powerful tools for graph structure data analysis. One main drawback arising in most existing GCN models is that of the oversmoothing problem, i.e., the vertex features abstracted from the existing graph convolution operation have previously tended to be indistinguishable if the GCN model has many convolutional layers (e.g., more than two layers). To address this problem, in this article, we propose a family of aligned vertex convolutional network (AVCN) models that focus on learning multiscale features from local-level vertices for graph classification. This is done by adopting a transitive vertex alignment algorithm to transform arbitrary-sized graphs into fixed-size grid structures. Furthermore, we define a new aligned vertex convolution operation that can effectively learn multiscale vertex characteristics by gradually aggregating local-level neighboring aligned vertices residing on the original grid structures into a new packed aligned vertex. With the new vertex convolution operation to hand, we propose two architectures for the AVCN models to extract different hierarchical multiscale vertex feature representations for graph classification. We show that the proposed models can avoid iteratively propagating redundant information between specific neighboring vertices, restricting the notorious oversmoothing problem arising in most spatial-based GCN models. Experimental evaluations on benchmark datasets demonstrate the effectiveness.

Erratum: Wang, J., et al. Microcanonical and Canonical Ensembles for fMRI Brain Networks in Alzheimer's Disease. Entropy 2021, 23, 216.

We sincerely apologize for the inconvenience of updating the authorship [...].

Early Detection of Alzheimer's Disease: Detecting Asymmetries with a Return Random Walk Link Predictor.

Alzheimer's disease has been extensively studied using undirected graphs to represent the correlations of BOLD signals in different anatomical regions through functional magnetic resonance imaging (fMRI). However, there has been relatively little analysis of this kind of data using directed graphs, which potentially offer the potential to capture asymmetries in the interactions between different anatomical brain regions. The detection of these asymmetries is relevant to detect the disease in an early stage. For this reason, in this paper, we analyze data extracted from fMRI images using the net4Lap algorithm to infer a directed graph from the available BOLD signals, and then seek to determine asymmetries between the left and right hemispheres of the brain using a directed version of the Return Random Walk (RRW). Experimental evaluation of this method reveals that it leads to the identification of anatomical brain regions known to be implicated in the early development of Alzheimer's disease in clinical studies.

A Quantum-Inspired Similarity Measure for the Analysis of Complete Weighted Graphs.

We develop a novel method for measuring the similarity between complete weighted graphs, which are probed by means of the discrete-time quantum walks. Directly probing complete graphs using discrete-time quantum walks is intractable due to the cost of simulating the quantum walk. We overcome this problem by extracting a commute time minimum spanning tree from the complete weighted graph. The spanning tree is probed by a discrete-time quantum walk which is initialized using a weighted version of the Perron-Frobenius operator. This naturally encapsulates the edge weight information for the spanning tree extracted from the original graph. For each pair of complete weighted graphs to be compared, we simulate a discrete-time quantum walk on each of the corresponding commute time minimum spanning trees and, then, compute the associated density matrices for the quantum walks. The probability of the walk visiting each edge of the spanning tree is given by the diagonal elements of the density matrices. The similarity between each pair of graphs is then computed using either: 1) the inner product or 2) the negative exponential of the Jensen-Shannon divergence between the probability distributions. We show that in both cases the resulting similarity measure is positive definite and, therefore, corresponds to a kernel on the graphs. We perform a series of experiments on publicly available graph datasets from a variety of different domains, together with time-varying financial networks extracted from data for the New York Stock Exchange. Our experiments demonstrate the effectiveness of the proposed similarity measures.

Face Frontalization Using an Appearance-Flow-Based Convolutional Neural Network.

Facial pose variation is one of the major factors making face recognition (FR) a challenging task. One popular solution is to convert non-frontal faces to frontal ones on which FR is performed. Rotating faces causes facial pixel value changes. Therefore, existing CNN-based methods learn to synthesize frontal faces in color space. However, this learning problem in a color space is highly non-linear, causing the synthetic frontal faces to lose fine facial textures. In this paper, we take the view that the nonfrontal-frontal pixel changes are essentially caused by geometric transformations (rotation, translation, and so on) in space. Therefore, we aim to learn the nonfrontal-frontal facial conversion in the spatial domain rather than the color domain to ease the learning task. To this end, we propose an appearance-flow-based face frontalization convolutional neural network (A3F-CNN). Specifically, A3F-CNN learns to establish the dense correspondence between the non-frontal and frontal faces. Once the correspondence is built, frontal faces are synthesized by explicitly "moving" pixels from the non-frontal one. In this way, the synthetic frontal faces can preserve fine facial textures. To improve the convergence of training, an appearance-flow-guided learning strategy is proposed. In addition, generative adversarial network loss is applied to achieve a more photorealistic face, and a face mirroring method is introduced to handle the self-occlusion problem. Extensive experiments are conducted on face synthesis and pose invariant FR. Results show that our method can synthesize more photorealistic faces than the existing methods in both the controlled and uncontrolled lighting environments. Moreover, we achieve a very competitive FR performance on the Multi-PIE, LFW and IJB-A databases.

Thermodynamic Analysis of Time Evolving Networks.

The problem of how to represent networks, and from this representation, derive succinct characterizations of network structure and in particular how this structure evolves with time, is of central importance in complex network analysis. This paper tackles the problem by proposing a thermodynamic framework to represent the structure of time-varying complex networks. More importantly, such a framework provides a powerful tool for better understanding the network time evolution. Specifically, the method uses a recently-developed approximation of the network von Neumann entropy and interprets it as the thermodynamic entropy for networks. With an appropriately-defined internal energy in hand, the temperature between networks at consecutive time points can be readily derived, which is computed as the ratio of change of entropy and change in energy. It is critical to emphasize that one of the main advantages of the proposed method is that all these thermodynamic variables can be computed in terms of simple network statistics, such as network size and degree statistics. To demonstrate the usefulness of the thermodynamic framework, the paper uses real-world network data, which are extracted from time-evolving complex systems in the financial and biological domains. The experimental results successfully illustrate that critical events, including abrupt changes and distinct periods in the evolution of complex networks, can be effectively characterized.

Thermodynamic characterization of networks using graph polynomials.

In this paper, we present a method for characterizing the evolution of time-varying complex networks by adopting a thermodynamic representation of network structure computed from a polynomial (or algebraic) characterization of graph structure. Commencing from a representation of graph structure based on a characteristic polynomial computed from the normalized Laplacian matrix, we show how the polynomial is linked to the Boltzmann partition function of a network. This allows us to compute a number of thermodynamic quantities for the network, including the average energy and entropy. Assuming that the system does not change volume, we can also compute the temperature, defined as the rate of change of entropy with energy. All three thermodynamic variables can be approximated using low-order Taylor series that can be computed using the traces of powers of the Laplacian matrix, avoiding explicit computation of the normalized Laplacian spectrum. These polynomial approximations allow a smoothed representation of the evolution of networks to be constructed in the thermodynamic space spanned by entropy, energy, and temperature. We show how these thermodynamic variables can be computed in terms of simple network characteristics, e.g., the total number of nodes and node degree statistics for nodes connected by edges. We apply the resulting thermodynamic characterization to real-world time-varying networks representing complex systems in the financial and biological domains. The study demonstrates that the method provides an efficient tool for detecting abrupt changes and characterizing different stages in network evolution.

Generative Graph Prototypes from Information Theory.

In this paper we present a method for constructing a generative prototype for a set of graphs by adopting a minimum description length approach. The method is posed in terms of learning a generative supergraph model from which the new samples can be obtained by an appropriate sampling mechanism. We commence by constructing a probability distribution for the occurrence of nodes and edges over the supergraph. We encode the complexity of the supergraph using an approximate Von Neumann entropy. A variant of the EM algorithm is developed to minimize the description length criterion in which the structure of the supergraph and the node correspondences between the sample graphs and the supergraph are treated as missing data. To generate new graphs, we assume that the nodes and edges of graphs arise under independent Bernoulli distributions and sample new graphs according to their node and edge occurrence probabilities. Empirical evaluations on real-world databases demonstrate the practical utility of the proposed algorithm and show the effectiveness of the generative model for the tasks of graph classification, graph clustering and generating new sample graphs.

Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence.

In this paper we propose a quantum algorithm to measure the similarity between a pair of unattributed graphs. We design an experiment where the two graphs are merged by establishing a complete set of connections between their nodes and the resulting structure is probed through the evolution of continuous-time quantum walks. In order to analyze the behavior of the walks without causing wave function collapse, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the divergence between the evolution of two suitably initialized quantum walks over this structure is maximum when the original pair of graphs is isomorphic. We also prove that under special conditions the divergence is minimum when the sets of eigenvalues of the Hamiltonians associated with the two original graphs have an empty intersection.

Approximate von Neumann entropy for directed graphs.

In this paper, we develop an entropy measure for assessing the structural complexity of directed graphs. Although there are many existing alternative measures for quantifying the structural properties of undirected graphs, there are relatively few corresponding measures for directed graphs. To fill this gap in the literature, we explore an alternative technique that is applicable to directed graphs. We commence by using Chung's generalization of the Laplacian of a directed graph to extend the computation of von Neumann entropy from undirected to directed graphs. We provide a simplified form of the entropy which can be expressed in terms of simple node in-degree and out-degree statistics. Moreover, we find approximate forms of the von Neumann entropy that apply to both weakly and strongly directed graphs, and that can be used to characterize network structure. We illustrate the usefulness of these simplified entropy forms defined in this paper on both artificial and real-world data sets, including structures from protein databases and high energy physics theory citation networks.

Spherical and Hyperbolic Embeddings of Data.

Many computer vision and pattern recognition problems may be posed as the analysis of a set of dissimilarities between objects. For many types of data, these dissimilarities are not euclidean (i.e., they do not represent the distances between points in a euclidean space), and therefore cannot be isometrically embedded in a euclidean space. Examples include shape-dissimilarities, graph distances and mesh geodesic distances. In this paper, we provide a means of embedding such non-euclidean data onto surfaces of constant curvature. We aim to embed the data on a space whose radius of curvature is determined by the dissimilarity data. The space can be either of positive curvature (spherical) or of negative curvature (hyperbolic). We give an efficient method for solving the spherical and hyperbolic embedding problems on symmetric dissimilarity data. Our approach gives the radius of curvature and a method for approximating the objects as points on a hyperspherical manifold without optimisation. For objects which do not reside exactly on the manifold, we develop a optimisation-based procedure for approximate embedding on a hyperspherical manifold. We use the exponential map between the manifold and its local tangent space to solve the optimisation problem locally in the euclidean tangent space. This process is efficient enough to allow us to embed data sets of several thousand objects. We apply our method to a variety of data including time warping functions, shape similarities, graph similarity and gesture similarity data. In each case the embedding maintains the local structure of the data while placing the points in a metric space.

Characterizing graph symmetries through quantum Jensen-Shannon divergence.

In this paper we investigate the connection between quantum walks and graph symmetries. We begin by designing an experiment that allows us to analyze the behavior of the quantum walks on the graph without causing the wave function collapse. To achieve this, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the quantum Jensen-Shannon divergence between the evolution of two quantum walks with suitably defined initial states is maximum when the graph presents symmetries. Hence, we assign to each pair of nodes of the graph a value of the divergence, and we average over all pairs of nodes to characterize the degree of symmetry possessed by a graph.

Backtrackless walks on a graph.

The aim of this paper is to explore the use of backtrackless walks and prime cycles for characterizing both labeled and unlabeled graphs. The reason for using backtrackless walks and prime cycles is that they avoid tottering, and can increase the discriminative power of the resulting graph representation. However, the use of such methods is limited in practice because of their computational cost. In this paper, we present efficient methods for computing graph kernels, which are based on backtrackless walks in a labeled graph and whose worst case running time is the same as that of kernels based on random walks. For clustering unlabeled graphs, we construct feature vectors using Ihara coefficients, since these coefficients are related to the frequencies of prime cycles in the graph. To efficiently compute the low order coefficients, we present an O(|V|(3)) algorithm which is better than the O(|V|(6)) worst case running time of previously known algorithms. In the experimental evaluation, we apply the proposed method to clustering both labeled and unlabeled graphs. The results show that using backtrackless walks and prime cycles instead of random walks can increase the accuracy of recognition.

Heat diffusion: thermodynamic depth complexity of networks.

In this paper we use the Birkhoff-von Neumann decomposition of the diffusion kernel to compute a polytopal measure of graph complexity. We decompose the diffusion kernel into a series of weighted Birkhoff combinations and compute the entropy associated with the weighting proportions (polytopal complexity). The maximum entropy Birkhoff combination can be expressed in terms of matrix permanents. This allows us to introduce a phase-transition principle that links our definition of polytopal complexity to the heat flowing through the network at a given diffusion time. The result is an efficiently computed complexity measure, which we refer to as flow complexity. Moreover, the flow complexity measure allows us to analyze graphs and networks in terms of the thermodynamic depth. We compare our method with three alternative methods described in the literature (Estrada's heterogeneity index, the Laplacian energy, and the von Neumann entropy). Our study is based on 217 protein-protein interaction (PPI) networks including histidine kinases from several species of bacteria. We find a correlation between structural complexity and phylogeny (more evolved species have statistically more complex PPIs). Although our methods outperform the alternatives, we find similarities with Estrada's heterogeneity index in terms of network size independence and predictive power.