Press "Enter" to skip to content

GCN in 2018:2018年顶会论文中的图卷积神经网络的理论与应用

GCN in 2018:2018年顶会论文中的图卷积神经网络的理论与应用

本文作者:陈俊华,来自中国人民大学大数据管理与分析方法研究北京市重点实验室,学术型硕士研究生。研究方向为Network Embedding,Tag Recommendation等。

引言

图卷积神经网络(GCN),是Thomas Kpif于2017年在Semi-supervised Classification with Graph Convolutional Networks一文中提出的针对Graph Embedding领域新的 end-to-end 学习方法。利用滤波器(filter)抽取出图中节点及其邻域的高维特征,发现节点之间的高阶相似性。本文将介绍2018年在GCN工作上的2篇顶会论文,分别着重于理论和应用。

一、Large-Scale Learnable Graph Convolutional Networks

会议:KDD 2018

1.1 论文核心

图中节点的邻节点数目是不确定的,邻节点之间也没有任何顺序可言。这2点对GCN提出了很大的挑战。该文提出的LGCNs模型能够基于数值排序的方法自动选择固定数目的邻居节点作为GCN的输入特征,从而解决了上述2个难点并使用常规的卷积操作来进行图编码,并使用子图训练方法来使LGCNs能够适用于大图(large-scale graphs)训练。

1.2 模型方法

该文中GCN的分层传播规则为:

\tilde{X}_{l} = g(X_l,A,k),

X_{l+1}=c(\tilde{X}_l) ,

A 代表邻接矩阵(adjacency matrix),g(\cdot) 代表执行k最大节点选择(k-largest node selection)以将通用图转换为网格状结构的数据的操作, c( \cdot) 表示常规的1-D CNN卷积操作用以将邻居信息整合为新的特征向量。

g( \cdot) :在第 l 层,给定一个节点 i 及其所有的 n  个邻接节点。我们得到一个 n \times C 的特征矩阵 M_l^i , C  为特征向量的维度。假定 n \geq k (若小于则用0补齐即可),对于每列,我们对 n 个值进行排名并选择 k 个最大值。这样我们就可以得到一个 k \times C 的输出矩阵。再将中心节点 i的特征向量置于第一行,我们就得到新的输入矩阵 \tilde{X} \in \mathbb{R}^{(k+1) \times C} 。该操作利用实数中的自然排序信息并迫使每个节点具有固定数量的有序邻居。

c( \cdot) :卷积操作将 \tilde{X}_l 作为input,输出为一个 N \times D 的矩阵, c( \cdot ) 将空间大小从 (k+1)减小到1。

g(\cdot) 和 c(\cdot) 的操作在该文中以图形的形式表示了出来:

An illustration of a learnable graph convolutional layer (LGCL)

Sub-Graph Training on Large-Scale Data

给定一个图表,我们首先对一些初始节点进行采样。 从它们开始,我们使用广度优先搜索(BFS)算法迭代地将相邻节点扩展到子图中。

Sub-Graph Training on Large-Scale Data

1.3 实验

数据集:

Dataset

实验结果:

二、Semi-supervised User Geolocation via Graph Convolutional Networks

会议:ACL 2018

2.1 论文核心

本文解决的问题是社交媒体用户的地理位置定位问题。位置定位常常依赖于用户的IP地址,WIFI使用足迹以及GPS信息。但是第三方的服务软件通常是很难拿到这样的信息,所以他们基本只能依赖于地理定位的公共信息如推文和社交关系。这些信息繁多,噪声大,给定位造成很大困难。因此本文采用GCN配上一种“highway gates”机制来进行信息过滤,利用少量的有明确地理位置信息的监督样本,学习如何海量文本和社交关系中提取位置信息。

2.2 模型方法

对于每个节点,传统GCN的分层传播规则为:

GCN传统分层传播规则

各个参数的定义请具体参考引言中的论文。

该文在这个规则的基础上,加入了”highway gates”的过滤机制,解释为:将邻域信息中的噪声信息过滤,达到控制应该将多少邻域信息传递给节点的所需平衡。具体机制表示如下:

Highway GCN

W_t^l,b_t^l 是”highway gates”的权重和偏置。T(\vec h^{l}) 即为GCN中输出层 \vec h^{l+1} 的门系数,这样最终的输出层 \vec h^{l+1} 就是GCN的输出层,输入层的加权和。

2.3 实验

数据集:

三个现有的Twitter用户地理位置数据集:GEOTEXT、TWITTER-US、TWITTER-WORLD。

Baseline:

GCN-LP、MLP+TXT+NET

实验结果:

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注