Neo4J：如何根据现有路径的数量计算相似度分数？

Question

我有一个简单的图表，其中包含节点

bgc

和

protein

，其中

(:bgc)-[:ENCODES]->(:protein)

。蛋白质可以彼此相似，并且用单独的关系来表示，例如

(:protein)-[:MMSEQS_90]->(:protein)

（90% 相似度，但也可以是

MMSEQS_80

、

MMSEQS_70

、

MMSEQS_50

等

对于两个

bgc

节点，图可以如下所示：

bgc

节点之间的路径可以是直接的（共享完全相同的

protein

）或间接的（通过相似的蛋白质）。

现在，我想计算

bgc

节点之间的相似度得分，其定义为：

score

=

100%  * pathsAll

/ (

pathsAll + notCommon

) 哪里

• pathsAll

  是路径总数，直接和间接（上例中的 1 + 2 = 3）

• notCommon

  是不被任何路径共享的节点 (3 + 2 = 5)

• score

  是相似度得分：100% * 3 / (3 + 5) = 37.5%

对所有

bgc

对逐对计算分数，并保存为关系

(:bgc)-[:SIMILAR_TO {score: <int>})-(:bgc)

。

我已经成功通过以下查询解决了这个问题：

MATCH (bgc1:bgc)-[:ENCODING]->(p1:protein)
MATCH (bgc2:bgc)-[:ENCODING]->(p2:protein)
WHERE elementId(bgc1) < elementId(bgc2)

OPTIONAL MATCH pathIndirect = (bgc1)-[:ENCODING]->(:protein)-[:MMSEQS_90*1..5]-(:protein)<-[:ENCODING]-(bgc2)
OPTIONAL MATCH pathDirect = (bgc1)-[:ENCODING]->(:protein)<-[:ENCODING]-(bgc2)

WITH bgc1, bgc2, COUNT(DISTINCT pathIndirect) + COUNT(DISTINCT pathDirect) AS pathsAll,
              COUNT(DISTINCT p1) + COUNT(DISTINCT p2) - 2 * (COUNT(DISTINCT pathIndirect) + COUNT(DISTINCT pathDirect)) AS notCommon

WITH bgc1, bgc2, 100 * pathsAll / (pathsAll + notCommon) AS similarity_score

WITH bgc1, bgc2, similarity_score
WHERE similarity_score > 0.0  

MERGE (bgc1)-[:IS_SIMILAR {score: similarity_score}]->(bgc2)
RETURN bgc1.id AS BGC1, bgc2.id AS BGC2, similarity_score
ORDER BY similarity_score DESC, BGC1, BGC2;

结果：

╒═══════╤═══════╤════════════════╕
│BGC1   │BGC2   │similarity_score│
╞═══════╪═══════╪════════════════╡
│"BGC03"│"BGC01"│83              │
├───────┼───────┼────────────────┤
│"BGC01"│"BGC02"│37              │
├───────┼───────┼────────────────┤
│"BGC03"│"BGC02"│25              │
└───────┴───────┴────────────────┘

然而，对于大量节点（几千个），这会立即导致数据库崩溃（内存不足），从而使其无法执行（尽管内存配置合理）。

我注意到第一行可以立即执行，但是添加第二行已经足以导致崩溃（所以也许这是第一个问题？）：

// this executes instantly
MATCH rs1=(bgc1:bgc)-[:ENCODING]->(p1:protein)
RETURN rs1;
// this goes forever and crashes
MATCH rs1=(bgc1:bgc)-[:ENCODING]->(p1:protein)
MATCH rs2=(bgc2:bgc)-[:ENCODING]->(p2:protein)
RETURN rs1, rs2 

非常感谢您提供关于为什么会崩溃以及如何构建更好的查询来做同样的事情的建议。也许我在这里做了一些完全错误的事情 - 我对 Neo4j 很陌生。

示例数据：

MERGE (b1:bgc {id: 'BGC01'})
MERGE (b2:bgc {id: 'BGC02'})
MERGE (b3:bgc {id: 'BGC03'})
MERGE (p1:protein {id: 'PROT01'})
MERGE (p2:protein {id: 'PROT02'})
MERGE (p3a:protein {id: 'PROT03a'})
MERGE (p3b:protein {id: 'PROT03b'})
MERGE (p4a:protein {id: 'PROT04a'})
MERGE (p4b:protein {id: 'PROT04b'})
MERGE (p5:protein {id: 'PROT05'})
MERGE (p6:protein {id: 'PROT06'})
MERGE (p7:protein {id: 'PROT07'})
MERGE (p8:protein {id: 'PROT08'})
MERGE (b1)-[:ENCODING]->(p1)
MERGE (b1)-[:ENCODING]->(p2)
MERGE (b1)-[:ENCODING]->(p3a)
MERGE (b1)-[:ENCODING]->(p4a)
MERGE (b1)-[:ENCODING]->(p5)
MERGE (b1)-[:ENCODING]->(p6)
MERGE (b2)-[:ENCODING]->(p2)
MERGE (b2)-[:ENCODING]->(p3b)
MERGE (b2)-[:ENCODING]->(p4b)
MERGE (b2)-[:ENCODING]->(p7)
MERGE (b2)-[:ENCODING]->(p8)
MERGE (b3)-[:ENCODING]->(p1)
MERGE (b3)-[:ENCODING]->(p2)
MERGE (b3)-[:ENCODING]->(p5)
MERGE (b3)-[:ENCODING]->(p6)
MERGE (b3)-[:ENCODING]->(p4b)
MERGE (p3a)-[:MMSEQS_90]->(p3b)
MERGE (p4a)<-[:MMSEQS_90]-(p4b)

Answer 1

首先，当您连续执行两个 MATCH 语句时，您将创建一个笛卡尔积，这在 Cypher 中始终是一个危险。数据库中两个 :ENCODING 关系的每个组合的结果将是一行。如果您有 1000 个 :ENCODING 关系，您将获得 1000000 行。您可以使用 WHERE elementId(bgc1) 来限制它 < elementId(bgc2) but you will already have created the cartesian product.

所以我们需要重写它以消除这种需要。

其次我感觉 notCommon 的计算不正确。您将其基于路径的数量，而不是节点的数量。因此，它在您显示的图像中是正确的，但在您的示例数据中是正确的（至少如果我正确理解您的公式的话）。

最后，匹配两条路径：直接路径和间接路径。但在公式中，您只使用两者的总和，即所有路径。所以你并不真正关心什么是直接的和间接的。因此，我们只需要一个路径匹配，通过将 1..5 更改为 0..5 来覆盖直接和间接。这也意味着我们可以使用它作为基本 MATCH 而不是笛卡尔积。

我做了一个看起来像这样的版本。在这里，我首先计算图中蛋白质的数量，然后用它来计算 notCommon：

MATCH (p:protein)
WITH COUNT(p) AS proteinCount

MATCH pathAll = (bgc1:bgc)-[:ENCODING]->(:protein)-[:MMSEQS_90*0..5]-(:protein)<-[:ENCODING]-(bgc2:bgc)
WHERE elementId(bgc1) < elementId(bgc2)

WITH bgc1, bgc2, SUM(SIZE([n IN nodes(pathAll) WHERE "protein" IN labels(n)])) AS commonProteins, COUNT(DISTINCT pathAll) AS pathsAll, proteinCount
WITH bgc1, bgc2, pathsAll, proteinCount-commonProteins AS notCommon

WITH bgc1, bgc2, 100 * pathsAll / (pathsAll + notCommon) AS similarity_score
WHERE similarity_score > 0.0  

MERGE (bgc1)-[:IS_SIMILAR {score: similarity_score}]->(bgc2)

RETURN bgc1.id AS BGC1, bgc2.id AS BGC2, similarity_score
ORDER BY similarity_score DESC, BGC1, BGC2

我没有得到与您相同的结果，但是当我尝试手动应用公式时，我得到了与我的版本相同的结果。我可能误解了你的公式，但希望你无论如何都可以使用我版本中的一些东西。

顺便说一句，非常高兴您提供了所有 MERGE 语句来创建示例图。它使帮助您变得更容易:)