Editing Openai/693e3ce6-229c-8008-97dc-ab720cb1f95a (section)

=== Assistant: Yes—there’s a clean way to package this as a primal–dual KKT certificate theorem plus a graph-structural corollary. ===
Yes—there’s a clean way to package this as a primal–dual (KKT certificate) theorem plus a graph-structural corollary. The main idea is:
* pick a “target cluster” CCC containing the seed,
* show the restricted minimizer supported on CCC is also the global minimizer (via strict dual feasibility on V∖CV\setminus CV∖C),
* then the margin is at least the dual-feasibility slack, which you can lower bound by something like Θ(ρ)\Theta(\sqrt{\rho})Θ(ρ) if (i) outside degrees are large enough so λi=ραdi\lambda_i=\rho\alpha\sqrt{d_i}λi=ραdi is ≳ρ\gtrsim \sqrt{\rho}≳ρ, and (ii) boundary coupling is small (low conductance / dispersed boundary) and CCC is internally well-conditioned.

I’ll write a theorem in a form that is actually checkable and then interpret it in cluster terms.

==== We’re in the ℓ1\ell_1ℓ1-regularized PPR problem (your eq. (3)) open-problem-fountoulakis22a ====

:

min⁡x∈Rn  F(x)=f(x)+g(x),f(x)=12x⊤Qx−αx⊤D−1/2s,g(x)=∑i=1nλi∣xi∣,\min_{x\in\mathbb{R}^n}\;F(x)= f(x)+g(x),\quad
f(x)=\tfrac12 x^\top Qx-\alpha x^\top D^{-1/2}s,\quad
g(x)=\sum_{i=1}^n \lambda_i |x_i|,x∈RnminF(x)=f(x)+g(x),f(x)=21x⊤Qx−αx⊤D−1/2s,g(x)=i=1∑nλi∣xi∣,
with

Q=αI+1−α2L,λi=ραdi,b:=αD−1/2s.Q=\alpha I+\tfrac{1-\alpha}{2}L,\qquad \lambda_i=\rho\alpha\sqrt{d_i},\qquad b:=\alpha D^{-1/2}s.Q=αI+21−αL,λi=ραdi,b:=αD−1/2s.
Let x⋆x^\starx⋆ be the unique minimizer and I⋆={i:xi⋆=0}I^\star=\{i:x_i^\star=0\}I⋆={i:xi⋆=0}.
The margin is

γ:=min⁡i∈I⋆(λi−∣∇f(x⋆)i∣)=min⁡i∈I⋆(λi−∣(Qx⋆−b)i∣).\gamma := \min_{i\in I^\star}\bigl(\lambda_i-|\nabla f(x^\star)_i|\bigr)
= \min_{i\in I^\star}\bigl(\lambda_i-| (Qx^\star-b)_i|\bigr).γ:=i∈I⋆min(λi−∣∇f(x⋆)i∣)=i∈I⋆min(λi−∣(Qx⋆−b)i∣).

==== ### ====

Let C⊆VC\subseteq VC⊆V contain the seed node vvv (i.e. s=evs=e_vs=ev and v∈Cv\in Cv∈C). Define the complement Cˉ:=V∖C\bar C:=V\setminus CCˉ:=V∖C. Partition QQQ and bbb into blocks (C,Cˉ)(C,\bar C)(C,Cˉ).

Assume there exists a vector x^∈Rn\hat x\in\mathbb{R}^nx^∈Rn supported on CCC (i.e. x^Cˉ=0\hat x_{\bar C}=0x^Cˉ=0) such that:
# Stationarity on CCC with a known sign pattern. There is a sign vector σC∈{−1,+1}∣C∣\sigma_C\in\{-1,+1\}^{|C|}σC∈{−1,+1}∣C∣ such that QCCx^C−bC+λC∘σC=0.Q_{CC}\hat x_C - b_C + \lambda_C\circ \sigma_C = 0.QCCx^C−bC+λC∘σC=0. (In the PPR setting one often expects x^C≥0\hat x_C\ge 0x^C≥0, so σC=1\sigma_C=\mathbf{1}σC=1.)
# Strict dual feasibility off CCC (a uniform slack η∈(0,1)\eta\in(0,1)η∈(0,1)). For all i∈Cˉi\in\bar Ci∈Cˉ, ∣(QCˉCx^C−bCˉ)i∣≤(1−η)λi.|(Q_{\bar C C}\hat x_C - b_{\bar C})_i| \le (1-\eta)\lambda_i.∣(QCˉCx^C−bCˉ)i∣≤(1−η)λi.

Then:
* x^\hat xx^ is the unique global minimizer: x^=x⋆\hat x=x^\starx^=x⋆, hence \supp(x⋆)⊆C\supp(x^\star)\subseteq C\supp(x⋆)⊆C.
* The margin satisfies the explicit lower bound γ  ≥  ηmin⁡i∈Cˉλi  =  η ραmin⁡i∈Cˉdi.\gamma \;\ge\; \eta\min_{i\in\bar C}\lambda_i \;=\; \eta\,\rho\alpha\min_{i\in\bar C}\sqrt{d_i}.γ≥ηi∈Cˉminλi=ηραi∈Cˉmindi.

In particular, if the outside minimum degree satisfies

min⁡i∈Cˉdi  ≥  c0α2ρfor some c0>0,\min_{i\in\bar C} d_i \;\ge\; \frac{c_0}{\alpha^2\rho}
\quad\text{for some }c_0>0,i∈Cˉmindi≥α2ρc0for some c0>0,
then

γ  ≥  η ραc0α2ρ  =  ηc0 ρ  =  Ω(ρ).\gamma \;\ge\; \eta\,\rho\alpha\sqrt{\frac{c_0}{\alpha^2\rho}}
\;=\;\eta\sqrt{c_0}\,\sqrt{\rho}
\;=\;\Omega(\sqrt{\rho}).γ≥ηραα2ρc0=ηc0ρ=Ω(ρ).
Why this theorem is the right abstraction.
It’s the exact analogue of a standard Lasso “primal–dual witness” / strict dual feasibility condition: once you have strict feasibility on the complement, the support is stable and you get a quantitative margin.

==== The theorem above is “certificate-based.” To connect it to conductance and “internally well connected,” you want easy-to-check conditions that imply the strict dual feasibility inequality. ====

Here is a sufficient (strong but explicit) set of structural assumptions that imply the certificate.

===== Let C⊆VC\subseteq VC⊆V contain the seed vvv, and suppose: =====

(A) Internal connectivity / conditioning on CCC.
The principal submatrix QCCQ_{CC}QCC satisfies

λmin⁡(QCC)≥μC,\lambda_{\min}(Q_{CC}) \ge \mu_C,λmin(QCC)≥μC,
for some μC>0\mu_C>0μC>0.
A natural way to ensure this is to assume CCC has a positive Dirichlet spectral gap for the normalized Laplacian (or, more informally, CCC is an internal expander); then μC\mu_CμC is bounded below by α+1−α2λmin⁡(LCD)\alpha+\tfrac{1-\alpha}{2}\lambda_{\min}(L^D_C)α+21−αλmin(LCD).

(B) Low external conductance and “dispersed boundary.”
Let cut(C,Cˉ)\mathrm{cut}(C,\bar C)cut(C,Cˉ) be the number of edges crossing (C,Cˉ)(C,\bar C)(C,Cˉ). Assume

ϕ(C)=cut(C,Cˉ)vol(C)≤coutρandmax⁡i∈Cˉdeg⁡C(i)≤b,\phi(C)=\frac{\mathrm{cut}(C,\bar C)}{\mathrm{vol}(C)} \le c_{\mathrm{out}}\rho
\quad\text{and}\quad
\max_{i\in\bar C}\deg_C(i)\le b,ϕ(C)=vol(C)cut(C,Cˉ)≤coutρandi∈CˉmaxdegC(i)≤b,
where deg⁡C(i)\deg_C(i)degC(i) is the number of neighbors of iii inside CCC, and bbb is a modest constant.
(Heuristically: not only is the cut small, it’s not concentrated onto a single outside low-degree node.)

(C) Degree lower bounds.

dj≥dC,min⁡  ∀j∈C,di≥dout  ∀i∈Cˉ,dout≥c0α2ρ.d_j \ge d_{C,\min}\ \ \forall j\in C,
\qquad
d_i \ge d_{\mathrm{out}}\ \ \forall i\in\bar C,
\qquad
d_{\mathrm{out}} \ge \frac{c_0}{\alpha^2\rho}.dj≥dC,min  ∀j∈C,di≥dout  ∀i∈Cˉ,dout≥α2ρc0.
(D) Choose ρ\rhoρ so the restricted solution is nonnegative (and not at a breakpoint).
Define the candidate supported on CCC (assuming positivity)

x^C:=QCC−1(bC−λC),x^Cˉ:=0,\hat x_C := Q_{CC}^{-1}(b_C-\lambda_C),
\qquad \hat x_{\bar C}:=0,x^C:=QCC−1(bC−λC),x^Cˉ:=0,
and assume x^C≥0\hat x_C\ge 0x^C≥0 componentwise, and that the following “boundary domination” inequality holds for some η∈(0,1)\eta\in(0,1)η∈(0,1):

1−α2bdoutdC,min⁡⏟(boundary coupling)⋅∥x^C∥2⏟(signal on C) ≤ (1−η)ραdout⏟min⁡i∈Cˉλi.\underbrace{\frac{1-\alpha}{2}\sqrt{\frac{b}{d_{\mathrm{out}}d_{C,\min}}}}_{\text{(boundary coupling)}}
\cdot
\underbrace{\|\hat x_C\|_2}_{\text{(signal on }C\text{)}}
\ \le\
(1-\eta)\underbrace{\rho\alpha\sqrt{d_{\mathrm{out}}}}_{\min_{i\in\bar C}\lambda_i}.(boundary coupling)21−αdoutdC,minb⋅(signal on C)∥x^C∥2 ≤ (1−η)mini∈Cˉλiραdout.
Then the strict dual feasibility condition holds, so x^=x⋆\hat x=x^\starx^=x⋆ and

γ≥η ραdout≥ηc0ρ.\gamma \ge \eta\,\rho\alpha\sqrt{d_{\mathrm{out}}} \ge \eta\sqrt{c_0}\sqrt{\rho}.γ≥ηραdout≥ηc0ρ.
Interpretation.
* Low conductance keeps the interaction across (C,Cˉ)(C,\bar C)(C,Cˉ) limited.
* Internal connectivity keeps QCCQ_{CC}QCC well-conditioned, preventing ∥x^C∥\|\hat x_C\|∥x^C∥ from blowing up.
* High degree outside ensures the thresholds λi=ραdi\lambda_i=\rho\alpha\sqrt{d_i}λi=ραdi are at least Θ(ρ)\Theta(\sqrt{\rho})Θ(ρ) (this is necessary for γ\gammaγ to be Θ(ρ)\Theta(\sqrt{\rho})Θ(ρ), because γ≤min⁡i∈I⋆λi\gamma\le \min_{i\in I^\star}\lambda_iγ≤mini∈I⋆λi).
* Dispersed boundary prevents a single outside vertex from having a large coupling QiCQ_{iC}QiC.

==== - This kind of theorem is plausible and standard (it’s exactly the strict dual feasibility logic), but it does require assumptions that are stronger than just “small conductance”. In particular, without something like “no low-degree boundary whiskers” (or at least “inactive nodes have large degree”), you cannot hope for γ≳ρ\gamma\gtrsim \sqrt{\rho}γ≳ρ, because γ≤min⁡i∈I⋆λi=ραmin⁡i∈I⋆di\gamma \le \min_{i\in I^\star}\lambda_i = \rho\alpha\min_{i\in I^\star}\sqrt{d_i}γ≤mini∈I⋆λi=ραmini∈I⋆di. ====
* If you’re thinking in the usual sparse-graph local clustering regime (many degree-1/2 nodes), the best “natural” order you can hope for is more like γ=Θ(ρ)\gamma=\Theta(\rho)γ=Θ(ρ) (up to constants), not Θ(ρ)\Theta(\sqrt{\rho})Θ(ρ).

If you want, I can convert the theorem + corollary into a compact LaTeX section and align notation precisely with your earlier appendices (including a short proof: it’s a one-page KKT/primal–dual witness argument).