Le travail de recherche de cette thèse de doctorat s'inscrit dans le cadre du suivi médical des patients atteints de démences liées à l'âge à l'aide des caméras videos portées par les patients. L'idée est de fournir aux médecins un nouvel outil pour le diagnostic précoce de démences liées à l'âge telles que la maladie d'Alzheimer. Plus précisément, les Activités Instrumentales du Quotidien (IADL: Instrumental Activities of Daily Living en anglais) doivent être indexées automatiquement dans les vidéos enregistrées par un dispositif d'enregistrement portable.Ces vidéos présentent des caractéristiques spécifiques comme de forts mouvements ou de forts changements de luminosité. De plus, la tâche de reconnaissance visée est d'un très haut niveau sémantique. Dans ce contexte difficile, la première étape d'analyse est la définition d'un équivalent à la notion de « plan » dans les contenus vidéos édités. Nous avons ainsi développé une méthode pour le partitionnement d'une vidéo tournée en continu en termes de « points de vue » à partir du mouvement apparent.Pour la reconnaissance des IADL, nous avons développé une solution selon le formalisme des Modèles de Markov Cachés (MMC). Un MMC hiérarchique à deux niveaux a été introduit, modélisant les activités sémantiques ou des états intermédiaires. Un ensemble complexe de descripteurs (dynamiques, statiques, de bas niveau et de niveau intermédiaire) a été exploité et les espaces de description joints optimaux ont été identifiés expérimentalement.Dans le cadre de descripteurs de niveau intermédiaire pour la reconnaissance d'activités nous nous sommes particulièrement intéressés aux objets sémantiques que la personne manipule dans le champ de la caméra. Nous avons proposé un nouveau concept pour la description d'objets ou d'images faisant usage des descripteurs locaux (SURF) et de la structure topologique sous-jacente de graphes locaux. Une approche imbriquée pour la construction des graphes où la même scène peut être décrite par plusieurs niveaux de graphes avec un nombre de nœuds croissant a été introduite. Nous construisons ces graphes par une triangulation de Delaunay sur des points SURF, préservant ainsi les bonnes propriétés des descripteurs locaux c'est-à-dire leur invariance vis-à-vis de transformations affines dans le plan image telles qu'une rotation, une translation ou un changement d'échelle.Nous utilisons ces graphes descripteurs dans le cadre de l'approche Sacs-de-Mots-Visuels. Le problème de définition d'une distance, ou dissimilarité, entre les graphes pour la classification non supervisée et la reconnaissance est nécessairement soulevé. Nous proposons une mesure de dissimilarité par le Noyau Dépendant du Contexte (Context-Dependent Kernel: CDK) proposé par H. Sahbi et montrons sa relation avec la norme classique L2 lors de la comparaison de graphes triviaux (les points SURF).Pour la reconnaissance d'activités par MMC, les expériences sont conduites sur le premier corpus au monde de vidéos avec caméra portée destiné à l'observation des d'IADL et sur des bases de données publiques comme SIVAL et Caltech-101 pour la reconnaissance d'objets. / The research of this PhD thesis is fulfilled in the context of wearable video monitoring of patients with aged dementia. The idea is to provide a new tool to medical practitioners for the early diagnosis of elderly dementia such as the Alzheimer disease. More precisely, Instrumental Activities of Daily Living (IADL) have to be indexed in videos recorded with a wearable recording device.Such videos present specific characteristics i.e. strong motion or strong lighting changes. Furthermore, the tackled recognition task is of a very strong semantics. In this difficult context, the first step of analysis is to define an equivalent to the notion of “shots” in edited videos. We therefore developed a method for partitioning continuous video streams into viewpoints according to the observed motion in the image plane.For the recognition of IADLs we developed a solution based on the formalism of Hidden Markov Models (HMM). A hierarchical HMM with two levels modeling semantic activities or intermediate states has been introduced. A complex set of features (dynamic, static, low-level, mid-level) was proposed and the most effective description spaces were identified experimentally.In the mid-level features for activities recognition we focused on the semantic objects the person manipulates in the camera view. We proposed a new concept for object/image description using local features (SURF) and the underlying semi-local connected graphs. We introduced a nested approach for graphs construction when the same scene can be described by levels of graphs with increasing number of nodes. We build these graphs with Delaunay triangulation on SURF points thus preserving good properties of local features i.e. the invariance with regard to affine transformation of image plane: rotation, translation and zoom.We use the graph features in the Bag-of-Visual-Words framework. The problem of distance or dissimilarity definition between graphs for clustering or recognition is obviously arisen. We propose a dissimilarity measure based on the Context Dependent Kernel of H. Sahbi and show its relation with the classical entry-wise norm when comparing trivial graphs (SURF points).The experiments are conducted on the first corpus in the world of wearable videos of IADL for HMM based activities recognition, and on publicly available academic datasets such as SIVAL and Caltech-101 for object recognition.

Un certain nombre de systèmes dans le monde réel, comprenant des agents interagissant, peut être utilement modélisé par des graphes, où les agents sont représentés par les sommets du graphe et les interactions par les arêtes. De tels systèmes peuvent être aussi divers et complexes que les réseaux sociaux (traditionnels ou virtuels), les réseaux d'interaction protéine-protéine, internet, réseaux de transport et les réseaux de prêts interbancaires. Une question importante qui se pose dans l'étude de ces réseaux est: dans quelle mesure, les statistiques locales d'un réseau déterminent sa topologie globale. Ce problème peut être approché par la construction d'un graphe aléatoire contraint d'avoir les mêmes statistiques locales que celles observées dans le graphe d'intérêt. Le modèle de configuration est un tel modèle de graphe aléatoire conçu de telle sorte qu'un sommet uniformément choisi présente une distribution de degré donnée. Il fournit le cadre sous-jacent à cette thèse. En premier lieu nous considérons un problème de propagation de l'influence sur le modèle de configuration, où chaque sommet peut être influencé par l'un de ses voisins, mais à son tour, il ne peut influencer qu'un sous-ensemble aléatoire de ses voisins. Notre modèle étendu est décrit par le degré total du sommet typique et le nombre de voisins il est capable d'influencer. Nous donnons une condition stricte sur la distribution conjointe de ces deux degrés, qui permet à l'influence de parvenir, avec une forte probabilité, à un ensemble non négligeable de sommets, essentiellement unique, appelé la composante géante influencée, à condition que le sommet de la source soit choisi à partir d'un ensemble de bons pionniers. Nous évaluons explicitement la taille relative asymptotique de la composant géante influencée, ainsi que de l'ensemble des bons pionniers, à condition qu'ils soient non-négligeable. Notre preuve utilise l'exploration conjointe du modèle de configuration et de la propagation de l'influence jusqu'au moment où une grande partie est influencée, une technique introduite dans Janson et Luczak (2008). Notre modèle peut être vu comme une généralisation de la percolation classique par arêtes ou par sites sur le modèle de configuration, avec la différence résultant de la conductivité orientée des arêtes dans notre modèle. Nous illustrons ces résultats en utilisant quelques exemples, en particulier, motivés par le marketing viral - un phénomène connu dans le contexte des réseaux sociaux… / A number of real-world systems consisting of interacting agents can be usefully modelled by graphs, where the agents are represented by the vertices of the graph and the interactions by the edges. Such systems can be as diverse and complex as social networks (traditional or online), protein-protein interaction networks, internet, transport network and inter-bank loan networks. One important question that arises in the study of these networks is: to what extent, the local statistics of a network determine its global topology. This problem can be approached by constructing a random graph constrained to have some of the same local statistics as those observed in the graph of interest. One such random graph model is configuration model, which is constructed in such a way that a uniformly chosen vertex has a given degree distribution. This is the random graph which provides the underlying framework for this thesis. As our first problem, we consider propagation of influence on configuration model, where each vertex can be influenced by any of its neighbours but in its turn, it can only influence a random subset of its neighbours. Our (enhanced) model is described by the total degree of the typical vertex and the number of neighbours it is able to influence. We give a tight condition, involving the joint distribution of these two degrees, which allows with high probability the influence to reach an essentially unique non-negligible set of the vertices, called a big influenced component, provided that the source vertex is chosen from a set of good pioneers. We explicitly evaluate the asymptotic relative size of the influenced component as well as of the set of good pioneers, provided it is non-negligible. Our proof uses the joint exploration of the configuration model and the propagation of the influence up to the time when a big influenced component is completed, a technique introduced in Janson and Luczak (2008). Our model can be seen as a generalization of the classical Bond and Node percolation on configuration model, with the difference stemming from the oriented conductivity of edges in our model. We illustrate these results using a few examples which are interesting from either theoretical or real-world perspective. The examples are, in particular, motivated by the viral marketing phenomenon in the context of social networks...

Lorsqu'un enseignant veut évaluer le savoir-faire des apprenants à l'aide d'un logiciel, il utilise souvent les systèmes Tutoriels Intelligents (STI). Or, les STI sont difficiles à développer et destinés à un domaine pédagogique très ciblé. Depuis plusieurs années, l'utilisation d'algorithmes de classification par apprentissage supervisé a été proposée pour évaluer le savoir des apprenants. Notre hypothèse est que ces mêmes algorithmes vont aussi nous permettre d'évaluer leur savoir-faire. Notre domaine d'application étant l'électronique numérique, nous proposons une mesure de similarité entre schémas électroniques et une bas d'apprentissage générée automatiquement. cette base d'apprentissage est composées de schémas électroniques pédagogiquement étiquetés "bons" ou "mauvais" avec des informations concernant le degré de simplification des erreurs commises. Finalement, l'utilisation d'un algorithme de classification simple (les k plus proches voisins) nous a permis de faire une évaluation des schémas électroniques dans la majorité des cas. / When a teacher wants to evaluate the know-how of the learners using a software, he often uses Intelligent Tutorial Systems (ITS). However, those systems are difficult to develop and intended for a very targeted educational domain. For several years, the used of supervised classification algorithms was proposed to estimate the learners' knowledge. From this fact, we assume that the same kinf of algorithms can help to adress the learners' know-how evaluation. Our application field being digital system design, we propose a similarity measure between digital circuits and instances issued from an automatically generated database. This database consists of electronic circuits pedagogically labelled "good" or "bad" with information concerning the simplification degrees or made mistakes. Finally, the use of a simple classification algorithm (namely k-nearest neighbours classifier) allowed us to achieve a circuit's evaluation in most cases.

Les réseaux sociaux numériques ont pris une place prépondérante dans l'espace informationnel, et sont souvent utilisés pour la publicité, le suivi de réputation, la propagande et même la manipulation, que ce soit par des individus, des entreprises ou des états. Alors que la quantité d'information rend difficile son exploitation par des humains, le besoin reste entier d'analyser un réseau social numérique : il faut dégager des tendances à partir des messages postés dont notamment les opinions échangées, qualifier les comportements des utilisateurs, et identifier les structures sociales émergentes.Pour résoudre ce problème, nous proposons un système d'analyse en trois niveaux. Tout d'abord, l'analyse du message vise à en déterminer l'opinion. Ensuite, la caractérisation et l'évaluation des comptes utilisateurs est réalisée grâce à une étape de profilage comportemental et à l'étude de leur importance et de leur position dans des graphes sociaux, dans lesquels nous combinons les mesures topologiques d'importance des noeuds dans un graphe avec les statistiques d'engagement, par exemple en nombre d'abonnés. Enfin, le système procède à la détection et à l'évaluation de communautés d'utilisateurs, pour lesquelles nous introduisons des scores de cohésion thématique qui complètent les mesures topologiques classiques de qualité structurelle des communautés détectées. Nous appliquons ce système d'analyse sur deux corpus provenant de deux médias sociaux différents : le premier est constitué de messages publiés sur Twitter, représentant toutes les activités réalisées par 5 000 comptes liés entre eux sur une longue période. Le second provient d'un réseau social basé sur TOR, nommé Galaxy2. Nous évaluons la pertinence de notre système sur ces deux jeux de données, montrant la complémentarité des outils de caractérisation des comptes utilisateurs (influence, comportement, rôle) et des communautés de comptes (force d'interaction, cohésion thématique), qui enrichissent l'exploitation du graphe social par les éléments issus des contenus textuels échangés. / Online Social Networks have taken a huge place in the informational space and are often used for advertising, e-reputation, propaganda, or even manipulation, either by individuals, companies or states. The amount of information makes difficult the human exploitation, while the need for social network analysis remains unsatisfied: trends must be extracted from the posted messages, the user behaviours must be characterised, and the social structure must be identified. To tackle this problem, we propose a system providing analysis tools on three levels. First, the message analysis aims to determine the opinions they bear. Then, the characterisation and evaluation of user accounts is performed thanks to the union of a behavioural profiling method, the study of node importance and position in social graphs and engagement and influence measures. Finally the step of user community detection and evaluation is accomplished. For this last challenge, we introduce thematic cohesion scores, completing the topological, graph-based measures for group quality. This system is then applied on two corpora, extracted from two different online social media. The first is constituted of messages published on Twitter, gathering every activity performed by a set of 5,000 accounts on a long period. The second stems from a ToR-based social network, named Galaxy2, and includes every public action performed on the platform during its uptime. We evaluate the relevance of our system on these two datasets, showing the complementarity of user account characterisation tools (influence, behaviour and role), and user account communities (interaction strength, thematic cohesion), enriching the social graph exploitation with textual content elements.

L’opérateur du p-Laplacien non local, l’équation d’évolution et la régularisation variationnelle associées régies par un noyau donné ont des applications dans divers domaines de la science et de l’ingénierie. En particulier, ils sont devenus des outils modernes pour le traitement massif des données (y compris les signaux, les images, la géométrie) et dans les tâches d’apprentissage automatique telles que la classification. En pratique, cependant, ces modèles sont implémentés sous forme discrète (en espace et en temps, ou en espace pour la régularisation variationnelle) comme approximation numérique d’un problème continu, où le noyau est remplacé par la matrice d’adjacence d’un graphe. Pourtant, peu de résultats sur la consistence de ces discrétisations sont disponibles. En particulier, il est largement ouvert de déterminer quand les solutions de l’équation d’évolution ou du problème variationnel des tâches basées sur des graphes convergent (dans un sens approprié) à mesure que le nombre de sommets augmente, vers un objet bien défini dans le domaine continu, et si oui, à quelle vitesse. Dans ce manuscrit, nous posons les bases pour aborder ces questions.En combinant des outils de la théorie des graphes, de l’analyse convexe, de la théorie des semi- groupes non linéaires et des équations d’évolution, nous interprétons rigoureusement la limite continue du problème d’évolution et du problème variationnel du p-Laplacien discrets sur graphes. Plus précisé- ment, nous considérons une suite de graphes (déterministes) convergeant vers un objet connu sous le nom de graphon. Si les problèmes d’évolution et variationnel associés au p-Laplacien continu non local sont discrétisés de manière appropriée sur cette suite de graphes, nous montrons que la suite des solutions des problèmes discrets converge vers la solution du problème continu régi par le graphon, lorsque le nombre de sommets tend vers l’infini. Ce faisant, nous fournissons des bornes d’erreur/consistance.Cela permet à son tour d’établir les taux de convergence pour différents modèles de graphes. En parti- culier, nous mettons en exergue le rôle de la géométrie/régularité des graphons. Pour les séquences de graphes aléatoires, en utilisant des inégalités de déviation (concentration), nous fournissons des taux de convergence nonasymptotiques en probabilité et présentons les différents régimes en fonction de p, de la régularité du graphon et des données initiales. / The non-local p-Laplacian operator, the associated evolution equation and variational regularization, governed by a given kernel, have applications in various areas of science and engineering. In particular, they are modern tools for massive data processing (including signals, images, geometry), and machine learning tasks such as classification. In practice, however, these models are implemented in discrete form (in space and time, or in space for variational regularization) as a numerical approximation to a continuous problem, where the kernel is replaced by an adjacency matrix of a graph. Yet, few results on the consistency of these discretization are available. In particular it is largely open to determine when do the solutions of either the evolution equation or the variational problem of graph-based tasks converge (in an appropriate sense), as the number of vertices increases, to a well-defined object in the continuum setting, and if yes, at which rate. In this manuscript, we lay the foundations to address these questions.Combining tools from graph theory, convex analysis, nonlinear semigroup theory and evolution equa- tions, we give a rigorous interpretation to the continuous limit of the discrete nonlocal p-Laplacian evolution and variational problems on graphs. More specifically, we consider a sequence of (determin- istic) graphs converging to a so-called limit object known as the graphon. If the continuous p-Laplacian evolution and variational problems are properly discretized on this graph sequence, we prove that the solutions of the sequence of discrete problems converge to the solution of the continuous problem governed by the graphon, as the number of graph vertices grows to infinity. Along the way, we provide a consistency/error bounds. In turn, this allows to establish the convergence rates for different graph models. In particular, we highlight the role of the graphon geometry/regularity. For random graph se- quences, using sharp deviation inequalities, we deliver nonasymptotic convergence rates in probability and exhibit the different regimes depending on p, the regularity of the graphon and the initial data.

Dans cette thèse nous étudions un problème fondamental, le partitionnement de graphe, dans le contexte de la croissance rapide des données, le volume des données continues à augmenter, allant des réseaux sociaux à l'internet des objets. En particulier, afin de vaincre les propriétés intraitables existant dans de nombreuses graphies, par exemple, la distribution des degrés en loi de puissance, nous appliquons un nouveau mode pour coupe de sommet, à la place de la méthode traditionnelle (coupe de bord), ainsi que pour assurer une charge de travail équilibrée et raisonnablement dans le traitement de graphe distribué. En outre, pour réduire le coût de communication inter-partitions, nous proposons une méthode de partition de bord basée sur les blocs, qui peut explorer efficacement les structures graphiques sous-jacentes au niveau local. , afin d'optimiser l'exécution de l'algorithme de graphe. Par cette méthode, le temps d'exécution et des communications généraux peuvent être considérablement réduits par rapport aux approches existantes. Les challenges qui se posent dans les grands graphiques comprennent également leur grande variété. Comme nous le savons, la plupart des applications graphiques au monde réel produisent des ensembles de données hétérogènes, dans lesquels les sommets et / ou les arêtes peuvent avoir des différents types ou des différentes étiquettes. De nombreuses algorithmes de fouille de graphes sont également proposés avec beaucoup d'intérêt pour les attributs d'étiquette. Pour cette raison, notre travail est étendu aux graphes de multicouches en prenant en compte la proximité des arêtes et la distribution des étiquettes lors du processus de partitionnement. En fin de cette thèse, Nous démontré à la ses performances exceptionnelles sur les ensembles de données du monde réel. / In this thesis, we mainly focus on a fundamental problem, graph partitioning, in the context of unexpectedly fast growth of data sources, ranging from social networks to internet of things. Particularly, to conquer intractable properties existing in many graphs, e.g. power-law degree distribution, we apply the novel fashion vertex-cut, instead of the traditional edge-cut method, for achieving balanced workload in distributed graph processing. Besides, to reduce the inter-partition communication cost, we present a block-based edge partition method who can efficiently explore the locality underlying graphical structures, to enhance the execution of graph algorithm. With this method, the overhead of both communication and runtime can be decreased greatly, compared to existing approaches. The challenges arising in big graphs also include their high-variety. As we know, most of real life graph applications produce heterogenous datasets, in which the vertices and/or edges are allowed to have different types or labels. A big number of graph mining algorithms are also proposed with much concern for the label attributes. For this reason, our work is extended to multi-layer graphs with taking into account the edges closeness and labels distribution during partitioning process. Its outstanding performance over real-world datasets is demonstrated finally.

Les systèmes d'information sont une cible de plus en plus attractive pour les attaquants. Dans cette thèse de doctorat, nous construisons une méthodologie complète d'analyse statique et dynamique de risque prenant en compte la connaissance à priori d'un système avec les événements dynamiques, afin de proposer des réponses permettant d'empêcher les attaques futures. Tout d'abord, nous étudions comment corriger les attaques potentielles qui peuvent arriver dans un système, en s'appuyant sur les graphes d'attaque logiques. Nous proposons une méthodologie de remédiation corrigeant les chemins d'attaque les plus significatifs. Les remédiations candidates sont classées en fonction de leur coût opérationnel et leur impact sur le système. Les graphes d'attaques ne peuvent pas être directement utilisés pour l'évaluation dynamique de risque. Nous étendons donc ce modèle pour construire des modèles d'analyse dynamique de risque basés sur des réseaux bayésiens. Le modèle hybride d'évaluation de risque se divise en deux modèles complémentaires: (1) Les modèles de corrélation de risque, permettant d'analyser les attaques en cours et fournir les probabilités de compromission des états du système, (2) les modèles d'évaluation du risque futur, permettant évaluer les attaques futures les plus probables. Nous analysons la sensibilité des paramètres probabilistes du modèle et en validons les résultats à partir de graphes d'attaque topologiques / Information systems constitute an increasingly attractive target for attackers. Given the number and complexity of attacks, security teams need to focus their actions, in order to select the most appropriate security controls. Because of the threat posed by advanced multi-step attacks, it is difficult for security operators to fully cover all vulnerabilities when deploying countermeasures. In this PhD thesis, we build a complete framework for static and dynamic risk assessment including prior knowledge on the information system and dynamic events, proposing responses to prevent future attacks. First, we study how to remediate the potential attacks that can happen in a system, using logical attack graphs. We build a remediation methodology to prevent the most relevant attack paths extracted from a logical attack graph. In order to help an operator to choose between several remediation candidates, we rank them according to a cost of remediation combining operational and impact costs. Then, we study the dynamic attacks that can occur in a system. Attack graphs are not directly suited for dynamic risk assessment. Thus, we extend this mode to build dynamic risk assessment models to evaluate the attacks that are the most likely. The hybrid model is subdivided in two complementary models: (1) the first ones analysing ongoing attacks and provide the hosts' compromise probabilities, and (2) the second ones assessing the most likely future attacks. We study the sensitivity of their probabilistic parameters. Finally, we validate the accuracy and usage of both models in the domain of cybersecurity, by building them from a topological attack graph

Dans cette thèse nous avons étudié la diffusion de l'information dans les grands graphes de terrain, en se focalisant sur les patterns structurels de la propagation. Sur le plan empirique, il s'est avéré difficile de capturer la structure des cascades de diffusion en termes de mesures simples. Sur le plan théorique, l'approche classique consiste à étudier des modèles stochastiques de contagion. Néanmoins, l'analyse formelle de ces modèles reste limité, car les graphes de terrain ont généralement une topologie complexe et le processus de diffusion se produit dans une fenêtre de temps limitée. Par conséquent, une meilleure compréhension des données empiriques, des modèles théoriques et du lien entre les deux est également cruciale pour la caractérisation de la diffusion dans les grands graphes de terrain. Après un état de l'art sur les graphes de terrain et la diffusion dans ce contexte au premier chapitre, nous décrivons notre jeu de données et discutons sa pertinence au chapitre 2. Ensuite, dans le chapitre 3, nous évaluons la pertinence du modèle SIR simple et de deux extensions qui prennent en compte des hétérogénéités de notre jeu de données. Dans le chapitre 4, nous explorons la prise en compte du temps dans l'évolution du réseau sous-jacent et dans le modèle de diffusion. Dans le chapitre 5, nous évaluons l'impacte de la structure du graphe sous-jacent sur la structure des cascades de diffusion générées avec les modèles étudiés dans les chapitres précédents. Nous terminons la thèse par un bilan des résultats et des perspectives ouvertes par les travaux menés dans cette thèse. / Understanding information diffusion on complex networks is a key issue from a theoretical and applied perspective. Epidemiology-inspired SIR models have been proposed to model information diffusion. Recent papers have analyzed this question from a data-driven perspective. We complement these findings investigating if epidemic models calibrate with a systematic procedure are capable of reproducing key spreading cascade properties. We first identify a large-scale, rich dataset from which we can reconstruct the diffusion trail and the underlying network. Secondly, we examine the simple SIR model as a baseline model and conclude that it was unable to generate structurally realistic spreading cascades. We found the same result examining model extensions to which take into account heterogeneities observed in the data. In contrast, other models which take into account time patterns available in the data generate qualitatively more similar cascades. Although one key property was not reproduced in any model, this result highlights the importance of taking time patterns into account. We have also analyzed the impact of the underlying network structure on the models examined. In our data the observed cascades were constrained in time, so we could not rely on the theoretical results relating the asymptotic behavior of the epidemic and network topological features. Performing simulations we assessed the impact of these common topological properties in time-bounded epidemic and identified that the distribution of neighbors of seed nodes had the most impact among the investigated properties in our context. We conclude discussing identifying perspectives opened by this work.

La simplification syntaxique, ou slicing, est une technique permettant d’extraire, à partir d’un programme et d’un critère consistant en une ou plusieurs instructions de ce programme, un programme plus simple, appelé slice, ayant le même comportement que le programme initial vis-à-vis de ce critère. Les méthodes d’analyse de code permettent d’établir les propriétés d’un programme. Ces méthodes sont souvent coûteuses, et leur complexité augmente rapidement avec la taille du code. Il serait donc souhaitable d’appliquer ces techniques sur des slices plutôt que sur le programme initial, mais cela nécessite de pouvoir justifier théoriquement l’interprétation des résultats obtenus sur les slices. Cette thèse apporte cette justification pour le cas de la recherche d’erreurs à l’exécution. Dans ce cadre, deux questions se posent. Si une erreur est détectée dans une slice, cela veut-il dire qu’elle se déclenchera aussi dans le programme initial ? Et inversement, si l’absence d’erreurs est prouvée dans une slice, cela veut-il dire que le programme initial en est lui aussi exempt ? Nous modélisons ce problème sur un mini-langage impératif représentatif, autorisant les erreurs et la non-terminaison, et montrons le lien entre la sémantique du programme initial et la sémantique de sa slice, ce qui nous permet de répondre aux deux questions précédentes. Pour généraliser ces résultats, nous nous intéressons à la première brique d’un slicer indépendant du langage : le calcul générique des dépendances de contrôle. Nous formalisons une théorie élégante de dépendances de contrôle sur des graphes orientés finis arbitraires prise dans la littérature et améliorons l’algorithme de calcul proposé.Pour garantir un maximum de confiance dans les résultats, tous ces travaux sont prouvés dans l’assistant de preuve Coq ou dans l’outil de preuve Why3. / Program slicing is a technique that extracts, given a program and a criterion that is one or several instructions in this program, a simpler program, called a slice, that has the same behavior as the initial program with respect to the criterion. Program analysis techniques focus on establishing the properties of a program. These techniques are costly, and their complexity increases with the size of the program. Therefore, it would be interesting to apply these techniques on slices rather than the initial program, but it requires theoretical foundations to interpret the results obtained on the slices. This thesis provides this justification for runtime error detection. In this context, two questions arise. If an error is detected in the slice, does this mean that it can also be triggered in the initial program? On the contrary, if the slice is proved to be error-free, does this mean that the initial program is error-free too? We model this problem using a small representative imperative language containing errors and non-termination, and establish the link between the semantics of the initial program and of its slice, which allows to give a precise answer to the two questions raised above. To apply these results in a more general context, we focus on the first step towards a language-independent slicer: an algorithm computing control dependence. We formalize an elegant theory of control dependence on arbitrary finite directed graphs taken from the literature and improve the proposed algorithm. To ensure a high confidence in the results, we prove them in the Coq proof assistant or in the Why3 proof plateform.

Cette thèse se focalise sur l'analyse de données structurées en graphes, un format de données répandu dans le monde réel. Le raisonnement dans ces données est un enjeu clé en apprentissage automatique, avec des applications allant de la classification de nœuds à la prédiction de liens. On distingue deux approches majeures pour le raisonnement dans les données en graphes : l'apprentissage relationnel statistique et l'apprentissage profond. L'apprentissage relationnel statistique construit des modèles graphiques probabilistes, efficaces pour capturer des dépendances complexes et intégrer des connaissances préexistantes, comme les règles logiques. Des méthodes notables incluent les réseaux logiques de Markov et les champs aléatoires conditionnels. L'apprentissage profond, quant à lui, se base sur l'apprentissage de représentations pertinentes des données observées pour une compréhension et un raisonnement rapides. Les réseaux neuronaux pour graphes (GNN) représentent un outil de pointe dans ce domaine. La combinaison de l'apprentissage relationnel statistique et de l'apprentissage profond offre une perspective enrichie sur le raisonnement, promettant un cadre plus robuste et efficace. Cette thèse explore cette combinaison, en développant des méthodes qui intègrent les deux approches. L'apprentissage profond renforce l'efficacité de l'apprentissage et de l'inférence dans l'apprentissage relationnel statistique, tandis que ce dernier affine les prédictions de l'apprentissage profond. Ce cadre intégré est appliqué à un éventail de tâches de raisonnement sur les graphes, démontrant son efficacité et ouvrant la voie à des recherches futures pour des cadres de raisonnement encore plus robustes. / This thesis centers on the analysis of graph-structured data, a ubiquitous data format in the real world. Reasoning within graph-structured data has long been a fundamental problem in machine learning, with applications spanning from node classification to link prediction. There are two principal approaches to tackle reasoning within graph-structured data: statistical relational learning and deep learning. Statistical relational learning techniques construct probabilistic graphical models based on observed data, excelling at capturing intricate dependencies of available evidence while accommodating prior knowledge, such as logic rules. Notable methods include Markov logic networks (MLNs) and conditional random fields (CRFs). In contrast, deep learning models harness the capability to learn meaningful representations from observed data, using these representations to rapidly comprehend and reason over the data. Graph neural networks (GNNs) have emerged as prominent tools in the realm of deep learning, achieving state-of-the-art results across a spectrum of tasks. Statistical relational learning and deep learning offer distinct perspectives on reasoning. Intuitively, combining these paradigms promises to create a more robust framework that inherits expressive power, efficiency, and the ability to model joint dependencies while simultaneously acquiring representations for more effective reasoning. In pursuit of this vision, this thesis explores the concept, developing methods that seamlessly integrate deep learning and statistical relational learning. Specifically, deep learning enhances the efficiency of learning and inference within statistical relational learning, while statistical relational learning, in turn, refines the predictions generated by deep learning to improve the accuracy. This integrated paradigm is applied across a diverse range of reasoning tasks on graphs. Empirical results demonstrate the effectiveness of this paradigm, encouraging further exploration to yield more robust reasoning frameworks.