Open Collections

Qian, Xinjie

University of British Columbia

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.

Text; Dataset; Software

2024-03-21

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/87607

Computer Science

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/