引用本文
董飒, 刘大有, 李丽娜, 欧阳若川, 柴晓丽. 基于类传播分布的关系近邻异质性网络分类方法.吉林大学学报:工学版, 2016, 46(2): 522-527
DONG Sa, LIU Da-you, LI Li-na, OUYANG Ruo-chuan, CHAI Xiao-li. Relational neighbor algorithm based on class propagation distributions for classification in networked data with heterophily. Journal of Jilin University Engineering and Technology Edition, 2016, 46(2): 522-527  
Permissions
Copyright©2016, 吉林大学学报编辑部
版权所有.吉林大学学报编辑部
基于类传播分布的关系近邻异质性网络分类方法
董飒1, 刘大有1, 李丽娜1, 欧阳若川2, 柴晓丽3
1.吉林大学 计算机科学与技术学院,长春 130012
2.中国第一汽车集团股份有限公司 研发中心,长春 130011
3.空军航空大学 基础部计算机教研室,长春 130022
通讯作者:刘大有(1942-),男,教授,博士生导师.研究方向:人工智能,数据挖掘.E-mail:liudy@jlu.edu.cn

作者简介:董飒(1985-),女,博士研究生.研究方向:数据挖掘.E-mail:dongsa7701@163.com

基金:国家自然科学基金项目(61133011); 国家自然科学基金面上项目(61373053,61472161,61170092)
摘要

基于同质性假设的关系分类方法对异质性网络分类性能较差,针对异质性网络的分类问题提出了一种基于类传播分布的关系近邻分类方法.该方法采用二阶马尔可夫假设,分类时考虑来自未标记结点邻居的邻居的影响,并通过计算传播类别向量和传播参考向量使结点间的影响进行传递,结合松弛标注的协作推理方法不断更新分类结果直至类分布收敛.对比实验结果表明,本文方法在异质性网络分类上具有较高的分类精度.

关键词: 人工智能; 异质性网络分类; 类传播分布关系近邻分类器; 协作推理
中图分类号:TP301 文献标志码:A 文章编号:1671-5497(2016)02-0522-06
Relational neighbor algorithm based on class propagation distributions for classification in networked data with heterophily
DONG Sa1, LIU Da-you1, LI Li-na1, OUYANG Ruo-chuan2, CHAI Xiao-li3
1.College of Computer Science and Technology, Jilin University, Changchun 130012, China
2.FAW Co., Ltd., Research and Development Center, Changchun 130011, China
3.Computer Office, Aviation University of Air Force, Changchun 130022, China
Abstract

The performance of the relational classifiers based on homophily is poor for the classification in networked data with heterophily. To solve this problem, a relational neighbor algorithm based on propagation distributions is proposed for heterophilous networks. The algorithm adopts the second-order Markov assumption and considers the influence from the neighbors of the unlabeled nodes' neighbors. At the same time the algorithm propagates the influence between nodes through computing propagating class vector and propagating reference vector; and by means of combining the relaxation labeling collective inference method, the algorithm continuously updates the results until the class distributions converge. Experiment results show that the proposed algorithm performs better on the networks with heterophily.

Keyword: artificial Intelligence; heterophilous network classification; class propagating distribution relational neighbor classifier; collective inference

与传统的相互独立且均匀分布的数据实体不同, 网络数据用于建模相互关联的实体.许多针对网络数据的分类方法都是基于同质性假设的.所谓同质性(homophily)是指具有相似特征的结点趋向于彼此连接, 也可以说相互连接的实体倾向于属于相同的类别.这种简单的假设在现实世界的网络中是普遍存在的.基于同质性假设的网络分类方法利用未标记结点的直接邻居的标签来分类结点, 所以当网络数据的同质度较高时这些方法能取得较高的分类精度.然而, 当网络的同质度低, 也就是说大部分相连接的结点具有不同的类标签, 即网络为异质性(heterophily)网络时, 显然基于同质性假设的方法不能获得较高的分类精度.

本文针对异质性网络数据的分类提出了一种基于类传播分布的关系近邻分类方法.未标记结点的类别受其邻居结点的邻居的标签影响, 本文方法通过计算结点的传播类别向量和传播参考向量将邻居结点的邻居的影响传递给待标记结点, 再通过协作推理使这种影响在网络中传播, 当未标记结点的类分布达到一个稳定状态时即得到了最终分类.在6个现实网络数据集上将本文方法与其他3种方法进行比较, 实验结果表明, 该方法在异质网络分类上获得了更好的性能.

1 相关工作

分类是网络数据挖掘的主要任务之一.网络数据分类是基于网络和已标记结点的类别预测未标记结点类别的过程.网络数据中的结点表示数据实体, 连接结点的边表示实体之间的关系.结点具有标签信息用于表示实体所属的类别, 例如通过超链接互连的网页, 由引用关系相连接的科研论文等.

针对网络数据分类, Chakrabarti等[1]提出了网络贝叶斯分类器NBC, 是将贝叶斯方法应用于网络数据的一种关系分类方法.2003年, Macskassy等[2]提出的加权投票关系近邻分类器WVRN是一个简单的协作推理方法, 该方法不需要训练过程, 直接以迭代的方式计算未标记结点的类别.2003年, Lu等[3]又提出了网络链接分类器NLB, NLB首先计算特征向量, 再使用逻辑回归建立模型.2006年, Perlich等[4, 5]提出了类分布关系近邻分类器CDRN, 通过未标记结点的直接邻居计算类别向量和参考向量, 由相似度函数得到结点类别的估计概率.2007年, Macskassy等[6]再次证明了WVRN与CDRN结合松弛标注的协作推理方法的分类性能不相上下, 特别是当抽样率小于50%时相比NBC和NLB显示出了卓越的分类性能, 可作为网络分类方法的基准; 而NLB更适合抽样率大于50%的情况.这些方法都是基于同质性假设[7]的, 都是根据直接邻居的类别来预测未标记结点的类别.当网络数据的同质度高时, 这些方法可以实现精确的分类, 然而对于异质性网络这些方法的分类精度有明显的下降.2013年, Wang等[8]针对异质性网络数据分类提出了基于概率的矩阵运算方法CPD, 该方法与随机行走方法MRW[9]和WVRN方法相似, 都是以迭代的方式计算未标记结点, 实验表明该方法对异质性网络分类显示出了较好的性能.但由于该方法的矩阵运算方式以及使用邻接矩阵计算类传播分布, 当网络中结点较多时计算时间的开销非常大.

文献[10]表明, 协作推理方法在处理稀疏标记的网络分类问题上显示了优越性.网络数据的协作推理是指不同的相互关连的实体可以同时被推理.协作推理机制与关系分类器相结合, 不断地更新未标记实体的标签, 直至达到迭代次数或满足收敛条件为止.典型的协作推理方法有迭代分类[3], 吉布斯抽样[11]和松弛标注[1]方法.

2 本文方法

不同于同质性网络, 异质性网络中大部分相连接的结点具有不同的类别, 显然此时传统的关系分类方法无法取得较高的分类精度.针对这种类型的网络, 本文将类传播分布的思想应用于基于同质性假设的类分布关系近邻分类器CDRN, 使其适用于异质性网络.

在网络G中, 将已标记结点即类别已知的结点集记为VK, xi 表示结点vi 的类别取值, 也称标签, 其中xi∈ {c1, , et al., cm}, m为类别个数.向量 {P(xi=ck)}k=1m为结点vi 的类分布, 可以代表vi的类别, 其中 ∑k=1mP(xi=ck)=1。网络中已标记结点的类分布为对应已知类别位置的概率为1, 其余类别位置的概率为0的向量.网络数据的分类问题可描述为:给定G和已标记结点集VK, 找到未标记结点的类别或类分布的过程.如果结点vi 与vj 之间有边, 则wij 表示边的权重, 本文只考虑无向边(即wij=wji).

网络数据分类由于链接(表达相应结点间的关联)的存在, 结点类别分类受其邻居结点的影响.传统关系分类方法基于一阶马尔可夫假设:

P(xi|G)=P(xi|Ni)(1)

式中: Ni为结点vi的邻居集.

一阶马尔可夫假设利用结点的直接邻居的类别进行分类.本文的分类方法关注的范围扩展到邻居结点的邻居, 基本思想是:假设结点vi 和vl 是相邻结点, 当计算vi 的类别时, 首先通过vl 邻居集Nl 计算vl 的类别向量CV(vl), 来自vl 的类别向量对vi 的分类产生影响, 根据CV(vl)计算vi 的传播类别向量PCV(vi), 此时vi 的传播类别向量PCV(vi)是根据vi 邻居的邻居计算得到的.来自vi 邻居的邻居的影响通过类别向量CV(vl)进行了传播.也可以说本文方法基于二阶马尔可夫假设:

P(xi|G)=P(xi|Nl)(2)

二阶马尔可夫假设使用待分类结点邻居的邻居进行分类.最后通过计算vi 的传播类别向量PCV(vi )k 与传播参考向量PRV(ck)之间的相似度得到vi的概率分布.本文方法中分类结点vi的计算步骤如下:

首先根据Macskassy[6]的方法, 在训练过程中, 结点vl 的类别向量CV(vl)为vl 的邻居结点集Nl 中所有已标记结点vm对应各个类别的加权平均值构成的向量:

CV(vl)k=1Z∑vm∈VK⋂Nl, xm=ckwlm(3)

式中:Z=|Nl |为标准化因子; CV(vl )k 为类别向量CV(vl)的第k个位置, 且ck∈ {c1, , et al., cm}是第k个类.

训练过程中忽略Nl 中所有未标记结点, 即vm∈ VK, 则此时vm 的类分布为对应已知类别ck的概率为1, 其余概率为0的向量.

本文方法为所有已标记结点vi 定义一个m元传播类别向量PCV(vi), 该向量为vi 所有邻居结点vl 的类别向量CV(vl)对应各个类别k之概率的加权平均值构成的向量:

PCV(vi)k=1Z∑vl∈Niwil·CV(vl)k(4)

式中: Z=|Ni|为标准化因子.

本文还给出了传播参考向量PRV(c)的定义, PRV(c)也为m元向量, 向量中第k个位置PRV(ck)为所有已标记为标签ck的结点vi 的传播类别向量PCV(vi)的平均值:

PRV(ck)=1VckK∑vi∈VckKPCV(vi)k(5)

式中: VckK={vi|vi∈VK, xi=ck}。

推理过程中计算类别向量时使用了Nl 中未标记结点vm的当前估计概率即类分布, 将式(3)改写为:

CV(vl)k=1Z∑vm∈Nlwlm·P(xm=ck|Nm)(6)

最后, 未标记结点vi 被标记为标签ck 的概率P(xi=ck|Nl), 定义为该结点的传播类别向量PCV(vi)与标签ck 的传播参考向量PRV(ck)间的余弦相似度:

P(xi=ck|Nl)=sim(PCV(vi)k, PRV(ck))(7)

式中: sim为任意向量相似度函数, 标准化值落在[0, 1]范围内, 本方法使用cosine余弦相似度函数, 使用类分布中概率最大的元素对应的标签标记结点.

在协作推理过程中本文采用松弛标注方法.该方法返回不确定性, 记录未标记结点集的当前类分布, 算法在式(6)中使用这些概率.松驰标注不是每次标记一个结点后马上更新网络G, 而是冻结当前类分布, 在t+1步迭代时所有结点将根据t步迭代的类分布进行更新.实验证明, 松弛标注方法有时不能收敛, 而是在两个或更多个网络状态间震荡.所以本文采用Macskassy等[6]提出的改进方法, 在每个子迭代中执行模拟退火, 分配给结点当前类分布更多的权重, 而逐渐削弱来自其邻居的影响:

P(xi|Nl)(t+1)=β(t+1)·P(xi|Nl)(t)+(1-β(t+1))·P(xi|Nl)(t+1)(8)

式中: β0=k; β(t+1)=β(t)·α; k为0至1间的常数, 这里设为1; α为衰退常量, 设为0.99.实验证明, 当 0.9< α< 1时性能是鲁棒的, 如果 α太小将导致来自邻居的影响过快地衰退, 当已标记结点非常少时会降低性能.

本文采用以结点为中心的计算方法, 每次分类只计算一个结点, 这种方法有利于将分类系统模块化, 框架由先验计算, 关系分类方法与协作推理方法3个模块组成, 与CPD方法的矩阵运算相区别.

3 实验与结果
3.1 实验设置

令网络中已标记结点抽样比例 r从10%到90%变化.从所有结点集中进行(100´ r)%的类别分层随机抽样得到训练数据集, 测试集由抽样后的其余结点组成.分类时将没有路径到达任何训练集结点的结点剪枝, 并对每个分类方法进行10次相同的训练/测试集分割, 精度计算取10次运行结果的平均值.虽然无法像传统机器学习方法那样, 训练集和测试集可以做到不相交分割(交叉验证), 尽可能地让测试集在每次运行时不相交, 本文遵循标准的10-折交叉验证.为了叙述方便, 将本文提出的方法记为PCDRN.

3.2 实验数据

本文使用6个真实的网络来检验本文算法的性能, 包括Cora, Imdb和4个WebKB数据集中的网络.其中WebKB的4个网络包括Cornell, Texas, Washington和Wisconsin.

WebKB项目中, 结点由4所大学的网页组成, 边由网页结点之间的超链接构成.Cora是根据引用关系建立的论文引用关系网络.Imdb中结点表示电影, 结点间的边表示所连接的电影由同一个制作公司制作.实验数据的信息如表1所示.

表1 实验数据信息 Table 1 Information about experimental data

本文使用Sen[12]给出的同质度形式化定义, 即网络的同质度可以表示为每个结点的邻居结点中与其具有相同标签的邻居所占的平均百分比.因此网络的同质度为:

Homophilydegree=∑i=1N(siNi)N(9)

式中:|Ni|为结点vi 的邻居结点数; |si|为与结点vi 具有相同标签的邻居结点数; N为网络中的结点数.

用式(9)对表1中的网络数据集进行计算, 得到数据集cora, imdb, cornell, texas, washington, wisconsin相应的同质度分别为0.805 703, 0.738 337, 0.265 515, 0.165 911, 0.409 598, 0.231 258.可以看出:cora和imdb是同质性网络, 而其他4个网络的同质度非常低, 从同质性的视角, 可将它们看作异质性网络.

3.3 实验结果

本文将PCDRN方法与其他3个关系分类器在6个现实网络数据集上进行了比较, 以测试PCDRN方法的分类性能.3个基准方法分别是加权投票关系近邻分类器WVRN, 类分布关系近邻分类器CDRN和基于概率的类传播分布CPD方法.其中WVRN是不需要训练过程的简单关系分类器.CDRN是根据类别向量和参考向量的相似度来分类结点的关系分类器.WVRN和CDRN都是基于同质性假设的方法, 同时结合松弛标注的协作推理方法.CPD是基于概率的处理异质网络分类的矩阵运算关系分类器, 其采用迭代的协作推理方法.4个分类器的10-折交叉验证的平均分类精度如图1所示.

本文采用只考虑网络中链接和类标签的单变量分类方法, 实验证明仅仅是网络结构本身(链接+已标记结点标签)对于分类就包括了可观的有用信息.PCDRN在后面4个异质性网络数据集上展现了较好的性能, 特别是当r=10%时.在cora和imdb数据集上PCDRN没有明显优于其他3个分类器, 这是因为WVRN和CDRN是基于同质性假设的分类器, 他们使用未标记结点的直接邻居分类结点, 所以对于高同质度的网络cora和imdb显示了较好的性能.然而不难发现PCDRN在网络cora上性能与WVRN不相上下, 并且略优于CPD, 当r< 40%时明显优于CDRN.可以说, PCDRN不仅在异质性网络上能取得较好的性能, 在同质性网络上同样具有优势.关于后面4个异质性网络, PCDRN的分类精度大大优于WVRN和CDRN.这是因为异质性网络中大部分相互连接的结点具有不同的类别, 所以基于同质性假设的WVRN和CDRN方法的性能降低了.CPD和PCDRN摒弃了同质性假设, 所以它们的分类精度优于以上两种分类器.从图1中还可看出, 在cornell和texas数据集上PCDRN明显优于CPD, 特别是r=10%时.当r> 40%时, PCDRN在异质性网络上体现了绝对优势.实验结果表明, PCDRN对于异质性网络具有较好的分类性能.

图1 实验对比结果Fig.1 Results of comparison experiments

WVRN, CDRN和PCDRN都采用了以结点为中心的计算方法, 每次迭代过程中的循环次数与未知结点的度以及标签个数有关, 并且迭代时只对测试集中未知结点进行分类, 与CPD方法采用邻接矩阵对所有结点进行运算不同.令网络数据中结点数为N, 测试集中未知结点数为Nu, 显然N> Nu, 结点vi 的度为d(vi), 标签个数为m, 迭代次数为K.WVRN方法的时间复杂度为O(KNu d(vi)m), 最坏情况结点vi 与所有其他N-1个结点相连接, 此时时间复杂度为O(KNu (N-1)m), 即O(KNu Nm).CDRN方法由于引入了类别向量和参考向量, 故时间复杂度为O(KNu (N-1)m+m2), 即O(KNu Nm+m2).CPD方法的时间复杂度为 O(KN2m), 高于WVRN和CDRN方法, 并且邻接矩阵的存储使CPD方法的空间复杂度也高于其他3种方法.PCDRN方法采用二阶马尔可夫假设的时间复杂度为O(KNu d(vi)d(vj)m+m2), 其中vi 与vj 相邻, 故最坏情况的时间复杂度为O(KNu (N-1)2 m+m2), 即O(KNu N2 m+m2), 但一般情况下d(vi)d(vj)≪N2 .

4 结束语

现实中存在很多异质性的网络, 这种网络同质度低, 并且大部分相连接的结点具有不同的类标签.此时基于同质性假设的网络数据分类方法应用未标记结点的邻居结点的类别进行分类将得不到合理的分类结果.本文针对异质性网络提出了一种基于类传播分布的关系近邻分类方法, 实验表明此方法对异质性网络分类具有较好的性能.

The authors have declared that no competing interests exist.

参考文献
[1] Chakrabarti S, Dom B, Indyk P. Enhanced hypertext categorization using hyperlinks[C]//In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, New York, USA, 1998: 307-319. [本文引用:2]
[2] Macskassy S A, Provost F. A simple relational classifier[C]//Proceedings of the Multi-Relational Data Mining Workshop at the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003: 64-76. [本文引用:1]
[3] Lu Q, Getoor L. Link-based classification[C]//Proceedings of 12th International Conference on Machine Learning (ICML), Washington DC, 2003: 496-503. [本文引用:2]
[4] Perlich C, Provost F. Distribution-based aggregation for relational leaning with identifier attributes[J]. Machine Learning, 2006, 62(1/2): 65-105. [本文引用:1]
[5] Perlich C, Provost F. Aggregation-based feature invention and relational concept classes[C]//Proceedings of 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington DC, 2003: 167-176. [本文引用:1]
[6] Macskassy S A, Provost F. Classification in networked data: A toolkit and a univariate case study[J]. Journal of Machine Learning Research, 2007, 8: 935-983. [本文引用:3]
[7] McPherson M, Smith-Lovin L, Cook J M. Birds of a feather: homophily in social networks[J]. Annual Review of Sociology, 2001, 27: 415-444. [本文引用:1]
[8] Wang Zhen-wen, Yin Feng-jing, Tan Wen-tang, et al. Classification in networked data with heterophily[J]. The Scientific World Journal, 2013: 236769. [本文引用:1]
[9] Lin F, Cohen W W. Semi-supervised classification of network data using very few labels[C]//In Proceedings of the International Conference on Advances in Social Network Analysis and Mining, IEEE Computer Society, Washington DC, USA, 2010, 10: 192-199. [本文引用:1]
[10] 李丽娜. 基于链接的网络分类和链接预测新方法研究[D]. 长春: 吉林大学计算机科学与技术学院, 2012.
Li Li-na. Research on classification and link prediction of network data based on links[D]. Changchun: College of Computer Science and Technology, Jilin University, 2012. [本文引用:1]
[11] Geman S, Geman D. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 1984, 6: 721-741. [本文引用:1]
[12] Sen P, Namata G M, Bilgic M, et al. Eliassi-Rad. collective classication in network data[J]. AI Magazine, 2008, 29(3): 93-106. [本文引用:1]