Graphs are powerful data structures that are widely used to represent complex forms of information. One area in which graphs are successfully being used is within compiler engineering, where a program under compilation can be represented as a graph that changes as the program is being compiled. These graphs, known as Intermediate Representation graphs, can be visualized to aid compiler engineers in understanding and debugging the compiler. However, graphs that change over time need to be visualized so that the viewer’s internal understanding of the graph is maintained. Simultaneously, the graph layouts should be of high quality. These criteria can be conflicting, making the visualization of changing graphs difficult. In this thesis, a dynamic graph layout algorithm to visualize dynamic Intermediate Representation graphs used in the C2 compiler in the Java HotSpotTM Virtual Machine was developed and evaluated. Currently, these graphs are visualized with hierarchical layouts, using a static graph layout algorithm. Five metrics were developed and used to evaluate the layouts by the dynamic algorithm against the layouts by the static algorithm. Four of these were concerned with the layout quality, by measuring the number of edge crossings, number of reversed edges, average degree of the edge bends and the average edge length. The fifth metric was related to mental map preservation and measures the Euclidean distance of node displacement across two layouts. Two experiments were conducted to compare the algorithms. The first experiment measured the layouts drawn by the algorithms when there were a couple of nodes added to or removed from a graph iteratively. A total of 1061 layouts were measured. In 74% of these, the dynamic algorithm caused less node displacement. The second experiment aimed to evaluate the algorithms against what is possible to achieve in regards of minimum node displacement while maintaining a high quality. The results of both experiments indicate that the dynamic layout algorithm yields layouts with less node displacement. However, the layouts generally have more reversed edges, more bends in the edges and overall longer edges. These metrics worsened as more iterations of changes were applied. The findings suggest that the dynamic layout algorithm is better at preserving the mental map, but at the cost of the layout quality. / Grafer är kraftfulla datastrukturer som används för att representera komplexa former av information. Ett område där grafer framgångsrikt används är inom kompilatorutveckling, där ett program under kompilering kan representeras som en graf som förändras medan programmet kompileras. Sådana grafer, kända som mellanrepresentationsgrafer, kan visualiseras för att hjälpa kompilatoringenjörer att förstå och felsöka kompilatorn. Dock behöver grafer som ändras över tid visualiseras så att användarens interna förståelse av grafen bibehålls. Samtidigt bör grafens layout vara av hög kvalitet. Dessa kriterier kan vara motsägelsefulla och gör visualiseringen av föränderliga grafer svår. I denna avhandling utvecklades och utvärderades en dynamisk layoutalgoritm för att visualisera dynamiska mellanrepresentationsgrafer som används i C2-kompilatorn i Java HotSpotTM Virtual Machine. Idag visualiseras dessa grafer med hierarkiska layouter som ritas av en statisk layoutalgoritm. Fem mått utvecklades och användes för att jämföra layouterna ritade av den dynamiska algoritmen med layouterna ritade av den statiska algoritmen. Fyra av dessa var relaterade till layoutkvaliteten och mäter antalet korsningar mellan kanter, antalet omvända kanter, den genomsnittliga graden av kantböjningar och den genomsnittliga kantlängden. Det femte måttet är relaterat till bevarandet av den mentala kartan och mätte nodförskjutningen mellan två layouter. Två experiment genomfördes för att jämföra algoritmerna. Det första experimentet mätte layouterna som ritades av algoritmerna när ett par noder lades till eller togs bort från en graf iterativt. Totalt mättes 1061 layouter. I 74% av dessa orsakade den dynamiska algoritmen mindre nodförskjutning. Det andra experimentet syftade till att utvärdera algoritmerna med avseende på minimal nodförskjutning samtidigt som hög kvalitet bibehålls. Resultaten från båda experimenten indikerar att den dynamiska layoutalgoritmen ger layouter med mindre nodförskjutning. Layouterna har dock generellt sett fler omvända kanter, fler böjningar i kanterna och längre kanter. Dessa mått försämrades när fler iterationer av förändringar tillämpades. Resultaten tyder på att den dynamiska layoutalgoritmen är bättre på att bevara den mentala kartan, men på bekostnad av layoutkvaliteten.

We have seen a rapid increase in the development of deep learning algorithms in recent decades. However, while these algorithms have unlocked new business areas and led to great development in many fields, they are usually limited to Euclidean data. Researchers are increasingly starting to find out that they can better represent the data used in many real-life applications as graphs. Examples include high-risk domains such as finding the side effects when combining medicines using a protein-protein network. In high-risk domains, there is a need for trust and transparency in the results returned by deep learning algorithms. In this work, we explore how we can quantify uncertainty in Graph Neural Network predictions using conventional methods for conformal prediction as well as novel methods exploiting graph connectivity information. We evaluate the methods on both static and dynamic graphs and find that neither of the novel methods offers any clear benefits over the conventional methods. However, we see indications that using the graph connectivity information can lead to more efficient conformal predictors and a lower prediction latency than the conventional methods on large data sets. We propose that future work extend the research on using the connectivity information, specifically the node embeddings, to boost the performance of conformal predictors on graphs. / De senaste årtiondena har vi sett en drastiskt ökad utveckling av djupinlärningsalgoritmer. Även fast dessa algoritmer har skapat nya potentiella affärsområden och har även lett till nya upptäckter i flera andra fält, är dessa algoritmer dessvärre oftast begränsade till Euklidisk data. Samtidigt ser vi att allt fler forskare har upptäckt att data i verklighetstrogna applikationer oftast är bättre representerade i form av grafer. Exempel inkluderar hög-risk domäner som läkemedelsutveckling, där man förutspår bieffekter från mediciner med hjälp av protein-protein nätverk. I hög-risk domäner finns det ett krav på tillit och att resultaten från djupinlärningsalgoritmer är transparenta. I den här tesen utforskar vi hur man kan kvantifiera osäkerheten i resultaten hos Neurala Nätverk för grafer (eng. Graph Neural Networks) med hjälp av konform prediktion (eng. Conformal Prediction). Vi testar både konventionella metoder för konform prediktion, samt originella metoder som utnyttjar strukturell information från grafen. Vi utvärderar metoderna både på statiska och dynamiska grafer, och vi kommer fram till att de originella metoderna varken är bättre eller sämre än de konventionella metoderna. Däremot finner vi indikationer på att användning av den strukturella informationen från grafen kan leda till effektivare prediktorer och till lägre svarstid än de konventionella metoderna när de används på stora grafer. Vi föreslår att framtida arbete i området utforskar vidare hur den strukturella informationen kan användas, och framförallt nod representationerna, kan användas för att öka prestandan i konforma prediktorer för grafer.

This work presents an investigation of tailoring Network Representation Learning (NRL) for an application in the Financial Industry. NRL approaches are data-driven models that learn how to encode graph structures into low-dimensional vector spaces, which can be further exploited by downstream Machine Learning applications. They can potentially bring a lot of benefits in the Financial Industry since they extract in an automatic way features that can provide useful input regarding graph structures, called embeddings. Financial transactions can be represented as a network, and through NRL, it is possible to extract embeddings that reflect the intrinsic inter-connected nature of economic relationships. Such embeddings can be used for several purposes, among which Anomaly Detection to fight financial crime.This work provides a qualitative analysis over state-of-the-art NRL models, which identifies Graph Convolutional Network (ConvGNN) as the most suitable category of approaches for Financial Industry but with a certain need for further improvement. Financial Industry poses additional challenges when modelling a NRL solution. Despite the need of having a scalable solution to handle real-world graph with considerable dimensions, it is necessary to take into consideration several characteristics: transactions graphs are inherently dynamic since every day new transactions are executed and nodes can be heterogeneous. Besides, everything is further complicated by the need to have updated information in (near) real-time due to the sensitivity of the application domain. For these reasons, GraphSAGE has been considered as a base for the experiments, which is an inductive ConvGNN model. Two variants of GraphSAGE are presented: a dynamic variant whose weights evolve accordingly with the input sequence of graph snapshots, and a variant specifically meant to handle bipartite graphs. These variants have been evaluated by applying them to real-world data and leveraging the generated embeddings to perform Anomaly Detection. The experiments demonstrate that leveraging these variants leads toimagecomparable results with other state-of-the-art approaches, but having the advantage of being suitable to handle real-world financial data sets. / Detta arbete presenterar en undersökning av tillämpningar av Network Representation Learning (NRL) inom den finansiella industrin. Metoder inom NRL möjliggör datadriven kondensering av grafstrukturer till lågdimensionella och lätthanterliga vektorer.Dessa vektorer kan sedan användas i andra maskininlärningsuppgifter. Närmare bestämt, kan metoder inom NRL underlätta hantering av och informantionsutvinning ur beräkningsintensiva och storskaliga grafer inom den finansiella sektorn, till exempel avvikelsehantering bland finansiella transaktioner. Arbetet med data av denna typ försvåras av det faktum att transaktionsgrafer är dynamiska och i konstant förändring. Utöver detta kan noderna, dvs transaktionspunkterna, vara vitt skilda eller med andra ord härstamma från olika fördelningar.I detta arbete har Graph Convolutional Network (ConvGNN) ansetts till den mest lämpliga lösningen för nämnda tillämpningar riktade mot upptäckt av avvikelser i transaktioner. GraphSAGE har använts som utgångspunkt för experimenten i två olika varianter: en dynamisk version där vikterna uppdateras allteftersom nya transaktionssekvenser matas in, och en variant avsedd särskilt för bipartita (tvådelade) grafer. Dessa varianter har utvärderats genom användning av faktiska datamängder med avvikelsehantering som slutmål.

Garg and Könemann developed a framework for computing multi-commodity maximum flow in a graph, later called a multiplicative weight update framework. Madry used this framework and exchanged Dijkstra’s algorithm to a dynamic graph algorithm for approximating the shortest paths through the graph. With this approachhe developed the fastest algorithm to date for calculating the multi-commodity maximum flow, with a running time of Õ(mnϵ2). This project have implemented the algorithm and compared it with a slightly modified version of the former fastest algorithm by Fleischer with a time complexity of Õ(m2ϵ2). The results show that Madry’s algorithms is slower than Fleischer’s algorithm in practice for graph with less than 100 million edges. This project also computed the space needed for the dynamic algorithms used in Madry’s algorithm and can show a resulting space complexity of O(n(n+m)log2n), compared to the space complexity of Fleischer’s algorithm of O(n). For a graph with 100 million edges, 50 million Gb of space is needed to use Madry’s algorithm, which is more than our test computers had. We can therefore conclude that Madry’s algorithm is not usable in real life today, both in terms of memory usage and time consumption. / Garg and Könemann utvecklade ett framework för att beräkna multi-commodity maximum flöde i en graf sedan kallat ett multiplicative weight update framework. Madry använde detta framework och bytte ut Dijkstra’s algoritm mot en dynamisk grafalgoritm för att kunna approximera kortaste vägen i grafen. Med detta angeppssätt utvecklade han den idag snabbaste algoritmen för beräkning av multicommodity maximum flöde med en tids komplexitet på Õ(mnϵ2). Det här projektet har implementerat hans algoritm och jämfört den med den tidigare snabbaste algoritmen skapad av Fleischer med en tidskomplexitet på Õ(m2ϵ2). Resultatet visar att Madrys algoritm är långsammare än Fleischers algoritm i praktiken för grafer med färre än 100 miljoner kanter. Detta projekt beräknade också minnesåtgången för de dynamiska algoritmerna i Madrys algorithm och kan visa en resulterade minneskomplexitet på O(n(n+m)log2n), jämfört med Fleischers algoritm på O(n). För en graf med 100 miljoner kanter så behövs 50 miljoner Gb av minne för att kunna använda Madrys algoritm, vilket var mer än våra testdatorer hade. Vi kan därför konstatera att Madrys algoritm inte är användbar i praktiken idag, både när det kommer till minnesanvändning och till tidsåtgång.