PaperlayerView exact revision on arXiv

Source-linked AI summary

Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors

Tatsuro Kawamoto, Yoshiyuki Kabashima

arXiv:1502.06775v2cs.SIcond-mat.stat-mechphysics.soc-ph

TL;DR

The paper asks when spectral methods cease to recover planted graph partitions, particularly in sparse graphs, and whether eigenvector localization explains their performance gap. Using replica-based estimates and numerical comparisons, it finds a considerable gap from the ultimate threshold even without localization in sparse graphs; the gap becomes negligible in the dense limit.

  • Problem

    The true detectability threshold for spectral methods in sparse graphs and the role of eigenvector localization in their gap from Bayesian inference were unresolved.

    Source: §I · pp. 1–2

  • Method

    The authors use the replica method to estimate unnormalized- and normalized-Laplacian thresholds and analyze eigenvector localization.

    Source: §IV · p. 5, §VI · p. 14, §X · p. 19

  • Results

    In sparse graphs, Laplacian spectral methods fall short of the ultimate threshold 2 √ c even without localization, while their estimated threshold gap is negligible at sufficiently large average degree.

    Source: §IX · p. 18, §X · p. 19

  • Takeaways & Limitations

    The gap from the ultimate detectability threshold can persist without localization, while localization may be significant when degree fluctuates considerably.

    Source: §I · p. 2

    The replica method's mathematical validity has not been proved.

    Source: §IV · p. 5

Abstract

from arXiv · show

Investigating the performance of different methods is a fundamental problem in graph partitioning. In this paper, we estimate the so-called detectability threshold for the spectral method with both unnormalized and normalized Laplacians in sparse graphs. The detectability threshold is the critical point at which the result of the spectral method is completely uncorrelated to the planted partition. We also analyze whether the localization of eigenvectors affects the partitioning performance in the detectable region. We use the replica method, which is often used in the field of spin-glass theory, and focus on the case of bisection. We show that the gap between the estimated threshold for the spectral method and the threshold obtained from Bayesian inference is considerable in sparse graphs, even without eigenvector localization. This gap closes in a dense limit.

I. INTRODUCTION

The paper studies when spectral graph partitioning stops recovering a planted partition, a key issue in sparse graphs where average degree stays constant as graph size grows. It estimates thresholds for Laplacian-based methods and examines whether eigenvector localization accounts for their gap from Bayesian inference.

I. INTRODUCTION

  • In sparse graphs, the detectability threshold marks the point below which a method's partition is completely uncorrelated with the planted partition.Sparse graphs are important to study because many real networks are sparse, while their average degree remains constant as graph size grows.Source: §I · p. 1
  • The study focuses on undirected graph bisection in the large-size limit, excluding hierarchical structures and overlapping modules.Source: §I · p. 1
  • The authors use the stochastic block model as a comparison framework for methods, while noting that real applications may lack known parameters or a justified model fit.They argue that theoretical comparisons can help identify methods that tend to produce similar partitions and thereby reduce redundant application of methods.Source: §I · p. 1
  • The paper asks whether spectral methods' gap from Bayesian inference persists without eigenvector localization, which can wash out block information when it occurs.The authors report a considerable gap even without localization, while localization may matter when degree fluctuates considerably.Source: §I · p. 2
  • Using the replica method, the paper estimates thresholds for unnormalized and normalized Laplacians and compares them with numerical experiments across several degree distributions.The estimates agree fairly well with experiments when localization does not occur, and the localization estimate is fairly accurate for bimodal degree distributions.Source: §I · p. 2

II. STOCHASTIC BLOCK MODEL AND THE DETECTABILITY THRESHOLD

The paper uses a two-block stochastic block model to represent planted partitions in random graphs. In the sparse case, it parameterizes assortative structure by the average degree and cross-module edge count, and states the Bayesian detectability boundary.

II. STOCHASTIC BLOCK MODEL AND THE DETECTABILITY THRESHOLD

  • The stochastic block model generates random edges according to preassigned module memberships and connection probabilities between module pairs.The model takes the number and sizes of modules and their pairwise connection probabilities as inputs.Source: §II · p. 2
  • For sparse two-module graphs of equal size, connection probabilities scale as c_rs/N, with average degree c=(c_in+c_out)/2 and persistent degree fluctuations.Assortative structure uses c_in>c_out.Source: §II · p. 2
  • Bayesian inference cannot retrieve the planted partition unless c_in−c_out exceeds 2 √ c, even when the model is assortative.Source: §II · p. 3
  • The paper parameterizes the two-block model by average degree c and average cross-module edge count γ, which increases as block structure weakens.Its microcanonical formulation fixes the cross-module and within-module edge totals in each realization.Source: §II · p. 3

III. SPECTRAL METHOD IN GRAPH BISECTION

The spectral method relaxes graph-partitioning objectives into eigenvector problems for the corresponding matrices. For bisection, the sign of entries in the selected eigenvector assigns vertices to modules.

III. SPECTRAL METHOD IN GRAPH BISECTION

  • The spectral method relaxes RatioCut and Ncut into eigenvector problems using the unnormalized Laplacian L and normalized Laplacian L, respectively.The adjacency matrix records edges, while the diagonal degree matrix records each vertex's degree.Source: §III · p. 3
  • For the relaxed objectives, the constrained solutions use the second-smallest eigenvalue's eigenvector, whose entry signs assign vertices to the two modules.The paper focuses on the relaxed problem and notes that its optimum need not coincide with the unrelaxed optimum.Source: §III · pp. 3–4
  • The paper examines how spectral partitions correlate with planted partitions in different random graphs.Source: §III · p. 4

IV. DETECTABILITY THRESHOLD IN RANDOM REGULAR GRAPHS

For two-block random regular graphs, the spectral method has a detectability threshold that is estimated analytically and checked against numerical experiments. In sparse graphs, that threshold remains below the Bayesian limit even without degree fluctuation or eigenvector localization; the gap closes in the dense limit.

IV. DETECTABILITY THRESHOLD IN RANDOM REGULAR GRAPHS

  • For fixed-degree random regular graphs, degree fluctuations are absent, so normalized and unnormalized Laplacians yield the same analysis.The graph is sparse because c stays constant as N grows.Source: §IV · p. 4
  • The replica method estimates the average second-smallest Laplacian eigenvalue through a saddle-point calculation with a replica-symmetric ansatz.The authors note that the replica method's mathematical validity is unproved, though its predictions are fairly accurate against experiments.Source: §IV · pp. 5, 7
  • The saddle-point equations reproduce the numerical distributions of second-smallest-eigenvector elements well.The figure compares numerical dots with analytical solid lines for two parameter settings.Source: §IV · p. 8, Figure 2 · p. 9
  • The equality point in the threshold condition marks detectability loss, and above it the solution has zero first moment.The resulting threshold lies between zero and p1p2 for the normalized intermodule-edge fraction γ/c.Source: §IV · pp. 9–10
  • Even without localization, the spectral method for sparse graphs does not reach the Bayesian limit; the gap closes as c → ∞.The analytical threshold agrees with the numerical experiments.Source: §IV · p. 9
  • A Gaussian approximation estimates classification accuracy fairly well, especially near the threshold, while a finite fraction of vertices remains misclassified as N grows.The planted partition need not optimize the objective function, particularly when the block structure is not sufficiently strong.Source: §IV · p. 10, Figure 5 · p. 11

V. DETECTABILITY THRESHOLD IN RANDOM GRAPHS WITH DEGREE FLUCTUATION: THE UNNORMALIZED LAPLACIAN

For the unnormalized Laplacian, the paper estimates the detectability threshold under degree fluctuation using the effective medium approximation (EMA). In bimodal graphs, the estimate agrees with numerical results when localization does not occur, while localization can make the spectral method fail.

V. Detectability threshold in random graphs with degree fluctuation: the unnormalized Laplacian

  • With degree fluctuation, the replica saddle-point equations no longer have the simple-form solutions available for random regular graphs, so the analysis uses the EMA.The EMA takes the replica distributions to be delta functions at a and â.Source: §V · p. 12
  • The equality condition in Eq. (68) estimates the detectability threshold from the EMA formal solution for the second-smallest eigenvalue.Source: §V · p. 13
  • For bimodal degree distributions, the saddle-point conditions yield an analytic solution for φ and a quadratic equation for a.Source: §V · p. 13
  • When localization does not occur, the EMA eigenvalue estimate agrees well with numerical results; when the module-informative eigenvector rises above a localized eigenvector, the spectral method fails.The estimated localization transition is close to where the EMA result begins to deviate from numerical results, when the chosen parameter is consistent with the numerical experiment.Source: §V · p. 13

VI. LOCALIZED EIGENVECTOR OF THE UNNORMALIZED LAPLACIAN WITH BIMODAL DEGREE DISTRIBUTIONS

The section models localization in sparse bimodal graphs by concentrating low-population defect vertices around a tree root. It derives conditions for a decaying, finite-norm eigenvector and connects its damping to the EMA response.

VI. Localized eigenvector of the unnormalized Laplacian with bimodal degree distributions

  • The analysis treats the lower-population degree class as defects and studies sparse bimodal graphs with bD < bB.Source: §VI · p. 14
  • The model aggregates defects around a root through distance g, then assigns uniform degree cB beyond that radius to obtain radial eigenvector recurrences.Source: §VI · pp. 14–15
  • A localized mode must decay at large distance, so its outer-region damping factor satisfies |κ| < 1.The eigenvector must also have finite norm.Source: §VI · p. 15
  • For a single defective root, the localized eigenvalue is λ = cD(cB − cD − 2)/(cB − cD − 1), with damping factor κ = 1/(cB − cD − 1).Finite norm requires cD < cB − 1 − √(cB − 1); the authors caution that this condition is specific to a tree with uniform degree beyond the root.Source: §VI · p. 15
  • On tree-like graphs, the EMA response damps with distance as O((1 + â)^D), linking its factor 1 + â to the localized-mode damping κ.The localized eigenvalue can be estimated by replacing κ with 1 + â*(λ) and solving consistently with the equations within distance g.Source: §VI · p. 15
  • Localization occurs when the localized eigenvalue falls below the second-smallest eigenvalue calculated in the preceding section.Source: §VI · p. 15

VII. DETECTABILITY THRESHOLD IN RANDOM GRAPHS WITH DEGREE FLUCTUATION: THE NORMALIZED LAPLACIAN

The normalized-Laplacian analysis estimates detectability using a replica-method saddle-point formulation, with numerical agreement when localization is negligible. Localization can make the predicted classification fraction differ from numerical results.

VII. DETECTABILITY THRESHOLD IN RANDOM GRAPHS WITH DEGREE FLUCTUATION: THE NORMALIZED LAPLACIAN

  • The normalized-Laplacian formulation uses y := D−1/2x; although y is not the eigenvector, its element signs preserve the correctly classified fraction.The free energy defined from the partition function is related to the second-smallest eigenvalue.Source: §VII · pp. 15–16
  • The detectability threshold is the equality boundary for existence of a saddle-point solution with nonzero m1k.The section compares the resulting estimates with numerical experiments for bimodal degree distributions.Source: §VII · p. 16
  • For bimodal degree distributions, localization is less likely with the normalized Laplacian than with the unnormalized Laplacian.In the region where localization is present, the Gaussian-fit classification estimate appears better than the saddle-point estimate.Source: §VII · p. 17

VIII. LOCALIZED EIGENVECTOR OF THE NORMALIZED LAPLACIAN WITH BIMODAL DEGREE DISTRIBUTIONS

The section derives localized-eigenvector behavior for the normalized Laplacian and compares it with numerical results for bimodal degree distributions. The reported conditions indicate localization is suppressed relative to the unnormalized Laplacian.

VIII. LOCALIZED EIGENVECTOR OF THE NORMALIZED LAPLACIAN WITH BIMODAL DEGREE DISTRIBUTIONS

  • For the normalized Laplacian, a localized eigenvector at g = 1 requires 2cD < cB, so defects must have lower degree.For g = 0, the analysis finds no localized eigenvector.Source: §VIII · p. 17
  • For bimodal degree distributions, the replica-method estimate predicts numerical results fairly accurately, while classification estimates diverge significantly where localization is present.The classification estimates are close when localization is negligible.Source: Figure 10 · p. 18
  • The normalized Laplacian’s stricter localization conditions imply that localization tends to be suppressed compared with the unnormalized Laplacian.The authors note consistency with analyses in data clustering.Source: §VIII · pp. 17–18

IX. DETECTABILITY THRESHOLD OF THE STOCHASTIC BLOCK MODEL WITH THE NORMALIZED LAPLACIAN

For the stochastic block model with a normalized Laplacian, the estimated threshold differs considerably from the ultimate threshold in sparse graphs, with the difference becoming negligible at sufficiently large average degree. Localization can affect estimates in the detectable region, particularly at c = 6 in tested graphs.

IX. DETECTABILITY THRESHOLD OF THE STOCHASTIC BLOCK MODEL WITH THE NORMALIZED LAPLACIAN

  • The phase diagrams show that the difference between the replica-method EMA threshold and the ultimate threshold is negligible at sufficiently large average degree but considerable in sparse graphs.The model excludes parameter values with cin − cout > 2c because cout ≥ 0.Source: §IX · pp. 18–19, Figure 11 · p. 19
  • The inverse participation ratio rises rapidly where EMA eigenvalue estimates begin to diverge from numerical results, and classification estimates start diverging there as well.The eigenvalue estimates agree excellently while the localized eigenstate does not occupy the second-smallest eigenvalue.Source: §IX · p. 18
  • For c = 6, a localized eigenvector appears significantly above the detectability threshold, within the detectable region, and its effect is not negligible.At c = 8, the localization-related error appears much smaller for the graph sizes tested; increasing average degree is expected to reduce degree fluctuations.Source: §IX · p. 19
  • For the Poisson degree distribution, EMA saddle-point results seem to converge to the estimate in around the detectability threshold; this coincidence depends on the degree distribution.The difference between EMA results generally depends on the form of the degree distribution.Source: §IX · p. 19

X. SUMMARY

The paper estimates sparse-graph detectability thresholds for both Laplacians and analyzes eigenvector localization. It finds a considerable gap from the ultimate threshold in sparse graphs, even absent localization, while estimates converge to the result in in the dense limit.

X. SUMMARY

  • For the normalized Laplacian, the estimated threshold converges to the result in as c → ∞.The general threshold expression is given for equal-sized modules.Source: §X · p. 19
  • Replica-method estimates agree with numerical results quite well when localization is absent, for the graph sizes tested.For infinite-support degree distributions such as Poisson, rare irregular-degree vertices may make finite-size effects non-negligible.Source: §X · p. 19
  • In sparse graphs, Laplacian spectral methods do not detect modules down to the ultimate threshold 2√c, even when localization is absent or negligible.The estimated gap is considerable for very sparse graphs; localization was relatively weak for tested stochastic block model sizes when average degree was not very low.Source: §X · p. 19
  • The paper does not guarantee that normalized-Laplacian results coincide precisely with the modularity-matrix threshold under spherical normalization..Source: §X · p. 20

Appendix A: Number of random graphs with two modules

The appendices describe a graph-counting technique used to calculate partition-function moments and a Gaussian fitting procedure for eigenvector-element distributions.

Appendix A: Number of random graphs with two modules

  • The graph-counting calculation gives the number of possible graph realizations, a technique used to calculate the partition-function moment.The appendix first considers two-block c-random regular graphs.Source: Appendix A · p. 20
  • At average degree c = 8, localization has a weaker effect, and the EMA estimate is more precise.Figure 13 shows the same plots as Figure 12 at c = 8.Source: Figure 13 · p. 21
  • The calculation also applies to two-block graphs with a given degree sequence, including the two-block configuration model and hard-constraint degree-corrected ensembles.The passage defines V(r,t) as the vertices in module r with degree c_t.Source: Appendix A · p. 23

Appendix B: Gaussian approximation of the fraction of correctly classified vertices

  • The appendix defines the distribution of second-smallest-eigenvector elements in module r by averaging over realizations of the unnormalized Laplacian.This is the distribution whose Gaussian fit is discussed in the appendix.Source: Appendix B · p. 24
  • For Gaussian fitting of Pr(x), the mean and variance are obtained from (B2), while the distribution of A is fixed at a_full.The text distinguishes a_full from a in the saddle-point equations and identifies Q_r(A,H) as the complete marginal corresponding to q_r(A,H).Source: Appendix B · p. 24

Appendix C: Approximations of the saddle-point equations and the free energy

The appendix compares two EMA-based approximations and explains why their estimates can differ. Their discrepancy depends on the mean-to-variance ratio, and neither estimate is generally exact.

Appendix C: Approximations of the saddle-point equations and the free energy

  • The EMA of the saddle-point equations differs from the EMA of the free energy because the latter applies its approximation before taking the saddle point.The discrepancy depends on the ratio of the mean and variance, or the Fano factor; neither quantity is exact, so which gives the better estimate is not generally clear.Source: Appendix C · p. 25

Related papers

Loading 1502.06775v2…