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

การฝังตัวของเครือข่าย — Node2Vec, DeepWalk, LINE

ปี
2014 (DeepWalk); 2016 (Node2Vec)
ประเภท
Representation learning / unsupervised network method

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

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

ใช้ทำอะไร?

การฝังตัวของเครือข่าย (Network embedding) เป็นกลุ่มของวิธีการเรียนรู้การนำเสนอที่แปลงแต่ละโหนดของกราฟให้อยู่ในรูปของเวกเตอร์ความหนาแน่นต่ำที่มีมิติไม่มากนัก โดยยังคงรักษาคุณสมบัติเชิงโครงสร้างของเครือข่ายไว้ วิธีการนี้ได้รับการกำหนดอย่างเป็นทางการสำหรับข้อมูลเครือข่ายสังคมโดย Perozzi, Al-Rfou, และ Skiena ด้วย DeepWalk (2014) ซึ่งปรับใช้โมเดล skip-gram ของ Word2Vec กับการเดินสุ่มบนกราฟ และได้รับการขยายโดย Grover และ Leskovec ด้วย Node2Vec (2016) ซึ่งนำเสนอการเดินสุ่มแบบมีอคติที่ปรับสมดุลระหว่างการสำรวจแบบ breadth-first และ depth-first การฝังตัวเหล่านี้เปลี่ยนข้อมูลเชิงสัมพันธ์ให้เป็นเวกเตอร์คุณลักษณะที่ตัวจำแนกประเภทและอัลกอริทึมการจัดกลุ่มของแมชชีนเลิร์นนิงมาตรฐานสามารถนำไปใช้ได้โดยตรง

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

กราฟประกอบด้วยโหนดและเส้นเชื่อม แต่ส่วนใหญ่แล้วอัลกอริทึมแมชชีนเลิร์นนิงจะคาดหวังตารางตัวเลข การฝังตัวของเครือข่ายช่วยแก้ปัญหาการแปลงนี้ได้ เช่นเดียวกับที่ Word2Vec เรียนรู้ความหมายของคำโดยพิจารณาว่าคำใดปรากฏใกล้กันในประโยค DeepWalk ก็เรียนรู้ความหมายของโหนดโดยพิจารณาว่าโหนดใดปรากฏใกล้กันในการเดินสุ่มทั่วทั้งกราฟ ผลลัพธ์ที่ได้คือพิกัดในปริภูมิเวกเตอร์ — โหนดที่มีโครงสร้างคล้ายกันหรือมีการเยี่ยมชมร่วมกันบ่อยครั้งจะอยู่ใกล้กัน เมื่อแต่ละโหนดมีเวกเตอร์แล้ว คุณสามารถป้อนเวกเตอร์เหล่านั้นเข้าสู่ตัวจำแนกประเภท จัดกลุ่มด้วย k-means หรือแสดงผลด้วย UMAP โดยไม่ต้องเขียนโค้ดที่เฉพาะเจาะจงสำหรับกราฟใดๆ

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

แนวคิดในการประยุกต์ใช้ Word2Vec กับข้อมูลที่มีโครงสร้างกราฟได้รับการแนะนำโดย Perozzi, Al-Rfou, และ Skiena ใน DeepWalk (KDD 2014) ซึ่งแสดงให้เห็นว่าการเดินสุ่มบนกราฟสังคมสามารถใช้แทนคุณลักษณะที่สร้างขึ้นด้วยมือสำหรับการจำแนกประเภทโหนดได้ Grover และ Leskovec ได้ขยายแนวคิดนี้ใน Node2Vec (KDD 2016) โดยการนำเสนอการเดินสุ่มแบบมีอคติลำดับที่สองที่กำหนดพารามิเตอร์ด้วย p และ q ซึ่งให้การควบคุมที่ชัดเจนในการแลกเปลี่ยนระหว่างการสำรวจเพื่อนบ้านแบบ homophily และ structural-equivalence ในช่วงเวลาเดียวกัน Tang et al. ได้เสนอ LINE (WWW 2015) ซึ่งเรียนรู้การฝังตัวโดยการปรับปรุงวัตถุประสงค์ความใกล้เคียงอันดับหนึ่งและอันดับสองโดยตรงแทนที่จะผ่านการเดินสุ่ม ทำให้เหมาะสำหรับกราฟขนาดใหญ่มาก วิธีการทั้งสามนี้ร่วมกันได้สร้างสาขาการเรียนรู้การนำเสนอเครือข่ายและเป็นแรงบันดาลใจให้กับสถาปัตยกรรมโครงข่ายประสาทเทียมกราฟในภายหลัง

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

การฝังตัวของเครือข่ายเหมาะสมเมื่อคุณมีกราฟที่มีอย่างน้อย 50 โหนด และคุณต้องการคุณลักษณะเวกเตอร์ต่อเนื่องสำหรับงานปลายทาง เช่น การจำแนกประเภทโหนด การทำนายการเชื่อมโยง หรือการจัดกลุ่มโหนด วิธีการนี้เหมาะสำหรับทั้งกราฟที่ไม่มีน้ำหนักและมีน้ำหนัก และจัดการกับโครงสร้างที่มีทิศทางหรือไม่ก็ได้ เลือก DeepWalk เมื่อพื้นฐานการเดินสุ่มแบบสม่ำเสมอที่เรียบง่ายเพียงพอ เลือก Node2Vec เมื่อคุณต้องการปรับสมดุลระหว่าง homophily และ structural equivalence ผ่านพารามิเตอร์ p และ q หากคุณต้องการฝังโหนดใหม่ที่ไม่เคยเห็นมาก่อนในเวลาอนุมานโดยไม่ต้องฝึกฝนใหม่ ให้เลือกวิธีการแบบ inductive เช่น GraphSAGE แทน การฝังตัวของเครือข่ายในรูปแบบมาตรฐานเป็นแบบ transductive วิธีการนี้ไม่ต้องการคุณลักษณะโหนดที่มีการแจกแจงแบบปกติ

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

  • Transductive: โมเดลไม่สามารถฝังโหนดที่ไม่ได้อยู่ในระหว่างการฝึกอบรมได้หากไม่มีการฝึกอบรมใหม่ทั้งหมด
  • ความไวของไฮเปอร์พารามิเตอร์: มิติการฝังตัว, ความยาวของการเดิน, จำนวนการเดิน, ขนาดหน้าต่าง, p และ q ล้วนส่งผลต่อคุณภาพการฝังตัวและต้องมีการปรับแต่ง
  • การเดินสุ่มไม่สามารถจับโครงสร้างกราฟลำดับสูงกว่าได้ (เช่น hyperedges หรือ multi-relational edges) หากไม่มีการขยาย
  • ประสิทธิภาพลดลงในกราฟขนาดเล็กมาก (น้อยกว่า 50 โหนด) ซึ่งคลังการเดินเบาบางเกินไปที่จะเรียนรู้สถิติที่เชื่อถือได้

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

จุดแข็ง

  • แปลงข้อมูลกราฟเชิงสัมพันธ์ให้เป็นเวกเตอร์ความยาวคงที่ที่เข้ากันได้กับไปป์ไลน์แมชชีนเลิร์นนิงมาตรฐานใดๆ
  • พารามิเตอร์ p และ q ของ Node2Vec ช่วยให้นักวิเคราะห์สามารถปรับสมดุลระหว่างการฝังตัวที่คำนึงถึงชุมชนและการฝังตัวที่คำนึงถึงบทบาท
  • สามารถรวมน้ำหนักเส้นเชื่อมเข้ากับความน่าจะเป็นของการเดินได้ โดยจับความแข็งแรงของความสัมพันธ์โดยไม่มีขั้นตอนการสร้างแบบจำลองเพิ่มเติม
  • ปรับขนาดได้กับกราฟขนาดใหญ่ผ่านการสุ่มตัวอย่างการเดินสุ่มที่มีประสิทธิภาพและขั้นตอนการฝึกอบรมแบบ skip-gram

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

  • การจำแนกประเภทโหนดในเครือข่ายการอ้างอิง, แพลตฟอร์มสังคม, หรือกราฟปฏิสัมพันธ์ทางชีวภาพ
  • การทำนายการเชื่อมโยง — การระบุเส้นเชื่อมที่ขาดหายไปหรือในอนาคตโดยการเปรียบเทียบความคล้ายคลึงของการฝังตัวของโหนด
  • การตรวจจับชุมชนโดยการจัดกลุ่มเวกเตอร์โหนดด้วย k-means หรือวิธีการแบบลำดับชั้น
  • การตรวจจับความผิดปกติ — โหนดที่การฝังตัวเป็นค่าผิดปกติในปริภูมิเวกเตอร์อาจแสดงถึงบทบาทเชิงโครงสร้างที่ผิดปกติ
  • ระบบแนะนำที่ผู้ใช้และรายการเป็นโหนดในกราฟปฏิสัมพันธ์แบบสองส่วนหรือหลายส่วน

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

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

1

กระบวนการเริ่มต้นด้วยกราฟ G ซึ่งโหนดคือเอนทิตีและเส้นเชื่อมแสดงถึงความสัมพันธ์ เส้นเชื่อมอาจมีทิศทางหรือไม่ก็ได้ และอาจมีน้ำหนักที่จะส่งผลต่อความน่าจะเป็นของการเดินทางในภายหลัง หากมีน้ำหนักเส้นเชื่อม จะถูกรวมอยู่ในความน่าจะเป็นของการเดิน หากไม่มี น้ำหนักของเส้นเชื่อมทั้งหมดจะเท่ากัน ในขั้นตอนนี้ นักวิเคราะห์ยังเลือกรูปแบบอัลกอริทึมด้วย — DeepWalk สำหรับการเดินสุ่มแบบสม่ำเสมอ, Node2Vec สำหรับการเดินแบบมีอคติที่ควบคุมโดยพารามิเตอร์ p (การย้อนกลับ) และ q (การออกนอก) หรือ LINE เมื่อต้องการเรียนรู้ความใกล้เคียงของเพื่อนบ้านอันดับหนึ่งและอันดับสองแยกกัน การเลือกระหว่างระบอบพารามิเตอร์ของ Node2Vec ถูกชี้นำโดยคุณสมบัติเครือข่ายที่คาดหวัง: homophily (โหนดที่คล้ายกันเชื่อมต่อกัน ดังนั้นจึงควรสำรวจแบบ breadth-first, q < 1) หรือ structural equivalence (โหนดที่มีบทบาทคล้ายกันอาจอยู่ห่างกัน ดังนั้นจึงควรสำรวจแบบ depth-first, p < 1)

2

เริ่มต้นจากแต่ละโหนด อัลกอริทึมจะจำลองชุดของการเดินสุ่มที่มีความยาวคงที่ (โดยทั่วไปคือ 30 ขั้น) และทำซ้ำหลายครั้ง (โดยทั่วไปคือ 200 ครั้งต่อโหนด) การเดินแต่ละครั้งจะสร้างลำดับของตัวระบุโหนดที่คล้ายกับประโยคของคำ ใน DeepWalk โหนดถัดไปจะถูกเลือกอย่างสม่ำเสมอจากเพื่อนบ้าน ใน Node2Vec โหนดถัดไปจะถูกเลือกตามความน่าจะเป็นของการเปลี่ยนสถานะที่มีอคติโดย p และ q: การกลับไปยังโหนดก่อนหน้าจะถูกลงโทษด้วย 1/p การคงอยู่ที่ระยะทางเดิมจะถูกเก็บไว้ที่ 1 และการเคลื่อนที่ออกไปไกลขึ้นจะถูกควบคุมโดย 1/q ชุดของการเดินทั้งหมดจะสร้างคลังลำดับโหนดที่เข้ารหัสโครงสร้างของกราฟ

3

คลังลำดับโหนดจะถูกป้อนเข้าสู่โมเดล skip-gram (สถาปัตยกรรมเดียวกับ Word2Vec) สำหรับแต่ละโหนดในการเดิน โมเดลจะทำนายโหนดบริบทโดยรอบภายในหน้าต่าง (โดยทั่วไปคือ 10 ขั้น) ผ่านการไล่ระดับความชันแบบสุ่ม โมเดลจะเรียนรู้การนำเสนอเวกเตอร์ความหนาแน่นสูงที่มีมิติคงที่ — โดยทั่วไปคือ 64 หรือ 128 — สำหรับแต่ละโหนด เพื่อให้โหนดที่ปรากฏร่วมกันในการเดินมีเวกเตอร์ที่คล้ายกัน มิติเป็นไฮเปอร์พารามิเตอร์: มิติที่ใหญ่ขึ้นจะจับโครงสร้างได้มากขึ้น แต่เพิ่มการคำนวณและความเสี่ยงที่จะเกิดการโอเวอร์ฟิตกับกราฟขนาดเล็ก

4

เมื่อได้รับการฝึกฝนแล้ว โมเดลจะให้เวกเตอร์การฝังตัวหนึ่งเวกเตอร์ต่อโหนด เวกเตอร์เหล่านี้ถูกใช้เป็นคุณลักษณะสำหรับการจำแนกประเภทโหนด (ป้อนเข้าสู่การถดถอยโลจิสติกส์หรือตัวจำแนกประเภทโครงข่ายประสาทเทียม) การทำนายการเชื่อมโยง (เปรียบเทียบเวกเตอร์ของคู่โหนดที่คาดการณ์) หรือการตรวจจับชุมชน (การจัดกลุ่มเวกเตอร์) การฝังตัวเหล่านี้เป็นแบบ transductive: พวกมันถูกกำหนดสำหรับโหนดที่เห็นระหว่างการฝึกฝน หากต้องฝังโหนดใหม่หลังการฝึกฝน ควรใช้วิธีการแบบ inductive เช่น GraphSAGE แทน เนื่องจากโมเดล Node2Vec หรือ DeepWalk มาตรฐานไม่สามารถสรุปผลไปยังโหนดที่ไม่เคยเห็นได้โดยไม่ต้องฝึกฝนใหม่

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

  • การใช้โมเดล Node2Vec กับโหนดใหม่ที่ไม่ได้อยู่ในกราฟการฝึกอบรม — โมเดลจะไม่มีเวกเตอร์สำหรับโหนดเหล่านั้น; ใช้วิธีการแบบ inductive (เช่น GraphSAGE) เมื่อการฝังตัวแบบ transductive ไม่เป็นที่ยอมรับ
  • การใช้ค่าเริ่มต้น p=1, q=1 (เทียบเท่ากับ DeepWalk) โดยไม่ได้ตรวจสอบว่าเครือข่ายเป็นไปตามรูปแบบ homophily หรือ structural-equivalence หรือไม่ — การปรับ p และ q ให้เข้ากับรูปแบบที่คาดหวังสามารถปรับปรุงประสิทธิภาพของงานปลายทางได้อย่างมาก
  • การถือว่ามิติการฝังตัวเป็นค่าคงที่: ในกราฟขนาดเล็ก มิติ 64 หรือ 128 อาจเกิดการโอเวอร์ฟิตได้; ควรเริ่มต้นด้วยมิติที่ต่ำกว่าและตรวจสอบความถูกต้องในงานปลายทาง
  • การละเลยข้อกำหนดตัวอย่างขั้นต่ำ: กราฟที่มีโหนดน้อยกว่า 50 โหนดจะสร้างคลังการเดินที่บางเกินไปที่จะฝึกฝนการฝังตัวที่เชื่อถือได้

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

DeepWalk, Node2Vec และ LINE แตกต่างกันอย่างไร?

DeepWalk ใช้การเดินสุ่มแบบสม่ำเสมอและโมเดล skip-gram ของ Word2Vec — เป็นพื้นฐานที่ง่ายที่สุด Node2Vec เพิ่มการเดินสุ่มแบบมีอคติที่ควบคุมโดย p และ q ทำให้นักวิเคราะห์สามารถปรับแต่งได้ว่าการเดินจะสำรวจแบบ breadth-first search (homophily) หรือ depth-first search (structural equivalence) LINE ไม่ใช้การเดินสุ่มเลย; มันปรับปรุงวัตถุประสงค์ความใกล้เคียงอันดับหนึ่งและอันดับสองโดยตรงบนรายการเส้นเชื่อม ซึ่งปรับขนาดได้ดีกว่าสำหรับกราฟขนาดใหญ่มาก แต่เสียสัญญาณเพื่อนบ้านจากการเดิน

ฉันจะเลือกพารามิเตอร์ p และ q ใน Node2Vec ได้อย่างไร?

p ควบคุมความน่าจะเป็นของการกลับไปยังโหนดก่อนหน้า (p ต่ำ = การย้อนรอยน้อยลง) และ q ควบคุมรัศมีการสำรวจ (q < 1 สนับสนุนการสำรวจออกไปด้านนอก, q > 1 ทำให้การเดินอยู่ใกล้แหล่งกำเนิด) หากคุณคาดว่าโหนดในชุมชนเดียวกันจะคล้ายกัน (homophily) ให้ตั้งค่า q < 1 เพื่อให้การเดินสำรวจออกไปด้านนอก หากคุณคาดว่าโหนดที่มีบทบาทเชิงโครงสร้างเดียวกันจะคล้ายกันแม้จะอยู่ห่างกัน ให้ตั้งค่า p < 1 เพื่อส่งเสริมการสำรวจแบบ depth-first ตรวจสอบความถูกต้องของทั้งสองระบอบในงานปลายทาง

ฉันสามารถฝังโหนดใหม่หลังการฝึกอบรมโดยไม่ต้องฝึกโมเดลใหม่ทั้งหมดได้หรือไม่?

Node2Vec และ DeepWalk มาตรฐานเป็นแบบ transductive: เมทริกซ์การฝังตัวครอบคลุมเฉพาะโหนดที่เห็นระหว่างการฝึกอบรมเท่านั้น สำหรับการสรุปผลแบบ inductive ไปยังโหนดใหม่ที่ไม่เคยเห็นมาก่อน ให้ใช้วิธีการโครงข่ายประสาทเทียมกราฟแบบ inductive เช่น GraphSAGE ซึ่งเรียนรู้ฟังก์ชันการรวมตัวบนเพื่อนบ้านของโหนดที่สามารถนำไปใช้กับโหนดใดๆ ในเวลาอนุมานได้

ฉันควรใช้กี่มิติสำหรับการฝังตัว?

ตัวเลือกที่พบบ่อยที่สุดคือ 64 และ 128 และสิ่งเหล่านี้ทำงานได้ดีสำหรับกราฟขนาดกลางถึงใหญ่ สำหรับกราฟขนาดเล็ก (50–200 โหนด) ให้เริ่มต้นด้วยมิติที่ต่ำกว่า (16 หรือ 32) เพื่อหลีกเลี่ยงการโอเวอร์ฟิต และประเมินคุณภาพการฝังตัวโดยการวัดประสิทธิภาพของงานปลายทาง (เช่น ความแม่นยำในการจำแนกประเภทโหนด) แทนที่จะเป็นข้อผิดพลาดในการสร้างใหม่เพียงอย่างเดียว

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

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

  1. Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.

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