 NSFPAR ID:
 10435114
 Date Published:
 Journal Name:
 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Many networked systems such as electric networks, the brain, and social networks of opinion dynamics are known to obey conservation laws. Examples of this phenomenon include the Kirchoff laws in electric networks and opinion consensus in social networks. Conservation laws in networked systems are modeled as balance equations of the form X=B*Y, where the sparsity pattern of B*∈R^{p×p} captures the connectivity of the network on p nodes, and Y, X ∈ R^p are vectors of ''potentials'' and ''injected flows'' at the nodes respectively. The node potentials Y cause flows across edges which aim to balance out the potential difference, and the flows X injected at the nodes are extraneous to the network dynamics. In several practical systems, the network structure is often unknown and needs to be estimated from data to facilitate modeling, management, and control. To this end, one has access to samples of the node potentials Y, but only the statistics of the node injections X. Motivated by this important problem, we study the estimation of the sparsity structure of the matrix B* from n samples of Y under the assumption that the node injections X follow a Gaussian distribution with a known covariance Σ_X. We propose a new ℓ1regularized maximum likelihood estimator for tackling this problem in the highdimensional regime where the size of the network may be vastly larger than the number of samples n. We show that this optimization problem is convex in the objective and admits a unique solution. Under a new mutual incoherence condition, we establish sufficient conditions on the triple (n,p,d) for which exact sparsity recovery of B* is possible with high probability; d is the degree of the underlying graph. We also establish guarantees for the recovery of B* in the elementwise maximum, Frobenius, and operator norms. Finally, we complement these theoretical results with experimental validation of the performance of the proposed estimator on synthetic and realworld data.more » « less

null (Ed.)Synopsis Many biological systems across scales of size and complexity exhibit a timevarying complex network structure that emerges and selforganizes as a result of interactions with the environment. Network interactions optimize some intrinsic cost functions that are unknown and involve for example energy efficiency, robustness, resilience, and frailty. A wide range of networks exist in biology, from gene regulatory networks important for organismal development, protein interaction networks that govern physiology and metabolism, and neural networks that store and convey information to networks of microbes that form microbiomes within hosts, animal contact networks that underlie social systems, and networks of populations on the landscape connected by migration. Increasing availability of extensive (big) data is amplifying our ability to quantify biological networks. Similarly, theoretical methods that describe network structure and dynamics are being developed. Beyond static networks representing snapshots of biological systems, collections of longitudinal data series can help either at defining and characterizing network dynamics over time or analyzing the dynamics constrained to networked architectures. Moreover, due to interactions with the environment and other biological systems, a biological network may not be fully observable. Also, subnetworks may emerge and disappear as a result of the need for the biological system to cope with for example invaders or new information flows. The confluence of these developments renders tractable the question of how the structure of biological networks predicts and controls network dynamics. In particular, there may be structural features that result in homeostatic networks with specific higherorder statistics (e.g., multifractal spectrum), which maintain stability over time through robustness and/or resilience to perturbation. Alternative, plastic networks may respond to perturbation by (adaptive to catastrophic) shifts in structure. Here, we explore the opportunity for discovering universal laws connecting the structure of biological networks with their function, positioning them on the spectrum of timeevolving network structure, i.e. dynamics of networks, from highly stable to exquisitely sensitive to perturbation. If such general laws exist, they could transform our ability to predict the response of biological systems to perturbations—an increasingly urgent priority in the face of anthropogenic changes to the environment that affect life across the gamut of organizational scales.more » « less

Many biological systems across scales of size and complexity exhibit a timevarying complex network structure that emerges and selforganizes as a result of interactions with the environment. Network interactions optimize some intrinsic cost functions that are unknown and involve for example energy efficiency, robustness, resilience, and frailty. A wide range of networks exist in biology, from gene regulatory networks important for organismal development, protein interaction networks that govern physiology and metabolism, and neural networks that store and convey information to networks of microbes that form microbiomes within hosts, animal contact networks that underlie social systems, and networks of populations on the landscape connected by migration. Increasing availability of extensive (big) data is amplifying our ability to quantify biological networks. Similarly, theoretical methods that describe network structure and dynamics are being developed. Beyond static networks representing snapshots of biological systems, collections of longitudinal data series can help either at defining and characterizing network dynamics over time or analyzing the dynamics constrained to networked architectures. Moreover, due to interactions with the environment and other biological systems, a biological network may not be fully observable. Also, subnetworks may emerge and disappear as a result of the need for the biological system to cope with for example invaders or new information flows. The confluence of these developments renders tractable the question of how the structure of biological networks predicts and controls network dynamics. In particular, there may be structural features that result in homeostatic networks with specific higherorder statistics (e.g., multifractal spectrum), which maintain stability over time through robustness and/or resilience to perturbation. Alternative, plastic networks may respond to perturbation by (adaptive to catastrophic) shifts in structure. Here, we explore the opportunity for discovering universal laws connecting the structure of biological networks with their function, positioning them on the spectrum of timeevolving network structure, that is, dynamics of networks, from highly stable to exquisitely sensitive to perturbation. If such general laws exist, they could transform our ability to predict the response of biological systems to perturbations—an increasingly urgent priority in the face of anthropogenic changes to the environment that affect life across the gamut of organizational scales.more » « less

Many papers have addressed the problem of learning the behavior (i.e., the local interaction function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the network topology and the behavior of such a system through active queries. Our results are for systems where the state of each node is from {0, 1} and the local functions are Boolean. We present inference algorithms under both batch and adaptive query models for dynamical systems with symmetric local functions. These algorithms show that the structure and behavior of such dynamical systems can be learnt using only a polynomial number of queries. Further, we establish a lower bound on the number of queries needed to learn such dynamical systems. We also present experimental results obtained by running our algorithms on synthetic and realworld networks.more » « less

Abstract Statistical relational learning (SRL) and graph neural networks (GNNs) are two powerful approaches for learning and inference over graphs. Typically, they are evaluated in terms of simple metrics such as accuracy over individual node labels. Complex
aggregate graph queries (AGQ) involving multiple nodes, edges, and labels are common in the graph mining community and are used to estimate important network properties such as social cohesion and influence. While graph mining algorithms support AGQs, they typically do not take into account uncertainty, or when they do, make simplifying assumptions and do not build full probabilistic models. In this paper, we examine the performance of SRL and GNNs on AGQs over graphs with partially observed node labels. We show that, not surprisingly, inferring the unobserved node labels as a first step and then evaluating the queries on the fully observed graph can lead to suboptimal estimates, and that a better approach is to compute these queries as an expectation under the joint distribution. We propose a sampling framework to tractably compute the expected values of AGQs. Motivated by the analysis of subgroup cohesion in social networks, we propose a suite of AGQs that estimate the community structure in graphs. In our empirical evaluation, we show that by estimating these queries as an expectation, SRLbased approaches yield up to a 50fold reduction in average error when compared to existing GNNbased approaches.