PaperlayerView exact revision on arXiv

Source-linked AI summary

Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap

Emmanuel Abbe, Colin Sandon

arXiv:1512.09080v4math.PRcs.CCcs.ITcs.LGcs.SImath.IT

TL;DR

Whether the conjectured efficient Kesten–Stigum threshold and information-theoretic detection below it hold for SBMs with k ≥ 3 remained unresolved. The paper uses linearized acyclic belief propagation for efficient detection and samples clusterings with typical volumes and cuts for the information-theoretic result. The paper proves efficient detection down to the Kesten–Stigum threshold and information-theoretic detection below it at k = 4.

  • Problem

    Whether the conjectured efficient Kesten–Stigum threshold and information-theoretic detection below it hold for SBMs with k ≥ 3 remained unresolved.

    Source: §1 · p. 3

  • Method

    The paper uses linearized acyclic belief propagation for efficient detection and samples clusterings with typical volumes and cuts for the information-theoretic result.

    Source: §1.1 · p. 5

  • Results

    The paper proves efficient detection down to the Kesten–Stigum threshold and information-theoretic detection below it at k = 4.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The information-theoretic bound yields a gap to the KS threshold that is large in some cases, quasi-linear in k.

    Source: §1 · p. 4

    Formal computational lower bounds for impossibility below the Kesten–Stigum threshold, especially for k ≥ 4, seem currently out of reach.

    Source: §5 · p. 37

Abstract

from arXiv · show

In a paper that initiated the modern study of the stochastic block model, Decelle et al., backed by Mossel et al., made the following conjecture: Denote by $k$ the number of balanced communities, $a/n$ the probability of connecting inside communities and $b/n$ across, and set $\mathrm{SNR}=(a-b)^2/(k(a+(k-1)b)$; for any $k \geq 2$, it is possible to detect communities efficiently whenever $\mathrm{SNR}>1$ (the KS threshold), whereas for $k\geq 4$, it is possible to detect communities information-theoretically for some $\mathrm{SNR}<1$. Massouli\'e, Mossel et al.\ and Bordenave et al.\ succeeded in proving that the KS threshold is efficiently achievable for $k=2$, while Mossel et al.\ proved that it cannot be crossed information-theoretically for $k=2$. The above conjecture remained open for $k \geq 3$. This paper proves this conjecture, further extending the efficient detection to non-symmetrical SBMs with a generalized notion of detection and KS threshold. For the efficient part, a linearized acyclic belief propagation (ABP) algorithm is developed and proved to detect communities for any $k$ down to the KS threshold in time $O(n \log n)$. Achieving this requires showing optimality of ABP in the presence of cycles, a challenge for message passing algorithms. The paper further connects ABP to a power iteration method with a nonbacktracking operator of generalized order, formalizing the interplay between message passing and spectral methods. For the information-theoretic (IT) part, a non-efficient algorithm sampling a typical clustering is shown to break down the KS threshold at $k=4$. The emerging gap is shown to be large in some cases; if $a=0$, the KS threshold reads $b \gtrsim k^2$ whereas the IT bound reads $b \gtrsim k \ln(k)$, making the SBM a good study-case for information-computation gaps.

1 Introduction

The paper proves the conjectured efficient and information-theoretic detection results for the stochastic block model, extending efficient detection to general, potentially asymmetric models. It develops acyclic belief propagation and a typical-clustering algorithm, and relates belief propagation to generalized nonbacktracking operators.

1 Introduction

  • The conjecture asks whether detection is efficient for SNR > 1 for any k, and whether some SNR < 1 permits information-theoretic detection for k ≥ 4.The SNR is (a−b)^2/[k(a+(k−1)b)], and detection means producing a clustering positively correlated with the planted one with high probability.Source: §1 · p. 3

1.2 Related literature

  • Prior work achieved the KS threshold efficiently for k = 2 [MNS14b] and for multiple-community SBMs with an asymmetry condition requiring µk to be a simple eigenvalue, but did not resolve Conjecture 1 for k ≥ 3.Source: §1 · p. 3, §1.2 · p. 7

1 Introduction

  • Belief propagation and spectral methods based on adjacency matrices, Laplacians, or SDPs do not straightforwardly attain the efficient threshold: degree fluctuations disrupt spectral eigenvectors, while BP is difficult to analyze on loopy graphs.Trimming high-degree nodes loses information and does not suffice to reach the threshold; BP can settle into wrong fixed points.Source: §1 · pp. 3–4

1.1 Our results

  • For every k, linearized acyclic belief propagation detects communities down to the Kesten–Stigum threshold in O(n log n) time, including for potentially asymmetric SBMs under a generalized detection notion.The paper also gives an efficient algorithm for learning a, b, and k in the symmetric SBM down to that threshold.Source: §1.1 · p. 5
  • The information-theoretic result crosses the Kesten–Stigum threshold at k = 4 using a non-efficient algorithm that samples clusterings with typical volumes and cuts.For a = 0, the bound is b > c k ln k + o_k(1), c ∈ [1, 2], compared with the Kesten–Stigum threshold b > k(k − 1).Source: §1.1 · p. 5
  • ABP corresponds to power iteration on a generalized nonbacktracking operator that forbids finite cycles as well as standard backtracks.The connection links message passing and spectral methods; the paper relates spectral concentration on singular structures to BP feedback and wrong fixed points.Source: §1 · p. 4, §1.1 · pp. 5–6
  • The paper’s information-theoretic bound is conjectured tight in the scaling of b for small b and in the scaling of k for large k and small a.Its typical-set analysis successively uses tree-like components, tree-like parts of the giant component, and vertices whose neighbors do not cover all communities.Source: §1.1 · pp. 5–6

1.3 Related models

  • Exact recovery is distinct from detection and has a sharp, efficiently achievable threshold for general SBMs with linear-size communities; related SBM variants include labelled, censored, degree-corrected, and overlapping models.The paper notes possible information-computation gaps for exact recovery with sub-linear communities, and conjectures a similar phenomenon when k exceeds log(n) in another setting.Source: §1.3 · pp. 8–9

2 Results

The results address detection and parameter estimation in the stochastic block model, establishing efficient detection at the generalized KS threshold and an information-theoretic detection region crossing it for k ≥ 4. They also distinguish the paper’s detection criterion from max-detection under asymmetric community priors and define balanced label vectors for typicality sampling.

2 Results

  • The paper’s detection criterion captures nontrivial community evidence under asymmetric priors, whereas max-detection may not; for uniform priors, detection implies max-detection.The distinction can matter when community sizes are unequal.Source: §2 · p. 10

2.1 Achieving the KS threshold efficiently

  • When λ2^2 > λ1, acyclic belief propagation detects communities in the general SBM in O(n log n) time; in the symmetric case, the SNR is (a-b)^2/(k(a+(k-1)b)).The symmetric-case condition is the KS threshold from the conjecture.Source: §2.1 · pp. 10–11

2.1.1 Acyclic Belief Propagation (ABP) Algorithm

  • ABP uses linearized message passing to update neighborhood evidence while mitigating cycles, and is connected to power iteration with a generalized-order nonbacktracking operator.The paper presents a simplified version for symmetric SBMs and a general version used to prove the detection theorem.Source: §2.1.1 · p. 11

2.2 Crossing the KS threshold information-theoretically

  • The Typicality Sampling Algorithm detects communities in a parameter region that strictly improves on the KS threshold for k ≥ 4.The region is stated for the symmetric SBM; the supplied passages do not expose its full inequality clearly.Source: §2.2 · p. 14
  • For a = 0, the information-theoretic bound has k ln(k) scaling, improving on the KS condition b > k(k-1); at b = 0, the stated bound a > 2k is not tight against a > k.The paper also conjectures that its k ln(k) scaling is the correct first-order information-theoretic scaling for a = 0.Source: §2.2 · pp. 14–15

2.2.1 Typicality Sampling Algorithm

  • The typicality-sampling subsection defines balanced assignments as those with every community’s vertex fraction within ε of 1/k.This set is denoted Bal(n, k, ε).Source: §2.2.1 · p. 15
  • Bal(n, k) consists of label vectors whose component fractions in each community are asymptotically uniform.The passage defines Bal(n, k) as Bal(n, k, log n/√n).Source: §2.2.1 · p. 15

2.3 Learning the model

  • If SNR > 1, a consistent and efficient estimator exists for a, b, and k in SBM(n, k, a, b).The parameters are learned by counting slowly growing cycles, with non-backtracking walks used to approximate the counts, as in for k = 2.Source: §2.3 · p. 16

3 Achieving the KS threshold: proof technique

The section sets up the balanced two-community SBM and frames detection as recovering a partition that is better than random guessing, despite the symmetry between community labels.

3 Achieving the KS threshold: proof technique

  • The two-community model uses equal community proportions, within-community edge probability a/n, and across-community probability b/n.Its average degree is λ1 = (a+b)/2, and the other eigenvalue of PQ is λ2 = (a−b)/2.Source: §3 · p. 16
  • The section defines approximate equality as |f − g| = o(|f + g|) with probability 1 − o(1).Source: §3 · p. 16
  • Detection seeks a partition whose assignments differ nontrivially between the two true communities, without requiring identification of which community is called 1 or 2.The stated goal is accuracy nontrivially better than random guessing.Source: §3 · p. 16

3.1 Amplifying luck

The section explains how random labels create a weak initial correlation with the true communities and how neighborhood information could amplify it. In sparse graphs, however, neighborhoods become too large before that amplification can yield useful accuracy.

3.1 Amplifying luck

  • Randomly assigning labels gives an expected difference of order 1/√n between the communities’ representation in the two assigned sets.The sets are oriented so community 1 is at least as represented in S1 as community 2.Source: §3.1 · pp. 17–18
  • On a tree neighborhood, belief propagation combines children’s weak beliefs to update the probability that a vertex belongs to community 1.When the child beliefs are small, the update is approximately proportional to their sum, scaled by ((a−b)/(a+b))^t.Source: §3.1 · p. 17
  • The expected number of vertices at distance t grows approximately as ((a+b)/2)^t, while the same-community excess grows as ((a−b)/2)^t.These neighborhood counts motivate amplification when the signal grows sufficiently relative to the noise.Source: §3.1 · p. 17
  • For (a−b)^2 > 2(a+b), neighborhood-based classification becomes more accurate as t increases, but useful accuracy would require neighborhoods too large for the approximation.The required scale would make the number of reached vertices ω(n); loops then prevent edges from leading to new vertices.Source: §3.1 · pp. 18–19
  • Figure 1 contrasts a small tree-like neighborhood with random initialization, whose lucky advantage is about √n vertices, motivating the move from neighborhoods to walks.At depth c log_λ1 n for c < 1/2, the neighborhood is a tree with high probability.Source: Figure 1 · p. 19

3.2 Nonbacktracking walks

The section replaces neighborhood counts with nonbacktracking walks: ordinary walks are confounded by cycles, while counting paths is inefficient. The walk-based procedure supports iterative belief updates while limiting immediate backtracking.

3.2 Nonbacktracking walks

  • Ordinary walk counts are unreliable for classifying vertices because walks can revisit earlier vertices and their edge counts are difficult to predict from the endpoint’s community.The last vertex may connect back to the second-to-last vertex and other vertices already on the walk.Source: §3.2 · p. 20
  • Counting paths avoids repeated vertices, but counting all such paths is inefficient.The expected number and same-community excess of paths grow approximately as ((a+b)/2)^t and ((a−b)/2)^t, respectively.Source: §3.2 · p. 20
  • The algorithm instead counts nonbacktracking walks, which can be computed recursively from shorter walks ending in directed edges.For logarithmic length, most such walks are paths, so the authors expect little effect on accuracy from allowing some repeated vertices.Source: §3.2 · p. 20
  • In the illustrated r-nonbacktracking rule, a walk is discarded if it repeats a vertex within r steps, while distinct walks from the same start vertex are counted separately.The example uses r = 3 and walks of length 7.Source: Figure 2 · p. 21
  • Because approximately equal numbers of walks connect each vertex pair, an initially dominant label can bias all classifications, so the procedure needs a compensation step.Source: Figure 2 · p. 21
  • The walk counts act as evolving beliefs about vertices, updated using beliefs about their neighbors while discounting information from the edge back to the current vertex.Source: §3.2 · p. 22

3.3 Compensation for the average value

This section identifies a bias in the walk-based beliefs: their average can grow faster than the community-dependent signal. It proposes periodically reducing that average and then converting vertex scores into a partition.

3.3 Compensation for the average value

  • Random initialization leaves the average edge-based belief nonzero, typically on the order of 1/√n, and this average grows with walk length.Source: §3.3 · p. 22
  • The growing average can make the empirical variance much larger than the difference between community-specific average beliefs, undermining classification by the edge scores.Source: §3.3 · p. 22
  • Subtracting the mean once is a simple correction, but the authors say it does not extend easily to general SBMs and the average can grow again.Source: §3.3 · pp. 22–23
  • The proposed correction reduces the belief magnitude at several selected indices to prevent the average from overwhelming the community-dependent difference.Source: §3.3 · p. 23
  • After these modifications, the community-specific average edge beliefs eventually differ by a constant multiple of their standard deviation.Source: §3.3 · p. 23
  • Because score signs alone need not yield unequal community representation, vertices are assigned randomly with probabilities scaled linearly to their final scores.Source: §3.3 · p. 23

3.4 Vanilla ABP

Vanilla ABP combines random initialization, acyclic walks, and end-of-run bias compensation to propagate community information while controlling dependencies.

3.4 Vanilla ABP

  • Each directed edge receives an independent Gaussian initial value with mean 0 and variance 1.Source: §3.4 · p. 24
  • The algorithm retroactively adjusts its computed values to compensate for biases rather than correcting each recursion step as it runs.This version calculates the y(t) values without compensation, then adjusts the results afterward.Source: §3.4 · p. 24
  • ABP* cancels walks that repeat a vertex within r steps, so its recursion counts walks without small cycles.The algorithm uses Gaussian initialization and moves average-value compensation to the end.Source: §3.4 · p. 25
  • A randomly selected fraction of edges separates one walk step from the others, helping keep adjacent messages from becoming disruptively dependent.The selected edges are nearly independent of the rest of the graph.Source: §3.4 · p. 25

3.5 ABP for the symmetric SBM

For the symmetric SBM, acyclic belief propagation detects community differences at the KS condition, and the algorithm runs in O(n log n) time.

3.5 ABP for the symmetric SBM

  • The basic two-community algorithm guarantees an expected fraction difference of at least ϵ under the same two-community threshold.Source: §3.5 · p. 25
  • For two communities, the modified acyclic BP algorithm separates community representation fractions by at least ϵ with probability 1 − o(1).This guarantee holds when (a − b)^2 > 2(a + b).Source: §3.5 · p. 26
  • The modified two-community algorithm samples a fraction of edges, then excludes walks containing cycles of length r or less.The sampled edges are removed before the walk recursion.Source: §3.5 · p. 27
  • When (a − b)^2 > k(a + (k − 1)b), kCS-ABP* distinguishes every pair of communities with expected accuracy at least ϵ.The algorithm runs in O(n log n) time.Source: §3.5 · p. 28

3.6 Spectral view of ABP

The spectral view interprets ABP as power iteration on a nonbacktracking walk operator, avoiding a backtracking issue that affects adjacency-based reasoning.

3.6 Spectral view of ABP

  • Backtracking makes the expected square of the adjacency matrix differ substantially from the square of its expectation.This undermines the direct adjacency-matrix eigenvector argument for community detection.Source: §3.6 · p. 28
  • The nonbacktracking walk matrix W advances directed edges without immediately reversing direction.Source: §3.6 · p. 28
  • ABP can be viewed as power iteration that suppresses the leading-eigenvector component, leaving a vector correlated with the communities.The paper uses r-nonbacktracking walks to make the proof easier.Source: §3.6 · p. 29
  • The r-nonbacktracking walk matrix maps a path of length r − 1 to paths formed by adding an element at the end and deleting the first.Source: §3.6 · p. 29
  • Although r = 2 may suffice for the SBM, larger r might help graph models with more short cycles.Source: §3.6 · p. 30

3.7 ABP for the general SBM

For general SBMs with community-independent expected degrees, ABP compensates for stronger eigenvalue components and detects community differences under a generalized KS condition.

3.7 ABP for the general SBM

  • When communities have different expected degrees, degree-based grouping can detect them; the general analysis therefore assumes expected degree is community-independent.Source: §3.7 · p. 30
  • Random initial guesses can correlate with the relevant eigenvector at scale ±Ω(1/√n), providing a starting point for belief propagation.The algorithm then uses nonbacktracking walks to amplify information when neighborhoods run out of vertices.Source: §3.7 · p. 31
  • The general algorithm compensates for each eigenvalue whose magnitude exceeds the target eigenvalue’s magnitude.It uses a separate compensation transformation for each such eigenvalue.Source: §3.7 · p. 32
  • When λ2^2 > λ1, ABP detects a difference of at least ϵ between two community fractions with probability 1 − o(1), in O(n log n) time.The theorem applies to SBM(n, p, Q/n) with symmetric nonnegative Q.Source: §3.7 · p. 32

3.8 Alternatives

The section sketches alternative nonbacktracking-walk spectral methods and an edge-partition scheme for forcing walks out of tangles.

3.8 Alternatives

  • A symmetric matrix of length-r nonbacktracking-walk counts is proposed; its second-largest-magnitude eigenvector is expected to correlate with communities.The proposed eigenvector approximation uses a random vector and power iteration after estimating and removing the leading eigenvalue’s contribution.Source: §3.8 · pp. 32–33
  • The walk-count matrix can be computed recursively from the adjacency matrix and degree matrix, enabling efficient computation of the length-r matrix.The recurrence is Σ(t) = Σ(1)·Σ(t−1) − D·Σ(t−2) for t > 2.Source: §3.8 · p. 33
  • Partitioning edges into mostly E0 and smaller random sets imposes periodic walk restrictions that force walks to leave tangles without greatly reducing their number.Edges at selected steps must come from successive smaller sets; other steps use E0.Source: §3.8 · p. 33

4 Crossing the KS threshold: proof technique

The proof bounds how many typical clusterings are bad, refining a union-bound argument by exploiting the graph’s tree structure. These refinements yield a bound crossing the KS threshold at k = 4 and matching the optimal threshold when a = 0.

4 Crossing the KS threshold: proof technique

  • A union bound over at most k^n bad clusterings gives a regime with no bad typical clustering, but is loose when b = 0 and a lies in (k, 2k].For b = 0, separating giant components detects once a > k, whereas the union bound requires a > 2k.Source: §4 · p. 35
  • The refinement exploits tree-like components outside the giant, where labels follow a broadcasting process on a Galton–Watson tree.Tree structure helps estimate the total number of typical clusterings, which matters because the algorithm samples uniformly from that set.Source: §4 · pp. 33, 35
  • The analysis tightens typical-set size estimates by counting tree vertices and edges, then accounting for unsaturated vertices that can be swapped without changing typicality.The planted-tree refinement gives the right bound when b = 0 and is conjectured to capture behavior for small b.Source: §4 · pp. 35–36
  • A typical clustering can be built by propagating labels through trees and freezing planted-tree roots to their true labels.For isolated trees, a root label is sampled uniformly; the edge channel flips labels with probability b/(a + (k−1)b).Source: §4 · pp. 35–36
  • The final bound crosses the KS threshold at k = 4 and interpolates the optimal threshold at a = 0.The authors conjecture tight scaling in b for small b and fixed k, and in large k for fixed a and b.Source: §4 · p. 36

5 Open problems

The paper identifies unresolved questions about computational impossibility below the KS threshold and optimal accuracy beyond detection. It also points to extensions of the SBM, including sublinear communities.

5 Open problems

  • For k ≥ 4, proving computational impossibility below the KS threshold remains difficult because formal computational lower bounds seem out of reach.The text notes that evidence supports the conjecture, while exact information-theoretic thresholds at all SNRs also remain an open problem.Source: §5 · p. 37
  • For more than two communities, using ABP to improve accuracy with full BP requires converting correlated outputs into nontrivial vertex beliefs.A proposed approach initializes deeper BP from signed-edge frequencies and edge densities; the general-SBM conjecture imposes an eigenvector-separation condition, and the original ABP may fail to distinguish communities with identical relevant eigenvector entries.Source: §5 · pp. 37–38
  • Potential extensions include labelled, censored, degree-corrected, and overlapping block models, as well as sublinear-size communities that may pose new challenges.Source: §5 · p. 38

6.1 Achieving the KS threshold

This section analyzes acyclic belief propagation and its walk-based signal amplification, alongside shard-decomposition bounds used to control variance expressions. The variance analysis distinguishes the target eigenvector from the others and bounds the variance of W_m/S under degree-bound conditions.

6.1 Achieving the KS threshold

  • With probability 1 − o(1), ABP yields community assignment probabilities that differ across communities by a positive constant, establishing detection at the KS threshold.The proof derives community-level signal separation and shows the resulting assignment probabilities differ by at least ε for sufficiently large C and small ε.Source: §6.1 · pp. 40–41
  • ABP runs in O(n log n) time, including the walk-sum computation and eigenvalue compensation step.Initialization and assignment each take O(n) time; computing y(t) takes O(n log n) expected time, while computing y′′ takes o(n log n).Source: §6.1 · p. 41

6.1.1 Preliminaries

  • The walk decomposition lemma covers every walk edge with at most 3(w − e) + 1 fresh segments, disjoint except at endpoints.Each segment endpoint is the walk's start or end vertex or a vertex repeated in the walk.Source: §6.1.1 · p. 43

6.1.2 The shard decomposition

  • The shard decomposition rewrites the weighted walk expression as a linear combination of terms to which the factorization lemma applies, and the conversion terminates.The conversion also preserves a constraint linking deleted vertices to retained vertices within distance r.Source: §6.1.2 · p. 45
  • At most 3y(m + 1)xnm−m′−x pairs can produce a level x shard when the coefficient sequence has at most y nonzero elements.The bound counts possible deleted vertices and their locations in the original walk.Source: §6.1.2 · p. 49
  • For a nonbacktracking shard of an l[r]-cycle, the deleted subseries is unique, so its coefficient has absolute value at most Λ/n.This bound assumes a Λ-bounded eigenvalue approximation and follows because each deletion multiplies the coefficient by −ci/n.Source: §6.1.2 · p. 50

6.1.3 Bounding the variance of Wm/S

  • For the degree bound, m1 + m2 − m′′ ≤ x + 6(w − e) + 2 + e/r under the stated shard conditions.The section motivates these bounds by using joined walk expressions to bound variances of Wm/S; the degree-bound lemma assumes m1, m2 = O(log n), sufficiently large r, and the specified eigenvalue and cycle conditions.Source: §6.1.3 · pp. 50, 51, 53
  • For j ≠ s, the average is O(1/(ln(n)√n)), versus Ω(1/√n) for j = s.Under the stated degree-bound conditions, the target-eigenvalue case is also bounded below by Ω(n^-1/2 times the product of |λ_s-c_i|).Source: §6.1.3 · pp. 55, 60
  • The argument aggregates shard contributions by enumerating graph options and possible index sets, then bounds their combined expected contribution.The passages give at most 2m/r possible values of I and bound the number of graph options for fixed parameters; the resulting expression is omitted.Source: §6.1.3 · p. 64
  • Lemma 14 states a uniform bound for all v when the degree-bound conditions hold, r exceeds r0, and m exceeds m0 = Θ(log n).The supplied passage omits the bound's expression.Source: §6.1.3 · p. 64

6.2 Crossing the KS threshold

The section analyzes bad clusterings and the size of the typical set to derive information-theoretic detection bounds. The initial bound improves on the KS threshold in some parameter regimes but is loose at certain extremes.

6.2.1 Atypicality of a bad clustering

  • For a = 0, the bound on b is Θ(ln k/k) times the KS bound and improves on KS for k ≥ 5.The same bound is loose when b = 0 and for k = 2, a = 0; the paper says the next section improves the extremal-regime behavior.Source: §6.2.1 · p. 65

6.2.2 Size of the typical set

  • A random-order reassignment preserves the joint distribution of the graph and clustering, so the resulting clustering belongs to the typical set with probability 1 − o(1).Vertices with multiple available assignments provide choices in constructing such clusterings.Source: §6.2.2 · p. 70
  • The proof constructs typical labelings by assigning random labels on isolated trees and propagating labels along their edges through a k-ary symmetric channel.The resulting assignment is typical with high probability as the number of tree edges grows.Source: §6.2.2 · p. 72

6.2.3 Sampling probability estimates

  • The sampling-probability analysis combines bounds on typical-set size and bad-clustering probability to derive the theorem’s bound.The supplied passages do not state the resulting bound’s condition.Source: §6.2.3 · pp. 76–77

6.3 Learning the model

This section uses cycle counts in the SBM to estimate model parameters. It relates expected cycle counts to eigenvalues and notes that non-backtracking walks can replace cycles for an efficient estimator.

6.3 Learning the model

  • The expected number of length-m cycles is asymptotic to (1/2m) times the sum of the mth powers of the eigenvalues of PQ.The eigenvalues are counted with multiplicity.Source: §6.3 · p. 77
  • Cycle counts for lengths up to M = ω(1), together with the edge count, estimate (a − b)/k and k with asymptotically vanishing error, yielding estimates of a and b.The edge count estimates k up to O(1/√n).Source: §6.3 · p. 78
  • For an efficient estimator, the paper proposes counting non-backtracking walks instead of cycles.Source: §6.3 · p. 78

Related papers

Loading 1512.09080v4…