Efficient Approximation Algorithms for Spanning Centrality

Shiqi Zhang; Renchi Yang; Jing Tang; Xiaokui Xiao; Bo Tang

doi:10.1145/3580305.3599323

Efficient Approximation Algorithms for Spanning Centrality

Shiqi Zhang, Renchi Yang, Jing Tang, Xiaokui Xiao^*, Bo Tang^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

1 Citation (Scopus)

Abstract

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 state of the arts often by over one order of magnitude speedup without degrading the accuracy.

Original language	English
Title of host publication	KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Editors	Ambuj Singh, Yizhou Sun
Publisher	Association for Computing Machinery (ACM)
Pages	3386–3395
Number of pages	10
ISBN (Print)	9798400701030
DOIs	https://doi.org/10.1145/3580305.3599323
Publication status	Published - Aug 2023
Event	29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023 - Long Beach, United States Duration: 6 Aug 2023 → 10 Aug 2023 https://kdd.org/kdd2023/ https://dl.acm.org/doi/proceedings/10.1145/3580305

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference	29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023
Country/Territory	United States
City	Long Beach
Period	6/08/23 → 10/08/23
Internet address	https://kdd.org/kdd2023/ https://dl.acm.org/doi/proceedings/10.1145/3580305

Scopus Subject Areas

Software
Information Systems

User-Defined Keywords

eigenvector
graph traversal
random walk
spanning centrality

Access to Document

10.1145/3580305.3599323

Cite this

Zhang, S., Yang, R., Tang, J., Xiao, X., & Tang, B. (2023). Efficient Approximation Algorithms for Spanning Centrality. In A. Singh, & Y. Sun (Eds.), KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 3386–3395). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Association for Computing Machinery (ACM). https://doi.org/10.1145/3580305.3599323

Zhang, Shiqi ; Yang, Renchi ; Tang, Jing et al. / Efficient Approximation Algorithms for Spanning Centrality. KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. editor / Ambuj Singh ; Yizhou Sun. Association for Computing Machinery (ACM), 2023. pp. 3386–3395 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{04eb7ea4a2494fa399befbf98ec1628e,

title = "Efficient Approximation Algorithms for Spanning Centrality",

abstract = "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 state of the arts often by over one order of magnitude speedup without degrading the accuracy.",

keywords = "eigenvector, graph traversal, random walk, spanning centrality",

author = "Shiqi Zhang and Renchi Yang and Jing Tang and Xiaokui Xiao and Bo Tang",

note = "Funding Information: This work is partially supported by the National Natural Science Foundation of China (Grant No. U22B2060), by Shenzhen Fundamental Research Program (Grant No. 20220815112848002), by Guangzhou Municipal Science and Technology Bureau (Grant No. 2023A03J0667), and by HKUST(GZ) and HKBU under Start-up Grants. Bo Tang is also affiliated with the Research Institute of Trustworthy Autonomous Systems, Southern University of Science and Technology, Shenzhen, China. Publisher Copyright: {\textcopyright} 2023 Owner/Author.; 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023 ; Conference date: 06-08-2023 Through 10-08-2023",

year = "2023",

month = aug,

doi = "10.1145/3580305.3599323",

language = "English",

isbn = "9798400701030",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery (ACM)",

pages = "3386–3395",

editor = "Ambuj Singh and Yizhou Sun",

booktitle = "KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining",

address = "United States",

url = "https://kdd.org/kdd2023/, https://dl.acm.org/doi/proceedings/10.1145/3580305",

}

Zhang, S, Yang, R, Tang, J, Xiao, X & Tang, B 2023, Efficient Approximation Algorithms for Spanning Centrality. in A Singh & Y Sun (eds), KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery (ACM), pp. 3386–3395, 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, California, United States, 6/08/23. https://doi.org/10.1145/3580305.3599323

Efficient Approximation Algorithms for Spanning Centrality. / Zhang, Shiqi; Yang, Renchi; Tang, Jing et al.
KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ed. / Ambuj Singh; Yizhou Sun. Association for Computing Machinery (ACM), 2023. p. 3386–3395 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Efficient Approximation Algorithms for Spanning Centrality

AU - Zhang, Shiqi

AU - Yang, Renchi

AU - Tang, Jing

AU - Xiao, Xiaokui

AU - Tang, Bo

N1 - Funding Information: This work is partially supported by the National Natural Science Foundation of China (Grant No. U22B2060), by Shenzhen Fundamental Research Program (Grant No. 20220815112848002), by Guangzhou Municipal Science and Technology Bureau (Grant No. 2023A03J0667), and by HKUST(GZ) and HKBU under Start-up Grants. Bo Tang is also affiliated with the Research Institute of Trustworthy Autonomous Systems, Southern University of Science and Technology, Shenzhen, China. Publisher Copyright: © 2023 Owner/Author.

PY - 2023/8

Y1 - 2023/8

N2 - 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 state of the arts often by over one order of magnitude speedup without degrading the accuracy.

AB - 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 state of the arts often by over one order of magnitude speedup without degrading the accuracy.

KW - eigenvector

KW - graph traversal

KW - random walk

KW - spanning centrality

UR - http://www.scopus.com/inward/record.url?scp=85171328320&partnerID=8YFLogxK

U2 - 10.1145/3580305.3599323

DO - 10.1145/3580305.3599323

M3 - Conference proceeding

SN - 9798400701030

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 3386

EP - 3395

BT - KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

A2 - Singh, Ambuj

A2 - Sun, Yizhou

PB - Association for Computing Machinery (ACM)

T2 - 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023

Y2 - 6 August 2023 through 10 August 2023

ER -

Zhang S, Yang R, Tang J, Xiao X, Tang B. Efficient Approximation Algorithms for Spanning Centrality. In Singh A, Sun Y, editors, KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery (ACM). 2023. p. 3386–3395. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/3580305.3599323

Efficient Approximation Algorithms for Spanning Centrality

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this