有向非巡回グラフ（DAG）とは

有向非巡回グラフ（DAG）とはグラフの一種で、ノードが一方向で接続され、循環しないものを指します。DAGは、依存関係と因果関係を示すために使用されます。

すべてのグラフと同様に、DAGは、データ、タスク、またはイベントを表すノード間の関係を視覚化するのに役立ちます。ただし、DAGは、目標を達成するために完了する必要があるタスクのスケジュールなど、イベントが特定の順序で発生するシステムを描写するのに役立ちます。

DAGは因果関係図を作成する上でも重要です。DAGは、一部のノードが他のノードに影響を与えますが、因果効果は逆方向には作用しないシステムを表現することができます。このような一方向の関係の基本的な例は、DAGが親と子の連続した世代をマップする家系図に見られます。

DAGの利用はコンピューター・サイエンスでは一般的であり、開発者やエンジニアはデータ・パイプラインやデータ処理、ニューラル・ネットワーク・アーキテクチャー、ロボティクスなどにDAGを利用しています。

有向非巡回グラフとは何かをよりよく理解するために、その構成要素を分解して説明します。

ノード：ノード（頂点とも呼ばれます）は、グラフ上のエンティティー、オブジェクト、または変数を表します。通常は点または円として表されます。

エッジ：エッジはエンティティー間の接続を表します。線として描かれます。

有向エッジ：有向エッジは、一方向にのみ向かうことができる接続を表します。このエッジの矢印は、その方向を示しています。

有向グラフ：完全に有向エッジで構成されたグラフは、有向グラフまたは有向グラフです。対照的に、有向エッジのないグラフは無向グラフと呼ばれます。

合流点：合流点とは、2つの有向エッジが指しているノードのことです。

経路：経路とは、あるノードを別のノードに接続している一連のエッジのことです。有向エッジのみで構成される経路は、有向経路と呼ばれます。因果関係を示す有向経路は、因果経路と呼ばれます。

ツリー：コンピューター・サイエンスにおいて、ツリーとは、開始ノード（「ルート」ノード）を除き、すべてのノードを指す有向エッジが1つだけある有向非巡回グラフです。エッジはルート・ノードから伸びますが、ルート・ノードを指すエッジはありません。

DAGのパーツを理解することに加えて、もう1つの構成要素、すなわちサイクルを認識することも重要です。有向非巡回グラフの「非巡回」とは、これらのグラフにサイクルすなわち閉ループがないことを指します。つまり、DAGの1つのノードから開始し、続くノードとエッジに移動すると、開始ノードに戻ることは不可能です。

グラフ理論（グラフの研究）では、有向非巡回グラフを操作するときに、次のような概念またはプロセスが適用されることがよくあります。

• トポロジカル・ソート
• 推移閉包
• 推移還元

トポロジカル・ソート（トポロジカル順序付けとも呼ばれる）は、他のノードを指すノードが最初に表示され、後続のノードが先行ノードの前に表示されないように、DAGのノードを線形に整理する方法です。トポロジカル・ソート・アルゴリズムは、DAGに基づいてこのようなシーケンスを生成できます。¹

複雑なグラフでは、どのノードが他のノードからの有向パスによって「到達可能」であるかを認識することが困難な場合があります。推移閉包では、ノード間のこのような間接的なリンクが識別され、図表化されます。

例えば、あるグラフにノードAとノードBを結ぶ有向エッジがあり、ノードBとノードCを結ぶ別の有向エッジがある場合、AとCは間接的にリンクしていることになります。推移閉包は、AとB、およびBとCとの元の有向エッジに加えて、AとCの2つのノードをつなぐ最短経路である、新しい有向エッジとなります。トポロジカル・ソートと同様、推移閉包の計算にもアルゴリズムを使用できます。

推移還元は推移閉包の反対と考えることができます。有向グラフのコンテキストでは、グラフの推移縮小には元のグラフと同じ数のノードが含まれ、到達可能なノードのペアは同じになります。ただし、グラフの推移縮小におけるエッジの数は最小限に抑えられます。

例えば、ノードAからノードCにリンクする有向エッジと、ノードAをノードBに、ノードBをノードCにリンクする一連の有向エッジを含む元のグラフを考えてみましょう。そのグラフの推移還元では、AとCとの間のエッジが除外され、より大きな変数のセット（AとB、BとC）間にあるエッジは維持されます。

つまり、元のグラフの「A」と「C」間の最長パスが新しいグラフに含まれ、エッジが1つだけのパスは削除されます。

有向非巡回グラフは、さまざまなユースケースを通じてコンピューター・サイエンスの分野で重要な役割を果たします。

• データ処理
• ニューラル・ネットワーク
• 機械学習における因果推論
• ロボティクス
• コンパイラーの設計
• ブロックチェーン

DAGは、データエンジニアがデータ構造を定義し、データ・フローの最適化を実現するために役立ちます。例えば、 Apache Airflowなどのデータ・オーケストレーション・プラットフォームは、（Pythonスクリプトで定義された）DAGを使用してデータ処理タスクを定義し、データ・パイプラインおよびワークフローにおける実行順序を指定します。

複数のDAGが相互に依存している場合、オーケストレーション・ツールは依存関係グラフを作成してそれらの関係を明確にすることができます。²データ観測プラットフォームは、データ・オーケストレーション・プラットフォームと組み合わせて使用することで、データ・パイプラインの問題を特定し、対処することができます。

データ・アクセスに依存する生成人工知能アプリケーションの導入が加速し、現代のテクノロジー環境におけるデータ・パイプラインとDAGの重要性が高まっています。

ニューラル・ネットワークは、生物学的ニューロンが連携して観察を行い結論を導き出す方法を模倣したプロセスを使用して、人間の脳と同様の方法で決定を下す機械学習プログラムです。DAGはニューラル・ネットワークをマッピングするために使用され、複数の層を持つディープ・ニューラル・ネットワークの視覚化に特に役立ちます。

DAGは、因果推論を通じてAIモデルに因果関係を認識させるように「教える」取り組みにおいて役割を果たすことができます。因果推論は因果効果を決定するためのパラダイムであり、多くの場合DAGが使用されます。例えば、DAGは、実際の因果関係を歪めたり不明瞭にしたりする変数である「交絡因子」を検知するのに役立ちます。因果推論機能が強化されたAIは、特に疫学の分野でツールとして登場しており、研究者による疾患の決定要因の調査に役立つ可能性があります。³

研究者らは、DAGと大規模言語モデルに基づく構造計画手法を使用して双腕ロボットのパフォーマンスを向上させることを提案しました。提案されたフレームワークでは、LLMは、複雑なタスクをサブタスクとして表すDAGを生成し、エッジはそれらの間の依存関係を示します。フレームワークでは、この情報は、タスク実行のための2本の腕の動作計画と調整を決定するために使用されます。⁴

DAGは、プログラミング言語（ソースコード）をコンピューターの命令（マシン・コード）に変換するプログラムであるコンパイラーの設計を最適化するために使用されます。例えば、DAGは、効率性を向上させるために削除できる共通の部分式を識別するのに役立ちます。

研究者によると、DAGに基づくブロックチェーンは、従来のブロックチェーンよりも優れた性能を示しています。DAGに基づくブロックチェーンは、トランザクションの並列処理を可能にすることで、一定期間内に処理されるトランザクションの割合を高め、より柔軟で拡張性の高い処理を可能にします。このような改善は、サプライチェーン管理やモノのインターネット・ネットワークのアクセス制御などの分野に応用できます。^5、6