2nd UGent Data Science Seminar with Prof. Aristides Gionis
Prof. Aristides Gionis (Aalto University, Finland): Active network alignment
Abstract
Network alignment is the problem of matching the nodes of two graphs, maximizing the similarity of the matched nodes and the edges between them. This problem is encountered in a wide array of applications-from biological networks to social networks to ontologies-where multiple networked data sources need to be integrated. Due to the difficulty of the task, an accurate alignment can rarely be found without human assistance. Thus, it is of great practical importance to develop network alignment algorithms that can optimally leverage experts who are able to provide the correct alignment for a small number of nodes. Yet, only a handful of existing works address this active network alignment setting.
The majority of the existing active methods focus on absolute queries (“are nodes a and b the same or not?”), whereas we argue that it is generally easier for a human expert to answer relative queries (“which node in the set {b1,…,bn} is the most similar to node a?”). We introduce two novel relative-query strategies, which can be applied on top of any network alignment method that constructs and solves a bipartite matching problem. Our methods identify the most informative nodes to query by sampling the matchings of the bipartite graph associated to the network-alignment instance. We compare the proposed approaches to several commonly-used query strategies and perform experiments on both synthetic and real-world datasets. Our sampling-based strategies outperform other baseline methods by more than 15 percentage points in some cases.
The presentation is based on joint work with Eric Malmi and Evimaria Terzi.
Bio
Aristides Gionis is a professor in the department of Computer Science in Aalto University. Previously he has been a senior research scientist in Yahoo! Research. He is currently serving as an action editor in the Data Management and Knowledge Discovery journal (DMKD), an associate editor in the ACM Transactions on Knowledge Discovery from Data (TKDD), and a managing editor in Internet Mathematics. He has contributed in several areas of data science, such as graph mining, social-media analysis, web mining, data clustering, and privacy-preserving data mining.
From 13:00 a sandwich lunch will be served for registered participants to continue discussions.