Introduction
A sheaf prescribes how local data glue into global data, and turns the obstruction to gluing into a cohomological invariant [1 , 2 , 3 , 4 ] . On a graph or a simplicial complex, a cellular sheaf [5 , 6 ] attaches a vector space to each cell and a linear map to each incidence, so that the theory becomes finite linear algebra. In this form sheaves have been used for fusing sensor readings [7 ] , for distributed coordination and optimization [8 , 9 ] , and in topological data analysis [10 , 11 , 12 ] , wherever a relation on a graph needs more than a scalar weight. Their central operator is the sheaf Laplacian, which has the foundations of a spectral theory [13 ] and a signal processing theory [14 ] , and which models opinion dynamics, the stalks carrying private opinions and the restriction maps the discourse between agents [15 ] .
In machine learning, where topology has entered from geometric deep learning [16 ] to higher-order domains such as simplicial complexes and hypergraphs [17 , 18 ] , the most notable application of sheaves is the Sheaf Neural Network [19 , 20 ] . A graph neural network diffuses node features along the edges, and fails on heterophilic graphs, where neighbours tend to carry different labels. A Sheaf Neural Network learns a sheaf over the graph and diffuses with its sheaf Laplacian, so that each node transforms its message differently for each neighbour, which restores separation power on heterophilic data. The sheaf is then an object produced by training. The limiting behaviour of sheaf diffusion is described by the Hodge decomposition, which identifies the kernel of the sheaf Laplacian with sheaf cohomology. Three questions that are standard for the graph Laplacian, however, remain open for a general sheaf Laplacian. The first is spectral : a general spectral theory of cellular sheaves is still far from complete [13 , 14 ] , and Cheeger-type bounds, classical for graphs [21 ] , are available only in special cases, notably connection Laplacians [22 , 23 ] . The second is probabilistic : it is not clear how to attach to a sheaf Laplacian a vector-valued random walk, a question left open in [13 ] . The third is combinatorial : cellular sheaves lack an analogue of Forman’s Bochner decomposition [24 ] , a local curvature, cheaper to compute than the spectrum and easier to interpret.
We address the three at once with a Bochner decomposition for cellular sheaves. Forman splits the Hodge Laplacian of a complex into a positive semidefinite term and a diagonal curvature term, using the absolute value of the off-diagonal entries; replacing it by the matrix absolute value ∣ A ∣ : = A A T |A| := \sqrt{AA^{\mathsf{T}}} ∣ A ∣ := A A T Bochner matrices the class of Laplacians the first term belongs to. It extends the connection Laplacians, the matrix-weighted Laplacians [25 , 26 ] and the weighted signed graphs [27 ] : a Bochner matrix is an anisotropic connection Laplacian, in which a positive semidefinite matrix replaces the scalar weight of an edge. We show that its kernel admits the same holonomy characterization known for connection Laplacians.
We then prove Cheeger inequalities for Bochner matrices, extending those of Bandeira, Singer and Spielman for connection Laplacians [22 ] : they relate the low eigenvalues of the normalized Bochner Laplacian to three frustration constants, the residuals of synchronization over S d − 1 S^{d-1} S d − 1 O ( d ) O(d) O ( d ) random walk on V × S d − 1 V \times S^{d-1} V × S d − 1 generalized Gremban expansion , each node being lifted to a whole sphere instead of two copies, and in the isotropic case it recovers the vector-valued walk of the connection Laplacian [23 ] . These two results answer the spectral and the probabilistic question.
The Forman term answers the combinatorial one. It is block diagonal, each block computed from the restriction maps at a single node. On 1-cells we call it the sheaf Forman Ricci curvature , and we prove a Bochner theorem for cellular sheaves: under nonnegative curvature, the first sheaf cohomology of a compact connected combinatorial n n n d d d n d nd n d n ≤ 3 n \le3 n ≤ 3 d ⋅ D ( M ) d \cdot D(M) d ⋅ D ( M ) D ( M ) D(M) D ( M ) [28 ] : sheaf diffusion can be seen as a reaction-diffusion process, the Bochner term diffusive and the Forman term reactive. On a graph this is an opinion dynamics model, in which the Bochner term drives the agents towards a common conviction , the norm a stalk carries, and the Forman block measures how loudly an agent speaks relative to its neighbours, its relative volume .
We then return to Sheaf Neural Networks. The available theory describes what they can represent: convergence of sheaf diffusion, and a universal approximation theorem by which a network can learn any sheaf on a graph. What is missing is a description of what the learning mechanism does : which region of the sheaf space a training pipeline reaches, and whether different pipelines are biased towards different regions. From the decomposition we derive two diagnostics of neural sheaf diffusion, one per term: the conviction and the Forman profile . The conviction is an operational score of node importance: on a frozen trained network, removing the highest-conviction nodes is the most damaging intervention at every budget and in every perturbation mode, while removing the lowest-conviction ones costs less than removing arbitrary nodes of the same graph. The Forman profile tracks, layer by layer, how a learning mechanism navigates the sheaf space, and each of the three mechanisms we test leaves its own signature: normalized general sheaf learning converges to local alignment with the normalized graph Laplacian, unnormalized learning aligns with neither reference, and joint diffusion [29 ] reverses the role of normalization. Evaluated without normalization, the profile of the same learnt maps stays far from that of the identity sheaf, so we read the alignment as an inductive bias towards one region of the sheaf space.
Related work
Sheaves on directed and undirected graphs have recently been given a differential calculus [30 ] , formalized for the Grothendieck topology and developed in the spirit of noncommutative geometry, where a Bochner Laplacian is defined as ∇ ∗ ∇ \nabla^{\ast}\nabla ∇ ∗ ∇ ∇ \nabla ∇ [31 ] , building restriction maps as a function of the Forman curvature of the edges and using the resulting sheaf Laplacian for community detection; the direction there is the opposite of ours: we define a curvature from a cellular sheaf, while they use a graph curvature to define a particular sheaf. Finally, dynamical processes on connection Laplacians have received considerable attention lately [32 , 33 , 34 , 35 ] , with a focus on Kuramoto models, Turing patterns and network coherence, and our framework opens the possibility of carrying those results to the anisotropic setting while still controlling the balance of the system through holonomy. We note that these works use the term “matrix-weighted graph” to mean a connection Laplacian, whereas we reserve it for the sense of [25 ] .
Curvature has also been studied on connection Laplacians independently of sheaves. Liu, Münch and Peyerimhoff [36 ] define a Bakry–Émery curvature for connection graphs and derive higher-order Buser inequalities from it, with Cheeger constants mixing the expansion of the underlying graph with the frustration index of the signature. This notion of curvature was moreover reformulated in [37 ] . Such curvatures are available on a connection Laplacian because it generates a random walk, with scalar transition rates. For a general sheaf Laplacian it is not clear how to obtain one, and that failure is exactly the Forman term, which measures how far the diagonal is from the sum of the magnitudes of the off-diagonal blocks. Sheaf Laplacians with vanishing Forman term are the Bochner matrices, and these, as we show in this work, do carry a random walk, so we believe a Bakry–Émery curvature can be built for them, and we leave this to future work.
Sheaf Neural Networks were introduced by Hansen and Gebhart [19 ] on a sheaf fixed in advance; Bodnar et al. [20 ] learn the sheaf from the data, and prove that a network can learn any sheaf on a graph. Several works have since studied the parametrization of the restriction maps, through connection Laplacians aligned with the data manifold [38 ] , equivariant transport [39 ] , or a diffusion process on the restriction maps themselves, run jointly with the one on the node features [29 ] . Others have extended the architecture, to features on SPD manifolds [40 ] and to message diffusion over flat vector bundles [41 ] . The sheaf formalism has also been used to generalize attention in graph neural networks [42 ] . On the theoretical side, oversmoothing has been related to a degeneration of the representation underlying the learnt sheaf [43 ] . On the other hand, Hernandez Caralt et al. [44 ] showed empirically that identity restriction maps perform similarly to learnt ones, which questions to what extent learning the sheaf matters. Finally, crucial features of graph neural networks such as over-squashing have been related to the curvature of the graph [45 ] . While we build a notion of Forman curvature for cellular sheaves, we do not pursue this direction, which would involve the Forman term of the sheaf Hodge Laplacian in degree 1; in § 6.4 we compute instead the Forman term of the graph sheaf Laplacian, in degree 0, which to avoid ambiguity we call Forman term and not curvature. Studying over-squashing in Sheaf Neural Networks from this curvature perspective is left for future work. We refer to § 6.2 and § 6.4 for a further discussion.
Organization of the paper
The paper is organized as follows. § 2 fixes notation and recalls cellular sheaves, signed graphs and Forman’s decomposition. § 3 introduces the Bochner decomposition for sheaf Laplacians, and § 4 and § 5 study its two terms in turn: within the first, § 4.2 proves the Cheeger inequalities and § 4.3 attaches the random walk. § 6 develops the dynamical reading and the applications to Sheaf Neural Networks. We conclude in § 7 . Proofs deferred from the body are collected in Appendix § 10 , each statement being restated before its proof, further properties of Bochner matrices are in Appendix § 12 , and the experimental protocols with the additional material are in Appendices § 13 and § 14 .
Background
This section fixes notation for cellular sheaves and their Laplacians, and recalls the facts on signed graphs and on Forman’s Bochner decomposition that the paper builds on.
Cellular sheaves on simplicial complexes
We follow [46 , 47 ] for simplicial cochain complexes and [5 , 6 ] for cellular sheaves. Let X X X X k X_k X k k k k n : = ∣ X 0 ∣ n := |X_0| n := ∣ X 0 ∣ σ ≺ τ \sigma\prec\tau σ ≺ τ X X X ϵ σ τ ∈ { − 1 , 0 , + 1 } \epsilon_{\sigma\tau} \in\{-1,0,+1\} ϵ σ τ ∈ { − 1 , 0 , + 1 } σ \sigma σ τ \tau τ
Definition 2.1 (Cellular sheaf). A cellular sheaf F \mathcal{F} F X X X σ \sigma σ F ( σ ) \mathcal{F}(\sigma) F ( σ ) σ ⊴ τ \sigma\trianglelefteq\tau σ ⊴ τ F σ ⊴ τ : F ( σ ) → F ( τ ) \mathcal{F}_{\sigma\trianglelefteq\tau}:\mathcal{F}(\sigma)\to\mathcal{F}(\tau) F σ ⊴ τ : F ( σ ) → F ( τ ) F σ ⊴ σ = id F ( σ ) \mathcal{F}_{\sigma\trianglelefteq\sigma}=\operatorname{id}_{\mathcal{F}(\sigma)} F σ ⊴ σ = id F ( σ ) F ρ ⊴ τ = F σ ⊴ τ F ρ ⊴ σ \mathcal{F}_{\rho\trianglelefteq\tau}=\mathcal{F}_{\sigma\trianglelefteq\tau}\mathcal{F}_{\rho\trianglelefteq\sigma} F ρ ⊴ τ = F σ ⊴ τ F ρ ⊴ σ ρ ⊴ σ ⊴ τ \rho\trianglelefteq\sigma\trianglelefteq\tau ρ ⊴ σ ⊴ τ
Equivalently, F \mathcal{F} F [5 ] , and it is determined by the maps attached to faces. Throughout, every stalk has dimension d d d C k ( X ; F ) = ⨁ σ ∈ X k F ( σ ) C^k(X;\mathcal{F})=\bigoplus_{\sigma\in X_k}\mathcal{F}(\sigma) C k ( X ; F ) = ⨁ σ ∈ X k F ( σ ) δ k : C k ( X ; F ) → C k + 1 ( X ; F ) \delta_k:C^k(X;\mathcal{F})\to C^{k+1}(X;\mathcal{F}) δ k : C k ( X ; F ) → C k + 1 ( X ; F )
( δ k c ) τ = ∑ σ ⊴ τ dim σ = k ϵ σ τ F σ ⊴ τ c σ (1) (\delta_k c)_\tau=\sum_{\substack{\sigma\trianglelefteq\tau\\ \dim\sigma=k}}\epsilon_{\sigma\tau}\mathcal{F}_{\sigma\trianglelefteq\tau}c_\sigma \tag*{(1)} ( δ k c ) τ = σ ⊴ τ d i m σ = k ∑ ϵ σ τ F σ ⊴ τ c σ (1) it satisfies δ k + 1 δ k = 0 \delta_{k+1}\delta_k=0 δ k + 1 δ k = 0 H k ( X ; F ) : = ker δ k / im δ k − 1 \mathcal{H}^k(X;\mathcal{F}):=\ker\delta_k/\operatorname{im}\delta_{k-1} H k ( X ; F ) := ker δ k / im δ k − 1 F \mathcal{F} F R \mathbb{R} R X X X C k ( X ; F ) C^k(X;\mathcal{F}) C k ( X ; F ) δ k ∗ \delta_k^* δ k ∗ δ k \delta_k δ k H k F = δ k − 1 δ k − 1 ∗ + δ k ∗ δ k H_k^{\mathcal{F}}=\delta_{k-1}\delta_{k-1}^*+\delta_k^*\delta_k H k F = δ k − 1 δ k − 1 ∗ + δ k ∗ δ k d × d d\times d d × d X k X_k X k ker H k F ≅ H k ( X ; F ) \ker H_k^{\mathcal{F}}\cong\mathcal{H}^k(X;\mathcal{F}) ker H k F ≅ H k ( X ; F ) ∂ : = δ ∗ \partial:=\delta^* ∂ := δ ∗ ∂ ∗ = δ \partial^*=\delta ∂ ∗ = δ k = 0 k=0 k = 0 L F : = H 0 F = δ 0 ∗ δ 0 L_{\mathcal{F}}:=H_0^{\mathcal{F}}=\delta_0^*\delta_0 L F := H 0 F = δ 0 ∗ δ 0 G = ( V , E ) G=(V,E) G = ( V , E ) ( L F ) v v = ∑ e : v ⊴ e F v ⊴ e T F v ⊴ e (L_{\mathcal{F}})_{vv}=\sum_{e:v\trianglelefteq e}\mathcal{F}_{v\trianglelefteq e}^{\mathsf{T}}\mathcal{F}_{v\trianglelefteq e} ( L F ) v v = ∑ e : v ⊴ e F v ⊴ e T F v ⊴ e e = ( v , u ) e=(v,u) e = ( v , u ) ( L F ) v u = − F v ⊴ e T F u ⊴ e (L_{\mathcal{F}})_{vu}=-\mathcal{F}_{v\trianglelefteq e}^{\mathsf{T}}\mathcal{F}_{u\trianglelefteq e} ( L F ) v u = − F v ⊴ e T F u ⊴ e
Two classes of graph sheaf Laplacians recur below. Taking F v ⊴ e = w v u O v ⊴ e \mathcal{F}_{v\trianglelefteq e}=\sqrt{w_{vu}}O_{v\trianglelefteq e} F v ⊴ e = w v u O v ⊴ e O v ⊴ e O_{v\trianglelefteq e} O v ⊴ e w v u > 0 w_{vu}>0 w v u > 0 − w v u W v u T -w_{vu}W_{vu}^{\mathsf{T}} − w v u W v u T W v u T : = O v ⊴ e T O u ⊴ e ∈ O ( d ) W_{vu}^{\mathsf{T}}:=O_{v\trianglelefteq e}^{\mathsf{T}}O_{u\trianglelefteq e}\in O(d) W v u T := O v ⊴ e T O u ⊴ e ∈ O ( d ) connection Laplacians [22 , 23 ] , called bundle sheaves in Sheaf Neural Networks [19 , 20 ] . Taking F v ⊴ e = M v u 1 / 2 \mathcal{F}_{v\trianglelefteq e}=M_{vu}^{1/2} F v ⊴ e = M v u 1/2 M v u ⪰ 0 M_{vu}\succeq0 M v u ⪰ 0 − M v u -M_{vu} − M v u matrix-weighted Laplacians [25 , 26 ] . With D : = blockdiag ( ( L F ) v v ) D:=\operatorname{blockdiag}((L_{\mathcal{F}})_{vv}) D := blockdiag (( L F ) v v ) normalized sheaf Laplacian Δ F : = D − 1 / 2 L F D − 1 / 2 \Delta_{\mathcal{F}}:=D^{-1/2}L_{\mathcal{F}}D^{-1/2} Δ F := D − 1/2 L F D − 1/2 [ 0 , 2 ] [0,2] [ 0 , 2 ] [13 ] . We work with unweighted sheaves: every weighted sheaf Laplacian, and in particular every normalized one, is the Laplacian of some unweighted sheaf [13 ] , a fact Sections 3 and 6.4 use directly.
Signed graphs, balance and holonomy
A signed graph Γ = ( V , E , W ) \Gamma=(V,E,W) Γ = ( V , E , W ) W W W [27 ] . With degrees d v : = ∑ u ∣ w v u ∣ d_v:=\sum_u\lvert w_{vu}\rvert d v := ∑ u ∣ w v u ∣ D : = diag ( d v ) D:=\operatorname{diag}(d_v) D := diag ( d v ) W = W + − W − W=W^+-W^- W = W + − W − L Γ : = D − W = D − W + + W − L_\Gamma:=D-W=D-W^++W^- L Γ := D − W = D − W + + W −
x T L Γ x = ∑ v u ∈ E ∣ w v u ∣ ( x v − sgn ( w v u ) x u ) 2 (2) x^{\mathsf{T}}L_\Gamma x=\sum_{vu\in E}\lvert w_{vu}\rvert\left(x_v-\operatorname{sgn}(w_{vu})x_u\right)^2 \tag*{(2)} x T L Γ x = v u ∈ E ∑ ∣ w v u ∣ ( x v − sgn ( w v u ) x u ) 2 (2) so L Γ ⪰ 0 L_\Gamma\succeq0 L Γ ⪰ 0 [48 ] , controlled by balance. A cycle is positive if it carries an even number of negative edges.
Definition 2.2 (Balance and antibalance). Γ \Gamma Γ
Theorem 2.1 (Structure theorem for balance [49 , 50 ] ). Γ \Gamma Γ V = V 1 ⊔ V 2 V=V_1\sqcup V_2 V = V 1 ⊔ V 2 V 1 V_1 V 1 V 2 V_2 V 2 V 1 V_1 V 1 V 2 V_2 V 2
The partition is visible in the spectrum [49 , 51 , 52 ] . Writing 1 V 1 \mathbb{1}_{V_1} 1 V 1 V 1 V_1 V 1
Theorem 2.2 (Kernel of a signed Laplacian). Let Γ \Gamma Γ Γ \Gamma Γ dim ker L Γ = 1 \dim\ker L_\Gamma=1 dim ker L Γ = 1 1 V 1 − 1 V 2 \mathbb{1}_{V_1}-\mathbb{1}_{V_2} 1 V 1 − 1 V 2
At the other end of the spectrum, the normalized signed Laplacian I − D − 1 / 2 W D − 1 / 2 I-D^{-1/2}WD^{-1/2} I − D − 1/2 W D − 1/2 [ 0 , 2 ] [0,2] [ 0 , 2 ] 2 2 2 Γ \Gamma Γ [53 ] ; a connected non-bipartite signed graph cannot be both balanced and antibalanced, since an odd cycle would be positive and negative at once. When Γ \Gamma Γ [54 , 55 ] . Other quantitative measures of balance have also been proposed, together with related Cheeger inequalities for signed graphs [52 , 56 ] . In the Gremban expansion [57 , 58 , 59 ] each vertex is split into a positive and a negative copy, a walker crossing a negative edge switching copy, so that L Γ L_\Gamma L Γ 2 n 2n 2 n [27 ] .
On a connection Laplacian, balance becomes holonomy. Every walk γ : v 0 → ⋯ → v k \gamma:v_0\to\cdots\to v_k γ : v 0 → ⋯ → v k transport map T γ : = W v k − 1 v k ⋯ W v 0 v 1 ∈ O ( d ) T_\gamma:=W_{v_{k-1}v_k}\cdots W_{v_0v_1}\in O(d) T γ := W v k − 1 v k ⋯ W v 0 v 1 ∈ O ( d ) trivial holonomy when T γ = I T_\gamma=I T γ = I d d d [20 , 22 , 23 ] . For d = 1 d = 1 d = 1 T γ T_\gamma T γ γ \gamma γ Theorem 2.2 .
Forman’s Bochner decomposition
On a Riemannian manifold the Bochner–Weitzenböck formula splits the Hodge Laplacian on 1-forms as Δ = ∇ ∗ ∇ + Ric \Delta= \nabla^* \nabla+ \operatorname{Ric} Δ = ∇ ∗ ∇ + Ric [60 ] , and the Bochner theorem follows from it: under nonnegative Ricci curvature every harmonic 1-form is parallel, so the first cohomology has dimension at most n n n [24 ] , resting on a splitting that applies to any symmetric matrix.
Definition 2.3 (Bochner and curvature terms). Let A A A n × n n \times n n × n B B B B i j = A i j B_{ij} = A_{ij} B ij = A ij i ≠ j i \ne j i = j B i i = ∑ k ≠ i ∣ A i k ∣ B_{ii} = \sum_{k \ne i} |A_{ik}| B ii = ∑ k = i ∣ A ik ∣ F : = A − B F := A - B F := A − B F i i = A i i − ∑ k ≠ i ∣ A i k ∣ F_{ii} = A_{ii} - \sum_{k \ne i} |A_{ik}| F ii = A ii − ∑ k = i ∣ A ik ∣
The matrix B B B F = 0 F = 0 F = 0
When A A A w σ > 0 w_\sigma> 0 w σ > 0 w σ w_\sigma w σ [24 ] :
F k ( σ ) = w σ [ ∑ σ ⊂ τ ( k + 1 ) w σ w τ + ∑ γ ( k − 1 ) ⊂ σ w γ w σ − ∑ σ ′ ≠ σ ∣ ∑ τ ( k + 1 ) ϵ σ τ ϵ σ ′ τ w σ w σ ′ w τ \mathcal{F}_k(\sigma) = w_\sigma\left[ \sum_{\sigma\subset\tau^{(k+1)}} \frac{w_\sigma}{w_\tau} + \sum_{\gamma^{(k-1)} \subset\sigma} \frac{w_\gamma}{w_\sigma} - \sum_{\sigma' \ne\sigma} \left| \sum_{\tau^{(k+1)}} \epsilon_{\sigma\tau}\epsilon_{\sigma'\tau}\frac{\sqrt{w_\sigma w_{\sigma'}}}{w_\tau} \right. \right. F k ( σ ) = w σ σ ⊂ τ ( k + 1 ) ∑ w τ w σ + γ ( k − 1 ) ⊂ σ ∑ w σ w γ − σ ′ = σ ∑ τ ( k + 1 ) ∑ ϵ σ τ ϵ σ ′ τ w τ w σ w σ ′ + ∑ γ ( k − 1 ) ϵ γ σ ϵ γ σ ′ w γ w σ w σ ′ ∣ ] . (3) \left. \left. + \sum_{\gamma^{(k-1)}} \epsilon_{\gamma\sigma}\epsilon_{\gamma\sigma'}\frac{w_\gamma}{\sqrt{w_\sigma w_{\sigma'}}} \right| \right]. \tag*{(3)} + γ ( k − 1 ) ∑ ϵ γ σ ϵ γ σ ′ w σ w σ ′ w γ . (3) the bracket being exactly the Forman term ( F k ) σ σ (F_k)_{\sigma\sigma} ( F k ) σ σ F k ( σ ) = w σ ⋅ ( F k ) σ σ \mathcal{F}_k(\sigma) = w_\sigma\cdot(F_k)_{\sigma\sigma} F k ( σ ) = w σ ⋅ ( F k ) σ σ § 2.1 ; therefore, we identify the curvature with the term and write F k F_k F k
With unit weights, the Forman term is a local count. Two distinct k k k σ ⌢ σ ′ \sigma\frown\sigma' σ ⌢ σ ′ σ ⌣ σ ′ \sigma\smile\sigma' σ ⌣ σ ′ parallel if exactly one of the two holds, and transverse if both do, in which case the contributions through the face and through the coface cancel. With deg u \deg_u deg u deg l \deg_l deg l
F k ( σ ) = deg u ( σ ) + deg l ( σ ) − # { parallel neighbours of σ } , (4) F_k(\sigma) = \deg_u(\sigma) + \deg_l(\sigma) - \#\{\text{parallel neighbours of }\sigma\}, \tag*{(4)} F k ( σ ) = deg u ( σ ) + deg l ( σ ) − # { parallel neighbours of σ } , (4) which on an edge, where deg l ( e ) = 2 \deg_l(e) = 2 deg l ( e ) = 2 Forman–Ricci curvature :
Ric ( e ) = # { triangles containing e } + 2 − # { parallel neighbours of e } . (5) \operatorname{Ric}(e) = \#\{\text{triangles containing }e\} + 2 - \#\{\text{parallel neighbours of }e\}. \tag*{(5)} Ric ( e ) = # { triangles containing e } + 2 − # { parallel neighbours of e } . (5) At k = 0 k = 0 k = 0 F 0 = 0 F_0 = 0 F 0 = 0
Forman’s theorem holds on quasiconvex complexes. A CW complex is regular when the characteristic map of every cell is a homeomorphism onto its image, so that the closure of each cell is a closed ball; incidence numbers then lie in { 0 , ± 1 } \{0, \pm1\} { 0 , ± 1 } p p p ( p − 1 ) (p - 1) ( p − 1 ) ( p + 1 ) (p + 1) ( p + 1 ) ( p + 1 ) (p + 1) ( p + 1 ) p p p β \beta β β ˉ \bar{\beta} β ˉ n n n v v v { σ : v ∉ σ , σ ∪ { v } ∈ X } \{\sigma: v \notin\sigma, \sigma\cup\{v\} \in X\} { σ : v ∈ / σ , σ ∪ { v } ∈ X } ( n − 1 ) (n - 1) ( n − 1 )
Theorem 2.3 (Forman’s Bochner theorem). Let M M M n n n n ≤ 3 n \le3 n ≤ 3 Ric ( e ) ≥ 0 \operatorname{Ric}(e) \ge0 Ric ( e ) ≥ 0 e e e dim H 1 ( M ) ≤ n \dim H^1(M) \le n dim H 1 ( M ) ≤ n
The Bochner Decomposition of a Sheaf Laplacian
For sheaf Laplacians with d d d H i j H_{ij} H ij d × d d \times d d × d matrix absolute value ∣ A ∣ : = A A T |A| := \sqrt{AA^{\mathsf{T}}} ∣ A ∣ := A A T d d d
Definition 3.1 (Block Bochner decomposition). Let H H H symmetric block matrix in R n d , n d \mathbb{R}^{nd,nd} R n d , n d with d × d d \times d d × d blocks H i j H_{ij} H ij
B i j = { H i j i ≠ j , ∑ k ≠ i ∣ H i j ∣ i = j , F i j = { 0 i ≠ j , H i j − ∑ k ≠ i ∣ H i k ∣ i = j . (6) \begin{aligned}
B_{ij} &=
\begin{cases}
H_{ij} & i \ne j,\\
\sum_{k\ne i}|H_{ij}| & i = j,
\end{cases}
&
F_{ij} &=
\begin{cases}
0 & i \ne j,\\
H_{ij}-\sum_{k\ne i}|H_{ik}| & i = j.
\end{cases} \tag*{(6)}
\end{aligned} B ij = { H ij ∑ k = i ∣ H ij ∣ i = j , i = j , F ij = { 0 H ij − ∑ k = i ∣ H ik ∣ i = j , i = j . (6) For this to define a Laplacian, B B B
Definition 3.2 (Block diagonally dominant matrix). A block matrix C ∈ R n d , n d C \in\mathbb{R}^{nd,nd} C ∈ R n d , n d C i j C_{ij} C ij d d d C i i ⪰ ∑ j ≠ i ∣ C i j ∣ C_{ii} \succeq\sum_{j\ne i}|C_{ij}| C ii ⪰ ∑ j = i ∣ C ij ∣ i i i
Proposition 3.1. Every symmetric, block diagonally dominant matrix is positive semidefinite.
Proof. Fix i ≠ j i \ne j i = j C i j = U Σ V T C_{ij} = U\Sigma V^{\mathsf{T}} C ij = U Σ V T ∣ C i j ∣ = U Σ U T |C_{ij}| = U\Sigma U^{\mathsf{T}} ∣ C ij ∣ = U Σ U T ∣ C i j T ∣ = V Σ V T |C_{ij}^{\mathsf{T}}| = V\Sigma V^{\mathsf{T}} ∣ C ij T ∣ = V Σ V T
( ∣ C i j ∣ C i j C i j T ∣ C i j T ∣ ) = ( U V ) Σ ( U T V T ) ⪰ 0 , \begin{pmatrix}
|C_{ij}| & C_{ij}\\
C_{ij}^{\mathsf{T}} & |C_{ij}^{\mathsf{T}}|
\end{pmatrix}
=
\begin{pmatrix}
U\\
V
\end{pmatrix}
\Sigma
\begin{pmatrix}
U^{\mathsf{T}} & V^{\mathsf{T}}
\end{pmatrix}
\succeq0, ( ∣ C ij ∣ C ij T C ij ∣ C ij T ∣ ) = ( U V ) Σ ( U T V T ) ⪰ 0 , and evaluating its quadratic form at ( x i T , x j T ) T (x_i^{\mathsf{T}},x_j^{\mathsf{T}})^{\mathsf{T}} ( x i T , x j T ) T
x i T C i j x j + x j T C i j T x i ≥ − ( x i T ∣ C i j ∣ x i + x j T ∣ C i j T ∣ x j ) . (7) x_i^{\mathsf{T}}C_{ij}x_j+x_j^{\mathsf{T}}C_{ij}^{\mathsf{T}}x_i
\ge-\left(x_i^{\mathsf{T}}|C_{ij}|x_i+x_j^{\mathsf{T}}|C_{ij}^{\mathsf{T}}|x_j\right). \tag*{(7)} x i T C ij x j + x j T C ij T x i ≥ − ( x i T ∣ C ij ∣ x i + x j T ∣ C ij T ∣ x j ) . (7) Summing this bound over every off-diagonal pair:
x T C x = ∑ i x i T C i i x i + ∑ i ≠ j x i T C i j x j ≥ ∑ i x i T ( C i i − ∑ j ≠ i ∣ C i j ∣ ) x i ≥ 0. (8) x^{\mathsf{T}}Cx
=
\sum_i x_i^{\mathsf{T}}C_{ii}x_i
+
\sum_{i\ne j}x_i^{\mathsf{T}}C_{ij}x_j
\ge
\sum_i x_i^{\mathsf{T}}
\left(C_{ii}-\sum_{j\ne i}|C_{ij}|\right)x_i
\ge0. \tag*{(8)} x T C x = i ∑ x i T C ii x i + i = j ∑ x i T C ij x j ≥ i ∑ x i T C ii − j = i ∑ ∣ C ij ∣ x i ≥ 0. (8) By the proposition above, B ⪰ 0 B \succeq0 B ⪰ 0 B = C T C B = C^{\mathsf{T}}C B = C T C C C C B k = ∇ ∗ ∇ B_k = \nabla^{*}\nabla B k = ∇ ∗ ∇
Graph and Hodge sheaf Laplacians. Applying Definition 3.1 to the Hodge sheaf Laplacian H k F = δ k − 1 δ k − 1 ∗ + δ k ∗ δ k H_k^F = \delta_{k-1}\delta_{k-1}^{*}+\delta_k^{*}\delta_k H k F = δ k − 1 δ k − 1 ∗ + δ k ∗ δ k ( B k ) σ σ ′ = ( H k ) σ σ ′ (B_k)_{\sigma\sigma'}=(H_k)_{\sigma\sigma'} ( B k ) σ σ ′ = ( H k ) σ σ ′ ( F k ) σ σ = ( H k ) σ σ − ∑ σ ′ ≠ σ ∣ ( H k ) σ σ ′ ∣ (F_k)_{\sigma\sigma}=(H_k)_{\sigma\sigma}-\sum_{\sigma'\ne\sigma}|(H_k)_{\sigma\sigma'}| ( F k ) σ σ = ( H k ) σ σ − ∑ σ ′ = σ ∣ ( H k ) σ σ ′ ∣ H k F = B k F + F k F H_k^F=B_k^F+F_k^F H k F = B k F + F k F L F = B F + F F L_F=B_F+F_F L F = B F + F F k = 0 k=0 k = 0 Ric F : = F 1 F \operatorname{Ric}_F:=F_1^F Ric F := F 1 F e e e
Ric F ( e ) = ∑ v : v ◃ e F v ◃ e T F v ◃ e + ∑ t : e ◃ t F e ◃ t T F e ◃ t − ∑ e ~ ≠ e ∣ ∑ v ϵ v e ϵ v e ~ F v ◃ e T F v ◃ e ~ + ∑ t ~ ϵ e t ϵ e ~ t ~ F e ◃ t T F e ~ ◃ t ~ ∣ . (9) \operatorname{Ric}_F(e)
=
\sum_{v:v\triangleleft e}F_{v\triangleleft e}^{\mathsf{T}}F_{v\triangleleft e}
+
\sum_{t:e\triangleleft t}F_{e\triangleleft t}^{\mathsf{T}}F_{e\triangleleft t}
-
\sum_{\tilde e\ne e}
\left|
\sum_{v}\epsilon_{ve}\epsilon_{v\tilde e}F_{v\triangleleft e}^{\mathsf{T}}F_{v\triangleleft\tilde e}
+
\sum_{\tilde t}\epsilon_{et}\epsilon_{\tilde e\tilde t}F_{e\triangleleft t}^{\mathsf{T}}F_{\tilde e\triangleleft\tilde t}
\right|. \tag*{(9)} Ric F ( e ) = v : v ◃ e ∑ F v ◃ e T F v ◃ e + t : e ◃ t ∑ F e ◃ t T F e ◃ t − e ~ = e ∑ v ∑ ϵ v e ϵ v e ~ F v ◃ e T F v ◃ e ~ + t ~ ∑ ϵ e t ϵ e ~ t ~ F e ◃ t T F e ~ ◃ t ~ . (9) ϵ α β ∈ { − 1 , 0 , + 1 } \epsilon_{\alpha\beta}\in\{-1,0,+1\} ϵ α β ∈ { − 1 , 0 , + 1 } k k k k k k k = 0 k=0 k = 0
( F F ) v v = ∑ e : v ◃ e ( F v ◃ e T F v ◃ e − ∑ v ~ ◃ e F v ◃ e T F v ~ ◃ e ) . (10) (F_F)_{vv}
=
\sum_{e:v\triangleleft e}
\left(
F_{v\triangleleft e}^{\mathsf{T}}F_{v\triangleleft e}
-
\sum_{\tilde v\triangleleft e}
F_{v\triangleleft e}^{\mathsf{T}}F_{\tilde v\triangleleft e}
\right). \tag*{(10)} ( F F ) v v = e : v ◃ e ∑ ( F v ◃ e T F v ◃ e − v ~ ◃ e ∑ F v ◃ e T F v ~ ◃ e ) . (10) with u u u e e e k = 0 k=0 k = 0 w σ w_\sigma w σ [13 ] , every weighted sheaf Laplacian is the Laplacian of some unweighted sheaf, so no generality is lost by working unweighted, and the Forman term of the decomposition is the genuine curvature itself, with no rescaling. For a higher-order connection Laplacian, with F v ◃ e F v ◃ e ~ T = F e ◃ t T F e ~ ◃ t F_{v\triangleleft e}F_{v\triangleleft\tilde e}^{\mathsf{T}}=F_{e\triangleleft t}^{\mathsf{T}}F_{\tilde e\triangleleft t} F v ◃ e F v ◃ e ~ T = F e ◃ t T F e ~ ◃ t e , e ~ e,\tilde e e , e ~ (9) collapses to ( F F ) e e = χ ( e ) ⋅ I (F_F)_{ee}=\chi(e)\cdot I ( F F ) ee = χ ( e ) ⋅ I χ ( e ) \chi(e) χ ( e )
Bochner Matrices
The Bochner term of a sheaf Laplacian belongs to a class of block matrices that is worth studying on its own, as we show it contains Connection Laplacians, Matrix-Weighted Laplacians, and signed graphs. This section develops that class: its kernel and the top of its spectrum here, its Cheeger inequalities, and the random walk it carries.
Polar factors, the kernel and holonomy
We call a symmetric block matrix produced by Definition 3.1 a Bochner matrix:
B = ( ⋱ ⋮ ⋮ ⋯ ∑ w ∼ v ∣ B b v ∣ ⋯ − B v u ⋯ ⋮ ⋱ ⋮ ⋯ − B v u ⊤ ⋯ ∑ w ∼ u ∣ B u w ∣ ⋯ ⋮ ⋮ ⋱ ) (11) B =
\begin{pmatrix}
\ddots& \vdots& \vdots\\
\cdots& \sum_{w\sim v}|B_{bv}| & \cdots& -B_{vu} & \cdots\\
\vdots& \ddots& \vdots\\
\cdots& -B_{vu}^{\top} & \cdots& \sum_{w\sim u}|B_{uw}| & \cdots\\
\vdots& \vdots& \ddots
\end{pmatrix} \tag*{(11)} B = ⋱ ⋯ ⋮ ⋯ ⋮ ⋮ ∑ w ∼ v ∣ B b v ∣ ⋱ − B v u ⊤ ⋮ ⋮ ⋯ ⋮ ⋯ ⋱ − B v u ∑ w ∼ u ∣ B u w ∣ ⋯ ⋯ (11) supported exactly on the edges of G G G block symmetry , B u v = B v u ⊤ B_{uv}=B_{vu}^{\top} B uv = B v u ⊤ invertibility , every B v u B_{vu} B v u connectivity : the graph on v ∼ u ⟺ B v u ≠ 0 v\sim u \Longleftrightarrow B_{vu}\ne0 v ∼ u ⟺ B v u = 0
Writing B v u = U v u Σ v u V v u ⊤ B_{vu}=U_{vu}\Sigma_{vu}V_{vu}^{\top} B v u = U v u Σ v u V v u ⊤ B v ⊴ e : = Σ v u 1 / 2 U v u ⊤ \mathcal{B}_{v\trianglelefteq e}:=\Sigma_{vu}^{1/2}U_{vu}^{\top} B v ⊴ e := Σ v u 1/2 U v u ⊤ B u ⊴ e : = Σ v u 1 / 2 V v u ⊤ \mathcal{B}_{u\trianglelefteq e}:=\Sigma_{vu}^{1/2}V_{vu}^{\top} B u ⊴ e := Σ v u 1/2 V v u ⊤ e = ( v , u ) e=(v,u) e = ( v , u ) B \mathcal{B} B B B B k = 0 k=0 k = 0 L F = L B + F F L_F=L_B+F_F L F = L B + F F H k F = B k F + F k F H_k^F=B_k^F+F_k^F H k F = B k F + F k F B k F B_k^F B k F k k k k k k
Writing B v u = U v u Σ v u V v u ⊤ = U v u Σ v u U v u ⊤ U v u V v u ⊤ B_{vu}=U_{vu}\Sigma_{vu}V_{vu}^{\top}=U_{vu}\Sigma_{vu}U_{vu}^{\top}U_{vu}V_{vu}^{\top} B v u = U v u Σ v u V v u ⊤ = U v u Σ v u U v u ⊤ U v u V v u ⊤ B v u = M v u W v u ⊤ B_{vu}=M_{vu}W_{vu}^{\top} B v u = M v u W v u ⊤ M v u : = ∣ B v u ∣ = U v u Σ v u U v u ⊤ ⪰ 0 M_{vu}:=|B_{vu}|=U_{vu}\Sigma_{vu}U_{vu}^{\top}\succeq0 M v u := ∣ B v u ∣ = U v u Σ v u U v u ⊤ ⪰ 0 W v u : = V v u U v u ⊤ ∈ O ( d ) W_{vu}:=V_{vu}U_{vu}^{\top}\in O(d) W v u := V v u U v u ⊤ ∈ O ( d ) B u v = B v u ⊤ B_{uv}=B_{vu}^{\top} B uv = B v u ⊤ W u v = W v u ⊤ W_{uv}=W_{vu}^{\top} W uv = W v u ⊤ W v u M v u W v u ⊤ = M u v W_{vu}M_{vu}W_{vu}^{\top}=M_{uv} W v u M v u W v u ⊤ = M uv ∥ z ∥ M 2 : = z ⊤ M z \|z\|_M^2:=z^{\top}Mz ∥ z ∥ M 2 := z ⊤ M z M ⪰ 0 M\succeq0 M ⪰ 0
Since ∣ B v u ∣ = M v u |B_{vu}|=M_{vu} ∣ B v u ∣ = M v u B B B D v : = B v v = ∑ u ∼ v M v u D_v:=B_{vv}=\sum_{u\sim v}M_{vu} D v := B v v = ∑ u ∼ v M v u D : = blockdiag ( D 1 , … , D n ) D:=\operatorname{blockdiag}(D_1,\ldots,D_n) D := blockdiag ( D 1 , … , D n ) anisotropic bundle sheaf : a rotation W v u W_{vu} W v u M v u M_{vu} M v u W v u W_{vu} W v u
Remark 4.1 (On the terminology). Throughout this work we treat Bochner matrices as a class extending the connection Laplacians of Singer and coauthors [22 , 23 ] . In differential geometry the Bochner Laplacian and the connection Laplacian are essentially the same operator. In our discrete setting they refer to distinct families of Laplacians, but this is simply because they come from two different constructions: connection Laplacians were obtained by discretizing bundles over manifolds, in the context of local PCA and vector diffusion maps, whereas we arrive at Bochner matrices in purely algebraic terms, as the first term of the Bochner–Weitzenböck decomposition of § 3 . The two nonetheless share the properties needed to model holonomy and parallel transport on a graph.
We now turn to the kernel characterization of the Bochner Laplacian.
Lemma 4.1 (Energy identity). For every x ∈ R n d x\in\mathbb{R}^{nd} x ∈ R n d x ⊤ B x = 1 2 ∑ v ≠ u ∥ x v − W v u ⊤ x u ∥ M v u 2 ≥ 0 x^{\top}Bx=\frac{1}{2}\sum_{v\ne u}\|x_v-W_{vu}^{\top}x_u\|_{M_{vu}}^2\ge0 x ⊤ B x = 2 1 ∑ v = u ∥ x v − W v u ⊤ x u ∥ M v u 2 ≥ 0 each unordered edge contributing equally from either orientation.
Proof. Expand ∥ x v − W v u ⊤ x u ∥ M v u 2 = x v ⊤ M v u x v − 2 x v ⊤ M v u W v u ⊤ x u + x u ⊤ W v u M v u W v u ⊤ x u \|x_v-W_{vu}^{\top}x_u\|_{M_{vu}}^2=x_v^{\top}M_{vu}x_v-2x_v^{\top}M_{vu}W_{vu}^{\top}x_u+x_u^{\top}W_{vu}M_{vu}W_{vu}^{\top}x_u ∥ x v − W v u ⊤ x u ∥ M v u 2 = x v ⊤ M v u x v − 2 x v ⊤ M v u W v u ⊤ x u + x u ⊤ W v u M v u W v u ⊤ x u x u ⊤ M u v x u x_u^{\top}M_{uv}x_u x u ⊤ M uv x u ∑ v , u x v ⊤ D v x v \sum_{v,u}x_v^{\top}D_vx_v ∑ v , u x v ⊤ D v x v − 2 x v ⊤ B v u x u -2x_v^{\top}B_{vu}x_u − 2 x v ⊤ B v u x u x ⊤ B x x^{\top}Bx x ⊤ B x M v u ⪰ 0 M_{vu}\succeq0 M v u ⪰ 0
When M v u = w v u I M_{vu}=w_{vu}I M v u = w v u I ∑ v ≠ u w v u ∥ x v − W v u ⊤ x u ∥ 2 \sum_{v\ne u}w_{vu}\|x_v-W_{vu}^{\top}x_u\|^2 ∑ v = u w v u ∥ x v − W v u ⊤ x u ∥ 2 [22 ] . Since B ⪰ 0 B\succeq0 B ⪰ 0 x ∈ ker ( B ) x\in\ker(B) x ∈ ker ( B )
Proposition 4.1 (Kernel). Let B B B ( H 1 ) (H1) ( H 1 ) ( H 2 ) (H2) ( H 2 ) x ∈ ker ( B ) x \in\ker(B) x ∈ ker ( B ) x u = W v u x v x_u = W_{vu}x_v x u = W v u x v ( v , u ) (v,u) ( v , u ) ∥ x v ∥ \lVert x_v\rVert ∥ x v ∥
An immediate corollary: each summand vanishes iff x v = W v u T x u x_v = W_{vu}^{\mathsf{T}}x_u x v = W v u T x u W v u W_{vu} W v u
With the kernel in hand, the same evaluation-map argument used for the Connection Laplacian [20 , 22 ] applies verbatim (proof in Appendix § 10 ):
Proposition 4.2 (Kernel and holonomy). Let B B B ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 ) γ : v 0 → ⋯ → v k \gamma: v_0 \to\cdots\to v_k γ : v 0 → ⋯ → v k T γ : = W v k − 1 v k ⋯ W v 0 v 1 ∈ O ( d ) T_\gamma:= W_{v_{k-1}v_k} \cdots W_{v_0v_1} \in O(d) T γ := W v k − 1 v k ⋯ W v 0 v 1 ∈ O ( d ) dim ker ( B ) ≤ d \dim\ker(B) \le d dim ker ( B ) ≤ d T γ = I T_\gamma= I T γ = I γ \gamma γ
While the technique is unchanged from the connection-Laplacian case, the result is novel: despite carrying the extra radial data M v u M_{vu} M v u [13 ] , the normalized Laplacian of any weighted cellular sheaf has spectrum in [ 0 , 2 ] [0,2] [ 0 , 2 ] spec ( B ~ ) ⊆ [ 0 , 2 ] \operatorname{spec}(\widetilde{B}) \subseteq[0,2] spec ( B ) ⊆ [ 0 , 2 ] B ~ : = D − 1 / 2 B D − 1 / 2 \widetilde{B} := D^{-1/2}BD^{-1/2} B := D − 1/2 B D − 1/2 N : = 2 D − B N := 2D-B N := 2 D − B N v u = − B v u = − M v u W v u T N_{vu} = -B_{vu} = -M_{vu}W_{vu}^{\mathsf{T}} N v u = − B v u = − M v u W v u T N N N B B B − W v u -W_{vu} − W v u x T B x ≤ 2 x T D x x^{\mathsf{T}}Bx \le2x^{\mathsf{T}}Dx x T B x ≤ 2 x T D x 2 2 2 N N N T ~ γ : = ( − 1 ) ∣ γ ∣ T γ \widetilde{T}_\gamma:= (-1)^{|\gamma|}T_\gamma T γ := ( − 1 ) ∣ γ ∣ T γ
Theorem 4.1 (Antibalance characterization). Let E 2 ( B ~ ) E_2(\widetilde{B}) E 2 ( B ) B ~ \widetilde{B} B 2 2 2 E 2 ( B ~ ) = D 1 / 2 ker ( N ) E_2(\widetilde{B}) = D^{1/2}\ker(N) E 2 ( B ) = D 1/2 ker ( N ) z ∈ ker ( N ) z \in\ker(N) z ∈ ker ( N ) z u = − W v u z v z_u = -W_{vu}z_v z u = − W v u z v dim E 2 ( B ~ ) ≤ d \dim E_2(\widetilde{B}) \le d dim E 2 ( B ) ≤ d T γ = ( − 1 ) ∣ γ ∣ I T_\gamma= (-1)^{|\gamma|}I T γ = ( − 1 ) ∣ γ ∣ I
This is immediate from 2 I − B ~ = D − 1 / 2 N D − 1 / 2 2I-\widetilde{B} = D^{-1/2}ND^{-1/2} 2 I − B = D − 1/2 N D − 1/2 N N N G G G x ∈ ker ( B ) x \in\ker(B) x ∈ ker ( B ) z ∈ ker ( N ) z \in\ker(N) z ∈ ker ( N ) E 2 ( B ~ ) = D 1 / 2 ker ( N ) E_2(\widetilde{B}) = D^{1/2}\ker(N) E 2 ( B ) = D 1/2 ker ( N ) ⟨ x v , z v ⟩ = 0 \langle x_v,z_v\rangle= 0 ⟨ x v , z v ⟩ = 0 § 12 ).
Cheeger inequalities and the synchronization problems
Seeing Bochner matrices as a generalization of both matrix-weighted Laplacians and connection Laplacians lets us extend techniques known for these two classes. Hansen’s comparison between the block spectrum of a matrix-weighted Laplacian and a scalar one [26 ] extends to Bochner matrices (Appendix § 12 ). Here we follow the synchronization framework of Bandeira, Singer and Spielman [22 , 63 ] , extended to the anisotropic setting. Each of the three theorems below comes with an algorithm attaining the bound, since the nontrivial half of a Cheeger-type inequality is proved by exhibiting a good combinatorial object.
Definition 4.1 (Anisotropy constants and companion graph). For each edge, w v u + : = λ min ( M v u ) w_{vu}^{+} := \lambda_{\min}(M_{vu}) w v u + := λ m i n ( M v u ) w v u − : = λ max ( M v u ) w_{vu}^{-} := \lambda_{\max}(M_{vu}) w v u − := λ m a x ( M v u )
κ E : = max e ∈ E w e + w e − ≥ 1 , κ D : = max v ∈ V λ max ( D v ) λ min ( D v ) . (12) \kappa_E := \max_{e\in E}\frac{w_e^{+}}{w_e^{-}} \ge1,\qquad\kappa_D := \max_{v\in V}\frac{\lambda_{\max}(D_v)}{\lambda_{\min}(D_v)}. \tag*{(12)} κ E := e ∈ E max w e − w e + ≥ 1 , κ D := v ∈ V max λ m i n ( D v ) λ m a x ( D v ) . (12) For each vertex, d v ± : = ∑ u ∼ v w v u ± d_v^{\pm} := \sum_{u\sim v} w_{vu}^{\pm} d v ± := ∑ u ∼ v w v u ± G − G_{-} G − V V V w v u − w_{vu}^{-} w v u − D 0 − : = diag ( d v − ) D_0^{-} := \operatorname{diag}(d_v^{-}) D 0 − := diag ( d v − ) L − L_{-} L − ( L − ) v v = d v − (L_{-})_{vv}=d_v^{-} ( L − ) v v = d v − ( L − ) v u = − w v u − (L_{-})_{vu}=-w_{vu}^{-} ( L − ) v u = − w v u − v ≠ u v\ne u v = u L − : = ( D 0 − ) − 1 / 2 L − ( D 0 − ) − 1 / 2 \mathcal{L}_{-} := (D_0^{-})^{-1/2}L_{-}(D_0^{-})^{-1/2} L − := ( D 0 − ) − 1/2 L − ( D 0 − ) − 1/2 x ∈ R n d x \in\mathbb{R}^{nd} x ∈ R n d n x ∈ R n n_x \in\mathbb{R}^{n} n x ∈ R n ( n x ) v : = ∥ x v ∥ (n_x)_v := \lVert x_v\rVert ( n x ) v := ∥ x v ∥
By ( H 2 ) (H2) ( H 2 ) ( H 3 ) (H3) ( H 3 ) G − G_{-} G − G G G λ 2 ( L − ) > 0 \lambda_2(\mathcal{L}_{-})>0 λ 2 ( L − ) > 0 κ E = 1 \kappa_E=1 κ E = 1 W = I W=I W = I κ E \kappa_E κ E
Definition 4.2 (Frustration constants). For M ⪰ 0 M \succeq0 M ⪰ 0 ∥ A ∥ M , F 2 : = tr ( A T M A ) \lVert A\rVert_{M,F}^{2} := \operatorname{tr}(A^{\mathsf{T}}MA) ∥ A ∥ M , F 2 := tr ( A T M A ) η ( x ) : = x T B x x T D x \eta(x) := \frac{x^{\mathsf{T}}Bx}{x^{\mathsf{T}}Dx} η ( x ) := x T D x x T B x
η G : = min x : V → S d − 1 η ( x ) , η G ∗ : = min x : V → S d − 1 ∪ { 0 } x ≠ 0 η ( x ) , (13) \eta_G := \min_{x:V\to S^{d-1}}\eta(x),\qquad\eta_G^{*} := \min_{\substack{x:V\to S^{d-1}\cup\{0\}\\x\ne0}}\eta(x), \tag*{(13)} η G := x : V → S d − 1 min η ( x ) , η G ∗ := x : V → S d − 1 ∪ { 0 } x = 0 min η ( x ) , (13) and, for a group potential g : V → O ( d ) g: V \to O(d) g : V → O ( d )
ν ( g ) : = 1 2 ∑ v ≠ u ∥ g v − W v u T g u ∥ M v u , F 2 vol ( G ) , vol ( G ) : = ∑ v tr ( D v ) , ν G : = min g : V → O ( d ) ν ( g ) . (14) \nu(g) := \frac{\frac{1}{2}\sum_{v\ne u}\left\|g_v-W_{vu}^{\mathsf{T}}g_u\right\|_{M_{vu},F}^{2}}{\operatorname{vol}(G)}, \qquad\operatorname{vol}(G):=\sum_v\operatorname{tr}(D_v), \qquad\nu_G:=\min_{g:V\to O(d)}\nu(g). \tag*{(14)} ν ( g ) := vol ( G ) 2 1 ∑ v = u g v − W v u T g u M v u , F 2 , vol ( G ) := v ∑ tr ( D v ) , ν G := g : V → O ( d ) min ν ( g ) . (14) Each of the three measures how far B B B § 2.2 ) measures how far it is from being balanced. The three constants correspond to three feasible sets: a unit vector at some vertices, at every vertex, and a full orthonormal frame at every vertex, each measuring the residual of explaining the measured rotations W v u W_{vu} W v u g u g v − 1 g_ug_v^{-1} g u g v − 1 ν ( g ) \nu(g) ν ( g ) ν ( g ) = ∑ k ≤ d ( g ( k ) ) T B g ( k ) / ∑ k ≤ d ( g ( k ) ) T D g ( k ) \nu(g)=\sum_{k\le d}(g^{(k)})^{\mathsf{T}}Bg^{(k)}/\sum_{k\le d}(g^{(k)})^{\mathsf{T}}Dg^{(k)} ν ( g ) = ∑ k ≤ d ( g ( k ) ) T B g ( k ) / ∑ k ≤ d ( g ( k ) ) T D g ( k ) ν \nu ν η \eta η d d d ∑ k ≤ d λ k ( B ~ ) \sum_{k\le d}\lambda_k(\widetilde{B}) ∑ k ≤ d λ k ( B ) λ 1 ( B ~ ) \lambda_1(\widetilde{B}) λ 1 ( B ) ν G \nu_G ν G Figure 1 pictures the S d − 1 S^{d-1} S d − 1 O ( d ) O(d) O ( d )
Figure 1. The S d − 1 S^{d-1} S d − 1 O ( d ) O(d) O ( d ) d = 2 d=2 d = 2 W 10 T W_{10}^{\mathsf{T}} W 10 T 90 ∘ 90^\circ 9 0 ∘ x 0 x_0 x 0 x 1 x_1 x 1 W 10 T x 0 W_{10}^{\mathsf{T}}x_0 W 10 T x 0 M 10 M_{10} M 10 M 10 M_{10} M 10 w 10 + w_{10}^{+} w 10 + w 10 − w_{10}^{-} w 10 − g v ∈ O ( d ) g_v\in O(d) g v ∈ O ( d ) ∥ g 1 − W 10 T g 0 ∥ M 10 , F \left\|g_1-W_{10}^{\mathsf{T}}g_0\right\|_{M_{10},F} g 1 − W 10 T g 0 M 10 , F
Proposition 4.3 (Relaxation). Under ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 ) (a) λ 1 ( B ~ ) ≤ η G ∗ ≤ η G \lambda_1(\widetilde{B})\le\eta_G^*\le\eta_G λ 1 ( B ) ≤ η G ∗ ≤ η G λ 1 ( B ~ ) ≤ ν G \lambda_1(\widetilde{B})\le\nu_G λ 1 ( B ) ≤ ν G 1 d κ D ∑ k = 1 d λ k ( B ~ ) ≤ ν G \frac{1}{d\kappa_D}\sum_{k=1}^{d}\lambda_k(\widetilde{B})\le\nu_G d κ D 1 ∑ k = 1 d λ k ( B ) ≤ ν G
Proof in Appendix § 10 . Parts (a) and (b) match the connection-Laplacian case; (c) does not, since ordinary vertex degrees no longer make the columns of a group potential D D D κ D \kappa_D κ D
Proposition 4.4 (Zero sets). Under ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 ) λ 1 ( B ~ ) = 0 ⟺ ker ( B ) ≠ { 0 } ⟺ η G = 0 ⟺ η G ∗ = 0 \lambda_1(\widetilde{B})=0\Longleftrightarrow\ker(B)\ne\{0\}\Longleftrightarrow\eta_G=0\Longleftrightarrow\eta_G^*=0 λ 1 ( B ) = 0 ⟺ ker ( B ) = { 0 } ⟺ η G = 0 ⟺ η G ∗ = 0 ν G = 0 \nu_G=0 ν G = 0 T γ T_\gamma T γ dim ker ( B ) = d \dim\ker(B)=d dim ker ( B ) = d
Proof in Appendix § 10 .
Partial synchronization. In the first problem some vertices are allowed to abstain.
Algorithm 4.1 (Partial synchronization). Input: a Bochner matrix B B B ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 )
Form B ~ = D − 1 / 2 B D − 1 / 2 \widetilde{B}=D^{-1/2}BD^{-1/2} B = D − 1/2 B D − 1/2 z z z λ 1 ( B ~ ) \lambda_1(\widetilde{B}) λ 1 ( B )
Set x : = D − 1 / 2 z x:=D^{-1/2}z x := D − 1/2 z max v ∥ x v ∥ = 1 \max_v\|x_v\|=1 max v ∥ x v ∥ = 1
For t ≥ 0 t \ge0 t ≥ 0 x > t x^{>t} x > t
x v > t : = { x v / ∥ x v ∥ , ∥ x v ∥ 2 > t , 0 , otherwise , (15) x_v^{>t} := \begin{cases} x_v / \lVert x_v \rVert, & \lVert x_v \rVert^2 > t, \\ 0, & \text{otherwise}, \end{cases} \tag*{(15)} x v > t := { x v / ∥ x v ∥ , 0 , ∥ x v ∥ 2 > t , otherwise , (15) and form the candidates x > t x^{>t} x > t n n n t = ∥ x v ∥ 2 t = \lVert x_v \rVert^2 t = ∥ x v ∥ 2 v ∈ V v \in V v ∈ V
Output: the candidate minimizing η \eta η
Steps 3 and 4 turn the eigenvector into an admissible assignment, the step that Cheeger-type proofs call rounding. Step 3 needs only finitely many thresholds: as t t t x > t x^{>t} x > t t t t ∥ x v ∥ 2 \lVert x_v \rVert^2 ∥ x v ∥ 2 n n n
Theorem 4.2 (Partial synchronization). Under ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 )
λ 1 ( B ~ ) ≤ η G ∗ ≤ κ E 3 / 2 10 λ 1 ( B ~ ) , (16) \lambda_1(\widetilde{B}) \le\eta_G^* \le\kappa_E^{3/2} \sqrt{10\lambda_1(\widetilde{B})}, \tag*{(16)} λ 1 ( B ) ≤ η G ∗ ≤ κ E 3/2 10 λ 1 ( B ) , (16) and Algorithm 4.1 returns a partial assignment attaining the upper bound.
Proof in Appendix § 10 .
Full synchronization. Moving from partial to full synchronization additionally requires controlling the connectivity of the companion graph, quantified by its spectral gap λ 2 ( L − ) \lambda_2(\mathcal{L}_-) λ 2 ( L − ) [22 ] .
Algorithm 4.2 (Full synchronization). Input: a Bochner matrix B B B ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 )
Form B ~ = D − 1 / 2 B D − 1 / 2 \widetilde{B} = D^{-1/2}BD^{-1/2} B = D − 1/2 B D − 1/2 z z z λ 1 ( B ~ ) \lambda_1(\widetilde{B}) λ 1 ( B )
Set x : = D − 1 / 2 z x := D^{-1/2}z x := D − 1/2 z
Output: the normalized assignment x ~ \widetilde{x} x x ~ v : = x v / ∥ x v ∥ \widetilde{x}_v := x_v/\lVert x_v\rVert x v := x v / ∥ x v ∥ x v ≠ 0 x_v \ne0 x v = 0 x v = 0 x_v = 0 x v = 0
Theorem 4.3 (Full synchronization). Under ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 )
λ 1 ( B ~ ) ≤ η G ≤ 54 κ E 2 λ 2 ( L − ) λ 1 ( B ~ ) , (17) \lambda_1(\widetilde{B}) \le\eta_G \le\frac{54\kappa_E^2}{\lambda_2(\mathcal{L}_-)}\lambda_1(\widetilde{B}), \tag*{(17)} λ 1 ( B ) ≤ η G ≤ λ 2 ( L − ) 54 κ E 2 λ 1 ( B ) , (17) and Algorithm 4.2 returns a full assignment attaining the upper bound.
Proof in Appendix § 10 .
Synchronization in O ( d ) O(d) O ( d ) The third problem asks for a full orthonormal frame at every vertex. Its solution uses the polar projection: for nonsingular X = P Σ Q ⊤ X = P\Sigma Q^\top X = P Σ Q ⊤ Pol ( X ) : = P Q ⊤ \operatorname{Pol}(X) := PQ^\top Pol ( X ) := P Q ⊤ D D D
d ‾ v : = 1 d tr ( D v ) , D ‾ : = blockdiag ( d ‾ v I d ) , B ‾ : = D ‾ − 1 / 2 B D ‾ − 1 / 2 , vol : = ∑ v d ‾ v , (18) \overline{d}_v := \frac{1}{d}\operatorname{tr}(D_v), \qquad\overline{D} := \operatorname{blockdiag}(\overline{d}_v I_d), \qquad\overline{B} := \overline{D}^{-1/2}B\overline{D}^{-1/2}, \qquad\operatorname{vol} := \sum_v \overline{d}_v, \tag*{(18)} d v := d 1 tr ( D v ) , D := blockdiag ( d v I d ) , B := D − 1/2 B D − 1/2 , vol := v ∑ d v , (18) whose relevant property is that, D ‾ \overline{D} D x ⊤ D ‾ x = ∑ v d ‾ v ∥ x v ∥ 2 = ∥ x ∥ D ‾ 0 2 x^\top\overline{D}x = \sum_v \overline{d}_v\lVert x_v\rVert^2 = \lVert x\rVert_{\overline{D}_0}^2 x ⊤ D x = ∑ v d v ∥ x v ∥ 2 = ∥ x ∥ D 0 2 x x x D ‾ 0 : = diag ( d ‾ v ) \overline{D}_0 := \operatorname{diag}(\overline{d}_v) D 0 := diag ( d v ) O ( d ) O(d) O ( d ) d d d D ‾ \overline{D} D D D D D ‾ \overline{D} D B ~ \widetilde{B} B D D D λ 2 ( L − ) \lambda_2(\mathcal{L}_-) λ 2 ( L − )
Algorithm 4.3 (O ( d ) O(d) O ( d ) B B B ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 )
Form d ‾ v = 1 d tr ( D v ) \overline{d}_v = \frac{1}{d}\operatorname{tr}(D_v) d v = d 1 tr ( D v ) B ‾ = D ‾ − 1 / 2 B D ‾ − 1 / 2 \overline{B} = \overline{D}^{-1/2}B\overline{D}^{-1/2} B = D − 1/2 B D − 1/2
Compute orthonormal eigenvectors z 1 , … , z d z^1,\ldots,z^d z 1 , … , z d B ‾ \overline{B} B d d d λ 1 ( B ‾ ) ≤ ⋯ ≤ λ d ( B ‾ ) \lambda_1(\overline{B}) \le\cdots\le\lambda_d(\overline{B}) λ 1 ( B ) ≤ ⋯ ≤ λ d ( B )
Set x k : = vol D ‾ − 1 / 2 z k x^k := \sqrt{\operatorname{vol}}\,\overline{D}^{-1/2}z^k x k := vol D − 1/2 z k k = 1 , … , d k = 1,\ldots,d k = 1 , … , d X v : = [ x v 1 ⋯ x v d ] ∈ R d × d X_v := [x_v^1 \ \cdots\ x_v^d] \in\mathbb{R}^{d \times d} X v := [ x v 1 ⋯ x v d ] ∈ R d × d
Output: the group potential g v : = Pol ( X v ) g_v := \operatorname{Pol}(X_v) g v := Pol ( X v ) X v X_v X v g v : = I d g_v := I_d g v := I d X v X_v X v
Theorem 4.4 (O ( d ) O(d) O ( d ) Under ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 )
1 d κ D ∑ k = 1 d λ k ( B ~ ) ≤ ν G ≤ 2 11 κ E 3 d 3 λ 2 ( L − ) ∑ k = 1 d λ k ( B ~ ) , (19) \frac{1}{d\kappa_D}\sum_{k=1}^{d}\lambda_k(\widetilde{B}) \le\nu_G \le\frac{2^{11}\kappa_E^3d^3}{\lambda_2(\mathcal{L}_{-})}\sum_{k=1}^{d}\lambda_k(\widetilde{B}), \tag*{(19)} d κ D 1 k = 1 ∑ d λ k ( B ) ≤ ν G ≤ λ 2 ( L − ) 2 11 κ E 3 d 3 k = 1 ∑ d λ k ( B ) , (19) with κ D ≤ κ E \kappa_D \le\kappa_E κ D ≤ κ E ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 )
Proof in Appendix A.
In the isotropic case every M v u = ω v u I d M_{vu} = \omega_{vu}I_d M v u = ω v u I d κ E = κ D = 1 \kappa_E = \kappa_D = 1 κ E = κ D = 1 D v = d v I d D_v = d_vI_d D v = d v I d D ‾ = D \overline{D} = D D = D G − G_{-} G − λ 2 ( L − ) = λ 2 ( L 0 ) \lambda_2(\mathcal{L}_{-}) = \lambda_2(\mathcal{L}_0) λ 2 ( L − ) = λ 2 ( L 0 ) ( H 3 ) (H3) ( H 3 ) [22 ] , up to the numerical constants: in place of our 54 54 54 2 11 2^{11} 2 11 44 44 44 2 10 2^{10} 2 10
The κ E 3 / 2 \kappa_E^{3/2} κ E 3/2 x ⊤ B x x^\top Bx x ⊤ B x ℓ 1 \ell^1 ℓ 1 η \eta η κ E 2 \kappa_E^2 κ E 2 κ E 3 \kappa_E^3 κ E 3
Related Cheeger inequalities. Liu, Münch and Peyerimhoff [36 ] prove Buser-type inequalities for connection Laplacians with orthogonal or unitary matrices, bounding eigenvalues from above under nonnegative Ricci curvature. Their Cheeger constants are mixtures of the expansion rate of the underlying graph and the frustration index of the signature. One open question would be to generalize Ricci curvature for Connection Laplacian to Bochner matrices, and, subsequently, apply analogous Cheeger inequalities to Bochner matrices.
For general sheaves, First and Kaufman [64 ] prove Cheeger-type inequalities bounding the coboundary expansion of sheaves obtained as quotients of a constant sheaf by a subsheaf. Their technique applies only to certain graphs, which they characterize, whereas the inequalities above hold for every Bochner matrix on an arbitrary graph. To our knowledge, the Bochner matrices defined in this work are therefore the largest class of cellular sheaves for which a Cheeger inequality is known on arbitrary graphs …
The anisotropic random walk
Attaching a random walk to a general sheaf Laplacian is nontrivial, and is left open by Hansen and Ghrist [13 ] . The obstruction is already visible for d = 1 d = 1 d = 1 v v v ∑ e F v ⊂ e 2 \sum_e F^2_{v\subset e} ∑ e F v ⊂ e 2 e = ( v , u ) e = (v,u) e = ( v , u ) F v ⊂ e F u ⊂ e F_{v\subset e}F_{u\subset e} F v ⊂ e F u ⊂ e p v u = w v u / ∑ ρ w v ρ p_{vu} = w_{vu}/\sum_{\rho}w_{v\rho} p v u = w v u / ∑ ρ w v ρ [22 , 23 ] ; Bochner matrices repair the general case, since by construction their diagonal block is exactly the sum of the matrix absolute values of the off-diagonal ones.
Definition 4.3 (Anisotropic random walk). Let B B B ( H 1 ) (H1) ( H 1 ) ( H 3 ) (H3) ( H 3 ) u u u v v v
P v u : = D v − 1 / 2 M v u D v − 1 / 2 ⪰ 0 , ∑ u ≠ v P v u = D v − 1 / 2 ( ∑ u ≠ v M v u ) D v − 1 / 2 = I , (20) P_{vu} := D_v^{-1/2}M_{vu}D_v^{-1/2} \succeq0,\qquad\sum_{u\ne v}P_{vu}=D_v^{-1/2}\left(\sum_{u\ne v}M_{vu}\right)D_v^{-1/2}=I, \tag*{(20)} P v u := D v − 1/2 M v u D v − 1/2 ⪰ 0 , u = v ∑ P v u = D v − 1/2 u = v ∑ M v u D v − 1/2 = I , (20) a Positive Operator-Valued Measure (POVM) at v v v x ^ v ∈ S d − 1 \hat{x}_v\in S^{d-1} x ^ v ∈ S d − 1 u u u p v u ( x ^ v ) : = x ^ v ⊤ P v u x ^ v p_{vu}(\hat{x}_v):=\hat{x}_v^\top P_{vu}\hat{x}_v p v u ( x ^ v ) := x ^ v ⊤ P v u x ^ v x ^ ↦ W v u x ^ \hat{x}\mapsto W_{vu}\hat{x} x ^ ↦ W v u x ^ S = V × S d − 1 \mathcal{S}=V\times S^{d-1} S = V × S d − 1 ( v , x ^ ) (v,\hat{x}) ( v , x ^ ) ( u , W v u x ^ ) (u,W_{vu}\hat{x}) ( u , W v u x ^ ) p v u ( x ^ ) p_{vu}(\hat{x}) p v u ( x ^ )
The jump law is state-dependent: which neighbour the walker visits next depends on the direction x ^ \hat{x} x ^ x ^ \hat{x} x ^ M v u M_{vu} M v u M v u = w v u I M_{vu}=w_{vu}I M v u = w v u I P v u P_{vu} P v u w v u / ∑ ρ w v ρ w_{vu}/\sum_{\rho}w_{v\rho} w v u / ∑ ρ w v ρ [22 , 23 ] . We also note that an effective conductance and resistance have recently been developed out of that notion of random walk [65 ] .
For d = 1 d = 1 d = 1 O ( 1 ) = { − 1 , + 1 } O(1) = \{-1, +1\} O ( 1 ) = { − 1 , + 1 } § 2.2 : each node is lifted to two copies, one per sign, and P v u P_{vu} P v u S d − 1 S^{d-1} S d − 1 { P v u } \{P_{vu}\} { P v u } d = 1 d = 1 d = 1 Figure 2 ). We call it the generalized Gremban expansion : it carries the scalar construction from S 0 = { − 1 , + 1 } S^0 = \{-1, +1\} S 0 = { − 1 , + 1 } O ( d ) O(d) O ( d )
Figure 2. The random walk of a Bochner matrix as a generalized Gremban expansion. (a) For the signed triangle with w 01 = − 3 w_{01} = -3 w 01 = − 3 w 02 = 1 w_{02} = 1 w 02 = 1 v + v^+ v + v − v^- v − 3 / 4 3/4 3/4 1 / 4 1/4 1/4 ∣ w 0 u ∣ |w_{0u}| ∣ w 0 u ∣ 0 ± → 1 ∓ 0^\pm\to1^\mp 0 ± → 1 ∓ 0 ± → 2 ± 0^\pm\to2^\pm 0 ± → 2 ± d > 1 d > 1 d > 1 S d − 1 S^{d-1} S d − 1 p 0 u ( x ^ ) = x ^ T P 0 u x ^ p_{0u}(\hat{x}) = \hat{x}^{\mathsf{T}}P_{0u}\hat{x} p 0 u ( x ^ ) = x ^ T P 0 u x ^ y y y 3 / 4 3/4 3/4 1 / 4 1/4 1/4 x x x 1 / 2 1/2 1/2
Trajectories and conserved quantities. The fibre carries no randomness of its own. Each step applies W v i v i + 1 W_{v_i v_{i+1}} W v i v i + 1 γ : v 0 → ⋯ → v t \gamma: v_0 \to\cdots\to v_t γ : v 0 → ⋯ → v t ( v t , T γ x ^ 0 ) (v_t, T_\gamma\hat{x}_0) ( v t , T γ x ^ 0 ) f y ( v , x ^ ) : = ⟨ x ^ , y v ⟩ f_y(v, \hat{x}) := \langle\hat{x}, y_v\rangle f y ( v , x ^ ) := ⟨ x ^ , y v ⟩ every trajectory, and not merely in expectation, are exactly those with y ∈ ker ( B ) y \in\ker(B) y ∈ ker ( B ) y y y § 10 . Kernel vectors therefore confine the walker to a subset of each fibre. The walk is not reversible in general, while a variant with the same fibre update and a modified jump law is; both facts are in Appendix § 12 .
Forman Sheaf Curvature
So far we have presented the Bochner–Weitzenböck decomposition for each order k k k k = 0 k=0 k = 0 k = 1 k=1 k = 1 H 1 F = B 1 F + F 1 F H^{\mathcal{F}}_1 = B^{\mathcal{F}}_1 + F^{\mathcal{F}}_1 H 1 F = B 1 F + F 1 F L F L_{\mathcal{F}} L F sheaf Forman Ricci curvature Ric F : = F 1 F \operatorname{Ric}_{\mathcal{F}} := F^{\mathcal{F}}_1 Ric F := F 1 F dim H 1 ( M ; F ) \dim\mathcal{H}^1(M;\mathcal{F}) dim H 1 ( M ; F ) M M M F \mathcal{F} F d d d
A Bochner theorem for cellular sheaves
The two ingredients of the theorem are assembled here: nonnegative curvature confines a harmonic cochain to the kernel of the Bochner term, and the kernel characterization of Section § 4 then propagates a vanishing from one edge to its neighbours.
Corollary 5.1. Under Ric F ⪰ 0 \operatorname{Ric}_{\mathcal{F}} \succeq0 Ric F ⪰ 0 ker ( H 1 F ) = ker ( B 1 F ) ∩ ker ( Ric F ) \ker(H^{\mathcal{F}}_1) = \ker(B^{\mathcal{F}}_1) \cap\ker(\operatorname{Ric}_{\mathcal{F}}) ker ( H 1 F ) = ker ( B 1 F ) ∩ ker ( Ric F )
Proof. B 1 F ⪰ 0 B^{\mathcal{F}}_1 \succeq0 B 1 F ⪰ 0 Ric F ⪰ 0 \operatorname{Ric}_{\mathcal{F}} \succeq0 Ric F ⪰ 0 c ∈ ker ( H 1 F ) c \in\ker(H^{\mathcal{F}}_1) c ∈ ker ( H 1 F ) 0 = ⟨ H 1 F c , c ⟩ = ⟨ B 1 F c , c ⟩ + ⟨ Ric F c , c ⟩ 0 = \langle H^{\mathcal{F}}_1 c,c\rangle= \langle B^{\mathcal{F}}_1 c,c\rangle+ \langle\operatorname{Ric}_{\mathcal{F}}c,c\rangle 0 = ⟨ H 1 F c , c ⟩ = ⟨ B 1 F c , c ⟩ + ⟨ Ric F c , c ⟩ c ∈ ker ( B 1 F ) ∩ ker ( Ric F ) c \in\ker(B^{\mathcal{F}}_1) \cap\ker(\operatorname{Ric}_{\mathcal{F}}) c ∈ ker ( B 1 F ) ∩ ker ( Ric F )
Lemma 5.1. Let c = ∑ e c e e ∈ ker ∂ ∗ ∩ ker B 1 F c = \sum_e c_e e \in\ker\partial^* \cap\ker B^{\mathcal{F}}_1 c = ∑ e c e e ∈ ker ∂ ∗ ∩ ker B 1 F f f f e 1 , e 2 ⊴ f e_1,e_2 \unlhd f e 1 , e 2 ⊴ f e ‾ 1 ∩ e ‾ 2 ≠ ∅ \overline{e}_1 \cap\overline{e}_2 \ne\varnothing e 1 ∩ e 2 = ∅ c e 1 = c e 2 = 0 c_{e_1} = c_{e_2} = 0 c e 1 = c e 2 = 0 c e = 0 c_e = 0 c e = 0 e ⊴ f e \unlhd f e ⊴ f
Proof. Let e ≠ e 1 , e 2 e \ne e_1,e_2 e = e 1 , e 2 f f f e e e e 1 e_1 e 1 e 2 e_2 e 2 B 1 F B^{\mathcal{F}}_1 B 1 F e e e e 1 e_1 e 1 F e ⊴ f F e 1 ⊴ f T \mathcal{F}_{e\unlhd f}\mathcal{F}_{e_1\unlhd f}^{\mathsf{T}} F e ⊴ f F e 1 ⊴ f T ∥ c e ∥ = ∥ c e 1 ∥ = 0 \lVert c_e\rVert= \lVert c_{e_1}\rVert= 0 ∥ c e ∥ = ∥ c e 1 ∥ = 0
Otherwise e e e e 1 , e 2 e_1,e_2 e 1 , e 2 M M M f f f v f ∈ F ( f ) v_f \in\mathcal{F}(f) v f ∈ F ( f ) ∂ v f \partial v_f ∂ v f f f f v f v_f v f c e 1 = c e 2 = 0 c_{e_1}=c_{e_2}=0 c e 1 = c e 2 = 0 ⟨ ∂ v f , c ⟩ = ± v f T F e ⊴ f c e \langle\partial v_f,c\rangle= \pm v_f^{\mathsf{T}}\mathcal{F}_{e\unlhd f}c_e ⟨ ∂ v f , c ⟩ = ± v f T F e ⊴ f c e ⟨ ∂ v f , c ⟩ = ⟨ v f , ∂ ∗ c ⟩ = 0 \langle\partial v_f,c\rangle= \langle v_f,\partial^*c\rangle= 0 ⟨ ∂ v f , c ⟩ = ⟨ v f , ∂ ∗ c ⟩ = 0 v f v_f v f F e ⊴ f c e = 0 \mathcal{F}_{e\unlhd f}c_e=0 F e ⊴ f c e = 0 F e ⊴ f \mathcal{F}_{e\unlhd f} F e ⊴ f c e = 0 c_e=0 c e = 0
Invertibility is what makes the last step work: without it, the argument only forces c e ∈ ker ( F e ⊴ f ) c_e \in\ker(\mathcal{F}_{e\unlhd f}) c e ∈ ker ( F e ⊴ f ) c e = 0 c_e=0 c e = 0
Theorem 5.1 (Unique continuation). Let M M M c ∈ ker ∂ ∗ ∩ ker B 1 F c \in\ker\partial^* \cap\ker B^{\mathcal{F}}_1 c ∈ ker ∂ ∗ ∩ ker B 1 F c e = 0 c_e=0 c e = 0 e e e c = 0 c=0 c = 0
By induction on graph distance from that vertex: at distance 0 the hypothesis gives c e = 0 c_e=0 c e = 0 k + 1 k+1 k + 1 § 10 .
Propagation turns a local hypothesis into a global bound on H 1 \mathcal{H}^1 H 1
Proposition 5.1. Let M M M Ric F ⪰ 0 \operatorname{Ric}_{\mathcal{F}} \succeq0 Ric F ⪰ 0 suppose Ric F ( e ) ≻ 0 \operatorname{Ric}_{\mathcal{F}}(e) \succ0 Ric F ( e ) ≻ 0 e e e H 1 ( M ; F ) = 0 \mathcal{H}^1(M;\mathcal{F})=0 H 1 ( M ; F ) = 0
Proof. By Corollary 5.1, a harmonic c c c ker ( Ric F ) \ker(\operatorname{Ric}_{\mathcal{F}}) ker ( Ric F )
Theorem 5.2 (Bochner theorem for combinatorial manifolds). Let M M M n n n n ≤ 3 n \le3 n ≤ 3 Ric F ⪰ 0 \operatorname{Ric}_{\mathcal F} \succeq0 Ric F ⪰ 0 dim H 1 ( M ; F ) ≤ n d \dim H^1(M;\mathcal F) \le nd dim H 1 ( M ; F ) ≤ n d
We follow Forman’s proof [24 Theorem 4.4] . By Corollary 5.1, a harmonic cochain c c c ker B 1 F \ker B_1^{\mathcal F} ker B 1 F c c c v v v parallel propagation : if two edges at v v v § 2.3 ) and c c c vertex relation : ∂ c = 0 \partial c = 0 ∂ c = 0 v v v c c c v v v n n n v v v c c c c c c v v v c = 0 c = 0 c = 0 c ↦ ( c e 1 , … , c e n ) c \mapsto(c_{e_1}, \ldots, c_{e_n}) c ↦ ( c e 1 , … , c e n ) H 1 ( M ; F ) H^1(M;\mathcal F) H 1 ( M ; F ) n d nd n d n = 1 n = 1 n = 1 n = 2 n = 2 n = 2 v v v v v v v v v n = 3 n = 3 n = 3 v v v S 2 S^2 S 2 v v v K 5 K_5 K 5 S 2 S^2 S 2 M M M § 10 checks them and recalls the choice.
Beyond n = 3 n = 3 n = 3
Definition 5.1 (Local homological dimension [24 ] ). At a vertex v v v ∼ \sim ∼ N ( v ) N(v) N ( v ) D ( v ) : = N ( v ) D(v) := N(v) D ( v ) := N ( v ) D ( v ) : = N ( v ) − 1 D(v) := N(v) - 1 D ( v ) := N ( v ) − 1 M M M D ( M ) : = inf v D ( v ) D(M) := \inf_v D(v) D ( M ) := inf v D ( v )
Theorem 5.3. Let M M M Ric F ⪰ 0 \operatorname{Ric}_{\mathcal F} \succeq0 Ric F ⪰ 0 dim H 1 ( M ; F ) ≤ d ⋅ D ( M ) \dim H^1(M;\mathcal F) \le d \cdot D(M) dim H 1 ( M ; F ) ≤ d ⋅ D ( M )
Full proof in Appendix § 10 . Since D ( v ) D(v) D ( v ) v v v
Comparison with combinatorial curvature
The same complex also carries the scalar Forman curvature Ric ( e ) = deg u ( e ) + deg l ( e ) − # { parallel neighbours of e } \operatorname{Ric}(e) = \operatorname{deg}_u(e) + \operatorname{deg}_l(e) - \#\{\text{parallel neighbours of }e\} Ric ( e ) = deg u ( e ) + deg l ( e ) − # { parallel neighbours of e } [24 ] . The two curvatures are independent: neither Ric ≥ 0 \operatorname{Ric} \ge0 Ric ≥ 0 Ric F ⪰ 0 \operatorname{Ric}_{\mathcal F} \succeq0 Ric F ⪰ 0 d = 1 d = 1 d = 1 Figure 3 .
Figure 3. The three examples of this section, with d = 1 d=1 d = 1 F 0 ⊴ [ 0 , 2 ] = F 1 ⊴ [ 1 , 2 ] = 2. \mathcal{F}_{0\trianglelefteq[0,2]}=\mathcal{F}_{1\trianglelefteq[1,2]}=2. F 0 ⊴ [ 0 , 2 ] = F 1 ⊴ [ 1 , 2 ] = 2. S 4 S_4 S 4 A A A A A A B B B q q q
Remark 5.1 (Curvature depends on the presentation). Ric F \operatorname{Ric}_{\mathcal F} Ric F Ric F ⪰ 0 \operatorname{Ric}_{\mathcal F} \succeq0 Ric F ⪰ 0
Example 5.1 (Nonnegative Ric \operatorname{Ric} Ric Ric F \operatorname{Ric}_{\mathcal F} Ric F M M M 0 , 1 , 2 0,1,2 0 , 1 , 2 2 2 2 Ric = 0 + 2 − 2 = 0 \operatorname{Ric} = 0 + 2 - 2 = 0 Ric = 0 + 2 − 2 = 0 1 1 1 F 0 ⊆ [ 0 , 2 ] = F 1 ⊆ [ 1 , 2 ] = 2 \mathcal F_{0\subseteq[0,2]} = \mathcal F_{1\subseteq[1,2]} = 2 F 0 ⊆ [ 0 , 2 ] = F 1 ⊆ [ 1 , 2 ] = 2 Ric F ( [ 0 , 1 ] ) = 2 − 2 − 2 = − 2 < 0 \operatorname{Ric}_{\mathcal F}([0,1]) = 2 - 2 - 2 = -2 < 0 Ric F ([ 0 , 1 ]) = 2 − 2 − 2 = − 2 < 0
Example 5.2 (Negative Ric \operatorname{Ric} Ric M M M S 4 S_4 S 4 0 0 0 1 , … , 4 1,\ldots,4 1 , … , 4 e i = [ 0 , i ] e_i = [0,i] e i = [ 0 , i ] Ric ( e i ) = 0 + 2 − 3 = − 1 \operatorname{Ric}(e_i) = 0 + 2 - 3 = -1 Ric ( e i ) = 0 + 2 − 3 = − 1 F 0 ⊆ i = 1 \mathcal F_{0\subseteq i} = 1 F 0 ⊆ i = 1 F i ⊆ e i = A \mathcal F_{i\subseteq e_i} = A F i ⊆ e i = A Ric F ( e i ) = 1 + A 2 − 3 ≥ 0 \operatorname{Ric}_{\mathcal F}(e_i) = 1 + A^2 - 3 \ge0 Ric F ( e i ) = 1 + A 2 − 3 ≥ 0 A ≥ 2 A \ge\sqrt{2} A ≥ 2 P 0 = 1 P_0 = 1 P 0 = 1 P i = A P_i = A P i = A R \mathbb R R − 1 -1 − 1
The following example instead considers a combinatorial 2 2 2
Example 5.3 (Negative Ric \operatorname{Ric} Ric Ric F \operatorname{Ric}_{\mathcal F} Ric F 2 2 2 M M M F \mathcal F F Ric < 0 \operatorname{Ric} < 0 Ric < 0 M M M Ric F ≻ 0 \operatorname{Ric}_{\mathcal F} \succ0 Ric F ≻ 0 M M M M M M v 0 , … , v 6 v_0,\ldots,v_6 v 0 , … , v 6 A A A B B B [ v i , v i + 1 , A ] [v_i,v_{i+1},A] [ v i , v i + 1 , A ] [ v i , v i + 1 , B ] [v_i,v_{i+1},B] [ v i , v i + 1 , B ] Ric ( [ u , v ] ) = 10 − deg ( u ) − deg ( v ) \operatorname{Ric}([u,v]) = 10-\deg(u)-\deg(v) Ric ([ u , v ]) = 10 − deg ( u ) − deg ( v ) + 2 +2 + 2 − 1 -1 − 1
For F \mathcal{F} F q q q F v ⊴ e : = q w \mathcal{F}_{v\trianglelefteq e}:=q_w F v ⊴ e := q w w w w e e e F e ⊴ t : = q z \mathcal{F}_{e\trianglelefteq t}:=q_z F e ⊴ t := q z z z z t t t e e e Ric F \operatorname{Ric}_{\mathcal{F}} Ric F
Ric F ( e ) = q u 2 + q v 2 + q z 1 2 + q z 2 2 − ∑ e ~ ∥ e q x q y , (21) \operatorname{Ric}_{\mathcal{F}}(e)=q_u^2+q_v^2+q_{z_1}^2+q_{z_2}^2-\sum_{\widetilde e\parallel e}q_xq_y, \tag*{(21)} Ric F ( e ) = q u 2 + q v 2 + q z 1 2 + q z 2 2 − e ∥ e ∑ q x q y , (21) with e = [ w , x ] e=[w,x] e = [ w , x ] e ~ = [ w , y ] \widetilde e=[w,y] e = [ w , y ] z 1 , z 2 z_1,z_2 z 1 , z 2 e e e q q q [ v i , A ] [v_i,A] [ v i , A ] [ v i , B ] [v_i,B] [ v i , B ] v i v_i v i [ v j , A ] [v_j,A] [ v j , A ] j ≠ i , i ± 1 j\ne i,i\pm1 j = i , i ± 1 A A A [ v i , v i + 1 ] [v_i,v_{i+1}] [ v i , v i + 1 ] [ v i − 1 , v i ] [v_{i-1},v_i] [ v i − 1 , v i ] [ v i + 1 , v i + 2 ] [v_{i+1},v_{i+2}] [ v i + 1 , v i + 2 ] ( q v 0 , … , q v 6 ) = ( 1 , 6 , 11 , 8 , 11 , 6 , 1 ) (q_{v_0},\ldots,q_{v_6})=(1,6,11,8,11,6,1) ( q v 0 , … , q v 6 ) = ( 1 , 6 , 11 , 8 , 11 , 6 , 1 ) q A = q B = 3 q_A=q_B=3 q A = q B = 3
Table 5.1.
Every entry is strictly positive, so Ric F ≻ 0 \operatorname{Ric}_{\mathcal{F}}\succ0 Ric F ≻ 0 Ric = − 1 \operatorname{Ric}=-1 Ric = − 1
Dynamical Interpretation and Applications to Sheaf Neural Networks
With both terms characterized, the decomposition admits a dynamical reading, in which sheaf diffusion can be seen as a reaction-diffusion process, and each term yields a computable quantity at every node: the conviction and the relative volume. We then apply this machinery to Sheaf Neural Networks [19 , 20 ] , which learn a sheaf diffusion on a graph parametrically, and we characterize their behaviour using these quantities.
A dynamical reading
The decomposition H k F = B k F + F k F H_k^F = B_k^F + F_k^F H k F = B k F + F k F [28 ] : the Bochner term is diffusive, driving the random walk of § 4.3 on the S d − 1 \mathbb{S}^{d-1} S d − 1
Opinion dynamics. At k = 0 k = 0 k = 0 L F = B F + F F L_F = B_F + F_F L F = B F + F F [15 ] . The Bochner term drives agents toward equilibria of equal stalk norm, the shared value we call conviction : how strongly an opinion is held. The Forman block ( F F ) v v (F_F)_{vv} ( F F ) v v v v v relative volume : how loudly v v v
If F F ≻ 0 F_F \succ0 F F ≻ 0 ker ( L F ) = { 0 } \ker(L_F) = \{0\} ker ( L F ) = { 0 } F F ⪰ 0 F_F \succeq0 F F ⪰ 0 B F B_F B F F F F_F F F ker ( L F ) = ker ( B F ) ∩ ker ( F F ) \ker(L_F) = \ker(B_F) \cap\ker(F_F) ker ( L F ) = ker ( B F ) ∩ ker ( F F ) ( F v ⊴ e x v = F u ⊴ e x u ) (F_{v\trianglelefteq e}x_v = F_{u\trianglelefteq e}x_u) ( F v ⊴ e x v = F u ⊴ e x u )
Each term therefore yields a quantity measurable on a trained Sheaf Neural Network. Through the Bochner term we observe the signal : how the conviction of each node varies along the diffusion, and how far from equal it remains at equilibrium. Through the Forman term we observe the operator that propagates it: the reactive block at each node, its relative volume, read from the restriction maps.
Sections 6.3 and 6.4 develop each in turn on Sheaf Neural Networks, where the sheaf is learnt from data: the conviction identifies the nodes a trained network relies on, and the Forman profile tracks how the learning mechanism navigates the sheaf space.
Sheaf Neural Networks
A Sheaf Neural Network learns the sheaf from data and unrolls a discretized sheaf diffusion as a network layer [19 , 20 ] . Writing X t ∈ R n × f t X_t \in\mathbb{R}^{n \times f_t} X t ∈ R n × f t Δ F = D F − 1 / 2 L F D F − 1 / 2 \Delta_F = D_F^{-1/2}L_FD_F^{-1/2} Δ F = D F − 1/2 L F D F − 1/2 D F D_F D F L F L_F L F
X t + 1 = X t − ζ ( Δ F ( t ) ( I n ⊗ W 1 ) X t W 2 ) , (22) X_{t+1} = X_t - \zeta\left(\Delta_F^{(t)}\left(I_n \otimes W_1\right)X_tW_2\right), \tag*{(22)} X t + 1 = X t − ζ ( Δ F ( t ) ( I n ⊗ W 1 ) X t W 2 ) , (22) with W 1 W_1 W 1 W 2 W_2 W 2 ζ \zeta ζ t t t F v ⊴ e ( t ) = ζ ( Θ [ x v ( t ) ∣ x u ( t ) ] ) F_{v\trianglelefteq e}^{(t)} = \zeta\left(\Theta[x_v^{(t)} \mid x_u^{(t)}]\right) F v ⊴ e ( t ) = ζ ( Θ [ x v ( t ) ∣ x u ( t ) ] ) Θ \Theta Θ
On heterophilic graphs, where adjacent nodes tend to carry different labels, the harmonic space of the graph Laplacian can provably fail to separate the classes in the infinite-depth limit; asymmetric and sign-changing restriction maps restore separation power, and d > 1 d > 1 d > 1 [20 ] . The available theory consists of convergence results identifying the equilibria of sheaf diffusion and of a universal approximation result, by which a network can learn any sheaf on a graph. Both describe what the model can represent . Neither describes what the learning mechanism does : which region of the sheaf space a training pipeline reaches, and whether different pipelines are biased toward different regions. The conviction and the Forman profile are computable on a trained network, and Sections 6.3 and 6.4 test whether what they measure is informative.
Experimental setting. We train on ten node classification benchmarks: Amazon Ratings, Minesweeper, Questions, Roman Empire and Tolokers [67 ] , Cora, Citeseer and Pubmed [68 ] , and Cornell and Wisconsin [69 , 70 ] . We report test accuracy, and ROC-AUC on the three binary tasks, Minesweeper, Tolokers and Questions, under 10-fold cross-validation, with stalk dimension and depth chosen per dataset. Cornell and Wisconsin are left out of the aggregation of § 6.3 , their training pools being too small for a percentage budget, so the numbers there are over the remaining eight datasets. In the body we report the GeneralSheaf learner, which produces unconstrained d × d d \times d d × d § 14 .§ 1 , and the other learners and regimes, the full metric battery and the per-dataset breakdowns in Appendices D and C.
Conviction analysis for SNNs
Definition 6.1 (Conviction). At diffusion layer t t t u u u X t [ u ] ∈ R d × f t X_t[u] \in\mathbb{R}^{d \times f_t} X t [ u ] ∈ R d × f t d d d f t f_t f t c t ( u ) : = ∥ X t [ u ] ∥ F c_t(u) := \lVert X_t[u] \rVert_F c t ( u ) := ∥ X t [ u ] ∥ F
The theory of § 4 is stated for a single vector in R d \mathbb{R}^{d} R d f t f_t f t § 13 .§ 3 .
Comparisons with other node statistics are in Appendix § 13 .§ 2 . Here we test whether the conviction is an importance score , that is, whether the nodes it ranks highest are those a trained network relies on. We train the network, record the conviction at the best-validation epoch, freeze the weights, perturb a selected set of training nodes, and re-evaluate. Nothing is retrained, so any change is attributable to the perturbation and not to a different optimization trajectory. We use three perturbation modes: masking sets the input features of the selected nodes to zero, gating multiplies their outgoing messages by zero and leaves their self-term intact, and pruning deletes them with their incident edges.
We compare nine selections of nodes: high and low conviction, high and low degree, high and low confidence, two degree-matched controls, which are random sets reproducing the degree distribution of the high- and low-conviction groups, and a uniformly random set. For each dataset we measure the drop in performance relative to the baseline’s headroom above chance (Appendix § 13 .§ 1 ), and we then average over datasets (Table 1, for masking). The full protocol is in Appendix § 13 .§ 1 , and the per-dataset results are in Appendix § 13 .§ 4 .
Table 1. Relative drop in performance (%) under zero masking, by selection strategy and budget. Mean± s . e . _{\pm\mathrm{s.e.}} ± s.e.
Conviction measures node importance with respect to performance. Removing the highest-conviction nodes is the most damaging intervention at every budget, and removing the lowest-conviction ones the least. At the 10% budget of Table 1 the top costs 2.18 ± 0.70%, the bottom 0.07 ± 0.07%, a random set 0.43 ± 0.29%, and a selection by degree 1.06 ± 0.40%. Low-conviction nodes are thus more likely than an arbitrary node of the same graph, which is the comparison of interest for applications. We obtain the same pattern for the other perturbation modes, as shown in Appendix § 13 .§ 3 .
The conviction is a graded score. In a decile experiment (Appendix § 13 .§ 3 ) the training pool is split into ten equal bins by conviction, and one bin is perturbed at a time. The damage stays close to zero over the bottom four bins and rises steadily from the fifth onward. From the bottom to the top decile, the damage goes from 0.07% to 2.18% for conviction, against 0.35% to 0.92% for confidence and 0.38% to 1.06% for degree. The conviction therefore grades how much each node matters, beyond separating the nodes to remove from the others. After this analysis of node importance, we believe the conviction could serve future and more extensive work on Sheaf Neural Networks, on their interpretability and explainability, and on their compression.
The Forman profile
The Forman term is block diagonal (§ 3 ), each block computed from the restriction maps at one node, so its spectrum describes the learnt operator node by node. We use it to track how a Sheaf Neural Network moves through the space of sheaves on a graph: any sheaf can be learnt [20 ] , but which sheaves training actually reaches, and whether it favours some regions of the sheaf space, is open. Moreover, a second motivation comes from the implementation: the sheaf is re-estimated at every layer, so the network can be seen as running a geometric flow [71 ] on the sheaf, and the descriptor should follow it across epochs and across layers.
Definition 6.2 (Forman profile). Let F \mathcal{F} F d d d n n n u u u λ 1 ( u ) ≤ ⋯ ≤ λ d ( u ) \lambda_1(u) \le\cdots\le\lambda_d(u) λ 1 ( u ) ≤ ⋯ ≤ λ d ( u ) ( F F ) u u (F_{\mathcal{F}})_{uu} ( F F ) uu F \mathcal{F} F f ( F ) = ( λ k ( u ) ) u ≤ n , k ≤ d ∈ R n × d f(\mathcal{F}) = \left(\lambda_k(u)\right)_{u \le n, k \le d} \in\mathbb{R}^{n \times d} f ( F ) = ( λ k ( u ) ) u ≤ n , k ≤ d ∈ R n × d k k k k k k
Compared with the spectrum of the whole Laplacian, the Forman profile is local and cheap: it takes n n n d × d d \times d d × d n d nd n d § 6.1 ) and as the term controlling the harmonic space under nonnegativity (§ 5 ). We are interested in comparing the learnt profiles with two references. The topological reference is the profile of the trivial sheaf under the normalized graph Laplacian, and depends on the graph alone; the zero reference is the profile of the unnormalized graph Laplacian, which vanishes identically (§ 3 ). We call closeness to the topological reference local alignment .
We report the 1-Wasserstein distance W 1 W_1 W 1 § 14 .§ 1 . Spearman, Pearson and NRMSE agree with W 1 W_1 W 1 L L L Table 20 –Table 22 (Appendix § 14 .§ 4 ). The untrained checkpoint, where the sheaf is randomly initialized, is the control.
Table 20. Normalized GeneralSheaf on Roman Empire, d = 5 d=5 d = 5
Table 22. Unnormalized JointSheafParams on Questions, d = 5 d = 5 d = 5
General (normalized) sheaf learning aligns with the normalized graph Laplacian. The learnt profile moves toward the topological reference along both axes of Table 2 , with epochs and with depth. At initialization it sits at W 1 ≃ 0.41 W_1 \simeq0.41 W 1 ≃ 0.41 0.253 ± 0.056 0.253 \pm0.056 0.253 ± 0.056 0.339 ± 0.059 0.339 \pm0.059 0.339 ± 0.059 learning . Node by node, the learnt sheaf and the normalized Laplacian have similar Forman profiles, so at the end of training the relative volume of each node resembles that of the normalized Laplacian. This holds on most datasets, with the exceptions discussed below.
Table 2. 1-Wasserstein distance between the Forman profile of the learnt normalized GeneralSheaf and the topological reference, by training epoch (rows; 0 is the untrained sheaf) and relative depth of the layer (columns). Darker cells are farther from the reference: the distance shrinks with training and with depth. Mean± s . e . _{\pm\mathrm{s.e.}} ± s.e. L = 2 L = 2 L = 2
Each learning mechanism has its own bias. We repeat the analysis for the unnormalized sheaf Laplacian and for Joint Sheaf Diffusion [29 ] , normalized and unnormalized (Appendix § 14 .§ 3 ). The unnormalized Laplacian matches neither the zero nor the topological reference; unnormalized joint diffusion diverges in the first epochs and middle layers, and recovers towards the end; normalized joint diffusion diverges from both references as layers and epochs increase. The Forman profile therefore distinguishes how each mechanism moves through the sheaf space.
The learnt maps stay away from the identity. To see whether the learnt maps are identity-like, we evaluate the Forman profile of their unnormalized Laplacian, the maps having been trained with the normalized one, and, conversely, the normalized profile of maps trained without normalization (Appendix § 14 .§ 2 ). In the first case the profile stays far from the zero reference (Table 14 and Table 15 in Appendix § 14 .§ 3 ). Locally the learnt maps act as the normalized Laplacian does, yet they can still differ from the identity sheaf, retaining features such as signs and transport.
Table 14. W 1 W_1 W 1
Table 15. W 1 W_1 W 1
Relation to representation degeneracy. The representation degeneracy reading of oversmoothing in Sheaf Neural Networks [43 ] argues, from performance analysis, that the optimizer is drawn towards a trivial subrepresentation of the learnt sheaf, without measuring the operator itself. Measuring it directly, we see local alignment with the topological reference while the maps stay away from the identity, in networks with few layers, far from oversmoothing; we interpret this as an inductive bias towards one region of the sheaf space. This may also explain why identity sheaves perform similarly to general ones [44 ] : general sheaves align locally with the normalized Laplacian, and so resemble normalized identity sheaves. Global features of the maps, which our lens does not see, may be what separates the two.
Exceptions. Minesweeper, Tolokers and Questions do not follow this pattern. None of the three loses task performance, with ROC-AUC 0.955 ± 0.006 0.955 \pm0.006 0.955 ± 0.006 0.854 ± 0.007 0.854 \pm0.007 0.854 ± 0.007 0.767 ± 0.014 0.767 \pm0.014 0.767 ± 0.014
Limits. Our aim was to test whether the Forman profile is a relevant characteristic of sheaf diffusion in real systems, and Sheaf Neural Networks are the setting in which we tested it. The analysis above already relates the profile to the learning mechanism, to normalization and to training; how the structure of the graph and that of its features shape it, which the exceptions above point to, will require a further analysis, for instance on synthetic benchmarks adapted to sheaves, which we expect to flow into a machine-learning study of the interpretability and explainability of Sheaf Neural Networks. The descriptor is also local: it sees only the relative magnitude, or volume, of the restriction maps, and misses their global features. At d = 1 d = 1 d = 1 [72 ] , could complement it once spectral sheaf theory is further developed.
Conclusion and Open Problems
In this work we introduced a Bochner decomposition for cellular sheaves, splitting a sheaf Laplacian into a positive semidefinite term, the Bochner sheaf Laplacian, and a block diagonal term, the Forman curvature, and we used it to answer a spectral, a probabilistic and a combinatorial question. The Bochner term belongs to the class of Bochner matrices, which contains connection Laplacians, matrix-weighted Laplacians and signed graphs. For this class we characterized the kernel by holonomy, proved Cheeger inequalities extending those of Bandeira, Singer and Spielman, with constants measuring the anisotropy, and attached a random walk on V × S d − 1 V \times S^{d-1} V × S d − 1
Both terms also yield a quantity that can be measured on a trained model, the conviction and the Forman profile, which we derived from the theory and then tested on a real system, Sheaf Neural Networks. The conviction is a score of node importance: removing high-conviction nodes is the most damaging intervention in every perturbation mode, removing low-conviction nodes costs less than removing arbitrary ones, a degree-matched control rules out connectivity as the explanation, and the damage grows steadily with the conviction rank. The Forman profile tracks how a learning mechanism moves through the sheaf space, and each mechanism leaves its own signature: normalized general sheaf learning aligns locally with the normalized graph Laplacian while its maps stay away from the identity, which we interpret as an inductive bias towards one region of the sheaf space. A systematic investigation of both, from the standpoint of machine-learning interpretability and explainability, is left for future work: of the role of the relationship between the structure of the graph and its features, of whether these mechanisms vary across more recent sheaf architectures [73 , 74 ] , and of the extension of our metrics, which assume a constant stalk dimension d d d [75 ] .
Several questions remain open. On the theoretical side, other techniques could sharpen the constants of the Cheeger inequalities, and relating the mixing time of the anisotropic random walk to the frustration constants of § 4.2 is left for future work. Since Bochner matrices carry a random walk, we believe a Bakry–Émery curvature can be built for them, as it has been for connection Laplacians [36 ] . Our framework also opens the possibility of carrying the dynamical processes recently studied on connection Laplacians, such as synchronization and Turing patterns [32 , 33 , 34 ] , to the anisotropic setting, which we regard as one of the most promising directions.
On the empirical side, we believe the conviction and the Forman profile could become tools for the interpretability of Sheaf Neural Networks, and for compressing or sparsifying the graphs they operate on. The Forman profile could also be complemented by a global, spectral descriptor, once spectral sheaf theory supplies one, such as the entropic susceptibility [72 ] , which detects the characteristic scales of diffusion on a network. Finally, the fact that every sheaf Laplacian is a Bochner Laplacian plus a block diagonal term may itself be put to work, inside Sheaf Neural Networks or to build new classes of sheaves.
Acknowledgements
F.M.G. carried out this work as his Master’s thesis at EPFL, while visiting the University of Cambridge, and acknowledges the support of the ELSA Mobility Program. The authors are grateful to Kathryn Hess Bellwald for supervising F.M.G.’s Master’s thesis at EPFL, from which this work originates. The authors also thank Ferran Hernandez Caralt for useful discussions and insights on joint sheaf diffusion.
Code availability
Our experiments build on the original implementation of Neural Sheaf Diffusion by Bodnar et al. [20 ] , https://github.com/twitter-research/neural-sheaf-diffusion , which we modified to extract the conviction and the Forman profile. The full code will be made available upon acceptance of the manuscript.
Additional Proofs
This appendix collects the proofs that do not sit inline with their statement: either because they are longer, or because the technique carries over unchanged from prior work and reads better collected in one place, without interrupting the results above. Each result is restated before its proof.
Proposition 4.2 (Kernel and holonomy). Let B B B γ : v 0 → ⋯ → v k \gamma: v_0 \to\cdots\to v_k γ : v 0 → ⋯ → v k T γ : = W v k − 1 v k ⋯ W v 0 v 1 ∈ O ( d ) T_\gamma:= W_{v_{k-1}v_k} \cdots W_{v_0v_1} \in O(d) T γ := W v k − 1 v k ⋯ W v 0 v 1 ∈ O ( d ) dim ker ( B ) ≤ d \dim\ker(B) \le d dim ker ( B ) ≤ d T γ = I T_\gamma= I T γ = I γ \gamma γ
Proof. The evaluation map φ v : ker ( B ) → R d \varphi_v : \ker(B) \to\mathbb{R}^{d} φ v : ker ( B ) → R d x ↦ x v x \mapsto x_v x ↦ x v x v = 0 x_v = 0 x v = 0 x u = 0 x_u = 0 x u = 0 x = 0 x = 0 x = 0 dim ker ( B ) ≤ d \dim\ker(B) \le d dim ker ( B ) ≤ d
If the transport maps are path independent, fix v v v α ∈ R d \alpha\in\mathbb{R}^{d} α ∈ R d x u : = T γ α x_u := T_\gamma\alpha x u := T γ α γ \gamma γ v v v u u u ( w 1 , w 2 ) (w_1,w_2) ( w 1 , w 2 ) w 1 w_1 w 1 x w 2 = W w 1 w 2 x w 1 x_{w_2} = W_{w_1w_2}x_{w_1} x w 2 = W w 1 w 2 x w 1 x ∈ ker ( B ) x \in\ker(B) x ∈ ker ( B ) φ v \varphi_v φ v dim ker ( B ) = d \dim\ker(B) = d dim ker ( B ) = d φ v \varphi_v φ v α \alpha α x ∈ ker ( B ) x \in\ker(B) x ∈ ker ( B ) x w = T γ α x_w = T_\gamma\alpha x w = T γ α γ \gamma γ v v v w w w T γ α = T γ ′ α T_\gamma\alpha= T_{\gamma'}\alpha T γ α = T γ ′ α α \alpha α T γ = T γ ′ T_\gamma= T_{\gamma'} T γ = T γ ′ T γ = I T_\gamma= I T γ = I
The proofs of § 4.2 use the following notation.
Table 1 (PDF p. 26).
Auxiliary lemmas for § 4.2 . We record three facts used throughout the Cheeger proofs, all resting on the Courant–Fischer characterization:
λ k ( B ~ ) = min dim S = k max 0 ≠ x ∈ S η ( x ) , in particular λ 1 ( B ~ ) = min x ≠ 0 η ( x ) , (23) \lambda_k(\widetilde B) = \min_{\dim S=k}\max_{0\ne x\in S}\eta(x), \qquad\text{in particular}\qquad\lambda_1(\widetilde B) = \min_{x\ne0}\eta(x), \tag*{(23)} λ k ( B ) = d i m S = k min 0 = x ∈ S max η ( x ) , in particular λ 1 ( B ) = x = 0 min η ( x ) , (23) which follows from the substitution y = D 1 / 2 x y = D^{1/2}x y = D 1/2 x η \eta η B ~ \widetilde B B compression bound : for symmetric A ∈ R N × N A \in\mathbb{R}^{N\times N} A ∈ R N × N Q ∈ R N × k Q \in\mathbb{R}^{N\times k} Q ∈ R N × k λ i ( Q ⊤ A Q ) ≥ λ i ( A ) \lambda_i(Q^\top AQ) \ge\lambda_i(A) λ i ( Q ⊤ A Q ) ≥ λ i ( A ) i ≤ k i \le k i ≤ k tr ( Q ⊤ A Q ) ≥ ∑ i ≤ k λ i ( A ) \operatorname{tr}(Q^\top AQ) \ge\sum_{i\le k}\lambda_i(A) tr ( Q ⊤ A Q ) ≥ ∑ i ≤ k λ i ( A ) λ i ( Q ⊤ A Q ) \lambda_i(Q^\top AQ) λ i ( Q ⊤ A Q ) i i i S ⊆ R k S \subseteq\mathbb{R}^k S ⊆ R k Q Q Q i i i Q S ⊆ R N QS \subseteq\mathbb{R}^N QS ⊆ R N λ i ( Q ⊤ A Q ) \lambda_i(Q^\top AQ) λ i ( Q ⊤ A Q ) λ i ( A ) \lambda_i(A) λ i ( A ) comparison toolkit . We write D ˉ 0 : = diag ( d ˉ v ) \bar D_0 := \operatorname{diag}(\bar d_v) D ˉ 0 := diag ( d ˉ v ) G − G_- G − vol : = ∑ v d ˉ v \operatorname{vol} := \sum_v \bar d_v vol := ∑ v d ˉ v v , u ∈ V v,u \in V v , u ∈ V z ∈ R d z \in\mathbb{R}^{d} z ∈ R d x ∈ R n d x \in\mathbb{R}^{nd} x ∈ R n d
(i) d ˉ v − ≤ λ min ( D v ) ≤ λ max ( D v ) ≤ d ˉ v + ≤ κ E d ˉ v − \bar d_v^- \le\lambda_{\min}(D_v) \le\lambda_{\max}(D_v) \le\bar d_v^+ \le\kappa_E\bar d_v^- d ˉ v − ≤ λ m i n ( D v ) ≤ λ m a x ( D v ) ≤ d ˉ v + ≤ κ E d ˉ v − κ D ≤ κ E \kappa_D \le\kappa_E κ D ≤ κ E
(ii) ∥ n x ∥ D ˉ 0 − 2 ≤ x ⊤ D x ≤ κ E ∥ n x ∥ D ˉ 0 − 2 \lVert n_x\rVert_{\bar D_0^-}^2 \le x^\top Dx \le\kappa_E\lVert n_x\rVert_{\bar D_0^-}^2 ∥ n x ∥ D ˉ 0 − 2 ≤ x ⊤ D x ≤ κ E ∥ n x ∥ D ˉ 0 − 2
(iii) w v u − ∥ z ∥ 2 ≤ ∥ z ∥ M v u 2 ≤ w v u + ∥ z ∥ 2 w_{vu}^-\lVert z\rVert^2 \le\lVert z\rVert_{M_{vu}}^2 \le w_{vu}^+\lVert z\rVert^2 w v u − ∥ z ∥ 2 ≤ ∥ z ∥ M v u 2 ≤ w v u + ∥ z ∥ 2
(iv) n x ⊤ L − n x ≤ x ⊤ B x n_x^\top L_-n_x \le x^\top Bx n x ⊤ L − n x ≤ x ⊤ B x λ min , λ max \lambda_{\min},\lambda_{\max} λ m i n , λ m a x D v = ∑ u M v u D_v=\sum_{u}M_{vu} D v = ∑ u M v u ∥ x v − W v u T x u ∥ M v u , F 2 ≥ w v u ( ∥ x v ∥ − ∥ x u ∥ ) 2 \lVert x_v-W_{vu}^{\mathsf T}x_u\rVert_{M_{vu},F}^2\ge w_{vu}(\lVert x_v\rVert-\lVert x_u\rVert)^2 ∥ x v − W v u T x u ∥ M v u , F 2 ≥ w v u (∥ x v ∥ − ∥ x u ∥ ) 2 columnwise dictionary : for X : V → R d × d X:V\to\mathbb{R}^{d\times d} X : V → R d × d k = 1 , … , d k=1,\ldots,d k = 1 , … , d x v k : = X v e k ∈ R d x_v^k:=X_ve_k\in\mathbb{R}^d x v k := X v e k ∈ R d k k k X v X_v X v e k e_k e k k k k R d \mathbb{R}^d R d x k ∈ R n d x^k\in\mathbb{R}^{nd} x k ∈ R n d
1 2 ∑ v ≠ u ∥ X v − W v u T X u ∥ M v u , F 2 = ∑ k ≤ d ( x k ) T B x k , (24) \frac{1}{2}\sum_{v\ne u}\lVert X_v-W_{vu}^{\mathsf T}X_u\rVert_{M_{vu},F}^2=\sum_{k\le d}(x^k)^{\mathsf T}Bx^k, \tag*{(24)} 2 1 v = u ∑ ∥ X v − W v u T X u ∥ M v u , F 2 = k ≤ d ∑ ( x k ) T B x k , (24) and if X X X ∑ k ( x k ) T D x k = vol ( G ) \sum_k(x^k)^{\mathsf T}Dx^k=\operatorname{vol}(G) ∑ k ( x k ) T D x k = vol ( G ) ∥ A ∥ M , F 2 = ∑ k ∥ A e k ∥ M 2 \lVert A\rVert_{M,F}^2=\sum_k\lVert Ae_k\rVert_M^2 ∥ A ∥ M , F 2 = ∑ k ∥ A e k ∥ M 2 g v g v T = I g_vg_v^{\mathsf T}=I g v g v T = I
Proposition 4.3 (Relaxation). (a) λ 1 ( B ~ ) ≤ η G ∗ ≤ η G \lambda_1(\widetilde{B})\le\eta_G^\ast\le\eta_G λ 1 ( B ) ≤ η G ∗ ≤ η G λ 1 ( B ~ ) ≤ ν G \lambda_1(\widetilde{B})\le\nu_G λ 1 ( B ) ≤ ν G 1 d κ D ∑ k ≤ d λ k ( B ~ ) ≤ ν G \frac{1}{d\kappa_D}\sum_{k\le d}\lambda_k(\widetilde{B})\le\nu_G d κ D 1 ∑ k ≤ d λ k ( B ) ≤ ν G
Proof. (a) By (A.1), λ 1 ( B ~ ) = min x ≠ 0 η ( x ) \lambda_1(\widetilde{B})=\min_{x\ne0}\eta(x) λ 1 ( B ) = min x = 0 η ( x ) η \eta η R n d ∖ { 0 } \mathbb{R}^{nd}\setminus\{0\} R n d ∖ { 0 } S d − 1 \mathbb{S}^{d-1} S d − 1 η G ∗ \eta_G^\ast η G ∗
For (b) and (c), fix g : V → O ( d ) g:V\to O(d) g : V → O ( d ) x k x^k x k y k : = D 1 / 2 x k y^k:=D^{1/2}x^k y k := D 1/2 x k Y : = [ y 1 ⋯ y d ] Y:=[y^1\ \cdots\ y^d] Y := [ y 1 ⋯ y d ] ( x k ) T B x k = ( y k ) T B ~ y k (x^k)^{\mathsf T}Bx^k=(y^k)^{\mathsf T}\widetilde{B}y^k ( x k ) T B x k = ( y k ) T B y k ( x k ) T D x k = ∥ y k ∥ 2 (x^k)^{\mathsf T}Dx^k=\lVert y^k\rVert^2 ( x k ) T D x k = ∥ y k ∥ 2 ν ( g ) = tr ( Y T B ~ Y ) / tr ( Y T Y ) \nu(g)=\operatorname{tr}(Y^{\mathsf T}\widetilde{B}Y)/\operatorname{tr}(Y^{\mathsf T}Y) ν ( g ) = tr ( Y T B Y ) / tr ( Y T Y )
Y Y Y d d d Y c = 0 Yc=0 Y c = 0 ∑ k c k x k = 0 \sum_kc_kx^k=0 ∑ k c k x k = 0 g v c = 0 g_vc=0 g v c = 0 c = 0 c=0 c = 0 Y = Q R Y=QR Y = QR R R R S : = Q T B ~ Q ⪰ 0 S:=Q^{\mathsf T}\widetilde{B}Q\succeq0 S := Q T B Q ⪰ 0 P : = R R T ≻ 0 P:=RR^{\mathsf T}\succ0 P := R R T ≻ 0 ν ( g ) = tr ( S P ) / tr ( P ) \nu(g)=\operatorname{tr}(SP)/\operatorname{tr}(P) ν ( g ) = tr ( S P ) / tr ( P )
(b) Diagonalizing P = ∑ j p j q j q j T P=\sum_jp_jq_jq_j^{\mathsf T} P = ∑ j p j q j q j T p j > 0 p_j>0 p j > 0 q j q_j q j q j T S q j ≥ λ 1 ( S ) q_j^{\mathsf T}Sq_j\ge\lambda_1(S) q j T S q j ≥ λ 1 ( S ) tr ( S P ) ≥ λ 1 ( S ) tr ( P ) \operatorname{tr}(SP)\ge\lambda_1(S)\operatorname{tr}(P) tr ( S P ) ≥ λ 1 ( S ) tr ( P ) λ 1 ( S ) ≥ λ 1 ( B ~ ) \lambda_1(S)\ge\lambda_1(\widetilde{B}) λ 1 ( S ) ≥ λ 1 ( B ) g g g
(c) Since R R R P = R R T P=RR^{\mathsf T} P = R R T R T R = Y T Y R^{\mathsf T}R=Y^{\mathsf T}Y R T R = Y T Y Y T Y = ∑ v g v T D v g v Y^{\mathsf T}Y=\sum_vg_v^{\mathsf T}D_vg_v Y T Y = ∑ v g v T D v g v g v g_v g v λ min ( D v ) I ⪯ g v T D v g v ⪯ λ max ( D v ) I \lambda_{\min}(D_v)I\preceq g_v^{\mathsf T}D_vg_v\preceq\lambda_{\max}(D_v)I λ m i n ( D v ) I ⪯ g v T D v g v ⪯ λ m a x ( D v ) I v v v a : = ∑ v λ min ( D v ) a:=\sum_v\lambda_{\min}(D_v) a := ∑ v λ m i n ( D v ) b : = ∑ v λ max ( D v ) b:=\sum_v\lambda_{\max}(D_v) b := ∑ v λ m a x ( D v )
a I ⪯ Y T Y ⪯ b I , hence λ min ( P ) ≥ a , λ max ( P ) ≤ b . (25) aI\preceq Y^{\mathsf T}Y\preceq bI,\qquad\text{hence}\qquad\lambda_{\min}(P)\ge a,\quad\lambda_{\max}(P)\le b. \tag*{(25)} a I ⪯ Y T Y ⪯ b I , hence λ m i n ( P ) ≥ a , λ m a x ( P ) ≤ b . (25) The trace of P P P d d d λ max ( P ) \lambda_{\max}(P) λ m a x ( P ) tr ( P ) ≤ d λ max ( P ) ≤ d b \operatorname{tr}(P)\le d\lambda_{\max}(P)\le db tr ( P ) ≤ d λ m a x ( P ) ≤ d b λ max ( D v ) ≤ κ D λ min ( D v ) \lambda_{\max}(D_v)\le\kappa_D\lambda_{\min}(D_v) λ m a x ( D v ) ≤ κ D λ m i n ( D v ) v v v b ≤ κ D a b\le\kappa_Da b ≤ κ D a λ min ( P ) ≥ a ≥ b / κ D ≥ tr ( P ) / ( d κ D ) \lambda_{\min}(P)\ge a\ge b/\kappa_D\ge\operatorname{tr}(P)/(d\kappa_D) λ m i n ( P ) ≥ a ≥ b / κ D ≥ tr ( P ) / ( d κ D ) P = λ min ( P ) I + P ′ P=\lambda_{\min}(P)I+P' P = λ m i n ( P ) I + P ′ P ′ ⪰ 0 P'\succeq0 P ′ ⪰ 0 tr ( S P ′ ) = tr ( S 1 / 2 P ′ S 1 / 2 ) ≥ 0 \operatorname{tr}(SP')=\operatorname{tr}(S^{1/2}P'S^{1/2})\ge0 tr ( S P ′ ) = tr ( S 1/2 P ′ S 1/2 ) ≥ 0
tr ( S P ) ≥ λ min ( P ) tr ( S ) ≥ λ min ( P ) ∑ k ≤ d λ k ( B ~ ) ≥ tr ( P ) d κ D ∑ k ≤ d λ k ( B ~ ) , (26) \operatorname{tr}(SP)\ge\lambda_{\min}(P)\operatorname{tr}(S)\ge\lambda_{\min}(P)\sum_{k\le d}\lambda_k(\widetilde{B})\ge\frac{\operatorname{tr}(P)}{d\kappa_D}\sum_{k\le d}\lambda_k(\widetilde{B}), \tag*{(26)} tr ( S P ) ≥ λ m i n ( P ) tr ( S ) ≥ λ m i n ( P ) k ≤ d ∑ λ k ( B ) ≥ d κ D tr ( P ) k ≤ d ∑ λ k ( B ) , (26) using the compression bound for the middle step. Divide by tr ( P ) \operatorname{tr}(P) tr ( P ) g g g □ \square □
Proposition 4.4 (Zero sets). λ 1 ( B ~ ) = 0 ⟺ ker ( B ) ≠ { 0 } ⟺ η G = 0 ⟺ η G ∗ = 0 \lambda_1(\widetilde{B})=0\Longleftrightarrow\ker(B)\ne\{0\}\Longleftrightarrow\eta_G=0\Longleftrightarrow\eta_G^\ast=0 λ 1 ( B ) = 0 ⟺ ker ( B ) = { 0 } ⟺ η G = 0 ⟺ η G ∗ = 0 ν G = 0 \nu_G=0 ν G = 0
Proof. B ~ = D − 1 / 2 B D − 1 / 2 \widetilde{B}=D^{-1/2}BD^{-1/2} B = D − 1/2 B D − 1/2 D ≻ 0 D\succ0 D ≻ 0 B ~ \widetilde{B} B B B B ker ( B ) ≠ { 0 } \ker(B)\ne\{0\} ker ( B ) = { 0 } 0 ≠ x ∈ ker ( B ) 0\ne x\in\ker(B) 0 = x ∈ ker ( B ) ∥ x v ∥ \lVert x_v\rVert ∥ x v ∥ c > 0 c>0 c > 0 x / c x/c x / c V V V S d − 1 \mathbb{S}^{d-1} S d − 1 η ( x / c ) = 0 \eta(x/c)=0 η ( x / c ) = 0 η G = 0 \eta_G=0 η G = 0 η G ∗ = 0 \eta_G^\ast=0 η G ∗ = 0 η G ∗ = 0 \eta_G^\ast=0 η G ∗ = 0 x ≠ 0 x\ne0 x = 0 S d − 1 \mathbb{S}^{d-1} S d − 1 x v = W v u T x u x_v=W_{vu}^{\mathsf T}x_u x v = W v u T x u S : = { v : x v ≠ 0 } S:=\{v:x_v\ne0\} S := { v : x v = 0 } v ∈ S v\in S v ∈ S u ∉ S u\notin S u ∈ / S x v = W v u T ⋅ 0 = 0 x_v=W_{vu}^{\mathsf T}\cdot0=0 x v = W v u T ⋅ 0 = 0 S = V S=V S = V x ∈ ker ( B ) x\in\ker(B) x ∈ ker ( B )
For the last claim, the columnwise dictionary gives ν ( g ) = 0 \nu(g)=0 ν ( g ) = 0 g g g ker ( B ) \ker(B) ker ( B ) g u = W v u g v g_u=W_{vu}g_v g u = W v u g v g g g dim ker ( B ) = d \dim\ker(B)=d dim ker ( B ) = d □ \square □
Theorem 4.2 (Partial synchronization). λ 1 ( B ~ ) ≤ η G ∗ ≤ κ E 3 / 2 10 λ 1 ( B ~ ) \lambda_1(\widetilde{B}) \le\eta_G^* \le\kappa_E^{3/2}\sqrt{10\lambda_1(\widetilde{B})} λ 1 ( B ) ≤ η G ∗ ≤ κ E 3/2 10 λ 1 ( B )
The lower bound is Proposition 4.3(a). For the upper bound we take an eigenvector for λ 1 ( B ~ ) \lambda_1(\widetilde{B}) λ 1 ( B ) M M M Lemma A ), its consequence on one edge (Lemma B ), the sum over the graph in an ℓ 1 \ell^1 ℓ 1 Lemma C ), and the passage back to the quotient η \eta η W v u T W_{vu}^{\mathsf{T}} W v u T W v u T ( x v t ) = ( W v u T x u ) t W_{vu}^{\mathsf{T}}(x_v^t)=(W_{vu}^{\mathsf{T}}x_u)^t W v u T ( x v t ) = ( W v u T x u ) t
Lemma A (Weighted normalization inequality). Let M ≻ 0 M \succ0 M ≻ 0 κ ( M ) : = λ max ( M ) / λ min ( M ) \kappa(M):=\lambda_{\max}(M)/\lambda_{\min}(M) κ ( M ) := λ m a x ( M ) / λ m i n ( M ) y , z ∈ R d y,z\in\mathbb{R}^d y , z ∈ R d α ≥ 1 \alpha\ge1 α ≥ 1
∥ z − y ∥ M + ( α 2 − 1 ) ∥ z ∥ M ≤ 5 2 κ ( M ) ∥ α z − y ∥ M ( 1 + α ) . (27) \lVert z-y\rVert_M+(\alpha^2-1)\lVert z\rVert_M\le\frac{\sqrt{5}}{2}\sqrt{\kappa(M)}\lVert\alpha z-y\rVert_M(1+\alpha). \tag*{(27)} ∥ z − y ∥ M + ( α 2 − 1 ) ∥ z ∥ M ≤ 2 5 κ ( M ) ∥ α z − y ∥ M ( 1 + α ) . (27) Proof. The three inequalities below use, in turn, ∥ z ∥ = 1 \lVert z\rVert=1 ∥ z ∥ = 1 ∥ z − y ∥ + α 2 − 1 ≤ 5 2 ∥ α z − y ∥ ( 1 + α ) \lVert z-y\rVert+\alpha^2-1\le\frac{\sqrt{5}}{2}\lVert\alpha z-y\rVert(1+\alpha) ∥ z − y ∥ + α 2 − 1 ≤ 2 5 ∥ α z − y ∥ ( 1 + α ) [22 ] , and the lower Rayleigh bound ∥ α z − y ∥ ≤ λ min ( M ) − 1 / 2 ∥ α z − y ∥ M \lVert\alpha z-y\rVert\le\lambda_{\min}(M)^{-1/2}\lVert\alpha z-y\rVert_M ∥ α z − y ∥ ≤ λ m i n ( M ) − 1/2 ∥ α z − y ∥ M
∥ z − y ∥ M + ( α 2 − 1 ) ∥ z ∥ M ≤ λ max ( M ) ( ∥ z − y ∥ + α 2 − 1 ) ≤ λ max ( M ) 5 2 ∥ α z − y ∥ ( 1 + α ) ≤ 5 2 κ ( M ) ∥ α z − y ∥ M ( 1 + α ) . (28) \begin{aligned}
\lVert z-y\rVert_M+(\alpha^2-1)\lVert z\rVert_M
&\le\sqrt{\lambda_{\max}(M)}\bigl(\lVert z-y\rVert+\alpha^2-1\bigr)\\
&\le\sqrt{\lambda_{\max}(M)}\frac{\sqrt{5}}{2}\lVert\alpha z-y\rVert(1+\alpha)\\
&\le\frac{\sqrt{5}}{2}\sqrt{\kappa(M)}\lVert\alpha z-y\rVert_M(1+\alpha). \tag*{(28)}
\end{aligned} ∥ z − y ∥ M + ( α 2 − 1 ) ∥ z ∥ M ≤ λ m a x ( M ) ( ∥ z − y ∥ + α 2 − 1 ) ≤ λ m a x ( M ) 2 5 ∥ α z − y ∥ ( 1 + α ) ≤ 2 5 κ ( M ) ∥ α z − y ∥ M ( 1 + α ) . (28) The factor κ ( M ) \sqrt{\kappa(M)} κ ( M ) M = diag ( 1 , ε ) M=\operatorname{diag}(1,\varepsilon) M = diag ( 1 , ε ) α = 2 \alpha=2 α = 2 z = ( 1 2 , 3 2 ) z=(\frac{1}{2},\frac{\sqrt{3}}{2}) z = ( 2 1 , 2 3 ) y = ( 1 , 0 ) y=(1,0) y = ( 1 , 0 ) α z − y = ( 0 , 3 ) \alpha z-y=(0,\sqrt{3}) α z − y = ( 0 , 3 ) ∥ α z − y ∥ M = 3 ε \lVert\alpha z-y\rVert_M=\sqrt{3\varepsilon} ∥ α z − y ∥ M = 3 ε ∥ z − y ∥ M ≥ 1 2 \lVert z-y\rVert_M\ge\frac{1}{2} ∥ z − y ∥ M ≥ 2 1 ∥ z ∥ M ≥ 1 2 \lVert z\rVert_M\ge\frac{1}{2} ∥ z ∥ M ≥ 2 1 2 2 2 M M M M M M α ≠ 1 \alpha\ne1 α = 1
Lemma B (Per-edge estimate). Let x ∈ R n d x\in\mathbb{R}^{nd} x ∈ R n d x v ∈ R d x_v\in\mathbb{R}^d x v ∈ R d max v ∥ x v ∥ = 1 \max_v\lVert x_v\rVert=1 max v ∥ x v ∥ = 1 t t t [ 0 , 1 ] [0,1] [ 0 , 1 ] ( v , u ) (v,u) ( v , u )
E t ∥ x v t − W v u T x u t ∥ M v u ≤ 5 2 κ E ∥ x v − W v u T x u ∥ M v u ( ∥ x v ∥ + ∥ x u ∥ ) . (29) \mathbb{E}_t\left\lVert x_v^t-W_{vu}^{\mathsf{T}}x_u^t\right\rVert_{M_{vu}}\le\frac{\sqrt{5}}{2}\sqrt{\kappa_E}\left\lVert x_v-W_{vu}^{\mathsf{T}}x_u\right\rVert_{M_{vu}}\left(\lVert x_v\rVert+\lVert x_u\rVert\right). \tag*{(29)} E t x v t − W v u T x u t M v u ≤ 2 5 κ E x v − W v u T x u M v u ( ∥ x v ∥ + ∥ x u ∥ ) . (29) Proof. Write M : = M v u M:=M_{vu} M := M v u a : = x v a:=x_v a := x v b : = W v u T x u b:=W_{vu}^{\mathsf{T}}x_u b := W v u T x u ∥ b ∥ = ∥ x u ∥ \lVert b\rVert=\lVert x_u\rVert ∥ b ∥ = ∥ x u ∥ b t = W v u T x u t b^t=W_{vu}^{\mathsf{T}}x_u^t b t = W v u T x u t a a a b b b ∥ b ∥ ≤ ∥ a ∥ \lVert b\rVert\le\lVert a\rVert ∥ b ∥ ≤ ∥ a ∥ b = 0 b=0 b = 0 ∥ a ∥ ∥ a ∥ M \lVert a\rVert\lVert a\rVert_M ∥ a ∥ ∥ a ∥ M 1 1 1 5 2 κ E ≥ 1 \frac{\sqrt{5}}{2}\sqrt{\kappa_E}\ge1 2 5 κ E ≥ 1 0 < ∥ b ∥ ≤ ∥ a ∥ ≤ 1 0<\lVert b\rVert\le\lVert a\rVert\le1 0 < ∥ b ∥ ≤ ∥ a ∥ ≤ 1
z : = a ∥ a ∥ , y : = b ∥ b ∥ , α : = ∥ a ∥ ∥ b ∥ ≥ 1. (30) z:=\frac{a}{\lVert a\rVert},\qquad y:=\frac{b}{\lVert b\rVert},\qquad\alpha:=\frac{\lVert a\rVert}{\lVert b\rVert}\ge1. \tag*{(30)} z := ∥ a ∥ a , y := ∥ b ∥ b , α := ∥ b ∥ ∥ a ∥ ≥ 1. (30) As t t t [ 0 , 1 ] [0,1] [ 0 , 1 ] ∥ b ∥ 2 \lVert b\rVert^2 ∥ b ∥ 2 z − y z-y z − y ∥ a ∥ 2 − ∥ b ∥ 2 \lVert a\rVert^2-\lVert b\rVert^2 ∥ a ∥ 2 − ∥ b ∥ 2 a a a z z z
E t ∥ a t − b t ∥ M = ∥ b ∥ 2 ∥ z − y ∥ M + ( ∥ a ∥ 2 − ∥ b ∥ 2 ) ∥ z ∥ M = ∥ b ∥ 2 [ ∥ z − y ∥ M + ( α 2 − 1 ) ∥ z ∥ M ] . (31) \mathbb{E}_t\left\lVert a^t-b^t\right\rVert_M=\lVert b\rVert^2\lVert z-y\rVert_M+\left(\lVert a\rVert^2-\lVert b\rVert^2\right)\lVert z\rVert_M=\lVert b\rVert^2\left[\lVert z-y\rVert_M+(\alpha^2-1)\lVert z\rVert_M\right]. \tag*{(31)} E t a t − b t M = ∥ b ∥ 2 ∥ z − y ∥ M + ( ∥ a ∥ 2 − ∥ b ∥ 2 ) ∥ z ∥ M = ∥ b ∥ 2 [ ∥ z − y ∥ M + ( α 2 − 1 ) ∥ z ∥ M ] . (31) Lemma A bounds the bracket. Since α z − y = ( a − b ) / ∥ b ∥ \alpha z-y=(a-b)/\lVert b\rVert α z − y = ( a − b ) / ∥ b ∥ 1 + α = ( ∥ a ∥ + ∥ b ∥ ) / ∥ b ∥ 1+\alpha=(\lVert a\rVert+\lVert b\rVert)/\lVert b\rVert 1 + α = (∥ a ∥ + ∥ b ∥) / ∥ b ∥ ∥ b ∥ \lVert b\rVert ∥ b ∥ κ ( M v u ) ≤ κ E \kappa(M_{vu})\le\kappa_E κ ( M v u ) ≤ κ E
Lemma C (Global ℓ 1 \ell^1 ℓ 1 Define:
Φ ( y ) : = ∑ v ≠ u w v u ∥ y v − W v u T y u ∥ M v u ∑ v d v − ∥ y v ∥ . (32) \Phi(y):=\frac{\sum_{v\ne u}\sqrt{w_{vu}}\lVert y_v-W_{vu}^{\mathsf{T}}y_u\rVert_{M_{vu}}}{\sum_v d_v^-\lVert y_v\rVert}. \tag*{(32)} Φ ( y ) := ∑ v d v − ∥ y v ∥ ∑ v = u w v u ∥ y v − W v u T y u ∥ M v u . (32) If max v ∥ x v ∥ = 1 \max_v \lVert x_v\rVert= 1 max v ∥ x v ∥ = 1 t ∈ [ 0 , 1 ) t \in[0,1) t ∈ [ 0 , 1 ) x > t ≠ 0 x^{>t} \ne0 x > t = 0 Φ ( x > t ) ≤ κ E 10 η ( x ) \Phi(x^{>t}) \le\kappa_E\sqrt{10\eta(x)} Φ ( x > t ) ≤ κ E 10 η ( x )
Proof. Multiply Lemma B by w v u \sqrt{w_{vu}} w v u
(A) : = ∥ x v − W v u T x u ∥ M v u and (B) : = w v u ( ∥ x v ∥ + ∥ x u ∥ ) . (33) \text{(A)} := \lVert x_v-W_{vu}^{\mathsf T}x_u\rVert_{M_{vu}} \qquad\text{and}\qquad\text{(B)} := \sqrt{w_{vu}}\left(\lVert x_v\rVert+\lVert x_u\rVert\right). \tag*{(33)} (A) := ∥ x v − W v u T x u ∥ M v u and (B) := w v u ( ∥ x v ∥ + ∥ x u ∥ ) . (33) For the first factor, Lemma 4.1 and item (ii) of the toolkit give:
∑ v ≠ u (A) 2 = 2 x T B x = 2 η ( x ) x T D x ≤ 2 κ E η ( x ) ∥ n x ∥ D 0 2 . (34) \sum_{v\ne u}\text{(A)}^2=2x^{\mathsf T}Bx=2\eta(x)x^{\mathsf T}Dx\le2\kappa_E\eta(x)\lVert n_x\rVert_{D_0}^2. \tag*{(34)} v = u ∑ (A) 2 = 2 x T B x = 2 η ( x ) x T D x ≤ 2 κ E η ( x ) ∥ n x ∥ D 0 2 . (34) For the second, ( p + q ) 2 ≤ 2 ( p 2 + q 2 ) (p+q)^2\le2(p^2+q^2) ( p + q ) 2 ≤ 2 ( p 2 + q 2 ) w v u = w u v w_{vu}=w_{uv} w v u = w uv
∑ v ≠ u (B) 2 ≤ 2 ∑ v ≠ u w v u ( ∥ x v ∥ 2 + ∥ x u ∥ 2 ) = 4 ∑ v d v − ∥ x v ∥ 2 = 4 ∥ n x ∥ D 0 2 . (35) \sum_{v\ne u}\text{(B)}^2\le2\sum_{v\ne u}w_{vu}\left(\lVert x_v\rVert^2+\lVert x_u\rVert^2\right)=4\sum_v d_v^-\lVert x_v\rVert^2=4\lVert n_x\rVert_{D_0}^2. \tag*{(35)} v = u ∑ (B) 2 ≤ 2 v = u ∑ w v u ( ∥ x v ∥ 2 + ∥ x u ∥ 2 ) = 4 v ∑ d v − ∥ x v ∥ 2 = 4 ∥ n x ∥ D 0 2 . (35) Multiplying the two square roots by the constant of Lemma B:
E t [ numerator of Φ ( x > t ) ] ≤ 5 2 κ E ⋅ 2 κ E η ( x ) ∥ n x ∥ D 0 ⋅ 2 ∥ n x ∥ D 0 = κ E 10 η ( x ) ∥ n x ∥ D 0 2 . (36) \mathbb{E}_t[\text{numerator of }\Phi(x^{>t})]\le\frac{\sqrt{5}}{2}\sqrt{\kappa_E}\cdot\sqrt{2\kappa_E\eta(x)}\lVert n_x\rVert_{D_0}\cdot2\lVert n_x\rVert_{D_0}
=\kappa_E\sqrt{10\eta(x)}\lVert n_x\rVert_{D_0}^2. \tag*{(36)} E t [ numerator of Φ ( x > t )] ≤ 2 5 κ E ⋅ 2 κ E η ( x ) ∥ n x ∥ D 0 ⋅ 2 ∥ n x ∥ D 0 = κ E 10 η ( x ) ∥ n x ∥ D 0 2 . (36) For the denominator, ∥ x v > t ∥ ∈ { 0 , 1 } \lVert x_v^{>t}\rVert\in\{0,1\} ∥ x v > t ∥ ∈ { 0 , 1 } x v > t x_v^{>t} x v > t ∥ x v ∥ 2 ≤ 1 \lVert x_v\rVert^2\le1 ∥ x v ∥ 2 ≤ 1 E t ∥ x v > t ∥ = Pr [ t < ∥ x v ∥ ] = ∥ x v ∥ \mathbb{E}_t\lVert x_v^{>t}\rVert=\Pr[t<\lVert x_v\rVert]=\lVert x_v\rVert E t ∥ x v > t ∥ = Pr [ t < ∥ x v ∥] = ∥ x v ∥ Φ ( x > t ) \Phi(x^{>t}) Φ ( x > t ) ∑ v d v − ∥ x v ∥ 2 = ∥ n x ∥ D 0 2 \sum_v d_v^-\lVert x_v\rVert^2=\lVert n_x\rVert_{D_0}^2 ∑ v d v − ∥ x v ∥ 2 = ∥ n x ∥ D 0 2 c : = κ E 10 η ( x ) c:=\kappa_E\sqrt{10\eta(x)} c := κ E 10 η ( x ) E t [ num ( t ) − c den ( t ) ] ≤ 0 \mathbb{E}_t[\operatorname{num}(t)-c\operatorname{den}(t)]\le0 E t [ num ( t ) − c den ( t )] ≤ 0 t t t num ( t ) ≤ c den ( t ) \operatorname{num}(t)\le c\operatorname{den}(t) num ( t ) ≤ c den ( t ) t < 1 t<1 t < 1 ∥ x v ∥ = 1 \lVert x_v\rVert=1 ∥ x v ∥ = 1 x > t ≠ 0 x^{>t}\ne0 x > t = 0
Lemma D (From ℓ 1 \ell^1 ℓ 1 ℓ 2 \ell^2 ℓ 2
Lemma D (From ℓ 1 \ell^1 ℓ 1 ℓ 2 \ell^2 ℓ 2 For every nonzero y : V → S d − 1 ∪ { 0 } y:V\to\mathbb{S}^{d-1}\cup\{0\} y : V → S d − 1 ∪ { 0 } η ( y ) ≤ κ E Φ ( y ) \eta(y)\le\sqrt{\kappa_E}\Phi(y) η ( y ) ≤ κ E Φ ( y )
Proof. Each y v y_v y v ∥ y v ∥ 2 = ∥ y v ∥ \lVert y_v\rVert^2=\lVert y_v\rVert ∥ y v ∥ 2 = ∥ y v ∥ ∥ y v − W v u T y u ∥ ≤ 2 \lVert y_v-W_{vu}^{\mathsf T}y_u\rVert\le2 ∥ y v − W v u T y u ∥ ≤ 2
1 2 ∥ y v − W v u T y u ∥ M v u 2 ≤ 1 2 w v u + ⋅ 2 ⋅ ∥ y v − W v u T y u ∥ M v u ≤ κ E w v u − ∥ y v − W v u T y u ∥ M v u , (37) \frac{1}{2}\lVert y_v-W_{vu}^{\mathsf T}y_u\rVert_{M_{vu}}^2\le\frac{1}{2}\sqrt{w_{vu}^+}\cdot2\cdot\lVert y_v-W_{vu}^{\mathsf T}y_u\rVert_{M_{vu}}\le\sqrt{\kappa_Ew_{vu}^-}\,\lVert y_v-W_{vu}^{\mathsf T}y_u\rVert_{M_{vu}}, \tag*{(37)} 2 1 ∥ y v − W v u T y u ∥ M v u 2 ≤ 2 1 w v u + ⋅ 2 ⋅ ∥ y v − W v u T y u ∥ M v u ≤ κ E w v u − ∥ y v − W v u T y u ∥ M v u , (37) using w v u + ≤ κ E w v u − w_{vu}^+\le\kappa_Ew_{vu}^- w v u + ≤ κ E w v u − η \eta η κ E \sqrt{\kappa_E} κ E Φ \Phi Φ
y T D y = ∑ v y v T D v y v ≥ ∑ v λ min ( D v ) ∥ y v ∥ 2 ≥ ∑ v d v − ∥ y v ∥ , (38) y^{\mathsf T}Dy=\sum_v y_v^{\mathsf T}D_vy_v\ge\sum_v\lambda_{\min}(D_v)\lVert y_v\rVert^2\ge\sum_v d_v^-\lVert y_v\rVert, \tag*{(38)} y T D y = v ∑ y v T D v y v ≥ v ∑ λ m i n ( D v ) ∥ y v ∥ 2 ≥ v ∑ d v − ∥ y v ∥ , (38) which is the denominator of Φ \Phi Φ
Proof of Theorem 4.2. Let z z z B ~ \widetilde{B} B λ 1 ( B ~ ) \lambda_1(\widetilde{B}) λ 1 ( B ) x : = D − 1 / 2 z x:=D^{-1/2}z x := D − 1/2 z max v ∥ x v ∥ = 1 \max_v\lVert x_v\rVert=1 max v ∥ x v ∥ = 1 η \eta η η ( x ) = λ 1 ( B ~ ) \eta(x)=\lambda_1(\widetilde{B}) η ( x ) = λ 1 ( B ) t t t x > t ≠ 0 x^{>t}\ne0 x > t = 0 Φ ( x > t ) ≤ κ E 10 η ( x ) \Phi(x^{>t})\le\kappa_E\sqrt{10\eta(x)} Φ ( x > t ) ≤ κ E 10 η ( x ) x > t x^{>t} x > t S d − 1 ∪ { 0 } \mathbb{S}^{d-1}\cup\{0\} S d − 1 ∪ { 0 } η G ∗ \eta_G^* η G ∗
η G ∗ ≤ η ( x > t ) ≤ κ E Φ ( x > t ) ≤ κ E 3 / 2 10 λ 1 ( B ~ ) . (39) \eta_G^*\le\eta(x^{>t})\le\sqrt{\kappa_E}\Phi(x^{>t})\le\kappa_E^{3/2}\sqrt{10\lambda_1(\widetilde{B})}. \tag*{(39)} η G ∗ ≤ η ( x > t ) ≤ κ E Φ ( x > t ) ≤ κ E 3/2 10 λ 1 ( B ) . (39) Algorithm 4.1 enumerates all the breakpoints of t ↦ x > t t\mapsto x^{>t} t ↦ x > t
Full synchronization
Theorem 4.3 (Full synchronization). λ 1 ( B ~ ) ≤ η G ≤ 54 κ E 2 λ 2 ( L − ) − 1 λ 1 ( B ~ ) \lambda_1(\widetilde{B})\le\eta_G\le54\kappa_E^2\lambda_2(\mathcal{L}_- )^{-1}\lambda_1(\widetilde{B}) λ 1 ( B ) ≤ η G ≤ 54 κ E 2 λ 2 ( L − ) − 1 λ 1 ( B )
The lower bound is Proposition 4.3(a). For the upper bound we again start from x : = D − 1 / 2 z x:=D^{-1/2}z x := D − 1/2 z z z z B ~ \widetilde{B} B λ 1 ( B ~ ) \lambda_1(\widetilde{B}) λ 1 ( B ) η ( x ) = λ 1 ( B ~ ) \eta(x)=\lambda_1(\widetilde{B}) η ( x ) = λ 1 ( B ) ∥ x v ∥ \lVert x_v\rVert ∥ x v ∥ x ~ v : = x v / ∥ x v ∥ \tilde{x}_v := x_v/\lVert x_v\rVert x ~ v := x v / ∥ x v ∥ n x n_x n x
Lemma E (Normalization of two vectors). For nonzero a , b ∈ R d a,b\in\mathbb{R}^d a , b ∈ R d
∥ a ∥ a ∥ − b ∥ b ∥ ∥ ≤ 2 ∥ a − b ∥ ∥ a ∥ + ∥ b ∥ ≤ ∥ a − b ∥ min ( ∥ a ∥ , ∥ b ∥ ) . (40) \left\lVert\frac{a}{\lVert a\rVert}-\frac{b}{\lVert b\rVert}\right\rVert\le\frac{2\lVert a-b\rVert}{\lVert a\rVert+\lVert b\rVert}\le\frac{\lVert a-b\rVert}{\min(\lVert a\rVert,\lVert b\rVert)}. \tag*{(40)} ∥ a ∥ a − ∥ b ∥ b ≤ ∥ a ∥ + ∥ b ∥ 2 ∥ a − b ∥ ≤ min (∥ a ∥ , ∥ b ∥) ∥ a − b ∥ . (40) Proof. Write p : = ∥ a ∥ p:=\lVert a\rVert p := ∥ a ∥ q : = ∥ b ∥ q:=\lVert b\rVert q := ∥ b ∥ c : = ⟨ a / p , b / q ⟩ ∈ [ − 1 , 1 ] c:=\langle a/p,b/q\rangle\in[-1,1] c := ⟨ a / p , b / q ⟩ ∈ [ − 1 , 1 ]
∥ a p − b q ∥ 2 = 2 − 2 c , ∥ a − b ∥ 2 = p 2 + q 2 − 2 p q c . (41) \left\lVert\frac{a}{p}-\frac{b}{q}\right\rVert^2=2-2c,\qquad\lVert a-b\rVert^2=p^2+q^2-2pqc. \tag*{(41)} p a − q b 2 = 2 − 2 c , ∥ a − b ∥ 2 = p 2 + q 2 − 2 pq c . (41) The first inequality, squared, reads ( 2 − 2 c ) ( p + q ) 2 ≤ 4 ( p 2 + q 2 − 2 p q c ) (2-2c)(p+q)^2\le4(p^2+q^2-2pqc) ( 2 − 2 c ) ( p + q ) 2 ≤ 4 ( p 2 + q 2 − 2 pq c ) 4 ( p 2 + q 2 − 2 p q c ) − 2 ( 1 − c ) ( p + q ) 2 = 2 ( p − q ) 2 ( 1 + c ) ≥ 0 4(p^2+q^2-2pqc)-2(1-c)(p+q)^2=2(p-q)^2(1+c)\ge0 4 ( p 2 + q 2 − 2 pq c ) − 2 ( 1 − c ) ( p + q ) 2 = 2 ( p − q ) 2 ( 1 + c ) ≥ 0 c ≥ − 1 c\ge-1 c ≥ − 1 p + q ≥ 2 min ( p , q ) p+q\ge2\min(p,q) p + q ≥ 2 min ( p , q )
Lemma F (Norm profile). For every x ≠ 0 x\ne0 x = 0 α x ≥ 0 \alpha_x\ge0 α x ≥ 0 u x : = n x − α x 1 u_x:=n_x-\alpha_x1 u x := n x − α x 1 1 T D 0 − u x = 0 1^{\mathsf{T}}D_0^-u_x=0 1 T D 0 − u x = 0
∥ u x ∥ D 0 − 2 ≤ κ E η ( x ) λ 2 ( L − ) ∥ n x ∥ D 0 − 2 . (42) \lVert u_x\rVert_{D_0^-}^2\le\frac{\kappa_E\eta(x)}{\lambda_2(\mathcal{L}_-)}\lVert n_x\rVert_{D_0^-}^2. \tag*{(42)} ∥ u x ∥ D 0 − 2 ≤ λ 2 ( L − ) κ E η ( x ) ∥ n x ∥ D 0 − 2 . (42) Proof. Let α x : = ( 1 T D 0 − n x ) / ( 1 T D 0 − 1 ) \alpha_x:=(1^{\mathsf{T}}D_0^-n_x)/(1^{\mathsf{T}}D_0^-1) α x := ( 1 T D 0 − n x ) / ( 1 T D 0 − 1 ) α ↦ ∥ n x − α 1 ∥ D 0 − \alpha\mapsto\lVert n_x-\alpha1\rVert_{D_0^-} α ↦ ∥ n x − α 1 ∥ D 0 − n x ≥ 0 n_x\ge0 n x ≥ 0 1 T D 0 − u x = 0 1^{\mathsf{T}}D_0^-u_x=0 1 T D 0 − u x = 0 L − 1 = 0 L_-1=0 L − 1 = 0 G − G_- G −
λ 2 ( L − ) = min 1 T D 0 − u = 0 u T L − u ∥ u ∥ D 0 − 2 . (43) \lambda_2(\mathcal{L}_-)=\min_{1^{\mathsf{T}}D_0^-u=0}\frac{u^{\mathsf{T}}L_-u}{\lVert u\rVert_{D_0^-}^2}. \tag*{(43)} λ 2 ( L − ) = 1 T D 0 − u = 0 min ∥ u ∥ D 0 − 2 u T L − u . (43) which gives u x T L − u x ≥ λ 2 ( L − ) ∥ u x ∥ D 0 − 2 u_x^{\mathsf{T}}L_-u_x\ge\lambda_2(\mathcal{L}_-)\lVert u_x\rVert_{D_0^-}^2 u x T L − u x ≥ λ 2 ( L − ) ∥ u x ∥ D 0 − 2 L − 1 = 0 L_-1=0 L − 1 = 0 1 1 1 u x T L − u x = n x T L − n x u_x^{\mathsf{T}}L_-u_x=n_x^{\mathsf{T}}L_-n_x u x T L − u x = n x T L − n x
n x T L − n x ≤ x T B x = η ( x ) x T D x ≤ κ E η ( x ) ∥ n x ∥ D 0 − 2 . (44) n_x^{\mathsf{T}}L_-n_x\le x^{\mathsf{T}}Bx=\eta(x)x^{\mathsf{T}}Dx\le\kappa_E\eta(x)\lVert n_x\rVert_{D_0^-}^2. \tag*{(44)} n x T L − n x ≤ x T B x = η ( x ) x T D x ≤ κ E η ( x ) ∥ n x ∥ D 0 − 2 . (44) Combining the two and dividing by λ 2 ( L − ) > 0 \lambda_2(\mathcal{L}_-)>0 λ 2 ( L − ) > 0
Lemma G (Ill-balanced vertices are few). Normalize x x x ∥ n x ∥ D 0 − 2 = vol − \lVert n_x\rVert_{D_0^-}^2=\operatorname{vol}^- ∥ n x ∥ D 0 − 2 = vol − I b x ( δ ) : = { v : ∣ ∥ x v ∥ − 1 ∣ ≥ δ } Ib_x(\delta):=\{v:\lvert\lVert x_v\rVert-1\rvert\ge\delta\} I b x ( δ ) := { v : ∣∥ x v ∥ − 1 ∣ ≥ δ }
vol − ( I b x ( δ ) ) vol − ≤ 4 δ 2 κ E η ( x ) λ 2 ( L − ) . (45) \frac{\operatorname{vol}^-(Ib_x(\delta))}{\operatorname{vol}^-}\le\frac{4}{\delta^2}\frac{\kappa_E\eta(x)}{\lambda_2(\mathcal{L}_-)}. \tag*{(45)} vol − vol − ( I b x ( δ )) ≤ δ 2 4 λ 2 ( L − ) κ E η ( x ) . (45) Proof. Write ε : = κ E η ( x ) / λ 2 ( L − ) \varepsilon:= \kappa_E\eta(x)/\lambda_2(\mathcal{L}_{-}) ε := κ E η ( x ) / λ 2 ( L − ) ∥ u x ∥ D 0 − ≤ ε v o l − \lVert u_x\rVert_{D_0^-} \le\varepsilon\,\mathrm{vol}^{-} ∥ u x ∥ D 0 − ≤ ε vol − α x \alpha_x α x 1 1 1 ∥ 1 ∥ D 0 − = v o l − = ∥ n x ∥ D 0 − \lVert\mathbf{1}\rVert_{D_0^-}=\mathrm{vol}^{-}=\lVert n_x\rVert_{D_0^-} ∥ 1 ∥ D 0 − = vol − = ∥ n x ∥ D 0 − ∥ ⋅ ∥ D 0 − \lVert\cdot\rVert_{D_0^-} ∥ ⋅ ∥ D 0 −
∣ 1 − α x ∣ v o l − = ∣ ∥ n x ∥ D 0 − − α x ∥ 1 ∥ D 0 − ∣ ≤ ∥ u x ∥ D 0 − ≤ ε v o l − , (46) |1-\alpha_x|\sqrt{\mathrm{vol}^{-}}=\left|\lVert n_x\rVert_{D_0^-}-\alpha_x\lVert\mathbf{1}\rVert_{D_0^-}\right|\leq\lVert u_x\rVert_{D_0^-}\leq\sqrt{\varepsilon\,\mathrm{vol}^{-}}, \tag*{(46)} ∣1 − α x ∣ vol − = ∥ n x ∥ D 0 − − α x ∥ 1 ∥ D 0 − ≤ ∥ u x ∥ D 0 − ≤ ε vol − , (46) hence ∣ 1 − α x ∣ ≤ ε |1-\alpha_x|\leq\sqrt{\varepsilon} ∣1 − α x ∣ ≤ ε v ∈ I b x ( δ ) v\in Ib_x(\delta) v ∈ I b x ( δ )
∣ ( u x ) v ∣ = ∣ ∥ x v ∥ − α x ∣ ≥ ∣ ∥ x v ∥ − 1 ∣ − ∣ 1 − α x ∣ ≥ δ − ε . (47) |(u_x)_v|=\left|\lVert x_v\rVert-\alpha_x\right|\geq\left|\lVert x_v\rVert-1\right|-|1-\alpha_x|\geq\delta-\sqrt{\varepsilon}. \tag*{(47)} ∣ ( u x ) v ∣ = ∣ ∥ x v ∥ − α x ∣ ≥ ∣ ∥ x v ∥ − 1 ∣ − ∣1 − α x ∣ ≥ δ − ε . (47) Suppose ε < δ / 2 \sqrt{\varepsilon}<\delta/2 ε < δ /2 δ − ε > δ / 2 > 0 \delta-\sqrt{\varepsilon}>\delta/2>0 δ − ε > δ /2 > 0 ∥ u x ∥ D 0 − 2 \lVert u_x\rVert_{D_0^-}^{2} ∥ u x ∥ D 0 − 2 I b x ( δ ) Ib_x(\delta) I b x ( δ )
ε v o l − ≥ ∥ u x ∥ D 0 − 2 ≥ ∑ v ∈ I b x ( δ ) d v − ( u x ) v 2 ≥ ( δ 2 ) 2 v o l − ( I b x ( δ ) ) , (48) \varepsilon\,\mathrm{vol}^{-}\geq\lVert u_x\rVert_{D_0^-}^{2}\geq\sum_{v\in Ib_x(\delta)}d_v^-(u_x)_v^2\geq\left(\frac{\delta}{2}\right)^2\mathrm{vol}^{-}(Ib_x(\delta)), \tag*{(48)} ε vol − ≥ ∥ u x ∥ D 0 − 2 ≥ v ∈ I b x ( δ ) ∑ d v − ( u x ) v 2 ≥ ( 2 δ ) 2 vol − ( I b x ( δ )) , (48) which rearranges to the claim. If instead ε ≥ δ / 2 \sqrt{\varepsilon}\geq\delta/2 ε ≥ δ /2 4 ε / δ 2 ≥ 1 4\varepsilon/\delta^2\geq1 4 ε / δ 2 ≥ 1 1 1 1
Lemma H (Cost of normalizing).
Lemma H (Cost of normalizing). For every x ≠ 0 x\neq0 x = 0 γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 )
η ( x ~ ) ≤ κ E 2 [ 16 γ 2 λ 2 ( L − ) + 1 ( 1 − γ ) 2 ] η ( x ) , (49) \eta(\widetilde{x})\leq\kappa_E^2\left[\frac{16}{\gamma^2\lambda_2(\mathcal{L}_{-})}+\frac{1}{(1-\gamma)^2}\right]\eta(x), \tag*{(49)} η ( x ) ≤ κ E 2 [ γ 2 λ 2 ( L − ) 16 + ( 1 − γ ) 2 1 ] η ( x ) , (49) and in particular, at γ = 2 / 3 \gamma=2/3 γ = 2/3 η ( x ~ ) ≤ 54 κ E 2 λ 2 ( L − ) − 1 η ( x ) \eta(\widetilde{x})\leq54\kappa_E^2\lambda_2(\mathcal{L}_{-})^{-1}\eta(x) η ( x ) ≤ 54 κ E 2 λ 2 ( L − ) − 1 η ( x )
Proof. Both η ( x ) \eta(x) η ( x ) x ~ \widetilde{x} x x ↦ c x x\mapsto cx x ↦ c x c > 0 c>0 c > 0 n c x = c n x n_{cx}=cn_x n c x = c n x x x x c x cx c x c : = v o l − / ∥ n x ∥ D 0 − c:=\sqrt{\mathrm{vol}^{-}/\lVert n_x\rVert_{D_0^-}} c := vol − / ∥ n x ∥ D 0 − ∥ n x ∥ D 0 − 2 = v o l − \lVert n_x\rVert_{D_0^-}^{2}=\mathrm{vol}^{-} ∥ n x ∥ D 0 − 2 = vol − I b : = I b x ( γ ) Ib:=Ib_x(\gamma) I b := I b x ( γ ) η ( x ~ ) \eta(\widetilde{x}) η ( x ) 1 2 ∑ v ≠ u ∥ x ~ v − W v u T x ~ u ∥ M v u 2 \frac{1}{2}\sum_{v\neq u}\lVert\widetilde{x}_v-W_{vu}^{\mathsf T}\widetilde{x}_u\rVert_{M_{vu}}^{2} 2 1 ∑ v = u ∥ x v − W v u T x u ∥ M v u 2 I b Ib I b
Denominator. Since ∥ x ~ v ∥ = 1 \lVert\widetilde{x}_v\rVert=1 ∥ x v ∥ = 1 v v v
x ~ T D x ~ = ∑ v x ~ v T D v x ~ v ≥ ∑ v λ min ( D v ) ≥ ∑ v d v − = v o l − . (50) \widetilde{x}^{\mathsf T}D\widetilde{x}=\sum_v\widetilde{x}_v^{\mathsf T}D_v\widetilde{x}_v\geq\sum_v\lambda_{\min}(D_v)\geq\sum_vd_v^-=\mathrm{vol}^{-}. \tag*{(50)} x T D x = v ∑ x v T D v x v ≥ v ∑ λ m i n ( D v ) ≥ v ∑ d v − = vol − . (50) Pairs meeting $Ib. Here we use only ∥ x ~ v − W v u T x ~ u ∥ ≤ 2 \lVert\widetilde{x}_v-W_{vu}^{\mathsf T}\widetilde{x}_u\rVert\leq2 ∥ x v − W v u T x u ∥ ≤ 2 { ( v , u ) : v ∈ I b } ∪ { ( v , u ) : u ∈ I b } \{(v,u):v\in Ib\}\cup\{(v,u):u\in Ib\} {( v , u ) : v ∈ I b } ∪ {( v , u ) : u ∈ I b } w v u + = w u v + w_{vu}^+=w_{uv}^+ w v u + = w uv + d v + ≤ κ E d v − d_v^+\leq\kappa_Ed_v^- d v + ≤ κ E d v − δ = γ \delta=\gamma δ = γ
1 2 ∑ ( v , u ) meeting I b ∥ x ~ v − W v u T x ~ u ∥ M v u 2 ≤ 4 ∑ v ∈ I b d v + ≤ 4 κ E v o l − ( I b ) ≤ 16 κ E 2 γ 2 η ( x ) λ 2 ( L − ) v o l − . (51) \frac{1}{2}\sum_{(v,u)\text{ meeting }Ib}\lVert\widetilde{x}_v-W_{vu}^{\mathsf T}\widetilde{x}_u\rVert_{M_{vu}}^2\leq4\sum_{v\in Ib}d_v^+\leq4\kappa_E\mathrm{vol}^{-}(Ib)\leq\frac{16\kappa_E^2}{\gamma^2}\frac{\eta(x)}{\lambda_2(\mathcal{L}_{-})}\mathrm{vol}^{-}. \tag*{(51)} 2 1 ( v , u ) meeting I b ∑ ∥ x v − W v u T x u ∥ M v u 2 ≤ 4 v ∈ I b ∑ d v + ≤ 4 κ E vol − ( I b ) ≤ γ 2 16 κ E 2 λ 2 ( L − ) η ( x ) vol − . (51) Pairs avoiding I b Ib I b For v ∉ I b v\notin Ib v ∈ / I b ∥ x v ∥ > 1 − γ > 0 \lVert x_v\rVert>1-\gamma>0 ∥ x v ∥ > 1 − γ > 0 x v ≠ 0 x_v\neq0 x v = 0 x ~ \widetilde{x} x I b Ib I b a : = x v a:=x_v a := x v b : = W v u T x u b:=W_{vu}^{\mathsf T}x_u b := W v u T x u 1 − γ 1-\gamma 1 − γ W v u T W_{vu}^{\mathsf T} W v u T b / ∥ b ∥ = W v u T x ~ u b/\lVert b\rVert=W_{vu}^{\mathsf T}\widetilde{x}_u b / ∥ b ∥ = W v u T x u
∥ x ~ v − W v u T x ~ u ∥ ≤ ∥ x v − W v u T x u ∥ 1 − γ . (52) \lVert\widetilde{x}_v-W_{vu}^{\mathsf T}\widetilde{x}_u\rVert\leq\frac{\lVert x_v-W_{vu}^{\mathsf T}x_u\rVert}{1-\gamma}. \tag*{(52)} ∥ x v − W v u T x u ∥ ≤ 1 − γ ∥ x v − W v u T x u ∥ . (52) Passing to the edge metric on both sides by item (iii) of the toolkit costs w v u + / w v u − ≤ κ E w_{vu}^+/w_{vu}^-\leq\kappa_E w v u + / w v u − ≤ κ E
1 2 ∑ avoiding I b ∥ x ~ v − W v u T x ~ u ∥ M v u 2 ≤ κ E ( 1 − γ ) 2 ⋅ 1 2 ∑ v ≠ u ∥ x v − W v u T x u ∥ M v u 2 = κ E ( 1 − γ ) 2 η ( x ) x T D x ≤ κ E 2 ( 1 − γ ) 2 η ( x ) v o l − . (53) \begin{aligned}
\frac{1}{2}\sum_{\text{avoiding }Ib}\lVert\widetilde{x}_v-W_{vu}^{\mathsf T}\widetilde{x}_u\rVert_{M_{vu}}^2\leq\frac{\kappa_E}{(1-\gamma)^2}\cdot\frac{1}{2}\sum_{v\neq u}\lVert x_v-W_{vu}^{\mathsf T}x_u\rVert_{M_{vu}}^2 \\
&=\frac{\kappa_E}{(1-\gamma)^2}\eta(x)x^{\mathsf T}Dx\leq\frac{\kappa_E^2}{(1-\gamma)^2}\eta(x)\,\mathrm{vol}^{-}. \tag*{(53)}
\end{aligned} 2 1 avoiding I b ∑ ∥ x v − W v u T x u ∥ M v u 2 ≤ ( 1 − γ ) 2 κ E ⋅ 2 1 v = u ∑ ∥ x v − W v u T x u ∥ M v u 2 = ( 1 − γ ) 2 κ E η ( x ) x T D x ≤ ( 1 − γ ) 2 κ E 2 η ( x ) vol − . (53) Conclusion. Adding the two contributions and dividing by the denominator:
η ( x ~ ) ≤ 1 vol − [ 16 κ E 2 γ 2 η ( x ) λ 2 ( L − ) vol − + κ E 2 ( 1 − γ ) 2 η ( x ) vol − ] = κ E 2 [ 16 γ 2 λ 2 ( L − ) + 1 ( 1 − γ ) 2 ] η ( x ) . (54) \begin{aligned}
\eta(\widetilde{x}) \le\frac{1}{\operatorname{vol}^{-}}\left[\frac{16\kappa_E^2}{\gamma^2}\frac{\eta(x)}{\lambda_2(L_{-})}\operatorname{vol}^{-}+\frac{\kappa_E^2}{(1-\gamma)^2}\eta(x)\operatorname{vol}^{-}\right] \\
&=\kappa_E^2\left[\frac{16}{\gamma^2\lambda_2(L_{-})}+\frac{1}{(1-\gamma)^2}\right]\eta(x). \tag*{(54)}
\end{aligned} η ( x ) ≤ vol − 1 [ γ 2 16 κ E 2 λ 2 ( L − ) η ( x ) vol − + ( 1 − γ ) 2 κ E 2 η ( x ) vol − ] = κ E 2 [ γ 2 λ 2 ( L − ) 16 + ( 1 − γ ) 2 1 ] η ( x ) . (54) For the constant, λ 2 ( L − ) ≤ 2 \lambda_2(L_{-}) \le2 λ 2 ( L − ) ≤ 2
16 γ 2 λ 2 ( L − ) + 1 ( 1 − γ ) 2 = 1 λ 2 ( L − ) [ 16 γ 2 + λ 2 ( L − ) ( 1 − γ ) 2 ] ≤ 1 λ 2 ( L − ) [ 16 γ 2 + 2 ( 1 − γ ) 2 ] . (55) \frac{16}{\gamma^2\lambda_2(L_{-})}+\frac{1}{(1-\gamma)^2}=\frac{1}{\lambda_2(L_{-})}\left[\frac{16}{\gamma^2}+\frac{\lambda_2(L_{-})}{(1-\gamma)^2}\right]\le\frac{1}{\lambda_2(L_{-})}\left[\frac{16}{\gamma^2}+\frac{2}{(1-\gamma)^2}\right]. \tag*{(55)} γ 2 λ 2 ( L − ) 16 + ( 1 − γ ) 2 1 = λ 2 ( L − ) 1 [ γ 2 16 + ( 1 − γ ) 2 λ 2 ( L − ) ] ≤ λ 2 ( L − ) 1 [ γ 2 16 + ( 1 − γ ) 2 2 ] . (55) The derivative of the bracket, − 32 / γ 3 + 4 / ( 1 − γ ) 3 -32/\gamma^3+4/(1-\gamma)^3 − 32/ γ 3 + 4/ ( 1 − γ ) 3 γ 3 = 8 ( 1 − γ ) 3 \gamma^3=8(1-\gamma)^3 γ 3 = 8 ( 1 − γ ) 3 γ = 2 / 3 \gamma=2/3 γ = 2/3 36 + 18 = 54 36+18=54 36 + 18 = 54
Proof of Theorem 4.3. With x : = D − 1 / 2 z x:=D^{-1/2}z x := D − 1/2 z η ( x ) = λ 1 ( B ~ ) \eta(x)=\lambda_1(\widetilde{B}) η ( x ) = λ 1 ( B ) x ~ \widetilde{x} x V V V S d − 1 S^{d-1} S d − 1 η G \eta_G η G
η G ≤ η ( x ~ ) ≤ 54 κ E 2 λ 2 ( L − ) − 1 λ 1 ( B ~ ) . (56) \eta_G\le\eta(\widetilde{x})\le54\kappa_E^2\lambda_2(L_{-})^{-1}\lambda_1(\widetilde{B}). \tag*{(56)} η G ≤ η ( x ) ≤ 54 κ E 2 λ 2 ( L − ) − 1 λ 1 ( B ) . (56) This x ~ \widetilde{x} x
Theorem 4.4 (O ( d ) O(d) O ( d )
1 d κ D ∑ k ≤ d λ k ( B ~ ) ≤ ν G ≤ 2 11 κ E 3 d 3 λ 2 ( L − ) ∑ k ≤ d λ k ( B ~ ) , (57) \frac{1}{d\kappa_D}\sum_{k\le d}\lambda_k(\widetilde{B})\le\nu_G\le\frac{2^{11}\kappa_E^3d^3}{\lambda_2(L_{-})}\sum_{k\le d}\lambda_k(\widetilde{B}), \tag*{(57)} d κ D 1 k ≤ d ∑ λ k ( B ) ≤ ν G ≤ λ 2 ( L − ) 2 11 κ E 3 d 3 k ≤ d ∑ λ k ( B ) , (57) and Algorithm 4.3 attains the upper bound.
The lower bound is Proposition 4.3(c). For the upper bound we take the eigenvectors of the d d d d × d d\times d d × d d d d
The lengths of the columns are controlled as in the full synchronization proof, by the spectral gap of the companion graph. Their inner products are not controlled directly, and we recover them from lengths through the polarization identity: for u : = 1 2 ( x k + x m ) u:=\frac{1}{\sqrt{2}}(x^k+x^m) u := 2 1 ( x k + x m ) ∥ u v ∥ 2 = 1 2 ∥ x v k + x v m ∥ 2 \lVert u_v\rVert^2=\frac{1}{2}\lVert x_v^k+x_v^m\rVert^2 ∥ u v ∥ 2 = 2 1 ∥ x v k + x v m ∥ 2
⟨ x v k , x v m ⟩ = ∥ u v ∥ 2 − ∥ x v k ∥ 2 + ∥ x v m ∥ 2 2 , (58) \langle x_v^k,x_v^m\rangle=\lVert u_v\rVert^2-\frac{\lVert x_v^k\rVert^2+\lVert x_v^m\rVert^2}{2}, \tag*{(58)} ⟨ x v k , x v m ⟩ = ∥ u v ∥ 2 − 2 ∥ x v k ∥ 2 + ∥ x v m ∥ 2 , (58) so that if the three lengths at v v v [ 1 − δ , 1 + δ ] [1-\delta,1+\delta] [ 1 − δ , 1 + δ ] ∣ ⟨ x v k , x v m ⟩ ∣ ≤ ( 1 + δ ) 2 − ( 1 − δ ) 2 = 4 δ |\langle x_v^k,x_v^m\rangle|\le(1+\delta)^2-(1-\delta)^2=4\delta ∣ ⟨ x v k , x v m ⟩ ∣ ≤ ( 1 + δ ) 2 − ( 1 − δ ) 2 = 4 δ u u u x k x^k x k x m x^m x m D ˉ \bar{D} D ˉ
Since D ˉ \bar{D} D ˉ
x T D ˉ x = ∑ v d ˉ v ∥ x v ∥ 2 = ∥ n x ∥ D ˉ 0 2 (59) x^{\mathsf T}\bar{D}x=\sum_v\bar{d}_v\lVert x_v\rVert^2=\lVert nx\rVert_{\bar{D}_0}^2 \tag*{(59)} x T D ˉ x = v ∑ d ˉ v ∥ x v ∥ 2 = ∥ n x ∥ D ˉ 0 2 (59) for every x ∈ R n d x\in\mathbb{R}^{nd} x ∈ R n d D ˉ \bar{D} D ˉ u u u Lemma K ). If the algorithm used D D D D ˉ \bar{D} D ˉ ∥ n x ∥ D ˉ 0 2 ≤ x T D x ≤ κ E ∥ n x ∥ D ˉ 0 2 \lVert nx\rVert_{\bar{D}_0}^2\le x^{\mathsf T}Dx\le\kappa_E\lVert nx\rVert_{\bar{D}_0}^2 ∥ n x ∥ D ˉ 0 2 ≤ x T D x ≤ κ E ∥ n x ∥ D ˉ 0 2 u u u ( 1 + τ ) vol − 1 (1+\tau)\operatorname{vol}^{-1} ( 1 + τ ) vol − 1 ∣ τ ∣ |\tau| ∣ τ ∣ κ E − 1 \kappa_E-1 κ E − 1 4 δ + ∣ τ ∣ ( 1 + δ ) 2 4\delta+|\tau|(1+\delta)^2 4 δ + ∣ τ ∣ ( 1 + δ ) 2 ∣ τ ∣ ( 1 + δ ) 2 |\tau|(1+\delta)^2 ∣ τ ∣ ( 1 + δ ) 2 δ \delta δ 1 / d 1/d 1/ d κ E − 1 \kappa_E-1 κ E − 1 1 / d 1/d 1/ d
The steps are then the following: convert between D ˉ \bar{D} D ˉ D D D Lemma I ), control lengths in the isotropized normalization (Lemma J), make polarization exact (Lemma K ), bound the volume of the vertices where the columns are not nearly orthonormal (Lemma L ), show that the matrix is well conditioned everywhere else (Lemma M ), show that the polar step is stable there (Lemma N), and assemble (Lemma O). Besides the notation of the two previous cases, the proof uses the following.
Table 23.
Lemma I (Conversion). Let λ ˉ 2 \bar\lambda_2 λ ˉ 2 D ˉ 0 − 1 / 2 L − D ˉ 0 − 1 / 2 \bar D_0^{-1/2}L_-\bar D_0^{-1/2} D ˉ 0 − 1/2 L − D ˉ 0 − 1/2 λ 2 ( L − ) \lambda_2(L_-) λ 2 ( L − ) D ˉ 0 \bar D_0 D ˉ 0 D ˉ 0 \bar D_0 D ˉ 0
d v − ≤ λ min ( D v ) ≤ d ˉ v ≤ λ max ( D v ) ≤ d v + ≤ κ E d v − d_v^- \le\lambda_{\min}(D_v)\le\bar d_v\le\lambda_{\max}(D_v)\le d_v^+\le\kappa_Ed_v^- d v − ≤ λ m i n ( D v ) ≤ d ˉ v ≤ λ m a x ( D v ) ≤ d v + ≤ κ E d v − D 0 − ⪯ D ˉ 0 ⪯ κ E D 0 − D_0^- \preceq\bar D_0\preceq\kappa_E D_0^- D 0 − ⪯ D ˉ 0 ⪯ κ E D 0 − κ D − 1 D ˉ ⪯ D ⪯ κ D D ˉ \kappa_D^{-1}\bar D\preceq D\preceq\kappa_D\bar D κ D − 1 D ˉ ⪯ D ⪯ κ D D ˉ
λ ˉ 2 ≥ λ 2 ( L − ) / κ E \bar\lambda_2\ge\lambda_2(L_-)/\kappa_E λ ˉ 2 ≥ λ 2 ( L − ) / κ E
λ ˉ 2 ≤ n n − 1 ≤ 2 \bar\lambda_2\le\frac{n}{n-1}\le2 λ ˉ 2 ≤ n − 1 n ≤ 2 n ≥ 2 n\ge2 n ≥ 2
λ k ( B ˉ ) ≤ κ D λ k ( B ~ ) \lambda_k(\bar B)\le\kappa_D\lambda_k(\widetilde B) λ k ( B ˉ ) ≤ κ D λ k ( B ) k k k
Proof. (i) Since d ˉ v = 1 d tr ( D v ) \bar d_v=\frac{1}{d}\operatorname{tr}(D_v) d ˉ v = d 1 tr ( D v ) D v D_v D v
D v ⪯ λ max ( D v ) I ⪯ κ D λ min ( D v ) I ⪯ κ D d ˉ v I (60) D_v\preceq\lambda_{\max}(D_v)I\preceq\kappa_D\lambda_{\min}(D_v)I\preceq\kappa_D\bar d_vI \tag*{(60)} D v ⪯ λ m a x ( D v ) I ⪯ κ D λ m i n ( D v ) I ⪯ κ D d ˉ v I (60) and symmetrically D v ⪰ κ D − 1 d ˉ v I D_v\succeq\kappa_D^{-1}\bar d_vI D v ⪰ κ D − 1 d ˉ v I
(ii) For a positive diagonal Λ \Lambda Λ L − 1 = 0 L_-1=0 L − 1 = 0 Λ − 1 / 2 L − Λ − 1 / 2 \Lambda^{-1/2}L_-\Lambda^{-1/2} Λ − 1/2 L − Λ − 1/2
min u u n o n c o n s t a n t u T L − u min α ∥ u − α 1 ∥ Λ 2 (61) \min_{\substack{u\\u\ \mathrm{nonconstant}}}\frac{u^{\mathsf T}L_-u}{\min_\alpha\lVert u-\alpha1\rVert_\Lambda^2} \tag*{(61)} u u nonconstant min min α ∥ u − α 1 ∥ Λ 2 u T L − u (61) since subtracting from u u u Λ \Lambda Λ 1 1 1 u T L − u u^{\mathsf T}L_-u u T L − u u u u 1 1 1 Λ \Lambda Λ Λ \Lambda Λ α ∗ \alpha^* α ∗ ∥ u − α 1 ∥ D ˉ 0 2 \lVert u-\alpha1\rVert_{\bar D_0}^2 ∥ u − α 1 ∥ D ˉ 0 2
min α ∥ u − α 1 ∥ D ˉ 0 2 ≤ ∥ u − α ∗ 1 ∥ D ˉ 0 2 ≤ κ E ∥ u − α ∗ 1 ∥ D 0 − 2 = κ E min α ∥ u − α 1 ∥ D 0 − 2 (62) \min_\alpha\lVert u-\alpha1\rVert_{\bar D_0}^2\le\lVert u-\alpha^*1\rVert_{\bar D_0}^2\le\kappa_E\lVert u-\alpha^*1\rVert_{D_0^-}^2=\kappa_E\min_\alpha\lVert u-\alpha1\rVert_{D_0^-}^2 \tag*{(62)} α min ∥ u − α 1 ∥ D ˉ 0 2 ≤ ∥ u − α ∗ 1 ∥ D ˉ 0 2 ≤ κ E ∥ u − α ∗ 1 ∥ D 0 − 2 = κ E α min ∥ u − α 1 ∥ D 0 − 2 (62) so each quotient for D ˉ 0 \bar D_0 D ˉ 0 κ E − 1 \kappa_E^{-1} κ E − 1 D 0 − D_0^- D 0 − u u u
(iii) The trace of D ˉ 0 − 1 / 2 L − D ˉ 0 − 1 / 2 \bar D_0^{-1/2}L_-\bar D_0^{-1/2} D ˉ 0 − 1/2 L − D ˉ 0 − 1/2 ∑ v d v − / d ˉ v ≤ n \sum_v d_v^-/\bar d_v\le n ∑ v d v − / d ˉ v ≤ n 0 0 0 n − 1 n-1 n − 1 n / ( n − 1 ) n/(n-1) n / ( n − 1 )
(iv) From D ⪯ κ D D ˉ D\preceq\kappa_D\bar D D ⪯ κ D D ˉ B ⪰ 0 B\succeq0 B ⪰ 0
x T B x x T D ˉ x ≤ κ D x T B x x T D x for every x ≠ 0. (63) \frac{x^{\mathsf T}Bx}{x^{\mathsf T}\bar D x}\le\kappa_D\frac{x^{\mathsf T}Bx}{x^{\mathsf T}Dx}\qquad\text{for every }x\ne0. \tag*{(63)} x T D ˉ x x T B x ≤ κ D x T D x x T B x for every x = 0. (63) Both λ k ( B ˉ ) \lambda_k(\bar B) λ k ( B ˉ ) λ k ( B ~ ) \lambda_k(\widetilde B) λ k ( B ) k k k D ˉ \bar D D ˉ
Lemma J (Lengths in the isotropized normalization). For x ≠ 0 x\ne0 x = 0 α x ≥ 0 \alpha_x\ge0 α x ≥ 0 u x : = n x − α x 1 u_x:=n_x-\alpha_x1 u x := n x − α x 1 1 T D ˉ 0 u x = 0 1^{\mathsf T}\bar D_0u_x=0 1 T D ˉ 0 u x = 0
∥ u x ∥ D ˉ 0 2 ≤ η ˉ ( x ) λ ˉ 2 ∥ n x ∥ D ˉ 0 2 . (64) \lVert u_x\rVert_{\bar D_0}^{2}\le\frac{\bar\eta(x)}{\bar\lambda_2}\lVert n_x\rVert_{\bar D_0}^{2}. \tag*{(64)} ∥ u x ∥ D ˉ 0 2 ≤ λ ˉ 2 η ˉ ( x ) ∥ n x ∥ D ˉ 0 2 . (64) Consequently, if ∥ n x ∥ D ˉ 0 2 = v o l ‾ \lVert n_x\rVert_{\bar{D}_0}^2=\overline{\mathrm{vol}} ∥ n x ∥ D ˉ 0 2 = vol
v o l ‾ ( I b x ( δ ) ) v o l ‾ ≤ 4 δ 2 η ‾ ( x ) λ ˉ 2 . (65) \frac{\overline{\mathrm{vol}}(I_{b_x}(\delta))}{\overline{\mathrm{vol}}}\leq\frac{4}{\delta^2}\frac{\overline{\eta}(x)}{\bar{\lambda}_2}. \tag*{(65)} vol vol ( I b x ( δ )) ≤ δ 2 4 λ ˉ 2 η ( x ) . (65) Proof. The proofs of Lemmas F and G carry over with D ˉ 0 \bar{D}_0 D ˉ 0 D 0 D_0 D 0 v o l ‾ \overline{\mathrm{vol}} vol v o l − \mathrm{vol}^{-} vol − α x : = ( 1 T D ˉ 0 n x ) / ( 1 T D ˉ 0 1 ) \alpha_x:=(\mathbf{1}^{\mathsf{T}}\bar{D}_0n_x)/(\mathbf{1}^{\mathsf{T}}\bar{D}_0\mathbf{1}) α x := ( 1 T D ˉ 0 n x ) / ( 1 T D ˉ 0 1 )
λ ˉ 2 ∥ u x ∥ D ˉ 0 2 ≤ u x T L u x = n x T L n x ≤ x T B x = η ˉ ( x ) x T D ˉ x = η ˉ ( x ) ∥ n x ∥ D ˉ 0 2 , (66) \bar{\lambda}_2\lVert u_x\rVert_{\bar{D}_0}^2\leq u_x^{\mathsf{T}}Lu_x=n_x^{\mathsf{T}}Ln_x\leq x^{\mathsf{T}}Bx=\bar{\eta}(x)x^{\mathsf{T}}\bar{D}x=\bar{\eta}(x)\lVert n_x\rVert_{\bar{D}_0}^2, \tag*{(66)} λ ˉ 2 ∥ u x ∥ D ˉ 0 2 ≤ u x T L u x = n x T L n x ≤ x T B x = η ˉ ( x ) x T D ˉ x = η ˉ ( x ) ∥ n x ∥ D ˉ 0 2 , (66) the last step being (A.37).
In the remainder we fix x 1 , … , x d x^1,\ldots,x^d x 1 , … , x d D ˉ \bar{D} D ˉ ∥ n x k ∥ D ˉ 0 2 = v o l ‾ \lVert n_{x^k}\rVert_{\bar{D}_0}^2=\overline{\mathrm{vol}} ∥ n x k ∥ D ˉ 0 2 = vol k k k X v : = [ x v 1 ⋯ x v d ] ∈ R d × d X_v:=[x^1_v\ \cdots\ x^d_v]\in\mathbb{R}^{d\times d} X v := [ x v 1 ⋯ x v d ] ∈ R d × d
Lemma K (Exact polarization). For k ≠ m k\ne m k = m u : = 1 2 ( x k + x m ) u:=\frac{1}{\sqrt{2}}(x^k+x^m) u := 2 1 ( x k + x m ) ∥ n u ∥ D ˉ 0 2 = v o l ‾ \lVert n_u\rVert_{\bar{D}_0}^2=\overline{\mathrm{vol}} ∥ n u ∥ D ˉ 0 2 = vol η ˉ ( u ) ≤ η ˉ ( x k ) + η ˉ ( x m ) \bar{\eta}(u)\leq\bar{\eta}(x^k)+\bar{\eta}(x^m) η ˉ ( u ) ≤ η ˉ ( x k ) + η ˉ ( x m )
Proof. By (A.37) and D ˉ \bar{D} D ˉ
∥ n u ∥ D ˉ 0 2 = u T D ˉ u = 1 2 [ ( x k ) T D ˉ x k + ( x m ) T D ˉ x m ] + ( x k ) T D ˉ x m = 1 2 ( 2 v o l ‾ ) + 0 = v o l ‾ . (67) \lVert n_u\rVert_{\bar{D}_0}^2=u^{\mathsf{T}}\bar{D}u=\frac{1}{2}\left[(x^k)^{\mathsf{T}}\bar{D}x^k+(x^m)^{\mathsf{T}}\bar{D}x^m\right]+(x^k)^{\mathsf{T}}\bar{D}x^m=\frac{1}{2}(2\overline{\mathrm{vol}})+0=\overline{\mathrm{vol}}. \tag*{(67)} ∥ n u ∥ D ˉ 0 2 = u T D ˉ u = 2 1 [ ( x k ) T D ˉ x k + ( x m ) T D ˉ x m ] + ( x k ) T D ˉ x m = 2 1 ( 2 vol ) + 0 = vol . (67) Expanding both quadratic forms:
u T B u = 1 2 ( x k + x m ) T B ( x k + x m ) = ( x k ) T B x k + ( x m ) T B x m − 1 2 ( x k − x m ) T B ( x k − x m ) ≤ ( x k ) T B x k + ( x m ) T B x m , (68) u^{\mathsf{T}}Bu=\frac{1}{2}(x^k+x^m)^{\mathsf{T}}B(x^k+x^m)=(x^k)^{\mathsf{T}}Bx^k+(x^m)^{\mathsf{T}}Bx^m-\frac{1}{2}(x^k-x^m)^{\mathsf{T}}B(x^k-x^m)\leq(x^k)^{\mathsf{T}}Bx^k+(x^m)^{\mathsf{T}}Bx^m, \tag*{(68)} u T B u = 2 1 ( x k + x m ) T B ( x k + x m ) = ( x k ) T B x k + ( x m ) T B x m − 2 1 ( x k − x m ) T B ( x k − x m ) ≤ ( x k ) T B x k + ( x m ) T B x m , (68) the last step since B ⪰ 0 B\succeq0 B ⪰ 0 η ˉ \bar{\eta} η ˉ v o l ‾ \overline{\mathrm{vol}} vol
Lemma L (Bad volume). Put I b x y ( δ ) : = { v : ∣ ⟨ x v , y v ⟩ ∣ > δ } I_{b_{xy}}(\delta):=\{v:|\langle x_v,y_v\rangle|>\delta\} I b x y ( δ ) := { v : ∣ ⟨ x v , y v ⟩ ∣ > δ }
G : = V ∖ [ ⋃ k I b x k ( 1 8 d ) ∪ ⋃ k ≠ m I b x k x m ( 1 2 d ) ] . (69) \mathcal{G}:=V\setminus\left[\bigcup_k I_{b_{x^k}}\left(\frac{1}{8d}\right)\cup\bigcup_{k\ne m}I_{b_{x^kx^m}}\left(\frac{1}{2d}\right)\right]. \tag*{(69)} G := V ∖ k ⋃ I b x k ( 8 d 1 ) ∪ k = m ⋃ I b x k x m ( 2 d 1 ) . (69) Then:
v o l ‾ ( G c ) v o l ‾ ≤ 2 8 d 3 λ ˉ 2 ∑ k ≤ d η ˉ ( x k ) . (70) \frac{\overline{\mathrm{vol}}(\mathcal{G}^{c})}{\overline{\mathrm{vol}}}\leq\frac{2^8d^3}{\bar{\lambda}_2}\sum_{k\leq d}\bar{\eta}(x^k). \tag*{(70)} vol vol ( G c ) ≤ λ ˉ 2 2 8 d 3 k ≤ d ∑ η ˉ ( x k ) . (70) Proof. Fix k ≠ m k\ne m k = m u k m : = 1 2 ( x k + x m ) u^{km}:=\frac{1}{\sqrt{2}}(x^k+x^m) u k m := 2 1 ( x k + x m ) v v v I b x k ( 1 8 d ) I_{b_{x^k}}\left(\frac{1}{8d}\right) I b x k ( 8 d 1 ) I b x m ( 1 8 d ) I_{b_{x^m}}\left(\frac{1}{8d}\right) I b x m ( 8 d 1 ) I b u k m ( 1 8 d ) I_{b_{u^{km}}}\left(\frac{1}{8d}\right) I b u k m ( 8 d 1 ) v v v [ 1 − 1 8 d , 1 + 1 8 d ] [1-\frac{1}{8d},1+\frac{1}{8d}] [ 1 − 8 d 1 , 1 + 8 d 1 ] u k m u^{km} u k m
∣ ⟨ x v k , x v m ⟩ ∣ = ∣ ∥ u v k m ∥ 2 − ∥ x v k ∥ 2 + ∥ x v m ∥ 2 2 ∣ ≤ ( 1 + 1 8 d ) 2 − ( 1 − 1 8 d ) 2 = 1 2 d , (71) |\langle x^k_v,x^m_v\rangle|=\left|\lVert u^{km}_v\rVert^2-\frac{\lVert x^k_v\rVert^2+\lVert x^m_v\rVert^2}{2}\right|\leq\left(1+\frac{1}{8d}\right)^2-\left(1-\frac{1}{8d}\right)^2=\frac{1}{2d}, \tag*{(71)} ∣ ⟨ x v k , x v m ⟩ ∣ = ∥ u v k m ∥ 2 − 2 ∥ x v k ∥ 2 + ∥ x v m ∥ 2 ≤ ( 1 + 8 d 1 ) 2 − ( 1 − 8 d 1 ) 2 = 2 d 1 , (71) so v ∉ I b x k x m ( 1 2 d ) . H e n c e v\notin I_{b_{x^kx^m}}\left(\frac{1}{2d}\right). Hence v ∈ / I b x k x m ( 2 d 1 ) . H e n ce d d d I b x k ( 1 8 d ) I_{b_{x^k}}\left(\frac{1}{8d}\right) I b x k ( 8 d 1 ) ( d 2 ) \binom{d}{2} ( 2 d ) I b u k m ( 1 8 d ) I_{b_{u^{km}}}\left(\frac{1}{8d}\right) I b u k m ( 8 d 1 ) δ = 1 8 d \delta=\frac{1}{8d} δ = 8 d 1 η ˉ ( u k m ) ≤ η ˉ ( x k ) + η ˉ ( x m ) \bar{\eta}(u^{km})\leq\bar{\eta}(x^k)+\bar{\eta}(x^m) η ˉ ( u k m ) ≤ η ˉ ( x k ) + η ˉ ( x m )
v o l ‾ ( G c ) v o l ‾ ≤ 2 8 d 2 λ ˉ 2 [ ∑ k η ˉ ( x k ) + ∑ { k , m } ( η ˉ ( x k ) + η ˉ ( x m ) ) ] . (72) \frac{\overline{\mathrm{vol}}(\mathcal{G}^{c})}{\overline{\mathrm{vol}}}\leq\frac{2^8d^2}{\bar{\lambda}_2}\left[\sum_k\bar{\eta}(x^k)+\sum_{\{k,m\}}\left(\bar{\eta}(x^k)+\bar{\eta}(x^m)\right)\right]. \tag*{(72)} vol vol ( G c ) ≤ λ ˉ 2 2 8 d 2 k ∑ η ˉ ( x k ) + { k , m } ∑ ( η ˉ ( x k ) + η ˉ ( x m ) ) . (72) Each index k k k d − 1 d-1 d − 1 [ 1 + ( d − 1 ) ] ∑ k η ˉ ( x k ) = d ∑ k η ˉ ( x k ) [1+(d-1)]\sum_k\bar{\eta}(x^k)=d\sum_k\bar{\eta}(x^k) [ 1 + ( d − 1 )] ∑ k η ˉ ( x k ) = d ∑ k η ˉ ( x k ) 2 8 d 3 2^8d^3 2 8 d 3
Lemma M (Smallest singular value on G \mathcal{G} G For v ∈ G v\in\mathcal{G} v ∈ G σ min ( X v ) ≥ 1 / 2 \sigma_{\min}(X_v)\geq1/\sqrt{2} σ m i n ( X v ) ≥ 1/ 2 X v X_v X v
Proof. Let Γ : = X v T X v \Gamma:= X_v^{\mathsf{T}}X_v Γ := X v T X v Γ k m = ⟨ x v k , x v m ⟩ \Gamma_{km} = \langle x_v^k,x_v^m\rangle Γ k m = ⟨ x v k , x v m ⟩ X v = P Σ Q T X_v = P\Sigma Q^{\mathsf{T}} X v = P Σ Q T Γ = Q Σ 2 Q T \Gamma= Q\Sigma^2Q^{\mathsf{T}} Γ = Q Σ 2 Q T λ min ( Γ ) = σ min ( X v ) 2 \lambda_{\min}(\Gamma) = \sigma_{\min}(X_v)^2 λ m i n ( Γ ) = σ m i n ( X v ) 2 v ∉ I b x k ( 1 8 d ) v \notin I_{b_{x^k}}\left(\frac{1}{8d}\right) v ∈ / I b x k ( 8 d 1 ) Γ k k = ∥ x v k ∥ 2 ≥ ( 1 − 1 8 d ) 2 ≥ 1 − 1 4 d \Gamma_{kk} = \lVert x_v^k\rVert^2 \ge\left(1-\frac{1}{8d}\right)^2 \ge1-\frac{1}{4d} Γ k k = ∥ x v k ∥ 2 ≥ ( 1 − 8 d 1 ) 2 ≥ 1 − 4 d 1 v ∉ I b x k x m ( 1 2 d ) v \notin I_{b_{x^k x^m}}\left(\frac{1}{2d}\right) v ∈ / I b x k x m ( 2 d 1 ) ∣ Γ k m ∣ ≤ 1 2 d \lvert\Gamma_{km}\rvert\le\frac{1}{2d} ∣ Γ k m ∣ ≤ 2 d 1
To bound λ min ( Γ ) \lambda_{\min}(\Gamma) λ m i n ( Γ ) λ \lambda λ Γ \Gamma Γ ∣ λ − Γ k k ∣ ≤ ∑ m ≠ k ∣ Γ k m ∣ \lvert\lambda-\Gamma_{kk}\rvert\le\sum_{m\ne k}\lvert\Gamma_{km}\rvert ∣ λ − Γ k k ∣ ≤ ∑ m = k ∣ Γ k m ∣ k k k Γ c = λ c \Gamma c=\lambda c Γ c = λ c c ≠ 0 c\ne0 c = 0 k k k ∣ c k ∣ = max m ∣ c m ∣ > 0 \lvert c_k\rvert=\max_m\lvert c_m\rvert>0 ∣ c k ∣ = max m ∣ c m ∣ > 0 k k k ( λ − Γ k k ) c k = ∑ m ≠ k Γ k m c m (\lambda-\Gamma_{kk})c_k=\sum_{m\ne k}\Gamma_{km}c_m ( λ − Γ k k ) c k = ∑ m = k Γ k m c m
∣ λ − Γ k k ∣ ∣ c k ∣ ≤ ∑ m ≠ k ∣ Γ k m ∣ ∣ c m ∣ ≤ ∣ c k ∣ ∑ m ≠ k ∣ Γ k m ∣ , (73) \lvert\lambda-\Gamma_{kk}\rvert\lvert c_k\rvert\le\sum_{m\ne k}\lvert\Gamma_{km}\rvert\lvert c_m\rvert\le\lvert c_k\rvert\sum_{m\ne k}\lvert\Gamma_{km}\rvert, \tag*{(73)} ∣ λ − Γ k k ∣ ∣ c k ∣ ≤ m = k ∑ ∣ Γ k m ∣ ∣ c m ∣ ≤ ∣ c k ∣ m = k ∑ ∣ Γ k m ∣ , (73) so λ ≥ Γ k k − ∑ m ≠ k ∣ Γ k m ∣ \lambda\ge\Gamma_{kk}-\sum_{m\ne k}\lvert\Gamma_{km}\rvert λ ≥ Γ k k − ∑ m = k ∣ Γ k m ∣ ( d − 1 ) 1 2 d (d-1)\frac{1}{2d} ( d − 1 ) 2 d 1
λ min ( Γ ) ≥ 1 − 1 4 d − d − 1 2 d = 1 2 + 1 4 d ≥ 1 2 . (74) \lambda_{\min}(\Gamma)\ge1-\frac{1}{4d}-\frac{d-1}{2d}=\frac{1}{2}+\frac{1}{4d}\ge\frac{1}{2}. \tag*{(74)} λ m i n ( Γ ) ≥ 1 − 4 d 1 − 2 d d − 1 = 2 1 + 4 d 1 ≥ 2 1 . (74) Lemma N (Stability of the polar step). For v , u ∈ G v,u\in G v , u ∈ G g v : = Pol ( X v ) g_v:=\operatorname{Pol}(X_v) g v := Pol ( X v )
∥ g v − W v u T g u ∥ M v u , F 2 ≤ 2 κ E ∥ X v − W v u T X u ∥ M v u , F 2 . (75) \lVert g_v-W_{vu}^{\mathsf{T}}g_u\rVert_{M_{vu,F}}^2\le2\kappa_E\lVert X_v-W_{vu}^{\mathsf{T}}X_u\rVert_{M_{vu,F}}^2. \tag*{(75)} ∥ g v − W v u T g u ∥ M v u , F 2 ≤ 2 κ E ∥ X v − W v u T X u ∥ M v u , F 2 . (75) Proof. First, the polar factor is equivariant: if X = P Σ Q T X=P\Sigma Q^{\mathsf{T}} X = P Σ Q T W ∈ O ( d ) W\in O(d) W ∈ O ( d ) W T X = ( W T P ) Σ Q T W^{\mathsf{T}}X=(W^{\mathsf{T}}P)\Sigma Q^{\mathsf{T}} W T X = ( W T P ) Σ Q T Pol ( W T X ) = W T Pol ( X ) \operatorname{Pol}(W^{\mathsf{T}}X)=W^{\mathsf{T}}\operatorname{Pol}(X) Pol ( W T X ) = W T Pol ( X ) σ min ( W T X ) = σ min ( X ) \sigma_{\min}(W^{\mathsf{T}}X)=\sigma_{\min}(X) σ m i n ( W T X ) = σ m i n ( X ) A : = X v A:=X_v A := X v A ′ : = W v u T X u A':=W_{vu}^{\mathsf{T}}X_u A ′ := W v u T X u W v u T g u = Pol ( A ′ ) W_{vu}^{\mathsf{T}}g_u=\operatorname{Pol}(A') W v u T g u = Pol ( A ′ ) σ min ( A ) \sigma_{\min}(A) σ m i n ( A ) σ min ( A ′ ) = σ min ( X u ) \sigma_{\min}(A')=\sigma_{\min}(X_u) σ m i n ( A ′ ) = σ m i n ( X u ) 1 / 2 1/\sqrt{2} 1/ 2 [76 ] :
∥ Pol ( A ) − Pol ( A ′ ) ∥ F ≤ 2 σ min ( A ) + σ min ( A ′ ) ∥ A − A ′ ∥ F , (76) \lVert\operatorname{Pol}(A)-\operatorname{Pol}(A')\rVert_F\le\frac{2}{\sigma_{\min}(A)+\sigma_{\min}(A')}\lVert A-A'\rVert_F, \tag*{(76)} ∥ Pol ( A ) − Pol ( A ′ ) ∥ F ≤ σ m i n ( A ) + σ m i n ( A ′ ) 2 ∥ A − A ′ ∥ F , (76) therefore has prefactor at most 2 / 2 = 2 2/\sqrt{2}=\sqrt{2} 2/ 2 = 2
∥ g v − W v u T g u ∥ F 2 ≤ 2 ∥ X v − W v u T X u ∥ F 2 . (77) \lVert g_v-W_{vu}^{\mathsf{T}}g_u\rVert_F^2\le2\lVert X_v-W_{vu}^{\mathsf{T}}X_u\rVert_F^2. \tag*{(77)} ∥ g v − W v u T g u ∥ F 2 ≤ 2 ∥ X v − W v u T X u ∥ F 2 . (77) Finally, item (iii) of the toolkit applied to each column gives w v u − ∥ C ∥ F 2 ≤ ∥ C ∥ M v u , F 2 ≤ w v u + ∥ C ∥ F 2 w_{vu}^{-}\lVert C\rVert_F^2\le\lVert C\rVert_{M_{vu,F}}^2\le w_{vu}^{+}\lVert C\rVert_F^2 w v u − ∥ C ∥ F 2 ≤ ∥ C ∥ M v u , F 2 ≤ w v u + ∥ C ∥ F 2 C ∈ R d × d C\in\mathbb{R}^{d\times d} C ∈ R d × d w v u + w_{vu}^{+} w v u + 1 / w v u − 1/w_{vu}^{-} 1/ w v u − w v u + / w v u − ≤ κ E w_{vu}^{+}/w_{vu}^{-}\le\kappa_E w v u + / w v u − ≤ κ E
Lemma O (Main O ( d ) O(d) O ( d ) Let g v : = Pol ( X v ) g_v:=\operatorname{Pol}(X_v) g v := Pol ( X v ) g v : = I d g_v:=I_d g v := I d X v X_v X v
ν ( g ) ≤ 2 11 κ E d 3 λ 2 ∑ k ≤ d η ˉ ( x k ) . (78) \nu(g)\le\frac{2^{11}\kappa_Ed^3}{\lambda_2}\sum_{k\le d}\bar{\eta}(x^k). \tag*{(78)} ν ( g ) ≤ λ 2 2 11 κ E d 3 k ≤ d ∑ η ˉ ( x k ) . (78) Proof. By Lemma M the fallback g v = I d g_v=I_d g v = I d G c G^c G c ν ( g ) \nu(g) ν ( g )
Both endpoints in G G G By Lemma N, extending the sum to all ordered pairs since every term is nonnegative, and then applying the columnwise dictionary to the matrix-valued map X X X
1 2 ∑ v , u ∈ G ∥ g v − W v u T g u ∥ M v u , F 2 ≤ 2 κ E ∑ k ( x k ) T B k x k = 2 κ E vol ‾ ∑ k η ˉ ( x k ) , (79) \frac{1}{2}\sum_{v,u\in G}\lVert g_v-W_{vu}^{\mathsf{T}}g_u\rVert_{M_{vu,F}}^2\le2\kappa_E\sum_k(x^k)^{\mathsf{T}}B^kx^k=2\kappa_E\overline{\operatorname{vol}}\sum_k\bar{\eta}(x^k), \tag*{(79)} 2 1 v , u ∈ G ∑ ∥ g v − W v u T g u ∥ M v u , F 2 ≤ 2 κ E k ∑ ( x k ) T B k x k = 2 κ E vol k ∑ η ˉ ( x k ) , (79) using ( x k ) T B k x k = η ˉ ( x k ) ( x k ) T D ˉ x k = η ˉ ( x k ) vol ‾ (x^k)^{\mathsf{T}}B^kx^k=\bar{\eta}(x^k)(x^k)^{\mathsf{T}}\bar{D}x^k=\bar{\eta}(x^k)\overline{\operatorname{vol}} ( x k ) T B k x k = η ˉ ( x k ) ( x k ) T D ˉ x k = η ˉ ( x k ) vol
At least one endpoint in G c G^c G c Here we use only g v , g u ∈ O ( d ) g_v,g_u\in O(d) g v , g u ∈ O ( d ) ∥ g v ∥ F = d \lVert g_v\rVert_F=\sqrt{d} ∥ g v ∥ F = d ∥ g v − W v u T g u ∥ F 2 ≤ ( d + d ) 2 = 4 d \lVert g_v-W_{vu}^{\mathsf{T}}g_u\rVert_F^2\le(\sqrt{d}+\sqrt{d})^2=4d ∥ g v − W v u T g u ∥ F 2 ≤ ( d + d ) 2 = 4 d 4 d w v u + 4d\,w_{vu}^{+} 4 d w v u + d v + ≤ κ E d ˉ v d_v^+\le\kappa_E\bar{d}_v d v + ≤ κ E d ˉ v
1 2 ∑ ( v , u ) meeting G c ∥ g v − W v u T g u ∥ M v u , F 2 ≤ 4 d ∑ v ∈ G c d v + ≤ 4 d κ E vol ‾ ( G c ) ≤ 2 10 κ E d 4 λ 2 vol ‾ ∑ k η ˉ ( x k ) . (80) \frac{1}{2}\sum_{\substack{(v,u)\\\text{meeting }G^c}}\lVert g_v-W_{vu}^{\mathsf{T}}g_u\rVert_{M_{vu,F}}^2\le4d\sum_{v\in G^c}d_v^+\le4d\kappa_E\overline{\operatorname{vol}}(G^c)\le\frac{2^{10}\kappa_Ed^4}{\lambda_2}\overline{\operatorname{vol}}\sum_k\bar{\eta}(x^k). \tag*{(80)} 2 1 ( v , u ) meeting G c ∑ ∥ g v − W v u T g u ∥ M v u , F 2 ≤ 4 d v ∈ G c ∑ d v + ≤ 4 d κ E vol ( G c ) ≤ λ 2 2 10 κ E d 4 vol k ∑ η ˉ ( x k ) . (80) Conclusion. The denominator of ν \nu ν vol ( G ) = ∑ v tr ( D v ) = d vol ‾ \operatorname{vol}(G)=\sum_v\operatorname{tr}(D_v)=d\overline{\operatorname{vol}} vol ( G ) = ∑ v tr ( D v ) = d vol
ν ( g ) ≤ ( 2 κ E d + 2 10 κ E d 3 λ ‾ 2 ) ∑ k η ‾ ( x k ) . (81) \nu(g)\leq\left(\frac{2\kappa_E}{d}+\frac{2^{10}\kappa_E d^3}{\overline{\lambda}_2}\right)\sum_k\overline{\eta}(x^k). \tag*{(81)} ν ( g ) ≤ ( d 2 κ E + λ 2 2 10 κ E d 3 ) k ∑ η ( x k ) . (81) Since λ ‾ 2 ≤ 2 \overline{\lambda}_2\leq2 λ 2 ≤ 2 Lemma I (iii), 2 10 κ E d 3 / λ ‾ 2 ≥ 2 9 κ E d 3 ≥ 2 κ E / d 2^{10}\kappa_Ed^3/\overline{\lambda}_2\geq2^9\kappa_Ed^3\geq2\kappa_E/d 2 10 κ E d 3 / λ 2 ≥ 2 9 κ E d 3 ≥ 2 κ E / d
Proof of Theorem 4.4. Run Algorithm 4.3. Since the z k z^k z k x k = vol ‾ D ‾ − 1 / 2 z k x^k=\sqrt{\overline{\operatorname{vol}}}\,\overline{D}^{-1/2}z^k x k = vol D − 1/2 z k ( x k ) T D ‾ x l = vol ‾ ( z k ) T z l = vol ‾ δ k l (x^k)^\mathsf{T}\overline{D}x^l=\overline{\operatorname{vol}}(z^k)^\mathsf{T}z^l=\overline{\operatorname{vol}}\delta_{kl} ( x k ) T D x l = vol ( z k ) T z l = vol δ k l D ‾ \overline{D} D ∥ n x k ∥ D ‾ 0 2 = vol ‾ \lVert nx^k\rVert^2_{\overline{D}_0}=\overline{\operatorname{vol}} ∥ n x k ∥ D 0 2 = vol η ‾ ( x k ) = ( z k ) T B ‾ z k = λ k ( B ‾ ) \overline{\eta}(x^k)=(z^k)^\mathsf{T}\overline{B}z^k=\lambda_k(\overline{B}) η ( x k ) = ( z k ) T B z k = λ k ( B ) g g g ν G ≤ ν ( g ) \nu_G\leq\nu(g) ν G ≤ ν ( g )
ν G ≤ 2 11 κ E d 3 λ ‾ 2 ∑ k ≤ d λ k ( B ‾ ) . (82) \nu_G\leq\frac{2^{11}\kappa_Ed^3}{\overline{\lambda}_2}\sum_{k\leq d}\lambda_k(\overline{B}). \tag*{(82)} ν G ≤ λ 2 2 11 κ E d 3 k ≤ d ∑ λ k ( B ) . (82) It remains to return to B ~ \widetilde{B} B λ 2 ( L − ) \lambda_2(\mathcal{L}_{-}) λ 2 ( L − ) Lemma I (ii), λ ‾ 2 − 1 ≤ κ E λ 2 ( L − ) − 1 \overline{\lambda}_2^{-1}\leq\kappa_E\lambda_2(\mathcal{L}_{-})^{-1} λ 2 − 1 ≤ κ E λ 2 ( L − ) − 1 Lemma I (iv) and item (i) of the toolkit, λ k ( B ‾ ) ≤ κ D λ k ( B ~ ) ≤ κ E λ k ( B ~ ) \lambda_k(\overline{B})\leq\kappa_D\lambda_k(\widetilde{B})\leq\kappa_E\lambda_k(\widetilde{B}) λ k ( B ) ≤ κ D λ k ( B ) ≤ κ E λ k ( B )
ν G ≤ 2 11 κ E 3 d 3 λ 2 ( L − ) ∑ k ≤ d λ k ( B ~ ) . (83) \nu_G\leq\frac{2^{11}\kappa_E^3d^3}{\lambda_2(\mathcal{L}_{-})}\sum_{k\leq d}\lambda_k(\widetilde{B}). \tag*{(83)} ν G ≤ λ 2 ( L − ) 2 11 κ E 3 d 3 k ≤ d ∑ λ k ( B ) . (83) Path determinacy (§ 4.3 ). If the walker of Definition 4.3 starts at ( v 0 , x ^ 0 ) (v_0,\widehat{x}_0) ( v 0 , x 0 ) γ : v 0 → ⋯ → v t \gamma:v_0\to\cdots\to v_t γ : v 0 → ⋯ → v t t t t ( v t , T γ x ^ 0 ) (v_t,T_\gamma\widehat{x}_0) ( v t , T γ x 0 ) T γ T_\gamma T γ
Proof. Each step applies W v i v i + 1 W_{v_iv_{i+1}} W v i v i + 1 γ \gamma γ T γ x ^ 0 T_\gamma\widehat{x}_0 T γ x 0 T γ T_\gamma T γ
Conserved observables (§ 4.3 ). For y ∈ R n d y\in\mathbb{R}^{nd} y ∈ R n d f y ( v , x ^ ) : = ⟨ x ^ , y v ⟩ f_y(v,\widehat{x}):=\langle\widehat{x},y_v\rangle f y ( v , x ) := ⟨ x , y v ⟩ f y f_y f y y ∈ ker ( B ) y\in\ker(B) y ∈ ker ( B )
Proof. If y ∈ ker ( B ) y\in\ker(B) y ∈ ker ( B ) y u = W v u y v y_u=W_{vu}y_v y u = W v u y v x ^ t \widehat{x}_t x t y v t y_{v_t} y v t x ^ 0 \widehat{x}_0 x 0 y v 0 y_{v_0} y v 0 T γ T_\gamma T γ
Conversely, the increment of f y f_y f y v → u v\to u v → u x ^ \widehat{x} x ⟨ W v u x ^ , y u ⟩ − ⟨ x ^ , y v ⟩ = ⟨ x ^ , W v u T y u − y v ⟩ \langle W_{vu}\widehat{x},y_u\rangle-\langle\widehat{x},y_v\rangle=\langle\widehat{x},W_{vu}^{\mathsf{T}}y_u-y_v\rangle ⟨ W v u x , y u ⟩ − ⟨ x , y v ⟩ = ⟨ x , W v u T y u − y v ⟩ f y f_y f y x ^ ∈ S d − 1 \widehat{x}\in S^{d-1} x ∈ S d − 1 y u = W v u y v y_u=W_{vu}y_v y u = W v u y v y ∈ ker ( B ) y\in\ker(B) y ∈ ker ( B )
Theorem 5.1 (Unique continuation). Let M M M c ∈ ker ∂ ∗ ∩ ker B 1 F c\in\ker\partial^*\cap\ker B_1^F c ∈ ker ∂ ∗ ∩ ker B 1 F c e = 0 c_e=0 c e = 0 e e e c = 0 c=0 c = 0
Proof. Let D ( e ) D(e) D ( e ) e e e M M M c e = 0 c_e=0 c e = 0 e e e D ( e ) D(e) D ( e ) D ( e ) = 0 D(e)=0 D ( e ) = 0
Assume c e = 0 c_e=0 c e = 0 e e e D ( e ) ≤ k D(e)\leq k D ( e ) ≤ k e e e D ( e ) = k + 1 D(e)=k+1 D ( e ) = k + 1 e 1 e_1 e 1 k k k e , e 1 e,e_1 e , e 1 c e = 0 c_e=0 c e = 0 f f f v 1 ⊴ e , e 1 ⊴ f v_1\trianglelefteq e,e_1\trianglelefteq f v 1 ⊴ e , e 1 ⊴ f e 2 e_2 e 2 f f f e 1 e_1 e 1 v 2 ⊴ e 1 , e 2 v_2\trianglelefteq e_1,e_2 v 2 ⊴ e 1 , e 2 v 1 v_1 v 1 M M M c e 2 = 0 c_{e_2}=0 c e 2 = 0 c e = 0 c_e=0 c e = 0
If k = 0 k=0 k = 0 v 1 v_1 v 1 v 2 v_2 v 2 D ( e ) = 0 D(e)=0 D ( e ) = 0 v 2 v_2 v 2 D ( e 2 ) = 0 D(e_2)=0 D ( e 2 ) = 0 k > 0 k>0 k > 0 e 3 e_3 e 3 D ( e 3 ) = k − 1 D(e_3)=k-1 D ( e 3 ) = k − 1 e 1 e_1 e 1 v 1 v_1 v 1 D ( e ) = k D(e)=k D ( e ) = k v 2 v_2 v 2 D ( e 2 ) = k D(e_2)=k D ( e 2 ) = k c e 2 = 0 c_{e_2}=0 c e 2 = 0
Theorem 5.2 (Bochner theorem for combinatorial manifolds). Let M M M n n n n ≤ 3 n \le3 n ≤ 3 Ric F ⪰ 0 \operatorname{Ric}_{\mathcal{F}} \succeq0 Ric F ⪰ 0 dim H 1 ( M ; F ) ≤ n d \dim\mathcal{H}^{1}(M;\mathcal{F}) \le nd dim H 1 ( M ; F ) ≤ n d
Proof. In each case we exhibit n n n v v v v v v ker ( H 1 F ) → F ( e 1 ) ⊕ ⋯ ⊕ F ( e n ) \ker(H^{\mathcal{F}}_{1}) \to\mathcal{F}(e_{1}) \oplus\cdots\oplus\mathcal{F}(e_{n}) ker ( H 1 F ) → F ( e 1 ) ⊕ ⋯ ⊕ F ( e n ) dim H 1 ( M ; F ) = dim ker ( H 1 F ) ≤ n d \dim\mathcal{H}^{1}(M;\mathcal{F}) = \dim\ker(H^{\mathcal{F}}_{1}) \le nd dim H 1 ( M ; F ) = dim ker ( H 1 F ) ≤ n d
n ≤ 1 n \le1 n ≤ 1 n = 0 n = 0 n = 0 M M M n = 1 n = 1 n = 1 M M M B 1 F B^{\mathcal{F}}_{1} B 1 F φ e : ker ( H 1 F ) → F ( e ) \varphi_e : \ker(H^{\mathcal{F}}_{1}) \to\mathcal{F}(e) φ e : ker ( H 1 F ) → F ( e ) e e e n = 1 n = 1 n = 1
n = 2 n = 2 n = 2 e 1 , e 2 e_1,e_2 e 1 , e 2 v v v f f f v v v e 1 , e 2 , … , e k e_1,e_2,\ldots,e_k e 1 , e 2 , … , e k k ≥ 4 k \ge4 k ≥ 4 e 3 , … , e k e_3,\ldots,e_k e 3 , … , e k e 1 e_1 e 1 e 2 e_2 e 2 c e 1 = c e 2 = 0 c_{e_1}=c_{e_2}=0 c e 1 = c e 2 = 0 c = 0 c=0 c = 0 e 1 , e 2 , e 3 e_1,e_2,e_3 e 1 , e 2 , e 3 v v v x v ∈ F ( v ) x_v \in\mathcal{F}(v) x v ∈ F ( v ) 0 = ⟨ ∂ c , x v ⟩ = ± c e 3 F v ◃ e 3 x v 0 = \langle\partial c,x_v\rangle= \pm c_{e_3}\mathcal{F}_{v\triangleleft e_3}x_v 0 = ⟨ ∂ c , x v ⟩ = ± c e 3 F v ◃ e 3 x v x v x_v x v c e 3 = 0 c_{e_3}=0 c e 3 = 0
n = 3 n = 3 n = 3 [24 Theorem 4.4] . As for n ≤ 2 n \le2 n ≤ 2 c c c parallel propagation : if e , e ~ e,\widetilde{e} e , e c e = 0 c_e = 0 c e = 0 c e ~ = 0 c_{\widetilde{e}} = 0 c e = 0 vertex relation : if c c c v v v e ∗ e^* e ∗ 0 = ⟨ ∂ c , x v ⟩ = ± c e ∗ F v ◃ e ∗ x v 0 = \langle\partial c,x_v\rangle= \pm c_{e^*}\mathcal{F}_{v\triangleleft e^*}x_v 0 = ⟨ ∂ c , x v ⟩ = ± c e ∗ F v ◃ e ∗ x v x v ∈ F ( v ) x_v \in\mathcal{F}(v) x v ∈ F ( v ) x v x_v x v F v ◃ e ∗ ∗ c e ∗ = 0 \mathcal{F}^{*}_{v\triangleleft e^*}c_{e^*} = 0 F v ◃ e ∗ ∗ c e ∗ = 0 c e ∗ = 0 c_{e^*} = 0 c e ∗ = 0 ± ω v c e ∗ = 0 \pm\omega_v c_{e^*} = 0 ± ω v c e ∗ = 0 M M M v v v v v v c = 0 c = 0 c = 0 v v v v v v S 2 S^2 S 2 v v v K K K K 5 K_5 K 5 S 2 S^2 S 2 K K K v v v K K K e 1 , … , e 4 e_1,\ldots,e_4 e 1 , … , e 4 e 5 e_5 e 5 K K K e 4 e_4 e 4 e 5 e_5 e 5 e 4 e_4 e 4 e 2 , e 3 , e 4 e_2,e_3,e_4 e 2 , e 3 , e 4 e 5 e_5 e 5 e 4 e_4 e 4 e 5 e_5 e 5 e 1 e_1 e 1
Theorem 5.3. Let M M M Ric F ⪰ 0 \operatorname{Ric}_{\mathcal{F}} \succeq0 Ric F ⪰ 0 dim H 1 ( M ; F ) ≤ d ⋅ D ( M ) \dim\mathcal{H}^{1}(M;\mathcal{F}) \le d \cdot D(M) dim H 1 ( M ; F ) ≤ d ⋅ D ( M )
Proof. Fix v v v dim ker ( H 1 F ) ≤ d ⋅ D ( v ) \dim\ker(H^{\mathcal{F}}_{1}) \le d \cdot D(v) dim ker ( H 1 F ) ≤ d ⋅ D ( v ) D ( v ) = N ( v ) D(v) = N(v) D ( v ) = N ( v ) v v v v v v c = 0 c = 0 c = 0
If instead some class { e ∗ } \{e^*\} { e ∗ } D ( v ) = N ( v ) − 1 D(v) = N(v) - 1 D ( v ) = N ( v ) − 1 v v v e ∗ e^* e ∗ 0 = ⟨ ∂ c , x v ⟩ = c e ∗ T F v ◃ e ∗ x v 0 = \langle\partial c,x_v\rangle= c_{e^*}^{\mathsf{T}}\mathcal{F}_{v\triangleleft e^*}x_v 0 = ⟨ ∂ c , x v ⟩ = c e ∗ T F v ◃ e ∗ x v x v x_v x v c e ∗ = 0 c_{e^*} = 0 c e ∗ = 0
Further Properties of Bochner Matrices
This appendix collects results on Bochner matrices that the main text does not use: a comparison with a scalar Laplacian, the interplay of balance and antibalance, and two further properties of the random walk.
Trace comparison
Following Hansen, we extend to Bochner matrices the comparison he develops between the block spectrum and a scalar one for matrix-weighted Laplacians [26 ] .
Definition B.1 (Trace shadow). Set w ^ v u : = tr ( B v u ) \widehat{w}_{vu} := \operatorname{tr}(B_{vu}) w v u := tr ( B v u ) L ^ ∈ R n × n \widehat{L} \in\mathbb{R}^{n \times n} L ∈ R n × n L ^ v u : = − w ^ v u \widehat{L}_{vu} := -\widehat{w}_{vu} L v u := − w v u v ≠ u v \ne u v = u L ^ v v : = tr ( D v ) \widehat{L}_{vv} := \operatorname{tr}(D_v) L v v := tr ( D v )
Theorem B.1 (Trace comparison). L ^ \widehat{L} L m m m
∑ i ≤ m d λ i ( B ) ≤ ∑ j ≤ m λ j ( L ^ ) , ∑ i > n d − m d λ i ( B ) ≥ ∑ j > n − m λ j ( L ^ ) , (84) \sum_{i \le md} \lambda_i(B) \le\sum_{j \le m} \lambda_j(\widehat{L}), \qquad\sum_{i > nd-md} \lambda_i(B) \ge\sum_{j > n-m} \lambda_j(\widehat{L}), \tag*{(84)} i ≤ m d ∑ λ i ( B ) ≤ j ≤ m ∑ λ j ( L ) , i > n d − m d ∑ λ i ( B ) ≥ j > n − m ∑ λ j ( L ) , (84) with equality at m = n m=n m = n
Proof. Symmetry and the split-vector identity. Symmetry is (H1), since w ^ u v = tr ( B u v ) = tr ( B v u T ) = w ^ v u \widehat{w}_{uv} = \operatorname{tr}(B_{uv}) = \operatorname{tr}(B_{vu}^{\mathsf T}) = \widehat{w}_{vu} w uv = tr ( B uv ) = tr ( B v u T ) = w v u ξ ∈ R n \xi\in\mathbb{R}^n ξ ∈ R n e 1 , … , e d e_1,\ldots,e_d e 1 , … , e d ξ ⊗ e α \xi\otimes e_\alpha ξ ⊗ e α ( ξ ⊗ e α ) v : = ξ v e α (\xi\otimes e_\alpha)_v := \xi_v e_\alpha ( ξ ⊗ e α ) v := ξ v e α ∑ α ( A e α ) T M ( A e α ) = tr ( A T M A ) \sum_\alpha(Ae_\alpha)^{\mathsf T}M(Ae_\alpha) = \operatorname{tr}(A^{\mathsf T}MA) ∑ α ( A e α ) T M ( A e α ) = tr ( A T M A )
∑ α = 1 d ( ξ ⊗ e α ) T B ( ξ ⊗ e α ) = 1 2 ∑ v ≠ u tr [ ( ξ v I − ξ u W v u T ) T M v u ( ξ v I − ξ u W v u T ) ] , (85) \sum_{\alpha=1}^{d}(\xi\otimes e_\alpha)^{\mathsf T}B(\xi\otimes e_\alpha)
= \frac{1}{2}\sum_{v\ne u}\operatorname{tr}\left[(\xi_v I-\xi_u W_{vu}^{\mathsf T})^{\mathsf T}M_{vu}(\xi_v I-\xi_u W_{vu}^{\mathsf T})\right], \tag*{(85)} α = 1 ∑ d ( ξ ⊗ e α ) T B ( ξ ⊗ e α ) = 2 1 v = u ∑ tr [ ( ξ v I − ξ u W v u T ) T M v u ( ξ v I − ξ u W v u T ) ] , (85) and expanding, using tr ( W M W T ) = tr ( M ) \operatorname{tr}(WMW^{\mathsf T})=\operatorname{tr}(M) tr ( W M W T ) = tr ( M ) ∑ v ξ v 2 tr ( D v ) − ∑ v ≠ u ξ v ξ u w ^ v u = ξ T L ^ ξ \sum_v \xi_v^2\operatorname{tr}(D_v)-\sum_{v\ne u}\xi_v\xi_u\widehat{w}_{vu}=\xi^{\mathsf T}\widehat{L}\xi ∑ v ξ v 2 tr ( D v ) − ∑ v = u ξ v ξ u w v u = ξ T L ξ ξ \xi ξ L ^ ⪰ 0 \widehat{L}\succeq0 L ⪰ 0
Conclusion. Let ξ 1 , … , ξ m \xi^1,\ldots,\xi^m ξ 1 , … , ξ m L ^ \widehat{L} L m m m Q Q Q m d md m d ξ j ⊗ e α \xi^j\otimes e_\alpha ξ j ⊗ e α ( ξ j ⊗ e α ) T ( ξ l ⊗ e β ) = ( ( ξ j ) T ξ l ) δ α β (\xi^j\otimes e_\alpha)^{\mathsf T}(\xi^l\otimes e_\beta)=((\xi^j)^{\mathsf T}\xi^l)\delta_{\alpha\beta} ( ξ j ⊗ e α ) T ( ξ l ⊗ e β ) = (( ξ j ) T ξ l ) δ α β § 10 applied to A = B A=B A = B
∑ i ≤ m d λ i ( B ) ≤ tr ( Q T B Q ) = ∑ j ≤ m ∑ α ( ξ j ⊗ e α ) T B ( ξ j ⊗ e α ) = ∑ j ≤ m λ j ( L ^ ) . (86) \sum_{i\le md}\lambda_i(B)\le\operatorname{tr}(Q^{\mathsf T}BQ)=\sum_{j\le m}\sum_\alpha(\xi^j\otimes e_\alpha)^{\mathsf T}B(\xi^j\otimes e_\alpha)=\sum_{j\le m}\lambda_j(\widehat{L}). \tag*{(86)} i ≤ m d ∑ λ i ( B ) ≤ tr ( Q T B Q ) = j ≤ m ∑ α ∑ ( ξ j ⊗ e α ) T B ( ξ j ⊗ e α ) = j ≤ m ∑ λ j ( L ) . (86) The second inequality follows by the same argument applied to − B -B − B − L ^ -\widehat{L} − L B B B L ^ \widehat{L} L m = n m=n m = n Q Q Q tr ( B ) = ∑ v tr ( D v ) = tr ( L ^ ) \operatorname{tr}(B)=\sum_v\operatorname{tr}(D_v)=\operatorname{tr}(\widehat{L}) tr ( B ) = ∑ v tr ( D v ) = tr ( L )
Balance and antibalance
Proposition B.1 (The two extremes). Let x ∈ ker ( B ) x\in\ker(B) x ∈ ker ( B ) z ∈ ker ( N ) z\in\ker(N) z ∈ ker ( N ) G G G G G G ⟨ x v , z v ⟩ = 0 \langle x_v,z_v\rangle=0 ⟨ x v , z v ⟩ = 0 dim ker ( B ) + dim E 2 ( B ~ ) ≤ d \dim\ker(B)+\dim E_2(\widetilde{B})\le d dim ker ( B ) + dim E 2 ( B ) ≤ d G G G dim ker ( B ) = dim E 2 ( B ~ ) \dim\ker(B)=\dim E_2(\widetilde{B}) dim ker ( B ) = dim E 2 ( B )
Proof. Put f ( v ) : = ⟨ x v , z v ⟩ f(v):=\langle x_v,z_v\rangle f ( v ) := ⟨ x v , z v ⟩ x u = W v u x v x_u=W_{vu}x_v x u = W v u x v z u = − W v u z v z_u=-W_{vu}z_v z u = − W v u z v W v u W_{vu} W v u f ( u ) = − f ( v ) f(u)=-f(v) f ( u ) = − f ( v ) f f f
If G G G f = 0 f=0 f = 0 f ≡ 0 f\equiv0 f ≡ 0 K = { x v 0 } K=\{x_{v_0}\} K = { x v 0 } K ′ = { z v 0 } K'=\{z_{v_0}\} K ′ = { z v 0 } v 0 v_0 v 0 R d \mathbb{R}^d R d dim ker ( B ) \dim\ker(B) dim ker ( B ) dim E 2 ( B ~ ) \dim E_2(\widetilde{B}) dim E 2 ( B ) d d d
If G G G V + ⊔ V − V_+\sqcup V_- V + ⊔ V − z v : = x v z_v:=x_v z v := x v V + V_+ V + z v : = − x v z_v:=-x_v z v := − x v V − V_- V − z u = − W v u z v z_u=-W_{vu}z_v z u = − W v u z v x ↦ z x\mapsto z x ↦ z ker ( B ) → ker ( N ) \ker(B)\to\ker(N) ker ( B ) → ker ( N )
Similarly to our treatment, balancedness, bipartiteness and their joint effect on the spectrum of a normalized Laplacian have been investigated on gain graphs by Kannan et al. [77 ] . A Bochner matrix is not a gain graph: its edge label B v u = M v u W v u T B_{vu}=M_{vu}W_{vu}^{\mathsf T} B v u = M v u W v u T W v u ∈ O ( d ) W_{vu}\in O(d) W v u ∈ O ( d ) M v u M_{vu} M v u
The non-bipartite case has no scalar analogue: the two kernels are orthogonal pointwise at every vertex, yet can both be nonzero, whereas for d = 1 d=1 d = 1 W 12 = W 23 = I W_{12}=W_{23}=I W 12 = W 23 = I W 31 = diag ( 1 , − 1 ) W_{31}=\operatorname{diag}(1,-1) W 31 = diag ( 1 , − 1 ) dim ker ( B ) = dim E 2 ( B ~ ) = 1 \dim\ker(B)=\dim E_2(\widetilde{B})=1 dim ker ( B ) = dim E 2 ( B ) = 1 e 1 , e 2 e_1,e_2 e 1 , e 2
Two further properties of the random walk
Confinement. Since a nonzero kernel vector never vanishes, choosing x 1 , … , x k ∈ ker ( B ) x^{1},\ldots,x^{k}\in\ker(B) x 1 , … , x k ∈ ker ( B ) k : = dim ker ( B ) k:=\dim\ker(B) k := dim ker ( B ) v 0 v_{0} v 0 k k k
Corollary B.1 (Confinement). With x 1 , … , x k x^{1},\ldots,x^{k} x 1 , … , x k c i : = ⟨ x ^ 0 , x v 0 i ⟩ c_{i}:=\langle\hat{x}_{0},x^{i}_{v_{0}}\rangle c i := ⟨ x ^ 0 , x v 0 i ⟩ r : = ( 1 − ∑ i c i 2 ) 1 / 2 r:=(1-\sum_{i}c_{i}^{2})^{1/2} r := ( 1 − ∑ i c i 2 ) 1/2 t t t ⟨ x ^ t , x v t i ⟩ = c i \langle\hat{x}_{t},x^{i}_{v_{t}}\rangle=c_{i} ⟨ x ^ t , x v t i ⟩ = c i i i i ∥ x ^ t − ∑ i c i x v t i ∥ = r \lVert\hat{x}_{t}-\sum_{i}c_{i}x^{i}_{v_{t}}\rVert=r ∥ x ^ t − ∑ i c i x v t i ∥ = r d − k − 1 d-k-1 d − k − 1 x ^ t \hat{x}_{t} x ^ t v t v_{t} v t k = d k=d k = d x ^ 0 = x v 0 \hat{x}_{0}=x_{v_{0}} x ^ 0 = x v 0 x ∈ ker ( B ) x\in\ker(B) x ∈ ker ( B )
Proof. By Proposition 4.1 each x i x^{i} x i x v t i = T γ x v 0 i x^{i}_{v_{t}}=T_{\gamma}x^{i}_{v_{0}} x v t i = T γ x v 0 i T γ T_{\gamma} T γ x v t i x^{i}_{v_{t}} x v t i x i x^{i} x i ⟨ x ^ t , x v t i ⟩ = c i \langle\hat{x}_{t},x^{i}_{v_{t}}\rangle=c_{i} ⟨ x ^ t , x v t i ⟩ = c i ∥ x ^ t ∥ = 1 \lVert\hat{x}_{t}\rVert=1 ∥ x ^ t ∥ = 1 x ^ t \hat{x}_{t} x ^ t span { x v t i } \operatorname{span}\{x^{i}_{v_{t}}\} span { x v t i } ( 1 − ∑ i c i 2 ) 1 / 2 = r (1-\sum_{i}c_{i}^{2})^{1/2}=r ( 1 − ∑ i c i 2 ) 1/2 = r k = d k=d k = d x v t i x^{i}_{v_{t}} x v t i c i c_{i} c i x ^ t \hat{x}_{t} x ^ t r = 0 r=0 r = 0 x ^ 0 = x v 0 \hat{x}_{0}=x_{v_{0}} x ^ 0 = x v 0 x ∈ ker ( B ) x\in\ker(B) x ∈ ker ( B ) x 1 : = x x^{1}:=x x 1 := x c 1 = 1 c_{1}=1 c 1 = 1 r = 0 r=0 r = 0
The bound can be strict: for d = 1 d=1 d = 1 { − 1 , + 1 } \{-1,+1\} { − 1 , + 1 } d = 2 d=2 d = 2
Reversibility. The walk of Definition 4.3 is not reversible in general: detailed balance would force M v u M_{vu} M v u D v D_{v} D v D u D_{u} D u D v D_{v} D v
Proposition B.2 (Failure of reversibility). There exist Bochner matrices satisfying (H1)–(H3) for which the walk of Definition 4.3 admits no reversible measure.
Proof. Take d = 2 d=2 d = 2 G G G { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } { 1 , 2 , 3 } × { e 1 } \{1,2,3\}\times\{e_{1}\} { 1 , 2 , 3 } × { e 1 } q v u = ω v T M v u ω v q_{vu}=\omega_{v}^{\mathsf{T}}M_{vu}\omega_{v} q v u = ω v T M v u ω v ω v \omega_{v} ω v D v − 1 / 2 D_{v}^{-1/2} D v − 1/2
M 12 = ( 2 1 1 2 ) , M 13 = ( 3 1 1 3 ) , M 23 = ( 5 / 2 − 1 − 1 5 / 2 ) , (87) M_{12}=\begin{pmatrix}2&1\\1&2\end{pmatrix},\quad M_{13}=\begin{pmatrix}3&1\\1&3\end{pmatrix},\quad M_{23}=\begin{pmatrix}5/2&-1\\-1&5/2\end{pmatrix}, \tag*{(87)} M 12 = ( 2 1 1 2 ) , M 13 = ( 3 1 1 3 ) , M 23 = ( 5/2 − 1 − 1 5/2 ) , (87) all positive definite, so (H1)–(H3) hold. Then D 1 = ( 5 2 2 5 ) D_{1}=\begin{pmatrix}5&2\\2&5\end{pmatrix} D 1 = ( 5 2 2 5 ) D 2 = 9 2 I D_{2}=\frac{9}{2}I D 2 = 2 9 I D 3 = 11 2 I D_{3}=\frac{11}{2}I D 3 = 2 11 I D 1 D_{1} D 1 7 , 3 7,3 7 , 3 f ± = 1 2 ( 1 , ± 1 ) f_{\pm}=\frac{1}{\sqrt{2}}(1,\pm1) f ± = 2 1 ( 1 , ± 1 ) D 1 − 1 / 2 D_{1}^{-1/2} D 1 − 1/2 a = 7 + 3 2 21 a=\frac{\sqrt{7}+\sqrt{3}}{2\sqrt{21}} a = 2 21 7 + 3 b = 7 − 3 2 21 b=\frac{\sqrt{7}-\sqrt{3}}{2\sqrt{21}} b = 2 21 7 − 3 a 2 + b 2 = 5 21 a^{2}+b^{2}=\frac{5}{21} a 2 + b 2 = 21 5 a b = − 1 21 ab=-\frac{1}{21} ab = − 21 1 ( m 1 1 m ) \begin{pmatrix}m&1\\1&m\end{pmatrix} ( m 1 1 m ) ( a , b ) (a,b) ( a , b ) m ( a 2 + b 2 ) + 2 a b m(a^{2}+b^{2})+2ab m ( a 2 + b 2 ) + 2 ab q 12 = 13 21 q_{12}=\frac{13}{21} q 12 = 21 13 q 13 = 13 21 q_{13}=\frac{13}{21} q 13 = 21 13 2 , 3 2,3 2 , 3 q 21 = 4 9 q_{21}=\frac{4}{9} q 21 = 9 4 q 23 = 5 9 q_{23}=\frac{5}{9} q 23 = 9 5 q 31 = 6 11 q_{31}=\frac{6}{11} q 31 = 11 6 q 32 = 5 11 q_{32}=\frac{5}{11} q 32 = 11 5 q 12 q 23 q 31 = 2079 2079 q_{12}q_{23}q_{31}=\frac{2079}{2079} q 12 q 23 q 31 = 2079 2079 q 13 q 32 q 21 = 260 2079 q_{13}q_{32}q_{21}=\frac{260}{2079} q 13 q 32 q 21 = 2079 260
The fix is to normalize outside the quadratic form, dividing by x ^ T D v x ^ \hat{x}^{\mathsf{T}}D_{v}\hat{x} x ^ T D v x ^ M u v = W v u M v u W v u T M_{uv}=W_{vu}M_{vu}W_{vu}^{\mathsf{T}} M uv = W v u M v u W v u T x ^ T M v u x ^ \hat{x}^{\mathsf{T}}M_{vu}\hat{x} x ^ T M v u x ^
Proposition B.3 (A reversible variant). Under (H1)–(H3), the walk with the same fibre update but jump law
p v u R ( x ^ ) : = x ^ T M v u x ^ x ^ T D v x ^ (88) p^{\mathrm{R}}_{vu}(\hat{x}):=\frac{\hat{x}^{\mathsf{T}}M_{vu}\hat{x}}{\hat{x}^{\mathsf{T}}D_{v}\hat{x}} \tag*{(88)} p v u R ( x ^ ) := x ^ T D v x ^ x ^ T M v u x ^ (88) is reversible with respect to the measure μ \mu μ { v } × S \{v\}\times S { v } × S d vol ( G ) ∫ S d − 1 x ^ T D v x ^ σ ( d x ^ ) \frac{d}{\operatorname{vol}(G)}\int_{S^{d-1}}\hat{x}^{\mathsf{T}}D_{v}\hat{x}\,\sigma(\mathrm{d}\hat{x}) vol ( G ) d ∫ S d − 1 x ^ T D v x ^ σ ( d x ^ ) σ \sigma σ S d − 1 S^{d-1} S d − 1 π v = tr ( D v ) / vol ( G ) \pi_{v}=\operatorname{tr}(D_{v})/\operatorname{vol}(G) π v = tr ( D v ) / vol ( G ) V V V
Proof. That p v u R p^{\mathrm{R}}_{vu} p v u R 1 1 1 v v v ∑ u ∼ v M v u = D v \sum_{u\sim v}M_{vu}=D_{v} ∑ u ∼ v M v u = D v x ^ T D v x ^ > 0 \hat{x}^{\mathsf{T}}D_{v}\hat{x}>0 x ^ T D v x ^ > 0 ∫ S d − 1 x ^ T D v x ^ σ ( d x ^ ) = tr ( D v ) / d \int_{S^{d-1}}\hat{x}^{\mathsf{T}}D_{v}\hat{x}\,\sigma(\mathrm{d}\hat{x})=\operatorname{tr}(D_{v})/d ∫ S d − 1 x ^ T D v x ^ σ ( d x ^ ) = tr ( D v ) / d μ \mu μ 1 1 1 ( v , x ^ ) (v,\hat{x}) ( v , x ^ ) ( v , u ) (v,u) ( v , u ) ( u , W v u x ^ ) (u,W_{vu}\hat{x}) ( u , W v u x ^ ) W u v = W v u T W_{uv}=W_{vu}^{\mathsf{T}} W uv = W v u T
d vol ( G ) ( x ^ T D v x ^ ) x ^ T M v u x ^ x ^ T D v x ^ = d vol ( G ) x ^ T M v u x ^ . (89) \frac{d}{\operatorname{vol}(G)}(\hat{x}^{\mathsf{T}}D_{v}\hat{x})\frac{\hat{x}^{\mathsf{T}}M_{vu}\hat{x}}{\hat{x}^{\mathsf{T}}D_{v}\hat{x}}=\frac{d}{\operatorname{vol}(G)}\hat{x}^{\mathsf{T}}M_{vu}\hat{x}. \tag*{(89)} vol ( G ) d ( x ^ T D v x ^ ) x ^ T D v x ^ x ^ T M v u x ^ = vol ( G ) d x ^ T M v u x ^ . (89) and the backward flow, with y ^ = W v u x ^ \hat{y}=W_{vu}\hat{x} y ^ = W v u x ^ d vol ( G ) y ^ ⊤ M u v y ^ \frac{d}{\operatorname{vol}(G)}\hat{y}^{\top}M_{uv}\hat{y} vol ( G ) d y ^ ⊤ M uv y ^ W v u M v u W v u ⊤ = M u v W_{vu}M_{vu}W_{vu}^{\top}=M_{uv} W v u M v u W v u ⊤ = M uv x ^ ↦ W v u x ^ \hat{x}\mapsto W_{vu}\hat{x} x ^ ↦ W v u x ^ σ \sigma σ μ \mu μ
The two jump laws coincide whenever D v D_v D v
Conviction: Protocol and Additional Material
Protocol
All interventions run on a model whose weights are loaded from the best-validation-epoch checkpoint and never updated. The candidate set is always a subset of the training nodes and the evaluation set always the full test set, so the quantity compared is identical across strategies, budgets and modes.
Interventions. Masking replaces the features of the selected nodes, by zero or by the dataset feature mean, and leaves the graph untouched; the mean is an unsupervised statistic computed over all nodes. Gating scales every cross-node entry of the sparse diffusion Laplacian by the gate of the source node, so a gated node keeps its own state and only what it transmits is suppressed. In the hard variant used in the body the gate is 0 on the selected nodes and 1 elsewhere; in the soft variant of Appendix § 13 .§ 3 it varies continuously:
g ( u ) = g min + ( 1 − g min ) s ( u ) − min v s ( v ) max v s ( v ) − min v s ( v ) , g min = 0.1 , (90) g(u)=g_{\min}+(1-g_{\min})\frac{s(u)-\min_v s(v)}{\max_v s(v)-\min_v s(v)},\qquad g_{\min}=0.1, \tag*{(90)} g ( u ) = g m i n + ( 1 − g m i n ) max v s ( v ) − min v s ( v ) s ( u ) − min v s ( v ) , g m i n = 0.1 , (90) with s s s Pruning deletes the selected nodes together with their incident edges and relabels the remaining ones; since the graph size is fixed at model construction, a new model is built for the reduced graph and the same frozen parameters are loaded into it, so no parameter is re-estimated.
Selection strategies. At each budget k ∈ { 1 % , 5 % , 10 % , 20 % , 30 % } k\in\{1\%,5\%,10\%,20\%,30\%\} k ∈ { 1% , 5% , 10% , 20% , 30% } k % k\% k % k k k
Decile experiment. It sorts the training pool by one criterion, splits it into ten disjoint bins of equal size, and perturbs exactly one bin at a time, each against the same unperturbed baseline. Instead, the budget sweep itself is cumulative: its selections are nested, the 30% one containing the 10% one, since each budget takes the top (or the bottom) k % k\% k % k k k
Aggregation. The relative drop is formed fold by fold, each fold against its own unperturbed baseline, and normalized by the headroom above chance:
drop % ( s ) = 100 ⋅ m b a s e l i n e − m s m b a s e l i n e − m c h a n c e , m c h a n c e = { 0 accuracy , 0.5 ROC-AUC . (91) \operatorname{drop}\%(s)=100\cdot\frac{m_{\mathrm{baseline}}-m_s}{m_{\mathrm{baseline}}-m_{\mathrm{chance}}},\qquad
m_{\mathrm{chance}}=
\begin{cases}
0 & \text{accuracy},\\
0.5 & \text{ROC-AUC}.
\end{cases} \tag*{(91)} drop % ( s ) = 100 ⋅ m baseline − m chance m baseline − m s , m chance = { 0 0.5 accuracy , ROC-AUC . (91) so a cell is the percentage of the learnt signal the intervention destroys, and means the same on an accuracy dataset and on an AUC one. Folds are then averaged within a dataset and the datasets averaged unweighted, so every benchmark counts the same. The quoted spread is the standard error across the per-dataset drops, and shows the variation across datasets.
Cornell and Wisconsin are excluded from the aggregation, since their training pools are too small for a percentage budget to be meaningful; every number reported is therefore over the remaining eight datasets.
The tables of this appendix follow the conventions of Table 1. Unless the caption says otherwise, a cell is the relative drop of Eq. (C.2), as mean± \pm ± most damaging and the least damaging selection of each column are highlighted.
What the conviction measures
§ 6.3 settles by intervention whether the conviction identifies the nodes a trained network relies on. Before intervening, we check what the conviction is by correlating it with node properties that are already interpretable: the degree and the betweenness centrality, both topological; the model’s softmax confidence; and the input-gradient saliency, the norm of the gradient of the loss with respect to the raw node features. We also measure the Cohen’s d d d
The results are collected in Table 3 . The conviction is moderately correlated with degree, 0.33 ± 0.07 0.33\pm0.07 0.33 ± 0.07 0.28 ± 0.06 0.28\pm0.06 0.28 ± 0.06 0.66 ± 0.05 0.66\pm0.05 0.66 ± 0.05 − 0.18 ± 0.09 -0.18\pm0.09 − 0.18 ± 0.09 d d d 0.54 ± 0.09 0.54 \pm0.09 0.54 ± 0.09 0.37 ± 0.08 0.37 \pm0.08 0.37 ± 0.08
Table 3.
The conviction is therefore not reducible to the topology or to the confidence: the topological correlations are moderate and appear only with training, and the agreement with the model’s confidence is partial.
Table 3 : Spearman correlation between the conviction and four node properties, and absolute Cohen’s d d d Untrained is the epoch-0 checkpoint, a control.
Robustness of the intervention
The other perturbation modes. Tables 4, 5 and 6 give the budget sweep for the three modes not shown in the body; zero masking appears as Table 1, and in all four the colored entries mark the most and the least damaging selection at each budget. High conviction is the most damaging selection in all four tables and at all five budgets, and low conviction the least; the only exception is the 1% gating budget, where low degree comes out marginally below it.
The decile experiment. Table 7 gives the deciles under zero masking. Of the three criteria, the conviction has the largest drop at bin 10 and usually the smallest at bin 1; its lower bins are close to zero and most of its growth occurs in the last two. Confidence and degree also increase along the bins, but more flatly and more irregularly. The experiment was run in all four modes; here we show one of them specifically.
Table 7 : Decile experiment under zero masking. The training pool is split into ten equal bins by each ranking criterion (columns), from the lowest-scoring bin 1 to the highest-scoring bin 10 (rows), and one bin is perturbed at a time. The conviction has the largest drop at bin 10, and most of its growth occurs in the last two bins.
Table 7.
A different conviction score. The body ranks nodes by last, the conviction at the final diffusion layer, since that is the representation the classifier reads, but this rests on a single layer whose scale is arbitrary. We therefore repeat the analysis with avg_z, in which the conviction of each post-diffusion layer is z-scored separately and the results averaged, so no single layer dominates the ranking (Table 8 ).
Table 8: As Table 1, with nodes ranked by the layer-averaged score avg z \operatorname{avg} z avg z
Table 8.
Table 5. As Table 4 , under hard gating. At the 1% budget low degree is marginally the least damaging.
Table 4. Budget sweep under mean masking, laid out as Table 1. High conviction is the most damaging selection at every budget, low conviction the least.
Every conclusion is unchanged and the effect is slightly sharper: high conviction remains the most damaging selection and low conviction the least at every budget.
Soft gating. The soft variant attenuates the whole training pool at once: each node’s outgoing message is attenuated in proportion to its own score, so there is neither a budget nor a selection axis. Attenuating by conviction costs 3.09 ± 0.95 % 3.09 \pm0.95\% 3.09 ± 0.95% 4.19 ± 1.95 % 4.19 \pm1.95\% 4.19 ± 1.95% 0.67 ± 0.37 % 0.67 \pm0.37\% 0.67 ± 0.37% Table 9 ). Unlike in the budget sweeps, conviction is therefore not the most damaging score here. A plausible reading is that the soft variant suppresses the low-conviction nodes and softens the high-conviction ones at the same time, so the two effects the budget sweep isolates are superimposed and partly cancel.
Table 9: Relative drop under soft gating, which attenuates the outgoing message of every training node in proportion to its score (gate floor g min = 0.1 g_{\min} = 0.1 g m i n = 0.1
Table 9.
Per-dataset results
Where the aggregate comes from. Table 10 and Table 11 give the sweep dataset by dataset for the high and the low selections, under zero masking and conviction score last. Here a cell is the mean over the ten folds of that dataset, and the quoted spread is the standard error across folds, which shows how stable the effect is within a dataset; the aggregated tables instead show how it varies across the datasets. The high-conviction effect is large on Minesweeper and Roman Empire, which at the 10% budget lose 5.40 ± 0.61 % 5.40 \pm0.61\% 5.40 ± 0.61% 4.02 ± 0.17 % 4.02 \pm0.17\% 4.02 ± 0.17% 0.00 ± 0.02 % 0.00 \pm0.02\% 0.00 ± 0.02% 0.33 ± 0.05 % 0.33 \pm0.05\% 0.33 ± 0.05% 5.40 % 5.40\% 5.40% 4.02 % 4.02\% 4.02%
Table 10. Budget sweep under zero masking, dataset by dataset, for the high-degree and high-conviction selections. Unlike the other tables, the spread is the standard error across the ten folds of each dataset.
Table 11: As Table 10 , for the low-degree and low-conviction selections.
Table 11.
The cost of pruning
Pruning is the only intervention that changes the graph, so for every (strategy, budget) pair we record the fraction of nodes and edges remaining, the number of connected components and the size of the giant component. These diagnostics show that under pruning degree and conviction are not on the same footing. Removing the top k % k\% k % 51.6 ± 4.3 % 51.6 \pm4.3\% 51.6 ± 4.3% 39.4 ± 2.8 % 39.4 \pm2.8\% 39.4 ± 2.8% k % k\% k % Table 12 ). Even so, its average cost at that budget, 5.77 ± 1.57 % 5.77 \pm1.57\% 5.77 ± 1.57% 7.08 ± 2.04 % 7.08 \pm2.04\% 7.08 ± 2.04% Table 6 ).
Table 6. As Table 4 , under pruning.
Table 12: Percentage of the graph’s edges deleted under pruning, by selection strategy and budget; the performance cost of the same selections is in Table 6 . Selecting by degree deletes the most edges.
Table 12.
The same diagnostics qualify the degree-matched control. At the 1% budget it removes 5.0 ± 1.3 % 5.0 \pm1.3\% 5.0 ± 1.3% 7.7 ± 3.1 % 7.7 \pm3.1\% 7.7 ± 3.1% 0.20 ± 0.05 % 0.20 \pm0.05\% 0.20 ± 0.05% 1.65 ± 0.96 % 1.65 \pm0.96\% 1.65 ± 0.96% 28.3 ± 1.7 % 28.3 \pm1.7\% 28.3 ± 1.7%
The Forman Profile: Protocol and Additional Material
Protocol
Models and training. Every configuration follows the same loop: the network is trained on the node classification task, and at selected epochs the Forman profile of the sheaf Laplacian currently produced by the restriction maps is extracted, layer by layer, and compared to the reference profiles. To extract it, we take the sheaf Laplacian produced at layer ℓ \ell ℓ n n n
Two model families are studied. In GeneralSheaf , the learner reported in the body, a neural map sends each edge to an unconstrained d × d d \times d d × d F ν ≤ ( ℓ ) ⊆ ( Θ [ X ν ( ℓ ) ∥ X u ( ℓ ) ] ) \mathcal{F}^{(\ell)}_{\nu\leq} \subseteq\left(\Theta[X^{(\ell)}_{\nu} \Vert X^{(\ell)}_{u}]\right) F ν ≤ ( ℓ ) ⊆ ( Θ [ X ν ( ℓ ) ∥ X u ( ℓ ) ] ) JointSheafParams [29 ] the node signals and the restriction maps are diffused jointly at each layer ℓ \ell ℓ
X ( ℓ + 1 ) = X ( ℓ ) − S ( ( I n d − α Δ F ( ℓ ) ) ( I n ⊗ Ω 1 ( ℓ ) ) X ( ℓ ) Ω 2 ( ℓ ) ) , F ⋆ ( ℓ + 1 ) = F ⋆ ( ℓ ) − S ( ( I 2 m d − β Δ X ( ℓ ) ) ( I 2 m ⊗ Ω 1 ⋆ ( ℓ ) ) F ⋆ ( ℓ ) Ω 2 ⋆ ( ℓ ) ) . (92) \begin{aligned}
X^{(\ell+1)} &= X^{(\ell)} - \mathcal{S}\left((I_{nd} - \alpha\Delta_{\mathcal{F}^{(\ell)}})(I_n \otimes\Omega_1^{(\ell)})X^{(\ell)}\Omega_2^{(\ell)}\right), \\
\mathcal{F}^{\star(\ell+1)} &= \mathcal{F}^{\star(\ell)} - \mathcal{S}\left((I_{2md} - \beta\Delta_{X^{(\ell)}})(I_{2m} \otimes\Omega_1^{\star(\ell)})\mathcal{F}^{\star(\ell)}\Omega_2^{\star(\ell)}\right). \tag*{(92)}
\end{aligned} X ( ℓ + 1 ) F ⋆ ( ℓ + 1 ) = X ( ℓ ) − S ( ( I n d − α Δ F ( ℓ ) ) ( I n ⊗ Ω 1 ( ℓ ) ) X ( ℓ ) Ω 2 ( ℓ ) ) , = F ⋆ ( ℓ ) − S ( ( I 2 m d − β Δ X ( ℓ ) ) ( I 2 m ⊗ Ω 1 ⋆ ( ℓ ) ) F ⋆ ( ℓ ) Ω 2 ⋆ ( ℓ ) ) . (92) where F ⋆ ∈ R 2 m d × d \mathcal{F}^{\star} \in\mathbb{R}^{2md \times d} F ⋆ ∈ R 2 m d × d 2 m 2m 2 m m m m Δ X ( ℓ ) \Delta_{X^{(\ell)}} Δ X ( ℓ ) Ω 1 , Ω 2 \Omega_1,\Omega_2 Ω 1 , Ω 2 α , β \alpha,\beta α , β F ( 0 ) = I d \mathcal{F}^{(0)} = I_d F ( 0 ) = I d
Each model is trained independently under both normalization regimes, with Δ F = D F − 1 / 2 L F D F − 1 / 2 \Delta_F = D_F^{-1/2}L_FD_F^{-1/2} Δ F = D F − 1/2 L F D F − 1/2 L F L_F L F d ∈ { 2 , 3 , 5 } d \in\{2, 3, 5\} d ∈ { 2 , 3 , 5 } L ∈ { 2 , … , 6 } L \in\{2, \ldots, 6\} L ∈ { 2 , … , 6 } d = 2 d = 2 d = 2 L = 2 L = 2 L = 2 d = 5 d = 5 d = 5 L = 6 L = 6 L = 6 { 0 , 1 , 5 , 15 , 50 , 200 } \{0, 1, 5, 15, 50, 200\} { 0 , 1 , 5 , 15 , 50 , 200 }
Alignment metrics. All metrics are computed per eigenvalue of the Forman term, per layer, per checkpoint and per fold, then averaged over eigenvalues and folds, so a configuration yields one scalar per (checkpoint, layer) cell, with checkpoints on the rows and layers on the columns.
For normalized runs each eigenvalue channel f k f_k f k f t o p f^{\mathrm{top}} f top ρ \rho ρ r r r W 1 W_1 W 1 ℓ 2 \ell_2 ℓ 2 § 6.4 is agreement in shape up to an offset, and why W 1 W_1 W 1
For unnormalized runs the baseline is ambiguous, since the unnormalized graph Laplacian has an identically zero profile. We therefore use both references: W 1 ( f k , f t o p ) W_1(f_k, f^{\mathrm{top}}) W 1 ( f k , f top ) W 1 ( f k , 0 ) W_1(f_k, 0) W 1 ( f k , 0 ) r r r f k t o p f_k^{\mathrm{top}} f k top
Aggregation. The global tables report W 1 W_1 W 1 L L L § 14 .§ 3 report W 1 W_1 W 1 § 14 .§ 4 report all the metrics above.
Separating normalization from training
To separate the effect of the learning from that of the normalization we recompute, for GeneralSheaf and at every checkpoint, a second Laplacian built from the same learnt restriction maps under the opposite normalization, the other Laplacian . This gives four profiles per dataset.
Table 1 (PDF p. 46).
Each column fixes the normalization used at evaluation and varies only the regime the maps were trained under, so comparing the two entries of one column isolates the role of the training regime. The ablation compares each other Laplacian against the reference profiles, with the metrics above. The cross-comparison instead compares the two Laplacians of one column with each other: the Forman profile of the Laplacian built from the maps trained with norm=True against that of the one built from the maps trained with norm=False, both evaluated with the same normalization, so that no reference profile is involved. It is done for GeneralSheaf, dataset by dataset, at every checkpoint and layer, and aggregated as in Appendix § 14 .§ 1 ; it measures how far apart the profiles produced by the two training regimes are.
§ 6.4 reports the normalized GeneralSheaf runs, which converge to local alignment with the normalized graph Laplacian. The remaining mechanisms each leave a different signature: we read the difference in Forman-profile behaviour between these sheaf learning mechanisms as a fingerprint of the learning process.
All tables of this section share the layout of Table 2 . Each cell is the 1-Wasserstein distance between two Forman profiles, with training epochs on the rows, epoch 0 being the initial sheaf, and the relative depth of the layer on the columns. Values are mean± \pm ±
Unnormalized general sheaf learning aligns with neither reference. The metrics against the topological reference stay almost constant in layer and epoch, while the distance from the zero reference is large and generally grows: on the large heterophilic datasets it peaks at intermediate depth and epoch, then recedes slightly but stays substantial (Table 13 ). We have no explanation for the non-monotonicity and read no mechanism into it.
Table 13. W1 distance of the unnormalized GeneralSheaf from the topological reference (top) and the zero reference (bottom). The profile aligns with neither.
The alignment comes from normalization, and the maps stay away from the identity. Maps trained normalized but evaluated unnormalized lose their alignment to both references. Were they identity-like, evaluating them unnormalized would reproduce the unnormalized graph Laplacian, whose profile vanishes identically, and the profile would sit at the zero reference. In the other direction, maps trained unnormalized but evaluated normalized do align with the topological reference, in W 1 W_1 W 1 Table 14 and Table 15 ).
Cross-comparison: the two normalization regimes. For GeneralSheaf, dataset by dataset, we compare the Forman profile of the maps trained normalized with that of the maps trained unnormalized, both evaluated normalized (Table 16 ) or both evaluated unnormalized (Table 17 ); no reference profile is involved (Appendix § 14 .§ 2 ). In both columns W 1 W_1 W 1
Table 16: W 1 W_1 W 1 § 14 .§ 2 ). They stay apart and neither converge nor diverge.
Table 16. W 1 W_1 W 1 § 14 .§ 2 ). They stay apart and neither converge nor diverge.
Table 17: As Table 16 , with both Laplacians evaluated unnormalized. The distances are of the same size.
Table 17. As Table 16 , with both Laplacians evaluated unnormalized. The distances are of the same size.
Joint diffusion reverses the role of normalization. Both joint regimes start at the identity sheaf, so their distances measure deviation from the identity. Unnormalized, the standard regime for this architecture, the small datasets stay very close to the identity sheaf while on the larger ones the maps deviate through the layers and are drawn back as training proceeds (Table 18 ). Normalized, the regime is less stable and needs a lower stalk dimension and fewer layers; there the maps deviate largely from the identity as training proceeds, which is the reverse of the unnormalized pattern (Table 19 ).
Table 18 : W 1 W_1 W 1
Table 18.
Table 19 : W 1 W_1 W 1
Table 19.
Per-dataset tables
The tables above average across datasets and report W 1 W_1 W 1 § 14 .§ 1 . Each table has one block per metric, with training epochs on the rows and layers on the columns; each cell is averaged over the eigenvalues of the Forman term and given as mean±s.e. across the ten folds of that dataset. Correlations are on a blue–red scale centred at zero, distances on a yellow–red scale, and a blank cell marks a correlation that is undefined because the profile is constant. The remaining datasets show similar patterns, with the exceptions discussed in § 6.4 .
Table 20 is the per-dataset counterpart of Table 2 : on Roman Empire, alignment with the topological reference strengthens with epochs and, at fixed epoch, with depth. Table 21 is the counterpart of Table 13 : on Citeseer, the unnormalized profile matches neither reference. Table 22 is the counterpart of Table 18 : on Questions, the maps deviate from the identity through the layers, and the deviation is attenuated as training proceeds.
Table 21. Unnormalized GeneralSheaf on Citeseer, d = 5 d = 5 d = 5
