บทนำที่เป็นมิตรต่อโครงข่ายประสาทกราฟ

 (distill.pub)
1 คะแนน โดย GN⁺ 2024-12-21 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • โครงข่ายประสาทกราฟ (GNN) คือโมเดลที่จัดการโหนด เอดจ์ และบริบททั่วทั้งกราฟ พร้อมกับโครงสร้างการเชื่อมต่อ เหมาะกับข้อมูลที่ต้องตีความกราฟเดียวกันให้มีความหมายเดียวกันแม้ลำดับของโหนดจะเปลี่ยนไป
  • ไม่เพียงแต่โมเลกุล โซเชียลเน็ตเวิร์ก และเครือข่ายการอ้างอิงเท่านั้น แต่กริดพิกเซลของภาพและลำดับโทเค็นของข้อความก็สามารถมองเป็นกราฟได้เช่นกัน อย่างไรก็ตามกราฟมีขนาดและการเชื่อมต่อแตกต่างกันไป จึงจัดการได้ยากเหมือน อินพุตแบบอาร์เรย์ทั่วไป
  • ปัญหาการทำนายของ GNN แบ่งเป็นระดับทั้งกราฟ ระดับโหนด และระดับเอดจ์ โดยโมเดลในตระกูลเดียวกันสามารถคงโครงสร้างอินพุตไว้พร้อมทำนายลาเบลในระดับต่างกันได้
  • การดำเนินการหลักคือ message passing ซึ่งรวบรวมข้อมูลจากโหนดและเอดจ์เพื่อนบ้านแล้วอัปเดต และเมื่อซ้อนหลายเลเยอร์ ก็จะสะท้อนข้อมูลจากเพื่อนบ้าน k-hop ที่ไกลขึ้นเข้าไปใน representation ได้
  • ประสิทธิภาพจริงขึ้นกับความลึกของเลเยอร์ มิติของ embedding ฟังก์ชัน aggregation และการไหลของข้อความระหว่าง representation ของโหนด เอดจ์ และทั่วทั้งกราฟ การเพิ่มพารามิเตอร์หรือความลึกจึงไม่ได้ให้ผลลัพธ์ดีที่สุดเสมอไป

ข้อมูลกราฟและแนวคิดพื้นฐานของ GNN

  • กราฟประกอบด้วย โหนด (node) ซึ่งเป็นเอนทิตี และ เอดจ์ (edge) ซึ่งเป็นความสัมพันธ์ระหว่างโหนด
  • โหนด เอดจ์ และกราฟทั้งกราฟสามารถเก็บข้อมูลเพิ่มเติมของตนเองได้
    • โหนดสามารถใส่คุณลักษณะอย่างชนิดอะตอม ค่า RGB ของพิกเซล หรือ document embedding ได้
    • เอดจ์สามารถใส่ข้อมูลอย่างชนิดพันธะหรือชนิดความสัมพันธ์ได้
    • กราฟทั้งกราฟสามารถมีบริบททั่วทั้งกราฟได้
  • เอดจ์สามารถแทนได้เป็น directed edge ที่มีทิศทาง หรือ undirected edge ที่ไม่มีทิศทาง
  • GNN ต้องแปลงโหนด เอดจ์ และบริบททั่วทั้งกราฟด้วยวิธีที่เรียนรู้ได้ พร้อมกับตีความโครงสร้างกราฟเดียวกันให้มีความหมายเดียวกันแม้ลำดับโหนดจะเปลี่ยนไป

ข้อมูลที่สามารถแทนเป็นกราฟได้

  • โดยทั่วไปภาพถูกแทนเป็นอาร์เรย์ เช่น 244×244×3 แต่ก็สามารถมองเป็น กราฟแบบสม่ำเสมอ โดยให้แต่ละพิกเซลเป็นโหนด และเชื่อมพิกเซลที่อยู่ติดกันด้วยเอดจ์ได้
    • พิกเซลที่ไม่อยู่ขอบจะมีเพื่อนบ้านพอดี 8 จุด
    • แต่ละโหนดเก็บเวกเตอร์ 3 มิติที่แทนค่า RGB
  • ข้อความสามารถมองเป็น กราฟมีทิศทาง โดยให้ตัวอักษร คำ หรือโทเค็นเป็นโหนด และมีเอดจ์ชี้ไปยังโทเค็นถัดไป
    • เชื่อมโยงกับ representation ของลำดับโทเค็นใน RNN
    • Transformer สามารถมองเป็นกราฟเชื่อมเต็มที่เรียนรู้ความสัมพันธ์ระหว่างโทเค็นได้
  • ภาพและข้อความมีโครงสร้างสม่ำเสมอมาก จึงอาจมีความซ้ำซ้อนเมื่อแทนเป็นกราฟ
    • adjacency matrix ของภาพมีโครงสร้างเป็นแถบเนื่องจากการเชื่อมต่อแบบกริด
    • adjacency matrix ของข้อความมีโครงสร้างใกล้เคียงแนวทแยง เพราะแต่ละคำเชื่อมกับคำก่อนหน้าและคำถัดไปเท่านั้น
  • โมเลกุลเหมาะที่จะแทนเป็นกราฟ โดยให้อะตอมเป็นโหนด และพันธะโคเวเลนต์เป็นเอดจ์
    • ระยะจะแตกต่างกันตามคู่ของอะตอมและชนิดพันธะ เช่น พันธะเดี่ยว พันธะคู่
  • โซเชียลเน็ตเวิร์กโมเดลคน สถาบัน และองค์กรเป็นโหนด และความสัมพันธ์เป็นเอดจ์
  • เครือข่ายการอ้างอิงแทนบทความวิจัยเป็นโหนด และความสัมพันธ์ที่บทความหนึ่งอ้างอิงอีกบทความเป็น เอดจ์มีทิศทาง
    • โหนดของแต่ละบทความสามารถเพิ่มข้อมูล เช่น word embedding ของบทคัดย่อได้
  • วัตถุในฉากของ computer vision, โมเดล machine learning, โค้ดโปรแกรม และสมการคณิตศาสตร์ก็สามารถแทนเป็นกราฟได้ โดยให้ตัวแปรหรือวัตถุเป็นโหนด และการดำเนินการหรือความสัมพันธ์เป็นเอดจ์

ปัญหาการทำนายกราฟสามระดับ

  • Graph-level task ทำนายคุณสมบัติหนึ่งอย่างของกราฟทั้งกราฟ
    • ตัวอย่างเช่น การทำนายว่ากราฟโมเลกุลมีกลิ่นแบบใด หรือจะจับกับตัวรับที่เกี่ยวข้องกับโรคหรือไม่
    • ติดลาเบลเดียวให้กับอินพุตทั้งหมด คล้ายการจำแนกภาพหรือการวิเคราะห์อารมณ์ของประโยค
  • Node-level task ทำนายคุณสมบัติหรือบทบาทของแต่ละโหนดในกราฟ
    • ชุดข้อมูล Zach's karate club เป็นปัญหาจำแนกโหนดบุคคลว่าจะภักดีต่อคลับใดในสองคลับหลังความขัดแย้งทางการเมือง
    • คล้ายปัญหาการติดลาเบลบทบาทของแต่ละพิกเซลใน image segmentation หรือการทำนายชนิดคำของแต่ละคำในประโยค
  • Edge-level task ทำนายคุณสมบัติหรือการมีอยู่ของเอดจ์
    • ตัวอย่างคือปัญหาในการทำความเข้าใจฉากภาพ โดยให้วัตถุเป็นโหนดแล้วทำนายว่ามีความสัมพันธ์ระหว่างวัตถุหรือไม่
    • สามารถเริ่มจากเชื่อมโหนดทุกคู่แบบ fully connected แล้วลบเอดจ์ตามค่าทำนายเพื่อสร้างกราฟ sparse ได้
  • การสร้างกราฟและการอธิบายการทำนายกราฟก็เป็นพื้นที่วิจัยที่เกี่ยวข้อง

ความยากในการทำให้กราฟเป็นอินพุตของโครงข่ายประสาท

  • โมเดล machine learning ทั่วไปถูกออกแบบให้รับอินพุตเป็นอาร์เรย์รูปสี่เหลี่ยมหรือกริด จึงใส่โครงสร้างการเชื่อมต่อของกราฟเข้าไปตรง ๆ ได้ยาก
  • กราฟมีข้อมูลได้สูงสุดสี่ประเภท
    • โหนด
    • เอดจ์
    • บริบททั่วทั้งกราฟ
    • การเชื่อมต่อ
  • โหนด เอดจ์ และบริบททั่วทั้งกราฟสามารถทำเป็นเมทริกซ์คุณลักษณะได้ แต่การแทน การเชื่อมต่อ ซับซ้อนกว่า
  • adjacency matrix ทำเป็นเทนเซอร์ได้ง่าย แต่มีข้อจำกัด
    • จำนวนโหนดในกราฟอาจอยู่ระดับหลายล้าน
    • จำนวนเอดจ์ต่อโหนดอาจแตกต่างกันมาก
    • adjacency matrix จะ sparse มาก ทำให้ประสิทธิภาพด้านพื้นที่ต่ำ
    • การเชื่อมต่อของกราฟเดียวกันสามารถแทนได้ด้วย adjacency matrix หลายแบบ จึงไม่มีหลักประกันว่า neural network จะให้ผลลัพธ์เหมือนกันเสมอ
  • adjacency list เหมาะกับกราฟ sparse มากกว่า
    • เก็บข้อมูลว่าเอดจ์ e_k เชื่อมโหนด n_i และ n_j เป็นทูเพิล (i, j)
    • แทนได้ใน O(n_edges) ซึ่งแปรตามจำนวนเอดจ์ แทนที่จะเป็น O(n_nodes^2) แบบ adjacency matrix
  • ในการแทนเป็นเทนเซอร์จริง ค่าโหนด เอดจ์ และทั่วทั้งกราฟไม่ใช่สเกลาร์ แต่เป็นเวกเตอร์
    • เทนเซอร์โหนดจึงมีรูป [n_nodes, node_dim] ไม่ใช่ [n_nodes]

เลเยอร์ GNN และ pooling

  • GNN ที่ง่ายที่สุดยังไม่ใช้การเชื่อมต่อของกราฟ แต่ใช้ MLP แยกกันกับโหนด เอดจ์ และบริบททั่วทั้งกราฟ เพื่อเรียนรู้ embedding ใหม่
    • เวกเตอร์ของแต่ละโหนดถูกอัปเดตด้วยวิธีเดียวกัน
    • เวกเตอร์ของแต่ละเอดจ์ก็ถูกอัปเดต
    • เวกเตอร์บริบททั่วทั้งกราฟก็ถูกอัปเดตเป็น embedding หนึ่งชุด
  • GNN ไม่เปลี่ยนการเชื่อมต่อของกราฟอินพุต
    • กราฟเอาต์พุตคง adjacency list เดิมและจำนวนเวกเตอร์คุณลักษณะเท่าเดิม
    • สิ่งที่เปลี่ยนคือ embedding ของโหนด เอดจ์ และบริบททั่วทั้งกราฟ
  • การทำนายใช้ pooling
    • gather embedding ของสิ่งที่ต้องการรวบรวมแล้วต่อเป็นเมทริกซ์
    • จากนั้น aggregate embedding ที่รวบรวมมา โดยปกติใช้การดำเนินการอย่าง sum
  • ในการทำนายโหนด หากมีข้อมูลโหนดอยู่แล้ว สามารถใช้ linear classifier กับ embedding ของแต่ละโหนดได้
  • หากข้อมูลที่จำเป็นต่อการทำนายโหนดอยู่เฉพาะในเอดจ์ ต้อง pooling ข้อมูลเอดจ์ไปยังโหนดเพื่อส่งต่อ
  • หากข้อมูลที่จำเป็นต่อการทำนายเอดจ์อยู่เฉพาะในโหนด ก็รวบรวมข้อมูลโหนดไปยังฝั่งเอดจ์เพื่อใช้ทำนาย
  • ในการทำนายทั้งกราฟ จะรวบรวมข้อมูลโหนดหรือเอดจ์ทั้งหมดเป็น representation ทั่วทั้งกราฟ
    • ทำหน้าที่คล้าย Global Average Pooling ใน CNN
    • ตัวอย่างคือการทำนายว่าโมเลกุลเป็นพิษหรือมีกลิ่นเฉพาะหรือไม่

ใช้โครงสร้างการเชื่อมต่อด้วย message passing

  • GNN แบบง่ายไม่ใช้การเชื่อมต่อของกราฟภายในเลเยอร์ และใช้การเชื่อมต่อเฉพาะตอน pooling ก่อนทำนายเท่านั้น
  • GNN ที่ทรงพลังกว่าจะทำ message passing ภายในเลเยอร์ เพื่อสะท้อนโครงสร้างการเชื่อมต่อในการอัปเดต embedding
  • message passing ทำงานสามขั้นตอน
    • แต่ละโหนด gather embedding หรือข้อความจากโหนดเพื่อนบ้าน
    • aggregate ข้อความด้วยฟังก์ชัน aggregation เช่น sum
    • ส่งข้อความที่รวบรวมแล้วผ่านฟังก์ชันอัปเดตที่เรียนรู้ได้
  • message passing คล้าย convolution มาตรฐาน
    • ในภาพ พิกเซลรวบรวมข้อมูลจากพิกเซลเพื่อนบ้านจำนวนคงที่
    • ในกราฟ โหนดรวบรวมข้อมูลจากโหนดเพื่อนบ้านจำนวนไม่คงที่
  • เมื่อซ้อนเลเยอร์ GNN หลายชั้น ข้อมูลจากโหนดที่ไกลขึ้นจะถูกสะท้อนเข้ามา
    • หลัง 3 เลเยอร์ โหนดหนึ่งอาจรวมข้อมูลจากโหนดที่ห่างออกไป 3 ขั้นได้
  • message passing สามารถทำได้ไม่เพียงระหว่างโหนด แต่ยังระหว่างเอดจ์ และระหว่างโหนดกับเอดจ์ด้วย

representation ของเอดจ์และ representation ทั่วทั้งกราฟ

  • ชุดข้อมูลไม่ได้มีข้อมูลโหนด เอดจ์ และบริบททั่วทั้งกราฟครบเสมอไป
  • เมื่อมีเฉพาะข้อมูลเอดจ์แต่ต้องทำนายโหนด สามารถ pooling ข้อมูลเอดจ์ส่งไปยังโหนดได้
  • ข้อมูลโหนดและเอดจ์อาจมีขนาดหรือรูปแบบต่างกัน วิธีรวมจึงเป็นตัวเลือกในการออกแบบ
    • สามารถเรียนรู้ linear mapping จากสเปซเอดจ์ไปสเปซโหนด หรือกลับกัน
    • สามารถต่อ representation ทั้งสองเข้าด้วยกันแล้วใส่เข้าไปในฟังก์ชันอัปเดต
  • การอัปเดตคุณสมบัติของกราฟใดก่อนหลังเป็นส่วนหนึ่งของการออกแบบ GNN
    • อัปเดตโหนดก่อน แล้วจึงอัปเดตเอดจ์ได้
    • อัปเดตเอดจ์ก่อน แล้วจึงอัปเดตโหนดได้
    • วิธี weave ที่รวม representation แบบ node-to-node, edge-to-edge, node-to-edge, edge-to-node ก็เป็นไปได้
  • โหนดที่อยู่ไกลกันอาจแลกเปลี่ยนข้อมูลได้ไม่มีประสิทธิภาพ แม้ทำ message passing หลายครั้ง
    • ใน k เลเยอร์ ข้อมูลจะแพร่ได้สูงสุดเพียง k-step
  • representation ทั่วทั้งกราฟ U สามารถทำหน้าที่เหมือน master node หรือเวกเตอร์บริบทที่เชื่อมกับทุกโหนดและเอดจ์
    • ทำหน้าที่เป็นสะพานส่งข้อมูลระหว่างโหนดและเอดจ์ที่อยู่ไกลกัน
    • สามารถสร้าง representation ที่สมบูรณ์ยิ่งขึ้นสำหรับทั้งกราฟได้
  • embedding ใหม่ของโหนดสามารถ condition ด้วยการต่อข้อมูลจากโหนดเพื่อนบ้าน เอดจ์ที่เชื่อมต่อ และข้อมูลทั่วทั้งกราฟเข้าด้วยกัน
    • อีกวิธีคือทำ linear mapping แล้วนำมาบวก หรือใช้ feature-wise modulation

GNN Playground และตัวอย่างการทำนายกลิ่นโมเลกุล

  • GNN Playground จัดการปัญหาการทำนายระดับ graph-level ของกราฟโมเลกุลขนาดเล็ก
  • ข้อมูลคือ Leffingwell Odor Dataset ซึ่งมีโมเลกุลและลาเบลการรับรู้กลิ่น
  • การทดลองจำแนกว่ากราฟโมเลกุลมีกลิ่น “pungent” หรือไม่ เป็นลาเบลไบนารีเดียว
    • pungent หมายถึงกลิ่นแรงและเด่นชัด
    • ตัวอย่างคือกระเทียมและมัสตาร์ดที่อาจมี allyl alcohol รวมถึง piperitone ที่ใช้ในลูกอมรส peppermint
  • โมเลกุลแทนด้วยอะตอมเป็นโหนด และพันธะเป็นเอดจ์
    • โหนดมีเอกลักษณ์ของอะตอม Carbon, Nitrogen, Oxygen, Fluorine แบบ one-hot encoding
    • เอดจ์มีชนิดพันธะ single, double, triple, aromatic แบบ one-hot encoding
  • เทมเพลตโมเดลเป็นโครงสร้างที่ต่อโมเดลเชิงเส้นที่มี sigmoid activation หลังเลเยอร์ GNN แบบลำดับ
  • ตัวเลือกการออกแบบถูกควบคุมด้วยสี่แกน
    • จำนวนเลเยอร์ GNN หรือ ความลึก
    • มิติ embedding ของแต่ละคุณสมบัติ
    • ฟังก์ชัน aggregation ของ pooling: max, mean, sum
    • จะอัปเดตและทำ message passing กับคุณสมบัติใดใน representation ของโหนด เอดจ์ และทั่วทั้งกราฟ
  • Playground ที่ทำงานในเบราว์เซอร์ทำงานบน tfjs
  • graph embedding มิติสูงถูกลดเหลือ 2D ด้วย PCA เพื่อแสดงภาพ representation รอบ decision boundary

แนวโน้มการออกแบบ GNN ที่เห็นในการทดลอง

  • ประสิทธิภาพขึ้นอยู่กับข้อมูล วิธีประกอบกราฟ และวิธีสร้างคุณลักษณะ
  • จำนวนพารามิเตอร์ที่มากขึ้นมีความสัมพันธ์กับประสิทธิภาพ แต่ GNN ยังพบโมเดลประสิทธิภาพสูงได้แม้มีพารามิเตอร์น้อย
    • พบโมเดลประสิทธิภาพสูงแม้มีพารามิเตอร์ประมาณ 3k
  • มิติ embedding ที่สูงขึ้นมีแนวโน้มทำให้ประสิทธิภาพเฉลี่ยและประสิทธิภาพขั้นต่ำดีขึ้น แต่โมเดลที่ดีที่สุดก็พบได้จากมิติขนาดเล็กเช่นกัน
  • เมื่อจำนวนเลเยอร์เพิ่มขึ้น ประสิทธิภาพเฉลี่ยมีแนวโน้มเพิ่มขึ้น แต่โมเดลที่ดีที่สุดไม่ได้อยู่ที่ 3 หรือ 4 เลเยอร์ แต่อยู่ที่ 2 เลเยอร์
    • ที่ 4 เลเยอร์ ประสิทธิภาพขั้นต่ำลดลง
    • เลเยอร์มากขึ้นทำให้ข้อมูล broadcast ไปได้ไกลขึ้น แต่มีความเสี่ยงที่ representation ของโหนดจะถูกเจือจางจากการทำซ้ำหลายรอบ
  • ในฟังก์ชัน aggregation, sum ดูดีกว่าเล็กน้อยมากในประสิทธิภาพเฉลี่ย แต่ max หรือ mean ก็สามารถสร้างโมเดลที่ดีเท่า ๆ กันได้
  • ยิ่งมีการส่งข้อความระหว่างคุณสมบัติของโหนด เอดจ์ และทั่วทั้งกราฟมากขึ้น ประสิทธิภาพเฉลี่ยของโมเดลมีแนวโน้มดีขึ้น
    • งานนี้เน้น representation ทั่วทั้งกราฟ จึงมีแนวโน้มว่าการเรียนรู้คุณสมบัติทั่วทั้งกราฟอย่างชัดเจนช่วยเพิ่มประสิทธิภาพ
    • representation ของโหนดดูมีประโยชน์กว่า representation ของเอดจ์ เพราะข้อมูลมากกว่าอยู่ในคุณสมบัติของโหนด

กราฟที่ซับซ้อนขึ้นและการเรียนรู้แบบ batch

  • เฟรมเวิร์ก message passing สามารถนำไปใช้กับโครงสร้างกราฟที่ซับซ้อนขึ้นได้
  • ใน Multigraph โหนดคู่เดียวกันสามารถแชร์เอดจ์หลายชนิดได้
    • ในโซเชียลเน็ตเวิร์กสามารถกำหนดประเภทความสัมพันธ์อย่าง acquaintance, friend, family เป็นชนิดเอดจ์ได้
    • สามารถมีขั้นตอน message passing ต่างกันสำหรับแต่ละชนิดเอดจ์
  • ใน nested graph โหนดหนึ่งสามารถแทนกราฟอีกกราฟได้
    • ในเครือข่ายโมเลกุล โหนดอาจเป็นโมเลกุล และเอดจ์อาจแทนปฏิกิริยาที่เปลี่ยนโมเลกุลหนึ่งเป็นอีกโมเลกุล
    • สามารถสลับกันเรียนรู้ GNN ระดับโมเลกุลกับ GNN ระดับเครือข่ายปฏิกิริยาได้
  • ใน hypergraph เอดจ์สามารถเชื่อมกับหลายโหนด ไม่ใช่แค่สองโหนด
    • สามารถระบุคอมมูนิตี้ของโหนดและมี hyper-edge ที่เชื่อมกับทั้งคอมมูนิตี้ได้
  • เนื่องจากกราฟมีจำนวนโหนดและเอดจ์ไม่คงที่ การเรียนรู้แบบ mini-batch ขนาดคงที่ทั่วไปจึงทำได้ยาก
  • แก่นของการเรียนรู้แบบ batch บนกราฟคือการสร้าง ซับกราฟ ที่รักษาคุณสมบัติสำคัญของกราฟใหญ่ไว้
    • ใน citation network การสุ่มตัวอย่างซับกราฟอาจเป็นไปตามธรรมชาติ
    • ในโมเลกุล ซับกราฟหมายถึงโมเลกุลใหม่ที่เล็กกว่า จึงอาจเป็นการดัดแปลงอย่างแรง
  • เมื่อกราฟใหญ่เกินกว่าจะใส่ในหน่วยความจำได้ graph sampling จึงสำคัญเป็นพิเศษ
    • โครงสร้างและกลยุทธ์การเรียนรู้อย่าง Cluster-GCN และ GraphSaint เกี่ยวข้องกับเรื่องนี้

inductive bias ที่เหมาะกับกราฟ

  • เมื่อโมเดลถูกออกแบบให้ใช้ประโยชน์จากสมมาตรและกฎเกณฑ์ในข้อมูลได้ จะมีประสิทธิภาพการทำนายดีขึ้น เวลาฝึกสั้นลง พารามิเตอร์น้อยลง และ generalization ดีขึ้น
  • โมเดลภาพใช้ convolution ที่ translation invariant เพื่อใช้ประโยชน์จากคุณสมบัติที่วัตถุเป็นวัตถุเดียวกันไม่ว่าจะอยู่ตรงไหนในภาพ
  • ในข้อความ ลำดับโทเค็นสำคัญ ดังนั้น RNN จึงประมวลผลแบบลำดับ ส่วนโมเดลตระกูล Transformer สามารถให้ความสนใจกับส่วนอื่นของประโยคได้
  • ในกราฟ ความสัมพันธ์ระหว่างเอดจ์ โหนด และองค์ประกอบทั่วทั้งกราฟสำคัญ จึงต้องมี relational inductive bias
    • ต้องรักษาโครงสร้าง adjacency ซึ่งเป็นความสัมพันธ์ที่ชัดเจน
    • ต้องรักษา permutation invariance ซึ่งเป็นสมมาตรของกราฟ
    • ต้องทำงานได้โดยไม่ขึ้นกับลำดับโหนดหรือเอดจ์ และรองรับอินพุตจำนวนไม่คงที่

การเลือกการดำเนินการ aggregation

  • การ pooling ข้อมูลโหนดและเอดจ์เพื่อนบ้านเป็นขั้นตอนหลักของสถาปัตยกรรม GNN ที่ทรงพลัง
  • แต่ละโหนดมีจำนวนเพื่อนบ้านต่างกัน และต้องไม่ขึ้นกับลำดับอินพุต จึงต้องใช้ฟังก์ชัน aggregation ที่หาอนุพันธ์ได้และไม่แปรตาม permutation
  • ตัวเลือกหลักคือ sum, mean, max
    • ทั้งหมดรับอินพุตจำนวนไม่คงที่และให้เอาต์พุตที่ไม่ขึ้นกับลำดับอินพุต
  • ไม่มีการดำเนินการใดดีที่สุดเสมอไป
    • mean มีประโยชน์เมื่อจำนวนเพื่อนบ้านแตกต่างกันมาก หรือเมื่อต้องการมุมมองที่ normalize แล้วของคุณลักษณะเพื่อนบ้านในพื้นที่
    • max มีประโยชน์เมื่อเน้นคุณลักษณะเด่นเพียงอย่างเดียวภายในเพื่อนบ้านในพื้นที่
    • sum แสดงการกระจายของคุณลักษณะในพื้นที่ และเพราะไม่ได้ normalize จึงสามารถเน้น outlier ได้ด้วย
  • ในทางปฏิบัติ sum ถูกใช้บ่อย
  • Principal Neighborhood Aggregation ต่อการดำเนินการ aggregation หลายแบบเข้าด้วยกัน และเพิ่ม scaling function ที่เปลี่ยนตาม degree ของการเชื่อมต่อ
  • ยังสามารถออกแบบการดำเนินการ aggregation เฉพาะโดเมน เช่น Tetrahedral Chirality ได้

GCN, การคูณเมทริกซ์ และการเดินบนกราฟ

  • GCN หรือ MPNN ที่มี k เลเยอร์และค้นหาเพื่อนบ้าน 1-degree สามารถมองเป็น neural network ที่ทำงานบน embedding ของซับกราฟขนาด k ได้
    • representation ที่อัปเดตของโหนดหนึ่งสะท้อนข้อมูลเพื่อนบ้านภายใน k-distance อย่างจำกัด
    • representation ของเอดจ์ก็สามารถตีความได้ในลักษณะเดียวกัน
  • ผลคูณ AX ของ adjacency matrix A กับเมทริกซ์คุณลักษณะโหนด X ใช้ทำ message passing อย่างง่ายที่ใช้ sum aggregation
    • กรณีที่ A_i,k เป็นบวกคือเมื่อมีเอดจ์ระหว่าง node_i และ node_k
    • การคูณเมทริกซ์สามารถมองเป็นการรวบรวมค่ามิติคุณลักษณะบางมิติของโหนดเพื่อนบ้าน
  • สำหรับ A ที่ sparse ไม่จำเป็นต้องบวกพจน์ที่เป็น 0 ทั้งหมด ดังนั้น adjacency list จึงมีประสิทธิภาพกว่า
  • การ implement ด้วย adjacency list ยังเอื้อต่อการใช้การดำเนินการ aggregation นอกเหนือจาก sum
  • กำลังของ adjacency matrix A^K เชื่อมโยงกับ walk ความยาว K
    • A^2_ij นับจำนวน walk ความยาว 2 จาก node_i ไป node_j
    • intuition นี้ต่อเนื่องจาก A^3 ไปจนถึง A^k

Attention, ความอธิบายได้ และโมเดลสร้างกราฟ

  • Graph Attention Networks ไม่ได้รวบรวมข้อมูลเพื่อนบ้านด้วยการบวกธรรมดา แต่รวบรวมเป็น weighted sum
    • ฟังก์ชันคะแนน f(node_i, node_j) คำนวณความเกี่ยวข้องระหว่างโหนดศูนย์กลางกับโหนดเพื่อนบ้าน
    • normalize น้ำหนักด้วย softmax เพื่อให้น้ำหนักกับเพื่อนบ้านที่สำคัญต่องานมากขึ้นได้
    • การคำนวณคะแนนเป็นรายคู่รักษา permutation invariance ไว้
  • Transformer สามารถมองเป็น GNN ที่มีกลไก attention ได้
    • โมเดลองค์ประกอบอย่างโทเค็นตัวอักษรเป็นโหนดของกราฟ fully connected
    • attention คำนวณ embedding และน้ำหนักของเอดจ์ของโหนดแต่ละคู่
    • ความแตกต่างคือ GNN สมมติรูปแบบการเชื่อมต่อแบบ sparse ส่วน Transformer โมเดลการเชื่อมต่อทั้งหมด
  • ความอธิบายได้ของ GNN อาจสำคัญต่อความน่าเชื่อถือของโมเดล การดีบัก และการค้นพบทางวิทยาศาสตร์
    • ในโมเลกุล การมีอยู่ของซับกราฟบางอย่างอาจสำคัญ
    • ในเครือข่ายการอ้างอิง ระดับการเชื่อมต่อของบทความอาจสำคัญ
    • GNNExplainer เข้าถึงปัญหาด้วยการดึงซับกราฟที่เกี่ยวข้องและสำคัญต่องานออกมา
    • เทคนิค attribution จัดอันดับความสำคัญให้ส่วนต่าง ๆ ของกราฟ
  • โมเดลสร้างกราฟสุ่มตัวอย่างกราฟใหม่จาก distribution ที่เรียนรู้ หรือเติมกราฟให้สมบูรณ์จากจุดเริ่มต้นที่กำหนด
    • มีการประยุกต์ใช้ในการออกแบบกราฟโมเลกุลใหม่ที่มีคุณสมบัติเฉพาะเป็นตัวเลือกยา
  • ความยากหลักของการสร้างกราฟคือการโมเดล topology ของกราฟ
    • topology มีขนาดเปลี่ยนแปลงมากและอาจมีพจน์ N_nodes^2
    • สามารถโมเดล adjacency matrix โดยตรงด้วย autoencoder เหมือนภาพได้
    • สามารถลดภาระ N_nodes^2 โดยทำนายเฉพาะเอดจ์ที่มีอยู่และบางส่วนของเอดจ์ที่ไม่มีอยู่
    • อีกวิธีคือสร้างกราฟตามลำดับโดยทำ action แบบ discrete ซ้ำ ๆ เช่น เพิ่มหรือลบโหนดและเอดจ์

สรุป

  • กราฟเป็นชนิดข้อมูลเชิงโครงสร้างที่มีจุดแข็งและข้อจำกัดต่างจากภาพและข้อความ
  • GNN อัปเดตโหนด เอดจ์ และบริบททั่วทั้งกราฟของกราฟ พร้อมจัดการโครงสร้างการเชื่อมต่อและ permutation invariance
  • pooling, message passing, representation ของเอดจ์, representation ทั่วทั้งกราฟ และการเลือกฟังก์ชัน aggregation เป็นองค์ประกอบหลักในการออกแบบ GNN
  • ประสิทธิภาพจริงไม่ได้ขึ้นกับความลึก มิติ และจำนวนพารามิเตอร์เท่านั้น แต่ยังขึ้นกับว่าคุณสมบัติใดของกราฟส่งข้อความถึงกัน และกราฟถูกสร้างขึ้นอย่างไรด้วย

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

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

 
GN⁺ 2024-12-21
ความคิดเห็นจาก Hacker News

  • มีงานวิจัยจำนวนมากที่ใช้ GNN กับ การจำลองทางฟิสิกส์ (เช่น พลศาสตร์ของไหลเชิงคำนวณ) เพราะ เมชแบบไม่เป็นโครงสร้าง ที่ใช้ดิสครีไทซ์โดเมนของปัญหาในแอปพลิเคชันเหล่านี้เข้ากับโครงสร้างกราฟได้ดีมาก
    ในทางปฏิบัติ แต่ละเมช/กราฟมักถูกใช้ครั้งเดียวเพื่อแก้ปัญหาเฉพาะหนึ่ง ๆ ดังนั้นการฝึก GNN สำหรับกราฟเฉพาะจึงไม่ค่อยมีความหมายมากนัก ถึงอย่างนั้น เหตุผลที่งานวิจัยส่วนใหญ่ทำแบบนั้นน่าจะเป็นเพราะเรายังไม่พบวิธีสร้าง GNN ที่ปรับตัวได้ดีกับเมช/กราฟและพารามิเตอร์การจำลองที่ต่างกัน ยังสงสัยอยู่ว่าจะมี breakthrough ที่ทำให้การ generalize แบบนี้เป็นไปได้ในเร็ว ๆ นี้หรือไม่

    • คำทั้งในและนอกประโยคก็ดูเหมือนจะทำงานคล้าย leaf node ที่อ้างอิงคำอื่นหรือถูกคำอื่นอ้างอิง จนเกิดเป็นกราฟชนิดหนึ่ง เมื่อเห็นความสำเร็จของ กลไก attention ใน LLM สมัยใหม่ ก็สงสัยว่า ถ้าฝึก LLM สำหรับการประมวลผลกราฟจริง ๆ จะทำได้ดีแค่ไหน
      ถ้าจะให้ได้ประสิทธิภาพสูงสุด น่าจะต้องใช้ tokenizer แบบอื่น
    • ตัวแก้กราฟแบบทั่วไป ต้องเป็นปัญญาทั่วไปด้วย เพราะมันน่าจะสามารถโมเดลทฤษฎีหมวดหมู่ได้สำเร็จด้วย

  • คุณภาพของงานสูงมาก แต่น่าเสียดายที่ distill.pub หาเส้นทางที่ยั่งยืนต่อไปไม่ได้ [1]
    เหตุผลหนึ่งที่ GNN ถูกพูดถึงน้อยลงอาจเป็นเพราะขาดชุดข้อมูล [2] เรื่องนี้เป็นปัญหาที่ส่งผลต่อวงการ semantic web ด้วย
    [1] https://distill.pub/2021/distill-hiatus/
    [2] https://huggingface.co/datasets?task_categories=task_categor...

    • เคล็ดลับส่วนตัวของผมคือ ก่อนจะกระโดดเข้าไปอ่านเปเปอร์ในสาขาที่ไม่คุ้นเคย ให้ค้นหา “ explained” บน YouTube ก่อน
      ถ้าเป็นสาขาที่ได้รับความนิยม มักมีคนจำนวนมากที่มีแรงจูงใจจะทำวิดีโอสั้น ๆ ที่ดึงดูดคนดู และคุณภาพก็มักดีแม้ในระดับคณิตศาสตร์ที่ค่อนข้างเป็นนามธรรม สื่อภาพช่วยให้จับความรู้สึกของแนวคิดนามธรรมได้จริง ๆ และ 3Blue1Brown ก็พิสูจน์ให้เห็นแล้ว สำหรับ GNN แค่ดูวิดีโอดี ๆ ไม่กี่คลิปที่ยาวไม่ถึง 10 นาที ก็มีฐานพอจะเข้าไปอ่านวรรณกรรมต่อได้
    • พูดตรง ๆ พอเห็นสิ่งนี้ขึ้นหน้าแรก ผมก็คาดหวังว่า distill จะหาทางเดินหน้าต่อได้แล้ว แต่ไม่ใช่

  • สำหรับผม GNN ค่อนข้างน่าผิดหวัง ลองนำไปใช้กับงานวิจัยหลายครั้ง แต่ไม่เคยออกมาดีเลย
    เป็นเวลานานที่ GNN ถูกนำเสนอเหมือนเป็นการ generalize ของ CNN แต่ CNN ทรงพลังกว่าเพราะ “น้ำหนักของเพื่อนบ้าน” มีความหมายมากกว่า มันเรียนรู้ความสัมพันธ์ของตำแหน่งสัมพัทธ์ ส่วน GNN มักพึ่งพา pooling อย่างที่อธิบายไว้ที่นี่ CNN สามารถสร้างภาพเป็นเอาต์พุตได้ แต่การสร้างกราฟเป็นเอาต์พุตด้วย GNN ไม่ใช่เรื่องง่าย โทโพโลจียังต้องกำหนดไว้ล่วงหน้า และบางครั้งต้องกำหนดแม้กระทั่งระหว่างการฝึก จุดตัดสินคือประสิทธิภาพ GNN ช้ากว่า CNN อย่างไม่น่าเชื่อ
    ทุกวันนี้ ด้วยเหตุผลเหล่านี้ attention ดูเหมือนจะเข้ามาแทนที่ GNN ไปมากแล้ว จะสร้าง GNN ที่ใช้ attention แทน pooling ก็ได้ แต่ก็ไม่ค่อยมีความหมายมากนัก โดยปกติกราฟจะถูกไล่ผ่านเพียงเพื่อสร้างเมทริกซ์มาสก์ แล้วส่วนที่เหลือก็ใช้ทรานส์ฟอร์เมอร์ธรรมดา ๆ ถ้ามีมาตรวัดระยะทางบางอย่างอยู่แล้วตั้งแต่แรก หลายครั้งก็ไม่จำเป็นต้องใช้แม้แต่ adjacency ของกราฟ
    GNN คงมีประโยชน์มากสำหรับใครสักคนที่ไหนสักแห่ง แต่จากประสบการณ์ของผม มันเหมือนค้อนที่กำลังมองหาตะปูมากกว่า

    • มีอย่างน้อยหนึ่งกรณีที่ GNN มีประโยชน์ คือเมื่อข้อมูลเป็นชุดของอะตอมที่นิยามรายการข้อมูลหนึ่งรายการผ่านปฏิสัมพันธ์กัน ขนาดของชุดนั้นใหญ่จนไม่สามารถใช้ attention ลุยแบบคร่าว ๆ ได้ ภายในชุดมี ความเป็นเพื่อนบ้าน/โครงสร้างเชิงเรขาคณิต ที่นิยามด้วยปฏิสัมพันธ์ และถ้ารักษาสิ่งนั้นไว้ ข้อมูลจะมีสมบัติ equivariance ต่อการเรียงสับเปลี่ยน แต่กลับไม่มีวิธีที่มีความหมายในการแสดงโครงสร้างเรขาคณิตนั้นแบบ implicit ตัวอย่างเช่น กรณีที่โครงสร้างเปลี่ยนไปในแต่ละ sample จึงส่งโครงสร้างเพื่อนบ้าน/ปฏิสัมพันธ์เข้าไปเป็นอินพุตให้ประมวลผล
      แทบทุกกรณีอื่น สามารถใช้โครงสร้างเพิ่มเติมเพื่อทำให้มีประสิทธิภาพมากขึ้นได้ ถ้ากำหนดลำดับได้ก็ใช้ sequential model ถ้าเป็นโครงสร้างแบบยุคลิด/รีมันน์ก็ใช้ CNN หรือโมเดลที่รับรู้แมนิโฟลด์ ถ้าไม่ต้องการสถานะระดับ global ก็ใช้ point cloud network ถ้ามีลำดับชั้นชัดเจนก็ใช้ U-Net เวอร์ชันของ modality นั้น ๆ
      เหตุผลที่ GNN น่าสนใจคือ 1) มัน encode แนวคิดของ ความสัมพันธ์ เอง และ 2) มันสัมพันธ์ได้ดีกับสมการเชิงอนุพันธ์แบบดิสครีไทซ์ที่ทั่วไปโดยสมบูรณ์ ในฐานะคนสายระบบซับซ้อน/ระบบพลวัต มันน่าสนใจ แต่ถ้าสามารถทำให้เฉพาะทางได้ ก็ยังมีวิธีที่ง่ายกว่าอยู่ดี
    • สงสัยว่ากำลังพูดถึงการจัดการข้อมูลที่มีความสม่ำเสมออย่างงาน vision หรือเปล่า
      ด้วยเหตุผลที่กล่าวมา ผมคิดว่าไม่ใช่เรื่องบังเอิญที่ GNN ได้รับความนิยมหลัก ๆ ในโดเมนอย่าง recommendation ซึ่งตัวโมเดลโดเมนเองให้ความรู้สึกเหมือนกราฟ ในโดเมนแบบนั้น การกระโดดไปสู่โทโพโลจีที่มีประโยชน์ไม่ไกลนัก
      สิ่งที่ผมรู้สึกหงุดหงิดกว่านั้นคือ ในโดเมนแบบกราฟจำนวนมาก ข้อมูลมักเป็นข้อมูลเครื่อง/มนุษย์ที่อิงพฤติกรรม เช่น log และมีมิติเชิงหมวดหมู่จำนวนมาก ส่วนกราฟก็ช่วยได้ แต่การจับ มิติเชิงหมวดหมู่ ให้ดีก็สำคัญไม่แพ้กัน และถ้าจะทำให้ดี ก็มักต้องหลุดไปใช้วิธีนอกโมเดลอย่าง random forest เริ่มจากสิ่งเหล่านั้นง่ายกว่า ส่วน GNN จะทำให้งานเพิ่มขึ้นมากเพื่อ “การปรับปรุงที่ดีขึ้นอีกเล็กน้อย”
      แน่นอน ถ้านี่เป็นธุรกิจหลักและมีเงินหลายล้านดอลลาร์เป็นเดิมพัน ก็อาจสมเหตุสมผล แต่ก็ยังยากสำหรับทีมปฏิบัติการส่วนใหญ่ ในทางปฏิบัติ มักจบด้วยการทำสิ่งอย่าง xgboost + umap กับผู้ใช้ pygraphistry แล้วข้ามไป แค่ทำให้ RGCN ทำงานได้ดีก็ใช้แรงมากแล้ว
    • GraphCast ของ Google เป็น GNN: https://deepmind.google/discover/blog/graphcast-ai-model-for...
    • ผมก็เจอคล้าย ๆ กัน เคยเห็นข้อเสนอจำนวนมากให้ใช้ GNN กับปัญหาที่เดิมใช้โมเดลแบบ “แบน” เช่น พิจารณาโครงสร้าง HTML ตอนทำนาย label ของหน้า แม้ในกรณีที่ดูเผิน ๆ เหมือนจะเข้ากันดีมาก ก็ไม่ได้ผลดีนัก
    • ผมติดตาม GNN ในชีววิทยาและลองนำไปใช้กับบางโดเมน แต่จนถึงตอนนี้ผลลัพธ์น่าผิดหวังอยู่บ้าง แปลกใจเล็กน้อยเพราะเคยใช้แนวทางอื่นที่อิงกราฟในชีววิทยาได้สำเร็จ

  • GNN ดูเหมือนจะทำงานบน โทโพโลจีที่คงที่ แล้วถ้าต้องการประมาณการแปลงบางอย่างของโทโพโลยีกราฟควรทำอย่างไร เช่น การเรียนรู้ graph layout หรือการเปลี่ยน abstract syntax tree ของโปรแกรมให้เป็น data flow graph

  • แก่นสำคัญของ GNN คือการกำหนดเงื่อนไขแนวคิดเรื่อง “เพื่อนบ้าน” อย่างชัดเจนด้วยกราฟที่ระบุโทโพโลยี ทำให้สามารถทำให้เป็นกรณีทั่วไปกับ โทโพโลยีใดก็ได้ การจัดวางกราฟเคยถูกลองใช้ที่นี่ และ https://github.com/limbo018/DREAMPlace ก็ได้รับความสนใจมาก แต่ช่วงหลังมีข้อถกเถียงที่เกี่ยวข้องด้วย https://www.semanticscholar.org/paper/The-False-Dawn%3A-Reev...
    การแปลงกราฟก็กำลังมีการศึกษาอยู่ https://arxiv.org/abs/2012.01470 แต่เป็นปัญหาที่ยาก เพราะโดยนัยแล้วต้องแก้ ปัญหาการจับคู่กราฟ

    • โฮโมโลยี อาจช่วยได้ มันเหมือนแคลคูลัสชนิดหนึ่งสำหรับโครงสร้างแบบไม่ต่อเนื่อง เป็นวิธีนับว่ามีรูมิติ N กี่รูเมื่อเวลาผ่านไป ผมไม่แน่ใจเรื่องโครงข่ายประสาท แต่กับ fMRI สามารถใช้ในลักษณะนั้นได้

  • อยากให้ distill กลับมาอีกครั้ง

  • เสียดายจริง ๆ ที่ distill.pub ไม่รับบทความส่งใหม่แล้ว

  • สงสัยว่าซอฟต์แวร์สร้างภาพแบบอินเทอร์แอคทีฟนั้นคืออะไร เป็น D3.js หรือเปล่า?

  • ผมรู้สึกว่าตัวเองโง่มาก ในหน้านั้นมีตัวอย่างที่มี 4 โหนด (a,b,c,d) และแสดงว่ามีชุดค่าผสมที่เป็นไปได้ทั้งหมด 24 แบบ
    ผมสงสัยว่าสูตรทั่วไปในการคำนวณสิ่งนี้คืออะไร เมื่อกำหนดจำนวนโหนด และเมื่อต้องพิจารณาเส้นเชื่อมด้วย บทความดูเหมือนไม่ได้อธิบายไว้ และผมคิดว่าอาจเป็น แฟกทอเรียล ก็ได้

    • คอมบินาทอริกส์มักคำนวณได้อย่างรวดเร็วด้วย แฟกทอเรียล ถ้ามีตัวเลือกที่เป็นไปได้ 4 ตัว และในแต่ละกรณีต้องเลือกทั้ง 4 ตัวอย่างละหนึ่งครั้งพอดี นั่นคือ 4! ถ้าคิดแบบสัญชาตญาณ ตอนเลือกครั้งแรกมี 4 ตัวเลือก ครั้งถัดไปเหลือ 3 ตัวเลือก ถัดไป 2 ตัวเลือก และสุดท้ายเหลือ 1 ตัวเลือก ดังนั้นจึงเป็น 4 * 3 * 2 * 1 = 24
      ถ้าอยากคุ้นเคยมากขึ้น เว็บไซต์นี้ดูเหมือนให้ภาพรวมที่ค่อนข้างดี: https://www.geeksforgeeks.org/mathematics-combinatorics-basi...
    • ผมคิดว่านี่น่าจะคำนวณได้ด้วย สัมประสิทธิ์ทวินาม หรือสัมประสิทธิ์ทวินามแบบซ้อนกัน เช่น (n choose 4)
      เนื่องจากแต่ละเส้นเชื่อมอาจมีอยู่หรือไม่มีอยู่ ก็อาจคูณสัมประสิทธิ์ทวินามด้วย 2 ได้