Back to search

University of British Columbia

A graph neural network approach to interval and box graph completion problems

Abstract

dc: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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Qian, Xinjie
Contributors dc:contributor
  • Gao, Yong

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/87607

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Qian, Xinjie. A graph neural network approach to interval and box graph completion problems. master's thesis, University of British Columbia, 2024. http://hdl.handle.net/2429/87607