• Canate Dew

[สรุป] Graph Neural Network จากคลาส Alex About Data


Node Embedding คืออะไร


Node Embedding คือการทำเน็ตเวิร์คหรือกราฟให้เป็นเวคเตอร์มีมิติที่ลดลงเรียกการทำแบบนี้ว่า Encoder โดยที่โหนดที่มีความใกล้เคียงกันจะอยู่ใกล้กันใช้ Similarity Function ในการหาความใกล้เคียงของโหนด 2 ตัว


Shallow Encoder คืออะไร


Shallow Encoder เป็นหนึ่งวิธีในการทำโหนดในเน็ตเวิร์คให้อยู่ในรูปของเวคเตอร์ซึ่ง 1 คอลัมน์ต่อโหนด เป็นการเปลี่ยนแปลงข้อมมูลแบบหนึ่งเลเยอร์ แต่ข้อจำกัดของวิธีนี้คือพารามิเตอร์ของมันไม่มีการเชื่อมกันระหว่างโหนดเพราะเป็นการเปลี่ยนข้อมูลในตัวของมันเอง ไม่มีการเอาโหนดใกล้เคียงมาคำนวน และมันมาสามารถสร้างหรือทำนายโหนดใหม่ขึ้นมาได้ (Transductive) เพราะว่าถึงโหนดเป็น Unique Embedding เพราะทุกโหนดมันมีคุณสมบัติที่เป็นเอกลักษณ์ เมื่อไม่เคยเห็นโหนดมาก่อนจึงสร้างโหนดใหม่ขึ้นมาไม่ได้ (ไม่สามารถนำโหนดอื่นมาทำนายได้ด้วยเช่นกันเพราะโหนดแต่ละโหนดมันมีเอกลักษณ์นั้นเอง) ไม่สามารถนำ Node Feature มาใช้ต่อได้ด้วย ข้อจำกัดนี้ทำให้ Deep Encoder มีบทบาท


Deep Graph Encoder คืออะไร


Deep Graph Encoder คือการเปลี่ยนแปลงเน็ตเวิร์คให้อยู่ในรูปแบบเวคเตอร์เพื่อลดมิติของข้อมูล โดยที่มีการเปลี่ยนแปลงโดยใช้มากกว่า 1 เลเยอร์ หรือสามารถเรียกได้ว่า Graph Neural Network สามารถทำมารวมกับ Node Similarity Function ได้ เหตุผลที่ต้องใช้ Graph Neural Network เพราะว่าข้อมูลของกราฟไม่ได้เรียงลำดับแบบภาพหรือข้อความ และข้อมูลไม่ได้เรียงกันชัดเจนเหมือนกันข้อมูลประเภทอื่น (ไม่มี Locality ไม่เป็น Grid Layer) เป้าหมายของการพัฒนาจาก CNN (Convolution Neural Network) คือการ Generalize Convolution ให้สามารถจัดการกับข้อมูลประเภทเน็ตเวิร์คหรือกราฟได้


  • Naive Approach - การนำ Adjacency Matrix ใส่เข้าไป Deep Neural Network เลยมีปัญหาเวลาคำนวน O(N) และไม่สามารถนำไปใช้เน็ตเวิร์คกราฟขนาดอื่นได้เพราะมีการระบุตำแหน่งโหนดตายตัว

  • Graph Convolution Network - เป็นสร้าง Computational Graph จากโหนดใกล้เคียงได้ (Local Network Neighborhood) นำมา Aggregate ซึ่งส่วนใหญ่จะเป็น 2 เลเยอร์ก็สามารถทั่วถึงทั้งเน็ตเวิร์คได้แล้ว (Stacking Multiple Layer) เพราะฉะนั้นทุกโหนดในเน็ตเวิร์คจะมี Computational Graph ของตัวมันเอง

  • Basic Approach นำโหนดใกล้เคียงมาหาค่าเฉลี่ยและทำ Neural Network และนำมาเทรนใน Loss Function เพื่อหาค่าพารามิเตอร์ต่อไปโดยแบ่งเป็น 1. Unsupervised Training (Random Walk, Graph Factorization) 2. Supervised Training (Node Classification) สุดท้ายแล้วสามารถ Generate Node Embedding ได้ (New Nodes)

  • GraphSAGE พัฒนามาจากพื้นฐานซึ่งจุดมุ่งหมายคือการพัฒนาการคำนวนมากกว่าการหาค่าเฉลี่ย จึงนำ Aggregate Function เช่น Mean, Pool, LSTM เขามาใช้แทนการหาค่าเฉลี่ย (พารามิเตอร์ยังเหมือนเดิม)

  • Graph Attention Network (GAT) - ให้เขาสำคัญในแต่ละโหนดไม่เท่ากัน (Graph Convolution Network จะนำมาคำนวนโดยให้โหนดทุกตัวมีความสำคัญเท่ากัน) เพราะบางโหนดอาจจะมีความสำคัญมากกว่าตัวอื่น จึงนำ Attention Strategy มาให้น้ำหนักของโหนดแต่ละตัวไม่เท่ากัน จะมี Attention Coefficient ในการคำนวนเพื่อหาค่าความสำคัญของโหนดโดยคำนวนกันเป็นคู่ (Pair of Node) จากนั้นใช้ Softmax Function ในการ normalize ซึ่งสามารถเทรนไปพร้อมกับ Neural Network ได้เลย ข้อดีคือ

  • Computationally Efficient - การคำนวนมีขนาดเล็กกว่า

  • Storage Efficient - O(V+E) ดีกว่า O(N)

  • Localized - ไม่ต้องดูกราฟทั้งกราฟเพราะดูแค่ Local Network Neighborhood

  • Inductive Capability - Edge-wise mechanism นำไปทำนายโหนดถัดไปได้



สามารถดูเนื้อหาเต็มได้ที่

Graph Neural Network - Alex About Data

GraphSage - Alex About Data

Graph Attention Networks - Alex About Data

ดู 654 ครั้ง0 ความคิดเห็น