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 solverfree approach (SFGRASS) 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 spectrallycritical edgesmore »
Improved Dynamic Graph Learning through FaultTolerant Sparsification
Graph sparsification has been used to improve the computational cost of learning over graphs, e.g., Laplacianregularized estimation and graph semisupervised learning (SSL). However, when graphs vary over time, repeated sparsification requires polynomial order computational cost per update. We propose a new type of graph sparsification namely faulttolerant (FT) sparsification to significantly reduce the cost to only a constant. Then the computational cost of subsequent graph learning tasks can be significantly improved with limited loss in their accuracy. In particular, we give theoretical analyze to upper bound the loss in the accuracy of the subsequent Laplacianregularized estimation and graph SSL, due to the FT sparsification. In addition, FT spectral sparsification can be generalized to FT cut sparsification, for cutbased graph learning. Extensive experiments have confirmed the computational efficiencies and accuracies of the proposed methods for learning on dynamic graphs.
 Award ID(s):
 1718738
 Publication Date:
 NSFPAR ID:
 10107148
 Journal Name:
 Proceedings of the 36th International Conference on Machine Learning
 Volume:
 97
 Page Range or eLocationID:
 76247633
 Sponsoring Org:
 National Science Foundation
More Like this


Computing similarity between graphs is a fundamental and critical problem in graphbased applications, and one of the most commonly used graph similarity measures is graph edit distance (GED), defined as the minimum number of graph edit operations that transform one graph to another. Existing GED solutions suffer from severe performance issues due in particular to the NPhardness of exact GED computation. Recently, deep learning has shown early promise for GED approximation with high accuracy and low computational cost. However, existing methods treat GED as a global, coarsegrained graph similarity value, while neglecting the typespecific transformative impacts incurred by different typesmore »

Recently there has been significant interest in using machine learning to improve the accuracy of cardinality estimation. This work has focused on improving average estimation error, but not all estimates matter equally for downstream tasks like query optimization. Since learned models inevitably make mistakes, the goal should be to improve the estimates that make the biggest difference to an optimizer. We introduce a new loss function, FlowLoss, for learning cardinality estimation models. FlowLoss approximates the optimizer's cost model and search algorithm with analytical functions, which it uses to optimize explicitly for better query plans. At the heart of FlowLoss ismore »

Graph compression or sparsification is a basic informationtheoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$approximate cutpreserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we initiate the study of a thresholded version of the problem: for a given parameter $c$, find a smaller graph, which we call \emph{connectivity$c$ mimicking network}, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that connectivity$c$ mimicking networks of size $O(kc^4)$ exist and can be found in time $m(c\log n)^{O(c)}$. We also givemore »

The application of graph Laplacian eigenvectors has been quite popular in the graph signal processing field: one can use them as ingredients to design smooth multiscale basis. Our longterm goal is to study and understand the dual geometry of graph Laplacian eigenvectors. In order to do that, it is necessary to define a certain metric to measure the behavioral differences between each pair of the eigenvectors. Saito (2018) considered the ramified optimal transportation (ROT) cost between the square of the eigenvectors as such a metric. Clonginger and Steinerberger (2018) proposed a way to measure the affinity (or `similarity') between themore »