Research-Stack/6-Documentation/docs/fiedler_non_identifiability.md

Fiedler Non-Identifiability Under k-Hop Projection

Setup

Let G = (V,E) be a graph, L its Laplacian, and v_2 the Fiedler vector (second eigenvector of L). Define the Fiedler sign \phi(x) = \operatorname{sign}(v_2(x)).

Define a $k$-hop sampling operator \mathcal{P}_k : G \to \tilde{G}_k that:

• samples seeds uniformly from V,
• expands each seed by k hops of neighborhood closure,
• induces the subgraph on the resulting node set (edges preserved iff both endpoints are sampled).

\mathcal{P}_k is not spectrum-preserving: it applies a local density filter to the eigenspace before eigenvalue decomposition.

Empirical Finding (cit-HepPh, k=2)

On the 30,985-node 2-hop induced subgraph of cit-HepPh (sampled from 34,546 nodes, 421,578 edges):

• \phi is constant on 94.62% of computed nodes
• \operatorname{Var}(\phi) \approx 0.0509 (essentially collapsed)
• PR-kNN recovers \phi at 94.40% accuracy — equal to the trivial majority predictor (94.56%)
• The minority class (B, 5.38%) has 99.7% PR-kNN error: the feature geometry contains no separable decision boundary for it
• \lambda_2(\tilde{L}_2) \approx 0.20, well-separated from \lambda_1 \approx 0, but the eigenvector aligns with a local density mode, not a global partition

Non-Identifiability Theorem

The Fiedler sign \phi is non-identifiable under \mathcal{P}_k when three conditions hold simultaneously:

Condition A — Boundary dilution

P_{\mathcal{P}_k}(x \in \partial C) \ll P(x \in C)

Boundary nodes (where \phi changes sign) are under-sampled because they occupy bridge positions with lower $k$-hop closure probability. A bridge node has O(1) neighbors in each community, so its $k$-hop expansion captures only one side of the partition.

Condition B — Degree-conditioned closure

\mathbb{E}[d(x) \mid x \in \tilde{G}_k] \not\approx \mathbb{E}[d(x)]

The sampled subgraph over-represents high-degree hubs whose neighborhoods are dense. Low-degree bridges are systematically excluded. Since degree correlates with community core membership, the sampling distribution is biased toward the dominant community's interior.

Condition C — Spectral gap collapse under restriction

\lambda_2(\tilde{L}_k) \ll \lambda_2(L)

or equivalently the second eigenvector of \tilde{L}_k aligns with the constant vector: the restricted Laplacian's second mode describes local density variation, not global partition structure. Operationally:

\langle \tilde{v}_2, \mathbf{1} \rangle \approx |\tilde{v}_2|

Theorem (informal)

If (A) boundary dilution and (B) degree-conditioned closure both hold, then \tilde{L}_k almost surely admits a Fiedler vector whose sign structure converges to a constant on the sampled support:

\tilde{v}_2(x) \approx c \quad \forall x \in \tilde{G}_k

and therefore \phi is unrecoverable from \tilde{G}_k:

\phi \not\approx \operatorname{sign}(\tilde{v}_2)

Proof sketch. Under (A), the $k$-hop subgraph contains predominantly interior nodes of the dominant community. Under (B), the spectral mass is concentrated in high-degree regions. The Cheeger inequality gives:

\lambda_2(\tilde{L}_k) \leq 2h(\tilde{G}_k)

where h is the Cheeger constant. With boundary dilution, h(\tilde{G}_k) approaches the trivial cut (one community empty), driving \lambda_2 toward the conductance of a single cluster's internal expansion rather than the inter-cluster bottleneck. The corresponding eigenvector therefore tracks local density rather than global division. \square

Interpretation

The $k$-hop projection pipeline does not "lose signal" — it enters a regime where the second eigenmode of the induced measure space is no longer the second eigenmode of the original.

Why PR and HITS survive. PageRank and HITS operate on first-order stationary mass flow:

• PR ≈ Perron eigenvector of the transition matrix (stationary distribution)
• HITS ≈ leading singular vectors of the adjacency matrix

These are stable under \mathcal{P}_k because they depend on aggregate mass flow through the $k$-hop subgraph, which approximates the global stationary distribution under ergodic assumptions. The Fiedler vector (\lambda_2) is a second-order property describing difference between communities, and collapses when boundary structure is suppressed.

Regime Classification

Regime	Fiedler behavior	Detection
(1) True spectral	Bimodal sign, meaningful partition	\operatorname{Var}(\phi) \approx 0.25
(2) Sampling collapse	Unimodal sign, density mode	\operatorname{Var}(\phi) \ll 0.1
(3) Propagation fake agreement	Majority prior amplified	PR-kNN accuracy ≈ majority baseline

The cit-HepPh cross-validation under \mathcal{P}_2 operates in regimes (2) → (3).

Operational Rule

If on the computed subgraph:

\frac{\max(n_{\text{neg}}, n_{\text{pos}})}{n_{\text{total}}} > 0.90 \quad\text{and}\quad \operatorname{Var}(\phi) < 0.1

flag Fiedler as non-informative under the current sampling regime and exclude from any scoring or purity metric.

References

• von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4), 395–416. — Fiedler vector as global partition signal.
• Chung, F. (1997). Spectral Graph Theory. CBMS Regional Conference Series. — Cheeger inequality and \lambda_2 as conductance.
• This repo: snap_pist_spectral_crossval.py — empirical collapse detection.
• This repo: docs/specs/DP_RRC_RECEIPT_ENCODING_SPEC.md — broader receipt encoding context for spectral observables.