방향성 비순환 그래프(DAG)란 무엇인가요?

방향성 비순환 그래프(DAG)는 노드가 주기를 형성하지 않는 단방향 연결로 연결된 그래프 유형입니다. DAG는 종속성과 인과 관계를 설명하는 데 사용됩니다.

모든 그래프와 마찬가지로 DAG는 데이터, 작업 또는 이벤트를 나타내는 노드 간의 관계를 시각화하는 데 도움이 될 수 있습니다. 그러나 DAG는 목표를 달성하기 위해 완료해야 하는 작업 일정과 같이 이벤트가 특정 순서로 발생하는 시스템을 묘사하는 데 유용합니다.

DAG는 인과 다이어그램을 만드는 데에도 중요합니다. DAG는 일부 노드가 다른 노드에 영향을 미치지만, 그 인과 효과가 반대 방향으로는 작동하지 않는 시스템을 나타낼 수 있습니다. 이러한 단방향 관계의 기본적인 예는 가계도에서 찾을 수 있는데, DAG는 부모와 자녀의 연속적인 세대를 매핑합니다.

DAG는 컴퓨터 과학 분야 에서 흔히 사용됩니다. 개발자와 엔지니어는 데이터 파이프라인 및 데이터 처리, 신경망 아키텍처, 로보틱스 등에 DAGS를 사용합니다.

방향성 비순환 그래프가 무엇인지 더 잘 이해하기 위해 구성 요소를 분석해 보겠습니다.

노드: 정점이라고도 하는 노드는 그래프에서 엔티티, 개체 또는 변수를 나타냅니다. 일반적으로 점이나 원으로 표시됩니다.

에지: 에지는 엔티티 간의 연결을 나타냅니다. 선으로 표시됩니다.

방향 에지: 방향성 에지는 단 하나의 방향으로만 횡단할 수 있는 연결을 나타냅니다. 이러한 에지의 화살표는 방향을 나타냅니다.

방향 그래프: 방향이 지정된 에지로만 구성된 그래프를 방향 그래프 또는 디그래프라고 합니다. 반대로 방향이 지정된 에지가 없는 그래프는 무방향 그래프입니다.

콜라이더: 콜라이더는 2개의 방향 에지가 자신을 가리키는 노드입니다.

경로: 경로는 주어진 노드 하나를 다른 노드로 연결하는 일련의 에지입니다. 전적으로 방향이 지정된 에지로 구성된 경로를 방향 경로라고 합니다. 인과 관계를 나타내는 방향 경로를 인과 경로라고 합니다.

트리: 컴퓨터 과학에서 트리는 시작 노드('루트' 노드)를 제외하고 모든 노드가 하나의 방향 에지만 가리키는 방향성 비순환 그래프입니다. 에지는 루트 노드에서 확장되지만, 어떤 에지도 루트 노드를 가리키지 않습니다.

DAG의 구성 요소를 이해하는 것 외에도 DAG에 부족한 한 가지 구성 요소, 즉 주기를 인식하는 것도 중요합니다. 방향성 비순환 그래프에서 '비순환'은 이러한 그래프에 주기 또는 폐쇄 루프가 없음을 의미합니다. 즉, DAG의 1개 노드에서 시작하여 후속 노드와 에지를 통과할 때 시작 노드로 돌아가는 것은 불가능합니다.

그래프 이론(그래프에 대한 연구)에서는 방향성 비순환 그래프로 작업할 때 몇 가지 개념이나 프로세스를 적용하는 경우가 많습니다. 여기에는 다음이 포함됩니다.

• 토폴로지 정렬
• 전이적 폐쇄
• 전이적 환원

토폴로지 정렬이라고도 하는 토폴로지 정렬은 다른 노드를 가리키는 노드가 먼저 나타나고 후속 노드가 이전 노드보다 먼저 나타나지 않도록 DAG의 노드를 선형 방식으로 구성하는 방법입니다. 토폴로지 정렬 알고리즘은 DAG를 기반으로 이러한 시퀀스를 생성할 수 있습니다.¹

복잡한 그래프에서는 어떤 노드가 다른 노드에서 방향성 경로로 '도달할 수' 있는지 파악하기 어려울 수 있습니다. 전이적 폐쇄에서는 노드 간의 이러한 간접 링크가 식별되고 다이어그램으로 표시됩니다.

예를 들어, 그래프에 노드 A에서 노드 B로 향하는 방향 에지가 있고, 또 노드 B에서 노드 C로 향하는 방향 에지가 있다면, 이는 A와 C가 간접적으로 연결되어 있음을 나타냅니다. 전이적 폐쇄는 A와 C를 연결하는 새로운 방향 에지를 추가함으로써, A에서 C로의 최단 경로를 형성하게 됩니다. 이는 기존의 A→B 및 B→C 에지 외에 추가되는 것입니다. 토폴로지 정렬과 마찬가지로, 전이적 폐쇄를 계산하는 데에도 알고리즘이 사용됩니다.

전이적 환원은 전이적 폐쇄의 반대 개념으로 간주될 수 있습니다. 방향성 그래프의 맥락에서 그래프의 전이적 환원은 원래 그래프와 동일한 수의 노드를 가지며 도달 가능한 노드 쌍이 동일합니다. 그러나 그래프의 전이적 환원에서 에지의 수는 최소화됩니다.

예를 들어, 원래 그래프에 노드 A에서 노드 C로 향하는 방향 에지가 있고, 동시에 노드 A에서 노드 B, 노드 B에서 노드 C로 이어지는 방향 에지들이 포함되어 있다고 가정해보겠습니다. 이 그래프의 전이적 환원은 A와 C 사이의 에지를 제거하면서, 더 큰 변수 집합 간의 에지들—즉, A와 B, B와 C 간의 에지는 유지합니다.

즉, 원래 그래프에서 A와 C 사이의 가장 긴 경로는 새 그래프에 포함되고 에지가 1개만 있는 경로는 제거됩니다. 

방향 비순환 그래프는 다양한 사용 사례를 통해 컴퓨터 과학에서 중요한 역할을 합니다.

• 데이터 처리
• 신경망
• 머신 러닝에서의 인과 추론
• 로봇 공학
• 컴파일러 설계
• 블록체인

DAG는 데이터 엔지니어가 데이터 구조를 정의하고 데이터 흐름을 최적화하는 데 도움이 됩니다. 예를 들어 Apache Airflow와 같은 데이터 오케스트레이션 플랫폼은 DAG(Python 스크립트에서 정의됨)를 사용하여 데이터 처리 작업을 정의하고 데이터 파이프라인 및 워크플로에서 실행 순서를 지정합니다.

여러 DAG가 서로 의존하는 경우 오케스트레이션 툴은 종속성 그래프를 만들어 이러한 관계를 명확히 할 수 있습니다.² 데이터 관측성 플랫폼은 데이터 오케스트레이션 플랫폼과 함께 사용하여 데이터 파이프라인 문제를 식별하고 해결할 수 있습니다.

데이터 접근에 의존하는 생성형 인공 지능 애플리케이션의 채택이 가속화되면서 현대 기술 환경에서 데이터 파이프라인과 DAG의 중요성이 커지고 있습니다.

신경망은 생물학적 뉴런이 함께 작동하여 관찰을 하고 결론에 도달하는 방식을 모방하는 프로세스를 사용함으로써 인간의 두뇌와 유사한 방식으로 결정하는 머신 러닝 프로그램입니다. DAG는 신경망을 매핑하는 데 사용되며 특히 여러 계층으로 구성된 심층 신경망을 시각화하는 데 유용할 수 있습니다.

DAG는 인과 추론을 통해 AI 모델이 인과 관계를 인식하도록 "학습"시키는 작업에서 중요한 역할을 할 수 있습니다. 인과 추론은 인과 관계를 파악하기 위한 패러다임으로, 종종 DAG를 사용합니다. 예를 들어, DAG는 실제 인과 관계를 왜곡하거나 모호하게 만드는 변수인 '교란 변수'를 탐지하는 데 도움이 될 수 있습니다. 인과 관계 추론으로 강화된 AI는 특히 역학 분야에서 연구자들이 질병 결정 요인을 조사하는 데 도움을 줄 수 있는 툴로 부상하고 있습니다.³

연구자들은 DAG 및 대규모 언어 모델 기반 구조 계획 방법을 사용하여 듀얼 암(arm) 로봇의 성능을 개선할 것을 제안했습니다. 제안된 프레임워크에서 LLM은 복잡한 작업을 하위 작업으로 나타내는 DAG를 생성하며, 에지는 이들 간의 종속성을 나타냅니다. 프레임워크에서 이 정보는 작업 실행을 위한 두 암(arm) 간의 동작 계획 및 조정을 결정하는 데 사용됩니다.⁴

DAG는 프로그래밍 언어(소스 코드)를 컴퓨터용 명령어(머신 코드)로 변환하는 프로그램인 컴파일러의 설계를 최적화하는 데 사용됩니다. 예를 들어, DAG는 효율성을 개선하기 위해 제거할 수 있는 일반적인 하위 표현식을 식별하는 데 도움이 될 수 있습니다.

연구원들에 따르면 DAG 기반 블록체인은 기존 블록체인보다 더 나은 성능을 보여준다고 합니다. DAG 기반 블록체인은 트랜잭션의 병렬 처리를 가능하게 하여 특정 기간 동안 처리되는 트랜잭션의 비율을 높이고 더 많은 유연성과 확장성을 가능하게 합니다. 이러한 개선은 공급망 관리 및 사물인터넷 네트워크에 대한 액세스 제어와 같은 영역에 적용될 수 있습니다.^{5, 6}