Abstract: Presents a listing of the editorial board, board of governors, current staff, committee members, and/or society editors for this issue of the publication. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Jiani Li;Waseem Abbas;Xenofon Koutsoukos;
Pages: 1 - 17 Abstract: In this article, we study resilient distributed diffusion for multi-task estimation in the presence of adversaries where networked agents must estimate distinct but correlated states of interest by processing streaming data. We show that in general diffusion strategies are not resilient to malicious agents that do not adhere to the diffusion-based information processing rules. In particular, by exploiting the adaptive weights used for diffusing information, we develop time-dependent attack models that drive normal agents to converge to states selected by the attacker. We show that an attacker that has complete knowledge of the system can always drive its targeted agents to its desired estimates. Moreover, an attacker that does not have complete knowledge of the system including streaming data of targeted agents or the parameters they use in diffusion algorithms, can still be successful in deploying an attack by approximating the needed information. The attack models can be used for both stationary and non-stationary state estimation. In addition, we present and analyze a resilient distributed diffusion algorithm that is resilient to any data falsification attack in which the number of compromised agents in the local neighborhood of a normal agent is bounded. The proposed algorithm guarantees that all normal agents converge to their true target states if appropriate parameters are selected. We also analyze trade-off between the resilience of distributed diffusion and its performance in terms of steady-state mean-square-deviation (MSD) from the correct estimates. Finally, we evaluate the proposed attack models and resilient distributed diffusion algorithm using stationary and non-stationary multi-target localization. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Weiyu Li;Yaohua Liu;Zhi Tian;Qing Ling;
Pages: 18 - 34 Abstract: In this paper, we propose a communication- and computation-efficient algorithm to solve a convex consensus optimization problem defined over a decentralized network. A remarkable existing algorithm to solve this problem is the alternating direction method of multipliers (ADMM), in which at every iteration every node updates its local variable through combining neighboring variables and solving an optimization subproblem. The proposed algorithm, called as communication-censored linearized ADMM (COLA), leverages a linearization technique to reduce the iteration-wise computation cost of ADMM and uses a communication-censoring strategy to alleviate the communication cost. To be specific, COLA introduces successive linearization approximations to the local cost functions such that the resultant computation is first-order and light-weight. Since the linearization technique slows down the convergence speed, COLA further adopts the communication-censoring strategy to avoid transmissions of less informative messages. A node is allowed to transmit only if the distance between the current local variable and its previously transmitted one is larger than a censoring threshold. COLA is proven to be convergent when the local cost functions have Lipschitz continuous gradients and the censoring threshold is summable. When the local cost functions are further strongly convex, we establish the linear (sublinear) convergence rate of COLA, given that the censoring threshold linearly (sublinearly) decays to 0. Numerical experiments corroborate with the theoretical findings and demonstrate the satisfactory communication-computation tradeoff of COLA. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Shahin Khobahi;Mojtaba Soltanalian;Feng Jiang;A. Lee Swindlehurst;
Pages: 35 - 47 Abstract: A central problem in analog wireless sensor networks is to design the gain or phase-shifts of the sensor nodes (i.e. the relaying configuration) in order to achieve an accurate estimation of some parameter of interest at a fusion center, or more generally, at each node by employing a distributed parameter estimation scheme. In this paper, by using an over-parametrization of the original design problem, we devise a cyclic optimization approach that can handle tuning both gains and phase-shifts of the sensor nodes, even in intricate scenarios involving sensor selection or discrete phase-shifts. Each iteration of the proposed design framework consists of a combination of the Gram-Schmidt process and power method-like iterations, and as a result, enjoys a low computational cost. Along with formulating the design problem for a fusion center, we further present a consensus-based framework for decentralized estimation of deterministic parameters in a distributed network, which results in a similar sensor gain design problem. The numerical results confirm the computational advantage of the suggested approach in comparison with the state-of-the-art methods-an advantage that becomes more pronounced when the sensor network grows large. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Rohan Varma;Harlin Lee;Jelena Kovačević;Yuejie Chi;
Pages: 48 - 62 Abstract: This article studies the denoising of piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness over a graph, where the value at each node can be vector-valued. We extend the graph trend filtering framework to denoising vector-valued graph signals with a family of non-convex regularizers, which exhibit superior recovery performance over existing convex regularizers. Using an oracle inequality, we establish the statistical error rates of first-order stationary points of the proposed non-convex method for generic graphs. Furthermore, we present an ADMM-based algorithm to solve the proposed method and establish its convergence. Numerical experiments are conducted on both synthetic and real-world data for denoising, support recovery, event detection, and semi-supervised classification. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Fei Hua;Roula Nassif;Cédric Richard;Haiyan Wang;Ali H. Sayed;
Pages: 63 - 77 Abstract: In this article, we are interested in adaptive and distributed estimation of graph filters from streaming data. We formulate this problem as a consensus estimation problem over graphs, which can be addressed with diffusion LMS strategies. Most popular graph-shift operators such as those based on the graph Laplacian matrix, or the adjacency matrix, are not energy preserving. This may result in an ill-conditioned estimation problem, and reduce the convergence speed of the distributed algorithms. To address this issue and improve the transient performance, we introduce a preconditioned graph diffusion LMS algorithm. We also propose a computationally efficient version of this algorithm by approximating the Hessian matrix with local information. Performance analyses in the mean and mean-square sense are provided. Finally, we consider a more general problem where the filter coefficients to estimate may vary over the graph. To avoid a large estimation bias, we introduce an unsupervised clustering method for splitting the global estimation problem into local ones. Numerical results show the effectiveness of the proposed algorithms and validate the theoretical results. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Mohammadreza Doostmohammadian;Usman A. Khan;
Pages: 78 - 87 Abstract: In this article, we consider composite networks formed from the Kronecker product of smaller networks. We find the observability and controllability properties of the product network from those of its constituent smaller networks. The overall network is modeled as a Linear-Structure-Invariant (LSI) dynamical system where the underlying matrices have a fixed zero/non-zero structure but the non-zero elements are potentially time-varying. This approach allows to model the system parameters as free variables whose values may only be known within a certain tolerance. We particularly look for minimal sufficient conditions11We emphasize that a minimal sufficient condition is not necessarily a necessary and sufficient condition. In fact, it implies that among all sufficient conditions that may result in an event, this condition is the least conservative but usually is not necessary; see [1] for details. on the observability and controllability of the composite network, which have a direct application in distributed estimation and in the design of networked control systems. The methodology in this article is based on the structured systems analysis and graph theory, and therefore, the results are generic, i.e., they apply to almost all non-zero choices of free parameters. We show the controllability/observability results for composite product networks resulting from full structural-rank systems and self-damped networks. We provide an illustrative example of estimation based on Kalman filtering over a composite network to verify our results. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Saber Jafarizadeh;
Pages: 88 - 104 Abstract: Markov chains are one of the well-known tools for modeling and analyzing stochastic systems. At the same time, they are used for constructing random walks that can achieve a given stationary distribution. This paper is concerned with determining the transition probabilities that optimize the mixing time of the reversible Markov chains towards a given equilibrium distribution. This problem is referred to as the Fastest Mixing Reversible Markov Chain (FMRMC) problem. It is shown that for a given base graph and its clique lifted graph, the FMRMC problem over the clique lifted graph is reducible to the FMRMC problem over the base graph, while the optimal mixing times on both graphs are identical. Based on this result and the solution of the semidefinite programming formulation of the FMRMC problem, the problem has been addressed over a wide variety of topologies with the same base graph. Second, the general form of the FMRMC problem is addressed on stand-alone topologies as well as subgraphs of an arbitrary graph. For subgraphs, it is shown that the optimal transition probabilities over edges of the subgraph can be determined independent of rest of the topology. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Peter Berger;Gabor Hannak;Gerald Matz;
Pages: 105 - 119 Abstract: We consider the problem of learning a graph from a given set of smooth graph signals. Our graph learning approach is formulated as a constrained quadratic program in the edge weights. We provide an implicit characterization of the optimal solution and propose a tailored ADMM algorithm to solve this problem efficiently. Several nearest neighbor and smoothness based graph learning methods are shown to be special cases of our approach. Specifically, our algorithm yields an efficient but extremely accurate approximation to b-matched graphs. We then propose a generalization of our scheme that can deal with noisy and incomplete data via joint graph learning and signal inpainting. We compare the performance of our approach with state-of-the art methods on synthetic data and on real-world data from the Austrian National Council. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Nafiseh Ghoroghchian;David M. Groppe;Roman Genov;Taufik A. Valiante;Stark C. Draper;
Pages: 120 - 132 Abstract: Data-driven graph learning models a network by determining the strength of connections between its nodes. The data refers to a graph signal which associates a value with each graph node. Existing graph learning methods either use simplified models for the graph signal, or they are prohibitively expensive in terms of computational and memory requirements. This is particularly true when the number of nodes is high or there are temporal changes in the network. In order to consider richer models with a reasonable computational tractability, we introduce a graph learning method based on representation learning on graphs. Representation learning generates an embedding for each graph node, taking the information from neighbouring nodes into account. Our graph learning method further modifies the embeddings to compute the graph similarity matrix. In this work, graph learning is used to examine brain networks for brain state identification. We infer time-varying brain graphs from an extensive dataset of intracranial electroencephalographic (iEEG) signals from ten patients. We then apply the graphs as input to a classifier to distinguish seizure vs. non-seizure brain states. Using the binary classification metric of area under the receiver operating characteristic curve (AUC), this approach yields an average of 9.13 percent improvement when compared to two widely used brain network modeling methods. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Mohammadreza Doostmohammadian;
Pages: 133 - 139 Abstract: Observability is a fundamental concept in system inference and estimation. This article is focused on structural observability analysis of Cartesian product networks. Cartesian product networks emerge in variety of applications including in parallel and distributed systems. We provide a structural approach to extend the structural observability of the constituent networks (referred as the factor networks) to that of the Cartesian product network. The structural approach is based on graph theory and is generic. We introduce certain structures which are tightly related to structural observability of networks, namely parent Strongly-Connected-Component (parent SCC), parent node, and contractions. The results show that for particular type of networks (e.g. the networks containing contractions) the structural observability of the factor network can be recovered via Cartesian product. In other words, if one of the factor networks is structurally rank-deficient, using the other factor network containing a spanning cycle family, then the Cartesian product of the two networks is structurally full-rank. We define certain network structures for structural observability recovery. On the other hand, we derive the number of observer nodes-the node whose state is measured by an output- in the Cartesian product network based on the number of observer nodes in the factor networks. An example illustrates the graph-theoretic analysis in the article. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Huaqing Li;Chicheng Huang;Zheng Wang;Guo Chen;Hafiz Gulfam Ahmad Umar;
Pages: 140 - 151 Abstract: A novel computation-efficient quantized distributed optimization algorithm is presented in this article for solving a class of convex optimization problems over time-varying undirected networks with limited communication capacity. These convex optimization problems are usually relevant to the minimization of a sum of local convex objective functions using only local communication and local computation. In most of the existing distributed optimization algorithms, each agent needs to calculate the subgradient of its local convex objective function at each time step, which leads to extremely heavy computation. The proposed algorithm incorporates random sleep scheme into procedures of agents' updates in a probabilistic form to reduce the computation load, and further allows for uncoordinated step-sizes of all agents. The quantized strategy is also applied, which overcomes the limitation of communication capacity. Theoretical analysis indicates that the convex optimization problems can be solved and numerical analysis shows that the computation load of subgradient can be significantly reduced by the proposed algorithm. The boundedness of the quantization levels at each time step has been explicitly characterized. Simulation examples are presented to demonstrate the effectiveness of the algorithm and the correctness of the theoretical results. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Mireille El Gheche;Giovanni Chierchia;Pascal Frossard;
Pages: 152 - 162 Abstract: Network data appears in very diverse applications, like biological, social, or sensor networks. Clustering of network nodes into categories or communities has thus become a very common task in machine learning and data mining. Network data comes with some information about the network edges. In some cases, this network information can even be given with multiple views or layers, each one representing a different type of relationship between the network nodes. Increasingly often, network nodes also carry a feature vector. We propose in this paper to extend the node clustering problem, that commonly considers only the network information, to a problem where both the network information and the node features are considered together for learning a clustering-friendly representation of the feature space. Specifically, we design a generic two-step algorithm for multilayer network data clustering. The first step aggregates the different layers of network information into a graph representation given by the geometric mean of the network Laplacian matrices. The second step uses a neural net to learn a feature embedding that is consistent with the structure given by the network layers. We propose a novel algorithm for efficiently training the neural net via gradient descent, which encourages the neural net outputs to span the leading eigenvectors of the aggregated Laplacian matrix, in order to capture the pairwise interactions on the network, and provide a clustering-friendly representation of the feature space. We demonstrate with an extensive set of experiments on synthetic and real datasets that our method leads to a significant improvement w.r.t. state-of-the-art multilayer graph clustering algorithms, as it judiciously combines nodes features and network information in the node embedding algorithms. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Tongxin Li;Lucien Werner;Steven H. Low;
Pages: 163 - 178 Abstract: We consider a specific graph learning task: reconstructing a symmetric matrix that represents an underlying graph using linear measurements. We present a sparsity characterization for distributions of random graphs (that are allowed to contain high-degree nodes), based on which we study fundamental tradeoffs between the number of measurements, the complexity of the graph class, and the probability of error. We first derive a necessary condition on the number of measurements. Then, by considering a three-stage recovery scheme, we give a sufficient condition for recovery. Furthermore, assuming the measurements are Gaussian IID, we prove upper and lower bounds on the (worst-case) sample complexity for both noisy and noiseless recovery. In the special cases of the uniform distribution on trees with n nodes and the Erdos-Rényi (n, p) class, the fundamental trade-offs are tight up to multiplicative factors with noiseless measurements. In addition, for practical applications, we design and implement a polynomialtime (in n) algorithm based on the three-stage recovery scheme. Experiments show that the heuristic algorithm outperforms basis pursuit on star graphs. We apply the heuristic algorithm to learn admittance matrices in electric grids. Simulations for several canonical graph classes and IEEE power system test cases demonstrate the effectiveness and robustness of the proposed algorithm for parameter reconstruction. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Michele Rossi;Marco Centenaro;Aly Ba;Salma Eleuch;Tomaso Erseghe;Michele Zorzi;
Pages: 179 - 195 Abstract: We consider the problem of joint lossy data compression and data routing in distributed Internet of Things (IoT). Heterogeneous sources compress their data using a source-specific lossy compression scheme, where heterogeneity is meant in terms of signal type and/or transmission rates. The compressed data is thus disseminated in a multi-hop fashion until it reaches a data collector (the IoT gateway). The problem we address is to compute a suitable rate-distortion working point for the compression scheme at the source nodes, while jointly assessing the most energy efficient routing paths for the data they transmit, under channel access, distortion and capacity constraints. This is formulated as a multi-objective optimization problem that is solved through distributed learning algorithms, where source coding and routing configurations emerge as the result of local interactions among the network devices. Our final algorithm is based on the alternating direction method of multipliers (ADMM), which is accelerated using the most recent findings from the literature. As a result, it has faster convergence (up to three times) to the global optimum than standard ADMM. Numerical results are discussed for selected network scenarios, emphasizing the interrelations that exist between signal reconstruction quality at the IoT gateway and total transport energy in the network. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Shengnan Wang;Chunguang Li;Hui-Liang Shen;
Pages: 196 - 210 Abstract: Hashing based approximate nearest neighbor search has attracted considerable attention in various fields. Most of the existing hashing methods are centralized, which cannot be used for many large-scale applications with the data stored or collected in a distributed manner. In this article, we consider the distributed hashing problem. The main difficulty of hashing is brought by its inherent binary constraints, which makes the problem generally NP-hard. Most of the existing distributed hashing methods chose to relax the problem by dropping the binary constraints. However, such a manner will bring additional quantization error, which makes the binary codes less effective. In this paper, we propose a novel distributed discrete hashing method, which learns effective hash codes without using any relaxations. Specifically, we give a method to transform the discrete hashing problem into an equivalent distributed continuous optimization problem. After transformation, we devise a distributed discrete hashing (dDH) algorithm based on the idea of DC programming to solve the problem. To obtain more efficient hash codes, we further add bits balance and uncorrelation constraints to the hashing problem, and we also propose a distributed constrained discrete hashing algorithm (dCDH) to solve this problem. Extensive experiments are provided to show the superiority of the proposed methods. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Mario Coutino;Elvin Isufi;Takanori Maehara;Geert Leus;
Pages: 211 - 225 Abstract: In this article, we explore the state-space formulation of a network process to recover from partial observations the network topology that drives its dynamics. To do so, we employ subspace techniques borrowed from system identification literature and extend them to the network topology identification problem. This approach provides a unified view of network control and signal processing on graphs. In addition, we provide theoretical guarantees for the recovery of the topological structure of a deterministic continuous-time linear dynamical system from input-output observations even when the input and state interaction networks are different. Our mathematical analysis is accompanied by an algorithm for identifying from data,a network topology consistent with the system dynamics and conforms to the prior information about the underlying structure. The proposed algorithm relies on alternating projections and is provably convergent. Numerical results corroborate the theoretical findings and the applicability of the proposed algorithm. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Ali Can Yağan;Mehmet Tankut Özgen;
Pages: 226 - 240 Abstract: In this article, we propose and develop a spectral graph based vertex varying Wiener filtering framework in the joint vertex-frequency domain for denoising of graph signals defined on weighted, undirected and connected graphs. To this end, we first extend the Zadeh time-frequency filter concept to graph signals and obtain vertex-frequency transfer function of the proposed Wiener filter by transforming its vertex varying impulse response that minimizes the mean square error between original and recovered signals. To facilitate the derived Wiener filter, we present a detailed derivation of a recently proposed graph Rihaczek vertex-frequency signal distribution (GRD) so as to match the structure of the proposed graph Zadeh filter, based on a graph translation operator defined by generalized convolution with a delta signal. We express the filter transfer function in terms of this graph transform of the original, noiseless signal. The form of the obtained Wiener filter is, interestingly, different than those of time-frequency Wiener filters prevalent in the classical signal processing. We also investigate the invertibility of the employed GRD. Assuming that the original graph signal of interest can be viewed as deterministic, we propose two algorithms to implement the proposed vertex-frequency Wiener filter from a single realization of a noisy, input signal. We derive mean and variance of the GRD of the noisy signal, since they are required in one of these algorithms. We apply proposed Wiener filter algorithms to denoise a standard set of images and three irregularly structured graph signals, and demonstrate their competitiveness with compared high performance denoising methods. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Fangyu Li;Maria Valero;Yifang Cheng;Tong Bai;WenZhan Song;
Pages: 241 - 250 Abstract: Distributed sensor networks can be used as passive seismic sensors to image and monitor subsurface and underground activities. Passive seismic surface-wave imaging adopts background ambient sounds from a far-field energy source. Because high frequency components decay a lot between the neighboring stations, conventional sparse sensor networks cannot image small-scale and shallow objects. In this article, we propose to use local seismic spatial autocorrelation coefficients, obtained by the combinations of independent dense sensor network measurements and pre-processed readings of its neighbor(s), to perform real-time collaborative imaging of the shallow subsurface objects. First, we derive the high-frequency spectral coefficient based shallow subsurface imaging method. Then, we apply the proposed approach to image a shallowly buried pipeline and obtain promising results. Furthermore, based on a time-lapse manner, the water leakage from the buried pipeline can also be detected using distributed computations between sensors. Comparisons and analysis of field deployments are made to validate the effectiveness and performance of the proposed method. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Thomas Maugey;Aline Roumy;Elsa Dupraz;Michel Kieffer;
Pages: 251 - 260 Abstract: In this paper, we study the problem of source coding with Massive Random Access (MRA). A set of correlated sources is encoded once for all and stored on a server while a large number of clients access various subsets of these sources. Due to the number of concurrent requests, the server is only able to extract a bitstream from the stored data: no re-encoding can be performed before the transmission of the data requested by the clients. First, we formally define the MRA framework and propose to model the constraints on the way subsets of sources may be accessed by a navigation graph. We introduce both storage and transmission costs to characterize the performance of MRA. We then propose an Incremental coding Based Extractable Compression (IBEC) scheme. We first show that this scheme is optimal in terms of achievable storage and transmission costs. Second, we propose a practical implementation of our IBEC scheme based on rate-compatible LDPC codes. Experimental results show that our IBEC scheme can almost reach the same transmission costs as in traditional point-to-point source coding schemes, while having a reasonable overhead in terms of storage cost. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Hermina Petric Maretic;Pascal Frossard;
Pages: 261 - 270 Abstract: Graph learning methods have recently been receiving increasing interest as means to infer structure in datasets. Most of the recent approaches focus on different relationships between a graph and data sample distributions, mostly in settings where all available data relate to the same graph. This is, however, not always the case, as data is often available in mixed form, yielding the need for methods that are able to cope with mixture data and learn multiple graphs. We propose a novel generative model that represents a collection of distinct data which naturally live on different graphs. We assume the mapping of data to graphs is not known and investigate the problem of jointly clustering a set of data and learning a graph for each of the clusters. Experiments demonstrate promising performance in data clustering and multiple graph inference, and show desirable properties in terms of interpretability and coping with high dimensionality on weather and traffic data, as well as digit classification. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Yanning Shen;Xiao Fu;Georgios B. Giannakis;Nicholas D. Sidiropoulos;
Pages: 271 - 283 Abstract: Discovering connectivity patterns of directed networks is a crucial step to understand complex systems such as brain-, social-, and financial networks. Several existing network topology inference approaches rely on structural equation models (SEMs). These presume that exogenous inputs are available, which may be unrealistic in certain applications. Recently, an alternative line of work reformulated SEM-based topology identification as a three-way tensor decomposition task. This way, knowing the exogenous input correlation statistics (rather than the exogenous inputs themselves) suffices for network topology identification. The downside is that this approach is computationally expensive. In addition, it is hard to incorporate prior information of the network structure (e.g., sparsity and local smoothness) into this framework, while such prior information may help enhance performance when handling real-world noisy data. The present work puts forth a joint diagonalizaition (JD)-based approach to directed network topology inference. JD can be viewed as a variant of tensor decomposition, but features more efficient algorithms, and can readily account for the network structure. Different from existing alternatives, novel identifiability guarantees are derived regardless of the exogenous inputs or their statistics. Three JD algorithms tailored for network topology inference are developed, and their performance is showcased using simulated and real data tests. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Saurabh Sihag;Sebastien Naze;Foad Taghdiri;Charles Tator;Richard Wennberg;David Mikulis;Robin Green;Brenda Colella;Maria Carmela Tartaglia;James R. Kozloski;
Pages: 284 - 299 Abstract: The study of structure-function relationships in the brain has been an active area of research in neuroscience. The availability of brain imaging data that captures the structural connectivity and functional co-activation of the brain regions has led to the study of multimodal technical frameworks that can help disentangle the mechanisms linking cognitive abilities and brain structural alterations. This paper analyzes the diffusion and resting state functional magnetic resonance imaging (dMRI and rs-fMRI) data collected from a population consisting of former athletes with a history of multiple concussions and healthy controls with no reported history of concussion. For each subject, the structural connectome is represented by a graph with its nodes associated with cortical brain regions and the adjacency matrix derived from dMRI. Each cortical brain region is associated with a blood oxygen level dependent (BOLD) signal derived from fMRI. This paper uses the tools from graph signal processing (GSP) to select the brain regions of interest (ROIs) that have significant statistical differences in the extracted high and low graph frequency components of the region specific BOLD signal across former athletes and healthy controls, where the graph frequencies represent the extent of spatial variations of the BOLD signal across the brain. The selected ROIs have also been previously identified to be affected in the existing clinical studies on traumatic brain injuries (TBI). Furthermore, the dynamic functional connectivity profiles of the selected ROIs are determined by leveraging the high and low graph frequency components of the BOLD signal and a sliding window based approach. Interestingly, the graph frequency functional connectivity profiles reveal unique characteristics that are not apparent in the unimodal dynamic functional connectivity profiles based on fMRI. Our analysis reveals statistically significant differences in the dwell times in multiple dynamic graph freque-cy functional connectivity states for the two groups of subjects. Therefore, the results presented in this paper underline the significance of graph signal processing tools for multimodal analysis of brain imaging data and also provide promising direction for applications in clinical research and medical diagnosis. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Yu Zhu;Michael T. Schaub;Ali Jadbabaie;Santiago Segarra;
Pages: 300 - 315 Abstract: We explore the problem of inferring the graph Laplacian of a weighted, undirected network from snapshots of a single or multiple discrete-time consensus dynamics, subject to parameter uncertainty, taking place on the network. Specifically, we consider three problems in which we assume different levels of knowledge about the diffusion rates, observation times, and the input signal power of the dynamics. To solve these underdetermined problems, we propose a set of algorithms that leverage the spectral properties of the observed data and tools from convex optimization. Furthermore, we provide theoretical performance guarantees associated with these algorithms. We complement our theoretical work with numerical experiments, that demonstrate how our proposed methods outperform current state-of-the-art algorithms and showcase their effectiveness in recovering both synthetic and real-world networks. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Gaëtan Frusque;Julien Jung;Pierre Borgnat;Paulo Gonçalves;
Pages: 316 - 328 Abstract: Functional connectivity (FC) is a graph-like data structure commonly used by neuroscientists to study the dynamic behaviour of brain activity. However, these analyses rapidly become complex and time-consuming, since the number of connectivity components to be studied is quadratic with the number of electrodes. In this work, we address the problem of clustering FC into relevant ensembles of simultaneously activated components, yielding a multiplex network that reveals characteristic patterns of the epileptic seizures of a given patient. While k-means is certainly the most popular method for data clustering, it is known to perform poorly on large dimensional data sets, and to be highly sensitive to noise. To overcome the so-called curse of dimensionality, we propose a new tensor decomposition to reduce the size of the data set formed by FC time-series recorded for several seizures, prior to apply k-means. We propose an adapted procedure to infer a multiplex network from several FC time series, and we emphasise one particular variant that imposes sparsity constraint. Then, we conduct a real case study, applying the proposed sparse tensor decomposition to iEEG data to infer a multiplex network corresponding to the different stages of an epileptic seizure. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Fasheng Zhou;Ning Wang;Gaoyong Luo;Lisheng Fan;Wei Chen;
Pages: 329 - 341 Abstract: Unmanned-aerial-vehicle (UAV) enabled radio access is an effective technology to improve the wireless coverage, in particular for remote and disaster-struck areas. It will become a key enabler in the forthcoming 5G heterogeneous cellular networks to provide improved and resilient coverage. In this article, we study edge caching for multiple UAV-enabled radio access networks (UAV-RANs) and investigate how the overall spectral efficiency (SE) can be improved by efficient edge caching. In this context, UAV base stations (UBSs) may not serve the immediate close-by users, but serve the users based on the requested contents, which brings the service contents closer to users. Based on analyses of the SE achieved by the content-centric UAV-RAN, a hybrid caching strategy is proposed to further improve the SE. In order to cache more files with limited cache resources while guaranteeing the quality-of-service, the contents are divided into two subsets, a popular set and a less popular set, based on their popularity profile that follows Zipf distribution. The popular files, according to the proposed hybrid caching strategy, are cached at all the UBSs, while each less popular file is cached at one UBS only. The overall SE is maximized by finding an optimal popularity threshold between the two subsets. By relaxing the formulated problem, analytical expression for the optimized threshold is derived. The effectiveness of the proposed method is verified by numerical examples where existing benchmark schemes are compared and outperformed. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Mattia Merluzzi;Paolo Di Lorenzo;Sergio Barbarossa;Valerio Frascolla;
Pages: 342 - 356 Abstract: The goal of this work is to propose an energy-efficient algorithm for dynamic computation offloading, in a multi-access edge computing scenario, where multiple mobile users compete for a common pool of radio and computational resources. We focus on delay-critical applications, incorporating an upper bound on the probability that the overall time required to send the data and process them exceeds a prescribed value. In a dynamic setting, the above constraint translates into preventing the sum of the communication and computation queues' lengths from exceeding a given value. Ultra-reliable low latency communications (URLLC) are also taken into account using finite blocklengths and reliability constraints. The proposed algorithm, based on stochastic optimization, strikes an optimal balance between the service delay and the energy spent at the mobile device, while guaranteeing a target out-of-service probability. Starting from a long-term average optimization problem, our algorithm is based on the solution of a convex problem in each time slot, which is provided with a very fast iterative strategy. Finally, we extend the approach to mobile devices having energy harvesting capabilities, typical of Internet of Things scenarios, thus devising an energy efficient dynamic offloading strategy that stabilizes the battery level of each device around a prescribed operating level. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Yuheng Jia;Hui Liu;Junhui Hou;Sam Kwong;
Pages: 357 - 370 Abstract: Graph-based clustering methods have demonstrated the effectiveness in various applications. Generally, existing graph-based clustering methods first construct a graph to represent the input data and then partition it to generate the clustering result. However, such a stepwise manner may make the constructed graph not fit the requirements for the subsequent decomposition, leading to compromised clustering accuracy. To this end, we propose a joint learning framework, which is able to learn the graph and the clustering result simultaneously, such that the resulting graph is tailored to the clustering task. The proposed method is formulated as a well-defined nonnegative and off-diagonal constrained optimization problem,which is optimized by an alternative iteration method with the convergence of the value of the objective function guaranteed. The advantage of the proposed model is demonstrated by comparing with 19 state-of-the-art clustering methods on 10 datasets with 4 clustering metrics. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Caitlin Gray;Lewis Mitchell;Matthew Roughan;
Pages: 371 - 381 Abstract: Contagion processes are strongly linked to the network structures on which they propagate, and learning these structures is essential for understanding and intervention on complex network processes such as epidemics and (mis)information propagation. However, using contagion data to infer network structure is a challenging inverse problem. In particular, it is imperative to have appropriate measures to quantify uncertainty in network structure estimates; however, these are largely ignored in many optimisation based approaches. We present a probabilistic framework using samples from the distribution of networks that are compatible with the dynamics observed to produce network and uncertainty estimates. We demonstrate the method using the well known independent cascade model to sample from the distribution of networks $P(G)$ conditioned on the observation of a set of infections $C$. We evaluate the accuracy of the method using the marginal probabilities of each edge in the distribution, and show the benefits of quantifying uncertainty to improve estimates and understanding, particularly with small amounts of data. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Apostolos Galanopoulos;Fotis Foukalas;Tamer Khattab;
Pages: 382 - 393 Abstract: In this paper, we consider a heterogeneous network consisting of both macro Base Station (MBS) and pico Base Stations (PBSs) in order to provide a spectrum allocation and mode selection in device-to-device (D2D) communications. A number of Component Carriers (CC) are considered available for allocation to the MBS and PBSs that are being utilized through carrier aggregation (CA) while mode selection decisions are made by each BS in order to balance between power consumption minimization and UE data rate requirements. A power minimization (energy-efficient) problem is formulated in order to provide a joint spectrum allocation and mode selection solution. This problem is solved using a state of the art optimization method known as proximal algorithm. First, a non-cooperative (centralized) solution is provided and second, a cooperative (distributed) employing distributed proximal algorithm is devised reducing the induced complexity. The cooperative solution is achieved by implementing distributed alternating direction method of multipliers (D-ADMM). Simulation results are carried out for all cases that reveal the energy efficient spectrum allocation and mode selection according under certain channels’ conditions that can balance between achieving high data rate requirements and power minimization. Finally, useful insights are presented such as complexity, convergence, delay and actual implementation of such a solution for the future wireless networks. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Eda Bayram;Dorina Thanou;Elif Vural;Pascal Frossard;
Pages: 394 - 406 Abstract: Structure inference is an important task for network data processing and analysis in data science. In recent years, quite a few approaches have been developed to learn the graph structure underlying a set of observations captured in a data space. Although real-world data is often acquired in settings where relationships are influenced by a priori known rules, such domain knowledge is still not well exploited in structure inference problems. In this paper, we identify the structure of signals defined in a data space whose inner relationships are encoded by multi-layer graphs. We aim at properly exploiting the information originating from each layer to infer the global structure underlying the signals. We thus present a novel method for combining the multiple graphs into a global graph using mask matrices, which are estimated through an optimization problem that accommodates the multi-layer graph information and a signal representation model. The proposed mask combination method also estimates the contribution of each graph layer in the structure of signals. The experiments conducted both on synthetic and real-world data suggest that integrating the multi-layer graph representation of the data in the structure inference framework enhances the learning procedure considerably by adapting to the quality and the quantity of the input data. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Navneet Garg;Aditya K. Jagannatham;Govind Sharma;Tharmalingam Ratnarajah;
Pages: 407 - 425 Abstract: This article presents limited feedback-based precoder quantization schemes for Interference Alignment (IA) with bounded channel state information (CSI) uncertainty. Initially, this work generalizes the min-max mean squared error (MSE) framework, followed by the development of robust precoder and decoder designs based on worst case MSE minimization. The proposed precoder and decoder designs capture the effect of CSI uncertainty using a single parameter, which is independent of the CSI uncertainty in the direct links. The IA algorithms derived employing these proposed designs are shown to be globally convergent under certain conditions. Moreover, precoder quantization schemes are presented for scenarios with and without CSI uncertainty for practical implementation of these techniques in systems with limited feedback. An optimal bit allocation scheme is presented to maximize the sum rate via analysis of the rate loss upper bound. Simulation results demonstrate the improved performance of the proposed IA schemes for various scenarios considering imperfect CSI as well as limited feedback. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Vini Gupta;Swades De;
Pages: 426 - 441 Abstract: This article presents an adaptive multi-sensing (MS) framework for a network of densely deployed solar energy harvesting wireless nodes. Each node is mounted with heterogeneous sensors to sense multiple cross-correlated slowly-varying parameters/signals. Inherent spatio-temporal correlations of the observed parameters are exploited to adaptively activate a subset of sensors of a few nodes and turn-OFF the remaining ones. To do so, a multi-objective optimization problem that jointly optimizes sensing quality and network energy efficiency is solved for each monitoring parameter. To increase energy efficiency, network and node-level collaborations based multi-sensing strategies are proposed. The former one utilizes spatial proximity (SP) of nodes with active sensors (obtained from the MS) to further reduce the active sensors sets, while the latter one exploits cross-correlation (CC) among the observed parameters at each node to do so. A retraining logic is developed to prevent deterioration of sensing quality in MS-SP. For jointly estimating all the parameters across the field nodes using under-sampled measurements obtained from MS-CC based active sensors, a multi-sensor data fusion technique is presented. For this ill-posed estimation scenario, double sparsity due to spatial and cross-correlation among measurements is used to derive principal component analysis-based Kronecker sparsifying basis, and sparse Bayesian learning framework is then used for joint sparse estimation. Extensive simulation studies using synthetic (real) data illustrate that, the proposed MS-SP and MS-CC strategies are respectively $48.2 (52.09)%$ and $50.30 (8.13)%$ more energy-efficient compared to respective state-of-the-art techniques while offering stable sensing quality. Further, heat-maps of estimated field signals corresponding to synthetically-generated and parsimoniously sensed multi-source parameters are also provided which may aid in source localization Internet-of-Things applications. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Mojtaba Shirazi;Azadeh Vosoughi;
Pages: 442 - 459 Abstract: We consider distributed estimation of a random source in a hierarchical power constrained wireless sensor network. Sensors within each cluster send their measurements to a cluster head (CH). CHs optimally fuse the received signals and transmit to the fusion center (FC) over orthogonal fading channels. To enable channel estimation at the FC, CHs send pilots, prior to data transmission. We derive the mean square error (MSE) corresponding to the linear minimum mean square error (LMMSE) estimator of the source at the FC, and obtain the Bayesian Cramér-Rao bound (CRB). Our goal is to find (i) the optimal training power, (ii) the optimal power that sensors in a cluster spend to transmit their amplified measurements to their CH, and (iii) the optimal weight vector employed by each CH for its linear signal fusion, such that the MSE is minimized, subject to a network power constraint. To untangle the performance gain that optimizing each set of these variables provide, we also analyze three special cases of the original problem, where in each special case, only two sets of variables are optimized across clusters. We define three factors that allow us to quantify the effectiveness of each power allocation scheme in achieving an MSE-power tradeoff that is close to that of the Bayesian CRB. Combining the information gained from the factors and Bayesian CRB with our computational complexity analysis provides the system designer with quantitative complexity-versus-MSE improvement tradeoffs offered by different power allocation schemes. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Razgar Rahimi;Shahram ShahbazPanahi;Björn Ottersten;
Pages: 460 - 478 Abstract: Considered in this article is an asynchronous single-carrier two-way relay network, where two transceivers aim to communicate through a set of amplify-and-forward (AF) relays. This network is asynchronous in the sense that the signal transmitted by any of the two transceivers arrives the other transceiver through different relaying paths, with possibly different propagation delays, thereby materializing a multipath channel. At sufficiently high data rates, this multi-path end-to-end channel causes inter-symbol-interference (ISI) in the received signals. Considering such a network, this paper presents two contributions. The first contribution is the rigorous characterization of the region of the mean-squared errors (MSEs) of the symbol estimates at the two transceivers under a total power budget, and when linear block post-channel equalization is used at the receiver front-end of the two transceivers. The importance of this MSE region characterization resides in the fact that knowing this region allows for characterization the region of un-coded probabilities of error at the two transceivers. Also, this MSE region characterization paves the way towards presenting the second contribution in this paper. Indeed, in the second contribution, this article relies on this MSE region characterization to rigorously prove that an MSE-constrained total power minimization approach and a rate-constrained total power minimization approach to design transceiver power allocation and distributed beamforming are equivalent, if the MSE thresholds in the former approach and the rate thresholds in the latter approach are properly chosen. The equivalence of these two approaches implies that the un-coded MSE performance of the network can be inferred from the rate-constrained problem, and conversely, the coded rate performance of the network can be inferred from the MSE-constrained total power minimization problem. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Gianni Pasolini;Davide Dardari;Michel Kieffer;
Pages: 479 - 490 Abstract: This article proposes two average consensus algorithms exploiting the memory of agents. The performance of the proposed as well as of several state-of-the-art consensus algorithms is evaluated considering different communication ranges, and evaluating the impact of transmission errors. To compare asymptotic and finite-time average consensus schemes, the $varepsilon$-convergence time is adopted for a fair comparison. A discussion about memory requirements, transmission overhead, a priori information on network topology, and robustness to errors is provided. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Florian Meyer;Moe Z. Win;
Pages: 491 - 507 Abstract: Tracking extended objects based on measurements provided by light detection and ranging (LIDAR) and millimeter wave radio detection and ranging (RADAR) sensors is a key task to obtain situational awareness in important applications including autonomous driving and indoor robotics. In this paper, we propose probabilistic data association methods for localizing and tracking of extended objects that originate an unknown number of measurements. Our approach is based on factor graphs and the sum-product algorithm (SPA). In particular, we reduce computational complexity in a principled manner by means of “stretching” factors in the graph. After stretching, new variable and factor nodes have lower dimensions than the original nodes. This leads to a reduced computational complexity of the resulting SPA. One of the introduced methods is based on an overcomplete description of data association uncertainty and has a computational complexity that only scales quadratically in the number of objects and linearly in the number of measurements. Without relying on suboptimal preprocessing steps such as a clustering of measurements, it can localize and track multiple objects that potentially generate a large number of measurements. Simulation results confirm that despite their lower computational complexity, the proposed methods can outperform reference methods based on clustering. PubDate:
2020
Issue No:Vol. 6 (2020)
Authors:
Başak Güler;A. Salman Avestimehr;Antonio Ortega;
Pages: 508 - 525 Abstract: This article proposes a coded distributed graph processing framework to alleviate the communication bottleneck in large-scale distributed graph processing. In particular, we propose a topology-aware coded computing (TACC) algorithm that has two novel salient features: (i) a topology-aware graph allocation strategy, and (ii) a coded aggregation scheme that combines the intermediate computations for graph processing while constructing coded messages. The proposed setup results in a trade-off between computation and communication, in that increasing the computation load at the distributed parties can in turn reduce the communication load. We demonstrate the effectiveness of the TACC algorithm by comparing the communication load with existing setups on both Erdös-Rényi and Barabási-Albert type random graphs, as well as real-world Google web graph for PageRank computations. In particular, we show that the proposed coding strategy can lead to up to $82%$ reduction in communication load and up to $46%$ reduction in overall execution time, when compared to the state-of-the-art and implemented on the Amazon EC2 cloud compute platform. PubDate:
2020
Issue No:Vol. 6 (2020)
Hybrid journal (It can contain Open Access articles)
