More Like this

1. Robustness of Interdependent Random Geometric Networks

   https://doi.org/10.1109/TNSE.2018.2846720  

   Zhang, Jianan; Yeh, Edmund; Modiano, Eytan (June 2018, IEEE Transactions on Network Science and Engineering)

   We propose an interdependent random geometric graph (RGG) model for interdependent networks. Based on this model, we study the robustness of two interdependent spatially embedded networks where interdependence exists between geographically nearby nodes in the two networks. We study the emergence of the giant mutual component in two interdependent RGGs as node densities increase, and define the percolation threshold as a pair of node densities above which the giant mutual component first appears. In contrast to the case for a single RGG, where the percolation threshold is a unique scalar for a given connection distance, for two interdependent RGGs, multiple pairs of percolation thresholds may exist, given that a smaller node density in one RGG may increase the minimum node density in the other RGG in order for a giant mutual component to exist. We derive analytical upper bounds on the percolation thresholds of two interdependent RGGs by discretization, and obtain 99% confidence intervals for the percolation thresholds by simulation. Based on these results, we derive conditions for the interdependent RGGs to be robust under random failures and geographical attacks. 

   more » « less
2. On Graphical Modeling of High-Dimensional Long-Range Dependent Time Series

   https://doi.org/10.1109/IEEECONF56349.2022.10052091  

   Tugnait, Jitendra K. (October 2022, 2022 56th Asilomar Conference on Signals, Systems, and Computers)

   We consider the problem of inferring the conditional independence graph (CIG) of a high-dimensional stationary, multivariate long-range dependent (LRD) Gaussian time series. In a time series graph, each component of the vector series is represented by a distinct node, and associations between components are represented by edges between the corresponding nodes. In a recent work on graphical modeling of short-range dependent (SRD) Gaussian time series, the problem was cast as one of multi-attribute graph estimation for random vectors where a vector is associated with each node of the graph. At each node, the associated random vector consists of a time series component and its delayed copies. A theoretical analysis based on short-range dependence has been given in Tugnait (2022 ICASSP). In this paper we analyze this approach for LRD Gaussian time series and provide consistency results regarding convergence in the Frobenius norm of the inverse covariance matrix associated with the multi-attribute graph. 

   more » « less
3. Graph Learning From Multivariate Dependent Time Series Via A Multi-Attribute Formulation

   https://doi.org/10.1109/ICASSP43922.2022.9746603  

   Tugnait, Jitendra K. (May 2022, ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   We consider the problem of inferring the conditional independence graph (CIG) of a high-dimensional stationary multivariate Gaussian time series. In a time series graph, each component of the vector series is represented by distinct node, and associations between components are represented by edges between the corresponding nodes. We formulate the problem as one of multi-attribute graph estimation for random vectors where a vector is associated with each node of the graph. At each node, the associated random vector consists of a time series component and its delayed copies. We present an alternating direction method of multipliers (ADMM) solution to minimize a sparse-group lasso penalized negative pseudo log-likelihood objective function to estimate the precision matrix of the random vector associated with the entire multi-attribute graph. The time series CIG is then inferred from the estimated precision matrix. A theoretical analysis is provided. Numerical results illustrate the proposed approach which outperforms existing frequency-domain approaches in correctly detecting the graph edges. 

   more » « less
4. Sparse-Group Non-convex Penalized Multi-Attribute Graphical Model Selection

   https://doi.org/10.23919/EUSIPCO54536.2021.9616255  

   Tugnait, Jitendra K. (August 2021, 2021 29th European Signal Processing Conference (EUSIPCO))

   We consider the problem of inferring the conditional independence graph (CIG) of high-dimensional Gaussian vectors from multi-attribute data. Most existing methods for graph estimation are based on single-attribute models where one associates a scalar random variable with each node. In multi-attribute graphical models, each node represents a random vector. In this paper we consider a sparse-group smoothly clipped absolute deviation (SG-SCAD) penalty instead of sparse-group lasso (SGL) penalty to regularize the problem. We analyze an SG-SCAD-penalized log-likelihood based objective function to establish consistency of a local estimator of inverse covariance. A numerical example is presented to illustrate the advantage of SG-SCAD-penalty over the usual SGL-penalty. 

   more » « less
5. OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs

   Zhou, Yangze; Kutyniok, Gitta; Ribeiro, Bruno (December 2022, Advances in neural information processing systems)

   This work provides the first theoretical study on the ability of graph Message Passing Neural Networks (gMPNNs) -- such as Graph Neural Networks (GNNs) -- to perform inductive out-of-distribution (OOD) link prediction tasks, where deployment (test) graph sizes are larger than training graphs. We first prove non-asymptotic bounds showing that link predictors based on permutation-equivariant (structural) node embeddings obtained by gMPNNs can converge to a random guess as test graphs get larger. We then propose a theoretically-sound gMPNN that outputs structural pairwise (2-node) embeddings and prove non-asymptotic bounds showing that, as test graphs grow, these embeddings converge to embeddings of a continuous function that retains its ability to predict links OOD. Empirical results on random graphs show agreement with our theoretical results. 

   more » « less