Aller au contenu. | Aller à la navigation

Outils personnels

Navigation

Voir le monde en interaction

  • Logo CNRS
  • Logo ENSL
  • logo-enssib.jpg
Vous êtes ici : Accueil / Agenda / Séminaires / Talk by Andreas Loukas (EPFL) : Graph reduction by local variation

Talk by Andreas Loukas (EPFL) : Graph reduction by local variation

Can we reduce the size of a graph without significantly altering its basic properties? We will approach the graph reduction problem from the perspective of restricted similarity, a modification of a well-known measure for graph approximation. Our choice is motivated by the observation that restricted similarity implies strong spectral guarantees and can be used to prove statements about certain unsupervised learning problems. The talk will then focus on coarsening, a popular type of graph reduction. We will derive sufficient conditions for a small graph to approximate a larger one in the sense of restricted similarity. Our findings give rise to nearly-linear coarsening algorithms that find coarse graphs of improved quality, often by a large margin, without sacrificing speed.
Quand ? Le 11/10/2018,
de 13:30 à 14:30
Où ? M7.101
Ajouter un événement au calendrier vCal
iCal

Graph reduction by local variation

Abstract:
Can we reduce the size of a graph without significantly altering its basic properties?
We will approach the graph reduction problem from the perspective of restricted similarity,
a modification of a well-known measure for graph approximation. Our choice is motivated
by the observation that restricted similarity implies strong spectral guarantees and can be
used to prove statements about certain unsupervised learning problems. The talk will then
focus on coarsening, a popular type of graph reduction. We will derive sufficient conditions
for a small graph to approximate a larger one in the sense of restricted similarity. Our findings
give rise to nearly-linear coarsening algorithms that find coarse graphs of improved quality,
often by a large margin, without sacrificing speed.

paper: https://arxiv.org/abs/1808.10650

https://scholar.google.fr/citations?hl=fr&user=-XGXJbQAAAAJ&view_op=list_works&sortby=pubdate