feature-aware spectral embeddings

[[concept]]

feature-aware spectral embeddings

feature-aware spectral embeddings incorporate the availability of node features into our predictions (for example, in a C-SBM) when using spectral embedding.

Let $G$ be a graph with diagonalizable adjacency matrix $A$ and node features $X\in {\mathbb{R}}^{n\times d}$. Suppose we have $C$ communities that we want to assign to the nodes.

1. Diagonalize $X{X}^T\in {\mathbb{R}}^{n\times n}$ as $\tilde{V}\Lambda {\tilde{V}}^T$
2. Pick the top $\kappa$ eigenvectors to create ${\tilde{V}}_{(\kappa )}\in {\mathbb{R}}^{n\times \kappa }$
3. Define $V_{c+\kappa }=[V_c|{\tilde{V}}_{(\kappa )}]$ where $V_c$ are the top $C$ eigenvectors of $A$.

Comparison to spectral embedding

Before, we had >[!equation] Spectral Embedding Problem

$\min_{f} \sum_{i \in T} \mathbb{1}(f(A){i} = y{i}), ;;; f \in{ f(A) = \sigma(V_{c}W), W \in \mathbb{R}^{C\times C} }$$

Now, our hypothesis class is instead:

Feature-Aware Spectral Embedding Hypothesis Class

$f(A,x)=\sigma (V_{c+\kappa }W),W\in {\mathbb{R}}^{(c+\kappa )+(c+\kappa )}$

Note

In the presence of node features, the information theoretic threshold for community detection becomes (with $p=\frac{a}{n},q=\frac{b}{n}$) $SNR(A)+SNR(x)=\frac{(a-b{)}^2}{2(a+b)}+\frac{{\mu }^{2}d}{n}>1$

Takeaway $p\approx q$ as long as the means of the communities are sufficiently separated (high $\mu$ and/or high $d$).

the community detection is possible in an information theoretic sense when

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