cayleypy.algo.RandomWalksGenerator

class cayleypy.algo.RandomWalksGenerator[source]

Generator for random walks on Cayley graphs.

This class encapsulates the logic for generating random walks using different modes:

  • “classic”: Simple random walks with independent steps.

  • “bfs”: Breadth-first search based random walks with uniqueness constraints.

__init__(graph: CayleyGraph)[source]

Initialize the random walks generator.

Parameters:

graph – The Cayley graph to generate walks on.

Methods

__init__(graph)

Initialize the random walks generator.

generate(*[, width, length, mode, ...])

Generates random walks on the graph.

random_walks_bfs(width, length, start_state)

Generate BFS-based random walks.

random_walks_classic(width, length, start_state)

Generate classic random walks.

random_walks_nbt(width, length, start_state)

Generate non-backtracking beam search random walks.
generate(*, width=5, length=10, mode='classic', start_state: None | Tensor | ndarray | list = None, nbt_history_depth: int = 0) → tuple[Tensor, Tensor][source]

Generates random walks on the graph.

The following modes of random walk generation are supported:

  • “classic” - random walk is a path in this graph starting from start_state, where on each step the next edge is chosen randomly with equal probability. We generate width such random walks independently. The output will have exactly width*length states. i-th random walk can be extracted as: [x[i+j*width] for j in range(length)]. y[i] is equal to number of random steps it took to get to state x[i]. Note that in this mode a lot of states will have overestimated distance (meaning y[i] may be larger than the length of the shortest path from x[i] to start_state). The same state may appear multiple times with different distance in y.

  • “bfs” - we perform Breadth First Search starting from start_state with one modification: if size of next layer is larger than width, only width states (chosen randomly) will be kept. We also remove states from current layer if they appeared on some previous layer (so this also can be called “non-backtracking random walk”). All states in the output are unique. y still can be overestimated, but it will be closer to the true distance than in “classic” mode. Size of output is <= width*length. If width and length are large enough (width at least as large as largest BFS layer, and length >= diameter), this will return all states and true distances to the start state.

  • “nbt” - non-backtracking beam search random walks. This mode generates improved non-backtracking random walks that “mix even faster” - the number of random walk steps will be better related to actual distance on the graph. The procedure is similar to beam search, except there is no goal function. All trajectories know about each other and avoid visiting states visited by any trajectory. Additionally, 1-neighbors of current states are also banned to improve mixing. The nbt_history_depth parameter controls how many previous levels to remember and ban.

Parameters:

  • width – Number of random walks to generate.

  • length – Length of each random walk.

  • start_state – State from which to start random walk. Defaults to the central state.

  • mode – Type of random walk (see above). Defaults to “classic”.

  • nbt_history_depth – For “nbt” mode, how many previous levels to remember and ban from revisiting.

Returns:

Pair of tensors x, y. x contains states. y[i] is the estimated distance from start state to state x[i].

random_walks_bfs(width: int, length: int, start_state: Tensor) → tuple[Tensor, Tensor][source]

Generate BFS-based random walks.

Parameters:

  • width – Maximum number of states per layer.

  • length – Maximum number of layers.

  • start_state – Starting state for the BFS.

Returns:

Tuple of (states, distances).

random_walks_classic(width: int, length: int, start_state: Tensor) → tuple[Tensor, Tensor][source]

Generate classic random walks.

Parameters:

  • width – Number of random walks to generate.

  • length – Length of each random walk.

  • start_state – Starting state for all walks.

Returns:

Tuple of (states, distances).

random_walks_nbt(width: int, length: int, start_state: Tensor, history_depth: int = 0) → tuple[Tensor, Tensor][source]

Generate non-backtracking beam search random walks.

This method generates improved non-backtracking random walks that “mix even faster” - the number of random walk steps will be better related to actual distance on the graph. The procedure is similar to beam search, except there is no goal function. All trajectories know about each other and avoid visiting states visited by any trajectory.

Parameters:

  • width – Number of random walks to generate in parallel.

  • length – Length of each random walk.

  • start_state – Starting state for all walks (encoded).

  • history_depth – How many previous levels to remember and ban from revisiting.

Returns:

Tuple of (states, distances).