# Efficient Approximation Algorithms for Spanning Centrality

arXiv: https://arxiv.org/abs/2305.16086 · HTML: https://mlsanity.com/paper/2305.16086/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2023.

## Built on by (most cited first, 6 of 6)

- [Efficient Topology-aware Data Augmentation for High-Degree Graph Neural Networks](https://mlsanity.com/paper/2406.05482/) (2024)
- [Cequel: Cost-Effective Querying of Large Language Models for Text Clustering](https://mlsanity.com/paper/2504.15640/) (2025)
- [Efficient Algorithms for Computing Random Walk Centrality](https://mlsanity.com/paper/2510.20604/) (2025)
- [Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks](https://mlsanity.com/paper/2602.09716/) (2026)
- [SAFT: Structure-aware Transformers for Textual Interaction Classification](https://mlsanity.com/paper/2504.04861/) (2025)
- [Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks](https://mlsanity.com/paper/2609.31466/) (2026)

## Abstract (arXiv)

Given a graph G, the spanning centrality (SC) of an edge e measures the importance of e for G to be connected. In practice, SC has seen extensive applications in computational biology, electrical networks, and combinatorial optimization. However, it is highly challenging to compute the SC of all edges (AESC) on large graphs. Existing techniques fail to deal with such graphs, as they either suffer from expensive matrix operations or require sampling numerous long random walks. To circumvent these issues, this paper proposes TGT and its enhanced version TGT+, two algorithms for AESC computation that offers rigorous theoretical approximation guarantees. In particular, TGT remedies the deficiencies of previous solutions by conducting deterministic graph traversals with carefully-crafted truncated lengths. TGT+ further advances TGT in terms of both empirical efficiency and asymptotic performance while retaining result quality, based on the combination of TGT with random walks and several additional heuristic optimizations. We experimentally evaluate TGT+ against recent competitors for AESC using a variety of real datasets. The experimental outcomes authenticate that TGT+ outperforms the state of the arts often by over one order of magnitude speedup without degrading the accuracy.