การทำนายลิงก์ — การอนุมานขอบที่ขาดหายไปและขอบในอนาคตในเครือข่าย
- ปี
- 2003
- ประเภท
- Network inference task
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การทำนายลิงก์ (Link prediction) เป็นภารกิจการวิเคราะห์เครือข่ายที่ประมาณการว่าขอบใดหายไปจากกราฟที่สังเกตได้ หรือขอบใดมีแนวโน้มที่จะก่อตัวขึ้นในอนาคต ซึ่งได้รับการกำหนดอย่างเป็นทางการโดย Liben-Nowell และ Kleinberg (2003, 2007) ครอบคลุมวิธีการที่หลากหลาย ตั้งแต่ดัชนีความคล้ายคลึงเชิงโครงสร้างอย่างง่าย เช่น Common Neighbors, Jaccard coefficient และ Adamic-Adar ไปจนถึงการแยกตัวประกอบเมทริกซ์ (matrix factorisation) และวิธีการโครงข่ายประสาทเทียมแบบกราฟ (graph neural network - GNN) และได้รับการประเมินด้วย AUC และ Average Precision เพื่อพิจารณาอัตราส่วนที่ไม่สมดุลอย่างมากของขอบที่มีอยู่จริงกับขอบที่ไม่มีอยู่จริง
แนวคิดเบื้องหลังวิธีการ
ในเครือข่ายจริงใด ๆ ขอบที่บันทึกไว้เป็นเพียงส่วนหนึ่งของการเชื่อมต่อที่แท้จริงเท่านั้น: แพลตฟอร์มเพื่อนอาจพลาดการเชื่อมโยงที่ไม่เปิดเผย, ฐานข้อมูลการอ้างอิงอาจละเว้นเอกสารที่ไม่ได้จัดทำดัชนี, และการทดสอบปฏิสัมพันธ์ของโปรตีนอาจทำให้คู่จำนวนมากไม่ได้รับการทดสอบ การทำนายลิงก์ถามว่า: เมื่อพิจารณาจากการเชื่อมต่อที่เราเห็น คู่ที่ไม่ได้สังเกตคู่ใดมีแนวโน้มที่จะเชื่อมต่อกันมากที่สุด? แนวคิดหลักคือโหนดสองโหนดที่มีเพื่อนบ้านร่วมกันจำนวนมาก หรืออยู่ใกล้กันในพื้นที่ฝังตัวที่เรียนรู้ มีแนวโน้มที่จะเชื่อมโยงกันมากกว่าโหนดสองโหนดที่อยู่ห่างกันเชิงโครงสร้าง ดัชนีที่อิงตามความคล้ายคลึงกันทำให้สิ่งนี้ชัดเจนด้วยสูตรเดียว; วิธีการที่อิงตาม GNN เรียนรู้ว่ารูปแบบโครงสร้างใดที่ทำนายการเชื่อมต่อได้ดีที่สุดจากตัวอย่างที่มีป้ายกำกับ
ประวัติศาสตร์
ภารกิจนี้ได้รับการกำหนดอย่างเป็นทางการโดย Liben-Nowell และ Kleinberg ในเอกสาร SODA ปี 2003 และฉบับขยาย JASIST ปี 2007 ซึ่งพวกเขาได้ทดสอบดัชนีความคล้ายคลึงเชิงโครงสร้างอย่างง่ายบนเครือข่ายการเขียนร่วม และแสดงให้เห็นว่าโครงสร้างเพียงอย่างเดียวมีสัญญาณการทำนายที่แข็งแกร่ง งานต่อมาได้ขยายภารกิจไปยังการแยกตัวประกอบเมทริกซ์และโมเดลสร้างความน่าจะเป็น สาขาวิชานี้ได้รับการพัฒนาอย่างมากโดย Zhang และ Chen (2018) ซึ่งเสนอโครงสร้าง Seal — การดึงกราฟย่อยที่ล้อมรอบในท้องถิ่นและจำแนกด้วย GNN — แสดงให้เห็นว่าคุณลักษณะเชิงโครงสร้างที่เรียนรู้มีประสิทธิภาพเหนือกว่าดัชนีความคล้ายคลึงที่สร้างขึ้นด้วยมืออย่างสม่ำเสมอในเครือข่ายมาตรฐานที่หลากหลาย
ควรใช้เมื่อใด
การทำนายลิงก์เหมาะกับปัญหาใด ๆ ที่เครือข่ายไม่สมบูรณ์หรือมีการเปลี่ยนแปลง และเป้าหมายคือการกู้คืนหรือคาดการณ์ขอบ สถานการณ์ที่เหมาะสม ได้แก่ การแนะนำการเชื่อมต่อใหม่ในเครือข่ายสังคมออนไลน์ การทำนายการอ้างอิงหรือการทำงานร่วมกันในอนาคต การอนุมานปฏิสัมพันธ์ระหว่างโปรตีน และการเติมเต็มกราฟความรู้ วิธีการนี้ต้องมีโหนดอย่างน้อย 50 โหนดและความหนาแน่นของขอบที่สังเกตได้เพียงพอ เพื่อให้สามารถเรียนรู้รูปแบบโครงสร้างได้ หากมีโหนดน้อยกว่า 20 โหนด การวิเคราะห์ความเป็นศูนย์กลาง (centrality analysis) เป็นทางเลือกที่ปลอดภัยกว่า ส่วนที่สังเกตได้ของกราฟต้องเป็นตัวแทนที่ดี; หากกลไกการสุ่มตัวอย่างมีอคติอย่างมาก ขอบที่อนุมานได้อาจสะท้อนถึงสิ่งประดิษฐ์จากการสุ่มตัวอย่างมากกว่าโครงสร้างที่แท้จริง
ข้อจำกัดและข้อควรพิจารณา
- ประสิทธิภาพขึ้นอยู่กับกลยุทธ์การสุ่มตัวอย่างเชิงลบอย่างมาก; กลยุทธ์ที่แตกต่างกันสามารถให้ข้อสรุปที่แตกต่างกันจากโมเดลเดียวกัน
- วิธีการที่อิงตาม GNN ต้องใช้ชุดขอบที่มีป้ายกำกับขนาดใหญ่พอสมควรและทรัพยากรการคำนวณจำนวนมาก
- ดัชนีเชิงโครงสร้างสมมติว่าความคล้ายคลึงกันในโครงสร้างที่สังเกตได้บ่งบอกถึงการเชื่อมต่อในอนาคต ซึ่งอาจไม่เป็นจริงในเครือข่ายที่มีโครงสร้างแบบ heterophilic
- การแบ่งชุดข้อมูลการฝึกอบรม-ทดสอบตามเวลาเป็นสิ่งจำเป็น แต่ต้องใช้ข้อมูลเวลาที่เชื่อถือได้; หากไม่มีข้อมูลเวลา การรั่วไหลของข้อมูลจะทำให้ประสิทธิภาพที่ปรากฏสูงเกินจริง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ครอบคลุมความซับซ้อนที่หลากหลาย — ดัชนี Jaccard หรือ Adamic-Adar อย่างง่ายไม่จำเป็นต้องมีการฝึกอบรมและทำงานโดยตรงกับโครงสร้างกราฟ ในขณะที่วิธีการที่อิงตาม GNN เรียนรู้รูปแบบโครงสร้างที่ซับซ้อน
- ดัชนีความคล้ายคลึงกันแบบไม่ใช้โมเดลนั้นรวดเร็ว ตีความได้ และแข็งแกร่งบนกราฟที่เบาบางซึ่งมีสัญญาณการฝึกอบรมจำกัด
- วิธีการ GNN สามารถสรุปผลได้ดีในโดเมนต่าง ๆ (สังคม, ชีวภาพ, กราฟความรู้) และจับโครงสร้างลำดับสูงได้
- กรอบการประเมิน AUC/AP แข็งแกร่งต่อความไม่สมดุลของคลาสที่รุนแรงระหว่างขอบจริงและขอบที่ไม่มีอยู่จริง
การประยุกต์ใช้
- การแนะนำเพื่อนหรือการเชื่อมต่อในเครือข่ายสังคมออนไลน์ (Facebook People You May Know, LinkedIn)
- การทำนายความร่วมมือวิจัยในอนาคตหรือความสัมพันธ์การอ้างอิงในเครือข่ายวิชาการ
- การอนุมานปฏิสัมพันธ์ระหว่างโปรตีนที่ขาดหายไปในเครือข่ายชีวภาพจากข้อมูลการทดลองบางส่วน
- การเติมเต็มกราฟความรู้โดยการทำนายความสัมพันธ์ระหว่างเอนทิตี
- การทำนายปฏิสัมพันธ์ระหว่างยาและเป้าหมายในเครือข่ายเภสัชวิทยา
วิธีการทำงาน
วิธีการทำงาน
เครือข่ายถูกสร้างขึ้นจากขอบที่สังเกตได้และแบ่งออกเป็นชุดข้อมูลการฝึกอบรมและชุดข้อมูลการทดสอบโดยใช้การแบ่งแบบตามเวลาหรือแบบสุ่ม การแบ่งแบบตามเวลาเป็นที่นิยมมากกว่าเมื่อมีข้อมูลเวลา เนื่องจากช่วยป้องกันการรั่วไหลของข้อมูล: ขอบในอนาคตจะต้องไม่ให้ข้อมูลแก่โมเดลเกี่ยวกับขอบในอดีต กราฟการฝึกอบรมเป็นกราฟเดียวที่วิธีการให้คะแนนสามารถสังเกตได้
เนื่องจากคู่โหนดส่วนใหญ่ไม่ได้เชื่อมต่อกัน การประเมินคู่ที่ไม่มีอยู่ทั้งหมดจึงไม่สามารถทำได้จริง กลยุทธ์การสุ่มตัวอย่างเชิงลบ (negative-sampling strategy) จะเลือกชุดของขอบที่ไม่มีอยู่จริงเพื่อใช้เป็นตัวอย่างเชิงลบ ขนาดและกลยุทธ์การสุ่มตัวอย่าง (สุ่ม, hard-negative, degree-balanced) ส่งผลกระทบอย่างมากต่อประสิทธิภาพที่วัดได้และต้องรายงานควบคู่ไปกับผลลัพธ์
แต่ละคู่ผู้สมัครจะได้รับคะแนนความน่าจะเป็น ดัชนีเชิงโครงสร้างคำนวณคะแนนจากโครงสร้างกราฟที่สังเกตได้ — Common Neighbors นับเพื่อนบ้านร่วมกัน, Jaccard ทำให้การนับนั้นเป็นมาตรฐานโดยยูเนียน, และ Adamic-Adar ถ่วงน้ำหนักเพื่อนบ้านร่วมกันด้วยลอการิทึมผกผันของดีกรี วิธีการแยกตัวประกอบเมทริกซ์จะแยกเมทริกซ์ความประชิดออกเป็นปัจจัยแฝงซึ่งผลคูณจุดประมาณความน่าจะเป็นของขอบ วิธีการที่อิงตาม GNN ซึ่งโดดเด่นที่สุดคือกรอบงาน Seal ของ Zhang และ Chen (2018) จะดึงกราฟย่อยในท้องถิ่นรอบ ๆ คู่ผู้สมัครแต่ละคู่และฝึกตัวจำแนกกราฟเพื่อแยกแยะขอบจริงออกจากขอบปลอม โดยจับรูปแบบโครงสร้างลำดับสูงที่ดัชนีอย่างง่ายพลาดไป
การทำนายจะถูกจัดอันดับตามคะแนนและเปรียบเทียบกับขอบบวกและลบที่ถูกเก็บไว้ AUC-ROC วัดความน่าจะเป็นที่คู่บวกแบบสุ่มจะถูกจัดอันดับสูงกว่าคู่ลบแบบสุ่ม Average Precision (AP) สรุปความแม่นยำตลอดการจัดอันดับทั้งหมดและให้ข้อมูลมากขึ้นเมื่อตัวอย่างบวกหายาก ต้องรายงานทั้งสองเมตริก; ความแม่นยำเพียงอย่างเดียวอาจทำให้เข้าใจผิดภายใต้ความไม่สมดุลของคลาสที่รุนแรง
ข้อผิดพลาดที่พบบ่อย
- การรั่วไหลของขอบในอนาคตเข้าสู่กราฟการฝึกอบรม — ควรใช้การแบ่งแบบตามเวลาหรือแบบสุ่มอย่างเคร่งครัด และตรวจสอบว่าไม่มีขอบทดสอบปรากฏในเมทริกซ์ความประชิดของการฝึกอบรม
- การรายงานความแม่นยำเท่านั้น; เนื่องจากขอบที่ไม่มีอยู่มีจำนวนมากกว่าขอบจริงอย่างมาก ความแม่นยำจึงแทบไม่มีความหมาย — ควรรายงาน AUC และ AP เสมอ
- การละเลยกลยุทธ์การสุ่มตัวอย่างเชิงลบเมื่อเปรียบเทียบวิธีการ; การเปลี่ยนการสุ่มตัวอย่างสามารถย้อนกลับการจัดอันดับระหว่างโมเดลได้
- การใช้การทำนายลิงก์กับกราฟที่มีโหนดน้อยกว่า 20 โหนด — ด้วยโหนดจำนวนน้อยเช่นนี้ รูปแบบโครงสร้างจะเบาบางเกินไปที่จะให้การทำนายที่เชื่อถือได้; ควรเลือกการวิเคราะห์ความเป็นศูนย์กลางแทน
- การถือว่ากราฟที่สังเกตได้ที่มีอคติเป็นตัวอย่างที่เป็นตัวแทน — หากขอบที่สังเกตได้ขาดประเภทโหนดบางประเภทอย่างเป็นระบบ การทำนายจะได้รับอคตินั้นมาด้วย
คำถามที่พบบ่อย
ฉันควรเลือกวิธีการใด — ดัชนีความคล้ายคลึงหรือ GNN?
ดัชนีความคล้ายคลึง (Common Neighbors, Jaccard, Adamic-Adar) เป็นจุดเริ่มต้นที่ดี: ไม่ต้องมีการฝึกอบรม ตีความได้ และมีประสิทธิภาพที่น่าประหลาดใจบนกราฟที่เบาบาง วิธีการที่อิงตาม GNN เช่น Seal มีประสิทธิภาพเหนือกว่าดัชนีบนเครือข่ายที่มีโครงสร้างลำดับสูงที่ซับซ้อน แต่ต้องใช้จำนวนขอบที่มีป้ายกำกับที่เพียงพอและทรัพยากรการคำนวณที่มากขึ้น เมื่อข้อมูลมีจำกัดหรือความสามารถในการตีความมีความสำคัญ ให้เริ่มต้นด้วยดัชนี
ฉันจะแบ่งกราฟสำหรับการประเมินโดยไม่ให้ข้อมูลรั่วไหลได้อย่างไร?
หากขอบของคุณมีข้อมูลเวลา ให้ใช้การแบ่งแบบตามเวลา: ฝึกอบรมบนขอบที่สังเกตได้ก่อนเวลาตัด และทดสอบบนขอบที่ก่อตัวขึ้นหลังจากนั้น หากไม่มีข้อมูลเวลา ให้เก็บเศษส่วนสุ่มของขอบเป็นบวก และสุ่มตัวอย่างจำนวนขอบที่ไม่มีอยู่เท่ากันหรือคงที่เป็นลบ โดยตรวจสอบให้แน่ใจว่าไม่มีขอบที่ถูกเก็บไว้ปรากฏในเมทริกซ์ความประชิดของการฝึกอบรม
ทำไม AUC ถึงดีกว่าความแม่นยำ?
ในเครือข่ายจริงใด ๆ จำนวนขอบที่ไม่มีอยู่มีมากกว่าจำนวนขอบที่มีอยู่จริงอย่างมาก — บ่อยครั้งหลายเท่าตัว โมเดลที่ไม่สำคัญที่ทำนายว่า 'ไม่มีขอบ' สำหรับทุกคู่จะมีความแม่นยำเกือบสมบูรณ์แบบในขณะที่ไม่ได้ทำนายสิ่งที่มีประโยชน์ใด ๆ AUC-ROC และ Average Precision เป็นเมตริกที่อิงตามการจัดอันดับซึ่งไม่ไวต่อความไม่สมดุลนี้และวัดคุณภาพของการจัดอันดับโดยตรง
การทำนายลิงก์สามารถนำไปใช้กับกราฟแบบมีทิศทางหรือแบบมีน้ำหนักได้หรือไม่?
ได้ สำหรับกราฟแบบมีทิศทาง คะแนนสามารถคำนวณแยกกันในแต่ละทิศทาง และกรอบงาน GNN บางอย่างสามารถจัดการความประชิดแบบมีทิศทางได้โดยธรรมชาติ สำหรับกราฟแบบมีน้ำหนัก ดัชนีความคล้ายคลึงสามารถรวมน้ำหนักขอบในการคำนวณเพื่อนบ้าน และวิธีการ GNN สามารถใช้คุณลักษณะขอบได้ อย่างไรก็ตาม การศึกษามาตรฐานส่วนใหญ่จะทำบนกราฟแบบไม่มีน้ำหนักและไม่มีทิศทาง ดังนั้นจึงต้องระมัดระวังเป็นพิเศษเมื่อปรับใช้วิธีการ
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Liben-Nowell, D. & Kleinberg, J. (2007). The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วZhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว