/

《A Comprehensiv Survey of Graph Embedding Problems Techniques and Applications》笔记

Questions:

  • auxiliary-node feature(text feature)
  • 方法之间的区别

图嵌入的意义：降低图研究的复杂程度

1.Introduction

因为要利用图中隐含的信息，所以要对图进行研究。但是图的规模太大，直接研究计算开销太大，因此要用合理的方式来给图换一种表示方法，同时要尽可能的保留原有的结构信息。
Graph embedding converts a graph into a low dimensional space in which the graph information is preserved.
区分图表示与图嵌入。graph representation不需要降维，graph embedding需要降维。

2.Problem Formalization

2.1 Notataion and Definition

  • graph
  • homogeneous graph：节点、边的类型只有一种。
  • heterogeneous graph：节点、边的类型不止一种。
  • knowledge graph：（h,r,t）（实体1，关系，实体2）可以看做一种异构图的特例。
  • first-order proximity：
    直接相邻的邻居之间，边的权值越大相似度越高
  • second-order proximity
    公共邻居越多越相似，由邻居的结构决定。用余弦相似度计算。

    3.Problem Settings

    从问题的角度分类，可以根据输入数据的类型，也可以根据需要的输出类型。
    因为携带的数据/需要保留的信息不同，所以说嵌入信息的方法也不同，评价嵌入结果的方法也不同。

    3.1 Input

    Fixed and given.
    不同的输入类型携带了不同的需要保存的信息。

    3.1.1 Homogeneous Graph

    最普通最直观的是无权无向图，近来也有考虑其中之一或者两者都考虑的。
    Challenge:如何保存连接模式的多样性/结构信息（因为只有这个需要保存）

    3.1.2 Heterogeneous Graph

    常用于三种应用场景：
  • 社区问答
  • 多媒体网络
  • 知识图谱？
    Challenge:如何在不同的类型之间保持一致与平衡？

    3.1.3 Graph with Auxiliaary Information

    点/边/全图除了结构之外，也可能自己带有一些相关信息。主要分类有：
  • Label:打了不同标签的节点在表示时距离应该尽量的远
  • Attribute：属性值既可以是离散的，也可以是连续的。
  • Node feature节点特征：大多数的节点特征是文本特征，可以代表words/documents.
    丰富的无结构信息。使归纳成为可能。
  • Information propagation信息传播：可能是级联的
  • Knowledge base基于知识库。
    Challenge:这些信息往往丰富而无结构。如何体现这样的信息，使结构与附加信息同时保存下来？//对比于Homogeneous，只需要考虑结构。

    3.1.4 Graph Constructed from Non-relational Data

    Input data is assumed to lie in a low dimensional maniofold.输入数据来自于低维流形空间
    ①Pairwise similarity based.点对之间的相似度。
    不能采用欧氏距离。可以用KNN,Isomap,Anchor等.
    ②Node co-occurrence based.基于节点同现
    ③etc.
    Challenge:如何计算相似程度

    3.2 Output

    Task driven.由解决的任务决定
    首要的挑战就是如何根据不同的问题选择合适的输出粒度(输出类型)。

    3.2.1 Node**最常见的一种

    与邻居的相似度
    Challenge：如何定义、编码”邻近度”

    3.2.2 Edge

    常用于预测类的任务。预测关系是什么（边的意义）？预测是否有边（有关系）？
    Challenge：如何定义边的相似度？不对称的边如何建模？（可能有向）

    3.2.3 Hybrid

    //最终产物是substructure
    如何生成子结构？在统一的空间里如何表示不同的子结构？

    3.2.4 Whole-Graph

    //substructure只是中间产物，是分析问题的一个步骤
    全图级别的相似度
    分析不同规模的子结构。
    Challenge:①如何归纳全图的信息②分析全图需要的开销很大，如何实现效率与表达能力的平衡。

    4.Graph Embedding Techniques

    4.1 Matrix Factorization矩阵分解

    多数情况下input from on-relational high dimensional data features,
    输出为node.

    4.1.1 Graph Laplacian Eigenmaps图拉普拉斯特征映射

    The graph property to be preserved can be interpreted as pairwise node similarities,and thus a larger penalty is imposed if two nodes with larger similarity are embedded far apart.
    相似度高的两节点映射到低维空间之后仍然应保持距离相近。

    4.1.2 Node Proximity Matrix Factorization

    Node proximity can be approximated in a low-dimensional space using matrix factorization.The objective of preserving node proximity is therefore to minimize the loss during the approximation.
    利用矩阵分解可以在低维空间中近似地逼近节点的邻近度。因此，保持节点邻近度的目标是在逼近过程中尽量减少损失。
    Summary
    Matrix factorization is mostly used to embed the graph constructed from non-relational data for node embedding as this is the original setting of the graph Laplacian eigenmaps based problems.In a few work,it is also used to embed homogeneous graphs.//从输入的角度总结
    矩阵分解主要用于嵌入由非关系数据构建的图，用于节点嵌入，因为这是基于问题的图拉普拉斯特征映射的原始设置。在一些工作中，它也被用来嵌入齐次图形。

    4.2 Deep Learning

    可以从别的研究方向推广而来。
    输入①边采样paths sampled from a graph②全图the whole graph
    依据边采样是否采用了随机游走分类
    鲁棒，高效，已经广泛应用。

    4.2.1 DL based Graph Embedding with Random Work

    刻画了网络的局部信息。
    两节点联系越紧密，在随机游走中共现的可能性就越大。如果不连通，就不可能共现。
    基础算法DeepWalk，其他算法在此基础上引申。
    从NLP/语言模型领域推广而来，思想来自于word2vec.
    e.g.DeepWalk的游走方法是随机DFS,node2vec是由参数控制的随机游走，加入了BFS。

    4.2.2…without Random Walk

    基于全图.
  • Autoencoder
  • Deep Neural Network
    不同算法的区别是在图上生成类似卷积的操作。

    4.3 Edge Reconstruction based Optimization

    The edges established based on node embedding should be as similar to those in the input graph as possible.
    基于边重建，重建的边应该近似于输入

    4.3.1 Maximizing Edge Reconstruction Probability最大化概率

    4.3.2 Minimizing Distance-based Loss最小化基于距离的损失

    4.3.3 Minimizing Margin-based Ranking Loss最小化基于

    图中一些节点可能与一组相关的节点有关
    A node’s embedding is more similar to the embedding of relevant nodes than that of any other irrellevant node.

    4.4 Graph Kernel

    把握全局特征。针对全图而生
    全图表示。拆分成分解出来的子结构
    The whole graph structure can be represented as a vector containing the counts of elementary substructures that are decomposed from it.
    子结构分类：
  • Graphlet
  • Subtree Patterns
  • Random Walks
    适合的输入类型：
  • homogeneous同质
  • auxiliary info.辅助信息

    4.5 Generative Model

    适用场景： 输出node,edge；输入heterogeneous,auxiliary infomation。

    4.5.1 Embed Graph Into The Latent Semantic Space

    嵌入到潜在语义空间

    4.5.2 Incorporate Latent Semantics for Graph Embedding

    4.6 Hybrid & Others

5.Appliacation

该节是按照输出类型分类的。

  • Node Classfication
  • Node Clustering
  • Node Recommendation/Retrieval/Ranking推荐、检索、排序
  • Link Prediction联系预测
  • Triple Classification三元组分类
  • Graph Classification图像分类
  • Visualization 可视化

    5.4 Other

  • Knowledge graph related
  • Multimedia network
  • Information propagation
  • Socail networks alignment
  • Image

    6.Future Directions

  • Computation
  • Problem settings
    动态的，随时间而变的
  • Techniques
  • Applications

    7.Conclusion

    Graph embedding的正式定义、基本概念
    两种分类方法，将现有工作分为①四输入四输出，分别的挑战②技术
    总结应用
    四个未来研究方向

DeepWalk:Online Learning of Social Representations

1.Introduction

2.Problem Definition

3.

Social representations应有的特征：

  • Adaptability适应性。能够适应社交网络的演化
  • Community aware.”有社区意识”，用距离度量相似度，有利于同质网络的泛化。
  • Low dimensional低维
  • Continuous连续

    3.1 Random Walks

    可用于相似度的度量。
    容易并行化
    适应小的变化

    3.2 Connection:Power Laws

    网络结构和语言结构是相似的。

    3.3 Language Model

    4.Method

    4.1

    4.2 Algorithm:DeepWalk

    4.2.1 SkipGram

    4.2.2 Hierarchical Softmax

    为了提高性能，加速计算。

    4.2.3 Optimization

    随机梯度下降