网络数据的无监督特征选择:一种生成式观点

sndnyangd

论文标题： Unsupervised Feature Selection on Networks: A Generative View

作者： Xiaokai Wei∗, Bokai Cao∗ and Philip S. Yu

论文链接： 链接
我在博客上的总结： 博客总结

摘要

现在的网络数据（社交网络或信息网络）， 不单纯是个图Graph，每个点还可能有若干个特性、属性。而那些对网络数据进行机器学习的任务，比如社区发现和链接预测，如果能够利用上这些附加信息，想必准确度上能得到一定提升。但这些点的属性或特征往往是高维度数据，对效率上影响比较大。

所以， 本文的目标就两个zhi：

    降   维

也就是对点的特征进行选取 (feature selection)


作者们发现 前人工作中的主要有以下两个问题：

1. 选取特征时没考虑数据的网络、图特性（存在边、连接）。
2. 网络数据没有标准的标签（label)，一般不适合监督学习的方法。但却用聚类等方法强行给标签，强行使用监督学习，准确性很差。

所以本文提出了一个特征选取方法：

1. 非监督的
2. 用生成模型（generative model)来整合连接和内容信息（即边和属性）

---------------------------------------------------------------------------------分隔图片怎么找不到了？
导论

和摘要差不多， 重复的不提。

主要思想：

       从点的所有特征中，选取重要的、关键的特征，记为 预特征（oracle features，叫圣特征、神谕特征都不好吧）

1. 对于边来说

边不是边~~~而是由两个点在预特征上的亲密度（就相似度）来决定两个点是不是该相连。

首先，非预特征对边没有影响。就像自然语言处理里肯定要把停用词过滤掉， 这种数据没有作用。
其次， 想说什么来着？忘了。

2. 对于点的属性特征来说

首先， 很多属性也是没用、没影响的，只占空间不干活。
其次， 还有很多的属性或特征 本质上是重复的。就像线性方程组消元，发现一些方程可能是另外方程的线性组合。

所以，原本比较大的点属性集合就可以用比较小的 预特征 集合来代替（还可以存在映射关系）

结论：
       可以用点的预特征集合来同时表示连接和内容信息。

---------------------------------------------------------------------------------分隔图片怎么找不到了？

于是我们就得到了一个模型， 类似于线性回归的那个线性方程的模型， 后面会写到模型具体的形式
然后，再去定义这个模型对应的：
1. 策略。 即损失函数，要优化的目标。
2. 算法。 如何进行优化。

*模型、策略、算法，机器学习三要素，《统计学习方法》的描述方法

---------------------------------------------------------------------------------分隔图片怎么找不到了？

正文
定义

Attributed Network 属性网络：G = (V; E; X)， X是n个点的D维属性、特征向量

s 是D维01向量， 1代表该位置是预特征， 0则否。
diag(s) 则是把s 拉成对角矩阵， 后面计算用得到--光点积不够用

目标是求出 预特征 集合

模型分为两部分：

1.  对连接信息建模

如之前所说：

probability of a link is determined by the oracle affinity between two nodes

所以要定义 Oracle Affinity

Oracle Affinity
dot product of oracle features of two nodes, 如下：

$$
a_{ij}=x^T_i diag(s) x_j
$$

再用某个转换函数F_g（比如sigmoid）将上面的 $a_{ij}$转成个概率值

最后， 概率值再用伯努利分布来决定边是生成还是不生成， 如下：
$$
p_{ij}=F_g(a_{ij}) \\
E_{ij} \sim Bernoulli(p_{ij})
$$

所以， 得到整个图的概率定义， 在给定 预特征 oracle features时， 整个网络的概率为：

$$
P(G|s) = \prod_{(i,j)\in E}p_{ij} \cdot \prod_{(i,j)\notin E}(1-p_{ij})
$$


最终式

把$a_{ij},F_g$代入上式， 求个-log, 化简得：

$\cal{L_G}=xxxx$

公式太长，省略~~~

---------------------------------------------------------------------------------分隔图片怎么找不到了？


2. 对内容建模
关键就是得到一个 预特征向量 和 原特征向量的映射关系。

所以可以是：（也可以使用和边相似的建模）

$$
\mu_i = F_c(diag(s)x_i) \\
x_i \sim \cal{N}(\mu_i, \sigma^2\bf{I}_D)
$$

为简便， Fc就等于左乘个 D行D列的投影矩阵 $\bf{W}$

使用以上模型的话， 那对内容的最大似然值优化 其实也就等效于 最小化误差平方和， 再加个控制项得：

$$
\cal{L}_C=||X^Tdiag(s)W - X^T||^2_F + \beta||W||^2_F
$$


---------------------------------------------------------------------------------分隔图片怎么找不到了？

3. 边和内容 二者结合
就是

$$
\min \limits_{s,b,W} \cal{L}_G + \cal{L}_C
$$

限制条件有， s向量里取值0或1，长度D，向量和=d

---------------------------------------------------------------------------------分隔图片怎么找不到了？

优化
出于优化难度，改写优化式：

$$
\begin{eqnarray}
& \min \limits_{s,b,W} & \cal{L}_G + \cal{L}_C + \lambda||s||_1 \\
& s.t. & 0 \leq s_p \leq 1, \forall p=1,...,D
\end{eqnarray}
$$

优化过程并不特殊， 貌似和SVM的优化过程SMO是一样的。

先固定W， 优化方程的s和b

再固定s和b， 优化方程的W

偏导方程就不写了。

总结
本文定义、 概念描述准确，逻辑清晰，没有太复杂的东西。
总结不太会写， 还不敢评价论文质量。

不过本文的实验部分写得比较简略~~~别的很多论文都3、5页的。本文将将一页出头。