Improving Graph Clustering Precision using Stacked Auto-Encoders

Présentée dans le cadre des séminaires étudiants de l’IID, présentation de Sara Karamivarnamkhast, étudiante au doctorat en génie électrique à l’Université Laval, sous la supervision de Christian Gagné portant sur l’amélioration de la précision de la classification des graphes à l’aide d’encodeurs automatiques empilés.

Date
  • 21 décembre 2021
Heure

15h00 à 16h00

Localisation

En ligne

Coûts

Gratuit

Résumé de la conférence

Graph clustering is one of the most fundamental tasks in machine learning, aimed to assign a graph’s nodes to separate clusters obtaining maximum intra-cluster edge density, while the inter-cluster edge density is minimized. Exploiting the deep neural networks (DNNs) ability in learning non-linear low dimensional representations and extracting key features of data, we propose a novel method employing stacked auto-encoders (SAEs) –a family of DNNs– for graph clustering. This method has 3 main steps: (1) dimensionality reduction (DR) using a sparse SAE, (2) fine-tuning the SAE by jointly optimizing the previous loss function and a newly adopted clustering penalty to make the learned representation more clustering friendly, and (3) applying K-means to extract clusters. The sequential application of DR and K-means is well studied in graph clustering context.

The novelty of our method lies in augmenting this common approach with an intermediate step, i.e., the unsupervised fine-tuning step with an objective function tailored to enforce similar nodes to stay close to each other in latent space; therefore, not only is the dimensionality reduced but also the clusters become denser and more separable. The experimental results on various graphs suggest up to 4% improvement in accuracy measured by NMI, and up to 10% and 2% improvement in clustering quality in terms of Modularity and Conductance, respectively.

Restons en contact!

Vous souhaitez être informé des nouvelles et activités de l'IID? Abonnez-vous dès maintenant à notre infolettre mensuelle.