TY - JOUR
T1 - A generalized Cheeger inequality
AU - Koutis, Ioannis
AU - Miller, Gary
AU - Peng, Richard
N1 - Funding Information:
I. Koutis was partially supported by NSF awards # 1813374 and # 2039863 . G. Miller was partially supported by NSF award # 1637523 . R. Peng was partially supported by NSF award # 1846218 .
Publisher Copyright:
© 2023 Elsevier Inc.
PY - 2023/5/15
Y1 - 2023/5/15
N2 - The generalized conductance ϕ(G,H) between two weighted graphs G and H on the same vertex set V is defined as the ratio [Formula presented] where capG(S,S¯) is the total weight of the edges crossing from vertex set S⊆V to S¯=V−S. We show that the minimum generalized eigenvalue λ(LG,LH) of the pair of Laplacians LG and LH satisfies ϕ(G,H)≥λ(LG,LH)≥ϕ(G,H)ϕ(G)/16, where ϕ(G) is the standard conductance of G. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to λ(LG,LH).
AB - The generalized conductance ϕ(G,H) between two weighted graphs G and H on the same vertex set V is defined as the ratio [Formula presented] where capG(S,S¯) is the total weight of the edges crossing from vertex set S⊆V to S¯=V−S. We show that the minimum generalized eigenvalue λ(LG,LH) of the pair of Laplacians LG and LH satisfies ϕ(G,H)≥λ(LG,LH)≥ϕ(G,H)ϕ(G)/16, where ϕ(G) is the standard conductance of G. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to λ(LG,LH).
KW - Cheeger inequality
KW - Generalized cuts
KW - Spectral graph theory
UR - http://www.scopus.com/inward/record.url?scp=85147999385&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85147999385&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2023.01.014
DO - 10.1016/j.laa.2023.01.014
M3 - Article
AN - SCOPUS:85147999385
SN - 0024-3795
VL - 665
SP - 139
EP - 152
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
ER -