Skip to content
กลับไปยังผลการค้นหา

โครงข่ายประสาทเทียมบนกราฟ — GCN / GAT / GraphSAGE (Graph Neural Network)

ปี
2017–2018 (major variants)
ประเภท
Deep learning on graph-structured data

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Graph Neural Network (GNN) คือสถาปัตยกรรม deep learning ที่ทำงานโดยตรงบนข้อมูลที่มีโครงสร้างแบบกราฟ โดยการรวมคุณลักษณะของโหนด (node features) เข้ากับข้อมูลเชิงโครงสร้างผ่านการส่งข้อความแบบวนซ้ำระหว่างเพื่อนบ้าน (iterative neighborhood message passing) รูปแบบหลักสามรูปแบบ — Graph Convolutional Network (GCN) ที่นำเสนอโดย Kipf และ Welling ในปี 2017, Graph Attention Network (GAT) ที่นำเสนอโดย Veličković และคณะ ในปี 2018, และ GraphSAGE — แตกต่างกันในวิธีการรวบรวมข้อมูลจากเพื่อนบ้าน: GCN ใช้คอนโวลูชันแบบสเปกตรัม (spectral convolution) บน adjacency matrix แบบเต็ม, GAT กำหนดน้ำหนักให้กับเพื่อนบ้านด้วยคะแนน attention ที่เรียนรู้ได้, และ GraphSAGE สุ่มตัวอย่างและรวบรวม neighborhood เฉพาะที่แบบอุปนัย (inductively) ทำให้สามารถสรุปไปยังโหนดที่ไม่เคยเห็นมาก่อนได้

แนวคิดเบื้องหลังวิธีการ

ลองนึกภาพโหนดแต่ละโหนดในกราฟเป็นบุคคลในเครือข่ายสังคม บุคคลนั้นมีโปรไฟล์ของตนเอง (คุณลักษณะ) แต่การที่พวกเขารู้จักใครก็บอกอะไรเกี่ยวกับพวกเขาได้มากเช่นกัน GNN ช่วยให้แต่ละโหนดรวบรวมข้อความจากเพื่อนบ้านซ้ำๆ ผสมข้อความเหล่านั้นกับข้อมูลของตนเอง และอัปเดตการแทนค่า (representation) ของตนเอง — ทีละชั้น (layer) หลังจากผ่านการส่งต่อข้อมูลระหว่างเพื่อนบ้านสองสามรอบ การแทนค่าของแต่ละโหนดจะสะท้อนไม่เพียงแค่ตัวมันเอง แต่ยังรวมถึง subgraph เฉพาะที่อยู่รอบๆ ด้วย GCN ทำสิ่งนี้ด้วยค่าเฉลี่ยแบบสมมาตร (symmetric average) ของเพื่อนบ้านที่คงที่; GAT ตัดสินใจว่าจะเชื่อเพื่อนบ้านคนไหนมากกว่าโดยการเรียนรู้น้ำหนัก attention; GraphSAGE สุ่มตัวอย่างชุดย่อย (subset) ของเพื่อนบ้านที่มีขนาดคงที่และเรียนรู้ฟังก์ชันการรวบรวม (aggregation function) ที่สามารถนำไปใช้กับโหนดที่ไม่เคยเห็นมาก่อนได้

ประวัติศาสตร์

รากฐานของการประยุกต์ใช้โครงข่ายประสาทเทียมกับกราฟถูกวางไว้โดย Scarselli และคณะ (2009) แต่ยุค GNN สมัยใหม่เริ่มต้นด้วย Graph Convolutional Network (2017) ของ Kipf และ Welling ซึ่งทำให้ spectral graph convolution ง่ายขึ้นเป็นการประมาณค่าอันดับแรกที่มีประสิทธิภาพโดยใช้การคูณ adjacency matrix แบบสมมาตรที่ทำให้เป็นมาตรฐาน หนึ่งปีต่อมา Veličković และคณะ (2018) ได้นำเสนอ Graph Attention Networks โดยแทนที่การหาค่าเฉลี่ยคงที่ของ GCN ด้วยค่าสัมประสิทธิ์ attention ที่เรียนรู้ได้ในแต่ละขอบ — ทำให้โมเดลสามารถให้น้ำหนักเพื่อนบ้านได้อย่างเลือกสรร ในขณะเดียวกัน Hamilton และคณะ (2017) ได้เสนอ GraphSAGE ซึ่งเป็นกรอบการทำงานแบบ inductive ที่สุ่มตัวอย่าง neighborhood ที่มีขนาดคงที่และเรียนรู้ฟังก์ชันการรวบรวมที่สามารถถ่ายทอดไปยังโหนดที่ไม่เคยเห็นได้ ทำให้ GNN สามารถใช้งานได้จริงกับกราฟขนาดใหญ่และเปลี่ยนแปลงได้ บทความทั้งสามนี้ได้สร้างกระบวนทัศน์ message-passing ที่เป็นพื้นฐานของงานวิจัย GNN ส่วนใหญ่ในปัจจุบัน

ควรใช้เมื่อใด

ใช้ GNN เมื่อข้อมูลของคุณมีโครงสร้างแบบกราฟโดยธรรมชาติ — เครือข่ายสังคม, เครือข่ายการอ้างอิง, กราฟโมเลกุล, กราฟความรู้, หรือสถานการณ์ใดๆ ที่ความสัมพันธ์ระหว่างเอนทิตีมีความสำคัญในการทำนาย คุณต้องมีเมทริกซ์คุณลักษณะของโหนดและรายการขอบ จำเป็นต้องมีโหนดอย่างน้อยประมาณ 50 โหนดสำหรับการฝึกที่สื่อความหมาย GNN สามารถนำไปใช้กับการจำแนกประเภทโหนด (ทำนายป้ายกำกับสำหรับแต่ละโหนด), การทำนายขอบ (อนุมานขอบที่ขาดหายไป), และการจำแนกประเภทกราฟ (กำหนดป้ายกำกับให้กับกราฟทั้งหมด) ข้อสมมติฐาน homophily — โหนดที่เชื่อมต่อกันมักจะมีป้ายกำกับเดียวกัน — ถูกใช้ประโยชน์โดยปริยายโดย GCN และ GAT มาตรฐาน; หากกราฟของคุณเป็นแบบ heterophilic ควรพิจารณาสถาปัตยกรรมที่ออกแบบมาสำหรับสถานการณ์นั้น สำหรับกราฟขนาดใหญ่ การฝึกแบบ full-batch จะใช้หน่วยความจำมากเกินไป และจำเป็นต้องใช้การสุ่มตัวอย่าง neighborhood แบบ mini-batch (สไตล์ GraphSAGE) หากกราฟของคุณมีโหนดน้อยกว่า 20 โหนด การวิเคราะห์ centrality แบบดั้งเดิมจะเป็นตัวเลือกที่เหมาะสมกว่า

ข้อจำกัดและข้อควรพิจารณา

  • Over-smoothing: การซ้อน GNN layers หลายชั้นทำให้การแทนค่าโหนดทั้งหมดลู่เข้าสู่ค่าเดียวกัน ทำให้ความลึกที่มีประสิทธิภาพจำกัดอยู่ที่ประมาณ 2–4 ชั้นในการใช้งานจริง
  • Scalability: GCN และ GAT แบบ full-batch ต้องการการเก็บ adjacency matrix และ feature matrix ทั้งหมดไว้ในหน่วยความจำ ซึ่งเป็นไปไม่ได้สำหรับกราฟขนาดใหญ่มากหากไม่มีการสุ่มตัวอย่างหรือการแบ่งพาร์ติชัน
  • ข้อสมมติฐาน homophily ที่ฝังอยู่ในฟังก์ชันการรวบรวมมาตรฐานทำให้ประสิทธิภาพลดลงบนกราฟ heterophilic ที่เพื่อนบ้านมักจะมีป้ายกำกับต่างกัน
  • ต้องมีจำนวนตัวอย่างขั้นต่ำประมาณ 50 โหนด; โหนดที่น้อยกว่านั้นจะทำให้โมเดลไม่มีสัญญาณเพียงพอที่จะเรียนรู้การแทนค่าที่มีความหมาย

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ใช้ประโยชน์ทั้งคุณลักษณะของโหนดและโทโพโลยีของกราฟร่วมกัน ทำให้มีประสิทธิภาพเหนือกว่าวิธีที่ใช้เพียงอย่างใดอย่างหนึ่ง
  • กลไก attention ของ GAT ให้คะแนนความสำคัญต่อขอบแต่ละอัน เพิ่มความสามารถในการตีความ (interpretability) ให้กับการรวบรวม
  • GraphSAGE เป็นแบบ inductive และสามารถสรุปไปยังโหนดและกราฟที่ไม่เคยเห็นระหว่างการฝึกได้ ทำให้สามารถใช้งานกับเครือข่ายที่กำลังเติบโตได้
  • กรอบการทำงาน message-passing แบบรวมศูนย์ครอบคลุมการจำแนกประเภทโหนด, การทำนายขอบ, และการจำแนกประเภทกราฟ ด้วยสถาปัตยกรรมพื้นฐานเดียวกัน

การประยุกต์ใช้

  • การจำแนกประเภทโหนดในเครือข่ายการอ้างอิง — การทำนายหัวข้อของบทความโดยพิจารณาจากเนื้อหาและลิงก์การอ้างอิง
  • การค้นคว้ายา — การทำนายคุณสมบัติของโมเลกุลโดยให้อะตอมเป็นโหนดและพันธะเคมีเป็นขอบ
  • ระบบแนะนำ — การสร้างแบบจำลองผู้ใช้และรายการเป็นกราฟสองส่วน (bipartite graph) และการทำนายปฏิสัมพันธ์ระหว่างผู้ใช้กับรายการผ่านการทำนายขอบ
  • การตรวจจับการฉ้อโกงในเครือข่ายธุรกรรมทางการเงิน — การระบุโหนดที่ผิดปกติโดยพิจารณาจากคุณลักษณะและโครงสร้าง neighborhood ของมัน
  • การเติมส่วนที่ขาดของกราฟความรู้ (knowledge graph completion) — การอนุมานความสัมพันธ์ที่ขาดหายไประหว่างเอนทิตีในฐานข้อมูลความรู้ขนาดใหญ่

วิธีการทำงาน

วิธีการทำงาน

1

กราฟถูกกำหนดโดยเมทริกซ์คุณลักษณะของโหนด X (หนึ่งแถวต่อโหนด หนึ่งคอลัมน์ต่อคุณลักษณะ) และรายการขอบ (edge list) (หรือ adjacency matrix) A ขอบแบบไม่ระบุทิศทาง (undirected edges) เป็นมาตรฐานสำหรับ GCN และ GAT; GraphSAGE ยังรองรับกราฟแบบมีทิศทาง (directed graphs) โดยทั่วไปจะมีการเพิ่ม self-loops เข้าไปใน A เพื่อให้แต่ละโหนดถูกรวมอยู่ในการรวบรวมของตนเอง

2

คุณลักษณะดิบของโหนดจะถูกทำให้เป็นมาตรฐาน (normalized) และหากจำเป็น จะถูกฝังลงในปริภูมิเวกเตอร์ต่อเนื่อง (continuous vector space) คุณลักษณะของขอบ (edge attributes) หากมี สามารถรวมเป็นสัญญาณเพิ่มเติมได้ ผลลัพธ์คือเมทริกซ์คุณลักษณะแบบหนาแน่น (dense feature matrix) ที่แต่ละ GNN layer จะแปลง

3

GNN layer แต่ละชั้นจะคำนวณการแทนค่าโหนดใหม่โดยการรวบรวมคุณลักษณะของเพื่อนบ้านของโหนด และรวมเข้ากับคุณลักษณะของโหนดเองผ่านเมทริกซ์น้ำหนักที่เรียนรู้ได้ (learnable weight matrix) และฟังก์ชันกระตุ้นแบบไม่เชิงเส้น (non-linear activation) GCN ใช้การคูณด้วย adjacency matrix ที่ทำให้เป็นมาตรฐาน (spectral convolution); GAT คำนวณค่าสัมประสิทธิ์ attention แบบ softmax สำหรับแต่ละขอบ เพื่อให้เพื่อนบ้านที่มีอิทธิพลมีส่วนร่วมมากขึ้น; GraphSAGE สุ่มตัวอย่าง neighborhood ที่มีขนาดคงที่และใช้ aggregator ที่สามารถหาอนุพันธ์ได้ (differentiable aggregator) (mean, LSTM, หรือ pooling) การซ้อน L ชั้นช่วยให้ข้อมูลไหลได้ L hop แต่การซ้อนหลายชั้นเกินไปจะทำให้เกิด over-smoothing ซึ่งการแทนค่าโหนดทั้งหมดจะลู่เข้าสู่ค่าเดียวกัน

4

การแทนค่าโหนดสุดท้ายจะถูกป้อนเข้าสู่ส่วนหัวเฉพาะสำหรับงาน (task-specific head) สำหรับการจำแนกประเภทโหนด (node classification) ชั้น softmax จะกำหนดความน่าจะเป็นของคลาสให้กับแต่ละโหนด สำหรับการทำนายขอบ (link prediction) ผลคูณภายใน (inner product) หรือ MLP จะให้คะแนนความเป็นไปได้ของขอบระหว่างการแทนค่าโหนดสองโหนด สำหรับการจำแนกประเภทกราฟ (graph classification) การรวบรวมแบบ global pooling (sum, mean, หรือ hierarchical) จะรวมการแทนค่าโหนดทั้งหมดเข้าเป็นเวกเตอร์ระดับกราฟเดียว ก่อนที่จะส่งไปยังชั้นจำแนกประเภท

5

ประสิทธิภาพของโมเดลวัดผลบนชุดข้อมูลทดสอบที่แยกไว้ (held-out test set) โดยใช้เมตริกที่เหมาะสมกับงาน: accuracy หรือ F1 สำหรับการจำแนกประเภทโหนดและกราฟ, AUC-ROC สำหรับการทำนายขอบ เนื่องจากชุดข้อมูลกราฟมักมีขนาดจำกัด การประเมินแบบ transductive (mask สำหรับ train/val/test บนกราฟเดียวกัน) หรือการแบ่งแบบ inductive (disjoint subgraphs) ควรตรงกับสถานการณ์การใช้งานจริง

ข้อผิดพลาดที่พบบ่อย

  • การเพิ่ม GNN layers มากเกินไปทำให้เกิด over-smoothing: การแทนค่าโหนดทั้งหมดจะลู่เข้าและโมเดลจะสูญเสียความสามารถในการแยกแยะ ควรคงจำนวนชั้นไว้ที่ 2–4 และตรวจสอบความแปรปรวนของการแทนค่า
  • การฝึกบนกราฟทั้งหมดโดยไม่มี mini-batch จะใช้หน่วยความจำมากเกินไปสำหรับเครือข่ายขนาดใหญ่; ใช้การสุ่มตัวอย่าง neighborhood แบบ mini-batch (เช่น GraphSAGE) หรือการแบ่งพาร์ติชันกราฟสำหรับกราฟที่มีโหนดมากกว่าไม่กี่พันโหนด
  • การใช้ GCN ที่ฝึกแบบ transductive กับโหนดใหม่ที่ไม่เคยเห็นระหว่างการอนุมาน (inference) นั้นไม่ถูกต้อง; ใช้วิธีแบบ inductive เช่น GraphSAGE หากการใช้งานของคุณต้องการการสรุปไปยังโหนดใหม่
  • การละเลยข้อสมมติฐาน homophily บนกราฟ heterophilic จะให้ผลลัพธ์ที่ไม่ดี; ตรวจสอบค่าสัมประสิทธิ์ assortativity ของกราฟก่อนเลือก GNN variant มาตรฐาน
  • สำหรับกราฟที่มีโหนดน้อยกว่า 20 โหนด การฝึก GNN จะให้ผลการแทนค่าที่ไม่น่าเชื่อถือ; ควรเลือกการวิเคราะห์ centrality แบบดั้งเดิมในกรณีนั้น

คำถามที่พบบ่อย

ควรเริ่มต้นด้วย GNN variant ใด — GCN, GAT, หรือ GraphSAGE?

GCN เป็น baseline ที่ง่ายที่สุดและทำงานได้ดีบนกราฟ homophilic ขนาดเล็กถึงปานกลางที่โหนดทั้งหมดเป็นที่รู้จักในระหว่างการฝึก GAT จะเหมาะสมกว่าเมื่อความสำคัญของเพื่อนบ้านแตกต่างกันและคุณต้องการน้ำหนัก attention ที่ตีความได้ GraphSAGE เป็นตัวเลือกที่เหมาะสมเมื่อคุณต้องการสรุปไปยังโหนดที่ไม่เคยเห็นระหว่างการฝึก หรือเมื่อกราฟมีขนาดใหญ่เกินกว่าจะประมวลผลแบบ full-batch ได้

Over-smoothing คืออะไร และจะหลีกเลี่ยงได้อย่างไร?

Over-smoothing เกิดขึ้นเมื่อ GNN layers หลายชั้นทำให้การแทนค่าโหนดทั้งหมดลู่เข้าสู่ค่าเดียวกัน ทำให้ข้อมูลที่แยกแยะได้สูญเสียไป ในทางปฏิบัติ โดยทั่วไป 2–4 ชั้นจะเหมาะสมที่สุด เทคนิคต่างๆ เช่น residual connections, jumping knowledge networks, และ DropEdge สามารถช่วยได้หากจำเป็นต้องใช้สถาปัตยกรรมที่ลึกกว่า

GNN จำเป็นต้องมีข้อมูลที่มีป้ายกำกับสำหรับทุกโหนดหรือไม่?

ไม่ GCN และ GAT มักใช้ในการตั้งค่าแบบกึ่งกำกับดูแล (semi-supervised) ซึ่งมีเพียงส่วนเล็กๆ ของโหนดที่มีป้ายกำกับ; โครงสร้างกราฟจะกระจายข้อมูลจากโหนดที่มีป้ายกำกับไปยังโหนดที่ไม่มีป้ายกำกับ GraphSAGE ยังสามารถฝึกได้ทั้งแบบ fully supervised หรือ unsupervised ขึ้นอยู่กับงาน

กราฟต้องมีขนาดเท่าใด?

ต้องมีโหนดอย่างน้อยประมาณ 50 โหนดสำหรับการฝึก GNN ที่สื่อความหมาย ด้วยโหนดที่น้อยกว่า 20 โหนด โมเดลจะไม่สามารถเรียนรู้การแทนค่าที่น่าเชื่อถือได้ และการวิเคราะห์แบบดั้งเดิมที่อิงตาม centrality จะเหมาะสมกว่า สำหรับกราฟที่มีโหนดหลายล้านโหนด จำเป็นต้องใช้การสุ่มตัวอย่าง neighborhood แบบ mini-batch (เช่นใน GraphSAGE) หรือวิธีการแบ่งพาร์ติชันกราฟ เพื่อให้การใช้หน่วยความจำสามารถจัดการได้

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR).

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  3. Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว