Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) Large-scale Heterogeneous DAta and Knowledge
A Family of Tractable Graph Distances
Stratis Ioannidis

04 July 2018, 10:30
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Web data management

Résumé :
Important data mining problems such as nearest-neighbour search and clustering admit theoretical guarantees when restricted to objects embedded in a metric space. Graphs are ubiquitous, and clustering and classification over graphs arise in diverse areas, including, e.g., image processing and social networks. Unfortunately, popular distance scores used in these applications that scale over large graphs are not metrics and thus come with no guarantees. Classic graph distances such as, e.g., the chemical distance and the Chartrand-Kubiki-Shultz (CKS) distance are arguably natural and intuitive, and are indeed metrics; however, these distances are intractable and their computation does not scale to large graphs. We define a broad family of graph distances, that includes both the chemical and the CKS distance, and prove that these are all metrics. Crucially, we show that our family includes metrics that are tractable. Moreover, we extend these distances by incorporating auxiliary node attributes, which is important in practice, while maintaining both the metric property and tractability.

Pour en savoir plus :
Séminaires
Heterogeneous Treatment Effects Estimation: When M
Automated Reasoning
Thursday 02 June 2022 - 10:30
Salle : 2011 - DIG-Moulon
Naoufal Acharki .............................................

Witness Generation for JSON Schema
Data-Centric Languages and Systems
Monday 30 May 2022 - 00:00
Salle : 455 - PCRI-N
Mohamed-Amine BAAZIZI .............................................

TUTORIAL CODALAB - Apprenez à organiser un challen
Wednesday 13 April 2022 - 00:00
Salle : 1 - DIG-Moulon
Adrien Pavao .............................................

Generative Neural Networks for Observational Causa
Automated Reasoning
Thursday 07 April 2022 - 10:30
Salle : 2011 - DIG-Moulon
Diviyan Kalainathan .............................................

Datamining in Epi- and Phylogenetics
Tuesday 15 March 2022 - 11:00
Salle : 455 - PCRI-N
Thomas Haschka .............................................