人工智能十大数学知识 - 图论

图论（Graph Theory）在人工智能中的核心应用

图论是描述“对象关联关系”的数学工具，通过顶点（实体） 和边（关系） 构建离散结构，是AI处理非欧几里得数据（如社交网络、知识图谱、分子结构）的核心基础，也是图神经网络（GNN）、推荐系统等模型的底层框架。

1. 图的基本定义与表示（Graph Definition & Representation）

1.1 图的核心概念与分类

图的通用定义

公式：
无向图 G=(V,E)G = (V, E)G=(V,E)，有向图 D=(V,A)D = (V, A)D=(V,A)
各组件含义： V={v1,v2,...,vn}V = {v_1, v_2, ..., v_n}V={v1​,v2​,...,vn​}：顶点集（n=∣V∣n = |V|n=∣V∣ 为顶点数，AI中对应“实体”，如用户、单词、分子原子）；E={e1,e2,...,em}E = {e_1, e_2, ..., e_m}E={e1​,e2​,...,em​}：无向边集（边无方向，e=(u,v)e = (u, v)e=(u,v) 表示 uuu 与 vvv 关联，如社交网络“好友关系”）；A={a1,a2,...,am}A = {a_1, a_2, ..., a_m}A={a1​,a2​,...,am​}：有向边集（边有方向，a=<u,v>a = <u, v>a=<u,v> 表示从 uuu 指向 vvv，如网页“超链接”、因果关系）。

常见图的分类

分类维度	类型	核心特征	AI应用场景示例
边的方向	无向图	(u,v)=(v,u)(u, v) = (v, u)(u,v)=(v,u)，边无方向	图像像素相邻关系、社交好友关系
	有向图	<u,v>≠<v,u><u, v> eq <v, u><u,v>=<v,u>，边有方向	网页超链接、食物链、任务依赖关系
边的权重	无权图	边无权重（默认权重为1）	简单好友关系、无权重的知识图谱关系
	加权图	边关联权重 w(e)∈Rw(e) in mathbb{R}w(e)∈R，记为 G=(V,E,W)G = (V, E, W)G=(V,E,W)（WWW 为权重矩阵）	用户互动频率（权重=互动次数）、词相似度
特殊结构	有向无环图（DAG）	无循环的有向图	神经网络计算图、任务调度依赖
	二分图	V=V1∪V2V = V_1 cup V_2V=V1​∪V2​（V1∩V2=∅V_1 cap V_2 = emptysetV1​∩V2​=∅），边仅存在于 V1−V2V_1-V_2V1​−V2​ 间	用户-物品推荐系统、学生-课程分配
	完全图	任意两顶点间均有边（无向完全图边数 m=n(n−1)2m = frac{n(n-1)}{2}m=2n(n−1)​）	全连接神经网络层内连接、全连通传感器网络

1.2 图的表示方法（AI核心操作）

1. 邻接矩阵（Adjacency Matrix）

公式：设图 G=(V,E)G = (V, E)G=(V,E) 有 nnn 个顶点，邻接矩阵 A∈{0,1}n×nA in {0, 1}^{n imes n}A∈{0,1}n×n（无权图）定义为：

核心特性：

无向图的邻接矩阵对称（AT=AA^T = AAT=A），有向图不一定；空间复杂度 O(n2)O(n^2)O(n2)，适合稠密图（边数 m≈n2m approx n^2m≈n2）。

AI应用：

图神经网络（GNN）核心输入：如 GCN 的层间传播公式 H(l+1)=σ(D~−1/2A~D~−1/2H(l)W(l))H^{(l+1)} = sigma( ilde{D}^{-1/2} ilde{A} ilde{D}^{-1/2}H^{(l)}W^{(l)})H(l+1)=σ(D~−1/2A~D~−1/2H(l)W(l))，A~ ilde{A}A~ 为带自环的邻接矩阵；小规模图的快速运算：如邻接矩阵乘法可计算“两跳邻居”（Aij2A^2_{ij}Aij2​ 表示 viv_ivi​ 到 vjv_jvj​ 的两跳路径数）。

2. 度与度矩阵（Degree & Degree Matrix）

节点度：

无向图：节点 viv_ivi​ 的度 di=∑j=1nAijd_i = sum_{j=1}^n A_{ij}di​=∑j=1n​Aij​（关联边数）；有向图：入度 di−=∑j=1nAjid_i^- = sum_{j=1}^n A_{ji}di−​=∑j=1n​Aji​（指向 viv_ivi​ 的边数），出度 di+=∑j=1nAijd_i^+ = sum_{j=1}^n A_{ij}di+​=∑j=1n​Aij​（从 viv_ivi​ 出发的边数）。

度矩阵：对角矩阵 D∈Rn×nD in mathbb{R}^{n imes n}D∈Rn×n，公式：
D=diag(d1,d2,...,dn)D = ext{diag}(d_1, d_2, ..., d_n)D=diag(d1​,d2​,...,dn​)（仅对角元素为节点度，其余为0）。

AI应用：

GNN中的特征归一化：如 GCN 用 D~−1/2 ilde{D}^{-1/2}D~−1/2 平衡不同度数节点的特征贡献，避免高度数节点主导聚合结果；节点重要性初判：社交网络中高度数节点可能是“意见领袖”，优先分析其传播影响力。

3. 邻接表（Adjacency List）

定义：用“数组+链表”存储，数组 adjadjadj 索引对应顶点，链表存储该顶点的邻接顶点：

无向图：adj[vi]=[vj∣(vi,vj)∈E]adj[v_i] = [v_j mid (v_i, v_j) in E]adj[vi​]=[vj​∣(vi​,vj​)∈E]；加权图：adj[vi]=[(vj,wij)∣(vi,vj)∈E]adj[v_i] = [(v_j, w_{ij}) mid (v_i, v_j) in E]adj[vi​]=[(vj​,wij​)∣(vi​,vj​)∈E]（同时存储邻接顶点及边权重）。

核心特性：

空间复杂度 O(n+m)O(n + m)O(n+m)，适合稀疏图（AI中大规模图多为稀疏图，如社交网络 m≪n2m ll n^2m≪n2）；高效遍历：遍历某顶点的所有邻居仅需访问对应链表，无需遍历整行矩阵。

AI应用：

大规模图的遍历算法：如 BFS、DFS 对社交网络（nnn 百万级）的高效节点访问；推荐系统存储：用户-物品二分图用邻接表存储“用户购买的物品”或“物品被购买的用户”，节省内存。

2. 图的基本性质与定理（Graph Properties & Theorems）

2.1 顶点度数与握手定理

握手定理（Handshaking Lemma）

无向图定理：所有顶点的度数和等于边数的2倍，公式：
∑v∈Vd(v)=2msum_{v in V} d(v) = 2m∑v∈V​d(v)=2m
（每边贡献2个度数，分别属于两个顶点）。

有向图推论：所有顶点的入度和等于出度和，且等于边数，公式：
∑v∈Vd−(v)=∑v∈Vd+(v)=msum_{v in V} d^-(v) = sum_{v in V} d^+(v) = m∑v∈V​d−(v)=∑v∈V​d+(v)=m。

AI应用：

图数据校验：如社交网络数据中，若度数和为奇数，说明数据存在统计错误（如漏记/多记边）；异常节点检测：度数远高于均值的节点可能是“超级节点”（如机器人账号），度数为0的节点是孤立节点（可剔除以简化模型）。

2.2 路径、回路与连通性

核心概念定义

路径：顶点序列 v1→v2→...→vkv_1 o v_2 o ... o v_kv1​→v2​→...→vk​，相邻顶点间有边，长度为 k−1k-1k−1（边数）；
简单路径：顶点不重复的路径（如 v1→v2→v3v_1 o v_2 o v_3v1​→v2​→v3​）。

回路：起点=终点的路径（如 v1→v2→v1v_1 o v_2 o v_1v1​→v2​→v1​）；
简单回路：除起点/终点外顶点不重复的回路。

连通性：

无向图：任意两顶点间有路径则为连通图，否则为非连通图，其极大连通子图称为连通分量；有向图：任意两顶点间有双向路径则为强连通图，忽略边方向后连通则为弱连通图。

AI应用：

社区发现：社交网络中，连通分量对应“用户社群”，强连通分量对应“核心互动群体”；知识图谱补全：实体间的路径长度可衡量语义关联强度（短路径关联更紧密）。

2.3 二分图判定定理

定理：一个无向图是二分图，当且仅当它不包含长度为奇数的回路（奇环）。

判定方法：染色法（用两种颜色标记顶点，相邻顶点颜色不同，无冲突则为二分图）。

AI应用：

用户-物品推荐：将“用户-物品”建模为二分图，保证无“用户-用户”或“物品-物品”直接边，简化推荐算法（如基于二分图匹配的协同过滤）；图像标注：将“图像区域-标签”建模为二分图，通过二分图匹配优化标签分配（避免同一区域被标注多个冲突标签）。

2.4 DAG的拓扑排序定理

定理：一个有向图存在拓扑排序，当且仅当它是有向无环图（DAG）。

拓扑排序：顶点的线性序列 v1,v2,...,vnv_1, v_2, ..., v_nv1​,v2​,...,vn​，对任意边 <vi,vj><v_i, v_j><vi​,vj​>，viv_ivi​ 在序列中早于 vjv_jvj​（满足“先后依赖”）。

AI应用：

深度学习框架计算：TensorFlow/PyTorch 将模型计算流程建模为DAG，拓扑排序确定算子执行顺序（避免依赖错误）；任务调度：AI workflow 中，基于拓扑排序规划“数据预处理→模型训练→结果评估”的执行顺序。

2.5 其他关键定理

定理名称	核心结论	AI应用场景
哈密顿回路定理	判断图是否存在“包含所有顶点的回路”是NP完全问题，需近似求解	旅行商问题（TSP）路径优化、物流配送路线规划
四色定理	任何平面图可用最多4种颜色着色，使相邻顶点颜色不同	地图区域着色、芯片设计中的寄存器分配
聚类系数定理	聚类系数 C=3×三角形数量连通三元组数量C = frac{3 imes ext{三角形数量}}{ ext{连通三元组数量}}C=连通三元组数量3×三角形数量​，衡量图的聚集程度	社交网络社群紧密性分析、蛋白质相互作用网络模块识别

3. 图的核心算法（Core Graph Algorithms）

3.1 图的遍历算法

1. 广度优先搜索（BFS）

核心思想：按“层次”遍历图，先访问起点的所有邻居，再访问邻居的邻居（保证无权图最短路径）。算法步骤： 初始化：队列 Q=[v0]Q = [v_0]Q=[v0​]，访问标记 visited={v0} ext{visited} = {v_0}visited={v0​}；循环：出队顶点 vvv，遍历其未访问的邻居 uuu，标记 visited ext{visited}visited 并入队；终止：队列为空，遍历完成。 时间复杂度：O(n+m)O(n + m)O(n+m)（每个顶点和边各访问一次）。AI应用： 无权图最短路径：如社交网络中“用户A到用户B的最短好友链”；图的连通分量检测：遍历过程中未访问的顶点对应新连通分量。

2. 深度优先搜索（DFS）

核心思想：“深度优先”探索，尽可能沿一条路径遍历至终点，再回溯探索其他分支。算法实现：递归或栈（避免递归栈溢出）。时间复杂度：O(n+m)O(n + m)O(n+m)。AI应用： 拓扑排序（针对DAG）：DFS后按顶点完成时间逆序排列，得到拓扑序列；强连通分量检测（Tarjan算法、Kosaraju算法）：如网页链接图中识别相互引用的网页集群。

3.2 最短路径算法

1. Dijkstra算法（单源最短路径，无负权边）

核心思想：贪心策略，从起点出发，每次选择“当前距离最短的未访问顶点”，更新其邻接顶点的距离。关键步骤： 初始化：距离数组 dist[v]=∞ ext{dist}[v] = inftydist[v]=∞，dist[s]=0 ext{dist}[s] = 0dist[s]=0（sss 为起点），优先队列 QQQ 存入所有顶点；循环：出队距离最小的顶点 uuu，对每个邻居 vvv 执行松弛操作：dist[v]=min⁡(dist[v],dist[u]+w(u,v)) ext{dist}[v] = min( ext{dist}[v], ext{dist}[u] + w(u,v))dist[v]=min(dist[v],dist[u]+w(u,v))；终止：队列为空，dist[v] ext{dist}[v]dist[v] 即为 sss 到 vvv 的最短距离。 时间复杂度：O(mlog⁡n)O(m log n)O(mlogn)（使用优先队列）。AI应用： 自动驾驶导航：道路网络建模为加权图（权重=距离/时间），计算起点到终点的最短路径；知识图谱推理：计算实体间的最短语义路径（如“李白→唐诗→杜甫”），衡量关联强度。

2. Floyd-Warshall算法（多源最短路径，支持负权边无负环）

核心思想：动态规划，通过“中间顶点”迭代更新任意两点间的最短距离，公式：
Dij(k)=min⁡(Dij(k−1),Dik(k−1)+Dkj(k−1))D_{ij}^{(k)} = min(D_{ij}^{(k-1)}, D_{ik}^{(k-1)} + D_{kj}^{(k-1)})Dij(k)​=min(Dij(k−1)​,Dik(k−1)​+Dkj(k−1)​)
其中 Dij(k)D_{ij}^{(k)}Dij(k)​ 表示“经过顶点编号≤k”时，viv_ivi​ 到 vjv_jvj​ 的最短距离。时间复杂度：O(n3)O(n^3)O(n3)（适合小规模图，n<1000n < 1000n<1000）。AI应用： 小规模网络多节点路径规划：如局域网内设备间的通信路径优化；图数据相似度计算：任意两点的最短距离可作为相似度指标（距离越短相似度越高）。

3.3 最小生成树（MST）算法

定义

最小生成树是“包含所有顶点、无回路、边权重和最小”的子图（边数 n−1n-1n−1），用于“最小成本连接所有节点”。

1. Kruskal算法（按边排序，贪心）

核心思想：将所有边按权重从小到大排序，依次选边加入MST，若选边形成回路则跳过（用并查集判断回路）。时间复杂度：O(mlog⁡m)O(m log m)O(mlogm)（边排序主导）。

2. Prim算法（按顶点扩展，贪心）

核心思想：从任意顶点出发，每次选择“连接已选顶点集与未选顶点集的最小权重边”，加入MST，直至包含所有顶点。

时间复杂度：O(mlog⁡n)O(m log n)O(mlogn)（使用优先队列）。

AI应用：

传感器网络部署：用MST连接所有传感器，最小化布线成本；图像分割：将像素视为顶点，边权重=像素相似度，MST的“最大边切割”对应分割边界（分离不同物体）。

3.4 二分图匹配算法（匈牙利算法）

核心概念

匹配：二分图中无公共顶点的边集；最大匹配：边数最多的匹配；完美匹配：匹配边数 = ∣V1∣=∣V2∣|V_1| = |V_2|∣V1​∣=∣V2​∣（所有顶点均被匹配）。

匈牙利算法（寻找最大匹配）

核心思想：通过“增广路径”迭代扩展匹配集——增广路径是“从非匹配顶点出发，交替经过非匹配边和匹配边的路径”，翻转路径中边的匹配状态（非匹配→匹配，匹配→非匹配），可使匹配边数+1。

时间复杂度：O(nm)O(nm)O(nm)（nnn 为顶点数，mmm 为边数）。

AI应用：

推荐系统：用户-物品二分图的最大匹配，最大化“用户-物品”匹配数（提升推荐覆盖率）；人才-岗位匹配：基于“技能匹配度”（边权重）的加权二分图匹配，优化人才资源分配。

3.5 节点重要性算法（PageRank & Node2Vec）

1. PageRank算法（网页/节点重要性）

迭代公式：
PR(p)=1−dn+d∑q∈In(p)PR(q)Out(q)PR(p) = frac{1-d}{n} + d sum_{q in ext{In}(p)} frac{PR(q)}{ ext{Out}(q)}PR(p)=n1−d​+d∑q∈In(p)​Out(q)PR(q)​
各参数含义： PR(p)PR(p)PR(p)：节点 ppp 的PageRank值（重要性）；ddd：阻尼因子（通常取0.85，模拟“随机跳转”，避免无出度节点问题）；In(p) ext{In}(p)In(p)：指向 ppp 的节点集合；Out(q) ext{Out}(q)Out(q)：节点 qqq 的出边数。 AI应用： 搜索引擎排序：网页重要性计算（高PR值网页排名靠前）；社交网络核心节点识别：高PR值用户是“关键传播者”（如病毒式营销的目标用户）。

2. Node2Vec算法（图嵌入）

核心思想：通过可控随机游走生成节点序列（参数 ppp 控制“回溯倾向”，qqq 控制“探索倾向”），再用Word2Vec学习低维嵌入（保留图结构信息）。目标函数：
max⁡f∑u∈Vlog⁡P(NS(u)∣f(u))max_f sum_{u in V} log P( ext{N}_S(u) mid f(u))maxf​∑u∈V​logP(NS​(u)∣f(u))
其中 NS(u) ext{N}_S(u)NS​(u) 是节点 uuu 的随机游走邻居集，f(u)f(u)f(u) 是 uuu 的嵌入向量。AI应用： 节点分类：将嵌入向量输入分类器（如SVM），实现社交网络用户标签预测；链路预测：计算节点嵌入的相似度（如余弦相似度），预测未连接的边（如知识图谱补全）。

4. 图的中心性与谱分析（Centrality & Spectral Analysis）

4.1 中心性指标（衡量节点重要性）

中心性类型	公式（无向图）	核心含义	AI应用场景
度中心性	Cd(v)=d(v)n−1C_d(v) = frac{d(v)}{n-1}Cd​(v)=n−1d(v)​（归一化，最大度数为 n−1n-1n−1）	节点的直接关联度（邻居数量）	社交网络“粉丝数”排名、知识图谱核心实体初筛
介数中心性	Cb(v)=∑s≠v≠tσst(v)σstC_b(v) = sum_{s eq v eq t} frac{sigma_{st}(v)}{sigma_{st}}Cb​(v)=∑s=v=t​σst​σst​(v)​（σstsigma_{st}σst​为s−ts-ts−t最短路径总数，σst(v)sigma_{st}(v)σst​(v)为经过vvv的路径数）	节点在“信息传递”中的中介作用（位于多对节点的最短路径上）	传播路径关键节点识别（如谣言传播的阻断节点）
特征向量中心性	Ac=λmaxcA oldsymbol{c} = lambda_{ ext{max}} oldsymbol{c}Ac=λmax​c（coldsymbol{c}c为特征向量，λmaxlambda_{ ext{max}}λmax​为AAA的最大特征值）	节点重要性由“邻居重要性”决定（与重要节点相连的节点更重要）	PageRank算法基础、学术论文影响力评估（被高影响力论文引用）
closeness中心性	Cc(v)=n−1∑u≠vdist(v,u)C_c(v) = frac{n-1}{sum_{u eq v} ext{dist}(v, u)}Cc​(v)=∑u=v​dist(v,u)n−1​（dist(v,u) ext{dist}(v,u)dist(v,u)为v−uv-uv−u最短距离）	节点到其他所有节点的“平均距离”（距离越短，中心性越高）	应急节点选址（如医院、消防站需快速到达所有区域）

4.2 图的拉普拉斯矩阵（谱图理论核心）

1. 普通拉普拉斯矩阵（Laplacian Matrix）

公式：L=D−AL = D - AL=D−A（DDD 为度矩阵，AAA 为邻接矩阵）。核心性质： 对称半正定矩阵（所有特征值 λi≥0lambda_i geq 0λi​≥0）；最小特征值 λ0=0lambda_0 = 0λ0​=0，对应特征向量为全1向量（1TL=0oldsymbol{1}^T L = oldsymbol{0}1TL=0）；特征值个数 = 顶点数 nnn，排序 λ0≤λ1≤...≤λn−1lambda_0 leq lambda_1 leq ... leq lambda_{n-1}λ0​≤λ1​≤...≤λn−1​。

2. 归一化拉普拉斯矩阵（Normalized Laplacian）

两种常用形式：

对称归一化：Lsym=D−1/2LD−1/2=I−D−1/2AD−1/2L_{ ext{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}Lsym​=D−1/2LD−1/2=I−D−1/2AD−1/2（GCN核心矩阵）；随机游走归一化：Lrw=D−1L=I−D−1AL_{ ext{rw}} = D^{-1} L = I - D^{-1} ALrw​=D−1L=I−D−1A（随机游走相关任务）。

AI应用：

图卷积网络（GCN）：LsymL_{ ext{sym}}Lsym​ 实现邻域特征的“平滑聚合”，避免高度数节点特征被过度稀释；谱聚类：对 LLL 做特征分解，取前 kkk 个最小特征值对应的特征向量聚类（利用谱特性保留全局结构，优于传统K-Means）；图平滑性衡量：XTLX=12∑(u,v)∈E(xu−xv)2X^T L X = frac{1}{2} sum_{(u,v) in E} (x_u - x_v)^2XTLX=21​∑(u,v)∈E​(xu​−xv​)2（值越小，相邻节点特征越相似，图信号越平滑）。

4.3 图傅里叶变换（Graph Signal Processing）

定义：类比传统信号处理，将图信号（如节点特征 XXX）从“空域”转换到“频域”，公式：
正变换（空域→频域）：X^(λl)=ulTXhat{X}(lambda_l) = oldsymbol{u}_l^T XX^(λl​)=ulT​X（uloldsymbol{u}_lul​ 是 LLL 的第 lll 个特征向量，λllambda_lλl​ 为对应特征值）；
逆变换（频域→空域）：X=∑l=0n−1X^(λl)ulX = sum_{l=0}^{n-1} hat{X}(lambda_l) oldsymbol{u}_lX=∑l=0n−1​X^(λl​)ul​。核心解读： 低特征值 λllambda_lλl​ 对应“低频信号”（图信号平滑变化，反映全局趋势）；高特征值 λllambda_lλl​ 对应“高频信号”（图信号局部波动，反映异常点或细节）。 AI应用： 图信号去噪：过滤高频分量，保留低频平滑信号（如传感器网络数据去噪）；图卷积定义：频域卷积 = 信号频域值 × 滤波器频域值（GCN的频域解释）。

5. 图表示学习与神经网络（Graph Representation Learning & GNN）

5.1 图嵌入（Graph Embedding）

将图节点/边映射到低维向量空间，保留图结构和语义信息，是GNN的前置基础。

嵌入方法	核心思想	AI应用场景
DeepWalk	随机游走生成节点序列，用Word2Vec学习嵌入（保留局部结构）	社交网络节点分类、链路预测
Node2Vec	可控随机游走（参数 p/qp/qp/q 平衡BFS/DFS），兼顾局部和全局结构	知识图谱实体嵌入、分子结构表示
谱聚类嵌入	拉普拉斯矩阵特征分解，取前 kkk 个特征向量作为嵌入（保留全局结构）	非球形数据聚类（如用户行为聚类）
TransE（知识图谱）	将实体和关系映射到向量，满足 h+r=th + r = th+r=t（hhh 头实体，rrr 关系，ttt 尾实体）	知识图谱补全、语义问答系统

5.2 图神经网络（GNN）

通过“消息传递”聚合邻居特征，处理图结构数据，是当前AI图任务的核心模型。

1. 图卷积网络（GCN）

层间传播公式：
H(l+1)=σ(D~−1/2A~D~−1/2H(l)W(l))H^{(l+1)} = sigmaleft( ilde{D}^{-1/2} ilde{A} ilde{D}^{-1/2} H^{(l)} W^{(l)} ight)H(l+1)=σ(D~−1/2A~D~−1/2H(l)W(l))
各组件含义： A~=A+I ilde{A} = A + IA~=A+I：带自环的邻接矩阵（保留节点自身特征）；D~ ilde{D}D~：A~ ilde{A}A~ 对应的度矩阵；H(l)H^{(l)}H(l)：第 lll 层节点特征矩阵；W(l)W^{(l)}W(l)：可学习权重矩阵；σsigmaσ：激活函数（如ReLU）。 AI应用： 分子结构预测：将原子视为节点，化学键视为边，预测分子活性（如药物研发）；知识图谱分类：对实体特征进行卷积聚合，实现实体类型预测。

2. 图注意力网络（GAT）

核心改进：引入注意力机制，为不同邻居分配不同权重（解决GCN“平等对待所有邻居”的缺陷）。注意力系数计算： 特征线性变换：hi′=Whih_i' = W h_ihi′​=Whi​（WWW 为共享权重）；注意力分数：eij=a(Whi,Whj)e_{ij} = a(W h_i, W h_j)eij​=a(Whi​,Whj​)（aaa 为注意力函数，如多层感知机）；归一化：αij=exp⁡(LeakyReLU(eij))∑k∈N(i)exp⁡(LeakyReLU(eik))alpha_{ij} = frac{exp( ext{LeakyReLU}(e_{ij}))}{sum_{k in mathcal{N}(i)} exp( ext{LeakyReLU}(e_{ik}))}αij​=∑k∈N(i)​exp(LeakyReLU(eik​))exp(LeakyReLU(eij​))​（N(i)mathcal{N}(i)N(i) 为 iii 的邻居集）；特征聚合：hi(l+1)=σ(∑j∈N(i)αijWhj(l))h_i^{(l+1)} = sigmaleft(sum_{j in mathcal{N}(i)} alpha_{ij} W h_j^{(l)} ight)hi(l+1)​=σ(∑j∈N(i)​αij​Whj(l)​)。 AI应用： 社交网络分析：对“亲密好友”分配高注意力权重，提升用户行为预测精度；图像分割：对“语义相似的邻域像素”分配高权重，优化分割边界。

3. 图自编码器（GAE）

核心结构： 编码器：用GCN将节点特征映射为低维嵌入 Z=GCN(X,A)Z = ext{GCN}(X, A)Z=GCN(X,A)；解码器：通过内积重构邻接矩阵 A^=σ(ZZT)hat{A} = sigma(Z Z^T)A^=σ(ZZT)（预测节点间是否存在边）。 AI应用： 无监督图嵌入：无需标签，通过重构邻接矩阵学习节点嵌入；链路预测：知识图谱补全（预测实体间缺失的关系）、社交网络好友推荐。

6. 图生成模型（Graph Generation Models）

生成符合特定结构的图，用于模拟真实网络或创造新结构（如药物分子、社交网络）。

生成模型	核心思想	AI应用场景
Erdős-Rényi模型	G(n,p)G(n, p)G(n,p)：每对顶点以概率 ppp 随机连接，度分布近似泊松分布	随机网络模拟、基准测试数据集生成
Watts-Strogatz模型	从完全图开始，随机重连部分边，生成“短平均路径+高聚类系数”的小世界网络	社交网络模拟、传染病传播建模
Barabási-Albert模型	偏好连接（新节点优先连接高度数节点），度分布服从幂律（无标度网络）	互联网拓扑模拟、 citation网络生成
图生成对抗网络（GGAN）	生成器生成图结构，判别器区分“真实图”与“生成图”，对抗训练优化生成质量	药物分子生成（设计新活性分子）、场景图生成

7. AI中的典型应用总结（Typical AI Applications）

7.1 自然语言处理（NLP）

语义网络：将单词/短语视为顶点，语义关系（同义、上下位）视为边（如WordNet），用于词义消歧、文本理解；文本摘要：将句子视为顶点，句子相似度视为边，通过连通分量提取核心句子（如新闻摘要）；知识图谱问答：将知识图谱建模为图，通过最短路径或GNN聚合实体特征，生成问答结果（如“李白的代表作是什么”）。

7.2 计算机视觉（CV）

图像分割：像素视为顶点，像素相似度视为边，用谱聚类或GNN实现语义分割（如区分“车、人、道路”）；目标检测：图像区域视为顶点，区域关联（如“人-车”相邻）视为边，通过图推理优化检测框位置；视觉SLAM：环境特征点视为顶点，特征点间空间关系视为边，构建环境图用于机器人定位导航。

7.3 社交网络分析

社区发现：用谱聚类或Louvain算法（最大化模块度）识别用户社群，用于精准营销；影响力分析：基于PageRank或介数中心性，识别“关键传播节点”，用于病毒式营销或谣言阻断；异常检测：通过度数分布异常（如超级节点）或路径长度异常，识别虚假账号、垃圾邮件发送者。

7.4 其他领域

药物研发：分子结构建模为图（原子=顶点，化学键=边），用GCN预测分子活性，设计新药物；推荐系统：用户-物品建模为二分图，通过二分图匹配或Node2Vec嵌入，推荐相似物品/用户；物流优化：城市/仓库视为顶点，运输路线视为边（权重=成本），用MST或最短路径算法优化配送路线。

附录：图论核心符号总结（读音+使用场景）

符号	写法规范	读音	核心使用场景
GGG	大写G	“G”	图的总称（如无向图 G=(V,E)G=(V,E)G=(V,E)，有向图 D=(V,A)D=(V,A)D=(V,A)）
VVV	大写V	“V”	顶点集（存储图中的实体，如用户、单词）
EEE	大写E	“E”	无向边集（存储无向关系，如好友关系）
AAA	大写A	“A”	1. 有向边集；2. 邻接矩阵（描述节点连接关系，GNN核心输入）
DDD	大写D	“D”	度矩阵（对角矩阵，存储节点度数，用于GNN特征归一化）
LLL	大写L	“L”	拉普拉斯矩阵（L=D−AL=D-AL=D−A，谱图理论和GCN的核心矩阵）
LsymL_{ ext{sym}}Lsym​	大写L+下标sym	“L sym”	对称归一化拉普拉斯矩阵（GCN的核心卷积矩阵）
d(v)d(v)d(v)	小写d+顶点v	“d of v”	节点 vvv 的度数（无向图），衡量节点直接关联数
d−(v)/d+(v)d^-(v)/d^+(v)d−(v)/d+(v)	小写d±+顶点v	“d minus/plus of v”	节点 vvv 的入度/出度（有向图），如网页的入链/出链数
PR(p)PR(p)PR(p)	大写PR+节点p	“P R of p”	节点 ppp 的PageRank值，衡量节点重要性（搜索引擎排序核心）
λmaxlambda_{ ext{max}}λmax​	小写lambda+下标max	“lambda max”	邻接矩阵/拉普拉斯矩阵的最大特征值，用于特征向量中心性和谱分析
hih_ihi​	小写h+节点i	“h of i”	节点 iii 的特征向量（GNN中存储节点的属性信息，如用户年龄、单词嵌入）
H(l)H^{(l)}H(l)	大写H+上标l	“H superscript l”	第 lll 层节点特征矩阵（GNN中层间传播的特征载体）
W(l)W^{(l)}W(l)	大写W+上标l	“W superscript l”	GNN第 lll 层的可学习权重矩阵（用于特征线性变换）
αijalpha_{ij}αij​	小写alpha+下标ij	“alpha i j”	GAT中的注意力系数，表示节点 jjj 对节点 iii 的贡献权重
w(u,v)w(u,v)w(u,v)	小写w+括号u,v	“w of u v”	边 (u,v)(u,v)(u,v) 的权重（如用户互动频率、路径长度）
dist(u,v) ext{dist}(u,v)dist(u,v)	英文dist+括号u,v	“dist of u v”	节点 uuu 到 vvv 的最短距离（最短路径算法的核心输出）