skip to main content


The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Friday, April 12 until 2:00 AM ET on Saturday, April 13 due to maintenance. We apologize for the inconvenience.

Title: On the Role of Interconnection Directionality in the Quadratic Performance of Double-Integrator Networks
This paper provides a framework to evaluate the performance of single and double integrator networks over arbitrary directed graphs. Adopting vehicular network terminology, we consider quadratic performance metrics defined by the L2-norm of position and velocity based response functions given impulsive inputs to each vehicle. We exploit the spectral properties of weighted graph Laplacians and output performance matrices to derive a novel method of computing the closed-form solutions for this general class of performance metrics, which include H2-norm based quantities as special cases. We then explore the effect of the interplay between network properties (such as edge directionality and connectivity) and the control strategy on the overall network performance. More precisely, for systems whose interconnection is described by graphs with normal Laplacian L, we characterize the role of directionality by comparing their performance with that of their undirected counterparts, represented by the Hermitian part of L. We show that, for single-integrator networks, directed and undirected graphs perform identically. However, for double-integrator networks, graph directionality -expressed by the eigenvalues of L with nonzero imaginary part- can significantly degrade performance. Interestingly, in many cases, well-designed feedback can also exploit directionality to mitigate degradation or even improve the performance to exceed that of the undirected case. Finally we focus on a system coherence metric -aggregate deviation from the state average- to investigate the relationship between performance and degree of connectivity, leading to somewhat surprising findings. For example, increasing the number of neighbors on a ω-nearest neighbor directed graph does not necessarily improve performance. Similarly, we demonstrate equivalence in performance between all-to-one and all-to-all communication graphs.  more » « less
Award ID(s):
1752362 1736448 2136324 1711188
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
IEEE Transactions on Automatic Control
Page Range / eLocation ID:
1 to 1
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We consider Byzantine consensus in a synchronous system where nodes are connected by a network modeled as a directed graph, i.e., communication links between neighboring nodes are not necessarily bi-directional. The directed graph model is motivated by wireless networks wherein asymmetric communication links can occur. In the classical point-to-point communication model, a message sent on a communication link is private between the two nodes on the link. This allows a Byzantine faulty node to equivocate, i.e., send inconsistent information to its neighbors. This paper considers the local broadcast model of communication, wherein transmission by a node is received identically by all of its outgoing neighbors, effectively depriving the faulty nodes of the ability to equivocate. Prior work has obtained sufficient and necessary conditions on undirected graphs to be able to achieve Byzantine consensus under the local broadcast model. In this paper, we obtain tight conditions on directed graphs to be able to achieve Byzantine consensus with binary inputs under the local broadcast model. The results obtained in the paper provide insights into the trade-off between directionality of communication links and the ability to achieve consensus. 
    more » « less
  2. Ranzato, M. ; Beygelzimer, A. ; Dauphin, Y. ; Liang, P.S. ; Vaughan, J. Wortman (Ed.)
    The prevalence of graph-based data has spurred the rapid development of graph neural networks (GNNs) and related machine learning algorithms. Yet, despite the many datasets naturally modeled as directed graphs, including citation, website, and traffic networks, the vast majority of this research focuses on undirected graphs. In this paper, we propose MagNet, a GNN for directed graphs based on a complex Hermitian matrix known as the magnetic Laplacian. This matrix encodes undirected geometric structure in the magnitude of its entries and directional information in their phase. A charge parameter attunes spectral information to variation among directed cycles. We apply our network to a variety of directed graph node classification and link prediction tasks showing that MagNet performs well on all tasks and that its performance exceeds all other methods on a majority of such tasks. The underlying principles of MagNet are such that it can be adapted to other GNN architectures. 
    more » « less
  3. This paper describes a group-level classification of 14 patients with prefrontal cortex (pFC) lesions from 20 healthy controls using multi-layer graph convolutional networks (GCN) with features inferred from the scalp EEG recorded from the encoding phase of working memory (WM) trials. We first construct undirected and directed graphs to represent the WM encoding for each trial for each subject using distance correlation- based functional connectivity measures and differential directed information-based effective connectivity measures, respectively. Centrality measures of betweenness centrality, eigenvector centrality, and closeness centrality are inferred for each of the 64 channels from the brain connectivity. Along with the three centrality measures, each graph uses the relative band powers in the five frequency bands - delta, theta, alpha, beta, and gamma- as node features. The summarized graph representation is learned using two layers of GCN followed by mean pooling, and fully connected layers are used for classification. The final class label for a subject is decided using majority voting based on the results from all the subject's trials. The GCN-based model can correctly classify 28 of the 34 subjects (82.35% accuracy) with undirected edges represented by functional connectivity measure of distance correlation and classify all 34 subjects (100% accuracy) with directed edges characterized by effective connectivity measure of differential directed information. 
    more » « less
  4. De Vico Fallani, Fabrizio (Ed.)
    The exponential family random graph modeling (ERGM) framework provides a highly flexible approach for the statistical analysis of networks (i.e., graphs). As ERGMs with dyadic dependence involve normalizing factors that are extremely costly to compute, practical strategies for ERGMs inference generally employ a variety of approximations or other workarounds. Markov Chain Monte Carlo maximum likelihood (MCMC MLE) provides a powerful tool to approximate the maximum likelihood estimator (MLE) of ERGM parameters, and is generally feasible for typical models on single networks with as many as a few thousand nodes. MCMC-based algorithms for Bayesian analysis are more expensive, and high-quality answers are challenging to obtain on large graphs. For both strategies, extension to the pooled case—in which we observe multiple networks from a common generative process—adds further computational cost, with both time and memory scaling linearly in the number of graphs. This becomes prohibitive for large networks, or cases in which large numbers of graph observations are available. Here, we exploit some basic properties of the discrete exponential families to develop an approach for ERGM inference in the pooled case that (where applicable) allows an arbitrarily large number of graph observations to be fit at no additional computational cost beyond preprocessing the data itself. Moreover, a variant of our approach can also be used to perform Bayesian inference under conjugate priors, again with no additional computational cost in the estimation phase. The latter can be employed either for single graph observations, or for observations from graph sets. As we show, the conjugate prior is easily specified, and is well-suited to applications such as regularization. Simulation studies show that the pooled method leads to estimates with good frequentist properties, and posterior estimates under the conjugate prior are well-behaved. We demonstrate the usefulness of our approach with applications to pooled analysis of brain functional connectivity networks and to replicated x-ray crystal structures of hen egg-white lysozyme. 
    more » « less
  5. Consensus algorithms constitute a powerful tool for computing average values or coordinating agents in many distributed applications. Unfortunately, the same property that allows this computation (i.e., the nontrivial nullspace of the state matrix) leads to unbounded state variance in the presence of measurement errors. In this work, we explore the trade-off between relative and absolute communication (feedback) in the presence of measurement errors. We evaluate the robustness of first and second-order integrator systems under a parameterized family of controllers (homotopy), that continuously trade between relative and absolute feedback interconnections, in terms of the H 2 norm of an appropriately defined input-output system. Our approach extends the previous H 2 norm-based analysis to systems with directed feedback interconnections whose underlying weighted graph Laplacians are diagonalizable. Our results indicate that any level of absolute communication is sufficient to achieve a finite H 2 norm, but purely relative feedback can only achieve finite norms when the measurement error is not exciting the subspace associated with the consensus state. Numerical examples demonstrate that smoothly reducing the proportion of absolute feedback in double integrator systems smoothly decreases the system performance (increases the H 2 norm) and that this performance degradation is more rapid in systems with relative feedback in only the first state (position). 
    more » « less