Penyederhanaan Algoritmik untuk Rekonstruksi Riwayat Difusi Sejuta Verteks

Battus-Z: Inferensi Mean-Field Deterministik Menggantikan Proposal Terpelajar, MCMC, dan Pemasangan Parameter Sambil Menyamai Kualitas Agregat HERMES

Gökhan Göktürk· 2026· DOI 10.48550/arXiv.2608.28955

Masalah inti

Rekonstruksi riwayat difusi menangani masalah invers untuk menyimpulkan keadaan node laten di antara observasi jarang dari proses penyebaran SI atau SIR. Diberikan graf G = (V, E) dan himpunan frame teramati pada waktu t_{1} < t_{2} < \dots < t_{k}, tugasnya adalah memulihkan lintasan keadaan tak teramati {x_{t} (v)}_{t \in (t_{i}, t_{i + 1}), v \in V} . Masalah ini mendasari aplikasi di bidang epidemiologi, pelacakan misinformasi, dan forensik jaringan, di mana observasi penuh tidak mungkin dilakukan. HERMES adalah pipeline mutakhir yang menggabungkan tiga komponen: (i) pemasangan parameter laju transmisi, (ii) distribusi proposal graph-neural terpelajar atas riwayat laten, dan (iii) Markov chain Monte Carlo (MCMC) yang sadar kelayakan untuk pengambilan sampel posterior. Meskipun efektif, arsitektur ini berat secara komputasi dan sulit diskalakan ke graf sejuta verteks. Karya ini mengajukan pertanyaan penyederhanaan: tahap mana dari HERMES yang sebenarnya diperlukan untuk mempertahankan kualitas agregat yang dipublikasikan? Penulis menghapus tahap satu per satu dan mengevaluasi setiap versi terablasi pada seluruh 12 dataset kanonis yang digunakan dalam benchmark HERMES. Metode yang dihas

Inovasi

Pada protokol benchmark HERMES standar (frame teramati terakhir disematkan sebelum penilaian), Battus-Z mencapai rata-rata macro- F_{1} 0,8726 dan NRMSE 0,1010 pada seluruh 12 dataset kanonis. Agregat HERMES yang dipublikasikan adalah 0,8692 macro- F_{1} dan 0,1483 NRMSE. Dengan demikian Battus-Z menyamai atau sedikit melampaui macro- F_{1} sekaligus menurunkan NRMSE secara substansial. Di bawah metrik yang lebih ketat yang mengecualikan semua frame teramati, Battus-Z memperoleh macro- F_{1} 0,8431 dan NRMSE 0,1181. Ini menegaskan bahwa penyederhanaan tersebut mempertahankan kualitas bahkan ketika model tidak dapat mengandalkan observasi yang disematkan. Hasil skalabilitas dilaporkan untuk implementasi CUDA. Implementasi ini memproses riwayat yang dihasilkan dengan hingga 4,84 juta verteks pada LiveJournal dan 117 juta sisi pada Orkut. Pada backend CUDA yang sama, Battus-Z mengurangi interval algoritma rata-rata geometrik relatif terhadap Battus terpasang sebesar 5,1x untuk SI dan 20,3x untuk SIR. Laju pelanggaran kausal berbobot peristiwa adalah 7,50% untuk SI dan 8,77% untuk SIR; penulis mencatat bahwa dekode yang dibatasi graf masih menjadi pekerjaan masa depan. | Metrik | HERMES (dipublikas

Rekonstruksi riwayat difusi menangani masalah invers untuk menyimpulkan keadaan node laten di antara observasi jarang dari proses penyebaran SI atau SIR. Diberikan graf G = (V, E) dan himpunan frame teramati pada waktu t_{1} < t_{2} < \dots < t_{k}, tugasnya adalah memulihkan lintasan keadaan tak teramati {x_{t} (v)}_{t \in (t_{i}, t_{i + 1}), v \in V} . Masalah ini mendasari aplikasi di bidang epidemiologi, pelacakan misinformasi, dan forensik jaringan, di mana observasi penuh tidak mungkin dilakukan.

HERMES adalah pipeline mutakhir yang menggabungkan tiga komponen: (i) pemasangan parameter laju transmisi, (ii) distribusi proposal graph-neural terpelajar atas riwayat laten, dan (iii) Markov chain Monte Carlo (MCMC) yang sadar kelayakan untuk pengambilan sampel posterior. Meskipun efektif, arsitektur ini berat secara komputasi dan sulit diskalakan ke graf sejuta verteks.

Mengapa penting

Ablasi menunjukkan bahwa proposal graph-neural terpelajar, pengambilan sampel MCMC, dan tahap pemasangan parameter HERMES tidak diperlukan untuk mempertahankan kualitas agregat yang dipublikasikan pada benchmark dan protokol penilaian yang dievaluasi. Ini adalah penyederhanaan yang signifikan: Battus-Z menggantikan pipeline yang kompleks, stokastik, dan mahal secara komputasi dengan inferensi mean-field deterministik dan dekode ambang. Percepatan—5,1x untuk SI dan 20,3x untuk SIR—diukur sebagai pengurangan interval algoritma rata-rata geometrik pada backend CUDA yang sama, menunjukkan bahwa penyederhanaan tersebut juga menghasilkan keuntungan komputasi yang substansial. Kemampuan memproses graf dengan hingga 4,84 juta verteks dan 117 juta sisi membuat metode ini praktis untuk analisis difusi jaringan berskala besar. Namun, laju pelanggaran kausal berbobot peristiwa sebesar 7,50% (SI) dan 8,77% (SIR) menunjukkan bahwa rekonstruksi deterministik dapat melanggar urutan kausal peristiwa. Penulis secara eksplisit mengidentifikasi dekode yang dibatasi graf sebagai pekerjaan masa depan untuk mengatasi batasan ini. Selain itu, protokol benchmark menyematkan frame teramati terakhir, yang dapat menggelembungkan skor; hasil tanpa frame teramati (macro- F_{1} 0,8431, NRMSE 0,1181) memberikan estimasi yang lebih konservatif. Secara keseluruhan, karya ini menunjukkan bahwa untuk rekonstruksi riwayat difusi pada benchmark kanonis, inferensi deterministik yang lebih sederhana dapat menyamai pendekatan terpelajar dan berbasis pengambilan sampel yang lebih kompleks, setidaknya di bawah kondisi yang dievaluasi. Kandidat taksonomi—Architecture, Cybersecurity, Network, Cryptography—mencerminkan relevansi metode ini terhadap inferensi jaringan dan aplikasi keamanan, meskipun makalahnya sendiri berfokus pada penyederhanaan algoritmik.

Siapa yang sebaiknya membaca

Praktisi dan peneliti ilmu komputer

Membuka konten member…