Causal Discovery in High-Dimensional Point Process Networks with Hidden Nodes

Thanks to technological advances leading to near-continuous time observations, emerging multivariate point process data offer new opportunities for causal discovery. However, a key obstacle in achieving this goal is that many relevant processes may not be observed in practice. Naïve estimation approaches that ignore these hidden variables can generate misleading results because of the unadjusted confounding. To plug this gap, we propose a deconfounding procedure to estimate high-dimensional point process networks with only a subset of the nodes being observed. Our method allows flexible connections between the observed and unobserved processes. It also allows the number of unobserved processes to be unknown and potentially larger than the number of observed nodes. Theoretical analyses and numerical studies highlight the advantages of the proposed method in identifying causal interactions among the observed processes.     

The Role of Instrumental Variables in Causal Inference Based on Independence of Cause and Mechanism

Causal inference methods based on conditional independence construct Markov equivalent graphs and cannot be applied to bivariate cases. The approaches based on independence of cause and mechanism state, on the contrary, that causal discovery can be inferred for two observations. In our contribution, we pose a challenge to reconcile these two research directions. We study the role of latent variables such as latent instrumental variables and hidden common causes in the causal graphical structures. We show that methods based on the independence of cause and mechanism indirectly contain traces of the existence of the hidden instrumental variables. We derive a novel algorithm to infer causal relationships between two variables, and we validate the proposed method on simulated data and on a benchmark of cause-effect pairs. We illustrate by our experiments that the proposed approach is simple and extremely competitive in terms of empirical accuracy compared to the state-of-the-art methods.     

Visibility graph analysis on quarterly macroeconomic series of China based on complex network theory

The visibility graph approach and complex network theory provide a new insight into time series analysis. The inheritance of the visibility graph from the original time series was further explored in the paper. We found that degree distributions of visibility graphs extracted from Pseudo Brownian Motion series obtained by the Frequency Domain algorithm exhibit exponential behaviors, in which the exponential exponent is a binomial function of the Hurst index inherited in the time series. Our simulations presented that the quantitative relations between the Hurst indexes and the exponents of degree distribution function are different for different series and the visibility graph inherits some important features of the original time series. Further, we convert some quarterly macroeconomic series including the growth rates of value-added of three industry series and the growth rates of Gross Domestic Product series of China to graphs by the visibility algorithm and explore the topological properties of graphs associated from the four macroeconomic series, namely, the degree distribution and correlations, the clustering coefficient, the average path length, and community structure. Based on complex network analysis we find degree distributions of associated networks from the growth rates of value-added of three industry series are almost exponential and the degree distributions of associated networks from the growth rates of GDP series are scale free. We also discussed the assortativity and disassortativity of the four associated networks as they are related to the evolutionary process of the original macroeconomic series. All the constructed networks have “small-world” features. The community structures of associated networks suggest dynamic changes of the original macroeconomic series. We also detected the relationship among government policy changes, community structures of associated networks and macroeconomic dynamics. We find great influences of government policies in China on the changes of dynamics of GDP and the three industries adjustment. The work in our paper provides a new way to understand the dynamics of economic development.     

GTAD: Graph and Temporal Neural Network for Multivariate Time Series Anomaly Detection

The rapid development of smart factories, combined with the increasing complexity of production equipment, has resulted in a large number of multivariate time series that can be recorded using sensors during the manufacturing process. The anomalous patterns of industrial production may be hidden by these time series. Previous LSTM-based and machine-learning-based approaches have made fruitful progress in anomaly detection. However, these multivariate time series anomaly detection algorithms do not take into account the correlation and time dependence between the sequences. In this study, we proposed a new algorithm framework, namely, graph attention network and temporal convolutional network for multivariate time series anomaly detection (GTAD), to address this problem. Specifically, we first utilized temporal convolutional networks, including causal convolution and dilated convolution, to capture temporal dependencies, and then used graph neural networks to obtain correlations between sensors. Finally, we conducted sufficient experiments on three public benchmark datasets, and the results showed that the proposed method outperformed the baseline method, achieving detection results with F1 scores higher than 95% on all datasets.     

Efficient Network Dismantling via Node Explosive Percolation

The network dismantling problem asks the minimum separate node set of a graph whose removal will break the graph into connected components with the size not larger than the one percentage of the original graph.This problem has attracted much attention recently and a lot of algorithms have been proposed. However, most of the network dismantling algorithms mainly focus on which nodes are included in the minimum separate set but overlook how to order them for removal, which will lead to low general efficiency during the dismantling process. In this paper,we reformulate the network dismantling problem by taking the order of nodes' removal into consideration. An efficient dismantling sequence will break the network quickly during the dismantling processes. We take the belief-propagation guided decimation(BPD) dismantling algorithm, a state-of-the-art algorithm, as an example, and employ the node explosive percolation(NEP) algorithm to reorder the early part of the dismantling sequence given by the BPD. The proposed method is denoted as the NEP-BPD algorithm(NBA) here. The numerical results on Erd¨os-R′enyi graphs,random-regular graphs, scale-free graphs, and some real networks show the high general efficiency of NBA during the entire dismantling process. In addition, numerical computations on random graph ensembles with the size from 2~(10) to2~(19) exhibit that the NBA is in the same complexity class with the BPD algorithm. It is clear that the NEP method we used to improve the general efficiency could also be applied to other dismantling algorithms, such as Min-Sum algorithm,equal graph partitioning algorithm and so on.     

Spectral Ranking of Causal Influence in Complex Systems

Similar to natural complex systems, such as the Earth’s climate or a living cell, semiconductor lithography systems are characterized by nonlinear dynamics across more than a dozen orders of magnitude in space and time. Thousands of sensors measure relevant process variables at appropriate sampling rates, to provide time series as primary sources for system diagnostics. However, high-dimensionality, non-linearity and non-stationarity of the data are major challenges to efficiently, yet accurately, diagnose rare or new system issues by merely using model-based approaches. To reliably narrow down the causal search space, we validate a ranking algorithm that applies transfer entropy for bivariate interaction analysis of a system’s multivariate time series to obtain a weighted directed graph, and graph eigenvector centrality to identify the system’s most important sources of original information or causal influence. The results suggest that this approach robustly identifies the true drivers or causes of a complex system’s deviant behavior, even when its reconstructed information transfer network includes redundant edges.     

Inverse problem for multivariate time series using dynamical latent variables

Factor analysis is a well known statistical method to describe the variability among observed variables in terms of a smaller number of unobserved latent variables called factors. While dealing with multivariate time series, the temporal correlation structure of data may be modeled by including correlations in latent factors, but a crucial choice is the covariance function to be implemented. We show that analyzing multivariate time series in terms of latent Gaussian processes, which are mutually independent but with each of them being characterized by exponentially decaying temporal correlations, leads to an efficient implementation of the expectation–maximization algorithm for the maximum likelihood estimation of parameters, due to the properties of block-tridiagonal matrices. The proposed approach solves an ambiguity known as the identifiability problem, which renders the solution of factor analysis determined only up to an orthogonal transformation. Samples with just two temporal points are sufficient for the parameter estimation: hence the proposed approach may be applied even in the absence of prior information about the correlation structure of latent variables by fitting the model to pairs of points with varying time delay. Our modeling allows one to make predictions of the future values of time series and we illustrate our method by applying it to an analysis of published gene expression data from cell culture HeLa.     

Clustering and community detection in directed networks: A survey

Networks (or graphs) appear as dominant structures in diverse domains, including sociology, biology, neuroscience and computer science. In most of the aforementioned cases graphs are directed — in the sense that there is directionality on the edges, making the semantics of the edges nonsymmetric as the source node transmits some property to the target one but not vice versa. An interesting feature that real networks present is the clustering or community structure property, under which the graph topology is organized into modules commonly called communities or clusters. The essence here is that nodes of the same community are highly similar while on the contrary, nodes across communities present low similarity. Revealing the underlying community structure of directed complex networks has become a crucial and interdisciplinary topic with a plethora of relevant application domains. Therefore, naturally there is a recent wealth of research production in the area of mining directed graphs — with clustering being the primary method sought and the primary tool for community detection and evaluation. The goal of this paper is to offer an in-depth comparative review of the methods presented so far for clustering directed networks along with the relevant necessary methodological background and also related applications. The survey commences by offering a concise review of the fundamental concepts and methodological base on which graph clustering algorithms capitalize on. Then we present the relevant work along two orthogonal classifications. The first one is mostly concerned with the methodological principles of the clustering algorithms, while the second one approaches the methods from the viewpoint regarding the properties of a good cluster in a directed network. Further, we present methods and metrics for evaluating graph clustering results, demonstrate interesting application domains and provide promising future research directions.     

Time series prediction using wavelet process neural network

In the real world, the inputs of many complicated systems are time-varying functions or processes. In order to predict the outputs of these systems with high speed and accuracy, this paper proposes a time series prediction model based on the wavelet process neural network, and develops the corresponding learning algorithm based on the expansion of the orthogonal basis functions. The effectiveness of the proposed time series prediction model and its learning algorithm is proved by the Macke-Glass time series prediction, and the comparative prediction results indicate that the proposed time series prediction model based on the wavelet process neural network seems to perform well and appears suitable for using as a good tool to predict the highly complex nonlinear time series.     

Analyzing multiple nonlinear time series with extended Granger causality

Identifying causal relations among simultaneously acquired signals is an important problem in multivariate time series analysis. For linear stochastic systems Granger proposed a simple procedure called the Granger causality to detect such relations. In this work we consider nonlinear extensions of Granger's idea and refer to the result as extended Granger causality. A simple approach implementing the extended Granger causality is presented and applied to multiple chaotic time series and other types of nonlinear signals. In addition, for situations with three or more time series we propose a conditional extended Granger causality measure that enables us to determine whether the causal relation between two signals is direct or mediated by another process.     

Causality detection based on information-theoretic approaches in time series analysis

Synchronization, a basic nonlinear phenomenon, is widely observed in diverse complex systems studied in physical, biological and other natural sciences, as well as in social sciences, economy and finance. While studying such complex systems, it is important not only to detect synchronized states, but also to identify causal relationships (i.e. who drives whom) between concerned (sub) systems. The knowledge of information-theoretic measures (i.e. mutual information, conditional entropy) is essential for the analysis of information flow between two systems or between constituent subsystems of a complex system. However, the estimation of these measures from a set of finite samples is not trivial. The current extensive literatures on entropy and mutual information estimation provides a wide variety of approaches, from approximation-statistical, studying rate of convergence or consistency of an estimator for a general distribution, over learning algorithms operating on partitioned data space to heuristical approaches. The aim of this paper is to provide a detailed overview of information theoretic approaches for measuring causal influence in multivariate time series and to focus on diverse approaches to the entropy and mutual information estimation.     

Efficient algorithm based on neighborhood overlap for community identification in complex networks

Community structure is an important feature in many real-world networks. Many methods and algorithms for identifying communities have been proposed and have attracted great attention in recent years. In this paper, we present a new approach for discovering the community structure in networks. The novelty is that the algorithm uses the strength of the ties for sorting out nodes into communities. More specifically, we use the principle of weak ties hypothesis to determine to what community the node belongs. The advantages of this method are its simplicity, accuracy, and low computational cost. We demonstrate the effectiveness and efficiency of our algorithm both on real-world networks and on benchmark graphs. We also show that the distribution of link strength can give a general view of the basic structure information of graphs.     

Accelerating Causal Inference and Feature Selection Methods through G-Test Computation Reuse

This article presents a novel and remarkably efficient method of computing the statistical G-test made possible by exploiting a connection with the fundamental elements of information theory: by writing the G statistic as a sum of joint entropy terms, its computation is decomposed into easily reusable partial results with no change in the resulting value. This method greatly improves the efficiency of applications that perform a series of G-tests on permutations of the same features, such as feature selection and causal inference applications because this decomposition allows for an intensive reuse of these partial results. The efficiency of this method is demonstrated by implementing it as part of an experiment involving IPC–MB, an efficient Markov blanket discovery algorithm, applicable both as a feature selection algorithm and as a causal inference method. The results show outstanding efficiency gains for IPC–MB when the G-test is computed with the proposed method, compared to the unoptimized G-test, but also when compared to IPC–MB++, a variant of IPC–MB which is enhanced with an AD–tree, both static and dynamic. Even if this proposed method of computing the G-test is presented here in the context of IPC–MB, it is in fact bound neither to IPC–MB in particular, nor to feature selection or causal inference applications in general, because this method targets the information-theoretic concept that underlies the G-test, namely conditional mutual information. This aspect grants it wide applicability in data sciences.     

Trans-dimensional geoacoustic inversion

This paper develops a general trans-dimensional Bayesian methodology for geoacoustic inversion. Trans-dimensional inverse problems are a generalization of fixed-dimensional inversion that includes the number and type of model parameters as unknowns in the problem. By extending the inversion state space to multiple subspaces of different dimensions, the posterior probability density quantifies the state of knowledge regarding inversion parameters, including effects due to limited knowledge about appropriate parametrization of the environment and error processes. The inversion is implemented here using a reversible-jump Markov chain Monte Carlo algorithm and the seabed is parametrized using a partition model. Unknown data errors are addressed by including a data-error model. Jumps between dimensions are implemented with a birth-death methodology that allows transitions between dimensions by adding or removing interfaces while maintaining detailed balance in the Markov chain. Trans-dimensional inversion results in an inherently parsimonious solution while partition modeling provides a naturally self-regularizing algorithm based on data information content, not on subjective regularization functions. Together, this results in environmental estimates that quantify appropriate seabed structure as supported by the data, allowing sharp discontinuities while approximating smooth transitions where needed. This approach applies generally to geoacoustic inversion and is illustrated here with seabed reflection-coefficient data.     

Sound-producing sources as objects of perception: rate normalization and nonspeech perception

In a variety of experiments and paradigms, researchers have attempted to determine whether or not speech perception is specialized by comparing perception of speech syllables to perception of nonspeech analogs. While nonspeech analogs appear optimal as comparisons to speech because they are acoustically similar without being recognized as speechlike, it is argued that the comparison they offer is confounded and uninterpretable. Two experiments are designed to show that, in auditory perception generally where acoustic signals are causal consequences of mechanical events, perceptual experiences are of the mechanical events themselves, not of the acoustic signal. This has two consequences. One is that there is a confounding in comparisons of speech with sine wave analogs that, whereas the one perceived as speech also has a definite causal source, the other, perceived as nonspeech, has an indeterminate or ambiguous source. A second is that response patterns in classification tasks such as those used in the literature comparing speech to nonspeech will reflect properties of the perceived sound-producing event; they will not provide a clear window on auditory system processes used to recover event properties. Experiment 3 is designed to show that perception of many acoustic-signal-producing events can appear to be special by the logic of speech-sine wave comparisons--even events that cannot plausibly be supposed to involve a specialization.     

Use of recurrence analysis to measure the dynamical stability of a multi-species community model

Quantifying the effects of species richness and environmental disturbance on the stability of communities is a long-standing challenge in ecology. In this study, multivariate recurrence analysis was used to assess the dynamical stability of modelled ecological communities subject to random, correlated environmental noise. Based on an analysis of biomass time series for each species, we show that two measures computed from the joint recurrence matrix, the Kolmogorov entropy and percent determinism, capture aspects of community stability that are not detected using the coefficient of variation for the whole community. In particular, when population fluctuations are correlated in time, recurrence analysis is a superior method for detecting the stabilizing effect of species richness on a community. We conclude that recurrence analysis is an appropriate tool for the analysis of ecological data, and that it may be particularly useful for detecting the relative importance of exogenous and endogenous drivers on the dynamics of ecological communities.     

Research on Community Structure in Bus Transport Networks

We abstract the bus transport networks (BTNs) to two kinds of complex networks with space L and space P methods respectively. Using improved community detecting algorithm (PKM agglomerative algorithm), we analyze the community property of two kinds of BTNs graphs. The results show that the BTNs graph described with space L method have obvious community property, but the other kind of BTNs graph described with space P method have not. The reason is that the BTNs graph described with space P method have the intense overlapping community property and general community division algorithms can not identify this kind of community structure. To overcome this problem, we propose a novel community structure called N-depth community and present a corresponding community detecting algorithm, which can detect overlapping community. Applying the novel community structure and detecting algorithm to a BTN evolution model described with space P, whose network property agrees well with real BTNs', we get obvious community property.     

Multivariate analysis of dynamical processes

The analysis of multi-dimensional biomedical systems requires analysis techniques, which are able to deal with multivariate data consisting of both time series as well as point processes. Univariate and bivariate analysis techniques in the frequency domain for time series and point processes are established and investigated, although the number of investigations is strongly biased towards time series. Actual multivariate techniques for time series or hybrids of time series and point processes are scarcely addressed. Here, we present spectral analysis techniques which are able to analyse point processes as well as time series. Thereby, univariate, bivariate as well as multivariate techniques are discussed. Applications to simulated as well as real-world data reveal the abilities of the proposed techniques.     

Minimum spanning trees for community detection

A simple deterministic algorithm for community detection is provided by using two rounds of minimum spanning trees. By comparing the first round minimum spanning tree (1st-MST) with the second round spanning tree (2nd-MST) of the network, communities are detected and their overlapping nodes are also identified. To generate the two MSTs, a distance matrix is defined and computed from the adjacent matrix of the network. Compared with the resistance matrix or the communicability matrix used in community detection in the literature, the proposed distance matrix is very simple in computation. The proposed algorithm is tested on real world social networks, graphs which are failed by the modularity maximization, and the LFR benchmark graphs for community detection.     

基于多路可视图的健康与心梗患者心电图信号复杂网络识别

可视图(visibility graph, VG)算法已被证明是将时间序列转换为复杂网络的简单且高效的方法,其构成的复杂网络在拓扑结构中继承了原始时间序列的动力学特性.目前,单维时间序列的可视图分析已趋于成熟,但应用于复杂系统时,单变量往往无法描述系统的全局特征.本文提出一种新的多元时间序列分析方法,将心梗和健康人的12导联心电图(electrocardiograph, ECG)信号转换为多路可视图,以每个导联为一个节点,两个导联构成可视图的层间互信息为连边权重,将其映射到复杂网络.由于不同人群的全连通网络表现为完全相同的拓扑结构,无法唯一表征不同个体的动力学特征,根据层间互信息大小重构网络,提取权重度和加权聚类系数,实现对不同人群12导联ECG信号的识别.为判断序列长度对识别效果的影响,引入多尺度权重度分布熵.由于健康受试者拥有更高的平均权重度和平均加权聚类系数,其映射网络表现为更加规则的结构、更高的复杂性和连接性,可以与心梗患者进行区分,两个参数的识别准确率均达到93.3%.