摘要:人工智能Artificial intelligence: AI
最近经历了一场复兴,并在视觉、语言、控制、决策等关键领域取得了重大进展。取得这些进展的部分原因是由于廉价的数据、廉价的计算资源,这符合深度学习的天然优势。然而,在不同压力下发展起来的人类智力,其许多决定性特点对于目前的人工智能方法而言仍然是触不可及的。具体而言,超越经验的泛化能力--人类智力从幼年开始发展的标志--仍然是现代人工智能面临的巨大挑战。
论文 《Relational inductive biases, deep learning, and graph networks》
认为:组合泛化combinatorial generalization
是AI
实现人类相似能力的首要任务,而结构化表示和计算structured representations and computations
是实现该目标的关键。正如生物学把先天 nature
和后天 nurture
相结合,论文摒弃手动设计特征 hand-engineering
、端到端学习 end-to-end learning
之间进行二选一选择的错误做法,而是提倡一种利用它们进行优势互补的做法。
论文探索深度学习框架中使用关系归纳偏置 relational inductive biases
如何促进对实体 entity
、关系 relation
、以及构成它们的规则 rule
的了解。论文为AI toolkit
提供了一个新的、具有强大关系归纳偏置的构建块 building block
:Graph Network
。Graph Network
概括和扩展了图上运行的各种神经网络方法,并为操作结构化知识 manipulating structured knowledge
和产生结构化行为 producing structured behaviors
提供了直接接口。
论文讨论Graph Network
如何支持关系推理 relational reasoning
、组合泛化combinatorial generalization
。这为更复杂、更可解释、更可扩展的推理模式 reasoning pattern
奠定了基础。
作为论文的补充,作者还发布了一个用于构建 Graph Network
的开源软件库,并演示了如何在实际工作中应用它们。
引言:人类智能的一个重要标志是 “无限使用有限方法” (infinite use of finite means
) 的能力,其中一小部分的、有限的原始(如单词 word
)可以无限地组合(如构成无限多的句子 sentence
)。这反映了组合泛化combinatorial generalization
的原理,即从已知的构建块 building block
来创建新的推论 inference
、预测 prediction
、行为 behavior
。这里我们探索如何通过将偏置学习 biasing learning
用于结构化的表示和计算 structured representations and computations
从而提高现代 AI
的组合泛化能力,尤其是对图 graph
进行操作的系统。
人类的组合泛化能力很大程度上取决于我们表达结构representing structure
和推理关系 reasoning about relations
的认知机制。
entity
及其相互作用 interaction
的组合。fine-grained
的差异,并捕获representations
和 behaviors
之间的更一般的共性,比如:同一个物体的一部分、同一个场景的物体、同一个城镇的社区。skills
和惯例 routines
来解决新的问题。Kenneth Craik
的 The Nature of Explanation
将世界的组成结构 compositional structure of the world
和我们内在的心理模型 internal mental model
的组织方式联系起来,即:世界是组合的 compositional
,或者至少我们是从组合的角度来理解它的。当我们学习的时候,我们要么将新知识放入现有的结构化表示 structured representations
中、要么调整结构本身从而更好地适应(和使用)新旧知识。
自 AI
诞生以来,如何构建具有组合泛化的人工智能系统一直就是 AI
的核心问题,它是很多结构化方法 structured approach
的核心,包括:逻辑 logic
、语法 grammar
、经典规划 classic planning
、图模型 graphical model
、因果推理causal reasoning
、贝叶斯非参数化 Bayesian nonparametric
以及概率规划 probabilistic programming
。
所有子领域都集中于显式的以实体 entity
和关系 relation
为中心的学习上,例如关系强化学习relational reinforcement learning
、统计关系学习 statistical relational learning
。结构化方法对于之前的机器学习如此重要的一个关键原因,部分是因为数据和计算资源的昂贵,而结构化方法强大的归纳偏置 inductive biases
所带来的样本复杂度 sample complexity
的改善是非常有价值的。
与过去的人工智能方法相比,现代深度学习经常遵循 “端到端”(end-to-end
) 的设计理念,强调最小限度的先验表征的、计算的假设 minimal a priori representational and computational assumptions
,并力求避免使用显式的结构 explicit structure
和特征工程hand-engineering
。这种强调 emphasis
和当前的大量廉价数据和廉价计算资源非常契合,也得到了充分的验证。这使得牺牲样本效率 sample efficiency
从而更灵活地学习成为一种理性的选择。从图像分类到自然语言处理,深度学习在很多具有挑战性的领域中取得了令人瞩目的快速发展,这证明了这种极简主义原则 minimalist principle
的成功。一个突出的例子是语言翻译,事实证明sequence-to-sequence
方法非常有效,无需使用显式的解析树 parse tree
或者语言实体 linguistic entity
之间的复杂关系。
尽管深度学习取得了巨大成功,但是也有一些严厉的批评:深度学习在复杂的语言和场景理解complex language and scene understanding
、结构化数据的推理reasoning about structured data
、训练条件之外的迁移学习 transferring learning beyond the training condition
以及少量经验中学习learning from small amounts of experience
时面临重大挑战。这些挑战需要组合泛化,因此摒弃组合性 compositionality
以及显式结构 explicit structure
的方法难以满足这些挑战,这并不奇怪。
当深度学习的前辈连接主义 connectionist
面临诸如结构性的structured
、符号性的 symbolic
立场 position
等类似批评时,有些工作直接地、细致地做出了建设性的努力来解决这些挑战。在诸如模拟制造 analogy-making
、语言分析 linguistic analysis
、符号操作 symbol manipulation
以及其它形式的关系推理之类的领域中,符号主义开发了用于表示和推理结构化对象的各种创新的亚符号 sub-symbolic
方法,以及有关大脑如何工作的更多综合理论 integrative theory
。这些工作还有助于培养更多的深度学习进展advances
,这些进展使用分布式向量表示来捕获文本text
、图 graph
、代数表达式 algebraic expression
、逻辑表达式 logical expression
、以及程序programs
中的丰富语义内容。
我们认为,现代 AI
的关键途径是致力于将组合泛化作为首要任务,并且我们主张采用综合方法 integrative approache
来实现这一目标。正如生物学没有在先天 nature
和后天 nurture
之间进行选择一样(生物学同时利用先天和后天,这种整体效果强于每个部分之和),我们也拒绝这样的观念(即,结构 struture
和灵活性 flexibility
在某种程度上是矛盾的或不相容的),并且我们同时拥抱结构和灵活性从而获得它们的互补优势。根据大量最新的一些混合了 structure-based
方法、deep learning
方法的案例,我们发现:将当今最好的方法(即 deeplearning
方法)和早期算力昂贵时必不可少的方法(即结构化方法)相结合的综合技术具有广阔的前景。
近年来,在深度学习和结构化方法的交集中出现了一类模型,这些模型聚焦于推理有关显式结构化数据(特别是图 graph
)的方法。这些方法的共同点是可以对离散实体 entity
以及实体之间的关系 relation
进行计算。这些方法和经典方法不同之处在于:如何学习实体和关系的representation
以及structure
,以及相应的计算,从而缓解了事先需要指定它们的负担。即,这些知识是通过学习而来,而不是预先指定的。至关重要的是,这些方法以特定的体系架构假设的形式引入强烈的关系归纳偏置 relational inductive biases
,这些偏置指导这些方法学习实体和关系。我们和很多其他人一起认为,这是类似人类智力的基本组成部分。
在文章的剩余部分,我们通过关系归纳偏置的角度考察了各种深度学习方法,表明现有方法通常带有关系假设relational assumptions
,这些假设并不总是很明显或者显而易见。然后我们提出了一个基于实体和关系推理的通用框架,我们称之为 Graph Network:GN
。GN
统一和扩展了图上运行的现有方法,并描述了使用 Graph Network
作为构建块 building block
来构建强大架构的关键设计原理。我们还发布了一个用于构建 Graph Network
的开源库。
定义结构 structure
为通过一组已知构建块 building block
组成的产品 product
。结构化表示 Structured representations
捕获了这种组成composition
,如元素element
的排列arrangement
。结构化计算 structured computations
以一个整体的方式对所有这些元素及其组合进行操作。关系推理 Relational Reasoning
涉及利用实体entity
和关系relation
的组成规则 composed rule
,从而操作实体和关系的结构化表示。我们用以下数据来描述认知科学、理论计算机科学、人工智能的相关概念:
实体 entity
:具有属性的元素,如具有大小、质量的物理对象。
关系 relation
:实体之间的属性。如两个对象之间的关系可能包括:相同大小 same size as
、比.. 更重 heavier than
、距离distance from
。
more than X times heavier than
带有一个属性 X
,它决定了这个关系取值为 true/false
的阈值。falls with greater accelaration than
取决于环境是在空气中还是真空中。这里我们关注实体之间的成对关系 pairwise relations
。
规则 rule
:将实体和关系映射到其它实体和关系的函数,就像一个非二元的逻辑谓词 non-binary logical predicate
。例如 is entity X large?
、 is entity X heavier than entity y?
这样的尺度比较scale comparison
。
这里我们仅考虑带有一个参数或两个参数、并返回一个属性的规则。
我们以图模型 graphical model
来作为机器学习中关系推理的示例性说明。
图模型可以通过在随机变量之间指定显式的条件独立性来建模复杂的联合分布。这样的模型非常成功,因为它捕获了稀疏结构 sparse structure
,而稀疏结构是很多现实世界生成过程generative processes
的基础,并且它们支持有效的学习和推理算法。
例如,隐马尔可夫模型可以显式指定条件独立性:
这和很多现实世界因果过程 causal process
的关系结构非常契合。
明确表达变量之间的稀疏依赖关系提供了各种高效的推断 inference
和推理 reasoning
算法。例如,消息传递算法在图模型内的各个位置之间采用通用的消息传播过程,从而导致一个可组合的composable
、部分并行化的 partially parallelizable
推理过程reasoning procedure
,这适用于不同大小和形状的图模型。
学习是通过观察世界并与世界互动来理解有用知识的过程,它涉及搜索解空间 space of solutions
以期找到可以更好地解释数据、或获得更高回报的解决方案 solution
。但是在很多情况下,有多种解决方案同样出色。归纳偏置 inductive bias
允许学习算法独立于观测到的数据,从而将一种解决方案(或者解释)优先于另一种解决方案(或解释)。
在贝叶斯模型中,归纳偏置通常以先验分布的选择choice
、参数化 parameterization
来表示。而在其它模型中,归纳偏置可能是为避免过拟合而添加的正则化项,也可能被编码到算法本身的体系结构中。
归纳偏置通常以灵活性 flexibility
为代价从而换取改善的样本复杂性 sample complexity
,并且可以从偏差-方差平衡 bias-variance tradeoff
的角度来理解。理想情况下,归纳偏置既可以在不显著降低性能的情况下改善对于解空间的搜索,又可以帮助找到理想泛化的解决方案。但是,不匹配mismatched
的归纳偏置也会引入过强的约束从而导致欠拟合。
归纳偏置可以表达关于数据生成过程 data-generating process
或解空间的假设。例如,当使用一维函数拟合数据时,线性最小二乘法遵循近似函数为线性模型的约束,并且在 additive Gaussian noise
破坏的线性过程 line process
。
类似地,ill-posed problem
可以得到唯一的解决方案和全局结果。这可以解释为关于学习过程的一种假设:当解决方案之间的分歧较少时,寻找好的解决方案更加容易。
注意,这些假设不需要明确地解释模型或算法如何与世界交互。
机器学习和 AI
中很多具有关系推理能力的方法使用关系归纳偏置 relational inductive bias
。虽然不是精确的正式定义,但是我们通常使用该术语来指归纳偏置 inductive bias
,它对于学习过程中实体之间的关系和交互施加了约束。
近年来新型的机器学习体系架构迅速增加,从业人员经常遵循通过组合基本构建块 elementary building block
来形成更复杂、更深计算的层次hierarchies
和计算图。
例如:
full connected layer
被堆叠到多层感知机 multilayer perceptrons: MLPs
中。convolutional layers
被堆叠到卷积神经网络 convolutional neural networks: CNNs
中。CNN
变体 + MLP
的组合。这种 layer
的组合提供了一种特殊类型的关系归纳偏置:层次处理 hierarchical processing
的关系归纳偏置。其中计算分阶段 in stages
进行,这会导致输入信号中的信息之间产生越来越长距离的交互 long range interaction
。
正如我们在下面探讨的那样,构建块本身也带有各种关系归纳偏置(如下表所述)。尽管超出了本文的范围,但是在深度学习中也使用各种非关系归纳偏置 non-relational inductive biases
,例如:激活值的非线性 non-linearity
、权重衰减、dropout
、batch normalization/layer normalization
、data augmentation
、训练方式、优化算法都对学习的轨迹和结果施加了约束。
要探索各种深度学习方法中表达的关系归纳偏置,我们必须确定几个关键因素:实体是什么、关系是什么、组成实体和关系的规则是什么、计算实体和关系的规则是什么。在深度学习中,实体和关系通常表示为分布式表示 distributed representation
,规则通常表示为神经网络函数逼近器 approximator
。然后,实体、关系、规则的精确形式在不同体系架构之间有所不同。为了理解架构之间的这些差异,我们通过以下探索进一步理解每种架构如何支持关系推理:
rule function
的自变量 argument
,例如:哪些实体和关系作为输入。step
。representation
之间的交互 interaction
与隔离 isolation
。例如:通过在相关的实体上应用规则来得出结论,而不是对每个实体独立处理。Fully Connected Layers
全连接层:也许最常见的构建块是全连接层。
通常全连接层被实现为输入向量的非线性函数:
其中
因此实体是网络中的单元,关系是 all-to-all
:
因此,在全连接层中的隐式关系归纳偏置非常弱week
:所有输入单元之间可以交互从而决定任何输出单元的值,并且所有输出单元之间相互独立。
Convolutional Layers
卷积层:另一个常见的构建块是卷积层。
卷积层通常被实现为输入向量或张量的卷积:
其中
这里的实体仍然是单个单元(或者网格元素,如像素),但是实体之间的关系更为稀疏。全连接层和卷积层之间的差异在于卷积层增加了一些重要的关系归纳偏置:局部性 locality
和平移不变性 translation invariance
。
relational rule
的自变量是那些在输入信号的坐标空间中紧密相邻的实体、并且和远处实体隔离。这些偏置对于处理天然的图像数据非常有效,因为图像数据局部邻域内存在较高的协方差,且随着距离增加,协方差会减小。并且统计量在整个图上大多是平稳的stationary
。
Recurrent Layers
递归层:第三种常用的构建块是递归层,它是通过一系列 step
来实现的。这里我们将每个 step
的输入和 hidden state
视为实体,将马尔可夫过程视为关系:当前 hidden state
依赖于前一个 hidden state
和当前 input
。实体组合的规则将当前 step
的输入、前一个 hidden state
作为规则的自变量,然后更新当前 hidden state
。
这个规则在每个 step
被复用,这反映了时间不变性(类似于 CNN
在空间上的平移不变性)的关系归纳偏置。例如,某些物理事件序列的结果不应该取决于一天中的某个时刻。
RNN
也通过其马尔可夫结构对序列带来局部性 locality
的 bias
。
下图给出了常见的深度学习构建块中的复用和共享,共享的权重由具有相同颜色的箭头表示。
(a)
:全连接层,其中所有权重都是独立的,并且没有共享。(b)
:卷积层,其中局部核函数在输入中多次重复使用。(c)
:循环层,其中相同的函数可以在不同的 step
中复用(水平方向代表了时间线)。虽然标准的深度学习工具包所包含的方法具有各种形式的关系归纳偏置,但是没有默认的深度学习组件可以在任意关系结构上运行。我们需要模型具有显式的实体表示和关系表示,并需要学习算法,该算法用于找到计算实体和关系交互的规则、以及将规则置于数据中的方式。
重要的是,世界上的实体(如对象、agent
)没有自然顺序。相反,可以通过关系的性质来定义顺序。如:可以根据对象之间的大小、质量、年龄、毒性、价格之间的关系来对它们进行排序。顺序不变性invariance to ordering
(除了处理关系时)是一种理想的属性,这种不变性应该由用于关系推理的深度学习组件来反映。
集合 sets
是描述包含一组无序实体的系统的自然表达形式。具体而言,集合的关系归纳偏置并不是来自于 something
的存在,而是来自于 something
的缺失。
为了说明,考虑由
但是,如果要使用 MLP
来预测该任务,即使已经知道了特定顺序输入 MLP
可能会认为每种顺序从根本上看是不同的,因此需要指数级的输入/输出训练样本来学习近似函数。
处理类似组合爆炸的自然方法是允许预测依赖于输入的对称函数。这可能意味着首先计算 per-object
参数共享的特征 Deep Sets
以及相关模型的本质。我们在后文进一步讨论。
当然,在很多问题中排列不变性 permutation invariance
并不是底层结构的唯一重要形式。例如,一个集合中的每个对象都可能受到集合中其它对象的 pairwise interaction
的影响。在我们的行星case
中,考虑在时间间隔
取而代之的是,我们可以将每个对象的状态计算为
我们在各处都使用相同的 global permutation invariance
。但是,它也支持不同的关系结构,因为
上述太阳系的例子说明了两种关系结构 relation structure
:一种完全没有关系,一种包含所有的 pairwise
关系。很多现实世界的系统(如下图所示)的关系结构在这两种极端 case
之间:某些实体 pair
对之间存在关系、另一些实体 pair
对之间缺乏关系。
在我们的太阳系例子中,如果该系统改为由行星及其卫星组成,则可能会试图通过忽略不同行星的卫星之间的相互作用来近似。实际上,这意味着仅计算某些对象之间的交互,即:
其中 graph
,因为第
注意:节点
下图为现实世界的不同系统,以及对应的graph
的表达:
(a)
:一个分子图,其中每个原子表示为一个节点,边对应于化学键。(b)
:一个质点弹簧系统,其中绳索由一个质点序列定义,这些质点在图中表示为节点。(c)
:一个 n body
系统,其中每个 body
为节点,节点之间全连接。(d)
:一个刚体系统,其中球和墙壁都为节点,底层的 graph
定义了球之间、球和墙壁之间的相互作用。(e)
:一个句子,其中单词对应于解析树上的叶结点,其它节点和边可以由解析器提供。或者也可以使用一个全连接的图。(f)
:一张图片,可以将其分解为图像块patch
,每个块代表一个节点,并且节点之间全连接。通常,图 graph
是支持任意 pairwise
关系结构的表示形式,并且图上的计算提供了超越卷积层、递归层的强大的关系归纳偏置。
图神经网络已经在监督学习、半监督学习、无监督学习、强化学习领域被应用。
visual scene understanding
任务、few-shot learning
任务等。physical system
和多智体系统 multi-agent system
,从而推理知识图谱、预测分子化学性质、预测道路交通流量、分类和分割图像/视频/3D
网格/点云、分类图像中的区域、执行半监督文本分类及机器翻译。model-free
和 model-based
连续控制中都被使用,用于 model-free
的强化学习,以及更经典的规划问题。satisfiability
、程序表示和验证、元胞自动机及图灵机建模,以及图模型上的 inference
。最近的工作还关注于图的生成模型、graph embedding
的无监督学习。这里介绍我们的图网络框架 Graph Networks:GN
,该框架定义了一族函数用于图结构表示graph-structured representations
的关系推理relational reasoning
。我们的 GN
框架概括并扩展了各种图神经网络、MPNN
、以及 NLNN
方法,并支持从简单的构建块构建复杂的体系架构。
注意,我们避免在 Graph Network
中使用术语 neural
来反映GN
可以使用除神经网络以外的函数来实现,尽管这里我们的重点是神经网络的实现。
GN
框架中的主要计算单元是 GN
块 GN block
。GN
块是一个 graph-to-graph
的模块,它将图作为输入,对结构进行计算,然后将图作为输出返回。图的节点表示实体,图的边表示关系,图的全局属性表示 system-level
属性。
GN
框架的 block
组织强调可定制性customizability
,以及综合了新的架构,这个新架构能够表达预期的关系归纳偏置。GN
框架的主要设计原则是:灵活的表示形式 flexible representations
、可配置的块内结构 configurable within-block structure
、可组合的多块体系架构 composable multi-block architectures
。我们引入一个例子来更具体的说明 GN
。可以在任意重力场中预测一组橡胶球的运动,这些橡胶球不会彼此弹跳,而是每个橡胶球都有一个或多个弹簧,这些弹簧将它们和其它橡胶球相连。我们将在下文中参考这个例子,从而启发 motivate
图的表示以及图上进行的计算。
这里我们使用图来表示带全局属性的、有向的、带属性的多图 multi-graph
。
graph-level
属性 sender
节点 receiver
节点 multi-graph
:节点之间可能存在多条边,包括自连接 self-edge
。在我们的 GN
框架内,图被定义为三元组
receiver
节点, sender
节点。例如:一个 GN
块包含三个更新函数
其中:
其物理意义为:
sender
节点属性 receiver
节点属性 receiver
为当前节点的所有边的属性(更新后的边属性)聚合后的 permutation invariant
,并且应该采用可变数量的自变量。一些典型的例子包括:逐元素求和、均值池化、最大值池化等。GN
块的计算步骤:
通过执行
receiver
。执行
通过执行
更新后,所有节点的属性集合为
通过执行
通过执行
通过执行
尽管这里我们给出了计算步骤的顺序,但是并不是严格地根据这个顺序来执行。例如,可以先更新全局属性、再更新节点属性、最后更新边属性。
GN block
更新函数 GraphNETWORK()
:
输入:图
输出:更新后的图
计算步骤:
迭代更新边的属性:
迭代更新节点的属性:
receiver
为当前节点 令
令
根据全局属性、聚合后的节点属性、聚合后的边属性来更新全局属性
返回更新后的图
给定一个图 GN
块的输入时,计算过程从边、节点、global-level
。下图给出了这些计算中,每一个计算都涉及哪些图元素。蓝色表示待更新的元素,黑色表示更新中涉及的其它元素(注意,蓝色元素更新之前的值也用于它的本次更新)。
下图给出了具有更新函数、聚合函数的完整 GN
块。它根据输入的节点属性、边属性、全局属性来预测输出的节点属性、边属性、全局属性。
当用于 learning process
的组成部分时,我们的 GN
框架会强制添加几个很强的关系归纳偏置:
首先,图可以表达实体之间的任意关系。这意味着 GN
的输入决定了 representation
是如何交互 interact
和隔离 isolated
的,而不是由固定 fixed
的体系架构来决定的。
即实体的交互和隔离是由数据决定,而不是由模型决定。
例如:
其次,图将实体及其关系表示为集合,这是排列不变的 permutation invariant
。这意味着 GN
对于这些元素的顺序是不敏感的,这通常是我们所需要的。
最后,GN
的 per-edge
函数、per-node
函数分别在所有边、所有节点之间重用。这意味着 GN
自动支持某种形式的组合泛化:由于图由边、节点、以及全局属性组成,因此单个 GN
可以在不同大小(以边和节点数量刻画)、不同形状(不同的连通性)的图上进行操作。
根据前述列出的设计原则,GN
框架可用于实现各种各样的体系架构。通常,GN
框架和特定的属性表示 attribute representation
和函数形式 functional form
无关。但是这里我们重点关注深度学习架构,该架构允许 GN
充当可学习的 graph-to-graph
的函数逼近器 function approximator
。
这里再回顾一下 GN
设计原则:灵活的表示 flexible representations
、可配置的块内结构 congurable within-block structure
、可组合的多块体系架构 composable multi-block architectures
。
这三个设计原则再我们的 GN
框架中结合在一起,非常灵活,适用于从感知、语言、到符号推理的广泛领域。并且,如前所述,GN
具有的强大的关系归纳偏置支持组合泛化,因此使得 GN
在实际和理论上都成为强大的工具。
灵活的表示有两层含义:
GN
块的全局属性、节点属性、边属性可以为任意表示形式 arbitrary representational formats
。属性形式:GN
块的全局属性、节点属性、边属性可以使用任意表示形式。在深度学习实现中,通常使用实值向量或张量。但是,也可以使用其它数据结构,如序列sequence
、集合set
、甚至是图 graph
。
通常我们需要决定:对某个问题采用何种表示形式来描述属性。例如:
patches
的张量。对于更广泛的体系架构中的每个 GN
块,每个边/节点的输出通常对应于一个张量/向量,而全局输出对应于单个张量/向量。这使得 GN
块的输出可以传递到其它深度学习构建块 building block
中,如 MLP,CNN,RNN
。GN
块的输出也可以根据任务需求进行定制化。具体而言:
edge-focused GN
可以仅仅将边作为输出。例如,做出有关实体之间相互作用的决策。node-focused GN
可以仅仅将节点作为输出。例如,用于推理物理系统。graph-focused GN
可以仅仅将全局属性作为输出。例如,预测物理系统的势能、分子性质、关于某个视觉场景问题的答案。节点属性、边属性、全局属性的输出也可以根据任务混合使用。
图结构形式:在定义如何将输入数据表示为图结构时,有两种情形:
首先,输入数据明确指定了关系结构。例如:知识图谱、社交网络、化学分子图、交通网络、以及具有已知交互作用的物理系统。
其次,需要从输入数据中推断或假设关系结构,即关系结构没有明确指定。例如视觉场景、文本文档等。
这里可以将数据表示为一组没有关系的实体,甚至仅表示为向量或张量(如:图像)。
如果未明确指定实体,则可以通过将诸如句子中的每个单词、或者 CNN
输出 feature map
中的 feature vector
视为节点来指定实体。
或者,也可以使用单独的学习机制从非结构化信号中推断实体,如通过解析树算法从文本中得到解析树。
如果关系不可用,则最简单的方法是在实体之间添加所有可能的有向边。如在图像的 patches
之间两两添加有向边。但是,这对于拥有大量实体的图而言是不可行的,因为边的数量会随着节点数量的增加而平方规模的增加。
因此,研发更复杂的方法来从非结构化数据中推断稀疏的图结构是未来的重要方向。
GN
块中的结构和函数可以通过不同的方式进行配置,从而可以灵活地确定哪些信息可以用作函数的输入,以及如何更新边属性、节点属性、全局属性。具体而言,GN
块中的每个 argument signature
决定了它需要哪些信息作为输入。
通过选择不同的函数 GN
框架可以表达其它各种架构,如下图所示。接下来讨论如何使用不同的方式配置 GN
的块内结构。
下图中,每个 incoming
箭头表示是否将
(a)
:full GN
(即完整的、原始的 GN
块)根据传入的节点属性、边属性、全局属性来输出节点属性、边属性、全局属性。(b)
:独立的循环块使用 input
和 hidden state
来进行更新,其中 RNN
。(c)
:MPNN
根据传入的节点属性、边属性来输出节点属性、边属性、全局属性。注意,全局预测中不包含聚合的边,输入中不包含全局属性。(d)
:NLNN
仅输出节点属性。(e)
:Relation Network
仅使用预测的边属性来输出全局属性。(f)
:Deep Set
没有采用边更新从而输出全局属性。
Full GN block
:《Relational inductive bias for physical construction in humans and machines》
和 《Graph networks as learnable physics engines for inference and control》
使用完整的 GN
块,如上图的 (a)
所示。
更新方程为:
其中:
MLP
作为 feature map
),通常采用 CNN
作为 RNN
,这需要额外的 hidden state
作为输入和输出。上图 (b)
展示了一个非常简单的 GN
块,其中 RNN
作为 block
可用于对某些 dynamic graph state
进行递归平滑 recurrent smoothing
。
当然,RNN
作为 full GN block
中使用。
Message-passing neural network: MPNN
概括了很多之前的体系架构,并且可以很自然地转换为 GN
的格式:
GN
中的 GN
的 GN
中的 readout
函数 GN
中的 GN
的 GN
中的 GN
的 上图 (c)
展示了如何根据 GN
块来构建 MPNN
。
Non-local Neural Networks:NLNN
统一了各种 intra/self/vertex/graph attention
方法,它也可以转换为 GN
的格式。
attention
指的是节点的更新方式:每个节点更新均基于其邻域节点属性(或者它的某些函数)的加权和,其中一个节点和它某个邻居之间的权重由属性之间的 scale pairwise
函数(然后整个邻域归一化)给出。
已发表的 NLNN
公式并未显式包含边,而是计算所有节点之间的 pairwise
注意力权重。但是,各种 NLNN-compliant
模型,例如节点注意力交互网络 vertex attention interaction network
、图注意力网络 graph attention network
都可以通过有效地将没有边的节点之间的权重设为零来显式处理边。
在 NLNN
中, pairwise-interaction
函数,该函数返回:
attention
系数,记作 non-pairwise
的向量值,记作 在 receiver
的所有边上归一化,然后
在 NLNN
论文中,set
(而不是图graph
)、并且这个图是根据集合中所有实体之间添加所有可能的边来构建的。
Transformer
体系架构中的 single-headed self-attention
,即 SA
, 实现为公式为:
其中
《Attention is all you need》
的 multi-head self-attention
机制增加了一个有趣的特性: Gated Graph Sequence Neural Networks
。
具体而言,multi-head self-attention
计算
Vertex Attention Interaction Networks
和 SA
很相似,但是它将欧几里得距离用于 attention
相似性度量,并在 attention
输入的 embedding
中共享参数,且在节点更新函数中使用节点的输入特征:
Graph Attention Networks
和 multi-head self-attention
相似,但是它使用神经网络作为 attention
相似性度量,并在 attention
输入的 embedding
中共享参数:
《Self-attention with relative position representations》
提出相对位置编码 relative position encodings
来扩展 multi-head self-attention
。relative
是指对序列中节点之间的空间距离进行编码、或度量空间中其它信号进行编码。这可以在 GN
中表示为边的属性 multi-head self-attention
中的
下图展示了如何在 GN
框架下通过 NLNN
。 通常 NLNN
假设图像(或句子中的单词)对应于全连接图中的节点,并假设注意力机制在聚合步骤中定义节点上的加权和。
完整的 GN block
公式可以预测完整的图
同样的思路可以适用于其它 GN
变体,这些变体不使用完整的 mapping
reduction
Interaction Networks
和 Neural Physics Engine
使用 full GN
,但是没有使用全局属性来更新边属性。
该工作还包括对上述公式的扩展:输出全局的、而不是 per-node
的预测:
这里没有使用全局属性来更新边属性,也没有用边属性来更新全局属性。
Relation Networks
完全绕开了节点更新,并直接从池化的边信息中预测全局属性输出:
Deep Sets
完全绕开了边更新,并直接根据池化的节点信息中预测全局属性输出:
PointNet
使用类似的更新规则,但是对于
Gated Graph Sequence Neural Networks: GGS-NN
使用稍微泛化的公式,其中每条边关联一个类别
这里 GRU
,
上述更新递归进行,然后接一个全局解码器,该解码器计算所有节点的最终 embedding
的加权和。
CommNet
的更新公式为:
structure2vec
也可以适配我们的算法,只需要进行少量的修改:
其中
边的属性现在在 receiver
和 sender
之间具有 message
的含义。注意,对于边和节点更新,现在只有一组参数需要学习。
注意:对于 CommNet、structure2vec、Graph Sequence Neural Networks
使用一种非对称的 pairwise interaction
,而是忽略receiver node
而仅考虑 sender
节点,并且某种程度上是在边属性上进行。这种做法可以通过具有以下签名 signature
的
.
GN
的主要设计原理是通过组合 GN block
来构建复杂的体系架构。我们将 GN block
定义为包含边属性、节点属性、全局属性的图作为输入,并返回新的边属性、节点属性、全局属性的图作为输出。如果某些元素不需要更新,则只需要直接对应的输入传递到输出即可。
这种 graph-to-graph
的 input/output
接口可以确保 GN block
的输出可以传递给另一个 GN block
作为输入。这两个 GN block
内部可以使用完全不同的配置,这类似于深度学习 toolkit
的 tensor-to-tensor
接口。
这种接口最基本的形式是:给定两个 GN block
GN1
和 GN2
,可以通过将 GN1
的输出作为 GN2
的输入,从而将它们组合在一起:
可以组合任意数量的 GN block
,如下图所示。图中 M
个重复的内部处理子步骤 repeated internal processing sub-steps
,可能包含共享或者不共享的 GN block
。
block
可以不共享(采用不同的函数或参数,类似于 CNN
的不同的 layer
),即 block
也可以共享(采用相同的函数或参数,类似于展开的 RNN
),即配置共享(采用相同的函数或参数)类似于消息传递,其中反复应用相同的局部更新过程从而在整个结构中传播消息,如下图所示。如果不考虑全局属性 step
之后,可访问的信息由最多 m-hop
的节点和边的集合确定。
这可以解释为将复杂的计算分解为较小的基础步 elementary step
。这些 step
也可以用于捕获时间上的顺序。
在我们的橡胶球示例中,如果每个step
预测持续时间为 step
的总的模拟时间为
下图中,每一行突出显式了从特定节点开始、然后扩展到整个图的信息。
step
能够传播的范围。注意:在完整的消息传递过程中,这种消息传播同时发生在图中所有节点和所有边上,而不仅仅是这里的两个初始节点。
可以通过 GN block
构建两种常见的体系架构:
一种体系架构我们称之为 encode-process-decode
配置,如下图 (b)
所示。其中:
core block
例如在我们的橡胶球例子种,编码器可能会计算球之间的初始力和相互作用势能,core
可能会应用基本动力学更新,解码器可能从更新后的图状态读取最终位置。
类似 encode-process-decode
设计,另一种体系架构我们称之为 recurrent GN-based
配置,如下图 (c)
所示。其中在 step
每个 step
维护一个 hidden graph
一个输入图
其中 (c)
的箭头合并),然后传递给
一个共享的 core block
unrolled
(一共展开 GRU
或者 LSTM
。
(c)
的箭头拆分),其中一路输出由
通过解码器
这种设计以两种方式重用 GN block
:
step
step
内,sub-step
内共享。这种类型的体系架构常用于预测 graph
序列,例如预测一段时间内动力系统的轨迹。
其它一些技术对于设计 GN
体系架构可能也有用。例如:
Graph Skip Connection
可以将 GN block
的输入
Recurrent GN
架构中合并输入图和 hidden
图的信息可以使用 LSTM
或 GRU
风格的 gating scheme
,而不是简单地拼接。
或者在其它 GN block
之前和/或之间组合不同的递归 GN
块,从而提高多个传播step
中 representation
的稳定性。
类似于可天然并行的 CNN
(在 GPU
上),GN
具有天然并行结构:
disjoint component
,可以自然地将几张图打包一起。因此可以将几个独立图上进行的计算打包在一起。重用 GN
的样本效率。类似于卷积核,GN
中用于优化
我们已经发布了用于构建 GN
的开源软件库,在 github.com/deepmind/graph_nets
。我们也给出了一些demo
包括:在最短路径搜索任务、排序任务、物理系统预测等任务上,如何创建、操作、训练 GN
来推理图结构数据。每个 demo
使用相同的 GN
体系架构,这凸显了该方法的灵活性。
GN
的结构天然支持组合泛化,因为它们并不严格地在系统级别执行计算,而且还跨实体、跨关系执行共享计算。这样可以推理未曾见过的系统,因为它们都是由熟悉的组件构成的,从而体现了 infinite use of finite means
的方式。
GN
和 MPNN
的消息传递学习方式的局限性之一是无法解决某些类型的问题,如区分某些非同构图 non-isomorphic graph
。
更一般而言,尽管图是表示结构信息的有效方式,但是它们也有局限性。诸如递归、控制流、条件迭代之类的概念并不容易用图来表示。就这些概念而言,program
和更多的 computer-like
处理过程可以提供更好的表示性。
关于使用 Graph Network
还存在很多悬而未决的问题:
一个紧迫的问题是:运行 GN
的图如何构建?
深度学习的标志之一是它能够对原始的感官数据 sensory data
(如图像、文本)执行复杂的计算,但是尚不清楚如何将感官数据转换为更结构化的表示形式(如 graph
)。
一种方法(我们已经讨论过)假设空间或语言实体之间是全连接的图结构,例如在 self-attention
的文献采用这种方法。但是,这样的representation
可能不完全对应于真实的实体,如卷积feature map
并不直接对应于真实场景中的对象。
此外,很多底层图结构比全连接的图稀疏的多,如何引入这种稀疏性也是一个悬而未决的问题。
有一些研究正在探索这些问题,但是目前为止并没有一种方法能够可靠地从感官数据中提取离散实体。开发这种方法是一个令人兴奋的挑战,一旦解决就可以推开更强大、更灵活的推理算法的大门。
一个相关的问题是如何在计算过程中自适应地修改图结构。例如,如果一个对象分解为多个片段,则代表该对象的节点也应该拆分为多个节点。同样,仅保留交互对象之间的边可能很有用,因此需要根据上下文添加、删除边的能力。
人类的认知提出了一个强有力的假设,即世界是由对象和关系组成的。并且,由于 GN
做出了类似的假设,因此它的行为往往更具有解释性。GN
所处理的实体和关系通常对应于人类理解的实物(如物理对象),因此支持更可解释的分析和可视化。未来一个有趣的方向是进一步探索网络行为的可解释性。
尽管我们的重点是图,但是本文的重点不是图本身,而更多是将强大的深度学习方法和结构化表示相结合的方法。
对图结构数据的学习需要有效地对图结构进行表示。最近,对图表示学习graph representation learning
的图神经网络 Graph Neural Network: GNN
引起了人们的广泛兴趣。GNN
遵循递归邻域聚合方案,其中每个节点聚合其邻居的representation
向量从而计算节点的新的 representation
。
已经有很多 GNN
的变体,它们采用不同的邻域聚合方法、graph-level
池化方法。从实验上看,这些 GNN
变体在很多任务(如节点分类、链接预测、图分类)中都达到了 state-of-the-art
性能。但是,新的 GNN
的设计主要基于经验直觉empirical intuition
、启发式heuristics
、以及实验性experimental
的反复试验。
人们对 GNN
的性质和局限性的理论了解很少,对 GNN
的表达容量representational capacity
的理论分析也很有限。论文 《How powerful are graph neural networks?》
提出了一个用于分析GNN
表达能力representational power
的理论框架。作者正式刻画了不同 GNN
变体在学习表达represent
和区分distinguish
不同图结构上的表达能力expressive
。
论文的灵感主要来自于GNN
和 Weisfeiler-Lehman:WL
图同构检验graph isomorphism test
之间的紧密联系。WL-test
是一种强大的、用于区分同构图的检验。类似于 GNN
,WL-test
通过聚合其网络邻域的特征向量来迭代更新给定节点的特征向量。WL-test
如此强大的原因在于它的单射聚合更新 injective aggregation update
,这可以将不同的节点邻域映射到不同的特征向量。
单射函数:假设
是集合 到集合 的映射。如果所有 且 都有 ,则称 是 从 到 的单射。
论文的主要洞察是:如果 GNN
的聚合方案具有很高的表达能力expressive
并且建模单射函数injective function
,那么 GNN
可以具有与 WL-test
一样强大的判别力discriminative power
。
为了从数学上形式化该洞察,论文的框架首先将给定节点的邻居的特征向量集合表示为 multiset
,即可能包含重复元素的集合。可以将 GNN
中的邻域聚合视为 multiset
上的聚合函数 aggregation function over the multiset
。因此,为了具有强大的表征能力 ,GNN
必须能够将不同的 multiset
聚合为不同的representation
。论文严格研究了multiset
函数的几种变体,并从理论上刻画了它们的判别能力,即不同的聚合函数如何区分不同的multiset
。multiset
函数的判别力越强,则底层GNN
的表征能力就越强。然后论文设计出一种简单的架构 Graph Isomorphism Network:GIN
,该架构被证明是 GNN
中最具表达能力的,并且和 WL-test
一样强大。
论文在图分类数据集上进行实验来验证该理论,其中GNN
的表达能力对于捕获图结构至关重要。具体而言,作者比较了使用各种聚合函数的 GNN
的性能。实验结果证明了最强大的 GNN
(即作者提出的 GIN
)在实验中也具有很高的表征能力,因为它几乎完美拟合训练数据。而能力更弱的 GNN
变体通常对于训练数据严重欠拟合underfit
。此外,GIN
在测试集上的准确率也超过了其它GNN
变体,并在图分类 benchmark
上达到了 state-of-the-art
性能。
论文的主要贡献:
GNN
在区分图结构方面最多和 WL-test
一样强大。readout
函数在什么条件下所得的 GNN
和 WL-test
一样强大。GNN
变体(如 GCN,GraphSAGE
)判别的图结构,然后刻画这些GNN-based
模型能够捕获的图结构。Graph Isomorphism Network: GIN
,并证明了其判别能力/表征能力等于 WL-test
。相关工作:尽管 GNN
在经验上取得成功,但是在数学上研究GNN
特性的工作很少。
《Computational capabilities of graph neural networks》
表明:早期的 GNN
模型在概率上逼近测度函数。《Deriving neural architectures fromsequence and graph kernels》
表明:该论文提出的架构位于graph kernel
的 PKHS
中,但没有明确研究该架构可以区分哪些图。这些工作中的每一个都专注于特定的体系结构,并且不容易推广到多种体系结构。相反,我们的研究为分析和刻画一系列GNN
模型的表征能力提供了一个通用框架。
另外,近期提出了一些基于 GNN
的体系结构大多数没有理论推导。与此相比,我们的 GIN
是有理论推导的,而且简单、强大。
我们首先总结一些常见的 GNN
模型。
令图
通常我们关心图上的两类任务:
representation
向量 representation
向量 GNN
利用图结构和节点特征 representation
向量 representation
向量
现代 GNN
使用邻域聚合策略,在该策略中我们通过聚合邻域的representation
来迭代更新节点的 representation
。在经过 representation
将捕获其 k-hop
邻域内的结构信息。
以数学公式来讲,GNN
的第
其中:
representation
。另外 在 GraphSAGE
的最大池化变体中,聚合函数为:
其中:
relu
非线性激活函数。而 GraphSAGE
中的拼接函数为简单的向量拼接:
其中 [,]
表示向量拼接,
在 Graph Convolutional Networks: GCN
中,聚合函数采用逐元素的均值池化。此时聚合函数、拼接函数整合在一起:
其中 MEAN(.)
为逐元素的均值池化,
对于节点分类任务,节点 representation
representation
。
对于图分类任务,READOUT
函数聚合所有节点最后一层的 representation
从而得到整个图的 representation
READOUT
函数可以是简单的排列不变函数permutation invariant function
,例如求和函数;也可以是更复杂的graph-level
池化函数。
图同构问题graph isomorphism problem
是判断两个图在拓扑结构上是否相同。这是一个具有挑战性的问题,尚不知道多项式时间polynomial-time
的算法。
除了某些极端情况之外,图同构的 Weisfeiler-Lehman(WL) test
是一种有效且计算效率高的算法,可用于各种类型的图。它的一维形式是 naïve vertex refinement
,它类似于 GNN
中的邻域聚合。
在 WL-test
过程中,每个节点都分配一个label
。注意:这里的 label
和分类任务中的label
不同,这里的 label
更多的表示“属性”, 而不是“监督信息”。
WL-test
对节点邻域进行反复迭代,最终根据两个图之间的节点label
是否完全相同,从而判断两个图是否同构的。
WL-test
迭代过程如下:
label
。label
经过哈希函数得到不同的、新的label
,即 relabel
。如下图所示:
首先将图中每个节点初始化为 label = 1
。
然后经过三轮迭代,最终:
1
具有 1
个label = 8
、2
个 label = 7
、2
个 label = 9
。2
具有1
个label = 8
、2
个 label = 7
、2
个 label = 9
。因此我们不排除图1
和图 2
同构的可能性。
下图的哈希函数为:
{1,1} --> 2
{1,1,1} --> 3
{2,3} --> 4
{3,3} --> 5
{2,2,3} --> 6
{4,6} --> 7
{6,6} --> 8
{4,5,6} --> 9
注意:这里的 label
集合需要根据label
大小排序,并且每次哈希之后都需要分配一个新的 label
。
《Weisfeiler-lehman graph kernels》
根据 WL-test
提出了 WL subtree kernel
来衡量两个图的相似性。核函数利用 WL tet
的不同迭代中使用的节点label
数作为图的特征向量。
直观地讲,WL test
第 label
代表了以该节点为根的、高度为 WL subtree kernel
考虑的图特征本质上是不同根子树的计数。
如下图所示为一棵高度 WL subtree
。 这里 label = 8
的节点代表一棵高度为 1
的 subtree
模式,其中subtree
根节点的 label
为 2
、包含label=3
和 label=5
的邻居节点。
我们首先概述我们的框架,下图说明了我们的思想:GNN
递归更新每个节点的representation
向量,从而捕获网络结构和邻域节点的representation
,即它的 rooted subtree
结构。
在整篇论文中,我们假设:
countable universe
。layer
的 representation
也是来自可数的范围。通常浮点数是不可数的,而整数是可数的。我们可以将浮点数离散化为整数,从而使得数值可数。
为便于说明,我们为每个representation vector
(输入特征向量是第0
层的 representation vector
)分配唯一的 label
,label
范围在 label
然后节点的邻域节点 representation vector
就构成一个 multiset
:由于不同的节点可以具有相同的 representation
向量,因此同一个 label
可以在 multiset
中出现多次。
下图中:
rooted subtree
结构,用于在 WL test
中区分不同的图。GNN
聚合函数捕获节点邻域的 full multiset
,则 GNN
能够以递归的方式捕获 rooted subtree
结构,从而和 WL test
一样强大。multiset
定义:multiset
是 set
概念的推广,它允许包含相同的多个元素。正式地讲,,multiset
是一个 2-tuple
set
,它包含唯一distinct
的元素。multiplicity
。为研究 GNN
的表征能力,我们分析GNN
何时将两个节点映射到 embedding
空间中的相同位置。
直观地看,能力强大的 GNN
仅在两个节点具有相同subtree
结构、且subtree
上相应节点具有相同特征的情况下才将两个节点映射到相同的位置。
由于 subtree
结构是通过节点邻域递归定义的,因此我们可以将分析简化为:GNN
是否将两个邻域(即两个multiset
)映射到相同的 embedding
或 representation
。
能力强大的 GNN
绝对不会将两个不同的邻域(即representation
向量的 multiset
)映射到相同的representation
。这意味着聚合函数必须是单射函数。因此我们将 GNN
的聚合函数抽象为神经网络可以表示的、multiset
上的函数,并分析它们能否表示multiset
上的单射函数。
接下来我们使用这种思路来设计能力最强的 GIN
。最后我们研究了主流的 GNN
变体,发现它们的聚合函数本质上不是单射的因此能力较弱,但是它们能够捕获图的其它有趣的特性。
我们首先刻画 GNN-based
通用模型的最大表征能力。
理想情况下,能力最强大的 GNN
可以通过将不同的图结构映射到 embedding
空间中不同的representation
来区分它们。这种将任意两个不同的图映射到不同 embedding
的能力意味着解决具有挑战性的图同构问题。即,我们希望将同构图映射到相同的 representation
,将非同构图映射到不同的 representation
。
在我们的分析中,我们通过一个稍弱的准则来刻画 GNN
的表征能力:一种强大powerful
的、启发式heuristic
的、称作 Weisfeiler-Lehman(WL)
的图同构测试graph isomorphism test
。
WL-test
通常工作良好,但是也有一些例外,如正规图regular graph
。正规图是图中每个节点的 degree
都相同。如:立方体包含四个节点,每个节点的 degree
为 3
,记作 4k3
。
引理2
:令 non-isomorphic graph
。如果一个图神经网络 embedding
,则 WL-test
也会判定
证明:这里采用反证法。
假设经过 WL-test
无法区分 WL-test
中从迭代0
到迭代 label collection
都相同。
具体而言,label multiset
label
集合 WL-test
第label
。否则WL-test
在第 label collection
从而区分出
现在我们证明:如果
当 WL-test
和 GNN
都使用节点的特征向量来初始化。如前所述,对于任意 label
假设对于第
考虑第
根据第
由于两个图 AGGREGATE
函数和 COMBINE
函数。因此相同的输入(如邻域特征)产生相同的输出。因此有:
因此第
因此如果 WL-test
节点 label
满足 representation
集合 graph-level readout
函数对于节点representation
集合是排列不变的permutation invariant
,因此有
根据引理2
,任何基于聚合的 GNN
在区分不同图结构方面最多和 WL-test
一样强大。
一个自然的问题是:是否存在和 WL-test
一样强大的 GNN
?在定理3
中,我们将证明:如果邻域聚合函数和 graph-level readout
函数是单射的,则得到的 GNN
和 WL-test
一样强大。
定理3
:令 GNN
。在具有足够数量 GNN
层的条件下,如果满足以下条件,则 WL-test
判定为非同构的两个图 embedding
:
representation
:
其中 multiset
上。
graph-level readout
函数是单射函数。其中 readout
函数作用在节点embedding multiset
证明:令 WL-test
在
我们假设 representation
为:
其中
假设 WL-test
应用一个预定义的单射函数 label
:
其中
接下来我们通过数学归纳法证明:对于任意迭代轮次
当 WL-test
和 GNN
都使用节点的特征向量来初始化。如前所述,对于任意 label
假设对于
现在考虑第
由于单射函数的复合函数也是单射函数,因此存在某个单射函数
则有:
因此复合函数
因此对于任意迭代轮次
经过 WL-test
判定 label multiset
injectivity
, embedding
集合
对于可数集,单射性injectiveness
很好地描述了一个函数是否保持输入的唯一性distinctness
。节点输入特征是连续的不可数集则需要进一步考虑。
此外,刻画学到的 representation
在 embedding
空间中的邻近程度(如果两个 embedding
不相等的话)也很有意义。我们将这些问题留待以后的工作,本文重点放在输入节点特征来自可数集的情况,并仅考虑输出 representation
相等/不等的情况。
引理 4
:假设输入特征空间 GNN
第 size
有界的multiset
representation
证明:证明之前我们先给出一个众所周知的结论,然后将其简化:对于任意
现在回到我们的的引理证明。如果我们可以证明在可数集上的、size
有限的 multiset
上定义的任何函数 range
也是可数的,则对于任意
现在我们的目标是证明
首先,因为 layer
定义良好well-defined
的函数,因此很明显 multiset
由于两个可数集的并集也是可数的,因此 dummy
元素且不在
正如 multiset
的集合映射到
由于
我们对于
由于 multiset
size
有界,则存在
其中最后 dummy element
显然 size
有界的 multiset
这里还值得讨论 GNN
在图结构判别能力上的一个重要优点,即:捕获图结构的相似性。
WL-test
中的节点特征向量本质上是one-hot
编码,因此无法捕获 subtree
之间的相似性。
相反,满足定理3
条件的 GNN
将 subtree
嵌入到低维空间来推广WL-test
。这使得 GNN
不仅可以区分不同的结构,还可以学习将相似的图结构映射到相似的 embedding
从而捕获不同图结构之间的依赖关系。
捕获node label
的结构相似性有助于泛化generalization
,尤其是当subtree
的共现co-occurrence
很稀疏时、或者存在边噪音和/或节点特征噪音时。
在研究出能力最强的 GNN
的条件之后,我们接下来将设计一种简单的架构,即图同构网络Graph Isomorphism Network:GIN
。可以证明GIN
满足定理3
中的条件。
GIN
将 WL-test
推广从而实现了 GNN
的最大判别力。
为建模用于邻居聚合的 multiset
单射函数,我们研究了一种 deep multiset
理论,即:使用神经网络对 multiset
函数进行参数化。
我们的下一个引理指出:sum
聚合实际上可以表示为 multiset
上的通用单射函数。
引理5
:假设输入特征空间 size
的 multiset
unique
。进一步地,任何 multiset
函数
证明:我们首先证明存在一个映射 size
的 multiset
由于 multiset
cardinality
是有界的,则存在自然数 one-hot
向量或 N-digit
数字的压缩表示。因此 multiset
的单射函数。
permutation invariant
,因此它是定义良好的 well-defined
的multiset
函数。对于任意 multiset
函数
引理5
将 《Deep sets》
中的结论从 set
扩展到 multiset
。deep multiset
和 deep set
之间的重要区别是:某些流行的 set
单射函数 (如均值聚合)不再是 multiset
单射函数。
通过将引理5
中的通用 multiset
函数建模机制作为构建块 building block
,我们可以设想一个聚合方案,该方案可以表示单个节点及其邻域的 multiset
上的通用函数,因此满足定理3
中的第一个条件。
我们的下一个推论是在所有这些聚合方案中选择一个简单而具体的形式。
推论6
:假设 pair
对 unique
,其中 size
的 multiset
pair
上的函数
证明:接着推论5
的证明过程,我们考虑 5
。
令
我们用反证法证明。
对于任意
此时
根据推论5
该等式不成立,因为
我们重写
因为
对于定义在
注意:这样的 well-defined
,因为
由于通用逼近定理universal approximation theorem
,我们可以使用多层感知机multi-layer perceptrons:MLPs
来建模和学习推论6
中的函数
实际上我们使用一个 MLP
来建模 MLPs
可以表示组合函数。
在第一轮迭代中,如果输入特征是 one-hot
编码,则在求和之前不需要 MLP
,因为它们的求和本身就是单射的。
即:
我们将 GIN
的节点representation
更新方程为:
通常而言,可能存在很多其它强大的 GNN
。GIN
是这些能力强大的 GNN
中的一个简单的例子。
GIN
学到的节点 embedding
可以直接用于诸如节点分类、链接预测之类的任务。对于图分类任务,我们提出以下 readout
函数,该函数可以在给定每个节点embedding
的情况下生成整个图的 embedding
。
关于graph-level readout
函数的一个重要方面是:对应于 subtree
结构的 node embedding
随着迭代次数的增加而越来越精细化refine
和全局化global
。足够数量的迭代是获得良好判别力的关键,但是早期迭代的representation
可能会泛化能力更好。
为了考虑所有结构信息,我们使用来自模型所有深度的信息。我们通过类似于 Jumping Knowledge Networks
的架构来实现这一点。在该架构体系中,我们将 GIN
所有层的 representation
拼接在一起:
通过定理3
和推论6
,如果 GIN
使用求和函数(求和针对相同迭代轮次中所有节点的 representation
进行)替代了上式中的 READOUT
(因为求和本身就是单射函数,因此在求和之前不必添加额外的 MLP
),它就可证明地provably
推广了 WL-test
和 WL subtree kernel
。
现在我们研究不满足定理3
中条件的 GNN
,包括 GCN、GraphSAGE
。另外,我们对 GIN
的聚合器的两个方面进行消融研究:
MLP
。我们将看到:这些 GNN
变体无法区分很简单的图,并且比 WL-test
能力更差。尽管如此,具有均值聚合的模型(如 GCN
)在节点分类任务中仍然表现良好。为了更好地理解这一点,我们精确地刻画了哪些 GNN
变体可以捕获或无法捕获图结构,并讨论了图学习的意义。
引理 5
中的函数 multiset
映射到唯一的 embedding
。
MLP
可以通过通用逼近定理对 GNN
改为使用单层感知机 relu
)。这种单层映射是广义线性模型Generalized Linear Models
的示例。
因此,我们有兴趣了解单层感知机是否足以进行图学习。引理7
表明:确实存在使用单层感知机的图模型永远无法区分的网络邻域(multiset
)。
引理7
:存在有限size
的 multiset
证明:考虑示例 multiset
,但是它们的sum
结果相同。我们将使用 ReLU
的同质性homogeneity
。
令
因此得到:
引理7
的证明的主要思想是:单层感知机的行为和线性映射非常相似。因此 GNN
层退化为简单地对邻域特征进行求和。我们的证明基于以下事实:线性映射中缺少偏置项。使用偏置项和足够大的输出维度,单层感知机可能区分不同的 multiset
。
尽管如此,和使用 MLP
的模型不同,单层感知机(即使带有偏置项)也不是 multiset
函数的通用逼近器。因此,即使具有单层感知机的 GNN
可以在不同程度上将不同的图嵌入到不同的位置,此类embedding
也可能无法充分捕获结构相似性,并且可能难以拟合简单的分类器(如线性分类器)。
在实验中,我们观察到带单层感知机的 GNN
应用于图分类时,有时对于训练数据严重欠拟合underfit
。并且在测试集准确率方面要比带 MLP
的 GNN
更差。
如果我们把 GCN、GraphSAGE
中的那样,结果会如何?
均值池化和最大池化仍然是 multiset
上定义良好的函数,因为它们是排列不变的permutation invariant
。但是,它们不是单射函数。
下图按照表征能力对这三种聚合器(sum/mean/max
聚合器)进行排名rank
。左图给出了输入的 multiset
,即待聚合的网络邻域。后面的三幅图说明了给定的聚合器能够捕获 multiset
的哪个方面:
sum
捕获了完整的multiset
。mean
捕获了给定类型的元素的比例/分布。max
忽略了多重性 multiplicity
,将multiset
简化为简单的 set
。下图说明了 mean
池化和 max
池化无法区分的一对图结构。这里节点颜色表示不同的节点特征,我们假设 GNN
首先将邻域聚合在一起,然后再将它们与标记为 combine
在一起。
在两个图之间,节点 embedding
,即使它们的图结构是不同的。如前所述:sum
捕获了完整的multiset
;mean
捕获了给定类型的元素的比例/分布;max
忽略了多重性 multiplicity
,将multiset
简化为简单的 set
。
图 (a)
给出均值池化和最大池化都无法区分的图。这表明:均值池化和最大池化无法区分所有节点特征都相同的图。
图 (b)
给出最大池化无法区分的图。令 r
表示红色、g
表示绿色) 为 max
池化:collapse
到相同的 representation
(即使对应的图结构不同)。因此最大池化也无法区分它们。
相反,均值池化是有效的,因为
图(c)
给出均值池化和最大池化都无法区分的图。这表明:均值池化和最大池化无法区分节点特征分布相同的图。因为:
为了刻画均值聚合器能够区分的 multiset
类型,考虑两个multiset
:distinct
元素,但是 embedding
,因为均值聚合器只是对各元素特征取均值。
因此,均值聚合器捕获的是multiset
中元素的分布(比例),而不是捕获确切的 multiset
本身。
推论8
:假设 1
的整数。
证明:假设 multiset
1
的正整数。即 set
,并且 multiplicity
为
因此有:
现在我们证明存在一个函数 distributionally equivalent
的 unique
的。由于 multiset
cardinality
是有界的,因此存在一个数
如果某个任务中,图的统计信息和分布信息比确切结构更重要,则对于该任务使用均值聚合器可能会表现良好。
此外,当节点特征多种多样diverse
,且很少重复时,均值聚合器的能力几乎和 sum
聚合器一样强大。这可以解释为什么尽管存在限制(只能捕获 multiset
中元素的分布、而不是捕获确切的 multiset
本身),但是具有均值聚合器的 GNN
对于节点特征丰富的节点分类任务(如文章主题分类和社区检测)有效,因为邻域特征分布足以为任务提供强有力的信号。
最大池化将多个具有相同特征的节点视为仅一个节点(即,将 multiset
视为一个简单的 set
)。
最大池化无法捕获确切的结构或分布。但是,它可能适合于需要识别代表性元素或者骨架 skeleton
,而不适合需要区分确切结构或分布的任务。
实验表明:最大池化聚合器学会了识别3D
点云的骨架,并对噪声和离群点具有鲁棒性。为了完整起见,下一个推论表明最大池化聚合器捕获了 multiset
底层的 set
。
推论9
:假设 set
有
证明:假设 multiset
set
现在我们证明存在一个映射 set
的 unique
的。由于
其中 multiset
映射到它的 one-hot embedding
。
attention
加权平均的聚合器、 LSTM
池化聚合器。我们强调,我们的理论框架足以通用从而刻画任何基于聚合的 GNN
的表征能力。未来我们会研究应用我们的框架来分析和理解其它聚合方案。我们评估和对比了 GIN
以及能力较弱的 GNN
变体的训练和测试性能。
GNN
模型的表征能力。GNN
模型的泛化能力。数据集:我们使用9
种图分类benchmark
数据集,包括4
个生物信息学数据集(MUTAG, PTC, NCI1, PROTEINS
)、5
个社交网络数据集(COLLAB, IMDB-BINARY, IMDB-MULTI, REDDITBINARY and REDDIT-MULTI5K
) 。
社交网络数据集:
IMDB-BINARY
和 IMDB-MULTI
是电影协作collaboration
数据集。
每个图对应于演员的协作图,节点代表演员。如果两个演员出现在同一部电影中,则节点之间存在边。
每个图都来自于预先指定的电影流派 genre
,任务的目标是对图的流派进行分类。
REDDIT-BINARY
和 REDDIT-MULTI5K
是平衡的数据集。
每个图对应于一个在线讨论话题thread
,节点对应于用户。如果一个用户评论了另一个用户的帖子,则两个节点之间存在一条边。
任务的目标是将每个图分类到对应的社区。
COLLAB
是一个科学协作collaboration
数据集,它来自3
个公共协作数据集,即 High Energy Physics, Condensed Matter Physics, Astro Physics
。
每个图对应于来自每个领域的不同研究人员的协作网络。任务的目标是将每个图分类到所属的领域。
生物学数据集:
MUTAG
是包含 188
个诱变mutagenic
的芳香族aromatic
和异芳香族heteroaromatic
硝基化合物nitro compound
的数据集,具有 7
个类别。PROTEINS
数据集中,节点是二级结构元素secondary structure elements:SSEs
,如果两个节点在氨基酸序列或3D
空间中是邻居,则两个节点之间存在边。它具有3
个类别,分别代表螺旋helix
、片sheet
、弯 turn
。PTC
是包含344
种化合物的数据集,给出了针对雄性和雌性老鼠的致癌性,具有 19
个类别。NCL1
是美国国家癌症研究所公开的数据集,是化学化合物平衡数据集的子集balanced datasets of chemical compounds
。这些化合物经过筛选具有抑制一组人类癌细胞系生长的能力,具有 37
个类别。重要的是,我们的目标不是让模型依赖于节点的特征,而是主要从网络结构中学习。因此:在生物信息图中,节点具有离散categorical
的输入特征;而在社交网络中,节点没有特征。对于社交网络,我们按照如下方式创建节点特征:
REDDIT
数据集,我们将所有节点特征向量设置为相同。因此这里特征向量不带任何有效信息。degree
的 one-hot
编码作为节点特征向量。因此这里的特征向量仅包含结构信息。下表给出了数据集的统计信息。
baseline
方法:
WL sbuntree kernel
,其中使用 C-SVM
来作为分类器。
SVM
的超参数 C
以及WL
迭代次数通过超参数调优得到,其中迭代次数从{1,2,3,4,5,6}
之中选择。
state-of-the-art
深度学习架构,如 Diffusionconvolutional neural networks: DCNN
、PATCHY-SAN
、Deep Graph CNN: DGCNN
。
Anonymous Walk Embeddings:AWL
。
对于深度学习方法和 AWL
,我们报告其原始论文中的准确率。
实验配置:我们评估 GIN
和能力较弱的 GNN
变体。
在 GIN
框架下,我们考虑两种变体:
一种是通过梯度下降来学习
另一种是固定 GIN-0
。
时, GIN
的邻域聚合就是sum
池化(不包含当前节点自身)。
正如我们将看到的,GIN-0
将表现出强大的实验性能:GIN-0
不仅与
对于能力较弱的GNN
变体,我们考虑使用均值池化或最大池化替代GIN-0
中的 sum
聚合,或者使用单层感知机来代替 GIN-0
中的多层感知机。
这些变体根据使用的聚合器、感知器来命名。如 mean-1-layer
对应于GCN
、max-1-layer
对应于 GraphSAGE
,尽管有一些小的体系架构修改。
对于 GIN
和所有的 GNN
变体,我们使用相同的 graph-level readout
函数。具体而言,由于更好的测试性能,生物信息学数据集的 readout
采用sum
函数,而社交网络数据集的 readout
采用 mean
函数。
我们使用 LIB-SVM
执行 10-fold
交叉验证,并报告 10-fold
交叉验证中验证集准确率的均值和标准差。
对于所有配置 configurations
:
5
层 GNN layer
(包含输入层),并且 MLP
都有 2
层(它不算在 5
层 GNN
内)。hidden layer
应用 batch normalization
。0.01
的 Adam
学习器,并且每 50
个 epoch
进行学习率衰减 0.5
。超参数是针对每个数据集进行调优的:
16
或 32
;对于社交网络数据集,隐层维度为64
。batch size
为32
或 128
。dropout
在 dense
层后,dropout
比例为0
或 0.5
。epoch
数量通过 10-fold
交叉验证来确定。注意:由于数据集规模较小,因此使用验证集进行超参数选择极其不稳定。例如对于 MUTAG
,验证集仅包含 18
个数据点。因此上述有很多超参数是我们人工调优的。
我们也报告了不同 GNN
的训练准确率。其中所有的超参数在所有数据集上都是固定的(调优之后):5
层 GNN layer
(包括输入层)、hidden
维度为 64
、batch size = 128
、dropout
比例为 0.5
。
为进行比较,我们也报告了 WL subtree kernel
的准确率,其中迭代数量为 4
。这和 5 GNN layer
相当。
通过比较 GNN
的训练准确率,我们验证了我们关于表征能力的理论分析。具有较高表达能力的模型应该具有较高的训练准确率。下图给出了具有相同超参数设置的 GIN
和能力较弱的 GNN
变体的训练曲线。
首先,GNN
,它们都可以几乎完美地拟合训练集。
在我们的实验中,在拟合训练数据集这个方面 ,显式学习 0
的
相比之下,使用均值/最大值池化聚合、或者单层感知机的 GNN
变体在很多数据集中严重欠拟合。
具体而言,训练准确率模式和我们通过模型表征能力的排名相符:
MLP
的 GNN
变体要比采用单层感知机的 GNN
变体拟合训练集效果更好。sum
聚合器的 GNN
变体要比采用均值/最大值池化聚合的 GNN
变体拟合训练集效果更好。在我们的数据集上,GNN
训练准确率永远不会超过 WL subtree kernel
。
这是可以预期的,因为 GNN
的判别力通常比 WL-test
更低。例如在 IMDB-BINARY
数据集上,没有一个模型能够完美拟合训练集,而 GNN
最多可达到与 WL kernel
相同的训练准确率。
这种模式和我们的结果一致,即 WL-test
为基于聚合的 GNN
的表征能力提供了上限。但是, WL kernel
无法学习如何组合节点特征,这对于给定的预测任务非常有用。我们接下来会看到。
接下来我们比较测试准确率。尽管我们的理论分析并未直接提及 GIN
的泛化能力,但是可以合理地预期具有强大表达能力的 GNN
可以准确地捕获感兴趣的图结构,从而更好地泛化。
下表给出了 GIN
(Sum-MLP
) 、其它GNN
变体、以及state-of-the-art baseline
的测试准确率。表现最好的 GNN
以黑色突出显示。在有些数据集上 GIN
的准确率在所有 GNN
变体之间并非最高,但是和最佳 GNN
相比 GIN
仍然具有可比的性能,因此GIN
也已黑色突出显示。如果 baseline
的性能明显高于所有 GNN
,则我们用黑体和星号同时突出显示。
结论:
首先,GIN
,尤其是 GIN-0
,在所有 9
个数据集上均超越了(或者达到可比的)能力较弱的 GNN
变体,达到了 state-of-the-art
性能。
其次,在包含大量训练数据的社交网络数据集中,GIN
效果非常好。
对于 Reddit
数据集,所有节点都使用相同的特征,因此模型仅能捕获图结构信息。
GIN
以及 sum
聚合的 GNN
准确地捕获到图结构,并且显著优于其它模型。GNN
无法捕获图的任何结构,并且其测试准确率和随机猜测差不多。对于其它社交网络数据集,虽然提供了节点degree
作为输入特征,但是基于均值聚合的 GNN
也要比基于sum
聚合的 GNN
差得多。
对于 GIN-0
和 GIN-0
稍微、但是一致地超越了 GIN-0
相比
机器学习预测分子和材料的性质仍处于起步阶段。迄今为止,将机器学习应用于化学任务的大多数研究都围绕着特征工程展开,神经网络在化学领域并未广泛采用。这使人联想到卷积神经网络被广泛采用之前的图像模型image model
的状态,部分原因是缺乏经验证据表明:具有适当归纳偏置inductive bias
的神经网络体系结构可以在该领域获得成功。
最近,大规模的量子化学计算 quantum chemistry calculation
和分子动力学模拟molecular dynamics simulation
,加上高通量high throughput
实验的进展,开始以前所未有的速度产生数据。大多数经典的技术不能有效地利用现在的大量数据。假设我们能找到具有适当归纳偏置的模型,将更强大和更灵活的机器学习方法应用于这些问题的时机已经成熟。原子系统的对称性表明,在图结构数据上操作并对图同构graph isomorphism
不变的神经网络可能也适合于分子。足够成功的模型有朝一日可以帮助实现药物发现或材料科学中具有挑战性的化学搜索问题的自动化。
在论文 《Neural Message Passing for Quantum Chemistry》
中,作者的目标是为化学预测问题展示有效的机器学习模型,这些模型能够直接从分子图 molecular graph
中学习特征,并且对图同构不变 invariant
。为此,论文描述了一个在图上进行监督学习的一般框架,称为信息传递神经网络(Message Passing Neural Network: MPNN
)。MPNN
简单地抽象了现有的几个最有前景的图神经模型之间的共性,以便更容易理解它们之间的关系,并提出新的变体。鉴于许多研究人员已经发表了适合 MPNN
框架的模型,作者认为社区应该在重要的图问题上尽可能地推动这种通用方法,并且只提出由application
所启发的新变体,例如论文中考虑的应用:预测小有机分子的量子力学特性(如下图所示)。
最后,MPNN
在分子属性预测benchmark
上取得了 state-of-the-art
的结果。
论文贡献:
MPNN
框架 ,它在所有13
个目标target
上都取得了 SOTA
的结果,并在 13
个目标中的 11
个目标上预测到 DFT
的化学准确性。MPNN
,在 13
个目标中的5
个目标上预测到 DFT
的化学准确性,同时仅对分子的拓扑结构进行操作(没有空间信息作为输入)。node representation
的 MPNN
,而不需要相应地增加计算时间或内存,与以前的MPNN
相比,在高维node representation
方面产生了巨大的节省。作者相信论文的工作是朝着使设计良好的 MPNN
成为中等大小分子上的监督学习的默认方法迈出的重要一步。为了实现这一点,研究人员需要进行仔细的实证研究,以找到使用这些类型的模型的正确方法,并对其进行必要的改进。
相关工作:尽管原则上量子力学可以让我们计算分子的特性,但物理定律导致的方程太难精确解决。因此,科学家们开发了一系列的量子力学近似方法,对速度和准确率进行了不同的权衡,如带有各种函数的密度功能理论(Density Functional Theory: DFT
)以及量子蒙特卡洛 Quantum Monte-Carlo
。尽管被广泛使用,DFT
仍然太慢,无法应用于大型系统(时间复杂度为 DFT
表现出系统误差和随机误差。
《Combined first-principles calculation and neural-network correction approach for heat of formation 》
使用神经网络来近似 DFT
中一个特别麻烦的项,即交换相关势能 exchange correlation potential
,以提高DFT
的准确性。然而,他们的方法未能提高DFT
的效率,而是依赖于一大套临时的原子描述符 atomic descriptor
。另一个方向试图直接对量子力学的解进行近似,而不求助于 DFT
。这两个方向都使用了有固有局限性的手工设计的特征。
为简单起见我们考虑无向图。给定无向图
将无向图推广到有向的多图multigraph
(即多条边)也很容易。
GNN
的前向传播具有两个阶段:消息传递阶段、readout
阶段:
消息传递阶段执行 step
,它通过消息函数message function
update function
在消息传递阶段,节点
其中
readout
阶段根据所有节点在 embedding
向量
其中 readout
函数readout function
。
permutation invariant
从而使得 MPNN
对图的同构不变性graph isomorphism invariant
。
注意:你也可以在 MPNN
中通过引入边的状态向量
消息函数 readout
函数
《Convolutional Networks for Learning Molecular Fingerprints》
:
消息函数
节点更新函数
degree
,并且不同的 degree
使用不同的映射矩阵。sigmoid
函数。Readout
函数 skip connection
连接所有节点的所有历史状态
其中
这种消息传递方案可能是有问题的,因为得到的消息向量
Gated Graph Neural Networks:GG-NN
:
消息函数 edge label
label
是离散的。
节点更新函数 GRU
为Gated Recurrent Unit
。
该工作使用了权重绑定 weight tying
,因此在每个时间步都使用相同的更新函数。
即,它将每个节点的
个时间步视为一个序列。
Readout
函数 sigmoid
函数。
Interaction Networks
:该工作既考虑了 node-level
目标,也考虑了 graph-level
目标。也考虑了在节点上施加的外部效应。
graph-level
输出时,Readout
函数 1
。Molecular Graph Convolutions
:该工作和 MPNN
稍有不同,因为它在消息传递阶段更新了边的表示
消息函数
节点更新函数 relu
为 ReLU
非线性激活函数,
边更新函数:
其中
Deep Tensor Neural Networks
:
bias
向量。Readout
函数 Laplacian Based Methods
,例如GCN
:
消息函数
其中 deg(v)
为节点 degree
。
节点更新函数
将这些方法抽象为通用的 MPNN
的好处是:我们可以确定关键的实现细节,并可能达到这些模型的极限,从而指导我们进行未来的模型改进。
所有这些方法的缺点之一是计算时间。最近的工作通过在每个time step
仅在图的子集上传递消息,已经将 GG-NN
架构应用到更大的图。这里我们也提出了一种可以改善计算成本的 MPNN
修改。
我们基于 GG-NN
模型探索 MPNN
,我们认为 GG-NN
是一个很强的 baseline
。我们聚焦于探索不同的消息函数、输出函数,从而找到适当的输入 representation
以及正确调优的超参数。
消息函数探索:
矩阵乘法作为消息函数:首先考察 GG-NN
中使用的消息函数,它定义为
其中 edge label
label
是离散的。
Edge Network
:为了支持向量值的 edge
特征,我们使用以下消息函数:
其中 edge
特征
Pair Message
:前面两种消息函数仅依赖于隐状态
其中
当我们将上述消息函数应用于有向图时,将使用两个独立的函数
虚拟节点 & 虚拟边:我们探索了两种方式来在图中添加虚拟元素,从而修改了消息传递的方式(使得消息传播得更广):
虚拟边:在未连接节点pair
对之间添加虚拟边,这个边的类型是特殊类型。这可以实现为数据预处理步骤,并允许消息在传播阶段传播很长一段距离。
虚拟节点:虚拟一个 master
节点,该节点以特殊的边类型来连接到图中的每个输入节点。
此时master
节点充当全局暂存空间,每个节点都在消息传递的每个step
中从master
读取信息、向 master
写入信息。这允许信息在传播阶段传播很长的距离。
我们允许 master
节点具有单独的节点维度 master
节点在内部状态更新函数中使用单独的权重矩阵。
由于加入了 master
节点,理论上模型复杂度有所增加,并提升了模型型容量。
Readout
函数:我们尝试了两种 Readout
函数。
一种是在 GG-NN
中使用的 Readout
函数:
另一种是 Set2Set
模型,该模型专门为Set
输入而设计的,并且比简单地累加final node state
具有更强的表达能力。
该模型首先将线性投影应用于每个元组 set
的元组投影作为输入。然后,在经过 step
之后,Set2Set
模型将产生 graph-level embedding
embedding
对于set
的顺序具有不变性。我们将这个 embedding
Multiple Towers
:MPNN
的一个问题是可扩展性,特别是对于稠密图。消息传递阶段的每个 step
需要
我们将 embedding
embedding
embedding
。
然后我们在每个隐空间 embedding
最后这 embedding
结果通过以下方式混合:
其中:
这种混合方式保留了节点的排列不变性permutation invariant
,同时允许图的不同embedding
在传播阶段相互交流。
这种方法是有利的,因为对于相同数量的参数数量,它能产生更大的假设空间,表达能力更强。并且时间复杂度更低。当消息函数是矩阵乘法时,某种 embedding
的传播step
花费 embedding
,因此总的时间复杂度为
Multiple Towers
就是multi-head
的思想。
数据集:QM-9
分子数据集,包含 130462
个分子。我们随机选择 10000
个样本作为验证集、10000
个样本用于测试集、其它作为训练集。特征(如下表所示)和 label
的含义参考原始论文。
我们使用验证集进行早停和模型选择,并在测试集上报告mean absolute error:MAE
。
结论:
13
个目标进行联合训练。MPNN
变体使用edge network
消息函数。master
节点、将 graph-level
输出修改为 Set2Set
输出对于 13
个目标都有帮助。Multiple Towers
不仅可以缩短训练时间,还可以提高泛化性能。具体实验细节参考原始论文。
下图中,enn-s2s
表示最好的 MPNN
变体(使用 edge network
消息函数、set2set
输出、以及在具有显式氢原子的图上操作),enn-s2s-ens5
表示对应的 ensemble
。
在半监督节点分类任务中,我们需要学习带标签的样本,然后对未标记样本进行预测。为更好地对节点进行分类,基于拉普拉斯平滑性假设Laplacian smoothing assumption
,人们提出了消息传递模型来聚合节点邻域的信息从而获得足够的事实fact
来对未标记节点产生更可靠的预测。
通常有两种实现消息传递模型的实用方法:
Graph Neural Network:GNN
:通过神经网络执行特征传播feature propagation
以进行预测。Label Propagation Algorithm:LPA
:跨 graph adjacency matrix
的标签传播 label propagation
来进行预测。由于 GNN
和 LPA
基于相同的假设:通过消息传播进行半监督分类。因此有一种直觉认为:将它们一起使用可以提高半监督分类的性能。已有一些优秀的研究提出了基于该想法的图模型。例如,APPNP
和 TPN
通过将 GNN
和 LPA
拼接在一起,GCN-LPA
使用 LPA
来正则化 GCN
模型。但是,如下表所示,上述方法仍然无法将 GNN
和 LPA
共同融入消息传递模型,从而在训练和预测过程中同时传播特征和标签。
为了统一特征传播和标签传播,主要有两个问题需要解决:
聚合特征信息和标签信息:由于节点特征是由embedding
表达的,而节点标签是一个 one-hot
向量。它们不在同一个向量空间中。
此外,它们的信息传递方式也不同:GNN
可以通过不同的神经网络架构来传播信息,如GraphSAGE
、GCN
和 GAT
;但是 LPA
只能通过图邻接矩阵来传递标签信息。
监督训练:用特征传播和标签传播进行监督训练的模型不可避免地会在 self-loop
标签信息中出现过拟合,这使得在训练时出现标签泄漏 label leakage
,导致预测的性能不佳。
受NLP
发展的启发,论文《Masked label prediction: unified message passing model for semi-supervised classification》
提出了一个新的统一消息传递模型 Unified Message Passing:UniMP
,并且使用带 masked label prediction
的 UniMP
来解决上述问题。UniMP
模型可以通过一个共享的消息传递网络将特征传播和标签传播xx,从而在半监督分类中提供更好的性能。
UniMP
是一个多层的 Graph Transformer
,它使用 label embedding
来将节点标签转换为和节点特征相同的向量空间。
一方面,UniMP
像之前的 attention-based GNN
一样传播节点特征;另一方面,UniMP
将multi-head attention
视为转移矩阵从而用于传播 label vector
。因此,每个节点都可以聚合邻域的特征信息和标签信息。
即,
label vector
的转移矩阵来自于attention
,而不是来自于图的邻接矩阵。
为了监督训练 UniMP
模型而又不过拟合于self-loop
标签信息,论文从 BERT
中的 masked word prediction
中吸取经验,并提出了一种 masked label prediction
策略。该策略随机mask
某些训练样本的标签信息,然后对其进行预测。这种训练方法完美地模拟了图中标签信息从有标签的样本到无标签的样本的转移过程。
论文在 Open Graph Benchmark:OGB
数据集上对三个半监督分类数据集进行实验,从而证明了 UniMP
获得了 state-of-the-art
半监督分类结果。论文还对具有不同输入的模型进行了消融研究,以证明 UniMP
方法的有效性。此外,论文还对标签传播如何提高 UniMP
模型的性能进行了最彻底的分析。
定义图
每个节点
每条边
每个节点 one-hot
表示为 one-hot
构成标签矩阵
实际上在半监督节点分类任务中,大部分节点的标签是未知的。因此我们定义初始标签矩阵 one-hot
标签向量或者全零向量组成:对于标记节点,它就是标签的 one-hot
向量;对于未标记节点,它就是全零的向量。
图的邻接矩阵定义为 degree
。
归一化的邻接矩阵定义为
特征传播Feature Propagation
模型:在半监督节点分类中,基于拉普拉斯平滑假设,GNN
将节点特征
GNN
的特征传播范式为:在第
其中:
representation
矩阵,final embedding
矩阵 标签传播Label Propagation
模型:LPA
假定相连节点之间的标签是平滑的,并在整个图上迭代传播标签。
LPA
的特征传播范式为:在第
其中
在 LPA
中,标签信息通过归一化的邻接矩阵
UniMP
整体架构如下图所示。我们采用了 Graph Transformer
并结合使用label embedding
来构建 UniMP
模型,从而将上述特征传播和标签传播结合在一起。
Graph Transformer
:由于 Transformer
已经在 NLP
中被证明功能强大,因此我们将常规的 multi-head attention
应用到 graph learning
中。
给定节点representation
集合 multi-head attention
:
其中:
head
的隐层大小。head attention
。我们首先将 source feature
query
向量 distant feature
key
向量 edge feature
key
向量作为额外的信息。编码过程中使用了可训练的参数
edge feature
跨层共享。在计算注意力系数时,edge feature
作为key
的附加信息。
当得到 graph multi-head attention
,我们聚合节点
注:这里的公式和上面的架构图不匹配。根据公式中的描述,残差应该连接在
Graph Transformer
层之后。即:残差连接 ->LayerNorm
->ReLU
。
其中:
节点embedding
value
向量考虑了和 。
和特征传播相比,multi-head attention
矩阵代替了原始的归一化邻接矩阵作为消息传递的转移矩阵(类似于 GAT
)。另外,我们提出一个层间的门控残差连接gated residual connection
来防止过度平滑oversmoothing
。
门控机制由
所提供,它因节点的不同而不同、因层深(即 )的不同而不同。
类似于 GAT
,如果我们在输出层应用 Graph Transformer
,则我们对multi-head output
应用均值池化(并且没有 LayerNorm
和 relu
):
Label Embedding and Propagation
:我们提出将部分观测到的标签信息 embed
到节点特征相同的空间中:label embedding
向量和未标记节点的零向量。
然后,我们通过简单地将节点特征和标签特征相加得到传播特征 propagation feature
:
我们可以证明,通过将部分标记的
证明:令 Graph Transformer
中的attention
矩阵(即 edge feature
,并且 bias
向量。那么我们有:
其中 APPNP
中预定义的超参数。
为简单起见,我们取
其中
因此我们发现UniMP
模型可以近似分解为特征传播
已有的GNN
相关工作很少考虑在训练和推断阶段都使用部分观测的标签。大多数工作仅将这些标签信息作为ground truth target
,从而监督训练模型参数
其中
但是,我们的 UniMP
模型会传播节点特征和标签信息从而进行预测:inference
性能很差。
我们向BERT
学习,它可以 mask
输入的 word
并预测被 masked
的word
从而预训练BERT
模型。有鉴于此,我们提出了一种 masked label prediction
策略来训练我们的模型。训练过程中,在每个iteration
,我们随机屏蔽部分节点标签为零并保留剩余节点标签,从而将 label_rate
所控制(label_rate
表示保留的标签比例)。
假设被 masked
之后的标签矩阵为
其中: masked
标签的节点数量,masked
标签。
每个
batch
内的target
节点的label
都是被屏蔽掉的。否则的话,对target
节点预测标签会发生标签泄漏。
通过这种方式,我们可以训练我们的模型从而不会泄露self-loop
标签信息。
这篇论文就是一篇水文,其思想就是把
node label
作为一个节点特征拼接到原始节点特征上去(当然,目标节点拼接全零信息而不是node label
从而防止信息泄露),然后在所有输入的特征上执行随机mask
。
在推断过程中,我们可以将所有
数据集:和实际工程应用的图相比,大多数论文常用的图数据集规模很小。GNN
在这些论文数据集上的性能通常不稳定,因为数据集太小、不可忽略的重复率或泄露率、不切实际的数据切分等。
最近发布的 OGB
数据集克服了常用数据集的主要缺点,它规模更大、更有挑战性。OGB
数据集涵盖了各种现实应用,并覆盖了多个重要领域,从社交网络、信息网络到生物网络、分子图、知识图谱。它还覆盖了各种预测任务,包括node-level
预测、graph-level
预测、edge-level
预测。
因此我们在该数据集上进行实验,并将 UniMP
和 SOTA
模型进行比较。如下表所示,我们对三个 OGBN
数据集进行实验,它们是具有不同大小的不同任务。其中包括:
ogbn-products
:关于 47
种产品类别的分类(多分类问题),其中每个产品给出了 100
维的节点特征。ogbn-proteins
:关于 112
种蛋白质功能的分类(多标签二分类问题),其中每条边并给出了 8
维的边特征。ogbn-arxiv
:关于 40
种文章主题的分类(多分类问题),其中每篇文章给出了 128
维的节点特征。实现细节:
这些数据集大小或任务各不相同,因此我们使用不同的抽样方法对模型进行评估。
ogbn-products
数据集中,我们在训练期间每一层使用 size=10
的 NeighborSampling
来采样子图,并在推断期间使用 full-batch
。ogbn-proteins
数据集中,我们使用随机分区Random Partition
将稠密图拆分为子图,从而训练和测试我们的模型。训练数据的分区数为 9
、测试数据的分区数为 5
。ogbn-arxiv
数据集中,我们对训练数据和测试数据进行full batch
处理。我们为每个数据集设置了模型的超参数,如下表所示。label rate
表示我们在应用 masked label prediction
策略期间保留的标签比例。
我们使用 lr=0.001
的Adam
优化器来训练模型。此外,我们在小型 ogbn-arxiv
数据集中将模型的权重衰减设置为 0.0005
来缓解过拟合。
所有的模型都通过 PGL
以及 PaddlePaddle
来实现,并且所有实验均在单个 NVIDIA V100 32 GB
上实现。
实验结果:baseline
方法和其它SOTA
方法均由 OGB
排行榜给出。其中一些结果是原始作者根据原始论文官方提供,其它结果由社区重新实现的。并且所有这些结果都保证可以用开源代码复现。
按照 OGB
的要求,我们对每个数据集运行 10
次实验结果,并报告均值和标准差。如下表所示,我们的 UniMP
模型在三个 OGBN
数据集上都超过所有其它模型。由于大多数模型仅考虑基于特征传播来优化模型,因此结果表明:将标签传播纳入 GNN
模型可以带来重大改进。
具体而言:
UniMP
在 gbn-products
中获得了 82.56%
的测试准确率,相比 SOTA
取得了 1.6%
的绝对提升。UniMP
在 gbn-proteins
中获得了 86.42%
的测试 ROC-AUC
,相比 SOTA
取得了 0.6%
的绝对提升。UniMP
在 gbn-arxiv
中获得了 73.11%
的测试准确率,相比 SOTA
实现了0.37%
的绝对提升。 作者没有消融研究:
- 不同
label_rate
对于模型性能的变化(当label_rate = 0
时表示移除标签传播)。- 除了
Graph Transformer
之外,UniMap
采用其它base model
的效果是否也很好。
摘要:GNN
是在图上学习的主要技术。然而,人们对 GNN
在实践中取得成功的原因、以及它们是否是良好性能所必需的了解相对较少。在这里,论文表明:对于许多标准的 transductive node classification benchmark
,可以结合忽略图结构的浅层模型、以及利用标签结构中相关性的两个简单后处理步骤,从而超过或匹配 SOTA
的 GNN
的性能。这些后处理步骤利用了标签结构label structure
中的相关性:
error correlation
:它将训练数据中的残差residual error
扩散,从而纠正测试数据中的误差。prediction correlation
:平滑了测试数据上的预测结果。论文的这个pipeline
称作 “矫正和平滑”Correct and Smooth:C&S
。论文的方法在各种transductive
节点分类 benchmark
上都超过或接近了SOTA GNN
的性能,而参数规模小得多,运行速度也快了几个量级,并可以轻松scale
到大型图。例如在 OGB-Products
数据集上,论文的方法相比于著名的 GNN
模型减少了 137
倍参数、提高了 100
倍的训练时间,并且效果还更好。还可以将论文的技术整合到大型 GNN
模型中,从而获得适度的收益。
引言:Graph Neural Network: GNN
目前在图数据领域取得巨大成功,并且经常排在 Open Graph Benchmark
等排行榜的榜首。通常 GNN
的方法论都围绕着创建比基本变体(如 GCN,GraphSAGE
)更具有表达力的体系架构,如GAT、GIN
以及其它各种深度模型。然而,随着这些模型变得越来越复杂,理解它们的性能为什么提升是一个重大挑战,而且将它们扩展到大型数据集也很困难。
相反,论文 《Combining label propagation and simple models out-performs graph neural networks》
研究了结合更简单的模型来获得收益。为此,论文提出了一个简单的 pipeline
,它包含三个主要部分(如下图所示):
base prediction
:使用忽略图结构(如 MLP
或线性模型)的节点特征进行基础预测base prediction
。correction step
:将训练数据中的误差传播到整个图,从而校正基础预测。smoothing
:最后,对图上的预测进行平滑。这里第二步和第三步只是后处理post-processing
,并且使用经典的标签传播 label propagation: LP
技术进行基于图的半监督学习。在该框架中,图结构不是用来学习参数的,而是作为一种后处理机制。这种简单性导致模型的参数数量减少,训练时间也减少了几个数量级,并且可以很容易地扩展到大型图。还可以将论文的思想与SOTA
的 GNN
结合起来,从而得到适度的性能提升。
论文性能提升的一个主要来源是:直接使用标签进行预测。这个思想并不新鲜,早期的 diffusion-based
的图半监督学习算法(如spectral graph transducer
、Gaussian random field model
和 label spreading
)都使用了这个思想。然而,这些方法的动机是对点云数据进行半监督学习,所以特征被用来构建图。然后,这些技术被用于仅从标签(即没有特征)来在关系数据上学习,而这种学习方式在 GNN
中基本上被忽略了。即,作者发现:即使是简单的标签传播(忽略了特征)在一些 benchmark
上也有令人惊讶的表现。这启发了作者结合结合两个正交的预测能力:一个预测能力来自节点特征(忽略图形结构),一个预测能力来自在预测中直接使用已知标签。
最近的研究将GNN
与标签传播label propagation
以及马尔科夫随机场Markov Random field
联系起来,一些技术在特征中使用标签信息的临时融合 (如 UniMP
)。然而,这些方法的训练成本仍然很高,而论文以两种可以理解的低成本方式使用标签传播:论文从一个无视图结构的模型开始进行廉价的 "基础预测";之后,论文使用标签传播进行纠错,然后对最终预测进行平滑处理。
这些后处理步骤是基于 error
和 label
在相连节点上是正相关的这一事实。假设相连节点之间的相似性是许多网络分析的中心,并对应于同质性 homophily
或同源混合assortative mixing
。在半监督学习文献中,类似的假设是平滑性 smoothness
或聚类假设 cluster assumption
。论文在各种数据集上看到的标签传播的良好表现表明:这些相关性在普通 benchmark
上是成立的。
总的来说,论文的方法表明:结合几个简单的思想,可以在模型大小(即参数数量)和训练时间方面,以很小的成本产生出色的transductive
节点分类性能。例如,在 OGB-Product benchmark
上,论文的表现超过了目前最著名的 GNN
,参数数量少了两个数量级,训练时间少了两个数量级。然而,论文的目标并不是说目前的 graph learning
方法很差或不合适。相反,论文的目标是强调提高 graph learning
预测性能的更容易的方法,并更好地理解性能提高的来源。论文的主要发现是:将标签更直接地纳入学习算法中是关键。而通过将论文的思想与现有的 GNN
相结合,也可以看到改进,尽管这些改进是微小的。作者希望论文的方法能够激发新的思想,帮助其他的 graph learning
任务,如inductive
节点分类、链接预测和图预测。
下图为C&S
方法的概览。左图表示数据集中有两个类别:橙色和蓝色。
MLP
进行基础预测,从而忽略了图结构。这里假设所有节点都给出了相同的预测。相关工作:
Approximate Personalized Propagation of Neural Predictions:APPNP
框架是和我们工作最相关的,因为它们也是平滑了基础预测。但是,他们专注于将这个平滑处理集成到训练过程中,以便可以端到端地训练他们的模型。这种方式不仅显著增加计算成本,而且还使 APPNP
无法在推断时纳入标签信息。
和 APPNP
相比,我们的框架可以产生更准确的预测、训练速度更快,并且更容易scale
到大规模图数据。
我们的框架还补充了 Simplified Graph Convolution
,以及旨在提高可扩展性的算法。然而,我们的方法的主要重点是直接使用标签,而可扩展性是一个副产品。
之前也有将 GCN
和标签传播联系起来的工作:
《Unifying graph convolutional neural networks and label propagation》
将标签传播作为预处理步骤从而用于 GNN
的edge
加权,而我们将标签传播作为后处理步骤并避免使用 GNN
。《Residual correlation in graph neural network regression》
将具备标签传播的GNN
用于回归任务,我们的 error correction
步骤将他们的一些思想适配为分类的情况。最后,最近有几种方法将非线性纳入标签传播从而与 GNN
竞争并实现可扩展性,但这些方法专注于 low label rate setting
,并且没有纳入 feature learning
。
给定无向图
每个节点
令 degree
度矩阵,
节点集合
one-hot
向量 one-hot
向量记作全零 所有节点标签的 one-hot
向量组成标签矩阵
进一步地,我们将标记节点集合
我们任务的目标是:给定
C&S
方法从基于节点特征的、简单的 base predictor
开始,这个 predictor
不依赖于对图的任何学习。然后执行两种类型的标签传播:
base prediction
,即误差平滑性。标签传播只是后处理步骤post-processing step
,因此我们的 pipeline
没有端到端的训练。
在 C&S
方法中,图数据仅在这些后处理步骤和预处理步骤 pre-processing step
中使用(比如构建节点特征),和标准的 GNN
模型相比,这使得训练更快且可扩展性更好。
图数据在预处理步骤中用于生成节点
embedding
,从而增强特征。
此外, C&S
方法同时使用了标签传播和节点特征,这些互补的信号会产生更出色的预测结果。
标签传播本身往往在没有特征的情况下也表现得很出色。
首先我们使用不依赖于图结构的、简单的base predictor
。具体而言,我们首先训练模型
其中:
one-hot
向量。所有损失在标记的训练集
本文选择 multilayer perceptron: MLP
后接一个softmax
输出层。这种 base predictor
忽略图结构,因此可以避免 GNN
的可扩展问题。不过我们可以使用任何 base predictor
,甚至包括 GNN
的 base predictor
。
但是,为了使得我们的 pipeline
简单且可扩展,我们仅使用线性模型或者 MLP
作为 base predictor
。
接下来我们通过融合标签信息来提高 base prediction
的准确率。核心思想是:我们预期基础预测的误差在图上正相关。换句话讲:节点
我们在图上传播spread
这种误差相似性。我们的方法在某种程度上受到残差传播的启发。在残差传播中,类似的概念用于节点回归任务。
为此,我们定义一个误差矩阵
其中:
base predictor
做出完美预测时,误差矩阵才为零。现在我们已知误差矩阵
应该是在训练集上和误差矩阵
比较接近。
因此我们使用标签扩散技术来平滑误差,优化目标:
其中:
第一项鼓励误差估计在图上的平滑性。这等价于:
的解就是 。
第二项使得最终的解接近已知的真实误差
这个目标函数可以通过迭代来求解:
其中:
该迭代方程快速收敛到
一旦得到平滑误差
我们强调这是一种后处理技术,没有和base predictor
相结合的训练过程。
在回归问题中,基于高斯假设,这种方式的误差传播被证明是正确的方法。但是对于分类问题,平滑误差
考虑到:
其中
因此,传播没有足够多的总质量total mass
,所以传播无法完全纠正图中所有节点上的误差。并且,实验发现调整残差的比例实际上可以提供帮助。
有鉴于此,我们提出了两种缩放残差的方法:
autoscale
:直观地,我们希望将
由于我们仅知道训练节点上的真实误差,所以我们用训练节点上的平均误差来计算这个缩放比例。
形式上,令
其中
然后我们将未标记节点
其中
FDiff-scale
:另一种方法,我们可以选择一种扩散方法,该方法在标记节点上(包括训练集和验证集)保持真实误差
具体而言,我们在未标记节点上迭代平滑误差为:
迭代过程中固定
直观地看,这将在标记节点
另外,我们仍然发现学习缩放的超参数
现在我们得到每个节点 score vector
base predictor
为了做出最终预测,我们进一步对校正后的预测进行平滑处理。这样做的动机是:图中相邻的节点可能具有相似的标签,这在网络同质性homophily
或者分类混合assortative mixing
的属性下是可以预期的。
因此,我们通过另一个标签传播来鼓励图上标签分布的平滑性。
首先我们定义标签矩阵的最优猜测
我们也可以在验证节点上使用真实标签,这将在后面的实验中讨论。
然后我们使用迭代公式:
其中
我们迭代上式直到收敛,从而得到最终预测
最终测试节点
和误差校正一样,这里的预测平滑是一个后处理步骤。这里的预测平滑在本质上类似于 APPNP
,我们稍后将其进行比较。但是,APPNP
是端到端训练的,在最后一层 representation
上进行传播而不是 softmax
,不使用标签,并且动机不同。
回顾我们的 pipeline
:
首先,我们从低成本的基础预测
然后,我们通过在训练数据上传播已知真实误差来估计平滑误差
将训练节点的真实误差传播到所有节点。注意,我们仅关心测试节点的误差,因为测试误差需要用于纠正测试节点的预测标签。而训练节点的标签是已知的,直接使用
ground-truth
。
最后,我们通过另外一个标记传播步骤将校正预测与已知标签相结合,从而生成平滑的最终预测。
标签传播时,训练节点传播的是真实标签,测试节点传播的是预测标签。
我们将这个通用的 pipeline
称作 Correct and Smooth:C&S
。
其核心就是两个平滑:误差平滑、输出平滑。
在显示该 pipeline
在 transductive
节点分类上实现 SOTA
性能之前,我们简要介绍了另一种提高性能的简单方法:特征增强。
深度学习的标志是:我们可以自动学习特征而不是手动的特征工程,但是GNN
仍然依靠输入的特征来执行预测。
有很多方法可以从图拓扑中获取有用的特征来扩展原始节点的特征。在我们的 pipeline
中,我们使用来自矩阵 eigenvector
作为规范化的谱域嵌入regularized spectral embedding
,从而增强特征。这里:
degree
。degree
。虽然底层的矩阵是稠密的,但是我们可以应用矩阵向量乘法,并使用迭代的特征向量求解器eigensolver
来在 embedding
。
在论文的实验部分,作者在进行训练速度的比较时没有考虑计算
spectral embedding
的预处理时间,因此是不公平的比较。此外,计算spectral embedding
对于大图而言是不可行的。
数据集:为证明我们方法的效果,我们使用了九个数据集,其中包括:
Open Graph Benchmark:OGB
中的 Arxiv
数据集和 Products
数据集:标签为论文类别或商品类别,特征从文本内容派生而来。benchmark
数据集 Cora,Citeseer,Pubmed
:标签为论文类别,特征从文本内容派生而来。web graph
数据集 wikiCS
::标签为网页类别,特征从文本内容派生而来。Rice University
的Facebook
社交网络数据集:类别为宿舍 dorm residence
,特征为画像诸如性别、专业、班级等属性。US County
数据:类别为 2016
年选举结果,特征为人口统计特征。email
数据集:类别为成员的部门,没有特征。数据集的统计信息如下所示。另外我们还给出了我们方法相比较于 SOTA GNN
:参数数量降低的比例、准确率的提升(绝对值)、以及我们方法的训练时间(秒)。结果表明:通过避免使用昂贵的 GNN
,我们的方法需要较少的参数、更快的训练速度,并且通常得到更准确的结果。
数据集拆分:
Arxiv
数据集和 Products
数据集中,训练集、验证集、测试集的拆分由benchmark
本身来提供。wikiCS
数据集的拆分,我们和 《A wikipedia-based benchmark for graph neural networks》
的拆分一致。Rice, US County, Email
数据集,我们随机拆分为 40%/10%/50%
。60%/20%/20%
的随机拆分。我们并没有采用很低的 label rate
,这是为了改善数据集对于超参数的敏感性。
在我们的所有实验中,不同拆分的预估准确率标准差在 1%
以内,并且通常不会改变我们的定性比较。
base predictor
和 baseline
:
base predictor
:
Linear
和 MLP
模型作为简单的 base predictor
,其中输入特征是原始节点特征和 spectral embedding
。Plain Linear
作为base predictor
进行比较。变种:我们对比了仅使用 base predictor
的方法、使用 autoscale
和 FDiff-scale
的方法。
baseline
:
我们对标签传播 Label Propagation
模型进行比较。
我们选择 GCN, SGC, APPNP
作为对比的 GNN
模型。对于 GCN
模型,我们将输入到每一层、以及从每一层到输出层都添加了额外的残差链接 residual connection
,从而产生了更好的效果。GCN
的层数、隐层维度和 MLP
相同。
注意:这里的 GCN
一种 GCN
风格的模型,而不是原始的、Kipf&Welling
提出的模型。
最后,我们还包含了几个 state-of-the-art
的 baseline
:
Arxiv
和 Product
数据集,我们使用 UniMP
模型。该模型在 2020-10-01
位于 OGB
排行榜的榜首。Cora,Citeseer,Pubmed
数据集,我们复用《 Simple and deep graph convolutional networks》
论文给出的最好的结果。Email
和 US County
数据集,我们使用 GCNII
模型。Rice31
,我们使用带spectral embedding
的 GCN
、以及带 node2vec embedding
的 GCN
。这是我们发现的、效果最好的 GNN-based
模型。WikiCS
,我们使用 APPNP
。对于所有模型,我们通过验证集来选择一组固定的超参数。
在平滑预测阶段,我们仅在训练节点上使用真实标签,即:
下表给出了实验结果,其中 Base Prediction
表示仅使用基础预测而没有任何后处理;Autoscale
和 FDiff-scale
表示使用不同的平滑预测缩放方式。
我们重点介绍一些重要发现:
首先,在我们模型中C&S
后处理带来可观的收益。例如在 Product
数据集上,应用了后处理之后 MLP base prediction
的测试准确率从 63%
提升到 84%
。
其次,在很多case
中:
C&S
的 Plain Linear
模型也足以战胜常规的 GCN
模型。LP
(一种没有可训练参数的方法)通常与 GCN
具有相当的竞争力。鉴于 GCN
的主要动机是解决连接的节点可能没有相似的标签的事实,这一点令人惊讶。我们的结果表明:通过简单地使用特征从而将相关性融合到图中,这通常是一个更好的主意。
第三,我们模型的变体在 Product,Cora,Email,Rice31, US County
上的表现优于 SOTA
。在其它数据集上,我们表现最好的模型和 SOTA
之间没有太大差异。
为了了解直接使用 ground truth
标签有多大帮助,我们还尝试了没有标签的 C&S
版本,其中不执行C&S
步骤,而是使用《Learning with local and global consistency》
中的方法来平滑 base predictor
的输出,我们称这个版本为 Basic Model
。即:
base predictor
的训练。base predictor
预测结果的平滑。这里面缺少了误差的平滑,仅保留预测结果的平滑。
结果如下表所示。我们看到:
Linear
和 MLP
的 base predictor
通常可以超过 GCN
的性能。这些结果再次表明输出平滑非常重要,而 GCN
的原始动机具有误导性。相反,我们假设 GCN
可以通过平滑图上的输出来获得性能提升。这与 《Simplifying graph convolutional networks》
的观察类似。Basic Model
和上图中使用 C&S
的方法之间仍然存在性能差异。
Plain Linear
缺少了节点的spectral embedding
特征。
下表给出了仅使用误差校正,但是未使用平滑预测的实验结果。
实验结果表明:误差校正、平滑预测这两个标签传播步骤对于最终效果提升都是至关重要的。
可以使用验证标签是我们方法的优势,这甚至可以进一步提升我们框架的性能。
在平滑预测阶段,我们在训练节点和验证节点上使用真实标签,即:
注意:我们不使用验证标签来训练 base predictor
模型,而是用于选择 base predictor
的超参数。
通过引入验证集标签,更多的节点被指定了
ground-truth
,因此网络中传播的信息量更大。
下表给出了实验结果(另外,数据集统计信息表给出了相对于 SOTA
的收益)。应用了验证标签之后,我们的最佳模型在 9
个数据集中的 7
个中超越了 SOTA
,并且具有可观的收益。
可以看到:
GNN
并没有这种优势,因为它们通常依靠早停来防止过拟合,可能并不总是从更多数据中受益(比如,在标签分布偏移 shift
的情况下),并且不直接使用标签。transductive
节点分类,要获得良好的性能,实际上并不需要大型的而且昂贵的GNN
模型。base predictor
相结合,在这些任务上的性能超越了 GNN
模型。和 GNN
以及其它 SOTA
解决方案相比,我们的 C&S
框架通常需要更少的参数。例如我们在下图绘制了 Product
数据中,不同模型的参数和性能的关系。
我们的方法不仅使用更少的参数,但真正的收益在于训练时间更快。和具有可比准确率的模型相比,我们的模型的训练时间要快几个量级。因为我们的 base prediction
不需要使用图结构。例如:
Arxiv
数据集上,我们的 MLP+C&S
模型和 GCN + label
的模型具有相似的参数数量。但是我们的模型训练中,每个 epoch
的训练速度要快 7
倍,并且收敛速度更快。Products
数据集上,和 SOTA
相比,我们的 linear base predictor +C&S
模型具有更高的准确率,训练速度提高了 100
倍、参数数量减少了 137
倍。papers 100M
上评估了我们的方法。这里我们以 Linear + C&S
模型,可以达到 65.33%
的准确率,比 SOTA
的 63.29%
更高。这种比较是不公平的比较,因此
C&S
方法需要节点的spectral embedding
作为输入,这通常是非常昂贵的且通常无法扩展到大型图。一种解决办法是用DeepWalk
来得到node emebdding
,但是这种预处理也非常耗时。如果没有
spectral embedding
(即,Plain Linear
),则C&S
的效果出现巨大的下降。而且这种依赖于人工特征工程(虽然是通过graph embedding
自动计算得到)的方式不太鼓励,因为强烈依赖于经验。
一般而言,我们的 pipeline
还可以用于改善 GNN
的性能。我们将误差校正、平滑预测应用到了更复杂的 base predictor
上,诸如 GCNII
和 GAT
。
实验结果如下表所示。这提升了我们在某些数据集上的结果,包括在 Arxiv
上击败了 SOTA
。但是,有时性能提升只是很小的,这表明大型模型可能正在捕获与我们简单的 C&S
框架相同的信号。
为了帮助理解 C&S
框架的性能,我们在 US County
数据集上的预测可视化。
(a)
:US County
可视化,其中 embedding
由 GraphViz
提供,颜色对应于类别标签。总体而言是经纬度坐标的压缩旋转版本。(b)
:和 (a)
部分对应的pannel
,显示 C&S
在哪个阶段做出了正确的预测。(c)
:显示了相同 pannel
上 GNN
做出的预测。如预期的那样,残差相关性倾向于校正节点,其中临县为这些节点提供了相关信息。例如:
base prediction
中的很多误差已被残差相关性校正(图 3b
的左图和右图)。在这些情况下,对应于德克萨斯州和夏威夷州的部分地区,县的人口统计特征和全国其它地区相比是异常的,这误导了 Linear
模型和 GCN
模型。而来自相邻县的残差相关性能够校正预测。3b
的中间部分所示,这使得可以基于邻居的正确分类来校正误差。CNN
在很多领域已经获得巨大成功,如图像领域、NLP
领域。这些领域背后的一个共同点是数据可以由网格结构表示,这使得可以在输入的每个位置上应用卷积算子。但是在很多实际应用中数据是图结构,如社交网络、引文网络、生物网络。网格结构是图结构的特殊情况,因此将图像领域的深度学习模型(尤其是 CNN
)推广到图结构数据很有吸引力。
但是,在图结构数据上应用常规卷积算子面临两个主要挑战。这些挑战来自于这样一个事实:常规卷积算子要求每个节点的邻域节点数量不变,并且这些邻域节点是有序的。论文 《Large-Scale Learnable Graph Convolutional Networks》
为解决这些挑战提出了优雅的解决方案。
两个挑战:图数据中,不同节点的邻域节点数量不同,并且邻域节点没有排序信息。
最近的一些研究试图将卷积算子推广到通用图结构:
GCN
提出使用类似卷积的运算来聚合每个节点的所有邻域节点的特征,然后进行线性变换来生成给定节点的新的 representation
。可以将其视为类似于卷积的运算,但是它在两个方面和常规的卷积算子有本质的不同:
首先,它不使用相同的局部滤波器来扫描每个节点。即,邻域数量不同的节点具有不同尺寸size
和权重的滤波器。
其次,对于感受野receptive field
中所有的邻域节点,滤波器中的权重均相同,权重为
相比之下,
CNN
滤波器的权重是可训练的。
GAT
采用注意力机制,通过衡量邻域节点的特征向量和中心节点的特征向量之间的相关性,从而获得邻域节点的不同、且可训练的权重。
但是,graph attention
操作仍然不同于常规卷积,后者直接学习局部滤波器的权重。此外,注意力机制需要根据成对的特征向量进行额外的计算,从而在实践中导致过多的内存和计算资源需求。
和这些方法不同,论文《Large-Scale Learnable Graph Convolutional Networks》
为在通用图结构数据上应用 CNN
做出了两个主要贡献:
首先,论文提出可学习的图卷积层learnable graph convolutional layer: LGCL
,以便能够在图上使用常规的卷积运算。
注意:之前的研究修改了原始卷积运算来适配图数据。相比之下, LGCL
修改了图数据来适配卷积运算。LGCL
为每个特征维度根据取值的排名自动选择固定数量的邻域节点,以便将graph
数据转换为 1-D
格式的网格结构,从而可以在通用的 graph
上应用卷积运算。
实验结果表明,基于 LGCL
的模型在 transductive learning
和 inductive learning
的节点分类任务上均表现出更好的性能。
其次,论文观察到现有方法的另一个局限性,即:现有的训练过程将整个图的邻接矩阵作为输入。当图包含大量节点时,这需要过多的内存和计算资源。
为克服这一局限性,论文提出了一种子图训练方法sub-graph training method
。该方法是一种简单而有效的方法,可以对大规模图数据进行训练。子图训练方法可以显著减少所需的内存和计算资源,而在模型性能方面的损失可以忽略不计。
给定图
degree
度矩阵。degree
矩阵。GCN
模型中,每一层的操作可以表示为:
其中:
embedding
矩阵,ReLU
函数。可以看到该操作类似于卷积运算:每个节点的感受野由其本身和邻域节点组成,然后在感受野上应用一个局部滤波器。但是这种运算和 CNN
中的常规卷积运算有两点区别:
因此,GCN
中这种不可训练的聚合操作限制了 CNN
在通用图数据上的能力。
两点区别:
GCN
中每个节点采用不同的滤波器(滤波器不会跨节点共享,且滤波器的尺寸不固定),且滤波器是不可训练的。
GAT
试图通过注意力机制来聚合邻域特征向量,从而使得学习聚合权重成为可能。
像 GCN
一样,GAT
中每个节点仍然具有局部滤波器,其感受野包含节点本身及其邻域。当执行特征向量的加权和时,每个邻居节点都通过衡量它与中心节点之间的相关性来接收不同的权重。
正式地,在第
其中:
attention
向量。
attention
权重。
尽管通过这种方式 GAT
向不同的邻域节点提供了不同、且可训练的权重,但学习权重的过程和常规 CNN
的学习过程不同。在常规 CNN
中,直接学习局部滤波器的权重。
另外,注意力机制需要在中心节点和所有邻域节点之间进行额外的计算,这在实践中会引起内存和计算资源的问题。
和现有的这些修改常规卷积运算使得其适合通用的图数据不同,我们提出将图转换为类似网格的数据来直接应用 CNN
。这个想法以前在 《Learning convolutional neural networks for graphs》
中有所探讨,但是该论文中的变换是在预处理过程中实现的。而我们的方法在模型中包含转换。
此外,我们的工作还提出了一种子图训练方法,这是一种允许大规模图的训练的简单而有效的方法。
这里我们介绍通用图数据的可学习图卷积层learnable graph convolutional layer:LGCL
。
LGCL
的传播规则为:
其中:
embedding
矩阵,k-largest
节点并将通用图结构转换为网格数据的操作。1-D CNN
来聚合邻域信息并为每个节点输出新的 representation
向量。下面我们分别讨论
k-largest node selection
k-largest node selection
的新颖方法,从而实现从图数据到网格数据的转换,其中 LGCL
的超参数。
执行该操作后,每个节点将聚合来自邻域的信息,并表示为具有 1D-CNN
来更新representation
向量。
假设 representation
。representation
的维度。
给定邻接矩阵 representation
向量拼接为矩阵:
不失一般性假设
k-largest
节点选择是在 k-largest
个节点。
注意,这里是对每一列单独进行排序,而不是根据维度取值来对节点进行排序。此外,这里不仅仅是选择了最大的
个值,而且还进行了排序。固定数量的邻域、且邻域节点有序,这运行 CNN
卷积的要求。这里的核心的两个操作是:如何
select
、如何sort
。除了论文里提到的这种维度独立的选择和排序,还可以选择样本独立的选择和排序:从第一个维度到最后一个维度,依次选择个该维度取值最大的节点,然后依次拼接起来。
最后,我们将 k-largest node selection
过程:中心节点具有6
个邻居;对于每个特征,根据特征取值从邻域中选择四个最大的值;最后将中心节点自己的特征拼接起来得到
通过在每个节点上应用这一过程,1D
网格数据,其中 batch size
、k-largest node selection
函数
k-largest node selection
操作利用了实数之间的自然排名信息,并强制每个节点具有固定数量的有序邻居。
1D-CNN
1D
网格数据,因此我们采用1-D CNN
模型
LGCL
的基本功能是聚合邻域信息并更新每个节点的 representation
,因此 1-D CNN
1
。
batch size
,它和
考虑节点 k-largest node selection
转换的输出为
由于任何常规卷积算子(滤波器尺寸大于 1
并且没有填充)都会减小空间尺寸,因此最简单的
同时,也可以使用任何多层 CNN
,只要其最终输出的尺寸为
同样地,对所有
总之,我们的 LGCL
使用 k-largest node selection
方法将通用的图数据转换为网格数据,并应用标准的1-D CNN
进行特征聚合从而为每个节点更新 representation
。
下图为 LGCL
的一个例子。考虑具有6
个邻域节点的中心节点(橙色表示),每个节点具有3
维特征(特征由三个分量的特征向量来表示)。LGCL
选择邻近的 1-D CNN
来更新中心节点的 representation
。
k-largest
节点的过程。1-D CNN
作用于生成的网格数据并得到中心节点的 representation
。输出为 5
维特征(输出通道数为 5
)。这里1-D CNN
的输入通道数和输出通道数都不相同,并且 1-D CNN
可以为任何 CNN
模型。
这里采用了两层的
1-D
卷积:第一层输入通道数为3
、输出通道数为4
;第二层输入通道数为4
、输出通道数为5
。
众所周知更深的网络通常会产生更好的性能,但是之前 GCN
之类的图模型通常只有两层,因为它们层数加深时会受到性能损失。但是在我们的 LGCL
中可以采用更深的层,从而为图节点分类提供可学习的图卷积网络 learnable graph convolutional networks: LGCNs
。
我们基于 densely connected convolutional networks:DCNNs
体系架构来构建 LGCN
,因为 DCNNs
在 ImageNet
分类挑战中获得了 state-of-the-art
性能。
在 LGCN
中,我们首先应用一个 graph embedding layer
来生成节点的低维representation
。因为某些图数据集中,原始输入通常是很高维度的特征向量。
第一层中的 graph embedding layer
实际上是一个线性变换,即:
其中:
也可以使用一个 GCN layer
作为 graph embedding layer
。
在 graph embedding layer
之后,根据图数据的复杂性,我们堆叠了多个 LGCL
。由于每个 LGCL
仅聚合来自于一阶邻域的信息,因此多个 LGCL
可以收集到更大感受野中的信息。
为了提高模型性能并简化训练过程,我们应用了 skip-connection
来连接 LGCL
的输入和输出。
最后,我们在softmax
输出层之前采用一个全连接层。
遵循 LGCNs
的设计原理, LGCL
堆叠层数是最重要的超参数。
degree
可以作为选择 LGCL
层的数量取决于任务的复杂性,如类别数量、图中节点数量等。通常更复杂的任务需要更深度的模型。LGCN
的一个例子如下图所示。在这个例子中,输入的节点具有两维特征。
首先,我们使用 graph embedding layer
将输入特征向量转换为低维 representation
。
然后,我们使用两个 LGCL
层,每个 LGCL
层和 skip-connection
堆叠在一起。
注意:LGCL
层和 skip-connection
输出是拼接起来,而不是相加。
最后,使用一个全连接层和 softmax
输出层用于节点分类。这里有三个不同的类别。
通常而言,在训练期间,图模型的输入是所有节点的特征向量及整个图的邻接矩阵。这些模型可以在小规模图上正常工作。但是对于大规模图,这些方法通常会导致过多的内存和计算资源需求,从而限制了这些模型的实际应用。
对于其它类型的数据(如网格数据)的深度神经网络,也会遇到类似的问题。如,在处理大尺寸图像时,模型通常使用随机裁剪的 patch
。受到该策略的启发,我们打算随机 “裁剪” graph
从而获得较小的graph
来进行训练。
但是,图像的矩形 patch
自然地保持了像素之间的相邻信息,而如何处理图中的节点之间的不规则连接仍然具有挑战性。这里我们提出了一种子图选择算法来解决大规模图数据上的内存和计算资源问题。
具体而言,给定一个图:
BFS
算法将相邻节点迭代地扩展到子图中。Sub-Graph Selection Algorithm
:
输入:
输出:子图的节点集合
算法步骤:
初始化
从
更新
记
当
候选节点集合为
更新
更新
注:为简单期间这里我们使用单个参数
。实际上我们可以为每次迭代选择不同的 值。
下图是一个子图选择过程的示例。我们从
BFS
查找 3
个初始节点(橙色)中的所有一阶相邻节点(不包括它们自己)。在这些节点中,我们随机选择 经过两次迭代,我们选择了 3+5+7=15
个节点并获得了所需的子图。这些节点以及相应的邻接矩阵将在训练迭代期间作为 LGCN
的输入。
有了这样的随机 “裁剪” 子图,我们就能够在大规模图上训练深度模型。
此外,我们可以利用 mini-batch
训练策略来加速学习过程。在每次训练迭代中,我们可以使用提出的子图选择算法来采样若干个子图,然后将这些子图放到 mini-batch
中。相应的特征向量和邻接矩阵构成了网络的输入。
子图采样也可以作为
GNN
的通用策略从而帮助GNN
的mini-batch
训练。
我们的方法主要解决节点分类问题,实践中有些任务需要对图进行分类,即图分类问题。
但是目前的图卷积方法(包括我们的方法)无法对图进行降采样(类似于图像数据的池化操作),我们需要一个layer
来有效地减少节点数,这是图分类所必须的。
另外,我们的方法主要应用于通用图数据,如引文网络。对于其它数据,如文本,我们的方法也可能会有所帮助,因为我们可以将文本数据视为图。
我们评估在 transductive learning
和 inductive learning
环境下 LGCN
在大规模图的节点分类任务上的表现。
另外,除了和 state-of-the-art
模型进行比较之外,我们还进行了一些性能研究,从而研究如何选择超参数。
最终实验结果表明,LGCN
可以提高性能,并且子图训练比全图训练更有效。
数据集:
transduction Learning
:在 transductive learning
环境下,未标记的测试节点可以在训练期间访问到,包括测试节点的特征和连接。这意味着训练期间知道包含测试节点的图结构。
我们使用三个标准的 benchmark
数据集:Cora, Citeseer, Pubmed
。这三个数据集是引文网络数据集,节点代表文档、边代表引用关系。每个节点的特征向量是文档的bag-of-word
表示。对于这三个数据集,我们采用和 GCN
中相同的实验设置:对于每个类别,我们选择 20
个节点进行训练、500
个节点进行验证、1000
个节点用于测试。
inductive Learning
:在 inductive learning
环境下,未标记的测试节点可以在训练期间不可用。这意味着训练期间不知道测试图的结构。
在 inductive learning
环境下,我们通常具有不同的训练图、验证图、测试图。在训练期间模型仅使用训练图、而无法访问验证图和测试图。
我们使用 protein-protein interaction: PPI
数据集,其中包含 20
个训练图、2
个验证图、2
个测试图。由于验证图和测试图是独立的,因此训练过程中不会使用它们。平均每个图包含 2372
个节点,每个节点包含 50
个特征。每个节点都有来自 121
个类别的多个标签。
下表给出这些数据集的统计量。degree
属性是每个数据集的平均节点 degree
,这有助于选择 LGCL
中的超参数
实验配置:
transduction Learning
:
由于 transductive learning
数据集使用高维的bag-of-word
作为特征向量,因此输入经过 graph embedding layer
来减小维度。
这里我们使用 GCN layer
来作为 graph embedding layer
,embedding
的输出维度为 32
。
然后我们使用 LGCL
,每个 LGCL
使用 8
的特征向量。对于 Cora/Citesser/Pubmed
,我们分别堆叠了 2/1/1
个 LGCL
。
另外,我们在 skip-connection
中使用拼接操作。
最后,将全连接层用作分类器以进行预测。在全连接层之前,我们执行一个简单的sum
操作来聚合邻域节点的特征向量。
在每一层的输入特征向量和邻接矩阵上都应用 dropout
,dropout
比例分别为 0.16
和 0.999
。
所有 LGCN
模型都使用子图训练策略,子图大小设置为 2000
。
inductive Learning
:除了某些超参数之外,使用和 transductive learning
相同的配置。
graph embedding layer
,输出特征向量维度为 128
。LGCL
, 500
和 200
。dropout
,dropout
比例为 0.9
。对于 transductive learning
和 inductive learning
,LGCN
模型共享以下配置:
L2
正则化。0.1
的 Adam
优化器。LGCN
中的权重使用 Glorot
方法初始化。1000
个 epoch
。实验结果:
Transduction Learning
实验结果:我们报告了不同模型在节点分类任务上的准确率。根据结果,LGCN
模型在 Cora, Citeseer, Pubmed
数据集上的性能比 state-of-the-art
的 GCN
分别提高了 1.8%, 2.7%, 0.5%
(绝对提升)。其中 LGCN
模型。
Inductive Learning
实验结果:我们报告了不同模型的 micro-averaged F1
得分。根据结果,LGCN
模型的性能比 GraphSAGE-LSTM
提高了 16%
。这表明在训练期间看不到测试图的情况下,LGCN
模型仍然取得很好的泛化能力。
上述实验结果表明:
LGCN
模型在不同节点分类数据集上一致性地达到 state-of-the-art
性能。k-largest node selection
实现的转换方法被证明是有效的。LGCL vs GCL Layer
:有人认为LGCN
性能的提高仅仅是因为 LGCN
模型采用的网络体系结构比 GCN
更深。但是,已有论文提出:通过堆叠更多的层来加深 GCN
会导致性能更差。
因此,这里我们进行另一项实验:将 LGCN
模型中所有 LGCL
替换为 GCN Layer
,称之为
下表给出了 LGCL
比 GCN Layer
更为有效。
子图训练vs
全图训练:上述实验中我们使用子图训练策略来训练 LGCN
模型,旨在节省内存和训练时间。但是,由于子图选择算法从整个图中抽取一些节点作为子图,这意味着以这种方式训练的模型在训练过程中不了解整个图的结构。同时,在 transductive learning
环境下,测试节点的信息可能会被忽略,从而增加了性能下降的风险。
为解决这个问题,我们在 transductive learning
环境下进行实验,从而比较子图训练策略subgraph training strategy
和全图训练策略whole-graph training strategy
。通过实验,我们证明了子图训练策略的优势,同时在模型性能方面的损失可以忽略不计。
对于子图选择过程,在 transductive learning
环境下我们仅从带有训练标签的节点中采样初始节点,以确保训练可以进行。具体而言,对于 Cora/Citeseer/Pubmed
数据集,我们分别随机采样 140/120/60
个初始节点。在迭代过程中,我们并没有设置 2000
。对于我们的 GPU
而言这是可行的大小。
为进行比较,我们使用相同的 LGCN
模型进行实验,但使用和 GCN
相同的全图训练策略来训练它们。这意味着输入是整个图的表示。和使用子图训练策略的
下表给出了这两种模型和 GCN
的比较结果:报告的节点数表示一次迭代训练使用了多少个节点;报告的时间是使用单个 TITAN Xp GPU
运行 100
个 epoch
的训练时间;报告的准确率是测试准确率。
可以看到:
Cora/Citeseer/Pubmed
数据集的子图训练中,子图的实际节点数量分别为 644/442/354
,远小于最大的子图大小 2000
。这表明这三个数据集中的节点是稀疏连接的。具体而言,从带有训练标记的几个初始节点开始,通过扩展相邻节点以形成连接的子图,只会选择一小部分节点。
尽管通常将这些数据集视为一个大图,但是整个图实际上只是由彼此独立的几个单独的子图组成。子图训练策略利用了这一事实,并有效利用了带训练标签的节点。
由于只有初始节点具有训练标签,并且所有这些初始节点的连接性信息都包含在所选子图中,因此子图训练中的信息丢失量降到最低,从而导致性能损失几乎可以忽略不计。
通过对比 Cora
数据集上有 0.5%
的微小性能损失,而在 Citeseer
和 Pubmed
数据集上却具有相同的性能。
在调查了性能损失的风险之后,我们看到子图训练策略在训练速度方面的巨大优势。通过使用子图训练策略,和全图训练策略相比,
从结果可以看到,这种训练效率的提升是显著的。尽管 GCN
的计算更简单,它在 Pubmed
之类的大规模图数据集上的运行时间比 LGCN
模型要长的多。
通常在大规模图数据上应用强大的深度学习模型,这使得子图训练策略在实践中很有用。子图训练策略可以使用更复杂的层,如LGCL
,而无需担心训练时间。结果,带有子图训练策略的大型 LGCN
不仅效果好而且效率高。
超参数 LGCN
中选择超参数 degree
会有所帮助。这里我们进行实验来展示不同的 LGCN
模型的性能。
我们在 Cora,Citeseer,Pubmed
数据集上调整 [2,4,8,16,32]
,这覆盖了合理范围内的整数值。
下图给出了不同 LGCN
模型的性能变化。可以看到:
LGCN
模型上的所有三个数据集在 Cora, Citeseer, Pubmed
数据集中,平均节点 degree
分别为 4/5/6
。这表明最佳的 degree
稍大一点。LGCN
模型的性能会降低。可能的解释是:如果 degree
大得多,那么在 k-largest node selection
过程中使用了太多的零填充,这会不利于接下来的 1-D CNN
模型的性能。PPI
数据集上的 inductive learning
任务,我们也探索了不同的 degree
为 31
。这和我们上面讨论的结果一致。摘要:直接读取graph
并对 graph
进行分类,有两个挑战:
graph
中丰富的信息从而用于分类。为此论文 《An End-to-End Deep Learning Architecture for Graph Classification》
设计了一个局部图卷积模型localized graph convolution model
,并展示了它与两个 graph kernel
的联系。meaningful
且一致的consistent
顺序来读取一个graph
。为此论文 《An End-to-End Deep Learning Architecture for Graph Classification》
设计了一个新颖的 SortPooling
层,该层以一致的顺序对图的节点进行排序,以便可以在图上训练传统的神经网络。在 benchmark
图分类数据集上的实验表明,所提出的架构与最先进的 graph kernel
和其他图神经网络方法相比,取得了极具竞争力的性能。此外,该架构允许使用原始图进行端到端的梯度训练,而不需要首先将图转化为向量。整个架构称之为 Deep Graph Convolutional Neural Network:DGCNN
。
引言:过去几年中,神经网络在图像分类、自然语言处理、强化学习、以及时间序列分析等应用领域日益盛行。层与层之间的连接结构使神经网络适合处理张量形式的信号,其中张量元素以有意义的顺序排列。这种固定的输入顺序是神经网络提取高层次特征的基石。例如,如果我们随机混洗下图所示图像的像素,那么SOTA
的卷积神经网络就无法将其识别为一只鹰。
虽然图像和许多其他类型的数据都是有自然的顺序,但还有另一大类结构化数据,即graph
,它们通常缺乏具有固定顺序的张量表示 tensor representation
。graph
的例子包括分子结构、知识图谱、生物网络、社会网络、以及有依赖关系的文本文档。有序张量表示的缺乏,限制了神经网络在图上的适用性。
最近,人们对将神经网络推广到图上的兴趣越来越大:
《Spectral networks and locally connected networks on graphs》
将卷积网络推广到谱域中的 graph
,其中滤波器应用于图的频率模式frequency mode
。这个频率模式由图傅里叶变换计算得到。《Convolutional neural networks on graphs with fast localized spectral filtering》
将谱域滤波器参数化为特征值的 Chebyshev
多项式,并实现了高效的和局部化的滤波器。上述谱域公式的一个局限性是:它们依赖于图拉普拉斯矩阵的固定频谱,因此只适合于具有固定单一结构的图。相反,空域公式不限于固定的图结构。为了提取局部特征,有几项工作独立提出在相邻节点之间传播特征。
《Convolutional networks on graphs for learning molecular fingerprints》
提出了可微分的神经图指纹Neural Graph Fingerprint
,它在1-hop
邻居之间传播特征,以模拟传统的圆形指纹 circular fingerprint
。《Diffusion-convolutional neural networks》
提出了 Diffusion-CNN
,它使用不同的权重将不同hop
的邻居传播到中心节点。《Semi-supervised classification with graph convolutional networks》
开发了针对 《Convolutional neural networks on graphs with fast localized spectral filtering》
提出的谱域卷积的一阶近似,这也导致了相邻节点之间的传播。《Learning convolutional neural networks for graphs》
提出了另一种空域图卷积的方式,从节点的邻域中提取固定大小的 local patch
,并用 graph labeling
方法和 graph canonization
工具对这些 patch
进行线性化处理。由此产生的算法被称为 PATCHY-SAN
。由于空域方法不需要单一的图结构,它们可以被应用于节点分类和图分类任务。虽然取得了 SOTA
的节点分类结果,但以前的大多数工作在图分类任务上的表现相对较差。其中一个原因是,在提取局部节点特征后,这些特征被直接 sum
从而用于图分类的图 graph-level
特征。在论文 《An End-to-End Deep Learning Architecture for Graph Classification》
中,作者提出了一个新的架构,可以保留更多的节点信息并从全局图的拓扑结构中进行学习。一个关键的创新是一个新的 SortPooling
层,它从空域图卷积中获取图的无序节点特征作为输入。SortPooling
不是将这些节点特征相加,而是将它们按照一致的顺序排列,并输出一个固定大小的 sorted graph representation
,这样传统的卷积神经网络就可以按照一致的顺序读取节点并在这个 representation
上进行训练。作为图卷积层和传统神经网络层之间的桥梁,SortPooling
层可以通过它来反向传播损失的梯度,将 graph representation
和 graph learning
融合为一个端到端的架构。
论文贡献如下:
multi-scale
的节点特征,并与流行的 graph kernel
进行类比,从而解释为什么它能发挥作用。SortPooling
层来对节点特征进行排序,而不是将它们相加,这样可以保留更多的信息,并允许我们从全局范围内学习。相关工作:
Graph Kernel
:Graph Kernel
通过计算一些半正定的 graph similarity
度量,使 SVM
等 kernel machine
在图分类中变得可行,在许多图数据集上取得了 SOTA
的分类结果。
《Convolution kernels on discrete structures》
中引入了 convolution kernel
,它将图分解成小的子结构substructure
,并通过增加这些子结构之间的成对相似度来计算核函数 kernel function
。常见的子结构类型包括 walk
、subgraph
、path
、以及 subtree
。《Graph invariant kernels》
以一种通用的方式重新表述了许多著名的基于子结构的核,称为图不变核 graph invariant kernel
。《Deep graph kernels》
提出了 deep graph kernel
,它学习子结构的潜在representation
从而利用其依赖信息。convolution kernel
根据两个图的所有子结构对进行比较。另一方面,assignment kernel
倾向于找到两个图的子结构之间的对应关系。
《An aligned subtree kernel for weighted graphs》
提出了包含显式子树对应关系的 aligned subtree kernel
。《On valid optimal assignment kernels and applications to graph classification》
为一种类型的 hierarchy-induced kernel
提出了最佳分配。大多数现有的 graph kernel
侧重于对比小的局部模式。最近的研究表明,对比图的全局模式可以提高性能。《Discriminative embeddings of latent variable models for structured data》
使用 latent variable model
表示每个图,然后以类似于 graphical model inference
的方式显式地将它们嵌入到特征空间。结果在准确性和效率方面与标准 graph kernel
相比都很好。
DGCNN
与一类基于 structure propagation
的 graph kernel
密切相关,具体而言是 Weisfeiler-Lehman(WL) subtree kernel
和 propagation kernel (PK)
。为了编码图的结构信息,WL
和 PK
基于中心节点的邻居的特征迭代更新中心节点的特征。WL
对 hard
节点标签进行操作,而 PK
对 soft
标签分布进行操作。由于这种操作可以有效地实现为随机行走,这些 graph kernel
在大型图上是有效的。与WL
和PK
相比,DGCNN
有额外的参数 graph kernel
的两阶段框架。
用于图的神经网络:
将神经网络推广到图的研究有两条线:给定一个单一的图结构,推断单个节点的标签或者单个图的标签;给定一组具有不同结构和大小的图,预测未见过的图的类标签(图分类问题)。
在本文中,我们专注于第二个问题,这个问题更加困难,因为:图的结构不是固定的,每个图内的节点数量也不是固定的。此外,在第一个问题中来自不同图的节点具有固定的索引或对应的索引,但是在第二个问题中节点排序往往是不可用的。
我们的工作与一项使用CNN
进行图分类的开创性工作有关,称为 PATCHY-SAN
。为了模仿 CNN
在图像上的行为,PATCHY-SAN
首先从节点的邻域中提取固定大小的局部 patch
作为卷积滤波器的感受野。然后,为了在这些 patch
上应用 CNN
,PATCHY-SAN
使用外部软件(如图规范化工具NAUTY
)在预处理步骤中为整个图定义一个全局节点顺序,以及为每个 patch
定义一个局部顺序。之后,graph
被转换为有序的 tensor representation
,并在这些张量上训练 CNN
。
虽然取得了与 graph kernel
有竞争力的结果,但这种方法的缺点包括繁重的数据预处理、以及对外部软件的依赖。我们的DGCNN
继承了其为图节点施加顺序的思想,但将这一步骤集成到网络结构中,即 SortPooling
层。
在如何提取节点特征方面,DGCNN
也与 GNN
、Diffusion-CNN
、以及 Neural Graph Fingerprint
相关。然而,为了进行graph-level
分类,GNN
监督单个节点(是一个虚拟的超级节点,它节点与所有其它真实节点相连),而 Diffusion-CNN
和 Neural Graph Fingerprint
使用 sum
的节点特征。相比之下,DGCNN
以某种顺序对节点进行排序,并将传统的CNN
应用于有序的 representation
上,这样可以保留更多的信息,并能从全局图拓扑结构中学习。
给定图
0/1
矩阵。并且图中没有自环self-loop
。DGCNN
包含三个连续的阶段:
graph convolution layer
抽取节点的局部子结构特征,并定义一致的节点顺序。SortPooling
层按照前面定义的顺序对节点特征进行排序,并统一输入尺寸 size
。dense
层读取排序的graph representation
并进行预测。DGCNN
整体架构如下图所示:图数据首先通过多个图卷积层,其中节点信息在邻域之间传播;然后对节点特征排序并通过 SortPooling
层池化;然后传递给传统的 CNN
结构以学习模型。节点特征以颜色来可视化。
我们的图卷积层的形式为:
其中:
self-loop
的邻接矩阵。图卷积层聚合局部邻域的节点信息从而抽取局部子结构。为了抽取多尺度 multi-scale
的子结构特征,我们堆叠多个图卷积层。第
其中:
representation
,representation
。假设一共有
拼接的结果 feature descriptor
,它编码了节点的多尺度局部子结构信息multi-scale local substructure information
。
我们的图卷积层和 GCN
层很相似,区别在于它们使用不同的传播矩阵。
GCN layer
采用作为传播矩阵,它本质上就等价于 。论文的表述有误。
可以证明,我们的图卷积层有效地模仿了两个流行的 graph kernel
(Weisfeiler-Lehman subtree kernel
、propagation kernel
)的行为,这有助于解释其graph-level
分类行为。
WL-test
对节点邻域进行反复迭代,最终根据两个图之间的节点label
是否完全相同,从而判断两个图是否同构的。注:这里的 label
更多地是节点的离散特征,而不是节点的监督信息。
WL-test
迭代过程如下:聚合节点及其邻域的 label
;将聚合后的label
经过哈希函数得到不同的、新的label
,即 relabel
。
《Weisfeiler-lehman graph kernels》
根据 WL-test
提出了 WL subtree kernel
来衡量两个图的相似性。核函数利用 WL tet
的不同迭代中使用的节点label
数作为图的特征向量。直观地讲,WL test
第 label
代表了以该节点为根的、高度为 WL subtree kernel
考虑的图特征本质上是不同根子树的计数。
如果我们记
我们可以视 continuous color
。因此我们的图卷积公式可以视为 WL-test
算法的一个 soft
版本。
soft
版本有两个好处:
WL subtree kernel
具有更好的表达能力。soft WL-test
,避免了读取和排序可能非常长的 WL signature
字符串。propagation kernel:PK
比较了两个图的label
分布,它基于扩散更新的方案diffusion update scheme
:
其中:
label distribution
向量。其初始值就是每个节点label
的 one-hot
。最终将所有迭代过程中的label distribution
向量通过 locality-sensitive hashing:LSH
映射到离散的分桶,从而计算 label distribution
向量之间的相似性。
PK
具有和 WL kernel
类似的 graph
分类性能,甚至具有更高的效率。而我们的图卷积公式和PK
非常相似。
WL kernel
在 hard vertex label
上进行,而 PK
在 soft label distribution
上进行。这些操作都可以有效地实现为随机游走,因此这些核函数在大规模图上非常有效。和 WL kernel
和 PK
相比,DGCNN
在传播之间具有其它参数,这些参数是通过端到端优化进行训练的。这允许从标签信息中进行有监督的特征学习,使其不同于 graph kernel
的两阶段框架。
WL kernel
的基本思想是将节点的颜色和其1-hop
邻域的颜色拼接起来作为节点的 WL-signature
,然后按照字典顺序对 signature
字符串进行排序从而分配新的颜色。具有相同signature
的节点将分配相同的新颜色。
这种 “聚合--分配” 动作和我们的图卷积层是类似的,因此我们称 WL color
。
SortPooling
层的主要功能是将特征描述符输入传统的1-D
卷积层和 dense
层之前,以一致的顺序对特征描述符进行排序,其中每个特征描述符对应于一个节点。
问题是:以什么样的顺序对节点进行排序?在图像分类中,像素天然地以某种空间顺序排序。在NLP
任务中,可以使用字典顺序对单词进行排序。在图中,我们可以根据节点在图中的结构角色structural role
对节点进行排序。
一些工作使用 graph labeling
方法(如 WL kernel
)来在预处理阶段对节点进行排序,因为最终的 WL color
定义了基于图拓扑的排序。WL
施加的这种节点顺序在各个图之间是一致的,这意味着如果两个不同图中的节点在各自图中具有相似的结构角色,那么它们会被分配以相似的相对位置。结果,神经网络可以按顺序读取图节点并学习有意义的模型。
在DGCNN
中,我们也使用 WL color
来对节点进行排序。幸运的是,我们已经看到图卷积层的输出正好是连续的 WL color
SortPooling
层。对于 SortPooling
层:
feature channel
。在 SortPooling
层中,首先根据 WL color
,并根据这个 final color
对所有节点进行排序。
通过这种方式,我们对图节点施加了一致的排序,从而可以在排序的graph representation
上训练传统的神经网络。理想情况下,我们需要图卷积层足够深(意味着
基于 node representation
的最后一维)。
除了一致性的顺序对节点特征进行排序外,SortPooling
还有一个能力是统一输出张量的尺寸 size
。
排序后,我们将输出张量的尺寸从 graph size
,使得不同数量节点的图将其大小同一为
这和
LGCN
的k-largest
节点选择方法很类似。只是LGCN
独立地选择并排序最大的k
个特征,而SortPooling
根据final color
选择最大的k
个节点。除此之外,LGCN
和DGCNN
还有一个最大的区别:
LGCN
中,卷积层用于根据邻域节点的k-largest representation
来更新中心节点的representation
,因此最终用于节点分类。DGCNN
中,卷积层根据所有节点的GCN representation
来获得graph representation
,因此最终用于图分类。
作为图卷积层和传统层之间的桥梁,SortPooling
还有另一个好处,就是通过它可以记住输入的排序顺序从而将损失梯度传递给前一层,从而可以训练前一层的参数。
相比之下,一些工作在预处理阶段对节点进行排序,因此无法在排序之前进行参数训练。
在 SortPooling
层之后,我们得到一个大小为
CNN
,我们添加若干个 1-D
卷积层和最大池化层,从而学习节点序列上的局部模式。softmax
输出层。GNN
设计的一个重要标准是:网络应该将同构图isomorphic graph
映射到相同的representation
,并且输出相同的预测。否则邻接矩阵中的任何排列permutation
都可能对同一个图产生不同的预测。
对于基于求和的方法这不是问题,因为求和对于节点排列是不变的。但是对于排序的方法DGCNN, PATCHY-SAN
需要额外注意。
为了确保将同构图预处理为相同的张量,PATCHY-SAN
首先使用 WL kernel
算法,然后使用图规范化工具 NAUTY
。尽管 NAUTY
对于小图足够有效,但是理论上讲,图规范化graph canonization
问题至少在计算上和图同构检验一样困难。
相比之下,我们表明DGCNN
可以避免这种图规范化步骤。DGCNN
使用最后一个图卷积层的输出对节点进行排序,我们表明:这可以视为是 soft WL
输出的连续颜色。因此 DCNN
能够将节点排序视为图卷积的副产品,从而避免像 PATCHY-SAN
这样显式运行运行 WL kernel
算法。并且,由于 SortPooling
中的排序方案,DGCNN
不再需要图规范化。因此 DGCNN
不需要显式运行 WL kernel
或 NAUTY
,这使我们摆脱了数据预处理和外部软件的束缚。
我们还指出,尽管 DGCNN
在训练过程中会动态地对节点进行排序,但是随着时间的增加,节点顺序会逐渐变得稳定。这是因为参数 continuous WL color
。此外,训练过程中
定理:在 DGCNN
中,如果两个图 SortPooling
之后它们的图representation
是相同的。
证明:注意,第一阶段的图卷积对于节点索引是不变的。因此,如果 multiset
。
由于 SortPooling
对于节点排序的方式是:当且仅当两个节点具有完全相同的特征描述符时,两个节点才有联系have a tie
,因此排序的representation
对于两个节点的排名具有不变性。因此,在 SortPooling
之后,representation
。
数据集:五个benchmark
生物信息学数据集,包括MUTAG
、PTC
、 NCI1
、 PROTEINS
、D&D
。所有节点都有 label
信息。
baseline
方法:四种graph kernel
,包括 graphlet kernel: GK
、random walk kernel: RW
、propagation kernel: PK
、Weisfeiler-Lehman subtree kernel: WL
。
实验配置:使用 LIBSVM
进行10-fold
交叉验证,训练集为 9 fold
、测试集为 1 fold
,并使用训练集中的 1 fold
进行超参数搜索。
每个实验重复 10
次(因此每个数据集训练了 100
次),报告了平均的准确率和标准差。
实验结果如下表所示,可以看到:
DGCNN
相比 graph kernel
具有很强的竞争力。DGCNN
通过 SGD
进行训练,避免了 graph kernel
所需的 DGCNN
优势更大。数据集:六个数据集,其中包括三个生物信息学数据集 NCI1, PROTEINS, D&D
、三个社交网络数据集 COLLAB, IMDB-B, IMDB-M
。这些社交网络数据集中的图没有节点label
,因此是纯结构。
baseline
:四种深度学习方法,包括PATCHY-SAN: PSCN, DiffusionCNN: DCNN, ECC, Deep Graphlet Kernel: DGK
。
实验配置:对于 PSCN, ECC, DGK
,我们报告原始论文中的最佳结果,因为他们实验配置和我们这里相同。对于 DCNN
,我们使用我们的实验配置重新实验。
PSCN, ECC
能够额外地利用边特征,但是由于这里很多数据集没有边特征,以及其它一些方法无法使用边特征,因此这里都没有利用边特征来评估效果。
实验结果如下表所示,可以看到:
DGCNN
在PROTEINS, D&D, COLLAB, IMDB-M
数据集上表现出最高的分类准确率。
和 PATCHY-SAN
相比,DGCNN
的改进可以解释如下:
SortPooling
向后传播,DGCNN
甚至可以在排序开始之前就启用参数训练,从而实现更好的表达能力。DGCNN
不太可能过拟合特定的节点排序。相比之下,PATCHY-SAN
遵从预定义的节点顺序。DGCNN
的另一个巨大优势是:它提供了一种统一方法,将预处理集成到神经网络结构中。
和使用 sum
节点特征来分类的 DCNN
相比,DGCNN
表现出显著的提升。
为了证明SortPooling
优于求和的优势,我们进一步列出了 DGCNN(sum)
的结果,该结果采用 sum layer
替换 DGCNN
的 SortPooling
和后面的 1-D
卷积层。可以看到,大多数情况下性能下降很多。
当前图神经网络GNN
的一个明显挑战是可扩展性。在 GCN
中计算图卷积需要跨层递归扩张邻域,这在计算上是不现实的,并且需要占用大量内存。即使对于单个节点,当图是稠密的或者满足幂律powerlaw
分布时,由于邻域的逐层扩张,这将迅速覆盖图的很大一部分。传统的 mini-batch
训练无法加快图卷积的计算速度,因为每个batch
都将涉及大量节点,即使 mini-batch
本身很小。
为缓解过度扩张over-expansion
的问题,一些工作通过控制采样邻域的大小来加速GCN
的训练。有几种基于采样的方法用于图上进行快速的 representation learning
:
GraphSAGE
通过对每个节点的邻域进行采样(node-wise
采样),然后执行特定的聚合器以进行信息融合来计算节点的 representation
。FastGCN
模型将图卷积解释为 embedding
函数的积分变换,并独立采样每一层中的节点(layer-wise
采样)。VRGCN
是control-variate-based
方法 ,这种采样方法也是 node-wise
,并且需要节点的历史激活值。论文 《Adaptive Sampling Towards Fast Graph Representation Learning》
提出了一种新的layer-wise
采样方法:按照自上而下的方式逐层构建网络,其中下层的节点是根据上层的节点有条件采样而来。这种层级采样layer-wise sampling
在两个技术方面是有效的:
visible
,并且由于它们在较高层中的不同父节点之间共享,因此我们可以复用采样邻域的信息(即低层节点)。fix
每一层的大小,从而避免邻域的过度扩张,因为较低层的节点是整体采样的。和基于节点采样的 GraphSAGE
相比,论文的方法基于层级采样,因为所有邻域都被一起采样,因此可以实现邻域共享;和独立构造每一层的 FastGCN
相比,论文的方法可以捕获跨层连接。因为较低的层根据上层的条件进行采样。
论文方法的核心是为 layer-wise
采样定义合适的采样器。通常,设计采样器的目标是使得结果的方差最小化。不幸的是,由于在论文的网络中自上而下的采样和自下而上的传播的不一致,使得方差最小化的最佳采样器是无法计算的uncomputable
。为解决这个问题,作者通过使用自依赖函数代替不可计算的部分,然后将方差添加到损失函数,从而逼近最佳采样器。结果,通过共同训练模型参数和采样器 ,方差得到显著降低,这反过来又促进了模型的训练。
此外,论文还探索了如何使得有效的消息跨远程节点distant node
来传递。有些方法通过随机游走以生成各个step
的邻域,然后对 multi-hop
邻域进行整合。相反,本文通过在第 skip-connection
从而提出了一种新的机制。这种跳跃连接将第 2-hop
邻域,因此它自然地保持了二阶邻近性,而无需进行额外的计算。
总之本文做出了以下贡献:
layer-wise
采样方法来加速 GCN
模型,该模型共享层间信息,并可控制采样节点的规模。layer-wise
采样的采样器是自适应的,并通过训练阶段显式降低方差来确定。skip-connection
来保留二阶邻近性。最后,论文在节点分类的四个流行benchmark
上评估了新方法的性能,包括 Cora, Citeseer, Pubmed, Reddit
。大量实验证明了新方法在分类准确率和收敛速度方面的有效性。
相关工作:
如何设计高效的图卷积网络已成为一个热门研究课题。图卷积方法通常被分为谱域卷积和空域卷积两类:
谱域卷积方法首先由 《Spectral networks and locally connected networks on graphs》
提出,并在傅里叶域定义卷积操作。
后来,《Deep convolutional networks on graph-structured data》
通过应用高效的频滤波器实现了局部滤波。
《Convolutional neural networks on graphs with fast localized spectral filtering》
采用图拉普拉斯矩阵的 Chebyshev
多项式来避免特征分解 eigen-decomposition
。
最近,《Semi-supervised classification with graph convolutional networks》
提出了GCN
,它用一阶近似和重参数化技巧 re-parameterization trick
简化了以前的方法。
空域卷积方法通过直接使用空间连接来定义图的卷积。例如:
《Convolutional networks on graphs for learning molecular fingerprints》
为每个 node degree
学习一个权重矩阵。
《Diffusion-convolutional neural networks》
通过使用转移矩阵transition matrix
的一系列幂次来定义 multiple-hop
邻域。
《Learning convolutional neural networks for graphs》
提取了包含固定数量节点的规范化的邻域。
最近的一个研究方向是通过利用 patch
操作和自注意力来泛化卷积。与 GCN
相比,这些方法隐含地为邻域中的节点分配不同的重要性,从而实现了模型容量的飞跃。具体而言:
《Geometric deep learning on graphs and manifolds using mixture model cnns》
提出了 mixture model CNN
,使用 patch
操作在图上建立 CNN
架构。《Graph attention networks》
通过 attend
中心节点的每个邻居,按照自注意力策略计算中心节点的 hidden representation
。最近有两种基于采样的方法(即,GraphSAGE
和 FastGCN
被开发出来),用于图上的 fast representation learning
。具体而言:
GraphSAGE
通过对每个节点的邻域进行采样,然后执行特定的信息融合聚合器来计算节点的representation
(node-wise
采样)。FastGCN
模型将图的卷积解释为 embedding
函数的积分变换,并对每一层的节点独立采样(layer-wise
采样)。虽然我们的方法与这些方法密切相关,但我们在本文中开发了一个不同的采样策略:
GraphSAGE
以节点为单位的方法相比,我们的方法是基于 layer-wise
采样的,因为所有的邻域都是整体采样的,因此可以允许邻域共享。FastGCN
相比,我们的模型能够捕捉到层与层之间的联系,因为下层是以上层为条件进行采样的。另一项相关工作是 《Fastgcn: Fast learning with graph convolutional networks via importance sampling》
的基于控制变量的方法。然而,这种方法的采样过程是 node-wise
的,需要节点的历史激活 historical activation
。
给定图
degree
矩阵,它是一个对角矩阵,GCN
是用于图representation learning
的最成功的卷积网络之一。为区分不同层的节点,我们将第
GCN
的前向传播公式为:
其中:
representation
,representation
。representation
的维度。GCN
的前向传播公式表明:GCN
要求邻域的完整扩张full expansion
才能对每个节点进行前向计算。这使得在包含数十万个节点的大规模图上的学习变得计算量大而且消耗内存。
为解决这个问题,本文通过自适应采样adaptive sampling
来加快前向传播。我们提出的采样器是自适应的,并且可以减少方差。
GCN
公式重写为期望的形式,并相应地引入 node-wise
采样。然后我们将 node-wise
采样推广为一个更有效的框架,称为 layer-wise
采样。variance reduction
来学习layer-wise
采样器。最后,我们介绍了skip-connection
的概念,通过应用skip-connection
来实现前向传播的二阶邻近性second-order proximity
。
node-wise
采样:我们首先观察到 GCN
前向传播公式可以重写为期望的形式,即:
其中:
degree
: 加快上式的一个自然想法是通过蒙特卡洛采样Monte-Carlo sampling
来近似期望的计算。具体而言,我们通过
其中
使用蒙特卡洛采样之后,GCN
前向传播公式的计算复杂度从
然后我们以自顶向下的方式构造网络结构:递归地对当前层中每个节点的邻居进行采样,如下图所示。这里实线表示采样到的节点,虚线表示为未采样到的节点,红色节点表示至少有两个父节点的节点。
虽然node-wise
采样能够降低单层的计算复杂度,但是对于深度网络而言,这样的 node-wise
采样在计算上仍然昂贵,因为要采样的节点数量随着层数呈指数增长。假设网络有
通常
graph
是稀疏的,因此节点邻域的规模远远小于,绝大多数 。因此,上面的 可以降低到 ,其中 为父节点 的 degree
。
layer-wise
采样:通过应用重要性采样,我们进一步地将 GCN
前向传播公式重写为以下形式:
其中
类似地,我们通过蒙特卡洛Monte-Carlo
方法来估计这个期望值从而加速计算:
我们这种方法称作 layer-wise
采样策略。
layer-wise
采样和 node-wise
采样方法不同:
在 node-wise
采样方法中,每个父节点
并且每个父节点的邻域(子节点集合)对于其它父节点是不可见的。
另外采样节点数量随着网络深度指数增长。
在 layer-wise
采样方法中,所有父节点
并且采样到的子节点集合
更重要的是,每层的大小固定为
layer-wise
采样剩下的问题是如何定义采样器
为简单起见,我们将分布 《Monte Carlo theory, methods and examples》
中重要性抽样的推导,我们得出结论:
命题:estimator
最小化上式中方差
不幸的是,这里得到的最优采样器是不可行的。根据定义,采样器 hidden feature
为缓解这个 “鸡和蛋” 的困境,我们学习了每个节点的自依赖函数self-dependent function
,从而确定每个节点对于采样的重要性。
令 hidden feature
,则得到:
在本文中,我们定义
其中 hidden feature
的维度。
现在我们得到了 node-wise
采样器,并且对于不同的 layer-wise
采样,我们汇总了所有节点
这里定义的采样器是高效的,因为
就是从节点 转移到 的概率,可以在预处理中快速处理,且仅需要处理一次即可。
注意,通过
假设有一个mini-batch
的数据pair
对 ground-truth label
。
layer-wise
采样,给定 hidden feature
并获得节点 softmax
函数进一步添加到 考虑分类损失和采样方差,我们将混合损失定义为:
其中:
trade-off
超参数,在我们的实验中固定为 0.5
。注意:这里的方差实际上是节点
最后一层 embedding
向量的各维度方差的和(方差是跨多个采样之间来计算)。另外这里只考虑最后一层embedding
的方差,并未考虑中间层embedding
的方差。为了计算最后一项(方差项),需要对每个
batch
执行多次采样,从而对同一个父节点的多个估计激活值计算方差。
在损失函数中我们仅对最后一层的embedding
的方差进行惩罚以进行有效的计算,并发现它足以在我们的实验中提供有效的性能。
为了使得混合损失最小化,我们需要对混合损失进行梯度计算。
Tensorflow
)轻松得到。幸运的是,我们证明了分类损失相对于采样器的梯度为零。我们还推导出有关采样器方差项相对于采样器的梯度。详细内容在原始论文的补充材料给出。
GCN
的更新方程仅聚合来自 1-hop
邻域的消息。为了使网络更好地利用远处节点上的信息,我们可以用类似于随机游走的方式来采样multi-hop
邻域,从而用于 GCN
更新。然而,随机游走需要额外的采样来获得远处的节点,这对于稠密图而言计算代价太高。
本文中我们提出通过 skip connection
来传播远处节点的信息。skip connection
的关键思想是重用第 2-hop
邻域。如果我们进一步从 skip connection
,则聚合将涉及 1-hop
邻域和 2-hop
邻域。
具体而言,skip connection
的更新方程为:
其中:
由于
虽然论文实验表明显式计算
的 skip connection
能提高模型效果,但是这里的近似计算带来的噪音使得最终没有效果提升。
我们并未学习一个额外的参数
其中
skip connection
的输出可以加到 GCN layer
,在非线性层之前。
考虑到
skip connection
的更新方程为:
通过skip connection
,无需额外的 2-hop
采样即可保持二阶邻近性。此外,skip connection
允许信息在两个远距离的层之间传递,从而实现了更有效的反向传播和模型训练。
尽管设计相似,但是我们使用 skip-connection
的动机和 ResNet
中的残差函数不同:
ResNet
中,使用 skip connection
的目的是通过增加网络深度来获得更好的准确率。skip connection
用于保留二阶邻近性second-order proximity
。另外和 ResNet
中使用恒等映射相反,我们模型中沿着 skip connection
的计算更加复杂,如
如下图所示,使用不同采样方法来构建网络:(a)
表示 node-wise
采样方法;(b)
表示 layer-wise
方法;(c)
表示考虑 skip-connection
的采样方法。
实线表示采样节点,虚线表示未采样节点,红色圆圈表示该节点在上层至少有两个父节点。
node-wise
采样中,每个父节点的邻域都不会被其它父节点看到,因此父节点邻域和其它父节点之间的连接未被复用。layer-wise
采样中,所有邻域被上层所有父节点所共享,因此利用了所有的层间连接。和其它采样方法的联系:我们的方法和 GraphSAGE
、FastGCN
等方法的区别如下:
我们提出的 layer-wise
采样方法是新颖的。
GrphSAGE
对每个节点随机采样固定大小的邻域,是 node-wise
采样的。FastGCN
虽然是 layer-wise
采样的,但是采样的分布对于每一层都是相同的。layer-wise
方法,较低层的节点是在较高层节点的条件下进行采样的,这能够捕获层之间的相关性。我们的框架是更通用的。GraphSAGE
和 FastGCN
都可以归类为我们框架的特定变体,具体而言:
GraphSAGE
被视为一个 node-wise
采样器。FastGCN
可以视为一个特殊的 layer-wise
方法。我们的采样器是参数化的,并且可以训练来显式减少方差。
GraphSAGE
和 FastGCN
的采样器不包含任何参数,并且没有自适应来最小化方差。optimal importance sampling distribution
。通过对网络和采样器进行微调,可以显著减少结果的方差。考虑 attention
机制:GAT
将 self-attention
机制应用于图representation learning
。简而言之,它使用特定的 attention
值来取代 GCN
中的归一化邻接矩阵,即:
其中 hiden feature
之间的attention value
。它通常计算为:
其中
直接在我们的框架中应用类似于 GAT
的注意力机制是不可行的,因为概率 attention
值 hidden feature
来决定。如前所述,除非在采样后已经建立了网络,否则就不可能计算出较低层的 hidden feature
。
为解决这个问题,我们通过应用类似于自依赖函数开发了一种新的注意力机制:
其中:
数据集:
Cora,Citeseer,Pubmed
:目标是对学术论文进行分类。Reddit
数据集:目标是预测不同的帖子属于哪个社区 community
。这些图的规模从小到大都有所不同。具体而言:Cora,Citeseer
的节点数量为 Pubmed
数据集包含超过 Reddit
数据集包含超过
下表给出了这些数据集的统计量。
实验配置:
FastGCN
中的监督学习场景,我们使用训练样本的所有标签进行训练。inductive learning
的。和提供了所有节点的 transductive learning
不同,我们的方法聚合来自每个节点的邻域信息,从而学到可以泛化到未见过节点的结构属性。embedding
,也可以像模型训练中那样通过采样进行近似。这里我们使用完整的邻域,因为它更直接、更容易实现。16
;对于Reddit
数据集,隐层维度为 256
。Reddit
数据集,我们固定底层的权重,并且预计算 layer-wise
采样数量为 256
,非顶层的 layer-wise
采样数量为:Cora, Citeseer
数据集 128
、Pubmed
数据集 256
、Reddit
数据集 512
。Adam
优化器,初始学习率为:对于 Cora,Citeseer,Pubmed
设置为 0.001
、对于 Reddit
为 0.01
。0.0004
。ReLU
激活函数,并且没有 dropout
。30
的早停来训练所有模型,并选择最佳验证准确率的模型用于测试。Tesla P40 GPU
上进行。baseline
方法:由于 GraphSAGE
和 FastGCN
它们作者提供的代码不一致,这里我们根据我们的框架重新实现它们,从而进行更公平的比较。
node-wise
采样,从而实现 GraphSAGE
方法。其中每个节点的邻域采样大小为 5
。这种重新实现命名为 Node-Wise
。《Fast learning with graph convolutional networks via importance sampling》
中提出的独立同分布采样器来实现 IID
。Full GCN
体系架构作为强大的 baseline
。所有比较的方法共享相同的网络结构和训练设置,以进行公平的比较。
我们还对所有方法进行了前述介绍的注意力机制。
不同采样方法的比较:这里我们固定随机数种子,并且不进行任何早停实验。下图报告了Cora,Citeseer, Reddit
训练期间所有采样方法的收敛行为。曲线代表测试数据上的准确率曲线accuracy curve
。这里一个 training epoch
意味着对所有训练样本进行一次完整的遍历。
另外,为证明方差缩减的重要性,我们通过设置 Adapt(no vr)
。其中自依赖函数的参数被随机初始化,并且不进行训练。
可以看到:
我们的方法(称作 Adapt
) 在所有三个数据集上的收敛速度都比其它采样方法更快。
有趣的是,我们的方法甚至优于 Cora,Reddit
上的 Full
模型。
和我们的方法类似,IID
采样也是 layer-wise
的,但是它独立地构造了每一层。和IID
采样相比,由于有条件采样,我们的方法获得了更稳定的收敛曲线。
事实证明,考虑层间信息有助于提高模型训练的稳定性stability
和准确性accuracy
。
移除方差缩减的损失项确实会降低我们的方法在 Cora
和 Reddit
上的准确率。对于 Citeseer
而言,移除方差缩减的损失项的效果不是很明显。我们推测这是因为 Citeseer
的平均 degree
(1.4
)小于 Cora
(2.0
)和 Reddit
(492
),并且由于邻域的多样性有限,因此对方差的惩罚并没有那么重要。
此外我们还给出了Pubmed
和 Reddit
数据集的训练时间,单位:second/epoch
。可以看到:
所有方法的训练速度都比完整模型更快。
和 node-wise
方法相比,我们的方法具有更紧凑的体系结构,因此具有更快的训练速度。
为了说明这一点,假设顶层的节点数量为 node-wise
方法的输入层、隐层、顶层的大小分别为 5
)。而我们模型中所有层的节点数量为 node-wise
方法。
和其它 state-of-the-art
方法的比较:我们使用 graph kernel
方法 KLED
和 Diffusion Convolutional Network:DCN
对比了我们方法的性能。
Cora
和 Pubmed
在《Diffusion-convolutional neural networks》
中报道的 KLED
和 DCN
的结果。GraphSAGE
和 FastGCN
的结果。对于 GraphSAGE
,我们报告了具有默认参数的均值聚合结果。对于 FastGCN
,我们直接使用 《Diffusion-convolutional neural networks》
提供的结果。对于 baseline
和我们的方法,我们使用随机数种子进行 20
多个随机实验,并记录了测试集的平均准确率和标准差。所有结果如下表所示,可以看到:
Cora
和 Reddit
上。另外,仅对顶层进行方差缩减就能够提升性能。事实上,在我们的方法中对所有层进行方差缩减也是方便的,例如将它们都添加到损失函数中。为说明这一点,我们通过最小化第一层和顶层隐层的方差来对 Cora
进行实验,其中实验配置和下表相同。结果为 0.8780 +- 0.0014
,这比下表中的 0.8744 +- 0.0034
要更好。
我们使用公开的代码重新运行了 FastGCN
实验。四个数据集的 FastGCN
的平均准确率为 0.840 +- 0.005
、0.774 +- 0.004
、0.881 +- 0.002
、0.920 +- 0.005
。显然,我们的方法仍然超越了 FastGCN
。
这里重新运行的
FastGCN
和上表给出的结果(来自于各自的原始论文)不一致。
我们观察到 GraphSAGE
和 FastGCN
的官方实现之间的不一致之处,包括邻接矩阵的构造、隐层维度、mini-batch size
、最大训练 epoch
数量、以及其它在论文中未提及的工程技巧。
我们评估在 Cora
数据集上 skip-connection
的有效性。我们进一步在输入层和顶层之间添加了 skip-connection
。下图显式了原始 Adapt
方法以及带skip-connection
变体的收敛曲线。其中随机种子是共享的,并且没有使用早停。
可以看到:尽管就最终准确率而言,我们的 skip-connection
带来的提升并不大,但是确实可以显著增加收敛速度。添加 skip-connection
可以将收敛 epoch
数量从 150
降低到 100
。
我们在 20
个实验中使用不同的随机数种子进行实验,并在下表报告了使用早停获得的平均结果。可以看到,使用 skip-connection
可以稍微改善性能。
另外,通过将归一化的邻接矩阵 2-hop
邻域采样包含在我们的方法中(直接计算归一化矩阵的二次幂)。如上表所示,显式 2-hop
邻域采样进一步提高了分类准确率。尽管skip-connection
要比显式 2-hop
采样略差一点,但是它避免了
最后,我们评估了 Citeseer,Pubmed
数据集上 skip-connection
的有效性。
Citeseer
数据集,skip-connection
有助于更快地收敛。Pubmed
数据集,添加 skip-connection
仅在训练的早期才有效果。目前将神经网络推广到图结构数据上已经取得了长足的进步,但是大多数成功的方法都是使用监督学习,而现实很多场景中图数据是缺乏标签信息的。此外,通常希望从大型的图中挖掘新颖或有趣的结构。因此,无监督的图学习对于很多任务至关重要。
目前图的无监督学习的主要算法依赖于随机游走的目标random walk-based objective
,有时会进一步简化为重建邻域信息。背后的直觉是:训练编码器网络,使得在输入图中邻近的节点在embedding
空间中也是邻近的。
尽管随机游走的方法的能力强大,但是仍然存在一些已知的限制:
aproximity information
,从而忽略图的结构信息structural information
,并且性能高度依赖于超参数的选择。inductive bias
,即相邻的节点具有相似的representation
。在论文 《Deep graph infomax》
中,作者提出了一个基于互信息mutual information
而不是随机游走的无监督的图学习的目标。作者提出了 Deep Graph Infomax:DGI
,这是一种以无监督方式学习图结构化数据的节点representation
的通用方法。
DGI
依赖于最大化图的 patch representation
(即节点 embedding
)和相应的 high-level summary
之间的互信息mutual information
,二者均使用已构建的图卷积网络体系结构得到。学到的 path representation
总结了目标节点为中心的子图,因此可复用于下游的 node-wise
学习任务。
和大多数以前的使用 GCN
进行无监督学习的方法相比,DGI
不依赖于随机游走目标,并且很容易应用于 transductive learning
和 inductive learning
。该方法在各种节点分类benchmark
上表现出有竞争力的性能,有时甚至超越了监督学习的性能。
最近 Mutual Information Neural Estimation:MINE
使得互信息的可扩展估计scalable estimation
可行又实用。MINE
认为,利用神经网络的梯度下降法可以实现高维连续随机变量之间互信息的估计。具体而言,给定随机变量
其中:
根据定义有 KL
散度。MINE
利用了 KL
散度的对偶表示,并依赖于训练一个统计网络作为样本的分类器,而样本来自于两个随机变量的联合分布(类别一)及其边际概率的乘积(类别二)。
继MINE
之后,Deep InfoMax: DIM
训练编码器模型,从而最大化 high-level
全局representation
和局部的部分输入(如图像的 patch
)的局部representation
之间的互信息。这鼓励编码器携带在所有位置location
都存在的信息类型(因此是全局相关的),例如图像类别标签。
DIM
在图像数据场景中严重依赖于卷积神经网络结构。据我们所知,目前还没有工作将互信息最大化应用于图结构数据。这里我们将DIM
的思想应用到图数据,因而提出了称之为Deep Graph Infomax:DGI
的方法。
相关工作:
对比方法contrastive method
:无监督学习 representation
的一种重要方法是训练编码器,使得编码器在捕获感兴趣的representation
和不感兴趣的representation
之间形成对比。例如,可以使得编码器对于 real
输入增加评分、对于 fake
输入降低评分。评分函数有很多种,但是在图数据相关论文中,常见的是分类的得分。
DGI
也使用了对比学习,因为我们的目标是基于真实 local-global pair
对、以及负采样的 local-global pair
对进行分类。
采样策略:对比学习的关键是如何采样正样本和负样本。
graph representation learning
的先前工作依赖于局部对比损失,即强制相邻的节点具有相似的 representation
。正样本通常对应于图的short random walk
中共现的 pair
对。从语言模型的观点来看,这是将随机游走视为句子、将节点视为word
。node-anchored
采样方法,该方法的负样本主要基于随机采样。例如:有一些curriculum-based
负采样方法,它逐渐采样更靠近closer
的负样本。或者,引入对抗方法来选择负样本。预测编码predictive coding
:对比预测编码contrastive predictive coding: CPC
是另一种基于互信息最大化的深度学习表示方法。和我们方法不同,CPC
和上述的图方法都是预测性的 predictive
:对比目标有效地在输入的结构之间训练了一个 predictor
,如相邻节点pair
对或者节点和它的邻域。而我们的方法同时对比了图的 global
部分和 local
部分,其中 global
变量是根据所有 local
变量计算而来。
给定图
每个节点
这里我们假设图是无权重的,即
我们的目标是学习一个编码器encoder
representation
矩阵,它的第 representation
向量,representation
向量的维度。
一旦学到 representation
向量就可以用于下游的任务,如节点分类任务。
这里我们重点介绍图卷积编码器,它是一种灵活的node embedding
架构,并且通过在局部邻域上反复聚合从而生成节点representation
。
一个关键结果是:生成的节点 embedding
summarize
了节点 patch
的信息,而不仅仅是节点 patch representation
来强调这一点。
我们学习编码器的方法依赖于最大化局部互信息local mutual information
,即:我们寻求节点的 representation
(局部的),它捕获了整个图的全局信息内容(通过一个 summary vector
为了获得graph-level
的 summary vector
readout
函数 patch representation
总结为 graph-level representation
:
作为最大化局部互信息的代理proxy
,我们使用了一个判别器discriminator
patch-summary
的 pair
对之间的概率得分。如果 summary
包含这个 patch
,则会返回一个更高的得分。
判别器的正样本来自于 patch representation
和 summary vector
的 pair
对
注意,正样本来自于联合分布
判别器的负样本来自于另一个图 patch representation
和图 summary vector
的 pair
对
在多图的环境下,可以将
注意,负样本来自于边际分布乘积
负样本的选择将决定特定类型的结构信息,这些结构信息是作为这种互信息最大化的副产品而希望捕获的。
我们遵循 Deep InfoMax:DIM
的直觉,使用对比噪音类型的目标函数noise-contrastive type objective
:在联合分布(正样本)和边际概率乘积(负样本)之间应用标准的二元交叉熵binary cross-entropy:BCE
损失。遵从DIM
的工作,我们使用以下目标函数:
基于联合分布与边际概率乘积之间的 JS
散度,该方法有效地最大化
由于迫使所有得到的 patch representation
都保持全局graph summary
的互信息,这使得可以保留 patch-level
的相似性。例如,具有相似结构角色structural role
的距离遥远的节点(众所周知,这些节点是很多节点分类任务的强力的 predictor
)。
假设在单图环境下,DGI
的过程如下图所示:
使用随机扰动函数
扰动函数的选择非常重要,可以仅扰动
而保留图结构、也可以仅扰动图结构 而保留节点特征、也可以二者同时扰动。
通过编码器获取输入图 patch representation
:
通过编码器获取负样本 patch representation
:
通过 readout
函数获取输入图 summary vector
:
通过对损失函数
现在我们提供一些直觉,将判别器 graph representation
上的互信息最大化联系起来。
令 node representation
(每一组代表一个图,一共 readout
函数,summary vector
,边际概率分布为
当
证明见原始论文。
可以证明:
其中:
Jensen
不等式来证明。readout
函数是一个常量时成立,此时没有任何分类器表现得比随机分类更好。推论:从现在开始,假设所使用的 readout
函数 summary vector
数量)满足 summary
证明见原始论文。
定理一:记MI
为互信息,则有
证明见原始论文。
该定理表明:对于有限的输入集和合适的确定性函数,可以通过最小化判别器中的分类误差来最大化输入和输出之间的互信息。
定理二:令 high-level
特征为:
假设有
证明见原始论文。
这激发了我们在联合分布和边际概率乘积的样本之间使用分类器,并且在神经网络优化的上下文下,使用binary cross-entropy:BCE
损失来优化该分类器。
我们评估了 DGI
编码器在各种节点分类任务(transductive learning
和 inductive learning
)上学到的 representation
的优势。
在每种情况下,都是用 DGI
以完全无监督方式学到了patch representation
,然后用简单的线性(逻辑回归)分类器来进行node-level
分类。分类器的输入就是节点的 representation
。
数据集:
引文网络 Cora, Citeseer, Pubmed
:它们是 transductive learning
数据集。在这些数据集中,节点表示论文,边表示论文之间的引用关系,节点特征对应于论文的 bag-of-word
。每个节点都有一个类别标签。
我们对每个类别仅允许使用 20
个节点进行训练。但是,为了遵循transductive learning
,无监督学习算法可以访问所有节点的特征向量。
我们在 1000
个测试节点上评估了学到representation
的预测能力。
Reddit
数据集:它是大图上的 inductive learning
数据集。我们使用 2014
年9
月期间创建的 Reddit
帖子作为数据集,每个帖子代表节点,如果同一个用户对两个帖子都发表了评论则这两个帖子之间存在边。
数据集包含 231443
个节点、11606919
条边。节点特征是帖子内容和评论的 GloVe embedding
向量、以及帖子的评分或者评论数量等指标。我们的目标是预测帖子所属的社区。
我们将前20
天发布的帖子用于训练、剩余帖子用于验证或测试。并且训练期间,验证集和测试集是不可见的。
PPI
数据集:它是多图的 inductive learning
数据集。该数据集由不同人体组织对应的graph
组成,其中包含 20
个图用于训练、2
个图用于验证、2
个图用于测试。注意,在训练过程中,测试图完全未被观察到。
每个节点具有 50
个特征,这些特征由 positional gene sets, motif gene sets, immunological signatures
等组成。一个节点可能具有多个标签,这些标签是从分子本体数据库收集的基因本体标签,共有 121
个。
所有数据集的统计信息如下表。
我们对于 transductive learning
、单图inductive learning
、多图 inductive learning
使用不同的编码器和扰动函数。
transductive learning
:我们使用单层GCN
作为编码器,即:
其中:
ReLU
(即 parametric ReLU: PReLU
)。Pubmed
数据集,由于内存限制我们选择 这里使用的扰动函数旨在鼓励representation
正确编码图中不同节点的结构相似性,因此 patch representation
。
论文证明了DGI
对于其它扰动函数是稳定的(参考原始论文),但是我们发现:保留图结构的那些扰动函数效果最好。
单图inductive learning
:这里我们不再使用单层 GCN
作为编码器,因为这种编码器依赖于固定且已知的邻接矩阵。相反,我们使用 GraphSAGE-GCN
,并选择均值池化:
这里通过度矩阵 GAT
模型来编码。
我们的编码器采用三层GraphSAGE-GCN
,并使用 skip connection
:
其中
PReLU
激活函数。Reddit
数据集规模较大,无法完全放入GPU
内存。这里我们采用 GraphSAGE
中的采样方法:分别在第一层、第二层、第三层对邻域采样 10/10/25
个邻居节点。因此每个中心节点将采样 1+10+100+2500=2611
个3-hop
邻域节点(称作一个 patch
)。batch-size=256
的 mini-batch
随机梯度下降。transductive learning
中类似的扰动函数,但是将每个采样的 patch
视为要扰动的子图。注意,这可能导致中心节点的特征被替换为采样邻居的特征,从而进一步促进了负样本的多样性。然后将中心节点的 patch representation
馈入到判别器。多图 inductive learning
:我们的编码器是一个三层的GraphSAGE
均值池化模型,并且带skip connection
:
其中 inductive learning
区别在于:这里的 skip connection
是sum
融合,而前述的 skip connection
是 concate
融合。
PReLU
激活函数。graph
来作为负样本。即我们的扰动函数只是从训练集中采样了不同的图。考虑到该数据集中 40%
以上的节点包含全零的特征,因此这种方法最为稳定。graph
的输入特征应用 dropout
。embedding
馈入到逻辑回归模型之前,对包括训练集上的embedding
进行标准化是有益的。在所有的配置下,我们使用统一的readout
函数、判别器架构:
我们使用简单的均值函数来作为readout
函数:
其中 sigmoid
非线性函数。
尽管我们发现该readout
函数在所有实验中表现最佳,但是我们假设其能力会随着graph size
的增加而降低。此时,可能需要使用更复杂的readout
架构,如 set2vec
或者 DiffPool
。
判别器通过应用简单的双线性评分函数对 summary-patch
进行评分:
其中 sigmoid
非线性激活函数。
所有模型都使用 Glorot
初始化,并使用 Adam SGD
优化器进行训练,初始学习率为 0.001
(对于 Reddit
为
在 transductive
数据集上,我们在training loss
上应用早停策略,patience epoch = 20
。在 inductive
数据集上,我们训练固定数量的 epoch
,对于 Reddit
为 150
、对于 PPI
为 20
。
baseline
方法:
transductive learning
:我们进行了 50
次实验并报告测试集上的平均准确率和标准差。然后将我们的结果和 DeepWalk, GCN, Label Propagation:LP, Planetoid
等方法进行比较。
另外我们还提供了对原始特征进行逻辑回归分类、将原始特征和 DeepWalk
特征拼接进行逻辑回归分类的结果。
inductive learning
:我们进行了 50
次实验并报告了测试集上的 micro-F1
得分的均值。我们直接复用 GraphSAGE
论文中的结果进行比较。
由于我们的方法是无监督的,因此我们对比了无监督的 GraphSAGE
方法。
我们还提供了两种监督学习的方法比较:FastGCN
和 Avg. pooling
。
实验结果如下表所示,其中第一列中我们给出每种方法在训练过程中可用的数据类型:X
为特征信息,A
为邻接矩阵,Y
为标签信息。GCN
对应于以监督方式训练的两层 DGI
编码器。
结论:
DGI
在所有五个数据集上均实现了出色的性能。尤为注意的是,DGI
方法和监督学习的 GCN
模型相比具有竞争力,并且在 Cora
数据集和 Citeseer
数据集上甚至超越了监督学习的 GCN
。
我们认为这些优势源自事实:DGI
方法间接地允许每个节点都可以访问整个图的属性,而监督学习的 GCN
仅限于两层邻域(由于训练信号的极其稀疏,因此可能会遭受过拟合的风险)。
应当指明的是,尽管我们能够超越同等编码器架构的监督学习,但是我们我们的性能仍然无法超越 state-of-the-art
的 transductive
架构。
DGI
方法在 Reddit
和 PPI
数据集上成功超越了所有竞争的无监督 GraphSAGE
方法,从而验证了 inductive learning
节点分类任务中,基于局部互信息最大化方法的潜力。
DGI
在 Reddit
上的结果和监督学习的 state-of-the-art
相比具有竞争力,而在 PPI
上差距仍然很大。我们认为这可以归因于节点可用特征的极度稀疏:在 PPI
数据集上超过 40%
的节点具有全零特征。而我们的 DGI
方法中的编码器非常依赖于节点特征。
我们注意到,随机初始化的图卷积网络(不需要经过训练)可能已经提取了非常有用的特征,并代表了强大的 baseline
。这是众所周知的事实,因为它和 WL test
图同构测试有关。这已被GCN
和 GraphSAGE
等论文所研究过。
为此,我们提供了 Random-Init
这个 baseline
,它是从随机初始化的编码器(不需要训练)获取节点 embedding
,然后馈入逻辑回归分类器。
DGI
可以在这个强大的 baseline
上进一步提升。inductive
数据集上的结果表明:以前基于随机游走的负采样方法可能对于学习分类任务是无效的。这个编码器其实就是
GCN/GraphSAGE
等常用架构。
最后,应该注意的是,更深的编码器减少了我们正负样本之间的有效变异性。我们认为这就是为什么浅层架构在某些数据集上表现更好的原因。虽然我们不能说这个趋势普遍存在,但是通过 DGI
损失函数我们发现,通常采用更wider
的模型而不是更 deeper
的模型可以带来收益。
定性分析:我们给出 Cora
数据集的 embedding
经过 t-SNE
可视化结果(因为该数据集节点数最少)。左图为原始特征的可视化,中间为Random-Init
得到 embedding
的可视化,右图为训练好的 DGI
得到 embedding
的可视化。
可以看到:DGI
得到的embedding
的投影表现出明显的聚类。
在t-SNE
可视化之后,我们关注Cora
数据集上判别器的得分。我们对于正样本和负样本(随机采样的)可视化了每个节点的判别器得分:左图为正样本(真实的图)、右图为负样本(负采样的图)。
可以看到:
在正样本学到的 embedding
的簇上,只有少数 hot
节点得到较高的判别器得分。这表明用于判别和分类的 embedding
各维度之间可能存在明显的差异。
正如预期的那样,模型无法在负样本中找到任何强大的结构。
一些负样本种的节点获得了较高的判别器得分,这是由于 Cora
中的一些 low-degree
节点引起的。
正样本的平均分高于负样本的平均分。
我们将判别器打分 top-score
的正样本和负样本的 embedding
进行可视化。如下图所示:上半部分为 highest-scored
正样本,下半部分为 lowerst-scored
负样本。
可以看到:在某些维度上,正样本和负样本都存在着严重的 bias
。
我们假设:在随机shuffle
bias
需要将负样本的判别器得分拉下来。对于正样本,可以使用其它维度来抵消这些维度上的 bias
,同时编码 patch
相似度。
为证明这一假设,我们根据正样本和负样本之间的可区分性对 512
个维度进行排序。我们从 embedding
中根据该顺序依次删除这些维度(要么从最有区分度的维度开始,记作
可以看到,观察到的趋势在很大程度上支持了我们的假设:如果我们首先删除 biased
维度(embedding
维度,同时仍保持对监督 GCN
的竞争优势)。正样本仍然能够保持正确的判别,直到移除了一半以上的维度为止。
注意:biased
维度指的是正样本和负样本都存在着严重的 bias
的维度,因此无法区分正样本和负样本。
当前GNN
架构的主要局限性在于它们本质上是平的 flat
,因为它们仅仅跨图的边来传播信息,并且无法以层次hierarchical
的方式推断和聚合信息。这种缺乏层次结构的情况对于graph
分类任务尤其成为问题。当GNN
应用到图分类时,标准方法是为图中的所有节点生成 embedding
,然后将所有这些节点 embedding
执行全局池化。这种全局池化忽略了图中可能存在的任何层次结构,并阻碍了人们为 graph-level
预测任务建立有效的 GNN
模型。
论文 《Hierarchical Graph Representation Learning with Differentiable Pooling》
提出了 DIFFPOOL
,这是一种可微分的graph pooling
模块,可以通过层次的、端到端的方式适应各种 GNN
架构,如下图所示。DIFFPOOL
允许开发更深的 、可以学习操作图的层次表示hierarchical representation
的 GNN
模型。
下图中,在每个层次的 layer
上运行一个 GNN
模型来获取节点 embedding
。然后,DIFFPOOL
使用这些学到的 embedding
将节点聚类到一起,并在这个粗化的图上运行另一个 GNN layer
。重复 representation
来对图进行分类。
DIFFPOOL
类似于 CNN
的空间池化。和标准的 CNN
相比,GNN
面临的挑战是:
graph
不包含自然的空间局部性概念,即不能简单的在graph
上对一个 patch
上的所有节点进行池化,因为图的复杂拓扑结构使得无法定义 patch
。为解决上述挑战,我们需要一个模型,该模型学习如何将节点聚类在一起从而在底层图之上搭建一个层次的 multi-layer
结构。
DIFFPOOL
方法在GNN
的每一层上学习可微的 soft assignment
,并根据其学到的 embedding
将节点映射到簇。在 DIFFPOOL
框架中,我们通过以层次的方式堆叠 GNN layer
,从而生成 deep GNN
:第 DIFFPOOL
的每一层都将输入图越来越粗化,并且 DIFFPOOL
能够在训练后生成任何输入图的hierarchical representation
。
实验表明:DIFFPOOL
可以和各种 GNN
方法结合使用,从而使得平均准确率提高 7%
,并且在五个benchmark
中的四个达到了 state-of-the-art
性能。
最后,论文证明 DIFFPOOL
可以学习和输入图中定义明确的社区相对应的、可解释的层次聚类。
相关工作:
通用的图神经网络:近年来提出了各种各样的图神经网络模型。这些方法大多符合 《Neural message passing for quantum chemistry》
提出的 "neural message passing
"的框架。在消息传递框架中,GNN
被看作是一种消息传递算法,其中 node representation
是使用可微聚合函数从其邻居节点的特征中反复计算出来的。
《Representation learning on graphs: Methods and applications》
对该领域的最新进展进行了回顾, 《Geometric deep learning:Going beyond euclidean data》
概述了图神经网络与谱图卷积 spectral graph convolution
的联系。
基于图神经网络的图分类:图神经网络已经被应用于各种任务,包括节点分类、链接预测、图分类、和化学信息学。在图分类的背景下应用 GNN
的一个主要挑战是如何从 node embedding
到整个图的 representation
。解决这个问题的常见方法包括:
node embedding
。virtual node
"。node embedding
。然而,所有这些方法都有一个局限性,即它们不学习 hierarchical representation
(即所有的 node embedding
都在单个 layer
中被全局地池化),因此无法捕捉到许多现实世界中图的自然结构。最近的一些方法也提出了将 CNN
架构应用于所有node embedding
的拼接,但这需要指定(或学习)节点的典型排序(一般来说这非常困难,相当于解决图的同构性graph isomorphism
)。
DIFFPOOL
的关键思想是:通过提供可微的模块来层次地池化图节点,从而构建深度的 multi-layer GNN
模型。
给定图
每个节点
为方便讨论,我们将所有维度(包括输入特征维度和 embedding
向量维度)都设为
这里我们假设图是无权重的,即
注意:这里我们未考虑边特征。
给定一组带标签的图 graph
到label
的映射函数
和标准的监督学习任务相比,这里的挑战是:我们需要一种从这些输入图中抽取有用的特征向量的方法。即,我们需要一个过程来将每个图转换为一个有限维的向量。
本文我们以GNN
为基础,以端到端的方式学习图分类的有用representation
。具体而言,我们考虑采用以下的 message-passing
架构的 GNN
:
其中:
embedding
,其中 embedding
我们提出的可微池化模块可以应用于任何 GNN
模型,并且对于如何实现
消息传递函数 GCN
中采用一个线性映射和一个 ReLU
非线性激活函数来实现:
其中:
完整的 GNN
模块可能包含 embedding
为 2~6
层。
为简化讨论,在后续内容中,我们将忽略GNN
的内部结构,并使用 GNN
模块,它根据邻接矩阵
上述GNN
的本质上是 flat
的,因为它们仅在图的边之间传播信息。我们的目标是定义一种通用的、端到端的可微策略,该策略允许人们以层次化的方式堆叠多个 GNN
模块。
形式上,给定一个邻接矩阵 GNN
模块的输出 embedding
然后,而可以将这个新的粗化图用作另一个 GNN layer
的输入,并且可以将整个过程重复 GNN layer
的模型,该模型对输入图的一系列越来越粗的版本进行操作。因此,我们的目标是学习如何使用 GNN
的输出将节点聚类在一起,以便我们可以将这个粗化图用作另一个 GNN layer
的输入。
和常规的图粗化任务相比,为 GNN
设计这样的池化层尤其具有挑战性的原因是:我们的目标不是简单地将一个图中的节点聚类,而是提供一个通用的方法对输入图的一组广泛的节点进行层次池化hierarchically pool
。即,我们需要模型来学习一种池化策略,该策略将在具有不同节点、边的图之间进行泛化,并且在推断过程中可以适配各种图结构。
DIFFPOOL
方法通过使用 GNN
模型的输出来学习节点上的cluster assignment
矩阵来解决上述挑战。关键的直觉是:我们堆叠了 GNN
模块,其中基于第 GNN
生成的 embedding
并以端到端的方式学习如何将节点分配给第
因此,我们不仅使用 GNN
来抽取对graph
分类有用的节点 embedding
,也使用 GNN
来抽取对层次池化有用的节点 embedding
。通过这种方式,DIFFPOOL
中的 GNN
学会编码一种通用的池化策略。
我们首先描述 DIFFPOOL
模块如何在给定assignment
矩阵的情况下在每一层上池化节点,接下来我们讨论如何使用 GNN
架构生成assignment
矩阵。
给定 assignment
矩阵的池化:我们将第 cluster assignment
矩阵定义为 soft assignment
给下一个粗化的、第
假设 assignment
矩阵。我们假设第 embedding
矩阵为 DIFFPOOL
层将粗化coarsen
输入图,生成一个新的粗化的邻接矩阵 embedding
矩阵
其中:
DIFFPOOL
根据cluster assignment
矩阵 embedding
embedding
。
物理意义:第
层的每个簇的 embedding
等于它包含的子节点的embedding
的加权和,权重为子节点属于这个簇的可能性(由assignment
矩阵给出)。
DIFFPOOL
根据cluster assignment
矩阵 cluser pair
对之间的连接强度。
物理意义:第
层的任意两个簇之间的距离等于各自包含的子节点之间距离的加权和,权重为子节点属于各自簇的可能性(由 assignment
矩阵给出)。
这样,DIFFPOOL
粗化了图:下一层邻接矩阵 cluster node
的粗化图,其中每个簇点cluster node
对应于第
注意:embedding
。
粗化的邻接矩阵 embedding
GNN layer
的输入。我们接下来详述。
学习 assignment
矩阵:现在我们描述DIFFPOOL
如何生成assignment
矩阵 embedding
矩阵 GNN
来生成这两个矩阵,这两个GNN
都作用到簇点cluster node
特征
第 embedding GNN
是标准的 GNN
模块:
即,我们采用第 GNN
来获取簇点的新的 embedding
矩阵
第 pooling GNN
使用簇点的邻接矩阵和特征矩阵来生成 assignment
矩阵:
其中 softmax
是逐行进行。
注意:
这两个 GNN
采用相同的输入数据,但是具有不同的参数化parameterization
并发挥不同的作用:embedding GNN
为第 embedding
;pooling GNN
为第
当
在倒数第二层 assignment
矩阵 1
的向量,即:将最后一层 final embedding
向量。
然后可以将这个final embedding
向量用于可微分类器(如 softmax
层)的特征输入,并使用随机梯度下降来端到端地训练整个系统。
排列不变性permutation invariance
:注意,为了对图分类有用,池化层应该是节点排列不变的。对于 DIFFPOOL
,我们得到以下正面的结论,这表明:只要GNN
的组件component
是排列不变的,那么任何基于 DIFFPOOL
的 deep GNN
模型都是排列不变的。
推论:令 permutation matrix
,则只要满足
证明:假设 GNN
模块是排列不变的,则
在实践中,仅使用来自图分类任务的梯度信号来训练 pooling GNN
可能会很困难。直观地讲,我们有一个非凸优化问题,在训练初期很难将 pooling GNN
推离局部极小值。
为缓解该问题,我们使用辅助的链接预测目标auxiliary link prediction objective
训练 pooling GNN
,该目标编码了先验知识:应该将相邻的节点映射到相同的簇。具体而言,在每一层
其中 Frobenius
范数。
给出任意两个节点位于相同簇中的可能性,如果它等于邻接矩阵那么表明: pooling GNN
将相连的节点分配到相同的簇、将不相连的节点分配到不同的簇。
注意:邻接矩阵 assignment
矩阵的函数,并且在训练期间会不断改变。
pooling GNN
的另一个重要特点是:每个节点的输出cluster assignment
通常应该接近一个one-hot
向量,从而清楚地定义节点属于哪个cluster
。因此,我们通过最小化以下目标来对cluster assignment
的熵进行正则化:
其中:assignment
矩阵
在训练期间,来自每一层的 cluster assignment
。
我们针对多个state-of-the-art
图分类方法评估了 DIFFPOOL
的优势,目的是回答以下问题:
Q1
:DIFFPOOL
对比其它 GNN
中的池化方法(如 sort pooling
或者 Set2Set
方法)相比如何?Q2
:结合了 DIFFPOOL
的 GNN
对比图分类任务中的 state-of-the-art
方法(包括 GNN
方法和 kernel-based
方法)相比如何?Q3
:DIFFPOOL
是否在输入的图上计算得到有意义且可解释的聚类?数据集:蛋白质数据集,包括ENZYMES, PROTEINS, D&D
;社交网络数据集 REDDIT-MULTI-12K
;科学协作数据集COLLAB
。
对这些数据集,我们执行 10-fold
交叉验证来评估模型性能,并报告 10
个 fold
的平均分类准确率。
模型配置:在我们的实验中,用于 DIFFPOOL
的 GNN
模型是建立在 GraphSAGE
架构之上的,因为我们发现GraphSAGE
比标准的 GCN
效果更好。
我们使用 GraphSAGE
的 mean
变体,并在我们的体系架构中每隔两个 GraphSAGE layer
之后应用一个 DIFFPOOL layer
。在每个 DIFFPOOL
层之后、下一个DIFFPOOL
层(或者 readout
层)之前,我们添加3
层图卷积层。
这里感觉前后矛盾,就是是
3
层图卷积层还是2
层图卷积层?要看代码。
数据集一共使用 2
个 DIFFPOOL
层。对于小型数据集(如 ENZYMES, COLLAB
),1
个 DIFFPOOL
层就可以实现相似的性能。
embedding
矩阵和 assignment
矩阵分别由两个单独的 GraphSAGE
模型计算。
在 2
个 DIFFPOOL
层的体系架构中,cluster
数量设置为 DIFFPOOL
之前节点数量的 25%
;在 1
个 DIFFPOOL
层的体系架构中,cluster
数量设置为 DIFFPOOL
之前节点数量的 10%
。
在GraphSAGE
的每一层之后都应用了 batch normalization
。
我们还发现,在每一层的节点 embedding
中添加
所有模型都训练最多 3000
个 epoch
,并基于验证损失来执行早停策略。
我们还评估了 DIFFPOOL
的两个简化版本:
DIFFPOOL-DET
:是一个DIFFPOOL
的变体,其中使用确定性的图聚类算法来生成 assignment
矩阵。DIFFPOOL-NOLP
:是一个 DIFFPOOL
的变体,其中移除链接预测的辅助目标。另外,我们还将在 Structure2Vec
架构上测试了 DIFFPOOL
的类似变体,从而演示如何将 DIFFPOOL
应用于其它 GNN
模型。
baseline
方法:这里我们考虑使用不同了池化的 GNN
方法,以及 state-of-the-art
的 kernel-based
方法。
GNN-based
方法:
GraphSAGE
。其它GNN
变体被忽略,因为根据经验,GraphSAGE
在任务中获得更高性能。Structure2Vec:S2V
是一种state-of-the-art
的graph representation learning
方法,它将一个潜在变量模型latent variable model
和 GNN
相结合,并使用全局均值池化。ECC
将边信息融合到 GCN
模型中,并使用一个图粗化算法来执行池化。PATCHYSAN
对每个节点定义一个感受野,并使用规范化的节点顺序,从而对节点embedding
的序列应用卷积。SET2SET
使用 Set2Set
方法来代替传统 GNN
架构中的全局均值池化。这里我们使用 GraphSAGE
作为 base GNN model
。SORTPOOL
应用GNN
架构,然后执行单层 soft pooling
层,然后对排序的节点 embedding
执行一维卷积。对于所有 GNN baseline
,我们尽可能使用原始作者报告的 10-fold
交叉验证的结果。如果作者没有公开结果,则我们从原始作者获取代码运行模型,并根据原始作者的准则执行超参数搜索。
对于 GraphSAGE
和 SET2SET
,我们像 DIFFPOOL
方法一样使用基本的实现和超参数择优。
kernel-based
算法:我们使用 GRAPHLET、SHORTEST-PATH 、WEISFEILERLEHMAN kernel:WL、 WEISFEILER-LEHMAN OPTIMAL ASSIGNMENT KERNEL:WLOA
等方法。
对于每个kernel
,我们计算归一化的 gram
矩阵。我们使用 10-fold
交叉验证,并使用 LISVM
计算分类准确率。超参数 C
的搜索范围 WL
和 WL-OA
的迭代范围从 0
到 5
。
下表给出了实验结果,这为 Q1
和 Q2
给出了正面的回答。最右侧的 Gain
列给出了相对于GraphSAGE
方法在所有数据集上的平均性能提升。
可以看到:
DIFFPOOL
方法在 GNN
的所有池化方法中获得了最好的性能,在 GraphSAGE
体系结构上平均提升 6.27%
,并且在 5
个 benchmark
上的 4
个达到了 state-of-the-art
。DIFFPOOLDET
在 COLLAB
数据集上达到了 state-of-the-art
性能。这是因为 COLLAB
的很多协作图仅显示了单层社区结构,这些结构可以通过预先计算的图聚类算法很好地捕获。有一个现象是:尽管性能有了显著提升,但是 DIFFPOOL
可能无法稳定训练。并且即使采用相同的超参数设置,不同运行之间的准确率也存在着差异。可以看到添加链接预测目标可以使得训练更加稳定,并减少不同运行之间准确率的标准差。
除了 GraphSAGE
之外,DIFFPOOL
也可以应用于其它GNN
架构,从而捕获图数据中的层次结构。为此我们在 Structure2Vec:S2V
上应用了 DIFFPOOL
。
我们使用三层的 S2V
架构:
S2V
的第一层之后应用一个 DIFFPOOL
层,并在 DIFFPOOL
的输出的顶部堆叠另外两个S2V
层。S2V
的第一层、第二层之后分别应用一个 DIFFPOOL
层。在这两个变体中,S2V
模型用于计算 embedding
矩阵,而 GraphSAGE
模型用于计算assignment
矩阵。
实验结果如下所示。可以看到: DIFFPOOL
显著改善了 ENZYMES
和 D&D
数据集上 S2V
的性能。
在其它数据集上也观察到类似的趋势。结果表明:DIFFPOOL
是一个可以提升不同 GNN
架构的通用池化策略。
尽管DIFFPOOL
需要对 asignment
矩阵进行额外的计算,但我们观察到 DIFFPOOL
实际上并不会带来大量的额外运行时间。这是因为每个 DIFFPOOL
层都通过粗化来减小了图的大小,从而加快了下一层中图的卷积操作。
具体而言,我们发现带有 DIFFPOOL
的 GraphSage
模型要比带有 SET2SET
池化的 GraphSage
模型快 12
倍,并且仍能实现明显更高的准确率。
为回答问题Q3
, 我们通过可视化不同层中的 cluster assignment
来调研 DIFFPOOL
是否学习有意义的节点聚类。下图给出 COLLAB
数据集中,第一层和第二层的节点分配的可视化,其中:
cluster
成员关系。节点的 cluster
成员关系是通过对cluster assignment
的概率取argmax
来确定的。graph
),图 (a)
给出两层的层次聚类,图 (b),(c)
给出一层的层次聚类。25%
,但是 assignment GNN
可以自动学习适当数量的、且有意义的簇,从而分配给这些不同的图。(即大量的簇没有分配到任何节点)。可以看到:
即使仅基于图分类目标,DIFFPOOL
仍可以捕获层次的社区结构。我们还通过链接预测辅助目标观察到cluster assignment
质量的显著提升。
稠密的子图结构 vs
稀疏的子图结构:我们观察到 DIFFPOOL
学会了以非均匀方式将所有节点折叠collapse
为 soft cluster
,并且倾向于将稠密的子图折叠为簇。
GNN
可以有效地对稠密的、clique-like
的子图执行消息传递(由于较小的直径),因此在这种稠密的子图中将节点池化在一起不太可能导致结构信息的丢失。这直观地解释了为什么折叠稠密子图是 DIFFPOOL
的有效池化策略。GNN
消息传递可能无法捕获这些结构。因此,通过分别池化稀疏子图的不同部分,DIFFPOOL
可以学习捕获稀疏子图中存在的有意义的结构。相似representation
节点的分配:由于assignment network
基于输入节点及其邻域特征来计算 soft cluster assignment
,因此具有相似的输入特征和邻域结构的节点将具有相似的cluster assignment
。
实际上,可以构造一个人工case
:其中两个节点尽管相距很远,但是它们具有相同的节点特征和邻域特征。这种情况下,pooling GNN
迫使它们分配到同一个cluster
中。这和其它体系结构中的池化概念完全不同。在某些情况下,我们确实观察到不相连的节点被池化到一起。
另外,我们观察到辅助链接预测目标有助于阻止很远的节点池化到一起。并且,可以使用更复杂的 GNN
聚合函数(诸如高阶矩)来区分结构相似和特征相似的节点,总体的框架保持不变。
预定义聚类数的敏感性:我们发现assignment
根据网络深度和 pooling GNN
可以对更复杂的层次结构进行建模,但是会导致更大的噪声和更低的训练效率。
尽管 pooling GNN
通过端到端训练来学习使用适当数量的 cluster
。具体而言,assignment
矩阵可能不会用到某些簇。对于未被使用的 cluster
对应的矩阵列,它在所有节点上都具有较低的值。例如图2(c)
中,节点主要分配到 3
个簇上。
与结构化数据打交道是一种挑战。一方面,找到正确的方式来表达和利用数据中的结构可以改善预测性能;另一方面,找到这样的 representation
可能是困难的,而且在模型中添加结构会大大增加预测的复杂性。
论文 《Diffusion-Convolutional Neural Networks》
的目标是为通用的结构化数据设计一个灵活的模型,在提高预测性能的同时避免复杂性的增加。为了实现这一目标,作者引入 "diffusion-convolution
"操作,将卷积神经网络扩展到通用的图结构数据。简而言之,diffusion-convolution
操作不是像标准卷积操作那样在网格结构的输入中扫描一个 "正方形",而是通过在图结构的输入中扫描每个节点的diffusion process
来建立一个 latent representation
。
这个模型的动机是这样的:封装了 graph diffusion
的 representation
可以为预测提供一个比 graph
本身更好的 basis
。 graph diffusion
可以表示为一系列的矩阵幂次从而包含上下文信息,并且可以在多项式时间内计算,以及可以在 GPU
上有效实现。
在论文 《Diffusion-Convolutional Neural Networks》
中,作者提出了 diffusion-convolutional neural network: DCNN
,并探讨了它们在图数据的各种分类任务中的表现。许多技术在分类任务中包括结构信息,如概率关系模型 probabilistic relational model
和核方法 kernel method
。DCNN
提供了一种补充方法,在节点分类任务的预测性能上有了明显的改善。
DCNN
的主要优势:
DCNN
在节点分类任务中的表现明显优于其他方法,在图分类任务中的表现与baseline
方法相当。DCNN
提供了一种灵活的图数据表示方法,可以编码节点特征、边特征、以及单纯的结构信息,只需进行少量的预处理。DCNN
可用于图数据的各种分类任务,包括节点分类和图分类。DCNN
的预测可以表示为一系列的多项式时间的张量运算,并且该模型可以使用现有的库在GPU
上有效地实现。相关工作:
其它 graph-based
神经网络方法:其他研究者已经研究了如何将 CNN
从网格结构扩展到更普遍的图结构数据。
《Spectral networks and locally connected networks on graphs》
提出了一种与层次聚类 hierarchical clustering
相联系的空间方法,其中网络的层是通过节点集合的 hierarchical partitioning
来定义的。在同一篇论文中,作者提出了一种谱方法,将卷积的概念扩展到 graph spectra
。《Deep Convolutional Networks on Graph-Structured Data》
将这些技术应用于这样的数据:图并不是立即出现但是必须被推断。属于空间类别的 DCNN
与这项工作不同,因为 DCNN
的参数化 parameterization
使模型可以迁移:在一个图上学习的 DCNN
可以应用于另一个图。
概率关系模型:DCNN
也与概率关系模型 probabilistic relational model: PRM
有着密切的联系。概率关系模型是一族 graphical model
,能够代表关系数据的分布(《Probabilistic Graphical Models: Principles and Techniques》
)。与概率关系模型相比,DCNN
是确定性的,这使得 DCNN
能够避免指数爆炸(指数爆炸阻碍了概率关系模型的学习和推断)。
我们的研究结果表明:DCNN
的表现优于部分观察的条件随机场conditional random field: CRF
,即半监督学习的 SOTA
概率关系模型。此外,DCNN
以相当低的计算成本提供这种性能。学习DCNN
和部分观测的 CRF
的参数需要数值上最小化一个非凸目标:对于 DCNN
来说是反向传播误差,对于 CRF
来说是负的边际对数似然。
CRF
的边际对数似然是使用对比分区函数 contrast-of-partition-function
方法来计算的,这需要运行两次循环的信念传播belief propagation
:一次是在整个图上,一次是在固定观测标签的情况下。这种算法,以及数值优化中的每个 step
,具有指数级的时间复杂度 maximal clique
的大小。DCNN
的学习程序只需要对训练数据中的每个实例进行一次前向传播和反向传播。复杂度由 graph definition matrix
graph design matrix
其中,
核方法:核方法kernel method
定义了节点之间(即 kernel on graph
)或图之间(即 graph kernel
)的相似性度量,这些相似性可以作为通过核技巧 kernel trick
进行预测的基础。graph kernel
的性能可以通过将图分解为子结构,将这些子结构视为句子中的一个词,并拟合一个 word-embedding
模型来获得矢量化来提高。
DCNN
与kernel on graph
的 exponential diffusion
族有联系。exponential diffusion graph kernel
diffusion-convolution activation
也是由幂级数构造的。然而,它和
kernel representation
不是从数据中学习的。diffusion-convolution representation
是由节点特征和图结构来建立的,而 exponential diffusion kernel
则仅由图结构来建立。representation
有不同的维度: kernel matrix
,而 kernel
的定义。其中 K-hop
邻域。DCNN
模型建立在扩散核 diffusion kernel
的思想上:基于两个节点之间的所有路径来衡量两个节点的邻近关系,其中路径越短权重越高。
术语 “扩散卷积” 表明网络的三个思想:特征学习feature learning
、参数共享、不变性。
DCNN
的核心是抽取图结构数据的特征。DCNN
也用到参数共享,其中共享是发生在扩散搜索深度上diffusion search depth
,而不是CNN
的网格位置上。DCNN
关于节点索引不变,即两个同构输入图的扩散卷积的 representation
将是相同的。和CNN
不同,DCNN
没有池化操作。
考虑我们有
degree
矩阵,其中 定义
令
定义扩散卷积为:
其中:k-hop
;
因此节点 representation
是对图
以张量形式表示为:
其中:
representation
张量。可以看到,模型只有 DCNN
可以应用到另一个图。
这里的核心是
,它定义了指定路径深度、指定维度的权重。而节点的聚合权重是由 阶转移概率矩阵来决定。
DCNN
可以用于节点分类或者图分类。
节点分类:一旦得到 dense
层和 softmax
输出层来进行节点分类。
图分类:如果将图 graph-level
的 representation
:
其中: 1
的行向量;representation
张量。
一旦得到 dense
层和 softmax
输出层来进行图分类。
注意:hop
的 representation
,在接入 dense
层之前可以把这 representation
拼接或者相加从而得到 final representation
。
对于没有节点特征的图,可以人工构造节点特征:
1.0
的 bias feature
。pagerank
值、节点degree
等。DCNN
局限性:
可扩展性scalability
:DCNN
被实现为对稠密张量的一系列运算。存储 out-of-memory:OOM
错误。
可以通过随机游走来近似
阶转移概率矩阵从而降低计算复杂度和内存需求。
局部性locality
:DCNN
旨在捕获图结构数据中的局部行为。我们是从每个节点开始的、最高 K
阶的扩散过程来构建representation
,因此可能无法对长程依赖或者其它非局部行为进行编码。
DCNN
的训练:通过 mini-batch
随机梯度下降来学习。
可以证明:如果两个图 diffusion-convolutional representation
是相同的;如果两个图 diffusion-convolutional representation
是不同的。
证明见原始论文。
实验配置:
使用 AdaGrad
算法进行梯度提升,学习率为 0.05
。
从均值为0
、方差为 0.01
的正态分布随机采样来初始化所有权重。
选择双曲正切 tanh
函数作为非线性激活函数
选择多分类 hinge loss
作为损失函数。假设一共
其中
数据集:Cora,Pubmed
论文引用数据集,每个节点代表一篇论文,边代表论文之间的引用关系,标签为论文的主题subject
。这里我们将引文网络视为无向图。
Cora
数据集包含 2708
篇论文、5429
条边。每篇论文都分配一个标签,标签来自 7
个可能的机器学习主题。每篇论文都由一个向量表示,向量的每一位对应于是否存在从词典中抽取的 1433
个术语是否存在。Pubmed
数据集包含关于糖尿病的 19717
篇论文、44338
条边。论文被分配到三个类别之一。每篇论文都由一个 TFIDF
向量来表示,其中词典大小为 500
(即论文的特征向量维度为 500
)。这里集合
我们报告了测试集分类准确率以及 micro-F1
和 macro-F1
,每个指标为多次实验计算得到的均值。
我们还提供了 CORA
和 Pubmed
数据集的 learning curve
,其中验证集和测试集分别包含 10%
的节点,训练集包含剩余节点的 10% ~ 100%
。
baseline
方法:
l1logistic
和 l2logistic
:分别代表 L1
正则化的逻辑回归、L2
正则化的逻辑回归。逻辑回归模型的输入仅仅是节点的特征(并未使用图结构),并使用验证集对正则化参数进行调优。KED
和 KLED
:分别代表图上的 exponential diffusion kernel
和 Laplacian exponential diffusion kernel
。这些 kernel model
将图结构作为输入(并未使用节点特征)。CRF-LBP
:表示使用循环信念传播loopy belief propagation:LBP
进行推断的、部分观测partially-observed
的条件随机场conditional random field:CRF
。该模型的结果来自前人论文的实验结果。下表给出了实验结果,可以看到:DCNN
(K=2
)提供了最佳性能。
下图的 (a),(b)
给出了learning curve
,可以看到:在 Cora
数据集上,无论可用的训练数据量如何,DCNN
通常都优于baseline
方法。
图(c)
给出 hop
数量的影响。可以看到:随着 hop
数从 0-hop
逐渐增加的过程中,性能先增加然后稳定,在 3-hop
达到收敛。
数据集:我们采用 NCI1、NCI109、MUTAG、PTC、ENZYMES
等标准的图分类数据集。
NCI1、NCI109
数据集由代表化合物的 4100
和 4127
个图组成,每个图都标有它是否具有抑制一组人类肿瘤细胞系生长的能力。图中每个节点分类有 37
个(对于 NCI1
)或 38
个(对于 NCI109
) 可能的标记之一。MUTAG
数据集包含 188
个硝基化合物,被标记为芳族或非芳族化合物。节点包含7
个特征。PTC
包含 344
个化合物,被标记为是否对于大鼠致癌。节点包含 19
个特征。ENZYMES
包含 600
个蛋白质的图,每个节点包含3
个特征。输入的图集合随机拆分为训练集、验证集、测试集,每个集合包含数量相等的图,我们报告测试集的准确率、micro-F1
和 macro-F1
。每个指标为多次实验计算得到的均值。
baseline
方法:
l1logistic
和 l2logistic
:分别代表 L1
正则化的逻辑回归、L2
正则化的逻辑回归,它们仅利用节点特征。deepwl
:表示 Weisfeiler-Lehman (WL) subtree deep graph kernel
,它仅利用图结构。下表给出了实验结果,可以看到:和节点分类实验相反,没有明确的最佳模型在所有数据集、所有指标上最优。
我们还提供了 MUTAG
(图 (a)
)和 ENZYMES
(图 (b)
) 数据集的learning curve
,其中验证集和测试集都分别包含 10%
的图、训练集包含剩余图的 10% ~ 100%
。从下图 (c)
可以看到:扩大hop
数量并没有明显的好处。
这些结果表明:尽管扩散卷积可以得到节点的有效表示,但是它们在 summarize
整个图的representation
方面做得很差。可以寻找一种方法来更有效地聚合节点来改善graph-level
的 representation
,这留待以后工作。
关于对象object
、关系relation
、物理physic
的推理reasoning
是人类智能的核心,也是人工智能的主要目标。论文 《Interaction Networks for Learning about Objects, Relations and Physics》
提出了交互网络interaction network:IN
模型,该模型可以推理复杂系统中的对象如何交互、支持动态预测dynamical prediction
、以及推断系统的摘要属性abstract property
(即系统的整体属性,如物理系统的势能)。
IN
结合了三种强大的方法:结构化模型structured model
、仿真simulation
、深度学习deep learning
。
approximating
动态系统,预测复杂系统中的元素如何受到彼此的交互影响、以及系统动态影响的有效方法。IN
明确地将对关系的推理与对对象的推理分开,每个任务分配不同的模型,即:以对象为中心的推理object-centric reasoning
、以关系为中心的推理 relation-centric reasoning
。这使得 IN
可以自动地将学习泛化到任意数量的、任意顺序的对象和关系,并且还可以通过新颖的、组合的方式重新组合IN
学到的、关于对象和关系的知识。
IN
模型将关系作为显式的输入,使得模型可以针对不同的输入数据有选择地处理不同的潜在交互,而不必被迫考虑每种可能的交互,也不必由固定的架构fixed architecture
施加特定的交互。
论文评估了IN
在推理几个物理领域的能力:n
体问题n-body problem
、刚体碰撞问题rigid-body collision
、非刚体动力学问题non-rigid dynamics
。实验结果表明:可以训练IN
模型从而精确模拟数千个 time step
上数十个对象的物理轨迹。
IN
是第一个通用的、可学习的物理引擎,并且是强大的通用框架,可用于在各种复杂的现实世界领域中进行对象和关系的推理。
为描述我们的模型,我们以物理系统的推理为例(如下图所示),并从简单的模型构建完整的interaction network:IN
。
为了预测单个对象的动力学dynamics
,可以使用对象为中心的函数object-centric function
如果两个或者多个对象由相同的动力学方程控制,那么
但是,如果对象之间彼此交互,那么 sender
receiver
如下图所示,一个固定的物体、一个自由移动的质点通过弹簧连接,则固定物体(sender
)通过弹簧影响自由质点(receiver
)的动力学。
可以通过以关系为中心的函数relation-centric function
effect
上面的公式仅考虑两个对象以及它们之间关系的简单系统。通过将对象和关系表示为图
我们假设一个带属性的、有向的多图multigraph
rigid interaction
、磁性作用magnetic interaction
。
external effect
sender
对象 receiver
对象 basic IN
模型定义为:
其中:
marshalling function
,它将对象及其它们之间的关系重排为三元组向量:
其中 ||
表示向量拼接。
所有三元组构成关系矩阵
relational model
,它通过在每条边 interaction effect
所有关系的交互效应组成交互效应矩阵
聚合函数 receiver
对象 receiver
的交互效应
所有对象模型的输入为对象模型输入矩阵
object model
,它通过在每个对象
所有对象模型的输出为预测结果矩阵
这个基础的 IN
可以预测动态系统中状态的演变。对于物理仿真,
还可以使用其它组件来扩展 IN
,从而对系统进行摘要推断abstract inference
。例如,不是将 IN
预测系统的整体势能从而探索这种变体。
IN
分别对每个 commutative
和关联的associative
。使用sum
操作可以满足这个要求,但是除法操作不行。
IN
模型的通用定义和函数、算法的选择无关,这里我们描述了一种易于学习的实现,该实现能够对具有非线性关系和动态的复杂系统进行推理。
定义 receiver
对象的 one-hot
索引;定义 sender
对象的 one-hot
索引。定义
根据定义有:
即,每个关系的三元组由
receiver
状态、sender
状态、关系属性而组成。
对 MLP
)从而构成了交互效应矩阵
receiver
对象 receiver
的交互效应
对 MLP
)从而得到输出矩阵
为了推断系统的摘要属性,我们首先在
然后将 MLP
)的输入,然后返回一个向量 abstract
的、全局的属性。
训练 IN
需要在
由于 CNN
,由于 CNN
的参数共享使得 CNN
非常高效。
CNN
将局部邻域的像素视为相关的交互实体,每个像素实际上是 receiver
对象、相邻像素是 sender
对象。卷积算子类似于 skip connection
大体上类似于 IN
将
我们探索了两种类型的物理推理任务:预测系统的未来状态、估计系统的 abstract
属性(尤其是势能)。
我们在三个复杂的物理领域中进行实验:
n
体系统 n-body system
:所有
6
个 body
的训练集上进行的,但是测试时我们分别测试了 3-body
、6-body
、12-body
。弹跳球bouncing ball
:固定盒子中的球,其中移动的球可能会相互碰撞,也可能和固定的墙壁碰撞。墙被表示为对象,其形状属性为一个矩形,inverse-mass
为零(质量无穷大)。一共有
1%
的时间发生碰撞,其它所有时间都遵循直线运动。因此,该模型必须了解:尽管两个对象之间存在刚性关系,但是仅在它们接触时才存在有意义的、碰撞的相互作用。shape
、质量等,以及恢复系数restitution coefficiency
(关系的一种属性)。6
个球的盒子的训练集上进行的,其中盒子有四种不同尺寸。但是测试时我们分别测试了 3
个球、6
个球、9
个球。线条 string
:由带质量的线条(通过弹簧连接的、带重量的质点)和位于线条下方静态的、刚性的圆组成。线条上的
15
个质点的线条上进行的。但是测试时我们分别测试了 5
个质点的线条、15
个质点的线条、30
个质点的线条。我们使用物理引擎模拟了这些系统对象的 2D
轨迹,并记录它们的状态序列
prediction experiment
的目标是输出对象在随后 time step
的速度。energy estimation experiment
的目标是当前time step
的势能。我们还为 prediction experiment
生成了包含未来多个时间步的 rollout
版本,从而评估模型在创建视觉的真实的仿真visually realistic simulation
模拟时的有效性。此时,时刻 panel
,分别代表三个视频帧,每帧代表 1000
个 rollout step
。
前两列表示n
体系统的真实情况和模型预测、中间两列表示弹跳球的真实情况和模拟预测、最后两列表示线条的真实情况和模拟预测。
上方的 pannel
表示对系统进行训练的结果、中间和底部的 pannel
表示模型对于不同大小、结构的系统的泛化:
n
体系统,训练针对 6-body
、泛化针对 3-body,12-body
。6-ball
、泛化针对 3-ball,12-ball
。15
个质点且固定线条的一端、泛化针对 20
个质点且固定线条的 0
个末端或 2
个末端。训练集:每个训练、验证、测试数据集都是通过在 1000
个 time step
上仿真 2000
个场景,并随机采样 100万
、200k
、200k
个单步的 (输入, 目标)
的 pair
对组成。我们报告模型在测试集的性能。
模型训练 2000
个 epoch
,在每个 epoch
对数据进行随机混洗。
我们使用mini-batch
随机梯度下降,batch size = 100
,并且数据分布保持平衡使得对象之间有相似的目标统计分布。
我们尝试在训练的初始阶段,将少量高斯噪声添加到20%
数据的输入位置、速度,然后在 epoch
的 50~250
期间降低到 0%
。噪音的标准差是验证集每个对象相应位置、速度标准差的 0.05
倍。
它使得模型能够体验物理上不可能由物理引擎生成的状态,并学会将其投影回附近的可能的状态。
我们报告的误差结果并没有看出有噪音、无噪音结果的明显差异,但是经过噪音训练的模型的 rollout
在视觉上更逼真,并且静态对象在很多step
上的漂移 drift
也较小。
模型架构:
MLP
,我们通过对隐层维度、层数进行网格搜索从而选择最佳的模型结构。MSE
。baseline
:很少有文献可以和我们的模型进行比较。我们考虑几种 baseline
:
baseline
:输出速度和输入速度相同。MLP
的 baseline
:具有两层的 300
维隐层,将所有输入数据展平为向量从而作为输入。IN
的变体:将交互效应 实验结果:
prediction experiment
:实验结果表明,IN
可以在训练后非常准确地预测下一步动态,其测试误差要比 baseline
低几个量级。每个物理领域的动力学主要取决于对象之间的交互,因此 IN
能够学习利用这些关系进行预测。
IN
变体,其执行方式和效果与恒定速度的baseline
相似。MLP
理论上可以学习对象之间的交互,但是它不会受益于关系和对象之间的共享学习,而是被迫为每个对象并行地学习交互。energy estimation experiment
:实验结果表明,IN
的准确性要高得多。IN
总体上学习了重力势能和弹簧势能函数,并将它们应用于各自物理领域的关系中。