Weisfeiler-Lehman (WL) Graph Isomorphism Test

Weisfeiler-Lehman (1-WL) Graph Isomorphism Test

Türkçe: Weisfeiler-Lehman Çizge Eşyapı Testi

Ayrıntılı Tanım

İki farklı çizgenin topolojik olarak birbirinin tıpatıp aynısı (eşyapılı / izomorfik) olup olmadığını renkleri (etiketleri) komşuluklar boyunca iteratif olarak hashleyerek test eden klasik algoritmadır; **standart mesaj iletimli GNN'lerin teorik üst güç sınırını (expressive power limit)** temsil eder (Morris & Xu et al., 2019).

Ne İşe Yarar / Çözülen Problem

Standart bir GNN'in ne kadar karmaşık ağ yapılarını ayırt edebileceğini kanıtlar: Hiçbir standart GNN, 1-WL testinin ayırt edemediği iki farklı çizgeyi birbirinden ayırt edemez.

Nasıl Çalışır? (Teknik & Mekanizma)

Düğümler renklendirilir. Her adımda bir düğümün rengi ve komşularının renkleri toplanıp yeni bir hash koduna dönüştürülür. İki çizgenin renk histogramları uyuşmuyorsa çizgeler kesinlikle farklıdır.

Örnek Senaryo & Pratik Uygulama

Birbirinden farklı olan ama her düğümünün tam olarak 2 komşusu olan iki halka: Biri 6 düğümlü tek bir altıgen halka; diğeri ise iki ayrı bağımsız üçgen halka. 1-WL ve standart GNN ikisinin de yerel komşulukları aynı olduğu için bu iki şekli birbirinden ayıramaz ve aynı sanır.

Benzer Terimlerden Farkı

Bir sinir ağı değil; GNN mimarilerinin zekâ tavanını belirleyen matematiksel bir turnusol kâğıdıdır.

İlişkili Terimler (1)

#554

Message Passing Neural Network (MPNN)

Mesaj İletimli Sinir Ağı Çerçevesi

Ait Olduğu Kategori

Grafiksel Modeller, Çizge Sinir Ağları ve Bilgi Çirgeleri

GNN, Graph Convolution, Knowledge Graphs, TransE ve geometrik derin öğrenme.

Toplam Terim:30 Madde

Bu Kategorideki Tüm Terimleri Gör →

Önceki Terim (#557)Inductive vs. Transductive Learning in Graphs

Sonraki Terim (#559)Over-Smoothing in GNNs