The Graph Mining Library - pustaka algoritme dan analisis graf

 (github.com/google)
3 poin oleh GN⁺ 2023-10-05 | 1 komentar | Bagikan ke WhatsApp
  • Tujuan tim Google Graph Mining adalah membangun pustaka yang sangat skalabel untuk algoritme dan analisis graf serta menerapkannya pada produk Google; cakupan yang saat ini tersedia adalah kumpulan algoritme klastering
  • Alat yang dikembangkan mencakup pembangunan graf kemiripan, klastering, klasifikasi node, embedding node, pelatihan graph neural network, visualisasi graf, berbagai metode sampling, dan pemeringkatan kemiripan
  • Area klastering terdiri dari algoritme paralel shared-memory yang dapat diskalakan hingga graf dengan puluhan miliar edge, serta beberapa algoritme sekuensial
  • Algoritme paralel merupakan implementasi yang berbasis pada makalah riset terkait HAC, correlation clustering, affinity clustering, dan parline
  • Framework Graph Neural Network disediakan melalui proyek terpisah, TF-GNN
  • Untuk menjalankan dengan cepat, instal Bazel lalu jalankan bazel run //examples:quickstart
  • Ini bukan produk yang didukung secara resmi oleh Google; pertanyaan dan masukan ditangani dengan membuat issue di repositori ini

Bacaan terkait

1 komentar

 
GN⁺ 2023-10-05
Pendapat di Hacker News

  • Graph mining sangat populer sekitar 10 tahun lalu. Ini mengingatkan pada GraphX (https://spark.apache.org/graphx/) dan GraphLab (https://en.wikipedia.org/wiki/GraphLab), serta database graf
    Mungkin waktunya beririsan dengan fenomena jejaring sosial, dan belakangan geometric learning, yaitu machine learning di atas graf dan struktur lain, sempat mendapat perhatian sebelum direbut oleh LLM. Meski begitu, geometric learning masih terlihat punya potensi besar, dan saya berharap bisa menjadi lebih populer

    • Dalam “database graf”, ada arus yang memandang graf sebagai pendekatan universal untuk data, dengan RDF dan SPARQL serta banyak upaya serupa. Kita juga bisa membayangkan kasus ketika struktur data inti dalam program C adalah graf pointer
      Graf semacam ini biasanya memiliki sangat banyak jenis edge yang berbeda, seperti “menikah dengan” atau “memiliki suhu rata-rata tahunan”. Sebaliknya, algoritme graf seperti PageRank atau sentralitas graf sering kali mengasumsikan hanya satu atau sedikit jenis edge. Memang ada algoritme umum yang bisa diterapkan pada graf dengan banyak jenis edge; misalnya pola SPARQL ?s1 ?p ?o . ?s2 ?p ?o . menemukan ?s1 dan ?s2 yang berbagi suatu ?o dan relasi ?p, lalu menjadi dasar ukuran kemiripan di antara keduanya. Graf umumnya tidak memiliki bentuk yang sudah ditentukan sehingga bisa memiliki struktur apa pun, dan dari sudut pandang latensi memori ini bisa menjadi bencana. Dulu saat memakai pola SPARQL ini, saya pernah membuat program yang akan berjalan 100 tahun, lalu dengan mengemas ulang struktur data dan mencari aproksimasi, perhitungannya bisa selesai dalam 20 menit. Karena itu para praktisi cenderung skeptis terhadap library pemrosesan graf serbaguna. Sebab ada banyak masalah yang bisa dibuat 1000 kali lebih cepat dengan menulis kode khusus dalam waktu yang lebih singkat daripada waktu bergulat dengan sistem build
      Namun kalau ingin mengikuti tren, arXiv belakangan ini penuh dengan makalah graph neural network yang tidak terlalu dibesar-besarkan di tempat lain. YOShInOn membuatkan daftar panjang makalah GNN untuk saya lihat, tetapi saya baru menelusuri beberapa saja; ada banyak tulisan yang mengatakan itu bisa diterapkan pada masalah analisis teks yang saya kerjakan, tetapi tidak tampak jelas lebih baik daripada sistem yang dipakai YOShInOn dan saya, jadi saya tidak terburu-buru
    • Untuk masalah yang paling baik diselesaikan dengan analisis graf, NetworkX masih banyak dipakai, dan saya sangat menyukai pengalaman pengembang dari paket ini

  • Bagi yang ingin bereksperimen dengan graf dan machine learning, saat membaca dokumentasi ArangoDB baru-baru ini saya melihat ada integrasi dengan beberapa library graf dan framework machine learning https://docs.arangodb.com/3.11/data-science/adapters/
    Saya juga melihat beberapa notebook Jupyter tentang machine learning pada graf https://github.com/arangodb/interactive_tutorials#machine-learning
    Integrasi yang tersedia mencakup NetworkX -- https://networkx.org/, DeepGraphLibrary -- https://www.dgl.ai/, cuGraph (Rapids.ai Graph) -- https://docs.rapids.ai/api/cugraph/stable/, dan PyG (PyTorch Geometric) -- https://pytorch-geometric.readthedocs.io/en/latest/

  • Jika ada yang familier dengan Bazel, bisa beri petunjuk cara membuild? bazel build memang melakukan sesuatu, tetapi hasilnya hanya memunculkan bazel-build dan bazel-build, dan tidak terlihat artefak build yang mencolok

    • Di Bazel, //... mirip dengan target all di make
      Bisa dipakai seperti bazel build //..., bazel test //..., bazel query //.... Kalau tidak salah ingat, perintah terakhir akan mencantumkan semua target
    • Menambahkan jawaban di atas, Anda juga bisa membuild satu paket saja. Misalnya, bazel build //in_memory/connected_components:asynchronous_union_find bisa membuild asynchronous_union_find
      Namun, di luar konteks aturan cc_binary, ini mungkin tidak terlalu berguna. Cara seperti ini memungkinkan proyek lain membuild dan memakai hanya paket yang dibutuhkan, tanpa membuild seluruh repositori. Misalnya jika hanya ingin memakai header asynchronous_union_find.h, tambahkan library graph-mining sebagai aturan git_repository di suatu tempat dalam file WORKSPACE proyek (lihat contoh WORKSPACE.bazel), lalu tambahkan @graph-mining//in_memory/connected_components:asynchronous_union_find ke aturan cc_library di file BUILD dalam proyek. Dengan begitu, header bisa di-include dari tempat lain, dan saat proyek dibuild hanya paket tersebut beserta dependensinya yang dibuild, bukan seluruh library graph-mining
    • Sejak dulu saya hanya berpikir suatu saat harus mencoba Bazel, dan “suatu saat” itu ternyata hari ini. Untuk menginstalnya, tampaknya cara yang disarankan adalah memasang Bazelisk terlebih dahulu, lalu mengganti namanya menjadi bazel dan menaruhnya di path seperti /usr/local/bin/bazel
      Namun saat menjalankan query muncul peringatan JDK, dan saat menjalankan build gagal karena tidak ada Java, disertai WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE.. Padahal saya bahkan tidak memakai Java, lalu setelah beberapa menit mencari JDK/JRE mana yang harus dipakai, saya menyerah; “suatu saat” hari ini pun kembali ditunda ke hari lain. Sampai rasanya memalukan betapa saya sudah terlalu terbiasa dengan cargo atau npm/yarn
      Koreksi: berkat https://sdkman.io/ akhirnya bisa jalan. Ternyata tidak seburuk itu

  • Pertanyaan pemula: apakah library ini bisa dilihat sebagai kandidat untuk diintegrasikan dengan wrapper atau library ekstensi agar algoritma clustering berbasis graf terkumpul di satu tempat? Dengan asumsi memang belum seperti itu saat ini
    Atau apakah sudah ada framework lain yang menyediakan fungsi yang sama dengan lebih baik? Misalnya NetworkX

  • Mungkin saya sangat ketinggalan zaman, tetapi apakah ini ada hubungannya dengan Pregel?

    • Pregel adalah sistem pemrosesan graf terdistribusi, sedangkan ini, menurut saya, adalah library untuk menangani graf di dalam memori satu komputer

  • Akan sangat membantu kalau ada contoh

    • Akan sangat membantu kalau ada dokumentasi dalam bentuk apa pun
    • Akan segera diunggah. Coba cek lagi 12 jam lagi, kemungkinan sudah ada

  • Bisa jelaskan library ini berguna untuk apa?

    • Bisa dipakai untuk clustering. Saya pernah memakai correlation clusterer di sini untuk masalah yang bisa direpresentasikan sebagai graf node dengan metrik kemiripan (data ini mirip dengan data itu) dan ciri tolakan kuat (data ini diketahui berbeda dari data itu, jadi jangan pernah digabung)

  • Di GitHub tertulis C, C++, Starland. Apa itu Starland?

    • Itu Starlark. Bahasa untuk mengonfigurasi sistem build Bazel, dan Bazel adalah port open-source dari sistem build internal Google, Blaze. Starlark adalah subset dari Python
    • Dugaan saya itu salah ketik dan seharusnya Starlark. Itu bahasa yang dipakai di file build Bazel
      Bazel adalah sistem build yang dipakai di sini

  • Algoritma graf sangat membutuhkan semacam standardisasi. Bayangkan BLAS dan LAPACK

  • Saya berharap ini benar-benar alat untuk menambang graf statistik dan melakukan deteksi anomali