Beyond Degree: Rooted Motif Signatures for Latent Position Identifiability in Graphon Models

What the math gives to ML

The paper provides a mathematically motivated replacement for degree-only node representations: vectors of rooted walk and motif densities. Its key transfer asset is the finite-rank spectral identity showing that successive rooted walk moments form a Vandermonde transform of latent eigenfunction coordinates; with distinct eigenvalues and nonzero constant-function overlaps, these moments can recover connectivity profiles even when degrees collide. In a graph neural network, this suggests deterministic motif positional encodings computed from sparse adjacency products and supplied to message passing or attention. The most direct test is equal-degree stochastic block models, where degree features are uninformative but short rooted motifs can separate blocks.