CS224W 3.3 Embedding Entire Graphs

目录

目标

方法1：聚合或平均所有节点的嵌入

方法2:引入一个虚拟节点

方法3：使用Anonymous Walk

方法3：简单使用walk的出现次数

方法3：聚合walk的嵌入生成图的嵌入

 总结

embedding的应用

第3节课总结

---

目标

想要嵌入整个图或者子图，图嵌入：

方法1：聚合或平均所有节点的嵌入

• 在图上或子图上执行一个标准的嵌入技巧。
• 然后仅仅求和或者平均子图或者图上所有节点的嵌入。

方法2:引入一个虚拟节点

引入一个虚拟节点去表示子图或者图，然后对这个虚拟节点运行嵌入技巧。

注意虚拟节点要与对应的子图或图中的节点连接。

方法3：使用Anonymous Walk

方法3：简单使用walk的出现次数

匿名walk的state是指在一个random walk中访问节点的第一次出现次数(索引)，与节点的身份无关。

•  采样anonymous walks：产生m个独立的random walks。计算长度l下匿名walks 出现的次数
• 用这些walks的概率分布表示图
• 可以确定所需m的数量。

方法3：聚合walk的嵌入生成图的嵌入

首先学习anonymous walk的embedding ，然后利用anonymous walk embeddings𝑍 = {:𝑖 = 1…𝜂},学习图嵌入。即一共要学习η+1个嵌入，η是采样的anonymous walks的个数。

• 运行T次以节点u为起始的长度为l的random walks
• 学习去预测共同出现在Δ-size窗里的walks
• 预测anonymous walk的嵌入：是Δ-size窗里的walk embedddings和图嵌入的concatenate的均值再线性组合

学习得到图嵌入后可以用于图分类：可以利用两个图嵌入的内积 或者 可以将图嵌入输入神经网络得到分类结果。

 总结

embedding的应用

• 聚类或社区检测，对节点嵌入进行聚类
• 节点分类：基于节点嵌入预测节点i的标签
• 链接预测：基于(,)预测(i,j)之间的边利用节点的嵌入
• 图分类：图嵌入通过聚合节点嵌入或者利用anonymous random walks 。可以用来预测标签。

第3节课总结

第三课讨论了graph representation learning,与传统的方法不同，不需要特征工程，可以学习节点嵌入和图嵌入用于下游任务。