Combining graphlets and random walks for capturing complex network topology

Random-walk–based methods are widely used for network embedding and downstream learning tasks, yet it remains unclear which aspects of network topology they capture and which they ignore. This is a critical limitation in networks where node function depends not only on direct connectivity, but also on higher-order structural patterns. To address this gap, we introduce orbit adjacency, a graphlet-based descriptor that measures how often pairs of nodes co-occur in specific symmetric positions within small induced subgraphs. Using orbit adjacency, we provide a theoretical analysis showing that random walks capture only a subset of local wiring patterns and inherently combine those they do capture, thereby obscuring structurally informative signals. We empirically demonstrate that these limitations hinder the ability of random-walk–based embeddings to capture topology–function relationships across 40 real-world networks from social, technological, and biological domains using a node-label prediction task. Our results show that orbit adjacency–based representations consistently outperform random-walk–based methods, highlighting the importance of explicitly modelling higher-order structural patterns. Overall, this work provides a unified framework for understanding the topology captured by random walks and establishes orbit adjacency as an effective alternative for topology-aware network analysis.

Citation

S.F.L. Windels, N. Malod-Dognin, N. Przulj, "Combining graphlets and random walks for capturing complex network topology," Scientific Reports, 2026, https://doi.org/10.1038/s41598-026-44410-x.

Source

Scientific Reports

Keywords

46 Information and Computing Sciences, 4605 Data Management and Data Science, 51 Physical Sciences

Publisher

Springer Nature

DOI

10.1038/s41598-026-44410-x

Additional links

https://www.nature.com/articles/s41598-026-44410-x