Category Archives: 0和1

《Inductive Representation Learning on Large Graphs》阅读笔记

摘要

大规模图网络的节点嵌入对很多任务有很重要的作用,比如在推荐系统领域、蛋白质网络研究领域等。然而,目前大多数节点嵌入方法要求所有节点都在训练集中,且难以泛化到未见过的新节点上,这些方法称为直推式(transductive)方法。本文提出了一个归纳式(inductive)的节点嵌入方法GraphSAGE,它利用节点属性生成未见过节点的embedding。GraphSAGE并不直接训练节点embedding本身,而是训练生成embedding的函数,这个函数通过采样并聚合节点邻居的特征来生成自身节点的embedding。在三个数据集上的实验结果表明,GraphSAGE的性能显著强于其他方法。

Continue reading

CS224W(1.14)Lecture 2. Traditional Methods for ML on Graphs-针对图的特征工程方法

针对图的特征工程方法主要是核方法(Kernel methods),这里的核方法和SVM中的核方法是一个意思,都是把特征映射到高维空间,在高维空间的特征交互可以用低维空间的核矩阵来表示。

图上的核方法的核心思想是bag-of-words,即统计不同子图(相当于words)的个数,比如下图子图4中是统计不同度的节点的个数,则这里度为k的节点就是一个不同的word,最后得到bag-of-words向量,比如[1,2,1]。前面介绍针对节点的特征工程时,其中的GDV向量本质上是bag of graphlets。

在介绍针对图的特征工程方法时,会介绍两种核方法:Graphlet Kernel和Weisfeiler-Lehman Kernel。

Continue reading

CS224W(1.14)Lecture 2. Traditional Methods for ML on Graphs-针对边的特征工程方法

针对边<A,B>的特征工程方法,固然可以把节点A和B的节点特征concat起来作为边<A,B>的特征,但是丢失了很多边特有的信息,效果不一定好。专门针对边设计的特征工程方法有三个,下面分别介绍:

  • 基于距离的特征(Distance-based feature)
  • 局部邻居重叠比例(Local neighborhood overlap)
  • 全局邻居重叠比例(Global neighborhood overlap)
Continue reading

CS224W(1.14)Lecture 2. Traditional Methods for ML on Graphs-针对节点的特征工程方法

前言

这节课主要介绍传统的图机器学习方法。传统方法主要分为两步,第一步人工设计特征,第二步使用各种机器学习方法进行预测。因此,特征工程在传统图机器学习方法中有很重要的地位。本节课主要介绍图上的特征工程方法,分别介绍针对节点(node-level)、边(link-level)和图(graph-level)的特征工程方法。

Continue reading

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

摘要

GCN模型是不是越复杂越好呢?这篇文章分析发现,GCN中常用的矩阵变换(feature transformation)和非线性激活函数(nonlinear activation)没有作用,甚至有反作用,据此作者提出了一个非常简单的GCN模型LightGCN,模型参数只有节点的embedding。这么简单的模型在推荐任务上,比大多数复杂模型的性能都要好,而且作者从理论分析了如此设计存在的若干好处。

Continue reading

《Fluent Python 2nd》代码示例1-1扑克牌类:如何让自定义类像内置类型

今天开始学习《Fluent Python 2nd》,Python进阶好书。第二版今年3月份刚刚出版,以最新Python 3.10为基础进行介绍。

第一个案例是Python风格的扑克牌类:

短短几行代码,包含了Python很多有趣的特性,咱们一一道来。

Continue reading

《DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs》论文阅读

前言

工业界的图规模都非常大,少说也是上千万的顶点+上亿的边,单机训练不现实,必须借助多机分布式训练。然而目前主流的图训练框架PyG、DGL对图的多机分布式训练支持都不太好。工业界好像阿里的Euler、百度的PGL可以支持分布式训练。今天介绍一下亚马逊DGL针对分布式训练所做的优化。

摘要

GNN广泛应用在推荐、搜索、风控等领域,在这些领域,图的规模往往非常大,有数以亿计的顶点和万亿的边。为支持大规模图的分布式训练,本文提出了DistDGL,它能以mini-batch的方式在多机上进行分布式训练。DistDGL基于DGL框架,它将图数据分布在多台机器上,并基于数据分布,将计算也分布在多台机器上(owner-compute rule)。DistDGL以同步更新的方式进行训练。为了减小分布式训练的通信开销,DistDGL使用一个高效、轻量的图分割算法对图进行分割,在分割时设计了多个负载均衡约束,使得每个分割的子图达到较好的负载均衡。此外,为了减小跨机器的通信,DistDGL在每个子图中保留了halo nodes(正文会介绍到),并且使用了稀疏embedding更新策略。这些优化策略使得DistDGL在分布式训练时能达到较好的高并行效率和内存可扩展性。实验结果表明,在分布式训练时,随着计算资源的增大,DistDGL的训练速度可以线性增长。在16台机器组成的分布式环境中,DistDGL仅用13秒就可以完成1亿节点+30亿边的一个epoch的训练。DistDGL是DGL的一部分,已开源在:https://github.com/dmlc/dgl/tree/master/python/dgl/distributed。

Continue reading

CS224W(1.12)Lecture 1. Introduction; Machine Learning for Graphs

前言

最近的工作涉及到图神经网络,打算系统学习下这方面的内容。首先搜集了相关的教材,发现市面上的教材大多数是罗列论文的形式,不太适合初学者入门。后来找到了斯坦福CS224W这门公开课,打算入坑,一是之前学习过斯坦福CS224N,感觉不错;二是CS224W这门课的老师是GraphSAGE的作者Jure Leskovec,有大佬背书错不了。

CS224W主页:http://web.stanford.edu/class/cs224w/
Winter 2021版主页:http://snap.stanford.edu/class/cs224w-2020/
Winter 2021版视频:https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn,Jure Leskovec是斯洛文尼亚人,英语不是很标准,建议打开YouTube的字幕。

Continue reading

和我一起构建搜索引擎(八)更新爬虫&修改打分&线上部署

时隔多年,我发现我写的和我一起构建搜索引擎系列是我的博客中访问量最高的内容,截至目前该搜索引擎的GitHub项目已经收获了上百个Star和Fork。这几天我又回顾了一下这个项目,并进行了部分的更新和修改,以及将该搜索引擎部署到了我的个人网站上,以便展示和外网访问。以下是我将搜索引擎部署到个人网站上的截图,大家可以访问 http://news.bitjoy.net/ 进行测试。

Continue reading