[TKDE 2021]Fast Semi-Supervised Learning WithOptimal Bipartite Graph

标签：TKDE right end Semi Graph begin frac aligned left

总结

损失函数中保证结构接近的同时让目标图中的标签和真实标签拟合，而结构接近的判断依据是顶点和锚点之间的关联程度

普通图上的半监督学习

亲和力矩阵：\(W_{ij}=\left\{ \begin{aligned} & exp(-||x_i-x_j||^2_2/2\sigma^2),\ x_i\ and\ x_j\ are\ neighbors, \\ & 0,\ others \end{aligned} \right.\)，其中\(\sigma\)为超参，需要根据数据集调整。
拉普拉斯矩阵：\(L = D - W,\ d_i = \sum_j W_{ij}\)
F范数：\(||M||^2_F = tr(M^TM),\ tr(A)=\sum_{i=1}^n(a_{ii})\)为矩阵的迹。由于F范数为矩阵内元素的平方和开方，因此正好等于矩阵外积的对角线的和，也就是矩阵外积的迹。
F为预测结果，损失函数：

\(\mathcal{J}(F)=\sum_{i,j=1}^nW_{ij}||F_i-F_j||^2_F+\sum^n_{i=1}\beta_i||F_i-Y_i||^2_F\)
可以转换为：
\(\mathcal{J}(F)=tr(F^TLF)+tr((F-Y)^TB(F-Y))\)，其中B为\(\beta\)的对角线矩阵。当损失函数的导数为0时：
\(\frac{\partial \mathcal{J}}{\partial F}|_{F=F^*}=2LF^*+2B(F^*-Y)=0\)
\(F^*=(L+B)^{-1}BY\)
最终的预测结果可写作\(y_i = {\rm arg\ max}_{j\leq c}F^*_{ij}\)。时间复杂度为\(O(n^2d+n^3)\)

锚点的半监督

通过k-means或者随机选择可以得到一组锚点\(U=[u_1,\dots,u_m]^T \in \mathbb{R}^{m \times d}\)
点i和锚点j的相似度可以用如下公式计算：

\(z_{ij}=\frac{K(x_i,u_j)}{\sum_{s \in \Phi }K(x_i,u_s)}, \forall j \in \Phi_i,\ \Phi \subset \{1,2,\dots, m\}\)表示i最近的k个锚点邻居，
高斯核函数：\(K(x_i,u_s)=exp(-||x_i-u_j||^2_2/2\sigma^2)\)

亲和力矩阵：\(W=Z\Lambda^{-1}Z^T,\ \Lambda_{jj}=\sum^n_{i=1}z_{ij}\)，实际上是对权重归一化了，拉氏矩阵：\(L=I-Z\Lambda^{-1}Z^T\)
reduced 拉普拉斯矩阵\(\widetilde{L} = Z^TLZ = Z^T(I-Z\Lambda^{-1}Z^T)Z = Z^TZ-(Z^TZ)\Lambda^{-1}(Z^TZ)\)

拉普拉斯矩阵的意义是矩阵中某一点进行微笑扰动后获得的总增益，即某点改变后对其他联通的点的影响情况。在这里，\(L \in \mathbb{R}^{n \times n}\)是针对所有顶点的，\(Z \in \mathbb{R}^{n \times m}\)针对所有点和锚点之间的权重，因此\(\widetilde{L} \in \mathbb{R}^{m \times m}\)体现的是锚点之间的影响情况。

损失函数\(\mathcal{J}(H)=\frac{1}{2}||Z_lH-Y||^2_F+\frac{1}{2}\beta tr(H^T\widetilde{L}H)\)，H为锚点的标签，\(Z_l\)为顶点和锚点之间的连接，实际就是认为和某个锚点相连，该点就和该锚点一种标签。连接多个锚点则获得各标签的概率。后半部分实际意义是各标签之间的影响程度，自然是越小越好了。
最终的结果：\(H^*=(Z_l^TZ_l + \beta\widetilde{L})^{-1}Z^T_lY,\ y_i={\rm arg\ max}_{j \leq c}\frac{Z_ih_j}{\xi_j}, i=l+1,\dots, n\)。其中\(\xi_j=1^TZh_j \in \mathbb{R}^{1\times c}\)用于归一，\(h_j \in \mathbb{R}^{m \times 1}\)为锚点和标签j的对应关系。

初始二部图上

不再使用高斯核计算Z，而是：

\(\min_{z_i^T1=1, zij \ge0}\sum_{j=1}^m||x_i-u_j||^2_2z_{ij}+\gamma z^2_{ij}\)
本质上是确保z中每一行归一，且都大于0的情况下，两点距离越远，赋权就要越小。同时还得保证\(Z_i\)平方和最小，这将会将\(Z_i\)中的元素拉向相等的值，也就是会让\(Z_i\)中尽可能不出现0。其中最优的\(\gamma\)的取值已有结论：
\(\gamma = \frac{k}{2}d(i,k+1)-\frac{1}{2}\sum^k_{j=1}d(i,j)\)
其中k为\(Z_i\)中的非零元素个数。此时可以得到最终的Z：
\(z_{ij}=\frac{d_{i,k+1}-d_{i,j}}{kd_{i,k+1}-\sum^k_{j=1}d(i,j)}\)
该方程比高斯核函数更加高效。在二部图中，亲和力矩阵就变为了：
\(W=\left[ \begin{aligned} & 0 & Z\\ &Z^T & 0 \end{aligned} \right],Z \in \mathbb{R}^{n \times m}\)

最优二部图

目标为学习一个S尽可能地和W接近，即：
\(\min_{A \ge0, A^T_i1=1}||S-W||^2_F,\ S=\left[ \begin{aligned} & 0 & A\\ &A^T & 0 \end{aligned} \right]\)
即：
\(\min_{A \ge 0, A1=1}||A-Z||^2_F\)

最优二部图上的半监督学习

\(F \in \mathbb{R}^{n \times c},\ G \in \mathbb{R}^{m \times c}\)代表原始顶点的标签和锚点节点的标签
\(L_S=D_S-S,\ D_S =\left[ \begin{aligned} & D_r & 0\\ & 0 & \Lambda \end{aligned} \right],\ D_r \in \mathbb{R}^{n \times n},\ \Lambda \in \mathbb{R}^{m \times m}\)
由于A归一了，\(D_r=I_n\)，\(D_S =\left[ \begin{aligned} & I_n & 0\\ & 0 & \Lambda \end{aligned} \right]\)
最终归一化的拉普拉斯矩阵：
\(\widetilde{L}_S= I-D_S^{-\frac{1}{2}}SD_S^{-\frac{1}{2}} =\left[ \begin{aligned} \begin{gather*} & I_n & -A\Lambda^{-\frac{1}{2}}\\ & -\Lambda^{-\frac{1}{2}}A^T & I_m \end{gather*} \end{aligned} \right]\)
目标函数：
\(\min_{A \ge 0, A^T_i1=1,F,G}=||A-Z||^2_F + \alpha Tr(\left[\begin{aligned} & F \\ & G \end{aligned} \right]^T\widetilde{L}_S \left[\begin{aligned} & F \\ & G \end{aligned} \right]) + Tr((\left[\begin{aligned} & F \\ & G \end{aligned} \right]-Y)^TB(\left[\begin{aligned} & F \\ & G \end{aligned} \right]-Y))\)

当F和G已经调整完成，目标就为：
\(\min_{A \ge 0, A^T_i1=1}||A-Z||^2_F + \alpha Tr(\left[\begin{aligned} & F \\ & G \end{aligned} \right]^T\widetilde{L}_S \left[\begin{aligned} & F \\ & G \end{aligned} \right])\)
根据拉普拉斯矩阵的性质，可知：
\(Tr(F^T\widetilde{L}_SG) = \frac{1}{2}\sum^{n+m}_{i=1}\sum^{n+m}_{j=1}||\frac{f_i}{\sqrt{d_i}}-\frac{g_i}{\sqrt{d_j}}||^2_2 S_{ij} = \sum^{n+m}_{i=1}\sum^{n+m}_{j=1}||\frac{f_i}{\sqrt{d_i}}-\frac{g_i}{\sqrt{d_j}}||^2_2 a_{ij}\)
因此原式可写作：
\(\min_{A \ge 0, A^T_i1=1} \sum^{n}_{i=1}\sum^{m}_{j=1}||\frac{f_i}{\sqrt{d_i}}-\frac{g_i}{\sqrt{d_j}}||^2_2 S_{ij} = \sum^{n+m}_{i=1}\sum^{n+m}_{j=1} (a_{ij}-z_{ij})^2 + \alpha ||\frac{f_i}{\sqrt{d_i}}-\frac{g_i}{\sqrt{d_j}}||^2_2 A_{ij}\)
设\(v_{ij}=||\frac{f_i}{\sqrt{d_i}}- \frac{g_j}{\sqrt{d_j}}||^2_2\)，原式可写作：\(\min_{A \ge 0, A^T_i1=1}||a_i-(z_i-\frac{\alpha}{2}v_i)||^2_2\)
最终的A可以通过递归计算获取

当A已被调整完成，目标就为：
\(\min_{F,G} \alpha Tr(\left[\begin{aligned} & F \\ & G \end{aligned} \right]^T\widetilde{L}_S \left[\begin{aligned} & F \\ & G \end{aligned} \right]) + Tr((\left[\begin{aligned} & F \\ & G \end{aligned} \right]-Y)^TB(\left[\begin{aligned} & F \\ & G \end{aligned} \right]-Y))\)
设\(Q=\left[\begin{aligned} & F \\ & G \end{aligned} \right], \ B_{\alpha} = \frac{B}{\alpha}\)，则原式可写作：
\(\mathcal{J}(Q)=tr(Q^T\widetilde{L}_SQ)+tr((Q-Y)^TB_{\alpha}(Q-Y))\)
\(Q^*=(\widetilde{L}_S+B_{\alpha})^{-1}B_{\alpha}Y = \left[\begin{aligned}&I_n+B_{\alpha n}&-A\Lambda^{-\frac{1}{2}}\\&-\Lambda^{-\frac{1}{2}}A^T&B_{\alpha m}+I_m\end{aligned}\right]^{-1}\left[\begin{aligned}\begin{gather*} B_{\alpha n}Y_n\\ 0\end{gather*}\end{aligned}\right]\)
设\(L_{11}=I_n+B_{\alpha n}, L_{12}=-A\Lambda^{-\frac{1}{2}},L_{21}=-\Lambda^{-\frac{1}{2}}A^T,L_{22}=B_{\alpha m}+I_m\)
最终可以获得F和G：
\(\left\{ \begin{aligned} &F = L^{-1}_{11}L_{12}(L_{22}-L_{21}L_{11}L_{12})^{-1}L_{21}L^{-1}_{11}B_{\alpha n}Y_n \\ & G = -(L_{22} - L_{21}L^{-1}_{11}L_{12})^{-1}L_{21}L^{-1}_{11}B_{\alpha n}Y_n \end{aligned} \right.\)

最终的预测结果：
\(y_{x,i}={\rm arg}\max_{j \leq c}F_{ij},\ y_{u,i}={\rm arg}\max_{j \leq c}G_{ij}\)