Yang Liu

Yang Liu, Youcheng Lou, Brian D. O. Anderson et al.

This paper presents a first-order {distributed continuous-time algorithm} for computing the least-squares solution to a linear equation over networks. Given the uniqueness of the solution, with nonintegrable and diminishing step size, convergence results are provided for fixed graphs. The exact rate of convergence is also established for various types of step size choices falling into that category. For the case where non-unique solutions exist, convergence to one such solution is proved for constantly connected switching graphs with square integrable step size, and for uniformly jointly connected switching graphs under the boundedness assumption on system states. Validation of the results and illustration of the impact of step size on the convergence speed are made using a few numerical examples.

Qunxi Zhu, Zuguang Gao, Yang Liu et al.

A Boolean control network (BCN) is a discrete-time dynamical system whose variables take values from a binary set $\{0,1\}$. At each time step, each variable of the BCN updates its value simultaneously according to a Boolean function which takes the state and control of the previous time step as its input. Given an ordered pair of states of a BCN, we define the set of reachable time steps as the set of positive integer $k$'s where there exists a control sequence such that the BCN can be steered from one state to the other in exactly $k$ time steps; and the set of unreachable time steps as the set of $k$'s where there does not exist any control sequences such that the BCN can be steered from one state to the other in exactly $k$ time steps. We consider in this paper the so-called categorization problem of a BCN, i.e., we develop a method, via algebraic graph theoretic approach, to determine whether the set of reachable time steps and the set of unreachable time steps, associated with the given pair of states, are finite or infinite. Our results can be applied to classify all ordered pairs of states into four categories, depending on whether the set of reachable (unreachable) time steps is finite or not.

Reilly Raab, Luca de Alfaro, Yang Liu

We prove that Fisher-Rao natural gradient descent (FR-NGD) optimally approximates the continuous time replicator equation (an essential model of evolutionary dynamics), and term this correspondence "conjugate natural selection". This correspondence promises alternative approaches for evolutionary computation over continuous or high-dimensional hypothesis spaces. As a special case, FR-NGD also provides the optimal approximation of continuous Bayesian inference when hypotheses compete on the basis of predicting actual observations. In this case, the method avoids the need to compute prior probabilities. We demonstrate our findings on a non-convex optimization problem and a system identification task for a stochastic process with time-varying parameters.

Yang Liu, Junfeng Wu, Ian R. Manchester et al.

A distributed computing protocol consists of three components: (i) Data Localization: a network-wide dataset is decomposed into local datasets separately preserved at a network of nodes; (ii) Node Communication: the nodes hold individual dynamical states and communicate with the neighbors about these dynamical states; (iii) Local Computation: state recursions are computed at each individual node. Information about the local datasets enters the computation process through the node-to-node communication and the local computations, which may be leaked to dynamics eavesdroppers having access to global or local node states. In this paper, we systematically investigate this potential computational privacy risks in distributed computing protocols in the form of structured system identification, and then propose and thoroughly analyze a Privacy-Preserving-Summation-Consistent (PPSC) mechanism as a generic privacy encryption subroutine for consensus-based distributed computations. The central idea is that the consensus manifold is where we can both hide node privacy and achieve computational accuracy. In this first part of the paper, we demonstrate the computational privacy risks in distributed algorithms against dynamics eavesdroppers and particularly in distributed linear equation solvers, and then propose the PPSC mechanism and illustrate its usefulness.

Yang Liu, Junfeng Wu, Ian Manchester et al.

In the first part of the paper, we have studied the computational privacy risks in distributed computing protocols against local or global dynamics eavesdroppers, and proposed a Privacy-Preserving-Summation-Consistent (PPSC) mechanism as a generic privacy encryption subroutine for consensus-based distributed computations. In this part of this paper, we show that the conventional deterministic and random gossip algorithms can be used to realize the PPSC mechanism over a given network. At each time step, a node is selected to interact with one of its neighbors via deterministic or random gossiping. Such node generates a random number as its new state, and sends the subtraction between its current state and that random number to the neighbor; then the neighbor updates its state by adding the received value to its current state. We establish concrete privacy-preservation conditions by proving the impossibility for the reconstruction of the network input from the output of the gossip-based PPSC mechanism against eavesdroppers with full network knowledge, and by showing that the PPSC mechanism can achieve differential privacy at arbitrary privacy levels. The convergence is characterized explicitly and analytically for both deterministic and randomized gossiping, which is essentially achieved in a finite number of steps. Additionally, we illustrate that the proposed algorithms can be easily made adaptive in real-world applications by making realtime trade-offs between resilience against node dropout or communication failure and privacy preservation capabilities.

Jiaqi Han, Jiacheng Cen, Liming Wu et al.

Geometric graphs are a special kind of graph with geometric features, which are vital to model many scientific problems. Unlike generic graphs, geometric graphs often exhibit physical symmetries of translations, rotations, and reflections, making them ineffectively processed by current Graph Neural Networks (GNNs). To address this issue, researchers proposed a variety of geometric GNNs equipped with invariant/equivariant properties to better characterize the geometry and topology of geometric graphs. Given the current progress in this field, it is imperative to conduct a comprehensive survey of data structures, models, and applications related to geometric GNNs. In this paper, based on the necessary but concise mathematical preliminaries, we formalize geometric graph as the data structure, on top of which we provide a unified view of existing models from the geometric message passing perspective. Additionally, we summarize the applications as well as the related datasets to facilitate later research for methodology development and experimental evaluation. We also discuss the challenges and future potential directions of geometric GNNs at the end of this survey.

Kaiqing Zhang, Yang Liu, Ji Liu et al.

This paper addresses the problem of distributed learning of average belief with sequential observations, in which a network of $n>1$ agents aim to reach a consensus on the average value of their beliefs, by exchanging information only with their neighbors. Each agent has sequentially arriving samples of its belief in an online manner. The neighbor relationships among the $n$ agents are described by a graph which is possibly time-varying, whose vertices correspond to agents and whose edges depict neighbor relationships. Two distributed online algorithms are introduced for undirected and directed graphs, which are both shown to converge to the average belief almost surely. Moreover, the sequences generated by both algorithms are shown to reach consensus with an $O(1/t)$ rate with high probability, where $t$ is the number of iterations. For undirected graphs, the corresponding algorithm is modified for the case with quantized communication and limited precision of the division operation. It is shown that the modified algorithm causes all $n$ agents to either reach a quantized consensus or enter a small neighborhood around the average of their beliefs. Numerical simulations are then provided to corroborate the theoretical results.

Elizaveta Rebrova, Gustavo Chavez, Yang Liu et al.

We present memory-efficient and scalable algorithms for kernel methods used in machine learning. Using hierarchical matrix approximations for the kernel matrix the memory requirements, the number of floating point operations, and the execution time are drastically reduced compared to standard dense linear algebra routines. We consider both the general $\mathcal{H}$ matrix hierarchical format as well as Hierarchically Semi-Separable (HSS) matrices. Furthermore, we investigate the impact of several preprocessing and clustering techniques on the hierarchical matrix compression. Effective clustering of the input leads to a ten-fold increase in efficiency of the compression. The algorithms are implemented using the STRUMPACK solver library. These results confirm that --- with correct tuning of the hyperparameters --- classification using kernel ridge regression with the compressed matrix does not lose prediction accuracy compared to the exact --- not compressed --- kernel matrix and that our approach can be extended to $\mathcal{O}(1M)$ datasets, for which computation with the full kernel matrix becomes prohibitively expensive. We present numerical experiments in a distributed memory environment up to 1,024 processors of the NERSC's Cori supercomputer using well-known datasets to the machine learning community that range from dimension 8 up to 784.

Yang Liu, Bo Li, Brian Anderson et al.

This paper proposes and investigates a framework for clique gossip protocols. As complete subnetworks, the existence of cliques is ubiquitous in various social, computer, and engineering networks. By clique gossiping, nodes interact with each other along a sequence of cliques. Clique-gossip protocols are defined as arbitrary linear node interactions where node states are vectors evolving as linear dynamical systems. Such protocols become clique-gossip averaging algorithms when node states are scalars under averaging rules. We generalize the classical notion of line graph to capture the essential node interaction structure induced by both the underlying network and the specific clique sequence. We prove a fundamental eigenvalue invariance principle for periodic clique-gossip protocols, which implies that any permutation of the clique sequence leads to the same spectrum for the overall state transition when the generalized line graph contains no cycle. We also prove that for a network with $n$ nodes, cliques with smaller sizes determined by factors of $n$ can always be constructed leading to finite-time convergent clique-gossip averaging algorithms, provided $n$ is not a prime number. Particularly, such finite-time convergence can be achieved with cliques of equal size $m$ if and only if $n$ is divisible by $m$ and they have exactly the same prime factors. A proven fastest finite-time convergent clique-gossip algorithm is constructed for clique-gossiping using size-$m$ cliques. Additionally, the acceleration effects of clique-gossiping are illustrated via numerical examples.