图遍历

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

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

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

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

此文档假定您对图形术语和流式表达式有基本的了解。您可以通过这篇维基百科文章开始了解图形遍历概念。本指南的流式表达式部分提供了有关流式表达式的更多详细信息。

基本语法

我们将从最基本的语法开始，然后逐渐增加复杂性。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字段。

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

curl --data-urlencode 'expr=nodes(emails,
                                  walk="[email protected], [email protected]>from",
                                  gather="to")' http://localhost: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 列表。

以下是将 trackTraversal 设置为 true 的示例 nodes 表达式

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

跨集合遍历

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

以下是从“emails”集合遍历到“logs”集合的示例 nodes 表达式

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”正文的电子邮件的人。然后，它找到这些人发送电子邮件的所有人。然后，它遍历到日志集合并收集这些人编辑的所有内容 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 表达式，它从 baskets 集合中返回 500 个随机 basketID，这些 basketID 具有 productID "ABC"。random 表达式对于推荐非常有用，因为它将遍历限制在固定的篮子集合中，并且因为它在推荐中增加了惊喜元素。使用 random 函数，您可以从非常大的图中提供快速样本集。
外部 nodes 表达式查找 baskets 集合中针对步骤 1 中生成的 basketID 的所有记录。它还过滤掉 productID "ABC"，以便它不会显示在结果中。然后，它收集并统计这些篮子中的 productID。
外部 top 表达式按计数对步骤 2 中发出的 productID 进行排名，并选择前 5 个。

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

使用 scoreNodes 函数进行推荐

此用例基于上面的市场篮子示例，该示例计算与 productID:ABC 最常共现的产品。排名的共现计数为推荐提供了候选者。scoreNodes 函数可用于对候选者进行评分，以找到最佳推荐。

在深入了解 scoreNodes 函数的语法之前，了解原始共现计数可能无法产生最佳推荐的原因非常有用。原因是原始共现计数偏向于在所有篮子中经常出现的项目。更好的推荐将找到与 productID ABC 关系最密切的产品。scoreNodes 函数使用词频-逆向文件频率 (TF-IDF) 算法来找到最重要的关系。

scoreNodes 的工作原理

scoreNodes 函数为节点表达式发出的每个节点分配一个分数。默认情况下，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 次的文章。它收集用户 ID 并汇总每个用户对应的计数。此步骤查找已阅读与“user1”阅读相同文章的用户，并统计他们阅读的相同文章数量。
内部 top 表达式对步骤 2 中发出的用户进行排名。它将发出与 user1 的阅读列表重叠度最高的 30 位用户。
外部 nodes 表达式收集步骤 3 中发出的用户的阅读列表。它统计收集到的 articleID。

由于循环检测，步骤 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，这是一个用于统计分析和可视化图形的高级开源工具。使用 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")' http://localhost: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>

图遍历