Grafik sinir ağı GNN'nin temellerinde ustalaşın, sadece bu makaleyi okuyun
Xin Zhiyuan Rehberi Grafik Sinir Ağları (GNN), çeşitli alanlarda giderek daha popüler hale geliyor.Bu makale, grafik sinir ağlarının temel bilgilerini ve iki daha gelişmiş algoritmayı tanıtıyor: DeepWalk ve GraphSage.
Son zamanlarda, grafik sinir ağları (GNN), sosyal ağlar, bilgi grafikleri, öneri sistemleri ve hatta yaşam bilimleri dahil olmak üzere çeşitli alanlarda giderek daha popüler hale geldi.
GNN, grafikteki düğümler arasındaki bağımlılıkları modelleme konusunda güçlü bir yeteneğe sahiptir ve bu da grafik analizi ile ilgili araştırma alanında atılımlar yapar. Bu makale, grafik sinir ağlarının temel bilgilerini ve iki daha gelişmiş algoritmayı tanıtmayı amaçlamaktadır: DeepWalk ile GraphSage .
Grafik
GNN'yi tartışmadan önce, önce ne olduğunu anlayalım Grafik . Bilgisayar biliminde grafik, iki bileşenden oluşan bir veri yapısıdır: Tepe noktaları (köşeler) ile Kenarlar . Bir G grafiği, V köşeleri kümesi ve içerdiği E kenarları ile tanımlanabilir.
Yan olabilir Yönetmen veya Yönsüz Köşeler arasında yön bağımlılığı olup olmadığına bağlıdır.
Tepe noktaları genellikle Düğümler . Bu makalede, bu iki terim birbirinin yerine kullanılabilir.
Grafik sinir ağı
Grafik sinir ağı bir Doğrudan grafik yapısı üzerinde çalıştırın Sinir ağı. Tipik bir GNN uygulaması Düğüm sınıflandırması . Esasen, grafikteki her bir düğüm bir etiket ile ilişkilendirilmiştir.Amacımız, bir düğümün etiketini kesin gerçek olmadan tahmin etmektir.
Bu bölüm açıklayacak Grafik sinir ağı modeli (Scarselli, F., vd., 2009) Bu makaledeki algoritma, bu GNN'yi öneren ilk makaledir, bu nedenle genellikle Orijinal GNN .
Düğüm sınıflandırma problemi ayarında, her v düğümünün x_v özelliği, bir kesin doğruluk etiketi t_v ile ilişkilendirilir. Kısmen etiketlenmiş bir G grafiği verildiğinde, amaç bu etiketli düğümleri etiketlenmemiş düğümlerin etiketlerini tahmin etmek için kullanmaktır. Her bir düğümü, mahalle bilgilerini içeren d boyutlu bir h_v vektörüyle temsil etmeyi öğrenir. hangisi:
X_co, v'ye bağlı kenarın özelliğini temsil ederken, h_ne, v'nin bitişik düğümünün gömülmesini temsil eder ve x_ne, v'nin bitişik düğümünün özelliğini temsil eder. F işlevi, bu girdileri d boyutlu bir uzaya eşleyen bir geçiş işlevidir. H_v'nin benzersiz çözümünü aradığımız için, Banach'ın sabit nokta teoremini uygulayabilir ve yukarıdaki denklemi yinelemeli bir güncelleme işlemi olarak yeniden yazabiliriz.
GNN'nin çıktısı, h_v durumunu ve x_v karakteristiğini g çıktı fonksiyonuna geçirerek hesaplanır.
Burada hem f hem de g, ileri beslemeli, tamamen bağlı sinir ağları olarak yorumlanabilir. L1 kaybı doğrudan şu şekilde ifade edilebilir:
Gradyan inişi ile optimize edilebilir.
ancak, Orijinal GNN'nin üç ana sınırlaması vardır :
- "Sabit nokta" varsayımı gevşetilirse, daha kararlı temsilleri öğrenmek için çok katmanlı algılayıcılar kullanılabilir ve yinelemeli güncelleme süreci ortadan kaldırılabilir. Bunun nedeni, orijinal makalede, farklı yinelemelerin transfer fonksiyonu f'nin aynı parametrelerini kullanması ve farklı MLP katmanlarındaki farklı parametrelerin hiyerarşik özellik çıkarımına izin vermesidir.
- Kenar bilgilerini işleyemez (örneğin, bilgi grafiğindeki farklı kenarlar, düğümler arasındaki farklı ilişkileri temsil edebilir)
- Sabit noktalar, düğüm dağılımının çeşitliliğini engeller ve düğümleri temsil etmeyi öğrenmek için uygun değildir.
Yukarıdaki problemleri çözmek için araştırmacılar, GNN'nin birkaç çeşidini önerdiler. Ancak, bu makalenin odak noktası bunlar değildir.
DeepWalk: Düğüm yerleştirme için ilk denetimsiz öğrenme algoritması
DeepWalk öneren ilk kişidir Denetimsiz yol Düğüm yerleştirme algoritmasını öğrenin.
Eğitim sürecindeki kelime dağarcığına çok benzer. Motivasyon, aşağıdaki şekilde gösterildiği gibi, grafikteki düğümlerin dağılımının ve korpustaki kelimelerin bir güç yasasını izlemesidir:
Algoritma iki adımdan oluşur:
Rasgele yürüyüşlerin her zaman adımında, bir sonraki düğüm, önceki düğümün komşularından eşit olarak örneklenir. Daha sonra her bir dizi, 2 | w | + 1 uzunluğunda bir alt diziye kesilir, burada w, atlama-gram cinsinden pencere boyutunu temsil eder.
Bu makale, çok sayıda düğüm nedeniyle yüksek maliyetli softmax hesaplaması sorununu çözmek için hiyerarşik softmax kullanır. Her bir çıktı elemanının softmax değerini hesaplamak için, k elemanının tüm e ^ xk değerlerini hesaplamalıyız.
Bu nedenle, orijinal softmax'ın hesaplama zamanı O (| V |) 'dir, burada V, grafikteki köşe kümelerini temsil eder.
Hiyerarşik softmax kullanımı İkili ağaç Bu sorunu çözmek için. Bu ikili ağaçta, tüm yapraklar (aşağıdaki şekilde v1, v2, ... v8) grafikteki köşeleri temsil eder. Her dahili düğümde, hangi yolun seçileceğine karar vermek için bir ikili sınıflandırıcı vardır. Belirli bir v_k tepe noktasının olasılığını hesaplamak için, kök düğümden v_k yaprak düğümüne kadar her alt yolun olasılığını hesaplayın. Her bir düğümün alt düğümlerinin olasılıklarının toplamı 1 olduğundan, tüm köşelerin olasılıklarının toplamının 1 olması özelliği hiyerarşik softmax'ta değişmeden kalır. İkili ağacın en uzun yolu O (log (n)) olduğundan, burada n yaprak düğüm sayısını temsil eder, bir elemanın hesaplama süresi artık O (log | V |) 'ye indirgenmiştir.
DeepWalk GNN'yi eğittikten sonra, model aşağıdaki şekilde gösterildiği gibi her düğümün iyi bir temsilini öğrendi. Farklı renkler, girdi haritasındaki farklı etiketleri gösterir. Çıktı grafiğinde (2 boyutlu gömme), aynı etikete sahip düğümlerin birlikte kümelendiğini, farklı etiketlere sahip çoğu düğümün ise doğru şekilde ayrıldığını görebiliriz.
Ancak, DeepWalk ile ilgili temel sorun Genelleme yeteneği eksikliği . Yeni bir düğüm göründüğünde, modeli bu düğümü temsil edecek şekilde yeniden eğitmelidir. Bu nedenle, bu GNN, grafikte sürekli değişen düğümlere sahip dinamik grafikler için uygun değildir.
GraphSage: Her düğümün yerleştirilmesini öğrenin
GraphSage, yukarıdaki sorunlara bir çözüm sağlar ve her düğümün tümevarımlı bir şekilde yerleştirilmesini öğrenir.
Özellikle, GraphSage'in her düğümü, komşularının toplanmasıyla temsil edilir (toplama) . Bu nedenle, eğitim sürecinde görülmeyen yeni bir düğüm grafikte görünse bile, yine de komşu düğümler tarafından düzgün bir şekilde temsil edilebilir.
İşte GraphSage algoritması:
Dış döngü, güncelleme yinelemelerinin sayısını temsil eder ve h ^ k_v, güncelleme yinelemesinde k düğüm v'nin gizli vektörünü temsil eder. Her güncelleme yinelemesinde, h ^ k_v'nin güncellemesi bir toplama işlevine, önceki yinelemedeki v ve v'nin komşuluğunun gizli vektörüne ve ağırlık matrisi W ^ k'ye dayanır.
Makalede üç toplama işlevi önerilmektedir:
1. Ortalama toplayıcı:
ortalama toplayıcı, bir düğümün ve tüm komşularının potansiyel vektörlerinin ortalamasını alır.
Orijinal denklem ile karşılaştırıldığında, yukarıdaki sözde kodun 5. satırındaki birleştirme işlemini siler. Bu tür bir işlem, bir tür "atlama bağlantısı" olarak kabul edilebilir Makalenin ilerleyen kısımlarında, bunun modelin performansını büyük ölçüde artırabileceği kanıtlanmıştır.
2. LSTM toplayıcı:
Grafikteki düğümler herhangi bir sıraya sahip olmadığından bu düğümleri düzenleyerek sırayı rastgele atarlar.
3. Havuzlama toplayıcı:
Bu operatör, bitişik kümeler üzerinde eleman bazında bir havuzlama işlevi gerçekleştirir. Aşağıda bir maksimum havuzlama örneği verilmiştir:
Kağıt, varsayılan toplama işlevi olarak maksimum havuzlamayı kullanır.
Kayıp işlevi aşağıdaki şekilde tanımlanır:
Bunlar arasında, u ve v sabit uzunlukta rastgele bir yürüyüşte bir arada bulunur ve v_n, u ile bir arada bulunmayan negatif bir örnektir. Bu kayıp işlevi, projeksiyon alanında daha uzaktaki düğümler ayrılırken, benzer gömmelere daha yakın olan düğümleri teşvik eder. Bu şekilde düğüm, komşusu hakkında gittikçe daha fazla bilgi elde edecektir.
GraphSage, yakındaki düğümleri toplayarak görünmez düğümler için temsil edilebilir yerleştirmeler oluşturabilir. Grafik yapısının sürekli değiştiği dinamik grafikler içeren alanlara düğüm yerleştirmenin uygulanmasına izin verir. Örneğin, Pinterest, içerik keşif sisteminin çekirdeği olarak GraphSage'in genişletilmiş bir sürümü olan PinSage'i kullanıyor.
sonuç olarak
Bu makalede, grafik sinir ağları, DeepWalk ve GraphSage'ın temellerini öğrendik. Karmaşık grafik yapısı modellemede GNN'nin gücü gerçekten şaşırtıcı. Etkinliği göz önüne alındığında, yakın gelecekte GNN'nin yapay zekanın geliştirilmesinde önemli bir rol oynayacağına inanıyorum.
Scarselli, Franco ve diğerleri "Grafik sinir ağı modeli."
Perozzi, Bryan, Rami Al-Rfou ve Steven Skiena. "Deepwalk: Sosyal temsillerin çevrimiçi öğrenimi."
Hamilton, Will, Zhitao Ying ve Jure Leskovec. "Büyük grafiklerde endüktif temsil öğrenme."
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
