Le terme « Compositional Reasoning over Graph » (Raisonnement Compositionnel sur Graphe) désigne une approche de résolution de problèmes et d’inférence qui s’appuie sur la décomposition de structures de données graphiques complexes en composants plus simples, l’analyse ou le traitement de ces composants individuellement, puis la combinaison des résultats pour obtenir une solution ou une compréhension globale. Cette approche met l’accent sur la modularité et la manière dont les significations ou les propriétés des éléments constitutifs d’un graphe et leurs interactions contribuent à la signification ou aux propriétés du graphe entier.
Les concepts fondamentaux du raisonnement compositionnel sur graphe reposent sur plusieurs principes essentiels. Au cœur se trouve le principe de compositionnalité, souvent attribué au philosophe Gottlob Frege, qui stipule que la signification d’une expression complexe est déterminée par les significations de ses constituants et par les règles utilisées pour les combiner. Appliqué aux graphes, cela signifie que les propriétés ou la sémantique d’un graphe ou d’un sous-graphe peuvent être inférées à partir des propriétés de ses nœuds, de ses arêtes, et des motifs structurels plus petits qui le composent. Les graphes eux-mêmes, avec leurs nœuds représentant des entités et leurs arêtes représentant des relations, fournissent un formalisme puissant et flexible pour modéliser des systèmes complexes dans divers domaines. La décomposition du problème est un autre pilier, impliquant la segmentation du graphe global ou du problème de raisonnement en sous-graphes ou sous-problèmes plus gérables. Une fois ces unités de base traitées, des opérations de composition spécifiques sont utilisées pour agréger les informations, propager les contraintes ou construire des solutions de plus haut niveau. L’abstraction et la hiérarchie jouent également un rôle crucial, permettant de raisonner à différents niveaux de granularité, où des sous-graphes complexes peuvent être abstraits en nœuds uniques à un niveau supérieur, facilitant ainsi la gestion de la complexité.
L’importance du raisonnement compositionnel sur graphe réside dans sa capacité à améliorer plusieurs aspects des systèmes intelligents. Il contribue de manière significative à l’intelligence artificielle explicable (XAI) en rendant le processus de raisonnement plus transparent et interprétable. En décomposant un problème, il devient plus facile de comprendre comment une conclusion est atteinte, quelles parties du graphe ont contribué à cette conclusion et de quelle manière. Cette approche favorise également la scalabilité ; traiter des graphes massifs de manière monolithique est souvent infaisable, tandis que l’analyse de composants plus petits et la combinaison des résultats peuvent être nettement plus efficaces. De plus, le raisonnement compositionnel est crucial pour la généralisation, en particulier la généralisation hors distribution (out-of-distribution generalization). Les systèmes capables de comprendre et de manipuler des concepts de base de manière compositionnelle peuvent potentiellement gérer des combinaisons inédites de ces concepts, ce qui est une faiblesse majeure de nombreux modèles d’apprentissage profond purement basés sur les données. Son impact se fait sentir dans des domaines variés, allant de la découverte scientifique, où il aide à modéliser des interactions complexes, à l’ingénierie logicielle, où il permet de vérifier la correction de grands systèmes.
Les applications pratiques du raisonnement compositionnel sur graphe sont nombreuses et variées. Dans le traitement du langage naturel (NLP), il est utilisé pour l’analyse sémantique de phrases, où la signification d’une phrase est construite à partir de la signification de ses mots et de la structure syntaxique (souvent représentée comme un graphe de dépendance). Les systèmes de question-réponse peuvent utiliser des graphes de connaissances et raisonner de manière compositionnelle pour trouver des réponses à des questions complexes qui nécessitent de combiner plusieurs éléments d’information. En vision par ordinateur, la reconnaissance de scènes bénéficie de cette approche en identifiant d’abord les objets individuels puis en analysant leurs relations spatiales et contextuelles pour comprendre la scène globale. Par exemple, identifier une « cuisine » implique de reconnaître des objets comme un « réfrigérateur », une « cuisinière », un « évier » et leurs agencements typiques. Dans le domaine de la vérification de logiciels, les propriétés d’un grand programme peuvent être établies en vérifiant les propriétés de ses modules constitutifs et en s’assurant que leur composition respecte les spécifications globales. En biologie des systèmes, l’analyse de réseaux d’interaction protéine-protéine ou de réseaux métaboliques utilise le raisonnement compositionnel pour prédire le comportement de systèmes biologiques complexes à partir des propriétés de leurs composants et de leurs interactions. La découverte de médicaments peut également s’appuyer sur cette approche pour prédire l’efficacité ou la toxicité de nouvelles molécules en composant les effets de leurs différents fragments structuraux ou de leurs cibles biologiques.
Il existe différentes nuances et interprétations du raisonnement compositionnel sur graphe. Les approches peuvent varier considérablement dans leur formalisme sous-jacent. Certaines s’appuient sur des logiques formelles (comme la logique descriptive ou la logique du premier ordre) pour définir les composants et les règles de composition. D’autres utilisent des modèles probabilistes (tels que les réseaux bayésiens graphiques) pour gérer l’incertitude inhérente à la composition d’informations. Plus récemment, les approches basées sur l’apprentissage profond, en particulier les réseaux de neurones graphiques (GNNs), ont été explorées pour apprendre de manière implicite ou explicite des fonctions de composition à partir des données. Cela conduit à une distinction entre les approches purement symboliques, qui manipulent des symboles et des règles explicites, les approches connexionnistes (neuronales), qui apprennent des représentations distribuées, et les approches neuro-symboliques, qui tentent de combiner les forces des deux. Le type de graphe utilisé (par exemple, graphes orientés, non orientés, hétérogènes, dynamiques) influence également la nature du raisonnement. De même, la granularité de la décomposition et de la composition peut varier, allant de la composition de paires de nœuds à l’assemblage de larges modules de graphe.
Plusieurs concepts sont étroitement liés au raisonnement compositionnel sur graphe. La modularité est un concept central, car elle est la prémisse de la décomposition en unités significatives. Le raisonnement hiérarchique est souvent une conséquence ou un outil du raisonnement compositionnel, permettant de construire des abstractions de plus en plus complexes. La décomposition de problème est la stratégie générale qui sous-tend cette approche. Les grammaires de graphes fournissent un formalisme pour définir des règles de production et de transformation de graphes de manière compositionnelle. Les réseaux de neurones graphiques (GNNs) peuvent être conçus pour incorporer des mécanismes de composition, par exemple en utilisant des opérations d’agrégation et de combinaison qui respectent certaines propriétés compositionnelles, ou en étant intégrés dans des architectures neuro-symboliques. L’intelligence artificielle symbolique a longtemps prôné des approches compositionnelles pour la représentation des connaissances et le raisonnement. Inversement, les approches holistiques ou les modèles « end-to-end » purement boîte noire, qui traitent l’entrée dans son intégralité sans décomposition explicite, peuvent être considérés comme antonymiques, bien que la distinction ne soit pas toujours stricte. Le terme « raisonnement modulaire sur graphes » est souvent utilisé de manière quasi-synonyme.
L’idée de compositionnalité trouve ses racines bien avant son application explicite aux graphes en informatique. Elle est fondamentale en philosophie du langage (avec les travaux de Frege sur le principe de compositionnalité du sens), en linguistique (par exemple, les grammaires génératives de Chomsky qui expliquent la productivité du langage par la composition de règles), et en psychologie cognitive (où elle est étudiée dans le contexte de l’apprentissage des concepts et de la résolution de problèmes). En informatique, les principes de modularité et de composition sont apparus très tôt, par exemple dans la programmation structurée, la conception de bases de données relationnelles (où les requêtes complexes sont composées à partir d’opérations plus simples), et la vérification formelle de programmes. L’application spécifique au raisonnement sur graphes s’est développée avec la reconnaissance croissante des graphes comme une structure de données universelle pour modéliser des relations et des systèmes complexes. L’intelligence artificielle symbolique a initialement porté ces idées, mais elles connaissent une renaissance significative avec l’essor de l’apprentissage profond et le développement de modèles neuro-symboliques qui cherchent à combiner la capacité d’apprentissage des réseaux de neurones avec la robustesse et l’interprétabilité du raisonnement symbolique compositionnel.
Le raisonnement compositionnel sur graphe offre de nombreux avantages. Son principal atout est souvent l’amélioration de l’interprétabilité et de l’explicabilité des modèles, car les décisions peuvent être tracées jusqu’aux contributions de composants spécifiques et de leurs interactions. Il favorise la scalabilité en permettant de diviser des problèmes complexes en sous-problèmes plus petits et plus faciles à gérer. La généralisation, en particulier la capacité à gérer des situations nouvelles en recombinant des éléments connus de manière inédite (généralisation systématique ou compositionnelle), est un autre avantage majeur, crucial pour construire des systèmes d’IA plus robustes et adaptables. La modularité inhérente facilite également la réutilisabilité des composants de raisonnement et la maintenance des systèmes. Cependant, cette approche présente aussi des inconvénients et des défis. L’un des défis majeurs est de définir les bonnes primitives de décomposition : comment segmenter un graphe ou un problème de manière significative ? Définir les opérations de composition appropriées peut également s’avérer complexe et dépendre fortement du domaine. Il existe un risque de perte d’information si la décomposition est trop grossière ou si les interactions entre les composants sont trop simplifiées. La gestion de la complexité de l’assemblage des solutions partielles peut elle-même devenir un problème. De plus, tous les problèmes ne sont pas naturellement décomposables ; certains phénomènes complexes présentent des propriétés émergentes qui ne peuvent pas être facilement prédites à partir de l’analyse des seules parties. Apprendre automatiquement des structures compositionnelles à partir des données, intégrer efficacement les connaissances du domaine dans le processus de composition, et gérer l’incertitude qui peut s’accumuler lors de la composition de multiples éléments sont des domaines de recherche actifs. Les limitations incluent donc les situations où la structure du problème est intrinsèquement non compositionnelle ou lorsque la décomposition optimale est inconnue ou trop coûteuse à trouver.