Mathematics

Graphon control (CDC 17-18-19, IEEE TAC 20, Gao and Caines) and graphon mean field games (CDC18, CDC19, Caines and Huang) were used to address decision problems on very large-scale networks by employing graphons to represent arbitrary size graphs, from, respectively centralized and decentralized perspectives. Graphon couplings may be considered as a generalization of mean-field couplings with network heterogeneity. Such couplings may appear in states, controls and cost, and may be represented by different graphons in each case. In this talk, I will present the use of graphon spectral decomposition in graphon control and graphon mean field games in a linear quadratic setting. The complexity of the method does not directly depend on the number of agents or number of nodes, instead, it depends on the dimension of the characterizing graphon invariant subspace shared by the coupling operators.

n this paper, we study the optimal control problem arising from the mean-field game formulation of the collective decision-making in honeybee swarms. A population of homogeneous players (the honeybees) has to reach consensus on one of two options. We consider three states: the first two represent the available options (or strategies), and the third one represents the uncommitted state. We formulate the continuous-time discrete-state mean-field game model. The contributions of this paper are the following: i) we propose an optimal control model where players have to control their transition rates to minimize a running cost and a terminal cost, in the presence of an adversarial disturbance; ii) we develop a formulation of the micro-macro model in the form of an initial-terminal value problem (ITVP) with switched dynamics; iii) we study the existence of stationary solutions and the mean-field Nash equilibrium for the resulting switched system; iv) we show that under certain assumptions on the parameters, the game may admit periodic solutions; and v) we analyze the resulting microscopic dynamics in a structured environment where a finite number of players interact through a network topology.

The Graphon Mean Field Game equations consist of a collection of parameterized Hamilton-Jacobi-Bellman equations, and a collection of parameterized Fokker-Planck-Kolmogorov equations coupled through a given graphon. In this talk, we will discuss the sensitivity of the gradient of HJB solutions with respect to the coefficients, which can be used for the solvability of Graphon Mean Field Game equation. It's based on the joint work with Peter Caines, Daniel Ho, Minyi Huang, and Jiamin Jian, see https://arxiv.org/pdf/2009.12144.pdf.

Large-scale systems comprising of multiple subsystems connected over a network arise in a number of applications including power systems, traffic networks, communication networks, and some economic systems. A common feature of such systems is that the state evolutions and costs are coupled, i.e., the state evolution and local cost of one subsystems depend not only on its own state and control action, but also on the state and control actions of other subsystems in the network.

We consider the problem of designing control strategies for such systems when some of the parameters of the system model are not known. Due to the unknown parameters, the control problem is also a learning problem. Directly using existing reinforcement learning algorithms on such network coupled subsystems would incur $O(n^{1.5} \sqrt{T})$ regret over a horizon $T$, where the $n$ is the number of subsystems. This superlinear dependence on $n$ is prohibitive in large scale networked systems because the regret per subsystem (which is $O(\sqrt{nT})$ grows with the size of the network.

We consider networks where the dynamics coupling may be represented by a symmetric matrix (e.g., the adjacency or Laplacian matrix corresponding to a undirected weighted graph) and the cost coupling matrix have the same eigenvalues as the dynamics coupling. We use spectral decomposition of the coupling matrices to decompose the system into (L + 1) systems which are only coupled through the noise, where L is the rank of the coupling matrix. We show that, when the system model is known, the optimal control input at each subsystem can be computing by solving (L+1) decoupled Riccati equations.

Using this structure of the planning solution, we propose a new Thompson sampling algorithm and show that its regret is bounded by $O(n\sqrt{T})$, which increases linearly in the size of the network. We present numerical simulations to illustrate our results on mean-field control and general low-rank networks.

Joint work with Shuang Gao, Sagar Sudhakara Ashutosh Nayyar, and Ouyang Yi

Real data collected from different applications that have additional topological structures and connection information are amenable to be represented as a weighted graph.
Considering the node labeling problem, Graph Neural Networks (GNNs) is a powerful tool, which can mimic experts' decisions on node labeling.
GNNs combine node features, connection patterns, and graph structure by using a neural network to embed node information and pass it through edges in the graph.
We want to identify the patterns in the input data used by the GNN model to make a decision and examine if the model works as we desire.
However, due to the complex data representation and non-linear transformations, explaining decisions made by GNNs is challenging.
In this work, we propose new graph features' explanation methods to identify the informative components and important node features. Besides, we propose a pipeline to identify the key factors used for node classification. We use four datasets (two synthetic and two real) to validate our methods. Our results demonstrate that our explanation approach can mimic data patterns used for node classification by human interpretation and disentangle different features in the graphs. Furthermore, our explanation methods can be used for understanding data, debugging GNN models, and examine model decisions.