Graph reduction with spectral and cut guarantees
Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for graph sparsification. This choice is motivated by the observation that restricted approximation carries strong spectral and cut guarantees, and that it implies approximation results for unsupervised learning problems relying on spectral embeddings. The paper then focuses on coarsening---the most common type of graph reduction. Sufficient conditions are derived for a small graph to approximate a larger one in the sense of restricted similarity. These findings give rise to nearly-linear algorithms that, compared to both standard and advanced graph reduction methods, find coarse graphs of improved quality, often by a large margin, without sacrificing speed.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Spectral estimation from simulations via sketching
Sketching is a stochastic dimension reduction method that preserves geometric structures of data and has applications in high-dimensional regression, low rank approximation and graph sparsification. In this work, we show…
Dimensionality ReductionregressionAn SDP-Based Algorithm for Linear-Sized Spectral Sparsification
For any undirected and weighted graph $G=(V,E,w)$ with $n$ vertices and $m$ edges, we call a sparse subgraph $H$ of $G$, with proper reweighting of the edges, a $(1+\varepsilon)$-spectral sparsifier if \[ (1-\varepsilon)…
Convexity-Driven Projection for Point Cloud Dimensionality Reduction
We propose Convexity-Driven Projection (CDP), a boundary-free linear method for dimensionality reduction of point clouds that targets preserving detour-induced local non-convexity. CDP builds a $k$-NN graph, identifies a…
Dimensionality ReductionPoint CloudsA parameter-free graph reduction for spectral clustering and SpectralNet
Graph-based clustering methods like spectral clustering and SpectralNet are very efficient in detecting clusters of non-convex shapes. Unlike the popular $k$-means, graph-based clustering methods do not assume that each …
ClusteringGraph ClusteringGraph Embeddinggraph partitioning+1Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs
In this paper we propose a pooling approach for convolutional information processing on graphs relying on the theory of graphons and limits of dense graph sequences. We present three methods that exploit the induced grap…
Dimensionality Reduction