# Concatenated-Neighbor Low-Rank Message Passing

- ID: 2782
- Canonical URL: https://synthcore.org/idea/2782/concatenated-neighbor-low-rank-message-passing
- API JSON: https://synthcore.org/api/idea/2782.json
- API Markdown: https://synthcore.org/api/idea/2782.md
- Verification status: unverified
- Source: [arXiv:2608.27936](https://arxiv.org/abs/2608.27936)
- Category: architecture
- Solves: speedup, memory, scalability
- ML areas: graph-nn, attention, memory, inference-speedup
- Math tags: linear-algebra, graph-theory, numerical-analysis, tensor-decomposition
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Replace a sparse graph layer's separate edge transformations with one joint low-rank factorization of all transformations entering each target node. For target node i, concatenate the neighbor matrices horizontally, project all neighbor features into a shared low-dimensional receiving basis, and reconstruct one output; retain the self transformation exactly. This can reduce edge-parameter storage and message-passing FLOPs when the incoming block row has rapidly decaying singular values.

## Mathematical statement

The paper uses the block system (Dₛ + O)x = b, where x is the concatenated vector of node or element states, Dₛ is the block diagonal matrix of exact self-interaction blocks, and O contains only retained off-diagonal interactions. Retained neighbors are selected as Nᵢ = {j ≠ i : dᵢⱼ ≤ d꜀}, where dᵢⱼ is a pairwise distance and d꜀ is a cutoff. For a neural layer, let hⱼ ∈ Rᵈⁱⁿ be the feature of neighbor j and Wᵢⱼ ∈ Rᵈᵒᵘᵗˣᵈⁱⁿ its edge map. Define the incoming block row Aᵢ = [Wᵢⱼ₁ Wᵢⱼ₂ ... Wᵢⱼₘ] ∈ Rᵈᵒᵘᵗˣᵐᵈⁱⁿ, with Nᵢ = {j₁,...,jₘ}. Compute a rank-r truncated SVD Aᵢ ≈ UᵢΣᵢVᵢᵀ. Split Vᵢᵀ into blocks Vᵢⱼᵀ ∈ Rʳˣᵈⁱⁿ. The compressed message is yᵢ = Wᵢᵢhᵢ + UᵢΣᵢ Σⱼ∈Nᵢ Vᵢⱼᵀhⱼ. The optimal rank-r Frobenius error is ||Aᵢ − UᵢΣᵢVᵢᵀ||²_F = Σₖ₌ᵣ₊₁ σ²ᵢₖ, where σᵢₖ are the singular values. Thus the spectral tail directly determines a rank or error tolerance.

## Key formulas

- (Dₛ + O)x = b,    Dₛ = blockdiag(Z₁₁, ..., Zₙₙ)
- Nᵢ = {j ≠ i : dᵢⱼ ≤ d꜀}
- Aᵢ = [Wᵢⱼ₁ Wᵢⱼ₂ ... Wᵢⱼₘ] ≈ UᵢΣᵢVᵢᵀ,    ||Aᵢ − UᵢΣᵢVᵢᵀ||²_F = Σₖ>ᵣ σ²ᵢₖ
- yᵢ = Wᵢᵢhᵢ + UᵢΣᵢ Σⱼ∈Nᵢ Vᵢⱼᵀhⱼ

## Implementation notes

Integrate this into a sparse graph-convolution or point-cloud message-passing layer, replacing the operation that computes Σⱼ∈Nᵢ Wᵢⱼhⱼ. Build a fixed-radius or k-nearest-neighbor graph and keep the self map Wᵢᵢ exact. Let the existing edge network produce Wᵢⱼ from relative coordinates, edge features, or edge types. For each target i, construct the conceptual horizontal matrix Aᵢ by concatenating all incoming edge maps. Compute a truncated SVD Aᵢ = UᵢΣᵢVᵢᵀ offline after initialization or every K training steps. Choose the smallest rank r satisfying Σₖ>ᵣ σ²ᵢₖ ≤ ε²Σₖ σ²ᵢₖ. Split Vᵢᵀ into dⁱⁿ-column blocks. Forward pseudocode: `for each target i: Nᵢ = neighbors(i); Aᵢ = concat(Wᵢⱼ for j in Nᵢ); U, S, V = truncated_svd(Aᵢ); choose r from the spectral-tail test; qᵢ = 0; for j in Nᵢ: qᵢ += V_block(i,j).T @ hⱼ; yᵢ = Wᵢᵢ @ hᵢ + U[:,:r] @ S[:r] @ qᵢ`. The SVD and rank criterion are mathematical components; cutoff distance, tolerance ε, and refresh interval K are empirical choices. Initially freeze the factors and compare against the original layer; later test periodic refactorization or direct factor training. Use a 10-layer GraphSAGE or point-cloud model on Cora or ModelNet40, hidden width 128, and neighborhoods of 32 or 64 nodes. Compare ordinary sparse maps with the compressed layer at matched accuracy. Measure wall-clock time, FLOPs, parameter memory, activation memory, and relative output error ||Ycompressed − Yfull||F / ||Yfull||F. Success means at least 2× lower edge-message FLOPs or memory with less than 0.5 percentage-point accuracy loss and measurable inference acceleration.

## Disclaimer

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