Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Graph Coarsening with Preserved Spectral Properties
 
conference paper

Graph Coarsening with Preserved Spectral Properties

Jin, Yu
•
Loukas, Andreas  
•
Jaja, Joseph F.
January 1, 2020
International Conference On Artificial Intelligence And Statistics, Vol 108
23rd International Conference on Artificial Intelligence and Statistics (AISTATS)

In graph coarsening, one aims to produce a coarse graph of reduced size while preserving important graph properties. However, as there is no consensus on which specific graph properties should be preserved by coarse graphs, measuring the differences between original and coarse graphs remains a key challenge. This work relies on spectral graph theory to justify a distance function constructed to measure the similarity between original and coarse graphs. We show that the proposed spectral distance captures the structural differences in the graph coarsening process. We also propose graph coarsening algorithms that aim to minimize the spectral distance. Experiments show that the proposed algorithms can outperform previous graph coarsening methods in graph classification and stochastic block recovery tasks.

  • Details
  • Metrics
Type
conference paper
Web of Science ID

WOS:000559931301063

Author(s)
Jin, Yu
Loukas, Andreas  
Jaja, Joseph F.
Date Issued

2020-01-01

Publisher

ADDISON-WESLEY PUBL CO

Publisher place

Boston

Published in
International Conference On Artificial Intelligence And Statistics, Vol 108
Series title/Series vol.

Proceedings of Machine Learning Research

Volume

108

Start page

4452

End page

4461

Subjects

Computer Science, Artificial Intelligence

•

Statistics & Probability

•

Computer Science

•

Mathematics

•

sparsification

•

distances

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LTS2  
Event nameEvent placeEvent date
23rd International Conference on Artificial Intelligence and Statistics (AISTATS)

ELECTR NETWORK

Aug 26-28, 2020

Available on Infoscience
October 25, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/172731
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés