GNN学习比较

GNN从入门到精通课程笔记

1.1 Graph基础知识

  • Graph:
    • Node + Edge
    • 无向图/有向图
    • degree：结点相连的边的数量
    • subgraph：子图
  • 图的表示：邻接矩阵adjacency
  • 连通图：任意节点i能够通过一些边到达任意节点j
    • 连通分量：一个极大的连通子图
    • 强连通图：如果节点u、v相互可达，则至少存在一条路径可以由u开始到v结束
  • 图直径：两节点的最短距离的最大值
  • 静态指标
    • $度中心性=\frac{N_degree}{n-1}$ (一个节点的度越大，就意味着这个节点的度中心性就越高，就说明这个节点越重要)
    • 特征向量中心性 Eigenvector Centrality：一个节点的中心性是相邻节点中心性的函数。(与你连接的人越重要，你也就越重要)
    • 中介中心性Betweenness Centrality：$BC=\frac{经过该节点的最短路径}{其余两两节点的最短路径}$（可以理解为“瓶颈”）
    • 连接中心性Closeness：$Closeness=\frac{n-1}{节点到其他节点的最短路径之和}$（反映在网络中某一节点与其他节点之间的接近程度。如果一个节点离其他的节点都很近，那么传递信息的时候就不需要依赖其他的节点，说明这个节点很重要）
    • PageRank（网页重要度算法）
    • HITS（网页重要度算法）