【同济子豪兄斯坦福CS224W中文精讲】学习笔记一_斯坦福大学公开课cs224w笔记

Introduction

图无处不在：图是描述关联数据的通用语言。
机器学习、深度学习所解决的大多数任务中数据都满足独立同分布和彼此孤立无关这两个假设，而图并非如此，因此我们需要使用全新的方法来处理图数据挖掘问题
常见的图：particle networks、underground networks、social networks、economic networks、knowledge graphs、
那么对于图这样一种与传统的序列、网格状数据不同的数据结构，我们应该怎么对其进行数据挖掘？

图深度学习的困难在何处？
图尺寸可能很大，拓扑结构可能很复杂
图没有固定的节点顺序和参考锚点
图往往是动态变化的并且会表现出多模态的特征(如音乐推荐，视频推荐等)

图深度学习流程图：

使用图深度学习需要什么技术？
使用representation learning将图数据表示为机器可以使用的向量，

我们在这门课上会需要学习什么？Machine Learning and Representation Learning

图机器学习的常见任务

图的基本表示

图的基本组成

图的本体设计

图的顶点表示什么，边表示什么？这就是图的本体ontology的设计问题，这回决定我们的图到底能在多大程度将网络数据表示出来。通常情况下，我们需要根据待解决的问题定义来决定图的本体设计

the way you assign links will determine the nature of the question you can study

图的种类

有向图：collaborations | Friendship on Facebook…
无向图：phone calls | following on Twitter
异质图：图中出现了不同类型的顶点。如电商网络图中会存在商家node，用户node。特别的，仅有两种node且edge只出现在两种节点之间的异质图被称为二部图(bipartite)

二部图举例：
Authors-to-Papers Graph
Actors-to-Movies Graph
Users-to-Movies Graph

与二部图相对应的展开二分图 “folded” network
比如 Author collaboration networks、Movie co-rating networks

节点连接数

用$k$表示
对于undirected graph 直接用$k_i$表示
对于derected graph 使用$k_i^{in}$和$k_i^{out}$表示节点的入度和出度

图的基本表示

邻接矩阵 adjacency matrix

在邻接矩阵中的一些计算
某节点的度：无向图中$k_i={\sum }_{j=1}^N{A}_{ij}={\sum }_{j=1}^N{A}_{ji}$ 有向图中$k_i^{out}={\sum }_{j=1}^N{A}_{ij}$ $k_i^{in}={\sum }_{i=1}^N{A}_{ij}$
无向图中连接数$L=\frac{1}{2}{\sum }_{i=1}^N{k}_i=\frac{1}{2}{\sum }_{ij}^N{A}_{ij}$ 有向图中连接总数$L={\sum }_{i=1}^N{k}_i^{in}={\sum }_{i=1}^N{k}_i^{out}={\sum }_{i,j}^N{A}_{ij}$
使用邻接矩阵表示图的缺点：矩阵过于稀疏，并且在实际问题上大多数网络都是很sparse的，结果是矩阵中有很多0

邻接列表 adjacency list
邻接列表在处理大型的稀疏网络具有优势
我们可以容易地获得某节点的所有邻接节点

连接列表 list of edges
每条边用一个二元组表示，(node1, node2)表示node1和node2之间有一条边相连

图的连通性

图论中的基本知识
对于无向图而言，连通图指任意两个节点之间都通过某路径连接的图。一个非连通图可以被划分为多个连通域
对于有向图，连通图分为强连通图(strongly connected directed graph)和弱连通图(weakly connected directed graph)。
强连通图指在考虑边方向时任意两个节点均连通的图。
弱连通图指不考虑边方向时任意两个节点均连通的图。

参考资料

1. 同济子豪兄课程repo地址：https://github.com/TommyZihao/zihao_course/tree/main/CS224W