feature-aware spectral embeddings

[[concept]]

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 R^{n \times d}$ . Suppose we have $C$ communities that we want to assign to the nodes.

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

Comparison to spectral embedding

Before, we had

Spectral Embedding Problem

$min_{f} \sum_{i \in T} 1 (f (A)_{i} = y_{i}), f \in {f (A) = σ (V_{c} W), W \in R^{C \times C}}$

Now, our hypothesis class is instead:

Feature-Aware Spectral Embedding Hypothesis Class

f (A, x) = σ (V_{c + κ} W), W \in R^{(c + κ) + (c + κ)} $ $^{h} y p o t h e s i s - c l a s s > [! n o t e] > I n t h e p r e s e n c e o f n o d e f e a t u r e s, t h e [[C o n c e p t W i k i / i n f o r m a t i o n t h e o r e t i c t h r e s h o l d ∥ i n f o r m a t i o n t h e o r e t i c t h r e s h o l d]] f o r c o m m u n i t y d e t e c t i o n b e c o m e s (w i t h $ p = \frac{a}{n}, q = \frac{b}{n} $) $ $ S N R (A) + S N R (x) = \frac{(a - b)^{2}}{2 (a + b)} + \frac{μ^{2} d}{n} > 1

Takeaway

the community detection is possible in an information theoretic sense when $p \approx q$ as long as the means of the communities are sufficiently separated (high $μ$ and/or high $d$ ).

Mentions

File
sometimes spectral algorithms fail
2025-02-12 graphs lecture 7