Thesis Defence: A Graph Neural Network Approach to Interval and Box Graph Completion Problems

Xinjie Qian, supervised by Dr. Yong Gao, will defend their thesis titled “A Graph Neural Network Approach to Interval and Box Graph Completion Problems” in partial fulfillment of the requirements for the degree of Master of Science in Computer Science.

An abstract for Xinjie Qian’s thesis is included below.

Defences are open to all members of the campus community as well as the general public. Please email yong.gao@ubc.ca to receive the Zoom link for this defence.

---

ABSTRACT

Interval and box graph editing/completion are interesting problems in the field of graph theory, which aim to transform an arbitrary graph into an interval or box graph by adding or removing edges, with a minimum number of such modification. 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(GNNs). 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 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 incorporate a learnable distance parameter into the attention aggregation process. Overall, our GNN model demonstrates promising results in addressing interval and box graph completion problems.