图论与图学习基础教程

---

引言

图（Graph）是一种表示实体及其关系的强大数据结构，广泛应用于社交网络、分子结构分析、推荐系统等领域。本教程将介绍图论基础知识、图的表示方法、常见类型及图学习任务，帮助读者构建对图数据的系统性理解。

---

一、预习资料

1. 图论基础

   • 核心概念：节点（Node/Vertex）、边（Edge）、邻接矩阵（Adjacency Matrix）。
   • 推荐阅读：GeeksforGeeks Graph Theory（重点阅读图的定义与基本操作）。
   • 目标：理解“节点表示实体，边表示关系”的核心思想。

2. 机器学习基础

   • 关键知识点：监督学习（带标签训练）、非监督学习（无标签聚类）、半监督学习（部分标签）。
   • 推荐工具：Scikit-learn Documentation（熟悉分类与聚类算法）。
   • 目标：掌握如何将机器学习方法应用于结构化数据。

---

二、图的表示方法

1. 邻接矩阵（Adjacency Matrix）

• 定义：用方阵 ( A ) 表示节点间的连接关系。若节点 ( i ) 与 ( j ) 之间有边，则 ( A[i][j] = 1 )（无权图）或边的权重（加权图）。
• 示例：

  # 3个节点的无向图（节点0-1、1-2相连）
  Adjacency Matrix = [
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]
  ]
  

• 特点：
  • 优点：快速判断两节点是否相连（时间复杂度 ( O(1) )）。
  • 缺点：空间复杂度 ( O(N^2) )，不适用于稀疏图（边数远小于 ( N^2 ) 的图）。

2. 邻接列表（Adjacency List）

• 定义：用列表存储每个节点的邻居。例如，节点 ( i ) 的邻居存储为列表 ( [j, k, ...] )。
• 示例：

  # 同上3个节点图的邻接列表
  Adjacency List = {
    0: [1],
    1: [0, 2],
    2: [1]
  }
  

• 特点：
  • 优点：空间复杂度 ( O(N + E) )，适合稀疏图。
  • 缺点：查询两节点是否相连需遍历列表（时间复杂度 ( O(d) )，( d ) 为节点度数）。

---

三、图的类型

1. 有向图 vs 无向图

类型	边的方向	示例场景
无向图	边无方向（双向）	社交网络中的好友关系
有向图	边有方向（单向）	网页超链接、微博关注关系

• 邻接矩阵区别：无向图的邻接矩阵是对称的，有向图不一定对称。

2. 加权图 vs 非加权图

类型	边是否带权重	示例场景
非加权图	边权重相同（通常为1）	论文合作网络（合作关系存在与否）
加权图	边有权重（如距离、概率）	交通网络（道路长度）、推荐系统（用户相似度）

---

四、常见图学习任务

1. 节点分类（Node Classification）

• 目标：预测图中节点的类别标签。
• 示例：
  • 社交网络中预测用户的兴趣领域（标签：科技、体育等）。
  • 引用网络中预测论文的研究主题。
• 方法：利用图神经网络（GNN）聚合邻居信息（如GCN、GraphSAGE）。

2. 链接预测（Link Prediction）

• 目标：预测节点间是否存在缺失的边。
• 示例：
  • 推荐系统中预测用户可能购买的商品（用户-商品边）。
  • 社交平台推荐“可能认识的人”。
• 方法：计算节点对的相似度（如DeepWalk、Node2Vec）。

3. 图分类（Graph Classification）

• 目标：预测整个图的类别。
• 示例：
  • 化学分子图中判断分子是否具有毒性。
  • 代码流程图分类（如检测恶意软件）。
• 方法：全局池化（Global Pooling）后接全连接层（如Graph Kernels、GIN）。

---

五、结语

掌握图论基础与图的表示方法是进行图学习的前提。后续可结合具体算法（如PageRank、GNN）深入实践。建议使用工具如NetworkX（图操作）和PyTorch Geometric（图神经网络）进行代码实战。

---

下一步学习建议：

• 实践邻接矩阵与邻接列表的相互转换（如用Python字典实现邻接列表）。
• 在Kaggle上尝试图分类任务（如TUDatasets）。