DSG Seminar Series • Efficient Network Embeddings for Large Graphs

Speaker: Xiaokui Xiao, National University of Singapore (Talk virtually over zoom)

Abstract: 

Given a graph G, network embedding maps each node in G into a compact, fixed-dimensional feature vector, which can be used in downstream machine learning tasks. Most of the existing methods for network embedding fail to scale to large graphs with millions of nodes, as they either incur significant computation cost or generate low-quality embeddings on such graphs. In this talk, we will present two efficient network embedding algorithms for large graphs with and without node attributes, respectively. The basic idea is to first model the affinity between nodes (or between nodes and attributes) based on random walks, and then factorize the affinity matrix to derive the embeddings. The main challenges that we address include (i) the choice of the affinity measure and (ii) the reduction of space and time overheads entailed by the construction and factorization of the affinity matrix. Extensive experiments on large graphs demonstrate that our algorithms outperform the existing methods in terms of both embedding quality and efficiency.

Bio: Xiaokui Xiao is a Dean's Chair Associate Professor at the School of Computing, National University of Singapore (NUS). His research focuses on data management, with special interests in data privacy and algorithms for large data. He received a Ph.D. in Computer Science from the Chinese University of Hong Kong in 2008. Before joining NUS in 2018, he was an associate professor at the Nanyang Technological University, Singapore.

Talk video