The Graph Mining Library - thư viện thuật toán và phân tích đồ thị

 (github.com/google)
3 điểm bởi GN⁺ 2023-10-05 | 1 bình luận | Chia sẻ qua WhatsApp
  • Mục tiêu của nhóm Google Graph Mining là xây dựng một thư viện có khả năng mở rộng cao cho các thuật toán và phân tích đồ thị, đồng thời áp dụng vào các sản phẩm của Google; phạm vi hiện tại được cung cấp là bộ sưu tập thuật toán phân cụm
  • Các công cụ được phát triển hướng đến xây dựng đồ thị tương đồng, phân cụm, phân loại nút, nhúng nút, huấn luyện mạng nơ-ron đồ thị, trực quan hóa đồ thị, nhiều phương pháp lấy mẫu khác nhau và xếp hạng độ tương đồng
  • Mảng phân cụm gồm các thuật toán song song dùng bộ nhớ chia sẻ có thể mở rộng tới các đồ thị với hàng chục tỷ cạnh, cùng với nhiều thuật toán tuần tự
  • Các thuật toán song song là các triển khai dựa trên các bài báo nghiên cứu liên quan đến HAC, correlation clustering, affinity clustering và parline
  • Framework Graph Neural Network được cung cấp trong dự án riêng TF-GNN
  • Cách chạy nhanh là sau khi cài Bazel, chạy bazel run //examples:quickstart
  • Đây không phải là sản phẩm được Google hỗ trợ chính thức; câu hỏi và ý kiến được tiếp nhận bằng cách tạo issue trong kho lưu trữ này

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-10-05
Các ý kiến trên Hacker News

  • Khai phá đồ thị từng thực sự là một trào lưu khoảng 10 năm trước. Nó khiến tôi nhớ đến GraphX (https://spark.apache.org/graphx/) và GraphLab (https://en.wikipedia.org/wiki/GraphLab), cùng các cơ sở dữ liệu đồ thị
    Có lẽ nó trùng thời điểm với hiện tượng mạng xã hội, và gần đây hơn thì học hình học — tức machine learning trên đồ thị và các cấu trúc khác — đã được chú ý, rồi bị LLM lấy mất sự quan tâm. Dù vậy tôi vẫn cho rằng học hình học còn rất nhiều tiềm năng và mong nó trở nên phổ biến hơn

    • Với “cơ sở dữ liệu đồ thị”, có một xu hướng xem đồ thị như một cách tiếp cận phổ quát cho dữ liệu, gồm RDF, SPARQL và rất nhiều nỗ lực tương tự. Cũng có thể nghĩ đến trường hợp cấu trúc dữ liệu cốt lõi trong một chương trình C là một đồ thị con trỏ
      Những đồ thị như vậy thường có vô số kiểu cạnh khác nhau, chẳng hạn “kết hôn với” hay “có nhiệt độ trung bình năm”. Ngược lại, các thuật toán đồ thị như PageRank hay độ trung tâm của đồ thị thường chỉ có một hoặc rất ít kiểu cạnh. Vẫn có các thuật toán tổng quát có thể áp dụng cho đồ thị có nhiều kiểu cạnh; ví dụ, mẫu SPARQL ?s1 ?p ?o . ?s2 ?p ?o . tìm các ?s1, ?s2 cùng chia sẻ một ?o nào đó và quan hệ ?p, từ đó làm cơ sở cho một thước đo độ tương đồng giữa chúng. Đồ thị nói chung không có hình dạng cố định, có thể mang bất kỳ cấu trúc nào, và xét từ góc độ độ trễ bộ nhớ thì có thể là thảm họa. Trước đây tôi từng dùng mẫu SPARQL này và tạo ra một chương trình phải chạy 100 năm; sau đó tôi đóng gói lại cấu trúc dữ liệu và tìm phép xấp xỉ để tính xong trong vòng 20 phút. Vì vậy, những người làm thực tế thường hoài nghi với các thư viện xử lý đồ thị đa dụng. Lý do là có rất nhiều bài toán mà ta có thể viết mã chuyên dụng trong thời gian còn ngắn hơn thời gian vật lộn với hệ thống build, nhưng lại chạy nhanh hơn 1000 lần
      Dù vậy, nếu muốn chạy theo xu hướng, hiện nay arXiv tràn ngập các bài về mạng nơ-ron đồ thị mà ở nơi khác không bị thổi phồng quá mức. YOShInOn đã lập cho tôi một danh sách dài các bài GNN để xem, nhưng tôi mới chỉ lướt qua vài bài; có nhiều bài nói rằng có thể áp dụng cho bài toán phân tích văn bản tôi đang làm, nhưng chúng không có vẻ tốt hơn rõ rệt so với hệ thống mà YOShInOn và tôi đang dùng, nên tôi chưa vội
    • Với những bài toán phù hợp nhất để giải bằng phân tích đồ thị, NetworkX vẫn được dùng nhiều, và tôi thực sự thích trải nghiệm lập trình viên của gói này

  • Nếu bạn muốn thử động đến đồ thị và machine learning, gần đây khi xem tài liệu ArangoDB tôi thấy họ có tích hợp nhiều thư viện đồ thị và framework machine learning https://docs.arangodb.com/3.11/data-science/adapters/
    Tôi cũng thấy vài notebook Jupyter về machine learning trên đồ thị https://github.com/arangodb/interactive_tutorials#machine-learning
    Các tích hợp gồm NetworkX -- https://networkx.org/, DeepGraphLibrary -- https://www.dgl.ai/, cuGraph (Rapids.ai Graph) -- https://docs.rapids.ai/api/cugraph/stable/, PyG (PyTorch Geometric) -- https://pytorch-geometric.readthedocs.io/en/latest/.

  • Nếu có ai quen với Bazel, có thể gợi ý cách build không? bazel build có vẻ có làm gì đó, nhưng kết quả chỉ tạo ra bazel-build và bazel-build, còn không thấy artifact build nào đáng chú ý

    • Trong Bazel, //... tương tự target all của make
      Có thể dùng như bazel build //..., bazel test //..., bazel query //.... Lệnh cuối, theo trí nhớ của tôi, sẽ liệt kê tất cả các target
    • Bổ sung cho câu trả lời trên, cũng có thể build chỉ một package. Ví dụ có thể build asynchronous_union_find bằng bazel build //in_memory/connected_components:asynchronous_union_find
      Tuy nhiên ngoài ngữ cảnh rule cc_binary thì có thể không hữu ích lắm. Cách này cho phép không cần build toàn bộ repository, mà chỉ build và dùng các package cần thiết từ dự án khác. Ví dụ nếu chỉ muốn dùng header asynchronous_union_find.h, hãy thêm thư viện graph-mining vào đâu đó trong file WORKSPACE của dự án bằng rule git_repository (tham khảo ví dụ WORKSPACE.bazel), rồi thêm @graph-mining//in_memory/connected_components:asynchronous_union_find vào rule cc_library trong file BUILD của dự án. Khi đó có thể include header ở nơi khác, và khi build dự án thì chỉ package đó cùng các dependency của nó được build, chứ không build toàn bộ thư viện graph-mining
    • Từ lâu tôi vẫn nghĩ rồi một ngày nào đó phải xem thử Bazel, và “một ngày nào đó” đã thành hôm nay. Có vẻ cách được khuyến nghị để cài là trước tiên cài Bazelisk, sau đó đổi tên thành bazel và đặt vào một đường dẫn như /usr/local/bin/bazel
      Nhưng chạy query thì xuất hiện cảnh báo JDK, chạy build thì thất bại vì không có Java, kèm WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE.. Tôi cũng đâu dùng Java, vậy mà phải tìm xem nên dùng JDK/JRE nào trong vài phút, rồi không tiếp tục nổi nữa, thế là “một ngày nào đó” của hôm nay lại dời sang ngày khác. Thật đáng buồn là tôi đã quá quen với cargo hay npm/yarn
      Sửa: Nhờ https://sdkman.io/ mà chạy được. Cuối cùng thì cũng không tệ đến thế

  • Câu hỏi của người mới: có thể xem thư viện này là ứng viên để tích hợp với wrapper hoặc thư viện mở rộng nhằm gom các thuật toán phân cụm dựa trên đồ thị vào một chỗ không? Giả sử là hiện chưa làm như vậy
    Hay đã có framework nào cung cấp cùng chức năng tốt hơn rồi? Kiểu như NetworkX chẳng hạn

  • Có thể tôi đã tụt hậu khá xa, nhưng cái này có liên quan đến Pregel không?

    • Pregel là hệ thống xử lý đồ thị phân tán, còn cái này theo tôi thấy là thư viện xử lý đồ thị trong bộ nhớ của một máy đơn

  • Nếu có ví dụ thì sẽ thật sự hữu ích

    • Có tài liệu dưới bất kỳ hình thức nào cũng sẽ thật sự hữu ích
    • Sẽ sớm được đăng. Thử quay lại sau 12 giờ, có lẽ sẽ có

  • Có thể giải thích thư viện này hữu ích ở đâu không?

    • Có thể dùng cho phân cụm. Tôi từng dùng bộ phân cụm tương quan ở đây cho các bài toán có thể biểu diễn dưới dạng đồ thị nút với thước đo độ tương đồng (dữ liệu này giống dữ liệu kia) và đặc trưng đẩy mạnh (dữ liệu này được biết là khác dữ liệu kia, nên tuyệt đối không gộp)

  • Trên GitHub ghi là C, C++, Starland. Starland là gì vậy?

    • Là Starlark. Đây là ngôn ngữ để cấu hình hệ thống build Bazel, và Bazel là bản port mã nguồn mở của hệ thống build nội bộ Blaze của Google. Starlark là một tập con của Python
    • Tôi đoán đó là lỗi chính tả và đáng lẽ phải là Starlark. Đây là ngôn ngữ dùng trong các file build của Bazel
      Bazel là hệ thống build được dùng ở đây

  • Các thuật toán đồ thị rất cần một mức độ chuẩn hóa nào đó. Cứ nghĩ đến BLAS và LAPACK là được

  • Tôi đã kỳ vọng đúng theo nghĩa đen là một công cụ khai phá đồ thị thống kê để phát hiện bất thường