Year: 2021

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 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.

heading: 1 INTRODUCTION
text: 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 to produce a canonical human brain map, our knowledge of the brain as an 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 fine-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 a connectivity induced by an underlying stochastic block model (SBM).
Approximation of high-dimensional (fine-scale) dynamical systems by lower-dimensional (coarsescale) ones is known as “model order reduction” (MOR) in the controls literature. There is a key difference in assumptions that differentiate our setting from that literature. In MOR the starting point is a complete description of the high-dimensional system. The task is to formulate a lower-dimension system, the dynamics of which well-approximate those of the full system. In contrast, we start from 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 a generative SBM). One might think of the
distinction as 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, so 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 et al., 2013). Herein we assume that we both measure and actuate a 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 to 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-usable 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-order system based on the coarse data, and use the average controllability vector of this system to approximate that of the fine-scale system. We derive a tight upper bound on the “approximationerror” 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 a function of the synchronization between the coarse summary data and the underlying community structure. If 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 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.

heading: 2 BACKGROUND / RELATED WORK
text: Coarsened SBM as a generative process: 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 (Abbe, 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 real-world networks, including brain networks is, at least empirically, known to have community structure across various spatial scales (Sporns and Betzel, 2016; Pavlović 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., 2020; Funke and Becker, 2019; Abbe, 2017).
Complex networks controllability: The development of control methods for complex networks is a 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., 2018; 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 a group of nodes. In this paper we consider a 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.

heading: 3 PRELIMINARY NOTIONS
text: Notation: We denote vectors and matrices using bold faced small and upper case letters. The n dimensional all-ones and -zero vectors are denoted by 1n and 0n. For M = [Muv] ∈ Rn×m, define ‖M‖∞ = max1≤u≤n ∑m v=1 |Muv|; ‖M‖max = maxu,v |Muv|; and ‖M‖2 = √ λmax(MTM). Let m = n, then define the spectral radius by ρ(M) = maxi{|λi|}; diag(M) = [M11, . . . ,Mnn]T ∈ Rn; and Diag(M) sets the off-diagonal entries of M to zero. For matrices M′is with arbitrary dimensions, BlkDiag(M1, . . . ,Md) denotes the block diagonal matrix. The inequality M1 ≤M2 implies element wise inequality. We write f(n) = O(h(n)) iff there exist positive reals c0 and n0 such that |f(n)| ≤ c0h(n) for all n ≥ n0. The support of a vector, supp(m), is the set of indices i such that mi 6= 0. The cardinality of a set V is denoted by |V|. For a positive integer m, we denote [m] , {1, . . . ,m}. 1(m) returns a vector of same size with non-zero replaced by 1.
Networks: A network is defined by an un-directed graph G , (V, E), where the node set V , {1, . . . , n} and edge set E ⊆ V × V . For an edge (u, v) ∈ E , assign the weight Auv = Avu ∈ R, and define the weighted symmetric adjacency matrix of G as A , [Auv], where Auv = Auv = 0 whenever Auv /∈ E . A random network is an un-directed graph with a random adjacency matrix.

heading: 3.1 LINEAR DYNAMICAL SYSTEM ON RANDOM NETWORK
text: For a network G with n nodes and the symmetric adjacency matrix A, associate a state xi[k] ∈ R to the i-th node, and let the nodes evolve with the linear and time-invariant (LTI) dynamics 1:
x[t+ 1] = 1
c · tr(A) Ax[t] + Bu[t], ∀ t = 0, 1, . . . . (1)
The state x[t] = [x1[t], . . . , xn[t]]T is steered to an arbitrary value by an input u[t] ∈ Rn. Here, the input matrix B = Diag(b) ∈ Rn×n, where b ∈ {0, 1}n determines which components of u[t] enters the network2. For e.g., for B = Diag(1n1 ,0n−n1), the input enters the network through control nodes set K = {1, . . . , n1}. The normalization c · tr(A) factor, with appropriately chosen constant c > 0, ensures that system in Eq. 1 is asymptotically stable. Finally, we define Anom , 1c·tr(A)A for the normalized matrix, and use this convention throughout the paper.
For fixed system matrix Anom, a necessary and sufficient condition for the asymptotic stability3 of Eq. 1 is that ρ(Anom) ≤ 1. For random Anom, we consider the probabilistic stability: P[ρ(Anom) ≤ 1]—the 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 P[ρ(Anom) ≤ 1]. The networked LTI system in Eq. 1 is T-step controllable if x[0] = 0 can be steered to any target state x ∈ Rn for some inputs: u[0], . . . ,u[T − 1]. The T -step controllability Gramian of Eq. 1 given below, among other things, allows us to study if Eq. 1 is controllable or not.
CT (Anom,B) = ∑T−1 t=0 (Anom) tBBT(Anom) t. (2)
By definition CT (Anom,B) 0, and it is well known that G with n nodes is T -step controllable if n-step controllable; or equivalently, CT (Anom,B) 0. For other interesting properties of Eq. 2 we refer to (Chen, 1999). For the simplicity of exposition, we let T →∞ and consider the infinite time horizon Gramian: C(Anom,B) = limT→∞ CT (Anom,B), which exists with 1 − P[ρ(Anom) ≥ 1]; see also Pasqualetti et al. (2014). We drop the notation (Anom,B) in C when the context is clear. Average energy: A widely used metric to measure how hard or easy it is to control the network is average energy: ∫ ‖x‖2=1 x TC†x dx/ ∫ ‖x‖2=1 dx, which evaluates to n
−1tr(C†) (Cortesi et al., 2014). Here, where C† is the pseudo inverse, and xTC†x is the minimum control energy needed to steer x[0] = 0 to an arbitrary target state x ∈ Rn. Thus, average energy measures the minimum control energy required to steer x[0] = 0 to an arbitrary state uniformly distributed over the unit sphere.
1 One may think our LTI model as the linearized system of an underlying non-linear system. Controllability of non-linear systems require a case by case analysis and we leave this topic for future research.
2Alternatively, Bu[t] = BKuK[t], where BK is the sub-matrix of B whose columns are indexed byK ⊂ [n]. However, we stick with notation in Eq. 1 to make our analysis less cumbersome.
3The LTI system Eq. 1 is asymptotically stable if ‖x[t]‖2 → 0 as t→∞, for u[t] = 0 and x[0] 6= 0.
Average controllability: Numerical computation of C† for large-scale networks is demanding. Owing to the fact that tr(C†) ≥ 1/tr(C), one uses tr(C)—called the average controllability—as a proxy for average energy Gu et al. (2015). The higher the average controllability is for a given set of control nodes defined by B, the smaller their average energy, thus higher their influence on the network.

heading: 3.2 STOCHASTIC BLOCK MODELS
text: Stochastic block models (SBMs) are probabilistic models that produce random graphs with planted communities. Formally, let Gfine , (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 SBM(n,Q,p), the graph Gfine is partitioned to K disjoint sub-graphs (or communities) of relative sizes p = [p1, . . . , pK ] such that V = ∪Kk=1Vk. Two nodes u ∈ Vk and v ∈ Vk′ are joined by an edge with the weight Auv ∈ {0, 1}, which is drawn with probability Qkk′ independently from other edges, for all k, k′ ∈ [K].
In General SBM, the probability distribution of weights Auv is common for all u ∈ Vk and u ∈ Vk′ . The general SBM(n,Q,p) thus generates a weighted symmetric graph with K communities with non-identical in- and cross-edge connection probabilities given by Q ∈ [0, 1]K×K . Alternatively,
Auv ∼ Bernoulli(Qk,k′) if k, k′ ∈ [K] : Pku > 0,Pk′v > 0, (3)
where the community membership matrix P = [Pkv] ∈ RK×n is given by PPT = Diag (|V1|, . . . , |VK |) with Pkv = {
1 if v ∈ Vk, 0 otherwise. (4)
We define D , 1nPP T which is a diagonal matrix of relative community sizes. Definition 2. (Coarse SBM Ghoroghchian et al. (2021)) Define a coarse-scale summary to A as
Ã , WAWT ∈ Rm×m, (5)
where the coarsening matrix W ∈ Rm,n is (a) r-homogeneous, for all i ∈ [m]; that is, each i-th row of W (say wi) has r non-zero terms and all rows have constant row sum and (b) (WWT = 1r Im).
Here, Ã can be interpreted as the symmetric adjacency matrix of an un-directed graph Gcoarse with m nodes— referred to as coarse graph. This interpretation is helpful when we discuss LTI system associated with Ã in Section 5. We refer the nodes in Gcoarse to as c-nodes4 as opposed to the fine nodes in Gfine. Note that r ≤ nm , 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. 1). The main goal of our paper is to quantify controllability of Gfine, with community structure, using the coarsely inferred network Gcoarse. Importantly, we do not have access to 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̄ , E[A] and ¯̃A , E[Ã] can be computed as
Ā = PTQP and ¯̃A = (WPT)︸ ︷︷ ︸ Φ Q(WPT)T, (6)
where Φ ∈ Rm×K is the coarse community membership matrix, and Φik captures the extent to which the i-th c-node overlaps with the k-th community. Let us also define the resolution parameter.
ν , min i∈[m],k∈[K]:Φik>0 Φik. (7)
By definition 1/r ≤ ν ≤ 1. In what follows, we assume that a c-node has a constant minimum overlap (i.e. ν) with each community that independent of other system parameters.
The example below will highlight the structural differences among matrices P, Φ, and W. Example 1. For fine network shown in Fig. 1, the following hold
4“c-” stands for compound or coarse.
1. P = BlkDiag(1T12,1 T 18,1 T 6 ). Here, 1d is the d-dimensional all-ones column vector.
2. Φ = [ΦT1 ,Φ T 2 , · · · ,ΦT6 ]T, where Φ1 = [1, 0, 0]; Φ2 = [ 23 , 1 3 , 0]; Φ3 = Φ4 = [0, 1, 0];
Φ5 = [0, 1 3 , 2 3 ]; and Φ6 = [0, 0, 1].
3. Finally, each row of the coarsening matrix W has three non-zero entries, all equal to 1/3.
Each c-node in {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 ∈ [K], we have 0 < cmin ≤ |Vk|n ≤ cmax < 1, where cmin, cmax are constants. There exists a ρn ∈ (0, 1) and a non-negative matrix Q(c), such that
Q = ρnQ (c), (8)
Assumption 2. (Fully-Synchronized c-node): The coarse graph has at least one pure node per community k ∈ [K]. Formally, for all k ∈ [K], there exist a coarse node i ∈ [m] such that Φik = 1. Assumption 3. (Uniform Coarsening): There exist c̃min and c̃max independent of m such that c̃min1K ≤ 1TmΦ/m ≤ c̃max1K .
We also assume that communities have self-connections, that is, tr(Q(c)) > 0, and Qc ≤ 1K×K . Assumption 1 helps us uniformly control the sparsity of connection in and cross communities. For several real-world networks, ρn typically decreases with n Abbe (2017). Assumption 2 states that for each community there exist at least one c-node that is fully inside one community. We call such c-node fully synchronized (see Remark 1). Finally, Assumption 3 ensures that the relative coverage of each community measured by coarse nodes scales linearly with respect to the graph size.
Remark 1. (Synchronization of community and coarsening): The coarsening operation is oblivious to the community structure in Gfine. Thus, the i-th c-node contains information about multiple communities if supp(Wi,:) ∩ supp(Pi,:) 6= ∅ (the subscript denotes the i-th row), for i 6= j. Perfect synchronization: A special case where the intersection is non-empty only when i = j. This happens when all the communities have the same size and each c-node covers only one whole community.

heading: 4 PROBLEM STATEMENT
text: Consider the LTI system on the network Gfine, defined by the symmetric adjacency matrixin A Eq. 3: Sfine : x[t+ 1] = Anomx[t] + BKu[t], (9)
where Anom , 1c·tr(A)A, A ∈ R n×n, and BK ∈ Rn×n selects a set of control nodes K ⊂ Gfine. Depending on the controllability properties of Gfine (see, Section 3.1), the inputs at these |K| control nodes may or may not effect all the states in x[k]. Let Ki = supp(wi), be the set (hereafter, group) of r nodes coarsened by wi. The following assumption states that Gfine is controllable from all Ki ⊂ Gfine; see Remark 2.
Assumption 4. Let BKi = Diag(wTi ). For any i ∈ [m], the Gramian C(Anom,BKi) is full rank.
As ρ(Anom) < 1 holds with high probability (see Lemma 1), it follows that C(Anom,BKi) exits, and hence, the infinite time Gramian C(Anom,BKi) exists. Assumption 4 ensures that average energy (see Section 3.1) is finite; however, average controllability need not be finite.
For Ki-th control node set with input matrix BKi = Diag(wTi ), associate the average controllabity measure: θ(i)group,A , tr[C(Anom,BKi)], for all i ∈ [m]. Since C(·) is a p.s.d matrix, it follows that θ
(i) group,A ≥ 0. Accordingly, define the group average controllability vector for Sfine: θgroup,A , ( θ (1) group,A, . . . ,θ (m) group,A ) ∈ Rm, (10)
which summarizes the average controllability measure (see Sec 3.1) for all control nodes sets {K1, . . . ,Km}. Thus, θgroup,A helps infer (i) Kis that drive the network to the desired target state with least control effort, and (ii) if such control node sets should have a community structure.
In this paper, using only the knowledge of Ã in Eq. 5, we want to estimate the random vector θgroup,A in Eq. 10. We consider two contrasting approaches: (i) the traditional model order reduction (MOR), where we rely upon the reduced order auxiliary system Scoarse (see Eq. 11) governed by Ã to infer θgroup,A; and (ii) the learning based approach, where we directly estimate θgroup,A using a clustering based mixed membership community learning algorithm; see Section 6. Fig. 1 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 A is a random matrix. Remark 2. (Group nodes controllability) Assumption 4 demands that a group of nodes should be able to control Gfine, which holds true for brain networks (Pasqualetti et al., 2019). This assumption is a very weaker condition than asking Gfine to be controllable from every single node. Moreover, if Gfine is not controllable from the control nodes, we can decompose the state-space of Gfine into controllable and uncontrollable sub-spaces (Chen, 1999), and adapt our analysis to the controllable sub-space.

heading: 5 MOR APPROACH FOR GROUP AVERAGE CONTROLLABILITY
text: We provide a tight upper bound on the element wise error between θgroup,A in Eq. 10 and θcoarse,Ã in Eq. 13. The latter quantity is the group average controllability vector of the reduced order system:
Scoarse : x̃[t+ 1] = Ãnomx̃[t] + B̃u[t] , (11)
where Ãnom , 1c̃·tr(Ã)Ã , Ã = WAW T is given by Eq. 5 and the normalization factor c̃ · tr(Ã) is used for stability purposes, where c̃ > 0. Importantly, the state x̃[t] ∈ Rm is not a compression of the true state x[t] in Sfine 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 B̃u[t] ∈ Rm. The following lemma states that Sfine and Scoarse are asymptotically stable with very high probability. Thus, θgroup,A in 10 and θcoarse,Ã in 13 are well defined. Let c, c̃, β ≥ 0, and define the stability indices: κnom := (cβ tr(Ā)−‖Ā‖∞)/(n(1−cβ)2) and κ̃nom := (c̃β tr( ¯̃ A)−‖ ¯̃A‖∞)/(m(1−rc̃β)2), where Ā ∈ Rn×n and ¯̃A ∈ Rm×m are given in Eq. 6 and r is the coverage size. Lemma 1. (Probabilistic stability of Sfine and Scoarse): Suppose that the stability indices κnom and κ̃nom are strictly positive for some constants c, c̃ > 0, and 0 ≤ β < 1. Then,
P [ρ(Anom) ≥ β] ≤ n exp (−2κnom) and P[ρ(Ãnom) ≥ β] ≤ m exp (−2κ̃nom) . (12)
For m = n, we have r = 1, and hence, the probabilistic inequalities in Eq. 12 coincide with each other. Further, the higher κnom and κ̃nom, the higher the chance that Sfine and Scoarse are stable. Interestingly, κnom and κ̃nom do not explicitly scale with n and m. In fact, κnom ≥ κnom, lb, where
κnom, lb := (cβ cmin tr(Q) − cmax ‖Q‖∞)/(1 − cβ)2 is independent of n. Thus, stability is not guaranteed for larger networks modeled using Sfine with c · trA normalization. Instead, κnom, lb →∞ as cβ → 1, thereby P [ρ(Anom) ≥ β] ≤ n exp(−2κnom, lb)→ 0. So, under what conditions κnom > 0 for cβ = 1? One such condition is cβ ≥ cmax ‖Q‖∞/(cmin tr(Q)). Let cmax = cmin . For diagonally dominant probability matrix Q (i.e., the community structure is assortative—more in-community edges than across-community edgess), tr(Q) ≥ ‖Q‖∞, and hence, we can choose c and β such that cβ = 1. However, non diagonally dominant matrices can satisfy tr(Q) ≥ ‖Q‖∞. For example, a symmetric matrix Q ∈ R3×3, with Qii = 0.2, Q12 = 0.25, and Q13 = 0.01 is not diagonally dominant because Qii ≤ ∑ j 6=i Qij , for all i, but tr(Q) ≥ ‖Q‖∞.
We now bound the difference between θgroup,A in 10 and θcoarse,Ã in 13. Let Ãnom , Ã/(c̃ · tr(Ã)) and B̃i = rWdiag(wTi )—the coarsened input matrix. Let the average controllability for the i-th c-node be θ(i)
group,Ã ,tr[C(Ãnom, B̃i)]≥0. Define the average controllability vector for Scoarse: θcoarse,Ã , ( θ (1) coarse,Ã , . . . ,θ (m) coarse,Ã ) ∈ Rm. (13)
In what follows, when the synchronization holds, we show that θcoarse,Ã associated with Scoarse can well approximate θgroup,A associated with Sfine. Define the error metric:
∆i(A, Ã) , ∣∣∣∣∣∣ rθ (i) group,A − 1∑m
i=1[rθ (i) group,A − 1]
− θ
(i)
coarse,Ã − 1∑m
i=1[θ (i) coarse,Ã − 1] ∣∣∣∣∣∣ , for all i ∈ [m]. (14) The proposed error metric ∆i(A, Ã) allows us to do a fair shifting- and scaling-free comparison between the vectors θgroup,A and θcoarse,Ã. The shift factor "-1" accounts for the inherent "+1" shift in the average controllability definition and the scale factor r discounts the 1/r factor in θgroup,A. Akin to ∆i(A, Ã) in Eq. 14, define ∆i(Ā, ˜̄A) associated with the expected quantities Ā and ˜̄A. Theorem 1. (Element wise bound on θgroup,A−θcoarse,Ã): Let ∆i(A, Ã) and ∆i(Ā,
˜̄A) be defined as above. Then, under the assumptions in Lemma 1, ∆i(A, Ã) ≤ ∆i(Ā, ˜̄A) +O ( 1ρnm + r2√mρ3n) with probability at least 1− 6 exp(−2κ(Q(c),D, ν,m, n, ρn)), where, for constants 0 < δ, ζ < 1,
κ(Q(c),D, ν,m, n, ρn) = min { nρ2n(tr(DQ (c))ζ)2, m(ρnν 2tr(Q(c))δ)2
ρ2nmn(c̃mincmin||Q(c)||1,1ζ)2, ρ2nm2(c̃2min||Q(c)||1,1δ)2 } ,
with ν, D, and Q(c) given by Eq. 7, Eq. 4, and Eq. 8, and c̃min is defined in Assumption 3. Theorem 1 says that ∆i(A, Ã) ≈ O (
1 ρnm
+ r 2
√ mρ3n
) provided ∆i(Ā, ˜̄A) is small. Thus, for fixed n,
MOR based estimate θcoarse,Ã approximates θgroup,A if the graph density ρn or number of c-nodes is large, which we validate using numerical simulations as well. It can be shown that the bias term ∆i(Ā,
˜̄A) is exactly zero if the communities are synchronized with the coarsening process (see Remark 1) and that Qii = p > 0 and Qij = q > 0, for i 6= j.

heading: 6 LEARNING APPROACH FOR GROUP AVERAGE CONTROLLABILITY
text: We present our learning based approach to estimate θgroup,A in Eq. 10. Unlike the MOR based approach that relies on Sfine, we directly estimate elements in θgroup,A based on 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 (Mao et al., 2020) which is not only numerically efficient but also has strong theoretical guarantees. Lemma 2. Let θgroup,Ā be obtained by replacing A with the expected matrix Ā in θgroup,A, given by Eq. 10. Let P and Φ be as in Eq. 4 and Eq. 6. Suppose that Assumption 1 hold. Then,
θgroup,Ā = (1m + dΦdiag(Υ)) /r, (15)
where d = 1/(ntr[DQ(c)]), D = (1/n)PPT, and Q(c) is given by Eq. 8, and
Υ , (nd)Q(c)DQ(c)[I− ((nd)DQ(c))2]−1. (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 3 (see Appendix) shows that ∆i(A, Ã) ≤ , for arbitrary > 0, hold with high probability. In view of this fact, we propose our candidate estimator as
θ̂group , 1m + Φ̂diag(Υ̂), (17)
where Υ̂ , Q̂D̂Q̂ tr(D̂Q̂) (I− ( D̂Q̂ tr(D̂Q̂) )2)−1. The hatted quantities Φ̂ and Q̂ are obtained from Algorithm5
2, which takes as input Ã and number of communities K. Instead, we obtain D̂ from Algorithm 1. Importantly, θ̂group in Eq. 17 is obtained from coarsened matrix Ã but not the fine scale matrix A.
Theorem 2. (Component wise error bound between θ̂group and θgroup,A): Suppose that there exist constants c̃min and c̃max that satisfy Assumption 3. Then, under the hypotheses stated in Lemma 1,∣∣∣∣∣ rθ (i) group,A − 1∑m
i=1(rθ (i) group,A − 1)
− θ̂ (i) group − 1∑m
i=1(θ̂ (i) group − 1) ∣∣∣∣∣︸ ︷︷ ︸ ,∆̂i(Ã) =O ( 1 m [ 1 ρn + ||EΦ||max + ||EQ||max + ||ED||max] )
holds with probability at least 1−3 exp(−2κ̂(Q(c),D,m, n, ρn)), where EΦ , Φ̂−Φ, EQ , Q̂−Q, and ED , D̂ − D are the error matrices. Further, for a constant 0 < ζ < 1, the exponent κ̂(Q(c),D,m, n, ρn) = min { nρ2n(tr(DQ (c))ζ)2, mnρ2n(c̃mincmin||Q(c)||1,1ζ)2 } .
Theorem 2 suggests that for sufficiently large m, the estimate θ̂group approximates θgroup,A to an arbitrary precision if: (a) the graph is dense enough (larger ρn), (b) the coarse community membership matrix is well estimated (smaller6 ||EΦ||max), (c) the cross-community probability estimation do not suffer from high error (smaller ||EQ||max), and the relative community sizes estimated from the coarse graph are close the ones in the fine graph (smaller ||ED||). The result of Theorem 2 is important because one can directly infer the most influential control node set Ki (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 Φ̂ and Q̂ from Algorithm 2, and the number of communities K 1: compute D̂ = diag( Φ̂
T1m 1KΦ̂T1m ) 2: return θ̂group = 1m + Φ̂diag ( Q̂D̂Q̂
tr(D̂Q̂) (I− ( D̂Q̂ tr(D̂Q̂) )2)−1) ) 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 Ã as V̂ Λ̂V̂ T and set Spruned = Prune(V̂ ) 2: set X = V̂ ([m]\Sp.runed, :) and compute Spure = Successive Projection Algorithm(XT) 3: set Xpure = X(Spure, :) and compute un-normalized Φ̂un-nom = V̂ X−1pure 4: Φ̂un-nomik ← 0 if Φ̂un-nomik < e−12,∀i ∈ [m], k ∈ [K] 5: return Φ̂ = Diag−1(Φ̂un-nom1K)Φ̂un-nom and Q̂ = XpureΛ̂XTpure
5This MM algorithm adapted from Mao et al. (2020) is a type of spectral clustering method that first performs eigen decomposition of Ã to find the overlapping membership (Φik) of the fine nodes. A pruning step is also included (see steps 4 and 5 in Algorithm 2) to speed up the algorithm performance.
6 (Mao et al., 2020) showed that ||EΦ||max and ||EQ||max stated in Theorem 2 approach zero under some conditions, as m→∞. But these conditions might not be applicable to our setup because of our coarsening operation. However, our simulations show that ∆̂i(Ã) decreases with m. The behavior of ||EΦ||max and ||EQ||max with respect to graph scaling is left for future work.

heading: 7 SIMULATIONS
text: We validate our theoretical results by plotting7 the errors 1m ∑m i=1 ∆i(A, Ã) and 1 m ∑m i=1 ∆̂i(Ã) and show that these errors are comparable to the bounds we obtained in Theorems 1 and 2. We generate A∼ SBM(n,Q,p) and then determine Ã = WAWT (see Supplemental material for generating W). We set number of fine nodes n = 5000, the overlap parameter η = 0.1, and the number of communities K = 5. Finally, for Q ∈ RK×K , we set Qkk = p = 0.05 and Qkk′ = q = 0.01 (for k 6= k′). If not specified, the number of c-nodes m = 100 and coverage size per c-node r = 4. Fig. 2(a)-2(d) illustrate the qualitative behavior of the errors with respect to changes in m, ρn, and the degree of (non-)synchronization in coarse nodes (i.e., η), and r. To fairly compare these errors,
we also consider a base line error: ∑m i=1 | µi−1∑m i=1(µi−1) − rθ (i) group,A −1∑m i=1(rθ (i) group,A −1) |/m, where µ ∈ [1, 2]m
contains i.i.d. uniform random variable drawn independently of Ã.

heading: 8 CONCLUSION AND FUTURE WORK
text: 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 of fine- and coarse-network sizes, graph density, and community synchronization bias (see Remark 1 in 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 on the controllability of brain networks.
7The Python code to reproduce the results is attached to the submitted file.

heading: 9 ETHICS STATEMENT
text: 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 a result of estimating the network group average controllability, may motivate manipulative actions; i.e. the most influential node group may be selected for control, in order to steer the whole network towards an unethical goal (like manipulating individuals in a social network to vote in favour of a particular election candidate). The negative impact may also result in bias against less-influential nodes, as they will be ignored when it comes to the selection of node groups for control actuation.

heading: 10 REPRODUCIBILITY STATEMENT
text: All the results presented in this paper are reproducible. The theoretical findings are annotated and step-by-step elaborated in the appendix. The data generation process and the parameter values used for numerical simulations are fully explained. In addition, the Python code from which the simulation figures are generated is attached to the submission files. The code is also on Github and the repository will go public upon submission acceptance.

heading: A APPENDIX
text: In this appendix, we first provide further detailed explanation for the numerical simulations that was missing due to space constraints. Next we have a remark that adds complementary interpretation of the group controllability formula estimated from the learning approach. Finally, we provide proofs for all results stated in our paper.

heading: A.1 MORE ON NUMERICAL SIMULATIONS: HOW TO GENERATE W
text: For a realization of Ã, we obtain the support of each row of W independently by first generating a random vector π ∈ {η}K using a Dirichlet distribution; larger positive η result in greater overlap and more communities. For each community k where πk > 0, br · πkc fine nodes are randomly chosen from Vnon−selk (i.e., non-selected fine indices in community k) and set as the support of wi. The chosen indices are removed from Vnon−selk .This process continues until the support of all wis are selected.

heading: A.2 MORE ON THE ESTIMATED GROUP CONTROLLABILITY USING THE LEARNING APPROACH
text: Remark 3. (Synchronization versus controllability) Recall that Φi,k = |{v : v ∈ Vk ∩ supp(wi)}|/r (for all k ∈ [K], i ∈ [m]) is the fraction of c-node i’s overlap with community k. Thus, from Eq. 15, it follows that θ(i) group,Ā ∝ ∑ k∈[K] Φi,kΥkk. In view of this observation and Lemma 2, we observe that c-nodes that have the largest overlap with communities of strongest Υkk are the most controllable.
Additional notation: For n×m dimensional real matrix M, denote ‖M‖F = √∑
u ∑ v M 2 uv =√
tr(MTM). For a symmetric matrix M, denote λmax(M) to be the maximum eigenvalue. diag(M) = [M11, . . . ,Mnn]
T ∈ Rn, and Diag(M) sets the off-diagonal entries of M to zero. Useful matrix norm bounds:
1. Let Z = XY. Then, ‖Z‖F ≤‖X‖2‖Y‖F ≤‖X‖F ‖Y‖F . 2. Cauchy-Schwartz inequality: tr(XTY) ≤ ‖X‖F ‖Y‖F . 3. For any norm: If ||M|| < 1⇒ ||(I−M)−1|| < 11−||M|| (Keinert). 4. ‖M‖∞ ≤ √ n‖M‖2 5. ‖M‖1 ≤ √ n‖M‖2 6. For any m× n matrix M, we have ‖M‖2 ≤ √ m‖M‖∞.
7. ‖MXY‖max ≤ ‖M‖∞‖X‖max‖Y‖1 8. ||M2 −M′2|| ≤ ||M−M′||(||M||+ ||M′||)
Proof. ||M2−M′2|| = ||M2−MM′+MM′−M′2|| = ||M(M−M′)+(M−M′)M′|| ≤ ||M−M′||(||M||+ ||M′||)
9. M−1 −M′−1 = M−1(M′ −M)M′−1
Lemma 3. (Lower-Bound Probability of Joint Events:) For the intersection of two events f1 and f2 we have: P {f1 ∩ f2} ≥ P {f1}+ P {f2} − 1.

heading: A.3 PROOFS FOR SECTION 5: MOR APPROACH FOR GROUP AVERAGE CONTROLLABILITY

heading: A.3.1 PROOF OF LEMMA 1
text: 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 Anom = A/(c · tr(A)) is symmetric, it follows that ρ(Anom) = ‖Anom‖2. From this observation and the fact that ‖Anom‖2 ≤ ‖Anom‖∞, we have
P [ρ(Anom) ≥ β] = P [‖Anom‖2 ≥ β] ≤ P [‖Anom‖∞ ≥ β] = P [‖A‖∞ − cβtr(A) ≥ 0] . (18)
Let F = ‖A‖∞ − cβtr(A) and note that E[F] = E‖A‖∞ − cβtr(Ā) ≥ ‖Ā‖∞ − cβtr(Ā). The inequality follows because ‖A‖∞ = maxi∈[n] ∑n j=1 |aij | and that E[max{X1, . . . , Xt}] ≥ max{E[X1], . . . ,E[Xt]}. From these observations, inequality in Eq. 18 can be further bounded as
P [F ≥ 0] = P [F− E[F] ≥ −E[F]] ≤ P [ F− E[F] ≥ cβtr(Ā)− ‖Ā‖∞ ] . (19)
We show that F is a sub-Gaussian random variable and then bound the right term in Eq. 19 using the well-known concentration inequality results. Rewrite F as follows
F = max  n∑ j=1 |a1j |, n∑ j=1 |a2j |, . . . , n∑ j=1 |anj | − cβtr(A) = max
 n∑ j=1 |a1j | − cβtr(A), n∑ j=1 |a2j | − cβtr(A), . . . , n∑ j=1 |anj | − cβtr(A)  = max
 n∑ j=1 (a1j − cβajj), n∑ j=1 (a2j − cβajj), . . . , n∑ j=1 (anj − cβajj)  . (20) In the last equality, we drop the absolute values because aij ∈ [0, 1]. From the latter fact, we also note that (akl − akk) ∈ [−cβ, 1]. Thus, for all k 6= l, (akl − akk) is bounded, and hence, sub-Gaussian with parameter at most √ 1 + (cβ)2/2. Instead, for k = l, (akl − akk) is sub-Gaussian
with parameter at most |1− cβ|/2. Finally, from Definition 1, notice that each term in the summation∑n j=1(akj − cβajj) is independent. From these facts and the linearity of sub-Gaussians, we note
that, for all k ∈ [n], summand ∑n j=1(akj − cβajj) is sub-Gaussian with parameter at most:
σ = 1
2
√ (n− 1)(1 + (cβ)2) + (1− cβ)2.
Putting all these pieces together in conjunction with the facts that maxima of sub-Gaussians concentrates near its expectation and cβtr(Ā)− ‖Ā‖∞ ≥ 0 (by assumption), from Eq. 19, we have
P [ F− E[F] ≥ cβtr(Ā)− ‖Ā‖∞ ] ≤ n exp ( −(cβtr(Ā)− ‖Ā‖∞)2/2σ2 ) ≤ n exp ( −2(cβtr(Ā)− ‖Ā‖∞)2/(n(1− cβ)2) ) . (21)
The last inequality follows because 2σ2 ≥ n/2(1− cβ)2. The left inequality in Eq. 12 follows by combining inequalities in Eq. 18 and Eq. 21. The proof is now complete.

heading: A.3.2 LEMMA 4:UPPER AND LOWER BOUNDS OF THE TRACE OF THE FINE- AND COARSE-SCALE MATRICES
text: Lemma 4. (Upper and Lower bounds of the trace of the fine- and coarse-scale matrices). For constants 0 < δ, ζ < 1:
P [ nρnζ(l) ≤ tr(A) ≤ nρnζ(u) ] ≥ 1− 2 exp ( −2nρ2n(tr(DQ(c))ζ)2 ) ,
P [ mρnν 2δ(l) ≤ tr(Ã) ≤ mρnδ(u) ] ≥ 1− 2 exp (−2m(ρnν2tr(Q(c))δ)2),
P [ 1TWAWT1 ≥ c̃2minρnm2||Q(c)||1,1(δ + 1) ] ≥ 1− exp ( −2ρ2nm2(c̃2min||Q(c)||1,1δ)2 ) ,
P [ 1TmWA1n ≥ c̃mincminρnmn||Q(c)||1,1(ζ + 1) ] ≥ 1− exp ( −2ρ2nmn(c̃mincmin||Q(c)||1,1ζ)2 ) (22)
where ν is the coarsening resolution parameter (c.f. Eq. 7), and
ζ(l) , tr(DQ(c))(1− ζ), ζ(u) , tr(DQ(c))(1 + ζ) δ(l) , tr(Q(c))(1− δ), δ(u) , tr(Q(c))(1 + δ)
(23)

heading: A.3.3 PROOF OF LEMMA 4
text: Proof. From definition, E[tr(A)] = tr(PTQP) = nρntr(DQ(c)) and E[tr(Ã)] = ρntr(ΦQ(c)ΦT). Using the Hoeffding’s inequality for tail bounding independent random variables, for a constant 0 < ζ < 1 we have:
P [ |tr(A)− nρntr(DQ(c))| ≥ nρntr(DQ(c))ζ ] ≤ 2 exp (−2(nρntr(DQ (c))ζ)2
n ) = 2 exp −2nρ2n(tr(DQ(c))ζ︸ ︷︷ ︸ = ζ(u)−ζ(l)
2
)2  (24)
Hence
nρn tr(DQ(c))(1− ζ)︸ ︷︷ ︸ ζ(l) ≤ tr(A) ≤ nρn tr(DQ(c))(1 + ζ)︸ ︷︷ ︸ ζ(u)
(25)
We follow similar steps for Ã. For all i ∈ [m]:∑ k,k′∈[K] ΦikQ (c) kk′Φik′ ≥ ∑ k∈[K]:Φik>0 [Φ2ikQ (c) kk + 2Φik ∑ k′>k Q (c) kk′Φik′ ]
≥ ν2tr(Q(c)) + 2ν2||Q(c)||min ≥ ν2tr(Q(c))
(26)
based on which the following upper and lower bounds on tr( ˜̄A) can be found. mρnν
2tr(Q(c)) ≤ tr( ˜̄A) = ρntr(ΦQ(c)ΦT) = ρn m∑ i=1 ∑ k,k′∈[K] ΦikQ (c) kk′Φik′ ≤ mρntr(Q (c))
(27)
We can now use Hoeffding’s inequality to obtain the tail bound for a constant 0 < δ < 1: P [ |tr(Ã)− ρntr(ΦQ(c)ΦT)| ≥ ρntr(ΦQ(c)ΦT)δ ] ≤ 2 exp (−2(ρntr(ΦQ (c)ΦT))2
m )
≤ 2 exp (−2m(ρnν2tr(Q(c))δ)2). (28)
The event in Eq. 28 leads to the following upper and lower bound on tr(Ã):
mρnν 2 tr(Q(c))(1− δ)︸ ︷︷ ︸
δ(l)
≤ ρntr(ΦQ(c)ΦT)(1− δ) ≤ tr(Ã) ≤ ρntr(ΦQ(c)ΦT)(1 + δ) ≤ mρn tr(Q(c))(1 + δ)︸ ︷︷ ︸ δ(u) .
(29)
We then replacing δ(l), δ(u) defined in Eq. 29 into Eq. 28.
Similarly, event
1TWAWT1 ≥ 1TΦ︸︷︷︸ ≥c̃minm1K QΦT1(1 + δ) ≥ c̃2minρnm2||Q(c)||1,1(1 + δ) (30)
happens with probability at least 1− P [ 1TWAWT1− 1TΦQΦT1 < c̃2minρnm2||Q(c)||1,1δ ] ≥ 1− exp (−2(c̃ 2 minρnm 2||Q(c)||1,1δ)2 m2 )
≥ 1− exp ( −2ρ2nm2(c̃2min||Q(c)||1,1δ)2 ) (31)
using Assumption 3 and following using one-sided Hoeffding’s concentration inequality.
Finally, similar arguments can be applied to the following event
1TmWA1n ≥ 1mΦ︸ ︷︷ ︸ ≥c̃minm1K Q P1n︸︷︷︸ =ndiag(D)(1+ζ)≥ncmin1K ≥ c̃mincminρnmn||Q(c)||1,1(1 + ζ) (32)
that occurs with probability at least
1− P [ 1TmWA1n − 1mΦQP1n < c̃mincminρnmn||Q(c)||1,1ζ ] ≥ 1− exp ( −2 (c̃mincminρnmn||Q (c)||1,1ζ)2 mn ) ≥ 1− exp ( −2ρ2nmn(c̃mincmin||Q(c)||1,1ζ)2
) (33)
using one-sided Hoeffding’s inequality. This concludes the proof.

heading: A.3.4 LEMMA: ERROR BETWEEN THE GRAMIANS OF RANDOM AND EXPECTED LTI SYSTEMS
text: Let Sfine and Scoarse 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 Sfine and Sfine and that of Scoarse and Scoarse. Lemma 5. (Error between the Gramians of random and expected LTI systems): Under the assumptions stated in Lemma 1, the following holds with probability at least 1 − 2 exp ( −2nρ2n(tr(DQ(c))ζ)2 ) :
αn , ‖C(Anom, In×n)− C(Ānom, In×n)‖max ≤ [1 + ‖Q (c)‖max tr(DQ(c)) ][ 1 ζ(l) + ρn‖Q (c)‖max tr(DQ(c)) ] c2(1− β2)ζ(l) [ 1− 1
c2·tr2(DQ(c))
] 1 ρ2nn = O( 1 ρ2nn ),
(34)
and with probability at least 1− 2 exp (−2m(ρnν2tr(Q(c))δ)2):
α̃n , ‖C(Ãnom, Im×m)− C( ¯̃ Anom, Im×m)‖max ≤
[1 + ‖Q (c)‖max
ν2tr(Q(c)) ][ 1 δ(l)
+ ρn‖Q (c)‖max
tr(Q(c)) ]
c̃2(1− β2)δ(l)(1− ( 1c̃ν2tr(Q(c)) )2) 1 mρ2nν 4
= O ( 1
mρ2nν 4
) ,
(35)
where r = |supp(wi)| is the homogeneous coarsening parameter.
Note that C(D, I) = (I−D2)−1, where D can take Anom, Ānom, Ãnom, or ¯̃ Anom. Thus, Theorem 5 is effectively bounding the difference of resolvents (zI−D2)−1 evaluated at z = 1. For n = m, we have r = 1, ν = 1 and both αn and α̃n coincide. Lemma 5 is basically a concentration result for the Gramians of Sfine (or Scoarse) and Sfine (or Scoarse); however the rate at which the difference goes to zero is different for fine- and coarse systems. Further, smaller the stability margin 1− β, looser are the bounds in Eq. 34 and Eq. 35.

heading: A.3.5 PROOF OF LEMMA 5
text: We begin by proving the inequality in Eq. 34. From Eq. 2 and Lemma 1, the limit below exists with the probability stated in the statement of lemma.
C(Anom, In×n) , lim T→∞
CT (Anom, In×n) = limT→∞ ∑T−1 t=0 (Anom) t(ATnom) t
= lim T→∞
∑T−1 t=0 (Anom) 2t = (I−A2nom)−1. (36)
The last but one equality follows because A is a symmetric matrix, ‖Anom‖2 = ‖ Ac·tr(A)‖2 ≤ β < 1 (follows from the lemma’s hypothesis), the last one from the Neumann series formula. Also, we have
‖Ānom‖2 = ‖ Āc·tr(Ā)‖2 = ‖ PTQ(c)P c·tr(PTQ(c)P)‖2 ≤ √ ‖PTQ(c)P‖∞‖PTQ(c)P‖1 c·ntr(DQ(c)) ≤ 1 c·tr(DQ(c)) < 1,
(37)
since [PTQ(c)P]`v ≤ 1 for all `, v ∈ [n]. Similarly
C(Ānom, In×n) , lim T→∞ CT (Ānom, In×n) = (I− Ā2nom)−1.
From these observations, we establish the following identity (explanations for each step succeeds the equations):
αn = ‖C(Anom, In×n)− C(Ānom, In×n)‖max = ‖(I− (Anom)2)−1 − (I− (Ānom)2)−1‖max (a) = ‖(I−Anom)−1(A2nom − Ā2nom)(I− Ā2nom)−1‖max (b)
≤ ‖(I−A2nom)−1‖∞‖A2nom − (Ā2nom‖max‖(I− Ā2nom)−1‖1 (c)
≤ √ n‖(I−A2nom)−1‖2‖A2nom − Ā2nom‖max √ n‖(I− Ā2nom)−1‖2 (d) ≤ n 11−‖A2nom‖2 ‖A 2 nom − Ā2nom‖max 11−‖Ā2nom‖2 (e) ≤ n 11−β2 ‖A 2 nom − Ā2nom‖max 11− 1 c2·tr2(DQ(c)) (f) ≤ n 11−β2 ‖Anom − Ānom‖max[‖Anom‖max + ‖Ānom‖max] 1
1− 1 c2·tr2(DQ(c))
≤ n 11−β2 ‖ A c·tr(A) − Ā c·tr(Ā)‖max[ 1 cnρnζ(l) + cρn‖Q (c)‖max nρntr(DQ(c)) ] 1 1− 1
c2·tr2(DQ(c))
≤ n 11−β2 1 c·tr(A)‖A− Ā‖max[1 + n‖Ā‖max tr(Ā) ] 1 cnρn [ 1ζ(l) + ρn‖Q(c)‖max tr(DQ(c)) ] 1 1− 1 c2·tr2(DQ(c)) (g) ≤ n 11−β2 1 cnρnζ(l) [1 + nρn‖Q (c)‖max ρnntr(DQ(c)) ] 1cnρn [ 1 ζ(l) + ρn‖Q (c)‖max tr(DQ(c)) ] 1
1− 1 c2·tr2(DQ(c))
≤ [1 + ‖Q (c)‖max tr(DQ(c)) ][ 1 ζ(l) + ρn‖Q (c)‖max tr(DQ(c)) ] c2(1− β2)ζ(l) [ 1− 1
c2·tr2(DQ(c)) ] ︸ ︷︷ ︸
O(1)
1 ρ2nn
= O( 1ρ2nn ).
(38)
where (a)-(d),(f) follow the inequalities itemized at the beginning of the appendix; (e) is because of the assumption in Lemma 1, Eq. 37, and that:
‖(I−A2nom)−1‖2 ≤ 1/(1− ‖A2nom‖2) ≤ 1/(1− ‖Anom‖22) ≤ 1/(1− β2); (39)
and the rest of inequalities follow from definitions of Anom, Ānom in the paragraphs processing Eq. 1 and Eq. 11.
The proof for the inequality in Eq. 35 follows similar lines as above, and hence, we provide a sketch, but not the full details. From Eq. 2, note that the following
C(Ãnom, Im×m) , lim T→∞
CT (Ãnom, Im×m) = limT→∞ ∑T−1 t=0 Ã t nom ( ÃTnom )t = lim T→∞ ∑T−1 t=0 Ã 2t nom = (I− Ã2nom)−1,
(40)
where ‖Ãnom‖2 = ‖ Ãc̃·tr(Ã)‖2 ≤ β < 1 (from the lemma’s hypothesis). Moreover, we have C( ¯̃Anom, Im×m) = (I− ¯̃ A 2 nom) −1, where
‖ ¯̃Anom‖2 = ‖ ˜̄A c̃tr( ˜̄A)‖2 = ‖ √ ‖ΦQ(c)ΦT‖∞‖ΦQ(c)ΦT‖1 c̃tr(ΦQ(c)ΦT) ‖2 ≤ √ mm c̃mν2tr(Q(c)) ≤ 1 c̃ν2tr(Q(c)) (41)
following the fact that [ΦQ(c)ΦT]ij ≤ 1.
Using these observations, we obtain the following inequality by taking similar steps as those for αn in Eq. 38 (inner steps are removed due to redundancy) :
α̃n , ‖C(Ãnom, Im×n)− C( ¯̃ Anom, Im×m)‖max
≤ m 1 1−‖(Ã2nom‖2 1 c̃tr(Ã) ‖Ã− ˜̄A‖max[1 + m‖ ˜̄A‖max
tr( ˜̄A) ][‖Ãnom‖max + ‖ ¯̃Anom‖max] 11−‖ ¯̃A2nom‖2 ≤ m 11−β2 1 mρnν2δ(l) [1 + mρn‖Q (c)‖max mρnν2tr(Q(c)) ][ 1c̃mρnν2δ(l) + ρn‖Q(c)‖max c̃mρnν2tr(Q(c)) ] 1 1−‖( ˜̄̃ A
tr( ˜̄A) )2‖2 ≤ m 11−β2 1 mρnν2δ(l) [1 + ‖Q (c)‖max ν2tr(Q(c)) ][ 1 c̃mρnν2δ(l) + ρn‖Q (c)‖max c̃mρnν2tr(Q(c)) ] 1 1−( 1
c̃ν2 tr(Q(c)) )2
≤ [1 + ‖Q (c)‖max ν2tr(Q(c)) ][ 1 δ(l) + ρn‖Q (c)‖max tr(Q(c)) ]
c̃2(1− β2)δ(l)(1− ( 1c̃ν2tr(Q(c)) )2)︸ ︷︷ ︸ O(1)
1 mρ2nν 4
= O (
1 mρ2nν 4
) .
(42)
The proof is now complete.

heading: A.3.6 PROOF OF THEOREM 1
text: The proof of the theorem makes use of Lemma 5. Let i ∈ [m], and recall that Bi = diag(wTi ) and B̃i = rWdiag(w T i ). From Eq. 10 and Eq. 13, consider the following bound
∆i(A, Ã) , | rθ
(i) group,A−1 m∑ i=1 (rθ (i) group,A − 1) − θ
(i) coarse,Ã −1 m∑ i=1 (θ (i) coarse,Ã − 1) |
≤ | rθ
(i) group,A − 1
m∑ i=1 (rθ (i) group,A − 1) − rθ
(i) group,Ā − 1
m∑ i=1 (rθ (i) group,Ā − 1) |
︸ ︷︷ ︸ =∆i(A,Ā)
+ | θ
(i) coarse,Ã − 1
m∑ i=1 (θ (i) coarse,Ã − 1)
− θ
(i) coarse, ˜̄A − 1 m∑ i=1 (θ (i) coarse, ˜̄A − 1) |
︸ ︷︷ ︸ =∆i(Ã,
˜̄A) + | rθ (i) group,Ā − 1
m∑ i=1 (rθ (i) group,Ā − 1)
− θ
(i) coarse, ¯̃ A − 1
m∑ i=1 (θ (i) coarse, ¯̃ A − 1) |
︸ ︷︷ ︸ bias=∆i(Ā), ˜̄A)
|
≤ ∆i(A, Ā) + ∆i(Ã, ˜̄A) + bias.
(43)
The complete proof of the bound on ∆i(A, Ā) will be elaborated in Thm. 3 and it follows:
∆i(A, Ā)
≤ ζ2(u)
c̃mincmin||Q(c)||1,1(1 + ζ)
[1 + ‖Q (c)‖max
tr(DQ(c)) ][ 1 ζ(l)
+ ρn‖Q (c)‖max
tr(DQ(c)) ] (1− β2)ζ(l) [ 1− 1
c2·tr2(DQ(c))
] 1 + K||Q(c)DQ(c)||max
||Q(c)DQ(c)||min(1− ( ||DQ (c)||F
tr(DQ(c)) )2)  ︸ ︷︷ ︸
O(1)
1 ρnm
= O( 1ρnm ) (44)
We now derive an upper bound on ∆i(Ã, ˜̄A). ∆i(Ã,
˜̄A) = | θ(i)coarse,Ã−1m∑ i=1 (θ (i) coarse,Ã − 1) − θ (i) coarse, ˜̄A−1 m∑ i=1 (θ (i) coarse, ˜̄A − 1) |
≤ 1m∑ i=1 (θ (i) coarse,Ã − 1) |θ(i) coarse,Ã − θ(i) coarse, ˜̄A +
m∑ i=1 (θ (i) coarse,Ã − θ(i)
coarse, ˜̄A) m∑ i=1 (θ (i) coarse, ˜̄A − 1) [θ (i) coarse, ˜̄A − 1]|
≤ 1m∑ i=1 (θ (i) coarse,Ã − 1) ||θcoarse,Ã − θcoarse, ˜̄A||max 1 + | mm∑ i=1 (θ (i) coarse, ˜̄A − 1) [θ (i) coarse, ˜̄A − 1]| 
≤ 1m∑ i=1 (θ (i) coarse,Ã − 1) α̃n 1 + m||θcoarse, ˜̄A−1||maxm∑ i=1 (θ (i) coarse, ˜̄A − 1)  , (45)
From the equality after Eq. 40, we have
θ (i) coarse, ˜̄A = diagi ( (I− Ā2nom)−1 ) (46)
Furthermore, since ΦQ(c)ΦT ≤ 11T then (ΦQ(c)ΦT)2 ≤ 11T11T = m11T
||θ coarse, ˜̄A − 1||max = ‖(I− Ā2nom)−1Ā2nom‖max
≤ 1tr2(ΦQ(c)ΦT)‖(I− Ā 2 nom) −1m11T‖max ≤ mtr2(ΦQ(c)ΦT)‖(I− Ā 2 nom)
−1‖∞ ≤ m √ m
tr2(ΦQ(c)ΦT)‖(I− Ā 2 nom) −1‖2 ≤ m √ m
(mρnν2tr(Q(c))2 ‖(I− Ā2nom)−1‖2
≤ 1√ mρ2nν
4tr2(Q(c))(1−( 1 c̃ν2 tr(Q(c))
)2) .
(47)
Similarly
m∑ i=1 (θ (i) coarse, ˜̄A − 1) = tr[(I− ¯̃A 2 nom) −1 − I]
= tr[ ¯̃A 2 nom(I− ¯̃ A 2 nom) −1] ≥ tr[ ¯̃A 2
nom]
≥ tr[(ΦQ (c)ΦT) 2 ]
tr2[ΦQ(c)ΦT]
≥ m 2ν3c̃mintr[(Q(c))2] (c̃mtr[Q(c)])2 = ν 3c̃mintr[(Q(c))2] c̃2tr2[Q(c)]
(48)
where all inequalities follow well-known matrix norm axiom. The last line in Eq. 48 is based on Assumption 2, and
tr[ ( ΦQ(c)ΦT )2 ] ≥ νc̃minmtr[Φ(Q(c))2ΦT] ≥ νc̃minmmν2tr[(Q(c))2] = m2ν3c̃mintr[(Q(c))2]
(49)
similar to the derivation of Eq. 27 since for all k ∈ [K]: [ΦTΦ]kk = ∑ i∈[m] Φ2ik ≥ ν ∑ i∈[m] Φik ≥ νc̃minm (50)
We use the definition of θcoarse,Ã in Eq. 13:
| m∑ i=1 (θ (i) coarse,Ã − 1)| = m∑ i=1 diagi ( (I− Ã2nom)−1 − I ) = tr ( (I− Ã2nom)−1 − I
) ≥ tr(Ã2nom) ≥ tr(Ã 2)
tr2(Ã) (a) ≥ m
2ρn||Q(c)||1,1 r2 c̃2min(1+δ) (mρnδ(u))2
= 1ρnr2 c̃2min(1+δ)||Q (c)||1,1 δ(u))2 ,
(51)
where the inequality (a) in Eq. 51 comes from tr(Ã2) = ∑ i,j Ã2ij
= ∑ i,j  1 r2 ∑ v∈Ki,`∈Kj Av` 2 = 1r4
∑ i,j ∑ v,v′∈Ki,`,`′∈Kj Av`Av′`′
= 1r4  ∑ v∈ ∪iKi, ` ∈ ∪jKj Av` + ∑ v 6=v′∈ ∪iKi or ` 6= `′ ∈ ∪jKj Av`Av′`′  ≥ 1r2
∑ i,j wTi Awj
= 1r2 1 TWAWT1
≥ 1r2 1 TΦ︸︷︷︸
≥c̃minm1K Q ΦT1︸︷︷︸ ≥c̃minm1TK (1 + δ)
≥ m 2ρn||Q(c)||1,1
r2 c̃ 2 min(1 + δ),
(52)
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:
∆i(Ã, ˜̄A) ≤ ρnr2 δ(u))2c̃2min(1+δ)||Q(c)||1,1 α̃n 1 + m 1√mρ2nν4 tr2(Q(c))(1−( 1c̃ν2 tr(Q(c)) )2) ν3 c̃mintr[(Q (c))2]
c̃2 tr2[Q(c)]  = O ( ρnr
2√m mρ2nρ 2 n ) = O ( r2√ mρ3n ) (53)
The statement of the theorem follows by invoking Eq. 44 and Eq. 53 into Eq. 43:
∆i( 1 tr(A)A, 1 tr(Ã) Ã) = bias +O
( 1
ρnm + r 2 √ mρ3n
) . (54)
with a joint probability of at least 1− 2 exp ( −2nρ2n(tr(DQ(c))ζ)2 ) − exp ( −2ρ2nmn(c̃mincmin||Q(c)||1,1ζ)2 ) − 2 exp (−2m(ρnν2tr(Q(c))δ)2)− exp ( −2ρ2nm2(c̃2min||Q(c)||1,1δ)2 ) (55)
per Lemma 3. We then get the minimum of the four exponents in Eq. 70. The proof is now complete.

heading: A.4 PROOFS FOR SECTION 6: LEARNING APPROACH FOR GROUP AVERAGE CONTROLLABILITY

heading: A.4.1 PROOF OF LEMMA 2
text: We start by defining θfine,M similar to Eq. 10 and Eq. 13 (M will be later substituted with A and Ā),
θTfine,M , [tr[C(Mnom, e1)] . . . tr[C(Mnom, en)]] ∈ Rn×1. (56) Using the Gramian definition in Eq. 2, we have:
θ (i) fine,M = tr [C(Mnom, ei)]
= tr [ ∞∑ τ=0 Mτnomeie T i M τ nom ] =
∞∑ τ=0 tr(Mτnomeie T i M τ nom)
= ∞∑ τ=0 tr(eTi M 2τ nomei)
= ∞∑ τ=0 diagi(M 2τ nom)
= diagi ( ∞∑ τ=0 M2τnom ) = diagi ( (I−M2nom)−1 ) .
(57)
We first simplify the term θfine,Ā in Eq. 60, by substituting Ā with PTQP introduced prior to Eq. 6:
θfine,Ā = tr[C(Ānom, e1)]. . . tr[C(Ānom, en)]  = diag( ∞∑ τ=0 Ā2τnom )
= diag( ∞∑ τ=0 ( 1 tr(PTQP) PTQP)2τ ) = diag( ∞∑ τ=0 ( 1 ntr(DQ(c)) PTQ(c)P)2τ ) = diag(I + ( 1 ntr(DQ(c)) ) 2PTQ(c)PPTQ(c)P + ( 1 ntr(DQ(c)) ) 4PTQ(c)PPTQ(c)P + · · · )
= diag(I + 1n ( 1 tr(DQ(c)) ) 2PTQ(c)
1 n PPT︸ ︷︷ ︸ ,D Q(c)P
+ 1n ( 1 tr(DQ(c)) ) 4PTQ(c)
1 n PPT︸ ︷︷ ︸Q(c) 1nPPT︸ ︷︷ ︸Q(c) 1nPPT︸ ︷︷ ︸Q(c)P + · · · )
= 1n + 1 ntr(DQ(c))diag(P TQ(c) DQ
(c)
tr(DQ(c))P + 1 tr(A)P TQ(c) DQ
(c) tr(DQ(c)) DQ(c) tr(DQ(c)) DQ(c) tr(DQ(c))P + · · · )
= 1n + 1 ntr(DQ(c))diag(P T Q
(c)DQ(c)
tr(DQ(c)) [I + (
DQ(c)
tr(DQ(c)) )2 + · · · ]︸ ︷︷ ︸
,Υ(Q(c),D)
P)
= 1n + 1 ntr(DQ(c))diag(P TΥ(Q(c),D)P) (a) = 1n +
1 ntr(DQ(c)) (P ◦P) Tdiag(Υ(Q(c),D)) (b) = 1n +
1 ntr(DQ(c))P Tdiag(Υ),
(58) where (a) is due to the special structure of P Eq. 4 since for an arbitrary matrix M of appropriate size:
diagi(P TMP) = ∑ k,k′∈[K] PkiMk,k′Pk′i = ∑ k,k′∈[K] PkiMk,k′Pk′i
= ∑ k∈[K] PkiMk,kPki = ∑ k∈[K] P2kiMk,k = (Pi ◦Pi)diag(M),
(59)
and (b) is true because P is binary. Replacing Eq. 58 into Eq. 60 yields:
θgroup,Ā = 1 rW ( 1n + 1 ntr(DQ(c))P Tdiag(Υ)) ) = 1r ( 1m + 1 ntr(DQ(c))Φdiag(Υ)) ) (60)
The proof is now complete.

heading: A.4.2 THEOREM 3 AND PROOF
text: Define the error metric similar to Eq. 14:
∆i(A, Ā) , ∣∣∣∣∣∣ rθ (i) group,A − 1∑m
i=1[rθ (i) group,A − 1]
− rθ
(i)
group,Ã − 1∑m
i=1[rθ (i) group,Ā − 1] ∣∣∣∣∣∣ , for all i ∈ [m]. (61) Theorem 3. (Component wise error bound between θgroup,A and θgroup,Ā): Let ∆i(A, Ā) be defined as above and ν be the resolution parameter given by Eq. 7. Under the assumptions stated in Section 3 and Lemma 1, the following holds:
∆i(A, Ā) ≤ ζ2(u)
c̃mincmin||Q(c)||1,1(1 + ζ)
[1 + ‖Q (c)‖max
tr(DQ(c)) ][ 1 ζ(l)
+ ρn‖Q (c)‖max
tr(DQ(c)) ] (1− β2)ζ(l) [ 1− 1
c2·tr2(DQ(c))
] 1 + K||Q(c)DQ(c)||max
||Q(c)DQ(c)||min(1− ( ||DQ (c)||F
tr(DQ(c)) )2)  ︸ ︷︷ ︸
O(1)
1
ρnm
(62) with probability at least 1 − 3 exp ( −2κ̂(Q(c),D,m, n, ρn) ) , where Further, for a constant 0 <
ζ < 1, the exponent is κ̂(Q(c),D,m, n, ρn) = min { nρ2n(tr(DQ (c))ζ)2, mnρ2n(c̃mincmin||Q(c)||1,1ζ)2 } .

heading: A.4.3 PROPOSITION 4 AND PROOF
text: Proposition 4. (Group Average Controllability for Ā) The group average controllability vector for Ā is
θ (i) group,M =
1 r wiθfine,M. (63)
Proof. We begin by simplifying the group average controllability using its definition in Eq. 10 and the definition of Gramian in Eq. 2, for a general matrix notation M which can be replaced by either A or Ā:
θ (i) group,M = tr [ C(Mnom,diag(wTi )) ] = tr
[ ∞∑ τ=0 Mτnomdiag(w T i )diag(w T i ) TMτnom ]
= tr [ ∞∑ τ=0 Mτnomdiag((wi ◦wi)T)Mτnom ] (a) = 1r2 tr  ∞∑ τ=0 Mτnom( ∑
v∈supp(wi)
eve T v )M τ nom  = 1r2
∑ v∈supp(wi) tr [ ∞∑ τ=0 Mτnomeve T vM τ nom ]
= 1r2 ∑
v∈supp(wi)
tr [ ∞∑ τ=0 Mτnomeve T vM τ nom ] ︸ ︷︷ ︸
θ (v) fine,M
,
(64)
where (a) is due to the assumption of r-homogeneous W, ◦ denotes the Hadamard product, and we have already defined θfine,M in Eq. 56. Putting Eq. 64 in vector form concludes the proof.

heading: A.4.4 PROOF OF THEOREM 3
text: Proof. We start by substituting M into Eq. 63, from Proposition 4, with A and Ā, yields :
∆i(A, Ā) = | rθ
(i) group,A−1 m∑ i=1 (rθ (i) group,A − 1) − rθ (i) group,Ā −1 m∑ i=1 (rθ (i) group,Ā − 1) | = | wiθfine,A−1m∑ i=1 (wiθfine,A − 1) − wiθfine,Ā−1m∑ i=1 (wiθfine,Ā − 1) |
= 1m∑ i=1 (wiθfine,A − 1) |wiθfine,A − 1−
m∑ i=1 (wiθfine,A − 1)
m∑ i=1 (wiθfine,Ā − 1) [wiθfine,Ā − 1]|
= 1m∑ i=1 (wiθfine,A − 1) |wi(θfine,A − θfine,Ā)−
 m∑ i=1 (wiθfine,A − 1)
m∑ i=1 (wiθfine,Ā − 1) − 1
 [wiθfine,Ā − 1]|
≤ 1m∑ i=1 (wiθfine,A − 1)
|wi(θfine,A − θfine,Ā)|+ | m∑ i=1 wi(θfine,A − θfine,Ā)
m∑ i=1 (wiθfine,Ā − 1) [wiθfine,Ā − 1]|

≤ 1m∑ i=1 (wiθfine,A − 1)
|wi(θfine,A − θfine,Ā)|+ | m∑ i=1 wi(θfine,A − θfine,Ā)
m∑ i=1
1
ntr(DQ(c)) Φ(i)diag(Υ)
1 ntr(DQ(c))Φ (i)diag(Υ)| 
≤ 1m∑ i=1 (wiθfine,A − 1)
|wi(θfine,A − θfine,Ā)|+ | m∑ i=1 wi(θfine,A − θfine,Ā)
m∑ i=1 Φ(i)diag(Υ)
Φ(i)diag(Υ)|  ≤ 1m∑
i=1
(wiθfine,A − 1)
[ ||θfine,A − θfine,Ā||max + m||θfine,A−θfine,Ā||max m||Υ||min ||Υ||max ]
≤ 1m∑ i=1 (wiθfine,A − 1) ||θfine,A − θfine,Ā||max
[ 1 + ||Υ||max||Υ||min ]
≤ 1m∑ i=1 (wiθfine,A − 1) αn
[ 1 + ||Υ||max||Υ||min ] ,
(65)
where (a) is due to Cauchy-Schwartz inequality, αn is defined in Eq. 34, θfine,Ā is substituted from Eq. 58, and (b) is the result of the properties of the coarsening matrix in Definition 2. We use the
definition of θfine,A in Eq. 57: m∑ i=1 (wiθfine,A − 1) = m∑ i=1 widiag ( (I−A2nom)−1 − I ) = 1mWdiag ( (I−A2nom)−1 − I
) = 1mWdiag ( A2nom
) = 1mWdiag ( A2nom
) = 1c2·tr2(A)1mWdiag ( A2 ) = 1c2·tr2(A)1mWA1n (a) ≥ c̃mincminρnmn||Q (c)||1,1(1+ζ)
c2(ζ(u)ρnn)2
= c̃mincmin||Q(c)||1,1(1+ζ)
c2ζ2 (u)
m ρnn .
(66)
inequality (a) uses the event defined in Eq. 32 is used whose corresponding probability is Eq. 33. Using the definition of Υ in Eq. 16
||Υ||max ≤ ||Q (c)DQ(c) tr(DQ(c)) (I− ( DQ(c) tr(DQ(c)) ) 2)−1||max
≤ K||Q (c)DQ(c)||max
tr(DQ(c))(1−( ||DQ (c)||F
tr(DQ(c)) )2)
= O(1)
(67)
||Υ||min ≥ ||Q (c)DQ(c) tr(DQ(c)) (I− ( DQ(c) tr(DQ(c)) ) 2)−1||min
≥ ||Q (c)DQ(c)||min tr(DQ(c)) = Ω(1),
(68)
where Ω(.) is the opposite scaling of O(.); we write f(m) = Ω(h(m)) iff there exist positive reals c0 and m0 such that |f(n)| ≥ c0h(m) for all m ≥ m0. We substitute Eq. 66 and Eq. 34 (with probability Eq. 24) into Eq. 65
∆i(A, Ā) ≤ ζ2(u)
c̃mincmin||Q(c)||1,1(1+ζ)
[1+ ‖Q(c)‖max tr(DQ(c)) ][ 1ζ(l) + ρn‖Q(c)‖max tr(DQ(c)) ] (1−β2)ζ(l) [ 1− 1
c2·tr2(DQ(c))
] [ 1 + K||Q (c)DQ(c)||max
||Q(c)DQ(c)||min(1−( ||DQ(c)||F
tr(DQ(c)) )2)
] 1
ρnm
(69)
with a joint probability of at least 1− 2 exp ( −2nρ2n(tr(DQ(c))ζ)2 ) − exp ( −2ρ2nmn(c̃mincmin||Q(c)||1,1ζ)2 ) (70)
per Lemma 3. We then get the minimum of the two exponents in Eq. 70 which concludes the proof.

heading: A.4.5 PROOF OF THEOREM 2
text: We start by using the triangle inequality for absolute values:
∆̂i(Ã) = | θ̂(i)group−1 m∑ i=1 (θ̂(i)group − 1) − rθ (i) group,A−1 m∑ i=1 (rθ (i) group,A − 1) |
≤ | rθ
(i) group,Ā − 1
m∑ i=1 (rθ (i) group,Ā − 1) − rθ
(i) group,A − 1
m∑ i=1 (rθ (i) group,A − 1) |
︸ ︷︷ ︸ ∆i(A,Ā)
+ | θ̂ (i) group − 1 m∑ i=1 (θ̂(i)group − 1) −
rθ (i)
group,Ā − 1
m∑ i=1 (rθ (i) group,Ā − 1) |
︸ ︷︷ ︸ ,∆̂i(Ã,Ā)
(71)
The first term on the RHS of Eq. 71 has already been bounded in Thm.3. Next, we bound the second term in Eq. 71 and combine the two bounds at the end.
We substitute θ̂(i)group from the output of Algorithm 1, and θ (i)
group,Ā from Eq. 60, for Υ defined in
Eq. 16. For notation simplicity we write Υ(Q(c),D) as Υ and Υ(Q̂(c), D̂) as Υ̂ yields
∆̂i(Ã, Ā) = | θ̂(i)group−1 m∑ i=1 (θ̂(i)group − 1) −
rθ (i)
group,Ā −1 m∑ i=1 (rθ (i) group,Ā − 1) | = ∣∣∣∣∣∣∣∣∣∣ Φ̂(i)diag(Υ̂) m∑ i=1 Φ̂(i)diag(Υ̂) − Φ (i)diag(Υ) m∑ i=1 Φ(i)diag(Υ) ∣∣∣∣∣∣∣∣∣∣ = 1m∑
i=1
Φ̂(i)diag(Υ̂) ∣∣∣∣∣∣∣∣∣∣ Φ̂(i)diag(Υ̂)− m∑ i=1 Φ̂(i)diag(Υ̂) m∑ i=1 Φ(i)diag(Υ) Φ(i)diag(Υ) ∣∣∣∣∣∣∣∣∣∣ .
(72)
We set Φ̂(i) = Φ(i) + EΦ, Q̂(c) = Q(c) + EQ, D̂ = D + ED, and Υ̂ = Υ + Ē where EΦ,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:
∆̂i(Ã, Ā)
= 1m∑ i=1 Φ̂(i)diag(Υ̂) ∣∣∣∣∣∣∣∣∣∣ (Φ(i) + EΦ)diag(Υ + Ē)− m∑ i=1 (Φ(i) + EΦ)diag(Υ + Ē) m∑ i=1 Φ(i)diag(Υ) Φ(i)diag(Υ) ∣∣∣∣∣∣∣∣∣∣ = 1m∑
i=1
Φ̂(i)diag(Υ̂) ∣∣∣∣∣∣∣∣∣∣ (Φ(i) + EΦ)[diag(Υ) + diag(Ē)]− m∑ i=1 (Φ(i) + EΦ)[diag(Υ) + diag(Ē)] m∑ i=1 Φ(i)diag(Υ) Φ(i)diag(Υ) ∣∣∣∣∣∣∣∣∣∣ = 1m∑
i=1
Φ̂(i)diag(Υ̂) ∣∣∣∣∣∣∣∣∣∣ Φ(i)diag(Ē) + EΦ[diag(Υ) + diag(Ē)]− m∑ i=1 Φ(i)diag(Ē) +mEΦ[diag(Υ) + diag(Ē)] m∑ i=1 Φ(i)diag(Υ) Φ(i)diag(Υ) ∣∣∣∣∣∣∣∣∣∣ = 1m∑
i=1
Φ̂(i)diag(Υ̂) ∣∣∣∣∣∣∣∣∣∣ [Φ(i) + EΦ]diag(Ē) + [EΦ − m∑ i=1 Φ(i)diag(Ē) +mEΦ[diag(Υ) + diag(Ē)] m∑ i=1 Φ(i)diag(Υ) Φ(i)]diag(Υ) ∣∣∣∣∣∣∣∣∣∣ ≤ 1m∑
i=1
Φ̂(i)diag(Υ̂)
(1 + ||EΦ||1)||Ē||max + [||EΦ||1 + m∑ i=1 Φ(i)diag(Ē) +mEΦ[diag(Υ) + diag(Ē)]
m∑ i=1 Φ(i)diag(Υ)
]||Υ||max  . (73)
To further simplify Eq. 73, we find upper bounds on the terms inside. The two terms ||Υ||max and ||Υ||min have already been bounded in Eq. 67 and Eq. 68 and we have:
1 m∑ i=1 Φ̂(i)diag(Υ̂) ≤ 1 m||diag(Υ̂)||min
≤ 1 m||Υ̂||min = O( 1m )
(74)
The following inequality holds from the definition of norms: ||EΦ||1 ≤ K||EΦ||max (75)
Using Eq. 74 and Eq. 75, the inner term in the last line of Eq. 73 is simplified as: m∑ i=1 Φ(i)diag(Ē) +mEΦ[diag(Υ) + diag(Ē)]
m∑ i=1 Φ(i)diag(Υ)
=
m∑ i=1 Φ(i)diag(Ē)
m∑ i=1 Φ(i)diag(Υ) +mEΦ[diag(Υ)+diag(Ē)]m∑ i=1 Φ(i)diag(Υ)
≤ m||diag(Ē)||maxm||diag(Υ)||min +mK ||EΦ||max[||diag(Υ)||max+||diag(Ē)||max]
m||diag(Υ)||min ≤ ||Ē||max||Υ||min +K ||EΦ||max[||Υ||max+||Ē||max] ||Υ||min = O(||EΦ||max + ||Ē||max) (76)
Replacing Eq. 67, Eq. 68, Eq. 74, Eq. 75, and Eq. 76 into Eq. 73 simplifies it as:
| θ̂ (i) group−1 m∑ i=1 (θ̂(i)group − 1) −
rθ (i)
group,Ā −1 m∑ i=1 (rθ (i) group,Ā − 1) | = O( 1m [||EΦ||max + ||Ē||max]). (77)
We now simplify the term ||Ē||max in Eq. 79:
||Ē||max = ||Υ̂−Υ||max = || Q̂ (c)D̂Q̂(c)
tr(D̂Q̂(c)) (I− ( D̂Q̂
(c)
tr(D̂Q̂(c)) )2)−1 − Q
(c)DQ(c) tr(DQ(c)) (I− ( DQ(c) tr(DQ(c)) ) 2)−1||max
= 1 tr(D̂Q̂(c))
||Q̂(c)D̂Q̂(c)(I− ( D̂Q̂ (c) tr(D̂Q̂(c)) )2)−1 − tr(D̂Q̂ (c)) tr(DQ(c))Q (c)DQ(c)(I− ( DQ (c) tr(DQ(c)) ) 2)−1||max.
(78)
To continue the simplification of ||Ē||max, we bring the two error matrices EQ and ED introduced in the statement of the theorem into play:
(Q(c) + EQ) (D + ED)(Q (c) + EQ) = (Q (c) + EQ)(DQ (c) + DEQ + EDQ (c) + EDEQ) = Q(c)DQ(c) + Γ,
(79)
where we define
Γ , Q(c)DEQ + Q (c)EDQ (c) + Q(c)EDEQ + EQDQ (c) + EQDEQ + EQEDQ (c) + EQEDEQ (80)
and
(D + ED) (Q (c) + EQ) = DQ (c) + DEQ + EDQ (c) + EDEQ︸ ︷︷ ︸
E
. (81)
Replacing Eq. 79 and Eq. 81 into Eq. 78 yields:
||Ē||max = 1tr(D̂Q̂(c)) ||(Q (c)DQ(c) + Γ)(I− ( D̂Q̂
(c)
tr(D̂Q̂(c)) )2)−1 − tr(DQ (c)+E) tr(DQ(c)) Q (c)DQ(c)(I− ( DQ (c) tr(DQ(c)) ) 2)−1||max
= 1 tr(D̂Q̂(c))
||Q(c)DQ(c)[(I− ( D̂Q̂ (c) tr(D̂Q̂(c)) )2)−1 − (I− ( DQ (c) tr(DQ(c)) ) 2)−1]
+Γ(I− ( D̂Q̂ (c) tr(D̂Q̂(c)) )2)−1 − tr(E)tr(DQ(c))Q (c)DQ(c)(I− ( DQ (c) tr(DQ(c)) ) 2)−1||max
= 1 tr(D̂Q̂(c)) [||Q(c)DQ(c)[ ∞∑ `=1 ( D̂Q̂(c) tr(D̂Q̂(c)) )2` − ( DQ (c)
tr(DQ(c)) )2`︸ ︷︷ ︸
, 1
]
+Γ(I− ( D̂Q̂ (c) tr(D̂Q̂(c)) )2)−1 − tr(E)tr(DQ(c))Q (c)DQ(c)(I− ( DQ (c) tr(DQ(c)) ) 2)−1||max]
≤ K tr(D̂Q̂(c))
[||Q(c)DQ(c)||max|| 1||max + ||Γ||max||(I− ( D̂Q̂ (c) tr(D̂Q̂(c)) )2)−1||max
+ tr(E)tr(DQ(c)) ||Q (c)DQ(c)||max||(I− ( DQ
(c)
tr(DQ(c)) ) 2)−1||max]
= O(|| 1||max + ||Γ||max + tr(E)) = O(|| 1||max + ||Γ||max + ||E||max)
(82)
We define another error term:( DQ(c) + E )2` = (DQ(c))2` + 2∑̀ ν=1
· · ·︸ ︷︷ ︸ ,R=O(E) . (83)
We can then simplify 1 for ` ≥ 1 as:
|| 1||max = || ∞∑ `=1
1
(tr(D̂Q̂(c)))2`
[ (D̂Q̂(c))2` − ( tr(D̂Q̂ (c))
tr(DQ(c)) )2`(DQ(c))2`
] ||max
= || ∞∑ `=1
1
(tr(D̂Q̂(c)))2`
[ (DQ(c))2` +R− (1 + tr(R)
tr(DQ(c)) )2`(DQ(c))2`
] ||max
= || ∞∑ `=1
1
(tr(D̂Q̂(c)))2`
[ R− ( tr(R)
tr(DQ(c)) )2`(DQ(c))2`
] ||max
= ||[(1− ( 1 tr(D̂Q̂(c)) )2)−1 − 1]R− ∞∑ `=1
[ (
tr(R) tr(DQ(c))tr(D̂Q̂(c)) )2`(DQ(c))2`
] ||max
= ||[(1− ( 1 tr(D̂Q̂(c)) )2)−1 − 1]R− [(I− ( tr(R) tr(DQ(c))tr(D̂Q̂(c)) DQ(c))2)−1 − I]||max ≤ [(1− ( 1
tr(D̂Q̂(c)) )2)−1 − 1]||R||max + ||[(I− ( tr(R)tr(DQ(c))tr(D̂Q̂(c))DQ (c))2)−1 − I]||max = O(||R||max) = O(||E||max)
(84)
Similarly, we can rewrite an upper bound on ‖Γ‖max as:
‖Γ‖max = K2(‖Q(c)D‖max‖EQ‖max + ‖Q(c)‖max‖ED‖max‖Q‖max + ‖Q(c)‖max‖ED‖max‖EQ‖max +‖EQ‖max‖DQ(c)‖max + ‖EQ‖max‖D‖max‖EQ‖max
+‖EQ‖max‖ED‖max‖Q(c)‖max + ‖EQ‖max‖ED‖max‖EQ‖max) = K2(‖EQ‖max + ‖ED‖max + ‖ED‖max‖EQ‖max + ‖EQ‖max + ‖EQ‖2max +‖EQ‖max‖ED‖max + ‖EQ‖2max‖ED‖max) = O(||EQ||max + ||ED||max),
(85)
and
‖E‖max = ‖DEQ + EDQ(c) + EDEQ‖max = K(‖D‖max‖EQ‖max + ‖ED‖max‖Q(c)‖max + ‖ED‖max‖EQ‖max) = K(‖EQ‖max + ‖ED‖max + ‖ED‖max‖EQ‖max) = O(||EQ||max + ||ED||max).
(86)
By substituting Eq. 84, Eq. 86, and Eq. 85 into Eq. 82, we get:
||Ē||max = O(||EQ||max + ||ED||max). (87)
Replacing Eq. 87 into the original error in Eq. 79 yields:
| θ̂ (i) group−1 m∑ i=1 (θ̂(i)group − 1) −
rθ (i)
group,Ā −1 m∑ i=1 (rθ (i) group,Ā − 1)
| = O (
1 m [||EΦ||max + ||EQ||max + ||ED||max]
) .
(88)
which happens with the same lower bound probability as in Eq. 70. The proof is now complete.

Review summaries:
The paper studies the problem of controlling the dynamics of a networked dynamical system, under partial observations. Such systems arise in a number of applications, and therefore the control problem is important and well motivated. The authors consider a reduced order system from coarse data, and derive bounds on the convergence and approximation error for the original dynamical systems model. These are evaluated empirically on a small synthetic dataset