Fetching the paper…
Reading the bibliography…
How might one "reduce" a graph? That is, generate a smaller graph that preserves the global structure at the expense of discarding local details? There has been extensive work on both graph sparsification (removing edges) and graph coarsening (merging nodes, often by edge contraction); however, these operations are currently treated separately.
Inverting Modified Matrices
Woodbury, M. A · 1950
Earlier work this paper cites.
Algebraic connectivity of graphs
Fiedler, M · 1973
Earlier work this paper cites.
Generalized inversion of modified matrices
Meyer, C. D., Jr · 1973
Earlier work this paper cites.
A Sherman–Morrison–Woodbury identity for rank augmenting matrices with application to centering
Riedel, K. S · 1992
Earlier work this paper cites.
A multilevel algorithm for partitioning graphs
Hendrickson, B. & Leland, R. W · 1995
Earlier work this paper cites.
The electrical resistance of a graph captures its commute and cover times
Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R. & Tiwari, P · 1996
Earlier work this paper cites.
A fast and high quality multilevel scheme for partitioning irregular graphs
Karypis, G. & Kumar, V · 1998
Earlier work this paper cites.
The Discrepancy Method: Randomness and Complexity (Cambridge University Press, 2000)
Chazelle, B · 2000
Earlier work this paper cites.
A fast multi-scale method for drawing large graphs
Harel, D. & Koren, Y · 2001
Earlier work this paper cites.
ACE: A fast multiscale eigenvectors computation for drawing huge graphs
Koren, Y., Carmel, L. & Harel, D · 2002
Earlier work this paper cites.
Community structure in jazz
Gleiser, P. M. & Danon, L · 2003
Earlier work this paper cites.
The principal components analysis of a graph, and its relationships to spectral clustering
Saerens, M., Fouss, F., Yen, L. & Dupont, P · 2004
Earlier work this paper cites.
Online learning over graphs
Herbster, M., Pontil, M. & Wainer, L · 2005
Earlier work this paper cites.
Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization
Lafon, S. & Lee, A · 2006
Earlier work this paper cites.
A new distributed time synchronization protocol for multihop wireless networks
Solis, R., Borkar, V. S. & Kumar, P · 2006
Earlier work this paper cites.
Matroid Theory , vol. 3 (Oxford University Press, USA, 2006)
Oxley, J. G · 2006
Earlier work this paper cites.
Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation
Pirotte, A., Renders, J.-M., Saerens, M. & Fouss, F · 2007
Earlier work this paper cites.
The Laplacian paradigm: Emerging algorithms for massive graphs
Teng, S.-H · 2010
Earlier work this paper cites.
Spectral sparsification of graphs
Spielman, D. A. & Teng, S.-H · 2011
Earlier work this paper cites.
Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
Christiano, P., Kelner, J. A., Madry, A., Spielman, D. A. & Teng, S.-H · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Spielman, D. A. & Srivastava, N · 2011
Cited alongside, same era.
Relaxation-based coarsening and multiscale graph organization
Ron, D., Safro, I. & Brandt, A · 2011
Cited alongside, same era.
Local graph sparsification for scalable clustering
Satuluri, V., Parthasarathy, S. & Ruan, Y · 2011
Cited alongside, same era.
High-resolution measurements of face-to-face contact patterns in a primary school
Stehl’e, J · 2011
Cited alongside, same era.
Robust network community detection using balanced propagation
S̆ubelj, L. & Bajec, M · 2011
Cited alongside, same era.
Advanced coarsening schemes for graph partitioning
Safro, I., Sanders, P. & Schulz, C · 2015
Later among the works it cites.
Graph Laplacians and least squares on graphs
Hirani, A., Kalyanaraman, K. & Watts, S · 2015
Later among the works it cites.
Algorithms for Lipschitz learning on graphs
Kyng, R., Rao, A., Sachdeva, S. & Spielman, D. A · 2015
Later among the works it cites.
Pyamg: Algebraic multigrid solvers in python v3. 0, 2015
Bell, W., Olson, L. & Schroder, J · 2015
Later among the works it cites.
Simple parallel and distributed algorithms for spectral graph sparsification
Koutis, I. & Xu, S. C · 2016
Later among the works it cites.
Geometric deep learning: Going beyond Euclidean data
Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A. & Vandergheynst, P · 2017
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
What’s in a crowd? Analysis of face-to-face behavioral networks
Isella, L · 2011
Cited alongside, same era.
Iterative ranking from pairwise comparisons
Negahban, S., Oh, S. & Shah, D · 2012
Cited alongside, same era.
Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties (Springer Science & Business Media, 2012)
Ausiello, G · 2012
Cited alongside, same era.
Graph sketches: sparsification, spanners, and subgraphs
Ahn, K. J., Guha, S. & McGregor, A · 2012
Cited alongside, same era.
The connectome of a decision-making neural network
Jarrell, T. A · 2012
Cited alongside, same era.
Spectral sparsification of graphs: Theory and algorithms
Batson, J., Spielman, D. A., Srivastava, N. & Teng, S.-H · 2013
Cited alongside, same era.
Later among the works it cites.
Dynamic edge-conditioned filters in convolutional neural networks on graphs
Simonovsky, M. & Komodakis, N · 2017
Later among the works it cites.
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
Cohen, M. B · 2017
Later among the works it cites.
Pseudoinverse of the Laplacian and best spreader node in a network
Van Mieghem, P., Devriendt, K. & Cetinay, H · 2017
Later among the works it cites.
A framework for analyzing resparsification algorithms
Kyng, R., Pachocki, J., Peng, R. & Sachdeva, S · 2017
Later among the works it cites.
An SDP-based algorithm for linear-sized spectral sparsification
Lee, Y. T. & Sun, H · 2017
Later among the works it cites.
Single pass spectral sparsification in dynamic streams
Kapralov, M., Lee, Y. T., Musco, C., Musco, C. P. & Sidford, A · 2017
Later among the works it cites.
HARP: Hierarchical representation learning for networks
Chen, H., Perozzi, B., Hu, Y. & Skiena, S · 2018
Later among the works it cites.
Network summarization with preserved spectral properties
Jin, Y. & JaJa, J. F · 2018
Later among the works it cites.
Spectrally approximating large graphs with smaller graphs
Loukas, A. & Vandergheynst, P · 2018
Later among the works it cites.
Nearly-linear time spectral graph reduction for scalable graph partitioning and data visualization
Zhao, Z., Wang, Y. & Feng, Z · 2018
Later among the works it cites.
The resistance perturbation distance: A metric for the analysis of dynamic networks
Monnig, N. D. & Meyer, F. G · 2018
Later among the works it cites.
Graph reduction with spectral and cut guarantees
Loukas, A · 2018
Later among the works it cites.
A general framework for graph sparsification
Fung, W.-S., Hariharan, R., Harvey, N. J. & Panigrahi, D · 2019
Closest in time.