Graph Embedding综述
2019-10-31 本文已影响0人
老羊_肖恩
Introduction
图嵌入或网络嵌入(Graph/Network Embedding)是Graph Learning的重要研究方向之一，也是目前的热门研究方向。图嵌入的主要目的就是将原来的图或网络中的顶点映射成固定维度的特征向量，以便于将常规的机器学习模型应用在图数据（网络数据），这里的图或网络主要是一类由顶点和边组成的特殊数据结构。图嵌入应该能尽可能的保留图的拓扑结构信息，边信息和顶点上的属性信息。Graph Embedding在生物网络，社交网络或单词共现网络的等领域有着重要的应用。主要的应用场景有：Node Classification，Link Prediction，Clustering，Network Compression，Visualization等。目前Graph Embedding主要面临以下挑战：
- Choice of Properties：在实际应用的网络上，顶点和边往往都带有不同的属性信息，如顶点的度数，中心度，或顶点所带的内容，如年龄，时间戳等。如何将这些信息有效地嵌入到新的特征向量中，是一个值得深入研究和探讨的话题。
- Scalability：可扩展性主要体现在图嵌入算法能够在不同规模的图或网络上进行扩展。即针对不同节点或边规模的图，改嵌入算法能否很好的使用。例如，有些图嵌入算法需要同时使用整个图的数据，那么当面对百亿顶点或百亿边规模的数据时，改嵌入算法很可能无能为力。
- Dimensionality：图嵌入的目标就是将图中的顶点或边嵌入成一个低维的特征向量，那么如何确定这个低维的维度是一个非常值得深入研究的话题。维度过低，可能会丢失部分信息，导致在后面的应用中，效果不好；而维度过高，可能使整个嵌入的过程变的更加复杂。
- Computation Complexity：计算复杂度也是图嵌入时必须考虑的一个问题，因为面对不同规模的网络，计算复杂度决定了整个嵌入过程的时间长短。
Network Embedding
Graph Embedding根据实现方式的不同，主要分成：
- Factorization based Methods
- Random Walks based Methods
- Deep Learning based Methods
-
Miscellaneous Methods
另外根据不同的方法是否保存了图中的指定类型的信息，又可以将图嵌入方法分成： - Structure and Property Preserving
- Embedding with Side Information
- Advanced Information Preserving
关于以上Graph Embedding的总体知识框架，可以参考上图。具体的算法实现和综述内容，可以参考以下参考文件。
参考：
