论文阅读:LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation

摘要 GCN模型是不是越复杂越好呢?这篇文章分析发现,GCN中常用的矩阵变换(feature transformation)和非线性激活函数(nonlinear activation)没有作用,甚至有反作用,据此作者提出了一个非常简单的GCN模型LightGCN,模型参数只有节点的embedding。这么简单的模型在推荐任务上,比大多数复杂模型的性能都要好,而且作者从理论分析了如此设计存在的若干好处。 简介 作者所在团队在2019年发表了一个NGCF的模型,该模型基于user和item的交互关系网络,使用GCN训练得到user和item的embedding,然后使用embedding相似度进行推荐。 简单来说,第k+1层的user和item的embedding使用如下公式计算。其中的W1是直接对embedding进行变换的矩阵,W2是对user和item点乘之后进行变换的矩阵;而σ是非线性激活函数。 以user为例,右边有两项,第一项是对user在第k层的embedding进行矩阵变换;第二项是邻居聚合。其中邻居聚合又有两项,第一项是对item的embedding进行矩阵变换;第二项是对user和item点乘之后进行矩阵变换。 作者发现,对于协同过滤任务来说,由于user和item都只有ID本身,没有很多的属性,所以并不需要复杂的矩阵变换和非线性激活函数。言下之意是,如果节点有丰富的属性信息的话,非线性变换和激活有用?感觉可以这么理解:有些属性重要,有些属性不重要,所以需要非线性激活函数进行识别?如果只有节点ID的话,ID的embedding的所有维度都是重要的,不需要非线性激活,直接线性加权聚合就行了。 然后作者对NGCF模型进行了简单的消融实验,如下表所示,NGCF就是原始的NGCF,NGCF-f、-n、-fn分别表示去掉矩阵变换W1和W2、去掉非线性激活函数σ、同时去掉W1、W2和σ。很意外的是,-f、-n、-fn居然都比原始的NGCF效果好,而且-fn效果最好。说明对于只有user和item顶点,没有属性的网络来说,不用过于复杂的矩阵变换和非线性激活,效果反而更好。 按道理NGCF的参数空间比NGCF-f大,且前者能覆盖后者(只需要把W1和W2设置成单位矩阵),为什么前者的效果反而比后者差呢?作者进一步分析了两者训练时的loss和recall曲线,发现NGCF的参数空间虽然比NGCF-f大,但其收敛后的loss更大,recall更小。也就是说训练效果反而不如NGCF-f。作者认为,加入过多的矩阵变换和非线性变换,导致模型过于复杂,难以训练到较好的效果。据此,作者提出了一个更简单的模型LightGCN,具体看下一节介绍。 方法 既然前面分析说矩阵变换和非线性激活函数会起副作用,LightGCN的方法非常简单,就是把这两个操作去掉。如公式3所示,每个节点的embedding表示直接等于其邻居的embedding的线性加权求和,既没有矩阵变换,也没有非线性激活函数,如此的简单。而且,对比公式3和公式1可知,LightGCN没有显式使用自回路,即计算某个节点的embedding的时候,只用了其邻居的embedding,没有用自己的embedding;而NGCF在公式1中使用了自回路。 其网络结构图如下: 最后,节点的最终embedding等于其各层embedding的加权求和。如公式4所示,权重系数α可以手工指定,也可以使用注意力网络来自动学习。为简便起见,本文直接设置为等权重,所有系数都等于1/(K+1),相当于所有层embedding求平均。 节点最终embedding等于各层embedding的加权求和有如下三个好处: GNN存在over-smoothing的问题,即随着网络层数越深,深层网络的输出结果趋向于相同。即所有节点的最后一层的输出有可能很接近。而如果把所有层加起来的话,能一定程度上缓解这个问题 GNN不同层捕获的语义信息不一样,使用所有层输出能增强表达能力,这个和CNN的道理是类似的。 所有层embedding求和可以捕获自回路的信息。也就是说虽然公式3没有显式使用自回路,但计算顶点最终embedding时(公式4)可以隐含自回路的信息,这个后面会给出证明。 除此之外,由于LightGCN很简单,所以也很好训练,更容易收敛,收敛效果更好。总之,虽然LightGCN很简单,但它很强大,而且有很多好处。 模型分析 接下来,作者分析了为什么LightGCN可以学习到自回路,其证明思路是这样的。另一篇工作SGCN和这篇工作很像,也做了很多简化,且显式添加了自回路。作者通过分析发现LightGCN可以表达SGCN的形式,间接说明LightGCN隐含可以考虑自回路。下面是具体的证明过程。 首先定义user和item的交互矩阵\(\mathbf{R}\in \mathbb{R}^{M\times N}\),其中M和N分别表示user和item的个数。\(\mathbf{R}_{ui}\)为1表示u和i有交互,等于0表示没有交互。则全图的邻接矩阵可以表示为公式6: 公式3的矩阵形式可以表示成公式7,其中矩阵D为度矩阵。对照下原始的GCN公式,其实就是把原始GCN的变换矩阵W和非线性激活函数σ去掉了。 由于LightGCN是将多层embedding加权求和,所以最终结果是公式8: 然后作者对SGCN的公式进行了简单的变换,发现形式上和公式8是一致的,所以LightGCN也能隐含学习到自回路特征。 此外,作者还分析了另一个模型APPNP,APPNP借鉴pagerank的思想,可以缓解GNN过深带来的over-smoothing问题。然后作者如法炮制,对APPNP的公式进行变换,发现也和公式8等价,所以LightGCN也能缓解GNN的over-smoothing问题。其实这个从LightGCN不只使用最后一层,而是使用所有层embedding就能得到这个结论,不需要这么大费周章证明。 实验 最后是实验环节。作者将LightGCN和本文开头提到的NGCF进行了对比,实验结果表明,LightGCN的性能相比NGCF有显著提升,而且比NGCF-fn也高。作者提到,虽然NGCF-fn已经去掉了矩阵变换和非线性激活函数,但NGCF-fn仍然还有自回路、user和item的点积、dropout等等,还是比较复杂,不好训练。而LightGCN非常简单,只有embedding和邻居的线性加权,所以LightGCN还是比NGCF-fn好。真的很神奇啊,照这个说法,难道连dropout也会起副作用? 此外,在消融实验中,作者还对比了LightGCN和LightGCN-single,LightGCN-single是只用LightGCN的最后一层作为节点的embedding。作者发现,当网络层数增大到4层时,LightGCN-single性能显著下降,出现了over-smoothing的问题。而LightGCN由于多层组合的操作,不会有over-smoothing的问题。考虑到性能和收益,LightGCN使用了3层神经网络。 评价 结果有些意外,LightGCN这么简单的模型,效果居然比复杂模型还要好?感觉即使是NGCF,模型也不复杂啊,和CV、NLP那些大模型相比简单多了,怎么就训练不好了呢?难道是GNN特有的现象? 感觉和数据有关,本文测试的数据是只包含user和item顶点,顶点没有属性。如果是属性图的话,也许结论会有变化。 不过至少提供了调参的思路:去掉矩阵变换、去掉非线性激活函数、甚至是去掉dropout。。。另外重要的一点是,不要只用最后一层的embedding,而是组合所有层的embedding进行加权求和。 另外,本文开篇提到的NGCF和本文是同一批作者,自己批判自己一年前发表的工作,不免让人担心这篇工作的可靠性。。。以及当时的NGCF难道没有做本文开篇的消融实验吗?难道不应该吗?

May 8, 2022 · 1 min

和我一起构建搜索引擎(五)推荐阅读

虽然主要的检索功能实现了,但是我们还需要一个“推荐阅读”的功能。当用户浏览某条具体新闻时,我们在页面底端给出5条和该新闻相关的新闻,也就是一个最简单的推荐系统。 搜狐新闻“相关新闻”模块 推荐模块的思路是度量两两新闻之间的相似度,取相似度最高的前5篇新闻作为推荐阅读的新闻。 我们前面讲过,一篇文档可以用一个向量表示,向量中的每个值是不同词项t在该文档d中的词频tf。但是一篇较短的文档(如新闻)的关键词并不多,所以我们可以提取每篇新闻的关键词,用这些关键词的tfidf值构成文档的向量表示,这样能够大大减少相似度计算量,同时保持较好的推荐效果。 jieba分词组件自带关键词提取功能,并能返回关键词的tfidf值。所以对每篇新闻,我们先提取tfidf得分最高的前25个关键词,用这25个关键词的tfidf值作为文档的向量表示。由此能够得到一个1000*m的文档词项矩阵M,矩阵每行表示一个文档,每列表示一个词项,m为1000个文档的所有互异的关键词(大概10000个)。矩阵M当然也是稀疏矩阵。 得到文档词项矩阵M之后,我们利用sklearn的pairwise_distances函数计算M中行向量之间的cosine相似度,对每个文档,得到与其最相似的前5篇新闻id,并把结果写入数据库。 推荐阅读模块的代码如下: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 # -*- coding: utf-8 -*- """ Created on Wed Dec 23 14:06:10 2015 @author: bitjoy.net """ from os import listdir import xml.etree.ElementTree as ET import jieba import jieba.analyse import sqlite3 import configparser from datetime import * import math import pandas as pd import numpy as np from sklearn.metrics import pairwise_distances class RecommendationModule: stop_words = set() k_nearest = [] config_path = '' config_encoding = '' doc_dir_path = '' doc_encoding = '' stop_words_path = '' stop_words_encoding = '' idf_path = '' db_path = '' def __init__(self, config_path, config_encoding): self.config_path = config_path self.config_encoding = config_encoding config = configparser.ConfigParser() config.read(config_path, config_encoding) self.doc_dir_path = config['DEFAULT']['doc_dir_path'] self.doc_encoding = config['DEFAULT']['doc_encoding'] self.stop_words_path = config['DEFAULT']['stop_words_path'] self.stop_words_encoding = config['DEFAULT']['stop_words_encoding'] self.idf_path = config['DEFAULT']['idf_path'] self.db_path = config['DEFAULT']['db_path'] f = open(self.stop_words_path, encoding = self.stop_words_encoding) words = f.read() self.stop_words = set(words.split('\n')) def write_k_nearest_matrix_to_db(self): conn = sqlite3.connect(self.db_path) c = conn.cursor() c.execute("'DROP TABLE IF EXISTS knearest'") c.execute("'CREATE TABLE knearest(id INTEGER PRIMARY KEY, first INTEGER, second INTEGER, third INTEGER, fourth INTEGER, fifth INTEGER)'") for docid, doclist in self.k_nearest: c.execute("INSERT INTO knearest VALUES (?, ?, ?, ?, ?, ?)", tuple([docid] + doclist)) conn.commit() conn.close() def is_number(self, s): try: float(s) return True except ValueError: return False def construct_dt_matrix(self, files, topK = 200): jieba.analyse.set_stop_words(self.stop_words_path) jieba.analyse.set_idf_path(self.idf_path) M = len(files) N = 1 terms = {} dt = [] for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text docid = int(root.find('id').text) tags = jieba.analyse.extract_tags(title + '。' + body, topK=topK, withWeight=True) #tags = jieba.analyse.extract_tags(title, topK=topK, withWeight=True) cleaned_dict = {} for word, tfidf in tags: word = word.strip().lower() if word == '' or self.is_number(word): continue cleaned_dict[word] = tfidf if word not in terms: terms[word] = N N += 1 dt.append([docid, cleaned_dict]) dt_matrix = [[0 for i in range(N)] for j in range(M)] i =0 for docid, t_tfidf in dt: dt_matrix[i][0] = docid for term, tfidf in t_tfidf.items(): dt_matrix[i][terms[term]] = tfidf i += 1 dt_matrix = pd.DataFrame(dt_matrix) dt_matrix.index = dt_matrix[0] print('dt_matrix shape:(%d %d)'%(dt_matrix.shape)) return dt_matrix def construct_k_nearest_matrix(self, dt_matrix, k): tmp = np.array(1 – pairwise_distances(dt_matrix[dt_matrix.columns[1:]], metric = "cosine")) similarity_matrix = pd.DataFrame(tmp, index = dt_matrix.index.tolist(), columns = dt_matrix.index.tolist()) for i in similarity_matrix.index: tmp = [int(i),[]] j = 0 while j <= k: max_col = similarity_matrix.loc[i].idxmax(axis = 1) similarity_matrix.loc[i][max_col] = -1 if max_col != i: tmp[1].append(int(max_col)) #max column name j += 1 self.k_nearest.append(tmp) def gen_idf_file(self): files = listdir(self.doc_dir_path) n = float(len(files)) idf = {} for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text seg_list = jieba.lcut(title + '。' + body, cut_all=False) seg_list = set(seg_list) – self.stop_words for word in seg_list: word = word.strip().lower() if word == '' or self.is_number(word): continue if word not in idf: idf[word] = 1 else: idf[word] = idf[word] + 1 idf_file = open(self.idf_path, 'w', encoding = 'utf-8') for word, df in idf.items(): idf_file.write('%s %.9f\n'%(word, math.log(n / df))) idf_file.close() def find_k_nearest(self, k, topK): self.gen_idf_file() files = listdir(self.doc_dir_path) dt_matrix = self.construct_dt_matrix(files, topK) self.construct_k_nearest_matrix(dt_matrix, k) self.write_k_nearest_matrix_to_db() if __name__ == "__main__": print('—–start time: %s—–'%(datetime.today())) rm = RecommendationModule('../config.ini', 'utf-8') rm.find_k_nearest(5, 25) print('—–finish time: %s—–'%(datetime.today())) 这个模块的代码量最多,主要原因是需要构建文档词项矩阵,并且计算k邻居矩阵。矩阵数据结构的设计需要特别注意,否则会严重影响系统的效率。我刚开始把任务都扔给了pandas.DataFrame,后来发现当两个文档向量合并时,需要join连接操作,当数据量很大时,非常耗时,所以改成了先用python原始的list存储,最后一次性构造一个完整的pandas.DataFrame,速度比之前快了不少。 ...

January 9, 2016 · 4 min