Cos'è un grafo aciclico diretto (DAG)?

Un grafo aciclico diretto (DAG) è un tipo di grafo in cui i nodi sono collegati da connessioni unidirezionali che non formano alcun ciclo. I DAG sono utilizzati per illustrare le dipendenze e le relazioni causali.

Come tutti i grafi, i DAG possono essere utili per visualizzare le relazioni tra i nodi che rappresentano dati, attività o eventi. Tuttavia, i DAG sono utili per rappresentare i sistemi in cui gli eventi si verificano in un ordine specifico, come una pianificazione delle attività che devono essere completate per raggiungere un obiettivo.

I DAG sono importanti anche per creare diagrammi causali, poiché possono rappresentare sistemi in cui alcuni nodi hanno un impatto su altri nodi, ma gli effetti causali non funzionano nella direzione opposta. Un esempio di tali relazioni unidirezionali è quello degli alberi genealogici, dove i DAG mappano le generazioni successive di genitori e figli.

L'applicazione dei DAG è comune in informatica, dove sviluppatori e ingegneri utilizzano i DAG per le pipeline e l'elaborazione dei dati, così come per l'architettura delle reti neurali, la robotica e molto altro.

Per capire meglio cos'è un grafo aciclico diretto, analizziamone i componenti:

Nodi: i nodi, chiamati anche vertici, rappresentano entità, oggetti o variabili su un grafo. In genere sono raffigurati come punti o cerchi.

Archi: gli archi rappresentano le connessioni tra le entità. Sono raffigurati come linee.

Archi diretti: gli archi diretti rappresentano connessioni che possono essere attraversate in una sola direzione. Le frecce su tali archi indicano la loro direzione.

Grafi diretti: i grafi costituiti interamente da archi diretti sono grafi o digrafi diretti. Al contrario, i grafi senza archi diretti sono grafi non diretti.

Collider: i collider sono nodi con 2 archi diretti che puntano verso di loro.

Percorsi: i percorsi sono una sequenza di archi che collegano un particolare nodo a un altro. I percorsi costituiti interamente da archi diretti sono detti percorsi diretti. I percorsi diretti che indicano relazioni causali sono chiamati percorsi causali.

Albero: in informatica, un albero è un grafo aciclico diretto in cui ogni nodo ha solo un arco diretto che punta verso di esso, ad eccezione del nodo iniziale (il nodo "radice"). Sebbene gli archi si estendono dal nodo radice, nessun arco punta al nodo radice.

Oltre a comprendere le parti di un DAG, è anche importante riconoscere un componente mancante, ovvero un ciclo. Il termine "aciclico" nel grafo aciclico diretto si riferisce all'assenza di cicli o loop chiusi in questi grafi. In altre parole, quando si parte da un nodo in un DAG e si attraversano nodi e archi successivi, è impossibile tornare al nodo iniziale.

Nella teoria dei grafi (lo studio dei grafi), vengono spesso applicati diversi concetti o processi quando si lavora con grafi aciclici diretti. Eccone alcuni:

• Ordinamento topologico
• Chiusura transitiva
• Riduzione transitiva

Un ordinamento topologico, noto anche come ordinamento topologico, è un modo di organizzare i nodi di un DAG in modalità lineare, affinché i nodi che puntano ad altri nodi appaiano per primi e i successori non appaiano prima dei loro predecessori. Gli algoritmi di ordinamento topologico possono produrre queste sequenze basate su DAG.¹

Nei grafici complessi può essere difficile riconoscere quali nodi possano essere "raggiungibili" tramite percorsi diretti da altri nodi. Nella chiusura transitiva, tali collegamenti indiretti tra i nodi sono identificati e schematizzati.

Ad esempio, se un grafo ha un arco diretto che collega il nodo A e il nodo B e un altro arco diretto che collega il nodo B e il nodo C, ciò indicherebbe che A e C sono collegati indirettamente. Una chiusura transitiva darebbe luogo a un nuovo arco diretto che collega A a C (ora il percorso più breve tra questi due nodi), oltre agli archi diretti originali tra A e B e tra B e C. Come per l'ordinamento topologico, è possibile utilizzare algoritmi per i calcoli di chiusura transitiva.

La riduzione transitiva può essere considerata l'opposto della chiusura transitiva. Nel contesto di un grafo diretto, la riduzione transitiva del grafo ha lo stesso numero di nodi del grafo originale e le coppie di nodi raggiungibili sono le stesse. Tuttavia, il numero di archi nella riduzione transitiva del grafo è ridotto al minimo.

Consideriamo, ad esempio, un grafo originale che include un arco diretto che collega il nodo A al nodo C e una sequenza di archi diretti che collega il nodo A al nodo B e il nodo B al nodo C. Una riduzione transitiva di quel grafo escluderebbe l'arco tra A e C mantenendo gli archi tra l'insieme più ampio di variabili: A e B e B e C.

In altre parole, il percorso più lungo tra A e C nel grafo originale è incluso nel nuovo grafo, mentre il percorso con un solo arco viene eliminato. 

I grafi aciclici diretti rivestono un ruolo di primo piano in informatica attraverso una serie di casi d'uso:

• Elaborazione dati
• Neural networks
• Inferenza causale nel machine learning
• Robotica
• Progettazione di compilatori
• Blockchain

I DAG aiutano i data engineer a definire le strutture dei dati e a ottenere l'ottimizzazione dei flussi di dati. Le piattaforme di orchestrazione dei dati come Apache Airflow, ad esempio, utilizzano i DAG (definiti negli script Python) per definire le attività di elaborazione dei dati e specificarne l'ordine di esecuzione nelle pipeline di dati e nei workflow.

Nei casi in cui più DAG dipendono l'uno dall'altro, gli strumenti di orchestrazione possono creare grafici delle dipendenze per chiarire tali relazioni.² Le piattaforme di osservabilità dei dati possono essere utilizzate insieme alle piattaforme di orchestrazione dei dati per identificare e risolvere i problemi della pipeline di dati.

L'accelerazione dell'adozione di applicazioni di intelligenza artificiale generativa, che si basano sull'accesso ai dati, ha amplificato l'importanza delle pipeline di dati e dei DAG nel panorama tecnologico moderno.

Una rete neurale è un programma di machine learning che decide in modo simile al cervello umano, utilizzando processi che imitano il modo in cui i neuroni biologici lavorano insieme per fare osservazioni e giungere a conclusioni. I DAG vengono utilizzati per mappare le reti neurali e possono essere particolarmente utili nella visualizzazione di reti neurali profonde con più livelli.

I DAG possono rivestire un ruolo negli sforzi per "insegnare" ai modelli AI a riconoscere le relazioni causali attraverso l'inferenza causale. L'inferenza causale è un paradigma per determinare gli effetti causali e spesso impiega i DAG. Ad esempio, i DAG possono aiutare a rilevare i “fattori di confondimento”, ovvero variabili che distorcono o oscurano la reale causalità. In particolare, l'AI potenziata con inferenza causale sta emergendo quale strumento nell'epidemiologia, poiché può potenzialmente aiutare molto i ricercatori impegnati nelle ricerche sui determinanti delle patologie.³

I ricercatori hanno proposto di utilizzare un metodo di pianificazione strutturale basato su DAG e modelli linguistici di grandi dimensioni per migliorare le prestazioni dei robot a doppio braccio. Nel framework proposto, un LLM genera un DAG che rappresenta attività complesse come attività secondarie, con archi che indicano le dipendenze tra di esse. Nel framework, queste informazioni vengono utilizzate per aiutare a determinare la pianificazione del movimento e il coordinamento tra i due bracci per l'esecuzione delle attività.⁴

I DAG sono utilizzati per ottimizzare la progettazione dei compilatori, ovvero programmi che convertono i linguaggi di programmazione (codice sorgente) in istruzioni per il computer (codice macchina). Ad esempio, un DAG può aiutare a identificare le sottoespressioni comuni che possono essere eliminate al fine di migliorare l'efficienza.

Secondo i ricercatori, una blockchain basata su un DAG dimostra prestazioni migliori rispetto alle blockchain convenzionali. Una blockchain basata su DAG può consentire l'elaborazione parallela delle transazioni, aumentando la velocità delle transazioni elaborate in un determinato periodo e consentendo un maggiore livello di flessibilità e scalabilità. Tali miglioramenti possono trovare applicazione in settori quali la gestione della supply chain e i controlli degli accessi per le reti Internet-of-Things .^{5, 6}