Unveiling the Power and Limitations of Unsupervised Node Embeddings

Ομιλητής: Χαράλαμπος Τσουρακάκης, καθηγητής στο τμήμα Πληροφορικής του Πανεπιστημίου της Βοστώνης.

Ώρα/τόπος: 3-4μμ, Δευτέρα 12/6, Τ105 (Τροίας)

Περίληψη:

Node embeddings, an emerging field at the intersection of network analysis and machine learning, have revolutionized the way we understand and analyze complex networks. Node embedding methods represent nodes in a network as low-dimensional vectors in a continuous space by leveraging techniques such as random walks, and deep learning architectures.

During this talk, I will delve into fundamental questions related to the power and limitations of node embeddings.   What information is encoded by popular node embedding methods such as DeepWalk and node2vec? How does this information correlate with performance in downstream machine learning tasks? Can we invert node embedding to approximately or exactly recover the input graph?  We answer these questions and we also show that low dimensional embeddings can provably capture important properties of real-world complex networks. We also study the power of edge independent random graph models (e.g., NetGAN or other generative models that model the likelihood of an edge based on the proximity of its embedded endpoints) with respect to their ability to generate graphs that are rich in triangles, a hallmark property of many real-world networks.  We prove foundational limitations of such models and we propose a novel hierarchy of models that are progressively more powerful. 

Joint works with Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos

Short Bio: Charalampos Tsourakakis is an Assistant Professor in Computer Science at Boston University and a research associate at Harvard. Dr. Tsourakakis obtained his PhD in Algorithms, Combinatorics and Optimization at Carnegie Mellon under the supervision of Alan Frieze, was a postdoctoral fellow at Brown University and Harvard under the supervision of Eli Upfal and Michael Mitzenmacher, respectively. Before joining Boston University, he worked as a researcher in the Google Brain team. He has received the 10-year highest impact paper award from IEEE, has won a best paper award in IEEE Data Mining, has delivered three tutorials in the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, and has designed two graph mining libraries for large-scale graph mining, one of which has been officially included in Windows Azure. His research focuses on large-scale graph mining, and machine learning.