Julien M. Hendrickx

Julien M. Hendrickx, John N. Tsitsiklis

We consider continuous-time consensus seeking systems whose time-dependent interactions are cut-balanced, in the following sense: if a group of agents influences the remaining ones, the former group is also influenced by the remaining ones by at least a proportional amount. Models involving symmetric interconnections and models in which a weighted average of the agent values is conserved are special cases. We prove that such systems always converge. We give a sufficient condition on the evolving interaction topology for the limit values of two agents to be the same. Conversely, we show that if our condition is not satisfied, then these limits are generically different. These results allow treating systems where the agent interactions are a priori unknown, e.g., random or determined endogenously by the agent values. We also derive corresponding results for discrete-time systems.

Julien M. Hendrickx, Karl Henrik Johansson, Raphael M. Jungers et al.

The resilience of Supervisory Control and Data Acquisition (SCADA) systems for electric power networks for certain cyber-attacks is considered. We analyze the vulnerability of the measurement system to false data attack on communicated measurements. The vulnerability analysis problem is shown to be NP-hard, meaning that unless $P = NP$ there is no polynomial time algorithm to analyze the vulnerability of the system. Nevertheless, we identify situations, such as the full measurement case, where it can be solved efficiently. In such cases, we show indeed that the problem can be cast as a generalization of the minimum cut problem involving costly nodes. We further show that it can be reformulated as a standard minimum cut problem (without costly nodes) on a modified graph of proportional size. An important consequence of this result is that our approach provides the first exact efficient algorithm for the vulnerability analysis problem under the full measurement assumption. Furthermore, our approach also provides an efficient heuristic algorithm for the general NP-hard problem. Our results are illustrated by numerical studies on benchmark systems including the IEEE 118-bus system.

Julien M. Hendrickx, Guodong Shi, Karl H. Johansson

We discuss the possibility of reaching consensus in finite time using only linear iterations, with the additional restrictions that the update matrices must be stochastic with positive diagonals and consistent with a given graph structure. We show that finite-time average consensus can always be achieved for connected undirected graphs. For directed graphs, we show some necessary conditions for finite-time consensus, including strong connectivity and the presence of a simple cycle of even length.

Julien M. Hendrickx, Alex Olshevsky, John N. Tsitsiklis

We propose a model for deterministic distributed function computation by a network of identical and anonymous nodes. In this model, each node has bounded computation and storage capabilities that do not grow with the network size. Furthermore, each node only knows its neighbors, not the entire graph. Our goal is to characterize the class of functions that can be computed within this model. In our main result, we provide a necessary condition for computability which we show to be nearly sufficient, in the sense that every function that satisfies this condition can at least be approximated. The problem of computing suitably rounded averages in a distributed manner plays a central role in our development; we provide an algorithm that solves it in time that grows quadratically with the size of the network.

Julien M. Hendrickx, Michel Gevers, Alexandre S. Bazanella

Much recent research has dealt with the identifiability of a dynamical network in which the node signals are connected by causal linear transfer functions and are excited by known external excitation signals and/or unknown noise signals. A major research question concerns the identifiability of the whole network - topology and all transfer functions - from the measured node signals and external excitation signals. So far all results on this topic have assumed that all node signals are measured. This paper presents the first results for the situation where not all node signals are measurable, under the assumptions that (1) the topology of the network is known, and (2) each node is excited by a known external excitation. Using graph theoretical properties, we show that the transfer functions that can be identified depend essentially on the topology of the paths linking the corresponding vertices to the measured nodes. A practical outcome is that, under those assumptions, a network can often be identified using only a small subset of node measurements.

Tao Liu, Ming Cao, Claudio De Persis et al.

This paper studies synchronization of dynamical networks with event-based communication. Firstly, two estimators are introduced into each node, one to estimate its own state, and the other to estimate the average state of its neighbours. Then, with these two estimators, a distributed event-triggering rule (ETR) with a dwell time is designed such that the network achieves synchronization asymptotically with no Zeno behaviours. The designed ETR only depends on the information that each node can obtain, and thus can be implemented in a decentralized way.

A. Mauroy, J. Hendrickx

We propose a new method to recover global information about a network of interconnected dynamical systems based on observations made at a small number (possibly one) of its nodes. In contrast to classical identification of full graph topology, we focus on the identification of the spectral graph-theoretic properties of the network, a framework that we call spectral network identification. The main theoretical results connect the spectral properties of the network to the spectral properties of the dynamics, which are well-defined in the context of the so-called Koopman operator and can be extracted from data through the Dynamic Mode Decomposition algorithm. These results are obtained for networks of diffusively-coupled units that admit a stable equilibrium state. For large networks, a statistical approach is considered, which focuses on spectral moments of the network and is well-suited to the case of heterogeneous populations. Our framework provides efficient numerical methods to infer global information on the network from sparse local measurements at a few nodes. Numerical simulations show for instance the possibility of detecting the mean number of connections or the addition of a new vertex using measurements made at one single node, that need not be representative of the other nodes' properties.

Paolo Frasca, Julien M. Hendrickx

This paper regards randomized discrete-time consensus systems that preserve the average "on average". As a main result, we provide an upper bound on the mean square deviation of the consensus value from the initial average. Then, we apply our result to systems where few or weakly correlated interactions take place: these assumptions cover several algorithms proposed in the literature. For such systems we show that, when the network size grows, the deviation tends to zero, and the speed of this decay is not slower than the inverse of the size. Our results are based on a new approach, which is unrelated to the convergence properties of the system.

Alexandre Mauroy, Julien Hendrickx

We consider a network of interconnected dynamical systems. Spectral network identification consists in recovering the eigenvalues of the network Laplacian from the measurements of a very limited number (possibly one) of signals. These eigenvalues allow to deduce some global properties of the network, such as bounds on the node degree. Having recently introduced this approach for autonomous networks of nonlinear systems, we extend it here to treat networked systems with external inputs on the nodes, in the case of linear dynamics. This is more natural in several applications, and removes the need to sometimes use several independent trajectories. We illustrate our framework with several examples, where we estimate the mean, minimum, and maximum node degree in the network. Inferring some information on the leading Laplacian eigenvectors, we also use our framework in the context of network clustering.

Yushan Li, Jiabao He, Julien M. Hendrickx et al.

This paper develops a feedback-based method to preserve the topology privacy of consensus protocols in network systems. The key idea is to intentionally violate topology identifiability conditions, thereby preventing unique or accurate recovery of the true topology from available observations, while preserving the intended consensus behavior. This problem is challenging because the feedback magnitude directly reflects the privacy level of edges, while it is strongly coupled with the consensus convergence and constrained by local communications at each node. To begin with, we derive the feedback conditions of both partial and full observation cases, where the topology unsolvability from observation data is characterized in the former, and the solution space that enforces topology inaccuracy from data is constructed in the latter. Then, we propose a novel distributed topology modification design under limited privacy budgets, and establish the performance guarantees through a controllable tradeoff between the consensus deviation and the topology privacy. Finally, we develop a low-complexity heuristic algorithm to achieve optimal privacy preservation on existing edges. Comparative simulations validate the effectiveness and outperformance of the proposed preservation design.

Christopher Lindberg, Julien M. Hendrickx, Henk Wymeersch

Belief propagation (BP) is a powerful tool to solve distributed inference problems, though it is limited by short cycles in the corresponding factor graph. Such cycles may lead to incorrect solutions or oscillatory behavior. Only for certain types of problems are convergence properties understood. We extend this knowledge by investigating the use of reweighted BP for distributed likelihood fusion problems, which are characterized by equality constraints along possibly short cycles. Through a linear formulation of BP, we are able to analytically derive convergence conditions for certain types of graphs and optimize the convergence speed. We compare with standard belief consensus and observe significantly faster convergence.

Chen Song, Angela Fontan, Rong Su et al.

This paper presents a theoretical convergence analysis for an opinion-action coevolution model that integrates the opinion updating rule of the Hegselmann-Krause model with a utility-based decision-making mechanism. The model is reformulated into an augmented state-space representation, where the state matrix induces a time-varying social interaction digraph. The convergence analysis is grounded on two existing theoretical findings that establish convergence for the Hegselmann-Krause type of models and containment control systems with multiple stationary leaders, respectively. Results indicate that, if the structure of the interaction digraph stabilizes within finite time, the model either converges to consensus, where all agents' opinions and actions reach an identical state, or exhibits clustering, where some opinion nodes act as stationary leaders while the remaining nodes approach the convex hull formed by the leaders. Numerical simulations are then provided to validate the theoretical results.

Julien Hendrickx, Alex Olshevsky

We consider the generalization error associated with stochastic gradient descent on a smooth convex function over a compact set. We show the first bound on the generalization error that vanishes when the number of iterations $T$ and the dataset size $n$ go to zero at arbitrary rates; our bound scales as $\tilde{O}(1/\sqrt{T} + 1/\sqrt{n})$ with step-size $α_t = 1/\sqrt{t}$. In particular, strong convexity is not needed for stochastic gradient descent to generalize well.

Erwan Meunier, Julien M. Hendrickx

We analyze Decentralized Online Optimization algorithms using the Performance Estimation Problem approach which allows, to automatically compute exact worst-case performance of optimization algorithms. Our analysis shows that several available performance guarantees are very conservative, sometimes by multiple orders of magnitude, and can lead to misguided choices of algorithm. Moreover, at least in terms of worst-case performance, some algorithms appear not to benefit from inter-agent communications for a significant period of time. We show how to improve classical methods by tuning their step-sizes, and find that we can save up to 20% on their actual worst-case performance regret.

Baptiste Goujaud, Céline Moucer, François Glineur et al.

PEPit is a Python package aiming at simplifying the access to worst-case analyses of a large family of first-order optimization methods possibly involving gradient, projection, proximal, or linear optimization oracles, along with their approximate, or Bregman variants. In short, PEPit is a package enabling computer-assisted worst-case analyses of first-order optimization methods. The key underlying idea is to cast the problem of performing a worst-case analysis, often referred to as a performance estimation problem (PEP), as a semidefinite program (SDP) which can be solved numerically. To do that, the package users are only required to write first-order methods nearly as they would have implemented them. The package then takes care of the SDP modeling parts, and the worst-case analysis is performed numerically via a standard solver.

Farhad Mehdifar, Charalampos P. Bechlioulis, Julien M. Hendrickx et al.

This work proposes a novel 2-D formation control scheme for acyclic triangulated directed graphs (a class of minimally acyclic persistent graphs) based on bipolar coordinates with (almost) global convergence to the desired shape. Prescribed performance control is employed to devise a decentralized control law that avoids singularities and introduces robustness against external disturbances while ensuring predefined transient and steady-state performance for the closed-loop system. Furthermore, it is shown that the proposed formation control scheme can handle formation maneuvering, scaling, and orientation specifications simultaneously. Additionally, the proposed control law is implementable in agents' arbitrarily oriented local coordinate frames using only low-cost onboard vision sensors, which are favorable for practical applications. Finally, a formation maneuvering simulation study verifies the proposed approach.

Julien M. Hendrickx, Alex Olshevsky, Venkatesh Saligrama

We consider the problem of learning the qualities of a collection of items by performing noisy comparisons among them. Following the standard paradigm, we assume there is a fixed "comparison graph" and every neighboring pair of items in this graph is compared $k$ times according to the Bradley-Terry-Luce model (where the probability than an item wins a comparison is proportional the item quality). We are interested in how the relative error in quality estimation scales with the comparison graph in the regime where $k$ is large. We prove that, after a known transition period, the relevant graph-theoretic quantity is the square root of the resistance of the comparison graph. Specifically, we provide an algorithm that is minimax optimal. The algorithm has a relative error decay that scales with the square root of the graph resistance, and provide a matching lower bound (up to log factors). The performance guarantee of our algorithm, both in terms of the graph and the skewness of the item quality distribution, outperforms earlier results.

Alexandre S. Bazanella, Michel Gevers, Julien M. Hendrickx et al.

Much recent research has dealt with the identifiability of a dynamical network in which the node signals are connected by causal linear time-invariant transfer functions and are possibly excited by known external excitation signals and/or unknown noise signals. So far all results on the identifiability of the whole network have assumed that all node signals are measured. Under this assumption, it has been shown that such networks are identifiable only if some prior knowledge is available about the structure of the network, in particular the structure of the excitation. In this paper we present the first results for the situation where not all node signals are measurable, under the assumptions that the topology of the network is known, that each node is excited by a known signal and that the nodes are noise-free. Using graph theoretical properties, we show that the transfer functions that can be identified depend essentially on the topology of the paths linking the corresponding vertices to the measured nodes. An important outcome of our research is that, under those assumptions, a network can often be identified using only a small subset of node measurements.

Julien M. Hendrickx, Alex Olshevsky

This paper investigates the asymptotic behavior of some common opinion dynamic models in a continuum of agents. We show that as long as the interactions among the agents are symmetric, the distribution of the agents' opinion converges. We also investigate whether convergence occurs in a stronger sense than merely in distribution, namely, whether the opinion of almost every agent converges. We show that while this is not the case in general, it becomes true under plausible assumptions on inter-agent interactions, namely that agents with similar opinions exert a non-negligible pull on each other, or that the interactions are entirely determined by their opinions via a smooth function.

Samuel Martin, Julien M. Hendrickx

We consider continuous-time consensus systems whose interactions satisfy a form or reciprocity that is not instantaneous, but happens over time. We show that these systems have certain desirable properties: They always converge independently of the specific interactions taking place and there exist simple conditions on the interactions for two agents to converge to the same value. This was until now only known for systems with instantaneous reciprocity. These result are of particular relevance when analyzing systems where interactions are a priori unknown, being for example endogenously determined or random. We apply our results to an instance of such systems.

Pierre-Yves Chevalier, Julien M. Hendrickx, Raphaël M. Jungers

We consider the problem of determining the existence of a sequence of matrices driving a discrete-time consensus system to consensus. We transform this problem into one of the existence of a product of the transition (stochastic) matrices that has a positive column. We then generalize some results from automata theory to sets of stochastic matrices. We obtain as a main result a polynomial-time algorithm to decide the existence of a sequence of matrices achieving consensus.

Pierre-Yves Chevalier, Julien M. Hendrickx, Raphaël M. Jungers

We address the problem of determining if a discrete time switched consensus system converges for any switching sequence and that of determining if it converges for at least one switching sequence. For these two problems, we provide necessary and sufficient conditions that can be checked in singly exponential time. As a side result, we prove the existence of a polynomial time algorithm for the first problem when the system switches between only two subsystems whose corresponding graphs are undirected, a problem that had been suggested to be NP-hard by Blondel and Olshevsky.