Averaging whenever you meet: community recovery on clustered graphs with a sparse cut #
Section 4 of arXiv:1703.05045 (v3) analyses Averaging(1/2) on an (n, d, b)-clustered regular
graph whose cut is sparse with respect to the inner expansion, λ₂ = 2b/d ≪ λ₃. The randomness is
the uniform initial vector x⁽⁰⁾ ∈ {-1, 1}ⁿ (the first-activation coins, see
Averaging.Opportunistic.oppRun_getD) together with i.i.d. uniform edges.
- Theorem 4.1 (second moment): for
3 (n/λ₃) log n ≤ t ≤ n/(4λ₂),E‖y⁽ᵗ⁾ + z⁽ᵗ⁾ - y⁽⁰⁾‖² ≤ 3 λ₂ t / n. - Lemma 4.2 (non-ephemeral good nodes): if
λ₂/λ₃ ≤ λ₃ ε⁴/(c log² n), then with probability at least1 - εat least(1 - 3ε) nnodes areε-good (Definition 4.1) at every round of the phase6 (n/λ₃) log n ≤ t ≤ 12 (n/λ₃) log n. - Main theorem (sign recovery over the phase, Sections 4.2 and C.4): an
ε-good nodevhas the sign ofx_∥,v + y⁽⁰⁾_v, the initial average of its own community, unless this average is too small, which has probabilityO(ε)(Lemma A.1). So, with probability1 - O(ε), all butO(ε) nnodes have the sign of their community's initial average throughout the phase (sign_phase). The two initial averages have opposite signs with probability1/2 - o(1); hence, with probability1/2 - O(ε), the sign of the values (+1if positive,-1otherwise) is anO(ε)-weak reconstruction (Definition 2.3) of the communities at every round of the phase (weakReconstruction_phase).
Logarithms are natural. The constant c ("large enough" in the paper) and the constant C of the
O(ε) terms are existential.
Definition 4.1: node v is ε-good in the state x = x⁽ᵗ⁾ reached from the initial state
x₀ = x⁽⁰⁾ if (x_v - (x_∥,v + y⁽⁰⁾_v))² ≤ (ε²/n) ‖y⁽⁰⁾‖².
Equations
- One or more equations did not get rendered due to their size.
Instances For
Definition 2.3: the labelling f : V → {±1} is an ε-weak reconstruction of the communities
V₁ and V₂ = V₁ᶜ if some W₁ ⊆ V₁ and W₂ ⊆ V₂, each of size at least (1 - ε) n/2, receive
disjoint sets of labels.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Lemma 4.2 on a general vertex type #
Lemma 4.2 (c = 10⁶) on a general vertex type, for ε ≤ 1.
The hypothesis of Lemma 4.2 forces n ε⁴ ≥ 5·10⁵.
A small initial community average forces one block sum to be small.
Good nodes, when the community averages are not too small, have the right sign.
Sign recovery over the phase (c = 10⁶, C = 4) on a general vertex type.
On the good event with opposite community averages that are not too small, the sign of the
values is a 6ε-weak reconstruction.
Weak reconstruction over the phase (c = 10⁶, C = 6) on a general vertex type.
Theorem 4.1 (second moment analysis): on an (n, d, b)-clustered regular graph with
λ₂ = 2b/d = o(λ₃ / log n) (here c λ₂ log n ≤ λ₃ for a large enough constant c), for every
round 3 (n/λ₃) log n ≤ t ≤ n/(4λ₂), E‖y⁽ᵗ⁾ + z⁽ᵗ⁾ - y⁽⁰⁾‖² ≤ 3 λ₂ t / n, the expectation
being over the uniform initial vector and the t uniform edges.
Lemma 4.2 (non-ephemeral good nodes): on an (n, d, b)-clustered regular graph with
λ₂/λ₃ ≤ λ₃ ε⁴/(c log² n) for a large enough constant c (λ₂ = 2b/d), with probability at least
1 - ε over the initial vector and the edges, at least (1 - 3ε) n nodes are ε-good at every
round t of the phase 6 (n/λ₃) log n ≤ t ≤ 12 (n/λ₃) log n.
Sign recovery over the phase (Lemma 4.2 with Lemma A.1, as in Section 4.2 and in the proof of
Lemma C.7): under the hypotheses of Lemma 4.2, with probability at least 1 - C ε, at least
(1 - C ε) n nodes v have, at every round of the phase, the sign of x_∥,v + y⁽⁰⁾_v, the
initial average of the community of v.
Main theorem (averaging whenever you meet recovers the communities): on an
(n, d, b)-clustered regular graph with λ₂/λ₃ ≤ λ₃ ε⁴/(c log² n) for a large enough constant c
(λ₂ = 2b/d), with probability at least 1/2 - C ε over the initial coins and the edges, the sign
of the values (+1 for a positive value, -1 otherwise) is a C ε-weak reconstruction of the two
communities at every round of the phase 6 (n/λ₃) log n ≤ t ≤ 12 (n/λ₃) log n.