A second-order biased random walk chooses its next node using both the current node and the node visited immediately before it. This contrasts with a first-order walk, which considers only its current node. section 9.3.2
The technique is used by node2vec to generate node sequences. Each sequence treats visited nodes as words, and the resulting sentences become training examples for the word2vec skip-gram model. Walk length controls sentence size, and walks begin from every node to capture the graph broadly. section 9.3.2 section 9.5
Key implementation ideas include:
- Use the previous step when evaluating the next traversal, rather than treating every visit to the current node identically. section 9.3.2
- Account for relationship weights when the graph is weighted; a connection's probability reflects its weight relative to neighboring weights. section 9.3.2
- Adjust walk length to control how many nodes appear in each generated sentence. section 9.3.2
Choosing the next move
After a walk moves from node D to node A, the next traversal is evaluated with both A and D in context. A first-order walk would use only A, assigning equal probabilities to four unweighted neighbors. section 9.3.2
Use the graph illustration to trace how the immediately previous node changes the next traversal possibilities. section 9.3.2
