文章目录

ProblemsQuestion 1: Node similarity calculationQuestion 2: Node embedding and prediction Question 1一.实验内容二．算法原理三．实验步骤四．实验结果五．总结 Question 2一．实验摘要二．模型和算法描述三．实验步骤1.数据预处理2.模型描述3.代码摘要 四．实验结果五．总结 参考文献

Problems

Question 1: Node similarity calculation

Firstly, use some heuristic methods to calculate the similarity between nodes in the network such as the shortest distance, the common neighbors. Secondly, predict the missing links using node pair similarity score.

Question 2: Node embedding and prediction

Feature extraction Recently, methods which use the representation of network nodes in vector space have gained traction from the research community. We first learn features of each node in the network. Then we can train a classifier such as SVM, KNN to predict the missing links. We can construct the feature of each node based on the network structure such as the adjacency matrix.Link prediction After obtaining the low-dimensional vector of each node, we can train a classifier (SVM, KNN; sklearn package in python) to predict whether a link in the test set exists or not. The evaluation metrics is AUC value.

Question 1

一.实验内容

首先阅读给定的代码，学习代码组织结构。然后设计一个衡量节点相似度的指标，对节点和节点之间边的存在性及其存在与否的可能性进行预测。在代码中自行补充node_distance和其他相关函数。将预测结果绘制成ROC曲线并计算曲线下的面积。之后对算法进行改进，观察不同启发式函数对预测结果的影响

二．算法原理

第一问我最终尝试了两种方法，第一种是以两节点相同邻居为指标进行判断，第二种是以两个节点之间的距离为指标，下边分别进行说明：

考察相同邻居 算法描述： 输入：计算图，需要进行预测的节点A,B 输出：两个节点之间关系存在与否的预测值$\alpha (0\le \alpha \le 1)$ 算法： 计算节点A邻居节点集合U1 计算节点B邻居节点集合U2 计算集合U0 = U1∩U2 计算输出值：$\alpha =\frac{|U_0|}{|U_1|+|U_2|-|U_0|}$，输出

如上图，考察两个节点A,B之间有联系的可能性大小。从突中容易求得$|U_A|=9,|U_B|=7,|U_A\bigcap U_B|=3$。所以继续进行计算得$\alpha =3/13=0.231$即为输出值

考察节点的距离 算法描述： 输入：计算图，需要进行预测的节点A,B 输出：节点之间存在关系可能性的相对指标β 算法过程: 计算无向图中节点A到节点B最近的距离dis，路径权值统一按照1进行计算 输出$\beta =1/dis$ 如上图，如果计算A,B之间的相关性: 可知最短路径有：$A->C->B,A->D->B,A->E->B$ 则输出值为$\beta =0.5$

三．实验步骤

第一问是不用训练model的，所以在简单阅读了代码之后，就开始考虑如何去预测了。根据上边的两个判断依据喝算法过程，我简单的编写了下边的两个函数:

def distance(graph,origin): dis = nx.shortest_path_length(graph,origin[0],origin[1]) return 1/dis def neighbors(graph,origin): neigh1 = set(graph.neighbors(origin[0])) neigh2 = set(graph.neighbors(origin[1])) prob = len(neigh1 & neigh2)/(len(neigh1)+len(neigh2)) return prob

其中distance函数是用距离来作为衡量依据的，后边neighbors是以相同邻居数量作为衡量依据。分别将这两个函数应用于下边的位置，运行后就可以获得结果

四．实验结果

使用distance作为依据：

使用neighbors作为依据：

五．总结

第一问比较简单，只涉及到寥寥数行的代码编写，但是对整个工程和问题的了解非常重要。在这一问我主要尝试了两种方法。其中用neighbor作为依据效果不是很好，毕竟有联系的节点不一定都要share很多的neighbors。下边就到了最有意思的Q2。

Question 2

一．实验摘要

本实验旨在根据已有的计算图，预测两个节点关系的存在性以及存在的可能性大小。 由于这个是预测图这个特殊的数据结构的未知边，所以需要考虑一种有效的方法来提取图中有效的特征信息。目前，CNN在图像处理领域现在有了非常成熟的应用，CNN这种“见微知著”的思想方法对提取图像中事物的特征非常有效，以至于让我们不得不去思考是否能在“图”中采取类似的方法来进行特征的提取，然后用其他方法利用这些特征去做更复杂的应用。 总的来说在这个实验中，我参考[1]建立了图卷积神经网络（GCN）来进行图节点之间特征的提取，然后建立了一个解码矩阵，经过两个特征提取的结果就可以计算两个节点联系存在的可能性。首先我对数据进行了简要的预处理，将数据集划分为train,validation和test三部分，之后定义了节点的编码和卷积层的矩阵运算，包括两层卷积层和相应的两个激活函数。之后为了将我们提取出的特征值向量转化为相应存在关系的概率，本模型又建立了一个解码器，对输入的两个特征值向量进行处理，输出一个概率值。模型建立完毕之后，利用划分后的数据集train对所有test集合中的各组节点输入模型即可得到我们需要的预测值。

二．模型和算法描述

对于一个图首先可以如下定义： $$G=(V,E),v_i,v_j\in V,e\in E,e=(v_i,v_j)$$ 其中V为所有节点的集合，E为所有边的集合。为了提取出图中节点的位置特征，我设计了两层图卷积神经网络来进行训练，传播函数为下方的公式(1)： $$h_i^{(}k+1)=\Theta (\sum _{j\in N^i}{c}^{ij}{W}^{(k)}{h}_j^k+c_r^i{h}_i^{(k)})$$ 公式(1)中 $h_i^{(k)}\in R^{d(k)}$ ,是节点i在第k层的特征向量， $d(k)$为第k层特征向量的维度描述。式中 $c^{i}j=\frac{1}{\sqrt{|N^i|||N^j}}$,$c^i=\frac{1}{|N^i|}$ ，这两个参数为标准化常数，采用这两个常数是为了方便权值共享，并增加模型的鲁棒性。其中$N^i$代表第i个节点的邻居集合。$\Theta (x)$是层与层之间的一个激活函数（这个模型用的是Relu) 对于每一个节点，神经元的初始输入是一个比较关键的问题，在这里我不加区分的使用了独热码对各个节点进行编号，如下公式（2），可以得到一个特征值向量的稀疏矩阵，每一行代表特定节点的特征值向量。 $$H_i^{(0)}=\left\{\begin{array}{c}{h}_0^{(0)}\\ h_1^{(0)}\\ h_2^{(0)}\\ \dots \\ h_n^{(0)}\end{array}\right\}=\left\{\begin{array}{ccccc}1& 0& \cdots & 0& 0\\ 0& 1& 0& 0& 0\\ 0& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \dots & 1& 0\\ 0& 0& 0& 0& 1\end{array}\right\}$$ 起初，训练过程中这一组特征值向量被直接输入到GCN中进行计算。由于输入节点数目太过于庞大，矩阵计算效率底下，所以随即采用稀疏矩阵进行运算，大大加快了训练进程。 通过公式(1)我们在每一个节点上建立不同的网络，同时在同一层上共享同一套关系矩阵$W^{(k)}$，结合下边要叙述的解码器，就可以构成完整的模型。 解码器模型如下式（3）： $$s(v_i,v_j)=v_i^T{M}_r{v}_j$$ 公式(3)$s(v_i,v_j)$中代表节点$v_i,v_j$之间存在联系的概率的相对值，$v_i,v_j$为公式（1）的输出，即经过两层GCN提取之后节点的位置特征向量。后边的关系矩阵$M_r$是后续计算$s(v_i,v_j)$的一个重要参数矩阵。在训练之后我们就可以输入$v_i,v_j$，从而得到关系存在与否的估计值。 基于公式（1）和公式（3），我们的模型基本上就建立完毕。后续就是训练和调参的过程。 本模型采用的损失函数如下： $$J(i,j)=-log{p}^{ij}-log(1-p^{in})$$ $$e^{in}\notin E_{pos},i,j,n\in V$$ 公式4（交叉熵损失函数）衡量了当前模型对节点和节点(预先知道的正样本)的预测情况，并同时综合了随机选取的一个负样本的预测情况，如果预测情况较好则最终输出的$J(i,j)$值就会比小。 公式（4）中$pij$ 代表节点i和节点j之间存在联系的可能性，计算如下： $$p^{ij}=probability((v_i,v_j)\in E_{pos})=\sigma ((s(v_i,v_j)))$$ 计算出$s(v_i,v_j)$本模型并没有直接将其作为$p^{ij}$来使用，而是在期间通过了一个$sigmoid$函数来将变量$p^{ij}$映射在区间$(0,1)$，方便我们后续的训练和计算。 综上，我们训练过程的损失函数可以描述为： $$J_{totalloss}=\sum _{(v_i,v_j)\in E}J(i,j)$$ 上述即为此模型整体的数学描述，接下来我们将从更细化的角度对这个模型建立、训练过程及其代码实现进行详细的讨论。

三．实验步骤

1.数据预处理

a)数据分割 本身可用的数据集只被划分为了训练集和测试集（包含各自的正负样本）。但是为了方便在实验过程中观察训练集训练情况，我将训练集中取出了5%的样本来作为验证集，在模型训练指定轮数后打印出验证集的测试结果。

b)训练批次的划分(batch) 合理的batch数量的划分在数据集划分上也比较重要，如果batch划分的太小，则算法收敛速度可能会变得很慢，当batch变大达到相同精度需要的epochs数量更多，所以我们需要选择一个合适的batch来使训练达到时间上的最优。由于最终收敛精度会陷入不同的局部极值，因此Batch_size增大到某些时候，可以达到最终收敛精度上的最优。 c)节点特征值向量建立难题 最初上手这个数据集时，想当然的以为节点编号是从1~n顺序进行编号的，直到出现了Overflow才恍然大悟。为此我在loaddata.py的load_training_graph()函数中引入了节点值得字典，为每一个节点建立一个唯一得索引值，使得每一个节点可以被唯一地标注和引用。

2.模型描述

a) 节点位置特征向量 如公式（1）所示，在GCN中，为了获取到每一个节点的与周围邻居节点的特征信息，我们有必要对单个节点的特征向量作为输入参数来进行单独的计算。而每一个节点，他们有着不同的邻居节点（数目，属性等），所以说不同的节点定义出的网络传播结构是不同的。在这个模型主要采用了权值共享、标准化等方法，并在层与层之间添加了一个激活函数。这些部分在上边算法描述中已经说的比较详尽了，在此不再赘述

3.代码摘要

a)源文件 大体地组织结构如上图，下边对各个文件的作用作简要介绍：

loaddata.py 这个文件里边包含两个函数： load_training_graph函数的作用是利用训练集数据建立计算图，并建立节点的索引字典，返回计算图、索引字典和图相关参数信息。load_data_list函数主要是用来读取测试集数据，输出数据的元组列表。

minibatch.py 这个文件主要定义了一个class:EdgeMinibatchIterator,在这个类中，为了清楚的说明这个类的作用，我们先来看这个类的调用位置： 上边显示的函数next_minibatch_feed_dict是用来获取minibatch中数据来feed我们的placeholder的。在这个类的__init__()函数中我们可以看到对函数training_edges()的调用，这个函数是这个类的私有函数，在类初始化的时候被调用，用来读取数据并划分数据集，主要过程如下： 此外，这个类还有一些辅助性的函数，不再赘述

layer.py 这个文件定义了如下类： 其中最关键的就是GraphConcolutionSparseMulti和GraphConvolutionMulti。前者是用来第一层卷积计算的，由于输入的初始位置特征向量是非常稀疏的，调用这个类的_call()函数时采用的是tf.sparse_tensor_dense_matmul()，提高了模型训练的效率。后者主要用于第二层卷积层的运算。

model.py 这个文件主要定义了如下两个父子类： 其中是最重要的，在这个类用了“算法原理”部分的数学模型，形成了一个完整的计算图。

main.py 主函数首先调用中的函数读取图和训练、测试数据，并对数据相关的参数、格式进行计算。再实例化数据划分器、数据模型和优化器。接着开始训练模型，模型训练过程中会打印验证集的情况，训练结束后将测试集输入模型，根据测试结果画出ROC曲线并计算出AUC的值。 b)过程摘要 A simple demo:

在上述过程的基础上,代码的运行就水到渠成了,上图是一个简单的demo,只简单的训练了30个epochs,可以看到训练过程中输出了验证集的测试结果.并在训练最后给出了ROC曲线

四．实验结果

经过训练，我们的模型AUC达到了0.9509，还算比较满意的一个效果了

五．总结

这次的实验做的还是蛮艰难的,遇到了很多问题，首先对python中networkx,scipy,tensorflow等等这些包之前应用的很少,所以刚开始在阅读这个decagon的代码的时候难度比较大。但是花了很大的功夫,到后期还是克服了,读懂了代码的核心部分,对外围部分也有了大体的了解。阅读了这种高端的代码,感觉自己都得到了升华哈哈，整个阅读代码的过程感觉就是兵来将挡水来土掩，当然并不顺利。 这次实验是第一次完整的一个AI的工程，经过这一次，我对AI研究的数据准备，数学建模，代码编写以及调参优化过程有了更深的了解，可以说是开了一个好头吧。 这次实验的整体思路是在阅读了一篇关于利用GCN来Model polypharmacy side effects的论文,在将这篇论文中的模型转变为本次实验的模型的过程中,我体会到了站到巨人肩上的重要性。在此前的学习中,总是喜欢埋头苦干(对自己太过于自信),全部过程都交给自己.这样会造成两个严重的后果,一个就是和其他的思维交流过少,导致容易走偏方向而全然不知,另一个就是并不是所有东西都可以完全由自己实现的,”不要重复造轮子”才是万年不变的真理(当然只是借鉴,还要有自己的创新)。 机器学习算法之间好多思想都是想通的,例如这次实验中的CNN,GCN,这两个看上去关系不是很大,但是深层次的思想都是非常类似的。然而想要创新这些思路还是很有挑战性的,需要非常敏锐的观察力和不怕失败的先驱精神,这对我今后的学习和工作也是有启发意义的吧。

参考文献

[1] Modeling Polypharmacy Side Effects with Graph Convolutional Networks Marinka Zitnik , Monica Agrawal and Jure Leskovec. Department of Computer Science, Stanford University, Stanford, CA, USA. Chan Zuckerberg Biohub, San Francisco, CA, USA [2]《DEEP LEARNING》2017 lan Goodfelllow, Yoshua Bengio