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

Ağ Gömme — Node2Vec, DeepWalk, LINE

Yıl
2014 (DeepWalk); 2016 (Node2Vec)
Tür
Representation learning / unsupervised network method

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

Yazı boyutu

Ne işe yarar?

Ağ gömme, bir grafiğin her düğümünü, ağın yapısal özelliklerini korurken yoğun, düşük boyutlu bir vektöre eşleyen bir temsil öğrenme yöntemleri ailesidir.

Bu yaklaşım, sosyal ağ verileri için Perozzi, Al-Rfou ve Skiena tarafından Word2Vec skip-gram modelini grafikler üzerindeki rastgele yürüyüşlere uyarlayan DeepWalk (2014) ile resmileştirilmiş ve Grover ve Leskovec tarafından, genişlik öncelikli ve derinlik öncelikli keşfi dengeleyen yanlı bir rastgele yürüyüş sunan Node2Vec (2016) ile genişletilmiştir. Bu gömmeler, ilişkisel verileri, standart makine öğrenimi sınıflandırıcıları ve kümeleme algoritmalarının doğrudan kullanabileceği özellik vektörlerine dönüştürür.

Yöntemin mantığı

Bir grafik düğümlerden ve kenarlardan oluşur, ancak çoğu makine öğrenimi algoritması bir sayı tablosu bekler. Ağ gömme, çeviri sorununu çözer. Tıpkı Word2Vec'in cümlelerde hangi kelimelerin birbirine yakın göründüğüne bakarak kelime anlamlarını öğrenmesi gibi, DeepWalk de grafikteki rastgele yürüyüşlerde hangi düğümlerin birbirine yakın göründüğüne bakarak düğüm anlamlarını öğrenir. Sonuç, bir vektör uzayında bir koordinattır — yapısal olarak benzer veya sıkça birlikte ziyaret edilen düğümler birbirine yakın konumlanır. Her düğüm bir vektöre sahip olduğunda, bu vektörleri herhangi bir grafiğe özgü kod yazmadan bir sınıflandırıcıya besleyebilir, k-means ile kümeleyebilir veya UMAP ile görselleştirebilirsiniz.

Tarih

Word2Vec'i grafik yapılı verilere uygulama fikri, Perozzi, Al-Rfou ve Skiena tarafından DeepWalk'ta (KDD 2014) tanıtıldı ve sosyal bir grafikteki rastgele yürüyüşlerin düğüm sınıflandırması için el yapımı özellikleri değiştirebileceğini gösterdi. Grover ve Leskovec bunu Node2Vec'te (KDD 2016) p ve q ile parametrelendirilmiş ikinci dereceden yanlı bir rastgele yürüyüş sunarak genişletti ve homofili tabanlı ve yapısal denklik tabanlı komşuluk keşfi arasındaki denge üzerinde açık kontrol sağladı. Aynı dönemde Tang ve diğerleri, rastgele yürüyüşler yerine birinci ve ikinci dereceden yakınlık hedeflerini doğrudan optimize ederek gömmeleri öğrenen LINE'ı (WWW 2015) önerdi, bu da onu çok büyük grafikler için uygun hale getirdi. Bu üç yöntem birlikte ağ temsil öğrenimi alanını kurdu ve sonraki grafik sinir ağı mimarilerine ilham verdi.

Ne zaman kullanılır?

Ağ gömme, en az 50 düğümlü bir grafiğiniz olduğunda ve düğüm sınıflandırması, bağlantı tahmini veya düğüm kümeleme gibi sonraki görevler için sürekli vektör özelliklerine ihtiyacınız olduğunda uygundur. Yöntem hem ağırlıksız hem de ağırlıklı grafikleri destekler ve yönlü veya yönsüz yapıları işler. Basit, tekdüze bir rastgele yürüyüş taban çizgisi yeterli olduğunda DeepWalk'ı seçin. Homofili ve yapısal denklik arasındaki dengeyi p ve q parametreleri aracılığıyla ayarlamak istediğinizde Node2Vec'i seçin. Çıkarım zamanında yeni, daha önce görülmemiş düğümleri yeniden eğitim olmadan gömmeniz gerekiyorsa, GraphSAGE gibi indüktif bir yöntemi tercih edin; standart biçimindeki ağ gömme transdüktiftir. Yöntem, normal dağılmış düğüm nitelikleri gerektirmez.

Sınırlar ve dikkat edilmesi gerekenler

  • Transdüktif: model, eğitim sırasında mevcut olmayan düğümleri tam yeniden eğitim olmadan gömemez.
  • Hiperparametre duyarlılığı: gömme boyutu, yürüyüş uzunluğu, yürüyüş sayısı, pencere boyutu, p ve q'nun tümü gömme kalitesini etkiler ve ayar gerektirir.
  • Rastgele yürüyüşler, uzatma olmadan daha yüksek dereceli grafik yapısını (örneğin, hiperkenarlar veya çok ilişkili kenarlar) yakalamaz.
  • Yürüyüş kümesinin güvenilir istatistikler öğrenmek için çok seyrek olduğu çok küçük grafiklerde (50'den az düğüm) performans düşer.

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

Güçlü yönleri

  • İlişkisel grafik verilerini, herhangi bir standart makine öğrenimi işlem hattıyla uyumlu sabit uzunluklu vektörlere dönüştürür.
  • Node2Vec'in p ve q parametreleri, analistin topluluk duyarlı ve rol duyarlı gömmeler arasındaki dengeyi ayarlamasına olanak tanır.
  • Kenar ağırlıkları, ek modelleme adımları olmadan ilişki gücünü yakalayarak yürüyüş olasılıklarına dahil edilebilir.
  • Verimli rastgele yürüyüş örneklemesi ve skip-gram eğitim prosedürü aracılığıyla büyük grafiklere ölçeklenir.

Uygulama alanları

  • Atıf ağlarında, sosyal platformlarda veya biyolojik etkileşim grafiklerinde düğüm sınıflandırması.
  • Bağlantı tahmini — düğüm gömme benzerliğini karşılaştırarak eksik veya gelecekteki kenarları belirleme.
  • Düğüm vektörlerini k-means veya hiyerarşik yöntemlerle kümeleyerek topluluk tespiti.
  • Anomali tespiti — vektör uzayında aykırı olan düğümler, alışılmadık yapısal rolleri temsil edebilir.
  • Kullanıcıların ve öğelerin iki parçalı veya çok katmanlı bir etkileşim grafiğindeki düğümler olduğu öneri sistemleri.

Nasıl çalışır?

Nasıl çalışır?

1

Süreç, düğümlerin varlıkları ve kenarların ilişkileri temsil ettiği bir G grafiği ile başlar. Kenarlar yönlü veya yönsüz olabilir ve daha sonra geçiş olasılığını etkileyecek ağırlıklar taşıyabilir. Kenar ağırlıkları mevcutsa, yürüyüş olasılıklarına dahil edilir; yoksa tüm kenarlar eşit ağırlık alır. Bu aşamada analist ayrıca algoritma varyantını seçer — tekdüze rastgele yürüyüşler için DeepWalk, p (geri dönüş) ve q (iç-dış) parametreleri tarafından kontrol edilen yanlı yürüyüşler için Node2Vec veya birinci ve ikinci dereceden komşuluk yakınlığının ayrı ayrı öğrenilmesi gerektiğinde LINE. Node2Vec parametre rejimleri arasındaki seçim, beklenen ağ özelliğine göre yönlendirilir: homofili (benzer düğümler bağlanır, bu nedenle genişlik öncelikli keşif tercih edilir, q < 1) veya yapısal denklik (benzer rollere sahip düğümler birbirinden uzakta olabilir, bu nedenle derinlik öncelikli keşif tercih edilir, p < 1).

2

Her düğümden başlayarak, algoritma sabit uzunlukta (genellikle 30 adım) bir dizi rastgele yürüyüşü simüle eder ve bunları birçok kez (genellikle düğüm başına 200 yürüyüş) tekrarlar. Her yürüyüş, kelime cümlelerine benzer bir düğüm tanımlayıcıları dizisi üretir. DeepWalk'ta bir sonraki düğüm komşular arasından tekdüze olarak seçilir. Node2Vec'te bir sonraki düğüm p ve q tarafından yanlı hale getirilmiş geçiş olasılıklarına göre seçilir: önceki düğüme dönmek 1/p ile cezalandırılır, aynı mesafede kalmak 1 olarak tutulur ve daha uzağa gitmek 1/q ile kontrol edilir. Tüm yürüyüşlerin toplanması, grafiğin topolojisini kodlayan bir düğüm dizileri kümesi oluşturur.

3

Düğüm dizileri kümesi bir skip-gram modeline (Word2Vec ile aynı mimari) beslenir. Bir yürüyüşteki her düğüm için, model bir pencere içindeki (genellikle 10 adım) çevreleyen bağlam düğümlerini tahmin eder. Stokastik gradyan inişi aracılığıyla model, yürüyüşlerde birlikte ortaya çıkan düğümlerin benzer vektörlere sahip olması için her düğüm için sabit boyutlu — genellikle 64 veya 128 — yoğun bir vektör temsili öğrenir. Boyut bir hiperparametredir: daha büyük boyutlar daha fazla yapıyı yakalar ancak hesaplamayı artırır ve küçük grafiklerde aşırı uyum riskini artırır.

4

Eğitildikten sonra, model düğüm başına bir gömme vektörü sağlar. Bu vektörler düğüm sınıflandırması (bunları bir lojistik regresyon veya sinirsel sınıflandırıcıya besleme), bağlantı tahmini (aday düğüm çiftlerinin vektörlerini karşılaştırma) veya topluluk tespiti (vektörleri kümeleme) için özellik olarak kullanılır. Gömme vektörleri transdüktiftir: eğitim sırasında görülen düğümler için sabittirler. Eğitimden sonra yeni düğümlerin gömülmesi gerekiyorsa, standart bir Node2Vec veya DeepWalk modeli görülmeyen düğümlere yeniden eğitim olmadan genelleşemediği için bunun yerine GraphSAGE gibi bir indüktif yöntem kullanılmalıdır.

Sık yapılan hatalar

  • Eğitim grafiğinde olmayan yeni düğümlere bir Node2Vec modeli uygulamak — modelin onlar için bir vektörü olmayacaktır; transdüktif gömme kabul edilebilir olmadığında indüktif bir yöntem (örneğin, GraphSAGE) kullanın.
  • Ağın bir homofili veya yapısal denklik modelini takip edip etmediğini incelemeden varsayılan p=1, q=1 (DeepWalk'a eşdeğer) kullanmak — p ve q'yu beklenen modele göre ayarlamak, sonraki görev performansını önemli ölçüde artırabilir.
  • Gömme boyutunu sabit bir sabit olarak ele almak: küçük grafiklerde 64 veya 128 boyutu aşırı uyuma neden olabilir; daha düşük bir değerle başlayın ve sonraki görevde doğrulayın.
  • Minimum örnek gereksinimini göz ardı etmek: 50'den az düğüme sahip grafikler, güvenilir gömmeleri eğitmek için çok seyrek yürüyüş kümeleri üretir.

Sık sorulan sorular

DeepWalk, Node2Vec ve LINE arasındaki fark nedir?

DeepWalk tekdüze rastgele yürüyüşler ve Word2Vec skip-gram modelini kullanır — en basit taban çizgisidir. Node2Vec, p ve q tarafından kontrol edilen yanlı rastgele yürüyüşler ekler, bu da analistin yürüyüşün genişlik öncelikli arama (homofili) gibi mi yoksa derinlik öncelikli arama (yapısal denklik) gibi mi keşfedeceğini ayarlamasına olanak tanır. LINE hiç rastgele yürüyüş kullanmaz; birinci ve ikinci dereceden yakınlık hedeflerini doğrudan kenar listesi üzerinde optimize eder, bu da çok büyük grafiklere daha ölçeklenebilirdir ancak yürüyüş tabanlı komşuluk sinyalini feda eder.

Node2Vec'te p ve q parametrelerini nasıl seçerim?

p, önceki düğüme dönme olasılığını kontrol eder (düşük p = daha az geri izleme) ve q, keşif yarıçapını kontrol eder (q < 1 dışa doğru keşfi destekler, q > 1 yürüyüşü kaynağa yakın tutar). Aynı topluluktaki düğümlerin benzer olmasını bekliyorsanız (homofili), yürüyüşün dışa doğru dolaşmasına izin vermek için q < 1 ayarlayın. Aynı yapısal role sahip düğümlerin uzakta olsalar bile benzer olmasını bekliyorsanız, derinlik öncelikli keşfi teşvik etmek için p < 1 ayarlayın. Her iki rejimi de sonraki görevde doğrulayın.

Tüm modeli yeniden eğitmeden eğitimden sonra yeni düğümleri gömebilir miyim?

Standart Node2Vec ve DeepWalk transdüktiftir: gömme matrisi yalnızca eğitim sırasında görülen düğümleri kapsar. Yeni, daha önce görülmemiş düğümlere indüktif genelleme için, çıkarım zamanında herhangi bir düğüme uygulanabilen düğüm komşulukları üzerinde bir toplama işlevi öğrenen GraphSAGE gibi indüktif bir grafik sinir ağı yöntemi kullanın.

Gömme için kaç boyut kullanmalıyım?

En yaygın seçimler 64 ve 128'dir ve bunlar orta ila büyük grafikler için iyi çalışır. Küçük grafikler (50-200 düğüm) için aşırı uyumu önlemek amacıyla daha düşük bir boyutla (16 veya 32) başlayın ve gömme kalitesini yalnızca yeniden yapılandırma hatası yerine sonraki görev performansını (örneğin, düğüm sınıflandırma doğruluğu) ölçerek değerlendirin.

İlgili yöntemler

Kaynaklar

  1. 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 kaynağını aç
    Kopyalandı.
  2. 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 kaynağını aç
    Kopyalandı.