A graph neural network approach to interval and box graph completion problems
department or school: Science, Irving K. Barber Faculty of (Okanagan)
department or school: Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
data provider: DSpace
degree campus: UBCO
creator: Qian, Xinjie
issued: 2024-03-21T18:31:20Z
issued: 2024
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: Interval and box graph editing/completion problems are interesting in the field of graph theory, whose aim is to transform an arbitrary graph into an interval or box graph by adding or removing edges, with a minimum number of such modifications. There are many existing algorithms that make use of the combinatorial properties of graphs to solve these problems. In this thesis, we propose an alternative approach that uses Graph Neural Networks(GNN). We introduce a GNN model that takes graphs as input and generates interval/box graphs by adding or removing edges. We also design and employ an aggregation process with an attention mechanism that leverages the neighborhood of each vertex, which aligns with the properties of the problem. To evaluate the capability of our GNN model, we develop a random model for generating interval and box graphs with adjustable parameters, inspired by Scheinerman’s random interval model [Sch90]. We observe that it is challenging for our GNN model to handle sparse graphs in terms of minimizing edge modification. To enhance GNN’s performance in such scenarios, we implement a data filtering mechanism and incorparate a learnable distance parameter into the attention aggregation process. Overall, our GNN model demonstrates promising results in addressing interval and box graph completion problems.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/87607
note: A Graph Neural Network Approach toInterval and Box Graph CompletionProblemsbyXinjie QianB.Sc. Hons., The University of Calgary, 2021A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)March, 2024© Xinjie Qian, 2024The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:A Graph Neural Network Approach to Interval and Box GraphCompletion Problemssubmitted by Xinjie Qian in partial fulfilment of the requirements of thedegree of Master of ScienceDr. Yong Gao, I. K. Barber Faculty of SciencesSupervisorDr. Shan Du, I. K. Barber Faculty of SciencesSupervisory Committee MemberDr. Donovan Hare, I. K. Barber Faculty of SciencesSupervisory Committee MemberDr. Qian Chen, School of EngineeringUniversity ExamineriiAbstractInterval and box graph editing/completion problems are interesting inthe field of graph theory, whose aim is to transform an arbitrary graph intoan interval or box graph by adding or removing edges, with a minimumnumber of such modifications. There are many existing algorithms thatmake use of the combinatorial properties of graphs to solve these problems.In this thesis, we propose an alternative approach that uses Graph NeuralNetworks(GNN).We introduce a GNN model that takes graphs as input and generatesinterval/box graphs by adding or removing edges. We also design and em-ploy an aggregation process with an attention mechanism that leverages theneighborhood of each vertex, which aligns with the properties of the prob-lem. To evaluate the capability of our GNN model, we develop a randommodel for generating interval and box graphs with adjustable parameters,inspired by Scheinerman’s random interval model [Sch90]. We observe thatit is challenging for our GNN model to handle sparse graphs in terms of mini-mizing edge modification. To en…
has type: Thesis/Dissertation
date issued: 2024-05
is shown at: 10.14288/1.0440711
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
contributor: Gao, Yong
type: Text
type: Dataset
type: Software
identifier URI: http://hdl.handle.net/2429/87607