On node embedding

One 、DeepWalk

The origin of the paper ：https://arxiv.org/pdf/1403.6652.pdf

Algorithm ：

DeepWalk The idea is ： For each node in the graph , We should all start from it $\gamma$ A random walk sequence with maximum length , In the end $|V|\cdot \gamma$ A sequence of . Think of each sequence as a sentence , Regard the nodes as words , So we can apply to these sequences Word2Vec（Skip-Gram + Hierachical Softmax） Get the embedded representation of the node .

In the diagram above ,$w$ Is the window size , That is to say Skip-Gram In the model , Predict with the central word $2w$ A context word ;$d$ Is the dimension of the node vector ;$\gamma$ For each node in the graph , How many random walk sequences should we generate from it ;$t$ Is the maximum length of the random walk sequence .

1.1 Simple implementation

Take an undirected graph as an example , Suppose that all nodes are identified by integer numbers , The corresponding implementation is as follows

import random
from gensim.models import Word2Vec


def random_walk(graph, root, walk_length):
	# graph by networkx Undirected graph type in ,root Is an integer 
	#  This function generates only one random walk sequence at a time 
    seq = [root]
    for _ in range(walk_length - 1):
        seq.append(random.choice(list(graph.neighbors(seq[-1]))))
    return seq


def deep_walk(graph, windows_size, embed_size, gamma, walk_length):
    seqs = [random_walk(graph, node, walk_length) for node in graph.nodes for _ in range(gamma)]
    model = Word2Vec(seqs, vector_size=embed_size, window=windows_size, sg=1, hs=1)
    return model.wv

Two 、Node2Vec

The origin of the paper ：https://arxiv.org/pdf/1607.00653.pdf

DeepWalk In fact, it means Word2Vec Used on the map ,Node2Vec stay DeepWalk On the basis of that, we improved , Walk completely random （ Suppose a node has $N$ Neighbor nodes , Then the probability of next step to each neighbor node is $1/N$） Changed to biased random walk （ The probability of next step to each neighbor node is different ）.

Here's the picture ,Node2Vec Second order random walk is used , That is, where to go next depends not only on the current node , It also depends on the previous node ：

Parameters $p$ Determines the probability of going back , Parameters $q$ Decided to prefer BFS still DFS.

In particular , Set the node of the previous time step as $t$, The node of the current time step is $v$, The node of the next time step is $x$, be

$$P(x|v)=\{\begin{array}{ll}{\pi }_{vx}/Z,& (v,x)\in E\\ 0,& others\end{array}$$

among ${\pi }_{vx}$ yes $v\to x$ Preprocessing transition probability （ It's not probability ）,$Z$ It's the normalization factor （ Is used to ${\pi }_{vx}$ Become probability ）,$E$ It's an edge set . set up $w_{vx}$ Represents the edge $(v,x)$ The weight of （ There are $w_{vx}=1$）, be ${\pi }_{vx}$ Defined as ${\pi }_{vx}=w_{vx}\cdot {\alpha }_{pq}(t,x)$, among

$${\alpha }_{pq}(t,x)=\{\begin{array}{ll}1/p,& d_{tx}=0\\ 1,& d_{tx}=1\\ 1/q,& d_{tx}=2\end{array}$$

It can be seen that , When ${\pi }_{vx}=1$ when ,Node2Vec It degenerates into DeepWalk.

Algorithm ：

You can see from the pseudo code that , This algorithm is similar to DeepWalk The main difference is the sampling strategy of nodes . because DeepWalk It's a completely random walk , So each time you just need to randomly select one of the neighbor nodes OK 了 , and Node2Vec Is biased random walk , So you need to use Alias Sampling technology , Its time complexity is $O(1)$（ Space for time ）.

of Alias Sampling May refer to ：https://www.keithschwarz.com/darts-dice-coins/.

2.1 Simple implementation

At present, there are ready-made third-party libraries （ be based on NetworkX and Gensim）, Project address ：https://github.com/eliorc/node2vec.

When in use, it can be imported directly ：

from node2vec import Node2Vec

An example ：

G = nx.les_miserables_graph()
model = Node2Vec(G, dimensions=32, walk_length=3, num_walks=600, p=2, q=0.5, workers=4).fit(window=3,
                                                                                            min_count=1,
                                                                                            batch_words=4)