**图4:**加权和有向图的示例。
第一类输入图是同构图(定义 2),其中节点和边分别属于单一类型。 同构图可以进一步分类为加权(或定
向)和无权(或无向)图,如图 4 所示的示例。
无向和无权的同构图是最基本的图嵌入输入设定。 许多研究都在这种情况下进行,例如 [1,16,17,18,19]。 它
们平等地处理所有节点和边,因为只有输入图的基本结构信息可用。
直观上,边的权重和方向提供了图的更多信息,并且有助于在嵌入空间中更准确地表示图。 例如,在图
4(a)中, 应该比 更接近 ,因为边的权重 更高。 同样在图 4(b)中, 应该比 更接
近 ,因为 和 在两个方向相连。 上述信息在无权和无向图中丢失。 注意到利用图边的权重和方向属
性的优点,图嵌入社区开始探索加权和/或有向图。 其中一些只关注一个图属性,即边权重或边方向。 一方
面,[20,21,22,23,24,25] 考虑了加权图 。 通过较高加权边连接的节点彼此靠得更近。 但是,他们的工作仍局
限于无向图。 另一方面,一些工作在嵌入过程中区分边的方向并且保持嵌入空间中的方向信息。 有向图的一
个例子是社交网络图,例如[26]。 每个用户都有其他用户的粉丝和关注关系。 但是,权重信息不适用于社交用
户链接。 最近,提出了一种更通用的图嵌入算法,其中考虑了权重和方向属性。 换句话说,这些算法(例
如,[27,3,28])可以处理有向和无向,以及加权和无权图 。
挑战: 如何捕获图中观察到的连接模式的多样性? 由于在同构图中只有结构信息可用,因此同构图嵌入的挑
战在于,如何在嵌入期间保留输入图中观察到的这些连通模式。
异构图
第二类输入是异构图(定义 3),主要存在于以下三种情形中。
基于社区的问答(cQA)网站。 cQA 是一种基于互联网的众包服务,使用户能够在网站上发布问题,然后由
其他用户回答[29]。 直观上,cQA 图中存在不同类型的节点,例如问题,答案,用户。 现有的 cQA 图嵌入方
法在它们利用的链接方面彼此区分,如表 2 所示 ,其中 表示 由用户j提供的问题i的答案k,比
用户p的答案o获得更多的投票(即点赞)。
表2: cQA站点的图嵌入算法
GE算法 利用的链接
[30]
用户 - 用户,用户 - 问题
[31]
用户 - 用户,用户 - 问题,问题 - 回答
[29]
用户 - 用户,问题 - 回答,用户 - 回答
[32]
用户的不对称关注链接,有序的元组