基于图嵌入和图神经网络的社交网络影响力最大化方法

贡献：

提出了一种新的使用struc2vec图嵌入和基于图神经网络的回归器的影响力最大化方法
将影响力最大化问题看作一个伪回归任务使深度学习和机器学习的方法可以应用到这个任务中
使用LSTM单元作为GNN中的邻域聚合器

方法概述：

影响力最大化问题中，一个很重要的部分是根据节点可能的影响力对节点进行排序。
这个可能的影响力形成了一组连续的值。因此，将影响最大化的问题解释为基于特定节点特征预测形成伪回归活动的连续值集的任务。
节点特征应保持网络中节点的结构特点及其拓扑特征。为了提取和处理这些节点特征，利用struc2vec节点嵌入方法来为网络的每个节点生成合适维度的特征向量。这简化了要在网络上执行的各种机器学习和深度学习任务的适用性。
生成的节点嵌入由GNN架构进一步处理。然后将这些处理后的嵌入传递到回归器上，以预测网络中的节点所实现的最终影响力扩散。
算法的基本功能是在训练网络上训练所提出的基于GNN的模型以获得模型参数，然后在目标网络上使用该训练模型来执行影响最大化。
通过计算信息扩散模型下训练网络的节点的个体影响来生成训练模型所需的标签。
四个阶段：
- 生成标签
- 通过嵌入生成特征
- 通过GNN处理特征
- 使用回归器预测影响力传播

1 标签生成

在本研究中，将影响最大化问题解释为伪回归问题。然而，对于任何回归任务，我们都需要一组定义良好且连续的标签。

沿着这些路线，我们还要求标签回归网络特征以进行训练。利用Barabasi-Albert（BA）合成网络的几个变体作为训练网络，训练我们的模型以进行影响最大化任务。

沿着伪回归任务的想法，在SIR信息扩散模型下计算每个节点的影响力。该计算的影响力用于训练回归任务的SGNN模型的标签。

表示如下：

$$label^G:=IDM(G(V,E))$$

2 使用struc2vec嵌入生成特征

大多数现实生活中的网络，如在线社交网络，都在不断发展，规模庞大，通常难以处理和分析。某些网络还关联特定的节点属性，但并非所有网络都是如此。为了解决这个困难，我们使用节点嵌入技术为每个网络生成节点属性。

因此，我们的目标是提供一个通用的影响最大化框架，利用网络结构来生成网络中的节点的功能。作为这项工作的一部分，我们采用了基于struct2vec节点嵌入的方法来为网络中的每个节点生成低维向量。

$$S=struc2vec(G,d)$$

节点v的嵌入表示为：

$$s_v=S[v],v\in V$$

3 使用GNN处理特征

基于图神经网络（GNN）的特征处理。使用图的节点之间的消息传递和邻域聚合来捕获图信息。它有助于表示来自具有任意深度的节点的邻域的信息，定义从该节点到形成邻域的跳数。

通过struct2vec捕获的网络细节通过GNN架构进一步增强和增强。这有助于更好地说明网络节点的结构细节。GNN中的聚合器函数可以是参数的，也可以是非参数的。

在我们的研究中，我们考虑了一个参数聚合函数，因为它通过不断更新学习参数的值来更深刻地捕捉网络的复杂结构，以获得更好的结果。GNN生成表示网络中每个节点v的特征的最终状态向量，如下所示。

$$h_{v}=f(s_{v},h_{\text{ne}[v]},s_{\text{ne}[v]}),v\in V$$

$h_v$是最终的状态向量
$s_v$是节点v生成的嵌入向量
$h_{ne[v]}$是节点v邻居节点的最终状态向量
$s_{ne[v]}$是节点v邻居节点的嵌入向量
$f$是邻域聚合函数，此处使用LSTM

逐层更新公式为：

$$H^{i+1}:=F(H^i,S)$$

4 使用一个回归器进行最终的影响力传播预测

通常，回归器用于输入数据点的一组特征，并在优化损失函数的同时生成一组连续值作为输出。

回归器是所提出的SGNN架构中预测网络中可能的影响力大小的部分。在先前步骤由GNN产生的最终特征向量被送到回归器中。回归器使用均方误差作为损失函数。

一旦被训练，整个模型就被用于对目标网络中的节点的可能影响力进行预测。回归器的工作是将影响力预测作为一组连续值。然后根据节点的预测影响对节点进行排列

$$Inf_v=o(h_v,s_v,\beta)$$

$$loss=\frac{\Sigma_{v=1}^{|V|}(Calc_v-Inf_v)^2}2$$

训练和测试模型的过程如下

$$trained_SGNN := SGNN(G^{train},S^{G^{train}},label^{G^{train}},f,o)$$

$$Predicted_Influence := trained SGNN(G^{test},S^{G^{test}})$$

$$Spread := trained SGNN(G^{test},S^{G^{test}},k)$$

使用带标签的训练网络对模型进行训练
使用训练好的模型在测试网络计算结点的影响力
计算前k个节点的影响力传播

参数分析

因为我们通过在一个网络上训练SGNN并在完全不同的网络上进行影响力预测。因此，我们执行参数分析以确定最佳训练网络。为此，我们在BA模型下创建了两组网络，分别用于训练和测试的$D^{Train}$和$D^{Test}$。通过在不同的训练网络上训练SGNN，SGNN的性能评估如下

$$trained_SGNN:=SGNN(D^{train}[i],S^{D^{train}[i]},label^{D^{train}[i]},f,o),i\in range(1,len(D^{train})),$$

$$F(t_c)[{i}][{j}]:=\sum_{k=10\wedge k+=5}^{k=50}{\textit{trained SGNN}(D^{\text{test}} [ { j }],S^{\text{D}^{\text{test}} [ { j }]},k),j\in\text{range}(1,\text{len}(D^{\text{test}} ) ) }$$

$F(t_c)[{i}][{j}]$代表最终的感染范围或者影响力扩散范围

根据如下公式选择训练网络：

$$Opt_Train:=argmax\left{\sum_{j=1}^{j=len(D^{test})}\frac{F(t_c)[i][j]}{\sum_{q=1}^{q=len(D^{train})}F(t_c)[q][j]},i\in D^{train}\right}$$

总结和思考：

方法总结

本文使用的方法核心为将影响力最大化问题转化为一个伪回归问题

回归问题中的标签：使用SIR模拟获取节点的影响力大小作为标签
对于特征的处理:
- 首先使用struc2vec生成节点的嵌入作为节点特征
  - struct2vec使用层次结构来度量不同尺度的节点相似性，并构造多层图来编码结构相似性并生成节点的结构上下文。最终通过结构上下文进行word2vec嵌入
  - 由于struc2vec使用的层次结构信息,因此生成的嵌入可以很好的捕捉节点周围的拓扑结构信息
- 使用GNN处理上边生成的节点特征
  - 使用一个聚合器聚合邻居的最终状态向量$h_{ne}$ , 邻居的嵌入向量$s_{ne}$, 自身的嵌入向量$h$ , 聚合后更新最终状态向量
  - 其中h的初始化文中没有提及, 此处使用了嵌入向量初始化最终状态向量
  - 这一步使用GNN处理, 可以聚合邻居节点的信息, 通过迭代在邻域上的聚合捕捉更加复杂的网络结构, 使用GNN也可以提高模型的泛化性, 提升在其他网络上的表现.

创新点：

1. 对影响力重叠问题做处理

在该论文的方法中，最终寻找的影响力最大的种子节点集可能会出现聚集的现象，导致影响力重叠问题。

可以在最后对候选节点进行筛选（距离过近的删除？）（需要进一步考虑如何筛选）

或者在前期嵌入阶段采取一些办法避免出现影响力重叠

2. 关于图中节点的属性补全？

本文中讨论的图均不考虑节点属性，然而现在越来越多的数据集中节点带有属性。

是否可以对不同的数据集做不同的处理：

对不带属性的图，先进行属性补全（使用其他方法获取嵌入作为特征或者使用一些中心性指标作为初始特征）

然后对于带属性的图，通过GNN聚合特征，判断影响力大小

3. 对嵌入方法（生成特征）进行改进?

本文使用struc2vec获取嵌入向量。可以考虑使用其他更有效的嵌入方法

比如：

~~CARE : community-aware random walk for network embedding~~

~~这种方法的优点（为什么选择它）：~~

~~降低花费的计算时间~~

~~邻域不仅包含一阶邻居的信息，而且可以包含不直接相连的节点（具有一阶和二阶邻域不包含的同质性）~~

对于影响力传播，一阶和二阶邻居应该是是比较重要的。

考虑LINE和SDNE（一阶和二阶方法）

或者调整struc2vec的层数

4. 该方法是否能扩展到异质图上?（暂时不考虑）

问题一 : 生成特征可以用哪些方法?

metapath2vec等异质图嵌入方法

问题二 : 处理特征时需要有哪些改变?

由于本文的GNN只涉及消息传递与聚合, 不需要过多改变就可以使用在异质图上.

但是,也可以对GNN进行一些完善, 比如加上激活函数等

问题三 : 本文最后得到的模型是一个泛化的通用模型, 在异质图上可以得到吗?

本文中使用了很多基于BA模型生成的数据集进行训练和测试, 最后通过比较选择了最好的参数. 然后用于其他数据集.

对于异质图, 对于不同节点类型数目的网络, 模型可能泛化性很差.

但是可以考虑如下情况, 在同一类异质图上(比如, 学术网络), 通过不同规模的学术网络数据集进行训练, 选择参数, 最后在其他同类数据集上直接使用.

问题四 : 异质图上边的类型不同, 信息传播模型是否需要改变?