Graf Verilerinde Yapay Zekayı Gözetimsiz Eğitmenin Yeni Bir Yolu

Yazarlar: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang ÖZET Sosyal ağlar ve iletişim ağları gibi çeşitli bilgi ağlarının içerik zenginliği, harici denetim olmadan yüksek kaliteli ifade edici temsiller öğrenmek için eşi görülmemiş bir potansiyel sunmaktadır. Bu makale, grafik yapıdaki verilerden bol bilgiyi denetimsiz bir şekilde koruma ve gömme alanına çıkarma konusunu araştırmaktadır. Bu amaçla, girdi grafikleri ile üst düzey gizli temsiller arasındaki korelasyonu ölçmek için Grafik Karşılıklı Bilgi (GMI) adlı yeni bir kavram öneriyoruz. GMI, geleneksel karşılıklı bilgi hesaplamalarının vektör uzayından grafik alanına genelleştirilmesini sağlar; burada hem düğüm özellikleri hem de topolojik yapı olmak üzere iki açıdan karşılıklı bilgiyi ölçmek vazgeçilmezdir. GMI birkaç fayda sunar: İlk olarak, birçok mevcut grafik temsil öğrenme algoritmasında kaçınılmaz bir kısıtlama olan girdi grafiklerinin izomorfik dönüşümlerine karşı değişmezdir; Ayrıca, MINE gibi mevcut karşılıklı bilgi tahmin yöntemleri tarafından verimli bir şekilde tahmin edilebilir ve maksimize edilebilir; Son olarak, teorik analizimiz doğruluğunu ve mantıklılığını doğrulamaktadır. GMI'nin yardımıyla, bir grafik sinir kodlayıcısının girdisi ve çıktısı arasındaki GMI'yi maksimize ederek eğitilen denetimsiz bir öğrenme modeli geliştiriyoruz. Hem transductive hem de endüktif düğüm sınıflandırma ve bağlantı tahmini üzerindeki kapsamlı deneyler, yöntemimizin en gelişmiş denetimsiz muadillerini geride bıraktığını ve hatta bazen denetimli olanların performansını aştığını göstermektedir. 1 GİRİŞ Çeşitli bilgi ağları için güvenilir nicel analiz elde etmek amacıyla, grafik yapıdaki veriler için yüksek kaliteli temsil öğrenimi, mevcut büyüleyici konulardan biri haline gelmiştir. Bu hedefe yönelik son yöntemler, yaygın olarak Grafik Sinir Ağları (GNN'ler) olarak sınıflandırılır ve düğüm sınıflandırma [ , , ], bağlantı tahmini [ , , ], grafik hizalama [ , , ], molekül üretimi [ , , ] gibi birçok öğrenme görevinde dikkate değer ilerlemeler kaydetmiştir. Verimli ilerlemelere rağmen, mevcut yaklaşımlarda GNN'leri eğitmek genellikle bir tür denetim gerektirir. Şüphesiz, etiketleme bilgisi elde etmek pahalıdır - manuel etiketleme veya izin için ödeme yapma - ve hatta gizlilik politikası nedeniyle elde edilmesi imkansızdır. Verilen etiketlerin güvenilirliğinin bazen sorgulanabilir olduğunu söylemeye gerek yok. Bu nedenle, denetim olmadan yüksek kaliteli grafik temsili nasıl elde edileceği, birçok pratik vaka için zorunlu hale gelmiş ve bu da bu makalenin çalışmasını motive etmiştir. 35 42 50 26 27 49 12 19 43 4 5 46 Topladığımız grafik yapıdaki verileri dikkatlice inceleyerek, bunların genellikle sosyal ağlar, atıf ağları ve iletişim ağları gibi çeşitli kaynaklardan geldiğini, bu ağlarda muazzam miktarda hem içerik hem de bağlantı bilgisi bulunduğunu bulduk. Örneğin, Twitter, Flickr ve Facebook gibi birçok sosyal platformdaki veriler, kullanıcıların özelliklerini ( , temel kişisel ayrıntılar, metinler, resimler, IP) ve ilişkilerini ( , aynı ürünü satın alma, arkadaş olma) içerir. Bu zengin içerik verileri, ek rehberlik olmadan sonraki madencilik görevlerini desteklemek için yeterlidir: İki varlık özelliklerde aşırı benzerlik gösteriyorsa, aralarında bir bağlantı olasılığı yüksektir (bağlantı tahmini) ve aynı kategoriye ait olma olasılıkları yüksektir (sınıflandırma); iki varlık aynı varlığa bağlanırsa, muhtemelen benzer özelliklere sahiptirler (öneri). Bu anlamda, bilgi ağlarından mümkün olduğunca fazla bilgiyi gömme alanına korumak ve çıkarmak, herhangi bir denetim biçimi olmadan madencilik görevlerinde arzu edilen performansı sergileyen yüksek kaliteli ifade edici temsiller öğrenmeyi kolaylaştırır. Denetimsiz grafik temsil öğrenimi, özellikle doğadaki büyük ölçekli etiketlenmemiş verilerden yararlanmak istediğimizde, etiketlerden özgürlüğü nedeniyle birçok durumda daha tercih edilen bir seçenektir. örneğin örneğin Grafikler içindeki zengin bilgiyi tam olarak miras almak için, bu makalede, resimler üzerinde çalışan Deep Info-Max yönteminin [ ] ampirik başarısından esinlenerek, karşılıklı bilgi (MI) maksimizasyonu temelinde grafik gömme gerçekleştiriyoruz. Faydalı temsiller keşfetmek için Deep InfoMax, kodlayıcıyı girdileri ( , resimler) ve çıktıları ( , gizli vektörler) arasındaki MI'yi maksimize etmek üzere eğitir. Grafik alanında Deep InfoMax'ı göz önünde bulundurduğumuzda, aşmamız gereken ilk engel, MI'yi grafikler ve gizli vektörler arasında nasıl tanımlayacağımızdır; zira grafiklerin topolojisi resimlerden daha karmaşıktır (Bkz. Şekil Zorluklardan biri, her bir düğümün gizli temsilinin ve komşuluk girdi özelliklerinin MI fonksiyonunun simetrik özelliklere uymasını, eşdeğer olarak, komşulukların permütasyonlarına karşı değişmez olmasını sağlamaktır. MI'yi dikkate alan son zamanlardaki çalışmalardan biri olan Deep Graph Infomax (DGI) [ ], önce bir girdi grafiğini ve karşılık gelen bozulmuş bir grafiği gömer, ardından okuma fonksiyonu aracılığıyla girdi grafiğini bir vektör olarak özetler, son olarak bu özet vektör ile gizli temsiller arasındaki MI'yi, bozulmuş grafikten (negatif örnek) girdi grafiğini (pozitif örnek) ayırt ederek maksimize eder. Şekil DGI'nin kolay anlaşılır bir genel bakışını sunmaktadır. Bu tür bir MI'yi maksimize etmenin, girdi düğüm özellikleri ile gizli vektörler arasındaki MI'yi maksimize etmeye eşdeğer olduğu kanıtlanmıştır, ancak bu denklik çeşitli önceden ayarlanmış koşullar altında geçerlidir, , okuma fonksiyonu enjektif olmalıdır, ki bu gerçek durumlarda aşırı kısıtlayıcı görünmektedir. Enjektif okuma fonksiyonunun varlığını belirli tasarımlarla, , DeepSets'te [ ] kullanılanla garanti etsek bile, okuma fonksiyonunun enjektif yeteneği, parametrelerinin nasıl eğitildiğinden de etkilenir. Yani, başlangıçta enjektif olan bir fonksiyon, harici bir denetim olmadan eğitilirse enjektif olmama riski taşır. Okuma fonksiyonu enjektif değilse, özet vektörde bulunan girdi grafik bilgisi, grafiğin boyutu arttıkça azalacaktır. Dahası, DGI kaba bir grafik/yama düzeyinde MI maksimizasyonunda kalır. Bu nedenle DGI'de, kodlayıcının girdi verilerinden yeterli bilgiyi damıtmasını garanti edecek bir garanti yoktur, çünkü gizli temsilleri orijinal girdileriyle özenle ilişkilendirmez. 20 yani yani 1). 41 1 örneğin örneğin 47 Bu makalede, herhangi bir okuma fonksiyonu ve bozulma fonksiyonu kullanmadan, grafik yapıları açısından MI'yi dikkate almanın daha basit bir yolunu ortaya koyuyoruz. MI'yi doğrudan kodlayıcının girdisi ( , girdi komşuluğundan oluşan alt-grafik) ve çıktısı ( , her düğümün gizli temsili) arasındaki karşılaştırma yoluyla türetiyoruz. Ve ilginç bir şekilde, teorik türetmelerimiz, doğrudan formüle edilmiş MI'nin, her bir komşuluk özelliği ve gizli vektör arasındaki yerel MI'ların ağırlıklı bir toplamına ayrıştırılabileceğini göstermektedir. Bu şekilde, girdi özelliklerini ayrıştırdık ve MI hesaplamasını yapılabilir hale getirdik. Dahası, bu MI formu, ağırlık değerlerini ayarlarsak simetrik özelliği kolayca sağlayabilir. Daha fazla ayrıntıyı § bulabilirsiniz. Yukarıdaki MI esas olarak düğüm özellikleri düzeyinde ölçüldüğü için, buna Özellik Karşılıklı Bilgi (FMI) adını veriyoruz. yani yani 3.1'de FMI ile ilgili iki sorun kalmaktadır: birleştirme ağırlıkları hala bilinmiyor ve topolojiyi ( , kenar özelliklerini) hesaba katmıyor. Bu iki sorunu daha fazla ele almak için, FMI'ye dayanarak Grafik Karşılıklı Bilgi (GMI) ölçümümüzü tanımlıyoruz. Özellikle, GMI, FMI'deki ağırlıkları her bir komşunun temsil alanındaki hedef düğüme olan yakınlığına eşitleyerek sezgisel bir değer ataması uygular. Topoloji bilgisini korumak için, GMI bu ağırlıkları ek bir karşılıklı bilgi terimi aracılığıyla girdi kenar özellikleriyle daha da ilişkilendirir. Sonuç GMI, topolojik olarak değişmezdir ve ayrıca Karşılıklı Bilgi Sinir Tahmini (MINE) ile hesaplanabilir. Çalışmamızın temel katkıları şunlardır: 1. 2. yani • : Geleneksel MI tahminini grafik alanına genelleştiriyoruz ve buna göre Grafik Karşılıklı Bilgi (GMI) adlı yeni bir kavram öneriyoruz. GMI, MI'yı girdi grafikleri ve üst düzey gömmeler arasında doğrudan bir desende dikkate aldığı için okuma fonksiyonundan kaynaklanan potansiyel riskten muaftır. Kavramlar • : Teorik analizimiz aracılığıyla, tüm GMI'yi yerel MI'ların ağırlıklı bir toplamına ayrıştıran yapılabilir ve hesaplanabilir bir GMI formu sunuyoruz. MINE yönteminin yardımıyla, GMI maksimizasyonu bir düğüm düzeyinde kolayca elde edilebilir. Algoritmalar • : GMI'nin etkinliğini, hem transductive hem de endüktif olan çeşitli popüler düğüm sınıflandırma ve bağlantı tahmini görevlerinde doğruluyoruz. Deneyler, yöntemimizin çeşitli kıyaslamalarda umut verici performans gösterdiğini ve hatta bazen denetimli muadillerini geride bıraktığını göstermektedir. Deneysel Bulgular 2 İLGİLİ ÇALIŞMALAR Çalışmamızın odağı doğrultusunda, önceki çalışmaları şu iki alanda kısaca gözden geçiriyoruz: karşılıklı bilgi tahmini ve grafikler üzerinde temsil öğrenmek için sinir ağları. 1. 2. . InfoMax prensibi [ ] sinir ağlarının girdileri ve çıktıları arasındaki MI'yi maksimize etmeyi savunurken, ICA algoritmaları [ , ] gibi birçok yöntem denetimsiz özellik öğreniminde MI fikrini kullanmaya çalışır. Bununla birlikte, bu yöntemler, yüksek boyutlu sürekli değişkenler arasındaki MI'yi hesaplamanın zorluğu nedeniyle derin sinir ağlarına kolayca genelleştirilemez. Neyse ki, Karşılıklı Bilgi Sinir Tahmini (MINE) [ ], ortak dağılımdan ve iki rastgele değişkenin marjinallerinin çarpımından gelen örnekleri ayırt etmek için bir istatistik ağı eğittiği için derin sinir ağlarındaki MI tahminini mümkün kılar. Spesifik olarak, MINE, KL tabanlı MI formülasyonunu kullanırken, KL olmayan bir alternatif olan Jensen-Shannon sapması (JSD) [ ], MI'nin kesin değeri konusunda endişelenmeden kullanılabilir. Karşılıklı bilgi tahmini 3 1 21 2 30 . Grafik sinir ağlarının (GNN'ler) hızlı gelişimiyle birlikte, son yıllarda GNN'lere dayanan çok sayıda grafik temsil öğrenme algoritması önerilmiştir ve bunlar geleneksel rastgele yürüyüş tabanlı ve faktörleştirme tabanlı gömme yaklaşımlarından [ , , , , ] daha güçlü performans sergilemektedir. Tipik olarak, bu yöntemler denetimli ve denetimsiz kategorilere ayrılabilir. Bunlar arasında, grafikler üzerinde denetimli temsil öğrenimi üzerine zengin bir literatür [ , , , , ] bulunmaktadır. Ağ mimarilerindeki çeşitliliklerine rağmen, genellikle gerçek senaryolarda erişilemeyen etiketlerin yardımıyla ampirik başarı elde ederler. Bu durumda, denetimsiz grafik öğrenme yöntemleri [ , , ] daha geniş uygulama potansiyeline sahiptir. İyi bilinen yöntem GraphSAGE [ ]'dir, denetimsiz ayarında GNN'leri rastgele yürüyüş tabanlı bir hedef ile eğiten endüktif bir çerçevedir. Ve son zamanlarda, DGI [ ] MI maksimizasyonu fikrini grafik alanına uygular ve denetimsiz bir desende güçlü performans elde eder. Ancak, DGI kaba taneli bir maksimizasyon uygular ( , grafik/yama düzeyinde MI'yi maksimize eder), bu da girdi grafiğindeki hassas bilgiyi korumayı zorlaştırır. Ayrıca, DGI'de kullanılan okuma fonksiyonu üzerindeki koşul, gerçek durumlarda aşırı kısıtlayıcı görünmektedir. Buna karşılık, okuma fonksiyonunun kısıtlamasını kaldırmaya ve kodlayıcının girdileri ve çıktıları arasındaki MI'yi doğrudan maksimize ederek düğüm düzeyinde grafik karşılıklı bilgi maksimizasyonuna ulaşmaya odaklanıyoruz. Yöntemimiz tarafından türetilen temsiller, girdi grafik bilgisini koruma açısından daha gelişmiştir, bu da düğüm sınıflandırma, bağlantı tahmini ve öneri gibi sonraki grafik madencilik görevleri için potansiyelini garanti eder. Grafik temsil öğrenimi için sinir ağları 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 yani 3 GRAFİK KARŞILIKLI BİLGİ: TANIM VE MAKSİMİZASYON Daha ileri gitmeden önce, bu makalede kullanılan ön kavramları sunuyoruz. G = (V, E), düğüm ∈ V ve kenarlar = ( , ) ∈ E olan bir grafiği temsil etsin. Düğüm özellikleri, varsayılan ampirik olasılık dağılımı P ile, ∈ R × = { 1, · · · , } olarak verilir, burada ∈ R , düğümü için özelliği temsil eder. Komşu matrisi ∈ R × , kenarına bağlı olan , gerçek bir sayı veya çok boyutlu bir vektör1 olabilir. N vi eij vi vj X N D x x N xi D vi A N N eij Aij Grafik temsil öğreniminin amacı, gizli vektörler = { 1, · · · , } = ( , ) tüm düğümler için üst düzey temsilleri gösteren bir kodlayıcı : R × × R × → R × ′ öğrenmektir. Kodlama süreci düğüm bazında yeniden yazılabilir. H h hN f X A f N D N N N D Bunu göstermek için, düğümü için ve 'yi sırasıyla komşularının özellikleri ve karşılık gelen komşulara bağlı koşullu komşu matrisi olarak tanımlıyoruz. i Xi Ai Özellikle, , kodlayıcı bir -katmanlı GNN ise ≤ olan k-hop komşularını içerir ve komşu matrisine kendi döngüleri eklersek düğüm 'yi de içerir. Burada, ve tarafından genişletilen alt-grafiği, düğüm için olarak adlandırıyoruz ve G ile gösteriyoruz. Destek grafiğinin tanımıyla, her düğüm için kodlama = (G ) = ( , ) olur. Xi f l k l i Xi Ai i destek grafiği i hi f i f Xi Ai Deep InfoMax'ta [ ], kodlayıcının eğitim hedefi girdileri ve çıktıları arasındaki MI'yı maksimize etmektir. MI, ortak dağılımdan gelen örnekleri marjinallerin çarpımından gelenlerden sınıflandırmak için bir diskriminatör olarak bir istatistik ağı kullanarak tahmin edilir. Doğal olarak, Deep InfoMax fikrini grafiklere uyarlarken, her düğüm için temsil ile destek grafiği G arasındaki MI'yı maksimize etmeliyiz. Böyle bir grafik MI'yi ( ; G ) ile gösteririz. Ancak, I (hi ; Gi )'yi tanımlamak doğrudan değildir. Zorluklar şunlardır: Grafik karşılıklı bilgi tanımlamada zorluklar. 20 hi i I hi i • Grafik MI, düğüm indeksine göre değişmez olmalıdır. Başka bir deyişle, eğer G ve G′ birbirine izomorfik ise ( ; G ) = ( ; G′ ) olmalıdır. i i I hi i I hi i • MI hesaplaması için MINE yöntemini benimsersek, MINE'daki diskriminatör yalnızca sabit boyutlu girdileri kabul eder. Bu, farklı G 'ler genellikle farklı sayıda düğüm içerdiği ve dolayısıyla farklı boyutlara sahip olduğu için G için henüz uygulanamaz. i i Grafik karşılıklı bilgi tanımlama sorununu aşmak için bu bölüm, yalnızca düğüm özelliklerine dayanan Özellik Karşılıklı Bilgi (FMI) kavramını tanıtarak başlar. FMI'nin ayrışmasından ilham alarak, hem düğüm özelliklerini hem de 3.1 ÖZellik KARŞILIKLI BİLGİ Düğüm özellikleri 'nin ampirik olasılık dağılımını ( ) olarak, 'nin olasılığını ( ) olarak ve ortak dağılımı ( , ) olarak gösteriyoruz. Bilgi teorisine göre, ve arasındaki MI şu şekilde tanımlanır: Xi p Xi hi p hi p hi Xi hi Xi İlginç bir şekilde, ( ; ) hesaplamak için aşağıdaki karşılıklı bilgi ayrıştırma teoremine sahibiz. I hi Xi Teorem 1 (Karşılıklı Bilgi Ayrıştırması). ( | ) ( ; ) Koşullu olasılık p hi Xi multiplikatif ise (multiplikatif tanımı için [ ]'e bakınız), Denklem'de tanımlanan küresel karşılıklı bilgi I 36 hi Xi (1) yerel MI'ların ağırlıklı bir toplamı olarak ayrıştırılabilir, yani, burada, xj düğüm i'nin j-inci komşusudur, in Xi 'deki tüm elemanların sayısıdır ve ağırlık wij 1 ≤ wi j ≤ 1 her j için sağlanır. Yukarıdaki teoremi kanıtlamak için önce iki lemma ve bir tanım sunuyoruz. Lemma 1. Herhangi bir rastgele değişken X, Y ve Z için, şunlar geçerlidir Teorem ayrıştırma ile, Denklem sağ tarafını MINE kullanarak hesaplayabiliriz; diskriminatörün girdileri artık ( , ) çiftleri haline gelir ve bunların boyutu her zaman aynı kalır ( , ′ × ). Ayrıca, ağırlıkları izomorfik dönüşümlere uyacak şekilde ayarlayabiliriz. Örneğin, eğer yalnızca düğüm 'nin bir-hop komşularını içeriyorsa, tüm ağırlıkları aynı ayarlamak, farklı sıralardaki girdi düğümleri için aynı MI'yi verecektir. 1'deki (2)'nin hi xj yani D D Xi i Ayrıştırmanın bazı faydalarına rağmen, ağırlıkların kesin değerlerini karakterize etmek zordur çünkü bunlar ( ; ) değerleri ve bunların altında yatan olasılık dağılımlarıyla ilgilidir. I hi xj Basit bir yol, tüm ağırlıkları olarak ayarlamaktır, o zaman Denklem sağ tarafını maksimize etmek, ( ; )'nin alt sınırını maksimize etmeye eşdeğerdir, böylece gerçek FMI de bir dereceye kadar maksimize edilir. Bu yöntemin yanı sıra, ağırlıkları eğitilebilir dikkatler olarak ele alarak daha gelişmiş bir çözüm sunuyoruz, bu da bir sonraki alt bölümde konudur. 1 (2)'nin I hi Xi Teorem ayrıştırmadan esinlenerek, değerlerinin daha esnek olabilmesi ve grafiklerin içsel özelliğini yakalayabilmesi için eğitilebilir ağırlıkları grafiklerin diğer yönünden ( , 3.2 Topolojiye Duyarlı Karşılıklı Bilgi 1'deki wij yani topolojik bakış açısından) oluşturmaya çalışıyoruz. Nihayetinde Grafik Karşılıklı Bilgi (GMI) tanımını türetiyoruz. Tanım 2 (Grafik Karşılıklı Bilgi). G = ( , ) Gizli vektör h ve destek grafiği X A arasındaki MI şu şekilde tanımlanır burada xj ve in'nin tanımları Teorem 1 ile aynıdır, aij komşu matrisindeki kenar ağırlığı/özelliğidir ve σ(·) sigmoid fonksiyonudur. Sezgisel olarak, Denklem (10)'un ilk terimindeki ağırlığı, yerel bir MI'nın küresel olana katkısının derecesini ölçer. Kenar ağırlığı/özelliği ile arasındaki karşılıklı bilgiyi maksimize etmek için wij aij wij ( ; ) = log + (1 - ) log (1 - ). & I wij aij aij wij aij wij