The Graph Mining Library - ไลบรารีสำหรับอัลกอริทึมและการวิเคราะห์กราฟ

 (github.com/google)
3 คะแนน โดย GN⁺ 2023-10-05 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เป้าหมายของทีม Google Graph Mining คือการสร้างไลบรารีที่ขยายขนาดได้สูงสำหรับอัลกอริทึมและการวิเคราะห์กราฟ และนำไปใช้กับผลิตภัณฑ์ของ Google โดยขอบเขตที่มีให้ในปัจจุบันคือชุดของ อัลกอริทึมการทำคลัสเตอร์
  • เครื่องมือที่พัฒนาครอบคลุมการสร้าง similarity graph, การทำคลัสเตอร์, การจัดประเภทโหนด, node embedding, การฝึก graph neural network, การแสดงภาพกราฟ, การสุ่มตัวอย่างหลายรูปแบบ, การจัดอันดับความคล้ายคลึง
  • ส่วนของการทำคลัสเตอร์ประกอบด้วย อัลกอริทึมขนานแบบ shared-memory ที่ขยายได้ถึงกราฟที่มีขอบนับหมื่นล้านรายการ และอัลกอริทึมแบบลำดับหลายแบบ
  • อัลกอริทึมแบบขนานเป็นการนำไปใช้งานตามงานวิจัยที่เกี่ยวกับ HAC, correlation clustering, affinity clustering และ parline
  • เฟรมเวิร์ก Graph Neural Network มีให้ในโปรเจ็กต์แยกต่างหาก TF-GNN
  • การรันอย่างรวดเร็วทำได้โดยติดตั้ง Bazel แล้วรัน bazel run //examples:quickstart
  • นี่ไม่ใช่ผลิตภัณฑ์ที่ Google สนับสนุนอย่างเป็นทางการ โดยคำถามและข้อคิดเห็นจะถูกรับผ่านการสร้าง issue ในรีโพซิทอรีนี้

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-10-05
ความคิดเห็นบน Hacker News

  • Graph mining เคยเป็นกระแสแรงมากเมื่อราว 10 ปีก่อน ทำให้นึกถึง GraphX (https://spark.apache.org/graphx/) กับ GraphLab (https://en.wikipedia.org/wiki/GraphLab) และฐานข้อมูลกราฟ
    คงเป็นช่วงที่ทับซ้อนกับปรากฏการณ์โซเชียลเน็ตเวิร์ก และในช่วงหลัง ๆ geometric learning ซึ่งเป็นแมชชีนเลิร์นนิงบนกราฟและโครงสร้างอื่น ๆ ก็เริ่มได้รับความสนใจ ก่อนจะถูก LLM แย่งพื้นที่พูดถึงไป ถึงอย่างนั้นก็ยังคิดว่า geometric learning มีศักยภาพสูง และอยากให้ได้รับความนิยมมากขึ้น

    • ใน “ฐานข้อมูลกราฟ” มีกระแสที่มองกราฟเป็นแนวทางทั่วไปสำหรับข้อมูล รวมถึง RDF และ SPARQL ตลอดจนความพยายามลักษณะคล้ายกันอีกมากมาย ลองนึกถึงกรณีที่โครงสร้างข้อมูลหลักในโปรแกรม C เป็นกราฟของพอยน์เตอร์ก็ได้
      กราฟแบบนี้มักมี ประเภทของเส้นเชื่อม ที่แตกต่างกันจำนวนมหาศาล เช่น “แต่งงานกับ” หรือ “มีอุณหภูมิเฉลี่ยรายปี” ในทางกลับกัน อัลกอริทึมกราฟอย่าง PageRank หรือ graph centrality มักมีประเภทของเส้นเชื่อมเพียงหนึ่งประเภทหรือไม่กี่ประเภทเท่านั้น แม้จะมีอัลกอริทึมทั่วไปที่ใช้กับกราฟซึ่งมีเส้นเชื่อมหลายประเภทได้ เช่น แพตเทิร์น SPARQL ?s1 ?p ?o . ?s2 ?p ?o . จะหา ?s1, ?s2 ที่แชร์ ?o และความสัมพันธ์ ?p บางอย่างร่วมกัน ซึ่งกลายเป็นพื้นฐานของตัวชี้วัดความคล้ายคลึงระหว่างทั้งสอง กราฟโดยทั่วไปไม่มีรูปแบบตายตัว จึงมีโครงสร้างได้ทุกแบบ และในแง่ memory latency อาจกลายเป็นหายนะได้ ครั้งหนึ่งเคยใช้แพตเทิร์น SPARQL นี้แล้วสร้างโปรแกรมที่ต้องใช้เวลา 100 ปี แต่หลังจากแพ็กโครงสร้างข้อมูลใหม่และหาวิธีประมาณค่า ก็ทำให้คำนวณเสร็จได้ภายใน 20 นาที ดังนั้นคนทำงานจริงจึงมักค่อนข้างกังขากับไลบรารีประมวลผลกราฟแบบเอนกประสงค์ เพราะมีปัญหาจำนวนมากที่สามารถเขียนโค้ดเฉพาะทางให้เร็วขึ้น 1000 เท่าได้ โดยใช้เวลาน้อยกว่าการไปปล้ำกับระบบ build
      ถึงอย่างนั้น ถ้าอยากตามกระแส ช่วงนี้ใน arXiv มีบทความเรื่อง graph neural network เต็มไปหมด ซึ่งไม่ได้ถูกโฆษณาเกินจริงมากนักในที่อื่น YOShInOn ทำลิสต์บทความ GNN ยาว ๆ ให้ดู แต่ผมดูผ่าน ๆ ไปแค่ไม่กี่บทความ และแม้จะมีหลายบทความบอกว่านำไปใช้กับปัญหาการวิเคราะห์ข้อความที่ผมทำอยู่ได้ แต่ก็ไม่ได้ดูดีกว่าระบบที่ YOShInOn กับผมใช้อยู่เป็นพิเศษ เลยยังไม่รีบร้อน
    • สำหรับปัญหาที่เหมาะที่สุดจะแก้ด้วยการวิเคราะห์กราฟ ก็ยังมีการใช้ NetworkX กันมาก และผมชอบ developer experience ของแพ็กเกจนี้มากจริง ๆ

  • ถ้าใครอยากลองเล่นกับกราฟและแมชชีนเลิร์นนิง ช่วงหลังผมดูเอกสารของ ArangoDB แล้วเห็นว่ามีการรวมเข้ากับ ไลบรารีกราฟ หลายตัวและเฟรมเวิร์กแมชชีนเลิร์นนิงด้วย https://docs.arangodb.com/3.11/data-science/adapters/
    ยังเห็น Jupyter Notebook หลายตัวที่ว่าด้วยแมชชีนเลิร์นนิงบนกราฟด้วย https://github.com/arangodb/interactive_tutorials#machine-learning
    สิ่งที่รองรับการเชื่อมรวมมี 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/](https://pytorch-geometric.readthedocs.io/en/latest/

  • ถ้ามีใครคุ้นกับ Bazel ช่วยแนะ วิธี build หน่อยได้ไหม? bazel build ดูเหมือนจะทำอะไรบางอย่าง แต่ผลลัพธ์มีแค่ bazel-build กับ bazel-build เกิดขึ้น และไม่เห็น artifact จากการ build ที่เด่นชัดเลย

    • ใน Bazel นั้น //... คล้ายกับ target all ของ make
      ใช้ได้แบบ bazel build //..., bazel test //..., bazel query //... คำสั่งสุดท้ายถ้าจำไม่ผิดจะแสดง target ทั้งหมด
    • เสริมจากคำตอบข้างบน ยัง build เฉพาะแพ็กเกจเดียวก็ได้ เช่น build asynchronous_union_find ด้วย bazel build //in_memory/connected_components:asynchronous_union_find
      แต่ถ้าอยู่นอกบริบทของกฎ cc_binary อาจไม่ได้มีประโยชน์มากนัก วิธีนี้ช่วยให้ไม่ต้อง build ทั้ง repository แต่ build เฉพาะแพ็กเกจที่ต้องใช้ในโปรเจกต์อื่นได้ ตัวอย่างเช่น ถ้าต้องการใช้แค่ header asynchronous_union_find.h ก็เพิ่มไลบรารี graph-mining ด้วยกฎ git_repository ไว้สักที่ในไฟล์ WORKSPACE ของโปรเจกต์ (ดูตัวอย่าง WORKSPACE.bazel) แล้วเพิ่ม @graph-mining//in_memory/connected_components:asynchronous_union_find ในกฎ cc_library ที่อยู่ในไฟล์ BUILD ภายในโปรเจกต์ จากนั้นก็ include header จากที่อื่นได้ และตอน build โปรเจกต์จะ build เฉพาะแพ็กเกจนั้นกับ dependency ของมัน โดยไม่ build ไลบรารี graph-mining ทั้งหมด
    • ตั้งแต่นานมาแล้วเคยคิดว่า “สักวัน” ต้องลองดู Bazel ให้ได้ แล้ว “สักวัน” นั้นก็มาถึงวันนี้ วิธีติดตั้งที่แนะนำดูเหมือนจะเป็นการติดตั้ง Bazelisk ก่อน แล้วเปลี่ยนชื่อเป็น bazel และวางไว้ใน path อย่าง /usr/local/bin/bazel
      แต่พอรัน query ก็เจอคำเตือนของ JDK และพอรัน build ก็ล้มเหลวเพราะไม่มี Java พร้อมข้อความ WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE. ทั้งที่ไม่ได้ใช้ Java เลย หลังค้นอยู่ไม่กี่นาทีว่าควรใช้ JDK/JRE ตัวไหน ก็ไปต่อไม่ไหวแล้ว “สักวัน” ของวันนี้เลยต้องเลื่อนไปวันอื่นอีกครั้ง รู้สึกน่าอายพอสมควรว่าถูก cargo หรือ npm/yarn ตามใจจนเคยตัวเกินไป
      แก้ไข: รันได้แล้วเพราะ https://sdkman.io/ สุดท้ายก็ไม่ได้แย่ขนาดนั้น

  • ขอถามแบบมือใหม่ ไลบรารีนี้พอจะถือเป็นตัวเลือกสำหรับรวมเข้ากับ wrapper หรือไลบรารีส่วนขยาย เพื่อรวบรวม อัลกอริทึม clustering ที่อิงกราฟ ไว้ในที่เดียวได้ไหม? สมมติว่ายังไม่ได้เป็นแบบนั้นอยู่แล้ว
    หรือมี framework ที่ให้ฟังก์ชันแบบเดียวกันได้ดีกว่าอยู่แล้ว เช่น NetworkX อะไรทำนองนั้น

  • อาจเป็นผมเองที่ตามยุคไม่ทันมาก ๆ แต่สิ่งนี้เกี่ยวข้องกับ Pregel ไหม?

    • Pregel เป็นระบบประมวลผลกราฟแบบกระจาย ส่วนอันนี้เท่าที่ผมดูเป็นไลบรารีสำหรับจัดการกราฟในหน่วยความจำของคอมพิวเตอร์เครื่องเดียว

  • ถ้ามีตัวอย่างจะช่วยได้มากจริง ๆ

    • ถ้ามี เอกสารประกอบ ไม่ว่าจะรูปแบบไหนก็ตาม จะช่วยได้มากจริง ๆ
    • กำลังจะมาเร็ว ๆ นี้ อีก 12 ชั่วโมงลองกลับมาดูใหม่น่าจะมีแล้ว

  • ช่วยอธิบายได้ไหมว่าไลบรารีนี้มีประโยชน์ตรงไหน?

    • ใช้กับ clustering ได้ เคยใช้ correlation clusterer ในนี้กับปัญหาที่แทนได้เป็นกราฟของ node ซึ่งมีเมตริกความคล้ายกัน (ข้อมูลนี้คล้ายกับข้อมูลนั้น) และคุณลักษณะการผลักออกที่แรง (รู้ว่าข้อมูลนี้ต่างจากข้อมูลนั้น จึงห้าม merge เด็ดขาด)

  • บน GitHub ระบุว่าเป็น C, C++, Starland Starland คืออะไร?

    • คือ Starlark เป็นภาษาสำหรับตั้งค่าระบบ build ของ Bazel และ Bazel เป็นพอร์ตโอเพนซอร์สของ Blaze ซึ่งเป็นระบบ build ภายในของ Google Starlark เป็น subset ของ Python
    • เดาว่าน่าจะพิมพ์ผิด และควรเป็น Starlark เป็นภาษาที่ใช้ในไฟล์ build ของ Bazel
      Bazel คือระบบ build ที่ใช้ในที่นี้

  • อัลกอริทึมกราฟต้องการ มาตรฐาน ในระดับหนึ่งอย่างมาก ลองนึกถึง BLAS กับ LAPACK

  • คาดหวังว่าจะเป็นเครื่องมือที่ขุด mining กราฟเชิงสถิติจริง ๆ เพื่อทำ anomaly detection

    • https://en.wikipedia.org/wiki/Graph_theory
      ตอนแรก ๆ น่าสนใจและดูง่ายกว่าที่เห็น
    • “กราฟ” ที่ใช้ในที่นี้น่าจะหมายถึงคนละอย่างกับความหมายที่ผมใช้
    • อันนั้นค่อนข้างง่าย และดูได้ที่ https://en.m.wikipedia.org/wiki/Interquartile_range