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.