Apa itu graf asiklik berarah (DAG)?

Graf asiklik berarah (directed acyclic graph, DAG) adalah jenis graf yang node-nodenya dihubungkan dengan koneksi satu arah yang tidak membentuk siklus apa pun. DAG digunakan untuk menggambarkan ketergantungan dan hubungan sebab-akibat.

Seperti graf lainnya, DAG dapat membantu memvisualisasikan hubungan antara node yang mewakili data, tugas, atau peristiwa. Namun, DAG berguna untuk menggambarkan sistem di mana peristiwa terjadi dalam urutan tertentu, misalnya jadwal tugas yang harus diselesaikan untuk mencapai tujuan.

DAG juga penting untuk membuat diagram kausal: DAG dapat mewakili sistem di mana beberapa node memengaruhi node lainnya, tetapi efek kausalnya tidak berlaku untuk arah yang berlawanan. Contoh dasar dari hubungan satu arah tersebut dapat ditemukan dalam silsilah keluarga, karena DAG memetakan generasi orang tua dan anak secara berurutan.

DAG umum diaplikasikan dalam ilmu komputer. Pengembang dan insinyur menggunakan DAG untuk pipeline data dan pemrosesan data, arsitektur jaringan neural, robotika, dan banyak lagi.

Untuk lebih memahami tentang graf asiklik berarah, mari kita uraikan komponennya:

Node: Node, juga dikenal sebagai verteks, mewakili entitas, objek, atau variabel pada graf. Node biasanya digambarkan sebagai titik atau lingkaran.

Edge: Edge mewakili hubungan antara entitas. Edge digambarkan sebagai garis.

Edge berarah (Directed edge): Edge berarah mewakili koneksi yang mungkin dilintasi hanya dalam 1 arah. Tanda panah pada edge berarah menunjukkan arah edge tersebut.

Graf berarah (Directed graph): Graf yang seluruhnya terdiri dari edge berarah disebut sebagai graf berarah atau digraf (digraph). Sebaliknya, graf tanpa edge berarah disebut sebagai graf tidak berarah (undirected graph).

Collider: Collider adalah node yang memiliki dua edge berarah yang menunjuk ke arahnya.

Jalur (Path): Jalur adalah rangkaian beberapa edge yang menghubungkan satu node tertentu ke node lainnya. Jalur yang seluruhnya terdiri dari edge berarah dikenal sebagai jalur berarah (directed path). Jalur berarah yang menunjukkan hubungan sebab-akibat disebut sebagai jalur kausal (causal path).

Pohon (Tree): Dalam ilmu komputer, pohon adalah graf asiklik berarah di mana setiap node hanya memiliki satu edge berarah yang mengarah ke node tersebut, kecuali node awal (node akar (“root”)). Meskipun edge memanjang dari node akar, tidak ada edge yang menunjuk ke node akar.

Selain memahami bagian-bagian DAG, penting juga untuk mengenali satu komponen yang tidak dimilikinya: siklus. Istilah “acyclic” (asiklik) dalam graf asiklik berarah mengacu pada tidak adanya siklus atau loop tertutup dalam graf ini. Dengan kata lain, ketika memulai dari satu node dalam DAG dan melintasi node dan edge berikutnya, tidak mungkin untuk kembali ke node awal.

Dalam teori graf (studi tentang graf), beberapa konsep atau proses sering diterapkan ketika menangani graf asiklik berarah. Hal ini termasuk:

• Topological sort (Penyortiran topologi)
• Transitive closure (Penutupan transitif)
• Transitive reduction (Reduksi transitif)

Penyortiran topologi atau pengurutan topologi, adalah cara untuk mengatur node-node DAG secara linear sehingga node yang menunjuk ke node lain ditampilkan pertama kali dan penerus tidak akan ditampilkan sebelum pendahulunya. Algoritma pengurutan topologi dapat menghasilkan rangkaian semacam ini berdasarkan DAG.¹

Pada graf yang rumit, mungkin sulit untuk mengenali node mana yang dapat “dijangkau” oleh jalur berarah dari node lain. Dalam penutupan transitif, hubungan tidak langsung antara node tersebut diidentifikasi dan digambarkan sebagai diagram.

Sebagai contoh, jika graf memiliki edge berarah yang menghubungkan node A dan node B serta sebuah edge berarah lainnya yang menghubungkan node B dan node C, hal ini mengindikasikan bahwa A dan C terhubung secara tidak langsung. Penutupan transitif akan menghasilkan edge berarah baru yang menghubungkan A ke C, yang kini merupakan jalur terpendek di antara kedua node tersebut, serta edge berarah asli antara A dan B dan B dan C. Mirip dengan penyortiran topologi, algoritma dapat digunakan untuk penghitungan penutupan transitif.

Reduksi transitif dapat dianggap sebagai kebalikan dari penutupan transitif. Dalam konteks graf berarah, reduksi transitif graf memiliki jumlah node yang sama dengan graf asli dan pasangan node yang dapat dijangkau adalah sama. Namun, terjadi pengurangan jumlah edge dalam reduksi transitif graf.

Kita ambil contoh graf asli yang memiliki edge berarah yang menghubungkan node A ke node C, dan rangkaian edge berarah yang menghubungkan node A ke node B dan node B ke node C. Reduksi transitif dari graf tersebut akan mengecualikan edge antara A dan C, tetapi mempertahankan edge di antara himpunan yang lebih besar dari variabel tersebut: A dan B dan B dan C.

Dengan kata lain, jalur terpanjang antara A dan C pada graf asli disertakan pada graf baru, sementara jalur yang hanya memiliki satu edge dihilangkan. 

Graf asiklik berarah menonjol dalam ilmu komputer pada sejumlah contoh penggunaan:

• Pemrosesan data
• Jaringan neural
• Inferensi kausal dalam machine learning
• Robotika
• Desain kompiler
• Blockchain

DAG membantu insinyur data menentukan struktur data dan mencapai optimalisasi dalam aliran data. Platform orkestrasi data seperti Apache Airflow, misalnya, menggunakan DAG (didefinisikan dalam skrip Python) untuk menentukan tugas pemrosesan data dan menentukan urutan eksekusi mereka dalam pipeline data dan alur kerja.

Dalam kasus apabila beberapa DAG saling bergantung satu sama lain, alat orkestrasi dapat membuat graf dependensi untuk memperjelas hubungan tersebut.² Platform observabilitas data dapat digunakan bersama dengan platform orkestrasi data untuk mengidentifikasi dan mengatasi masalah pipeline data.

Percepatan adopsi aplikasi kecerdasan buatan generatif, yang mengandalkan akses data, telah memperkuat signifikansi pipeline data dan DAG dalam lingkungan teknologi modern.

Jaringan neural adalah program machine learning yang mengambil keputusan dengan cara yang mirip dengan otak manusia. Program ini menggunakan proses yang meniru cara neuron biologis bekerja sama untuk melakukan pengamatan dan mengambil kesimpulan. DAG digunakan untuk memetakan jaringan neural dan dapat sangat membantu dalam visualisasi jaringan neural dalam dengan banyak lapisan.

DAG dapat ambil bagian dalam upaya untuk “mengajari” model AI untuk mengenali hubungan sebab-akibat melalui inferensi kausal. Inferensi kausal adalah paradigma untuk menentukan efek kausal, dan kerap kali menggunakan DAG. Misalnya, DAG dapat membantu deteksi “confounder” (pengganggu) yang merupakan variabel yang mendistorsi atau mengaburkan sebab-akibat nyata. AI yang disempurnakan dengan inferensi kausal muncul sebagai alat bantu, khususnya dalam epidemiologi, yang berpotensi membantu peneliti dalam menyelidiki faktor-faktor penentu penyakit.³

Para peneliti telah mengusulkan penggunaan metode perencanaan struktural berbasis DAG dan model bahasa besar (large language model, LLM) untuk meningkatkan kinerja robot lengan ganda. Dalam kerangka kerja yang diusulkan, LLM menghasilkan DAG yang mewakili tugas-tugas kompleks sebagai subtugas, dengan edge yang menunjukkan dependensi antara tugas-tugas tersebut. Dalam kerangka kerja tersebut, informasi ini digunakan untuk membantu menentukan perencanaan gerakan dan koordinasi antara kedua lengan untuk pelaksanaan tugas.⁴

DAG digunakan untuk mengoptimalkan desain kompiler, yaitu program yang mengubah bahasa pemrograman (kode sumber) menjadi instruksi untuk komputer (kode mesin). Misalnya, DAG dapat membantu mengidentifikasi subekspresi umum yang dapat dihilangkan untuk meningkatkan efisiensi.

Blockchain berdasarkan DAG menunjukkan kinerja yang lebih baik daripada blockchain konvensional, menurut para peneliti. Blockchain berbasis DAG memungkinkan pemrosesan transaksi secara paralel, sehingga meningkatkan persentase transaksi yang diproses dalam periode tertentu, sekaligus memberikan fleksibilitas dan skalabilitas yang lebih baik. Peningkatan tersebut dapat diaplikasikan di bidang-bidang seperti manajemen rantai pasokan dan kontrol akses untuk jaringan Internet-of-Things.^{5, 6}