Alibaba, mimari algoritmanın yorumlanması olan büyük ölçekli grafik sinir ağı platformu AliGraph'ı yayınladı
Giriş
Karmaşık bir model olarak grafikler, çeşitli gerçek dünya uygulamalarında verilerin modellenmesi ve yönetilmesinde yaygın olarak kullanılmaktadır. Tipik örnekler arasında sosyal ağlar, fiziksel sistemler, biyolojik ağlar ve bilgi grafikleri bulunur. Grafik analizi, son on yılda büyük ilgi gören grafik verilerinde saklı potansiyel içgörüleri araştırıyor. Düğüm sınıflandırması, bağlantı tahmini, grafik kümeleme ve öneri sistemleri gibi birçok alanda önemli bir rol oynadılar.
Geleneksel grafik analizi görevleri genellikle yüksek hesaplama ve alan maliyetleriyle karşı karşıya olduğundan, grafik gömme (GE) adı verilen yeni bir paradigma, bu tür sorunları çözmek için etkili bir yöntem sağlar. Özellikle, Grafik Gömme (GE), grafiğin yapısını ve içerik bilgilerini büyük ölçüde korumak için grafik verilerini düşük boyutlu alana dönüştürür. Bundan sonra, oluşturulan yerleştirmeler, aşağı akış makine öğrenimi görevlerine özellikler olarak girilir. Ek olarak, derin öğrenme teknolojisi ile birleştirildiğinde, grafik yerleştirme (GE) ile evrişimli sinir ağı (CNN) birleştirilerek bir grafik sinir ağı (GNN) önerilmektedir. CNN'de öğrenme yeteneğini geliştirmek için paylaşılan ağırlıklar ve çok katmanlı yapı kullanılır. Grafik, hesaplama maliyetlerini azaltmak için ağırlıkları paylaşan en tipik kısmi bağlantı yapısıdır.Çok katmanlı yapı, hiyerarşik modu işlemenin anahtarıdır ve çeşitli değişen boyutların özelliklerini yakalayabilir. GNN, grafikte CNN'nin bir promosyonudur. Bu nedenle, GNN yalnızca grafik yerleştirme (GE) esnekliğine sahip olmakla kalmaz, aynı zamanda etkinlik ve sağlamlık açısından üstünlüğünü de gösterir.
GNN'nin karşılaştığı zorluklar
Şu anda, çok sayıda makale, grafik gömme (GE) ve GNN algoritmalarının geliştirilmesine büyük miktarda enerji katmıştır.Bu çalışmalar esas olarak yardımcı bilgi içermeyen veya çok az yardımcı bilgi içeren basit grafiklere odaklanmıştır. Bununla birlikte, büyük verilerin ve karmaşık sistemlerin yükselişi, grafik verilerinde yeni içgörüler ortaya çıkardı. Bu bir fikir birliğidir.Gerçek iş senaryolarıyla ilgili çoğu grafik verisi dört özellik sergiler, yani Büyük ölçekli, heterojen, atfedilen ve dinamik . Örneğin, mevcut e-ticaret grafiği genellikle milyarlarca köşe ve kenar içerir, bu köşeler ve kenarlar çeşitli türlere ve zengin özelliklere sahiptir ve zaman içinde hızla gelişecektir. Bu özellikler, aşağıda gösterildiği gibi grafik verilerini gömmek ve karakterize etmek için büyük zorluklar getirir:
Kağıt katkısı
Yukarıdaki zorlukların üstesinden gelmek için, verimli ve etkili GNN yöntemlerinin tasarlanması için çok sayıda araştırma çalışması yapılmıştır. Tablo 1'de, farklı çalışmaların odağına ve dahili olarak geliştirdiğimiz modellere (sarı ile gölgelendirilmiş) dayalı olarak bir dizi popüler GE ve GNN modelini sınıflandırdık.
Şekilde gösterildiği gibi, mevcut yöntemlerin çoğu aynı anda bir veya iki özelliğe odaklanır. Ancak, gerçek dünyadaki iş verileri genellikle daha fazla zorlukla karşı karşıyadır. Bu durumu hafifletmek için bu makalede kapsamlı ve sistematik bir GNN çözümü öneriyoruz. Çeşitli GNN yöntemlerini ve uygulamalarını daha iyi desteklemek için daha pratik sorunları çözmek için bir dizi karşılık gelen sistem ve algoritma sağlayan AliGraph adlı bir grafik sinir ağı platformu tasarladık ve uyguladık.
AliGraph'ın ana katkıları şunları içerir:
sistemi
Aligraph'ın temel bileşenlerinde, GNN algoritmalarını ve uygulamalarını destekleyen bir sistem oluşturduk. Sistem yapısı genel GNN yönteminden soyutlanmıştır ve bir depolama katmanı, bir örnekleme katmanı ve bir işlem katmanından oluşur. Özellikle, depolama katmanı, gelişmiş işlemlerin ve algoritmaların hızlı veri erişimini karşılamak için büyük ölçekli ham verileri depolamak için yapılandırılmış ve ilişkilendirilmiş özel depolama, grafik bölümleme ve bazı önemli köşelerin önbelleğe alınması gibi üç yeni teknoloji uygular. İddia.
Örnekleme katmanı, GNN yöntemindeki temel örnekleme işlemlerini optimize eder. Örnekleme yöntemlerini TRAVERSE, NEIGHBORHOOD ve NEGATIVE olmak üzere üç kategoriye ayırıyoruz ve dağıtılmış bir ortamda örnekleme işlemleri için kilitsiz bir yöntem öneriyoruz.
İşlem katmanı, GNN algoritmasında yaygın olarak kullanılan iki uygulama işleminin, yani toplama (AGGREGATE) ve kombinasyon (COMBINE) optimize edilmiş uygulamalarını sağlar. Hesaplama sürecini hızlandırmak için ara sonuçları depolamak için bir önbelleğe alma stratejisi uyguluyoruz. Bu bileşenler, tüm sistemi etkili ve ölçeklenebilir hale getirmek için birlikte tasarlanmış ve birlikte optimize edilmiştir.
algoritma
Sistem, GNN algoritmalarını tasarlamak için esnek bir arayüz sağlar. Araştırma sonuçlarımız, mevcut tüm GNN yöntemlerinin sistemimize kolayca uygulanabileceğini göstermektedir. Ek olarak, gerçek ihtiyaçlar için dahili olarak birkaç yeni GNN algoritması geliştirdik. Tablo 1'de gösterildiği gibi, dahili olarak geliştirdiğimiz yöntemlerimiz sarı ile gölgelenmiştir.Her yöntem pratik problemlerle başa çıkmada daha esnek ve pratiktir.
AliGraph platformu aslında Alibaba içinde konuşlandırıldı. Deneysel sonuçlar, etkinliğini ve verimliliğini hem sistemden hem de algoritmadan doğrulamaktadır. Şekil 1'de gösterildiği gibi, AliGraph platformunda dahili olarak geliştirdiğimiz GNN modeli, Standartlaştırılmış değerlendirme göstergeleri% 4,12-% 17,19 artırıldı . Veriler, Alibaba'nın e-ticaret platformu Taobao'dan geliyor. Bu alandaki daha fazla gelişmeyi teşvik etmek için bu veri setine (Mayıs 2019'da bekleniyor) katkıda bulunacağız.
Önkoşul bilgisi
Bu bölümde Tablo 2, bu makaledeki yaygın sembolleri ve işaretleri özetlemektedir.
Heterojen grafiği öznitelik
Gerçek dünyadaki ticari verileri tam olarak tanımlamak için, gerçek grafikler genellikle birden çok köşe türü, birden çok kenar türü ve nitelik vb. Gibi zengin içerik bilgileri içerir, bu nedenle heterojen grafiği (AHG) özniteliğini daha ayrıntılı olarak tanımlarız. AHG, V, ve W'nin basit grafikle aynı anlama sahip olduğu bir gruptur (V, , W, TV, TE, AV, AE). T (V): V > F (V) ve T (E): > F (E), köşe tipi ve kenar tipinin eşleme işlevini temsil eder. Heterojenliği sağlamak için, | FV | değerinin 2'den büyük veya 2'ye eşit ve (veya) | FE | 2'den büyük veya eşit olmalıdır. A (v) ve A (E), niteliklerini karakterize etmek için her köşe v'ye ve her kenar e'ye bazı özellik vektörleri atayan iki işlevdir. Köşe v ve kenar e'nin i-inci özellik vektörünü sırasıyla x (v, i) ve w (e, i) olarak gösteriyoruz. Şekil 2'de bir AHG örneği gösterilmektedir. Kullanıcı ve öğe olmak üzere iki tür köşe ve bunları birbirine bağlayan dört tür kenar içerir.
dinamik resim
Gerçek dünyadaki grafikler genellikle zamanla gelişir. Bir zaman aralığı verildiğinde, dinamik grafik G (1), G (2), ..., G (T) grafik serisidir. 1'den büyük veya 1'e eşit ve T'ye eşit veya daha küçük her t için, G (T) basit bir grafik veya bir AHG'dir. Belleği kolaylaştırmak için, nesnenin t zaman damgasındaki ilgili durumunu temsil eden bir üst simge t ekliyoruz. Örneğin, V (t) ve E (t) sırasıyla G (t) grafiğinin köşe kümesini ve kenar kümesini gösterir.
Problem tanımı
Basit bir grafik veya AHG olan bir G girdi grafiği verildiğinde, bir gömme boyutu d N önceden tanımlanır, burada d < < | V |, grafiğin doğasını olabildiğince korurken, gömme problemi G grafiğini d boyutlu bir uzaya dönüştürmektir. GNN, sinir ağlarını grafiklere uygulayan ve gömme sonuçlarını öğrenen özel bir grafik gömme yöntemidir. Bu makalede, esas olarak köşe düzeyinde yerleştirmeye odaklandığımızı unutmayın. Diğer bir deyişle, her köşe v için gömme çıktı sonucu d boyutlu bir vektördür h (v). Bölüm 7'deki gelecekteki çalışmayla ilgili tartışmamızda, kenar gömme, alt grafik yerleştirme ve hatta tüm grafik yerleştirmeyi de ele alacağız.
AliGraph sisteminin ayrıntılı açıklaması
Aligraph platform mimarisi Şekil 3'te gösterilmektedir. Yüksek seviyeli GNN algoritmalarını ve uygulamalarını daha iyi desteklemek için düşük seviyeli bir sistem (açık mavi karelerle işaretlenmiş) tasarladık ve uyguladık. Bu bölüm sistemin ayrıntılarını tanıtacaktır Bölüm 3.1'de, sistemimizin neden bu şekilde tasarlandığını açıklamak için bir GNN genel çerçevesi soyutlayacağız; Bölüm 3.2 ila 3.5, sistemdeki her bir anahtar bileşenin tasarımını ve tasarımını tanıtmaktadır. Uygulama ayrıntıları.
3.1 GNN algoritma çerçevesi
Bu bölümde, GNN algoritmasını genel bir çerçeve olarak soyutlayacağız. Structure2Vec, GCN, FastGCN, AS-GCN ve GraphSAGE gibi bir dizi klasik GNN, çerçevedeki operatörlerin somutlaştırılmasıyla tanımlanabilir. GNN çerçevesinin girdisi, gömme boyutu d N olan bir G grafiğinden, her köşe v V'nin köşe özelliği x (v) ve komşu k'nin (maks) maksimum atlama sayısından oluşur. Her v V köşe noktası için GNN'nin çıktısı bir gömme vektörüdür h (v), sınıflandırma, bağlantı tahmini vb. gibi aşağı akış makine öğrenimi görevlerine gönderilecektir.
Algoritma 1, GNN çerçevesinin bir açıklamasıdır. En başta, köşe v'nin gömme vektörü h (v) (0), girdi öznitelik vektörüne eşit olacak şekilde başlatılır x (v). Daha sonra, her k noktasında, her köşe v, kendi gömme vektörünü güncellemek için komşu köşelerinin gömme vektörünü toplar. Spesifik olarak, v tepe noktasının Nb (v) etki alanı kümesine dayalı olarak tepe noktasının bir S alt kümesini çıkarmak için örnek işlevini kullanıyoruz ve bir h ^ (v vektörü elde etmek için u S tüm köşelerinin yerleştirmelerini toplamak için toplama işlevini kullanıyoruz ) ve h ^ (v) ile h (v) (k-1) Fonksiyonu birleştirerek gömme vektörü oluşturun h (v) (k). Tüm köşeleri işledikten sonra, gömme vektörü normalleştirilir. Son olarak, k (max) sıçramasından sonra,
h (v) (k (maks)) köşe v'nin gömme sonucu olarak h (v) İade.
Yukarıda açıklanan GNN çerçevesine dayanarak, önceki bölümde Şekil 3'te gösterildiği gibi AliGraph platformunun sistem mimarisini oluşturduk. Platform, üçü algoritma katmanını ve uygulama katmanını desteklemek için sistemi oluşturan beş katmandan oluşur. Sistemin içinde, depolama katmanı, gelişmiş işlemlerin ve algoritmaların hızlı veri erişim gereksinimlerini karşılamak için farklı türlerde ham verileri düzenler ve depolar.
Bu temelde, Algoritma 1 aracılığıyla, üç ana operatörün çeşitli GNN algoritmalarında, yani örnekleme, toplama ve kombinasyonda önemli bir rol oynadığını bulduk. Bunların arasında, örnekleme işlemi, işlenecek bilgi aralığını doğrudan kontrol ettiği için toplama ve birleştirme işlemlerinin temelini oluşturur. Bu nedenle, eğitim örneklerini hızlı ve doğru bir şekilde oluşturmak için örnekleme katmanını depoya erişecek şekilde tasarladık. Bunun da ötesinde, işlem katmanı özellikle toplama ve kompozisyon işlevlerini optimize eder. Sistem temelinde, GNN algoritması, uygulama katmanının gerçek görevleri için hizmetler sağlamak üzere algoritma katmanında oluşturulabilir.
3.2 Saklama
Bu bölümde, ham verilerin nasıl saklanacağını ve düzenleneceğini tartışacağız. Gerçek dünya grafiklerini depolamanın alan maliyeti çok yüksektir. Yaygın e-ticaret grafikleri on milyarlarca düğüm ve on milyarlarca kenar içerebilir ve depolama maliyeti kolayca 10 TB'ı aşabilir. Grafiğin büyük boyutu, özellikle bir kümenin dağıtılmış ortamında, etkili erişim için büyük bir zorluk getiriyor. Gelişmiş bilgi işlem işlemlerini ve algoritmalarını daha iyi desteklemek için, AliGraph'ın depolama katmanına aşağıdaki üç stratejiyi uyguladık.
Grafik bölümü
Aligraph platformu dağıtılmış bir ortamda oluşturulmuştur, bu nedenle tüm grafik bölümlere ayrılır ve farklı çalışma düğümlerinde depolanır. Grafik bölümlemenin amacı, uç noktaları farklı çalışma düğümlerine dağıtılmış olan kesişen kenarların sayısını en aza indirmektir. Bu nedenle literatür çalışmasında bir dizi algoritma önerilmiştir.
Dört yerleşik grafik bölümleme algoritması uyguladık: (1) METIS; (2) köşe kesme ve kenar kesme bölümleme; (3) 2 boyutlu bölümleme; (4) akış bölümleme stratejisi, bu dört algoritma farklı çevre. Kısacası, METIS seyrek grafiklerde uzmanlaşmıştır; köşe kesimi ve kenar kesim bölümleri yoğun grafiklerde daha iyi performans gösterir; çalışan sayısı sabitlendiğinde genellikle 2 boyutlu bölümleme kullanılır; akış bölümleme yöntemleri genellikle sık güncellenen kenarlara uygulanır Haritada. Kullanıcılar ihtiyaçlarına göre en iyi bölümleme stratejisini seçebilir, ayrıca sistemde eklenti olarak diğer grafik bölümleme algoritmalarını da uygulayabilirler.
Algoritma 2'de 1-4 satırları grafik bölümünün arayüzünü verir. Her bir e kenarı için, 4. satırdaki genel ASSIGN işlevi, uç noktasına göre hangi woker düğümünün e içinde olduğunu hesaplayacaktır.
Özellikleri ayrı saklayın
AHG için, bölüm grafiğinin yapısını ve niteliklerini her çalışma düğümünde saklamamız gerekir. Grafiğin yapı bilgisi basit bir şekilde bitişik tabloya kaydedilebilir. Yani, her v köşe noktası için, komşu kümesini Nb (v) saklarız. Bununla birlikte, iki köşenin nitelikleri ve kenarları için, bunların bitişik tabloda saklanması tavsiye edilmez. Bunun iki nedeni var:
Sistemimizde, I (v) ve I (e) dizinlerini oluşturarak sırasıyla köşelerde ve kenarlarda öznitelikleri depoluyoruz. Şekil 4'te gösterildiği gibi, bitişiklik listesinde, her bir u köşesi için, Av (u) özelliğinin indeksini I (v) 'de saklıyoruz. Her kenar (u, v) için, I (e) 'de Ae (u, v) özelliğini de saklarız. N (D) ve N (L) 'nin sırasıyla ortalama komşu sayısı ve ortalama öznitelik uzunluğu olduğunu varsayalım. N (D) köşelerdeki ve kenarlardaki farklı özniteliklerin sayısı olsun. Açıktır ki, ayrı depolama stratejimiz alan maliyetini O (n * ND * NL) 'den O (n * ND + NA * NL)' ye düşürür.
Önemli köşelerin komşularını önbelleğe al
Her çalışma düğümünde, iletişim maliyetlerini azaltmak için önemli köşelerin komşularının yerel olarak önbelleğe alınması için bir yöntem öneriyoruz. Bir köşe v diğer köşeler tarafından sıklıkla ziyaret ediliyorsa, dış komşularını oluştuğu her bölümde saklayabiliriz. Bunu yapmak, v aracılığıyla bitişik köşelere erişen diğer köşelerin ek yükünü büyük ölçüde azaltabilir. Bununla birlikte, v'nin komşularının sayısı fazla ise, v'nin komşularının birden çok kopyasının depolanması da büyük depolama alanı maliyetlerine neden olacaktır. Daha iyi tartmak için, her bir köşenin önemini değerlendirmek ve bir köşenin önbelleğe almaya değer olup olmadığını belirlemek için bir ölçüt tanımlarız.
Diyelim ki Di (v) (k) ve Do (v) (k), sırasıyla tepe v'nin iç ve dış komşularının k-hop sayısını gösterdi. Daha sonra Di (v) (k) ve Do (v) (k), köşe v'nin dış komşularının önbelleğe alınmasının faydasını ve maliyetini ölçebilir. Bu nedenle, köşe v'nin k'inci önemi aşağıdaki gibi tanımlanan Imp (v) (k) olarak ifade edilir:
Algoritma 2'de 5-9 satırları, önemli köşelerin komşularının önbelleğe alınması sürecini gösterir. H'nin komşunun maksimum derinliğini temsil ettiğini varsayalım. Her bir köşe v için, Imp (v) (k) 'nin k' dan büyük veya ona eşit olması şartıyla, dış komşu köşelerini 1'den k-sekme v noktasına kadar önbelleğe alıyoruz. Bunlar arasında k, kullanıcı tarafından belirlenen eşiktir. H'yi küçük bir sayıya (genellikle 2) ayarlamak, bir dizi gerçek GNN algoritmasını desteklemek için yeterlidir. Aslında, k'nin hassas bir parametre olmadığını bulduk. Deneysel değerlendirme yoluyla, k değerini yaklaşık 0,2 olarak ayarlamak, önbellek maliyeti ve faydası arasında en iyi dengeyi sağlayabilir.
İlginç bir şekilde, önbelleğe alınacak köşelerin tüm grafiğin yalnızca küçük bir parçası olduğunu gördük. Di (v) (1) ve Do (v) (1) genellikle gerçek grafiklerdeki güç yasası dağılımına uyar. Diğer bir deyişle, grafikte büyük ölçüde giriş ve çıkışa sahip yalnızca birkaç köşe vardır. Buna dayanarak, aşağıdaki iki teoremi elde ederiz.
Teorem 2, grafikteki yalnızca birkaç köşenin daha yüksek öneme sahip olduğunu gösterir.Bu, grafik geçişinin maliyetini önemli ölçüde azaltmak için yalnızca birkaç önemli köşeyi önbelleğe almamız gerektiği anlamına gelir.
3.3 Örnekleme
GNN algoritmasının, her bir tepe noktasının gömülmesini oluşturmak için komşu bilgilerinin toplanmasına dayandığını hatırlayın. Bununla birlikte, gerçek dünya grafiğinin derece dağılımı genellikle çarpıktır, bu da evrişim işleminin çalıştırılmasını zorlaştırır. Bu sorunu çözmek için, mevcut GNN'ler genellikle aynı boyuttaki komşuların bir alt kümesini örneklemek için çeşitli örnekleme stratejileri kullanır. Önemi nedeniyle, örnekleme stratejisini optimize etmek için AliGraph'ta belirli bir örnekleme katmanını soyutladık.
özet
Resmi olarak, örnekleme işlevi, V (T) köşelerinin bir alt kümesinin girdisini kabul eder ve küçük bir alt küme V (S), | V (S) | < < | V (T) |. Mevcut GNN modellerini araştırarak, üç farklı örnekleyiciyi, yani geçiş, komşuluk ve negatif örnekleme soyutladık.
- çapraz (TRAVERSE): Tüm bölüm grafiğinden bir grup tepe noktası veya kenarı örneklemek için kullanılır.
- Alan (NEIGHBORHOOD): Köşe bağlamı oluşturulacaktır. Köşe bağlamı, tepe noktasını kodlamak için kullanılan bir veya daha fazla sekme komşusu olabilir.
- Negatif örnekleme (NEGATIV): Eğitim sürecinin yakınsamasını hızlandırmak için negatif örnekler oluşturmak için kullanılır.
başarmak
Literatürde, örnekleme yöntemleri GNN algoritmasının etkinliğini ve doğruluğunu artırmada önemli bir rol oynamaktadır. Sistemimizde örnekleyiciler eklenti şeklinde mevcuttur. Bu üç örnekleyici aşağıdaki şekilde uygulanabilir:
- Çapraz örnekleyici için kısmi grafikten veri alırlar.
- Etki alanı örnekleyicileri için, yerel depolamadan bir atlama (bir atlama) komşuları alabilir veya yerel önbellekten çok atlama (multi-hop) komşuları alabilirler. Önbellek tepe noktasının komşusu yoksa, uzak bir grafik sunucusundan çağrılması gerekir. Bir köşe kümesinin bağlamını elde ederken, önce köşeleri alt yığınlara ayırırız ve karşılık gelen grafik sunucusundan döndürülen sonuçları elde ettikten sonra, her bir alt partinin bağlamları birbirine eklenir.
- Negatif örnekleyiciler genellikle bu harita sunucusundan örnekler oluşturur. Bazı özel durumlar için, diğer grafik sunucularından negatif örnekleme gerekebilir. Negatif örnekleme algoritmik olarak esnektir ve tüm grafik sunucularını toplu olarak çağırmamıza gerek yoktur.
Kısaca, Şekil 5'te gösterildiği gibi tipik bir örnekleme aşaması uygulanabilir.
Dinamik ağırlıklarla birkaç etkili örnekleme stratejisi benimseyerek eğitimi hızlandırabiliriz. Güncelleme işlemini, örnekleyicinin geri hesaplamasında, tıpkı geri yayılma işlemi gibi gerçekleştiriyoruz. Dolayısıyla, güncellememiz gerektiğinde, yapmamız gereken şey örnekleyici için bir gradyan işlevi kaydetmektir. Güncelleme modunun eşzamanlı mı yoksa eşzamansız mı olacağı eğitim algoritması tarafından belirlenir.
Şimdiye kadar, bellekteki grafik depolamada hem okuma hem de güncellemeler gerçekleştirilecek ve bu da performans düşüşüne neden olabilir. Komşuların ihtiyaçlarına göre grafik, kaynak köşelerine bölünmüştür. Bu temelde, grafik sunucusundaki köşeleri gruplandırıyoruz. Her grup bir istek akışı paketiyle ilişkilendirilir ve işlemler (okuma ve güncelleme dahil) gruptaki köşelerle ilgilidir. Kova, kilitsiz bir kuyruktur Şekil 6'da gösterildiği gibi, her bir kepçeyi bir CPU çekirdeğine bağlarız Daha sonra, kovadaki her işlem kilitlenmeden sırayla işlenir ve bu da sistemin verimliliğini daha da artırır.
3.4 Operatör
özet
Örneklemeden sonra çıktı verileri hizalanır ve işlenmesi çok daha kolaydır. Örnekleyicide, onları kullanmak için bazı GNN benzeri operatörlere ihtiyacımız var. Sistemimizde, toplama ve kompozisyon olmak üzere iki tür işleç soyutlarız. Rolleri aşağıdaki gibidir:
- polimerizasyon: Birleşik bir sonuç oluşturmak için her bir tepe noktasının komşu bilgilerini toplayın. Örneğin, Algoritma 1'deki toplama algoritması, bir dizi vektörü h (u) ile tek bir h ^ (v) vektörüne eşler; burada u, v'nin örnekleme komşu düğümüne aittir. h ^ (v), h (k) (v) 'yi daha fazla oluşturmak için bir ara sonuçtur. Toplama işlevi, çevredeki komşulardan bilgi toplar ve bir evrişim işlemi olarak kullanılabilir. Farklı GNN'lerde eleman ortalaması, maksimum havuzlama sinir ağı ve LSTM gibi çeşitli toplama yöntemleri uygulanır.
- kombinasyon: Köşeyi tanımlamak için köşenin komşularının nasıl kullanılacağından sorumludur. Algoritma 1'de, kombinasyon işlevi iki vektör h (v) (k-1) ve h ^ (v) 'yi bir h (v) (k) vektörüne eşler. Kombinasyon işlevi, önceki atlama ve alanın bilgilerini birleşik bir alana entegre edebilir. Genel olarak mevcut GNN yöntemlerinde, h (v) (k-1) ve h ^ (u) Toplam daha sonra sinir ağına girilir.
başarmak
Örnekleyici ve GNN benzeri operatörler yalnızca ileri işlemleri gerçekleştirmekle kalmaz, aynı zamanda parametreleri güncellemek ve tüm modeli uçtan uca bir eğitim ağı yapmak için geriye dönük işlemler de gerçekleştirebilir. Grafik verilerinin özellikleri göz önüne alındığında, daha iyi performans elde etmek için bir çok optimizasyon düşünülebilir. Tipik bir operatör, derin ağın eğitimine katılmak için ileri ve geri işlemlerden oluşur. Kullanıcılar, operatörlere dayalı olarak hızlı bir şekilde GNN algoritmaları oluşturabilir.
Bu iki operatörün çalışmasını daha da hızlandırmak için, ara sonuç vektörüne bir strateji uyguluyoruz h (v) (k) Önbellek. Eğitim sürecindeki her bir mini partide, tüm köşeler için örnek komşular kümesini paylaşabiliriz. Benzer şekilde, aynı mini partide, tüm k için > = 1 ve k < = k (max), vektörleri de paylaşabiliriz h (v) (k). Bunun için k (max) yapacağız h ^ v (1), h ^ v (2), ... h ^ V (kmax) vektörü, mini serideki tüm köşelerin en son vektörü olarak depolanır. Toplama fonksiyonunda vektörü kullanıyoruz h ^ v (1), h ^ v (2), ... h ^ v (kmax) almak h ^ (v). Ardından, bir kombinasyon fonksiyonu uygulayarak hesaplıyoruz h ^ (v) ve h (v) (k-1) almak h ^ (v) (k). Son olarak, depolanan vektör h ^ (k) geçer h ^ (v) (k) Güncelleme. Bu strateji sayesinde, operatörlerin hesaplama maliyeti büyük ölçüde azaltılabilir.
Metodoloji
Sistem bazında algoritmanın tasarımını tartışalım. Araştırma sonuçlarımız, mevcut GNN'lerin AliGraph'ta oluşturulmasının çok kolay olduğunu gösteriyor. Ek olarak, Bölüm 1'de özetlenen gerçek dünya grafik verilerinin gömülmesinin dört yeni zorluğunu çözmek için bir dizi yeni GNN algoritması da önerdik. AliGraph platformunun algoritma katmanındaki eklentiler şeklinde kullanıcılar için mevcuttur.
4.1 GNN en iyi uygulamaları
AliGraph platformu genel GNN algoritmasına dayalı olarak soyutlandığından, mevcut GNN bu platformda kolayca uygulanabilir. Özellikle, Tablo 1'de listelenen GNN, Algoritma 1'deki çerçeveye göre AliGraph'ta oluşturulabilir. Burada kısa bir giriş için örnek olarak GraphSAGE alıyoruz Diğer GNN'ler de benzer şekilde uygulanabilir. GraphSAGE için, her bir tepe noktasının bitişik kümesinden bir alt küme çıkarmak için basit düğüm düğüm örnekleme uygular. Açıktır ki, bu örnekleme stratejisi, örnekleme operatörümüz tarafından kolayca uygulanabilir. Ardından, Algoritma 1'de toplama ve kompozisyon işlevlerini somutlaştırmamız gerekir. GraphSAGE, 4. sıradaki toplama fonksiyonunda ağırlıklı eleman ortalamasını uygulayabilir. Ek olarak, makspooling sinir ağı ve LSTM sinir ağı gibi diğer daha karmaşık işlevler de kullanılabilir. GCN, FastGCN ve AS-GCN gibi diğer GNN yöntemlerinde, örnekleme, toplama ve kombinasyonda farklı stratejileri ikame edebiliriz.
Alibaba tarafından dahili olarak geliştirilen 4.2 GNN'ler
Dahili olarak geliştirilen GNN'miz, örnekleme (AHEP), bileşik kenarlar (GATNE), çok modlu (Karışım GNN), hiyerarşik (Hiyerarşik GNN), dinamik (Gelişen GNN) ve çok kaynaklı bilgiler (Bayesian GNN) gibi farklı yönlere odaklanır. .
AHEP algoritması
Bu algoritma, heterojen ağlarda (HEP) geleneksel gömülü yayılma (EP) algoritmalarının ağır hesaplama ve depolama maliyetlerini azaltmak için tasarlanmıştır. HEP, AHG'de küçük değişiklikler yaparak GNN'nin genel çerçevesini takip etmektedir.
HEP'de tüm köşe yerleştirmeleri yinelemeli bir şekilde oluşturulur. K'inci atlamada, her köşe v ve her düğüm tipi c için, c'deki v'nin tüm komşuları u, bir h ^ (v, c) yerleştirmeyi yeniden yapılandırmak için gömülmesini h (u, c) 'den v' ye yayarlar. . Ardından, v'nin yerleştirmelerini güncellemek için tüm düğüm türlerinde h ^ (v, c) yerleştirmelerini bağlayın. Bununla birlikte, AHEP'te (HEP uyarlamalı örnekleme kullanır), tüm komşuları dikkate almadan yalnızca önemli komşuları örnekliyoruz.
Yapısal bilgileri ve özellikleri birleştirerek her bir köşenin önemini değerlendirmek için bir metrik tasarladık. Daha sonra, karşılık gelen olasılık dağılımına göre, farklı türlerdeki tüm komşular sırasıyla örneklenir. Örnekleme varyansını en aza indirmek için olasılık dağılımını dikkatlice tasarladık. Belirli bir görevde, AHEP algoritmasını optimize etmek için kayıp işlevi genel olarak şu şekilde tanımlanabilir:
Bunlar arasında, L (SL) toplu işlemede denetimli öğrenme kaybı, L (EP) toplu örnekleme sırasında gömülü yayılma kaybı, () tüm eğitilebilir parametrelerin düzenlenmesi, , iki hiperparametredir . Bölüm 5'deki deneysel sonuçlara göre, AHEP'in çalışma hızı HEP'inkinden çok daha hızlıdır ve aynı zamanda hatırı sayılır bir doğruluk elde etmiştir.
GATNE algoritması
Bu algoritma, heterojen grafikleri işlemek ve köşeler ve kenarlar hakkında bilgi vermek için kullanılır. Yukarıda belirtilen sorunları çözmek için, zengin öznitelik bilgilerini yakalayabilen ve farklı düğüm türlerini, yani genel öznitelik çoklu heterojen ağ gömme veya kısaca GATNE'yi kullanabilen birden çok topolojik yapının yeni bir yöntemini öneriyoruz.
Her bir tepe noktasının genel yerleştirme sonucu üç bölümden oluşur: sırasıyla açıklama yapısı bilgilerine, heterojen bilgilere ve öznitelik bilgilerine karşılık gelen genel gömme, özel gömme ve öznitelik gömme. Her köşe v ve herhangi bir düğüm tipi c için, genel gömme b (v) ve gömme özniteliği f (v) aynı kalır. 1 t ^ t, g (v, t ^) metaya özgü bir gömme olduğunda t, ayarlanabilir bir hiperparametre olsun. Spesifik yerleştirme, tüm g (v, t ^) 'nin birleştirilmesiyle elde edilir. Daha sonra, her c tipi için tüm h (v, c) aşağıdaki gibi gömülür:
Bunlar arasında, © ve ©, belirli gömme ve öznitelik yerleştirmenin önemini yansıtan iki ayarlanabilir parametredir; dikkat mekanizması a © katsayı matrisini hesaplamak için kullanılır; M © ve D eğitilebilir iki değişim matrisidir. Nihai gömme sonucu h (v), tüm h (v, c) 'ye bağlanabilir.
Gömme, rastgele yürüyüşlere benzer yöntemler kullanılarak öğrenilebilir. Spesifik olarak, rastgele bir yürüyüşte c tipi bir köşe v ve bir pencere boyutu p verildiğinde, v (-p), v (-p + 1), ... v, v (1), ... v§ bağlamını göstersin . Negatif log-olasılığını en aza indirmemiz gerekiyor:
Karışım GNN algoritması
Model, çok modlu heterojen grafikleri işlemek için hibrit bir GNN modelidir. Bu modelde, heterojen grafiklerdeki belirsiz sahneye uyum sağlamak için heterojen grafiklerde atlama-gram modelini genişletiyoruz. Geleneksel gram atlama modelinde, olabilirlik fonksiyonunu maksimize ederek parametresiyle gömülü grafiği bulmaya çalışırız:
Bunların arasında, Nb (v) v'nin komşusunu temsil eder ve Pr (u | v) softmax fonksiyonunu temsil eder.Heterojen grafikteki ayarımızda, her bir düğümün ne kadar farkında olduğu. Bunları ayırt etmek için, P'nin bilinen düğüm algısı dağılımı olduğunu varsayalım. Amaç işlevini şu şekilde yeniden yazıyoruz:
Şu anda, negatif örnekleme yöntemiyle birlikte denklemi (6) doğrudan optimize etmek zordur. Ya da, yeni bir alt sınır L (düşük) denklemi (6) türetir ve L'yi (düşük) maksimize etmeye çalışırız. Negatif örnekleme ile alt sınır L'nin (düşük) tahmin edilebileceğini bulduk. Bu nedenle, Deepwalk ve node2vec gibi mevcut çalışmalarda, örnekleme sürecini biraz değiştirerek eğitim süreci kolayca uygulanabilir.
Hiyerarşik GNN algoritması
Mevcut GNN yöntemi esasen düzdür ve grafiğin hiyerarşik temsilini öğrenmez. Bu sınırlama, özellikle farklı kullanıcı davranışı türlerinin benzerliğini incelerken belirgindir. Hiyerarşik GNN algoritma modeli, hiyerarşik bir yapıyı birleştirir ve GNN'nin ifade yeteneğini geliştirir.
H (k) 'nin, GNN'nin k adımından sonra düğümün gömme matrisini hesapladığını varsayalım. A, G grafiğinin bitişik matrisidir. Algoritma 1'de, geleneksel GNN yinelemeli öğrenme H (k), H (k-1), A ve bazı eğitilebilir parametreleri (k) birleştirir. Başlangıçta, H (0) = X olarak ayarladık, burada X, düğüm özelliklerinin matrisini temsil ediyor. Hiyerarşik GNN'mizde, gömme sonuçlarını hiyerarşik bir şekilde öğreniyoruz. Spesifik olarak, A (l) ve X (l), sırasıyla, 1. katmandaki bitişik matris ve düğüm özellik matrisini göstersin. Tek katmanlı bir GNN'ye A (l) ve X (l) girerek, l'inci katmanın düğüm gömme vektörünün sonuç matrisini Z (l) öğrenin.
Bundan sonra, grafikte bazı köşeleri kümeleriz ve bitişik matris A (l) 'yi A (l + 1) olarak güncelleriz. S (l), 1. katmandaki öğrenilebilir atama matrisini göstersin. S (l) 'deki her satır ve her sütun, 1. katmandaki ve (l + 1) katmandaki bir kümeye karşılık gelir. S (l), softmax fonksiyonunu başka bir GNN havuzunun A (l) ve X (l) 'sine uygulayarak elde edilebilir. Z (l) ve S (l) kullanarak yeni bir iri taneli bitişik matrisi elde edebiliriz A (l + 1) = S (l) (T) * A (l) * S (l ) Ve yeni bir özellik matrisi X (l + 1) = S (l) (T) * Z (l). Bölüm 5'te doğrulandığı gibi, çok katmanlı GNN, tek katmanlı geleneksel GNN'den daha etkilidir.
Dinamik olarak geliştirilmiş (Gelişen) GNN algoritması
Bu model, dinamik ağ ayarlarında köşe yerleştirme için kullanılır. Amacımız, grafik dizisindeki (G (1), G (2), G (3), ... G (T)) köşelerin temsilini öğrenmektir.
Dinamik grafiklerin evrimsel doğasını yakalamak için, evrim bağlantılarını iki türe ayırıyoruz: (1) normal evrim, makul kenar değişikliklerinin çoğunu temsil eder; (2) patlama bağlantıları, nadir ve anormal kenar evrimini temsil eder.
Bu temelde, dinamik grafikteki tüm köşelerin gömülmesi, araya eklenmiş bir şekilde öğrenilir. Zaman damgası t'de, G (t) grafiğinde bulunan normal ve ani bağlantılar, G (t) 'deki her köşe v için gömme sonucunu h (v) oluşturmak için GraphSAGE modeliyle entegre edilir. Ardından, G (t + 1) grafiğindeki normal ve patlama bilgilerini tahmin etmek için varyasyonel otomatik kodlayıcı ve RNN modelini kullanırız. Bu işlem, her zaman damgasında t her bir köşe v'nin gömme sonucunu çıkarmak için yinelemelerde gerçekleştirilir.
Bayesian GNN algoritması
Model, Bayesian çerçevesi aracılığıyla iki tür bilgi kaynağını entegre eder, yani bilgi grafiği yerleştirme veya davranış grafiği yerleştirme. Bilişsel bilimde insan anlayış sürecini simüle eder Bu süreçte, her bir biliş türü, belirli görevler altında önceki bilgileri ayarlayarak yönlendirilir. Spesifik olarak, bir bilgi grafiği G ve G'de bir varlık (tepe) v verildiğinde, temel gömme h (v) tamamen G'nin kendisi dikkate alınarak öğrenilir, bu da G'deki önceki bilgileri açıklar ve sonra Hv'ye göre, belirli bir görevin altına z (v) yerleştirme üretilir ve görev için bir düzeltme terimi v oluşturulur, yani:
Bunlar arasında f doğrusal olmayan bir fonksiyondur. Doğru v ve f'yi öğrenmek mümkün görünmüyor, çünkü v varlığı farklı v'ye sahip ve f fonksiyonu çok karmaşık. Bu işlevi işlemek için, ikinci dereceden bilgileri dikkate alarak, h (v) 'den z (v)' ye bir üretici model uygularız. Spesifik olarak, her v varlığı için, bir Gauss dağılımından N (0, s (v) (2)) düzeltme değişkenini v örnekliyoruz. Bunlar arasında, s (v), h (v) 'nin korelasyon katsayısı ile belirlenir. Daha sonra, her v1 ve v2 varlık çifti için, başka bir Gauss dağılımından z (v1) -z (v2) örnekliyoruz:
Bunlar arasında , f fonksiyonunun eğitilebilir parametrelerini temsil eder. v'nin arka ortalaması u ^ (v) ve ^ sonuç parametresidir. H (v) + u ^ (v) 'yi değiştirilmiş bilgi grafiğinin gömülmesi olarak ve f (h (v) + u ^ (v)) değiştirilmiş belirli görevin gömülmesi olarak uygularız.
Deney
5.1 Sistem değerlendirmesi
Bu bölümde, AliGraph platformundaki temel sistemin performansını (grafik oluşturma ve komşu düğümleri önbelleğe alma) depolama, örnekleme ve hesaplama açısından değerlendiriyoruz. Tüm deneyler, Tablo 3'te gösterildiği gibi, Taobao-küçük ve Taobao-büyük olmak üzere iki veri seti üzerinde gerçekleştirildi, ikincisinin depolama kapasitesi öncekinden altı kat daha büyük. Hepsi, Taobao e-ticaret platformundaki kullanıcıların ve öğelerin alt resimlerini temsil eder.
Grafik yapısı
Grafik yapımının performansı, grafik hesaplama platformlarında merkezi bir rol oynar. AliGraph, bölümlenmiş olsun ya da olmasın farklı dosya sistemlerinden çeşitli ham verileri destekler. Şekil 7, iki veri seti üzerinde çalışan düğümler için grafik oluşturmanın zaman maliyetini göstermektedir. Aşağıdaki iki sonucu gözlemledik: (1) Woker düğümlerinin sayısı arttıkça, grafiği oluşturma süresi önemli ölçüde kısalır; (2) AliGraph birkaç dakika içinde büyük bir grafik oluşturabilir Gibi: Taobao-büyük 5 dakika sürer. Bu, grafikleri oluşturmak için genellikle birkaç saat süren çoğu teknikten (örneğin, PowerGraph) çok daha etkilidir.
Komşuları önbelleğe almanın etkinliği
Önemli köşe noktalarının k-hop komşularının önbelleğe alınmasının etkisini inceledik. Önbelleğe alma algoritmamızda, Di (k) ve Dv (k) 'yi analiz etmek için Denklem 1'de Imp (v) için bir eşik belirledik. Deneyde, tüm köşelerin 1-sekmeli komşularını yerel olarak önbelleğe alıyoruz ve 2-atlamalı komşuların önbelleğini kontrol eden eşiği değiştiriyoruz. Duyarlılığını ve etkinliğini test etmek için eşiği kademeli olarak 0,05'ten 0,45'e yükselttik.
Şekil 8, önbelleğe alınan köşelerin yüzdesini ve eşiği göstermektedir. Eşik 0.2'den küçük olduğunda, önbellek köşelerinin yüzdesi keskin bir şekilde düşer ve ardından nispeten kararlı hale gelir. Bunun nedeni, Teorem 2'de ispatladığımız gibi, köşelerin öneminin güç yasası dağılımına uymasıdır. Önbelleğe alma maliyetleri ve faydaları arasında iyi bir denge kurmak için, eşiği Şekil 9'a göre 0,2 olarak belirledik ve fazladan köşelerin yalnızca yaklaşık% 20'sini önbelleğe almamız gerekiyor.
Öneme dayalı önbelleğe alma stratejisini diğer iki strateji ile karşılaştırdık: rastgele strateji (önbelleğe alma, az sayıda köşenin komşularını rastgele seçer) ve LRU değiştirme stratejisi. Şekil 9, zaman maliyeti ile önbelleğe alınan tepe noktalarının yüzdesi arasındaki ilişkiyi göstermektedir. Deneysel sonuçlar, stokastik strateji yöntemimizin zaman maliyetinden yaklaşık% 40 -% 50 tasarruf sağladığını ve LRU değiştirme stratejisinin zaman maliyetinden yaklaşık% 50 -% 60 tasarruf sağladığını göstermektedir. Bunun nedeni şudur: (1) rastgele seçilen köşelere erişme olasılığının düşük olması; (2) LRU stratejisi, önbelleğe alınmış köşelerin sık sık değiştirilmesinden dolayı ekstra maliyet ekler.
4 512 20% Keşfedeceğiz: 1 60 2 Taobao-large Taobao-small
5 . AliGraph
5.2
5.2.1
veri seti
Amazon Taobao-small
6 AHGAmazon user item user item preference
- C1Homogeneous GE DeepWalkLINE Node2Vec
- C2 GE ANRL
- C3Heterogeneous GE Methpath2VecPMNEMVE MNEMethPath2Vec PMNE Node2Vec PMNE-nPMNE-r PMNE-c
- C4 GNN Structural2VecGCNFast-GCNAS-GCNGraphSAGE HEP
GNN GNN GNN
ROC ROC-AUCPR PR-AUCF1 HR Rate
d 20
5.2.1
AHEP
AHEP 7 Taobao-small AHEP 10
1 Taobao-small HEP AHEP AHEP HEP 2-3 HEP 2AHEP ROC-AUC F1 HEP AHEP HEP
GATNE
GATNE GATNE 8
GATNE Taobao-small GATNE ROC-AUCPR-AUC F1 4.6%1.84% 5.08% GATNE GATNE woker GATNE 150 GATNE
Mixture GNN
Mixture GNNDAE *-VAE 9 2%
GNN
GNN GraphSAGE 10 7.5% GNN
Evolving GNN
Evolving GNN DeepWalkDANE DNE TNE GraphSAGETaobao-small 11
Evolving GNN Evolving GNN micro (macro)F1 4.2% 3.6%
GNN
GNN GraphSAGE 12 1% 3% 900 item
GE GNN 1
DeepWalk skip-gram LINE NetMF DeepWalk LINENode2Vec SDNE structure-preserving GCN GraphSAGE
Heterojenlik
PMNE MVE MNE Mvn2Vec HNE PTE Metapath2Vec HERec skip-gram
TADW LANE AANE SNE DANE ANRL skip-gram
skip-gram Dynamic network embedding by modeling triadic closure processAttributed network embedding for learning in a dynamic
environment streaming
sonuç olarak
AliGraph
https://arxiv.org/pdf/1902.08730.pdf
https://tianchi.aliyun.com/dataset/dataDetail?dataId=9716
