ISyE Department Seminar - Laurent Massoulié

Event Details
Contact
No contact information submitted.
Summaries

Summary Sentence: From tree matching to graph alignment

Full Summary: Title: From tree matching to graph alignment Joint work with Luca Ganassali   Abstract: In this work we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erdős-Rényi random graphs, we prove that the algorithm returns -- in polynomial time -- a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds with average degree of the graphs in O(1) and correlation parameter s bounded away from 1, conditions under which random graph alignment is particularly challenging. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent.  

Abstract: In this work we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erdős-Rényi random graphs, we prove that the algorithm returns -- in polynomial time -- a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds with average degree of the graphs in O(1) and correlation parameter s bounded away from 1, conditions under which random graph alignment is particularly challenging. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent.

 

Bio: Laurent Massoulié is research director at Inria, head of the Microsoft Research – Inria Joint Centre, and professor at the Applied Maths Centre of Ecole Polytechnique. His research interests are in machine learning, probabilistic modelling and algorithms for networks. He has held research scientist positions at: France Telecom, Microsoft Research, Thomson-Technicolor, where he headed the Paris Research Lab. He obtained best paper awards at IEEE INFOCOM 1999, ACM SIGMETRICS 2005, ACM CoNEXT 2007, NeurIPS 2018, was elected "Technicolor Fellow" in 2011, received the  "Grand Prix Scientifique" of the Del Duca Foundation delivered by the French Academy of Science in 2017, and is a Fellow of the “Prairie” Institute.

Related Links

Additional Information

In Campus Calendar
Yes
Groups

School of Industrial and Systems Engineering (ISYE)

Invited Audience
Faculty/Staff, Postdoc, Public, Graduate students, Undergraduate students
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: sbryantturner3
  • Workflow Status: Published
  • Created On: Oct 9, 2020 - 1:51pm
  • Last Updated: Oct 9, 2020 - 1:51pm