SimGNN : Une approche par réseau neuronal pour le calcul rapide de la similarité de graphes
La recherche de similitude de graphes est l'une des applications les plus importantes basées sur les graphes, par exemple, trouver les composés chimiques les plus similaires à un composé de requête. Le calcul de la similitude de graphes, tel que la distance d'édition de graphes (Graph Edit Distance, GED) et le sous-graphe commun maximal (Maximum Common Subgraph, MCS), est l'opération centrale de la recherche de similitude de graphes et d'autres nombreuses applications, mais il est très coûteux en pratique. Inspirés par les récents succès des approches basées sur les réseaux neuronaux dans plusieurs applications liées aux graphes, comme la classification de nœuds ou de graphes, nous proposons une nouvelle approche basée sur les réseaux neuronaux pour résoudre ce problème classique et difficile des graphes, visant à alléger le fardeau computationnel tout en conservant une bonne performance.L'approche proposée, appelée SimGNN, combine deux stratégies. Premièrement, nous concevons une fonction d'embedding apprenable qui mappe chaque graphe dans un vecteur, fournissant ainsi un résumé global du graphe. Un nouveau mécanisme d'attention est proposé pour mettre l'accent sur les nœuds importants en fonction d'une métrique spécifique de similitude. Deuxièmement, nous concevons une méthode de comparaison par paires des nœuds pour compléter les embeddings au niveau du graphe avec des informations détaillées au niveau des nœuds. Notre modèle atteint une meilleure généralisation sur des graphes non vus et, dans le pire des cas, s'exécute en temps quadratique par rapport au nombre de nœuds dans deux graphes.En prenant le calcul de la GED comme exemple, les résultats expérimentaux sur trois jeux de données réels démontrent l'efficacité et l'efficience de notre approche. Plus précisément, notre modèle atteint un taux d'erreur plus faible et une réduction considérable du temps par rapport à une série de méthodes de référence (baselines), y compris plusieurs algorithmes d'approximation pour le calcul de la GED et nombreux modèles existants basés sur les réseaux neuronaux pour les graphes. À notre connaissance, nous sommes parmi les premiers à utiliser des réseaux neuronaux pour modéliser explicitement la similitude entre deux graphes et à offrir une nouvelle direction pour les recherches futures en matière de calcul et recherche de similitude entre graphes.