BLOG

个人博客,记录学习与生活

读论文9月第四周

Published Oct. 5, 2020, 8:55 p.m. by kkk

Heterogeneous Information Network Embedding for Recommendation[TKDE 2018]

提出了基于异质信息网络(HIN)表示的推荐框架HERec,作者称是第一个尝试采用异质网络表示手段抽取信息并利用信息进行评分预测的方法,2017年发在arXiv,2018年登上TKDE。基于HIN的方法虽然取得了一定的效果提升,但存在两个问题:

  1. 基于元路径的相似性依赖于路径可达性,在路径稀疏并且存在噪音的推荐场景中可能不可靠
  2. 基于元路径的相似性主要描述了HIN中定义的语义关系,可能不能直接应用到推荐系统。

HERec流程

元路径随机游走

首先人为设定出几条元路径,有元路径集$P$,分别根据每条元路径的模式,进行随机游走,满足类型的节点采样概率相同,对于游走后得到的序列,要进行一个类型过滤操作, 只从得到的序列中选择与开始节点类型相同的节点。就是在metapath2vec中加入了类型过滤。

embedding训练

对于所得节点,按照node2vec,通过SGD优化下式得到节点表示: $$ \max_f \sum_{u\in V}\log Pr(N_u\vert f(u)) $$ 只在$N_u$上,即节点序列上与之前的方法不同。此步分别得到商品和用户的embedding表示$e_u^{(l)}, e_i^{(l)}$,$(l)$表示对应元路径集中的第$l$个。

embedding转换

由于商品和用户都有多个embedding(每个元路径对应一个embedding),需要把这多个embedding融合成一个最终embedding表示。采用一个通用的函数$g(\cdot)$: $$ e_u^{(U)} \leftarrow g(\lbrace e_u^{(l)} \rbrace),\\ e_i^{(I)} \leftarrow g(\lbrace e_i^{(l)} \rbrace) $$ $g(\cdot)$可采取三种方式:简单线性组合、带权重线性组合、带权重非线性组合。商品和用户的$g(\cdot)$参数分别是$\Theta^{(U)}, \Theta^{(I)}$。

矩阵分解

将整个用户-商品的评分矩阵分解为用户矩阵$x$和商品矩阵$y$(确实没想到会使用矩阵分解,应该是通过SGD更新)

评分预测

最终用户对商品的评分预测通过下式求出: $$ \tilde r_{u,i} = x_u^T\cdot y_i + \alpha\cdot {e_u^{(U)}}^T \cdot \gamma_i^{(I)} + \beta \cdot {\gamma_u^{(U)}}^T\cdot e_i^{(I)} $$ 其中为了不需要将$e_u, e_i$投影到同一向量空间,引入$\gamma_i^{(I)}, \gamma_u^{(U)}$,分别与两个embedding同维度。

损失函数

$$ L = \sum_{\langle u,i,r_u\rangle\in R}(r_{u,i}-\tilde r_{u,i})^2+\lambda \sum_u(\Vert x_u \Vert_2 + \Vert y_i\Vert_2 + \Vert \gamma_u^{(U)}\Vert_2 + \Vert \gamma_i^{(I)}\Vert_2 +\Vert \Theta^{(U)}\Vert_2 + \Vert \Theta^{(I)}\Vert_2) $$

$\lambda$为正则化系数

参数更新

分为两截,先获取各元路径对应的商品、用户embedding。

通过三元组$\langle u,i,r\rangle$更新$x_u, y_i$,通过$e_u$更新$\Theta^{(U)}$和$\gamma^{(I)}$,通过$e_i$更新$\Theta^{(I)}$和$\gamma^{(U)}$,都是通过SGD。


HIN2Vec: Explore Meta-paths in Heterogeneous Information Networks for Representation Learning[CIKM 2017]

提出了异质网络的表示学习框架HIN2Vec,基于给定的关系集(元路径)联合进行多个预测任务的训练,学习网络中节点和元路径的向量表示,特别点在于学习元路径的表示。

算法框架

网络仅有一层隐层结构,实际上不同上图,为了降低复杂度,预测任务模式是——判断两个节点是否存在关系$r$,将多分类问题变成了二分类问题。输入是节点$x, y$,元路径$r$,都采用one-hot表示,变换矩阵分别是$W_X, W_Y,W_R$,在论文实验中设置$W_X==W_Y$。

关于元路径的输入形式:首先列出元路径集,保持一定顺序,将其转变为one-hot形式。但是变换矩阵$W_R$另外加了一个约束函数$f(\cdot)$使其($W_R$)所有元素处于$0-1$之间,两方面作用:1. 避免出现负值;2. 避免元素值过大。多个函数都可以达到效果,如sigmoid、binary step函数等,作者选择了binary step函数,论文中说比sigmoid效果更好。

隐层设置:激活函数选择线性恒等函数,即$\sigma(x)=x$,经过变换的三个向量处于同一向量空间,采用逐元素相乘的形式连接起来。

训练数据:数据通过在图上随机游走(按照元路径模式)取得,形式为$\langle x,y,r,L(x,y,r)\rangle$,其中$L(x,y,r)$表示$x,y$间是否存在关系$r$,取值为0、1。

优化方式:依旧是随机梯度下降,也使用了负样本,但只是为了增加训练集,负样本的选择方式是替换掉正确数据$\langle x,y,r\rangle$中$x,y$中的一个,因为节点取值比关系取值更多,且更换之后的节点与原节点具有相同的类型值

目标函数:采用取对数方式,具体形式如下: $$ Loss = L(x,y,r)\log P(r\vert x,y)+[1-L(x,y,r)]\log[1-P(r\vert x, y)]\\ P(r\vert x, y) = sigmoid(\sum W_x \vec x \odot W_Y \vec y\odot f(W_R \vec r)) $$ 应用:节点多分类,链路预测

总结:引入了元路径的同时保持了同一向量空间,每个节点只有一个向量表示,没有根据每个元路径单独学习一个向量表示;将多分类问题变成了二分类问题,降低了计算成本;通过负样本实现了数据增强功能。


Heterogeneous Graph Attention Network[WWW2019]


基于注意力机制提出了异质网络的图神经网络框架HAN,有层次化的两个注意力层,分别是节点层和语义层。

模型框架

网络类型就是一个普通的异质网络,比如电影-用户、作者-论文-会议等,构建元路径集$\Phi=(\Phi_1,\Phi_2,\cdots, \Phi_P)$,如何有效构造每个节点的embedding呢,图神经网络的思想是:每个节点的信息接受域是其所有邻节点,现在面临的问题是如何在异质网络中聚合这些邻节点的信息。

在元路径理念中,邻节点并不是指网络中完全相邻的节点,这里的邻节点指通过特定一条元路径所能访问到的节点,以此构成一个个节点对,作为训练数据。由于不同类型节点的表示不同(one-hot表示),为了聚合不同类型节点,论文采用的方式是对于每个类型的节点构造一个转移矩阵$M_{\Phi_i}$,将所有类型的节点都转到同一个向量空间内,将输入节点$(h_i,h_i)$变为$(h^\prime_i, h_j^\prime)$,对应上图中的最左侧(节点的Proj操作)。

对于同一中心节点,为了聚合所有邻节点并使不同节点有不同大小的贡献,如上图所示,引入自注意力机制(如模型框架图中的Node Attention操作),节点$j$对节点$i$的注意力贡献为($a_\Phi$为节点层注意力向量): $$ e_{ij}^\Phi = att_{node}(h_i^\prime, h_j^\prime;\Phi) \\ e_{ij}^\Phi = \sigma(a_\Phi^T \cdot [h_i^\prime\Vert h_k^\prime]) $$

将节点$i$的所有邻节点注意力进行规范化得到各自权重: $$ \alpha_{ij}^\Phi = softmax(e_{ij}^\Phi) $$ 于是得到节点$i$的表示(其中$N_i^\Phi$指节点$i$通过元路径$\Phi$能访问到的节点集,$\sigma$为任意一个非线性函数): $$ z_i^\Phi = \sigma(\sum_{j\in N_i^\Phi}\alpha_{ij}^\Phi \cdot h_j^\prime) $$ 至此得到了模型框架图中的$Z_{\Phi_0},Z_{\Phi_P}$。然而这只是在一条元路径上的表示,多条元路径上的表示如何进行聚合?同样是采用注意力机制。在此之前,由于网络上数据方差比较大,为了增加模型的健壮性,实际上对于$z_i^\Phi$的获取,采用的是Multihead attention,见下式($\Vert$是向量连接操作,连接次数$K$是一个全局固定的超参数): $$ z_i^\Phi = \Vert^K_{k=1}\sigma(\sum_{j\in N_i^\Phi}\alpha_{ij}^\Phi \cdot h_j^\prime) $$ 之后,对不同元路径再进行注意力机制,得到各元路径的注意力系数: $$ (\beta_{\Phi_0},\cdots, \beta_{\Phi_P}) = att_{sem}(Z_{\Phi_0}, \cdots, Z_{\Phi_P}) $$ 更具体的描述是($q$论文中称之为语义层注意力向量): $$ \beta_{\Phi_i} = \frac{\exp(w_{\Phi_i})}{\sum_{i=1}^P \exp(w_{\Phi_i})}\\ w_{\Phi_i} = \frac{1}{\vert V\vert}\sum_{i\in V}q^T\cdot \tanh(W\cdot z_i^\Phi + b) $$ 于是将各元路径上的embedding进行聚合,即可得到最终的embedding(对应模型框架图中的(b)): $$ Z = \sum_{i=1}^P \beta_{\Phi_i}\cdot Z_{\Phi_i} $$ 之后可用来进行一些下游任务如节点分类,这也正是模型框架图中(c)中的做法,通过多层感知机,利用交叉熵作为损失函数,进行节点类别预测。


Inductive Representation Learning on Large Graphs[NIPS2017]

属于比较标志性的一个算法,相较于此前的网络,有个很明显的表现提供,提出了GraphSAGE,SAGE意为“SAmple and aggreGatE”。此前的方法主要是transductive,而GraphSAGE是inductive,可以利用节点属性来生成未曾被训练的节点(unseen data)。

思想比较简单,有点同LLE,将一个节点视为多个邻节点和自身节点的信息叠加,通过设置步长控制节点接收信息的节点范围,为$K$意味着循环接收$K$层的邻节点信息。算法如下:

上图算法流程比较清晰,对点循环更新embedding时,采用聚合邻节点的方式,聚合的邻节点集通过采样获取,保持固定长度。其中聚合器有多种选择:平均、LSTM、池化(逐元素最大池化)。更新每个点在聚合邻节点信息之后,将聚合的信息与原节点进行连接,连接方式论文中采用的是一个全连接层(采用非线性激活函数),然后将节点更新为连接后的新embedding。

GraphSAGE受到一个传统算法的启发:Weisfeiler-Lehman isomorphism test。GraphSAGE时对该算法的一个连续式近似。

激活函数为: $$ J_G(z_u) = -\log(\sigma(z_u^Tz_v))-Q\cdot \mathbb E_{v_n\sim P_n(v)}\log(\sigma(-z_u^Tz_{v_n})) $$


A Heterogeneous Graph Neural Model for Cold-start Recommendation[SIGIR2020]

利用异质网络处理冷启动推荐问题,重点仍是通过构造节点embedding进行点击预测,提出了HGNR模型。冷启动推荐指的是对特定一类用户的推荐,这类用户与商品的交互次数小于等于某个值,论文中是10次。

最终评分预测(用户-商品相似度预测)为: $$ \widehat y_{ui} = e_u^{\ast T}e_i^\ast $$ 技术方案:

对现有算法进行了整合,首先将原始网络图$H$表示成了三个(都为矩阵形式):$R$为用户-商品间的交互图,每个元素表示用户对商品的评分(如何处理无评分数据?应该是都用特定的数如0表示);$S$为用户间的关联图,每个元素表示两个用户间是否有社交连接(上图中$C,S$标反了);$C$表示两个商品间是否有相似的用户评价(文本信息)。最终的$H$表示为: $$ H = \left[ \begin{matrix} \alpha S & R\\ R^T & \beta C \end{matrix}\right] $$ 三个矩阵中$R$本身就存在,$S$通过传统算法BPR和IMF处理而得,$C$矩阵通过对商品的评论合并然后经过Sentence-BERT处理而得,每个商品最终生成固定(且)相同长度的embedding,属于商品语义连接关系。$\alpha, \beta$分别是控制社交网络连接$S$和语义连$C$接贡献量的权重系数。合成后的矩阵$H$,先经过图拉普拉斯处理得到图拉普拉斯矩阵: $$ L^c = D^{-\frac{1}{2}}HD^{\frac{1}{2}} $$ 其中$D$为$H$的对角度矩阵,最后训练的点embedding为: $$ \begin{align}HGNR(H)^{(l)} &= E^{(l)}\\ &= \sigma((L^{(c)}+I)E^{(l-1)}W_o^{(l)}+L^{c}E^{(l-1)}\odot E^{(l-1)}W_n^{(l)} \end{align} $$ 采用了多层GCN结构,激活函数采用LeakyReLU,$W_o^{l}$保存了每个用户或商品的原有信息,$W_n^{(l)}$聚合了邻节点的信息。

创新点:

引入用户社交信息和商品语义信息来增强模型的表示能力;组合了多种算法。


Heterogeneous Graph Neural Network[KDD2019]

针对异质网络(节点属性包括值、文本、图片)提出了表示学习框架HetGNN,属于图神经网络框架,运用到多种深度学习技术。

聚焦了三个问题:

  1. 异质网络中很多节点可能不直接相连,很多GNN方法只能聚合邻节点的信息,导致很多节点间的关系不能被很好的表达,也难处理冷启动问题。
  2. 异质网络的节点可能带有非结构内容,而且不同节点的内容可能不同。
  3. 对一个而言节点,不同邻节点的贡献是不一样的。

整体框架:

解决方案:

HetGNN各个部分的结构设计正好对应于所聚焦的问题。

  1. 对于第一个问题,使用了带重启的随机游走策略进行采样,游走长度固定,游走过程中有一定概率回到起点,并且限制每个类型节点的个数,以保证每个节点都能被采样到;将采样的节点按类别分组,分组找那个选择频率最高的$k_t$个节点作为训练的邻节点。

  2. 对于第二个问题,不同类别属性节点的处理,引入不同的网络技术,使用Par2Vec对文本属性进行预训练,使用CNN对图片属性进行预训练...;通过双向LSTM(Bi-LSTM)将训练的embedding进行连接,连接之后的节点表示为: $$ f_1(v) = \frac{\sum_{i\in C_v}[\overrightarrow{LSTM}{FC_{\theta_x}(x_i)}\oplus \overleftarrow{LSTM}{FC_{\theta_x}(x_i)}]}{\vert C_v\vert} $$ 先通过$FC$层(全连接层)处理以训练的embedding,然后使用Bi-LSTM获取深层属性交互关系,然后对所有层进行平均池化操作。

  3. 对于第三个问题,分为两个环节:聚合同类节点聚合各类信息。聚合同类节点,首先通过一层$AG$网络处理(可以是全连接层、卷积层、循环网络层): $$ f_2^t(v) = AG^t_{v^\prime \in N_t(v)}{f_1(v^\prime)} $$ 论文中继续使用了Bi-LSTM,于是有,如框架图中的(c): $$ f_2^t(v) = \frac{\sum_{v^\prime \in N_t(v)}[\overrightarrow{LSTM}{f_1(v^\prime)}\oplus \overleftarrow{LSTM}{f_1(v^\prime)}]}{\vert N_t(v)\vert} $$ 聚合各类信息,为了聚合各个不同类型的邻节点,采用注意力机制,运算的对象为$F(v)={f_1(v)\cup(f_2^t(v),t\in O_V}$,最终的输出是$\xi_v$: $$ \xi = \sum_{f_i\in F(v)}\alpha^{v,i}f_i\\ \alpha^{v,i}=\frac{\exp{LeakyReLU(u^T[f_i\oplus f_1(v)])}}{\sum_{f_j\in F(v)}\exp{LeakyReLU(u^T[f_j\oplus f_1(v)])}} $$



Share this post
< Pre: 主成分分析 Pos: 推荐系统概念 >
4 comments
Similar posts
Add a new comment