CN109767008A - 一种基于元模式的高度异构网络多态特征学习方法 - Google Patents
一种基于元模式的高度异构网络多态特征学习方法 Download PDFInfo
- Publication number
- CN109767008A CN109767008A CN201910017697.6A CN201910017697A CN109767008A CN 109767008 A CN109767008 A CN 109767008A CN 201910017697 A CN201910017697 A CN 201910017697A CN 109767008 A CN109767008 A CN 109767008A
- Authority
- CN
- China
- Prior art keywords
- node
- meta
- pattern
- network
- learning method
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 26
- 238000005295 random walk Methods 0.000 claims abstract description 20
- 230000006870 function Effects 0.000 claims abstract description 17
- 239000011159 matrix material Substances 0.000 claims abstract description 12
- 230000007704 transition Effects 0.000 claims description 16
- 230000004927 fusion Effects 0.000 claims description 10
- 238000005070 sampling Methods 0.000 claims description 8
- 238000013507 mapping Methods 0.000 claims description 6
- 239000000284 extract Substances 0.000 claims description 5
- 239000013598 vector Substances 0.000 claims description 4
- 230000011218 segmentation Effects 0.000 claims description 3
- 238000013528 artificial neural network Methods 0.000 claims description 2
- 238000007477 logistic regression Methods 0.000 claims description 2
- 238000012706 support-vector machine Methods 0.000 claims description 2
- 238000000605 extraction Methods 0.000 abstract description 3
- 238000003780 insertion Methods 0.000 abstract 3
- 230000037431 insertion Effects 0.000 abstract 3
- 238000005516 engineering process Methods 0.000 description 3
- 230000014509 gene expression Effects 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000013075 data extraction Methods 0.000 description 1
- 238000007418 data mining Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000018109 developmental process Effects 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- 230000001537 neural effect Effects 0.000 description 1
- 238000012545 processing Methods 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
本发明公开了一种基于元模式的高度异构网络多态特征学习方法，基于原网络中相似节点在嵌入空间中也相似的原则，提取方法包括以下步骤。首先，采用基于元模式的随机游走来提取异构网络中的随机路径。然后，利用滑窗提取路径中特定目标的相似节点对。最后，根据网络影响力矩阵和加权skip‑gram模型来学习异构节点的多态嵌入表达。得到的节点嵌入可以进一步送入有监督学习模型中，实现对节点分类等任务的预测。本发明实现了从异构网络连接中学习节点特征的功能，具有计算简单、时间复杂度低、嵌入表达多样效果好的技术效果。
Description
技术领域
本发明属于网络技术领域，尤其涉及一种基于元模式的异构网络多态特征学习方法。
背景技术
随着互联网的快速发展和各类社交网站的相继出现，网络科学逐渐成为一门备受关注的学科，在大数据研究中发挥着重要作用。生活中的网络随处可见，例如计算机领域中的万维网，能源领域的电力网络，交通领域的航空网络，社交领域的在线交友网络等等。当人们试图去解决如节点分类、链路预测、聚类等网络传统问题时，迫切需要关于网络节点、连边、社团或其他网络元素的特征。而网络嵌入算法就提供了一种从网络的关系和属性中自动的提取特征表达的方法。异构网络是一种包含了多种类型的节点或者连边网络的总称。如何从异构网络中提取特征成为一个急需解决的问题。
目前网络嵌入技术主要可以根据数据提取方式分为三类：节点到邻居，节点到节点，随机游走。第一类方法([文献1])假设每个节点的嵌入是其邻居节点的线性组合。第二类方法([文献2])试图让两个节点嵌入的距离更近，如果他们之间的权重更大。第三类方法([文献3、4])通过随机游走提取相似节点对，然后通过skip-gram算法学习节点嵌入。然而，这些方法在高度异构网络中的效率和表达能力有限，迫切需要一种灵活的可以对高度异构网络进行特征提取的方法。
[文献1].S.T.Roweis,Nonlinear dimensionality reduction by lo callylinear emb edding,Science 290(5500)(2000)2323{2326.doi:10.1126/science.290.5500.2323
[文献2]M.Belkin,P.Niyogi,Laplacian eigenmaps and sp ectral tech-250niques for emb edding and clustering,in:Advances in neural in-formationpro cessing systems,2002,pp.585{591}
[文献3]A.Grover,J.Leskovec,no de2vec:Scalable feature learning fornetworks,in:Pro ceedings of the 22nd ACM SIGKDD Interna-tional Conference onKnowledge Discovery and Data Mining,KDD'16,ACM,2016,pp.855{864.doi:10.1145/2939672.275 2939754
[文献4]Y.Dong,N.V.Chawla,A.Swami,metapath2vec:Scalable rep-resentation learning for heterogeneous networks,in:Pro ceed-ings of the 23rdACM SIGKDD International Conference on Knowledge Discovery and Data Mining-KDD'17,ACM,2017,280pp.135{144.doi:10.1145/3097983.3098036
发明内容
针对现有技术存在的不足，本发明提出了一种基于元模式的异构网络多态特征学习方法。
本发明所采用的技术方案是：一种基于元模式的高度异构网络多态特征学习方法，其特征在于，包括以下步骤：
步骤1：给定的异构网络G＝{V,E,φv,φe}，其中V表示节点集合，E表示边集合，φv是从V到Tv的节点类型映射函数，φe是从E到Te的边类型映射函数，其中Tv和Te分别是节点类型和边类型的集合，高度异构性要求|Tv|+|Te|＞＞1。根据异构网络G初始化采样元模式S，初始化影响力权重矩阵α；
步骤2：从异构网络每个节点出发，利用基于元模式的随机游走获取k条随机游走路径；
步骤3：利用长度为l的滑动窗在随机游走路径中采样，所有窗口中心节点和窗口内其余节点均分别作为相似节点对提出，所有窗口内的节点都被认为是相似的；
步骤4：根据影响力权重矩阵α和相似节点对snp，利用加权skip-gram算法优化以下目标函数，该目标函数减少相似节点对之间的距离同时增加其余节点对之间的距离，最终求得网络节点特征X∈R|V|*d，其中|V|为异构网络节点数量，d为网络节点特征的维度，满足d《|V|。
其中，up为相似节点对中的一个节点，un为其余节点对中的一个节点，t(up)和t(v)分别表示节点up和节点v的类型，neg表示通过负采样得到的其余节点对，表示从节点类型t(up)到t(v)的影响力权重，p(u|v)表示从节点u观测到节点v的概率；
步骤5：将节点嵌入通入后续有监督分类器中，解决实际任务。
与现有网络嵌入技术与系统相比，本发明具有以下优点和有益效果：
1)与现有技术相比，本发明提出了一个新的面向异构网络的基于元模式的相似节点提取技术；
2)与现有技术相比，本发明通过设置影响力矩阵，可以得到多种异构网络特征表达，全面提取异构网络节点间的相似和差异性。
附图说明
图1：为本发明实施例的流程图；
图2：为本发明实施例中元模式示意图。
具体实施方式
为了便于本领域普通技术人员理解和实施本发明，下面结合附图对本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明和解释本发明，并不用于限定本发明。
请见图1，本发明提供的一种基于元模式的高度异构网络多态特征学习方法，包括以下步骤：
步骤1：给定的异构网络G＝{V,E,φv,φe}，其中V表示节点集合，E表示边集合，φv是从V到Tv的节点类型映射函数，φe是从E到Te的边类型映射函数，其中Tv和Te分别是节点类型和边类型的集合，高度异构性要求|Tv|+|Te|》1。根据异构网络G初始化采样元模式S，初始化影响力权重矩阵α；
请见图2，本实施例的元模式S是网络模式的子网络，规定每个节点的加权出度为1。
步骤2：从异构网络每个节点出发，利用基于元模式的随机游走获取k条随机游走路径；
本实施例中，利用基于元模式的随机游走获取k条随机游走路径，具体实现包括以下子步骤：
步骤2.1：查找随机游走路径末端节点在异构网络中的邻居节点集ngb；
假设随机游走路径末端节点为v，首先在元模式中查找节点v的类型所连接的节点和连边类型t，然后在实际网络中查找v满足t的邻居节点集ngb；
步骤2.2：根据元模式计算节点到邻居节点集ngb的转移概率，计算转移概率的具体公式为：
其中，为在元模式S中从节点类型t(vs)到边类型t(est)的转移概率，为元模式S中所有节点类型组成的集合，为元模式中所有从节点类型t(vs)出发的所有边类型组成的集合。
所述转移概率在0～1之间，是元模式中的设定值，在游走中每个节点上的目标转移概率矩阵是非归一化矩阵；
步骤2.3：利用Alias采样方法，从节点转移概率集中采样出目标转移节点；
步骤2.4：将目标转移节点送入游走路径中，然后跳转到步骤2.1，重复多次，直到目标函数中的L小于某一设定的临界值时结束重复。
步骤3：利用长度为l的滑动窗在随机游走路径中采样，所有窗口中心节点和窗口内其余节点均分别作为相似节点对提出，所有窗口内的节点都被认为是相似的；
本实施例中，滑动窗在路径上只提取目标节点对，并非元模式中全部节点对。
步骤4：根据影响力权重矩阵α和相似节点对snp，利用加权skip-gram算法优化以下目标函数，该目标函数减少相似节点对之间的距离同时增加其余节点对之间的距离，最终求得网络节点特征X∈R|V|*d，其中|V|为异构网络节点数量，d为网络节点特征的维度，满足d《|V|。
其中，up为相似节点对中的一个节点，un为其余节点对中的一个节点，t(up)和t(v)分别表示节点up和节点v的类型，neg表示通过负采样得到的其余节点对，表示从节点类型t(up)到t(v)的影响力权重，p(u|v)表示从节点u观测到节点v的概率；
本实施例中，影响力权重大小在0～1，0表示节点类型间影响力较小，分割性较大；1表示节点类型间影响力较大，分割性较小。加权skip-gram算法的目标函数将节点对相似性目标设置为节点对类型的影响力权重。
步骤5：将节点嵌入通入后续有监督分类器中，解决如节点分类、链路预测、聚类等实际任务；
本实施例中，分类器是逻辑回归、支持向量机或神经网络中的一种；
节点分类，是根据部分已知标签的节点，预测其他标签缺失的节点标签，将skip-gram学习的节点特征作为输入特征通入有监督分类器；
链路预测，是将节点对的特征作为输入特征通入有监督分类器，节点对(u,v)的特征f(u,v)可以按照如下方式中的一种进行融合：
(1)均值融合：f(u,v)i＝f(u)i+f(v)i/2；
(2)Hadamard融合：f(u,v)i＝f(u)i*f(v)i；
(3)加权L1融合：f(u,v)i＝|f(u)i-f(v)i|；
(4)加权L2融合：f(u,v)i＝|f(u)i-f(v)i|；
(5)串联融合：f(u,v)i＝concatenate(f(u),f(v))；
其中，u和v分别表示异构网络中的两个节点，f(u)和f(v)分别表示节点u和节点v的两个特征嵌入，f(u)i和f(v)i分别表示这两个特征嵌入向量的第i个元素，concatenate函数表示将两个向量f(u)和f(v)进行串联。
应当理解的是，本说明书未详细阐述的部分均属于现有技术。
应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。
Claims (9)
1.一种基于元模式的高度异构网络多态特征学习方法，其特征在于，包括以下步骤：
步骤1：给定异构网络G＝{V，E，φv，φe}，其中V表示节点集合，E表示边集合，φv是从V到Tv的节点类型映射函数，φe是从E到Te的边类型映射函数，其中Tv和Te分别是节点类型和边类型的集合，高度异构性要求|Tv|+|Te|>>1；根据异构网络G初始化采样元模式S，初始化影响力权重矩阵α；
步骤2：从异构网络每个节点出发，利用基于元模式的随机游走获取k条随机游走路径；
步骤3：利用长度为l的滑动窗在随机游走路径中采样，所有窗口中心节点和窗口内其余节点均分别作为相似节点对提出，所有窗口内的节点都被认为是相似的；
步骤4：根据影响力权重矩阵α和相似节点对snp，利用加权skip-gram算法优化以下目标函数，该目标函数减少相似节点对之间的距离同时增加其余节点对之间的距离，最终求得网络节点特征X∈R|V|*d，其中|V|为异构网络节点数量，d为网络节点特征的维度，满足d<<|V|；
其中，up为相似节点对中的一个节点，un为其余节点对中的一个节点，t(up)和t(v)分别表示节点up和节点v的类型，neg表示通过负采样得到的其余节点对，表示从节点类型t(up)到t(v)的影响力权重，p(u|v)表示从节点u观测到节点v的概率；
步骤5：将节点嵌入通入后续有监督分类器中，解决实际任务。
2.根据权利要求1所述的基于元模式的高度异构网络多态特征学习方法，其特征在于：步骤1中，所述元模式S是网络模式的子网络，规定每个节点的加权出度为1。
3.根据权利要求1所述的基于元模式的高度异构网络多态特征学习方法，其特征在于：步骤2中，所述利用基于元模式的随机游走获取k条随机游走路径，具体实现包括以下子步骤：
步骤2.1：查找随机游走路径末端节点在异构网络中的邻居节点集ngb；
步骤2.2：根据元模式计算节点到邻居节点集ngb的转移概率，计算转移概率的具体公式为：
其中，为在元模式S中从节点类型t(vs)到边类型t(est)的转移概率，为元模式S中所有节点类型组成的集合，为元模式中所有从节点类型t(vs)出发的所有边类型组成的集合；
所述转移概率在0～1之间，是元模式中的设定值，在游走中每个节点上的目标转移概率矩阵是非归一化矩阵；
步骤2.3：利用Alias采样方法，从节点转移概率集中采样出目标转移节点；
步骤2.4：将目标转移节点送入游走路径中，然后跳转到步骤2.1，重复多次，直到目标函数中的L小于某一设定的临界值时结束重复。
4.根据权利要求1所述的基于元模式的高度异构网络多态特征学习方法，其特征在于：步骤3中，滑动窗在路径上只提取目标节点对，并非元模式中全部节点对。
5.根据权利要求1所述的基于元模式的高度异构网络多态特征学习方法，其特征在于：步骤4中，影响力权重大小在0～1，0表示节点类型间影响力较小，分割性较大；1表示节点类型间影响力较大，分割性较小。
6.根据权利要求1所述的基于元模式的高度异构网络多态特征学习方法，其特征在于：步骤4中，所述加权skip-gram算法的目标函数将节点对相似性目标设置为节点对类型的影响力权重。
7.根据权利要求1所述的基于元模式的高度异构网络多态特征学习方法，其特征在于：步骤4中，所述从节点u观测到节点v的概率p(u|v)＝σ(X(u)Tθ(v))，其中X(u)表示节点u的特征嵌入，θ(v)表示节点v的辅助特征嵌入，σ为sigmoid函数。
8.根据权利要求1所述的基于元模式的高度异构网络多态特征学习方法，其特征在于：步骤5中，所述分类器是逻辑回归、支持向量机或神经网络中的一种。
9.根据权利要求1-8任意一项所述的基于元模式的高度异构网络多态特征学习方法，其特征在于：步骤5中，实际任务包括节点分类、链路预测、聚类；
所述节点分类，是根据部分已知标签的节点，预测其他标签缺失的节点标签，将skip-gram学习的节点特征作为输入特征通入有监督分类器；
所述链路预测，是将节点对的特征作为输入特征通入有监督分类器，节点对(u，v)的特征f(u，v)可以按照如下方式中的一种进行融合：
(1)均值融合：f(u，v)i＝f(u)i+f(v)i/2；
(2)Hadamard融合：f(u，v)i＝f(u)i*f(v)i；
(3)加权L1融合：f(u，v)i＝|f(u)i-f(v)i|；
(4)加权L2融合：f(u，v)i＝|f(u)i-f(v)i|；
(5)串联融合：f(u，v)i＝concatenate(f(u)，f(v))；
其中，u和v分别表示异构网络中的两个节点，f(u)和f(v)分别表示节点u和节点v的两个特征嵌入，f(u)i和f(v)i分别表示这两个特征嵌入向量的第i个元素，concatenate函数表示将两个向量f(u)和f(v)进行串联。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910017697.6A CN109767008A (zh) | 2019-01-07 | 2019-01-07 | 一种基于元模式的高度异构网络多态特征学习方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910017697.6A CN109767008A (zh) | 2019-01-07 | 2019-01-07 | 一种基于元模式的高度异构网络多态特征学习方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN109767008A true CN109767008A (zh) | 2019-05-17 |
Family
ID=66453516
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910017697.6A Pending CN109767008A (zh) | 2019-01-07 | 2019-01-07 | 一种基于元模式的高度异构网络多态特征学习方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109767008A (zh) |
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111325326A (zh) * | 2020-02-21 | 2020-06-23 | 北京工业大学 | 一种基于异质网络表示学习的链路预测方法 |
| CN111400560A (zh) * | 2020-03-10 | 2020-07-10 | 支付宝(杭州)信息技术有限公司 | 一种基于异构图神经网络模型进行预测的方法和系统 |
| CN111581488A (zh) * | 2020-05-14 | 2020-08-25 | 上海商汤智能科技有限公司 | 一种数据处理方法及装置、电子设备和存储介质 |
| CN112507244A (zh) * | 2019-09-16 | 2021-03-16 | 腾讯科技（深圳）有限公司 | 社交数据推荐方法、装置、分布式计算集群及存储介质 |
| CN112561688A (zh) * | 2020-12-21 | 2021-03-26 | 第四范式（北京）技术有限公司 | 基于图嵌入的信用卡逾期预测方法、装置及电子设备 |
-
2019
- 2019-01-07 CN CN201910017697.6A patent/CN109767008A/zh active Pending
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112507244A (zh) * | 2019-09-16 | 2021-03-16 | 腾讯科技（深圳）有限公司 | 社交数据推荐方法、装置、分布式计算集群及存储介质 |
| CN112507244B (zh) * | 2019-09-16 | 2023-09-26 | 腾讯科技（深圳）有限公司 | 社交数据推荐方法、装置、分布式计算集群及存储介质 |
| CN111325326A (zh) * | 2020-02-21 | 2020-06-23 | 北京工业大学 | 一种基于异质网络表示学习的链路预测方法 |
| CN111400560A (zh) * | 2020-03-10 | 2020-07-10 | 支付宝(杭州)信息技术有限公司 | 一种基于异构图神经网络模型进行预测的方法和系统 |
| CN111581488A (zh) * | 2020-05-14 | 2020-08-25 | 上海商汤智能科技有限公司 | 一种数据处理方法及装置、电子设备和存储介质 |
| CN111581488B (zh) * | 2020-05-14 | 2023-08-04 | 上海商汤智能科技有限公司 | 一种数据处理方法及装置、电子设备和存储介质 |
| CN112561688A (zh) * | 2020-12-21 | 2021-03-26 | 第四范式（北京）技术有限公司 | 基于图嵌入的信用卡逾期预测方法、装置及电子设备 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Ding et al. | Graph prototypical networks for few-shot learning on attributed networks | |
| CN109767008A (zh) | 一种基于元模式的高度异构网络多态特征学习方法 | |
| CN112241481B (zh) | 基于图神经网络的跨模态新闻事件分类方法及系统 | |
| CN113378913B (zh) | 一种基于自监督学习的半监督节点分类方法 | |
| CN112035669A (zh) | 基于传播异质图建模的社交媒体多模态谣言检测方法 | |
| CN108256561A (zh) | 一种基于对抗学习的多源域适应迁移方法及系统 | |
| US20230117980A1 (en) | Systems and methods for graph prototypical networks for few-shot learning on attributed networks | |
| CN114818719B (zh) | 一种基于复合网络与图注意力机制的社区话题分类方法 | |
| Huang et al. | Large-scale heterogeneous feature embedding | |
| Li et al. | Attributed network embedding with micro-meso structure | |
| CN112100372B (zh) | 头版新闻预测分类方法 | |
| Zhang et al. | Hypergraph label propagation network | |
| CN113228059A (zh) | 面向跨网络的表示学习算法 | |
| CN113989544A (zh) | 一种基于深度图卷积网络的群体发现方法 | |
| Selvarajah et al. | Dynamic network link prediction by learning effective subgraphs using CNN-LSTM | |
| CN113051397A (zh) | 一种基于异质信息网络表示学习和词向量表示的学术论文同名排歧方法 | |
| CN113420154A (zh) | 基于层次注意的分层多标签文本分类模型的构建方法 | |
| CN114898141B (zh) | 一种基于对比损失的多视图半监督图像分类方法 | |
| CN104463864B (zh) | 多级并行关键帧云提取方法及系统 | |
| Zhang et al. | Modeling the Homophily Effect between Links and Communities for Overlapping Community Detection. | |
| CN106203164A (zh) | 基于可信计算和云计算的信息安全大数据资源管理系统 | |
| CN114207573A (zh) | 基于度分布生成模型的社交网络图生成方法 | |
| CN110851733A (zh) | 基于网络拓扑和文档内容的社团发现和情感解释方法 | |
| CN112668633A (zh) | 一种基于细粒度领域自适应的图迁移学习方法 | |
| CN112836763A (zh) | 一种图结构数据分类方法及装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20190517 |