İçeriğe atla
Arama sonuçlarına dön

Graf Sinir Ağı — GCN / GAT / GraphSAGE

Yıl
2017–2018 (major variants)
Tür
Deep learning on graph-structured data

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Bir Graf Sinir Ağı (GNN), düğüm özelliklerini yapısal bilgilerle yinelemeli komşu mesajlaşması yoluyla birleştirerek doğrudan graf yapılı veriler üzerinde çalışan bir derin öğrenme mimarisidir.

Üç kanonik varyant — Kipf ve Welling tarafından 2017'de tanıtılan Graf Evrişimsel Ağı (GCN), Veličković ve ark. tarafından 2018'de tanıtılan Graf Dikkat Ağı (GAT) ve GraphSAGE — komşu bilgilerini nasıl topladıkları konusunda farklılık gösterir: GCN tam komşuluk üzerinde spektral evrişim uygular, GAT komşuları öğrenilmiş dikkat puanlarıyla ağırlıklandırır ve GraphSAGE, görülmemiş düğümlere genelleme sağlayan tümevarımsal olarak yerel komşulukları örnekler ve toplar.

Yöntemin mantığı

Bir sosyal ağdaki her düğümü bir kişi olarak düşünün. O kişinin kendi profili (özellikleri) vardır, ancak kimleri tanıdığı da onun hakkında çok şey söyler. Bir GNN, her düğümün komşularından tekrarlı olarak mesajlar toplamasını, bu mesajları kendi bilgisiyle karıştırmasını ve temsilini katman katman güncellemesini sağlar. Bu dedikodu tarzı değişimin birkaç turundan sonra, her düğümün gömülüşü sadece kendisini değil, etrafındaki yerel alt grafı yansıtır. GCN bunu komşuların sabit simetrik ortalamasıyla yapar; GAT, dikkat ağırlıklarını öğrenerek hangi komşulara daha çok güveneceğine karar verir; GraphSAGE, sabit bir komşu alt kümesini örnekler ve daha önce hiç görmediği düğümlere uygulanabilen bir toplama fonksiyonu öğrenir.

Tarih

Sinir ağlarının graflara uygulanmasının temelleri Scarselli ve ark. (2009) tarafından atıldı, ancak modern GNN çağı, spektral graf evrişimini simetrik normalize edilmiş komşuluk çarpımı kullanarak verimli bir birinci dereceden yaklaşıma basitleştiren Kipf ve Welling'in Graf Evrişimsel Ağı (2017) ile başladı. Bir yıl sonra, Veličković ve ark. (2018), GCN'nin sabit ortalamasını her kenarda öğrenilebilir dikkat katsayılarıyla değiştirerek Graf Dikkat Ağlarını tanıttı — modelin komşuları seçici olarak ağırlıklandırmasına izin verdi. Eş zamanlı olarak, Hamilton ve ark. (2017), sabit boyutlu komşulukları örnekleyen ve görülmemiş düğümlere aktarılabilir toplama fonksiyonları öğrenen tümevarımsal bir çerçeve olan GraphSAGE'i önerdi, bu da GNN'leri büyük ve dinamik graflar için pratik hale getirdi. Bu üç makale, günümüzde GNN araştırmalarının çoğuna temel oluşturan mesaj-geçirme paradigmasını oluşturdu.

Ne zaman kullanılır?

Verileriniz doğal olarak graf yapılı olduğunda — sosyal ağlar, atıf ağları, moleküler graflar, bilgi grafları veya varlıklar arasındaki ilişkilerin tahmin edici sinyal taşıdığı herhangi bir ortam — bir GNN kullanın. Bir düğüm özellik matrisine ve bir kenar listesine ihtiyacınız var. Anlamlı eğitim için minimum yaklaşık 50 düğüm gereklidir. GNN'ler düğüm sınıflandırmasına (her düğüm için bir etiket tahmin etme), bağlantı tahminine (eksik kenarları çıkarma) ve graf sınıflandırmasına (tüm bir graf için bir etiket atama) uygulanabilir. Homofili varsayımı — bağlı düğümlerin aynı etiketi paylaşma eğiliminde olması — GCN ve standart GAT tarafından örtük olarak kullanılır; grafınız heterofilik ise, bunun için tasarlanmış mimarileri düşünün. Büyük graflar için tam toplu eğitim bellek açısından yasaktır ve mini toplu komşu örneklemesi (GraphSAGE tarzı) gereklidir. Grafınız 20'den az düğüme sahipse, geleneksel merkezilik metrikleri daha uygun bir seçenektir.

Sınırlar ve dikkat edilmesi gerekenler

  • Aşırı Düzleşme: Çok sayıda GNN katmanı istiflemek, tüm düğüm gömülüşlerini ortak bir değere doğru iter, pratikte etkili derinliği yaklaşık 2-4 katmanla sınırlar.
  • Ölçeklenebilirlik: Tam toplu GCN ve GAT, tüm komşuluk matrisini ve özellik matrisini bellekte tutmayı gerektirir, bu da örnekleme veya bölümleme olmadan çok büyük graflar için uygulanamaz.
  • Standart toplama işlemine yerleştirilmiş homofili varsayımı, komşuların farklı etiketlere sahip olma eğiliminde olduğu heterofilik graflardaki performansı düşürür.
  • Minimum ~50 düğüm örnek boyutu gereklidir; daha az düğüm, modelin anlamlı temsiller öğrenmesi için yeterli sinyale sahip olmamasını sağlar.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Hem düğüm özelliklerini hem de graf topolojisini ortaklaşa kullanır, yalnızca birini kullanan yöntemlerden daha iyi performans gösterir.
  • GAT'ın dikkat mekanizması kenar başına önem puanları sağlar, toplama işlemine yorumlanabilirlik katar.
  • GraphSAGE tümevarımsaldır ve eğitim sırasında görülmeyen düğümlere ve graflara genelleme yapabilir, büyüyen ağlarda dağıtıma olanak tanır.
  • Tekdüzen bir mesaj-geçirme çerçevesi, aynı mimari omurgayla düğüm sınıflandırması, bağlantı tahmini ve graf sınıflandırmasını kapsar.

Uygulama alanları

  • Atıf ağlarında düğüm sınıflandırması — bir makalenin konusunu içeriğine ve atıf bağlantılarına göre tahmin etme.
  • İlaç keşfi — atomları düğüm ve kimyasal bağları kenar olarak ele alarak moleküler özellikleri tahmin etme.
  • Öneri sistemleri — kullanıcıları ve öğeleri iki taraflı bir graf olarak modelleme ve bağlantı tahmini yoluyla kullanıcı-öğe etkileşimlerini tahmin etme.
  • Finansal işlem ağlarında dolandırıcılık tespiti — özelliklerine ve komşuluk yapısına göre anormal düğümleri belirleme.
  • Bilgi grafı tamamlama — büyük ölçekli bilgi tabanlarındaki varlıklar arasındaki eksik ilişkileri çıkarma.

Nasıl çalışır?

Nasıl çalışır?

1

Graf, bir düğüm özellik matrisi X (düğüm başına bir satır, öznitelik başına bir sütun) ve bir kenar listesi (veya komşuluk matrisi) A ile tanımlanır. Yönsüz kenarlar GCN ve GAT için standarttır; GraphSAGE yönlü grafikleri de destekler. Kendi kendine döngüler genellikle A'ya eklenir, böylece her düğüm kendi toplama işlemine dahil edilir.

2

Ham düğüm öznitelikleri normalleştirilir ve gerekirse sürekli bir vektör uzayına gömülür. Kenar öznitelikleri, mevcutsa, ek sinyaller olarak dahil edilebilir. Sonuç, her GNN katmanının dönüştüreceği yoğun bir özellik matrisidir.

3

Her GNN katmanı, bir düğümün komşularının özelliklerini toplayarak ve bunları öğrenilebilir bir ağırlık matrisi ve doğrusal olmayan bir aktivasyon aracılığıyla düğümün kendi özellikleriyle birleştirerek yeni bir düğüm temsili hesaplar. GCN, normalleştirilmiş komşuluk çarpımı (spektral evrişim) uygular; GAT, her kenar için softmax dikkat katsayıları hesaplar, böylece etkili komşular daha fazla katkıda bulunur; GraphSAGE, sabit boyutlu bir komşuluğu rastgele örnekler ve farklılaştırılabilir bir toplayıcı (ortalama, LSTM veya havuzlama) uygular. L katmanı istiflemek, bilginin L atlama uzağa akmasını sağlar, ancak çok fazla katman istiflemek, tüm düğüm gömülüşlerinin aynı değere yakınsadığı aşırı düzleşmeye neden olur.

4

Son düğüm gömülüşleri göreve özgü bir başlığa beslenir. Düğüm sınıflandırması için bir softmax katmanı her düğüme sınıf olasılıkları atar. Bağlantı tahmini için bir iç çarpım veya MLP, iki düğüm gömülüşü arasındaki bir kenarın olasılığını puanlar. Graf sınıflandırması için küresel bir havuzlama (toplam, ortalama veya hiyerarşik) sınıflandırma katmanından önce tüm düğüm gömülüşlerini tek bir graf düzeyinde vektöre toplar.

5

Model performansı, göreve uygun metrikler kullanılarak tutulan bir test kümesinde ölçülür: düğüm ve graf sınıflandırması için doğruluk veya F1, bağlantı tahmini için AUC-ROC. Graf veri kümeleri genellikle sınırlı boyutta olduğundan, transdaktif değerlendirme (aynı graf üzerinde tren/val/test maskeleri) veya tümevarımsal bölmeler (ayrık alt graflar) dağıtım senaryosuna uygun olmalıdır.

Sık yapılan hatalar

  • Çok fazla GNN katmanı eklemek aşırı düzleşmeye neden olur: tüm düğüm gömülüşleri yakınsar ve model ayırt edici gücünü kaybeder. Katman sayısını 2-4 arasında tutun ve gömülüş varyansını izleyin.
  • Mini toplu işlem olmadan tam graf üzerinde eğitim, büyük ağlar için bellek açısından yasaktır; birkaç binden fazla düğüme sahip graflar için GraphSAGE tarzı komşu örneklemesi veya graf bölümlemesi kullanın.
  • Transdaktif olarak eğitilmiş bir GCN'yi çıkarım zamanında yeni, görülmemiş düğümlere doğrudan uygulamak yanlıştır; dağıtımınız yeni düğümlere genelleme gerektiriyorsa GraphSAGE gibi tümevarımsal bir yöntem kullanın.
  • Heterofilik graflardaki homofili varsayımını göz ardı etmek kötü sonuçlar verir; standart bir GNN varyantı seçmeden önce grafın assortativity katsayısını inceleyin.
  • 20'den az düğümle GNN eğitimi güvenilmez temsiller üretir; bu rejimde geleneksel merkezilik tabanlı analizi tercih edin.

Sık sorulan sorular

Hangi GNN varyantıyla başlamalıyım — GCN, GAT veya GraphSAGE?

GCN, en basit temel çizgidir ve tüm düğümlerin eğitim sırasında bilindiği küçük ila orta ölçekli homofilik graflarda iyi çalışır. Komşu öneminin değiştiği ve yorumlanabilir dikkat ağırlıkları istediğinizde GAT tercih edilir. Eğitim sırasında görülmeyen düğümlere genelleme yapmanız gerektiğinde veya graf tam toplu işlem için çok büyük olduğunda GraphSAGE doğru seçimdir.

Aşırı düzleşme nedir ve nasıl önlenir?

Aşırı düzleşme, çok sayıda GNN katmanının tüm düğüm gömülüşlerinin aynı değere yakınsamasına neden olarak ayırt edici bilgiyi ortadan kaldırdığında meydana gelir. Pratikte, 2-4 katman genellikle optimaldir. Daha derin mimariler gerekliyse artık bağlantılar, zıplayan bilgi ağları ve DropEdge gibi teknikler yardımcı olabilir.

GNN'ler tüm düğümler için etiketli veri gerektirir mi?

Hayır. GCN ve GAT, yaygın olarak yalnızca az sayıda düğümün etiket taşıdığı yarı denetimli ortamlarda kullanılır; graf yapısı etiketli düğümlerden etiketsiz düğümlere bilgi yayar. GraphSAGE ayrıca göreve bağlı olarak tam denetimli veya denetimsiz bir şekilde eğitilebilir.

Graf ne kadar büyük olmalı?

Anlamlı GNN eğitimi için minimum yaklaşık 50 düğüm gereklidir. 20'den az düğümle model güvenilir temsiller öğrenemez ve geleneksel merkezilik tabanlı analiz daha uygundur. Milyonlarca düğüme sahip graflar için, bellek kullanımını yönetilebilir tutmak amacıyla mini toplu komşu örneklemesi (GraphSAGE'deki gibi) veya graf bölümleme yöntemleri gereklidir.

İlgili yöntemler

Kaynaklar

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

    DOI kaynağını aç
    Kopyalandı.
  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 kaynağını aç
    Kopyalandı.
  3. Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.

    DOI kaynağını aç
    Kopyalandı.