Rohin Aryaは、人物検索エンジンのClado（YC X25）のチーフサイエンティストおよび創業エンジニアである。
グラフは至るところに存在している。テクノロジーから金融まで、人物、ネットワーク、生物学的経路など、価値ある情報をモデル化することが多い。これらのグラフは数十億、数兆の個別ノードで構成されることがあるため、科学者やテクノロジストはより良い探索方法を考案する必要がある。賢明なグラフ探索とは、すべてのノードを訪問することではなく、どの経路を探索し、いつ停止するかを知ることである。
JaimyとCladoでの私の経験を通じて、大規模言語モデル（LLM）に基づくグラフアルゴリズムの研究とプロトタイピングを多く行ってきた。その研究結果に基づき、複雑な関係ネットワークをナビゲートできるエージェントの活用方法を紹介する。
課題
従来の幅優先探索（BFS）や深さ優先探索（DFS）などのグラフ探索アルゴリズムは、体系的だが盲目的に探索する。これにより規模の問題が現実のものとなる。一般的な知識グラフでは、各ノードが平均10〜20の接続を持つことがある。盲目的な探索では、求めているものを見つける前に、何千もの無関係なノードを探索する可能性がある。深さ制限を設けたとしても、可能性の数の多さから網羅的な探索は現実的ではない。
関連性の問題も同様に難しい。すべての関係が同等に作られているわけではない。「WORKS_WITH（一緒に働く）」という接続は、組織に関するクエリでは非常に関連性が高いかもしれないが、個人の興味を探す場合には完全に無関係かもしれない。
エージェントのアーキテクチャ
グラフ探索エージェントには3つの基本操作が必要である。まず、任意のノードに関するメタデータを取得できなければならない。次に、すべての隣接ノードとそれらを接続する関係タイプをリストアップする必要がある。第三に、エージェントは特定の隣接ノードに関する詳細情報を取得する必要がある。これらの操作がインテリジェントな探索の基盤を形成する。
重要なステップは、探索するノードの優先順位付けである。以下を組み合わせた関連性スコアリング関数を使用する：
• クエリとの意味的類似性（コサイン類似度または高性能な代替手段）
• 接続性（ノードの接続の良さ）
• 開始点からの距離
スコアリング関数の例：R(node) = α × 意味的スコア + β × 接続性 + γ × 距離係数
実際には、この式は関連性を意味的類似性＋接続性＋距離として計算することを意味する。α、β、γは、特定のアプリケーションやクエリのニーズに応じて、一つの要素を他の要素よりも強調するために調整できる重みである。
この実験を行った際、リストアップされた各ノードに対して1文の自然言語による説明を含めることが、探索エージェントがノードについて推論するのに役立つことがわかった。
スマートな探索戦略
ランダムに探索するのではなく、エージェントは以下を行うべきである：
1. 初期検索結果からのノードから開始する。
2. 関連性関数を使用して、すべての直接の隣接ノードにスコアを付ける。
3. 最も高いスコアの隣接ノードを最初に探索する。
4. この処理を深さ制限付きで再帰的に適用する。
基礎となるグラフによっては、サイクルをインテリジェントに処理する必要もある。ソーシャルネットワークでは相互関係が一般的であり、エージェントがループに陥ることは避けたい。訪問済みのセットを維持するが、大幅に異なる経路を通じて同じノードに到達した場合は、再訪問する価値があるかもしれないことを考慮する。
終了条件
いつ停止するかを知ることが重要である。エージェントは、クエリ満足度のしきい値または最大反復回数に達した場合、あるいは新しい高価値ノードが発見されなくなった場合に終了すべきである。これにより、無限の探索を防ぎながら、関連領域の包括的なカバレッジを確保できる。満足度のしきい値は特に微妙である。関連する結果の最小数を見つけること、特定の信頼レベルに達すること、またはすべての高スコアパスを使い果たすことと定義できる。異なるクエリには異なる停止基準が必要かもしれない。
現代のLLMは、探索を停止してユーザーに戻るタイミングを判断することが非常に得意である。探索エージェントのシステムプロンプトに一連の終了条件を含めるだけで、これを簡単に活用できる。
実世界での実装
このアプローチは、openCypherグラフクエリと従来のSQL操作を組み合わせることができるPostgreSQL上のApache AGEで特によく機能する。関係タイプについては、エージェントが推論できる明確なエッジラベル（例：FRIENDS_WITH、WORKS_AT、CREATEDなど）を定義する。理想的な世界では、クエリのコンテキストに応じて異なる関係タイプに異なる重みを持たせるべきだが、これはクエリのバリエーションが少ない場合にのみ有用であることが多い。
一部のエッジタイプが他のタイプよりも一般的である関係階層の実装を検討する。これにより、特定の関係が結果をもたらさない場合に、エージェントがより広い関係カテゴリにフォールバックできるようになる。
パフォーマンスに関する考慮事項
グラフ探索はコストがかかる場合がある。データベース接続を効率的に管理するためにコネクションプーリングを使用し、冗長な検索を避けるためにノード情報をキャッシュすることを検討する。
エージェントは、同時に探索しているアクティブなパスの数を制限するためにビームサーチなどの戦略を実装する必要があるかもしれない。そして確実にデータベースインデックスを使用すること—私はしばしば、高速であるはずのクエリがなぜそれほど時間がかかるのか、長い間疑問に思っていた。
結論
グラフ探索エージェントは、徹底的な探索とインテリジェントな優先順位付けのバランスを取ることで、複雑な関係ネットワークをナビゲート可能な知識空間に変えることができる。これにより、無駄な探索に迷うことなく、関連するすべてのものを見つけることができる。そして本当に見識のあるシステムは、異なるクエリタイプに対してどの探索戦略が機能するかを追跡するフィードバックループを実装し、エージェントが時間とともに関連性スコアリングとパス選択を継続的に改良できるようにする。
