cypher-direction-competition で優勝🥇

2023-10-07

9月17日に終了した cypher-direction-competition という超小規模コンペで優勝して €1,500 を獲得した。そして優勝したコードが langchain に組み込まれた。斬新なアルゴリズムなどは使っておらず、技術的に何か凄いことをしたわけではないが、意識したことはいくつかあるのでその辺りについて書こうかと。コンペの内容に関する詳細は、主催者の Tomaz Bratanic さんの Medium に記載されているので、気になる方は直接そちらを確認すると良い。

コンペの背景と概要

昨今 LLM を用いた RAG（Retrieval Augmented Generation, 検索拡張生成）が注目されている。 retrieve する外部知識の蓄積場所の一つとして Neo4j 内に構築されたナレッジグラフが挙げられるが、質問文を入力として Neo4j から答えを得るには、自然言語から cypher クエリを生成（= text2cypher）する必要がある。 Neo4j 内に定義した relation type や node label（= スキーマ）を添え、質問文を cypher クエリに変換させるプロンプトを ChatGPT に投げれば良いと思うだろうが、案外そう上手くはいかない。何が上手くいかないかというと、想定されていないリレーションの type・向きで cypher クエリが生成されてしまうケースが割と多く発生する。そこで欲しくなってくるのが、生成された cypher クエリをスキーマに適合するように post-processing で修正するようなアルゴリズム。 cypher-direction-competition ではこのアルゴリズムの開発がお題だった。

コンペのルール

詳細はコンペのリポジトリに記載されているので、本投稿では要点のみ記載する。

期間

2023 年 8 月 11 日〜 2023 年 9月 17日

内容

以下の入力、出力を伴うアルゴリズムの実装。

入力: cypher クエリとスキーマ出力: スキーマに適合するように修正した cypher クエリ

要は、cypher クエリ内に記述されているパスの中に想定されていない label、type 及び両者の組み合わせがないかを確認し、修正できるのであればクエリの内容を修正するということ。

例えば、以下のようなスキーマが想定されており、MATCH (movie:Movie)-[:ACTED_IN]->(person:Person) RETURN movie というクエリが入力されたとする。

スキーマによれば、:Movie が :Person に :ACTED_IN しているケースは想定されておらず、このクエリは誤りであると判断できる。しかし逆に :Person が :ACTED_IN している :Movie はスキーマに存在する。したがって、relation の向きを逆にした以下のクエリに修正できれば正解になる。

MATCH (movie:Movie)<-[:ACTED_IN]-(person:Person) RETURN movie

ルールベースで容易に対応可能なタスクである。

評価方法

以下の4項目の総合評価。

評価項目

精度
シンプルさ
可読性
パフォーマンス

各項目を具体的にどう評価するか、どれだけ重視するといった方針は特に記載がなかった。（Kaggle のコンペに慣れている自分としては、定量指標が存在しないのはどうなんだという気持ちはあった。）

制限事項

できれば Python を使用。一応他の言語でも可。
外部ライブラリやツールの利用禁止。言語に標準組み込みされたライブラリのみ利用可能。唯一の例外として Cypher の AST parser は利用可。

取り組み方

最初に、どの評価項目で他の参加者と差をつけられるかを考えた。タスクの内容から全参加者が精度 100% で提出することは確実だと思っていたので、精度で差は付かないと考えた。一方パフォーマンスについては当然差が付くと考えた。しかし明記はされていないものの、パフォーマンスは主催者がそこまで重視していない観点ではないかと推察した。何故なら、パフォーマンスを重視するのであれば、わざわざ Python を推奨しないと考えられるため。飽くまでも処理に時間が掛かり過ぎる場合に評価を下げられる程度の消極的要件であると仮定した。従って、残るシンプルさと可読性で差を付けるべきだと判断した。

シンプルさ

可読性にも共通することだが、リーダブルコードに記載されているような点をただ意識しただけ。例えば、

一関数に一つのビジネスロジックを記述する。
過剰なモジュール分割、クラス設計は行わない。ことを意識した。

1 点目は記載の通り、且つよく言われていることだと思うのでここではスルー。 2 点目で具体的に行ったことの一つには namedtuple の使用が挙げられる。知っている人からすれば特に目新しいものではないが、周りに使っている人があまりいないので簡潔に紹介すると、namedtuple は、tuple の各フィールドに名前を付けられる仕組み。例えば以下のように :Person という namedtuple を定義すれば、age というフィールド名を指定して値を取得できるようになる。

from collections import namedtuple

Person = namedtuple('Person', ['name', 'age'])
person = Person('Jack', 24)
person.age

勿論 :Person の class を定義しても、person.age のような形でフィールドにアクセスできるようにはできるが、明らかにコード量が増える。構造化して整理した方が分かりやすい概念（前記の例だと :Person）について、その概念が持つべき関数（例えば、購入を意味する buy 関数など）を定義する必要がなく、またその概念が持つフィールドの値（age）が書き変わることが想定されないのであれば、namedtuple は最もコード量を抑えつつ可読性を担保できる手段だと思う。

可読性

コードの可読性もさることながら、コードを読む前にアルゴリズムの概要を簡潔に記載することで、読み手がコードを読み始めやすくするように心掛けた。具体的には以下の 2 点を行った。

コードを読ませる前に README でアルゴリズムの概要を記載
アルゴリズムの使い方を示す notebook の作成自分自身、普段利用したいライブラリなどがあれば、README を読んだ上で利用し始める習慣があるので、特に README には丁寧な説明を記載した。（最初はアルゴリズムの図解なども用意しようかと思ったが、そんなに難解な仕組みでもないしかえって余計かなぁと思い、結局図解はやめた。）

また、実際にどのようにアルゴリズムを利用できるか、どの程度の精度か、どの程度の処理時間が掛かるのかについても、具体例があれば分かりやすいだろうと思い、デモ用の notebook を作成した。正直このぐらいは参加者のほとんどがやるだろうと思っていたが、案外そうでもなかった。確認した限りでは一番ドキュメント類を充実させてた気がするので、もしかしたらここで差がついたのかも？

実装したアルゴリズム

冒頭に記載した通り、アルゴリズムの内容自体に特筆すべき点はないが、成果物の中心となるものなので一応触れる。アルゴリズムの処理の流れは概ね以下の 4 ステップ。

宣言された変数と node label, relation type の対応を検出
パスの検出
パスから node - relation - node という形の部分パスを検出
検出した部分パスごとにスキーマとの適合性を評価・修正

以下では前掲のスキーマ例と以下のサンプルクエリを用いて大まかなアルゴリズムの挙動を記載する。

MATCH (p1:Person)-[:DIRECTED]->(m:Movie)<-[:WROTE]-(p1)
MATCH (p2:Person)<-[:ACTED_IN]-(m)
RETURN p2

ちなみにこのクエリは「ある人が脚本とディレクターを同時に務めた映画が出演した人物は？」という質問に対する答えを得たい時のクエリ。（普通に考えてもおかしいが、）映画が人物に出演するというのはスキーマに照らして誤り。アルゴリズムはこれを自動で修正する。

なお、検出とか抽出とか表現している部分はすべて正規表現芸で実現したが、使用したパターンについて解説するのはつまらないので割愛する。以下では、飽くまでもアルゴリズムの流れについてのみ記載する。

1. 変数と対応する label, type

クエリ内で宣言されている変数を検出し、その変数に対して指定されている label, type が何であるかを辞書化する。

key	value
p1	[Person]
m	[Movie]
p2	[Person]

2. パスの検出

クエリ内に記述されているパスをすべて検出する。例では以下の 2 つのパスが検出される。

(p1:Person)-[:DIRECTED]->(m: Movie)<-[:WROTE]-(p1)
(p2:Person)<-[:ACTED_IN]-(m)

3. 部分パスの検出

検出したパスを node-relation-node の部分パスにさらに分解する。この時、1 ノードずつずらして部分パスを生成していく。従って、n 個目の部分パスの右端のノードと n+1 個目の左端のノードは同一にな。

(p1:Person)-[:DIRECTED]->(m: Movie)<-[:WROTE]-(p1)から 2 つの部分パスを抽出
- (p1:Person)-[:DIRECTED]->(m: Movie)
- (m:Movie)<-[:WROTE]-(p1)
(p2:Person)<-[:ACTED_IN]-(m) から 1 つの部分パスを抽出
- (p2:Person)<-[:ACTED_IN]-(m)

4. スキーマとの比較

抽出した部分パスごとにスキーマへの適合性を評価する。部分パス内で変数が使用されている場合は「1. 」で構築した辞書から label, type を特定して評価する。

(p1:Person)-[:DIRECTED]->(m:Movie) → :Person が :Movie を :DIRECTED するスキーマは存在する。これは正しい部分パス。
(m:Movie)<-[:WROTE]-(p1) → 辞書によれば、p1 は :Person label。 → :Person が Movie を :WROTE するスキーマは存在する。これは正しい部分パス。

目次