Relaxation-based coarsening and multiscale graph organization

By Dorit Ron, Ilya Safro, Achi Brandt. 2010

140 citations recorded by the source corpus.

In this paper we generalize and improve the multiscale organization of graphs by introducing a new measure that quantifies the "closeness" between two nodes. The calculation of the measure is linear in the number of edges in the graph and involves just a small number of relaxation sweeps. A similar notion of distance is then calculated and used at each coarser level. We demonstrate the use of this measure in multiscale methods for several important combinatorial optimization problems and discuss the multiscale graph organization.

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering, Statistical and Nonlinear Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Electrical and Electronic Engineering

In Statistical and Nonlinear Physics

In Optimization & Training

Citations in the corpus

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, background): “And the last step is the graph pooling operation that trades spatial resolution for higher filter resolution.”
The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains (2012, methodology): “[47] leverages an algebraic distance measure to downsample the vertices; recursive spectral bisection [48] repeatedly divides the graph into parts according to the polarity (signs) of the Fiedler vectors u1 of successive subgraphs; Narang and Ortega [49] minimize the number”
Recent Advances in Graph Partitioning (2013, background): “These principles and their relevance to AMG are summarized in [178].”
Advanced Coarsening Schemes for Graph Partitioning (2012, methodology): “As in AMG-based approaches for linear ordering problems [21] we observed that the order in which Vf is traversed does play an important role in reducing the dependence on random seeds (for details on future volume ordering see [20]).”