一种基于图卷积网络的图可视化方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN109753589A(43)申请公布日2019.05.14(21)申请号201811432008.X(22)申请日2018.11.28(71)申请人中国科学院信息工程研究所地址100093北京市海淀区闵庄路甲89号(72)发明人朱梓豪周川曹亚男张鹏刘萍郭莉(74)专利代理机构北京君尚知识产权代理事务所(普通合伙)11200代理人司立彬(51)Int.Cl.G06F16/901(2019.01)G06F16/904(2019.01)权利要求书2页说明书8页附图1页(54)发明名称一种基于图卷积网络的图可视化方法(57)摘要本发明公开了一种基于图卷积网络的图可视化方法，其步骤包括：1)对于目标领域的网络G＝(V，E)，将网络G中的节点嵌入到一个低维欧式空间中，得到网络G的低维嵌入向量；所述低维嵌入向量包含网络G中节点的特征信息和网络G的拓扑结构信息；其中，V是节点集合，E是边集合；2)将所述低维嵌入向量构造成一张K近邻图，即KNN图；3)基于概率模型将所述KNN图在二维空间中绘制出来。本发明学习到的嵌入向量同时保留了节点的结构信息和特征信息，可以对可视化结果进行粒度化调整。CN109753589ACN109753589A权利要求书1/2页1.一种基于图卷积网络的图可视化方法，其步骤包括：1)对于目标领域的网络G＝(V,E)，将网络G中的节点嵌入到一个低维欧式空间中，得到网络G的低维嵌入向量；所述低维嵌入向量包含网络G中节点的特征信息和网络G的拓扑结构信息；其中，V是节点集合，E是边集合；2)将所述低维嵌入向量构造成一张K近邻图，即KNN图；3)基于概率模型将所述KNN图在二维空间中绘制出来。2.如权利要求1所述的方法，其特征在于，设置一粒度参数，基于PageRank算法计算每个所述节点的重要性评分，所述粒度参数的不同取值分别对应不同的节点重要性评分；当调整粒度参数大小时展示对应不同重要程度的节点。3.如权利要求2所述的方法，其特征在于，根据PageRank网页排序算法计算每个节点的重要性评分。4.如权利要求1所述的方法，其特征在于，节点vi的重要性评分其中，是所有对vi有出链的节点集合，L(vj)是节点vj的出链数目，N是节点总数，α为一设定系数，0<α<1。5.如权利要求1所述的方法，其特征在于，将网络G中的节点嵌入到一个低维欧式空间中，得到网络G的低维嵌入向量的方法为：1)设置一参数k代表神经网络的卷积层数或者搜索深度、代表在神经网络第k层时节点v的向量表示,v∈V；在k＝0，将网络G中节点v的特征向量赋值给2)在神经网络的后续每一层卷积层都重复如下步骤：首先对于每个节点v∈V，将v的邻接节点的上一层向量的表示汇聚成一个单独的向量其中，N(v)表示对节点v的邻接节点的采样，然后将节点v的上一层的向量表示与邻域节点聚合成的向量拼接在一起，得到向量3)将向量传递给一个全连接层进行计算其中，Wk为全连接层对应的权重矩阵；4)将作用在激活函数σ(·)上，得到节点v在第k层的嵌入向量5)对做归一化处理，得到节点v在第k层或第k个搜索深度迭代后的低维嵌入向量。6.如权利要求5所述的方法，其特征在于，利用对节点的低维嵌入向量进行调整；其中，zu是目标节点u的调整后的低维嵌入向量，v是在以u为起点的固定长度的随机游走序列中出现的节点，g(·)是Sigmoid函数，Pn是v的负采样分布，Q代表负采样的个数，vn表示节点v的负采样节点，是vn的低维嵌入向量。7.如权利要求1所述的方法，其特征在于，基于概率模型将所述KNN图在二维空间中绘制出来的方法为：首先确定KNN图中节点之间的权重wij；然后任选一节点作为中心点，将中心点和其邻居节点构成一个正样本，而中心点与非邻居节点构成负样本，则两个节点在KNN2CN109753589A权利要求书2/2页图中有边的概率为：设正样本集合为E，负样本集合为整个网络G的优化目标为γ是统一为负样本边设定的权值，jk是根据噪声分布Pn(j)选取的节点j的负样本，eij＝1代表节点i和节点j之间有边，代表节点i和节点jk之间有边；然后使用随机梯度下降算法训练优化目标为O的网络G，得到节点在二维空间中的坐标并绘制。8.如权利要求7所述的方法，其特征在于，确定KNN图中节点之间的权重的方法为：设在高维空间中的两个数据点为xi和xj，p(j|i)表示xi选择xj作为它的邻近点的条件概率，若xj越靠近xi，则p(j|i)越大，反之则越小；KNN图中vi和vj的权重为：其中，σi表示以xi为中心点的高斯分布的方差。9.如权利要求1所述的方法，其特征在于，使用随机投影树将所述低维嵌入向量映射成一张KNN图。3CN109753589A说明书1/8页一种基于