第1章概论
大到宇宙天体，小到微观世界，世间万物相互之间具有复杂的关系。要理解世界和自然现象，就必须对事物背后的复杂关系进行分析和研究。图（或网络）为物理、生物、社会等学科提供了一种不同于传统文本、图像的数据描述方式，通过分析研究图数据能够揭示通信系统、交通系统、人类社会系统等复杂系统背后共性的科学问题。本章阐述图的定义和主要类型，介绍图的基本属性，阐述图学习的概念、发展历程和应用，讨论图深度学习智能系统面临的安全风险以及安全可信图学习领域的研究现状与发展挑战。
1.1图结构化数据表示
图是由若干节点（顶点）及连接节点的边（链路）所构成的拓扑图形，这种图形通常用来描述事物之间的某种特定关系。其中，节点用于表示事物对象，连接两节点的边则用于表示两个事物之间的关系。一般认为，著名数学家莱昂哈德？欧拉于1736年发表的关于“柯尼斯堡七桥问题”的论文是图论领域的**篇文章。1859年，哈密顿发明了“环游世界游戏”，与此相关的则是广为人知的“哈密顿路径”图论问题。1878年，詹姆斯？西尔维斯特发表在《自然》上的一篇论文*次提出“图”这一名词，他用图来表示化学分子结构之间的关系。自此之后，图逐渐成为科学研究的重要领域之一。
当前，图是建模不同来源、不同性质数据的强大工具，它可以非常自然、高效地对各种数据资源进行抽象表示。一方面，通过图可以对“人、机、物”三元世界中的复杂网络系统直接进行抽象表示，例如社交网络、交通网络、金融网络、蛋白质网络等，从而基于图模型刻画用户-用户、站点-站点、机构-机构等关系，进而通过图挖掘完成预测**、风险控制、欺诈检测等任务。另一方面，通过图可以对各模态的数据进行转换表示。例如，基于属性图（attributed graph）对图像进行表示，其中每个节点表示属性信息，如颜色值、纹理特征、位置坐标等，链路表示空间邻近性、颜色相似性、纹理一致性等关系；基于文本属性图（text attributed graph）对文本进行表示，其中节点表示单词、短语、句子或段落，链路表示这些文本单元之间的语义关系；基于可视图（visibility graph）对时间序列数据进行表示，其中节点表示每个数据点，链路表示两个数据点之间在所有其他数据点之上的可见性。
图可以让人们高效地理解系统内在的复杂关系，因此可以推测人脑信息的本质存在形式是图结构，通过图结构进行信息表征可以直观地描述世界万物之间的关系。假设目标系统中对象之间的关系如图1.1（a）和图1.1（b）所示，对于图1.1（a）所示的邻接关系表，如果要“找出X的全部邻居节点”或者“找出全部相互邻接的三个节点”，相关任务的计算需要多次遍历此邻接关系表。相对地，对于图1.1（b）所示的图结构化数据表示，可以非常直观地“找出X的全部邻居节点”以及“找出全部相互邻接的三个节点”。因此，相对于传统数据表示方式，图结构化数据表示更具有优势。
图1.1邻接关系表和图结构化数据表示示例
1.2图的类型与形式化定义
1.2.1图的主要类型
1.有向图、无向图和简单图
在图中表示节点之间关系的边可以分为有向边和无向边。如图1.2所示，与无向图相比，有向图的边使用箭头表示两个节点之间的方向关系，信息朝着箭头所指的方向传递。另外，若图中任意一对节点之间至多只有一条边相连且各个节点没有自环，则称该图为简单图，否则称为多重图。
图1.2无向图和有向图示例
2.有权图和无权图
在实际生活中，事物之间关系的重要性往往是不完全相同的。例如，人际关系存在亲密与疏远之分，连通关系存在主干与旁路之分。如果只将这些关系简单地映射到图数据中，不包括关系的亲疏性，形成的表征数据则会丢失重要信息。因此，通过带权重的边来表示事物之间关系的具体含义是非常有意义的。如果图中任意一对节点之间的边都有权重值，则称该图为有权图；反之，如果图中所有边的地位相同，则称该图为无权图。
3.同构图、异构图和属性图
同构图指图中的节点类型和关系类型都仅有一种。假设有两个简单图和，当且仅当存在一个将图的节点映射到图的节点且一一对应的，使得图中任意两个节点和相连接，均等价于图中对应的两个节点和相连接，则图G和图H是同构的。为了更好地理解同构图的含义，本书给出了表1.1作为参考。
表1.1同构图的映射关系
图G 图H 从图G到图H的映射同构
异构图和同构图恰好相反，异构图是指图中的节点类型或关系类型多于一种。在现实场景中，通常研究的复杂系统所包含的对象以及对象与对象之间的关系是具有多种类型的，因此异构图能够更准确地表征复杂系统。
相较于同构图和异构图，属性图给图增加了额外的属性信息，包括节点标签（label）、节点特征（feature）等。属性图是一种*常见的工业级图的表示方式，能够广泛应用于多种业务场景下的数据表达。
1.2.2图的形式化定义
图可以形式化地定义为一个二元组，其中是节点（或顶点）集合，是中节点组成的某些无序对的集合，称为边集。
在计算机科学中，图可以使用多种不同的方法进行表示，采用何种表示方法取决于图的类型、规模和需要解决的问题。常见的表示方法有邻接矩阵、邻接关系表、关联矩阵、三元组等，本节将主要介绍邻接矩阵这种表示方式。
邻接矩阵是一种矩阵形式，用于表示图中不同节点之间的相邻关系。它主要用于描述图的拓扑结构，通常被用来表示无向图和有向图。
1.无向图的邻接矩阵
设是无向简单图，令
（1.1）
则称为的邻接矩阵，记作，简记。
2.有向图的邻接矩阵
设是有向图，令
（1.2）
则称为的邻接矩阵，记作，简记。
在算法中使用邻接矩阵时，由于存储稀疏图会造成大量的内存浪费，一般只存储稠密图。
1.3图的基本属性
与传统的文本、图像数据不同，图数据不具有天然的语义性，人类无法直接理解图数据。因此，为了描述不同的图数据、更好地分析和利用图数据，研究人员提出了用于刻画图数据特征的多种不同特征指标。本节将介绍图的基本特征指标，包括节点度与度分布、连通性、直径、聚类系数等。对这些指标的认识，可为图数据的建模和分析提供坚实的基础。在后续章节中，本书将借助这些基本特征指标，深入探讨图数据的建模和学习方法。
1.3.1节点度与度分布
在网络科学和图论等学科中，节点度与度分布是研究图的重要概念，它们提供了洞察图结构和性质的有用工具。本小节将深入探讨节点度与度分布的定义、重要性以及其与实际应用的关系。
1.节点度
节点度是指与该节点直接相连的边的数量。在无向图中，度表示节点的连接数量；而在有向图中，度分为入度（指向该节点的边的数量）和出度（由该节点引出的边的数量）。无向图节点的度可以用表示，简记为，有向图的入度记为，出度记为。
2.度分布
度分布描述在整个图中不同度的节点的数量。它是一个概率分布，通常表示为，其中是节点的度。度分布可以是离散的或连续的，这具体取决于图的类型。度分布的形状对理解图的拓扑结构和特性非常重要。
（1）度分布可以帮助理解图的整体结构。不同图类型具有不同的度分布特征。例如，随机图的度分布通常近似于泊松分布，而复杂网络（如社交网络或互联网）的度分布通常呈幂律分布。通过分析度分布，可以识别图的结构类型，例如是否为小世界网络、无标度网络或规则网络。
（2）度分布有助于识别图中的关键节点。在许多图数据中，少数高度连接的节点在信息传播、传染病传播、信息传输等方面起着重要作用。通过对度分布的分析，可以确定这些关键节点，以更好地理解图的动力学特性。
（3）度分布与图的连通性密切相关。当图中存在大量高度连接的节点时，图通常更容易传播信息。这在社交网络、互联网和通信网络中具有重要意义。高度连接的节点可以充当信息传播的关键媒介，信息通过它们可以快速传播到整个网络。
（4）度分布还与图的脆弱性和鲁棒性相关。恶意攻击和故障可能专门瞄准高度连接的节点，从而对复杂系统的稳定性造成严重威胁。通过对度分布的分析，可以帮助识别这些易受攻击的节点，从而通过采取保护措施来增强复杂系统的鲁棒性。
1.3.2连通性
连通性用于描述图中节点之间的连接性和可达性，有助于理解图的结构特征。下面将介绍图的连通性的相关概念。
1.连通图
在无向图中，如果包含一条从到的路径，则两个节点和被称为是连通的，记作。若和之间存在一条长度为1的路径，则称和相邻。如果图中的每一对节点都是连通的，则称该图为连通图。
在有向图中，将连通图分为弱连通图和强连通图。设为有向图，若去掉中各有向边的方向后得到的无向图是连通的，则称为弱连通图；如果对于中任意两节点、，或者到可达或者到可达，则称图为单向连通图；如果中任意两节点之间都相互可达，则称为强连通图。
2.连通分量
连通分量是无向图的极大连通子图，每个节点和每条边都仅属于一个连通分量。当一个图有且仅有一个连通分量时，此图就是连通的。
1.3.3直径
直径为图中任意两个节点之间的“*长*短路径”（图的*长测地线）的长度，其中为图距离。简言之，一个图的直径是从一个节点到另一个节点而必须遍历的*大的节点数。因此，图的直径等于图的距离矩阵中所有值的*大值。用数学语言描述即为：定义图的一个节点到其他节点的*远距离，从而图的半径定义为。所有满足的节点都称为的中心。显然，一个图的直径可以定义为。
直径作为图数据的一个基本属性，在社交网络中，可以表示为在*坏情况下信息到达网络中每个人的速度；在科学合作网络中，高直径可能表明有一些研究小组没有非常紧密地合作；在互联网路由网络中，直径可以揭示网络中任意两台机器之间在*坏情况下的响应时间。
1.3.4聚类系数
聚类系数是用来描述图中的节点集结成团的程度的指标。具体地，聚类系数表示一个点的邻接点之间相互连接的紧密程度。假设图中的节点通过条边与其他节点相连接，是节点的邻居节点数目。如果个节点之间互相连接，它们之间存在条边，而这个节点之间实际存在的边数与总的可能存在的边数之比就是节点的聚类系数[1]。
（1.3）
一个图的聚类系数就是图中各个节点的聚类系数的平均值，即
（1.4）
显然有。在全连通图中，聚类系数取值等于1，通常情况下小于1。
1.3.5同配系数
同配系数是用于衡量图中节点与其邻居节点之间连接的趋势或倾向的指标。它用来描述图中节点之间的连接是否更倾向于具有相似特征的节点。对于一条给定的边，两个端点的度值并不总是*立的。这种节点度之间的相关性可以通过条件概率来衡量，即一个度为的节点在连接度为时节点的概率。其数学定义式为
（1.5）
展开
