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. Spectrally approximating large graphs with smaller graphs
 
conference paper

Spectrally approximating large graphs with smaller graphs

Loukas, Andreas  
•
Vandergheynst, Pierre  
July 10, 2018
Proceedings of International Conference in Machine Learning 2018
International Conference in Machine Learning (ICML)

How does coarsening affect the spectrum of a general graph? We provide conditions such that the principal eigenvalues and eigenspaces of a coarsened and original graph Laplacian matrices are close. The achieved approximation is shown to depend on standard graph-theoretic properties, such as the degree and eigenvalue distributions, as well as on the ratio between the coarsened and actual graph sizes. Our results carry implications for learning methods that utilize coarsening. For the particular case of spectral clustering, they imply that coarse eigenvectors can be used to derive good quality assignments even without refinement---this phenomenon was previously observed, but lacked formal justification.

  • Files
  • Details
  • Metrics
Type
conference paper
Author(s)
Loukas, Andreas  
Vandergheynst, Pierre  
Date Issued

2018-07-10

Published in
Proceedings of International Conference in Machine Learning 2018
Subjects

graph coarsening

•

graph sparsification

•

randomized matching

•

spectral approximation

•

restricted spectral similarity

•

graph spectral methods

•

spectral clustering

•

non-linear dimensionality reduction

•

ml-ai

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LTS2  
Event nameEvent placeEvent date
International Conference in Machine Learning (ICML)

Stockholmsmässan, Sweden

July 10-15, 2018

Available on Infoscience
May 11, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/146395
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