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

Graphon estimation requires structural assumptions to address its intrinsic non-identifiability.

A standard approach is degree-based identifiability, where the degree function is assumed to be strictly monotonic.

This assumption is rather restrictive and fails for graphons with constant or non-injective degree function, even when distinct latent positions have different connectivity profiles.

In this paper, we introduce \emph{rooted motif signatures} as higher-order node-level representations for graphons.

They extend the degree function by recording, at each latent position, the densities of rooted motifs such as triangles, cycles, paths, and other local subgraph patterns.

We study the extent to which these signatures can distinguish latent positions beyond degree information.

For generic finite-rank graphons, we prove that suitable rooted motif signatures determine the connectivity profiles of latent positions.

We also explain why such a property cannot hold for arbitrary graphons without additional assumptions, since different latent positions may have identical rooted motif signatures.

On the statistical side, we define empirical rooted motif signatures from a single observed graph and prove uniform concentration bounds for these estimators.

Simulation experiments illustrate that rooted motif signatures can reveal latent structure in settings where degree-based representations are uninformative, including graphons with constant or non-injective degree functions and stochastic block models with equal block degrees.