Overview
We consider the graph alignment problem, where the goal is to identify the vertex/user correspondence between two correlated graphs. Existing work mostly recovers the correspondence by exploiting the user-user connections. However, in many real-world applications, additional information about the users, such as affiliation or educational background, might be publicly available. In this talk, we introduce the attributed graph alignment problem, where additional user information, referred to as attributes, is incorporated to assist graph alignment. We derive information-theoretic limits, which demonstrate the benefit of attribute information. When specialized to seeded graph alignment and bipartite graph alignment, the region we derive improves the existing region. For the vanilla graph alignment problem (without attribute information), it is conjectured that constant edge correlation is required for any polynomial-time algorithms to achieve exact recovery. We demonstrate that with a vanishing amount of additional attribute information, it is possible to design polynomial-time algorithms that achieve exact recovery with vanishing edge correlation.
Speaker
Lele Wang
Lele Wang is an Assistant Professor in the Department of Electrical and Computer Engineering at the University of British Columbia, Vancouver. Before joining UBC, she was an NSF Center for Science of Information postdoctoral fellow. From 2015 to 2017, she was a postdoctoral researcher at Stanford University and Tel Aviv University. She received her Ph.D. degree in Communication Theory and Systems at the University of California, San Diego, in 2015. She attended the Academic Talent Program and obtained a B.E. degree at Tsinghua University, China in 2009. Her research interests include information theory, coding theory, communication theory, statistical inference on graphs, and high-dimensional statistics. She is a recipient of the 2013 UCSD Shannon Memorial Fellowship, the 2013-2014 Qualcomm Innovation Fellowship, and the 2017 NSF Center for Science of Information Postdoctoral Fellowship. Her PhD thesis “Channel coding techniques for network communication” won the 2017 IEEE Information Theory Society Thomas M. Cover Dissertation Award. She serves as the Vice President of the Canadian Society of Information Theory 2022-2025, an associate editor for the IEEE Transactions on Communications 2023-2026, and a guest associate editor for the IEEE Journal on Selected Areas on Information Theory 2023.
Event details
Speaker: Lele Wang
Date: August 7, 2024
Time: 2:00 PM – 4:30 PM
Location: ITB/A113