Comparing random walks in graph embedding and link prediction.

Area of Science:

• Network Science
• Data Mining
• Machine Learning

Background:

• Random walks are crucial for complex network analysis, particularly in embedding generation and link prediction.
• The specific influence of various random walk biases on embedding quality and downstream link prediction performance is not well understood.

Purpose of the Study:

• To comparatively analyze the impact of different random walk strategies on embedding generation and link prediction.
• To investigate how biases like node degree and self-avoidance affect network representation.

Main Methods:

• Evaluated traditional random walks, self-avoiding random walks, and degree-biased random walks.
• Adapted the node2vec algorithm to explore diverse random walk behaviors.
• Assessed the performance of generated embeddings in link prediction tasks.

Main Results:

• Despite significant variations in random walk behaviors and embedding characteristics, link prediction performance showed only minor differences across strategies.
• The network structure appears robustly recoverable irrespective of the specific random walk heuristic used.

Conclusions:

• The choice of random walk strategy has a limited impact on the effectiveness of link prediction in complex networks.
• Network data generated from sequences with unknown underlying mechanisms can be reliably reconstructed using these methods.