More Like this

1. Learning coherent clusters in weakly‑connected network systems

   Min, Hancheng; Mallada, Enrique (July 2023, Proceedings of The 5th Annual Learning for Dynamics and Control Conference)

   We propose a structure-preserving model-reduction methodology for large-scale dynamic networks with tightly-connected components. First, the coherent groups are identified by a spectral clustering algorithm on the graph Laplacian matrix that models the network feedback. Then, a reduced network is built, where each node represents the aggregate dynamics of each coherent group, and the reduced network captures the dynamic coupling between the groups. We provide an upper bound on the approximation error when the network graph is randomly generated from a weight stochastic block model. Finally, numerical experiments align with and validate our theoretical findings. 

   more » « less
2. Multigrid for model reduction of power grid networks

   https://doi.org/10.1002/nla.2201  

   Lee, B. (June 2018, Numerical Linear Algebra with Applications)

   Summary This paper presents a method for determining the relevant buses for reduced models of power grid networks described by systems of differential‐algebraic equations and for constructing the coarse‐grain dynamical power grid systems. To determine these buses, time integration of differential equations is not needed, but rather, a stationary system is analyzed. However, unlike stationary‐system approaches that determine only coarse generator buses by approximating the coherency of the generators, the proposed method analyzes the graph Laplacian associated with the admittance matrix. The buses for the reduced model are chosen to ensure that the graph Laplacian of the reduced model is an accurate approximation to the graph Laplacian of the full system. Both load and generator buses can be selected by this procedure since the Laplacian is defined on all the buses. The basis of this proposed approach lies in the close relationship between the synchrony of the system and the spectral properties of this Laplacian, that is, conditions on the spectrum of this Laplacian that almost surely guarantee the synchrony of the system. Thus, assuming that the full system is in synchrony, our strategy is to coarsen the full‐system Laplacian such that the coarse Laplacian possesses good approximation to these spectral conditions. Accurate approximation to these conditions then can better lead to synchronous reduced models. The coarsened Laplacian is defined on coarse degrees of freedom (DOFs), which are associated with the relevant buses to include in the reduced model. To realize this coarse DOF selection, we use multigrid coarsening techniques based on compatible relaxation. Multigrid is the natural choice since it has been extensively used to coarsen Laplacians arising from discretizations of elliptic partial differential equations and is actively being extended to graph Laplacians. With the selection of the buses for the reduced model, the reduced model is completed by constructing the coarse admittance matrix values and other physical parameters using standard power grid techniques or by using the intergrid operators constructed in the coarse DOFs selection process. Unfortunately, the selection of the coarse buses and the coarsening of the admittance matrix and physical parameters are not sufficient by themselves to produce a stable reduced system. To achieve a stable system, system structures of the fine‐grain model must be preserved in the reduced model. We analyze this to develop a multigrid methodology for constructing stable reduced models of power grid systems. Numerical examples are presented to validate this methodology. 

   more » « less
3. Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering

   https://doi.org/10.3389/fdata.2023.1020173  

   Zhu, Yu; Segarra, Santiago (February 2023, Frontiers in Big Data)

   We study p -Laplacians and spectral clustering for a recently proposed hypergraph model that incorporates edge-dependent vertex weights (EDVW). These weights can reflect different importance of vertices within a hyperedge, thus conferring the hypergraph model higher expressivity and flexibility. By constructing submodular EDVW-based splitting functions, we convert hypergraphs with EDVW into submodular hypergraphs for which the spectral theory is better developed. In this way, existing concepts and theorems such as p -Laplacians and Cheeger inequalities proposed under the submodular hypergraph setting can be directly extended to hypergraphs with EDVW. For submodular hypergraphs with EDVW-based splitting functions, we propose an efficient algorithm to compute the eigenvector associated with the second smallest eigenvalue of the hypergraph 1-Laplacian. We then utilize this eigenvector to cluster the vertices, achieving higher clustering accuracy than traditional spectral clustering based on the 2-Laplacian. More broadly, the proposed algorithm works for all submodular hypergraphs that are graph reducible. Numerical experiments using real-world data demonstrate the effectiveness of combining spectral clustering based on the 1-Laplacian and EDVW. 

   more » « less
4. SF-GRASS: solver-free graph spectral sparsification

   https://doi.org/10.1145/3400302.3415629  

   Zhang, Ying; Zhao, Zhiqiang; Feng, Zhuo (November 2020, International Conference on Computer-Aided Design)

   null (Ed.)

   Recent spectral graph sparsification techniques have shown promising performance in accelerating many numerical and graph algorithms, such as iterative methods for solving large sparse matrices, spectral partitioning of undirected graphs, vectorless verification of power/thermal grids, representation learning of large graphs, etc. However, prior spectral graph sparsification methods rely on fast Laplacian matrix solvers that are usually challenging to implement in practice. This work, for the first time, introduces a solver-free approach (SF-GRASS) for spectral graph sparsification by leveraging emerging spectral graph coarsening and graph signal processing (GSP) techniques. We introduce a local spectral embedding scheme for efficiently identifying spectrally-critical edges that are key to preserving graph spectral properties, such as the first few Laplacian eigenvalues and eigenvectors. Since the key kernel functions in SF-GRASS can be efficiently implemented using sparse-matrix-vector-multiplications (SpMVs), the proposed spectral approach is simple to implement and inherently parallel friendly. Our extensive experimental results show that the proposed method can produce a hierarchy of high-quality spectral sparsifiers in nearly-linear time for a variety of real-world, large-scale graphs and circuit networks when compared with prior state-of-the-art spectral methods. 

   more » « less
5. Strong Consistency, Graph Laplacians, and the Stochastic Block Model

   Deng, Shaofeng; Ling, Shuyang; Strohmer, Thomas (May 2021, Journal of machine learning research)

   Spectral clustering has become one of the most popular algorithms in data clustering and community detection. We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the stochastic block model. Our aim is to answer the following question: when is spectral clustering via the graph Laplacian able to achieve strong consistency, i.e., the exact recovery of the underlying hidden communities? Our work provides an entrywise analysis (an ℓ∞-norm perturbation bound) of the Fiedler eigenvector of both the unnormalized and the normalized Laplacian associated with the adjacency matrix sampled from the stochastic block model. We prove that spectral clustering is able to achieve exact recovery of the planted community structure under conditions that match the information-theoretic limits. 

   more » « less