The NFM separated-eigenvector conjecture under Dirichlet noise

Let G=(V,W)G=(V,W) be generated using the node-feature model (NFM), with simplex distribution given by a Dirichlet distribution with constant parameter α\bm{\alpha}. For j[k]j\in[k], define

Vj:={i[n]:θjit(k,α)},Θj:=Θ(Vj,:).V_j':= \{i\in[n]:\theta^i_j\geq t(k,\bm{\alpha})\},\qquad \Theta_j:=\Theta(V_j',:).

NFM separated-eigenvector conjecture. There exists a scalar t(k,α)(0.5,1/2)t(k,\bm{\alpha})\in(0.5,1/\sqrt{2}) such that, for every j[k]j\in[k], with probability not converging to 00 as nn\to\infty, the largest eigenvalue of

4.4ΘjΘjT2.2E4.4\Theta_j\Theta_j^T-2.2E

is well separated from the remaining eigenvalues and its corresponding eigenvector is positive.

The conjecture formalizes the computational observation that strong-node subgraphs have a dominant positive spectral direction, which could support robust identification of cluster structure under asymmetric noise.

Sources & referencesView supporting material

Primary source

Jimit Majmudar and Stephen Vavasis, “Robust Correlation Clustering with Asymmetric Noise”, arXiv:2110.08385 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.