Joint SINE/DCL Seminar: Matthias Grossglauser - Aligning and Assembling Networks without Labels

Signals, Inference, and Networks (SINE)

and

Decision and Control (DCL)
Lecture Series

Coordinated Science Laboratory

 

“Aligning and Assembling Networks without Labels”

 

Matthias Grossglauser, Ph.D.

École polytechnique fédérale de Lausanne (EPFL)

 

Wednesday, April 19, 2017

4:00 p.m. to 5:00 p.m.

141 CSL

____________________________________________________________________________________________________________________________________________________________________

Abstract:

A lot of data comes in the form of networks: social networks, the Web, the Internet, and biological networks, among others. Frequently, we cannot rely on globally unique labels, especially when we combine multiple datasets into a single network. This may be by design (e.g., anonymization), or inherent in the application (e.g., proteins with the same function are chemically different across species). In this talk, we explore two specific problems of combining network data under ambiguous node labels.

The first problem is network alignment: we observe two noisy, unlabeled versions of a hidden generator graph, and we wish to reconstruct the correct matching between the vertex sets of the observable graphs. This is akin to "noisy" graph isomorphism, with applications in social network privacy and in protein-protein interaction (PPI) network alignment.

The second problem is network assembly: we observe a set of small, unlabeled subgraphs of a hidden graph, which we wish to reconstruct. We describe a technique of fingerprinting every edge through an associated subgraph, such that assembly succeeds if all fingerprints are globally unique. This has applications in entity resolution and network anonymization.

For both problems, we first discuss random graph-based models to capture their salient features, and provide achievability results for perfect inference. We also give algorithmic results with provable performance guarantees over our random graph models, and comment on some pertinent applications.

Bio:

Matthias Grossglauser is Associate Professor in the School of Computer and Communication Sciences at EPFL. His current research interests are in stochastic models and algorithms for graph and mobility mining, and machine learning for large social systems, including recommender systems. He is also the current director of EPFL's Doctoral School in Computer and Communication Sciences.

From 2007-2010, he was with the Nokia Research Center (NRC) in Helsinki, Finland, serving as director of the Internet Laboratory, and driving a tech-transfer program focused on data mining and machine learning. In addition, he served on Nokia's CEO Technology Council, a technology advisory group reporting to the CEO. Prior to this, he was Assistant Professor at EPFL, and Principal Research Scientist in the Networking and Distributed Systems Laboratory at AT&T Research in New Jersey.

He received the 1998 Cor Baayen Award from the European Research Consortium for Informatics and Mathematics (ERCIM), the 2006 CoNEXT/SIGCOMM Rising Star Award.