💻 computer science

PathFinder: A unified approach for handling paths in graph query languages

本論文は、コンパクトなパス表現とパイプライン実行を活用することで、安定した性能を実現し、既存のグラフエンジンを桁違いに上回る性能を達成する、現代のグラフ言語におけるパスクエリ処理のための統一的かつ極めて効率的な手法であるPathFinderを紹介するものである。

原著者： Benjamín Farías, Wim Martens, Carlos Rojas, Domagoj Vrgoč

公開日 2026-07-15

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Benjamín Farías, Wim Martens, Carlos Rojas, Domagoj Vrgoč

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、**グラフ・シティ（Graph City）**と呼ばれる巨大で魔法のような街を探索していると想像してください。この街では、あらゆる人が建物（ノード）であり、彼らの間のあらゆる関係は、「フォローする」「住んでいる」「働いている」といった特定の看板が付いた道（エッジ）です。

長年、この街のツアーガイドたち（古いデータベースエンジン）には奇妙なルールがありました。もしあなたが「『フォローする』という道だけを通って、ジョーからエッフェル塔へ行く方法はすべて教えて」と頼んだら、ガイドはただ指をさして「よし、そこへ行けます！」と言って止まってしまうのです。彼らは目的地は教えてくれますが、その旅の地図は見せてくれませんでした。

これは探偵たちにとって問題です。もしあなたがミステリーを解こうとしているなら（例えば、マネーロンダリングを特定したり、噂の広まりを追跡したりする場合）、単に誰が繋がっているかを知るだけでは不十分です。その人が辿った経路全体を見る必要があります。直接そこへ行ったのか？それとも3回ほどループしたのか？あるいは近道をしたのか？

そこに登場するのが、ベンジャミン、ヴィム、カルロス、ドマゴイによって作られた、新しい超スマートなツアーガイド、PathFinderです。この論文は、単に誰が繋がっているかを教えるだけでなく、ルールがいかに複雑であっても、あらゆる可能なルートの正確な地図をあなたに手渡すことができる、最初のガイドであるPathenderを紹介しています。

「積グラフ（Product Graph）」の魔法

PathFinderは、迷路の中で迷わずにどうやってこれを行うのでしょうか？普通の街の地図と、同時に「『フォローする』という道を通り、次に別の『フォローする』通りを通り、次に『働く』通りを通らなければならない」という小さな魔法のチェックリスト（オートマトン）を持っていると想像してください。

PathFinderはただ街を歩くだけではありません。彼は、実際の街の建物と、チェックリスト上のステップを組み合わせた影の街（積グラフと呼ばれます）を構築します。

もしあなたが「ジョー」にいて、まだステップを0回踏んでいるなら、あなたは (ジョー, ステップ0) にいます。
もしあなたが「フォローする」という道を通って「ポール」へ移動したら、あなたは (ポール, ステップ1) に移動します。

この影の街を歩くことで、PathFinderはどのルートがあなたのチェックリストに一致するかを瞬時に見分けることができます。それは、許可された道路だけに明かりが灯り、それ以外の道路は無視されるGPSを持っているようなものです。

27通りの歩き方

この論文では、グラフ・シティをどのように歩くかについての27種類の異なるルール（モード）について説明しています。PathFinderは、これら27種類すべてを扱うことができる最初のエンジンです。いくつかの例を挙げます：

WALK（ウォーク）: どこへでも行けます。たとえ円を描いて歩いたり、同じ家を2回訪れたりしても構いません。（これは最も簡単ですが、無限ループにつながる可能性があります！）。
TRAIL（トレイル）: 同じ家を2回訪れることはできますが、同じ道を2回通ることはできません。
SIMPLE（シンプル）: 同じ家を2回訪れることはできません（出発地と目的地が同じ場合を除く）。これはルールを守るのが最も難しく、経路の数が爆発的に増加する可能性があります。
ANY SHORTEST（任意の最短経路）: 最も速いルートを1つだけ教えてください。
ALL SHORTEST（すべての最短経路）: 最も速いルートのすべてを教えてください。
SHORTEST k GROUPS（kグループの最短経路）: 最速のルート、次に2番目に速いグループのルート、というように、 $k$ グループ分まで教えてください。

著者らは、これらのルールの一部（例えば「シンプル」な経路を見つけること）が理論的には非常に困難であり、そのためコンピュータが巨大な地図に対して諦めてしまうことが多いことを示していますが、PathFinderは現実の世界では驚くほどうまくこれらを処理できることを示しています。

「無限ループ」問題

グラフ・シティにおける大きな悩みの一つは、もしループ（例えば、ジョーがポールをフォローし、ポールがジョーをフォローしている場合）があると、そのループを永遠に回り続けることができることです。もし「すべてのウォーク」を求めると、答えは無限になります！

これを解決するために、GQLやSQL/PGQの標準規格（これらの言語のルールブック）では、「シンプル」や「トレイル」のようなモードを選択できるようにしています。PathFinderはこれらのルールを完璧に尊重します。彼は、無限の円の中に閉じ込められないよう、いつ経路の探索を止めるべきかを正確に理解しており、同時にあなたが求めたすべての有効な経路を見つけ出します。

スピードテスト：PathFinder vs 他のエンジン

著者らは単にPathFinderを構築しただけでなく、業界の有力な名前たちと比較してテストを行いました：Neo4j, Nebula, Kuzu, Jena, Blazegraph, そして Virtuoso です。

彼らは3つのシナリオでテストを実行しました：

Pokec: 160万人の人々と言い、3000万の接続を持つ中規模のソーシャルネットワーク。
Wikidata: 3億6400万のノードと12億5700万のエッジを持つ、巨大な実世界の知識グラフ。
Diamond: 指数関数的な数の経路（具体的には $2^n$ 個の経路）を持つように数学的に構築された、トリッキーなグラフ。

結果：

スピード: PathFinderは、ほとんどのテストにおいて他のエンジンよりも10倍から100倍速かったです。
安定性: 他のエンジンが経路が長くなったり複雑になったりするとクラッシュしたりタイムアウト（断念）したりする一方で、PathFinderは力強く走り続けました。
「手に負えない」という驚き: 「シンプル」や「トレイル」のモードについては、理論上、コンピュータは答えを見つけるのに永遠に時間がかかるはずだとされています。しかし、Wikidataのような実世界のテストにおいて、PathFinderは10万個の経路を素早く見つけ出しました。著者らは、これは現実世界のデータには、数学を爆発させるような特定の「完璧な嵐」のような接続が通常存在しないためであると示唆しています。

PathFinderが（現時点では）行わないこと

この論文が主張していないことも知っておくことが重要です：

PathFinderが魔法であるとは言っていません。もしループのあるグラフですべての経路を求めれば、答えは依然として無限であり、どのコンピュータもそれを印刷することはできません。PathFinderは、あなたが設定した制限（例えば10万件の結果）で停止するだけです。
すべてのグラフに対して「シンプル」な経路の問題を解決したとは主張していません。論文では、最悪の理論的シナリオにおいては、シンプルな経路を見つけることは依然としてNP完全（計算が非常に難しいという意味の専門用語）であることを認めています。PathFinderは、単に私たちが実際に使用するグラフにおいて、他の誰よりも優れた働きをすることを示したのです。
RDF（特定のデータ形式）に対する「シンプル」モードをまだ修正したとは言っていません。著者らは、エッジに一意の名前がない場合に「トレイル」をどう定義すべきかが不明確であるため、RDFの「トレイル」モードをまだ実装していないと述べています。

結論

PathFinderは、スーパーパワーを備えたツアーガイドとして機能する新しいエンジンです。複雑なルール（例えば、「『フォローする』次に『働く』というパターンに従う、ジョーからENS Parisへのすべての経路を見つけて」）を受け取り、それらの旅の実際の地図を返すことができます。

著者らはこれを実データで測定し、PathFinderが現在のトップクラスのグラフデータベースよりも大幅に高速で安定していることを示しました。彼らは、この新機能を既存のシステム（SPARQLエンジンなど）に追加できることも示しました。数学的にはこれらのタスクのいくつかは迅速に行うことが不可能であるとされていますが、乱雑で複雑な現実の世界において、PathFinderは驚くべきスピードでそれが可能であることを証明しています。

技術要約: PathFinder: グラフクエリにおけるパスの返却

問題提起

SPARQL、Cypher、SQL/PGQ、そして台頭しつつあるGQL標準を含む現代のグラフクエリ言語は、パス・クエリに大きく依存している。SPARQLは、正規表現に一致するノード間のペアを特定するための正規パスクエリ（RPQ）をサポートしているが、エンドポイント（始点と終点）のみを返す。対照的に、Cypher、SQL/PGQ、およびGQLは、ユーザーがこれらのクエリを満たすパス全体（ウィットネス）を返せるようにしている。

しかし、これらの言語の理論的な能力と、その実用的な実装の間には大きな隔たりが存在する。現在のグラフデータベースエンジンは、GQLおよびSQL/PGQ標準で定義されている27種類のパスモードの全範囲において、パスを返すための包括的なサポートを欠いている。これらのモードには、様々な制約（例：WALK、TRAIL、SIMPLE、ACYCLIC）やセレクター（例：ANY、ALL SHORTEST、SHORTEST k、SHORTEST k GROUPS）が含まれる。既存のエンジンは以下のいずれかの状態にある：

すべてのRPQをサポートしているが、パスを返すことができない（SPARQLエンジン）。
パスを返すことはできるが、正規表現またはパスモードの限定的なサブセットのみに限定されている（Neo4j、Kuzu、Nebulaなどのプロパティグラフエンジン）。
スケーラビリティの問題に苦しみ、一致するパスの潜在的な指数関数的増加により、パス・クエリを効率的に処理できず失敗することが多い。

さらに、単純パス（simple paths）やトレイル（trails）を見つけることの理論的な複雑さはNP完全であることが知られているが、実用的な実装においては、理論的に困難なクエリであっても安定したパフォーマンスを提供することに苦慮する場合が多い。

手法

本論文では、RPQを評価し、すべてのGQLパスモードの下でパスを返すための統一フレームワークであるPATHFINDERを紹介する。このアプローチの核心は、入力グラフデータベース $G$ と、クエリの正規表現から導出された非決定性有限オートマトン（NFA） $A$ を組み合わせる直積グラフ構成にある。

コアとなるアルゴリズム原理

直積グラフ構成: フレームワークは、ノードがグラフのノード $v$ とオートマトンの状態 $q$ のペア $(v, q)$ で表される直積グラフ $G \times A$ を構築する。直積グラフのエッジは、グラフ内のエッジラベルに一致するオートマトンの遷移に対応する。
遅延構成（Lazy Construction）: 直積グラフは遅延構成される。つまり、クエリを評価するために必要な部分のみが生成されるため、検出された結果を即座に返却するパイプライン実行が可能になる。
パス多重集合表現（PMR）: アルゴリズムは、探索状態を用いて一致するすべてのパスのコンパクトな表現を維持する。探索状態には通常、現在のノード、オートマトン状態、深度、および先行する状態へのポインタが含まれ、これにより探索中にパスを明示的に保存することなく、パスの再構成が可能になる。

パスモード別の特定アルゴリズム

本論文では、異なるパスモードに対する直積グラフ探索の具体的な適応について詳述している：

WALKモード (ANY, ANY SHORTEST, ALL SHORTEST, ANY k, SHORTEST k, SHORTEST k GROUPS):
- ANY/ANY SHORTEST: 直積グラフ上で標準的なBFSまたはDFSを使用する。非決定性を扱い、エンドポイントのペアごとに単一のパスを保証するために、アルゴリズムは訪問済み状態 $(n, q)$ を追跡し、重複した返却を防ぐために ReachedFinal セットを使用する。
- ALL SHORTEST: ノードへのすべての最短パスを追跡するためにBFSを拡張する。探索状態には、最短パスをもたらすすべての先行者へのポインタのリスト（prevList）が含まれ、複数の最短パスの列挙を可能にする。
- SHORTEST k / ANY k: $k$ の制限値までの増加する長さのパスを追跡する。アルゴリズムは、終了を保証するために各状態に到達するパスのカウントを維持し、 $k$ 個の最短パスを返す。
- SHORTEST k GROUPS: 上記と同様だが、パスを長さごとにグループ化し、 $k$ 番目の異なる長さが見つかるまでのすべてのパスを返す。
制限付きモード (TRAIL, SIMPLE, ACYCLIC):
- これらのモードは、最悪の場合NP完全であることが知られている。フレームワークは、**枝刈り（pruning）**を伴う直積グラフの総当たり探索を採用している。
- isValid 関数は、パスの拡張が特定の制約（例：TRAILにおけるエッジの重複、またはSIMPLEにおけるノードの重複）に違反していないかをチェックする。
- 最悪の計算量は依然として指数関数的であるが、このアプローチは、有効なパスの数が管理可能な範囲内であることが多い実世界のグラフにおいて効率的に動作するように設計されている。

実装と統合

プロパティグラフ: オープンソースのグラフエンジンであるMillenniumDB上で実装されている。構文は、パス変数とモード（例：MATCH (src)=[MODE ?p rgx]=>(tgt)）を含むようにCypherライクなパターンを拡張している。
SPARQL拡張: パス返却をサポートするためにSPARQL構文を拡張し（例：src MODE (path AS ?p) tgt）、RDFエンジンがこれらの機能を備えることが可能であることを示している。
実行モデル: アルゴリズムはパイプライン実行のための線形イテレータを使用して実装されており、出力前にソリューションセット全体を構築する必要がなく、パスをオンザフライで返却することを保証している。

主な貢献

初の統一フレームワーク: PATHFINDERは、GQLおよびSQL/PGQ標準で規定されているすべての27種類のパスモードに対して、すべての正規パスクエリのパス返却をサポートする初のシステムである。
アルゴリズムの新規性: 非決定性オートマトンや複数の最短パスまたはパスグループの列挙といった複雑さを処理する、直積グラフ構成に基づく実装可能なアルゴリズムを提供する。
SPARQL拡張: パス・ウィットネスを返すためのSPARQLの拡張可能性を示し、RDFとプロパティグラフのクエリ能力の間のギャップを埋める。
実用的な実現可能性: 広範な実験を通じて、特定のモード（TRAILなど）における理論的な困難さがあるにもかかわらず、本アプローチが実世界のデータに対して極めて安定したパフォーマンスを発揮することを示す。

実験結果

著者らは、Pokec（ソーシャルネットワーク）、Wikidata（大規模知識グラフ）、および合成的なDiamondグラフ（指数関数的に多くのパスを持つように設計されたもの）の3つのデータセットを用いてPATHFINDERを評価した。

パフォーマンス: PATHFINDERは、一貫して最新鋭のエンジン（Neo4j, Nebula, Kuzu, Jena, Blazegraph, Virtuoso）を1桁から2桁（10倍〜100倍）上回る速度でアウトパフォームした。
スケーラビリティ:
- Pokecにおいて、他のシステムが頻繁にタイムアウトする中で、PATHFINDERはパスの長さが増加しても安定したパフォーマンスを維持した。
- Wikidataにおいて、PATHFINDERは659個の複雑なクエリを正常に処理したが、SPARQLエンジン（パスを返さないもの）は大幅に低速であり、プロパティグラフエンジン（Neo4j）は大多数のクエリでタイムアウトした。
- Diamondグラフにおいて、PATHFINDERはWALKモードに対して線形時間計算量を示したが、他のエンジンは指数関数的な成長を示した。TRAILモードについては、PATHFINDERのDFS（深さ優先探索）バリアントが、膨大な数のパスを扱う上でBFS（幅優先探索）よりも優れていることが証明された。
堅牢性: システムは、理論的に困難なクエリ（大規模グラフにおけるTRAILなど）を安定したパフォーマンスで処理し、実世界のデータ分布が最悪のケースの理論的複雑さを緩和していることを示唆した。

意義と主張

本論文は、PATHFINDERがGQL/SQL/PGQの理論的な能力と実用的な実装を統一することで、グラフクエリ処理における重要な一歩を踏み出したと主張している。

パス返却の実現可能性: 本研究は、複雑なRPQに対してフルパス・ウィットネスを返すことが、単に理論的に可能であるだけでなく、実用的に効率的であることを証明している。
標準への準拠: GQL標準の27種類のパスモードを完全にサポートする初のエンジンであり、現在のデータベース技術における重要なギャップを解消している。
拡張性: MillenniumDBへの統合成功とSPARQLの拡張は、これらのアルゴリズムが、基礎となるエンジンを完全に書き換えることなく、既存のデータベース・パイプラインに組み込めることを示している。
控えめな将来展望: 著者らは、現在の実装は標準的なRPQを扱うものであるが、ノードおよびエッジのデータプロパティを含むより表現力豊かなクエリの検討や、パス返却のセマンティクスがSPARQLの特定のプロパティパス構文とどのように統合されるかについてのさらなる調査が必要であると述べている。

結論として、PATHFINDERは、パスを返すクエリに関する健全かつ高性能な戦略を提供しており、そのような機能がスケーラビリティを犠牲にしたり、クエリ言語の表現力を制限したりしなければならないという概念に異を唱えている。