1.本发明涉及时序图的数据分析和预测技术领域，尤其涉及融合长短期依赖的节点-边交互式动态链路预测方法。
背景技术：
2.时序图包含了结构信息和时间信息，因此如何综合利用这两类信息进行动态链路的精准预测是一个难点；同时，相邻两个时刻之间的时间间隔对于链路预测也至关重要，而如何准确地捕捉时间间隔信息也面临着挑战。目前已有的相关技术主要是基于传统的机器学习算法(如决策树、支持向量机等)或者简单的时间序列模型(如arima、指数平滑等)进行动态链路预测。
3.当前方法主要将节点和边的特征向量作为输入，忽略了图的拓扑结构信息。图结构中的社区结构、节点中心性等信息可能对链路预测有重要影响，而目前的方法没有充分利用这些结构信息。虽然当前方法考虑了时间间隔信息，但仅采用简单的加法或乘法方式将其与时序信息进行融合。这种简单的融合方式可能无法充分挖掘时间间隔与时序关系之间的复杂联系。因此，需要开发一种新的动态链路预测方法。
技术实现要素：
4.为克服传统链路预测算法无法准确捕捉时间间隔信息导致预测链接关系和链接出现的时间不够准确的技术缺陷，本发明提供了一种融合长短期依赖的节点-边交互式动态链路预测方法。本方法引入时间间隔到经典循环神经网络lstm，以更好的捕捉时间间隔信息，通过融合长短期依赖的节点-边交互式建模，更好地利用时序信息和结构信息，准确捕捉时间间隔信息，从而实现对动态链路的精准预测，为实际应用提供更加准确、可靠的支持。
5.本发明提供了融合长短期依赖的节点-边交互式动态链路预测方法，包括以下步骤：
6.步骤一、构建时间序列：将时间戳信息看作边上的属性信息，即可用属性图的形式表示时序图，从而将时序图中的节点和节点之间的边按照时间顺序组织成节点时间序列和边时间序列，在时序图中，每条边上均带有时间戳信息，且时间戳信息表示为(u,v,t)，其中u,v∈v,v为时序图上的顶点集合，t为时刻，这一步中，主要构建节点和边的特征向量，并将其与时间戳信息进行关联；
7.步骤二、基于lstm捕获长短期依赖：
8.其次需要对节点时间序列进行处理，对每个节点的时间序列应用lstm，捕获节点自身的长短期依赖关系，也就是捕获节点在不同时刻的表示向量，其中节点时间序列的lstm处理公式为：
9.10.式(1)中，为节点v在t时刻的隐藏状态，为节点v在t时刻的细胞状态；
11.考虑到时间戳信息，将节点v的时间间隔δtv加入到lstm中，来处理非均匀分布的时间序列，使其对时间敏感，并融合节点自身特征向量和当前时刻边上的表示向量生成节点的输入向量，加入时间间隔δtv后，节点时间序列的lstm处理公式更新为：
[0012][0013]
接着对边时间序列进行处理：对每条边的时间序列应用lstm，捕获边自身的长短期依赖关系，其中边时间序列的lstm处理公式为：
[0014][0015]
式(3)中，u和v是边(u，v)的两个节点，为边(u，v)在t时刻的隐藏状态，为边(u，v)在t时刻的细胞状态；
[0016]
同样考虑到时间戳信息，将边(u，v)的时间间隔δt
(u,v)
加入到lstm中，使其对时间敏感，加入时间间隔δt
(u,v)
后，边时间序列的lstm处理公式更新为：
[0017][0018]
步骤三、节点-边交互式训练：
[0019]
捕获节点和边的长短期依赖关系后，接着进行动态链路预测，为了考虑节点-边之间的交互信息对状态向量的影响，设计了节点-边交互模型，节点-边交互模型通过在lstm中引入节点-边交互层，利用节点向量和边向量相互作用来更新状态向量，以充分考虑节点和边之间的动态关系，即在每个时刻t，使用节点时间序列中节点v的最新状态和边时间序列中边(u，v)的最新状态通过公式(5)进行交互生成特征向量，用于表示边(u，v)的状态；
[0020]
边状态更新公式为：
[0021][0022]
式(5)中，为节点状态更新公式，其为：
[0023][0024]
式(6)中，为节点v的自身特征向量；
[0025]
由于边上的时间戳信息并不是在任意相邻的时刻都存在，即边时间序列不是均匀分布的，因此，在lstm中加入时间间隔，式(5)和(6)更新后为：
[0026][0027][0028]
步骤四、模型训练与预测：使用可用的训练数据对步骤三中建立的模型进行记性训练，并进行参数优化，得到训练好的节点-边交互模型，利用训练好的节点-边交互模型即可对未标记的时序图进行链路预测，得到时序图中节点之间的连接关系。
[0029]
优选的，步骤四中，参数优化使用的是随机梯度下降优化方法或动量优化方法。
[0030]
本发明提供的技术方案与现有技术相比具有如下优点：一、本发明的技术方案可以更好地利用时序信息和结构信息：该技术方案通过长短期记忆网络分别对节点和边的时间序列进行建模，同时在模型中融合时间间隔信息和节点-边交互信息，从而更好地利用了时序图数据中所包含的时序信息和结构信息；二、可以准确捕捉时间间隔信息：该技术方案通过对相邻两个时刻间时间间隔的建模，能够准确捕捉时间间隔信息对链路预测的影响；三、该方法还可通过调整滑动窗口大小来灵活控制时间尺度，进一步提高时间间隔信息的准确性；四、可以提高预测精度和可解释性：该技术方案通过融合时序信息和结构信息、处理时间间隔信息以及节点-边交互信息等多种因素，能够大幅提高动态链路预测的精度和可解释性，为实际应用提供更加准确、可靠的支持；五、它适用于各种时序图数据：该技术方案采取的基于长短期记忆网络进行动态链路预测的方法，不仅能够适用于社交网络、交通网络等常见的时序图数据，还可扩展应用于其他领域的时序图数据预测中。
附图说明
[0031]
此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本发明的实施例，并与说明书一起用于解释本发明的原理。
[0032]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，对于本领域普通技术人员而言，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0033]
图1为本发明某个实施例中融合长短期依赖的节点-边交互式动态链路预测方法涉及的时序图链路预测模型图。
具体实施方式
[0034]
为了能够更清楚地理解本发明的上述目的、特征和优点，下面将对本发明的方案进行进一步描述。需要说明的是，在不冲突的情况下，本发明的实施例及实施例中的特征可以相互组合。
[0035]
在描述中，需要说明的是，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性。需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。
[0036]
在下面的描述中阐述了很多具体细节以便于充分理解本发明，但本发明还可以采用其他不同于在此描述的方式来实施；显然，说明书中的实施例只是本发明的一部分实施例，而不是全部的实施例。
[0037]
下面结合附图对本发明的具体实施例进行详细说明。
[0038]
在一个实施例中，如图1所示，本发明提供了融合长短期依赖的节点-边交互式动态链路预测方法，包括以下步骤：
[0039]
步骤一、构建时间序列：将时间戳信息看作边上的属性信息，即可用属性图的形式表示时序图，从而将时序图中的节点和节点之间的边按照时间顺序组织成节点时间序列和
边时间序列，在时序图中，每条边上均带有时间戳信息，且时间戳信息表示为(u,v,t)，其中u,v∈v,v为时序图上的顶点集合，t为时刻，步骤一主要进行数据预处理，主要构建节点和边的特征向量，并将其与时间戳信息进行关联；将时序图表示为属性图的形式，即将时间戳信息看作边上的属性信息，具体可表示为(u,v,t)，从而用属性图表示；另外，时序图也可以表示为在时间轴上边的时间序列；时序图上的动态链路预测问题可以建模为一个分类问题，即利用节点的表示向量来预测它们之间的连接关系；时序图中所有边均带有时间戳信息，故特定节点在不同时刻的状态构成一个节点时间序列，特定边在不同时刻的状态构成一个边时间序列；
[0040]
步骤二、基于lstm捕获长短期依赖：
[0041]
其次需要对节点时间序列进行处理，对每个节点的时间序列应用lstm，捕获节点自身的长短期依赖关系，也就是捕获节点在不同时刻的表示向量，其中节点时间序列的lstm处理公式为：
[0042][0043]
式(1)中，为节点v在t时刻的隐藏状态，为节点v在t时刻的细胞状态；
[0044]
考虑到时间戳信息，将节点v的时间间隔δtv加入到lstm中，来处理非均匀分布的时间序列，使其对时间敏感，并融合节点自身特征向量和当前时刻边上的表示向量生成节点的输入向量，加入时间间隔δtv后，节点时间序列的lstm处理公式更新为：
[0045][0046]
接着对边时间序列进行处理：对每条边的时间序列应用lstm，捕获边自身的长短期依赖关系，其中边时间序列的lstm处理公式为：
[0047][0048]
式(3)中，u和v是边(u，v)的两个节点，为边(u，v)在t时刻的隐藏状态，为边(u，v)在t时刻的细胞状态；
[0049]
同样考虑到时间戳信息，将边(u，v)的时间间隔δt
(u,v)
加入到lstm中，使其对时间敏感，加入时间间隔δt
(u,v)
后，边时间序列的lstm处理公式更新为：
[0050][0051]
步骤三、节点-边交互式训练：
[0052]
捕获节点和边的长短期依赖关系后，接着进行动态链路预测，为了考虑节点-边之间的交互信息对状态向量的影响，设计了节点-边交互模型，节点-边交互模型通过在lstm中引入节点-边交互层，利用节点向量和边向量相互作用来更新状态向量，以充分考虑节点和边之间的动态关系，即在每个时刻t，使用节点时间序列中节点v的最新状态和边时间序列中边(u，v)的最新状态通过公式(5)进行交互生成特征向量，用于表示边(u，v)的状态；
[0053]
边状态更新公式为：
[0054][0055]
式(5)中，为节点状态更新公式，其为：
[0056][0057]
式(6)中，为节点v的自身特征向量；
[0058]
由于边上的时间戳信息并不是在任意相邻的时刻都存在，即边时间序列不是均匀分布的，因此，在lstm中加入时间间隔，而且时间间隔越大，与需要损失的信息越多，式(5)和(6)更新后为：
[0059][0060][0061]
步骤四、模型训练与预测：使用可用的训练数据对模型记性训练，可用的训练数据即为已知连接关系的节点对和时间戳信息，并采用随机梯度下降优化方法、动量优化方法或其他优化方法进行参数优化，对模型进行监督式学习，得到训练好的节点-边交互模型，利用得到的节点-边交互模型即可对未标记的时序图进行链路预测，得到时序图中节点之间的连接关系。
[0062]
还可对本发明所述方法中的模型进行评估，具体的，评估指标采用常见的精确度(accuracy)、召回率(recall)、f1值(f1-score)等。其中，准确度表示被正确预测的连接关系占所有连接关系的比例，召回率表示被正确预测的连接关系占所有正确连接关系的比例，f1值则是综合准确度和召回率的一种综合评估指标。
[0063]
具体实施例中本发明所述链路预测模型如图1所示，时序图中顶点集合v＝{a,b,c,d}，边集为{(u,v)|u,v∈v}，图1中每条边上附带两个顶点之间交互的时刻，比如顶点为a和b的边(a,b)上附带(6，7，11)，表示顶点a和b在第6、7、11时刻进行了交互。a,b,c,d表示成节点时间序列，也就是表示成自身特征向量，在图1的右上角的图中我们将该时间序列表示成一条直线。两条之间的曲线连接即为边时间序列，也就是顶点之间的交互。在交互训练时我们引入了lstm，图1以节点b为例，在节点b的交互信息中引入lstm，其中图1左下角展示了节点b在交互时刻，节点状态信息的更新。图1右下角为节点b与节点c、d进行交互时的边状态信息更新。
[0064]
边在每一时刻的输入向量应由与其相关联的两个节点在当前时刻的状态向量产生。这也与动态链路预测问题的目标一致，即通过聚合节点向量来预测这两个节点之间是否有边存在。时序图中节点的表示向量也与时间戳紧密相关，及每个时刻均对应特定的表示。节点v在不同时刻有不同的表示向量，而且这些表示向量之间也具有长短期依赖，故也可以使用lstm捕获长期依赖关系，时间戳信息也类似加入到lstm模块中。通过节点和边的不断交互，最终可以生成节点的表示向量，利用分类模型即可进行链路预测。由于在模型中融入了时间间隔，通过对分类模型进行适当调整，从而可以估计边的出现时刻。
[0065]
以上所述仅是本发明的具体实施方式，使本领域技术人员能够理解或实现本发明。尽管参照前述各实施例进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等
同替换；而这些修改或者替换，并不使相应技术方案的本质脱离各实施例技术方案的范围，其均应涵盖权利要求书的保护范围中。