Node2Vec

8/2/2021 Node2Vec

# Node2Vec中的同质性和结构性指的是什么?他们与DFS和BFS的对应关系如何?

Node2Vec通过调整随机游走权重的方法使Graph Embedding的结果更倾向于体现网络的同质性或结构性。

网络的”同质性“指的是距离相近节点的Embedding应尽量近似,如图所示,节点与其相连的节点的Embedding表达应该是接近的,这就是网络”同质性“的体现。

”结构性“指的是结构上相似的节点的Embedding应尽量近似,图中节点U和节点都是各自局域网络的中心节点,结构上相似,其Embedding的表达也应该近似,这就是”结构性“的体现。

为表达同质性,可以让游走的过程更倾向于DFS,因为DFS更有可能通过多次跳转,游走到远方的节点上,但无论怎样,DFS的游走更大概率会在一个集团内部进行,这就使得一个集团或者社区内部的节点的Embedding更为相似,从而更多地表达网络的”同质性“。

为表达”结构性“,可以让游走的过程更倾向于BFS,因为BFS会更多地在当前节点的领域中游走遍历,相当于对当前节点周边的网络结构进行一次”微观扫描“。当前节点是"局部中心节点",还是”边缘节点“,或是”连接性节点“,其生成的序列包含的节点数量和顺序必然是不同的,从而最终的Embedding抓取到更多结构性信息。

# 请写出Node2Vec的节点间跳转概率公式。

在Node2Vec算法中,主要是通过节点间的跳转概率来控制其同质性和结构性的倾向的。

下图所示为Node2Vec算法从节点t跳转到节点v,再从节点v跳转到周围各点的跳转概率。

从节点v跳转到下一个节点x的概率,其中是边的权重,的定义如下:

\begin{cases} \frac{1}{p}, if d_{tx}=0 \\ 1,if d_{tx}=1 \\ \frac{1}{q} ,if d_{tx}=2\end{cases}

其中,指节点到节点的距离,参数共同控制随机游走的倾向。参数被称为返回参数,越小,随机游走回节点的可能性越大,Node2Vec就更注重表达网络的结构性。参数被称为进出参数,越小,随机游走到远方节点的可能性越大,Node2Vec就更注重表达网络的同质性;反之,则当前节点更可能在附近节点游走。

# 举例说明Node2Vec的同质性和结构性在推荐系统中的直观解释。

同质性相同的物品很可能是同品类、同属性,或者经常被一同购买的商品,而结构性相同的物品则是各品类的爆款、各品类的最佳凑单商品等拥有类似趋势或者结构性属性的商品。这两者在推荐系统中都是非常重要的特征表达。

由于Node2Vec的这种灵活性,以及发掘不同图特征的能力,甚至可以把不同Node2Vec生成的偏向”结构性“的Embedding结果和偏向”同质性“的Embedding结果共同输入后续的深度学习网络,以保留物品的不同图特征信息。