# Rooted Motif Positional Encoding

- ID: 328
- Canonical URL: https://synthcore.org/idea/328/rooted-motif-positional-encoding
- API JSON: https://synthcore.org/api/idea/328.json
- API Markdown: https://synthcore.org/api/idea/328.md
- Verification status: mechanism_works
- Source: [arXiv:2607.01358](https://arxiv.org/abs/2607.01358)
- Category: architecture
- Solves: accuracy, sample-efficiency
- ML areas: graph-nn, embedding, attention
- Math tags: graph-theory, spectral-theory, linear-algebra
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Augment every graph node with a vector of rooted walk and motif densities rather than relying only on degree or Laplacian positional encodings. This should distinguish nodes or communities with identical expected degree but different connectivity profiles, especially in equal-degree stochastic block models and graphs with locally heterogeneous structure.

## Mathematical statement

Let W be a graphon and let T_W f(u) = integral from 0 to 1 of W(u,v) f(v) dv be its integral operator. The degree function is g(u) = T_W 1(u). For a finite-rank graphon with W(u,v) = sum from j=1 to m of lambda_j phi_j(u) phi_j(v), where the eigenvalues lambda_1 through lambda_m are pairwise distinct, define c_j = inner product of 1 and phi_j. The rooted walk moments satisfy h_k(u) = T_W^k 1(u) = sum from j=1 to m of lambda_j^k c_j phi_j(u). For k = 1 through m, the moment vector equals V diag(c_1,...,c_m) times the eigenfunction-coordinate vector, where V_{kj} = lambda_j^k. The paper gives det(V) = (product over j of lambda_j) times (product over i less than j of (lambda_j - lambda_i)), which is nonzero under distinct nonzero eigenvalues. If every c_j is nonzero, the moments determine the eigenfunction coordinates. For a finite graph with adjacency matrix A and n nodes, use empirical features h_hat_k(i) = ((A/n)^k 1)_i. A rooted triangle feature is t_hat_triangle(i) = [(A/n)^3]_{ii}. Small eigenvalue gaps or small overlaps c_j predict unstable or non-discriminative encodings.

## Key formulas

- $$g(u)=\int_0^1 W(u,v)\,dv=T_W\mathbf{1}(u)$$
- $$h_k(u)=T_W^k\mathbf{1}(u)=\sum_{j=1}^{m}\lambda_j^k c_j\phi_j(u),\qquad c_j=\langle\mathbf{1},\phi_j\rangle$$
- $$\begin{pmatrix}h_1(u)\\h_2(u)\\\vdots\\h_m(u)\end{pmatrix}=V\,\operatorname{diag}(c_1,\ldots,c_m)\begin{pmatrix}\phi_1(u)\\\phi_2(u)\\\vdots\\\phi_m(u)\end{pmatrix},\quad V_{kj}=\lambda_j^k$$
- $$\det(V)=\left(\prod_{j=1}^{m}\lambda_j\right)\prod_{1\leq i<j\leq m}(\lambda_j-\lambda_i)\neq0,\qquad \widehat h_k=\left(\frac{A}{n}\right)^k\mathbf{1},\quad \widehat t_{\triangle}(i)=\left[\left(\frac{A}{n}\right)^3\right]_{ii}$$

## Implementation notes

Integrate this at the input positional-encoding stage of a message-passing GNN or graph transformer. For a graph with adjacency matrix A and n nodes, compute K short rooted-walk channels without constructing dense matrix powers. Initialize q to an all-ones vector. For k from 1 through K, replace q by (A multiplied by q) divided by n, and append q as the k-th node feature channel. Compute a rooted triangle channel as the diagonal of A multiplied by A multiplied by A, divided by n cubed. With sparse graphs, use sparse matrix-vector products for walks and sparse matrix-matrix products or a triangle-counting kernel for triangles. Concatenate the original node features with all motif channels, standardize each channel across nodes, then apply LayerNorm and a learned linear projection before the first GNN or attention layer. Pseudocode is: q = ones(n); channels = []; for k in 1,...,K: q = sparse_matvec(A,q)/n; channels.append(q); triangle = diag(A @ A @ A)/n^3; z = Linear(LayerNorm(concat(x, channels, triangle))); output = GNN(z,A). Use K equal to 3 or 4 initially. The exact mathematical computation is the rooted-walk recursion and the finite-rank Vandermonde identifiability argument; eigenvalues do not need to be estimated in the first implementation. For a conditioning-aware variant, estimate the leading eigenvalues of A/n with Lanczos and reduce the weight of channels when eigenvalue gaps are small or when the empirical feature variance is near zero. First experiment: use a two-layer GCN and a graph transformer for node classification on four-block stochastic block model graphs whose blocks have equal expected degrees but different within-block connectivity patterns. Compare raw features, degree features, Laplacian positional encodings, and the proposed features at similar parameter counts. Use graphs with 500 to 2000 nodes and sparse matrix operations. The main success signal is higher test accuracy and better accuracy with fewer labeled nodes, while also reporting feature-computation time and robustness under edge noise.

## Verification

- Status: mechanism_works
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a sparse rooted-walk and rooted-triangle feature extractor plus a finite-rank Vandermonde numerical verification. The mathematical identities passed at approximately 1e-17 numerical error. On the equal-row-sum four-block SBM, degree-only accuracy was 25.08%, walks-only 24.94%, triangles-only 25.12%, while walks plus triangles reached 27.30%, a modest but consistent improvement over chance and the baseline; the idea shows a promising signal, though not every channel helped alone.

### Mechanism check

- Verdict: Built a sparse rooted-walk and rooted-triangle feature extractor plus a finite-rank Vandermonde numerical verification. The mathematical identities passed at approximately 1e-17 numerical error. On the equal-row-sum four-block SBM, degree-only accuracy was 25.08%, walks-only 24.94%, triangles-only 25.12%, while walks plus triangles reached 27.30%, a modest but consistent improvement over chance and the baseline; the idea shows a promising signal, though not every channel helped alone.
- Confidence: 7/10
- Limitations: This MVP used a logistic classifier rather than a GNN or graph transformer, tested one 800-node SBM family and one 20% labeled split, and did not test Laplacian encodings, edge-noise robustness, larger graphs, GPU execution, or multiple graph families. The improvement is modest and rooted walks alone did not outperform degree.

## Artifacts

- [experiment.py](https://synthcore.org/code/78/experiment.py)
- [report.md](https://synthcore.org/code/78/report.md)
- [results.json](https://synthcore.org/code/78/results.json)
- [Download all files as ZIP](https://synthcore.org/download/78)

## Disclaimer

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