ナレッジグラフをNeo4jに載せて4つ問う

ノード 1,050・エッジ 2,261 のグラフを Neo4j に投入して、クエリを4本書きました。投入は 0.6 秒、ヒープは 512MB で足ります。

大きなマシンは要りません。この規模なら手元のノートPCで動きます。そして書けるようになるのは、段数を先に決めなくていいクエリです。表との差はここに出ます。

立てる

Docker で 1 コンテナです。

docker run -d --name kg-neo4j -p 7474:7474 -p 7687:7687 \
  -e NEO4J_AUTH="neo4j/<パスワード>" \
  -e NEO4J_server_memory_heap_initial__size=512m \
  -e NEO4J_server_memory_heap_max__size=512m \
  -e NEO4J_server_memory_pagecache_size=256m \
  neo4j:5-community

ヒープを明示的に絞っています。指定しないと Neo4j は搭載メモリから自動で決めるので、他のものが動いているマシンでは取りすぎます。1,050 ノードに 512MB は過剰なくらいです。

7474 がブラウザ、7687 が Bolt (プログラムからの接続) です。

載せる

ノードは Item 1種類、エッジは INGREDIENT_OF 1種類だけにしました。種類を増やすのは、1種類で答えられない問いが出てからで間に合います。

s.run("CREATE CONSTRAINT item_name IF NOT EXISTS "
      "FOR (i:Item) REQUIRE i.name IS UNIQUE")

s.run("UNWIND $rows AS r MERGE (i:Item {name: r.name}) "
      "SET i.display_name = r.display, i.craftable = r.craftable, "
      "    i.unambiguous = r.unambiguous", rows=rows)

s.run("UNWIND $rows AS r "
      "MATCH (a:Item {name: r.src}), (b:Item {name: r.dst}) "
      "MERGE (a)-[:INGREDIENT_OF]->(b)", rows=edges)

3点だけ補足します。

制約を先に張る。 name に一意制約を付けておくと、MERGE が索引を使うので投入が速くなります。付けないと全走査になります。

UNWIND でまとめて渡す。 1行ずつ run を呼ぶと往復のオーバーヘッドが支配的になります。リストごと渡して Cypher 側で展開します。

CREATE ではなく MERGE。 同じスクリプトを2回流しても増えません。更新の設計をここで先に決めておきます。

unambiguous という属性を付けているのは、前の章で外した曖昧なアイテムを、消さずに印を付けて載せているからです。無いことと分からないことを、同じ表示にしないためです。

問い1: 段数を書かずに原材料まで辿る

MATCH p = (leaf:Item)-[:INGREDIENT_OF*]->(t:Item {name: 'polished_andesite_stairs'})
WHERE NOT (:Item)-[:INGREDIENT_OF]->(leaf)
RETURN DISTINCT leaf.name AS raw, min(length(p)) AS hops ORDER BY raw

raw          hops
cobblestone  3
quartz       4

INGREDIENT_OF* のアスタリスクが、この章の主役です。 何段辿るかを書いていません。WHERE NOT (:Item)-[:INGREDIENT_OF]->(leaf) が「そのノードに入ってくるエッジが無い」つまり行き止まりを表していて、行き止まりに当たるまで辿れと言っています。

表で同じことをするなら、JOIN を何回書くかを先に決める必要があります。段数が対象ごとに違うので、そのままでは書けません。

問い2: これが無くなると何が作れなくなるか

MATCH (x:Item {name: 'quartz'})-[:INGREDIENT_OF*1..4]->(d:Item)
RETURN count(DISTINCT d) AS affected

affected
30

方向が逆になっただけです。エッジを逆向きに辿ると影響範囲になります。 同じグラフ、同じエッジで、「何が要るか」と「何に効くか」の両方に答えられます。

ここでは *1..4 と上限を書いています。実運用では必ず上限を書いてください。 上限のない * は探索が発散するので、ノードが数万を超えるあたりから返ってこなくなります。

問い3: 解決できないものが何件あるか

MATCH (i:Item) WHERE i.craftable AND NOT i.unambiguous
RETURN count(i) AS ambiguous

ambiguous
496

グラフ自身に「ここは分からない」を数えさせています。 曖昧なものを消していたら、この問いは書けません。496 件という数字が出てくること自体が、データの状態の報告になります。

問い4: 最も広く効いている原材料は何か

MATCH (leaf:Item)-[:INGREDIENT_OF*1..5]->(d:Item)
WHERE NOT (:Item)-[:INGREDIENT_OF]->(leaf)
RETURN leaf.name AS raw, count(DISTINCT d) AS reaches ORDER BY reaches DESC LIMIT 5

raw            reaches
bamboo         192
pale_oak_log   190
birch_log      189
acacia_log     189
cherry_log     189

これは元データを眺めていても出てきません。グラフ全体を横断して初めて出る数字です。1つの原材料が5ホップ以内に届く範囲を数えています。

Cypher で書けなかったこと

正直に書いておくと、全部が Cypher のほうが素直だったわけではありません。

循環の除外は、Python 側のほうが書きやすかったです。「探索中のスタックに載っているノードを要求する枝を外す」という条件を Cypher で表現するのは、再帰関数で書くより手数がかかります。Neo4j 側では、循環を含むノードを最初から除いたうえで投入する形にしました。

一般化すると、構築時の判断はプログラム側、問い合わせはグラフDB側という分担になります。グラフDB は「決まったグラフを速く辿る」道具であって、「何をグラフにするか決める」道具ではありません。

残っているのは更新

ここまでで、作って、載せて、辿るところまでが一通り通りました。この形のまま置いておくと、確実に古くなります。

元データが新しいバージョンになったとき、グラフをどう作り直すか。全部消して入れ直すのか、それとも差分だけ当てるのか。4つの型の比較で「更新の自動化が一番効く軸」と書いたのは、ここのことです。

そして更新が止まったグラフは、間違った答えを自信を持って返すようになります。 空のグラフより古いグラフのほうが危険で、しかも危険であることが表に出ません。このシリーズでは、まだ測っていません。 更新を止めたグラフがどのくらいの速さで実態からずれるかは、時間を置かないと分からないためです。

シリーズの全体像と、各章の検証状態は入口のページにまとめてあります。

---

Minecraft は Mojang Synergies AB の商標です。このページは Mojang Studios および Microsoft とは無関係で、承認も後援も受けていません。クラフトデータは PrismarineJS/minecraft-data から取得しています。