Quantifying the Controllability of Coarsely Characterized Networked Dynamical Systems
Authors: Nafiseh Ghoroghchian
Rajasekhar Anguluri
Gautam Dasarathy
Stark Draper
Venue: ICLR 2022 Submitted (2022)

Abstract: We study the controllability of large-scale networked dynamical systems when complete knowledge of network structure is unavailable. In particular, we establish the power of learning community-based representations to understand the ability of a group of control nodes to steer the network to a target state. We are motivated by abundant real-world examples, ranging from power and water systems to brain networks, in which practitioners do not have access to fine-scale knowledge of the network.  Rather, knowledge is limited to coarse summaries of network structure. Existing work on "model order reduction" starts with full knowledge of fine-scale structure and derives a coarse-scale (lower-dimensional) model that well-approximates the fine-scale system.  In contrast, in this paper the controllability aspects of the coarse system are derived from coarse summaries {\em without} knowledge of the fine-scale structure.  We study under what conditions measures of controllability for the (unobserved) fine-scale system can be well approximated by measures of controllability derived from the (observed) coarse-scale system. To accomplish this, we require knowledge of some inherent parametric structure of the fine-scale system that makes this type of inverse problem feasible. To this end, we assume that the underlying fine-scale network is generated by the stochastic block model (SBM) often studied in community detection. We quantify controllability using the ``average
controllability'' metric and bound the difference between the controllability of the fine-scale system and that of the coarse-scale system.  Our analysis indicates the necessity of underlying structure to make possible the learning of community-based representations, and to be able to quantify  accurately the controllability of coarsely characterized  networked dynamical systems.

Under review as a conference paper at ICLR 2022
QUANTIFYING THE CONTROLLABILITY OF COARSELY CHARACTERIZED NETWORKED DYNAMICAL SYSTEMS
Anonymous authors Paper under double-blind review
ABSTRACT
We study the controllability of large-scale networked dynamical systems when complete knowledge of network structure is unavailable. In particular, we establish the power of learning community- -aseed representations understand the ability of group of control nodes to steer the network to target state. We are moti- vated by abundant real-world examples, ranging from power and water systems to brain networks, in which practitioners do not have access to fine-scale knowledge the network. Rather, knowledge is limited to coarse summaries of network structure. Existing work on "model order reduction" starts with full knowledge fine-scale structure and derives a coarse-scale (lowerddimensional) model that well-approximates the fine-scale system. In contrast, in this paper the controlla- bility aspects of the coarse system are derived from coarse summaries without knowledge of the fine-scale structure. We study under what conditions measures of controllability for the (unobserved) fine-scale system can be well approximated by measures of controllability derived from the (observed) coarse-scale system. To accomplish this, we require knowledge of some inherent parametric structure of the fine-scale system that makes this type of inverse problem feasible. To this end, we assume that the underlying fine-scale network is generated by the stochastic block model (SBM) often studied in community detection. We quantify controllability using the "average controllability" metric and bound the difference between the controllability of the fine-scale system and that the coarse-scale system. Our analysis indicates the necessity of underlying structure to make possible the learn- ing of community-baseee representations, and to be able to quantify accurately the controllability of coarsely characterized networked dynamical systems.
INTRODUCTION
In this paper we study controllability for networked dynamical systems when our knowledge of system structure is limited to coarse summaries. We are motivated by myriad real-world settings where system identification must be performed based upon measurements taken by low-resolution instruments unable to probe fine-scale structure. Our motivating example is the human brain. While efforts are under way produce canonical human brain map, our knowledge of the brain interconnected, network system is not yet to the level of the whole-brain individual neuron (Betzel and Bassett 2017). And yet. motivated by emerging medical technologies, there are important control tasks we would like to tackle. For example, novel brain implants designed for epilepsy patients aim to "steer" the brain away from states that correspond to seizures (Heck et al. 2014 Muldoon et al.) 2016). Our goal is to quantify the controllability of a scale networked dynamical system given access only to coarse knowledge of network structure. Generally, without parametric structure, this is impossible. But real networks do have structure and so in our model we assume the fine-scale network has connectivity induced by an underlying stochastic block model (SBM).
Approximation of high-dimensional (fine-scale) dynamical systems by lower-dimensional (coarse- scale) ones is known as "model order reduction" (MOR) in the controls literature. There a key difference in assumptions that differentiate our setting from that literature. In MOR the starting point is a complete description of the high-dimension. system. The task is to formulate a lower-dimension system, the dynamics of which well-approximate those of the full system. In contrast, coarse summaries of the fine-scale system. We do not have access to the fine-scale dynamics and must exploit parametric knowledge (via the assumption of generative SBM). One might think of the
start from

---

Under review as a conference paper at ICLR 2022
distinction akin to "active" versus "passive" MOR. Traditional MOR is active in that it actively decides how to coarsen the system to yield the best reduction. But for us, our knowledge is limited by the precision of our instrumental observations, passively collected data is our starting point.
Controllability is a function both of system dynamics and how we actuate the system (Pasqualetti et al.] 2014 Yuan al.) 2013). Herein we assume that we both measure and actuate system only coarsely. A control question we study is which coarse-level actuations are most "influential" in controlling the underlying fine-scale system. Such knowledge can assist with actuation selection; e.g., in our motivating epilepsy application, where best to position devices to be able to collapse the unstable brain-state oscillations that lead seizures. (O'Leary et al. 2018; Pazhouhandeh et al., 2019; Kassiri et al.) 2017)] Shulyzki et al., 2015) To accomplish our goal we characterize the average controllability of a vector of systems, each corresponding to a different coarse-scale actuation input. By comparing these vectors, and because these vectors well approximate the corresponding vectors for the fine-scale system, we aim (in the long term) to produce clinically-usse information for the neurologist.
Contribution: Our work is the first of its kind that proposes a learning-based framework for inferring the controllability of fine networks from coarse measurements, and characterizes the mismatch between the controllability of the coarse and fine-scale networks. We study two approaches.
1. In Section 5 we build from MOR. We define an auxiliary. fictitious, reduced-orde system based on the coarse data, and use the average controllability vector of this system to approx- imate that of the fine-scale system. We derive a tight upper bound on the "approximation- error" which is the sum of two terms. One term goes to zero as the coarse network size increases and the network becomes dense. The second term is function of the synchro- nization between the coarse summary data and the underlying community structure. synchronization is not sufficiently high, this term may not approach zero even as the network size increases.
2. In Section 6 we learn the fine-scale system's 's average controllability vector directly from the coarse data. This learning-based algorithm builds on the mixed-membership algorithm of Mao et al. (2017) for unsupervised learning of the parameters and the community structure of a SBM. We derive a tight upper bound on estimation error and characterize its convergence. Although the error bound implicitly depends on synchronization, unlike in the MOR-based approach, the error of this approach converges to zero as the coarse network size and its density increases.
2 BACKGROUND / RELATED WORK
The study of extracting community structure from coarse summaries is recent. The authors in (Ghoroghchian et al., 2021) used the stochastic block model (SBM), developed in the community detection literature (Abbel 2017), to lay out a framework for a coarsened and weighted variant of the SBM. We build off those results in this paper. The structure of many worldworld networks, including brain networks is, at least empirically, known to have community structure across various spatial scales (Sporns and Betzel 2016 Pavlovié et al., 2020). The SBM and its variants provide a powerful modeling framework to facilitate fundamental understanding of graph community organization and have found applications in many domains, including social and power networks. (Dulac et al. 20200 Funke and Becker 2019 Abbe 2017).
Coarsened SBM as a generative process:
Complex networks controllability: The development of control methods for complex networks is major effort in network science (Scheid et al., 2020)). Coupling traditional notions of controllability with graph theory reveals several insights into the role of network structure (e.g.. presence of communities, diameter, and sparsity). size, and edge weight strength in controlling large-scale networks (Wu-Yan et al., 2018 Kim et al., 20188 Constantino et al. 2019: Sun 2015). Further one may want to understand which group of nodes, when actuated as inputs, can be used to steer the network to an arbitrary target state, and at what cost (Cortesi et al., 2014 Gu et al. 2015). Recent works in network neuroscience Gu et al. 2015) have popularized the notion of average controllability. This scalar metric associate a measure the relative control influence of group of nodes. In this paper consider vector of such scalar measures to study the comparative influence of different sets of nodes. To the best of our knowledge ours is the first work that characterizes this type of error bounds for the controllability of coarse graphs.
2

---

Under review as a conference paper at ICLR 2022
3 PRELIMINARY NOTIONS
Notation: We denote vectors and matrices using bold faced small and upper case letters. The n
dimensional all-ones and -zero vectors denoted by 1, and O,,. For M = [Mue] Roxm define
||M]|c = maxisusn Σx=1 Muul]: M = m Muel: and || |M V (MT)). Let m = n. then define the spectral radius by p(M) = max; [|>:]]: diag(M) = [M...... M IT R"; and (Ma sets the off-diagonal entries of M to zero. For matrices M'S with arbitrary dimensions, BilkDiagMM,,....
Ma) denotes the block diagonal matrix. The inequality M, s M implies element wise inequality. We write f(n) = (h((n) iff there exist positive reals co and no such that (zx) S (n)(n) for all n 2 no. The support of a vector, supp(m), is the set of indices i such that m, * 0. The cardinality of set V is denoted by [V. For positive integer m, we denote [m] (1, [1....,m,) m.). 1 (m) returns vector of same size with non-zero replaced by 1.
Networks: A network is defined by an un-directed graph _ (V,E), where the node set V - (1....,n)) n and edge set & C V x V. For an edge (u, E E, assign the weight Aue = Am E R, and define the weighted symmetric adjacency matrix of G as A å [Aue], where Auv Aur 0 whenever Auv & E. A random network is an un-directed graph with a random adjacency matrix.
3.1 LINEAR DYNAMICAL SYSTEM ON RANDOM NETWORK
For network G with nodes and the symmetric adjacency matrix A, associate state z:lk] E IR to the i-th node and let the nodes evolve with the linear and time-invariant (LTI) dynamics
Ax([] + Bu(j, x(1 + +1 = C. c.tr(A)
A
(1)
The state x[{] = [1] ................................ In [0] is steered to an arbitrary value by an input u(t] E R". Here, the
input matrix B Diag(b) Ru where b E (0, 1]" determines which components of u|(] enters the network For e.g., for B = Diag(1m. On-n,), ). the input enters the network through control nodes set
{1..... n The normalization e tr(A) factor, with appropriately chosen constant e > 0, ensures that system in Eq. is asymptotically stable. Finally, we define Anom the normalized matrix, and use this convention throughout the paper.
for c-u(A)
For fixed system matrix Apom- necessary and sufficient condition for the asymptotic stability of Eq. [ is that p( mm)) I 1. For random A A we consider the probabilistic stability: P(p(A (ppAAmom S 1]ethe greater the value, the greater the chance that Anom is stable. For SBM generated random symmetric matrices, we provide sharp non-asymptotic lower bounds on
< 1].
The networked LTI system in Eq. D is T-step controllable if x
can be steered to any target state x E RD for some inputs: u(O),-. uuT' -1.. The -tep controllability Gramian of Eq. 1 given
below, among other things, allows us to study if Eq controllable or not.
Cr B) ET- (A (Anom) 'BBT (Anom)"
(BBT(A
(2)
By definition C- [A B) 2 O. and is well known that G with n nodes is T-step controllable if n-step controllable; or equivalently, CA B) > For other interesting properties of Eq. we refer to (Chen) 1999). For the simplicity of exposition, we let T - co and consider the infinite time lim Cr (A B), which exists with 1 - PP(p(A)))) 2 1]; see also Pasqualetti et al. 2014). We drop the notation (Anom, B) in C when the context is clear.
horizon Gramian: C(Anom B)
Average energy: A widely used metric to measure how hard or easy is to control the network is average energy: ]]x]=== xTe Cx'x dxxxx/ ||m]|== dx, which evaluates to n (t((C)) Cortesi et al. 2014).
Here, where Ci is the pscudo inverse, and x xTcxx x is the minimum control energy needed to steer x 0) = 0 to arbitrary target state x E R². Thus, average energy measures the minimum control energy required to steer x x0] = 0 to an arbitrary state uniformly distributed over the unit sphere.
One may think our LTT model as the lincarized system of an underlying non-linear system. Controllability rescarch. whose columms are indexed by K. C [m].
of non-linear systems require case by case analysis and we leave this topic for future
2 AAleemaaively, Bu(t) = [g where Bx is the mub-matrix
However, we stick with notation in Eq. to make our analysis less cumbersome.
'The LTT system Eq. 1 ii asymptotically stable if ||x[t]]] 2 + 0 as + co, for u(() and x( * 0.
3

---

Under review as a conference paper at ICLR 2022
Average controllability: Numerical computation of C for large-scale networks is demanding. Owing to the fact that tr(Ct) > 1/tr(C), uses tr(C)-called the average controllability a proxy for average energy Gu et al. (2015). The higher the average controllability for a given set of control nodes defined by B, the smaller their average energy, thus higher their influence on the network.
3.2 STOCHASTIC BLOCK MODELS
Stochastic block models (SBMs) are probabilistic models that produce random graphs with planted communities. Formally, let Gnne a (V, E) be the un-directed graph (also referred as fine graph) with n nodes and random edge weights generated according to the general SBM(n, Q, p):
Definition 1. (General SBM) In the general (BM(n, Q, p). the graph Gune is partitioned to K disjoint sub-graphs (or communities) of relative sizes p [PI..... Pk] such that V = U Vx- Two nodes u E Vi and v E V&' are joined by an edge with the weight Aue E (0, which is drawn with probability QuK independently from other edges, for all k. k [K].
In General SBM, the probability distribution of weights Aue is common for all E Vv- and u E Ve- The general (nM Q. p) thus generates a weighted symmetric graph with communities with non-identical in- and cross-edge connection probabilities given by Q E [0, 1j x Alternatively,
A Bernoulli Qu,k)
if if k' E [K]: Pku > O, Pk > 0,
(3)
where the community membership matrix P = [Pkel R is given by
PP = =Diag (DVi...... [Vk)) with Pku
{
1
if Vk. otherwise.
(4)
We define D A 1PP which is diagonal matrix of relative community sizes. Definition 2. (Coarse SBM Ghoroghchian al. ))2T Define coarse-scale summary to A as
Ā WAWT mmm
(5)
where the coarsening matrix W Rm.. is (a) r-homogeneous, for all i [m]: that is, each i-th row of W (say w:) has r non-zero terms and all rows have constant row sum and (b) (WWT = Im). O
Here, A can be interpreted as the symmetric adjacency matrix of an un un-directed graph Gecarse with m nodes- referred to as coarse graph. This interpretation is helpful when we discuss LTT system associated with À in Section 5 We refer the nodes in Geoarse to c-node as opposed the fine nodes in Gine- Note that r < m. and r < n indicating that c-nodes can cover the fine graph only sparsely. In other words, there may exist (several) fine nodes that do not contribute to A (see Fig. []. The main goal of our paper is to quantify controllability of Gine. with community structure, using the coarsely inferred network Geoarse. Importantly, we do not have access the way the coarse graph is acquired at the time of decision making though the results depend on them.
From Eq. 8 and Eq. 3 the expected quantities of Á [[A] and Ā A E[A] can be computed as
A = PTQ and À (WPT) Q(WP")T
where o E RRRx K is the coarse community membership matrix, and i captures the extent to which the i-th c-node overlaps with the k-th community. Let us also define the resolution parameter.
min [
sk-
By definition 1/r < < In what follows, we assume that a c-node has a constant minimum overlap (i.e. v) with each community that independent of other system parameters.
The example below will highlight the structural differences among matrices P, 4. and W. Example 1. For fine network shown in Fig. the following hold
Aug" stands for compound coarse.
4

---

Under review as a conference paper at ICLR 2022
1. P BIkDiag (1 12: 1s 1.). Here, 1a is the d-dimensional all-ones column vector.
2. Φ- [ 1 $ where Φ [1,0,0]; Φ2 1 03; D3 4 10,1,0]:
45 0, 3 3 and t 00, 0, 1).
3. Finally, each row of the coarsening matrix W has three non-zero entries, all equal 1 1/3.
Each c-node (1, 1,3,4, 6) covers one community; each c-nodes in (2, 5 overlap with two.
Assumption 1. (SBM scaling Abbe 2017 For all k E [ we have O < Cmin
[el S Cmax < 1,
where Cmin: Coax constants. There exists pn (0,1) and non-negative malrix Q(0, such that
Q = pre
(8)
Assumption 2. community & E [K]. Formally, for all k E [K], there exist a coarse node E [mn] such that Pix Assumption 3. (Uniform Coarsening): There exist Emin and Emux independent of m such that
c-node): The coarse graph has at least one pure node per
Gmin 1 & 1 4 f/m Emar1x.
We also assume that communities have ceff-connections, that is. tr(Q(o) > O, and Q < <lak Assumption [ helps us uniformly control the sparsity of connection in and cross communities. For several real-world networks, Pn. typically decreases with n /bbbe (017). Assumption states that for each community there exist least one c-node that is fully inside one community. We call such c-node fully synchronized (see Remark [ Finally, Assumption 3 Jensures that the relative coverage of each community measured by coarse nodes scales lincarly with respect to the graph size.
Reduction
approach
ooarsc.A
[ uitil
Sccarse: k[++1] =Â... xt1 Guft]
(1))
[b]
target:0
gronp grgget
Learning approach
1
+=
Coarsening
Algarithm (2)
i
Algnrithm
group
K
(d)
Figure 1: Schematic of MOR and learning-hasse hased approaches for estimating @grup, A- (a) For Giiee consisting of 36 nodes, we have = communities (V1, V2, Va) with m = coarse (c)-nodes (.1.....aa each having a coverage size r == 3. The control node set is Ka. (b) In MOR approach, we infer O group A via reduced order dynamical system Scourse. (c) Learning based approach capitalizes mixed membership (MM) Algorithm to estimate @grou..A directly from A, therehy avoiding the need to do consider Scoarse-
Remark 1. (Synchronization of community and coarsening): The coarsening operation oblivi- to the community structure in Gime- Thus, the i-th c-node contains information about multiple communities if supp( s.)) n supp + 0 (the subscript denotes the i-th ror). + j. Perfect synchronizaatin A special case where the intersection is non-empty only when i= This happens when all the communities have the same size and each c-node covers only one whole community.
synchronization:
PROBLEM STATEMENT
Consider the L.TI system on the network Grines defined by the symmetric adjacency matrixin A Eq. Sine x[| 1] = Anomx[|| + Bxu(())
where A DUT(A]
A, A Raxn and Bx Raxx selects
of control nodes I. Güne-
Depending on the controllability properties of Gime (see, Section 3.1 the inputs at these |AC] control nodes may may not effect all the states in x(k]. Let IC; supp (, be the set (hereafter, group) of r nodes coarsened by w, The following assumption states that gime is controllable from all K;; C Gine; see Remark
5

---

Under review as a conference paper at ICLR 2022
Assumption 4. Let Bx, Di For any E [m]. the Gramian C(Anom: Bx.,) is full rank.
As pl ((Anmm) < 1 holds with high probability (see Lemma D it follows that C(Amm,, Bx.) exits, and hence, the infinite time Gramian C(Anm,, Bx,) exists. Assumption 4 ensures that average energy (see Section 3.1 is finite; however, average controllability need not be finite.
For K,-th control node set with input matrix Bx, Diag(w3 associate the average controllabity
measure: ( Aroup.A tr(C Bxc, )l, for all i E [m]. Since C()) is p.s.d matrix, it follows that
(1) A 2 0. Accordingly, define the group average controllability vector for Siac:
group. - (o Aroup.A
(m group.A
(10)
which summarizes the average controllability measure (see Sec 3.1 for all control nodes sets {KI,.... Km Thus, group.. helps infer (i) ic,s that drive the network to the desired target state with least control effort, and (ii) if such control node sets should have community structure.
In this paper, using only the knowledge of À in Eq. 5 we want to estimate the random vector A in Eq. T0 We consider two contrasting approaches: (i) the traditional model order reduction (MOR), where rely upon the reduced order auxiliary system Scuarse (see Eq. [1 governed by A to infer ggroup.Ai and (ii) the learning based approach, where we directly estimate 2 group. A using clustering based mixed membership community learning algorithm; see Section 6 Fig. provides a nice graphical illustration of our approaches. Broadly, our analysis highlights the role of community structure, coarsening process, and graph sparsity conditions on the performance of these both approaches. Our numerical simulations show that both approaches can outperform each other; however, learning based approach outperforms its counterpart in several parametric regions Finally, our main results in Sections 5 and 6 are probabilistic in nature because is a random matrix.
Remark 2. (Group nodes controllability) Assumption 4 demands that a group of nodes should be able to control Gime. which holds true for brain networks (f (Pasqualetti et al. 2019). This assumption is a very weaker condition than asking Gime be controllable from every single node. Moreover, Gime is not controllable from the control nodes, we can decompose the state-space of Gime into controllable and uncontrollable sub-spuces (Chen 1999), and adapt our analysis to the controllable sub-space.
MOR APPROACH FOR GROUP AVERAGE CONTROLLABILITY
We provide tight upper bound on the element wise error between Aroopp. in Eq. 10 and coarse, À in Eq. 13 The latter quantity is the group average controllability vector of the reduced order system:
Scuarso
X[t + 1] = AnomX((t) X((] + Bu[t],
(1I)
A used for stability purposes, where ē > 0. Importantly, the state X[t] E RT is not compression of the true state x[t] in Sinc and m < n (hence the name MOR). Rather, X|t] is a fictitious state that describes the dynamics of the (scaled) matrix A. This fictitious state is controlled by the input Bu[t] E I
where A Anom
WAWT is given by Eq. 5 and the normalization factor ē tr( (A) is A-t(A)) A À
The following lemma states that Sine and Scoarse are asymptotically stable with very high probability, Thus, Ogroup.A in 10 and O coarso, A in 13 are well defined. Let c, C, 3 > O, and define the stability
indices: Knom
(cB tr (r(A) || //x))/ (n - cB)²) and Kinm == (σ3 ir( || )/ (mm((1)2mm)))
where A E BRax and A Rmxm are given in Eq. 6nd r the coverage size.
Lemma 1. (Probabilistic stability of Sjine and Scoarse): Suppose that the stability indices Knom and Fnom are strictly positive for some constants c, C > O, and 0 S 1 < 1. Then,
PP (p(Apom) 2 3] S n exp (- -k6mmm)
and ((p(Anmm) 2 3) & m mxep (-2
(12)
For have 1, and hence, the probabilistic inequalities in Eq. 12 coincide with each other. Further, the higher Knom and Knom- the higher the chance that Sime and Senarse are stable. Interestingly, Knom and Knom do not explicitly scale with and m. In fact, Knom Kaoo,, lb. where

---

Under review as a conference paper at ICLR 2022
Knom, 16 == (cß Cmin (r(Q)= Cmax [[Q]|s))(11 c3 2 is independent of n. Thus, stability is not guaranteed for larger networks modeled using Sine with c trA normalization.
Instead, Knom, 1b
cB 1, thereby P [(((Anom) 3] S exp(-22knom 1b - 0. So, under
tr Q)). Let Cmax Cmin For diagonally dominant probability matrix Q (i.e., the community structure is assortative-mot in-community edges than acmoss-community edgess), tr(Q) 2 =|Q and hence, we can choose e and such that cg 1. However, non diagonally dominant matrices can satisfy tr(Q) (Q) 2 || Q lo. For example, a symmetric matrix Q E R3x3, with Q = 0.2, Q12 = 0.25, and Q13 0.01 not diagonally dominant because Qis S E jah
what conditions Knom > 0 for cB = 1? One such condition cg 2 Caax
Qij. for all but tr( Q) 2 Q
We now bound the difference between 0 groop..A A in 10 and 0
13 Let Änom A/(ē-tr(l tr(A))
coarse,
and B; rWdiaggw' the coarsened input matrix. Let the average controllability for the i-th 2.) Define the average controllability vector for Scoarse:
c-node be g(i) - (r((((Anuu group.A
(O()) coarse,
m coarse,
E R
(13)
coarse,
In what follows, when the symchronization holds, we show that 0 Ā associated with Scoarse can well approximate Ogroup. associated with Sine. Define the error metric:
re()) group.A
((1)
A) A
Coarse,
for all i [m].
(14)
(6)
(
1
group.
The proposed error metric A.(A, A) allows us to do a fair shifting- and scaling-free comparison between the vectors 0 A and O coarse_A The shift factor "-1" accounts for the inherent "+1" shift in the average controllability definition and the scale factor discounts the 1/r factor in 0 Aroup.A. Akin to (,(A, A) in Eq. 14 define A,, associated with the expected quantities A and Å.
Theorem 1. (Element wise bound on O Arrop..A coarse, A): Let Ai(A, A) and A (A, A) be defined
as above. Then, under the assumptions in Lemmal (A, S A. O Pam vmp2
with probability at least 1 - 6 6xxp(- (exp(-2x(QQe) (c) D, n. Pn))) where, for constants 0 < o, x x<Q(1 (c) D.U,m,n, n. p..) min npt (tr(QQ m(p.v² (
p mn (Gmin Cmin 11,,)) ph m 3 (cain 1100000)10000 11110)
(rmin
with v, D, and Q (e)) given by Eq. 7 Eq. 4 and Eq..
8 and Emin is defined in Assumption 3
Theorem says that (A, ~ Pnm
provided ,, ) is small. Thus, for fixed n, MOR based estimate 0 c Ä approximates O @group.A if the graph density Pr. or number of c-nodes is large, which we validate using numerical simulations as well. can be shown that the bias term (A, A) is exactly zero if the communities are synchronized with the coarsening process (see Remark T and that Qi = p > 0 and Q = q > 0, for 4 j.
Ymp2
6 LEARNING APPROACH FOR GROUP AVERAGE CONTROLLABILITY
We present our learning based approach to estimate Ogroup. A in Eq. 10 Unlike the MOR based
approach that relies Snue. directly estimate elements in O group.. A based the popular mixed membership (MM) community learning algorithms (Mao et al., 2020 Huang et al. [2019] Mao et al. 2018 2017 Aicher et al., 2015). Specifically, we work with the MM algorithm by MMa al. 2020 which is not only numerically efficient but also has strong theoretical guarantees.
Lemma 2. Let 0 group. A be obtained by replacing A with the expected matrix À in O Agroup.A. given by Eq. 10 Let P and & be as in Eq. 4 and Eg. 6 Suppose that Assumption I holdd Then,
@gropp A (1m dddiag( (T)) /r,
(15)
7

---

Under review as a conference paper at ICLR 2022
where d == (/tntt//n/////// ( ()), D (1/n)PPT, and Q(1) is given by Eq. 8 and
- (nd)Q 0 DQ (c) ((nd)DQ (0) p--
(16)
Lemma 2 gives us a formula to compute the group average controllability vector associated with the expected matrix A (see Supplemental material for complementary explanation and interpretation).
Theorem (see Appendix) shows that (A A) S e, for arbitrary e O, hold with high probability. In view of this fact, we propose our candidate estimator as
group - 1m + @diag( (T)
(17)
where r QDQ
y The hatted quantities & and Q are obtained from Algorithm which takes as input A and number of communities K. Instead, we obtain D from Algorithm
(I - (r(
v(D))
Importantly, Ogroup Eq. is obtained from coarsened matrix A but not the fine scale matrix A.
Theorem 2. (Component wise error bound between ① @group and O @group.Al a): Suppose that there exist constants Emin and Emoz that satisfy Assumption 3
Then, under the hypotheses stated Lemma
r group,
g(0)
group
=0
|max + E4 +
[EQ Imax +
ED maxx
(rg() group, -
2i=1
group
Pn.
(ā:(A)
holds with probability at least 1 -
D, m. n, Pn)), where Es A - Eq 2
Q Q.
and ED A D D are the error matrices. Further, for constant 0
<
< 1, the exponent S
R(Q (c) D, n...n mmi) min (n mnp? (Emin Cain QQ ( (1,2))
Theorem 2 suggests that for sufficiently large m, the estimate 0 ggroup approximates group..A A to an arbitrary precision if: (a) the graph dense enough (larger Px). (b) the coarse community membership matrix is well estimated (smalle 6 E+ max). (c) the cross-community probability estimation do not suffer from high error (smaller |Eql Imax), and the relative community sizes estimated from the coarse graph are close the ones in the fine graph (smaller ||Eb))> The result of Theorem 2 is important because one directly infer the most influential control node set KG (one with high average controllability) via the most influential i-the c-nodes, and vice versa.
Algorithm 1: Direct Inference of the Group Average Controllability
Require: estimates O and Q from Algorithm and the number of communities K 1: compute D = diag( T 1x 1m
2: return @group 1m &diag
QDQ (DQ (DD )
(I
DQ
Algorithm 2: Mixed Membership Community Estimation Algorithm (Mao et al. 2020
Require: Coarse adjacency matrix A, number of communities K
1: compute the highest K eigen-decomposition of Á as VÂÁT and set Speaned Prune V)
2: set X [[m]] (Sp.uned and compute Spure Successive Projection Algorithm
3: set Xpuue = X (Spure::) and compute un un-normalized famm-nom_ x1
pure
4: duun-nom
if d un-nom 112 Vi E [m], k E [K]
5: return Diag
(a nom--nmm 1x) fun nom and Q = X AX
pure
'This MM algorithm adapted from Mao et al. (200)) a type of spectral clustering method that first performs eigen decomposition of Á to find the overlapping membership ($.x) of the fine nodes. A pruning step is also included (see steps and 5 A Algorithm 2 to speed up the algorithm performance.
6 Mao et al. 2020| showed that EEgg Imxx and || |l stated in Theorem 2 approach zero under some conditions, m oc. But these conditions might not he applicable to our setup because of our coarsening operation. However, simulations show that (,(A) decreases with m. The hehavior of ||E.g mms and ||Ea]] max with respect graph scaling left for future work.
8

---

Under review as a conference paper at ICLR 2022
7 SIMULATIONS
We validate our theoretical results by plotting the errors |/ - A,(A, A) and 1 > (A) and show that these eтrоTs are comparable to the bounds we obtained in Theorems I
and 2
We generate
A ~ (B, Q. p) and then determine A = WAWT (see Supplemental material for generating W). We set number of fine nodes = 5000, the overlap parameter 7 0.1, and the number of communities K 5. Finally, for Q E R x we set Quk = p = 0.05 and Q&K = q = 0.01 (for 4. Fig. 2(d) illustrate the qualitative behavior of the errors with respect to changes in m. Pa. and the degree of msohhosyncronnzztioon in coarse nodes (i.e., M) and To fairly compare these errors,
k * k'). If not specified, the number of c-nodes m 100 and coverage size per c-node
rg(i) group.A
we also consider base line error: D
(/4 Em (10 group. -1) 1/m, where μ E [1,
contains i..dd uniform random variable drawn independently of A.
Enor Type
Enor Type
Casaline Ente
Daseline Encr
MDR Entr Leartin Entr
MDr Eimr
10"
10"
Learning Encoe
Enor
10
10
100
203
700
400
500
C00
10
20
40
50
durailyScaknng
(8) w.r. no. course nodes m..
(b) wirl Prr. for 5g 0. 0.005.
10"
10
10f
overlop
(c) wat overlap extent 7)-
(d) was. coverage size
Figure 2: Estimation enror based MOR and Learning approaches. MOR Emor= A.(A, A)mm and Learning Brro==... (A) The shaded region in the figures represent standard deviation computed for 20 independent realizations. We make the following observations. First, both the learning and MOR hased errors are consistently better than the random baseline. Second, the learning based approach has consistently smaller error than that of the MOR approach for large parametric regimes. Third, (a) shows that all errors monotonically decrease shows that errors decrease as Pn increases. This is expected because larger values of p. result in more distant in- and estimation casier. Fifth, (c) demonstrates the higher tolerance of the Learning approach to situations whenin coarse measurements are less synchronized, in comparison to the MOR method. Finally, (d) shows that error decreases with r. This should be the case as larger means more fine nodes are sampled during coarsening.
increases. This is consistent with our bounds in Theorems T and Fourth, (b)
edge densitics. This makes community representation extraction and controllability
CONCLUSION AND FUTURE WORK
We introduced a learning-based framework that exploits the power of community-based representation learning to infer average controllability of fine graphs from coarse summary data. We compared the performance of this approach with that of MOR approach. For both these methods, we derived high probability error bounds on the deviation between the error estimate and ground truth, and validated the theory with numerical simulations. Our results highlight the role fine- and coarse-netwond sizes, graph density, and community synchronization bias (see Remark modulating the estimation errors. Interestingly, for the latter approach, we show that the estimation error decreases with network size albeit the synchronization bias, which is not the case with the MOR-based approach. For future, we plan to implement our theory to study the role of coarsening, community structures, and synchronization aspects the controllability of brain networks.
'The Python code reproduce the results is attached to the submitted file.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Although our work mainly takes a theoretical perspective to the controllability of coarse graphs motivated by therapeutic neuroscience applications, our results can potentially involve negative impacts if employed in other applications. For instance, identifying the most influential groups of nodes (or equivalently individuals) in a social network as result of estimating the network group average controllability. may motivate manipulative actions; i.e. the most influential node group may selected for control, in order to steer the whole network towards an unethical goal (like manipulating individuals in social network to vote in favour of particular election candidate). The negative impact may also result in bias against less-influential nodes, as they will be ignored when comes to the selection of node groups for control actuation.
10 REPRODUCIBILITY STATEMENT
All the results presented in this paper are reproducible. The theoretical findings annotated and step-by-step elaborated the appendix. The data generation process and the parameter values used for numerical simulations fully explained. In addition, the Python code from which the simulation figures are generated attached to the submission files. The code is also on Github and the repository will go public upon submission acceptance.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Emmanuel Abbc. Community detection and stochastic block models; recent developments. The Journal of Machine Learning Research, 1, 2017.
Christopher Aicher, Abigail Z Jacobs, Aaron Clauset. Learning latent block structure weighted networks. Journal of Complex Networks, 3(2):221-28) 248, 2015.
Richard F Betzel and Danielle S Bassett. Multi-scale brain networks. Neuroimage, 160:73-83, 2017.
Chi-Tsong Chen. Linear system theory and design. 1999.
Pedro H. Constantino, Wentao Tang, and Prodromos Daoutidis. Topology effects sparse control of complex networks with laplacian dynamics. Scientific reports, 9()):19, 2019.
Fabrizio L. Cortesi, Tyler H. Summers, and John Lygeros. Submodularity of energy related controllability metrics. 53rd IEEE Conference on Decision and Control, pages 2883-2888, 2014. doi: 10.1109/CDC. 2014.7039832.
Adrien Dulac, Eric Gaussier, and Christine Largeron. Mixed memberrim stochastic block models weighted networks. In Conference on Uncertainty Artificial Intelligence, pages 679 688. PMLR, 2020.
Thorben Funke and Becker. Stochastic block models: comparison of variants and inference methods. PloS one, 14(4):+0215296, 2019.
Nafiseh Ghoroghchian, Gautam Dasarathy, and Stark Draper. Graph community detection from coarse measure- ments: Recovery conditions for the coarsened weighted stochastic black model. In International Conference on Artificial Intelligence and Statistics, pages 3619-3627. PMLR. 2021.
Shi Gu, Fabio Pasqualetti. Matthew Cieslak, Qawi K Telesford, B Yu Alfred, Ari E Kahn, John D Medaglia, Jean M Vettel, Michael B Miller, Scott T Grafton, et al. Controllability of structural brain networks, Nature communications, 6(1):1-10, 2015.
Christianne N Heck, David King-Stephens Andrew D Massey, Dilcep R Nair, Barbara C Jobst, Gregory L Barkley, Vicenta Salanova, Andrew J Cole, Michael C Smith, Ryder Gwinn, et al. Two-year scizure reduction adults with medically intractable partial onset epilepsy treated with responsive neurostimulation: final results of the rms system pivotal trial. Epilepsia, 55(3):432-441, 2014.
Ling Huang, Chang-Dong Wang, and Hongyang Chao. ocomm: Overlapping community detection multi-view brain network. /EEE/ACM Transactions on Computational Biology and Bioinformatics, 2019.
Hossein Kassiri, Sana Tonckaboni, M Tariqus Salam, Nima Soltani, Karim Abdelhalim, Jose Luis Perez Velazquez, and Roman Genov, Closed-loop ncurostimulators: A survey and a seizure- peezurepredicttig design example for intractable epilepsy treatment. IEEE trans, biomedical circuits and systems, 1266-1002- 2017.
Fritz Keinert. Course notes: Applied linear algebra. httt::://orion.mmcc.istttttttt.e mmth5077/nctes//aapprrs.. pdf
Jason Z Kim, Jonathan M Soffer, Ari Kahn, Jean M Vettel, Fabio Pasqualetti, and Danielle S Bassett. Role of graph architecture in controlling dynamical networks with applications neural systems. Nature physics, 14 (1):91-98, 2018.
Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti. On mixed memberships and symmetric nonnegative matrix factorizations. In International Conference on Machine Learning, pages 2324 2233, PMLR, 2017.
Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti. Overlapping clustering models, and one (class) svm to bind them all. In Advances in Neural Information Processing Systems, pages 2126-2136, 2018.
Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti. Estimating mixed memberships with sharp cigenvector deviations. Journal of the American Statistical Association, (ust=accceteed):1222 2020.
Sarah Feldt Muldoon, Fabio Pasqualetti, Shi Gu, Matthew Cieslak, Scott Grafton, Jean M Vettel, and Danielle Bassett, Stimulation-based control of dynamic brain networks. PLoS computational biology, 12(9)x1005076 2016.
Gerard O' D'Leary. David M Groppe, Taufik A Valiante, Naveen Verma, and Roman Genov, NURIP: Neural interface processor for brain-state classification and progranmable-waveoom neurostimulation. IEFF Journal of Solid-State State Circuits, 53(1 33(11):3100-3162 2018.
11

---

Under review as a conference paper at ICLR 2022
Fabio Pasqualetti, Sandro Zampieri, and Francesco Bullo. Controllability metrics, limitations and algorithms for complex networks, IEEE Transactions on Control of Network Systems, 1(1):00-52 2014.
Fabio Pasqualetti, Shi Gu, and Danielle $ Bassett. Re: Warnings and caveats in brain controllability. Neurolmage, 197:586-58$ 2019.
Dragana M Pavlović, Bryan RL Guillaume, Emma Towlson, Nicole MY Kuek, Soroosh Afyouni, Petra Vértes, Thomas Yeo, Edward Bullmore, and Thomas E Nichols. Multi-subbeet stochastic blockmodels for adaptive analysis of individual differences in human brain network cluster structure. Neurolmage, 220:
116611, 1, 2020.
M Reza Pazhouhandch, Gerard O'Lrary, liya Weisspapir, David Groppe, Xuan-Thuan Nguyen, Karim Ab- delhalim, Hamed Mazhab Jafari, Taufik A Valiante, Peter Carlen, Naveen Verma, et al. 22.8 adaptively clock-boosted auto-ranging responsive neurostimulator for emerging neuromodulation applications. In 2019
IEEE International Solid-State Circuits Conference-(ISSCC), pages 374-376. IEEE, 2019.
Brittany H Scheid, Arian Ashourvan, Jennifer Stiso, Kathryn A Davis, Fadi Mikhail, Fabio Pasqualetti, Brian Litt, and Danielle Bassett. Time-cvolving controllability of effective connectivity networks during seizure progression. arXiv preprint arXiv:2004.03008 2020.
Ruslana Shulyzki, Karim Abdelhalim, Arezu Bagheri, Tariqus Salam, Carlos M Florez, Jose Luis Perez Velazquez, Peter I. Carlen, and Roman Genov. 320-channel active probe for high-resolution neuromonitoring and responsive neurostimulation. IEEE trans. on biomedical circuits and systems, 9(1 4)),3444,, 2015.
Olaf Sporns and Richard Betzel. Modular brain networks. Annual review of psychology, 67:613 640, 2016.
Peng Gang Sun. Controllability and modularity of complex networks. Information Sciences, 325:20-32, 2015.
Elena Wu- Yan, Richard F Betzel, Evelyn Tang, Shi Gu, Fabio Pasqualetti, and Danielle Bassett. Benchmarking measures network controllability on canonical graph models. Journal of Nonlinear Science, pages 1-39, 2018.
Zhengzhong Yuan, Chen Zhao, Zengru Di, Wen-Xu Wang, and Ying-Cheng Lai. Exact controllability of complex networks, Nature communications, 4(1):1-9, 2013.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
In this appendix, we first provide further detailed explanation for the numerical simulations that was missing due to space constraints. Next we have remark that adds complementary interpretation of the group controllability formula estimated from the learning approach. Finally, we provide proof' for all results stated in our paper.
A.1 MORE ON NUMERICAL SIMULATIONS: HOW TO GENERATE W
For realization of A, we obtain the support of each row of W independently by first generating a random vector {n) using a Dirichlet distribution; larger positive result in greater overlap and more communities, For each community i where T7 > 0, [r- -T&] fine nodes are randomly chosen from V ynon-sel (i.e., non-selected fine indices in community and set as the support of w,- The chosen indices are removed from selected.
V ynon-sel .his process continues until the support of all w,s are
A.2 MORE ON THE ESTIMATED GROUP CONTROLLABILIT USING THE LEARNING APPROACH
VE n supp( H/r (for all k E [K], i E (ml) is the fraction of c-node i's overlap with community k. Thus, from Eq. 15 it follows that 00)
Remark 3. (Synchronization versus controllability) Recall that Pi,k He
group. A x LiE(K]] Dick Yuke In view of this observation and Lemma 2 observe that c-nodes thut have the largest overlup with communities of strongest Y are the most controllable.
Additional notation: For n X m dimensional real matrix M, denote
/ /tr(MMMM M). For a symmetric matrix M, denote Amax(M) be the maximum eigenvalue. (M) [M.,.... Ma.. J R", and Diag(M) sets the off-diagonal entries of M zero.
Useful matrix norm bounds:
1. Let Z = XY. Then, |Z1L S |X XII < <X
2. Cauchy-Schwand inequality: Y) < | p.
3. For any norm: [|M]] [[ (AM-MM--T M| I- M
Keinert).
4. [M]] 20 S V1
5. [M]] S M1|
6. For any m7 matrix M. we have || S Vm |||
7. |MXY|| mmxx < MM| X mmx Y
8. 2 2 < M- M M + [[M']]
Proof. | M 2 = MMM--MM++MM---M WWW----AAAANNNNWWWII/IIMIMMVVMA- <
M M [I + [M]']]
9. -
M)M
Lemma 3. (Lower-Bound Probability of Joint Events:) For the intersection of two events V5, and U2 we have: TP (U,n00s 0 2 P (3,} P (82)
A.3 PROOFS FOR SECTION
5: MOR APPROACH FOR GROUP AVERAGE CONTROLLABILITY
A.3.1 PROOF OF LEMMA
Proof. We prove only the left inequality in Eq. 12 The right inequality in Eq. 12 can be proved using
similar steps. and the details are omitted. Because A A/(c- tr (A)) symmetric, it follows
that pl )
A nom 2. From this observation and the fact that || || < Anamllos oo. we have
P lp m ) 2 B = P |[]]A 2/2 2 3 < P ||| A oo 2 3]
P
[[] cotr(A) (A) 2 0]
(18)
13

---

Under review as a conference paper at ICLR 2022
Let F || cBtr(() and note that E[F] = E E s0 cBtr(A)
|
c A).
The inequality follows because || = g ش a.yl and that E i X,} 2
max. From these observations, inequality in Eq. 18 can be further bounded as
P PF
0]
P
F ス F]]
S P
F
[| Z cBtr(A) - ||A bo]
(19)
We show that F is sub-suusuuaa Gaussian random variable and then bound the right term in Eq. 19 uuinn the well-known concentration inequality results. Rewrite F as follows
12
F max
d1j
a2j
anz
cB(r(A)
j=1
n Σ
m any cstr(A)
max
a1j
c,tr(A)
|2yl ccttr(A),... Σ
j=1
max
fij cBajz):
(2) cBajz),....
ang cBazs)
(20)
In the last equality, drop the absolute values because ai [0, 1]. From the latter fact, also note that (az - agx) E [-c3, 1]. Thus, for all k * 1, (ax d&a) ) is bounded, and hence, sub-Gaussian with parameter at most VI+ /2. Instead, for k = I, (ax - is sub-Gaussian with parameter at most cBl/2. Finally, from Definition notice that each term in the summation Σj= (aks cBazz) is independent. From these facts and the linearity of uub-Gaussians, we note that, for all ls [n). summand
cBasz) is sub-Gaussian with parameter most:
1n (1 + (1-c8)²
Putting all these pieces together in conjunction with the facts that maxima of sub- Gaussians concen- trates near its expectation and cBtr(A)
| loo 2 0 (by assumption), from Eq. 19 we have
P F - F cA) - || [o] < n exp (- (csSrr A)
| (0)l)>22/))) /2/2 | ||x 3 -1-))))))))
< nxep
- 2(cBlr(A)
(21)
The last inequality follows because 2n n1/(11 c,3)2 The left inequality in Eq. 12 follows by
combining inequalities in Eq. 18 and Eq. 21 The proof is now complete.
A.3.2 LEMMA 4 UPPER AND LOWER BOUNDS OF THE TRACE OF THE FINE- AND COARSE-SCALE MATRICES
Lemma 4. (Upper and Lower bounds of the trace of the fine- and coarse-scale matrices). For constants 0 < 8,5 <
P (mppS()) tr(A)) S npnS(w))
2 1 2exp (tr (c)
IP mp 220 80) S tr(A) < mp,
2 1 2 exx
(r(((())))))
P
WAW 2 Pninn m2
(6
2 1 1- 1-exp (-2p m2² ( (22 11,15))))))
P WA1, 2 Caiin Pm
Q (1
1)] 2 - exp
2pp mn Emin Canial | (c) 5)))
(22)
where v is the coarsening resolution parameter (c.f. Eq. 7 and
S() -
& (DQ()) (1++)
(c)
(23)
50 - (r((()))
8,, - (((())
14

---

Under review as a conference paper at ICLR 2022
A.3.3 PROOF OF LEMMA
Proof. From definition, [[]] tr(P' = ((((t((D((t) and B[r(AA] ( (
Using the Hoeffding's s inequality for tail bounding independent random variables, for a constant
< <1
have:
P [[t((A) (p,tr mp.tr(D((s)) S 2exp (( 2exp
-2mph (1r(DQ())))
Scwi 55
(24)
Hence
npn (I tr(A) S np, (T(DQ( +
(25)
C())
((w)
We follow similar steps for A. For all [m]:
Σ
Pik
PiK
Σ
[ Qkk + +
Σ
Dukl
kk
loke
k
kE|K]: 20
(26)
tr ((+) + 2v 2022110001 (1) 1l
((())))))
based on which the following upper and lower bounds on (r()) can be found.
(p(,))r(Q(()) S ir(A) Pr +Q (T)
(c) Okk Dur mp,,t(((())
Pr.
i=1 K,K'((
(27)
can now use Hoeffding's inequality to obtain the tail bound for constant
<
P ( P.tr( (QQ
(c) (c) TT) p. Φ (=)))))) T
s exxp 2(p (0
m
(28)
S 2xxp (
The event in Eq. 28 leads to the following upper and lower bound on tr( (A)):
mp (r((Q(r) (c)) (1 5) S (. - 5) s ur( ({) S p.tr(( (c) + )) + 8) S mp, tr
(() +
6(m)
(29)
We then replacing b(t) d(w) defined in Eq. 29 into Eq. 28 Similarly, event
1WAWT1 >
TΦ
1
2 2 2 m 2 (1, + 8)
(30)
20mm
happens with probability least
1-P | wWWw - < (
> exp
-
111,1) 513
> 1 exp
22
(c) 1)))))2))
(31)
using Assumption 3 and following using one-sided Hoeffding's concentration inequality.
Finally, similar arguments can be applied the following event
1 m WA1, >
1mm ml
P1
2 CminnCinn
Q [11111111111 (1+ +
(32)
(1)
15

---

Under review as a conference paper at ICLR 2022
that occurs with probability at least
1 1 PP [ WAI, PQPI, Cminn (00 [1,1c
(-2 CemCon Q 1)
exp
(-2p2 (Cmin Gmin Cmin
Q ( (1,15)))
exp
(33)
using one-sided Hoeffding's inequality. This concludes the proof.
A.3.4 LEMMA: ERROR BETWEEN THE GRAMIANS OF RANDOM AND EXPECTED LTI SYSTEMS
Let Sime and S coarse denote the expected dynamics of LTI Eq. 9 when A and A are replaced with the expected quantities A and A. The following result provides an error bound between the difference of Gramians of Sūne and S Sine and that of Scoarse and S coarse
Lemma 5. (Error between the Gramians of random and expected LTI systems): Under the assumptions stated in Lemma ! the following holds with probability at least 2 exp (-2mp", (tr((Q(())
[1 I1Q ())
+ p.. Iow
((DQ())
On IC Inxa] - C(A Iaxn) (lxn)llul Mmmax S
Pn = O
c² 32)(())
Pa
(34)
and with probubility least 2exp u2
19 11+ (=M(Que))
Pr. P 60) 1
on IC [A m C(Ā I (mmm Immax
(1))
(((()e)
=0
t0 32) (o aqaan
mp? vr
.p3:v4
(35)
where (supp(wi)] is the homogeneous coarsening parameter.
Note that C(D,I) (I D²)-1 where D can take A nom: A nom- Apom- A Thus, Theorem effectively bounding the difference of resolvents (=I D evaluated at 2 = 1. For n = m, we have 1, 1 and both an and an coincide. Lemma 5 is basically concentration result for the Gramians of Sime (or Scoarse) and Sime (or Scuarse); however the rate at which the difference goes to zero is different for fine- and coarse systems. Further, smaller the stability margin
looser
the bounds in Eq. 34]and and Eq. 35
A.3.5 PROOF LEMMA
We begin by proving the inequality in Eq. 34 From Eq. Eqq.aan and Lemma 1 the limit below exists with the probability stated in the statement of lemma.
C C(Anom- Iaxn) lim Cr Iaxn) = limm +00 ET= (Anom) )' (AT
T-000
(36)
lim TT1 000
(Anom) ) ====1 (I
A2 2um)
The last but equality follows because A is symmetric matrix, A || c ||2 < 3 <1 (follows from the lemma's hypothesis), the last one from the Neumann series formula. Also, we have
A nom ||2 ll c
A 1
P DDDio <1, exnr)
(37)
since PTQ(O) for all E, E [n]. Similarly
C( C(A Inxx) A lim CA Inxx) = (I A
T T-000
nom
16

---

Under review as a conference paper at ICLR 2022
From these observations, establish the following identity (explanations for each step succeeds the equations):
On
CC A Ixx1] C(Anom: Xnx)] I Imaax
[I
(A 12)
(I
(A )
max
(I A
2
A (I
Ag
2
- Illmax
(I
2 ||00
nom
poom Imax || A nom) ) ||1
[I
numn
)-1
||2||A
num
2 max V 71 (I
A nom)
5
A
momm
max A Daa
(c)
11
82 A
A
Aom max
5
S
B2 A
Aom Imax ||| nom max
| [maa
1- 2 (2D
(38)
A max cop
SPalIQ(0 lm inp.t((DDo)
c-t((A)
A max [ +
n A aas Ir(A)
1-33" CEFA
empa S(
tn (e
((Q(9)
(9)
"1 S()
1
ne. RP./QQ
Ant
e.1 M (DQ(
(DQ
[1 +
Q |
1
+ en Q - II
k(DQ
(())
(((Q(())
c2 -(2)(())
2 (DQ
0(1)
00 P
where (f) follow the inequalities itemized at the beginning of the appendix; (c) is because of the assumption in Lemmal Eq. 37 and that:
[I - A nom
- 1|2 < 1/(1- ||A (12) S 1/(1 ||Amamm (12) 11/(1 ;8));
(39)
and the rest of inequalities follow from definitions of Anom, Anom in the paragraphs processing Eq. and Eq. 11
The proof for the inequality in Eq. 35 follows similar lines as above, and hence, provide sketch, but not the full details. From Eq, note that the following
C(Anum Imxm)
lim Cr (Anam; Imxm) limy Et=
Aoom
A
A
T-000
(40)
lim ~T 20
(I - A -1
+00 1 nom
nom
where |
l2 <
1 (from the lemma's hypothesis). Moreover, we have
C( C(Anom Imxm) = (I- A A
where
|| 1|2
Ā
ll2
||2
(41)
(1((A)
ar(
following the fact that ($Q()) $1
17

---

Under review as a conference paper at ICLR 2022
Using these observations, we obtain the following inequality by taking similar steps those for On in Eq. 38 (inner steps are removed due to redundancy):
On
CC (A I (AAnom: mm ( max
$ m |I A 12 (ar(A)
A
A max
[1
m
((A))
las
nom max
A
mux
Am
mpnllQ(e) mpp.vu(((K)))
Pni Q llms
< m 1- mpn (2)
Empa (
)
((A)
IQ PirQ
Or. 11 Ia
S m 1- mpp. (
+
Empp ('1
Emp, (r(
[1 + 11 Im
er Q
(Q(r) 6m2)
ir u((()))
(1 B2 (0(0) aePa(Qrooy )2)
mmp mM
0(1)
0
(42)
The proof is now complete.
A.3.6 PROOF OF THEOREM
The proof of the theorem makes use of Lemma
Let i E [m]] and recall that B; = (iag(w!) and consider the following bound
B, ==ddiag(w From Eq. and Eq. 13
re(s)
@ coarse, A
A A A)
A
Aroup,A -
m
m
(re(1) group.A
(i)
(o))
1)
coarse, Ä
r (i)
rf(a)
group.A
group.A
(r group,A 1)
(ro(1) (1)
group.A - 1)
-A((AAA)
(1)
h
1
coarse Á
(43)
(t)
1)
(1)
-1)
C Ā
Ä
=A((Á.))
r
1
group. A
coarse, Ä
M
group. 1)
-1)
Coarse,
bins A. (A).A)
AA A, A) + bias.
The complete proof of the bound on A, (A, A) will be elaborated in Thm. andd follows:
AA)
[q [1 +
()
(())
+
K (e) (Q |
Emin Cmiin| Q (1+ +)
(1 (2) (F
(c( DQ Imin
[[Dg (2)
Pm
irDq
O(1)
0 mm
(44)
18

---

Under review as a conference paper at ICLR 2022
We now derive an upper bound on (A A).
(
1
(A A)
- 1)
0 roarse, A
1)
Coarse,
TR
(
coarse, A
course.
[0())
1]
coarse,
coarse, A
m
coarse,
course, Ä 1)
0
1)
Coarse,
(
coarse, A - 1)
110
poarse, À
coarse, max
1 m
Σ
(
m
1)
coarse, À
(
1]1
Coarse,
1=1
m 0 11
Ol
+
(
C 1)
coarse, À
(45)
From the equality after Eq. 40 we have
diag, ((I- A nom -11
(46)
coarse. A
Furthermore, since (
T
< 11 then (+Q (c) $ y)2 < 11 =m11
0
1
| A 2
2
Immxx
nom
A
2
m11
Bom
max
2
100
bom
my
A
2
112
(47)
(
nom
mym
A
1|2
imp.u'ir(Q1o))
pom
Similarly
Σ
m
(0(
1)
22 m tr[
1-1
C
tr(A gom
nom
tr noml
(48)
ul( (Q ( +
w + (0) T
m ( (1)))
(EmtriQ(a))
tm y
2 Qq1e]
where all inequalities follow well-known matrix norm axiom. The last line in Eq. Assumption and
48 is based on
vomin mntr E [
2 vomin momp (Q
(49)
m u & tr (((
19

---

Under review as a conference paper at ICLR 2022
similar to the derivation of Eq. 27
since for all lt [K]:
T
kk
tk
2
Σ
ii 2 17
(50)
[m
xE [ml]
We use the definition of 0
coarse, Ä in Eq.
13
Σ
(0()
1)1
diag, (I A A )
coarse, A
tr A 11mm)-111
-
tr A 2
(51)
(A(A
II8e I
(A(
m
2 (1+5)
(1 (1+5) (.))
B(w))
where the inequality (a) in Eq. 51 comes from
tr An(A
A
Σ
Ave
HEKi,
E
AvAAve
Σ
Aut
Σ
AuAree
(52)
EE U,K,
WAE'E or + + EUSK,
w Aw,
W
Q + (1+8) L
mlg
2mm
m Pal
(1 8),
where the event defined in Eq.
30 is used whose corresponding probability is Eq.
31
Replacing Eq.
47
Eq.
48
Eq.
51 and Eq. 42 into Eq.
45 yields:
AA
I pur²
2 (1+5) Q 1011 On
5 )
1
Per }2)
(53)
o
pntt 3 vmm mppi, pi 2 Vmppp
The statement of the theorem follows by invoking Eq. 44 and Eq. 53 into Eq. 43
A ITAJ m(A)
A) bias + O P. +
2
(54)
Vmpa
with joint probability of at least
2 exp
exp (-2ph 22ppr (mmiaaa Q (c) (11111))) (-2np, (tr (DQ
exp (-2m (r - exp (-2p² (22 ||Q (Q())) (1,,1))
(55)
per Lemma We then get the minimum of the four exponents in Eq. 70 The proof now complete.
20

---

Under review as a conference paper at ICLR 2022
A.4 PROOFS FOR SECTION 6 LEARNING APPROACH FOR GROUP AVERAGE CONTROLLABILITY
A.4.1 PROOF OF LEMMA
We start by defining ine. M similar Eq. 10
and Eq. 13 (M will be later substituted with and A),
O fine, M
[tr[C(Mnom ei)
tr tr(C en]]] E R
(56)
Using the Gramian definition in Eq. 2 have:
tr
C CMM ei)l
fine M
ur
M
nom e M
tr tr(M nom C. M
tr(e) M e4)
(57)
diag, (M
nom
o
diag;
M
nom
diag,
M
nom
We first simplify the term 0 A in Eq. 60 by substituting A with QP introduced prior Eq. 6
[tr[C A
nom: e1)]
i O
diag
A
tr BrrC(Anoo en]
= diag(
P QP) (T) = diag
P'Q(
(PPPPP
ntr (tQ(e)
==0
= diag( [ + (Q())
P PP Q (
) /PTT
= diag(/ + DQ
PP (c)
PPT Q P
AD
TTQ())
PP
PP Q(o
-P Q p +...)
HDQ
In (iQ(e) diag (c) DQ [e]
DQ (e)
DQ (c)
DQ (e)
P + .....
DDQ
E(D
ED [e)
DDQ
DQ (+)
m diag
P
P
(D(
(r(DQ(e)
(r(Q()))))
1, (DQ diag P TT(Q())
(F)((Q)),))) D)PP
(a) 1, ner (Q
P o P) (i DD)
1 eD
P diag((1) (T),
(58)
where (a) is due the special structure of P Eq. 4 since for an arbitrary matrix M of appropriate size:
diag, (PTMP)
Σ PR.M PAY= P
Σ
PR.ME PK
K.
KREKK
M = Σ PR,ME
(59)
KEIK = =PP P, (M))
KE[K]
21

---

Under review as a conference paper at ICLR 2022
and (b) is true because P is binary. Replacing Eq. 58 into Eq. 60 yields:
group. W (In ii((DQur)) P (Tdiag(T))) 1 m ((()) Ddiagg (T))
(60)
The proof is now complete.
A.4.2 THEOREM 3 AND PROOF
Define the error metric similar to Eq.
r (i)
r
(A)
group.A
group. A
for all E [m]. (61)
Σ ( (5)
1]
[re()
group.
group.
Theorem 3. (Component wise error bound between O group. A and O A. Let (A(A,)) be defined as above and v be the resolution parameter given by Eq. Under the assumptions stated in Section Band Lemmal [
the following holds:
(Q( Iaw m(DQ(o))
Pa q
(A, V
(i Cain [Q(0] 11.1 (1+ + (1 (3(( (DQ
4(0)
+
m(DQlo)
1+
K (c) DQ max
|| (o) DQ
(
(1
( ( 1 )2)
Pa
mIDQ (0))
O(1)
(62)
with probability least exp (-2R(Q(1) D,
m, n, Pn)), where Further, for a constant 0
Ç the exponent &(Q (c), D.m.n,P min (L)(Q(())))) mmpp Cmin Q (e) (),
A.4.3 PROPOSITION 4 AND PROOF
Proposition 4. (Group Average Controllability for A) The group average controllability vector for
A is
(6) group.M w. W.0fgne.Mr
(63)
Proof. We begin by simplifying the group average controllability using its definition in Eq. and the definition of Gramian in Eq. 2 for a general matrix notation M which can be replaced by either or A:
( = tr CM diag( (w]) [T]]
group.M
tr
M diagg w )diag(w)) (w!) M nom
M diag(( (W; ow) M T
72
tr
M
nom
Σ
e M MM
(64)
r=0
(w.)
tr
M nom C M nom
vEsupp(w.)
Σ
M Mram e e M
DEsupp(w;)
(v)
where (a) is due to the assumption of y-homogeneous W, denotes the Hadamard product, and we have already defined 0 fine.MM M in Eq. 56) Putting Eq. 64 in vector form concludes the proof. I
22

---

Under review as a conference paper at ICLR 2022
A.4.4 PROOF OF THEOREM
Proof.
We start by substituting M into Eg. 63 from Proposition 4
with A and A, yields:
(A,
r
group.A A -1
r (4)
promp, A -1
m
(r)())
(r0(1)
1)
group, A - 1)
group. A
w:Onee.h
w, w.0m A
w, A 1)
w,O Anc. - 1)
Σ Ow,OfineA -1)
w;O Anc.
[ Anc 1]
w; wwrrine - 1)
(w,0 iin.. 1)
m
(w (w;Orie.A. - 1)
w. (w:non -0 Alme,
[w, Winei 1]]
wy Anc.AA 1)
(W,OrincA -
W: Onnc.A)
W: ifnne θ -fiiee A) +
1=1
(w,0ine, - 1]] (w, fine,
w. WiBuneeA - 1)
(w, WrOnnee,A -1)
(O 0 line.A)
(O flnneA)l 31+
ni(QQqaa diag
W. W.Oline 1)
(1) diag(T)
ntr (DQ (c))
w; W 10niie 1 Pine. A
T (0) didg((()
WwOOine, 1)
c (+) (liiia))))))
110 line,A 1 Oune. max +
Otre ml|/0are. A O I
||'0|
m mnn
Iaax
W;Orne.A - 1)
Aamc. Ofine. I|max
luas
7
mm
w. Inne, 1)
On 1
||
[
w. Fino - 1)
(65)
where (a) due to Cauchy- Saucchy-Shwwrtz inequality, a, is defined in Eq. 34 θ 0 A is substituted from Eq. 58 and (b) is the result of the properties of the coarsening matrix Definition 2 We the
23

---

Under review as a conference paper at ICLR 2022
definition of 0 i in Eq. 57
w. nnne, - 1) =
w, didiag
(II
A Amm) )1 I)
==1
1 Wdiag [I
A nom 1ommm1 1)
1m W Wdiag A 2
nom
1m Wdiag A
(A mm Wdlag (A2)
(66)
(A-)((A) 1m WA1,
IVE.
Eum Cinia mend
Q (h+
Euis Guio. 19
PaT
inequality (a) uses the event defined in Eq. Using the definition of in Eq. 16
32 is used whose corresponding probability is Eq. 33
Imx
W
Q (0)
(DQ
DQ )
Ima
()
Q| DQ
(67)
u(DQ )1
[D ( (2)
((1)
|| Imi
( DQ 10)
DQ
DDQic
(Q
-
Iin
Q ( DQ
0 Ilais
(68)
M
(D(
2(1).
where S2(.) is the opposite scaling of O(): write f(m) (2(mm)) iff there exist positive reals co and ma such that [f()] 2 cph((m) for all m 2 mg.
We substitute Eq. 66 and Eq. 34 (with probability Eq 24 into Eq. 65
[1+ [q
pullg
A)
e()it))
#iDgl))
K| DQ
Eain |Q 1
(1-89)Ga)
| (Q(() Ilii
(1-(
Pnm
(DQ
((Q(())
(69)
with joint probability of at least
1 1xp
2-2mp (tr (() - exp (-2p², (
(mmniiininnn Cminl Q
( (1))5)))
(70)
per Lemma We then get the minimum of the two exponents Eq. which concludes the proof.
A.4.5 PROOF OF THEOREM 2
We start by using the triangle inequality for absolute values:
@ group
(4) group.
(A)
7/4
(re())
1)
g -11
grOup
(1)
ro(1) (i)
r0( (1)
< m
group.
A
|+|
group
group.A
m
(ro())
(()
1)
(r(()
1)
(
1)
(rg()) (i)
group.A - 1)
group. A
group.
group
1=1
1=1
i=1
AA(AA)
(A,A)
(71)
24

---

Under review as a conference paper at ICLR 2022
The first term on the RHS of Eq. 71 has already been bounded in Thm 3 Next, bound the second term in Eq. 7 and combine the two bounds at the end.
We substitute
0 group from the output of Algorithm and 0 (+)
group.A from Eq. 60 for T defined in
Eq.
16
For notation simplicity we write T(Q(s) D) Y and ((Q(s), D) as T yields
rg( group. A -1
A)
group
(9 (T)
m
m
(
1)
(rg(1)
group.A 1)
$ (
10 diag(M)
group
$ ( diag (
$ b(0
1 ((dig((
Σ $ ( diag(()
d (i)
diag(M)) (
(72)
We set (1)
(0 + Egg, Q D ED. and r = +
+ E where Eg. Eq and
ED are error matrices of appropriate sizes. Substitution of theses error matrices into Eq. 72 as well as multiple applications of the triangle inequality, gives: (A,
Σ
T ( + E. )diag( E)
(1)1) + Ex diaa)(aaa(rrr + E)
diag(T)
$ (0) diag
diag(T)
ab (
(diag() T) + diag(E)
($(1 + Ex (d)agg((()) + diag(E)
( diag( (T)
( (T)
( diag(Y)
diag F) + mE diag( [.)]
diag (E) + Ex (diag(T) () + diag(E)) (F)]
diag
m
m
( diag(
diag(Y)
diag(E) ()) + m mE (diag (T) + (iag(E))
( Eg ddag((()))) [Eg-
$ diig((T)
$ (1) (idiagg")) (P)
diag(T) (T)
m
$ diag F. + m E.g (diag(M) diag [)]
(1 + E+ 111 + [||E ++
m
max
(4) diag(f)
e diag(T)
(73)
To further simplify Eq. 73 we find upper bounds on the terms inside. ||in have already been bounded in Eq. 67 and Eq. 68 and we have:
The two terms ||]] max and
n m|llding (T)
o (0) didg
(74)
The following inequality holds from the definition of norms:
|E |11 < K Ex max
(75)
25

---

Under review as a conference paper at ICLR 2022
Using Eq. 74 and Eq. 75 the inner term in the last line of Eq. 73 is simplified as:
p 1 diag E) + m E (diag (T) diag( [)]
o 10)
diag E)
Ex (diig (T) t-igg E)]
(i) diag(T)
(8) diag
( diag(?)
==
ma Idlig Billmm
diag( I') Iiiis mnk | mi [ilia T) [|diag| E Ellmd
m.
mi [dag 11mm
Fig Ilees
lan Fillan)
1 Ex max + max
(76)
Replacing Eq. 67
Eq.
68
Eq.
74
Eq.
75
and Eq. 76 into Eq. 73 simplifies it as:
0
(
group.
0 E max + || lmax])
(ro()
(77)
1)
group
group.A A
We now simplify the term || max in Eq.
79
= ||
Ml
( Do
u( (o) )²)-1 Dg
DQ
Do )2) m|
((D
((DQ())
ir DQDQ (oj
|1Q ( DQ (c) "n(Q(t
(Q
)²)-1
nD in iDDQ
DQ (0) (I
(mDQQo)) (
DQ )3)-11
((DQ()
max
(78)
To continue the simplification of || |max we bring the two error matrices Eq and Ep introduced in the statement of the theorem into play:
(Q (c) + Eq)
(D +
(D)(Q = Eq) (Q(*) (DQ - DEq + EpQ + EDEE) DQ +r
(79)
where we define
r Q DEQ EpQ Q EqDQ + EqDEq EqEDQ (6)
EE Eq
(80)
and
(D ED) (Q(4) Eq) DQ(() + DEE + Ep
EDEq
(81)
Replacing Eq. 79
and Eq.
81 into Eq. 78 yields:
F
|1(Q (c) DQ (c)
[ DQl
inD
Q DQ
(e)
DQ
max
((DQ)))
DD
t((Qie)
((Q
max
|Q (c) DQ [[I
DO (e)
(I
DQ
(DQ
rDQ
i[DQie
+r
DQ (c)
Q (c) DQ (c)
(Q
) max
((Q [
DDQe
(DQ
DQ (c)
DQ (c)
Q DQ
2
(QQ
tr
tr(D (e)
+I
((DQ (0) )2)
Do
u(e)
(c) DQ (c) [I
DQ
)2) 121111
i(DQUeT
((Q
max
||Q (c)
DQ
max 6 max + |[] max
(ó (r)
)2) max
((DQ
((DQ
DDQ
ir(e)
(c) DQ (c)
max [I
((QQ
(Q
max
O(Iee
max +
max
+ tr é
O(1e
max
r max
+
mmxx
(82)
26

---

Under review as a conference paper at ICLR 2022
We define another error term:
28
(DQ( + +0)² = (DQ(
+ Σ
(83)
RR- ((0
We then simplify 61 for & 2 1 as:
1
(QQ ir(DQ (r)
22 (DQ(1))2
Immax
max
(tr(DQ(0))2
tr(DQ() (c)
tr (R)
(DQ ) + (1
2 (DQ(o))
|max
((DQ())))
tr (r(D(e)) ()
1
R (r(R)
22 (DQ )))
E=1 (tr(D
tr(DQ(e) (c)
max
II[(1
)²)-1
1|R
tr(R)
28 (DQ()))22
|
())
tr(DQ (3) (DQ
8=1
[I[(1
)2) 1 1j
I()
DQ (c) (c))2) IJ max
(DQQ (n)
(DQ
< [(1
)2) 1]][ + ||[ (DDQ
(R
DQ (2) max
((DQ(
0 R
max
O E
(84)
Similarly, we can rewrite an upper bound on T
max as:
=²
EQ
Q
(c)
ED
Q max
|QQ
(+)
Ep max
EQ Iax
max
max
max
max
max
max
+|
E||
DQ
(c)
EQ
EQ
max
EQ
Ep
Q (c)
max
EQ lmmx
EQ
max
E
max
max
+
EQ
E
E Q
E
max
max
max
max
= 0 [EQ]
Ep
mmax)
(85)
and
|||||ma max
IDEQ + E Q
ED Eq max
[ D max EQ
K
mux
ED
Q (c) max +
ED
mmxx [Q mmxx
(86)
K
Eq
max
ED
max
ED
max
Eq max
O
Eq
max
+
Ep
Imax)
By substituting Eq.
84
Eq.
86
and Eq. 85 into Eq. 82
we get:
|
max
O EQ max + EE mmax).
(87)
Replacing Eq.
87 into the original error in Eq. 79 yields:
((i)
rg(a)
0
Ex
max
+
[Eq
max
+
( group 1)
Σ
(1)
A - 1)
(88)
which happens with the same lower bound probability as in Eq. 70 The proof now complete.
27


Reviews:
[{"review_id": "JjNAGqfzQxw", "reviewer": "Reviewer_SdpL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: It provides a clue about how to infer the global property of network controllability with partial knowledge of the connectome. As interdisciplinary research linking control theory with network science, this work is inspiring with relatively rigorous mathematical support. \n\nWeakness: \n1. The scope is a bit limited for the computer science community. The framework can be described in a more general sense. \n2. Since the network controllability has its application in practice, it would be better if the authors can provide illustrative examples on when such kind of approximation is needed. \n3. Is there any statistical significance for the results shown in Figure 2?\n4. The assumptions on the diagonal elements are not consistent throughout the article. In the case of brain networks, the self-loop does not exist. In the case of the SBMs, the self-loop does exist from the probabilistic assumption. Indeed, the stability of Eqn (11) only requires a parameter to shrink the largest eigenvalues of $\\tilde{A}$, which is unnecessary to be related to $tr(\\tilde{A})$. \n5. Is the result a corollary from the inference on the hidden stochastic block structure?  The two steps of estimating controllability and block structures seem to be isolated with each other. ", "summary_of_the_paper": "This paper studies network controllability with partial knowledge of the network structure. It provides insight into how the controllability can be approximated from the topology. ", "summary_of_the_review": "This paper established a framework for inferring the global controllability measurement based on the community information. The scope might be narrow for the computer science group. But the topic itself is very interesting and lays on the frontier of control theory and network neuroscience fields. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8ERIyyjUDQf", "reviewer": "Reviewer_zMsx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "What is the motivation of studying the controlability problem on SBMs?\n\npage 3: It would be useful to explain Gramian and other background on dynamical systems, since typical ML reviewers\nmight not be completely familiar with the literature\n\nDefinition 1, 3rd line: should be v\\in V'_k. Also in the line right after Definition 1\n\npage 4: what does \"c-nodes can cover the fine graph\" mean? What is the notion of covering here?\n\nThe paper initially discusses partial observability, but it is not clear how that fits into the problem\nformulation\n\nThe use of the term synchronization here seems odd, since this is usually considered in the context of\ndynamical systems. Here it is about coverage of the coarse communities.\n\nWhat is the justification for assumptions 2 and 3?\n\nThe problem statement in section 4 is not at all clear.\n\nRemark 2: \"This assumption is a very weaker condition than asking...\" (needs to be rephrased)\n\nThe experiments section is quite limited. It would be useful to consider other networks as well.\n\nThe use of \"learning\" is not consistent with learning theory, and should be explained better\n\npage 6: \"Broadly, our analysis highlight the role of\" (should be highlights)", "summary_of_the_paper": "The paper studies the problem of controlling the dynamics of a networked dynamical system,\nunder partial observations. Such systems arise in a number of applications, and therefore the\ncontrol problem is important and well motivated.\nThe authors consider a reduced order system from coarse data,\nand derive bounds on the convergence and approximation error for the original dynamical systems model.\nThese are evaluated empirically on a small synthetic dataset", "summary_of_the_review": "The paper is written very poorly, and is hard to follow. Even the problem statement is not clear. The authors study the controlability problem for SBMs. It is not clear how well this is motivated from the applications they mention. The technical contribution is not very clear, and the experimental section is very weak. The fit for ICLR is not very clear", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "6kmXnhigOfN", "reviewer": "Reviewer_AEYY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, I think this is an interesting topic, which has so far received not a lot of attention in the literature. Learning network properties from aggregate descriptions is clearly of relevance in a number of settings.\n\nHowever, I have several reservations about some of the results presented here. \n\nThe motivation in terms of brain networks and linear control system is questionable, I think. Yes, there is a large literature now that uses linear control theory to study brain networks; but the brain is clearly a nonlinear system.\n\nIt seems the authors have neglected that there exists a branch in the literature concerned with \"blind estimation\" of community structure (such as SBMs) and other network properties, which has a very similar flavor to the work presented here. I think this should be discussed in more detail. See, e.g.,\nWai, Hoi-To, et al. \"Blind community detection from low-rank excitations of a graph filter.\" IEEE Transactions on signal processing 68 (2019): 436-451.\nRoddenberry, T. Mitchell, et al. \"Exact blind community detection from signals on multiple graphs.\" IEEE Transactions on Signal Processing 68 (2020): 5016-5030.\nSchaub, Michael T., Santiago Segarra, and John N. Tsitsiklis. \"Blind identification of stochastic block models from dynamical observations.\" SIAM Journal on Mathematics of Data Science 2.2 (2020): 335-367.\n\nFurther, while the choice of the SBM is understandable from a theoretical perspective, from a practical point of view this is highly questionable: SBMs (and graphons) more generally, lead to dense graphs, while in practice we encounter highly sparse graphs. One could at least consider the degree corrected variant of the SBM.\nMoreover, SBMs will not concentrate well in spectral norm in the \"sparse regime\" (node degrees being constant as the number of nodes increases), which is problematic for the setup considered here. \nI think the authors should at least discuss these issues in more detail.\n\nAssumption 4 would merit more discussion -- it seems to a pretty strong assumption.\n\n\nThere are also some flaws in the technical presentation.\n\nThe adjacency matrix of a network has zero diagonal, hence normalizing by the trace is a bad idea -- the authors effectively assume the existence of self-loops here (presumably from the low-rank SBM assumption). For the coarse grained version (which will have self-loops) this is not a problem.\n\nSimilarly, the expression for the expectation of the SBM corresponds to a version in which self-loops are allowed -- though this is not unusual in the literature this should at least be commented upon.\n\nI am not sure that the statement about the controllability for T vs n steps is correct. This is true for continuous time systems, but for discrete time systems it it seems choosing a small T could prevent a system from being fully controllable, which is controllable for T=n.\n", "summary_of_the_paper": "The paper studies the problem of quantifying certain controllability metrics, based on coarse scale observations of a network, which is assume to have community structure. \nThe main contributions are some theoretical characterizations on when and how well this is possible, given the chosen setup.", "summary_of_the_review": "The paper makes progress in an interesting direction: learning of network properties from aggregate observations.\n\nWhat should be improved in a revised version  (see above)\na) the relations to previous work in the literature should be explained more clearly (ideas from concentration of measure, blind community detection and MOR)\nb) a more careful discussion about the SBM and the weaknesses of this modelling assumption should be given.\nc) a number of technical mistakes should be fixed", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of controlling the dynamics of a networked dynamical system, under partial observations, considering a reduced order system from coarse data, and providing approximation bounds and an empirical evaluation.  Reviewers agree it is a borderline paper.  Technical results are nontrivial, and it introduces new questions, but the main contribution is rather narrow and it could be better written.
Decision: Reject