# Principal-module graph compression

- ID: 1242
- Canonical URL: https://synthcore.org/idea/1242/principal-module-graph-compression
- API JSON: https://synthcore.org/api/idea/1242.json
- API Markdown: https://synthcore.org/api/idea/1242.md
- Verification status: unverified
- Source: [arXiv:2607.21494](https://arxiv.org/abs/2607.21494)
- Category: memory
- Solves: memory, speedup, accuracy
- ML areas: graph-nn, memory, inference-speedup
- Math tags: graph-theory, linear-algebra, algebra, representation-theory
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Build a low-dimensional basis for the principal module generated by the all-ones vector, then perform adjacency and degree propagation in compressed coordinates. On forests, the paper states that this module equals the automorphism-orbit module, so the reduced representation can preserve principal adjacency-degree information while using far fewer coordinates than the number of vertices.

## Mathematical statement

Let K in R^{n x r} contain linearly independent principal-module vectors of the form w(A_G,D_G)1, where r=rank(K) estimates the dimension of M_G. If the columns span an invariant module, adjacency and degree have reduced coordinate matrices C_A,C_D in R^{r x r} satisfying AK=KC_A and DK=KC_D. With K^dagger the Moore-Penrose pseudoinverse, compute C_A=K^dagger AK and C_D=K^dagger DK, and verify closure using residuals ||AK-KC_A|| and ||DK-KC_D||. The paper gives an explicit example in which five columns span the principal module of a ten-vertex graph and satisfy these intertwining identities. For forests, M_G=U_G, where U_G is the space of vectors constant on automorphism orbits, giving the structural reason this compression can retain orbit-level information.

## Key formulas

- $$K=\bigl[\mathbf{1},\;A\mathbf{1},\;D\mathbf{1},\;A^2\mathbf{1},\;AD\mathbf{1},\;DA\mathbf{1},\ldots\bigr]\in\mathbb{R}^{n\times r}$$
- $$AK=KC_A,\qquad DK=KC_D$$
- $$C_A=K^{\dagger}AK,\qquad C_D=K^{\dagger}DK$$
- $$\rho_A=\frac{\|AK-KC_A\|_F}{\|AK\|_F},\qquad \rho_D=\frac{\|DK-KC_D\|_F}{\|DK\|_F}$$

## Implementation notes

Use this as an optional compressed branch for graph message passing, especially for graph-level tasks or graphs with repeated structural patterns. Construct candidate columns K incrementally: start with ones(n), repeatedly apply A and D to every retained column, and append a candidate only when its residual after projection onto the current orthonormal basis exceeds epsilon. Use QR orthogonalization rather than explicit matrix inversion. After obtaining K, form C_A=K^dagger A K and C_D=K^dagger D K. A reduced state z is propagated by z_new=C_A z or z_new=C_D z, while a node-space state can be reconstructed as h=Kz. The paper supplies the exact algebraic closure criterion; rank truncation, epsilon, and regularization are empirical. For non-exact modules, retain a residual correction or reject compression when rho_A or rho_D is too large. First benchmark on synthetic trees and molecular graphs against a GIN with equal message-passing depth and hidden channels. Measure rank r/n, peak memory, wall-clock propagation time, closure residuals, and task accuracy. The desired result is lower node-state memory and faster propagation when r is much smaller than n, with no accuracy loss on orbit-sensitive tree classification. The method should be rejected for graph families where r approaches n or closure residuals remain high.

## Disclaimer

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