PaperlayerView exact revision on arXiv

Source-linked AI summary

Random Walks: A Review of Algorithms and Applications

Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan, Xiangjie Kong

arXiv:2008.03639v1cs.SIcs.LGphysics.data-an

TL;DR

The paper addresses the need for a unified understanding of classical and quantum random walks, including their algorithms, applications, and computational issues. It reviews foundational concepts and representative methods, compares algorithmic time complexity, and surveys computer-science applications. The review concludes that quantum computation can significantly accelerate random-walk computation, while large graphs create speed and storage challenges.

  • Problem

    Classical and quantum random walks had not been reviewed together across concepts, algorithms, applications, computational complexity, and open issues.

  • Method

    The paper reviews classical and quantum random-walk concepts and algorithms, compares them by time complexity, and surveys computer-science applications and open issues.

  • Results

    The review finds that quantum computation significantly accelerates random-walk algorithms, while classical methods such as RWR and LRW are time-consuming on large real-world graphs.

  • Takeaways & Limitations

    Random walks support node proximity and network-topology extraction across collaborative filtering, computer vision, network embedding, link prediction, and related tasks.

Abstract

from arXiv · show

A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this paper, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.

I. INTRODUCTION

Random walks model paths formed by successive random steps and support analysis of correlations, node proximity, and network structure. The review introduces classical and quantum walks, their algorithms, applications, and open issues.

  • Foundations: Random walks describe paths formed by successive random steps in mathematical space.They can analyze and simulate randomness and calculate correlations among objects.
  • Foundations: Network random walks assign transition probabilities according to edge association strength, producing paths that describe network structure.Stronger associations receive greater transition probabilities.
  • Algorithms: PageRank and variants including personalized PageRank, random walk with restart, and lazy random walk are representative computer-science algorithms.PageRank estimates web-page importance through random movement among pages.
  • Quantum walks: Quantum walks differ from classical walks through quantum interference and may spread faster or slower without converging to limiting distributions.The review compares quantum- and classical-walk algorithms by time complexity.
  • Applications: The paper reviews random-walk applications including collaborative filtering, link prediction, recommender systems, computer vision, semi-supervised learning, and network embedding.Random walks can incorporate contextual information when calculating nearby nodes.
  • Notation: The review organizes foundational notation around transition probabilities, hitting time, commute time, graph matrices, and random-walk evolution.It introduces graph G=(V,E), adjacency and transition matrices, and related quantities.

A Review of Random Walks

The review surveys classical random-walk concepts and algorithms, including transition behavior, hitting time, commute time, and representative applications. It also identifies computational concerns involving speed, memory, and hitting- or commute-time calculation.

  • Classical random walks: The review covers classical random-walk concepts including transition probability, hitting time, and commute time.Its listed classical algorithms include PageRank, personalized PageRank, RWR, B_LIN, K-dash, and LRW.
  • Applications: The framework includes applications in collaborative filtering, recommender systems, link prediction, computer vision, semi-supervised learning, and network embedding.It also lists element distinctness and quantum-walk algorithms such as quantum PageRank and Grover search.
  • Open issues: Existing random-walk analysis faces concerns about calculating speed, main-memory volume, and the computation of hitting and commute time.These concerns are presented as review dimensions rather than a single performance result.
  • Classical random walks: Hitting time is the expected number of steps before a walk starting at node i visits node j.The hitting-time matrix need not be symmetric, even on a regular graph.
  • Classical random walks: Commute time measures the expected steps from node i to node j and back to node i.For undirected graphs, it is compared with electrical-network resistance; shorter commute time corresponds to easier diffusion.

B. Quantum Views of Random Walks

Quantum walks are quantum-mechanical counterparts to classical random walks, with dynamics shaped by interference rather than convergence to a limiting distribution. The section introduces their physical representation and two principal forms.

  • Quantum-walk foundations: Quantum walks are the quantum-mechanical counterparts of classical random walks and do not converge to some limiting distributions.Quantum interference can make them spread significantly faster or slower than classical random walks.
  • Quantum-walk foundations: A one-dimensional quantum walk represents a localized wave-packet using position and momentum operators, with translation expressed as a unitary operator.The reduced Planck constant may be set to 1 to simplify notation.
  • Quantum-walk foundations: A spin-1/2 particle is represented using the eigenstates |↑⟩ and |↓⟩ of the z-component spin operator.The wave function has components in the spin-up and spin-down subspaces.
  • Quantum-walk forms: Quantum walks comprise discrete-time and continuous-time forms, illustrated through a one-dimensional example.The review presents both forms as basic concepts for understanding quantum walks.

1) Discrete Time Quantum Walks:

Discrete-time quantum walks combine position and coin degrees of freedom, while continuous-time walks evolve through a Hamiltonian-like generator. Their operators determine conditional movement and time evolution.

  • Discrete Time Quantum Walks: A one-dimensional discrete-time quantum walk uses a Hilbert space H=H_p⊗H_c spanning particle positions and coin states.The coin space is spanned by |↑⟩ and |↓⟩.
  • Discrete Time Quantum Walks: The conditional translation operator moves the particle right for spin up and left for spin down.The tensor product separates the particle’s spin and space degrees of freedom.
  • Discrete Time Quantum Walks: The coin operator is a unitary transformation that rotates spin in the coin space, with the Hadamard coin as a frequently used example.The Hadamard walk on Z is defined from this coin operation.
  • Discrete Time Quantum Walks: A single-step quantum-walk transformation is defined by the combined unitary operations, and a t-step walk is represented by U^t.The formulation captures repeated evolution of the walk.
  • Continuous Time Quantum Walks: Continuous-time quantum walks use a generator matrix analogous to the classical transition matrix, with the generator becoming the Hamiltonian that produces U(t).Discrete- and continuous-time walks can be connected through a precise limiting procedure.

2) Continuous Time Quantum Walks:

Classical random-walk algorithms estimate node importance or proximity through transition structures and iterative or matrix-based computations. The section highlights convergence acceleration, personalization, graph partitioning, low-rank approximation, and LU decomposition, while noting scalability constraints.

  • PageRank: PageRank ranks web pages by modeling pages as nodes and hyperlinks as directed edges.Its simple version corresponds to the stationary distribution of a random walk on the web graph.
  • Personalized PageRank: Personalized PageRank incorporates a user-specific vector to reflect node importance for that user.This addresses the keyword-independent nature of ordinary PageRank.
  • Random Walk with Restart: Random walk with restart computes affinity from a starting node by returning to that node with probability c.The steady-state probability of visiting node j forms the proximity measure.
  • Bipartite RWR: Bipartite RWR performs computation only on the partition containing the query node, providing a local estimate.This exploits bipartite structure rather than estimating RWR across the entire graph.
  • K-dash: K-dash avoids computing proximity for all nodes, but directly inverting its sparse matrix may require unrealistic quadratic space on large graphs.LU decomposition is then used to calculate the proximity vector.

3) Lazy Random Walk:

Lazy random walk constructs an image graph whose nodes are pixels and whose transition process permits staying at the current node. The surveyed algorithms differ in scalability and approximation strategy, with K-dash reported as more exact than B-LIN.

  • Lazy Random Walk: LRW represents each image pixel as a graph node and defines node similarity from image intensity values.The similarity uses a user-defined parameter σ.
  • Transition process: LRW assigns probability 1−α to staying at the current node and probability α to walking to an adjacent node.Here α is a control parameter in the range (0, 1).
  • Algorithm comparison: PageRank, personalized PageRank, RWR, and LRW are time-consuming on large graphs, while B-LIN and K-dash have fast convergence on any graph.K-dash calculates proximity more exactly than B-LIN because LU decomposition is not an approximation like B-LIN’s SVD.

B. Algorithms Based on Quantum Walks

Quantum-walk algorithms are organized according to continuous-time and discrete-time models. The continuous-time category includes a quantum decision-tree algorithm based on systematic probabilistic exploration of a whole tree.

  • Quantum-walk categories: Quantum-walk algorithms are divided into continuous-time and discrete-time categories.Quantum decision trees exemplify the continuous-time category, while quantum PageRank exemplifies the discrete-time category.
  • Continuous-time quantum walks: The continuous-time quantum-walk category includes the quantum decision-tree algorithm.The algorithm was originally presented using a decision-tree example.
  • Continuous-time quantum walks: The decision-tree approach systematically explores the whole tree using a probabilistic rule.

1) Continuous Quantum Walk Based Algorithms:

Continuous-time quantum-walk algorithms use Hamiltonians to model time evolution and can improve search performance over classical random walks. Reviewed applications include decision trees, quantum PageRank, and database search, alongside broader comparisons of efficiency and topology preservation.

  • Decision-tree algorithms: Decision-tree nodes are represented as quantum states in Hilbert space, with a Hamiltonian determining the quantum system’s time evolution.The resulting unitary evolution operator supports the continuous-time walk formulation.
  • Decision-tree algorithms: Quantum walks can solve decision-tree problems in polynomial time when corresponding classical algorithms require exponential time.For trees solvable classically in polynomial time, the quantum algorithm also requires polynomial time.
  • Decision-tree algorithms: Childs et al. use two balanced binary trees with a randomly connected pair of leaves to construct an entrance-to-exit oracle problem.The Hamiltonian is based on the graph’s adjacency matrix.
  • Quantum PageRank: Quantum PageRank defines coin and oriented-edge Hilbert spaces and can reveal complex networks’ underlying topology more univocally than classical PageRank.The oriented-edge space uses node pairs and direction labels.
  • Search and comparative analysis: Quantum-walk database-search algorithms reduce the classical O(N) step requirement, while broader comparisons report improved complexity, convergence speed, application scope, and topology preservation.The reviewed literature also identifies performance evaluation across scenarios as difficult.

IV. APPLICATIONS OF RANDOM WALKS

Random walks support applications across recommendation and collaborative filtering by modeling relationships and propagating information through graphs. Reviewed methods address cold-start, similarity estimation, ranking, and collaborator discovery.

  • A. Collaborative Filtering: Random walks model customer-product associations to estimate customer affinities from walk statistics and cosine correlation between graph states.The approach incorporates contextual information from the relational database graph.
  • A. Collaborative Filtering: Cross-validation experiments found the random-walk cosine similarity measure more predictive and robust to perturbations than original measures.The comparison evaluates similarity measures on association graphs.
  • A. Collaborative Filtering: The Laplacian pseudoinverse L+ almost always outperformed standard methods in movie recommendation comparisons.The study compared ten scoring algorithms, including five based on random walks.
  • A. Collaborative Filtering: Random Walk Recommender constructs an item-similarity graph and significantly outperformed a top-N algorithm, especially with sparse training data.Random-walk rank values are treated as user-item ratings.
  • A. Collaborative Filtering: Cold-start users have too few ratings for collaborative filtering, while existing trust-based methods may provide insufficient precision.TrustWalker combines trust-based and item-based recommendation using ratings from similar items.
  • A. Collaborative Filtering: Random-walk methods also support product ranking, paper recommendation, article recommendation, and valuable-collaborator discovery.These methods use correlation, citation, author, preference, or academic-social-network graphs.

C. Link Prediction

Random walks are applied to link prediction, computer vision, and semi-supervised learning by using graph proximity, transition probabilities, and absorption behavior. The reviewed methods balance predictive performance with computational efficiency and parameter control.

  • C. Link Prediction: Link prediction estimates unobserved network links, and random-walk methods include hitting time, PageRank, and related variants.The task uses network information to assess the possibility of future connections.
  • C. Link Prediction: Truncated commute time and local random-walk indices reduce computation or time complexity while retaining good prediction performance.GRANCH also reduces computation and storage while retaining the performance of existing methods.
  • C. Link Prediction: Supervised random walks learn edge-strength parameters so walkers are more likely to reach nodes that will receive future links.The method incorporates rich node and edge attributes.
  • Computer Vision: Random walks support computer-vision tasks including image clustering, segmentation, shape characterization, and visual tracking.Applications use transition matrices, boundary-hitting times, commute time, or graph relationships between superpixels.
  • E. Semi-supervised Learning: Semi-supervised methods use graph structure and unlabeled data for classification, with random walks producing probabilistic label assignments.Some approaches represent labels with a real-valued function or use Markov random walks over manifold structure.
  • E. Semi-supervised Learning: The rendezvous algorithm avoids choosing a good transition parameter t by letting labeled points absorb random-walk states.Absorption probabilities from unlabeled points determine the label distribution as transition steps increase indefinitely.

F. Network Embedding

Network embedding uses random walks to convert graph structure into lower-dimensional node representations for downstream tasks. DeepWalk samples local neighborhoods, while Node2Vec adjusts sampling between breadth-first and depth-first exploration.

  • F. Network Embedding: Network embedding encodes nodes or edges as lower-dimensional vectors while preserving network structure for downstream tasks.It is presented as a direction for network representation.
  • F. Network Embedding: DeepWalk uses truncated random walks to extract local node information, treating node sequences as sentences and nodes as vocabulary words.The approach is inspired by Word2Vec.
  • F. Network Embedding: DeepWalk extends SkipGram and Hierarchical Softmax to reduce computation and speed convergence.
  • F. Network Embedding: Node2Vec provides flexible neighborhood sampling through random walks to represent diverse connection patterns.Its transition strategy uses return parameter p and in-out parameter q.
  • F. Network Embedding: Node2Vec’s sampling parameterization trades off breadth-first sampling and depth-first sampling.

V. OPEN ISSUES

The review identifies scalability challenges for random-walk algorithms in speed, approximation accuracy, main-memory capacity, and large-graph computation. It discusses approximation, graph partitioning, external memory, and quantum-walk computation as responses while highlighting remaining needs.

  • A. Speed of Random Walk Algorithms: O(n^3) or O(m^2) time makes random walk graph kernels impractical on real-world networks, while ARK reduces complexity to O(n^2) or O(m) under a low-intrinsic-rank condition.The review notes that many random-walk models remain at least O(n^2).
  • A. Speed of Random Walk Algorithms: Random walk with restart can be slow at query time or prohibitive in storage, motivating B-LIN, which uses network structure to save storage and computing time while preserving performance.B-LIN exploits block-wise community-like structure and linear correlations in real-world adjacency matrices.
  • A. Speed of Random Walk Algorithms: Approximate computation addresses random-walk speed, but the review calls for more accurate approximate algorithms.
  • B. Problem of Main-Memory Volume: Fast random-walk algorithms generally assume the whole graph fits in main memory, a condition threatened by network growth; graph partitioning and external memory are proposed responses, though latency remains problematic.RWDISK is reported as a better partitioning method on DBLP and Citeseer, but the review still identifies unacceptable latency on enormous graphs.
  • C. Computation of Hitting and Commute Time: O(n^3) commute-time computation is prohibitive for large graphs, and approximations may fail to represent their structure or node connectivity.For sufficiently large random geometric graphs, one approximation uses 1/d_u + 1/d_v, relying on the local densities of two nodes rather than whole-graph structure.
Loading 2008.03639v1…