GNN：抽象数据类型，图（1）
文章来自微信公众号“科文路”，欢迎关注、互动。转载须注明出处。
图神经网络（GNN）是用于处理可以表示为图的数据的一类人工神经网络。本文为图神经网络系列文章第 1 期，介绍作为抽象数据类型的图，怎么去“抽象”。
相信学过数据结构或者离散数学相关课程的朋友不会陌生“图”这个概念，今天一起来复习一下。
为了消除歧义，最好熟练记下英文术语。
图，基本概念
在计算机科学中，图是一种抽象数据类型（ADT，abstract data type），旨在实现数学里的图论领域中无向图和有向图的概念。
上面就是一个“抽象”的图，其中，
- 蓝色圆圈为 vertex（node，节点/顶点），简记为 $V$
- 这里注意 vertex 的复数形式是 vertices
- 黑色连线为 edge（link，边）
- 如果带箭头，则为 directed（有向），如图，简记为 $E$
- 不带箭头，则为 undirected（无向）
- 整幅图，简记为 $U$
- 为 GNN 引入的概念，表示这幅图的整体信息
也就是说，图数据结构就是一组有限的顶点和边的集合。那 GNN 中的研究对象，一个图，就可以记作 $G(V,E,U)$。
怎么理解“抽象”
这里注意，既然是抽象数据类型，那么图的组成部分携带的信息应该也是抽象出来的。也就是说，要从任务出发，用 $(V,E,U)$ 三个变量/集合，携带所有需要的信息。
简单举个建模的例子——用上面那张图来构建一次旅行规划的基础。
1. 任务
我现在人在成都，正在考虑一个一日游，有两个方案可选，
- 去重庆玩一天返回
- 上午去宜宾，然后下午经重庆返回
2. 根据地图构建图
打开地图，根据列车信息，构建了这样一个图，
- 三个节点分别表示地点 宜宾/重庆/成都
- 三条有向边，带信息
- 宜宾->重庆，车程 1 h
- 重庆->成都，车程 1 h
- 成都->重庆，车程 1 h
- 成都->宜宾，车程 1 h
- 整个图表示一个“一日游方案”
抽象成 $G(V,E,U)$，其中，
- $V={宜宾,重庆,成都}$
- $E={E_1,E_2,E_3,E_4}$
- $E_1 = 宜宾重庆:1$
- …
- $U=”一日游方案”$
3. 哪里抽象了?
由于我的目的是根据在途时长信息制定行程，于是图上只有我想去的城市以及行程耗时。
这个地方有什么风景、中间会经过哪些站、谁将和我一起去、我在哪一天去等等这些与目的无关的信息通通都被去掉了。
最终剩下了一个只包含必要信息的数据结构，这即是“抽象”。
当然，这个“必要信息”就是“抽象”的过程。
4. 收益
看这张图，平平无奇，却抽象出了我两个方案的所有信息以及其他一些可以直接推导的信息（由于这是我拍脑袋想出来的例子,有些信息有些无厘头），
- 方案 1 总耗时 2h
- 方案 2 总耗时 3h
- 去了宜宾就得去重庆，因为没有回来的车
- 去了重庆就没有回宜宾的车
5. permutation invariant
最重要的是，假定这张图已包含了所有的与旅程规划相关的信息，那么对这个图翻转/旋转/拉伸等等，都不会改变这些所包含的信息以及推出的信息。
抽象点讲就是，只要 $G(V,E,U)$ 的内容没有变，那他包含的那些信息不会因为图被画出来的样子改变。
这些信息通过“图”体现出一个非常重要的特性，permutation invariant，也叫置换不变性/排列不变性。这就是后面 GNN 的应用里，需要重点寻找的特征。
总结
本期作为 GNN 系列文章的开篇，介绍了图抽象数据类型的概念，并且使用一个简单的例子说明了如何去抽象一个现实问题。
下一期将介绍如何使用代码表示这些信息。
参考
~~
都看到这儿了，不如关注每日推送的“科文路”、互动起来~
至少点个赞再走吧~
GNN：抽象数据类型，图（1）