Sinir ağlarının son zamanlardaki başarısı, örüntü tanıma ve veri madenciliği üzerine araştırmaları artırdı.

Nesne algılama, makine çevirisi ve konuşma tanıma gibi makine öğrenimi görevlerine CNN, RNN veya otomatik kodlayıcılar gibi uçtan uca derin öğrenme paradigmaları ile yeni bir hayat verildi.

Derin Öğrenme, Öklid verilerinin (resimler, metinler, videolar) gizli kalıplarını yakalamada iyidir.

Peki, verilerin Öklid dışı alanlardan üretildiği, nesneler arasında karmaşık ilişkiler ve karşılıklı bağımlılıklara sahip grafikler olarak temsil edilen uygulamalar ne olacak?

Bu yazımızda inceleyeceğimiz Grafik Sinir Ağları (GNN) işte burada devreye giriyor. Grafik teorileri ve temel tanımlarla başlayacağız, GNN formlarına ve ilkelerine geçeceğiz ve bazı GNN uygulamaları ile bitireceğiz.

GRAFİK NEDİR?

Grafik Sinir Ağlarının (GNN) en temel parçası bir Grafiktir.
Bilgisayar biliminde bir grafik, iki bileşenden oluşan bir veri yapısıdır. Bunlar: Düğümler (köşeler) ve kenarlardır.
Bir G grafik, G=(V,E) olarak tanımlanabilir, burada V düğümleri, E kenarları temsil eder.
Düğümler arasında yön bağımlılıkları varsa, kenarlar yönlendirilir. Yoksa yönlendirilmez.

Kaynak: https://cdn-images-1.medium.com/max/800/0*qpdwFvjH3LzyCUO9.png

Bir grafik, sosyal medya ağları veya moleküller gibi şeyleri temsil edebilir. Düğümleri kullanıcılar, uçları bağıntılar olarak düşünün. Bir sosyal medya grafiği şöyle görünebilir:

Kaynak: https://cdn-images-1.medium.com/max/800/0*LGZFJIY4Wb_PJNPr.png

Bir grafik genellikle bir bağıntı matris olan A ile temsil edilir.
Bir grafiğin düğümleri varsa, A’nın boyutu (nxn) olur.
Bazen düğümlerin bir dizi özelliği vardır (örneğin, bir kullanıcı profili). Düğümde f sayı özelliği varsa, düğüm özellik matrisi X (nxf) boyutuna sahip olur.

Bir Grafiği Analiz Etmek Neden Zordur?
Grafik verileri o kadar karmaşık ki, mevcut makine öğrenimi algoritmaları için pek çok zorluk yarattı.
Bunun nedeni, geleneksel Makine Öğrenimi ve Derin Öğrenme araçlarının basit veri türlerinde uzmanlaşmasıdır. Aynı yapıya ve boyuta sahip görüntüler gibi, bunları sabit boyutlu ızgara grafikleri olarak düşünebiliriz. Metin ve konuşma dizilerdir, dolayısıyla bunları çizgi grafikler olarak düşünebiliriz.
Ancak, sabit bir formu olmayan, değişken boyutta sırasız düğümlere sahip, düğümlerin farklı miktarlarda komşuları olabileceği daha karmaşık grafikler vardır.
Ayrıca, mevcut makine öğrenimi algoritmalarının örneklerin birbirinden bağımsız olduğuna dair temel bir varsayıma sahip olmasına da yardımcı olmuyor. Bu, grafik verileri için yanlıştır, çünkü her bir düğüm, çeşitli türlerdeki bağlantılarla diğerleriyle ilişkilidir.

Kaynak: https://web.stanford.edu/class/cs224w/slides/08-GNN.pdf

GRAFİK SİNİR AĞLARI

Grafik Sinir Ağları (GNN’ler), grafiklerle tanımlanan veriler üzerinde çıkarım yapmak için tasarlanmış bir derin öğrenme yöntemleri sınıfıdır.
GNN’ler, doğrudan grafiklere uygulanabilen ve düğüm düzeyinde, kenar düzeyinde ve grafik düzeyinde tahmin görevlerini gerçekleştirmenin kolay bir yolunu sağlayan sinir ağlarıdır.
GNN’ler, Evrişimli Sinir Ağlarının (CNN’ler) yapamadığını yapabilir.

Evrişimli Sinir Ağları (CNN’ler) Neden Grafiklerde Başarısız Oluyor?
CNN’ler, makinelerin nesneleri görselleştirmesini sağlamak ve görüntü sınıflandırma, görüntü tanıma veya nesne algılama gibi görevleri gerçekleştirmek için kullanılabilir. Burası CNN’lerin en popüler olduğu yerdir.
CNN’lerin arkasındaki temel konsept, çekirdek biçimindeki bir dizi alıcı alan aracılığıyla uzamsal olarak yerelleştirilmiş özellikleri tanımlamak için gizli evrişim ve havuzlama katmanları sunar.

Kaynak: https://web.stanford.edu/class/cs224w/slides/08-GNN.pdf

Evrişim, normal ızgaralar olan görüntülerde nasıl çalışır? Evrişimli operatör penceresini iki boyutlu bir görüntü boyunca kaydırıyoruz ve bu kayan pencere üzerinde bazı işlevleri hesaplıyoruz. Sonra onu birçok katmandan geçiriyoruz.
Amacımız, evrişim kavramını bu basit iki boyutlu kafeslerin ötesinde genelleştirmek.
Amacımıza ulaşmamızı sağlayan içgörü, evrişimin görüntünün küçük bir alt parçasını (görüntünün küçük bir dikdörtgen bölümünü) alması, ona bir işlev uygulaması ve yeni bir parça (yeni bir piksel) üretmesidir.
Olan şu ki, bu merkez pikselin merkez düğümü, yeni bir değer üretmek için komşularından ve kendisinden gelen bilgileri toplar.
Grafiğin keyfi boyutu ve karmaşık topoloji nedeniyle grafiklerde CNN gerçekleştirmek çok zordur, bu da uzamsal konum olmadığı anlamına gelir.
Ayrıca sabitlenmemiş düğüm sıralaması da vardır. İlk önce A, B, C, D, E düğümlerini etiketlediysek ve ikinci kez B, D, A, E, C olarak etiketlediysek, ağdaki matrisin girişleri değişecektir. Grafikler düğüm sıralamasına göre değişmez, bu nedenle düğümleri nasıl sıraladığımızdan bağımsız olarak aynı sonucu almak istiyoruz.

Grafikler için Derin Öğrenmenin Temelleri
Grafik teorisinde, Düğüm Gömme kavramını uyguluyoruz. Grafikteki benzer düğümlerin birbirine yakın yerleştirilmesi için düğümleri d-boyutlu bir gömme uzayına (grafiğin gerçek boyutu yerine düşük boyutlu uzay) eşlemek anlamına gelir.
Amacımız, yerleştirme alanındaki benzerliğin ağdaki benzerliğe yaklaşması için düğümleri haritalamaktır.
U ve v‘yi bir grafikteki iki düğüm olarak tanımlayalım.
X_U ve X_V iki özellik vektörüdür.
Şimdi, özellik vektörlerini Z_U ve Z_V‘ye dönüştüren kodlayıcı işlevi Enc (u) ve Enc (v) ‘yi tanımlayacağız.
Not: Benzerlik işlevi Öklid mesafesi olabilir.

Kaynak: https://web.stanford.edu/class/cs224w/slides/08-GNN.pdf

Öyleyse şimdi sorun, kodlayıcı işlevinin nasıl ortaya çıkacağıdır?
Kodlayıcı işlevi şunları gerçekleştirebilmelidir:

• Yerellik (yerel ağ komşuları)
• Toplu bilgiler
• Birden çok katmanı istifleme (hesaplama)

Konum bilgisi, hesaplamalı bir grafik kullanılarak elde edilebilir. Aşağıdaki grafikte gösterildiği gibi i, bu düğümün komşularına ve bu komşularının komşularına nasıl bağlandığını gördüğümüz kırmızı düğümdür. Olası tüm bağlantıları göreceğiz ve bir hesaplama grafiği oluşturacağız.

Bunu yaparak, yapıyı yakalıyoruz ve aynı zamanda özellik bilgilerini de ödünç alıyoruz.

Komşu keşfi ve bilgi paylaşımı
Kaynak: https://web.stanford.edu/class/cs224w/slides/08-GNN.pdf

Konum bilgisi hesaplama grafiğini koruduğunda, toplamaya başlarız. Bu temelde sinir ağları kullanılarak yapılır.

Kaynak: https://web.stanford.edu/class/cs224w/slides/08-GNN.pdf

Sinir Ağları gri kutularda sunulmuştur. Toplam, ortalama, maksimum gibi toplamaların sırayla değişmez olmasını gerektirirler, çünkü bunlar permütasyonla değişmeyen fonksiyonlardır. Bu özellik, toplamaların gerçekleştirilmesini sağlar.
GNN’lerde ileriye doğru yayılma kuralına geçelim. Girişten gelen bilginin sinir ağının çıkış tarafına nasıl gideceğini belirler.

Kaynak: https://web.stanford.edu/class/cs224w/slides/08-GNN.pdf

Her düğümün bir özellik vektörü vardır.
Örneğin, (X_A) , A düğümünün bir özellik vektörüdür.
Girdiler bu öznitelik vektörleridir ve kutu iki öznitelik vektörünü (X_A ve X_C) alacak, onları toplayacak ve ardından bir sonraki katmana aktaracaktır.
Örneğin, C düğümündeki girdinin, düğüm C‘nin özellikleri olduğuna, ancak 1. katmandaki C düğümünün düğümün gizli, gizli bir temsili olacağına ve 2. katmanda başka bir gizli temsil olacağına dikkat edin.
Dolayısıyla, bu hesaplama grafiğinde ileriye doğru yayılım gerçekleştirmek için 3 adıma ihtiyacımız var:

1.Aktivasyon birimlerini başlatın:

2. Ağdaki her katman:

Bu denklem için iki bölüm olduğunu fark edebiliriz:
İlk bölüm temelde düğüm v‘nin tüm komşularının ortalamasını alıyor.

İkinci kısım, eğitilebilir bir ağırlık matrisi olan ve temelde düğüm v için bir kendi kendine döngü aktivasyonu olan bir bias Bk ile çarpılan v düğümünün önceki katmanıdır.

σ: İki parça üzerinde gerçekleştirilen doğrusal olmayan aktivasyon.

3. Son denklem (son katmanda):

Bu, komşu kümelemesinin K katmanından sonraki yerleştirmedir.

Şimdi modeli eğitmek için düğümlerde bir kayıp fonksiyonu tanımlamamız gerekiyor.
Yerleştirmeleri herhangi bir kayıp fonksiyonuna besleyebilir ve ağırlık parametrelerini eğitmek için stokastik gradyan inişi çalıştırabiliriz.
Eğitim gözetimsiz veya denetimli olabilir:
Denetimsiz eğitim:
Yalnızca grafik yapısını kullanın: benzer düğümlerin benzer yerleştirmeleri vardır. Denetimsiz kayıp işlevi, grafikteki düğüm yakınlığına dayalı bir kayıp veya rastgele yürüyüşler olabilir.
Denetimli eğitim:
Düğüm sınıflandırması, normal veya anormal düğüm gibi denetlenen bir görev için modeli eğitin.
Özetlemek gerekirse, bu bölümde komşu bilgilerini toplayarak düğüm yerleştirmeleri oluşturmanın temel bir fikrini açıkladık.
Ardından, Grafik Evrişimli Ağlar (GCN’ler) konusunu ele alacağım.

GRAFİK EVRİŞİMLİ AĞLAR

GCN’ler ilk olarak “Spectral Networks and Deep Locally Connected Networks on Graphs” (Bruna ve diğerleri, 2014) ‘de, grafik yapılı verilere sinir ağlarını uygulama yöntemi olarak tanıtıldı.
En basit GCN’nin yalnızca üç farklı operatörü vardır:

• Grafik evrişimi
• Doğrusal katman
• Doğrusal olmayan aktivasyon

İşlemler genellikle bu sırayla yapılır. Birlikte bir ağ katmanı oluştururlar. Tam bir GCN oluşturmak için bir veya daha fazla katmanı birleştirebiliriz.
Python’da, PyTorch kullanarak kolayca bir GCN oluşturabiliriz:

import torch
from torch import nn

class GCN(nn.Module):
def __init__(self, *sizes):
super().__init__()
self.layers = nn.ModuleList([
nn.Linear(x, y) for x, y in zip(sizes[:-1], sizes[1:])
])
def forward(self, vertices, edges):
# ----- Build the adjacency matrix -----
# Start with self-connections
adj = torch.eye(len(vertices))
# edges contain connected vertices: [vertex_0, vertex_1]
adj[edges[:, 0], edges[:, 1]] = 1
adj[edges[:, 1], edges[:, 0]] = 1

# ----- Forward data pass -----
for layer in self.layers:
vertices = torch.sigmoid(layer(adj @ vertices))

return vertices

Kaynak: https://neptune.ai/blog/graph-neural-network-and-some-of-gnn-applications

GraphSAGE fikri:

GraphSAGE (Hamilton ve diğerleri, NIPS 2017) dinamik grafikler için bir temsil öğrenme tekniğidir.
Yeniden eğitim prosedürüne ihtiyaç duymadan yeni bir düğümün yerleştirilmesini tahmin edebilir.
GraphSAGE bunu yapmak için tümevarımlı öğrenmeyi kullanır. Düğümün özelliklerine ve komşuluğuna bağlı olarak yeni düğüm yerleştirmeyi tetikleyebilen toplayıcı işlevlerini öğrenir.

Kaynak: https://web.stanford.edu/class/cs224w/slides/08-GNN.pdf

İki büyük fark görebiliriz. İki şeyi bir araya toplamak ve izini kaybetmek yerine, bunları birleştirerek ayrı tutan genel bir toplama işlevi kullanırız.
Daha önce, Ortalama toplama işlevini kullanıyorduk – sadece komşulardan gelen mesajı alıp onları ekledik ve sonra bunu komşuların sayısına göre normalize ettik. Şimdi, havuzlama tipi bir yaklaşım da yapabiliriz veya bir LSTM gibi derin bir sinir ağı da kullanabiliriz.

Komşu Toplama: Varyantlar
Kaynak: https://web.stanford.edu/class/cs224w/slides/08-GNN.pdf

GNN UYGULAMALARI

Girişte bahsettiğim gibi, birkaç GNN uygulamasıyla bitirmek istiyorum.
Grafik yapılı veriler her yerde mevcuttur. GNN’lerin çözdüğü sorunlar şu kategorilere ayrılabilir:

• Düğüm Sınıflandırması: Buradaki görev, komşularının etiketlerine bakarak (düğümler olarak temsil edilen) örneklerin etiketlemesini belirlemektir. Genellikle, bu tür sorunlar yarı denetimli bir şekilde eğitilir ve grafiğin yalnızca bir kısmı etiketlenir.
• Grafik Sınıflandırma: Buradaki görev, tüm grafiği farklı kategorilere ayırmaktır. Görüntü sınıflandırması gibidir, ancak hedef grafik alanına dönüşür. Grafik sınıflandırmasının uygulamaları çoktur ve bir proteinin biyoinformatikte bir enzim olup olmadığını belirlemekten, NLP’deki belgeleri kategorize etmeye veya sosyal ağ analizine kadar çeşitlilik gösterir.
• Grafik görselleştirme: Geometrik grafik teorisi ve bilgi görselleştirmenin kesiştiği noktada matematik ve bilgisayar biliminin bir alanıdır. Verilerde mevcut olabilecek yapıları ve anormallikleri ortaya çıkaran ve kullanıcının grafikleri anlamasına yardımcı olan grafiklerin görsel temsiliyle ilgilenir.
• Bağlantı tahmini: Burada, algoritma grafiklerdeki varlıklar arasındaki ilişkiyi anlamalıdır ve ayrıca iki varlık arasında bir bağlantı olup olmadığını tahmin etmeye çalışır. Sosyal ağlarda, sosyal etkileşimlerden çıkarım yapmak veya kullanıcılara olası arkadaşlar önermek çok önemlidir. Tavsiye sistemi problemlerinde ve suç derneklerini tahmin etmede de kullanılmıştır.
• Grafik kümeleme: Verilerin grafikler biçiminde kümelenmesini ifade eder. Grafik verileri üzerinde gerçekleştirilen iki farklı kümeleme biçimi vardır. Köşe kümeleme, grafiğin düğümlerini kenar ağırlıklarına veya kenar mesafelerine göre yoğun şekilde bağlı bölge grupları halinde kümelemeyi amaçlar. İkinci grafik kümeleme biçimi, grafikleri kümelenecek nesneler olarak ele alır ve bu nesneleri benzerliğe göre kümeler.

GNN’nin çeşitli zorlukları çözebileceği alanlarda bazı uygulamaları gözden geçirelim.

Bilgisayar biliminde GNN’ler
Normal CNN’leri kullanan makineler, görüntüler ve videolardaki nesneleri ayırt edebilir ve tanımlayabilir. Yine de makinelerin bir insanın görsel sezgisine sahip olması için çok fazla gelişme gerekiyor. Yine de GNN mimarileri görüntü sınıflandırma problemlerine uygulanabilir.
Bu sorunlardan biri, modelin bir görüntüyü nesnelerden ve bunların anlamsal ilişkilerinden oluşan anlamsal bir grafiğe ayrıştırmayı amaçladığı sahne grafiği oluşturmadır. Bir görüntü verildiğinde, sahne grafiği oluşturma modelleri nesneleri algılar, tanır ve nesne çiftleri arasındaki anlamsal ilişkileri tahmin eder.
Bununla birlikte, GNN’lerin bilgisayarla görmedeki uygulamalarının sayısı hala artmaktadır. İnsan-nesne etkileşimi, az çekim görüntü sınıflandırması ve daha fazlasını içerir.

Doğal Dil İşlemede GNN’ler
Doğal Dil İşleme (NLP)’de, metnin bir RNN veya bir LSTM ile tanımlanabilen bir sıralı veri türü olduğunu biliyoruz. Bununla birlikte, grafikler, doğallıkları ve temsil kolaylıkları nedeniyle çeşitli NLP görevlerinde yoğun bir şekilde kullanılmaktadır.
Son zamanlarda, metin sınıflandırması, makine çevirisinde anlambilimden yararlanma, kullanıcı konum belirleme, ilişki çıkarma veya soru yanıtlama gibi çok sayıda NLP problemine GNN’lerin uygulanmasına yönelik bir ilgi artmıştır.
Her düğümün bir varlık olduğunu ve kenarların bunlar arasındaki ilişkileri tanımladığını biliyoruz. NLP araştırmasında, soru cevaplama sorunu yeni değildir. Ancak mevcut veri tabanı ile sınırlıydı. GraphSage (Hamilton ve diğerleri) gibi tekniklerle yöntemler daha önce görülmemiş düğümlere genelleştirilebilir.

Trafikteki GNN’ler
Trafik ağlarında trafik hızını, hacmini veya yol yoğunluğunu tahmin etmek akıllı bir ulaşım sisteminde temelde önemlidir. STGNN’leri kullanarak trafik tahmin problemini çözebiliriz.
Trafik ağını, düğümlerin yollara kurulu sensörler olduğu uzaysal-zamansal bir grafik olarak ele alındığında, kenarlar düğüm çiftleri arasındaki mesafeyle ölçülür ve her düğüm, dinamik girdi özellikleri olarak bir pencere içindeki ortalama trafik hızına sahiptir.

Kimyada GNN’ler
Kimyagerler, moleküllerin veya bileşiklerin grafik yapısını araştırmak için GNN’leri kullanabilir. Bu grafiklerde düğümler atomlar ve kenarlar – kimyasal bağlardır.

Diğer etki alanlarındaki GNN’ler
GNN’lerin uygulanması, yukarıdaki alanlar ve görevler ile sınırlı değildir. GNN’leri program doğrulama, program muhakemesi, sosyal etki tahmini, tavsiye sistemleri, elektriksel sağlık kayıtları modellemesi, beyin ağları ve düşman saldırıları önleme gibi çeşitli sorunlara uygulama girişimleri olmuştur.

SONUÇ:

Grafikleri ve Grafik sinir ağlarını anlama yolundan geçtik. Geçtiğimiz birkaç yıl içinde, grafik sinir ağları grafiklerle modellenebilen herhangi bir problem için güçlü ve pratik araçlar haline geldi. Araştırma literatürü genişlemekte ve birçok uygulama sahası mevcuttur.

NOT: Bu yazıdaki notlar, denklemler ve resimler kaynak [1]’de yer alan adresten alınmıştır. Ayrıca detaylı çalışmalarından dolayı “Amal Menzli”’ye teşekkürler. https://www.linkedin.com/in/amal-menzli-3ab655155/

Kaynaklar:
[1] https://neptune.ai/blog/graph-neural-network-and-some-of-gnn-applications
[2] https://web.stanford.edu/class/cs224w/slides/08-GNN.pdf