Random Walk

A random walk strictly adheres to the Markov property: the probability of transitioning to the next node depends solely on the current node, not on the history of previously visited nodes. This memoryless assumption simplifies computation and enables efficient sampling. In a first-order random walk on a graph G, the transition probability from node v_i to v_j is P(v_j | v_i) = 1 / deg(v_i) for uniform walks, where deg(v_i) is the degree of the current node. This property is both a strength—enabling tractable algorithms—and a limitation, as it ignores long-range dependencies in the traversal path.

The Node2Vec algorithm extends the basic random walk by introducing two tunable bias parameters, p and q, creating a second-order Markov chain that interpolates between BFS and DFS exploration:

• Return parameter p: Controls the likelihood of immediately revisiting the previous node. A low p keeps the walk local, capturing structural equivalence.
• In-out parameter q: Controls exploration of inward vs. outward nodes. A low q encourages DFS-like outward exploration, capturing homophily. This biased walk generates sequences that balance local structural roles and global community membership, producing richer node embeddings.

DeepWalk employs a simple, unbiased first-order random walk to generate truncated sequences of nodes. The process treats these sequences analogously to sentences in natural language:

• A fixed number of walks of length L are initiated from each node.
• The resulting node sequences are fed into a SkipGram language model with hierarchical softmax.
• Nodes that appear in similar contexts within these walks are mapped to nearby points in the embedding space. This approach was the first to demonstrate that local neighborhood structure can be learned using techniques originally designed for text corpora.

An infinitely long, irreducible, and aperiodic random walk on a finite graph converges to a unique stationary distribution π, where the probability of being at node v_i is proportional to its degree: π(v_i) = deg(v_i) / 2|E|. This property guarantees that the walk's visitation frequency reflects the graph's connectivity structure. In practice, finite truncated walks are used, and the mixing time—how quickly the walk approaches this stationary distribution—determines the minimum walk length needed to capture representative structural information before the sequence is terminated.

Standard random walks capture proximity-based similarity (nodes near each other get similar embeddings). To capture structural identity—where nodes in different parts of the graph play similar roles (e.g., hub, bridge)—anonymous random walks are used. In an anonymous walk, the state records the first occurrence index of each visited node rather than its identity. The sequence A → B → C → B becomes 1 → 2 → 3 → 2. This anonymization makes the walk agnostic to node labels, allowing structurally analogous nodes in disconnected graph regions to share similar embedding vectors.

The walk length L and the context window size w are critical hyperparameters that define the scope of learned representations:

• Short walks (L small): Capture micro-scale, local neighborhood patterns. Useful for detecting tightly-knit fraud rings.
• Long walks (L large): Capture macro-scale community structure but risk introducing noise from distant, irrelevant nodes.
• Context window w: In the SkipGram model, this defines how many steps forward and backward are considered 'co-occurring.' A larger w smooths embeddings over broader neighborhoods, while a smaller w preserves fine-grained local distinctions.

The process of mapping discrete nodes to a low-dimensional, continuous vector space. Random walks serve as the primary sampling strategy for algorithms like DeepWalk and Node2Vec, generating sequences that preserve structural equivalence and community membership. The geometric proximity of these vectors reflects the original graph's topology, enabling downstream fraud classifiers to operate on dense numerical features.

The unsupervised partitioning of a graph into clusters of densely connected nodes. Random walk-based methods like Walktrap exploit the intuition that short random walks tend to get trapped within communities. This is directly applied to fraud ring detection, identifying tightly-knit groups of malicious actors who exhibit synchronized behavior and share resources within a financial network.

A self-supervised paradigm that trains encoders to maximize mutual information between augmented views of the same graph. Random walk-based augmentations—such as edge dropping or subgraph sampling—create positive pairs for contrastive objectives. This learns robust node representations without labeled fraud data, a critical advantage in domains where known fraud labels are scarce and expensive to obtain.

A technique that jointly optimizes graph topology and GNN parameters during training. Random walks can probe the latent connectivity of a noisy or adversarially manipulated transaction graph, helping to denoise the structure. This improves the robustness of fraud classifiers against adversarial attacks designed to hide malicious activity by subtly rewiring the graph.