Bağlantı Tahmini — Ağlarda Eksik ve Gelecekteki Kenar Çıkarımı
- Yıl
- 2003
- Tür
- Network inference task
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Bağlantı tahmini, gözlemlenen bir grafikten hangi kenarların eksik olduğunu veya gelecekte hangi kenarların oluşma olasılığının yüksek olduğunu tahmin eden bir ağ analizi görevidir.
Liben-Nowell ve Kleinberg (2003, 2007) tarafından formüle edilen bu yöntem, Ortak Komşular, Jaccard katsayısı ve Adamic-Adar gibi basit yapısal benzerlik indekslerinden matris çarpanlarına ayırma ve grafik sinir ağı (GNN) yöntemlerine kadar geniş bir yaklaşım yelpazesini kapsar. Gerçek ve mevcut olmayan kenarlar arasındaki yüksek derecede dengesiz oranı hesaba katmak için AUC ve Ortalama Hassasiyet (Average Precision) ile değerlendirilir.
Yöntemin mantığı
Herhangi bir gerçek dünya ağında, kaydedilen kenarlar gerçek bağlantıların yalnızca bir kısmını temsil eder: arkadaşlık platformları açıklanmayan bağları kaçırır, atıf veritabanları indekslenmemiş makaleleri atlar ve protein-etkileşim deneyleri birçok çifti test etmeden bırakır. Bağlantı tahmini şunu sorar: görebildiğimiz bağlantılar göz önüne alındığında, hangi gözlemlenmemiş çiftlerin bağlantılı olma olasılığı en yüksektir? Temel sezgi, birçok ortak komşuyu paylaşan veya öğrenilmiş bir gömme uzayında birbirine yakın oturan iki düğümün, yapısal olarak uzak iki düğüme göre bağlantılı olma olasılığının daha yüksek olduğudur. Benzerlik tabanlı indeksler bunu tek bir formülle açıkça belirtirken; GNN tabanlı yaklaşımlar, etiketli örneklerden bağlantıyı en iyi tahmin eden yapısal modelleri öğrenir.
Tarih
Görev, Liben-Nowell ve Kleinberg tarafından 2003 tarihli bir SODA makalesinde ve genişletilmiş 2007 JASIST versiyonunda resmi olarak tanımlanmıştır; burada ortak yazarlık ağlarında basit yapısal benzerlik indekslerini karşılaştırmış ve yalnızca topolojinin güçlü bir tahmin sinyali taşıdığını göstermişlerdir. Sonraki çalışmalar görevi matris çarpanlarına ayırma ve olasılıksal üretken modellere genişletmiştir. Alan, Zhang ve Chen (2018) tarafından önemli ölçüde ilerletilmiştir; Seal çerçevesini önermişlerdir — yerel çevreleyen alt grafikleri çıkarıp bir GNN ile sınıflandırarak — öğrenilen yapısal özelliklerin çeşitli kıyaslama ağlarında el yapımı benzerlik indekslerinden sürekli olarak daha iyi performans gösterdiğini kanıtlamışlardır.
Ne zaman kullanılır?
Bağlantı tahmini, ağın eksik veya gelişmekte olduğu ve amacın kenarları kurtarmak veya tahmin etmek olduğu her türlü probleme uyar. Uygun senaryolar arasında sosyal ağlarda yeni bağlantılar önerme, gelecekteki atıfları veya işbirliklerini tahmin etme, protein-protein etkileşimlerini çıkarım yapma ve bilgi grafiklerini tamamlama yer alır. Yöntem, yapısal modellerin öğrenilebilir olması için en az 50 düğüm ve yeterli yoğunlukta gözlemlenmiş kenar gerektirir. 20'den az düğüm mevcut olduğunda, merkezilik analizi daha güvenli bir seçimdir. Grafiğin gözlemlenen kısmı temsili olmalıdır; örnekleme mekanizması ağır bir şekilde yanlıysa, çıkarılan kenarlar gerçek yapıyı değil, örnekleme artefaktlarını yansıtabilir.
Sınırlar ve dikkat edilmesi gerekenler
- Performans, negatif örnekleme stratejisine kritik olarak bağlıdır; farklı stratejiler aynı modelden farklı sonuçlar verebilir.
- GNN tabanlı yöntemler, yeterince büyük etiketli kenar kümesi ve önemli hesaplama kaynakları gerektirir.
- Yapısal indeksler, gözlemlenen topolojideki benzerliğin gelecekteki bağlantıyı ima ettiğini varsayar; bu, heterofilik yapıya sahip ağlarda geçerli olmayabilir.
- Zamansal eğitim-test bölmesi esastır ancak güvenilir zaman damgaları gerektirir; bunlar olmadan, bilgi sızıntısı görünen performansı şişirir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Geniş bir karmaşıklık yelpazesini kapsar — basit Jaccard veya Adamic-Adar indeksleri eğitim gerektirmez ve doğrudan grafik topolojisi üzerinde çalışırken, GNN tabanlı yöntemler karmaşık yapısal modelleri öğrenir.
- Modelden bağımsız benzerlik indeksleri hızlı, yorumlanabilir ve sınırlı eğitim sinyali olan seyrek grafiklerde sağlamdır.
- GNN yaklaşımları alanlar arasında (sosyal, biyolojik, bilgi grafiği) iyi genelleşir ve daha yüksek dereceli topolojiyi yakalar.
- AUC/AP değerlendirme çerçevesi, gerçek ve mevcut olmayan kenarlar arasındaki şiddetli sınıf dengesizliğine karşı sağlamdır.
Uygulama alanları
- Sosyal ağlarda arkadaş veya bağlantı önerisi (Facebook Tanıyor Olabileceğin Kişiler, LinkedIn).
- Akademik ağlarda gelecekteki araştırma işbirliklerini veya atıf ilişkilerini tahmin etme.
- Kısmi deneysel verilerden biyolojik ağlarda eksik protein-protein etkileşimlerini çıkarım yapma.
- Varlıklar arasındaki ilişkileri tahmin ederek bilgi grafiklerini tamamlama.
- Farmakolojik ağlarda ilaç-hedef etkileşimi tahmini.
Nasıl çalışır?
Nasıl çalışır?
Ağ, gözlemlenen kenarlardan oluşturulur ve zamansal veya rastgele bir bölme kullanılarak eğitim ve test kümelerine ayrılır. Zaman damgaları mevcut olduğunda zamansal bölme tercih edilir çünkü bilgi sızıntısını önler: gelecekteki kenarlar, modeli geçmiştekiler hakkında bilgilendirmemelidir. Puanlama yönteminin gözlemleyebileceği tek grafik eğitim grafiğidir.
Düğüm çiftlerinin büyük çoğunluğu bağlantısız olduğundan, her eksik çifti değerlendirmek pratik değildir. Bir negatif örnekleme stratejisi, negatif örnekler olarak hizmet etmek üzere mevcut olmayan kenarlardan bir küme seçer. Boyut ve örnekleme stratejisi (rastgele, zor-negatif, derece-dengeli) ölçülen performansı önemli ölçüde etkiler ve sonuçlarla birlikte rapor edilmelidir.
Her aday çift bir olasılık puanı alır. Yapısal indeksler puanı gözlemlenen grafik topolojisinden hesaplar — Ortak Komşular paylaşılan komşuları sayar, Jaccard bu sayıyı birleşimle normalleştirir ve Adamic-Adar paylaşılan komşuları derecelerinin ters logaritmasıyla ağırlıklandırır. Matris çarpanlarına ayırma yöntemleri, komşuluk matrisini, nokta çarpımları kenar olasılığını yaklaşık olarak veren gizli faktörlere ayrıştırır. En belirgin olarak Zhang ve Chen'in (2018) Seal çerçevesi olan GNN tabanlı yöntemler, her aday çiftin etrafındaki yerel alt grafikleri çıkarır ve gerçek kenarları sahte kenarlardan ayırmak için bir grafik sınıflandırıcı eğitir, böylece basit indekslerin kaçırdığı daha yüksek dereceli yapısal modelleri yakalar.
Tahminler puana göre sıralanır ve ayrılmış pozitif ve negatif kenarlarla karşılaştırılır. AUC-ROC, rastgele bir pozitif çiftin rastgele bir negatif çiftin üzerinde sıralanma olasılığını ölçer. Ortalama Hassasiyet (AP), tüm sıralamadaki hassasiyeti özetler ve pozitif örneklerin nadir olduğu durumlarda daha bilgilendiricidir. Her iki metrik de rapor edilmelidir; şiddetli sınıf dengesizliği altında yalnızca doğruluk yanıltıcıdır.
Sık yapılan hatalar
- Gelecekteki kenarları eğitim grafiğine sızdırmak — her zaman zamansal veya kesinlikle rastgele bölmeler kullanın ve eğitim komşuluk matrisinde hiçbir test kenarının görünmediğini doğrulayın.
- Yalnızca doğruluğu rapor etmek; mevcut olmayan kenarlar gerçek kenarlardan çok daha fazla olduğu için, doğruluk neredeyse anlamsızdır — her zaman AUC ve AP raporlayın.
- Yöntemleri karşılaştırırken negatif örnekleme stratejisini göz ardı etmek; örneklemeyi değiştirmek modeller arasındaki sıralamaları tersine çevirebilir.
- Bağlantı tahminini 20'den az düğüme sahip grafiklere uygulamak — bu kadar az düğümle yapısal modeller güvenilir tahminler verecek kadar seyrek olur; bunun yerine merkezilik analizini tercih edin.
- Yanlı gözlemlenmiş bir grafiği temsili bir örnek olarak ele almak — gözlemlenen kenarlar sistematik olarak belirli düğüm türlerini eksik bırakıyorsa, tahminler bu yanlılığı miras alacaktır.
Sık sorulan sorular
Hangi yaklaşımı seçmeliyim — bir benzerlik indeksi mi yoksa bir GNN mi?
Benzerlik indeksleri (Ortak Komşular, Jaccard, Adamic-Adar) iyi bir başlangıç noktasıdır: eğitim gerektirmezler, yorumlanabilirler ve seyrek grafiklerde şaşırtıcı derecede iyi performans gösterirler. Seal gibi GNN tabanlı yöntemler, karmaşık daha yüksek dereceli yapıya sahip ağlarda indekslerden daha iyi performans gösterir ancak yeterli sayıda etiketli kenar ve daha fazla hesaplama kaynağı gerektirir. Veriler sınırlı olduğunda veya yorumlanabilirlik önemli olduğunda, indekslerle başlayın.
Bilgi sızdırmadan değerlendirme için grafiği nasıl bölerim?
Kenarlarınız zaman damgaları taşıyorsa, zamansal bir bölme kullanın: bir kesme süresinden önce gözlemlenen kenarlar üzerinde eğitim yapın ve ondan sonra oluşan kenarlar üzerinde test yapın. Zaman damgaları olmadan, kenarların rastgele bir kısmını pozitif olarak ayırın ve eşit veya sabit sayıda mevcut olmayan kenarı negatif olarak örnekleyin, ayrılmış hiçbir kenarın eğitim komşuluk matrisinde görünmediğinden emin olun.
AUC neden doğruluktan daha çok tercih edilir?
Herhangi bir gerçek ağda, mevcut olmayan kenarların sayısı mevcut olanların sayısını kat kat aşar — genellikle birkaç büyüklük mertebesinde. Her çift için 'kenar yok' tahmininde bulunan önemsiz bir model, neredeyse mükemmel doğruluk elde ederken hiçbir faydalı tahmin yapmaz. AUC-ROC ve Ortalama Hassasiyet, bu dengesizliğe duyarsız olan ve sıralamanın kalitesini doğrudan ölçen sıralama tabanlı metriklerdir.
Bağlantı tahmini yönlü veya ağırlıklı grafiklere uygulanabilir mi?
Evet. Yönlü grafikler için, puanlar her yönde ayrı ayrı hesaplanabilir ve bazı GNN çerçeveleri yönlü komşuluğu doğal olarak işler. Ağırlıklı grafikler için, benzerlik indeksleri komşuluk hesaplamasında kenar ağırlıklarını dahil edebilir ve GNN yöntemleri kenar özelliklerini kullanabilir. Ancak, çoğu kıyaslama çalışması ağırlıksız yönsüz grafikler üzerindedir, bu nedenle yöntemleri uyarlarken ekstra dikkat gereklidir.
İlgili yöntemler
Kaynaklar
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 kaynağını açKopyalandı.Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.
Yayın kaynağını açKopyalandı.