Documentation

Averaging.OpportunisticSparseCut

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.

Logarithms are natural. The constant c ("large enough" in the paper) and the constant C of the O(ε) terms are existential.

def Averaging.Opportunistic.IsGood {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (ε : ℝ) (x₀ x : V → ℝ) (v : V) :

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
    def Averaging.Opportunistic.IsWeakReconstruction {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (ε : ℝ) (f : V → ℤˣ) :

    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 #

      The phase 6 (n/λ₃) log n ≤ t ≤ 12 (n/λ₃) log n in integer form.

      theorem Averaging.Opportunistic.IsClusteredRegular.prob_good_window {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) {ε : ℝ} (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hl3 : 0 < lam3) (hc : 2 * ↑b / ↑d / lam3 ≤ lam3 * ε ^ 4 / (10 ^ 6 * Real.log ↑(Fintype.card V) ^ 2)) :
      1 - ε ≤ Dynamics.avg fun (σ : V → ℤˣ) => Dynamics.expList G.Dart ⌊12 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V)⌋₊ fun (l : List G.Dart) => if (1 - 3 * ε) * ↑(Fintype.card V) ≤ ↑{v : V | ∀ (t : ℕ), 6 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V) ≤ ↑t → ↑t ≤ 12 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V) → IsGood V₁ ε (signVec σ) (avgRun G (signVec σ) (List.take t l)) v}.card then 1 else 0

      Lemma 4.2 (c = 10⁶) on a general vertex type, for ε ≤ 1.

      theorem Averaging.Opportunistic.IsClusteredRegular.card_mul_pow_four_ge {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) {ε : ℝ} (hε0 : 0 < ε) (hl3 : 0 < lam3) (hc : 2 * ↑b / ↑d / lam3 ≤ lam3 * ε ^ 4 / (10 ^ 6 * Real.log ↑(Fintype.card V) ^ 2)) :
      5 * 10 ^ 5 ≤ ↑(Fintype.card V) * ε ^ 4

      The hypothesis of Lemma 4.2 forces n ε⁴ ≥ 5·10⁵.

      theorem Averaging.Opportunistic.inv_sqrt_half_le {N ε : ℝ} (hN : 0 ≤ N) (hε0 : 0 < ε) (hε1 : ε ≤ 1) (h : 5 * 10 ^ 5 ≤ N * ε ^ 4) :
      1 / √(N / 2 + 1) ≤ ε / 10
      theorem Averaging.Opportunistic.IsClusteredRegular.blockSum_small {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) {ε : ℝ} (hε0 : 0 ≤ ε) (hε1 : ε ≤ 1) (σ : V → ℤˣ) (v : V) (h : (projOne (signVec σ) v + projCut V₁ (signVec σ) v) ^ 2 ≤ ε ^ 2 / ↑(Fintype.card V) * ∑ w : V, projCut V₁ (signVec σ) w ^ 2) :
      |blockSum V₁ σ| ≤ ε * |blockSum V₁ᶜ σ| ∨ |blockSum V₁ᶜ σ| ≤ ε * |blockSum V₁ σ|

      A small initial community average forces one block sum to be small.

      theorem Averaging.Opportunistic.pos_iff_of_sq_lt {x μ : ℝ} (h : (x - μ) ^ 2 < μ ^ 2) :
      0 < x ↔ 0 < μ
      theorem Averaging.Opportunistic.sq_sub_lt_of_good {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} {ε : ℝ} {x₀ x : V → ℝ} {v : V} (hgood : IsGood V₁ ε x₀ x v) (hs : ε ^ 2 / ↑(Fintype.card V) * ∑ w : V, projCut V₁ x₀ w ^ 2 < (projOne x₀ v + projCut V₁ x₀ v) ^ 2) :
      (x v - (projOne x₀ v + projCut V₁ x₀ v)) ^ 2 < (projOne x₀ v + projCut V₁ x₀ v) ^ 2

      Good nodes, when the community averages are not too small, have the right sign.

      theorem Averaging.Opportunistic.IsClusteredRegular.prob_sign_window {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) {ε : ℝ} (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hl3 : 0 < lam3) (hc : 2 * ↑b / ↑d / lam3 ≤ lam3 * ε ^ 4 / (10 ^ 6 * Real.log ↑(Fintype.card V) ^ 2)) :
      1 - 4 * ε ≤ Dynamics.avg fun (σ : V → ℤˣ) => Dynamics.expList G.Dart ⌊12 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V)⌋₊ fun (l : List G.Dart) => if (1 - 4 * ε) * ↑(Fintype.card V) ≤ ↑{v : V | ∀ (t : ℕ), 6 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V) ≤ ↑t → ↑t ≤ 12 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V) → SignType.sign (avgRun G (signVec σ) (List.take t l) v) = SignType.sign (projOne (signVec σ) v + projCut V₁ (signVec σ) v)}.card then 1 else 0

      Sign recovery over the phase (c = 10⁶, C = 4) on a general vertex type.

      theorem Averaging.Opportunistic.IsClusteredRegular.isWeakReconstruction_of_good {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) {ε : ℝ} (σ : V → ℤˣ) (x : V → ℝ) (Good : Finset V) (hcount : (1 - 3 * ε) * ↑(Fintype.card V) ≤ ↑Good.card) (hgood : ∀ v ∈ Good, IsGood V₁ ε (signVec σ) x v) (hs : ∀ (v : V), ε ^ 2 / ↑(Fintype.card V) * ∑ w : V, projCut V₁ (signVec σ) w ^ 2 < (projOne (signVec σ) v + projCut V₁ (signVec σ) v) ^ 2) (hopp : blockSum V₁ σ * blockSum V₁ᶜ σ < 0) :
      IsWeakReconstruction V₁ (6 * ε) fun (v : V) => if 0 < x v then 1 else -1

      On the good event with opposite community averages that are not too small, the sign of the values is a 6ε-weak reconstruction.

      theorem Averaging.Opportunistic.IsClusteredRegular.prob_weakReconstruction_window {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) {ε : ℝ} (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hl3 : 0 < lam3) (hc : 2 * ↑b / ↑d / lam3 ≤ lam3 * ε ^ 4 / (10 ^ 6 * Real.log ↑(Fintype.card V) ^ 2)) :
      1 / 2 - 6 * ε ≤ Dynamics.avg fun (σ : V → ℤˣ) => Dynamics.expList G.Dart ⌊12 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V)⌋₊ fun (l : List G.Dart) => if ∀ (t : ℕ), 6 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V) ≤ ↑t → ↑t ≤ 12 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V) → IsWeakReconstruction V₁ (6 * ε) fun (v : V) => if 0 < avgRun G (signVec σ) (List.take t l) v then 1 else -1 then 1 else 0

      Weak reconstruction over the phase (c = 10⁶, C = 6) on a general vertex type.

      theorem Averaging.Opportunistic.secondMoment_bound :
      ∃ (c : ℝ), 0 < c ∧ ∀ (n : ℕ) (G : SimpleGraph (Fin n)) [inst : DecidableRel G.Adj] (V₁ : Finset (Fin n)) (d b : ℕ) (lam3 : ℝ), IsClusteredRegular G V₁ d b → ThirdEigenvalueLB G V₁ d lam3 → c * (2 * ↑b / ↑d) * Real.log ↑n ≤ lam3 → ∀ (t : ℕ), 3 * ↑n / lam3 * Real.log ↑n ≤ ↑t → ↑t ≤ ↑n / (4 * (2 * ↑b / ↑d)) → (Dynamics.avg fun (σ : Fin n → ℤˣ) => Dynamics.expList G.Dart t fun (l : List G.Dart) => ∑ v : Fin n, (projCut V₁ (avgRun G (signVec σ) l) v + projRest V₁ (avgRun G (signVec σ) l) v - projCut V₁ (signVec σ) v) ^ 2) ≤ 3 * (2 * ↑b / ↑d) * ↑t / ↑n

      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.

      theorem Averaging.Opportunistic.nonEphemeral_good :
      ∃ (c : ℝ), 0 < c ∧ ∀ (n : ℕ) (G : SimpleGraph (Fin n)) [inst : DecidableRel G.Adj] (V₁ : Finset (Fin n)) (d b : ℕ) (lam3 ε : ℝ), IsClusteredRegular G V₁ d b → ThirdEigenvalueLB G V₁ d lam3 → 0 < lam3 → 0 < ε → 2 * ↑b / ↑d / lam3 ≤ lam3 * ε ^ 4 / (c * Real.log ↑n ^ 2) → 1 - ε ≤ Dynamics.avg fun (σ : Fin n → ℤˣ) => Dynamics.expList G.Dart ⌊12 * ↑n / lam3 * Real.log ↑n⌋₊ fun (l : List G.Dart) => if (1 - 3 * ε) * ↑n ≤ ↑{v : Fin n | ∀ (t : ℕ), 6 * ↑n / lam3 * Real.log ↑n ≤ ↑t → ↑t ≤ 12 * ↑n / lam3 * Real.log ↑n → IsGood V₁ ε (signVec σ) (avgRun G (signVec σ) (List.take t l)) v}.card then 1 else 0

      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.

      theorem Averaging.Opportunistic.sign_phase :
      ∃ (c : ℝ) (C : ℝ), 0 < c ∧ 0 < C ∧ ∀ (n : ℕ) (G : SimpleGraph (Fin n)) [inst : DecidableRel G.Adj] (V₁ : Finset (Fin n)) (d b : ℕ) (lam3 ε : ℝ), IsClusteredRegular G V₁ d b → ThirdEigenvalueLB G V₁ d lam3 → 0 < lam3 → 0 < ε → 2 * ↑b / ↑d / lam3 ≤ lam3 * ε ^ 4 / (c * Real.log ↑n ^ 2) → 1 - C * ε ≤ Dynamics.avg fun (σ : Fin n → ℤˣ) => Dynamics.expList G.Dart ⌊12 * ↑n / lam3 * Real.log ↑n⌋₊ fun (l : List G.Dart) => if (1 - C * ε) * ↑n ≤ ↑{v : Fin n | ∀ (t : ℕ), 6 * ↑n / lam3 * Real.log ↑n ≤ ↑t → ↑t ≤ 12 * ↑n / lam3 * Real.log ↑n → SignType.sign (avgRun G (signVec σ) (List.take t l) v) = SignType.sign (projOne (signVec σ) v + projCut V₁ (signVec σ) v)}.card then 1 else 0

      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.

      theorem Averaging.Opportunistic.weakReconstruction_phase :
      ∃ (c : ℝ) (C : ℝ), 0 < c ∧ 0 < C ∧ ∀ (n : ℕ) (G : SimpleGraph (Fin n)) [inst : DecidableRel G.Adj] (V₁ : Finset (Fin n)) (d b : ℕ) (lam3 ε : ℝ), IsClusteredRegular G V₁ d b → ThirdEigenvalueLB G V₁ d lam3 → 0 < lam3 → 0 < ε → 2 * ↑b / ↑d / lam3 ≤ lam3 * ε ^ 4 / (c * Real.log ↑n ^ 2) → 1 / 2 - C * ε ≤ Dynamics.avg fun (σ : Fin n → ℤˣ) => Dynamics.expList G.Dart ⌊12 * ↑n / lam3 * Real.log ↑n⌋₊ fun (l : List G.Dart) => if ∀ (t : ℕ), 6 * ↑n / lam3 * Real.log ↑n ≤ ↑t → ↑t ≤ 12 * ↑n / lam3 * Real.log ↑n → IsWeakReconstruction V₁ (C * ε) fun (v : Fin n) => if 0 < avgRun G (signVec σ) (List.take t l) v then 1 else -1 then 1 else 0

      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.