说到 GNN, 各位炼丹师会想到哪些算法呢? 不管想到哪些算法, 我们真正用到过哪些呢? 确实我们可能都看过 GNN 相关论文, 但是还是缺乏实战经验的. 特别是对于推荐系统而言, 我们又该如何应用这些模型呢? 下面我们就从 DeepWalk 这篇论文开始, 先讲原理, 再讲实战, 最后讲应用.

GNN 相关背景知识

GNN 的本质, 是要学习网络中每个节点的表达的, 这些潜在的表达对图中每个节点的 “社交” 关系进行了编码, 把离散值的节点编码成稠密向量, 后续可用于分类回归, 或者作为下游任务的特征. Deepwalk 充分利用了随机游走提取的“句子”, 去学习句子中每个单词的表达. Deepwalk 原文就提到了在数据稀疏的情况下可以把 F1-scores 提升 10%, 在一些实验中, 能够用更少的训练数据获得了更好的效果. 看下图的例子:

大有可为的GNN：DeepWalk - 图1

Deepwalk

问题定义:

先把问题定义为给社交网络中的每个节点进行分类, 图可以表达为 G=,V 就是图上所有节点, E 是所有边. 有一部分有 label 的数据 GL=(V,E,X,Y),X 就是节点的特征, Y 就是分类的 label. 在传统机器学习算法中, 我们都是直接学习 (X,Y), 并没有充分利用节点间的依赖关系. Deepwalk 可以捕捉图上的拓扑关系, 通过无监督方法学习每个节点的特征, 学到的图特征和标签的分布是相互独立的.

随机游走:

选定一个根节点,“随机” 走出一条路径, 基于相邻的节点必然相似, 我们就可以用这种策略去挖掘网络的社群信息. 随机游走很方便并行, 可以同时提取一张图上各个部分的信息. 即使图有小的改动, 这些路径也不需要重新计算. 和 word 的出现频率类似, 通过随机游走得到的节点访问频率都符合幂律分布, 所以我们就可以用 NLP 相关方法对随机游走结果做相似处理, 如下图所示:

大有可为的GNN：DeepWalk - 图2

所以在随机游走后, 我们只需要通过下公式, 学习节点向量即可:

大有可为的GNN：DeepWalk - 图3

该公式就是 skip-gram, 通过某个节点学习它左右的节点. 我们都知道 skip-gram 用于文本时的语料库就是一个个句子, 现在我们提取图的句子. 如下所示:

大有可为的GNN：DeepWalk - 图4
大有可为的GNN：DeepWalk - 图5

算法很简单, 把所有节点顺序打乱 (加速收敛), 然后遍历这些节点随机游走出序列, 再通过 skipgram 算法去拟合每个节点的向量. 如此反复. 注: 这里的随机是均匀分布去随机. 当然有些图会有些 “副产物”, 比如用户浏览网页的顺序, 可以直接输入到模型.

接下来我们看下 deepwalks 的核心代码:

  1. # 代码来源 
  2. # phanein/deepwalk
  3. # Random walk
  4. with open(f, 'w') as fout:
  5.   for walk in graph.build_deepwalk_corpus_iter(G=G, # 图
  6.                                                num_paths=num_paths, # 路径数
  7.                                                path_length=path_length, # 路径长度
  8.                                                alpha=alpha, #
  9.                                                rand=rand): #
  10.     fout.write(u"{}\n".format(u" ".join(v for v in walk)))
  12. class Graph(defaultdict):
  13.   """
  14.   Efficient basic implementation of nx
  15.   这里我们看到,
  16.   该类继承defaultdict,
  17.   图其实可以简单的表示为dict,
  18.   key为节点,value为与之相连的节点
  19.   """  
  20.   def __init__(self):
  21.     super(Graph, self).__init__(list)
  23.   def nodes(self):
  24.     return self.keys()
  26.   def adjacency_iter(self):
  27.     return self.iteritems()
  29.   def subgraph(self, nodes={}):
  30.     # 提取子图
  31.     subgraph = Graph()
  33.     for n in nodes:
  34.       if n in self:
  35.         subgraph[n] = [x for x in self[n] if x in nodes]
  37.     return subgraph
  39.   def make_undirected(self):
  40.     #因为是无向图,所以v in self[u]并且 u in self[v]
  41.     t0 = time()
  43.     for v in list(self):
  44.       for other in self[v]:
  45.         if v != other:
  46.           self[other].append(v)
  48.     t1 = time()
  49.     logger.info('make_directed: added missing edges {}s'.format(t1-t0))
  51.     self.make_consistent()
  52.     return self
  54.   def make_consistent(self):
  55.     # 去重
  56.     t0 = time()
  57.     for k in iterkeys(self):
  58.       self[k] = list(sorted(set(self[k])))
  60.     t1 = time()
  61.     logger.info('make_consistent: made consistent in {}s'.format(t1-t0))
  63.     self.remove_self_loops()
  65.     return self
  67.   def remove_self_loops(self):
  68.     # 自已不会与自己有连接
  69.     removed = 0
  70.     t0 = time()
  72.     for x in self:
  73.       if x in self[x]: 
  74.         self[x].remove(x)
  75.         removed += 1
  77.     t1 = time()
  79.     logger.info('remove_self_loops: removed {} loops in {}s'.format(removed, (t1-t0)))
  80.     return self
  82.   def check_self_loops(self):
  83.     for x in self:
  84.       for y in self[x]:
  85.         if x == y:
  86.           return True
  88.     return False
  90.   def has_edge(self, v1, v2):
  91.     # 两个节点是否有边
  92.     if v2 in self[v1] or v1 in self[v2]:
  93.       return True
  94.     return False
  96.   def degree(self, nodes=None):
  97.     # 节点的度数
  98.     if isinstance(nodes, Iterable):
  99.       return {v:len(self[v]) for v in nodes}
  100.     else:
  101.       return len(self[nodes])
  103.   def order(self):
  104.     "Returns the number of nodes in the graph"
  105.     return len(self)    
  107.   def number_of_edges(self):
  108.     # 图中边的数量
  109.     "Returns the number of nodes in the graph"
  110.     return sum([self.degree(x) for x in self.keys()])/2
  112.   def number_of_nodes(self):
  113.     # 图中结点数量
  114.     "Returns the number of nodes in the graph"
  115.     return self.order()
  117.   # 核心代码
  118.   def random_walk(self, path_length, alpha=0, rand=random.Random(), start=None):
  119.     """ Returns a truncated random walk.
  120.         path_length: Length of the random walk.
  121.         alpha: probability of restarts.
  122.         start: the start node of the random walk.
  123.     """
  124.     G = self
  125.     if start:
  126.       path = [start]
  127.     else:
  128.       # Sampling is uniform w.r.t V, and not w.r.t E
  129.       path = [rand.choice(list(G.keys()))]
  131.     while len(path) < path_length:
  132.       cur = path[-1]
  133.       if len(G[cur]) > 0:
  134.         if rand.random() >= alpha:
  135.           path.append(rand.choice(G[cur])) # 相邻节点随机选
  136.         else:
  137.           path.append(path[0]) # 有一定概率选择回到起点
  138.       else:
  139.         break
  140.     return [str(node) for node in path]
  142. # TODO add build_walks in here
  144. def build_deepwalk_corpus(G, num_paths, path_length, alpha=0,
  145.                       rand=random.Random(0)):
  146.   walks = []
  148.   nodes = list(G.nodes())
  149.   # 这里和上面论文算法流程对应
  150.   for cnt in range(num_paths): # 外循环,相当于要迭代多少epoch
  151.     rand.shuffle(nodes) # 打乱nodes顺序,加速收敛
  152.     for node in nodes: # 每个node都会产生一条路径
  153.       walks.append(G.random_walk(path_length, rand=rand, alpha=alpha, start=node))
  155.   return walks
  157. def build_deepwalk_corpus_iter(G, num_paths, path_length, alpha=0,
  158.                       rand=random.Random(0)):
  159.   # 流式处理用
  160.   walks = []
  162.   nodes = list(G.nodes())
  164.   for cnt in range(num_paths):
  165.     rand.shuffle(nodes)
  166.     for node in nodes:
  167.       yield G.random_walk(path_length, rand=rand, alpha=alpha, start=node)
  170. def clique(size):
  171.     return from_adjlist(permutations(range(1,size+1)))
  172. # How do you split a list into evenly sized chunks?
  173. def grouper(n, iterable, padvalue=None):
  174.     "grouper(3, 'abcdefg', 'x') --> ('a','b','c'), ('d','e','f'), ('g','x','x')"
  175.     return zip_longest(*[iter(iterable)]*n, fillvalue=padvalue)
  177. def parse_adjacencylist(f):
  178.   adjlist = []
  179.   for l in f:
  180.     if l and l[0] != "#":
  181.       introw = [int(x) for x in l.strip().split()]
  182.       row = [introw[0]]
  183.       row.extend(set(sorted(introw[1:])))
  184.       adjlist.extend([row])
  186.   return adjlist
  188. def parse_adjacencylist_unchecked(f):
  189.   adjlist = []
  190.   for l in f:
  191.     if l and l[0] != "#":
  192.       adjlist.extend([[int(x) for x in l.strip().split()]])
  194.   return adjlist
  196. def load_adjacencylist(file_, undirected=False, chunksize=10000, unchecked=True):
  198.   if unchecked:
  199.     parse_func = parse_adjacencylist_unchecked
  200.     convert_func = from_adjlist_unchecked
  201.   else:
  202.     parse_func = parse_adjacencylist
  203.     convert_func = from_adjlist
  205.   adjlist = []
  207.   t0 = time()
  209.   total = 0 
  210.   with open(file_) as f:
  211.     for idx, adj_chunk in enumerate(map(parse_func, grouper(int(chunksize), f))):
  212.       adjlist.extend(adj_chunk)
  213.       total += len(adj_chunk)
  215.   t1 = time()
  217.   logger.info('Parsed {} edges with {} chunks in {}s'.format(total, idx, t1-t0))
  219.   t0 = time()
  220.   G = convert_func(adjlist)
  221.   t1 = time()
  223.   logger.info('Converted edges to graph in {}s'.format(t1-t0))
  225.   if undirected:
  226.     t0 = time()
  227.     G = G.make_undirected()
  228.     t1 = time()
  229.     logger.info('Made graph undirected in {}s'.format(t1-t0))
  231.   return G 
  234. def load_edgelist(file_, undirected=True):
  235.   G = Graph()
  236.   with open(file_) as f:
  237.     for l in f:
  238.       x, y = l.strip().split()[:2]
  239.       x = int(x)
  240.       y = int(y)
  241.       G[x].append(y)
  242.       if undirected:
  243.         G[y].append(x)
  245.   G.make_consistent()
  246.   return G
  249. def load_matfile(file_, variable_name="network", undirected=True):
  250.   mat_varables = loadmat(file_)
  251.   mat_matrix = mat_varables[variable_name]
  253.   return from_numpy(mat_matrix, undirected)
  256. def from_networkx(G_input, undirected=True):
  257.     G = Graph()
  259.     for idx, x in enumerate(G_input.nodes()):
  260.         for y in iterkeys(G_input[x]):
  261.             G[x].append(y)
  263.     if undirected:
  264.         G.make_undirected()
  266.     return G
  269. def from_numpy(x, undirected=True):
  270.     G = Graph()
  272.     if issparse(x):
  273.         cx = x.tocoo()
  274.         for i,j,v in zip(cx.row, cx.col, cx.data):
  275.             G[i].append(j)
  276.     else:
  277.       raise Exception("Dense matrices not yet supported.")
  279.     if undirected:
  280.         G.make_undirected()
  282.     G.make_consistent()
  283.     return G
  286. def from_adjlist(adjlist):
  287.     G = Graph()
  289.     for row in adjlist:
  290.         node = row[0]
  291.         neighbors = row[1:]
  292.         G[node] = list(sorted(set(neighbors)))
  294.     return G
  297. def from_adjlist_unchecked(adjlist):
  298.     G = Graph()
  300.     for row in adjlist:
  301.         node = row[0]
  302.         neighbors = row[1:]
  303.         G[node] = neighbors
  305.     return G

至于 skipgram, 大家可以直接用 gensim 工具即可.

from gensim.models import Word2Vec
from gensim.models.word2vec import Vocab

logger = logging.getLogger("deepwalk")

class Skipgram(Word2Vec):
    """A subclass to allow more customization of the Word2Vec internals."""

    def __init__(self, vocabulary_counts=None, **kwargs):

        self.vocabulary_counts = None

        kwargs["min_count"] = kwargs.get("min_count", 0)
        kwargs["workers"] = kwargs.get("workers", cpu_count())
        kwargs["size"] = kwargs.get("size", 128)
        kwargs["sentences"] = kwargs.get("sentences", None)
        kwargs["window"] = kwargs.get("window", 10)
        kwargs["sg"] = 1
        kwargs["hs"] = 1

        if vocabulary_counts != None:
          self.vocabulary_counts = vocabulary_counts

        super(Skipgram, self).__init__(**kwargs)

应用

在推荐场景中, 无论是推荐商品还是广告, 用户和 item 其实都可以通过点击 / 转化 / 购买等行为构建二部图, 在此二部图中进行随机游走, 学习每个节点的向量, 在特定场景, 缺乏特征和标签的情况下, 可以通过 user2user 或者 item2iterm 的方式, 很好的泛化到其他的标签. GNN 提取的向量也可以用于下游双塔召回模型或者排序模型. 如果有社交网络, 通过挖掘人与人直接的关系提取特征, 供下游任务也是个不错的选择. 当然大家也可以尝试在一些推荐比赛中用于丰富特征.

大有可为的GNN：DeepWalk - 图6

听说 GNN 大有可为, 从这篇开始学以致用mp.weixin.qq.com大有可为的GNN：DeepWalk - 图7

https://zhuanlan.zhihu.com/p/389218052