软件学报ISSN 1000 - 9825, CODEN RUXUEW  Journal of Software,  [doi: 10.13328/j.cnki.jos.00 5928] © 中国科学院软件研究所版权所有.   面向推荐系统的图卷积网络* 葛   尧,    陈松灿 ( 南京航空航天大学  计算机科学与技术学院,   江苏  南京  2通讯作者:  陈松灿,   E - mail:  s.chen@nuaa .edu.cn   摘要:     图卷积网络是一种针对图信号的深度学习模型可视为图信号的链接预测问题,因此近年来提出了使用品间的异质顶点交互和用户(或商品) 内部的同质顶点交互行, 要么仅在同质顶点间进行, 留下了提升此类推荐系统卷积网络的推荐算法,使用两组图卷积操作同时利用两种不同的交互信息中存在的连接信息, 同质顶点卷积用于使相似顶点具有相近表示精度. 关键词:  图卷积网络;图信号;几何深度学习;神经网络中图法分类号:   TP3 9 1  中文引用格式:  葛尧, 陈松灿. 面向推荐系统的图卷积网络. 软件学报英文引用格式:  Ge  Y,  Chen  SC.   Graph  Convolutional  Network  for  Recommender  SystemsSoftware, 2020  (in Chinese).  http://www.jos.org.cn/1000- 9825/Graph Convolutional Network for Recommender SystemsGE Yao,  CHEN Song- Can (College   of Computer  Science and Technology, Nanjing  UniversityAbstract :   Graph convolutional network (GCN) is a deep learning moapplications due to its   powerful ability of feature extraction. As the recommendation problem can be viewed as link prediction of graph signals,  recently  several GCN based methods have been proposed for recommender systeminteraction s , with one representing interaction s   between users and items and the otherHowever, existing methods f ocus on either heterogeneous  or homogeneousIn this paper, we propose a new GCN based recommendation algorithm to jointly utilizheterogeneous  convolutional  operator  is  used  to  mine  information  from  the  spectrum  of  userconvolutional operator is used   to   enforce  similar   vertices  to   be similarshow that our new method   achieves better performance compared with several stateKey words:   graph convolutional network ;   graph signal;   geometric deep learning卷积神经网络( convolutional neural nework, 简称自然语言处理等领域得到了极大关注[2 , 3]. 文本、图像和视频对应地视为分布在1 维、2 维和3 维网格支撑集上. CNN中, 除这些规则网格数据之外, 还存在一类重要的称为                                                                 *   基金项目:  国家自然科学基金( 61672281, 61732006 ) Foundation item: National Natural Science Foundation of China  收稿时间: 2019 -05-31;  修改时间: 2019 -07- 29;  采用时间: 2019   E - mail: jos@iscas.ac.cn   http://www.jos.org.cn    Tel: +86-10-62562563 2 11106 ) 图卷积网络是一种针对图信号的深度学习模型, 由于具有强大的特征表征能力得到了广泛应用. 推荐系统因此近年来提出了使用图卷积网络解决推荐问题的方法.推荐系统中存在用户与商顶点交互, 然而, 现有方法中的图卷积操作要么仅在异质顶点间进推荐系统性能的空间. 考虑到这一问题, 本文提出了一种新的基于图同时利用两种不同的交互信息,其中异质顶点卷积用于挖掘交互图谱域用于使相似顶点具有相近表示. 实验结果验证了本文算法比现有算法具有更优的神经网络;推荐系统 软件学报.   http://www.jos.org.cn/1000- 9825/5928.htm  Graph  Convolutional  Network  for  Recommender  Systems.  Ruan  Jian  Xue  Bao/ Journal  of 9825/5928.htm  Graph Convolutional Network for Recommender Systems University  of Aeronautics and Astronautics, Nanjing 211106, China)  Graph convolutional network (GCN) is a deep learning model for graph signal processing   and  has been used in many real- world powerful ability of feature extraction. As the recommendation problem can be viewed as link prediction of graph roposed for recommender system s .   A recommender system involves two kinds of sers and items and the other  representing interaction s   among users ( or items). or homogeneous   inte ractions  only, thus their modeling expressiveness is limited. In this paper, we propose a new GCN based recommendation algorithm to jointly utiliz e these two types of interactions . Specifically, a ation  from  the  spectrum  of  user -item  graphs,  while  a  homogeneous similar   in the hidden space . Finally, our experiments on benchmark da tasets achieves better performance compared with several state -of -the-art methods. geometric deep learning;   neural network;  recommender system  简称CNN)[1]具有强大的特征表征能力, 因而在诸如计算机视觉、图像和视频均是定义在规则网格( regular grid)上的数据, 它们能CNN能方便地运算可归因于这些网格的规则性. 然而, 现实称为图信号( graph siganl)[4]的数据( 下称图信号) , 它分布或定义Foundation item: National Natural Science Foundation of China   ( 61672281, 61732006 )  : 2019 -09-20; jos 在线出版时间: 2020 -01-10 网络出版时间：2020-01-14 09:53:29网络出版地址：http://kns.cnki.net/kcms/detail/11.2560.TP.20200114.0953.013.html   2  Journal of Software 软件学报  在不规则网格( irregular grid) 支撑集上. 针对图信号的深度学习又称几何深度学习( geometric deep learning)[5]. 一方面, 图信号可视为图及其顶点上的信号集合; 另一方面, 图信号也可视为一组非独立同分布的数据点, 是一类非传统型数据, 它们之间的关系用图的链接表示. 如何将传统CNN推广到能处理更复杂的图信号的卷积网络,即图卷积网络( graph  convolutional  network, 简称GCN), 利用其强大的特征表征能力提升学习效果, 正得到越来越多关注.  目前已有许多工作围绕G CN 展开研究并在理论和应用上取得了丰富成果[6 - 13, 24- 26]. 将一个问题用图信号刻画后, 就可根据问题特点设计相应G CN 来解决. 学者网络[8]、社交网络[11]、分子活性预测[12]和推荐系统[13]都是G CN 的典型应用场景. 具体到推荐系统, 涉及的用户和商品可视为图顶点, 用户对商品的评分可视为边( 链接), 而用户和商品特征视为分布在顶点集( 图) 上的信号, 如此推荐问题便转化为图的链接预测问题. 值得注意的是, 推荐系统中存在两种图: 一种是异质顶点交互图, 反映用户对商品的行为, 例如评分、购买等; 另一种是同质顶点交互图, 反映用户( 商品) 间相似性, 例如朋友关系、商品特征相似等. 两种图都包含部分信息, 兼顾两者以实现信息互助对推荐系统至关重要. 然而, 现有基于G CN 的推荐系统要么仅关注异质图, 要么仅关注同质图, 缺少联合利用两者的统一框架, 由此为我们留下了深入利用图提升推荐性能的空间. 因此, 本文目的就是提出能统一利用此两种图的G CN, 通过它们的互惠互利提升推荐效果. 下面首先介绍现有的两类方法.  异质顶点交互GCN 类方法( H etero- GCN)在异质顶点间进行图卷积操作. 将m 个用户对n 个商品的评分视为一个( m+n ) × ( m+n ) 的二部图, 此类方法重点挖掘交互图谱域中蕴含的连接信息, 使用GCN 直接从二部图中提取特征.   GC- MC[14]和SpectralCF[15]是两种代表方法, 两者都以顶点特征为信号, 以评分信息为图进行图卷积操作. 此类方法仅使用异质顶点交互信息, 忽略了顶点相似性信息, 在评分过少时会遇到冷启动( cold start)问题.  同质顶点交互G CN 类方法( H omo - GCN)在同质顶点间进行图卷积操作. 将m 个用户对n 个商品的评分视为一个m × n 的矩阵, 使用评分或特征信息构建m × m 的行图( row  graphs)和n × n 的列图( column  graphs) , 分别代表用户和商品相似度. 此类方法认为相似用户( 商品) 的表示向量应当相近, 因此在相似的同质顶点间进行图卷积使其信号平滑.   RGCNN[16]和GCMC - BEP[17]是两种代表方法, 两者都从评分矩阵获取初始特征, 分别在行图和列图上进行图卷积获取新特征表示. 此类方法将评分信息视为提供特征的矩阵, 没有将其视为图, 使评分图中蕴含的连接信息未能得到利用.  本文第1 节介绍Hetero - GCN框架及代表方法; 第2 节介绍Homo- GCN框架及代表方法; 第3 节提出一种联合利用异质与同质交互信息的GCN推荐算法; 第4 节在真实数据集上进行实验, 验证了本文方法优于现有方法; 最后总结全文, 并对未来工作进行展望.  1     H etero-G CN 1.1     模型框架 设m 个用户对n 件商品的评分矩阵为 ∈  × , 评分取值范围为{ 1,2,…, L } , 用户和商品特征为 ∈  × 

V维度设为2 00,  -jk和- 维度设为6 4 , 顶点信号dropout概率设为0 .7 , 激活函数选用R eLU ( ∙) . 使用Adam 优化器[23], 学习率为0 .01.对MovieLens, 顶点特征不进行d ropout , 运行1000轮迭代; 对其他3 个数据集, 顶点特征dropout概率设为0 .7 , 运行2 00轮迭代. 参照文献[14]建议, 在参数学习过程中加入衰减因子0 .995 的指数移动平均.  对比方法选取异质交互类算法G C - MC[14], 同质交互类算法R GCNN[16]、GCNCF[24], 并选取矩阵补全M C[20],几何矩阵补全G MC[21], 交替最小二乘几何矩阵补全G RALS[22]等算法作为参照. 此外还设置两种G CN4RS变种进行比对分析, 其中G CN4RS- hetero 仅进行异质顶点卷积, GCN4RS - homo 仅进行同质顶点卷积.  评价指标采用R MSE:   RMSE = —1\("#− ["#)˜" a ` ( 22)  其中,   n 为测试样本数量,   "# 和["# 分别代表第i 个样本的真实和预测评分. 实验中对算法随机初始化并运行5次, RMSE 取5 次的平均值.     葛尧  等:面向推荐系统的图卷积网络 4.2     实验结果 4.2.1    参数选取 如4 .1 节所述, 为使用同质交互信息, 需对四个数据集分别构建同质交互图交互图阈值K 的选取. 本小节通过实验说明预测误差和训练时间一种在兼顾效果和效率的情况下选取最佳K 值的方法Fig. 4  Selection of threshold 图4 由图4 可知, 随着K 的增加, 预测误差先降后增, 训练时间不断减少被加入同质交互图中, 一方面会引入噪声使效果下降同质交互图中的链接变少, 训练加快, 但同质交互信息不足预测误差和训练时间在K 增加过程中均存在斜率突变的拐点低; 在拐点右侧, 预测误差开始增加, 训练时间继续减少拐点左侧, 预测误差过大, 不应选取这样的K ; 在拐点右侧点横坐标值作为K . 本文为Flixster, Douban, YahooMusic4.2.2    结果与分析 实验结果汇总见表3 . 所有对比方法均采用对应文献MovieL ens 数据集上进行实验, 故未汇报结果.  其中,   MC、G MC和G RALS 属于矩阵补全类算法和G CN4RS- hetero 属于异质交互G CN类算法,   RGCNN9   需对四个数据集分别构建同质交互图 和
, 构建过程中涉及到同质误差和训练时间( 每轮迭代耗时) 随阈值K 的变化情况, 并给出的方法. K 值对GCN4 RS效果和效率的影响见图4 .    Selection of threshold K  4  阈值K 的选取  训练时间不断减少. 这是因为若K 过小,   一些不置信的链接引入噪声使效果下降, 另一方面会大幅增加计算量而影响训练速度. 若K 过大,同质交互信息不足, 算法效果下降.  增加过程中均存在斜率突变的拐点. 在拐点左侧, 预测误差和训练时间都快速降继续减少, 但速度远低于拐点左侧. 可依据拐点位置选择阈值K : 在在拐点右侧, 可权衡效果和效率后选择最合适的K , 也可直接选取拐Flixster, Douban, YahooMusic 和MovieLens 数据集分别选取5 , 15, 2, 30 作为阈值K .  文献中的默认参数设置.   GCNCF 结果取自文献[24], 其未在属于矩阵补全类算法, 其余算法均属于G CN类算法.   GCN类算法中,   GC- MCRGCNN、G CNCF 和G CN4RS- homo 属于同质交互G CN类算   10 Journal of Software 软件学报  法.   GCN4RS 是本文算法, 统一利用异质与同质信息. 我们将对比各类算法效果, 并给出相应理论分析.   Table  3   Experimental  results   ↓  表3  实验结果↓    F lixster   D ouban   YahooMusic   M ovieLens  M C[20]  1 .428   0 .902   4 4.2  0 .973  G MC[21]  1 .411   0 .878   4 0.4  0 .996  G RALS[22]  1 .245   0 .833   3 8.0  0 .945  G C - MC[14]  0 .917   0 .734   2 0.5  0 .905  R GCNN[16]  0 .926   0 .801   2 2.4  0 .929  G CNCF[24]  0 .903   0 .729   1 9.0  -  GCN4RS -hetero   0 .890   0 .730   1 9.2  0 .897  GCN4RS -homo  0 .941   0 .814   1 9 . 0   0 .953  GCN4RS   0.883  0.728  18.7   0.895  我们的算法G CN4RS在4 个数据集上都取得了最优结果. 此外, 由实验结果可得如下结论:  (1)  矩阵补全类算法M C, GMC, GRALS的效果显著差于G CN类算法. 矩阵补全类算法将用户与商品的交互视为矩阵, 重点挖掘线性相关与低秩信息;   GCN类算法重点挖掘交互图中的信息. 图相比于矩阵可刻画更多信息, 例如链接刻画相邻顶点间的联系, 拉普拉斯矩阵刻画图所有顶点间的整体联系, 链接密度刻画图中社区结构. 正是由于图具有矩阵无法比拟的强大表示能力,   GCN类算法效果显著优于矩阵补全类算法, 这印证了3.4 的结论.  (2)  异质交互类算法和同质交互类算法的效果是可比的. 两类算法采用不同的图卷积方式, 但两者都将推荐系统建模成图信号, 区别仅在于图信号的各成分指代的信息不同. 虽然同质交互类算法将评分信息视为矩阵而不是图, 但评分信息会以顶点信号的形式参与同质图上的图卷积运算, 使此类方法依然能受益于图的强大表示能力.  (3)  除YahooMusic 外, GCN4RS- hete ro 在其他数据集上效果均显著优于G CN4RS- homo. 这是因为GCN4RS - homo 完全未利用评分信息, 而评分信息恰为推荐系统的核心.   GCN4RS- hetero 能很好地利用评分信息, 但忽略了顶点相似性, 相比于G CN4RS- hetero ,   G CN4RS提升部分就来自对顶点相似性信息的利用.   YahooMusic数据集的特点是评分密度很低( 见表2 ) , 即异质交互信息很少,   GCN4RS- hetero无充足的异质交互信息可用, 反而丢失了同质交互信息, 故G CN4RS- hetero 在此数据集上效果略差于G CN4RS- homo.  (4)  G CN4RS效果优于异质交互类和同质交互类算法. 相比于异质交互类算法,   GCN4RS 利用了顶点间的相似性信息, 使相似顶点具有相近的嵌入向量表示, 在进行推荐时, 相似顶点更可能产生相近的行为, 这符合推荐系统基本假设; 相比于同质交互类算法,   GCN4RS 用图而不是矩阵刻画评分信息, 能更好地利用交互图谱域中蕴含的深层次的连接信息, 不再局限于观测到的链接.  5     总结与展望 本文解决的问题是如何为推荐系统设计更合理的图卷积网络算法. 首先根据信息利用方式不同, 将现有基于图卷积网络的推荐算法分类为异质顶点交互算法和同质顶点交互算法, 而两类方法都忽略了两者间的互助.正是为了两者互惠互利, 本文提出了一种联合利用异质和同质交互图的图卷积网络算法. 真实数据集上的实验结果表明, 本文方法具有比现有方法更优的性能.  未来的改进方向将是更合理地在图卷积操作中利用边权信息展开.   GCN4RS 为每一级评分构建一个交互图, 独立地利用这些交互图, 最后将各个交互图上的信息融合并利用. 然而, 评分间存在有序关系, 即5   >  4  >  3  >    葛尧  等:面向推荐系统的图卷积网络  11   2  >  1 , 不同评分的交互图实际是存在关联的, 忽略此类关系会造成推荐性能下降. 因此, 未来的工作应当探索如何在G CN4RS中嵌入评分有序信息, 可考虑借助有序回归( ordinal regression) 等模型进行改进.  此外, 在实际生产环境中, 如何对图卷积操作进行改进, 使其能适应大规模图也是值得探索的问题.  GCN4RS 中的图卷积采用基于矩阵乘法的谱域卷积, 虽然能有效挖掘图谱域中的信息, 但在内存受限时难以进行运算. 可考虑的改进方向是选用基于采样- 聚合的卷积操作, 进行分批次的、分布式的运算.  References :  [1]     LeCun Y, Bottou L, Bengio Y, et al. Gradient- based learning applied to document recognition. Proceedings of the IEEE,   1998, 86(11): 2278-2324. [2]     LeCun Y, Kavukcuoglu K, Farabet C . Convolutional networks   and applications in vision. Proceedings of 2010 IEEE International Symposium on Circuits and Systems,  IEEE, 2010: 253 - 256.  [3]     Dos Santos C, Gatti M. Deep convolutional neural networks for sentiment analysis of short text.   Proceedings of COLING 2014, the 25th International Conference on Computationa l Linguistics: Technical Papers,  2014: 69 - 78. [4]     Shuman D I, Narang S K, Frossard P, et al. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 2013, 30(3):83 - 98. [5]     Bronstein  M  M,  Bruna  J,  Lecun  Y,  et  al.  Geometric  Deep  Learning:  Going  be yond  Euclidean  data .  IEEE  Signal  Processing Magazine, 2017, 34(4):18- 42. [6]     Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally c onnected networks on graphs. International Conference on Learning Representations ,   2014. [7]     Defferrard  M,  Bresson  X,  Vandergheynst  P.  Convolutional  neural  networks  on  graphs  with  fast  localized  spectral  filtering. Advan ces in neural information processing syste ms,  2016: 3844 -3852. [8]     Kipf T N, Welling  M. Semi-supervised classification with   graph convolutional  networks .  International  Conference   on Learning Representations, 2017.  [9]     Henaff M, Bruna J, LeCun Y. Deep convolutional   networks   on graph -structured data. arXiv preprint arXiv:1506.05163, 2015. [10]     Niepert  M,  Ahmed  M,  Kutzkov  K.  Learning  convolutional   neural  networks  for  graphs.  International  conference  on  machine learning,   2016: 2014 -2023. [11]     Chen  J,  Ma  T,  Xiao  C.  FastGCN:  Fast  Learning  with  Graph  Convolutional  Netwo rks  via  Importance  Sampling.   International Conference on L earning Representations,  2018. [12]     Hechtlinger Y, Chakravarti P, Qin J. A generalization of convolutional neural netw orks to graph -structured data. arXiv  preprint arXiv:1704.08165, 2017. [13]     Ying R, He R, Chen K, et al. Graph convolutional neural networks for we b - scale recommender systems. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2018: 974-983.  [14]     Berg   R, Kipf T N, Welling M. Graph convolutional matrix completion . arXiv preprint arXiv:1706.02263, 2017. [15]     Zheng  L,  Lu  C  T,  Jiang  F,  et  al.  Spectral  collaborative  filtering.  Proceedings  of  the  12th  ACM  Co nference  on  Recommender Systems,   ACM, 2018: 311- 319.  [16]     Mon ti F, Bronstein M, Bresson X. Geometric matrix completion with recurrent multi-graph neural networks.  Advances in Neural Information Processing Systems,   2017: 3697 -3707. [17]     Wu Y, Liu H, Yang Y. Graph Convolutional Matrix Completion for Bipartite Edge Predicti on. International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management (KDIR),   2018: 51 -60. [18]     Hammond  D  K,  Vandergheynst  P,  Gribonval  R.  Wavelets  on  graphs  via  spectral  graph theory .  Applied  and  Computational Harmonic Analysis, 2011, 30(2): 129-150.  [19]     Hinton G E, Salakhutdinov R R. Reducing the dimensionality  of data with neural networks . science, 2006, 313(5786): 504-507.  [20]     Candès E J, Recht B. Exact matrix compl etion via convex optimization . Foundations of Computational  mathematics, 2009, 9(6): 717.  [21]     Kalofolias V, Bresson X, Bronstein M, et al. Matrix completion on graphs . arXiv preprint arXiv:1408.1717, 2014.     12 Journal of Software 软件学报  [22]     Rao N, Yu H F, Ravikumar P K, et al. Collaborative filtering with graph information: Consistency and scalable meth ods.  Advances in neural   information processing systems,   2015: 2107 -2115. [23]     Kingma D P, Ba J. Adam: A method for stochastic optimization . arXiv preprint arXiv:1412.6980, 2014.  [24]     Jiang Y.  I nformation Fusion Recommendation based on Convolutional Graph and Neural  Collaborative Filtering. Jilin University, 2018.  (in Chinese with English abstract).  [25]     Q u Q, Yu HT, Huang RY. Spammer detection technology of social network   based on graph convolution network.   Chinese Journal of Network and Information Security,  2018,4(05):39 -46.  (in Chinese with English abstract).  [26]     C ai  XD,  Wang  M,  Liang  XX,  Chen  Y.  Community  detection  method  based  on  graph  convolutional  network  via  importance sampling. Journal of Zhejiang University (Engineering Science),  2019(03):1 - 6 .  (in Chinese with Englis h abstract).  附中文参考文献:  [ 24]  江原. 基于图卷积与神经协同过滤的融合信息推荐模型. 吉林大学,   2018. [25]  曲强, 于洪涛, 黄瑞阳. 基于图卷积网络的社交网络Spammer 检测技术. 网络与信息安全学报,   2018,4(05):39 -46. [26]  蔡晓东, 王萌, 梁晓曦, 陈昀. 基于重要性抽样的图卷积社团发现方法. 浙江大学学报( 工学版) ,  2019(03):1 -6 .