Czym jest Graph Isomorphism Network (GIN)?

Sieć izomorfizmu grafów (GIN) to rodzaj sieci neuronowej grafów (GNN), zaprojektowanej do skutecznego rozróżniania grafów. GIN opiera się na idei, że jej architektura jest w stanie przybliżyć moc algorytmu testu izomorfizmu grafów (test Weisfeiler-Lehmana), co czyni ją bardzo wyrazistą.

Główną ideą GIN jest agregacja cech sąsiednich wierzchołków za pomocą sumowania, a następnie zastosowania wielowarstwowego perceptronu (MLP). Pozwala to sieci lepiej rozróżniać struktury grafów w porównaniu z innymi metodami agregacji (np. średnią).

Przykład formuły aktualizacji cech wierzchołka v:

h_v^{(k)} = MLP^{(k)} \left( (1 + \epsilon^{(k)}) \cdot h_v^{(k-1)} + \sum_{u \in N(v)} h_u^{(k-1)} \right)

gdzie:

• (h_v^{(k)}) to cechy wierzchołka v na warstwie k,
• (N(v)) to zbiór sąsiadów wierzchołka v,
• (\epsilon^{(k)}) to uczony parametr,
• MLP to wielowarstwowy perceptron.

W związku z tym, GIN jest skuteczny w zadaniach, gdzie ważne jest rozróżnianie subtelnych różnic strukturalnych między grafami.