FRTD embedding: Random walks improve network alignment beyond graph metrics

The first return time distribution (FRTD) of a random walk is emerging as a powerful and interpretable network embedding. In a new paper, Vedanta Thapar, Renaud Lambiotte, and George T. Cantwell show that by recording the probability of a random walker returning to a node at each time step, each node can be represented as a probability mass function. This allows network distances to be computed using standard metrics for discrete distributions, such as total variation or Jensen-Shannon divergence, making the embedding both mathematically grounded and easy to use.

The team rigorously demonstrates that FRTDs are strictly more informative than eigenvalue spectra, a classic structural descriptor. However, they are not sufficient to uniquely identify every graph, placing FRTD equivalence between cospectrality (same eigenvalues) and full isomorphism (identical structure). This subtle positioning means FRTD captures meaningful structural similarity without being overly discriminative. The authors also show that nodes with similar FRTDs tend to play analogous roles in a network, supporting its use as a structural node feature.

Empirically, the FRTD embedding outperforms purpose-built graph metrics in network alignment tasks, which aim to match corresponding nodes across different networks. Furthermore, random graphs generated to approximately match a target network's FRTD also preserve other salient topological properties. This suggests FRTD is not just a descriptive feature but a generative constraint. The work offers a simple, no-training-needed alternative to deep-learned embeddings for complex network analysis, particularly valuable when interpretability and mathematical guarantees are priorities.