Combining graphlets and random walks for capturing complex network topology.

Area of Science:

• Network Science
• Graph Theory
• Machine Learning

Background:

• Random-walk-based methods are prevalent for network embedding and learning tasks.
• Understanding the topological features captured or ignored by these methods is crucial for network analysis.
• Node function often depends on higher-order structural patterns beyond direct connectivity.

Purpose of the Study:

• To investigate the limitations of random-walk-based methods in capturing network topology.
• To introduce orbit adjacency as a novel graphlet-based descriptor for network analysis.
• To compare the performance of orbit adjacency with random-walk methods in capturing topology-function relationships.

Main Methods:

• Theoretical analysis of random walks to understand captured topological signals.
• Introduction and application of orbit adjacency, a descriptor measuring co-occurrence in symmetric subgraph positions.
• Empirical evaluation on 40 real-world networks using a node-label prediction task.

Main Results:

• Random walks capture only a subset of local wiring patterns and obscure informative signals.
• Orbit adjacency-based representations significantly outperform random-walk-based embeddings.
• Explicit modeling of higher-order structural patterns is vital for topology-aware network analysis.

Conclusions:

• Random-walk methods have inherent limitations in capturing complex network topology.
• Orbit adjacency provides a unified framework for understanding random walk topology capture.
• Orbit adjacency is an effective alternative for topology-aware network analysis and function prediction.