# Jacobian-Coherence Graph Filtration

- ID: 1529
- Canonical URL: https://synthcore.org/idea/1529/jacobian-coherence-graph-filtration
- API JSON: https://synthcore.org/api/idea/1529.json
- API Markdown: https://synthcore.org/api/idea/1529.md
- Verification status: unverified
- Source: [arXiv:2607.28284](https://arxiv.org/abs/2607.28284)
- Category: regularization
- Solves: accuracy, generalization, sample-efficiency
- ML areas: graph-nn, data-augmentation, regularization
- Math tags: spectral-theory, linear-algebra, graph-theory
- Ratings: usefulness 6/10; difficulty 4/10; novelty 7/10

## Idea description

Replace random edge dropout in a GNN with an order-aware filtration that removes edges in decreasing local spectral coherence. High-coherence edges are those whose rank-one Laplacian perturbations align strongly with the current local Laplacian, so their removal creates structured, spectrally meaningful augmentations rather than arbitrary damage. Train the GNN jointly on the original graph and several filtration states using supervised loss plus prediction or embedding consistency.

## Mathematical statement

For a weighted undirected graph with Laplacian L, an edge e=(i,j) has incidence vector b_{ij}=e_i-e_j, where e_i is the i-th standard basis vector, and its unit-weight Laplacian update is B_{ij}=b_{ij}b_{ij}^{    op}. For hop radius k, U_e^{(k)}=N_k(i)\cup N_k(j), where N_k(v) is the set of vertices within at most k graph hops of v. The paper defines the local Jacobian-coherence score \rho_e^{(k)}=\langle B_{ij}[U_e^{(k)}],L[U_e^{(k)}]\rangle_F/(\|B_{ij}[U_e^{(k)}]\|_F\|L[U_e^{(k)}]\|_F)\in[-1,1]. Here \langle A,C\rangle_F=\operatorname{tr}(A^{    op}C) is the Frobenius inner product, \|A\|_F=(\sum_{p,q}A_{pq}^2)^{1/2} is the Frobenius norm, and brackets denote principal submatrices. Sort edges e_1,\ldots,e_m by decreasing \rho_e^{(k)}. The filtration graph after t removals has Laplacian L_t=L_0-\sum_{r=1}^{t}w_{e_r}B_{e_r}, where w_{e_r} is the original edge weight. Use graph embeddings z_t=z_    heta(G_t) and optimize \mathcal{L}=\mathcal{L}_{\mathrm{sup}}(f_    heta(G_0),y)+\lambda T^{-1}\sum_{t=1}^{T}\|z_t-z_0\|_2^2, with \lambda\geq0.

## Key formulas

- $$\rho_{e}^{(k)}=\frac{\langle B_{ij}[U_{e}^{(k)}],\,L[U_{e}^{(k)}]\rangle_{F}}{\|B_{ij}[U_{e}^{(k)}]\|_{F}\,\|L[U_{e}^{(k)}]\|_{F}}\in[-1,1}$$
- $$B_{ij}=(e_i-e_j)(e_i-e_j)^{\top},\qquad L_t=L_0-\sum_{r=1}^{t}w_{e_r}B_{e_r}$$
- $$\mathcal{L}=\mathcal{L}_{\mathrm{sup}}(f_\theta(G_0),y)+\lambda\frac{1}{T}\sum_{t=1}^{T}\left\|z_\theta(G_t)-z_\theta(G_0)\right\|_2^2$$

## Implementation notes

Integrate this at the graph-data augmentation layer immediately before message passing, rather than modifying the GNN weights. For each training graph, compute its weighted Laplacian L and choose k=1 initially. For every edge e=(i,j), obtain U_e^{(k)} using k-hop BFS from i and j, form B_e=(e_i-e_j)(e_i-e_j)^T restricted to U_e^{(k)}, and calculate rho_e with an epsilon in the denominator for numerical safety. Sort edges by decreasing rho_e. Select a few removal levels, such as t in {0, ceil(0.1m), ceil(0.2m)}, where m is the edge count, and construct G_t by deleting the first t ordered edges. Run the same GNN on every G_t, producing embeddings z_t and logits q_t. Optimize cross-entropy on q_0 plus lambda times the average squared embedding distance from z_0. Pseudocode is: `L=laplacian(G); scores=[]; for (i,j,w) in edges: U=khop_union(i,j,k); B=outer(e_i-e_j,e_i-e_j); rho=frob_inner(B[U,U],L[U,U])/(frob_norm(B[U,U])*frob_norm(L[U,U])+eps); scores.append(rho); order=argsort(scores,descending=True); for t in levels: G_t=remove_edges(G,order[:t]); z_t,q_t=GNN(G_t); loss=CE(q_0,y)+lambda*mean(||z_t-z_0||^2)`. The ordering, local restriction, and Laplacian update come from the paper; lambda, k, removal fractions, and consistency target are empirical. First test on MUTAG or a synthetic graph-classification dataset with localized edge edits, comparing no augmentation, uniform random edge dropout, and this filtration. Measure clean accuracy, accuracy under localized test-time edge noise, and training loss at equal FLOPs. Success means improved robustness or sample efficiency without a substantial clean-accuracy decrease.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.