almost exact recovery is impossible when the signal to noise ratio is less than the threshold

TABLE WITHOUT ID file.cday as "Created", file.mday as "Last Edited", length(modified) as "Edits"
 
WHERE file.link = this.file.link

Data

subject:: Data Science Methods for Large Scale Graphs parent:: Graph Signals and Graph Signal Processing theme:: math notes

Theorem

Suppose we have a stochastic block model problem where the adjacency matrix $A\sim P,P=YB{Y}^T$, and $B=\{\begin{array}{l}p\text{ if }{c}_1=c_2\\ q\text{ otherwise}\end{array}$.

If the signal to noise ratio $SNR<\frac{1}{n}$, then almost exact recovery is impossible.

Even with infinite time and resources, there is no algorithm that can recover the true communities with just the probabilities of adjacency. This gives us the information theoretic threshold

Proof

see proofs in Massoulié (2014) and Mossel (2014). Aside: interesting to see since there are different proof methods from different domains. See also Abbe (survey papers).

Example: Sparse Graphs

$p=\frac{a}{n},q=\frac{b}{n}$ and $\frac{|E|}{n^2}\to 0$ as $n\to \infty$ (the average degree vanishes).

Then $SNR=\frac{{\left(\frac{a}{n}-\frac{b}{n}\right)}^2}{2\frac{(a+b)}{n}}=\frac{1}{2n}\frac{(a-b{)}^2}{(a+b)}$ ie, in sparse graphs, it is not difficult to identify the information theoretic threshhold (we can easily calculate the signal to noise ratio)

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source