Notifications
Clear all

Graph Neural Networks (GNNs) สำหรับผู้เริ่มต้น อย่างละเอียด

5 ข้อความ
1 Users
0 Likes
3,270 Views
The Neural Engineer
(@neural-engineer)
Honorable Member Admin
เข้าร่วมเมื่อ: 6 years ago
ข้อความ: 399
Topic starter  

Graph Neural Networks สำหรับผู้เริ่มต้น (tutorial อธิบายแนวคิดเบื้องต้นอย่างละเอียด)

ThaiKeras and Kaggle - 9 Jan 2022

 

สวัสดีครับ ถ้าถามถึงโมเดล Deep Learning ที่คนส่วนใหญ่ใช้งานมากที่สุด รวมทั้งให้ประสิทธิภาพความแม่นยำสูงสุด เชื่อว่า Convolution Neural Networks (CNNs) และ Transformers น่าจะเป็น 2 โมเดลที่พวกเรานึกถึงเป็นอันดับแรก เนื่องจากสองโมเดลนี้ใช้งานได้กับประเภท Data ที่พบกันได้มากที่สุด เช่น รูปภาพ วิดิโอ ข้อความ และเสียง (Image, Video, Text และ Speech) เป็นต้น

อย่างไรก็ดียังมีข้อมูลอีกหลายประเภทที่มีโครงสร้างเฉพาะ ทำให้ CNNs หรือ Transformers ไม่สามารถใช้ประโยชน์จากโครงสร้างเฉพาะนั้นได้ในประโยชน์สูงสุด เช่น

  • ข้อมูล Social Media เช่น Pinterest ที่มี data อยู่สองประเภทคือ "Pin" (รูปภาพ) และ "Board" (คอลเลคชั่นของรูปภาพ) โดยแต่ละ Pin อยู่ได้หลายบอร์ด และแต่ละบอร์ดมีได้หลาย Pins ตามรูปที่ 1 และเราต้องการให้โมเดลทำนายความสัมพันธ์ระหว่าง Pin และ Board 

สังเกตว่าปัญหานี้ input จะประกอบไปด้วยรูป pin หลายๆ รูปเชื่อมโยงกัน ซึ่งต่างจากกรณีใช้งานของ CNNs ปกติ ที่มักใช้ทำนายคุณสมบัติของรูปภาพ หรือ Pin ทีละรูป

  • ข้อมูลทางเคมี เช่น ปัญหาการคิดค้น "ยา" ประเภทใหม่ (Drug Discovery) โดยตัวยานั้นแท้จริงแล้วคือ "โมเลกุล" ของอะตอมต่างๆ ทางเคมีที่มาอยู่รวมกันด้วยพันธะทางเคมีต่างๆ ซึ่ง Transformers หรือ CNNs ไม่สามารถนำโครงสร้างของ "พันธะ" เหล่านั้นมาคำนวนในโมเดลได้โดยตรง ดูรูปที่ 2

  • ข้อมูลทางชีววิทยา เช่น สายสตริง RNA ซึ่งประกอบไปด้วยตัวอักษร A G U C ซึ่งในการโมเดลและทำนายคุณสมบัติของ RNA นั้นเราอาจจะมองว่า RNA เป็น string ธรรมดาเรียงต่อกัน และใช้โมเดลเช่น Recurrent Neural Networks (RNNs) หรือ Transformers ก็ได้ ทว่าแท้จริงแล้วสายสตริง RNA นั้นมี "รูปร่าง" การขดตัวเฉพาะตัวอยู่ ดังแสดงในรูปที่ 3 และข้อมูลที่จุดที่แต่ละตัวอักษรสัมผัสกันนั้น ไม่สามารถป้อนให้ RNNs หรือ Transformers ตรงๆ ได้

 

ตัวอย่างทั้ง 3 และข้อมูลที่เจอใน applications อื่นอีกมากมายนั้นสามารถ represent ได้ด้วย "กราฟ" ทางคณิตศาสตร์ ซึ่งประกอบไปด้วยเซ็ตของ Nodes และเซ็ตของ Edges โดย edge ก็คือเส้นเชื่อมระหว่าง 2 nodes ใดๆ ในกราฟ ซึ่งจะเห็นได้ว่าไม่ว่าจะเป็น พันธะเคมี การเชื่อมระหว่าง Pin/Board หรือตัวอักษรที่ติดกันในสาย RNA สามารถโมเดลด้วย edge ในกราฟได้

นั่นคือในปัญหาดังกล่าว เราสามารถระบุ input ให้อยู่ในรูปกราฟได้นั่นเอง ดังนั้นจึงเป็นจุดกำเนิดโมเดล deep learning ประเภทใหม่ที่สามารถรับกราฟเป็น input เพื่อทำนายในสิ่งที่เราสนใจได้ ซึ่งโมเดลที่ว่านั้นก็คือ Graph Neural Networks (GNNs) นั่นเอง

(ทบทวนทฤษฎีกราฟที่นี่ https://en.wikipedia.org/wiki/Graph_theory )

 

.

 

Graph Neural Networks (GNNs)

GNN ก็คือโมเดล neural network ที่รับกราฟเป็น input และ output เป็นคำทำนาย ซึ่งโดยปกติทำนายได้ 3 รูปแบบ คือ Graph prediction, node prediction และ edge prediction เช่น

  • Graph prediction ใน Drug Discovery : ทำนายว่า "กราฟ" ของโมเลกุลนั้นสามารถทำหน้าที่เป็น "ยา" (ฆ่าเชื้อ หรือยับยั้งเชื้อ ฯลฯ) ได้ดีหรือไม่ ดังแสดงในรูปที่ 4
  • Node prediction ใน RNA string : ทำนายว่าแต่ละโหนดในกราฟของ RNA นั้น "ทนทาน" ต่อความร้อนในมากแค่ไหน (ทำนายทุกโหนดในกราฟ)
  • Edge prediction ใน Pinterest : ทำนายว่า Pin ใหม่ที่ user เพิ่ง upload เข้ามาควรจะถูก recommend ใน board ใดหรือไม่ (มี edge เชื่อมระหว่างโหนด pin และโหนด board หรือไม่)

.

 

ว่าด้วยเรื่องการระบุ input ให้อยู่ในรูปกราฟ

ใน CNNs หรือ Transformers , inputs นั้นจะอยู่ในรูปของ vectors หรือ matrix หรือ tensor ขึ้นกับจำนวนมิติของ input เช่น image 1 รูปอาจเป็น 3D tensor ขนาด 512x512x3 ส่วน texts อาจเป็น sequence of vectors (หรือ matrix = 2D tensor) อาทิ เช่น 2,048 x 500,000 โดย 2048 คือจำนวน "คำ" สูงสุดในข้อความและ 500,000 คือ 1-hot vector ที่ระบุ vocabulary หรือคำศัพท์ทั้งหมดที่โมเดลรู้จัก เป็นต้น

 

เมื่อ input เราเป็นกราฟนั้น ตามนิยาม inputs ก็มักจะประกอบไปด้วย input สองส่วน นั่นคือ node-input และ edge-input นั่นเอง ดั่งแสดงในรูปที่ 5

นั่นคือเรา represent Graph G = (X, A) โดย X แทน vectors ทั้งหมดของทุกโหนดในกราฟ ,  ส่วน A ระบุ edges ในกราฟ

 

ในรูปที่ 5 แสดงกรณีเรามี input 3 กราฟ ซึ่งแทนด้วย G_1สีส้ม G_2เขียว G_3น้ำเงินตามลำดับ

สังเกตกราฟ G_1 สีส้ม

  • X_1 ก็คือ matrix ที่แต่ละแถวประกอบไปด้วย vector ของแต่ละโหนด
  • A_1 คือ Adjacency-matrix หรือ Edges-matrix ที่ระบุว่าโหนดใดเชื่อมต่ออยู่กับโหนดใด เช่น ในตัวอย่างนี้มีโหนดทั้งหมด 5 โหนดแทนด้วย x0, x1, x2, x3, x4 สังเกตจากสีได้ว่า A_1 ระบุว่า node x_0 เชื่อมกับ x_1 และ x_3 เป็นต้น โดย A_i อาจเป็น 0/1 หรืออาจเป็น real number ซึ่งแสดง weight ของ edge ก็ได้

 

.

 

ในการเขียนโค้ดเช่น keras  เนื่องจากกราฟนั้นแทนด้ย 2 input tensors, แทนที่เราจะเรียก model.fit(X,y) ตามปกติเหมือนโมเดลอื่นๆ

เราก็จะต้องเตรียม 2 inputs X,A และเรียกใช้งานแบบนี้ครับ

model.fit([X, A], y)

(โค้ด keras ในบทความหน้า)

.

 

ในปัญหา drug discovery นั้น 1 กราฟแทนด้วย 1 โมเลกุลของยาที่เราต้องการทดสอบ ทำนองเดียวกันกับปัญหา RNA ที่ 1 กราฟแทนด้วย 1 RNA string

ในปัญหา Pinterest's edge prediction ที่อธิบายข้างต้นนั้น การออกแบบกราฟอาจจะไม่ชัดเจนเท่า 2 ปัญหาข้างต้น โดยในทางปฏิบัติเราอาจจัดหมวดหมู่ category ของรูปภาพตาม popular tags โดยอาจจะเจาะจง 10,000 tags ที่ได้รับความนิยมสูงที่สุด  และแทนให้แต่ละ tag คือ 1 กราฟ

โดยแต่ละ กราฟ นั้นก็จะมี pin และ board ทั้งหมดที่ถูก tag นั้นๆ อยู่ในกราฟ ซึ่งในกรณี pinterest นั้นแต่ละกราฟจะมีขนาดใหญ่มหึมา เนื่องจากแต่ละกราฟอาจประกอบไปด้วยรูป pin ถึงหลักแสน หลักล้าน หรือมากกว่า

 

.

 

เรา represent node-input ในรูป vector ได้อย่างไร?

ในกรณีของโมเลกุลและ RNA นั้นเราสามารถใช้ one-hot vector เพื่อระบุว่าแต่ละโหนดเป็น โมเลกุล/RNA-base ประเภทใด และเรียนรู้ embedding vector ของ 1-hot vector นั้นๆ อีกที (ใช้ tf.keras.layers.Embedding )

 

ส่วนตัวอย่าง Pinterest ซึ่งแต่ละกราฟประกอบไปด้วยโหนดซึ่งแทนด้วยรูปภาพ pin หลักล้านรูป และโมเดล GNN ต้องรับ input นี้เข้าไปเพื่อทำนายนั้น

อาจทำให้สงสัยว่าจะเป็นไปได้ในทางปฏิบัติหรือ เพราะในกรณี CNNs ปกตินั้นแค่รับ input ด้วยภาพขนาด 1 batch นั้นในแต่ละ batch ก็มักจะมีขนาดหลักร้อยหรือหลักพันเท่านั้น สำหรับ GPU ที่มีหน่วยความจำมาตรฐานขนาด 16GB-32GB

 

ในกรณีของ Pinterest และ GNN นั้นแต่ละรูปไม่จำเป็นต้อง input ด้วย raw image (เช่น ขนาด 512x512x3) แต่อาจจะเป็น processed vector หรือ image vector ที่ผ่านโมเดล Neural Networks อื่นมาก่อนแล้ว เช่นเป็น Pooling output ของ EfficientNet-B0 ซึ่งเป็น vector ขนาด 1280x1 เป็นต้น

 

(ยิ่งไปกว่านั้น ในกรณีนี้ Pinterest ยังออกแบบ Graph sampling หรือการสุ่ม sub-graph เพียงบางส่วนขึ้นมาทำนายเพื่อประหยัดขนาดของข้อมูลได้อีก ดูรายละเอียดได้ที่ Pinterest blog : https://medium.com/pinterest-engineering/pinsage-a-new-graph-convolutional-neural-network-for-web-scale-recommender-systems-88795a107f48 )

.

 

Message passing ใน GNN

หัวใจของโมเดล Deep Learning เช่น CNNs หรือ Transformers ก็คือการเปลี่ยน input ที่อยู่ในรูปแบบดั้งเดิม (raw) เปลี่ยนให้เป็นเวกเตอร์ทางคณิตศาสตร์ (เรียก embedding vector) เช่น EfficientNet เปลี่ยนรูปภาพ 512x512x3 ให้เป็น 1280x1  หรือ BERT Transformers เปลี่ยน 1-hot vector ของ "คำศัพท์" แต่ละคำเป็น 768x1 เป็นต้น

 

โดยการเปลี่ยนข้อมูล input จาก raw ให้เป็นเวกเตอร์นั้นถ้าพูดกันในภาพรวมจะผ่าน 2 กระบวนการดังนี้ (ดูรูปที่ 6)

[1] นำ input เข้า non-linear transformation เมื่อได้ output แล้วก็นำ output นั้นไปเข้า non-linear transformation บล็อกถัดไป ทำอย่างนี้ต่อเนื่องหลายๆ ครั้ง (หลายๆ บล็อคสี่เหลี่ยมในรูปที่ 6) ซึ่งใน Deep Learning นั้น แต่ละ transformation block ก็คือ Neural Network layer นั่นเอง และการทำ transformation ต่อเนื่องหลายรอบนี้เอง ที่เป็นที่มาของคำว่า "Deep" (ลึก) เพราะ Neural network ที่เอา layers มาต่อกันนับสิบหรือร้อย layer เปรียบเปรยได้กับสมการที่มีความยาว หรือ "ความลึก" มากนั่นเอง

 

[2] ตรงนี้สำคัญมาก -- ในแต่ละ transformation layer นั้น แต่ละโมเดลจะออก "กระบวนการ process input-ย่อย" ที่แตกต่างกัน -- หมายเหตุ input-ย่อย ของรูปภาพคือจุด pixel, หรือ input-ย่อยของข้อความก็คือ "แต่ละคำในข้อความ" เป็นต้น ส่วน input-ย่อยของกราฟ ก็คือโหนดนั่นเอง -- โดยทุกโมเดลที่เรารู้จักกันดีจะมีแนวคิดในการ process input-ย่อยด้วยแนวคิดที่เรียกว่า "Message Passing" หรือ "การกระจาย information จาก input-ย่อยหนึ่ง ไปยังอีก input-ย่อยหนึ่ง" ที่ต่างกันออกไป ดูรูปที่ 7 และรูปที่ 8 เช่น

    1. ใน CNN นั้น message passing ระหว่าง pixel นึงไปยังอีก pixel จะผ่านกระบวนการที่เรียกว่า convolution นั่นคือ, pixel นึงจะรับ information ( information ที่ส่งผ่านกันนิยมเรียกว่า "message") จาก pixel รอบข้าง
    2. ใน RNN นั้น message passing จะทำจากคำที่อยู่ติดกัน ส่งไปยังคำถัดไปเรื่อยๆ (ถ้าเป็น bi-directional ก็คือส่ง message ทั้งจากคำด้านหน้า และคำด้านหลัง)
    3. ใน Transformer นั้น message passing จะเป็นแบบ "fully connected" นั่นคือ ทุกๆ "input-ย่อย" (เช่น คำแต่ละคำในข้อความ) ก็จะกระจาย information หรือ message ไปให้ทุกๆ input-ย่อย นั่นคือคำอื่นๆ ทั้งหมด

 

การออกแบบ message-passing นี้ส่งผลอย่างมีนัยสำคัญกับประสิทธิภาพของแต่ละโมเดล โดยจะดีหรือไม่ขึ้นอยู่กับประเภทของข้อมูล input เช่น message passing ของ Transformer นั้นเหมาะสมกับข้อมูลข้อความ มากกว่า message-passing ของ RNN มาก เพราะ information นั้นสามารถกระจายถึงกันได้อย่างเหมาะสม (ตัวอย่างเช่นคำว่า "it" ในข้อความเช่น "Dog is a very good friend of mine. I love it." โยงกับคำว่า "Dog" ซึ่งมีตำแหน่งอยู่ 10 คำก่อนหน้า "it"

โดย RNN นั้น message จาก 10 คำก่อนหน้าจะไม่ส่งมาถึงคำปัจจุบันโดยตรงได้เหมือน transformer) นั่นทำให้ปัจจุบันโมเดล transformer นั้นมาทดแทน RNN ไปแทบจะสิ้นเชิง

 

ทว่าใน input ที่เป็นรูปภาพนั้น การกระจายข้อมูล local message passing ของ CNN ที่เน้นกระจายข้อมูลจาก pixel ใกล้ๆ กัน ก็ยังมีประสิทธิภาพดีกว่าของ Transformer ที่กระจายข้อมูลจากทุกจุดในภาพไปยังจุดอื่นๆ อีกทั้งหมดในภาพ เป็นต้น

 

 

รูปที่ 7

ซ้าย - message passing ใน convolution ของ CNN จะทำผ่าน pixel รอบข้าง

ขวา - message passing ของ GNN จะกระทำผ่านโหนดรอบข้าง ซึ่งพยายามทำให้ใกล้เคียงกับแนวคิดของ convolution นั่นเอง

 

รูปที่ 8 บน message passing ของ RNN จะทำจากคำที่อยู่ติดกัน

ล่าง message passing ของ transformer จะส่งจากทุกๆ คำไปยังทุกๆ คำ (ซึ่งพบว่าเหมาะสมกับ input ที่เป็นข้อความมากกว่า RNN)

 

 

สำหรับ GNN นั้นโมเดลก็จะประกอบไปด้วย neural network layers หลาย layers เช่นเดียวกันกับโมเดลอื่นๆ ส่วน message passing ในกราฟนั้นโมเดลส่วนใหญ่จะออกแบบให้ส่ง information หรือ message ผ่าน "edges" ในกราฟ ดังแสดงในรูปที่ 7 ครับ ซึ่งการกระจายข้อมูลแบบนี้สามารถแปลงเป็น programming code ได้อย่างง่ายดาย และถือได้ว่ามีการใช้ "โครงสร้างของกราฟ" ที่เราเกริ่นในตอนต้นของบทความได้อย่างเหมาะสม ซึ่งเราจะดูโค้ดกันในบทความหน้า

 

สำหรับแนวคิดการออกแบบ GNN ก็น่าจะมีราวๆ นี้นะครับ ซึ่งบทความนี้พยายามอธิบายให้ง่ายที่สุดแบบบ้านๆ  จึงอาจจะไม่เป็นทางการบ้าง ทว่าเพื่อนๆ สามารถศึกษาแนวคิด GNN "อย่างจริงจัง" เพิ่มเติมได้จากแหล่งอ้างอิง 2 ที่นี่นะครับ

 

 

ในคราวหน้าเราจะมาศึกษา GNNs ที่มาตรฐานที่สุดคือ Graph Convolution Networks (GCNs) และ Graph Attention Networks (GATs) พร้อม Keras code และ Keras library ที่ชื่อ Spektral กัน

This topic was modified 2 years ago by The Neural Engineer

   
อ้างอิง
The Neural Engineer
(@neural-engineer)
Honorable Member Admin
เข้าร่วมเมื่อ: 6 years ago
ข้อความ: 399
Topic starter  

Convolutional และ Attentional GNNs (อธิบายแนวคิดและที่มาของสมการอย่างละเอียด สำหรับผู้เริ่มต้น)

ThaiKeras and Kaggle -  16 Jan 2022

จากบทความอธิบายแนวคิดพื้นฐานของ GNNs ( https://web.facebook.com/thaikeras/posts/961868211394526 ทวนก่อนอ่านบทความนี้นะครับผม 😉  เราได้ทราบเรื่องสำคัญที่ต้องรู้ก่อนใช้งาน GNNs ดังนี้

  •  Input ของGNNs เป็นกราฟ ซึ่งประกอบไปด้วย tensor 2 ส่วน คือ Node-tensor-input และ Edge-tensor-input ซึ่งต่างจากโมเดลพื้นฐานเช่น CNNs และ Transformers ที่ input มักจะมีเพียง 1 tensor
  • "Message passing" คือแนวคิดสำคัญของการออกแบบการประมวลผลในแต่ละ layers ของ Deep learning ไม่ว่าจะเป็น CNNs, RNNs หรือ Transformers  … GNN layers ในยุคแรกนั้นมีแรงบันดาลใจจาก convolution message passing ใน CNNs
  • เมื่อเรานำ GNN layers มาซ้อนกันหลายชั้น ตามรูปที่ 1 (ในทำนองเดียวกันกับ Deep CNNs และ Deep Transformers) เราก็จะได้ Deep GNNs ซึ่งจะเปลี่ยน raw-node-input X ไปเป็น node-embedding-vectors H หรือบางครั้งเรียก node-latent-vectors … สังเกตจากรูปว่า edge-input A จะไม่ได้ถูก transform
  • จาก output node-embedding-vectors H = (h_1, …, h_n) เราสามารถนำไปทำ Node prediction / Edge prediction / Graph prediction ได้ โดยแสดงในรูปที่ 1 โดยหลักการง่ายๆ ก็คือนำ Dense layer (tf.keras.layers.dense) มาต่อเข้ากับ nodes ที่ต้องการจะทำนาย เช่น ถ้าต้องการทำนาย edge ระหว่าง 2 nodes, ก็นำ vectors ของทั้ง 2 nodes นั้นมา concat กันก่อนต่อด้วย dense layer เป็นต้น

ในบทความนี้เราจะทำความรู้จักกับ GNNs 2 ชนิดที่น่าจะมาตรฐานที่สุด คือ Graph Convolution Networks (GCNs) และ Graph Attention Networks (GATs) โดย GCNs ได้รับแรงบันดาลใจจาก CNNs โดยตรง ส่วน GATs นั้นได้นำความคิดของ attention mechanism ใน transformer มาปรับปรุง GCNs อีกที

.

 

Graph Convolution Networks (GCNs)

อ้างอิง Kipf & Welling, ICLR2017 : https://arxiv.org/abs/1609.02907

GCN ก็คือ GNN ที่นำ GCN layer มาต่อกันหลายๆ ชั้น

โดย GCN layer นั้นมีไอเดียง่ายๆ คือ ดัดแปลงสมการของ (fully-connected) perceptron layer ซึ่งอธิบายได้ดังนี้

 

ก) เริ่มจากสมการพื้นฐาน linear perceptron (ดูรูปที่ 2 ประกอบ)

h = Wx + b  --- x เป็น input-vector, และ W เป็นตัวแปรที่เราจะเรียนจากการสอน (เช่นผ่าน model.fit ใน keras)

 

ข) เขียนสมการข้างต้นให้อยู่ในรูป matrix, เพื่อรับ input พร้อมกันมากกว่า 1 input

H = WX + b --   แต่ละ column ใน X แทน input x_i ทำให้ output ก็จะเป็น matrix เช่นกัน

 

ค) เพิ่ม nonlinearity เช่น relu function

H = relu(WX + b) -- nonlinear perceptron สมการมาตรฐานของ tf.keras.layers.dense

.

*จุดสำคัญ* ง) ดัดแปลงสมการของ perceptron เล็กน้อยให้มี message passing จากโหนดที่ติดกันก่อนที่จะทำ nonlinear transform 

กำหนดให้ A เป็น Adjacency หรือ Edge matrix ซึ่งเป็นอีกหนึ่ง input จากกราฟ G = (X,A) เราจะได้สมการ

H = relu(WXA + b)  

 

หรืออาจจะเป็น activation function อื่นๆ นอกจาก relu ก็ได้ครับ

ในการทำความเข้าใจเทอม WXA ลองจินตนาการตามนี้ครับ,

  • จินตนาการให้ X' = WX ซึ่งแต่ละ column i ของ X' ก็คือ x'_i หรือเวกเตอร์ที่ linear transform x'_i = Wx_i มาแล้ว,
  • จินตนาการให้ A เป็น 0/1 matrix, นั่นคือ A_ij = 1 ถ้าโหนด i,j นั้นเชื่อมกันในกราฟ  …

พิจารณา column j ซึ่งก็คือ vector a_j ที่ระบุโหนดอื่นๆ ทั้งหมดที่เชื่อมกับโหนด j ไว้

(ในกรณีทั่วไป A ไม่จำเป็นต้องเป็น 0/1 แต่การทำความเข้าใจจะคล้ายกันครับ)

 

  • เราจึงได้ว่าใน WXA นั้นเพียงพอที่เราทำความเข้าใจเทอม X'a_j ซึ่งก็คือ "ผลรวม" (หรือ message) จากโหนด x’ ทั้งหมดที่เชื่อมกับ j นั่นเอง …

ซึ่งไอเดียคล้ายๆ convolution ที่ pixel หนึ่งจะได้รับ information message จาก pixels รอบข้าง

  • h_j =  relu(X'a_j + b) จึงเป็น nonlinear output ของกระบวนการนี้ โดย bias-vector b ช่วยให้ output มีความหลากหลายมากขึ้น …
  • Matrix output H = (h_1, …, h_n) จึงเป็นผลลัพธ์ของ nonlinear message passing ทั้งหมดของทุกโหนดจาก edge ในกราฟ

สังเกตว่าสมการ H = relu(WXA + b)  นั้นต่างจากสมการของ perceptron layer เพียงการส่ง message ด้วยการใช้ edge-input A เท่านั้น

 

.

จ) อย่างไรก็ดี Kipf & Welling นักวิจัยผู้คิดค้น GCN ได้ดัดแปลงสมการดังกล่าวเพิ่มอีก 2 จุด คือ

 

[จ1] กำหนดให้ A+I แทนที่จะใช้ A เฉยๆ ซึ่ง I คือ Identity matrix เท่ากับเป็นการเพิ่ม self-loop เข้าไปใน edge-input เนื่องจากต้องการให้ message ของ node_j ใน layer นึงๆ มี message ของตัวเองส่งมาจาก layer ก่อนหน้าด้วย

[จ2] normalized edge-matrix (A+I) เพื่อให้ output มีความเสถียรภาพในทางคณิตศาสตร์ขึ้นครับ

โดยเรียก normalized matrix ของ (A+I) ว่า A' ซึ่งสามารถ normalize ได้ 2 รูปแบบ คือแบบ simple และ symmetric ดูรายละเอียดตัวแปร A'  ได้ใน paper GCN ที่อ้างอิงด้านบนครับ

(สังเกตว่า A' ยังเป็นค่าคงที่ คำนวนได้จาก Edge-inupt ไม่ได้เป็นตัวแปรที่จะเรียนรู้ผ่าน model.fit )

.

 

โดยสรุปเมื่อเราดัดแปลง 2 จุดนี้แล้ว เราจะได้สมการ GCN layer ดังนี้

H = relu(WXA' + b)

หมายเหตุ 1: ในหลายบทความ (เช่นรูปที่ 3) มักกำหนดให้ H และ X เป็น matrix ของ row vectors แทนที่จะเป็น column vectors

ทำให้สูตรที่เห็นบ่อยๆ จะสลับด้านกับสมการด้านบนดังนี้ครับ

H = relu(A'XW + b)

.

หมายเหตุ 2: เราเริ่มต้นอธิบายของสมการ GCN layer ด้วย perceptron layer ซึ่งมีอีกชื่อว่า fully-connected dense layer คำว่า "fully-connected layer" นี้

อาจทำให้สับสนกับ "fully-connected graph" ซึ่งเป็นการทำ message passing ของ transformer attention layer — ขออธิบายเพื่อไม่ให้สับสนดังนี้ครับ

 

แท้จริงแล้ว เราต้องแยกระหว่าง feature-level กับ vector-level ครับ

  • perceptron นั้นพูดถึง fully-connected ในแง่ feature-level (ทุกๆ features ใน vector ของ 1 example) จะกระจาย information หากัน

** แต่ไม่มีการกระจาย message/information ข้าม examples หรือ feature-vectors กัน **

  • Transformer นั้นเป็น fully-connected GNN ซึ่งก็คือระดับ vector-level นั่นคือจะมีการกระจาย message จาก แต่ละ vector ไปยัง vector อื่นๆ ทั้งหมด

เช่น กระจาย (attend) word vector ในประโยคไปยัง word-vectors อื่นๆ ทั้งหมดในประโยค เป็นต้น

 

.

Graph Attention Networks (GATs)

อ้างอิง Velickovi et. al. ICLR 2018: https://arxiv.org/abs/1710.10903

จากสมการ message passing ของ GCN layer, แม้จะมีการกระจาย message/information จากโหนดติดกันในกราฟอย่างที่ควรจะเป็น

ทว่า **น้ำหนัก** หรือ weights ของแต่ละ message นั้นถูกกำหนดจาก matrix A อย่างตายตัวครับ

 

Graph Attention Networks (GATs) ได้เสนอวิธีปรับปรุงให้แต่ละโหนดส่ง message หากันได้ด้วย "น้ำหนัก"

ขึ้นกับ "ความคล้าย" กันของโหนดคู่ใดๆ ที่เชื่อมกัน --- คู่โหนดที่ "คล้ายกัน" มากกว่า ก็ควรจะมีน้ำหนักของ messgage มากกว่า

คู่โหนดที่ "ไม่คล้ายกัน"

 

โดย GAT layer นั้นใช้ Attention mechanism สำหรับแต่ละ edge เพื่อคำนวณและ normalize "ความคล้าย" นี้ โดยเรียก

ความคล้ายว่า "attention score" นั่นเอง ดูรูป 4 ประกอบครับ (attention score คือตัวแปร alpha ในรูป)

 

 

สมการของ GAT layer นั้น แท้จริงแล้วเขียนได้เหมือน GCN layer นั่นคือ

H = relu(WXA' + b)

เพียงแต่ว่าใน GAT นั้น, matrix A' จะเป็น learnable matrix ที่เรียนรู้ผ่าน model.fit ได้บน attention mechanism ครับ

ซึ่งทำให้โมเดลเรียนรู้ "น้ำหนักของ message ของแต่ละคู่โหนด" ที่ส่งให้กัน ต่างจาก GCN ที่ A' นั้นเป็น constant

 

โดยแต่ละ element alpha_ij ใน A' นั้นจะเกิดจากสมการนี้

alpha_ij = SoftMax( relu( ความคล้ายของโหนด_ij ))

 

โดยความคล้ายของโหนด i และ j นั้นคำนวณจาก dot-product ของ concat(x_i, x_j) กับ learnable-vector a ครับ

ซึ่ง vector a นี้จะเป็นค่าเดียวกันสำหรับทุกคู่ ij และเรียนผ่าน model.fit

 

ในสมการ alpha_ij นั้นเพิ่ม relu เข้าไปเพื่อให้ score >= 0, จากนั้นใช้ softmax เพื่อ normalize score ให้รวมกันเท่ากับ 1 สำหรับทุกโหนด

จากความเรียบง่ายของสมการด้านบน นับว่า GATs เป็นการอัพเกรด GCNs ที่ง่ายแต่สวยงามมากครับ

 

.

หมายเหตุ สังเกตว่า GATs แม้มีการใช้ attention mechanism แต่ยังขาดส่วนประกอบที่สำคัญมากใน original transformers ซึ่งก็คือ

“positional encoding” ซึ่งในช่วงปี 2020-2021 มีอีกหลายงานที่ได้ปรับปรุงและเพิ่มในส่วน Positional/Spatial embedding เข้าไป

เช่น ดูงานล่าสุดของ Microsoft ที่นี่ครับ https://github.com/microsoft/Graphormer

 

.

เขียน GCNs/ GATs บน keras

จริงๆ แล้วที่ keras.io นั้นมีตัวอย่างการ implement GCNs และ GATs ด้วยตนเองตั้งแต่แรก ซึ่งดูได้ที่นี่ครับ

 

GCN layer - https://keras.io/examples/graph/gnn_citations/

GAT layer - https://keras.io/examples/graph/gat_node_classification/

 

ทั้งสอง tutorial นี้อธิบายได้ดีและละเอียดมากครับ อย่างไรก็ดีถ้าเราไม่อยาก implement ด้วยตัวเองนั้นเราจะสามารถเรียกใช้

Layers เหล่านี้ได้ทำนองเดียวกันกับ Convolutinal layer หรือ RNN layer (ผ่าน tf.keras.layers ) ได้หรือไม่?

 

คำตอบคือ tf.keras.layers นั้นยังไม่ได้ implement GNN layers ทั้งหลายอย่างเป็นทางการครับ แต่ว่า F.Chollet

ผู้ให้กำเนิด Keras นั้นได้แนะนำ “spektral” ซึ่งเป็น external keras library ซึ่งใช้งานได้ง่ายและผสานกับ tf.keras.layers ได้อย่างกลมกลืน  

 

เพียง install lib นี้ก่อน

pip install spektral

 

แล้วก็ใช้ spektral layer ได้กับ keras layers อื่นๆ เลย เช่น minimal example นี้ครับ

 

</p>
<pre>from tensorgraph.layers.graph_convolutional import DenseGraphConvolution

from spektral.layers import GATConv, GCNConv




def build_model0(embed_size=32, seq_len=108):

    node_inputs = L.Input(shape=(seq_len,),name='node_inputs')

    edge_inputs = L.Input(shape=(seq_len, seq_len),name='edge_inputs')

    node_embed = L.Embedding(input_dim=embed_size,

                             output_dim=256)(node_inputs)

   

    n_layers=3

    for x in range(n_layers):

        node_embed = GCNConv(256)([node_embed, edge_inputs])

   

    out = L.Dense(5, activation='linear')(node_embed)

   

    model = tf.keras.Model(inputs=[node_inputs,edge_inputs],

                           outputs=out)

   

    return model</pre>
<p>

 

หมายเหตุ เดือนที่ผ่านมา Tensorflow ได้ออก official  TF-GNN library (แต่ไม่ใช่ keras interface) ซึ่งน่าจะมีประสิทธิภาพดีที่สุด แต่ยังใช้งานค่อนข้างยาก

และ documents ยังไม่ดีเหมือนกับ spektral ครับผม

 

----

 

สำหรับบทความ Tutorial นี้และบทความก่อน น่าจะทำให้เพื่อนเข้าใจถึงบทบาท และการทำงานของ GNNs พอสมควรทั้งความเข้าใจ สมการ และโค้ด

ในบทความหน้า เราจะลองใช้ GNNs ในการช่วยทำนายปัญหา Bioinformatics ที่สำคัญมากๆ  นั่นคือ Deep Prediction เกี่ยวกับคุณสมบัติของ RNA ครับ

This post was modified 2 years ago 2 times by The Neural Engineer

   
ตอบกลับอ้างอิง
The Neural Engineer
(@neural-engineer)
Honorable Member Admin
เข้าร่วมเมื่อ: 6 years ago
ข้อความ: 399
Topic starter  

ThaiKeras ได้ทำ Tutorial สำหรับงาน RNA Prediction และ DeepLearning อย่างละเอียดตั้งแต่เตรียมข้อมูล จวบจนสร้างโมเดลขั้นสูงอย่างง่ายๆ 

Tutorial เตรียม Features : www.kaggle.com/ratthachat/preprocessing-deep-learning-input-from-rna-string
Tutorial สร้าง DeepLearning model:  www.kaggle.com/ratthachat/tutorial-pretrained-sota-deeprna-model-made-easy  
(มี GCN เป็นส่วนประกอบของโมเดลครับ)

Github: https://github.com/ratthachat/deep-rna

This post was modified 2 years ago by The Neural Engineer

   
ตอบกลับอ้างอิง
The Neural Engineer
(@neural-engineer)
Honorable Member Admin
เข้าร่วมเมื่อ: 6 years ago
ข้อความ: 399
Topic starter  

รู้จักปัญหา Manifold Learning และ Graph Embedding

ThaiKeras and Kaggle, July 24 2022

ในอดีตกาล ในยุคก่อน Deep Learning นั้น (จริงๆ แค่เกือบ 20 ปีเอง 🙂 ในวงการ machine learning ได้ให้ความสนใจกับสองปัญหาที่เรียกว่า "Manifold Learning" และ "Graph Embedding" เป็นอย่างมาก

ปัญหาแรก "Manifold Learning" เกิดจากแรงบันดาลใจว่า ข้อมูลหลายประเภทแม้จะถูก represent ด้วยเวกเตอร์หลายมิติ ทว่าแท้จริงแล้วชุดข้อมูลเหล่านั้นจริงๆ อาจเรียงต่อกันบนระนาบที่มิติน้อยมากๆ

อุปมาอุปไมยเหมือนกับ เชือก 1 เส้นความยาว L ถ้ายืดตรงๆ ทุกๆ จุดบนเชือกจากจุดปลายหนึ่งไปยังอีกจุดปลายหนึ่ง นั้นสามารถแทนได้จำนวนจริงเพียง 1 ค่า

เช่นให้จุดเริ่มต้นอยู่ตำแหน่งที่ 0 และจุดปลายอยู่ที่ตำแหน่ง L จุดต่างๆ บนเชือกก็จะอยู่ตำแหน่งระหว่าง [0, L] ซึ่งก็คือทุกจุดในเชือกสามารถ represent ได้ด้วยเวกเตอร์ 1 มิตินั่นเอง

ทว่าในโลกความเป็นจริงถ้าเราขดเชือกให้พันกันไปมา (นึกภาพสายชาร์จแบตเตอรรี หรือหูฟังแบบมีสายที่ขดในกระเป๋า) เชือก 1 มิตินั้น ก็จะกลายเป็น บอลยุ่งๆ ในโลก 3 มิติของเรา (ดูภาพที่ 1 ประกอบ และขอบคุณหูฟังแบบ Bluetooth ในวันนี้ 🙂

ซึ่งเชือกขดกันยุ่งๆ นี่แหละคือตัวอย่างของ "วัตถุที่เรียกว่า manifold" หรือ วัตถุในหลายมิติที่แท้จริงแล้วสามารถ "คลี่ออก" เป็นวัตถุน้อยมิติได้

รูปที่ 1 หูฟังพันกันยุ่งๆ แสดงให้เห็นถึงวัตถุง่ายๆ ใน 1 มิติ (เชือกที่ยืดตรงๆ) สามารถกลายเป็นวัตถุที่ซับซ้อนใน 3 มิติได้

หัวใจของปัญหา manifold learning ก็คือ การสร้าง machine learning model ที่รับ input วัตถุยุ่งๆ ในหลายมิติ และสามารถสร้าง output ที่เป็นการ "คลี่" วัตถุที่ยุ่งๆ ออกให้กลายเป็นวัตถุเรียบง่ายในมิติน้อยๆ

ตัวอย่าง Manifold Learning Model จาก 3D -> 1D : input : เชือกยุ่งๆ ใน 3 มิติตามรูปที่1 --> Model --> เชือกตรงใน 1มิติ

รูปที 2 swiss-roll

ตัวอย่าง Manifold Learning Model จาก 3D -> 2D : input : SwissRoll ใน 3 มิติตามรูปที่2 --> Model --> แผ่นระนาบใน 2มิติ ในสมัย 2000s นี่คือตัวอย่างที่หลายโมเดลต้องมาแข่งกันว่าใครจะคลี่ swissroll ได้ดีกว่ากัน สังเกตโมเดลในรูป 2(บน) คลี่ได้ดีมาก ในขณะที่รูป 2(ล่าง)คลี่ผิด เพราะสีในแต่ละส่วนของ swissroll ซ้อนทับกัน

อีกตัวอย่าง Application ที่สำคัญในยุคนั้น ลองจินตานาการถึง รูปภาพขาวดำขนาด 32x32 pixels เมื่อแต่ละ pixel เป็นจำนวนจริง 1 ค่า ทำให้รูปภาพทั้งหมดแทนด้วยเวกเตอร์ขนาดเท่ากับ 32x32=1,024 มิติ

สมมติให้ dataset รูปภาพของเราทั้งหมดเป็นหน้ารูปปั้นที่ "หมุนหน้าไปมา" (ดูรูปที่ 3) เนื่องจากรูปทั้งหมดเป็นรูปปั้นทำให้"องค์ประกอบของภาพอื่นๆ นั้นไม่เปลี่ยน" นอกจากการหมุนหน้า

เนื่องจาก "การหมุนหน้า" ทั้งหมดแท้จริงแล้วทำในโลก 3มิติ ดังนั้นแท้จริงแล้ว dataset ของรูปภาพแทนที่จะอยู่ในมิติสูงๆ เช่น 1,024 มิติ แต่ด้วยธรรมชาติของมัน dataset นี้ควรจะเป็น "manifold ขนาดไม่เกิน 3มิติ" ที่ขดกันอยู่ไปมาใน 1024 มิติ

 

รูปที่ 3 นั่นคือเราน่าจะคลี่ dataset นี้ให้เรียงตัวเป็นระเบียบใน 3 มิติได้ (ดั่งแสดงในรูปที่ 3 นั่นเอง)!

หัวใจของงาน manifold learning อาจพูดได้ว่าเป็นงาน "ลดมิติ" หรือ dimensionality reduction ในลักษณะแบบ "non-linear" (คลี่วัตถุที่ขดกันยุ่งๆ ในหลายมิติ)

จากตัวอย่างด้านบน เมื่อเราลดมิติของภาพรูปปั้นหมุนหน้ามาใน 3 มิติแล้ว ถ้าการคลี่ manifold ทำได้สมบูรณ์แบบ สมมติเราเทียบจุด 2 จุด (x, y, z) และ (x+a, y, z) สองจุดนี้ควรจะเป็นรูปภาพที่ต่างกันเพียง มีการหมุนหน้าไปในทิศแกน x ด้วยมุมขนาด a องศา

สังเกตว่าโดยทั่วไป manifold ไม่สามารถแก้ได้ด้วย "linear" projection (การฉายภาพ) เช่นด้วยเทคนิคเช่น PCA (Principal Component Analysis) ในตัวอย่างด้านบน PCA คือการฉายแสงไปยังเชือกยุ่งๆ นั้น และพยามเลือกทิศการการฉายแสงที่ทำให้ได้ "เงา" ที่ดีที่สุด ทว่าไม่ว่าเราจะฉายแสงทิศไหน ก็ไม่มีทิศที่ทำให้เราเห็นเงาของเชือกที่ขดยุ่งๆ มาเป็นระเบียบได้

ด้วย concept ที่น่าตื่นเต้นนี่เอง manifold learning จึงเป็นงานวิจัยที่ hot มากๆ ในช่วงปี 2000s ก่อนยุค Deep Learning และมีโมเดลดังๆ มากมายเช่น Isomap, Local Linear Embedding, Kernel PCA และ Laplacian Eigenmaps ที่เราจะกล่าวถึงในบทความหน้า

ใน sklearn นั้นมี implementation ของ classic manifold learning ทั้งหมดที่กล่าวด้านบน โดยเพื่อนๆ สามารถดูรายละเอียดคร่าวๆ ได้ที่นี่ครับ https://scikit-learn.org/stable/auto_examples/manifold/plot_compare_methods.html

แท้จริงแล้วปัญหา Manifold Learning ก็ยังสืบเนื่องมาจนถึงยุค Deep Learning นี้ เพียงแต่ว่าเรามักจะใช้คำว่า "Neural Embedding" แทน และเรารับมือกับข้อมูลที่ซับซ้อนกว่าตัวอย่างด้านบนมากๆ

ซึ่งถ้าพยายามแปล "Neural Embedding" เป็นไทย ก็คือการ "embed (ฝัง) ข้อมูลในหลายมิติ ให้อยู่ในมิติน้อยๆ ด้วย neural network" นั่นเอง

ซึ่ง Deep neural network คือเทคนิค non-linear dimensionality reduction ที่ครอบจักรวาลและดีที่สุดในปัจจุบัน ซึ่งจัดการข้อมูลที่ซับซ้อนกว่าภาพรูปปั้นด้านบนมากๆ เช่น ข้อมูล video ความละเอียดสูง ที่ neural network เรียนรู้นั้นอาจจะอยู่ในหลายล้านมิติ (ไม่ใช่แค่ 1,024 มิติ)

ซึ่ง Deep Learning ก็จะพยายามเรียน manifold ในหลายล้านมิตินั้นให้เหลือเพียงน้อยมิติ (เช่น เวกเตอร์ในเลเยอร์รองสุดท้ายก่อนจะทำ softmax / regression) ซึ่งในการเขียนโปรแกรมเรามักกำหนดให้เป็น manifold ใน 128/256/512 หรือ 1024 มิติ เป็นต้น (สังเกตว่า 1,024 มิติถือว่าน้อย ในยุค Deep Learning นี้ 🙂

ซึ่งเป็นอีกสาเหตุที่ทำให้ Deep Learning ผงาดเป็น 1 ในวงการ machine learning และ AI ทุกวันนี้ (ดูเพิ่มเติมได้ที่นี่ครับ https://thaikeras.com/2020/rise-of-dl/ )

.

ปัญหา Graph Embedding --------

กราฟคือวัตถุที่สำคัญมากใน computer science เพราะสามารถนำมาประยุกต์ใช้กับข้อมูลที่ซับซ้อนหลากหลายรูปแบบ เช่น กราฟของ Social Network, กราฟของสถานที่ต่างๆ ที่เชื่อมกันในแผนที่ หรือ กราฟของอะตอมในโมเลกุล เป็นต้น (รูปที่ 4)

รูปที่4 ใน computer science กราฟอธิบายได้ด้วย node และ edges ทว่าเมื่อเราต้องการใช้ Machine Learning ในการทำความเข้าใจกราฟ เราต้องพยายามเปลี่ยนกราฟให้เป็นเวกเตอร์เสียก่อน

ความหมายของการ "เปลี่ยนกราฟเป็นเวกเตอร์ " คือ การเปลี่ยน โหนดแต่ละโหนดให้เป็นเวกเตอร์ใน D มิติ (1 โหนดต่อ 1 เวกเตอร์) โดยถ้าสองโหนดใดๆ นั้นเชื่อมต่อกันบนกราฟแล้ว ระยะห่าง (แบบยุคลิด) บน D มิติก็ควรจะอยู่ใกล้กันด้วย

เมื่อเราเปลี่ยนกราฟเป็นเวกเตอร์ได้แล้ว เราก็สามารถทำโมเดล classification, regression หรือ prediction อื่นๆ ได้เช่นเดียวกับข้อมูลประเภทอื่นๆ (รูปภาพ เสียง ภาษา ฯลฯ)

ปัญหาการเปลี่ยนกราฟให้เป็นเวกเตอร์ในยุค Deep Learning นั้นดูได้ที่บทความนี้ครับ https://bit.ly/thaikeras-gnns

ทว่าในยุคก่อน Deep Learning เราจะมีวิธีการเปลี่ยนกราฟให้เป็นเวกเตอร์ได้อย่างไร?

ในยุคนั้นปรากฏว่าวิธีการเปลี่ยนกราฟเป็นเวกเตอร์ กับโมเดล Manifold Learning กลายเป็นเรื่องเดียวกัน!

โดยในการทำ Manifold Learning นั้น แท้จริงแล้วเราจะเปลี่ยนข้อมูลในมิติสูงๆ ให้อยู่ในรูปกราฟก่อน โดยใช้เทคนิคง่ายๆ เช่น k-Nearest-Neighbours graph จากนั้นก็จะทำ Graph Embedding เพื่อเปลี่ยนเป็นเวกเตอร์นั่นเอง! (ขยายความในบทความหน้า)

นั่นคือ ในยุค 2000s ปรากฏว่าปัญหา Manifold Learning และ Graph Embedding มักจะถูกเชื่อมเป็นปัญหาเดียวกัน นั่นคือ algorithm เดียวจะสามารถจัดการได้ทั้งสองปัญหา

โดยตัวอย่างหนึ่งที่เราจะเล่าในบทความหน้าคือ เทคนิคที่ชื่อ Laplacian Eigenmaps ที่เป็นได้ทั้ง Manifold Learning และ Graph Embedding นอกจากนี้ยังฟื้นคืนชีพมารับหน้าที่สำคัญอีกครั้งในยุค Deep Learning อีกด้วยครับผม

แล้วพบกันตอนถัดไปคร้าบ


   
ตอบกลับอ้างอิง
The Neural Engineer
(@neural-engineer)
Honorable Member Admin
เข้าร่วมเมื่อ: 6 years ago
ข้อความ: 399
Topic starter  

Laplacian Eigmaps : Manifold Learning และ positional vector ของ Graph Neural Networks --------------

ในบทความเดือนก่อนเราได้เกริ่นถึงปัญหาของ Manifold Learning และ Graph Embedding ว่าโดยเนื้อแท้คือปัญหา Non-linear dimensionality reduction วันนี้เราจะอธิบายเทคนิค Laplacian Eigenmaps และเล่าว่าเทคนิคนี้กลับมามีบทบาทอย่างไรในยุค Deep Learning ครับ

(อ่านย้อนหลังเพื่อทบทวนได้ที่) https://www.facebook.com/thaikeras/posts/pfbid02bPBdvv65ifwgL9W4MfDWS8iFy3mmBxS4RqwkWK5TxeAuT8HdPFQ7BGNFFG32mT5wl

โดย Laplacian Eigmaps เป็นหนึ่งในเทคนิค Manifold Learning ที่ simple และมีประสิทธิภาพในยุคก่อน Deep Learning ซึ่งเปเปอร์ฉบับกระชับสามารถศึกษาได้ที่นี่ครับ (อาจจะอ่านง่ายกว่าบทความฉบับนี้ของเราด้วยซ้ำครับ ฮา 😀 ทั้งนี้เนื่องจากบน facebook เราไม่สามารถเขียนสมการคณิตศาสตร์สวยๆ ได้ครับ) https://proceedings.neurips.cc/paper/2001/file/f106b7f99d2cb30c3db1c3cc0fde9ccb-Paper.pdf

โดยขั้นตอนในการทำ Manifold Learning อธิบายในหน้าที่ 2 มี 3 ขั้นตอนดังนี้ โดยใน 2 ขั้นแรกเป็นการสร้างกราฟจาก N training data บน Euclidean space \(R^M\), ถ้าปัญหาของเราเริ่มจาก Graph data อยู่แล้ว เราสามารถข้ามไปขั้นตอนที่ 3 คือ Graph Emdedding ได้เลย

1. (สร้างกราฟ - โดยกำหนดค่า k เป็น hyperparameter) จาก Graph G = (V,E) กำหนดให้ทุก data point คือโหนดใน V จากนั้นหา k nearest neighbors ของแต่ละ data point บน Eucliean distance, ในการสร้าง E, กำหนดให้ทุกโหนดมี edge เชื่อมจำนวน k edges ดังกล่าว

2. (สร้าง weight ของแต่ละ edge) สามารถใช้ 0/1 weights บน E หรือจะใช้ weighted edges เช่น heat kernel ก็ได้ เช่น \(w_{ij}\) สำหรับ edge ที่เชื่อมโหนด i และ j คือ \(e^{[x_i - x_j ]^2/t}\) ซึ่ง heat kernel เป็น similarity function อย่างง่ายบน Euclidean space และมี t (temperature) เป็น hyperparameter

ทำให้เราได้ weighted matrix W จาก E โดย W มีขนาด NxN ตามจำนวน training data

3. (Embedding โดย Eigenvectors) จาก W, กำหนดให้ D เป็น diagonal matrix โดย \(D_{ii} = \sum_j w_{ij}\) และสร้าง Laplacian matrix \(L = D-W\)

เราจะ solve ปัญหา generalized eigenvalue problem ดังนี้

\(Ly = \lambda*Dy\)

ซึ่งเราจะได้ y เป็น eigenvector ของ \(L,D\) และ \(\lambda\) เป็น eigenvalue ของ y โดย y เป็นเวกเตอร์ขนาด N

เมื่อเรากำหนด m เป็น hyperparameter (มิติของ reduced dimensions) ให้เรา solve ปัญหา eigenvectors ดังกล่าว m+1 ครั้งโดย "เรียง eigenvalue จากน้อยไปมาก" และทิ้ง eigenvector ที่มีค่าน้อยที่สุดทิ้งไป

นั่นทำให้สุดท้ายเราจะได้ matrix Y ขนาด Nxm ซึ่งแต่ละแถวใน Y ก็จะเป็น embedded vector ใหม่ของแต่ละ data point บน \(R^m\) นั่นเองครับ

.

กล่าวโดยสรุปในปัญหา Manifold Learning เราเริ่มจาก input data บน high dimensional Euclidean space \(R^M\) เราจะได้ output data บน low dimensional space \(R^m\) และมี Graph embedding เป็นขั้นตอนตรงกลาง (intermediate step)

โดยขั้นตอนที่ 3 เป็นขั้นตอนสำคัญโดยใน Section 3 ในเปเปอร์ข้างต้นมีการพิสูจน์ให้ดูอย่างง่ายๆ ว่า eigenvector ทีคำนวณได้ บน reduced dimension \(R^m\) จะ minimize \( \sum_{ij} w_{ij}*(y_i - y_j)^2\)

ซึ่งเป็นสิ่งที่เราต้องการเพราะเราสนใจให้ embedded space ใหม่ \(R^m\) นั้นรักษาระยะห่างระหว่างจุดเฉพาะระยะทางระหว่างโหนดที่มีเส้นเชื่อมกันในกราฟเท่านั้น

ดังนั้นเมื่อเรา solve ปัญหา eigenvector ดังกล่าวเราก็จะ solve ปัญหา Manifold Learning ในแนวทางของ Laplacian Eigenmaps ครับ

.

แล้ว Laplacian Eigenmaps สำคัญอย่างไรในยุค Deep Learning?

เท้าความกลับมาที่ Transformers ที่เป็นโมเดลที่ประสบความสำเร็จสูงสุดในการเรียนรู้และทำนายข้อมูลประเภท sequential เช่น ข้อความในภาษาต่างๆ

Transformers ที่รับข้อมูลเป็นประโยคภาษาอังกฤษเช่น

My cat does not like the other cat

สามารถแยกคำว่า "cat" ที่ปรากฏสองครั้งในประโยคข้างต้นได้ โดยใช้เทคนิคที่เรียกว่า Positional encoding นั่นคือ นอกจาก encode คำศัพท์ของคำว่า cat แล้ว ยัง encode ตำแหน่งที่สองคำดังกล่าวปรากฏในประโยค เช่น คำว่า cat ตัวแรกปรากฏในตำแหน่งที่ 2 และคำว่า cat ครั้งสองอยู่ในตำแหน่งที่ 8

กล่าวคือ transformers จะสร้าง vector ของ "ตำแหน่งที่ 2" และ "ตำแหน่งที่ 8" (รวมทั้งตำแหน่งอื่นๆ ของทุกคำ) ทำให้แยกความแตกต่างระหว่างคำศัพท์เดียวกันที่ปรากฏหลายครั้งในประโยคได้

ใน Graph Neural Networks (GNNs) เองก็มีปัญหาเช่นเดียวกัน เช่น ในโมเลกุลกราฟ เราอาจจะเจอ Oxygen atom ในหลายตำแหน่งบนโมเลกุล ซึ่งแม้ classic graph neural networks เองจะทรงพลัง แต่ก็ไม่สามารถจำแนกตำแหน่งของแต่ละ Oxygen atom ได้ (ย้อนอ่านบทความ GNNs ของเราได้ที่นี่ครับ

ตอนที่ 1 https://www.facebook.com/thaikeras/posts/pfbid02Sj33o3pM5Gp5XErRLSpwuTLp5ic4yWLb6S4SNzEfiqFJv1nQMa557V915tmbPe2El

ตอนที่ 2 https://www.facebook.com/thaikeras/posts/pfbid02PM1BfG4tecSruKVaPoX2e6NPZENHag9yhrVCaT8Kf7V9XgJXRBczdtZVNTaB8fsSl )

ซึ่งนักวิจัยก็มาค้นพบว่า Laplacian Eigenmaps บน Graph Data นั้นเป็นตัวแทนของ sinusidal positional positional embedding บน sequential data นั่นเองครับ และการ embed Laplacian Positional encoding ลงไปเพิ่มเติมใน graph data นั้นทำให้ประสิทธิภาพของ GNNs นั้นดีขึ้นมาก

(Ref: https://arxiv.org/pdf/2003.00982v4.pdf ดูหน้า 39 สำหรับการเทียบกับ classic transformers และผลการทดลองที่ดีขึ้นมากเมื่อเพิ่ม Laplacian position encoding ลงใน graph data)

แท้จริงแล้วเราพบว่า GNNs ที่ไม่ได้ใส่ Positional encoding ลงไปมีข้อจำกัดทางทฤษฎีที่สำคัญ และ positional encoding (ซึ่งทำได้หลายแบบดังรูปที่ 1) เป็นเพียงหนึ่งในหลายวิธีที่ทำลายข้อจำกัดนั้น สามารถอ่านเพิ่มเติมได้ในบทความนี้ของ Michael Bronstein เจ้าพ่อ GNNs จาก DeepMind ครับ https://thegradient.pub/graph-neural-networks-beyond-message-passing-and-weisfeiler-lehman/

This post was modified 1 year ago 2 times by The Neural Engineer

   
ตอบกลับอ้างอิง
Share: