More Like this

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

   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. Graph embedding on biomedical networks: methods, applications and evaluations

   https://doi.org/10.1093/bioinformatics/btz718  

   Yue, Xiang ; Wang, Zhen ; Huang, Jingong ; Parthasarathy, Srinivasan ; Moosavinasab, Soheil ; Huang, Yungui ; Lin, Simon M ; Zhang, Wen ; Zhang, Ping ; Sun, Huan ; et al ( October 2019 , Bioinformatics)

   Abstract Motivation Graph embedding learning that aims to automatically learn low-dimensional node representations, has drawn increasing attention in recent years. To date, most recent graph embedding methods are evaluated on social and information networks and are not comprehensively studied on biomedical networks under systematic experiments and analyses. On the other hand, for a variety of biomedical network analysis tasks, traditional techniques such as matrix factorization (which can be seen as a type of graph embedding methods) have shown promising results, and hence there is a need to systematically evaluate the more recent graph embedding methods (e.g. random walk-based and neural network-based) in terms of their usability and potential to further the state-of-the-art. Results We select 11 representative graph embedding methods and conduct a systematic comparison on 3 important biomedical link prediction tasks: drug-disease association (DDA) prediction, drug–drug interaction (DDI) prediction, protein–protein interaction (PPI) prediction; and 2 node classification tasks: medical term semantic type classification, protein function prediction. Our experimental results demonstrate that the recent graph embedding methods achieve promising results and deserve more attention in the future biomedical graph analysis. Compared with three state-of-the-art methods for DDAs, DDIs and protein function predictions, the recent graph embedding methods achieve competitive performance without using any biological features and the learned embeddings can be treated as complementary representations for the biological features. By summarizing the experimental results, we provide general guidelines for properly selecting graph embedding methods and setting their hyper-parameters for different biomedical tasks. Availability and implementation As part of our contributions in the paper, we develop an easy-to-use Python package with detailed instructions, BioNEV, available at: https://github.com/xiangyue9607/BioNEV, including all source code and datasets, to facilitate studying various graph embedding methods on biomedical tasks. Supplementary information Supplementary data are available at Bioinformatics online. 

   more » « less
4. Graph Convolutional Networks: Algorithms, Applications and Open Challenges

   https://doi.org/https://doi.org/10.1007/978-3-030-04648-4_7  

   Si Zhang, Hanghang Tong ( October 2018 , International Conference on Computational Social Networks CSoNet 2018: Computational Data and Social Networks)

   Graph-structured data naturally appear in numerous application domains, ranging from social analysis, bioinformatics to computer vision. The unique capability of graphs enables capturing the structural relations among data, and thus allows to harvest more insights compared to analyzing data in isolation. However, graph mining is a challenging task due to the underlying complex and diverse connectivity patterns. A potential solution is to learn the representation of a graph in a low-dimensional Euclidean space via embedding techniques that preserve the graph properties. Although tremendous efforts have been made to address the graph representation learning problem, many of them still suffer from their shallow learning mechanisms. On the other hand, deep learning models on graphs have recently emerged in both machine learning and data mining areas and demonstrated superior performance for various problems. In this survey, we conduct a comprehensive review specifically on the emerging field of graph convolutional networks, which is one of the most prominent graph deep learning models. We first introduce two taxonomies to group the existing works based on the types of convolutions and the areas of applications, then highlight some graph convolutional network models in details. Finally, we present several challenges in this area and discuss potential directions for future research. 

   more » « less
5. Large sample spectral analysis of graph-based multi-manifold clustering

   Garcia Trillos, Nicolas ; He, Pengfei ; Li, Chenghui ( May 2023 , Journal of machine learning research)

   Carreira-Perpinan, Miguel (Ed.)

   In this work we study statistical properties of graph-based algorithms for multi-manifold clustering (MMC). In MMC the goal is to retrieve the multi-manifold structure underlying a given Euclidean data set when this one is assumed to be obtained by sampling a distribution on a union of manifolds M = M1 ∪ · · · ∪ MN that may intersect with each other and that may have different dimensions. We investigate sufficient conditions that similarity graphs on data sets must satisfy in order for their corresponding graph Laplacians to capture the right geometric information to solve the MMC problem. Precisely, we provide high probability error bounds for the spectral approximation of a tensorized Laplacian on M with a suitable graph Laplacian built from the observations; the recovered tensorized Laplacian contains all geometric information of all the individual underlying manifolds. We provide an example of a family of similarity graphs, which we call annular proximity graphs with angle constraints, satisfying these sufficient conditions. We contrast our family of graphs with other constructions in the literature based on the alignment of tangent planes. Extensive numerical experiments expand the insights that our theory provides on the MMC problem. 

   more » « less