Information Extraction is a sub-field of Natural Language Processing that aims to extract structured data from unstructured sources. With the progress in digitization, extracting key information like account number, gross amount, etc. from business invoices becomes an interesting problem in both industry and academy. Such a process can largely facilitate online payment, as users do not have to type in key information by themselves. In this project, we design and implement an extraction system that combines Machine Learning and Heuristic Rules to solve the problem. Invoices are transformed into a graph structure and then Graph Neural Networks are used to give predictions of the role of each word appearing on invoices. Rule-based modules output the final extraction results based on aggregated information from predictions. Different variants of graph models are evaluated and the best system achieves 90.93% correct rate. We also study how the number of stacked graph neural layers influences the performance of the system. The ablation study compares the importance of each extracted feature and results show that the combination of features from different sources, rather than any single feature, plays the key role in the classification. Further experiments reveal the respective contributions of Machine Learning and rule-based modules for each label. / Informationsutvinning är ett delområde inom språkteknologi som syftar till att utvinna strukturerade data från ostrukturerade källor. I takt med den ökande digitaliseringen blir det ett intressant problem för både industrin och akademin att extrahera nyckelinformation som t.ex. kontonummer, bruttobelopp och liknande från affärsfakturor. En sådan process kan i hög grad underlätta onlinebetalningar, eftersom användarna inte behöver skriva in nyckelinformation själva. I det här projektet utformar och implementerar vi ett extraktionssystem som kombinerar maskininlärning och heuristiska regler för att lösa problemet. Fakturor kommer att omvandlas till en grafstruktur och sedan används grafiska neurala nätverk för att förutsäga betydelsen av varje ord som förekommer på fakturan. Regelbaserade moduler producerar de slutliga utvinningsresultaten baserat på aggregerad information från förutsägelserna. Olika varianter av grafmodeller utvärderas och det bästa systemet uppnår 90,93 % korrekta resultat. Vi studerar också hur antalet neurala graflager påverkar systemets prestanda. I ablationsstudien jämförs betydelsen av varje extraherat särdrag och resultaten visar att kombinationen av särdrag från olika källor, snarare än något enskilt särdrag, spelar en nyckelroll i klassificeringen. Ytterligare experiment visar hur maskininlärning och regelbaserade moduler på olika sätt bidrar till resultatet.

Link prediction is a crucial task in many downstream applications of graph machine learning. Graph Neural Networks (GNNs) are a prominent approach for transductive link prediction, where the aim is to predict missing links or connections only within the existing nodes of a given graph. However, many real-life applications require inductive link prediction for the newly-coming nodes with no connections to the original graph. Thus, recent approaches have adopted a Multilayer Perceptron (MLP) for inductive link prediction based solely on node features. In this work, we show that incorporating both connectivity structure and features for the new nodes provides better model expressiveness. To bring such expressiveness to inductive link prediction, we propose LEAP, an encoder that features LEArnable toPology augmentation of the original graph and enables message passing with the newly-coming nodes. To the best of our knowledge, this is the first attempt to provide structural contexts for the newly-coming nodes via learnable augmentation under inductive settings. Conducting extensive experiments on four real- world homogeneous graphs demonstrates that LEAP significantly surpasses the state-of-the-art methods in terms of AUC and average precision. The improvements over homogeneous graphs are up to 22% and 17%, respectively. The code and datasets are available on GitHub*. / Att förutsäga länkar är en viktig uppgift i många efterföljande tillämpningar av maskininlärning av grafer. Graph Neural Networks (GNNs) är en framträdande metod för transduktiv länkförutsägelse, där målet är att förutsäga saknade länkar eller förbindelser endast inom de befintliga noderna i en given graf. I många verkliga tillämpningar krävs dock induktiv länkförutsägelse för nytillkomna noder utan kopplingar till den ursprungliga grafen. Därför har man på senare tid antagit en Multilayer Perceptron (MLP) för induktiv länkförutsägelse som enbart bygger på nodens egenskaper. I det här arbetet visar vi att om man införlivar både anslutningsstruktur och egenskaper för de nya noderna får man en bättre modelluttryck. För att ge induktiv länkförutsägelse en sådan uttrycksfullhet föreslår vi LEAP, en kodare som innehåller LEArnable toPology augmentation av den ursprungliga grafen och möjliggör meddelandeöverföring med de nytillkomna noderna. Såvitt vi vet är detta det första försöket att tillhandahålla strukturella sammanhang för de nytillkomna noderna genom en inlärningsbar ökning i induktiva inställningar. Omfattande experiment på fyra homogena grafer i den verkliga världen visar att LEAP avsevärt överträffar "state-of-the-art" metoderna när det gäller AUC och genomsnittlig precision. Förbättringarna jämfört med homogena grafer är upp till 22% och 17%. Koden och datamängderna finns tillgängliga på Github*.

This master's thesis investigates the application of Graph Neural Networks (GNNs) to address scalability challenges in combinatorial optimization, with a primary focus on the minimum Total Dominating set Problem (TDP) and additionally the related Carrier Scheduling Problem (CSP) in networks of Internet of Things. The research identifies the NP-hard nature of these problems as a fundamental challenge and addresses how to improve predictions on input graphs of sizes much larger than seen during training phase. Further, the thesis explores the instability in such scalability when leveraging GNNs for TDP and CSP. Two primary measures to counter this scalability problem are proposed and tested: incorporating node degree as an additional feature and modifying the attention mechanism in GNNs. Results indicate that these countermeasures show promise in addressing scalability issues in TDP, with node degree inclusion demonstrating overall performance improvements while the modified attention mechanism presents a nuanced outcome with some metrics improved at the cost of others. Application of these methods to CSP yields bleak results, evincing the challenges of scalability in more complex problem domains. The thesis contributes by detecting and addressing scalability challenges in combinatorial optimization using GNNs and provides insights for further research in refining methodologies for real-world applications. / Denna masteruppsats undersöker tillämpningen av Grafiska Neurala Nätverk (GNN) för att hantera utmaningar inom skalbarhet vid kombinatorisk optimering, med ett primärt fokus på minimum Total Dominating set Problem (TDP) samt även det relaterade Carrier Scheduling Problem (CSP) i nätverk inom Internet of Things. Studien identifierar den NP-svåra karaktären av dessa problem som en grundläggande utmaning och lyfter hur man kan förbättra prediktioner på indatagrafer av storlekar som är mycket större än vad man sett under träningsfasen. Vidare utforskar uppsatsen instabiliteten i sådan skalbarhet när man utnyttjar GNN för TDP och CSP. Två primära åtgärder mot detta skalbarhetsproblem föreslås och testas: inkorporering av nodgrad som ett extra attribut och modifiering av attention-mekanismer i GNN. Resultaten indikerar att dessa motåtgärder har potential för att angripa skalbarhetsproblem i TDP, där inkludering av nodgrad ger övergripande prestandaförbättringar medan den modifierade attention-mekanismen ger ett mer tvetydigt resultat med vissa mätvärden förbättrade på bekostnad av andra. Tillämpning av dessa metoder på CSP ger svaga resultat, vilket antyder om utmaningarna med skalbarhet i mer komplexa problemdomäner. Uppsatsen bidrar genom att upptäcka och adressera skalbarhetsutmaningar i kombinatorisk optimering med hjälp av GNN och ger insikter för vidare forskning i att förfina metoder för verkliga tillämpningar.

Cyber attacks are ubiquitous and increasingly prevalent in industry, society, and governmental departments. They affect the economy, politics, and individuals. Ever-increasingly skilled, organized, and funded threat actors combined with ever-increasing volumes and modalities of data require increasingly sophisticated and innovative cyber defense solutions. Current state-of-the-art security systems conduct threat detection on dynamic graph representations of computer systems and enterprise communication networks known as provenance graphs. Most of these security systems are statistics-based, based on rules defined by domain experts, or discard temporal information, and as such come with a set of drawbacks (e.g., incapability to pinpoint the attack, incapability to adapt to evolving systems, reduced expressibility due to lack of temporal information). At the same time, there is little research in the machine learning community on graphs such as provenance graphs, which are a form of largescale, heterogeneous, and continuous-time dynamic graphs, as most research on graph learning has been devoted to static homogeneous graphs to date. Therefore, this thesis aims to bridge these two fields and investigate the potential of learning-based methods operating on continuous-time dynamic provenance graphs for cyber threat detection. Without loss of generality, this work adopts the general Temporal Graph Networks framework for learning representations and detecting anomalies in such graphs. This method explicitly addresses the drawbacks of current security systems by considering the temporal setting and bringing the adaptability of learning-based methods. In doing so, it also introduces and releases two large-scale, continuoustime temporal, heterogeneous benchmark graph datasets with expert-labeled anomalies to foster future research on representation learning and anomaly detection on complex real-world networks. To the best of the author’s knowledge, these are one of the first datasets of their kind. Extensive experimental analyses of modules, datasets, and baselines validate the potency of continuous-time graph neural network-based learning, endorsing its practical applicability to the detection of cyber threats and possibly other semantically meaningful anomalies in similar real-world systems. / Cyberattacker är allestädes närvarande och blir allt vanligare inom industrin, samhället och statliga myndigheter. De påverkar ekonomin, politiken och enskilda individer. Allt skickligare, organiserade och finansierade hotaktörer i kombination med ständigt ökande volymer och modaliteter av data kräver alltmer sofistikerade och innovativa cyberförsvarslösningar. Dagens avancerade säkerhetssystem upptäcker hot på dynamiska grafrepresentationer (proveniensgrafer) av datorsystem och företagskommunikationsnät. De flesta av dessa säkerhetssystem är statistikbaserade, baseras på regler som definieras av domänexperter eller bortser från temporär information, och som sådana kommer de med en rad nackdelar (t.ex. oförmåga att lokalisera attacken, oförmåga att anpassa sig till system som utvecklas, begränsad uttrycksmöjlighet på grund av brist på temporär information). Samtidigt finns det lite forskning inom maskininlärning om grafer som proveniensgrafer, som är en form av storskaliga, heterogena och dynamiska grafer med kontinuerlig tid, eftersom den mesta forskningen om grafinlärning hittills har ägnats åt statiska homogena grafer. Därför syftar denna avhandling till att överbrygga dessa två områden och undersöka potentialen hos inlärningsbaserade metoder som arbetar med dynamiska proveniensgrafer med kontinuerlig tid för detektering av cyberhot. Utan att för den skull göra avkall på generaliserbarheten använder detta arbete det allmänna Temporal Graph Networks-ramverket för inlärning av representationer och upptäckt av anomalier i sådana grafer. Denna metod tar uttryckligen itu med nackdelarna med nuvarande säkerhetssystem genom att beakta den temporala induktiva inställningen och ge anpassningsförmågan hos inlärningsbaserade metoder. I samband med detta introduceras och släpps också två storskaliga, kontinuerliga temporala, heterogena referensgrafdatauppsättningar med expertmärkta anomalier för att främja framtida forskning om representationsinlärning och anomalidetektering i komplexa nätverk i den verkliga världen. Såvitt författaren vet är detta en av de första datamängderna i sitt slag. Omfattande experimentella analyser av moduler, dataset och baslinjer validerar styrkan i induktiv inlärning baserad på kontinuerliga grafneurala nätverk, vilket stöder dess praktiska tillämpbarhet för att upptäcka cyberhot och eventuellt andra semantiskt meningsfulla avvikelser i liknande verkliga system.