·551· 常新功，等：基于图卷积集成的网络表示学习 第3期 的无监督性，设计评价指标2网评价网络表示学习 10)output tanh(X3) 的好坏。对于节点：和y之间的边即一个正例， 11)loss(output) 由一对节点(v。)表示，一个正例对应采样K条 12)Backpropagation(loss) 负边，即采样K个点(1,2，…，)，其中i,j(1,K), 13)更新output,.⊙ 构成负例集合{(y,n),(,2),…,(v,n}。 14)end for 衡量一对节点的相似度可计算它们网络表示 15)返▣output 的内积，正例(，)的相似度s=·z,负例的相似 训练阶段进行模型计算和损失计算，所以训 度5p=z2,p=(1,2,…,K),相似值越大越好，所 练阶段的时间复杂度是O(EHTF+dKED,测试阶 以将sp的值由大到小排序，记录s插入{sp}的索 段的时间复杂度是O(KED),其中H是特征输入维 引ranking,索引是从0开始的，衡量指标需要的 数384，T为中间层维数256，F为输出层维数128， 是排名位置，所以令ranking-=ranking+l,ranking越 数据边的数量是E,测试数据边的数量是E。综 小说明网络表示学习的嵌入越有效。 上所述，总体时间复杂度是O(EHTF+dKE)。 上文针对一个正例计算得到了一个ranking,. 3 实验和结果分析 对于整个网络设计指标如表1所示。 表1评价指标 在6个数据集上分别对比DeepWalk、Node Table 1 Evaluating indicator 2Vec、Line这3个经典的网络表示学习方法和 评价指标 含义 stacking集成后的实验效果，验证GCN作为stack-. ing集成次级学习器的有效性。实验环境为：Win- MRR 所有ranking的倒数的平均值 dows10操作系统，Intel i7-67002.6 GHz CPU,nvidia Hit@1/3/10 ranking在负例相似度排名的前1/3/10个 GeForce GTX950MGPU,8GB内存。编写Py- 评价数据边的数量为E1,时间复杂度为 thon和Pytorch实现。 OKED。 3.1 实验设定 2.5算法描述 1)数据集 基于图卷积集成的网络表示主要包括3个步骤 实验使用6个真实数据集，即Cora、Citeseer、 首先得到初级学习器的网络表示，然后用stack- Pubmed、Wiki-Vote、P2P.Gnutella05和Email-En- ing集成，其中次级学习器选用GCN。对于网络 ron,详细信息见表2。Cora是引文网络，由机器 表示学习的无监督性在GCN模型中设计了损失 学习论文组成，每个节点代表一篇论文，论文根 函数，也设计了其测试指标，相关算法如算法1 据论文的主题分为7类，边代表论文间的引用关 所示。 系。Citeseer也是引文网络，是从Citeseer数字论 算法1基于图卷积集成的网络表示 文图书馆中选取的一部分论文，该网络被分为 输入网络G=(V,E),窗口大小w,节点表示 6类，边代表论文间的引用关系。Pubmed数据集 向量维度d,每个节点随机游走次数y,随机游走 包括来自Pubmed数据库的关于糖尿病的科学出 序列长度t,节点个数size,邻近性阶数order,超参 版物，被分为3类。Wiki-Vote是社交网络，数据 集包含从Wikipedia创建到2008年1月的所有 数p控制节点随机游走回溯概率，超参数q控制 Wikipedia投票数据。网络中的节点表示Wikipe- BFS和DFS,数据集文件datafile,.训练轮数epoch,. dia用户，从节点i到节点j的定向边表示用户i给 GCN参数O; 用户j的投票。P2P-Gnutella05是因特网点对点网 输出网络表示output。. 络，数据集是从2002年8月开始的Gnutella点对 1)z=DeepWalk(G,w,y,t,d) 点文件共享网络的一系列快照，共收集了9个 2)z2=Node2Vec(G,w,y,t,d.p,q) Gnutella网络快照。节点表示Gnutella网络拓扑 3)z3=Line(size,d,order) 中的主机，边表示Gnutella主机之间的连接。 4)X=Concatenate(z1,Z2,Z3) Email-Enron是安然公司管理人员的电子邮件通 5)A=load date(datafile) 信网络，覆盖了大约50万封电子邮件数据集中的 6)for each epoch do: 所有电子邮件通信，这些数据最初是由联邦能源 7)XI GraphConvolution(X,A, 管理委员会在调查期间公布在网上的，网络的节 8)X2 ReLU(X) 点是电子邮件地址，边表示电子邮件地址之间的 9)X3 GraphConvolution(X2,A,) 通信。(n1,n2,··· ,nk) i, j < (1,K) {(vi ,n1),(vi ,n2),··· ,(vi ,nk)} 的无监督性，设计评价指标[24] 评价网络表示学习 的好坏。对于节点 vi 和 vj 之间的边即一个正例， 由一对节点 (vi , vj ) 表示，一个正例对应采样 K 条 负边，即采样 K 个点 ，其中 ， 构成负例集合 。 (vi , vj) s = zi · z T j sp = zi · z T np p = (1,2,··· ,K) 衡量一对节点的相似度可计算它们网络表示 的内积，正例 的相似度 ，负例的相似 度 ， ，相似值越大越好，所 以将 sp 的值由大到小排序，记录 s 插入{sp}的索 引 ranking，索引是从 0 开始的，衡量指标需要的 是排名位置，所以令 ranking=ranking+1，ranking 越 小说明网络表示学习的嵌入越有效。 上文针对一个正例计算得到了一个 ranking， 对于整个网络设计指标如表 1 所示。 表 1 评价指标 Table 1 Evaluating indicator 评价指标 含义 MRR 所有ranking的倒数的平均值 Hit@1/3/10 ranking在负例相似度排名的前1/3/10个 |E ’ | O(K|E ’ |) 评价数据边的数量为 ，时间复杂度为 。 2.5 算法描述 基于图卷积集成的网络表示主要包括 3 个步骤， 首先得到初级学习器的网络表示，然后用 stack￾ing 集成，其中次级学习器选用 GCN。对于网络 表示学习的无监督性在 GCN 模型中设计了损失 函数，也设计了其测试指标，相关算法如算法 1 所示。 算法 1 基于图卷积集成的网络表示 γ Θ 输入 网络 G=(V,E)，窗口大小 w，节点表示 向量维度 d，每个节点随机游走次数 ，随机游走 序列长度 t，节点个数 size，邻近性阶数 order，超参 数 p 控制节点随机游走回溯概率，超参数 q 控制 BFS 和 DFS，数据集文件 datafile，训练轮数 epoch， GCN 参数 ； 输出 网络表示 output。 1) z1 = DeepWalk(G,w, γ,t,d) 2) z2 = Node2Vec(G,w, γ,t,d, p,q) 3) z3 = Line(size,d,order) 4) X = Concatenate(z1,z2,z3) 5) Aˆ = load_date(datafile) 6) for each epoch do: X1 = GraphConvolution1(X, Aˆ 7) ,Θ) 8) X2 = ReLU(X1) X3 = GraphConvolution2(X2, Aˆ 9) ,Θ) 10) output = tanh(X3) 11) loss(output) 12) Backpropagation(loss) 13) 更新 output,Θ 14) end for 15) 返回 output O(|E|HT F +dK|E|) O(K|E ′ |) |E| |E ′ | O(|E|HT F +dK|E|) 训练阶段进行模型计算和损失计算，所以训 练阶段的时间复杂度是 ，测试阶 段的时间复杂度是 ，其中 H 是特征输入维 数 384，T 为中间层维数 256，F 为输出层维数 128， 数据边的数量是 ，测试数据边的数量是 。综 上所述，总体时间复杂度是 。 3 实验和结果分析 在 6 个数据集上分别对比 DeepWalk、Node 2Vec、Line 这 3 个经典的网络表示学习方法和 stacking 集成后的实验效果，验证 GCN 作为 stack￾ing 集成次级学习器的有效性。实验环境为：Win￾dows10 操作系统，Intel i7-6700 2.6 GHz CPU，nvidia GeForce GTX 950M GPU，8 GB 内存。编写 Py￾thon 和 Pytorch 实现。 3.1 实验设定 1) 数据集 实验使用 6 个真实数据集，即 Cora、Citeseer、 Pubmed、Wiki-Vote、P2P-Gnutella05 和 Email-En￾ron，详细信息见表 2。Cora 是引文网络，由机器 学习论文组成，每个节点代表一篇论文，论文根 据论文的主题分为 7 类，边代表论文间的引用关 系。Citeseer 也是引文网络，是从 Citeseer 数字论 文图书馆中选取的一部分论文，该网络被分为 6 类，边代表论文间的引用关系。Pubmed 数据集 包括来自 Pubmed 数据库的关于糖尿病的科学出 版物，被分为 3 类。Wiki-Vote 是社交网络，数据 集包含从 Wikipedia 创建到 2008 年 1 月的所有 Wikipedia 投票数据。网络中的节点表示 Wikipe￾dia 用户，从节点 i 到节点 j 的定向边表示用户 i 给 用户 j 的投票。P2P-Gnutella05 是因特网点对点网 络，数据集是从 2002 年 8 月开始的 Gnutella 点对 点文件共享网络的一系列快照，共收集了 9 个 Gnutella 网络快照。节点表示 Gnutella 网络拓扑 中的主机，边表示 Gnutella 主机之间的连接。 Email-Enron 是安然公司管理人员的电子邮件通 信网络，覆盖了大约 50 万封电子邮件数据集中的 所有电子邮件通信，这些数据最初是由联邦能源 管理委员会在调查期间公布在网上的，网络的节 点是电子邮件地址，边表示电子邮件地址之间的 通信。 ·551· 常新功，等：基于图卷积集成的网络表示学习 第 3 期