简单实践GraphEmbedding图嵌入的几种方法

水深无声 2023-01-23 11:51 9阅读 0赞

参考：  
[详解Graph Embedding经典方法：算法原理、代码实现与应用样例][Graph Embedding]  
[Graph Embedding 图表示学习的原理及应用][Graph Embedding 1]

代码参考：  
https://github.com/shenweichen/GraphEmbedding

本篇简单测试一下该库

--------------------

### 文章目录 ###

*  1 Graph Embedding 几种常见方法
 *   *  1.1 DeepWalk
     *  1.2 LINE
     *  1.3 nodo2vec
     *  1.4 SDNE
     *  1.5 Struc2Vec
 *  2 实验代码

--------------------

# 1 Graph Embedding 几种常见方法 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Model</th> 
   <th align="left">Paper</th> 
   <th align="left">Note</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">DeepWalk</td> 
   <td align="left">[KDD 2014]<a href="http://www.perozzi.net/publications/14_kdd_deepwalk.pdf" rel="nofollow">DeepWalk: Online Learning of Social Representations</a></td> 
   <td align="left"><a href="https://zhuanlan.zhihu.com/p/56380812" rel="nofollow">【Graph Embedding】DeepWalk：算法原理，实现和应用</a></td> 
  </tr> 
  <tr> 
   <td align="center">LINE</td> 
   <td align="left">[WWW 2015]<a href="https://arxiv.org/pdf/1503.03578.pdf" rel="nofollow">LINE: Large-scale Information Network Embedding</a></td> 
   <td align="left"><a href="https://zhuanlan.zhihu.com/p/56478167" rel="nofollow">【Graph Embedding】LINE：算法原理，实现和应用</a></td> 
  </tr> 
  <tr> 
   <td align="center">Node2Vec</td> 
   <td align="left">[KDD 2016]<a href="https://www.kdd.org/kdd2016/papers/files/rfp0218-groverA.pdf" rel="nofollow">node2vec: Scalable Feature Learning for Networks</a></td> 
   <td align="left"><a href="https://zhuanlan.zhihu.com/p/56542707" rel="nofollow">【Graph Embedding】Node2Vec：算法原理，实现和应用</a></td> 
  </tr> 
  <tr> 
   <td align="center">SDNE</td> 
   <td align="left">[KDD 2016]<a href="https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf" rel="nofollow">Structural Deep Network Embedding</a></td> 
   <td align="left"><a href="https://zhuanlan.zhihu.com/p/56637181" rel="nofollow">【Graph Embedding】SDNE：算法原理，实现和应用</a></td> 
  </tr> 
  <tr> 
   <td align="center">Struc2Vec</td> 
   <td align="left">[KDD 2017]<a href="https://arxiv.org/pdf/1704.03165.pdf" rel="nofollow">struc2vec: Learning Node Representations from Structural Identity</a></td> 
   <td align="left"><a href="https://zhuanlan.zhihu.com/p/56733145" rel="nofollow">【Graph Embedding】Struc2Vec：算法原理，实现和应用</a></td> 
  </tr> 
 </tbody> 
</table>

Graph Embedding 技术将图中的节点以低维稠密向量的形式进行表达，要求在原始图中相似 ( 不同的方法对相似的定义不同 ) 的节点其在低维表达空间也接近。得到的表达向量可以用来进行下游任务，如节点分类，链接预测，可视化或重构原始图等。

## 1.1 DeepWalk ##

DeepWalk 的思想类似 word2vec，使用图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系，DeepWalk 给出的方法是使用随机游走 (RandomWalk) 的方式在图中进行节点采样。

分类任务结果

> micro-F1 : 0.6674  
> macro-F1 : 0.5768

## 1.2 LINE ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI2OTE3Mzgz_size_16_color_FFFFFF_t_70]

之前介绍过DeepWalk，DeepWalk使用DFS随机游走在图中进行节点采样，使用word2vec在采样的序列学习图中节点的向量表示。

LINE也是一种基于邻域相似假设的方法，只不过与DeepWalk使用DFS构造邻域不同的是，LINE可以看作是一种使用BFS构造邻域的算法。此外，LINE还可以应用在带权图中(DeepWalk仅能用于无权图)。

分类任务结果

> micro-F1: 0.6403  
> macro-F1:0.5286

结果有一定随机性，可以多运行几次，或者稍微调整epoch个数。

## 1.3 nodo2vec ##

前面介绍过基于DFS邻域的DeepWalk和基于BFS邻域的LINE。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI2OTE3Mzgz_size_16_color_FFFFFF_t_70 1]

node2vec是一种综合考虑DFS邻域和BFS邻域的graph embedding方法。简单来说，可以看作是deepwalk的一种扩展，是结合了DFS和BFS随机游走的deepwalk。  
分类任务

> micro-F1: 0.6757 macro-F1: 0.5917

这个结果相比于DeepWalk和LINE是有提升的。

## 1.4 SDNE ##

SDNE（Structural Deep Network Embedding ）是和node2vec并列的工作，均发表在2016年的KDD会议中。可以看作是基于LINE的扩展，同时也是第一个将深度学习应用于网络表示学习中的方法。  
SDNE使用一个自动编码器结构来同时优化1阶和2阶相似度(LINE是分别优化的)，学习得到的向量表示能够保留局部和全局结构，并且对稀疏网络具有鲁棒性。

分类任务

> micro-F1: 0.6341 macro-F1: 0.4962

这里还有一个SDNE在业界的应用的介绍：  
[阿里凑单算法首次公开！基于Graph Embedding的打包购商品挖掘系统解析][Graph Embedding 2]

## 1.5 Struc2Vec ##

前面介绍过DeepWalk,LINE,Node2Vec,SDNE几个graph embedding方法。这些方法都是基于近邻相似的假设的。其中DeepWalk,Node2Vec通过随机游走在图中采样顶点序列来构造顶点的近邻集合。LINE显式的构造邻接点对和顶点的距离为1的近邻集合。SDNE使用邻接矩阵描述顶点的近邻结构。  
事实上，在一些场景中，两个不是近邻的顶点也可能拥有很高的相似性，对于这类相似性，上述方法是无法捕捉到的。Struc2Vec就是针对这类场景提出的。Struc2Vec的论文发表在2017年的KDD会议中。

分类

> Struc2Vec结果 micro-F1: 0.7143, macro-F1: 0.7357  
> Node2Vec结果 micro-F1: 0.3571, macro-F1: 0.3445

差距还是蛮大的，说明Struc2Vec确实能够更好的捕获空间结构性。

--------------------

# 2 实验代码 #

import pandas as pd
    import copy
    from collections import Counter
    from tqdm import tqdm
    import sys
    import random
    sys.path.append('GraphEmbedding')
    #from GraphEmbedding.examples.struc2vec_flight import *
    import time
    import numpy as np
    import matplotlib.pyplot as plt
    import networkx as nx
    from sklearn.manifold import TSNE
    import pandas as pd
    from collections import Counter
    
    
    data_list = [set(['A','B']),set(['D','C']),set(['E','A']),set(['E','D']),set(['A','D']),set(['B','D'])]
    
    
    item_id = set()
    data_list_3 = {}
    total_freq = len(data_list)
    
    for dl in tqdm(data_list):
        # 
        for d in dl:
            item_id.add(str(d).replace(' ',''))
        # 
        dl = copy.deepcopy(tuple(str(d).replace(' ','') for d in dl))
        if dl not in data_list_3.keys():
            data_list_3[dl] = 0
        data_list_3[dl] += 1
    
    data_label = {str(ii).replace(' ',''):str(n) for n,ii in enumerate(item_id)} # 节点：节点编号
    data_list_3 = {k:v for k,v in data_list_3.items()}   # [A,B]出现频率
    
    # 数据导出 - 节点-节点
    edgelist_file = open('GraphEmbedding/test/data.edgelist','w+',encoding = 'utf-8') 
    
    for k,v in tqdm(data_list_3.items()):
        k = [str(_k) for _k in k]
        text = ' '.join([data_label[_k] for _k in k]+[str(v)]) + '\n'
        # text = ' '.join(list(k)) + '\n'
        edgelist_file.write(text)
    
    edgelist_file.close()
    
    # 数据导出 - 节点-解释
    edgelist_label = open('GraphEmbedding/test/data.label','w+',encoding = 'utf-8') 
    
    for k,v in tqdm(data_label.items()):
        text = ' '.join([k,v]) + '\n'
        # text = ' '.join(list(k)) + '\n'
        edgelist_label.write(text)
    
    edgelist_label.close()
    
    
    
    #----
    def bit_product_sum(x, y):
        return sum([item[0] * item[1] for item in zip(x, y)])
    
    
    def cosine_similarity(x, y, norm=False):
        """ 计算两个向量x和y的余弦相似度 """
        assert len(x) == len(y), "len(x) != len(y)"
        zero_list = [0] * len(x)
        if x == zero_list or y == zero_list:
            return float(1) if x == y else float(0)
    
        # method 1
        res = np.array([[x[i] * y[i], x[i] * x[i], y[i] * y[i]] for i in range(len(x))])
        cos = sum(res[:, 0]) / (np.sqrt(sum(res[:, 1])) * np.sqrt(sum(res[:, 2])))
    
        # method 2
        # cos = bit_product_sum(x, y) / (np.sqrt(bit_product_sum(x, x)) * np.sqrt(bit_product_sum(y, y)))
    
        # method 3
        # dot_product, square_sum_x, square_sum_y = 0, 0, 0
        # for i in range(len(x)):
        #     dot_product += x[i] * y[i]
        #     square_sum_x += x[i] * x[i]
        #     square_sum_y += y[i] * y[i]
        # cos = dot_product / (np.sqrt(square_sum_x) * np.sqrt(square_sum_y))
    
        return 0.5 * cos + 0.5 if norm else cos  # 归一化到[0, 1]区间内
    
    
    def plot_embeddings(emb_list,color_random = []):
        #X, Y = read_node_label('../data/wiki/wiki_labels.txt')
        X = emb_list
        if len(color_random) == 0:
            color_random = [random.sample(range(20), 1)[0] for _ in range(len(embeddings))]
    
        model = TSNE(n_components=2)
        node_pos = model.fit_transform(emb_list)
        
        color_idx = {}
        for i in range(len(X)):
            color_idx.setdefault(color_random[i], [])
            color_idx[color_random[i]].append(i)
    
        for c, idx in color_idx.items():
            plt.scatter(node_pos[idx, 0], node_pos[idx, 1], label=c)
        plt.legend()
        plt.show()
    
    
    G = nx.read_edgelist('GraphEmbedding/test/data.edgelist', create_using=nx.DiGraph(), nodetype=None,
                         data=[('weight', int)])
    # struc2vec -> 最有规律
    from ge import Struc2Vec
    s2v_model = Struc2Vec(G, 10, 80, workers=4, verbose=40, )
    s2v_model.train()
    embeddings = s2v_model.get_embeddings()
    
    
    
    # from ge import SDNE
    # sdne_model = SDNE(G, hidden_size=[1024, 512],)
    # sdne_model.train(batch_size=20000, epochs=50, verbose=2)
    # embeddings = sdne_model.get_embeddings()
    
    # node2vec -> 有一小簇有规律
    from ge import Node2Vec
    n2v_model = Node2Vec(G, walk_length=10, num_walks=80,
                     p=0.25, q=4, workers=1, use_rejection_sampling=0)
    n2v_model.train(window_size = 5, iter = 3)
    embeddings=n2v_model.get_embeddings()
    
    # DeepWalk -> 最散
    from ge import DeepWalk
    dw_model = DeepWalk(G, walk_length=10, num_walks=80, workers=1)
    dw_model.train(window_size=5, iter=3)
    embeddings = dw_model.get_embeddings()
    
    # 画图
    emb_list = np.array(list(embeddings.values()))
    #evaluate_embeddings(embeddings)
    plot_embeddings(emb_list)
    
    
    # id中文名
    label = pd.read_table('GraphEmbedding/test/data.label',header = None)
    id_to_label = {l.split(' ')[1]:l.split(' ')[0]  for l in label[0]}
    label_to_id = {l.split(' ')[0]:l.split(' ')[1]  for l in label[0]}
    
    
    # 求相似产品
    simi = n2v_model.w2v_model.wv.most_similar(label_to_id['D'],topn = 20)
    simi
    n2v_model.sentences

开源代码已经把各个调用写的非常简单了，所以简单处理数据就可以直接测试，需要包括：

*  data.edgelist 边信息
 *  data.label 节点信息

后续还可以通过TSNE把向量可视化出来,在函数`plot_embeddings`之中

因为借助的是gensim，所以可以使用任何词向量的功能，包括近似词查询等

在自己的实践里，貌似`struc2vec`从可视化TSNE效果来看，最好，分的最清楚。

[Graph Embedding]: https://mp.weixin.qq.com/s/opMWSr5TQ7bUaz_LkwsgrQ
[Graph Embedding 1]: https://mp.weixin.qq.com/s/Th3dS8Sd5R7MZe7pQYHwtw
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI2OTE3Mzgz_size_16_color_FFFFFF_t_70]: /images/20221004/ab04b488595e48c882e93f1b75d303fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI2OTE3Mzgz_size_16_color_FFFFFF_t_70 1]: /images/20221004/c2dbb79bb2a74c45b28dc4e4e89db2cc.png
[Graph Embedding 2]: https://mp.weixin.qq.com/s?__biz=MzIzOTU0NTQ0MA==&mid=2247486868&idx=1&sn=c2d3e38e9ab7cc61f2a2ffaeecf0febe&chksm=e929309bde5eb98dfa657c7fd1bf7e80495f9c9ad0cde2ee78b36a1f0a453d2cc322948cb3a3&mpshare=1&scene=21&srcid=0213HJqpvPzBLS7AW7L6K3Zz#wechat_redirect