----------------------------------------------------------------------------------------------------

    Department of Systems Engineering and Engineering Management

                       The Chinese University of Hong Kong

----------------------------------------------------------------------------------------------------

Date: Friday, October 20, 2023, 4:30pm to 5:30pm HKT

Venue: ERB 513, The Chinese University of Hong Kong

Title: Efficient Approximation Algorithms for Spanning Centrality

Speaker: Dr. Renchi Yang, Department of Computer Science at Hong Kong Baptist University

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 offer 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.

Biography:

Dr. Renchi Yang is currently an Assistant Professor at the Department of Computer Science, Hong Kong Baptist University. He received his Ph.D. degree in computer science from Nanyang Technological University, followed by a postdoctoral stint at the National University of Singapore. His research mainly focuses on developing efficient algorithms and systems for large-scale data management, analytics, and mining, with special interests in big graph processing, similarity search, community detection, and graph representation learning. He has published over 20 papers in big data-related conferences/journals including SIGMOD, VLDB, TODS, VLDBJ, KDD, and WWW. His research works received the VLDB 2021 Best Research Paper Award, the 2022 ACM SIGMOD Research Highlight Award, and the Best Paper Award Nominee in WWW 2022.

Everyone is welcome to attend the talk!

SEEM-5201 Website: http://seminar.se.cuhk.edu.hk

Email: seem5201@se.cuhk.edu.hk