การฝังตัวของเครือข่าย — 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 หรือวิธีการแบบลำดับชั้น
- การตรวจจับความผิดปกติ — โหนดที่การฝังตัวเป็นค่าผิดปกติในปริภูมิเวกเตอร์อาจแสดงถึงบทบาทเชิงโครงสร้างที่ผิดปกติ
- ระบบแนะนำที่ผู้ใช้และรายการเป็นโหนดในกราฟปฏิสัมพันธ์แบบสองส่วนหรือหลายส่วน
วิธีการทำงาน
วิธีการทำงาน
กระบวนการเริ่มต้นด้วยกราฟ G ซึ่งโหนดคือเอนทิตีและเส้นเชื่อมแสดงถึงความสัมพันธ์ เส้นเชื่อมอาจมีทิศทางหรือไม่ก็ได้ และอาจมีน้ำหนักที่จะส่งผลต่อความน่าจะเป็นของการเดินทางในภายหลัง หากมีน้ำหนักเส้นเชื่อม จะถูกรวมอยู่ในความน่าจะเป็นของการเดิน หากไม่มี น้ำหนักของเส้นเชื่อมทั้งหมดจะเท่ากัน ในขั้นตอนนี้ นักวิเคราะห์ยังเลือกรูปแบบอัลกอริทึมด้วย — DeepWalk สำหรับการเดินสุ่มแบบสม่ำเสมอ, Node2Vec สำหรับการเดินแบบมีอคติที่ควบคุมโดยพารามิเตอร์ p (การย้อนกลับ) และ q (การออกนอก) หรือ LINE เมื่อต้องการเรียนรู้ความใกล้เคียงของเพื่อนบ้านอันดับหนึ่งและอันดับสองแยกกัน การเลือกระหว่างระบอบพารามิเตอร์ของ Node2Vec ถูกชี้นำโดยคุณสมบัติเครือข่ายที่คาดหวัง: homophily (โหนดที่คล้ายกันเชื่อมต่อกัน ดังนั้นจึงควรสำรวจแบบ breadth-first, q < 1) หรือ structural equivalence (โหนดที่มีบทบาทคล้ายกันอาจอยู่ห่างกัน ดังนั้นจึงควรสำรวจแบบ depth-first, p < 1)
เริ่มต้นจากแต่ละโหนด อัลกอริทึมจะจำลองชุดของการเดินสุ่มที่มีความยาวคงที่ (โดยทั่วไปคือ 30 ขั้น) และทำซ้ำหลายครั้ง (โดยทั่วไปคือ 200 ครั้งต่อโหนด) การเดินแต่ละครั้งจะสร้างลำดับของตัวระบุโหนดที่คล้ายกับประโยคของคำ ใน DeepWalk โหนดถัดไปจะถูกเลือกอย่างสม่ำเสมอจากเพื่อนบ้าน ใน Node2Vec โหนดถัดไปจะถูกเลือกตามความน่าจะเป็นของการเปลี่ยนสถานะที่มีอคติโดย p และ q: การกลับไปยังโหนดก่อนหน้าจะถูกลงโทษด้วย 1/p การคงอยู่ที่ระยะทางเดิมจะถูกเก็บไว้ที่ 1 และการเคลื่อนที่ออกไปไกลขึ้นจะถูกควบคุมโดย 1/q ชุดของการเดินทั้งหมดจะสร้างคลังลำดับโหนดที่เข้ารหัสโครงสร้างของกราฟ
คลังลำดับโหนดจะถูกป้อนเข้าสู่โมเดล skip-gram (สถาปัตยกรรมเดียวกับ Word2Vec) สำหรับแต่ละโหนดในการเดิน โมเดลจะทำนายโหนดบริบทโดยรอบภายในหน้าต่าง (โดยทั่วไปคือ 10 ขั้น) ผ่านการไล่ระดับความชันแบบสุ่ม โมเดลจะเรียนรู้การนำเสนอเวกเตอร์ความหนาแน่นสูงที่มีมิติคงที่ — โดยทั่วไปคือ 64 หรือ 128 — สำหรับแต่ละโหนด เพื่อให้โหนดที่ปรากฏร่วมกันในการเดินมีเวกเตอร์ที่คล้ายกัน มิติเป็นไฮเปอร์พารามิเตอร์: มิติที่ใหญ่ขึ้นจะจับโครงสร้างได้มากขึ้น แต่เพิ่มการคำนวณและความเสี่ยงที่จะเกิดการโอเวอร์ฟิตกับกราฟขนาดเล็ก
เมื่อได้รับการฝึกฝนแล้ว โมเดลจะให้เวกเตอร์การฝังตัวหนึ่งเวกเตอร์ต่อโหนด เวกเตอร์เหล่านี้ถูกใช้เป็นคุณลักษณะสำหรับการจำแนกประเภทโหนด (ป้อนเข้าสู่การถดถอยโลจิสติกส์หรือตัวจำแนกประเภทโครงข่ายประสาทเทียม) การทำนายการเชื่อมโยง (เปรียบเทียบเวกเตอร์ของคู่โหนดที่คาดการณ์) หรือการตรวจจับชุมชน (การจัดกลุ่มเวกเตอร์) การฝังตัวเหล่านี้เป็นแบบ 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) เพื่อหลีกเลี่ยงการโอเวอร์ฟิต และประเมินคุณภาพการฝังตัวโดยการวัดประสิทธิภาพของงานปลายทาง (เช่น ความแม่นยำในการจำแนกประเภทโหนด) แทนที่จะเป็นข้อผิดพลาดในการสร้างใหม่เพียงอย่างเดียว
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
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คัดลอกแล้ว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คัดลอกแล้ว