O que é DAG (directed acyclic graph)?

Como todos os gráficos, os DAGs podem ser úteis para ver as relações entre os nós que representam dados, tarefas ou eventos. No entanto, os DAGs são úteis para representar sistemas onde os eventos ocorrem em uma ordem específica, como um cronograma de tarefas que devem ser concluídas para atingir uma meta.

Os DAGs também são importantes na criação de diagramas causais: os DAGs podem representar sistemas em que alguns nós afetam outros nós, mas os efeitos causais não funcionam na direção oposta. Um exemplo básico de tais relações unidirecionais pode ser encontrado em árvores genealógicas, pois os DAGs associam gerações sucessivas de pais e filhos.

A aplicação de DAGs é comum na ciência da computação, com desenvolvedores e engenheiros utilizando DAGS para pipelines de dados e processamento de dados, arquitetura de redes neurais, robótica e outros.

Para entender melhor o que é um grafo acíclico direcionado, vamos detalhar seus componentes:

Nós: os nós, também conhecidos como vértices, representam entidades, objetos ou variáveis em um gráfico. Eles são geralmente descritos como pontos ou círculos.

Arestas: as arestas representam conexões entre entidades. São representadas por linhas.

Arestas direcionadas: Arestas direcionadas representam conexões que podem ser percorridas em somente uma direção. As setas dessas arestas indicam sua direção.

Gráficos direcionados: Os gráficos compostos inteiramente de arestas direcionadas são grafos direcionados ou digrafos. Por outro lado, os gráficos sem arestas direcionadas são grafos não direcionados.

Colisores: colisores são vértices com duas arestas direcionadas apontando para eles.

Caminhos: caminhos são uma sequência de arestas que conectam um determinado vértice a outro. Caminhos que consistem inteiramente em arestas direcionadas são conhecidos como caminhos direcionados. Os caminhos direcionados que indicam relações causais são chamados de caminhos causais.

Árvore: em ciência da computação, uma árvore é um grafo acíclico direcionado no qual cada nó tem apenas 1 edge direcionada apontando para ele, exceto pelo nó inicial (o nó “raiz”). Enquanto as bordas se estendem do nó raiz, nenhuma borda aponta para o nó raiz.

Além de entender as partes de um DAG, também é importante reconhecer um componente que falta: um ciclo. O "acíclico" do grafo acíclico direcionado refere-se à ausência de ciclos ou circuitos fechados nesses gráficos. Em outras palavras, ao iniciar em um vértice de um DAG e percorrer os vértices e as arestas subsequentes, é impossível retornar ao vértice inicial.

Na teoria dos grafos (o estudo dos grafos), vários conceitos ou processos são frequentemente aplicados ao trabalhar com grafos acíclicos direcionados. São eles:

• Classificação topológica
• Encerramento transitório
• Redução transitória

Uma classificação topológica, também conhecida como ordenação topológica, é uma forma de organizar os nós de um DAG de forma linear, de modo que os nós que apontam para outros nós apareçam primeiro e os sucessores não apareçam antes de seus antecessores. Algoritmos de classificação topológica podem produzir tais sequências com base em DAGs.¹

Em grafos complicados, pode ser um desafio reconhecer quais nós podem ser alcançáveis por caminhos direcionados de outros nós. No fechamento transitivo, tais ligações indiretas entre nós são identificadas e diagramadas.

Por exemplo, se um gráfico tem um nó A de vinculação de borda direcionada e nó B e outro nó B de vinculação de borda direcionada, isso indicaria que A e C estão vinculados indiretamente. Um fechamento transitivo resultaria em uma nova edge conectando A a C, agora o caminho mais curto entre esses dois vértices, além das arestas direcionadas originais entre A e B e B e C. Assim como na classificação topológica, podem ser usados algoritmos para cálculos de fechamento transitivo.

A redução transitiva pode ser considerada o oposto do fechamento transitivo. No contexto de um grafo direcionado, a redução transitiva do grafo tem o mesmo número de vértices que o grafo original e os pares de vértices que são alcançáveis são os mesmos. No entanto, o número de arestas na redução transitiva do grafo é minimizado.

Considere, por exemplo, um grafo original contendo uma aresta direcionada ligando o vértice A ao vértice C, e uma sequência de arestas direcionadas ligando o vértice A ao vértice B e o vértice B ao vértice C. Uma redução transitiva desse gráfico excluiria a aresta entre A e C, mantendo as arestas entre o conjunto maior de variáveis: A e B e B e C.

Em outras palavras, o caminho mais longo entre A e C no grafo original é incluído no novo grafo, enquanto o caminho com apenas uma aresta é eliminado. 

Os gráficos acíclicos direcionados ocupam um lugar de destaque na ciência da computação por meio de uma série de casos de uso:

• Processamento de dados
• Redes neurais
• Inferência causal em aprendizado de máquina
• Robótica
• Projeto de compiladores
• Blockchain

Os DAGs ajudam os engenheiros de dados a definirem estruturas de dados e otimizar os fluxos de dados. Plataformas de orquestração de dados como o Apache Airflow, por exemplo, utilizam DAGs (definidos em scripts Python) para definir tarefas de processamento de dados e especificar sua ordem de execução em pipelines de dados e fluxos de trabalho.

Nos casos em que vários DAGs dependem uns dos outros, as ferramentas de orquestração podem criar grafos de dependência para esclarecer essas relações.² Plataformas de observabilidade de dados podem ser usadas com plataformas de orquestração de dados para identificar e lidar com problemas de pipeline de dados.

A aceleração da adoção de aplicativos de inteligência artificial generativa, que dependem do acesso a dados, ampliou a importância dos pipelines de dados e dos DAGs no cenário tecnológico moderno.

Uma Neural Network é um programa de aprendizado de máquina que decide de maneira semelhante ao cérebro humano, utilizando processos que imitam a maneira como os neurônios biológicos trabalham juntos para fazer observações e chegar a conclusões. Os DAGs são usados para mapear redes neurais e podem ser especialmente úteis na visualização de redes neurais profundas com várias camadas.

Os DAGs podem desempenhar um papel nos esforços para “ensinar” os modelos de IA a reconhecer relações causais por meio de inferência causal. A inferência causal é um paradigma para determinar os efeitos causais e frequentemente emprega DAGs. Por exemplo, os DAGs podem ajudar a detectar “fatores de confusão”, que são variáveis que distorcem ou obscurecem a causalidade real. A IA aprimorada com inferência causal está surgindo como uma ferramenta especialmente na epidemiologia, com potencial para ajudar os pesquisadores em suas investigações sobre os determinantes de doenças^.3

Os pesquisadores propuseram o uso de um método de planejamento estrutural baseado em DAG e grandes modelos de linguagem para melhorar o desempenho de robôs com dois braços. No framework proposto, um LLM gera um DAG que representa tarefas complexas como subtarefas, com arestas indicando as dependências entre elas. Na estrutura, essas informações são usadas para ajudar a determinar o planejamento de movimento e a coordenação entre os dois braços para execução de tarefas.⁴

Os DAGs são usados para otimizar o projeto de compiladores, programas que convertem linguagens de programação (código-fonte) em instruções para computadores (código de máquina). Por exemplo, um DAG pode ajudar a identificar subexpressões comuns que podem ser eliminadas para aumentar a eficiência.

Uma Blockchain baseado em um DAG demonstra melhor desempenho do que Blockchains convencionais, de acordo com pesquisadores. Uma blockchain baseada em DAG pode permitir o processamento paralelo de transações, aumentando assim a taxa de transações processadas em um determinado período e permitindo mais flexibilidade e escalabilidade. Essas melhorias podem ter aplicações em áreas como gerenciamento da cadeia de suprimentos e controles de acesso para redes de Internet das coisas. ^{5, 6}