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. Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

   https://doi.org/10.1109/FOCS46700.2020.00109  

   Chen, Li; Goranci, Gramoz; Henzinger, Monika; Peng, Richard; Saranurak, Thatchaphol (November 2020, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020)

   null (Ed.)

   We present a general framework of designing efficient dynamic approximate algorithms for optimization on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1) A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in $$\tilde{O}(n^{2/3})$$ amortized time against an oblivious adversary, and $$\tilde{O}(m^{3/4})$$ time against an adaptive adversary. (2) An incremental data structure that maintains $O(1)$-approximate shortest path in $$n^{o(1)}$$ time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in $$\tilde{O}(n^{2/3+o(1)})$$ amortized time per operation. (3) A fully-dynamic algorithm that approximates all-pair effective resistance up to an $$(1+\eps)$$ factor in $$\tilde{O}(n^{2/3+o(1)} \epsilon^{-O(1)})$$ amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as j-trees) and approximately captures the cut-flow and metric structure of the graph. The $O(1)$-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM `05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC `19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. 

   more » « less
3. Graph Few-Shot Learning via Knowledge Transfer

   https://doi.org/10.1609/aaai.v34i04.6142  

   Yao, Huaxiu; Zhang, Chuxu; Wei, Ying; Jiang, Meng; Wang, Suhang; Huang, Junzhou; Chawla, Nitesh; Li, Zhenhui (June 2020, Proceedings of the AAAI Conference on Artificial Intelligence)

   Towards the challenging problem of semi-supervised node classification, there have been extensive studies. As a frontier, Graph Neural Networks (GNNs) have aroused great interest recently, which update the representation of each node by aggregating information of its neighbors. However, most GNNs have shallow layers with a limited receptive field and may not achieve satisfactory performance especially when the number of labeled nodes is quite small. To address this challenge, we innovatively propose a graph few-shot learning (GFL) algorithm that incorporates prior knowledge learned from auxiliary graphs to improve classification accuracy on the target graph. Specifically, a transferable metric space characterized by a node embedding and a graph-specific prototype embedding function is shared between auxiliary graphs and the target, facilitating the transfer of structural knowledge. Extensive experiments and ablation studies on four real-world graph datasets demonstrate the effectiveness of our proposed model and the contribution of each component. 

   more » « less
4. Improved Dynamic Graph Learning through Fault-Tolerant Sparsification

   Zhu, Chunjiang; Storandt, Sabine; Lam, Kam-Yiu; Han, Song; Bi, Jinbo (July 2019, Proceedings of the 36th International Conference on Machine Learning)

   Graph sparsification has been used to improve the computational cost of learning over graphs, e.g., Laplacian-regularized estimation and graph semi-supervised 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 fault-tolerant (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 Laplacian-regularized estimation and graph SSL, due to the FT sparsification. In addition, FT spectral sparsification can be generalized to FT cut sparsification, for cut-based graph learning. Extensive experiments have confirmed the computational efficiencies and accuracies of the proposed methods for learning on dynamic graphs. 

   more » « less
5. diGRASS: Directed Graph Spectral Sparsification via Spectrum-Preserving Symmetrization

   https://doi.org/10.1145/3639568  

   Zhang, Ying; Zhao, Zhiqiang; Feng, Zhuo (May 2024, ACM Transactions on Knowledge Discovery from Data)

   Recent spectral graph sparsificationresearch aims to construct ultra-sparse subgraphs for preserving the original graph spectral (structural) properties, such as the first few Laplacian eigenvalues and eigenvectors, which has led to the development of a variety of nearly linear time numerical and graph algorithms. However, there is very limited progress in the spectral sparsification of directed graphs. In this work, we prove the existence of nearly linear-sized spectral sparsifiers for directed graphs under certain conditions. Furthermore, we introduce a practically efficient spectral algorithm (diGRASS) for sparsifying real-world, large-scale directed graphs leveraging spectral matrix perturbation analysis. The proposed method has been evaluated using a variety of directed graphs obtained from real-world applications, showing promising results for solving directed graph Laplacians, spectral partitioning of directed graphs, and approximately computing (personalized) PageRank vectors. 

   more » « less