NRL论文阅读笔记（二）

NRL paper

Learning from Labeled and Unlabeled Vertices in Networks

问题背景：只有少数结点拥有标签。如社交网络中，很多用户并不填写个人信息。
网络中的结点往往不满足i.i.d的条件，因此不适于使用LapSVM等半监督式学习的算法。
relational leanring捕捉相邻结点的信息与其彼此的关联，但如果一个结点的邻居中有太多无标签者，效果不佳。
提出一个半监督学习的框架wvGN(weighted-vote Geometric Neighbor classifier）。通过random walk捕捉结点的local和global neighborhood的信息，并由此决定结点的标签。
主要贡献：
1. 通过不同跳数的random walk（1~m，m由power iteration method隐式决定）来积累局部和全局的neighborhood information
2. 将网络中的半监督学习问题形式化为一个优化问题，并提出了一个基于L2-loss SVM的目标函数。
3. 提出gradient and coordinate descent（GCD）作为搜索策略以最优化目标函数，结合了GD和CD，不容易陷入局部最优点。

Weighted-vote Geometric Neighbor classifier
$\mathcal{N}_1$: geometric one-hop neighborhood

• class indicator score:
  $f(\mathbf{p}_q) = \mathbf{p}_q \cdot \mathbf{w^T} + \mathit{b}$
• the label of the vertex is given by:
  $y_q = \mathbf{sign}(f(\mathbf{p_q})) = \mathbf{sign}(\mathbf{p}_q \cdot \mathbf{w^T} + \mathit{b})$

上式类似SVM，但未考虑到邻居之间的相关性。故引入weighted-voted strategy来加入neighborhood information：

两个情况合并，可写为：

$\mathcal{N}^m$： Geometric m-hop Neighborhood
类似地，有：

将各阶转移矩阵累加以获得每个结点的向量表示：

为了防止所有结点的表示相同（m越大越全局），每一跳引入一个dampening factor，使得跳数越大惩罚越大。

后面的GCD没大看懂。
感觉这篇文章和network embedding关系不是特别大……