Notes-Representation Learning on Graphs: Methods and Applications

Representation Learning on Graphs: Methods and Applications.


作者:William L. Hamilton, Rex Ying

论文地址: https://arxiv.org/pdf/1709.05584.pdfhe

摘要

在不同图(Graph)上的机器学习是一项重要且无处不在的任务,其应用范围从药物设计到社交网络中的好友推荐。该领域的主要挑战是找到一种方法来表 示或编码图结构,以便机器学习模型可以轻松利用它。传统的机器学习方法依赖于用户定义的启发式方法来提取编码关于图的结构信息的特征(例如,度数统计或内核 函数)。然而,近年来,使用基于深度学习和非线性降维的技术,自动学习将图结构编码为低维嵌入的方法出现了激增。在这里,我们提供了关于图形表示学习领域进 展的关键概念回顾,包括基于矩阵分解的方法,基于随机游走的算法和图形卷积网络。文中回顾了嵌入单个节点的方法以及嵌入整个(子)图的方法。为此,制定了一 个统一的框架来描述这些最新的方法,并且强调了未来工作的一些重要应用和方向。

论文笔记

Introduction

对于图的机器学习,其核心问题是找到一种方法,将有关图结构的信息纳入机器学习模型。而其面临的挑战在于没有一种直接方法将高维非欧的图结构信息转换为特征向量。

传统方法用预处理方法来提取结构信息。常见的方法有:图统计信息(e.g. 度(degree)或聚类系数(clustering coefficients)),核方法(Kernel function/method),特征工程(feature engineering)。但是他们测量邻结构往往有着诸多限制。这是因为他们的方法是通用性弱(inflexible),在学习过程中不能适应,并且耗费大量时间与财力。

随着机器学习发展,网络表征学习被提出。其背后思想是通过学习将节点或整个(子)图作为点嵌入到低维向量空间 $\mathbb{R}^d$ 中。目标是优化这个映射,使嵌入空间中的几何关系反映原始图的结构。

与传统方法相比,网络表征学习将此问题视为机器学习任务本身,使用数据驱动方法来学习编码图结构的嵌入。

Notation and essential assumption

Assume:

  • 无向图 $G = (V ,\varepsilon)$ 与二值邻接矩阵 $A$
  • 节点属性的实值矩阵 $X \in \mathbb{R}^{m \times \vert V \vert}$

Goal :使用$A$和$X$中包含的信息将每个节点或子图映射到向量$z\in \mathbb{R}^d$,其中$d << \vert V\vert$。

Embedding nodes