Les réseaux de neurones graphiques (GNN) sont devenus la boîte à outils standard pour apprendre à partir des données graphiques. Les GNN sont capables d'apporter des améliorations pour des problèmes à fort impact dans différents domaines, tels que la recommandation de contenu ou la découverte de médicaments. Contrairement à d'autres types de données tels que les images, l'apprentissage à partir de données graphiques nécessite des méthodes spécifiques. Tel que défini par Michel Bronstein:
[..] ces méthodes sont basées sur une certaine forme de message passant sur le graphe permettant à différents nœuds d'échanger des informations.
Pour accomplir des tâches spécifiques sur les graphes (classification des nœuds, prédiction de liens, etc.), une couche GNN calcule les représentations des nœuds et des arêtes via ce que l'on appelle diffusion récursive de quartier (ou message passant). Selon ce principe, chaque nœud de graphe reçoit et agrège les caractéristiques de ses voisins afin de représenter la structure locale du graphe: différents types de couches GNN exécutent diverses stratégies d'agrégation.
Les formulations les plus simples de la couche GNN, telles que Graph Convolutional Networks (GCNs) ou GraphSage, exécutent une agrégation isotrope, où chaque voisin contribue également à mettre à jour la représentation du nœud central. Ce billet de blog présente une mini-série (2 articles) dédiée à l'analyse des Graph Attention Networks (GAT), qui définissent une opération d'anisotropie dans la diffusion récursive de voisinage. En exploitant le paradigme de l'anisotropie, la capacité d'apprentissage est améliorée par le mécanisme d'attention, qui attribue une importance différente à la contribution de chaque voisin.
Cet échauffement est basé sur les détails GAT rapportés par la bibliothèque Deep Graph site de NDN Collective.
Avant de comprendre le comportement de la couche GAT, récapitulons les calculs derrière l'agrégation effectuée par la couche GCN.
GCN Layer - Fonction d'agrégation
N est l'ensemble des voisins à un saut du nœud i. Ce nœud pourrait également être inclus parmi les voisins en ajoutant une auto-boucle.
c est une constante de normalisation basée sur la structure du graphe, qui définit un calcul de moyenne isotrope.
σ est une fonction d'activation, qui introduit la non-linéarité dans la transformation.
W est la matrice de poids des paramètres apprenables adoptée pour la transformation d'entités.
La couche GAT étend la fonction d'agrégation de base de la couche GCN, en attribuant une importance différente à chaque bord via les coefficients d'attention.
Équations de couche GAT
Équation (1) est une transformation linéaire de l'incorporation de la couche inférieure salut, ainsi que W est sa matrice de poids apprenable. Cette transformation permet d'obtenir une puissance expressive suffisante pour transformer les caractéristiques d'entrée en caractéristiques de haut niveau et denses.
Équation (2) calcule un score d'attention non normalisé par paire entre deux voisins. Ici, il concatène d'abord le z plongements des deux nœuds, où || désigne la concaténation. Ensuite, il faut un produit scalaire d'une telle concaténation et un vecteur de poids apprenable a. En fin de compte, un LeakyReLU est appliqué au résultat du produit scalaire. Le score d'attention indique l'importance d'un nœud voisin dans le cadre de transmission de messages.
Équation (3) applique un softmax pour normaliser les scores d'attention sur les bords entrants de chaque nœud. Le softmax encode la sortie de l'étape précédente dans une distribution de probabilité. En conséquence, les scores d'attention sont beaucoup plus comparables entre les différents nœuds.
Équation (4) est similaire à l'agrégation GCN (voir l'équation au début de la section). Les plongements des voisins sont agrégés ensemble, mis à l'échelle par les scores d'attention. La principale conséquence de ce processus de mise à l'échelle est d'apprendre une contribution différente de chaque nœud de voisinage.
Implémentation NumPy
La première étape consiste à préparer les ingrédients (matrices) pour représenter un graphique simple et effectuer la transformation linéaire.
Code NumPy
print('nn----- One-hot vector representation of nodes. Shape(n,n)n')
X = np.eye(5, 5)
n = X.shape[0]
np.random.shuffle(X)
print(X) print('nn----- Embedding dimensionn')
emb = 3
print(emb) print('nn----- Weight Matrix. Shape(emb, n)n')
W = np.random.uniform(-np.sqrt(1. / emb), np.sqrt(1. / emb), (emb, n))
print(W) print('nn----- Adjacency Matrix (undirected graph). Shape(n,n)n')
A = np.random.randint(2, size=(n, n))
np.fill_diagonal(A, 1) A = (A + A.T)
A[A > 1] = 1
print(A)
La première matrice définit une représentation codée à chaud des nœuds (le nœud 1 est indiqué en gras). Ensuite, nous définissons une matrice de poids, en exploitant la dimension d'intégration définie. J'ai mis en évidence le vecteur de la 3e colonne de W car, comme vous le verrez sous peu, ce vecteur définit la représentation mise à jour du nœud 1 (une valeur 1 est initialisée en 3ème position). Nous pouvons effectuer la transformation linéaire pour obtenir une puissance expressive suffisante pour les caractéristiques des nœuds à partir de ces ingrédients. Cette étape vise à transformer les entités d'entrée (encodées à chaud) en une représentation basse et dense.
L'opération suivante consiste à introduire les coefficients d'auto-attention pour chaque arête. Nous concaténons la représentation du nœud source et la représentation du nœud de destination pour représenter les arêtes. Ce processus de concaténation est activé par la matrice de contiguïté A, qui définit les relations entre tous les nœuds du graphe.
Couche GAT (équation 2)
Code NumPy
# equation (2) - First part
print('nn----- Concat hidden features to represent edges. Shape(len(emb.concat(emb)), number of edges)n')
edge_coords = np.where(A==1)
h_src_nodes = z1[edge_coords[0]]
h_dst_nodes = z1[edge_coords[1]]
z2 = np.concatenate((h_src_nodes, h_dst_nodes), axis=1)
Dans le bloc précédent, j'ai mis en évidence les 4 lignes représentant les 4 bords entrants connectés au nœud 1. Les 3 premiers éléments de chaque ligne définissent la représentation d'incorporation des voisins du nœud 1, tandis que les 3 autres éléments de chaque ligne définissent les plongements de le nœud 1 lui-même (comme vous pouvez le remarquer, la première ligne encode une auto-boucle).
Après cette opération, nous pouvons introduire les coefficients d'attention et les multiplier par la représentation d'arête, issue du processus de concaténation. Enfin, la fonction Leaky Relu est appliquée à la sortie de ce produit.
Code NumPy
# equation (2) - Second part
print('nn----- Attention coefficients. Shape(1, len(emb.concat(emb)))n')
att = np.random.rand(1, z2.shape[1])
print(att) print('nn----- Edge representations combined with the attention coefficients. Shape(1, number of edges)n')
z2_att = z2.dot(att.T)
print(z2_att) print('nn----- Leaky Relu. Shape(1, number of edges)')
e = leaky_relu(z2_att)
print(e)
À la fin de ce processus, nous avons obtenu un score différent pour chaque bord du graphique. Dans le bloc supérieur, j'ai mis en évidence l'évolution du coefficient associé à la première arête. Ensuite, pour rendre le coefficient facilement comparable entre différents nœuds, une fonction softmax est appliquée aux contributions de tous les voisins pour chaque nœud de destination.
Pour interpréter la signification de la dernière matrice définissant les scores de bord normalisés, récapitulons le contenu de la matrice de contiguïté.
Comme vous pouvez le voir, au lieu d'avoir 1 valeurs pour définir les arêtes, nous avons redimensionné la contribution de chaque voisin. La dernière étape consiste à calculer l'agrégation de voisinage: les plongements des voisins sont incorporés dans le nœud de destination, mis à l'échelle par les scores d'attention.
Dans le futur article, je décrirai les mécanismes derrière la couche GAT multi-têtes, et nous verrons quelques applications pour la tâche de prédiction de lien.
Bibliographie
La version en cours d'exécution du code est disponible dans les éléments suivants cahier. Vous trouverez également une implémentation DGL, utile pour vérifier l'exactitude de l'implémentation.
L'article original sur les réseaux d'attention graphique de Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, Yoshua Bengiois disponible sur arXiv.
Pour une explication approfondie du sujet, je suggère également la vidéo de Aleksa Gordic.
Cet article a été publié initialement le Vers la science des données et republié sur TOPBOTS avec la permission de l'auteur.
Profitez de cet article? Inscrivez-vous pour plus de mises à jour de l'IA.
Nous vous informerons lorsque nous publierons plus de formation technique.
