skip to main content
10.1145/1374376.1374456acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
research-article

Graph sparsification by effective resistances

Published: 17 May 2008 Publication History

Abstract

We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph G=(V,E,w) and a parameter ε>0, we produce a weighted subgraph H=(V,~E,~w) of G such that |~E|=O(n log n/ε2) and for all vectors x in RV. (1-ε) ∑uv ∈ E (x(u)-x(v))2wuv≤ ∑uv in ~E(x(u)-x(v))2~wuv ≤ (1+ε)∑uv ∈ E(x(u)-x(v))2wuv. This improves upon the sparsifiers constructed by Spielman and Teng, which had O(n logc n) edges for some large constant c, and upon those of Benczur and Karger, which only satisfied (1) for x in {0,1}V. We conjecture the existence of sparsifiers with O(n) edges, noting that these would generalize the notion of expander graphs, which are constant-degree sparsifiers for the complete graph. A key ingredient in our algorithm is a subroutine of independent interest: a nearly-linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in O(log n) time.

References

[1]
D. Achlioptas. Database-friendly random projections. In PODS '01, pages 274--281, 2001.
[2]
D. Achlioptas and F. McSherry. Fast computation of low rank matrix approximations. In STOC '01, pages 611--618, 2001.
[3]
S. Arora, E. Hazan, and S. Kale. A fast random sampling algorithm for sparsifying matrices. In APPROX-RANDOM '06, volume 4110 of Lecture Notes in Computer Science, pages 272--279. Springer, 2006.
[4]
A. A. Benczúr and D. R. Karger. Approximating s-t minimum cuts in O(n2) time. In STOC '96, pages 47--55, 1996.
[5]
B. Bollobas. Modern Graph Theory. Springer, July 1998.
[6]
A. K. Chandra, P. Raghavan, W. L. Ruzzo, and R. Smolensky. The electrical resistance of a graph captures its commute and cover times. In STOC '89, pages 574--586, 1989.
[7]
F. R. K. Chung. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997.
[8]
P. Doyle and J. Snell. Random walks and electric networks. Math. Assoc. America., Washington, 1984.
[9]
P. Drineas and R. Kannan. Fast monte-carlo algorithms for approximate matrix multiplication. In FOCS '01, pages 452--459, 2001.
[10]
P. Drineas and R. Kannan. Pass efficient algorithms for approximating large matrices. In SODA '03, pages 223--232, 2003.
[11]
A. Firat, S. Chatterjee, and M. Yilmaz. Genetic clustering of social networks using random walks. Computational Statistics & Data Analysis, 51(12):6285--6294, August 2007.
[12]
F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. Knowledge and Data Engineering, IEEE Transactions on, 19(3):355--369, 2007.
[13]
A. Frieze, R. Kannan, and S. Vempala. Fast monte-carlo algorithms for finding low-rank approximations. J. ACM, 51(6):1025--1041, 2004.
[14]
C. Godsil and G. Royle. Algebraic Graph Theory. Graduate Texts in Mathematics. Springer-Verlag, 2001.
[15]
A. V. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem. In STOC '86, pages 136--146, 1986.
[16]
S. Guattery and G. L. Miller. Graph embeddings and laplacian eigenvalues. SIAM J. Matrix Anal. Appl., 21(3):703--723, 2000.
[17]
W. Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemp. Math., 26:189--206, 1984.
[18]
J. Kelner. Lecture notes for 18.409, an algorithmist's toolkit. 2007.
[19]
R. Khandekar, S. Rao, and U. Vazirani. Graph partitioning using single commodity flows. In STOC '06, pages 385--390, 2006.
[20]
G. Lugosi. Concentration-of-measure inequalities, 2003. Available at http://www.econ.upf.edu/ lugosi/anu.ps.
[21]
M. Rudelson. Random vectors in the isotropic position. J. of Functional Analysis, 163(1):60--72, 1999.
[22]
M. Rudelson and R. Vershynin. Sampling from large matrices: An approach through geometric functional analysis. J. ACM, 54(4):21, 2007.
[23]
D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In STOC '04, pages 81--90, 2004. Full version available at http://arxiv.org/abs/cs.DS/0310051.
[24]
D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. Available at http://www.arxiv.org/abs/cs.NA/0607105, 2006.

Cited By

View all
  • (2025)Resistance distance in generalized core–satellite graphsDiscrete Applied Mathematics10.1016/j.dam.2024.11.011362(100-108)Online publication date: Feb-2025
  • (2024)Two heads are better than oneProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694560(60197-60219)Online publication date: 21-Jul-2024
  • (2024)Knowledge graphs can be learned with just intersection featuresProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693117(26199-26214)Online publication date: 21-Jul-2024
  • Show More Cited By

Index Terms

  1. Graph sparsification by effective resistances

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing
    May 2008
    712 pages
    ISBN:9781605580470
    DOI:10.1145/1374376
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 17 May 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. electrical flows
    2. random sampling
    3. spectral graph theory

    Qualifiers

    • Research-article

    Conference

    STOC '08
    Sponsor:
    STOC '08: Symposium on Theory of Computing
    May 17 - 20, 2008
    British Columbia, Victoria, Canada

    Acceptance Rates

    STOC '08 Paper Acceptance Rate 80 of 325 submissions, 25%;
    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)239
    • Downloads (Last 6 weeks)32
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2025)Resistance distance in generalized core–satellite graphsDiscrete Applied Mathematics10.1016/j.dam.2024.11.011362(100-108)Online publication date: Feb-2025
    • (2024)Two heads are better than oneProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694560(60197-60219)Online publication date: 21-Jul-2024
    • (2024)Knowledge graphs can be learned with just intersection featuresProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693117(26199-26214)Online publication date: 21-Jul-2024
    • (2024)Fast, scalable, warm-start semidefinite programming with spectral bundling and sketchingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692134(1579-1615)Online publication date: 21-Jul-2024
    • (2024)A comprehensive survey on graph reductionProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/891(8058-8066)Online publication date: 3-Aug-2024
    • (2024)Similarity of Graphs and Complex Networks Based on Resistance DistanceAdvances in Applied Mathematics10.12677/aam.2024.13414913:04(1585-1598)Online publication date: 2024
    • (2024)Graph Rewiring and Preprocessing for Graph Neural Networks Based on Effective ResistanceIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.339769236:11(6330-6343)Online publication date: Nov-2024
    • (2024)Resistance Eccentricity in Graphs: Distribution, Computation and Optimization2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00315(4113-4126)Online publication date: 13-May-2024
    • (2024)Energy-Efficient Decentralized Learning Via Graph SparsificationICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10445868(13026-13030)Online publication date: 14-Apr-2024
    • (2024)On the Scalability of Large Graph Methods for Kernel-Based Machine Learning*2024 60th Annual Allerton Conference on Communication, Control, and Computing10.1109/Allerton63246.2024.10735281(1-8)Online publication date: 24-Sep-2024
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media