奇妙:【异质相似性度量】-PathSim-HeteSim

　　奇妙:【异质相似性度量】-PathSim-HeteSim

　　在同构或二分网络上，例如 PageRank (P-PageRank)、Sim-Rank 和 SCAN，这些相似性度量忽略了对象和链接之间不同类型的细微差别。异构网络中不同类型和链接的对象具有不同的语义，混合度量是没有意义的。这些度量偏向于寻找高度可见的对象（即与大量路径相关联的对象）或高度集中的对象（即大部分路径到达对象的小子集）。

　　与 P-PageRank 和 SimRank 相比，PathSim 的计算效率更高，因为它是一个局部图度量。但是对于 top-k 搜索功能，它仍然涉及昂贵的矩阵乘法运算，因为需要计算查询与网络中每个相同类型的对象之间的相似度。为了支持*敏*感*词*网络中的快速在线查询处理，首先提出了一种基线方法（PathSim-baseline），计算查询对象x与所有同类候选对象y的相似度。接下来，提出了一种基于联合聚类的剪枝方法（PathSim-pruning），该方法根据相似度上限剪除没有希望的候选者。

　　1. PathSim--异构网络中同类型对象之间的相似性搜索

　　原文：PathSim: Meta PathBased TopK Similarity Search in Heterogeneous Information Networks

　　一、原理

　　引入基于元路径的相似性的概念来研究异构网络中相同类型的对象之间的相似性搜索（两个相似的对象不仅应该是强连接的，而且应该具有可比的可见性）。由于对等点的关系应该是对称的，PathSim 只限于对称元路径。

　　分子表示从节点 x 到 y 的路径实例数；分母表示从 x 到 x 的路径实例数和从 y 到 y 的路径实例数

　　s(x,y)由两个方面来定义，一是：元路径上定义的两个顶点对象之间的关系；另一个是它们与它们自身之间的路径实例数。

　　例如：

　　作者和会议的邻接矩阵值是作者在该会议上发表的论文数量

　　根据pathsim计算mike和jim的相似度

　　与其他相似度度量方法相比，计算结果表明pathsim更合理

　　正式：

　　给定一个网络 G，计算矩阵 M，元路径 P，MAiAj 是节点 Ai 和 Aj 的邻接矩阵，M(i,j) 表示元路径 p 下节点 xi 和 xj 之间的元路径实例的数量。

　　2. PathSim 的本质

　　

　　1. 对称性（节点 i 和 j 与节点 j 和 i 具有相同的相似度） 2. 最大自我（节点之间的相似度在 0-1 之间，节点自身的相似度最大） 3. 可见性平衡（一定程度上缓解了前面提到的强连接和可见性的平衡）

　　尽管使用基于元路径的相似性，我们可以在给定任何往返元路径的情况下定义两个对象之间的相似性，但非常长的元路径并不是很有意义。事实上，由于真实网络的稀疏性，相似对象可能不共享直接邻居，较长的元路径会将相似性传播到远邻居。例如，在 DBLP 示例中，如果我们考虑元路径 APA，则只有两个共同作者的相似度分数不为零；但是如果我们考虑更长的元路径，如 A*敏*感*词*A 或 APTPA，如果作者在相似的场所发表或共享相似的术语集，无论他们是否合着，都被认为是相似的。文章证明很长的元路径可能会产生误导（有关证明过程，请参见论文）。Pathsim 方法更适合于相对较短的元路径的 k-top 相似性搜索。

　　即使对于相对较短的长度，实现所有元路径仍然可能在时间和空间上效率低下。因此，作者也在论文中对其进行了讨论。（此处省略）

　　2. HeteSim - 测量异构对象（相同类型或不同类型的对象）的相关性

　　原创论文：HeteSim：异构网络中相关性度量的通用框架

　　这里参考CSDN博文，在此基础上进行简化：【论文翻译】HeteSim: A General Framework for Correlation Measurement in Heterogeneous Networks_Mrong1013967的博客-CSDN博客

　　1 简介

　　相似性搜索通常侧重于测量相同类型对象之间的相似性。然而，在很多场景中，我们需要衡量不同类型对象之间的相关性。随着异构网络研究的兴起，不同类型对象的相关性度量变得越来越重要。本文研究异构网络中的相关性搜索问题，其任务是衡量异构对象的相关性，包括相同类型或不同类型的对象。提出了一种新的度量方法HeteSim，具有以下特点： （1）一致性度量：可以在一个统一的框架内度量同类型或不同类型对象之间的相关性；(2) 路径约束测量：

　　相似性搜索是广泛应用中的一项重要任务，例如网络搜索 [1] 和产品推荐 [2]。相似性搜索的关键是相似性度量，它评估对象对之间的相似性。对于传统的分类和数值数据类型，例如 Jaccard 系数和余弦相似度。也有一些使用网络中的链接信息来衡量节点相似度的研究，如 Personalized PageRank、SimRank 和 PathSim。传统的相似度测量研究主要集中在同类型的物体上。也就是说，被测量的对象是同一类型的，例如“文档到文档”、“网页到网页”和“用户到用户”。

　　然而，在许多应用中都需要针对不同类型对象的相似性度量。例如，在推荐系统中，我们需要知道用户和电影之间的关系才能做出准确的推荐。特别是随着异构信息网络研究的兴起，研究不同类型对象之间的相关性变得越来越重要。异构信息网络是指收录多种对象和代表不同关系的多种链接的逻辑网络。例如，书目网络包括作者、论文、会议、术语和指示它们之间关系的链接。在这样的网络中，为不同类型的对象提供相关的搜索功能是非常有必要的，这是很多应用的基础。

　　本文研究了异构信息网络中的相关搜索问题。关联搜索的目的是有效衡量异构对象（包括相同类型或不同类型的对象）之间的关联。与相似性搜索只衡量同类型对象之间的相似性不同，相关性搜索衡量的是异类对象之间的相关性，而不限于同类型的对象。这里的关联搜索是在异构网络上进行的，由对象的元数据组成。此外，我们认为理想的相关性度量应该满足对称性，原因如下。(1) 对称度量在许多学习任务中更加通用和有用。尽管在查询任务中不需要对称性，它对于许多重要任务（例如聚类和协同过滤）至关重要。此外，它也是测量的必要条件。(2) 对称度量在许多应用中更有意义，特别是对于异质对象对的相关性。例如，在某些应用程序中，我们需要回答诸如谁对会议 SIGIR 和 JFnaughton 对 SIGMOD 一样重要等问题。通过比较对象对之间的相关性，我们可以推断出它们的相对重要性。但是，它只能通过对称措施来实现，而不是通过不对称措施来实现。这可以通过图 1 中所示的示例来解释。特别是对于异质对象对的相关性。例如，在某些应用程序中，我们需要回答诸如谁对会议 SIGIR 和 JFnaughton 对 SIGMOD 一样重要等问题。通过比较对象对之间的相关性，我们可以推断出它们的相对重要性。但是，它只能通过对称措施来实现，而不是通过不对称措施来实现。这可以通过图 1 中所示的示例来解释。特别是对于异质对象对的相关性。例如，在某些应用程序中，我们需要回答诸如谁对会议 SIGIR 和 JFnaughton 对 SIGMOD 一样重要等问题。通过比较对象对之间的相关性，我们可以推断出它们的相对重要性。但是，它只能通过对称措施来实现，而不是通过不对称措施来实现。这可以通过图 1 中所示的示例来解释。

　　部分标记为黑色的矩形表示两个对象的相关性。

　　对于对称测量，我们可以推断 WBCroft1 对 SIGIR 的重要性与 JFNaughton2 对 SIGMOD 的重要性一样，因为它们密切相关。假设我们知道 JF Norton 是 SIGMOD 的一位有影响力的研究员，我们可以得出结论，WB Croft 也是 SIGIR 的一位有影响力的研究员。然而，我们不能从图 1（b）所示的不对称度量中推断出相对重要性信息。

　　HeteSim 是一种基于路径的相关性度量，可以有效地捕捉搜索路径的微妙语义。HeteSim 基于成对随机游走模型，统一处理任意搜索路径，保证了 HeteSim 的对称性。另一个好处是 HeteSim 可以以相同的方式评估具有相同或不同类型对象的依赖关系。此外，HeteSim 是一个半度量标准。换句话说，HeteSim 满足非负性、不可区分的同一性和对称性。这意味着 HeteSim 可以用于许多学习任务（例如聚类和协同过滤）。我们还考虑了 HeteSim 的计算问题，并提出了四种快速计算策略。大量实验验证了 HeteSim 的有效性。作为一般的关联度量，HeteSim通过四个例子说明了其在异构网络知识发现中的优势和*敏*感*词*性：对象轮廓的自动提取、对象对相对重要性的专家搜索、基于路径语义的关联搜索和基于语义的电影推荐。HeteSim 还在机器学习任务（查询和聚类）中展示了其潜力，其中 HeteSim 优于其他成熟的相似性度量。此外，大量实验验证了 HeteSim 快速计算策略的重要性。HeteSim 还在机器学习任务（查询和聚类）中展示了其潜力，其中 HeteSim 优于其他成熟的相似性度量。此外，大量实验验证了 HeteSim 快速计算策略的重要性。HeteSim 还在机器学习任务（查询和聚类）中展示了其潜力，其中 HeteSim 优于其他成熟的相似性度量。此外，大量实验验证了 HeteSim 快速计算策略的重要性。

　　2、相关工作

　　与相关性搜索最相关的工作是相似性搜索。相似性搜索已经被很好地研究了很长时间。这些研究大致可以分为两类：基于特征的方法和基于链接的方法。基于特征的方法根据对象的特征值来衡量对象的相似度，例如余弦相似度、杰卡德系数和欧几里得距离。k-最近邻也广泛用于相似性度量，其目的是根据数值特征上定义的相似性找到前 k 个最近邻。基于特征相似度的top-k相似度对搜索算法（即top-k-join）考虑了元组之间的相似度。该方法不考虑对象之间的链接关系，因此不能应用于网络数据。

　　基于链接的方法根据对象在图中的链接结构来衡量对象的相似性。不对称相似性度量 PageRank 通过重新开始随机游走来评估从源对象到目标对象的概率。SimRank 是一种对称相似度度量，通过相邻对象的相似度来评估两个对象的相似度。SCAN 通过比较两个对象的最近邻集来测量两个对象的相似性。最近，Jin 等人。提出 RoleSim 通过自值得等价来衡量节点对的角色相似性。这些方法只考虑相同类型的对象，不适用于异构网络。ObjectRank 将基于权威的排名应用于标签图中的关键字搜索，PopRank 提出了与领域无关的对象级链接分析模型。

　　近年来出现了异构数据的相关性研究。[22] 提出了一个从异构数据中学习相关性的模型，他们的模型更侧重于分析异构网络的上下文而不是网络结构。[23]基于随机游走的马尔可夫链模型设计了一种具有良好属性和解释能力的相似性度量ECTD。不幸的是，由于缺乏路径约束，ECTD 无法捕捉异构网络中的微妙语义。孙等人。[5] 考虑了由不同类型对象组成的元路径的语义，提出了基于对称路径的 PathSim 来衡量相同对象的相似性。然而，许多有价值的路径是不对称的，不同类型的对象之间的相关性也是有意义的。PathSim 不适合这些条件。在信息检索领域，Lao 和 Cohen [9]、[24] 提出了一种路径约束随机游走 (PCRW) 模型来测量由丰富的科学文献元数据构建的有向图中的实体接近度。虽然 PCRW 模型可以用来衡量不同类型对象之间的相关性，但 PCRW 模型的不对称性限制了它的应用。在 HeteSim 的定义中，用户可以根据任意搜索路径测量异构对象的相关性。HeteSim 的对称性和自最大化等优点使其适用于更多应用。虽然 PCRW 模型可以用来衡量不同类型对象之间的相关性，但 PCRW 模型的不对称性限制了它的应用。在 HeteSim 的定义中，用户可以根据任意搜索路径测量异构对象的相关性。HeteSim 的对称性和自最大化等优点使其适用于更多应用。虽然 PCRW 模型可以用来衡量不同类型对象之间的相关性，但 PCRW 模型的不对称性限制了它的应用。在 HeteSim 的定义中，用户可以根据任意搜索路径测量异构对象的相关性。HeteSim 的对称性和自最大化等优点使其适用于更多应用。

　　3. 初步定义

　　

　　例1：书目信息网络是典型的异构信息网络。ACM 数据集的网络模式如图 2(a) 所示。它收录来自七个实体的对象：论文 (P)、作者 (A)、隶属关系 (F)、术语 (T)、主题 (S)、位置 (V) 和会议 (C)（一个会议包括多个位置，例如KDD包括KDD2010、KDD2009等）。存在连接不同类型对象的链接。链接类型由两个对象类型之间的关系定义。例如，作者和论文之间有一个链接，表示写作或关系写作，地点和论文之间有一个链接，表示出版或关系出版。图 2(b) 和 (c) 分别显示了 DBLP 数据集和 IMDB 电影数据的网络模式。

　　与同构网络不同，异构网络中的两个对象可以通过不同的路径连接，具有不同的含义。例如，在图 2(a) 中，作者和会议可以通过“Author Papers Venue Meeting”（APVC）路径、“Author Papers Subject Paper Venue Meeting”（APSPVC）路径等连接。这两条路径下的语义不同。APVC 路径是指作者撰写的论文在会议上发表，而 APSPVC 路径是指与作者论文主题相同的论文在会议上发表。显然，不同路径下的不同语义会导致不同的结果。APVC 路径下的相关性强调作者参加的会议，APSPVC 路径下的相关性和相关性强调发表与作者论文相同主题的论文的会议。例如，Christos Faloutsos 的大部分论文都发表在 KDD、VLDB 和 SIGMOD 上。但是，与他的论文主题相同的论文可能会在 ICDM、SDM 和 CIKM 等广泛的会议上发表。因此，在异构网络中，对象的关联性取决于搜索路径。形式上，我们将元搜索路径定义为关联路径（其实就是元路径的定义和一些属性，各种论文都会介绍，对比大家的理解）。与他的论文主题相同的论文可能会在ICDM、SDM和CIKM等广泛的会议上发表。因此，在异构网络中，对象的关联性取决于搜索路径。形式上，我们将元搜索路径定义为关联路径（其实就是元路径的定义和一些属性，各种论文都会介绍，对比大家的理解）。与他的论文主题相同的论文可能会在ICDM、SDM和CIKM等广泛的会议上发表。因此，在异构网络中，对象的关联性取决于搜索路径。形式上，我们将元搜索路径定义为关联路径（其实就是元路径的定义和一些属性，各种论文都会介绍，对比大家的理解）。

　　4. HeteSim

　　（一）基本思想

　　相似对象更有可能与许多领域中的其他相似对象相关。例如，类似的研究人员经常发表许多类似的论文；相似的客户购买相似的产品。因此，如果两个对象被相似的对象引用，则它们是相似的。这种直觉也适用于异构对象。例如，研究人员与研究人员发表论文的会议更相关；客户更忠诚于客户通常购买的品牌。当我们将这个想法应用于异构网络时，它面临以下挑战。(1)异构对象的关联是路径约束的。关联路径不仅捕获语义信息，还约束步行路径。因此，有必要设计一种基于路径的相似度度量方法。(2) 任何路径都应该设计一个统一和对称的度量。对于给定的路径（对称或不对称），该度量可以使用分数来评估成对的异构对象（相同或不同类型）的相关性。

　　(2) 基于路径的相关性测量

　　O(s|R1) 表示基于关系 R1 的 s 的外邻居，I(t|Rl) 表示基于关系 R1 的节点 t 的内邻居。当 s 没有外部邻居时，O(s |R1) = ∅，或者，当 t 没有内部邻居时，I(t|Rl) = ∅，在这种情况下，我们无法推断 s 和 t 之间的任何相关性，所以我们把它们的相关值定义为0。

　　等式 (1) 表明 HeteSim(s, t|P) 的计算需要迭代节点对 (s, t) 的所有路径（s 路径和 t 对路径）并计算这些节点对的相关性。然后我们通过 s 的外部邻居和 t 的内部邻居的总数对其进行归一化。也就是说，s 和 t 之间的相关性是 s 的外部邻居和 t 的内部邻居之间的平均相关性。这个过程一直持续到 s 和 t 沿着路径相遇。与 SimRank [4] 类似，HeteSim 也基于成对随机游走，同时考虑了路径约束。正如我们所知，SimRank 测量两个随机冲浪者预计在同一节点相遇的时间 [4]。相反，HeteSim(s, t|P) 测量当 s 沿着路径且 t 与路径相反时 s 和 t 在同一节点处相遇的概率。

　　特别是，我们认为同一类型的对象具有自相关性（记为 I 关系），并且每个对象仅与自身具有自相关性。显然，对于 I 关系，对象只与自身相似。基于自相关的 HeteSim：基于自相关 I 的相同类型 s 和 t 的两个对象之间的 HeteSim 为：

　　如果 s 和 t 相同，则 (s, t) = 1，否则 (s, t) = 0。

　　(3) 关联路径分解

　　但是，源对象 s 和目标对象 t 可能不会沿着给定的路径 P 相遇。对于相同类型的对象的相似性度量，相关路径通常是等长的，甚至是对称的，因此源对象和目标对象会在中间对象处相遇. 然而，对于不同类型对象的关联度量，关联路径通常是奇数长度。在这种情况下，源对象和目标对象将永远不会在同一个对象上相遇。以 APVC 路径为例，作者沿着路径和反对路径的相遇永远不会在同一个对象中相遇。因此，原创的 HeteSim 算法不适用于奇数长度的相关路径。为了解决这个问题，一个基本的想法是将奇数长度的路径转换为偶数长度的路径，这样源对象和目标对象总是可以在同一个对象上相遇。所以，

　　剩下的论文就是证明HeteSim的属性和特点，有兴趣的可以自己看，有点难……

　　超强:关键字*敏*感*词*

　　今天，在做公司的编码用我活动ppt时，我需要一个描述网页插座特征的文本墙。我记得在Coursera的NLP课上听老师说有一个工具。

　　

　　向下搜索并真正找到它，在标记下，为了不可预见的需求，wordle是使用Java小程序实现的SaaS关键字文本墙生成工具，因此需要JRE环境。除了强大的关键字提取功能外，您还可以自定义文本墙的样式和字体。

　　以下是ppt使用的网页索克简介图片