图遍历

使用流式表达式进行图遍历使用 nodes 函数执行广度优先图遍历。

nodes 函数可以与 scoreNodes 函数结合使用以提供建议。nodes 还可以与更广泛的流式表达式库结合使用，以对收集的节点集执行复杂的操作。

nodes 遍历在 SolrCloud 集合中分布，并且可以跨集合。

nodes 旨在用于涉及放大图中的邻域并执行精确遍历以收集节点集和聚合的用例。在这些类型的用例中，nodes 通常会提供亚秒级的性能。本文档稍后将提供一些示例用例。

本文档假设对图术语和流式表达式有基本的了解。您可以通过这篇 Wikipedia 文章开始探索图遍历概念。有关流式表达式的更多详细信息，请参阅本指南的流式表达式部分。

基本语法

我们将从最基本的语法开始，并逐步构建更复杂的内容。nodes 的最基本语法是

nodes(emails,
      walk="[email protected]>from",
      gather="to")

让我们分解这个简单的表达式。

第一个参数 emails 是要遍历的集合。第二个参数 walk 将硬编码的节点 ID (“[email protected]”) 映射到索引中的字段 (from)。这将返回索引中 from 字段中具有 [email protected] 的所有边。

gather 参数告诉函数收集 to 字段中的值。收集的值是函数发出的节点 ID。

在上面的示例中，发出的节点将是 “[email protected]” 已发送电子邮件的所有人员。

walk 参数还接受根节点 ID 列表

nodes(emails,
      walk="[email protected], [email protected]>from",
      gather="to")

上面的 nodes 函数查找 from 字段中具有 “[email protected]” 或 “[email protected]” 的所有边，并收集 to 字段。

像所有流式表达式一样，您可以通过将其发送到 /stream 处理程序来执行 nodes 表达式。例如

curl --data-urlencode 'expr=nodes(emails,
                                  walk="[email protected], [email protected]>from",
                                  gather="to")' https://127.0.0.1:8983/solr/emails/stream

此表达式的输出如下所示

{
  "result-set": {
    "docs": [
      {
        "node": "[email protected]",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "node": "[email protected]",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "node": "[email protected]",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "EOF": true,
        "RESPONSE_TIME": 44
      }
    ]
  }
}

返回的所有元组都具有 node 字段。node 字段包含函数收集的节点 ID。遍历的 collection、field 和 level 也包含在输出中。

请注意，示例中每个元组的级别均为“1”。根节点的级别为 0 (在上面的示例中，根节点为“[email protected]，[email protected]”) 默认情况下，nodes 函数仅发出遍历的 *叶节点*，即最外层的节点集。要发出根节点，您可以指定 scatter 参数

nodes(emails,
      walk="[email protected]>from",
      gather="to",
      scatter="branches, leaves")

scatter 参数控制是否连同叶子一起发出分支。根节点被认为是“分支”，因为它们不是遍历的最外层。

当同时散布分支和叶子时，输出将如下所示

{
  "result-set": {
    "docs": [
      {
        "node": "[email protected]",
        "collection": "emails",
        "field": "node",
        "level": 0
      },
      {
        "node": "[email protected]",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "node": "[email protected]",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "node": "[email protected]",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "EOF": true,
        "RESPONSE_TIME": 44
      }
    ]
  }
}

现在，级别 0 的根节点已包含在输出中。

聚合

nodes 还支持聚合。例如

nodes(emails,
      walk="[email protected], [email protected]>from",
      gather="to",
      count(*))

上面的表达式查找 from 字段中包含 "[email protected]" 或 "[email protected]" 的边，并收集 to 字段的值。它还聚合了每个收集的节点 ID 的计数。

如果 "[email protected]" 和 "[email protected]" 都向同一个人发送了电子邮件，则收集的节点可能具有计数 2。节点集包含一组唯一的节点，因此同一个人不会在节点集中出现两次，但计数将反映它在遍历期间出现了两次。

边作为遍历的一部分被唯一化，因此计数将不反映 "[email protected]" 向同一个人发送电子邮件的次数。例如，personA 可能已向 personB 发送了 100 次电子邮件。这些边将被唯一化，并且只会被计数一次。但是，如果 personC 也向 personB 发送了电子邮件，则 personB 的计数将增加。

支持的聚合函数有 count(*)、sum(field)、min(field)、max(field) 和 avg(field)。被聚合的字段应存在于遍历期间收集的边中。后面的示例（如下所示）将展示聚合可以成为提供建议和限制遍历范围的强大工具。

嵌套节点函数

可以嵌套 nodes 函数以更深入地遍历图形。例如

nodes(emails,
      nodes(emails,
            walk="[email protected]>from",
            gather="to"),
      walk="node->from",
      gather="to")

在上面的示例中，外部 nodes 函数对从内部 nodes 函数收集的节点集进行操作。

请注意，内部 nodes 函数的行为与已讨论的示例完全相同。但是外部 nodes 函数的 walk 参数的行为不同。

在外部 nodes 函数中，walk 参数与来自内部流式表达式的元组一起工作。在这种情况下，walk 参数将 node 字段映射到 from 字段。请记住，从内部 nodes 表达式收集的节点 ID 放置在 node 字段中。

简单来说，内部表达式收集 "[email protected]" 发送电子邮件的所有人。我们可以将这个群体称为“[email protected] 的朋友”。外部表达式收集“[email protected] 的朋友”发送电子邮件的所有人。这是一个基本的朋友的朋友遍历。

这种嵌套 nodes 函数的结构是通过图形执行受控遍历的基本技术。

循环检测

nodes 函数在整个遍历过程中执行循环检测。这确保了已访问过的节点不会再次遍历。循环检测对于限制遍历的大小和收集准确的聚合非常重要。如果没有循环检测，遍历的大小可能会随着遍历中的每一次跳跃呈指数增长。通过循环检测，只会遍历遇到的新节点。

循环检测不会跨越集合边界。这是因为在内部，集合名称是节点 ID 的一部分。例如，节点 ID "[email protected]" 实际上是 emails/[email protected]。当遍历到另一个集合时，"[email protected]" 将被遍历。

过滤遍历

遍历中的每个级别都可以使用过滤器查询进行过滤。例如

nodes(emails,
      walk="[email protected]>from",
      fq="body:(solr rocks)",
      gather="to")

在上面的示例中，只有与过滤器查询匹配的电子邮件才会包含在遍历中。任何 Solr 查询都可以包含在此处。因此，您可以执行诸如地理空间查询之类的有趣操作，应用任何可用的查询解析器，甚至编写自定义查询解析器来限制遍历。

根流

任何流式表达式都可用于为遍历提供根节点。例如

nodes(emails,
      search(emails, q="body:(solr rocks)", fl="to", sort="score desc", rows="20")
      walk="to->from",
      gather="to")

上面的示例通过搜索表达式提供根节点。您还可以提供任意复杂的、带有连接等的嵌套流式表达式，来指定根节点。

请注意，walk 参数映射来自内部流生成的元组的字段。在这种情况下，它将内部流的 to 字段映射到 from 字段。

跳过高频节点

通常需要跳过图形中的高频节点。这在本质上类似于搜索词停用列表。描述这种情况的最佳方法是通过一个用例示例。

假设您想根据协同过滤为用户推荐内容。以下是简单协同过滤的一种方法

查找用户 A 已阅读的所有内容。
查找阅读列表与用户 A 最接近的用户。这些用户与用户 A 有相似的品味。
根据步骤 2 中用户已阅读但用户 A 尚未阅读的内容推荐内容。

仔细查看步骤 2。在大型图形中，步骤 2 可能导致非常大的遍历。这是因为用户 A 可能已查看过数百万其他人已查看过的内容。我们可能想要出于以下两个原因跳过这些高频节点

访问数百万个唯一节点的大型遍历速度很慢，并且占用大量内存，因为循环检测是在内存中跟踪的。
高频节点在确定具有相似品味的用户方面也没有用。较少人查看过的内容提供了更精确的推荐。

nodes 函数具有 maxDocFreq 参数，允许过滤掉高频节点。下面的示例代码显示了推荐的步骤 1 和 2

 nodes(logs,
       search(logs, q="userID:user1", fl="articleID", sort="articleID asc", fq="action:view", qt="/export"),
       walk="articleID->articleID",
       gather="userID",
       fq="action:view",
       maxDocFreq="10000",
       count(*)))

在上面的示例中，内部搜索表达式搜索 logs 集合并返回 "user1" 查看的所有文章。外部 nodes 表达式获取从内部搜索表达式发出的所有文章，并查找这些文章的 logs 集合中的所有记录。然后，它收集并聚合阅读过这些文章的用户。maxDocFreq 参数将返回的文章限制为那些在不超过 10,000 条日志记录（每个分片）中出现的文章。这可以防止返回数百万用户已查看过的文章。

跟踪遍历

默认情况下，nodes 函数仅跟踪足够的信息来执行循环检测。这提供了足够的信息来输出图形中的节点和聚合。

对于某些用例，例如图形可视化，我们还需要输出边。设置 trackTraversal="true" 会告诉 nodes 跟踪节点之间的连接，以便可以构建边。启用 trackTraversal 时，每个节点都会出现一个新的 ancestors 属性。ancestors 属性包含指向该节点的节点 ID 列表。

以下是一个示例 nodes 表达式，其中 trackTraversal 设置为 true

nodes(emails,
      nodes(emails,
            walk="[email protected]>from",
            gather="to",
            trackTraversal="true"),
      walk="node->from",
      trackTraversal="true",
      gather="to")

跨集合遍历

嵌套的 nodes 函数可以在不同的 SolrCloud 集合上运行。这允许遍历从一个集合“步行”到另一个集合以收集节点。循环检测不会跨越集合边界，因此在一个集合中收集的节点将在另一个集合中遍历。这是有意为之，以支持跨集合遍历。请注意，来自跨集合遍历的输出很可能包含具有不同集合属性的重复节点。

以下是一个示例 nodes 表达式，该表达式从 “emails” 集合遍历到 “logs” 集合

nodes(logs,
      nodes(emails,
            search(emails, q="body:(solr rocks)", fl="from", sort="score desc", rows="20")
            walk="from->from",
            gather="to",
            scatter="leaves, branches"),
      walk="node->user",
      fq="action:edit",
      gather="contentID")

上面的示例查找所有发送正文包含 “solr rocks” 的电子邮件的人。然后，它查找这些人发送电子邮件的所有人。然后，它遍历到 logs 集合并收集这些人编辑的所有内容 ID。

将节点与其他流式表达式组合

nodes 函数可以充当流源和流装饰器。与更广泛的流式表达式库的连接在执行图形遍历时提供了巨大的能力和灵活性。以下是使用流式表达式库来相交两个朋友网络的示例

            intersect(on="node",
                      sort(by="node asc",
                           nodes(emails,
                                 nodes(emails,
                                       walk="[email protected]>from",
                                       gather="to"),
                                 walk="node->from",
                                 gather="to",
                                 scatter="branches,leaves")),
                       sort(by="node asc",
                            nodes(emails,
                                  nodes(emails,
                                        walk="[email protected]>from",
                                        gather="to"),
                                  walk="node->from",
                                  gather="to",
                                  scatter="branches,leaves")))

上面的示例收集了两个单独的朋友网络，一个以 "[email protected]" 为根，另一个以 "[email protected]" 为根。然后，朋友网络按 node 字段排序并相交。生成的节点集将是两个朋友网络的交集。

图形遍历的示例用例

计算市场购物篮共现

了解哪些产品最常与特定产品一起购买通常很有用。此示例使用一个简单的市场购物篮表（在 Solr 中索引）来存储过去的购物篮。该表的架构非常简单，每一行都包含一个 basketID 和一个 productID。这可以看作是一个图形，表中的每一行都表示一条边。可以非常快速地遍历它以计算购物篮共现，即使图形包含数十亿条边。

以下是示例语法

top(n="5",
    sort="count(*) desc",
    nodes(baskets,
          random(baskets, q="productID:ABC", fl="basketID", rows="500"),
          walk="basketID->basketID",
          fq="-productID:ABC",
          gather="productID",
          count(*)))

让我们分解一下此遍历的具体作用。

首先评估的表达式是内部 random 表达式，它从具有 productID "ABC" 的 baskets 集合返回 500 个随机 basketID。random 表达式对于推荐非常有用，因为它将遍历限制为固定的购物篮集，并且因为它在推荐中添加了惊喜元素。使用 random 函数，您可以从非常大的图形中提供快速样本集。
外部 nodes 表达式查找在步骤 1 中生成的 basketID 的 baskets 集合中的所有记录。它还会过滤掉 productID "ABC"，因此它不会显示在结果中。然后，它收集并计算这些购物篮中的 productID。
外部 top 表达式按计数对在步骤 2 中发出的 productID 进行排名，并选择前 5 个。

简而言之，此表达式查找过去购物篮中与产品 “ABC” 最常共现的产品。

使用 scoreNodes 函数进行推荐

此用例建立在市场购物篮示例以上的基础上，该示例计算哪些产品与 productID:ABC 共现最频繁。排名共现计数为推荐提供了候选者。可以使用 scoreNodes 函数对候选者进行评分，以找到最佳推荐。

在深入研究 scoreNodes 函数的语法之前，了解为什么原始共现计数可能无法产生最佳推荐是很有用的。原因是原始共现计数有利于在所有购物篮中频繁出现的商品。更好的推荐会找到与 productID ABC 关系最显着的产品。scoreNodes 函数使用词频-逆文档频率 (TF-IDF) 算法来查找最重要的关系。

scoreNodes 的工作原理

scoreNodes 函数为 nodes 表达式发出的每个节点分配一个分数。默认情况下，scoreNodes 函数使用 count(*) 聚合（即共现计数）作为 TF 值。每个节点的 IDF 值是从收集该节点的集合中获取的。然后使用 TF*IDF 公式对每个节点进行评分，该公式会提高在所有市场购物篮中频率较低的节点的分数。

将共现计数与 IDF 相结合可提供一个分数，该分数显示 productID ABC 与推荐候选者之间的关系有多重要。

scoreNodes 函数将分数添加到每个节点的 nodeScore 字段中。

`scoreNodes` 语法示例

top(n="1",
    sort="nodeScore desc",
    scoreNodes(top(n="50",
                   sort="count(*) desc",
                   nodes(baskets,
                         random(baskets, q="productID:ABC", fl="basketID", rows="500"),
                         walk="basketID->basketID",
                         fq="-productID:ABC",
                         gather="productID",
                         count(*)))))

此示例建立在之前的示例“计算市场购物篮共现”的基础上。

请注意，最内层的 top 函数正在选取与 productID ABC 共现频率最高的 50 个产品。这提供了 50 个候选推荐。
然后，scoreNodes 函数根据每个节点的 TF*IDF 为候选推荐分配分数。
外部的 top 表达式选择得分最高的节点。这就是推荐项。

在此示例中，我们将基于协同过滤为用户推荐内容。此推荐是使用包含 userID 和 articleID 以及执行的操作的日志记录生成的。在此场景中，每个日志记录都可以视为图中的一条边。userID 和 articleID 是节点，操作是用于筛选遍历的边属性。

以下是示例语法

top(n="5",
    sort="count(*) desc",
    nodes(logs,
          top(n="30",
              sort="count(*) desc",
              nodes(logs,
                    search(logs, q="userID:user1", fl="articleID", sort="articleID asc", fq="action:read", qt="/export"),
                    walk="articleID->articleID",
                    gather="userID",
                    fq="action:read",
                    maxDocFreq="10000",
                    count(*))),
              walk="node->userID",
              gather="articleID",
              fq="action:read",
              count(*)))

让我们逐步分解上面的表达式。

首先评估的表达式是最内部的 search 表达式。此表达式在 logs 集合中搜索与 “user1” 匹配的所有记录。这是我们要为其进行推荐的用户。

应用了一个过滤器来仅拉回 “action:read” 的记录。它返回找到的每条记录的 articleID。换句话说，此表达式返回 “user1” 已阅读的所有文章。
内部的 nodes 表达式在从步骤 1 返回的 articleID 上运行。它获取找到的每个 articleID，并针对 articleID 字段搜索它们。

请注意，它使用 maxDocFreq 参数跳过高频节点，以过滤掉在日志中出现超过 10,000 次的文章。它收集 userIDs 并汇总每个用户的计数。此步骤查找已阅读与 “user1” 阅读的相同文章的用户，并计算他们阅读的相同文章的数量。
内部的 top 表达式对从步骤 2 发出的用户进行排名。它将发出与 user1 的阅读列表重叠最多的前 30 个用户。
外部的 nodes 表达式收集从步骤 3 发出的用户的阅读列表。它计算收集的 articleIDs。

步骤 1 中选择的任何文章（user1 阅读列表）都不会出现在此步骤中，因为有循环检测。因此，此步骤返回与 “user1” 具有最相似阅读习惯的用户阅读的、但 “user1” 尚未阅读的文章。它还计算此用户组中每篇文章被阅读的次数。
外部的 top 表达式采用从步骤 4 发出的顶级文章。这就是推荐项。

蛋白质通路遍历

近年来，科学家们越来越能够合理地设计靶向突变蛋白质（称为癌基因）的药物，这些蛋白质导致某些癌症。蛋白质通常通过多个蛋白质之间的长链化学相互作用（称为通路）发挥作用，并且，虽然通路中的癌基因可能没有相应的药物，但通路中的另一种蛋白质可能有。对记录蛋白质相互作用和药物的蛋白质集合进行图遍历可能会产生可能的候选药物。（感谢 NCBI 的 Lewis Geer 提供此示例）。

下面的示例说明了蛋白质通路遍历

nodes(proteins,
      nodes(proteins,
            walk="NRAS->name",
            gather="interacts"),
      walk="node->name",
      gather="drug")

让我们分解一下此遍历的具体作用。

内部的 nodes 表达式在 proteins 集合中遍历。它找到图中蛋白质名称为 “NRAS” 的所有边。然后，它收集 interacts 字段中的蛋白质。这收集了与 “NRAS” 相互作用的所有蛋白质。
外部的 nodes 表达式也与 proteins 集合一起工作。它收集与从步骤 1 发出的蛋白质相对应的所有药物。
使用这种逐步方法，您可以收集从根蛋白质开始的任何数量步骤的相互作用通路中的药物。

导出 GraphML 以支持图可视化

在上面的示例中，nodes 表达式像任何其他流式表达式一样发送到 Solr 的 /stream 处理程序。此方法以与其他流式表达式相同的 JSON 元组格式输出节点，以便可以将其视为任何其他流式表达式。当您需要直接对元组进行操作时，可以使用 /stream 处理程序，例如在上述推荐用例中。

还有其他涉及图可视化的图遍历用例。Solr 通过引入 /graph 请求处理程序来支持这些用例，该处理程序接受 nodes 表达式并将结果以 GraphML 格式输出。

GraphML 是一种 XML 格式，受图可视化工具（如 Gephi）支持，Gephi 是一款用于统计分析和可视化图的复杂开源工具。使用 nodes 表达式，可以将较大图的一部分以 GraphML 格式导出，然后导入到像 Gephi 这样的工具中。

在以 GraphML 格式导出图时，需要注意一些事项

/graph 处理程序可以导出图中的节点和边。默认情况下，它仅导出节点。要导出边，您必须在 nodes 表达式中设置 trackTraversal="true"。
/graph 处理程序当前接受任意复杂的流式表达式，其中包括 nodes 表达式。如果流式表达式不包含 nodes 表达式，则 /graph 处理程序将无法正确输出 GraphML。
/graph 处理程序当前每个请求接受单个任意复杂、嵌套的 nodes 表达式。这意味着您不能发送流式表达式来连接或相交多个 nodes 表达式中的节点集。/graph 处理程序支持在单个 nodes 表达式中进行任意级别的嵌套。/stream 处理程序支持连接和相交节点集，但 /graph 处理程序当前不支持。

GraphML 请求示例

curl --data-urlencode 'expr=nodes(enron_emails,
                                  nodes(enron_emails,
                                        walk="[email protected]>from",
                                        trackTraversal="true",
                                        gather="to"),
                                  walk="node->from",
                                  scatter="leaves,branches",
                                  trackTraversal="true",
                                  gather="to")' https://127.0.0.1:8983/solr/enron_emails/graph

GraphML 输出示例

<graphml xmlns="http://graphml.graphdrawing.org/xmlns"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
<graph id="G" edgedefault="directed">
     <node id="[email protected]">
           <data key="field">node</data>
           <data key="level">0</data>
           <data key="count(*)">0.0</data>
     </node>
     <node id="[email protected]">
           <data key="field">to</data>
           <data key="level">1</data>
           <data key="count(*)">1.0</data>
     </node>
     <edge id="1"  source="[email protected]"  target="[email protected]"/>
     <node id="[email protected]">
           <data key="field">to</data>
           <data key="level">1</data>
           <data key="count(*)">1.0</data>
    </node>
    <edge id="2"  source="[email protected]"  target="[email protected]"/>
    <node id="[email protected]">
          <data key="field">to</data>
          <data key="level">1</data>
          <data key="count(*)">1.0</data>
    </node>
    <edge id="3"  source="[email protected]"  target="[email protected]"/>
</graph></graphml>

图遍历