Diffusing a graph signal at multiple scales requires to compute the action of the exponential of as many versions of the Laplacian matrix. Considering the truncated Chebyshev polynomial approximation of the exponential, we derive a tightened bound on the approximation error, allowing thus for a better estimate of the polynomial degree that reaches a prescribed error. We leverage the properties of these approximations to factorize the computation of the action of the diffusion operator over multiple scales, thus drastically reducing its computational cost.

We present a novel multiview canonical correlation analysis model based on a variational approach. This is the first nonlinear model that takes into account the available graph-based geometric constraints while being scalable for processing large scale datasets with multiple views. It is based on an autoencoder architecture with graph convolutional neural network layers. We experiment with our approach on classification, clustering, and recommendation tasks on real datasets. The algorithm is competitive with state-of-the-art multiview representation learning techniques.

The use of the heat kernel on graphs has recently given rise to a family of so-called Diffusion-Wasserstein distances which resort to Optimal Transport theory for comparing attributed graphs. In this paper, we address the open problem of optimizing the diffusion time used in these distances. Inspired from the notion of triplet-based constraints, we design a loss function that aims at bringing two graphs closer together while keeping an impostor away. After a thorough analysis of the properties of this function, we show on synthetic data that the resulting Diffusion-Wasserstein distances outperforms the Gromov and Fused-Gromov Wasserstein distances on unsupervised graph domain adaptation tasks.

We study the inference of conditional independence graph from the partial Phase Locking Value (PLV) index of multivariate time series. A typical application is the inference of temporal functional connectivity from brain data. We extend the recently proposed time-varying graphical lasso to the measurement of partial locking values, yielding a sparse and temporally coherent dynamical graph that characterizes the evolution of the phase synchrony between each pair of signals. Cast as an optimization problem, we solve it using the alternating direction method of multipliers. The approach is validated on simulated Gaussian multivariate signals and Roessler oscillators. The potential of this regularized partial PLV is then illustrated on actual iEEG data during an epileptic seizure.

We study the problem of parametric modeling of network-structured signals with graph filters. To benefit from the properties of several graph shift operators simultaneously, and to enhance interpretability, we investigate combinations of parallel graph filters with different shift operators. Due to their extra degrees of freedom, these models might suffer from over-fitting. We address this problem through a weighted ℓ2-norm regularization formulation to perform model selection by encouraging group sparsity. What makes this formulation interesting is that it is actually a smooth convex optimization problem. Experiments on real-world data structured by undirected and directed graphs show the effectiveness of this method.

Over the last years, several stationarity tests have been proposed. One of these methods uses time-frequency representations and stationarized replicas of the signal (known as surrogates) for testing wide-sense stationarity. In this letter, we propose a procedure to improve the original surrogate test. The proposed methodology can be seen as a guideline on how the surrogate test can be improved. We show mathematically that the modified test should exhibit improved classification performance. Numerical simulations on synthetic and real-world signals are carried out to evaluate the modified test against competing ones.

The success of Empirical Mode Decomposition (EMD) resides in its practical approach to dissect non-stationary data. EMD repetitively goes through the entire data span to iteratively extract Intrinsic Mode Functions (IMFs). This approach, however, is not suitable for data stream as the entire data set has to be reconsidered every time a new point is added. To overcome this, we propose Online EMD, an algorithm that extracts IMFs on the fly. The two key elements of Online EMD are a sliding window to compute local IMFs, and a stitching procedure to gradually append local IMFs to the final result. Using synthetic data we show that the decomposition quality of Online EMD is similar to classical EMD. We also present results obtained with a real data set to expose the practical advantages of Online EMD when dealing with data stream or large data set.

BACKGROUND: Structural interaction frequency matrices between all genome loci are now experimentally achievable thanks to high-throughput chromosome conformation capture technologies. This ensues a new methodological challenge for computational biology which consists in objectively extracting from these data the structural motifs characteristic of genome organisation. RESULTS: We deployed the fast multi-scale community mining algorithm based on spectral graph wavelets to characterise the networks of intra-chromosomal interactions in human cell lines. We observed that there exist structural domains of all sizes up to chromosome length and demonstrated that the set of structural communities forms a hierarchy of chromosome segments. Hence, at all scales, chromosome folding predominantly involves interactions between neighbouring sites rather than the formation of links between distant loci. CONCLUSIONS: Multi-scale structural decomposition of human chromosomes provides an original framework to question structural organisation and its relationship to functional regulation across the scales. By construction the proposed methodology is independent of the precise assembly of the reference genome and is thus directly applicable to genomes whose assembly is not fully determined.

Bluetooth sensors have recently been developed throughout the world for traffic information gathering. Primarily designed for travel time analysis, this article presents a method for vehicular trajectories retrieval. After a short description of some of the challenges at hand in using Bluetooth data in an urban network, a procedure to extract trip information from such data is proposed. It is further analyzed and illustrated at work on a real dataset collected in Brisbane. Last, this article shows that using spatially constrained shortest path analysis, this trip information, once extracted, can be used for the reconstruction of the trajectories. The performance of the process is assessed using both a simulated dataset and one from the real-world acquired in Brisbane, showing encouraging results, with up to 84% of accurately recovered trajectories.

In the mid 1990s, it was shown that the statistics of aggregated time series from Internet traffic departed from those of traditional short range-dependent models, and were instead characterized by asymptotic self-similarity. Following this seminal contribution, over the years, many studies have investigated the existence and form of scaling in Internet traffic. This contribution first aims at presenting a methodology, combining multiscale analysis (wavelet and wavelet leaders) and random projections (or sketches), permitting a precise, efficient and robust characterization of scaling, which is capable of seeing through non-stationary anomalies. Second, we apply the methodology to a data set spanning an unusually long period: 14 years, from the MAWI traffic archive, thereby allowing an in-depth longitudinal analysis of the form, nature, and evolutions of scaling in Internet traffic, as well as network mechanisms producing them. We also study a separate three-day long trace to obtain complementary insight into intra-day behavior. We find that a biscaling (two ranges of independent scaling phenomena) regime is systematically observed: long-range dependence over the large scales, and multifractallike scaling over the fine scales. We quantify the actual scaling ranges precisely, verify to high accuracy the expected relationship between the long range dependent parameter and the heavy tail parameter of the flow size distribution, and relate fine scale multifractal scaling to typical IP packet inter-arrival and to round-trip time distributions.

We build upon recent advances in graph signal processing to propose a faster spectral clustering algorithm. Indeed, classical spectral clustering is based on the computation of the first k eigenvectors of the similarity matrix' Laplacian, whose computation cost, even for sparse matrices, becomes prohibitive for large datasets. We show that we can estimate the spectral clustering distance matrix without computing these eigenvectors: by graph filtering random signals. Also, we take advantage of the stochasticity of these random vectors to estimate the number of clusters k. We compare our method to classical spectral clustering on synthetic data, and show that it reaches equal performance while being faster by a factor at least two for large datasets.

We present a new anomaly detector for data traffic, ‘SMS’, based on combining random projections (sketches) with multiscale analysis, which has low computational complexity. The sketches allow ‘normal’ traffic to be automatically and robustly extracted, and anomalies detected, without the need for training data. The multiscale analysis extracts statistical descriptors, using wavelet leader tools developed recently for multifractal analysis, without any need for timescales to be selected a priori. The proposed detector is illustrated using a large recent dataset of Internet backbone traffic from the MAWI archive, and compared against existing detectors.

In transport networks, Origin-Destination matrices (ODM) are classically estimated from road traffic counts whereas recent technologies grant also access to sample car trajectories. One example is the deployment in cities of Bluetooth scanners that measure the trajectories of Bluetooth equipped cars. Exploiting such sample trajectory information, the classical ODM estimation problem is here extended into a link-dependent ODM (LODM) one. This much larger size estimation problem is formulated here in a variational form as an inverse problem. We develop a convex optimization resolution algorithm that incorporates network constraints. We study the result of the proposed algorithm on simulated network traffic.

Temporal networks describe a large variety of systems having a temporal evolution. Characterization and visualization of their evolution are often an issue especially when the amount of data becomes huge. We propose here an approach based on the duality between graphs and signals. Temporal networks are represented at each time instant by a collection of signals, whose spectral analysis reveals connection between frequency features and structure of the network. We use nonnegative matrix factorization (NMF) to find these frequency features and track them over time. Transforming back these features into subgraphs reveals the underlying structures which form a decomposition of the temporal network.

This paper presents a 2D transposition of the Hilbert-Huang Transform (HHT), an empirical data analysis method designed for studying instantaneous amplitudes and phases of non-stationary data. The principle is to adaptively decompose an image into oscillating parts called Intrinsic Mode Functions (IMFs) using an Empirical Mode Decomposition method (EMD), and then to perform Hilbert spectral analysis on the IMFs in order to recover local amplitudes and phases. For the decomposition step, we propose a new 2D mode decomposition method based on non-smooth convex optimization, while for the instantaneous spectral analysis, we use a 2D transposition of Hilbert spectral analysis called monogenic analysis, based on Riesz transform and allowing to extract instantaneous amplitudes, phases, and orientations. The resulting 2D-HHT is validated on simulated data.

In this manuscript, we propose a novel nonparametric test for nonstationarities that are seen as a trend or an evolution in the local energy of the signal. The idea of the proposed technique consists in applying empirical mode decomposition for estimating and further quantifying the trend in the time marginal of the estimated time-frequency representation. Such methodology allows for the detection of slowly-varying nonstationarities of first and second-order.

This paper provides an extension of the 1D Hilbert Huang transform for the analysis of images using recent optimization techniques. The proposed method consists of: 1) adaptively decomposing an image into oscillating parts called intrinsic mode functions (IMFs) using a mode decomposition procedure and 2) providing a local spectral analysis of the obtained IMFs in order to get the local amplitudes, frequencies, and orientations. For the decomposition step, we propose two robust 2D mode decompositions based on nonsmooth convex optimization: 1) a genuine 2D approach, which constrains the local extrema of the IMFs and 2) a pseudo-2D approach, which separately constrains the extrema of lines, columns, and diagonals. The spectral analysis step is an optimization strategy based on Prony annihilation property and applied on small square patches of the IMFs. The resulting 2D Prony–Huang transform is validated on simulated and real data.

Intrapartum fetal heart rate monitoring constitutes an important stake aiming at early acidosis detection. Measuring heart rate variability is often considered a powerful tool to assess the intrapartum health status of fetus and has been envisaged using various techniques. In the present contribution, scale invariance parameters, such as the Hurst exponent and the global regularity exponent, are estimated from wavelet coefficients of intrapartum fetal heart rate time series. Their ability to evaluate the health status of fetuses is quantified from a case study database, constituted at a French Academic Hospital in Lyon. Notably, the ability of such parameters to discriminate subjects incorrectly classified according to FIGO rules as abnormal is discussed. Also, the impact of the occurrence of decelerations identified as complicated by obstetricians on the values taken by Hurst parameter is investigated in detail.

Sensor deployments in large buildings allow the administrators to supervise the building infrastructure and identify abnormalities. Nevertheless, the numerous data streams reported by the increasing number of sensors overwhelm the building administrators. We propose a methodology that assists them to identify abnormal devices usages. The proposed method takes advantage of Ensemble Empirical Mode Decomposition (E-EMD) to uncover the patterns of power-draw signals, thereby enabling us to estimate the intrinsic inter-device correlations. By monitoring the devices correlations over time we compute the usual usage of the devices and report the devices that deviate from their normal usage. Our evaluation with 10 weeks of real data shows the efficiency of the proposed method to uncover the devices intrinsic relationships and detect peculiar events that require the administrators attention.

A typical large building contains thousands of sensors, monitoring the HVAC system, lighting, and other operational sub-systems. With the increased push for operational efficiency, operators are relying more on historical data processing to uncover opportunities for energy-savings. However, they are overwhelmed with the deluge of data and seek more efficient ways to identify potential problems. In this paper, we present a new approach called the Strip, Bind and Search (SBS); a method for uncovering abnormal equipment behavior and in-concert usage patterns. SBS uncovers relationships between devices and constructs a model for their usage pattern relative to other devices. It then flags deviations from the model. We run SBS on a set of building sensor traces; each containing hundred sensors reporting data flows over 18 weeks from two separate buildings with fundamentally different infrastructures. We demonstrate that, in many cases, SBS uncovers misbehavior corresponding to inefficient device usage that leads to energy waste. The average waste uncovered is as high as 2500~kWh per device.

End-host profiling by analyzing network traffic comes out as a major stake in traffic engineering. Graphlet constitutes an efficient and common framework for interpreting host behaviors, which essentially consists of a visual representation as a graph. However, graphlet analyses face the issues of choosing between supervised and unsupervised approaches. The former can analyze a priori defined behaviors but is blind to undefined classes, while the latter can discover new behaviors at the cost of difficult a posteriori interpretation. This paper aims at bridging the gap between the two. First, to handle unknown classes, unsupervised clustering is originally revisited by extracting a set of graphlet-inspired attributes for each host. Second, to recover interpretability for each resulting cluster, a synoptic graphlet, defined as a visual graphlet obtained by mapping from a cluster, is newly developed. Comparisons against supervised graphlet-based, port-based, and payload-based classifiers with two datasets demonstrate the effectiveness of the unsupervised clustering of graphlets and the relevance of the a posteriori interpretation through synoptic graphlets. This development is further complemented by studying evolutionary tree of synoptic graphlets, which quantifies the growth of graphlets when increasing the number of inspected packets per host.

Surrogates are investigated as procedures of synthesis for multi-variate time series with prescribed properties. First it is shown how to prescribe a multivariate covariance function jointly with the (possibly non-Gaussian) marginal distributions. Second, using histogram matching by approximate optimal transport with the Sliced Wasserstein Distance, the surrogate synthesis is extended to prescribe covariance function and joint-distribution of the components. Algorithms are described and justified, and numerical examples are shown. MATLAB codes are publicly available online.

We propose a novel gap-filling technique, based on the empirical mode decomposition (EMD). The idea is that a signal with missing data can be decomposed into a set of intrinsic mode functions (IMFs) with missing data. Filling the gaps in each IMF should be easier than filling the gaps in the original signal. This is because each IMF varies much more slowly than the original signal, and also because the IMFs are known to have useful regularity properties. We demonstrate the performance of our technique on environmental pollutant data.

Recently, a time-frequency approach for testing stationarity was proposed. However, this method inefficiently detects nonstationarities of the first-order. Here, we present two contributions that improve the test performance and allow the detection of first-order evolutions. The first one is to use an adequate distance measure. The second is a modification of the method in order to consider the spectral content from the signal itself when computing the distances.

While an exact stationarization of a process with a given spectrum magnitude can be obtained via a complete randomization of the spectrum phase ("surrogates" technique), we pro pose here a softened version in which the degree of stationarization can be controlled by a perturbation of the actual phase. A basic theory for such "transitional surrogates" is first discussed, with emphasis on two effective constructions based on either white Gaussian noise or random walks. Some typical examples are considered for illustration, and performance evaluations are provided for supporting the usefulness of the approach in the context of stationarity testing.

Evaluating anomaly detectors is a crucial task in traffic monitoring made particularly difficult due to the lack of ground truth. The goal of the present article is to assist researchers in the evaluation of detectors by providing them with labeled anomaly traffic traces. We aim at automatically finding anomalies in the MAWI archive using a new methodology that combines different and independent detectors. A key challenge is to compare the alarms raised by these detectors, though they operate at different traffic granularities. The main contribution is to propose a reliable graph-based methodology that combines any anomaly detector outputs. We evaluated four unsupervised combination strategies; the best is the one that is based on dimensionality reduction. The synergy between anomaly detectors permits to detect twice as many anomalies as the most accurate detector, and to reject numerous false positive alarms reported by the detectors. Significant anomalous traffic features are extracted from reported alarms, hence the labels assigned to the MAWI archive are concise. The results on the MAWI traffic are publicly available and updated daily. Also, this approach permits to include the results of upcoming anomaly detectors so as to improve over time the quality and variety of labels.

We propose a new estimate of the time-varying spectra of uniformly modulated processes. The estimate is based on a resampling scheme which incorporates empirical mode decompositions and surrogate data techniques. The performance of the method is studied via simulations.

An operational framework is developed for testing stationarity relatively to an observation scale. The proposed method makes use of a family of stationary surrogates for defining the null hypothesis of stationarity. As a further contribution to the field, we demonstrate the strict-sense stationarity of surrogate signals and we exploit this property to derive the asymptotic distributions of their spectrogram and power spectral density. A statistical hypothesis testing framework is then proposed to check signal stationarity. Finally, some results are shown on a typical model of signals that can be thought of as stationary or nonstationary, depending on the observation scale used.

Usually the mel-frequency cepstral coefficients are estimated either from a periodogram or from a windowed periodogram. We state a general estimator which also includes multitaper estimators. We propose approximations of the variance and bias of the estimate of each coefficient. By using Monte Carlo computations, we demonstrate that the approximations are accurate. Using the proposed formulas, the peak matched multitaper estimator is shown to have low mean square error (squared bias + variance) on speech-like processes. It is also shown to perform slightly better in the NIST 2006 speaker verification task as compared to the Hamming window conventionally used in this context.

After the seminal work by Taqqu relating self-similarity to heavy-tailed distributions, a number of research articles verified that aggregated Internet traffic time series show self-similarity and that Internet attributes, like Web file sizes and flow lengths, were heavy-tailed. However, the validation of the theoretical prediction relating self-similarity and heavy tails remains unsatisfactorily addressed, being investigated using either numerical or network simulations, or from uncontrolled Web traffic data. Notably, this prediction has never been conclusively verified on real networks using controlled and stationary scenarios, prescribing specific heavy-tailed distributions, and estimating confidence intervals. With this goal in mind, we use the potential and facilities offered by the large-scale, deeply reconfigurable and fully controllable experimental Grid5000 instrument, combined with state-of-the-art estimators, to investigate the prediction's observability on real networks. To this end, we organize a large number of controlled traffic circulation sessions on a nationwide real network involving 200 independent hosts. We use a FPGA-based measurement system to collect the corresponding traffic at packet level. We then estimate both the self-similarity exponent of the aggregated time series and the heavy-tail index of flow-size distributions, independently. Not only do our results complement and validate, with a striking accuracy, some conclusions drawn from a series of pioneering studies, but they also bring in new insights on the controversial role of certain components of real networks.

In this work we present a simple toy-model that is able to explain certain empirical observations reported in a set of previous papers by Hohn et al. about the wavelet spectrum of real traffic traces. Therein, the authors found that the wavelet spectrum is substantially invariant to flow scrambling and truncation. Such finding suggested that super-flow structures above the transport layer - i.e., sessions - can be ignored for modeling the packet arrival process. Based on the proposed toy-model, we offer an interpretation framework that goes in the opposite direction, indicating that sessions, not transport-layer flows, should be taken as the main structural entities in simplified on/off models.

This contribution aims at performing a longitudinal study of the evolution of the traffic collected every day for seven years on a trans-Pacific backbone link (the MAWI dataset). Long term characteristics are investigated both at TCP/IP layers (packet and flow attributes) and application usages. The analysis of this unique dataset provides new insights into changes in traffic statistics, notably on the persistence of Long Range Dependence, induced by the on-going increase in link bandwidth. Traffic in the MAWI dataset is subject to bandwidth changes, to congestions, and to a variety of anomalies. This allows the comparison of their impacts on the traffic statistics but at the same time significantly impairs long term evolution characterizations. To account for this difficulty, we show and explain how and why random projection (sketch) based analysis procedures provide practitioners with an efficient and robust tool to disentangle actual long term evolutions from time localized events such as anomalies and link congestions. Our central results consist in showing a strong and persistent long range dependence controlling jointly byte and packet counts. An additional study of a 24-hour trace complements the long-term results with the analysis of intraday variabilities.

In the case of multicomponent AM-FM signals, the idealized representation which consists of weighted trajectories on the time-frequency (TF) plane, is intrinsically sparse. Recent advances in optimal recovery from sparsity constraints thus suggest to revisit the issue of TF localization by exploiting sparsity, as adapted to the specific context of (quadratic) TF distributions. Based on classical results in TF analysis, it is argued that the relevant information is mostly concentrated in a restricted subset of Fourier coefficients of the Wigner-Ville distribution neighbouring the origin of the ambiguity plane. Using this incomplete information as the primary constraint, the desired distribution follows as the minimum l1-norm solution in the transformed TF domain. Possibilities and limitations of the approach are demonstrated via controlled numerical experiments, its performance is assessed in various configurations and the results are compared with standard techniques. It is shown that improved representations can be obtained, though at a computational cost which is significantly increased.

A new family of distributions, constructed by summing two correlated gamma random variables, is studied. First, a simple closed form expression for their density is derived. Second, the three parameters characterizing such a density are estimated by using the maximum likelihood (ML) principle. Numerical simulations are conducted to compare the performance of the ML estimator against those of the conventional estimator of moments. Finally, a multiresolution multivariate gamma based modeling of Internet traffic illustrates the potential interest of the proposed distributions for the detection of anomalies. Aggregated times series of IP packet counts are split into adjacent non overlapping time blocks. The distribution of the resulting time series are modeled by the proposed multivariate gamma based distributions, over a collection of different aggregation levels. The anomaly detection strategy is based on tracking changes along time of the corresponding multiresolution parameters.

The goals of the present contribution are twofold. First, we propose the use of a non-Gaussian long-range dependent process to model Internet traffic aggregated time series. We give the definitions and intuition behind the use of this model. We detail numerical procedures that can be used to synthesize artificial traffic exactly following the model prescription. We also propose original and practically effective procedures to estimate the corresponding parameters from empirical data. We show that this empirical model relevantly describes a large variety of Internet traffic, including both regular traffic obtained from public reference repositories and traffic containing legitimate (flash crowd) or illegitimate (DDoS attack) anomalies. We observe that the proposed model accurately fits the data for a wide range of aggregation levels. The model provides us with a meaningful multiresolution (i.e., aggregation level dependent) statistics to characterize the traffic: the evolution of the estimated parameters with respect to the aggregation level. It opens the track to the second goal of the paper: anomaly detection. We propose the use of a quadratic distance computed on these statistics to detect the occurrences of DDoS attack and study the statistical performance of these detection procedures. Traffic with anomalies was produced and collected by us so as to create a controlled and reproducible database, allowing for a relevant assessment of the statistical performance of the proposed (modeling and detection) procedures

We study a class of self-similar processes that are not stationary, nor have stationary increments. They are called Euler-Cauchy (EC) processes and are built as output of linear scale-invariant parametric systems. This article study several discretization methods of EC processes which are not bandlimited processes: direct sampling, bilinear transformation and approximation on fractional B-splines. For the three different methods, we obtain theoretical formulae and compute numerical realizations and properties

A definition of stochastic discrete scale invariance (DSI) is proposed and its properties studied. It is shown how the Lamperti (1962) transformation, which transforms stationarity in self-similarity, is also a means to connect processes deviating from stationarity and processes which are not exactly scale invariant: in particular we interpret DSI as the image of cyclostationarity. This theoretical result is employed to introduce a multiplicative spectral representation of DSI processes based on the Mellin transform, and preliminary remarks are given about estimation issues.