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. A Shared-Memory Parallel Algorithm for Updating Single-Source Shortest Paths in Large Dynamic Networks

   https://doi.org/10.1109/HiPC.2018.00035  

   Srinivasan, Sriram; Riazi, Sara; Norris, Boyana; Das, Sajal K.; Bhowmick, Sanjukta (December 2018, 2018 IEEE 25th International Conference on High Performance Computing (HiPC))

   Computing the single-source shortest path (SSSP) is one of the fundamental graph algorithms, and is used in many applications. Here, we focus on computing SSSP on large dynamic graphs, i.e. graphs whose structure evolves with time. We posit that instead of recomputing the SSSP for each set of changes on the dynamic graphs, it is more efficient to update the results based only on the region of change. To this end, we present a novel two-step shared-memory algorithm for updating SSSP on weighted large-scale graphs. The key idea of our algorithm is to identify changes, such as vertex/edge addition and deletion, that affect the shortest path computations and update only the parts of the graphs affected by the change. We provide the proof of correctness of our proposed algorithm. Our experiments on real and synthetic networks demonstrate that our algorithm is as much as 4X faster compared to computing SSSP with Galois, a state-of-the-art parallel graph analysis software for shared memory architectures. We also demonstrate how increasing the asynchrony can lead to even faster updates. To the best of our knowledge, this is one of the first practical parallel algorithms for updating networks on shared-memory systems, that is also scalable to large networks. 

   more » « less
3. Learning Backbones: Sparsifying Graphs Through Zero Forcing for Effective Graph-Based Learning

   Ahmad, Obaid Ullah; Said, Anwar; Shabbir, Mudassir; Koutsoukos, Xenofon; Abbas, Waseem (April 2025, Springer Nature Switzerland)

   Cherifi, Hocine; Donduran, Murat; Rocha, Luis; Cherifi, Chantal; Varol, Onur (Ed.)

   This paper introduces a novel framework for graph sparsification that preserves the essential learning attributes of original graphs, improving computational efficiency and reducing complexity in learning algorithms. We refer to these sparse graphs as “learning backbones.” Our approach leverages the zero-forcing (ZF) phenomenon, a dynamic process on graphs with applications in network control. The key idea is to generate a tree from the original graph that retains critical dynamical properties. By correlating these properties with learning attributes, we construct effective learning backbones. We evaluate the performance of our ZF-based backbones in graph classification tasks across eight datasets and six baseline models. The results demonstrate that our method outperforms existing techniques. Additionally, we explore extensions using node distance metrics to further enhance the framework’s utility. 

   more » « less
4. Learning Backbones: Sparsifying Graphs Through Zero Forcing for Effective Graph-Based Learning

   https://doi.org/10.1007/978-3-031-82427-2_8  

   Ahmad, Obaid Ullah; Said, Anwar; Shabbir, Mudassir; Koutsoukos, Xenofon; Abbas, Waseem (April 2025, Springer Nature Switzerland)

   This paper introduces a novel framework for graph sparsification that preserves the essential learning attributes of original graphs, improving computational efficiency and reducing complexity in learning algorithms. We refer to these sparse graphs as ``learning backbones.'' Our approach leverages the zero-forcing (ZF) phenomenon, a dynamic process on graphs with applications in network control. The key idea is to generate a tree from the original graph that retains critical dynamical properties. By correlating these properties with learning attributes, we construct effective learning backbones. We evaluate the performance of our ZF-based backbones in graph classification tasks across eight datasets and six baseline models. The results demonstrate that our method outperforms existing techniques. Additionally, we explore extensions using node distance metrics to further enhance the framework's utility. 

   more » « less
5. Vertex Sparsification for Edge Connectivity

   https://doi.org/10.1137/1.9781611976465.74  

   Chalermsook, Parinya; Das, Syamantak Das; Kook, Yunbum; Laekhanukit, Bundit; Liu, Yang P.; Peng, Richard Peng; Sellke, Mark; Vaz, Daniel (January 2021, Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021)

   null (Ed.)

   Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $$(1+\epsilon)$$-approximate cut-preserving 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 give a separate algorithm that constructs such graphs of size $$k \cdot O(c)^{2c}$$ in time $$mc^{O(c)}\log^{O(1)}n$$. These results lead to the first offline data structures for answering fully dynamic $$c$$-edge-connectivity queries for $$c \ge 4$$ in polylogarithmic time per query as well as more efficient algorithms for survivable network design on bounded treewidth graphs. 

   more » « less