Spectral Graph Connectivity and Spherical Representation Fusion

An Undergraduate Guide to Graph Laplacians, Random-Walk Mixing, and Multi-Modal Clustering on the Unit Hypersphere

1 Why Hard Single-Topic Assignment Breaks Graph Random Walks

Suppose you want to organize thousands of technical or legal documents into \(T\) thematic clusters using both text embeddings (what words a document uses) and graph structure (how documents connect to shared topics and to one another).

A common beginner mistake is to build a single-topic top-1 bipartite graph \(G_{\mathrm{bipartite}}\), where each document node \(d_i\) connects only to its single highest-scoring topic hub \(t_{m^*(i)}\). As we show below using elementary linear algebra, this seemingly natural choice shatters the graph into \(T\) isolated pieces and prevents random-walk algorithms from learning how topics relate to one another!

2 Step 1: The Normalized Graph Laplacian and Conditional Spectral Connectivity

For any weighted undirected graph \(G = (V, E, \mathbf{A})\) without isolated vertices, the normalized graph Laplacian is defined as:

\[\mathcal{L} = \mathbf{I} - \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}, \qquad 0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_{|V|} \le 2.\]

A foundational theorem of Spectral Graph Theory states that the multiplicity of the \(0\) eigenvalue (\(\dim\ker(\mathcal{L})\)) equals the exact number of connected components in the graph:

1. The Disconnected Bipartite Star Trap (\(\dim\ker(\mathcal{L}_{\mathrm{bipartite}}) = T > 1\)): When each document links only to its top-1 topic hub (assuming all \(T\) topics are non-empty), \(G_{\mathrm{bipartite}}\) decomposes into \(T\) disconnected star subgraphs \(S_1 \sqcup \dots \sqcup S_T\). Therefore, \(\lambda_1 = \lambda_2 = \dots = \lambda_T = 0\), and a random walker starting in topic star \(S_1\) has zero probability of ever visiting \(S_2\).
2. Restoring Global Connectivity (\(\dim\ker(\mathcal{L}) = 1, \lambda_2 > 0\)): We augment the graph with two edge families: multi-topic bridge edges (\(E_{DT}\)) connecting documents to up to \(M > 1\) topics above cosine threshold \(\tau\), and local semantic \(k\)-NN edges (\(E_{DD}\)) connecting each document to its \(k_{\mathrm{NN}}\) nearest neighbors with temperature-sharpened cosine weights \(\cos(\mathbf{e}_i, \mathbf{e}_j)^\beta\).
3. The Exact Mathematical Condition: Define the \(T\)-vertex meta-graph \(H_T\) where two topic stars \((S_m, S_{m'})\) are linked whenever at least one document in \(S_m\) has a bridge edge to \(t_{m'}\) or a \(k\)-NN edge to a document in \(S_{m'}\). Whenever \(H_T\) is connected, the full multi-relational graph forms a single connected component (\(\dim\ker(\mathcal{L}) = 1, \lambda_2(\mathcal{L}) > 0\)). Furthermore, local document-document triangles in \(E_{DD}\) create odd cycles (\(3\)-cycles), making the random walk both irreducible and aperiodic.

3 Step 2: Spherical Modality Fusion (TGSF) and Multi-Objective Trade-offs

Once our connected graph produces informative random-walk node embeddings \(\mathbf{g}_i \in \mathbb{R}^{d_g}\) alongside pretrained text embeddings \(\mathbf{e}_i \in \mathbb{R}^{d_e}\), how should we combine them? If we simply concatenate raw vectors, whichever modality has larger Euclidean variance will dominate \(k\)-means clustering.

Topic-Graph Spherical Fusion (TGSF) projects both representations onto their respective unit hyperspheres first (\(\tilde{\mathbf{e}}_i = \mathbf{e}_i / \|\mathbf{e}_i\|_2\) and \(\tilde{\mathbf{g}}_i = \mathbf{g}_i / \|\mathbf{g}_i\|_2\)) and fuses them via a convex weight \(\alpha \in (0, 1)\):

\[\mathbf{z}_i(\alpha) = \mathrm{Normalize}\!\left(\left[\sqrt{\alpha}\,\tilde{\mathbf{e}}_i \;;\; \sqrt{1-\alpha}\,\tilde{\mathbf{g}}_i\right]\right) \in \mathbb{S}^{d_e + d_g - 1}.\]

Because the fused vector lies on the unit sphere, dot products equal cosine similarities:

\[\langle \mathbf{z}_i(\alpha), \mathbf{z}_j(\alpha) \rangle = \alpha \cos(\mathbf{e}_i, \mathbf{e}_j) + (1 - \alpha) \cos(\mathbf{g}_i, \mathbf{g}_j).\]

Tuning the graph and fusion hyperparameters \((\alpha, M, k_{\mathrm{NN}}, \beta, \gamma)\) reveals a classic Pareto frontier between geometric cluster compactness (Cosine Silhouette) and human-interpretable topic coherence (\(C_V\)).

Graph / Fusion Concept	Spectral / Geometric Property	Practical Consequence
Single-Topic Bipartite Graph (\(M=1, k_{\mathrm{NN}}=0\))	\(\dim\ker(\mathcal{L}) = T > 1\) (\(\lambda_1 = \dots = \lambda_T = 0\))	Decomposes into \(T\) isolated stars; random walks cannot cross topic boundaries
Multi-Relational Topic-\(k\)-NN Graph (\(M>1, k_{\mathrm{NN}}>0\))	\(\dim\ker(\mathcal{L}) = 1\) and Fiedler \(\lambda_2(\mathcal{L}) > 0\) when \(H_T\) connected	Irreducible & aperiodic random walks encode boundary documents and cross-topic proximity
Spherical Modality Fusion \(\mathbf{z}_i(\alpha)\)	\(\langle \mathbf{z}_i, \mathbf{z}_j \rangle = \alpha \cos(\mathbf{e}_i, \mathbf{e}_j) + (1-\alpha)\cos(\mathbf{g}_i, \mathbf{g}_j)\)	Prevents norm dominance and balances semantic similarity with graph topology

4 Exploring Further: Research Directions

Research Track	Core Question to Investigate	Tools & Methods
1. Fiedler Eigenvalue & Mixing Time	How quickly does the algebraic connectivity \(\lambda_2(\mathcal{L})\) grow as we add \(k\)-NN edges, and how does it control random-walk mixing time?	scipy.sparse.linalg, Spectral Graph Theory, Markov Chains
2. Spectral Graph Sparsification	Can we prune \(50\%\) of the \(k\)-NN edges using effective resistance while keeping the graph connected and preserving cluster quality?	Graph Laplacians, Effective Resistance Sampling
3. Directional Statistics on the Sphere	How does fitting von Mises-Fisher (vMF) probability distributions on \(\mathbb{S}^{d-1}\) compare to spherical \(k\)-means when cluster sizes are imbalanced?	Directional Statistics, Expectation-Maximization (EM)