In den letzten Jahren hat das Teilgebiet des Maschinellen Lernens, das sich mit Graphdaten beschäftigt, durch die Entwicklung von spezialisierten Graph-Neuronalen Netzen (GNNs) mit mathematischer Begründung in der spektralen Graphtheorie große Sprünge nach vorn gemacht. Zusätzlich zu natürlichen Graphdaten können diese Methoden auch auf Datensätze ohne Graphen angewendet werden, indem man einen Graphen künstlich mithilfe eines definierten Adjazenzbegriffs zwischen den Samplen konstruiert. Nach dem neueste Stand der Technik wird jedes Sample mit einer geringen Anzahl an Nachbarn verknüpft, um gleichzeitig das dünnbesetzte Verhalten natürlicher Graphen nachzuahmen, die Stärken bestehender GNN-Methoden auszunutzen und quadratische Abhängigkeit von der Knotenanzahl zu verhinden, welche diesen Ansatz für große Datensätze unbrauchbar machen würde. Die vorliegende Arbeit beleuchtet die alternative Konstruktion von vollbesetzten Graphen basierend auf Kernel-Funktionen. Dabei quantifizieren die Verknüpfungen eines jeden Samples explizit die Ähnlichkeit zu allen anderen Samplen. Deshalb enthält der Graph eine quadratische Anzahl an Kanten, die die lokalen und nicht-lokalen Nachbarschaftsinformationen beschreiben. Obwohl dieser Ansatz in anderen Kontexten wie der Lösung partieller Differentialgleichungen ausgiebig untersucht wurde, wird er im Maschinellen Lernen heutzutage meist wegen der dichtbesetzten Adjazenzmatrizen als unbrauchbar empfunden. Aus diesem Grund behandelt ein großer Teil dieser Arbeit numerische Techniken für schnelle Auswertungen, insbesondere Eigenwertberechnungen, in wichtigen Spezialfällen, bei denen die Samples durch niedrigdimensionale Vektoren (wie z.B. in dreidimensionalen Punktwolken) oder durch kategoriale Attribute beschrieben werden. Weiterhin wird untersucht, wie diese dichtbesetzten Adjazenzinformationen in Lernsituationen auf Graphen benutzt werden können. Es wird eine eigene transduktive Lernmethode vorgeschlagen und präsentiert, eine Version eines Graph Convolutional Networks (GCN), das auf die spektralen und räumlichen Eigenschaften von dichtbesetzten Graphen abgestimmt ist. Schließlich wird die Anwendung von Kernel-basierten Adjazenzmatrizen in der Beschleunigung der erfolgreichen Architektur “PointNet++” umrissen. Im Verlauf der Arbeit werden die Methoden in ausführlichen numerischen Experimenten evaluiert. Zusätzlich zu der empirischen Genauigkeit der Neuronalen Netze liegt der Fokus auf wettbewerbsfähigen Laufzeiten, um die Berechnungs- und Energiekosten der Methoden zu reduzieren. / Over the past few years, graph learning - the subdomain of machine learning on graph data - has taken big leaps forward through the development of specialized Graph Neural Networks (GNNs) that have mathematical foundations in spectral graph theory. In addition to natural graph data, these methods can be applied to non-graph data sets by constructing a graph artificially using a predefined notion of adjacency between samples. The state of the art is to only connect each sample to a low number of neighbors in order to simultaneously mimic the sparse behavior of natural graphs, play into the strengths of existing GNN methods, and avoid quadratic scaling in the number of nodes that would make the approach infeasible for large problem sizes. In this thesis, we shine light on the alternative construction of kernel-based fully-connected graphs. Here the connections of each sample explicitly quantify the similarities to all other samples. Hence the graph contains a quadratic number of edges which encode local and non-local neighborhood information. Though this approach is well studied in other settings including the solution of partial differential equations, it is typically dismissed in machine learning nowadays because of its dense adjacency matrices. We thus dedicate a large portion of this work to showcasing numerical techniques for fast evaluations, especially eigenvalue computations, in important special cases where samples are described by low-dimensional feature vectors (e.g., three-dimensional point clouds) or by a small set of categorial attributes. We then continue to investigate how this dense adjacency information can be utilized in graph learning settings. In particular, we present our own proposed transductive learning method, a version of a Graph Convolutional Network (GCN) designed towards the spectral and spatial properties of dense graphs. We furthermore outline the application of kernel-based adjacency matrices in the speedup of the successful PointNet++ architecture. Throughout this work, we evaluate our methods in extensive numerical experiments. In addition to the empirical accuracy of our neural network tasks, we focus on competitive runtimes in order to decrease the computational and energy cost of our methods.

The core research of this thesis, mostly comprising chapter four, has been accepted to the Learning on Graphs (LoG) 2022 conference for a spotlight presentation as a standalone paper, under the title "Taxonomy of Benchmarks in Graph Representation Learning", and is to be published in the Proceedings of Machine Learning Research (PMLR) series. As a main author of the paper, my specific contributions to this paper cover problem formulation, design and implementation of our taxonomy framework and experimental pipeline, collation of our results and of course the writing of the article. / L'apprentissage profond sur les graphes a atteint des niveaux de succès sans précédent ces dernières années grâce aux réseaux de neurones de graphes (GNN), des architectures de réseaux de neurones spécialisées qui ont sans équivoque surpassé les approches antérieurs d'apprentissage définies sur des graphes. Les GNN étendent le succès des réseaux de neurones aux données structurées en graphes en tenant compte de leur géométrie intrinsèque. Bien que des recherches approfondies aient été effectuées sur le développement de GNN avec des performances supérieures à celles des modèles références d'apprentissage de représentation graphique, les procédures d'analyse comparative actuelles sont insuffisantes pour fournir des évaluations justes et efficaces des modèles GNN. Le problème peut-être le plus répandu et en même temps le moins compris en ce qui concerne l'analyse comparative des graphiques est la "couverture de domaine": malgré le nombre croissant d'ensembles de données graphiques disponibles, la plupart d'entre eux ne fournissent pas d'informations supplémentaires et au contraire renforcent les biais potentiellement nuisibles dans le développement d’un modèle GNN. Ce problème provient d'un manque de compréhension en ce qui concerne les aspects d'un modèle donné qui sont sondés par les ensembles de données de graphes. Par exemple, dans quelle mesure testent-ils la capacité d'un modèle à tirer parti de la structure du graphe par rapport aux fonctionnalités des nœuds? Ici, nous développons une approche fondée sur des principes pour taxonomiser les ensembles de données d'analyse comparative selon un "profil de sensibilité" qui est basé sur la quantité de changement de performance du GNN en raison d'une collection de perturbations graphiques. Notre analyse basée sur les données permet de mieux comprendre quelles caractéristiques des données de référence sont exploitées par les GNN. Par conséquent, notre taxonomie peut aider à la sélection et au développement de repères graphiques adéquats et à une évaluation mieux informée des futures méthodes GNN. Enfin, notre approche et notre implémentation dans le package GTaxoGym (https://github.com/G-Taxonomy-Workgroup/GTaxoGym) sont extensibles à plusieurs types de tâches de prédiction de graphes et à des futurs ensembles de données. / Deep learning on graphs has attained unprecedented levels of success in recent years thanks to Graph Neural Networks (GNNs), specialized neural network architectures that have unequivocally surpassed prior graph learning approaches. GNNs extend the success of neural networks to graph-structured data by accounting for their intrinsic geometry. While extensive research has been done on developing GNNs with superior performance according to a collection of graph representation learning benchmarks, current benchmarking procedures are insufficient to provide fair and effective evaluations of GNN models. Perhaps the most prevalent and at the same time least understood problem with respect to graph benchmarking is "domain coverage": Despite the growing number of available graph datasets, most of them do not provide additional insights and on the contrary reinforce potentially harmful biases in GNN model development. This problem stems from a lack of understanding with respect to what aspects of a given model are probed by graph datasets. For example, to what extent do they test the ability of a model to leverage graph structure vs. node features? Here, we develop a principled approach to taxonomize benchmarking datasets according to a "sensitivity profile" that is based on how much GNN performance changes due to a collection of graph perturbations. Our data-driven analysis provides a deeper understanding of which benchmarking data characteristics are leveraged by GNNs. Consequently, our taxonomy can aid in selection and development of adequate graph benchmarks, and better informed evaluation of future GNN methods. Finally, our approach and implementation in the GTaxoGym package (https://github.com/G-Taxonomy-Workgroup/GTaxoGym) are extendable to multiple graph prediction task types and future datasets.

La géométrie moléculaire, également connue sous le nom de conformation, est la représentation la plus intrinsèque et la plus informative des molécules. Cependant, prédire des conformations stables à partir de graphes moléculaires reste un problème difficile et fondamental en chimie et en biologie computationnelles. Les méthodes expérimentales et computationelles traditionnelles sont généralement coûteuses et chronophages. Récemment, nous avons assisté à des progrès considérables dans l'utilisation de l'apprentissage automatique, en particulier des modèles génératifs, pour accélérer cette procédure. Cependant, les approches actuelles basées sur les données n'ont généralement pas la capacité de modéliser des distributions complexes et ne tiennent pas compte de caractéristiques géométriques importantes. Dans cette thèse, nous cherchons à construire des modèles génératifs basés sur des principes pour la génération de conformation moléculaire qui peuvent surmonter les problèmes ci-dessus. Plus précisément, nous avons proposé des modèles de diffusion basés sur les flux, sur l'énergie et de débruitage pour la génération de structures moléculaires. Cependant, il n'est pas trivial d'appliquer ces modèles à cette tâche où la vraisemblance des géométries devrait avoir la propriété importante d'invariance par rotation par de translation. Inspirés par les progrès récents de l'apprentissage des représentations géométriques, nous fournissons à la fois une justification théorique et une mise en œuvre pratique sur la manière d'imposer cette propriété aux modèles. Des expériences approfondies sur des jeux de données de référence démontrent l'efficacité de nos approches proposées par rapport aux méthodes de référence existantes. / Molecular geometry, also known as conformation, is the most intrinsic and informative representation of molecules. However, predicting stable conformations from molecular graphs remains a challenging and fundamental problem in computational chemistry and biology. Traditional experimental and computational methods are usually expensive and time-consuming. Recently, we have witnessed considerable progress in using machine learning, especially generative models, to accelerate this procedure. However, current data-driven approaches usually lack the capacity for modeling complex distributions and fail to take important geometric features into account. In this thesis, we seek to build principled generative models for molecular conformation generation that can overcome the above problems. Specifically, we proposed flow-based, energy-based, and denoising diffusion models for molecular structure generation. However, it's nontrivial to apply these models to this task where the likelihood of the geometries should have the important property of rotational and translation invariance. Inspired by the recent progress of geometric representation learning, we provide both theoretical justification and practical implementation about how to impose this property into the models. Extensive experiments on common benchmark datasets demonstrate the effectiveness of our proposed approaches over existing baseline methods.

L'intelligence artificielle (IA) moderne a ouvert de nouvelles perspectives prometteuses pour la création de robots intelligents. En particulier, les architectures d'apprentissage basées sur le gradient (réseaux neuronaux profonds) ont considérablement amélioré la compréhension des scènes 3D en termes de perception, de raisonnement et d'action. Cependant, ces progrès ont affaibli l'attrait de nombreuses techniques ``classiques'' développées au cours des dernières décennies. Nous postulons qu'un mélange de méthodes ``classiques'' et ``apprises'' est la voie la plus prometteuse pour développer des modèles du monde flexibles, interprétables et exploitables : une nécessité pour les agents intelligents incorporés. La question centrale de cette thèse est : ``Quelle est la manière idéale de combiner les techniques classiques avec des architectures d'apprentissage basées sur le gradient pour une compréhension riche du monde 3D ?''. Cette vision ouvre la voie à une multitude d'applications qui ont un impact fondamental sur la façon dont les agents physiques perçoivent et interagissent avec leur environnement. Cette thèse, appelée ``programmes différentiables pour modèler l'environnement'', unifie les efforts de plusieurs domaines étroitement liés mais actuellement disjoints, notamment la robotique, la vision par ordinateur, l'infographie et l'IA. Ma première contribution---gradSLAM--- est un système de localisation et de cartographie simultanées (SLAM) dense et entièrement différentiable. En permettant le calcul du gradient à travers des composants autrement non différentiables tels que l'optimisation non linéaire par moindres carrés, le raycasting, l'odométrie visuelle et la cartographie dense, gradSLAM ouvre de nouvelles voies pour intégrer la reconstruction 3D classique et l'apprentissage profond. Ma deuxième contribution - taskography - propose une sparsification conditionnée par la tâche de grandes scènes 3D encodées sous forme de graphes de scènes 3D. Cela permet aux planificateurs classiques d'égaler (et de surpasser) les planificateurs de pointe basés sur l'apprentissage en concentrant le calcul sur les attributs de la scène pertinents pour la tâche. Ma troisième et dernière contribution---gradSim--- est un simulateur entièrement différentiable qui combine des moteurs physiques et graphiques différentiables pour permettre l'estimation des paramètres physiques et le contrôle visuomoteur, uniquement à partir de vidéos ou d'une image fixe. / Modern artificial intelligence (AI) has created exciting new opportunities for building intelligent robots. In particular, gradient-based learning architectures (deep neural networks) have tremendously improved 3D scene understanding in terms of perception, reasoning, and action. However, these advancements have undermined many ``classical'' techniques developed over the last few decades. We postulate that a blend of ``classical'' and ``learned'' methods is the most promising path to developing flexible, interpretable, and actionable models of the world: a necessity for intelligent embodied agents. ``What is the ideal way to combine classical techniques with gradient-based learning architectures for a rich understanding of the 3D world?'' is the central question in this dissertation. This understanding enables a multitude of applications that fundamentally impact how embodied agents perceive and interact with their environment. This dissertation, dubbed ``differentiable world programs'', unifies efforts from multiple closely-related but currently-disjoint fields including robotics, computer vision, computer graphics, and AI. Our first contribution---gradSLAM---is a fully differentiable dense simultaneous localization and mapping (SLAM) system. By enabling gradient computation through otherwise non-differentiable components such as nonlinear least squares optimization, ray casting, visual odometry, and dense mapping, gradSLAM opens up new avenues for integrating classical 3D reconstruction and deep learning. Our second contribution---taskography---proposes a task-conditioned sparsification of large 3D scenes encoded as 3D scene graphs. This enables classical planners to match (and surpass) state-of-the-art learning-based planners by focusing computation on task-relevant scene attributes. Our third and final contribution---gradSim---is a fully differentiable simulator that composes differentiable physics and graphics engines to enable physical parameter estimation and visuomotor control, solely from videos or a still image.

<p dir="ltr">The rapid development of machine learning techniques makes it possible to manipulate or synthesize video and audio information while introducing nearly indetectable artifacts. Most media forensics methods analyze the high-level data (e.g., pixels from videos, temporal signals from audios) decoded from compressed media data. Since media manipulation or synthesis methods usually aim to improve the quality of such high-level data directly, acquiring forensic evidence from these data has become increasingly challenging. In this work, we focus on media forensics techniques using the metadata in media formats, which includes container metadata and coding parameters in the encoded bitstream. Since many media manipulation and synthesis methods do not attempt to hide metadata traces, it is possible to use them for forensics tasks. First, we present a video forensics technique using metadata embedded in MP4/MOV video containers. Our proposed method achieved high performance in video manipulation detection, source device attribution, social media attribution, and manipulation tool identification on publicly available datasets. Second, we present a transformer neural network based MP3 audio forensics technique using low-level codec information. Our proposed method can localize multiple compressed segments in MP3 files. The localization accuracy of our proposed method is higher compared to other methods. Third, we present an H.264-based video device matching method. This method can determine if the two video sequences are captured by the same device even if the method has never encountered the device. Our proposed method achieved good performance in a three-fold cross validation scheme on a publicly available video forensics dataset containing 35 devices. Fourth, we present a Graph Neural Network (GNN) based approach for the analysis of MP4/MOV metadata trees. The proposed method is trained using Self-Supervised Learning (SSL), which increased the robustness of the proposed method and makes it capable of handling missing/unseen data. Fifth, we present an efficient approach to compute the spectrogram feature with MP3 compressed audio signals. The proposed approach decreases the complexity of speech feature computation by ~77.6% and saves ~37.87% of MP3 decoding time. The resulting spectrogram features lead to higher synthetic speech detection performance.</p>

Accurate estimation of voltage drop (IR drop), in Application-Specific Integrated Circuits (ASICs) is a critical challenge, which impacts their performance and power consumption. As technology advances and die sizes shrink, predicting IR drop fast and accurate becomes increasingly challenging. This thesis focuses on exploring the application of Machine Learning (ML) algorithms, including Extreme Gradient Boosting (XGBoost), Convolutional Neural Network (CNN) and Graph Neural Network (GNN), to address this problem. Traditional methods of estimating IR drop using commercial tools are time consuming, especially for complex designs with millions of transistors. To overcome that, ML algorithms are investigated for their ability to provide fast and accurate IR drop estimation. This thesis utilizes electrical, timing and physical features of the ASIC design as input to train the ML models. The scalability of the selected features allows for their effective application across various ASIC designs with very few adjustments. Experimental results demonstrate the advantages of ML models over commercial tools, offering significant improvements in prediction speed. Notably, GNNs, such as Graph Convolutional Network (GCN) models showed promising performance with low prediction errors in voltage drop estimation. The incorporation of graph-structures models opens new fields of research for accurate IR drop prediction. The conclusions drawn emphasize the effectiveness of ML algorithms in accurately estimating IR drop, thereby optimizing ASIC design efficiency. The application of ML models enables faster predictions and noticeably reducing calculation time. This contributes to enhancing energy efficiency and minimizing environmental impact through optimised power circuits. Future work can focus on exploring the scalability of the models by training on a smaller portion of the circuit and extrapolating predictions to the entire design seems promising for more efficient and accurate IR drop estimation in complex ASIC designs. These advantages present new opportunities in the field and extend the capabilities of ML algorithms in the task of IR drop prediction. / Noggrann uppskattning av spänningsfallet (IR-fall), i ASIC är en kritisk utmaning som påverkar deras prestanda och strömförbrukning. När tekniken går framåt och formstorlekarna krymper, blir det allt svårare att förutsäga IR-fall snabbt och exakt. Denna avhandling fokuserar på att utforska tillämpningen av ML-algoritmer, inklusive XGBoost, CNN och GNN, för att lösa detta problem. Traditionella metoder för att uppskatta IR-fall med kommersiella verktyg är tidskrävande, särskilt för komplexa konstruktioner med miljontals transistorer. För att övervinna det undersöks ML-algoritmer för deras förmåga att ge snabb och exakt IR-falluppskattning. Denna avhandling använder elektriska, timing och fysiska egenskaper hos ASIC-designen som input för att träna ML-modellerna. Skalbarheten hos de valda funktionerna möjliggör deras effektiva tillämpning över olika ASIC-designer med mycket få justeringar. Experimentella resultat visar fördelarna med ML-modeller jämfört med kommersiella verktyg, och erbjuder betydande förbättringar i förutsägelsehastighet. Noterbart är att GNNs, såsom GCN-modeller, visade lovande prestanda med låga prediktionsfel vid uppskattning av spänningsfall. Införandet av grafstrukturmodeller öppnar nya forskningsfält för exakt IRfallförutsägelse. De slutsatser som dras betonar effektiviteten hos MLalgoritmer för att noggrant uppskatta IR-fall, och därigenom optimera ASICdesigneffektiviteten. Tillämpningen av ML-modeller möjliggör snabbare förutsägelser och märkbart minskad beräkningstid. Detta bidrar till att förbättra energieffektiviteten och minimera miljöpåverkan genom optimerade kraftkretsar. Framtida arbete kan fokusera på att utforska skalbarheten hos modellerna genom att träna på en mindre del av kretsen och att extrapolera förutsägelser till hela designen verkar lovande för mer effektiv och exakt IR-falluppskattning i komplexa ASIC-designer. Dessa fördelar ger nya möjligheter inom området och utökar kapaciteten hos ML-algoritmer i uppgiften att förutsäga IR-fall.

With the arrival of 5G networks, telecommunication systems are becoming more intelligent, integrated, and broadly used. This thesis focuses on predicting the upcoming traffic to efficiently promote resource allocation, guarantee stability and reliability of the network. Since networks modeled as graphs potentially capture more information than tabular data, the construction of the graph and choice of the model are key to achieve a good prediction. In this thesis traffic prediction is based on a time-evolving graph, whose node and edges encode the structure and activity of the system. Edges are created by dynamic time-warping (DTW), geographical distance, and $k$-nearest neighbors. The node features contain different temporal information together with spatial information computed by methods from topological data analysis (TDA). To capture the temporal and spatial dependency of the graph several dynamic graph methods are compared. Throughout experiments, we could observe that the most successful model GConvGRU performs best for edges created by DTW and node features that include temporal information across multiple time steps. / Med ankomsten av 5G nätverk blir telekommunikationssystemen alltmer intelligenta, integrerade, och bredare använda. Denna uppsats fokuserar på att förutse den kommande nättrafiken, för att effektivt hantera resursallokering, garantera stabilitet och pålitlighet av nätverken. Eftersom nätverk som modelleras som grafer har potential att innehålla mer information än tabulär data, är skapandet av grafen och valet av metod viktigt för att uppnå en bra förutsägelse. I denna uppsats är trafikförutsägelsen baserad på grafer som ändras över tid, vars noder och länkar fångar strukturen och aktiviteten av systemet. Länkarna skapas genom dynamisk time warping (DTW), geografisk distans, och $k$-närmaste grannarna. Egenskaperna för noderna består av dynamisk och rumslig information som beräknats av metoder från topologisk dataanalys (TDA). För att inkludera såväl det dynamiska som det rumsliga beroendet av grafen, jämförs flera dynamiska grafmetoder. Genom experiment, kunde vi observera att den mest framgångsrika modellen GConvGRU presterade bäst för länkar skapade genom DTW och noder som innehåller dynamisk information över flera tidssteg.

Real-time prediction of taxi demand in a discrete geographical space is useful as it can minimise service disequilibrium by informing idle drivers of the imbalance, incentivising them to reduce it. This, in turn, can lead to improved efficiency, more stimulating work conditions, and a better customer experience. This study aims to investigate the possibility of utilising an artificial neural network model to make such a prediction for Stockholm. The model was trained on historical demand data and - uniquely - crowd flow data from a cellular provider (aggregated and anonymised). Results showed that the final model could generate very helpful predictions (only off by less than 1 booking on average). External factors - including crowd flow data - had a minor positive impact on performance, but limitations regarding the setup of the zones lead to the study being unable to make a definitive conclusion about whether crowd flow data is effective in improving taxi demand predictors or not. / Prognos av taxiefterfrågan i ett diskret geografiskt utrymme är användbart då det kan minimera obalans mellan utbud och efterfrågan genom att informera lediga taxiförare om obalansen och därmed utjämna den. Detta kan i sin tur leda till förbättrad effektivitet, mer stimulerande arbetsförhållanden och en bättre kundupplevelse. Denna studie ämnar att undersöka möjligheten att använda artificiella neurala nätverk för att göra en sådan prognos för Stockholm. Modellen tränades på historisk data om efterfrågan och - unikt för studien - folkströmsdata (aggregerad och anonymiserad) från en mobiloperatör. Resultaten visade att den slutgiltiga modellen kunde generera användbara prognoser (med ett genomsnittligt prognosfel med mindre än 1 bil per tidsenhet). Externa faktorer – inklusive folkströmsdata – hade en märkbar positiv inverkan på prestandan, men begränsningar rörande framställningen av zonerna ledde till att studien inte kunde dra en definitiv slutsats om huruvida folkströmsdata är effektiva för att förbättra prognoser för taxiefterfrågan eller ej.