Science, Irving K. Barber Faculty of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Qian, Xinjie
Master of Science - MSc
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.
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 enhance GNN’s performance in such scenarios,we implement a data filtering mechanism and incorparate a learnable dis-tance parameter into the attention aggregation process. Overall, our GNNmodel demonstrates promising results in addressing interval and box graphcompletion problems.iiiLay SummaryGraph completion, a fundamental problem in graph theory, involves fill-ing in missing edges to achieve specific graph structures. We propose aGraph Neural Networks (GNN) model to address interval and box graphcompletion problems. GNN have shown promise in capturing complex de-pendencies in graph data and efficiently handling large-scale graphs. Bytraining GNN on datasets of known interval and box graphs, the networkcan add and remove edges to complete the graph. This approach offers analternative to previous methods and explores the potential of GNN to pro-vide efficient and effective solutions to interval and box graph completionproblems.ivPrefaceThe research reported in this thesis has been conducted at the Universityof British Columbia, Okanagan as partial fulfillment of the requirements forthe Master’s Degree in Computer Science. The thesis was written solely byme, with guidance from my supervisor, Dr. Yong Gao.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Submitted Files . . . . . . . . . . . . . . . . . . . . . . . xiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: Background and Preliminaries . . . . . . . . . . . . 32.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1.1 Connectedness . . . . . . . . . . . . . . . . . . . . . . 42.1.2 Boxicity of Graphs . . . . . . . . . . . . . . . . . . . . 52.1.3 Graph Editing Problems . . . . . . . . . . . . . . . . . 72.1.4 Interval Graph Completion Problem . . . . . . . . . . 82.2 Graph Neural Networks . . . . . . . . . . . . . . . . . . . . . 92.2.1 Encoder and Decoder . . . . . . . . . . . . . . . . . . 132.2.2 GraphSage . . . . . . . . . . . . . . . . . . . . . . . . 132.2.3 Attention Mechanism . . . . . . . . . . . . . . . . . . 15Chapter 3: Random Box Graphs . . . . . . . . . . . . . . . . . 173.1 The Connectivity Threshold . . . . . . . . . . . . . . . . . . . 24viTABLE OF CONTENTSChapter 4: GNN-Based Approach to Interval and Box GraphCompletion and Editing . . . . . . . . . . . . . . . . 324.1 Model Architecture . . . . . . . . . . . . . . . . . . . . . . . . 324.1.1 Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . 334.1.2 Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . 364.1.3 Loss Functions . . . . . . . . . . . . . . . . . . . . . . 374.2 The Generation of Training Dataset . . . . . . . . . . . . . . 394.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.3.1 Learnable neighbourhood distance parameter . . . . . 47Chapter 5: Conclusions . . . . . . . . . . . . . . . . . . . . . . . 51Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58Appendix A: Training Data Format . . . . . . . . . . . . . . . . . . 59Appendix B: Visualization of Sample Graphs . . . . . . . . . . . . 62viiList of TablesTable 4.1 Average diameter of random interval graphs with dif-ferent densities. . . . . . . . . . . . . . . . . . . . . . . 36Table 4.2 Average diameter of random box graphs with differentdensities. . . . . . . . . . . . . . . . . . . . . . . . . . . 36Table 4.3 r value with its corresponding edge probability p valuein interval graphs generated with model B(n, r, 1). . . 39Table 4.4 r value with its corresponding edge probability p valuein box graphs generated with model B(n, r, 2). This isunder the assumption that rx for x-parallel intervalsand ry for y-parallel intervals are equal. . . . . . . . . 39Table 4.5 Result of GNN on interval graph editing in terms ofmodel edited percentage. . . . . . . . . . . . . . . . . . 41Table 4.6 Result of GNN on interval graph completion in termsof model edited percentage. . . . . . . . . . . . . . . . 41Table 4.7 Result of GNN on box graph editing in terms of modeledited percentage. . . . . . . . . . . . . . . . . . . . . 42Table 4.8 Result of GNN on box graph completion in terms ofmodel edited percentage. . . . . . . . . . . . . . . . . . 42Table 4.9 Average number of isolated components with differentsizes for random interval graphs. . . . . . . . . . . . . 44Table 4.10 Average number of isolated components with differentsizes for random box graphs. . . . . . . . . . . . . . . . 44Table 4.11 Comparison of GNN’s performance on interval editing,with graph edge probability p = 1100 , with and withoutdata filtering, in terms of model edited percentage. . . 45Table 4.12 Comparison of GNN’s performance on interval com-pletion, with graph edge probability p = 1100 , withand without data filtering, in terms of model editedpercentage. . . . . . . . . . . . . . . . . . . . . . . . . 45viiiLIST OF TABLESTable 4.13 Comparison of GNN’s performance on box editing,with graph edge probability p = 1100 , with and withoutdata filtering, in terms of model edited percentage. . . 46Table 4.14 Comparison of GNN’s performance on box completion,with graph edge probability p = 1100 , with and withoutdata filtering, in terms of model edited percentage. . . 46Table 4.15 Result of GNN on highly sparse interval graph editingwith learnable distance parameter during aggregation,with graph edge probability p = 1100 , in terms of modeledited percentage. . . . . . . . . . . . . . . . . . . . . 47Table 4.16 Learned neighbourhood distance by GNN in intervalediting, with graph edge probability p = 1100 , in termsof model edited percentage. . . . . . . . . . . . . . . . 47Table A.1 Example of the CSV file recording node feature of ainterval representation of the graph in Figure 2.1. . . . 60Table A.2 Example of the CSV file recording edges and non-edgesof a interval representation of the graph in Figure 2.1,as well as a box representation of the graph in Figure2.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Table A.3 Example of the CSV file recording node feature of abox representation of the graph in Figure 2.2. . . . . . 61ixList of FiguresFigure 2.1 An Interval Graph with its vertices’ intervals on thenumber line. . . . . . . . . . . . . . . . . . . . . . . . 6Figure 2.2 An box Graph with its vertices’ boxes in the xy-plane. 7Figure 2.3 [KST99]Three structure that indicate a chordal graphis not a proper interval graph. a) Tent. b) Claw. c)Net. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Figure 2.4 A Simple illustration of Neural Network Structure. . . 11Figure 2.5 A flowchart of a two-layer message-passing process inGNN of graph G(V,E) for target node 1. Messagefrom node 2, 3, 4 are aggregated from their respectiveneighbours, and then the generated message is aggre-gated to the embedding of node 1. . . . . . . . . . . . 12Figure 3.1 A plot highlighting the area where all the (x, y) in thearea will ensure |x− y| ≤ t for some t ∈ [0, 1]. . . . . 18Figure 3.2 A plot highlighting the area where all the (ρ, σ) inthe area will ensure ρ+ σ ≤ t for some 0 ≤ t ≤ r. . . 19Figure 3.3 A plot highlighting the area where all the (ρ, σ) inthe area will ensure ρ+ σ ≤ t for some r ≤ t ≤ 2r. . . 20Figure 3.4 Area representing the event when two random inter-vals intersect in a interval graph. . . . . . . . . . . . . 25Figure 3.5 Area representing the event when c > 1 and a rightend point of node i is a broken end in ([0, r] ∪ [1− r]). 30Figure 3.6 Shaded area representing the event when c > 1 and aright end point of node i is a broken end in [r, 1− r]. 30Figure 4.1 A flowchart of our GNN model. . . . . . . . . . . . . 33Figure 4.2 A flowchart of our attention aggregation process ofnode i. . . . . . . . . . . . . . . . . . . . . . . . . . . 35xLIST OF FIGURESFigure 4.3 A bar plot of the ratio of the average neighborhoodsize of our randomly generated interval graphs withedge probability p = 1100 , to the expected neighbor-hood size in a Erdos Renyl graph with edge probabil-ity p = 1100 . The red line represents when ratio= 0.8. 37Figure 4.4 Training loss over steps for: A) Interval graph editingwith data filtering(top left), B) Interval graph edit-ing without data filtering(top right), C)Interval graphcompletion with data filtering(bottom left), D)Intervalgraph completion without data filtering(bottom right). 49Figure 4.5 Training loss over steps for: A) Box graph editingwith data filtering(top left), B) Box graph editingwithout data filtering(top right), C)Box graph com-pletion with data filtering(bottom left), D)Box graphcompletion without data filtering(bottom right). . . . 50Figure B.1 Visualization of a random interval graph with edgeprobability p = 1100 , n = 1024. . . . . . . . . . . . . . 62Figure B.2 Visualization of a random box graph with edge prob-ability 1100 , n = 1024. . . . . . . . . . . . . . . . . . . 63xiList of Submitted FilesFile 1 ubc 2024 may qian xinjie boxdata1.zipFile 2 ubc 2024 may qian xinjie boxdata2.zipFile 3 ubc 2024 may qian xinjie intervaldata1.zipFile 4 ubc 2024 may qian xinjie intervaldata2.zipFile 5 ubc 2024 may qian xinjie model.zipxiiAcknowledgementsI would like to express my sincere gratitude to Dr. Yong Gao, mydedicated supervisor, for his invaluable guidance and unwavering supportthroughout the journey of completing my graduate thesis. His expertise,encouragement, and constructive feedback played a pivotal role in shapingthe direction and quality of my research. Furthermore, I extend my thanksto Dr. Shan Du and Dr. Donovan Hare for their assistance and encourage-ment that greatly contributed to the successful completion of my thesis.I am also deeply thankful to the entire academic community at the uni-versity for providing a stimulating and enriching environment for learning.My heartfelt appreciation goes to Dr. Jim Nastos and Dr. Congsong Zhangfor their insights and resources during various phases of my research.xiiiChapter 1IntroductionGraph completion is a fundamental problem in graph theory that in-volves filling in missing edges to achieve specific graph structures. The mo-tivation for researching graph completion problems stems from their wide-ranging applications in solving real-world problems, addressing data incom-pleteness, and deepening our understanding of fundamental graph proper-ties. An illustrative example of such application is in the area of knowledgegraphs, where the graph completion problem is modeled as a link predictionproblem [GSP09, KL11]. In recent years, the adoption of Graph Neural Net-works (GNN) for link prediction problems has drawn significant attention inthe study of graph completion problems [ZC18, ZLT+23]. One of the earli-est approaches is the application of R-GCN, as demonstrated in the work ofSchlichtkrull et al. [SKB+18], for predicting absent links within knowledgegraphs.In this thesis, we primarily focus on resolving the link prediction problemdescribed by specific intersection models—namely, interval and box graphs.These graphs capture our attention through their unique structural features.Interval and box graph completion problems have been studied in the areaof graph theory and computer science with many algorithms. Interval graphcompletion refers to the task of reconstructing missing edges in an intervalgraph, where the vertices represent intervals on a real line, and edges con-nect non-overlapping intervals [KST99, GH64]. Many existing algorithmsfocus on minimal interval completion problem [LdC10, RST06, HSTV05]and k-interval completion problem [HPTV07, VHPT09] – both aim to findthe interval graph with desired size as a supergraph of the original graph.Box graph completion, on the other hand, deals with reconstructing missingedges in a box graph, which is a generalization of interval graphs where eachvertex is associated with 2 intervals(e.g., rectangles in a plane).The interval and box graph completion problems are known to be NP-complete [PC06]. Previous approaches to interval graph completion havebeen designed to make use of the combinatorial characteristics of graphs to1find the maximal or minimal interval graph representation. In this research,we have designed a GNN-based model to tackle these problems. We aim toassess the feasibility of GNN in solving these problems through an empiricalstudy. For the purpose of training our GNN model, we have also designed arandom model for generating interval/box graphs with controllable param-eters. By training our GNN model on a dataset of random interval or boxgraphs, the network can learn to predict edges by learning the intersectionmodel, effectively completing the graph. By leveraging the expressive powerof GNN, we hope that our model will provide an alternative solution for theproblem.This thesis has five chapters. The next chapter will begin with expositionon background definitions before transitioning into describing the problemsat hand. Chapter 3 will center on the analysis of the random model forgenerating interval and box graphs, where this model serves as crucial datasources for training our GNN model. In Chapter 4, we will introduce ourGNN model architecture and elaborate on the experiments conducted to ad-dress the interval and box graph editing/completion problems. Additionally,we will analyze notable or significant results derived from them. Finally, theconclusion and the direction for future work will be presented in Chapter 5.2Chapter 2Background andPreliminariesGraphs are fundamental structures used to represent relationships be-tween objects. As a branch of study in mathematics, graph theory serves asa powerful tool for modelling and analyzing structural properties of varioussystems, such as social and biological networks. It provides insights to howlocal properties like adjacency between nodes affect global properties suchas the intersection model. We are particularly interested in one of theseproperties, called boxicity, and its related problems: interval graph edit-ing/completion problem and box graph editing/completion problem.Traditional methods in graph theory have typically relied on combinato-rial properties of graphs, while our approach involves using machine learn-ing to solve the graph completion problem. This chapter will introduce keyproperties and behaviors of both graphs and Graph Neural Networks (GNN).2.1 GraphsIn this section, we will introduce the fundamental properties of graphsthat serve as the basis for our research. Let us begin by looking at theformal definition of a graph.Definition 2.1. A directed graph G = (V,E) consists of a set of verticesV , and a set of edges E ⊆ {(u, v)|(u, v) ∈ V 2}.Each vertex in a graph typically represents an entity or an elementin a given system, such as an individual in a social network graph, or acity/intersection in a transportation network graph. Edges serve to repre-sent relationships or connections between vertices.In the given definition, an edge between two vertices u, v ∈ V is repre-sented as an ordered pair (u, v), referred to as a directed edge. A directed32.1. GRAPHSgraph is formed by these directed edges, where (u, v) and (v, u) representdistinct edges. When the relationships are symmetric, they are called undi-rected edges and are denoted as {u, v}.A weighted graph is a type of graph where each edge is assigned a nu-merical weight, and it is often used to model real objects and relationshipsbetween nodes. In contrast, in an unweighted graph, all edges are consideredequal without any distinction in terms of numerical weights.Simple graphs are undirected graphs without any self-looping or paralleledges between the same pair of vertices. They are particularly beneficial incapturing the essence of relationships between entities without redundantor repetitive edge information. Due to their simplicity, they serve as a foun-dational element in graph theory for the examination of various properties,algorithms, and concepts. The interval and box graphs considered in thisthesis are unweighted, undirected, and simple graphs.We now present some basic definitions and concepts of graphs, as theycapture local properties that we are interested in.Definition 2.2. An adjacency matrix of an undirected graph G(V,E) is an×n binary matrix A = (Aij) where n = |V |, such that Aij = 1 if and onlyif {vi, vj} ∈ E.The neighborhood N(v) of a vertex v ∈ V of an undirected graphG = (V,E) is the set of all vertices u ∈ V such that u ̸= v and {u, v} ∈ E.The degree d(v) of a vertex v ∈ V is the size of its neighbourhood |N(v)|.2.1.1 ConnectednessGraph connectedness is a fundamental concept in graph theory thatexplores the relationships between vertices in a graph. A walk in a graphG(V,E) is a sequence of edges (e1, e2, . . . , en−1), corresponding to a sequenceof vertices (v1, v2, . . . , vn), such that ei = {vi, vj}, i, j = 1, 2, . . . , n − 1. Apath is a walk where all edges and vertices are distinct. Paths are crucialin establishing connectivity between different parts of a graph, illustratinghow information can flow within the graph.The distance between two vertices in a graph is the number of edges ina shortest path connecting them. When there is no such path, the distance42.1. GRAPHSis infinity. With this concept, we could define the d- neighborhood of avertex in a graph.Definition 2.3. The d-neighborhood Nd(v) of a vertex v ∈ V of a graphG = (V,E) is the set of all vertices that have graph distance d to v.A connected component in an undirected graph is a maximal sub-graph in which each pair of nodes is connected with each other via a path.Within each connected component, all vertices are reachable from any othervertices. If a graph is connected, it has only one connected component.Connected components highlight distinct clusters or groups within a graph,and studying them provides insights into the modular nature of the network.The diameter of a connected graph is the length of the shortest pathbetween the most distanced nodes. It measures the maximum distance onewould have to move from one point in the graph to another. A graph havingmore than one connected components would have infinite diameter.The examination of these characteristics in graphs would later provideus meaningful insights for our random model in Chapter 3.2.1.2 Boxicity of GraphsThe study of boxicity and its relationships with other graph parametershas been an active area of research in graph theory. Boxicity is a graphinvariant introduced by Fred S. Roberts [Rob69]. The boxicity of a graphG, denoted as box(G), is the minimum dimension b, such that the graph Gcan be represented as the intersection graph of axis-aligned b−dimensionalboxes. In such graphs, there exist a bijection between the set of verticesand the set of boxes, such that two boxes intersect if and only if there is anedge between the corresponding vertices. Interval graphs are a special classof graphs, with boxicity 1, while box graphs have boxicity 2.Various algorithms and heuristics have been developed to find box rep-resentations of graphs [KST99, GH64]. These approaches involve techniquesfrom combinatorial optimization, computational geometry, and graph algo-rithms. Ultimately, the goal is to efficiently find or approximate the mini-mum dimension required to represent a given graph as an intersection graphof boxes.52.1. GRAPHSInterval GraphsAn interval graph, first introduced by Lekkeikerker, C. and Boland, J[LB62], is a type of graph that can be represented by a set of intervals ona real line, where each vertex is assigned an interval, and edges betweenvertices depend on the intersection between those intervals. An example ofinterval graphs is shown in Figure 2.1. Formally, an interval graph can bedefined asDefinition 2.4. A graph G(V,E) is an interval graph if there is a mappingf : V → I from the set of vertices V to the collection of closed real intervalsI, such that u, v ∈ E if and only if f(u) ∩ f(v) ̸= ø.Figure 2.1: An Interval Graph with its vertices’ intervals on the numberline.Interval graphs have found wide applications in a variety of domains. Forexample, in regards to scheduling issues, interval graphs are used to modelthe availability of resources over time [BNBYF+01]. In genomics, intervalgraphs are employed to represent gene intervals on chromosomes, aiding inthe analysis of gene interactions and regulatory networks [Gol04]. In thesubsequent sections, we will explore the interval graph completion problemin details and the approaches which currently exist.Box GraphsA graph with boxicity 2 is a graph that can be represented as the inter-section graph of two axis-parallel rectangles in the Cartesian plane. Eachvertex of the graph corresponds to a rectangle, and edges between verticesdepend on the overlap of their corresponding rectangles. Figure 2.2 showsan example of box graphs. Formally, a box graph is defined as62.1. GRAPHSDefinition 2.5. A graph G(V,E) is an box graph if there is a mappingf : V → I × I from the set of vertices V to the collection of the Cartesianproduct of two closed real intervals I, such that u, v ∈ E if and only iff(u) ∩ f(v) ̸= ø.Figure 2.2: An box Graph with its vertices’ boxes in the xy-plane.2.1.3 Graph Editing ProblemsGraph editing problems involve modifying or transforming existing graphsto satisfy certain properties. One common type of graph editing problemsis graph completion. Graph completion problems involve predicting missingor unobserved information in graphs, with the goal of enhancing our un-derstanding of complex relationships and enabling more accurate analysis.The key objective is to infer the missing information based on the observedgraph structure and available attributes.In addition to the link prediction problem, graph editing problem isalso closely related to community detection and clustering in graphs. Manytypes of community structures in graphs can be defined as graphs with spe-cial properties, and detecting such community structures is equivalent tothe problem of editing given graphs to satisfy certain properties. For exam-ple, algorithm proposed by Gao and Nastos [NG13], and method proposedby Newman[New04] have used the idea of editing graphs into graphs withspecial properties to detect community structures.72.1. GRAPHSIn the graph completion problem, only addition of edges is allowed,whereas graph editing problem performs both addition and deletion of edges.In this thesis, we are interested in both editing and completion on intervaland box graphs.2.1.4 Interval Graph Completion ProblemThe interval graph completion problem aims to find a interval graph asthe supergraph of the given graph with the minimum of edge added [RAK91].Existing algorithms for interval graph completion often involve creatinga vertex ordering by graph search algorithms and utilizing the special struc-tural information of interval graphs. Below, We will briefly introduce someof the previous approaches to interval graph completion.A graph G(V,E) is an interval graph if and only if its vertex set hasan interval ordering, which is a linear ordering (v1, v2, . . . , vn) such that forany 1 ≤ i ≤ j ≤ k ≤ n, if {vi, vk} ∈ E, then {vi, vj} must also be in E.Suchan, K. and Todinca, I [ST06] proposed an algorithm called MIC Order-ing, which produces such a vertex ordering using a breadth-first search. Itcan be proved that this interval ordering corresponds to a minimal intervalgraph completion.Heggernes et al. [HSTV05] utilizes a fixed ordering of vertices to computea minimal interval completion of an arbitrary graph G. The authors discussconditions for obtaining a valid ordered partition and elaborate on achievinga nice ordered partition. They also introduce the concepts of clique pathsand define the notion of a nice clique path. The algorithm considers twocases based on the presence of nice clique path in the neighborhood of avertex, using the nice ordered partition to obtain a minimal interval graphrepressentation in each case.The algorithm described in the paper by Kaplan et al. [KST99] focuseson a method that guarantees the addition of a chosen edge maintains tri-angulation. By using the maximum chordality search algorithm [TY84] todetect chordality and finding chordless cycles, the algorithm avoids generat-ing non-triangulated children during traversal. Since proper interval graphsare chordal graphs that do not contain any of the three obstructions: Tent,Claw, and Net(Figure 2.3), as an induced subgraph, one could use the al-gorithm designed by Deng et al. [DHH96] to check whether a graph G is82.2. GRAPH NEURAL NETWORKSa proper interval graph. In case the input graph is not a proper intervalgraph, the information maintained by the algorithm can be used to extracteither a chordless cycle or one of the obstructions.Figure 2.3: [KST99]Three structure that indicate a chordal graph is not aproper interval graph. a) Tent. b) Claw. c) Net.2.2 Graph Neural NetworksFollowing the introduction of key concepts related to graphs, we will nowshift our focus to another crucial component of our research: Graph NeuralNetworks(GNN), which are a special type of neural networks.Neural networks [MRS95] are a class of machine learning models inspiredby the structure and functionality of the human brain. They are designedto recognize patterns and make predictions by learning from data. Theyconsist of interconnected neurons that are organized in layers, as shown inFigure 2.4. The basic building block of a neural network is a neuron, whichtakes a set of inputs, applies a mathematical operation to them, and pro-duces an output. Each input is associated with a weight that determines itscontribution to the neuron’s output. The weighted inputs are then passedthrough an activation function, which enables it to learn complex relation-92.2. GRAPH NEURAL NETWORKSships between the inputs and outputs.Neurons are typically organized into an input layer, one or more hiddenlayers, and an output layer. The input layer receives the initial data, andthe output layer produces the final predictions or decisions. The hidden lay-ers, located between the input and output layers, contain multiple neuronsand serve as intermediate processing stages. Each neuron in a hidden layerreceives inputs from the previous layer and propagates its output to the nextlayer.During the training phase, neural networks adjust their internal param-eters associated with each neuron to minimize the difference between pre-dicted outputs and the truth values. This adjustment is achieved throughthe use of optimization algorithms such as gradient descent [KW52], whichiteratively update the weights based on the computed error or loss. The pro-cess of training a neural network involves feeding it with a labeled dataset,computing the error, and updating the parameters through backpropaga-tion, which efficiently calculates the gradients necessary for weight updates.The power of neural networks lies in their ability to learn complex map-pings and extract meaningful features from raw data. They can handlediverse types of data, including images, text, time series, and graphs. Neu-ral networks have achieved remarkable success in various fields, includingthe the analysis of graph data. Their versatility, scalability, and capacityto handle large amounts of data make them a fundamental tool in modernmachine learning and artificial intelligence research.Graph Neural Networks (GNN) [WCP+22, Ham20] are a class of neuralnetworks specifically designed to handle graph-structured data. They lever-age the concept of message passing to capture complex relationships anddependencies present in graphs.The main components of a GNN consist of a graph G(V,E), a set X ofnode feature vectors, and an aggregation function. Graphs are defined inthe form of edge-list representation as the input of GNN models. The graphrepresents the structural relationships between the nodes, while the featurevectors contain information associated with each node. The aggregationfunction is selected based on the specific task at hand, enabling the opti-mal aggregation of neighborhood information to serve the intended purpose.102.2. GRAPH NEURAL NETWORKSFigure 2.4: A Simple illustration of Neural Network Structure.The key idea behind GNN is to update the representation of each nodeby iteratively aggregating and combining information from its neighbors.This is achieved through a series of message passing steps, where the node’srepresentation is refined based on the features of its neighbors. The generalform of message passing in a GNN can be represented as:h(l+1)v = Update(h(l)v , Aggregate(MessagelN(v))), v ∈ V,where N(v) denotes the neighbourhood of node v. The two functions Updateand Aggregate are differentiable functions defined by the GNN model. Theinput feature xv ∈ X of each vertex v ∈ V is first mapped to a lower-dimensional vector h1v, called the embedding of the input feature. At eachiteration of the GNN, the aggregation function takes the embeddings of nodev′s neighbourhood N(v) as input and generates a message based on this ag-gregated neighborhood information. The Update function then combinesthe message with the previous embedding h(l)v of node v to generate the up-dated embedding h(l+1)v . After running K iterations of the GNN’s messagepassing, the output is used as the final embedding of each node. A flowchartof such process in shown in Figure 2.5.GNN have been successfully applied in various domains such as socialnetwork analysis [WCP+22], molecular chemistry [FBSBH17], and knowl-edge graph related tasks [HOSM17]. They offer a powerful framework forlearning from graph data, and can be used for tasks such as node clas-112.2. GRAPH NEURAL NETWORKSFigure 2.5: A flowchart of a two-layer message-passing process in GNN ofgraph G(V,E) for target node 1. Message from node 2, 3, 4 are aggregatedfrom their respective neighbours, and then the generated message is aggre-gated to the embedding of node 1.sification [ZCZ+19, ZCC+23], link prediction [ZC18, AQSL22], and graphclustering [Mu¨l23, KNG+20]. By leveraging the graph structure and incor-porating node-level and graph-level information, GNN provide a means toanalyze and understand complex relational data.The adoption of GNN as a novel approach to interval and box graphediting/completion offers an alternate solution to the problems. Unlike tra-ditional algorithms that handle different graphs differently, the GNN-basedapproach has the capability to learn patterns and relationships related to theproblem from training data, and apply them to any input data post-training.While not ensuring a minimal supergraph, GNN may uncover alternative so-lutions and provide an exploratory perspective beyond predefined optimiza-122.2. GRAPH NEURAL NETWORKStion criteria. The trade-off between precision and adaptability positionsGNN as a valuable approach for interval and box graph editing/completion.2.2.1 Encoder and DecoderThe graph encoder in a GNN is responsible for capturing and repre-senting information about nodes and their relationships in a graph. Thepurpose of the encoder is to learn a continuous, fixed-size vector represen-tation(embedding) from the input feature vector of each node in the graph.This embedding captures both the node’s intrinsic properties and its rela-tionships with other nodes in the graph. Common graph encoders includeGraph Convolutional Networks (GCNs) [KW16] and GraphSAGE [HYL17].These models use techniques such as graph convolutions to propagate infor-mation across the graph and update node representations.While the encoder processes and learns representations of the inputgraph, the graph decoder generates an output based on these learned rep-resentations. The output of GNN’s decoder is consistently in the form of agraph. In the context of link prediction, the decoder predict the existenceof edges between nodes by utilizing learned node representations generatedby the graph encoder, thereby constructing the final output graph .2.2.2 GraphSageGraphSage is a powerful GNN model that learns node representationsby aggregating information from their local neighborhoods in a graph. Itwas introduced by Hamilton et al [HYL17], and has since become a popularand effective approach for learning node embeddings in large-scale graphanalysis tasks.The selection of GraphSAGE for this research is justified by its flexi-bility in aggregation process that could target the specific requirements ofthe interval and box graph editing/completion. Another advantage is thatGraphSAGE does not mandate labels for vertices and edges, aligning seam-lessly with the nature of our input random graphs.GraphSage considers the node features, which can include attributesor properties associated with each node in the graph. These features canbe diverse, ranging from continuous values (e.g., numerical attributes) todiscrete values (e.g., categorical labels). Node features provide additional132.2. GRAPH NEURAL NETWORKSAlgorithm 1 GraphSAGE embedding generation algorithm [HYL17].Input: G(V,E); input features xv,∀v ∈ V ; depth K; weight matricesW k,∀k∈{1, . . . ,K}; non-linear function σ; differentiable aggregatorfunctions AGGREGATEk,∀k∈{1, . . . ,K}; neighborhood samplingfunction N : v → 2VOutput: Vector representations zv,∀v ∈ Vh0v ← xv,∀v ∈ Vfor k := 1 to K dofor v ∈ V dohkN(v) ← AGGREGATEk({hk−1u ,∀u ∈ N(v)})hkv ← σ(W k · CONCAT (hk−1v , hkN(v)))endhkv ← hkv/∥hkv∥2,∀v ∈ Vendreturn zv ← hKv ,∀v ∈ Vinformation about the nodes beyond their connectivity, and they can carryimportant characteristics that contribute to the node representations. Inthe GraphSage algorithm, the neighborhood information is combined withthe node features to learn feature-based embeddingshkv ← (W ·MEAN({hk−1v } ∪ {hk−1u ,∀u ∈ N(v)}).The neighborhood embeddings obtained through the aggregation pro-cess capture the structural information from the local graph neighborhood.The flexibility of GraphSage in aggregation methods, such as sum, mean,LSTM-based, and pooling, provides versatility in capturing different typesof relationships and dependencies within the graph, enhancing the model’sadaptability to diverse structural characteristics. Our algorithm provides animproved aggregation method explained in the next section.The neighbourhood sampling function N of GraphSage starts by ran-domly selecting a subset of nodes from the graph. This subset serves as the“seed nodes” from which the neighborhoods will be sampled. The depth ofneighbourhood and the number of seed nodes selected can vary dependingon the properties of the graph and the computational resources available.Typically, a small fraction of nodes is selected as seed nodes. For each seed142.2. GRAPH NEURAL NETWORKSnode, GraphSage performs a random walk or a fixed-depth traversal to sam-ple a fixed number of neighbors. Padding can be employed to ensure thatthe sampled neighborhoods have a consistent size across different nodes.The fixed number of neighbors sampled for each node ensures that the com-putational cost remains manageable and independent of the overall graphsize, and it can be controlled by parameters in the GraphSage algorithm.Balancing the neighborhood size is important to ensure that the model cancapture both local and global structural information effectively. In contrastto GraphSage, we leverage the d-neighborhood of seed nodes, where d isdetermined by the size distributions of their neighborhood. Details of ourapproach will be presented in Chapter 4.2.2.3 Attention MechanismAttention mechanism is first introduced in the filed of natural languageprocessing by D Bahdanau et al. [BCB14]. The basic attention mechanismintroduces a innovative approach to the traditional method of encoding anentire sentence into a single vector. It instead encodes the input sentenceinto a sequence of vectors and adaptively selects a subset of these vectorswhile decoding the translation. As a result, attention mechanisms is ableto selectively focus on input elements based on their significance towardsprioritizing and emphasizing relevant information, improving prediction ac-curacy and computational efficiency. In this way, it enhances overall modelperformance.The primary advantage of applying attention mechanisms is that it learnsan alignment model, which permits the gradient of the loss function to beback propagated through the model. This alignment model can be used totrain both the attention model and the whole neural network.A more advanced variation of the attention model was later proposed in awork by Vaswani A et al. [VSP+17]. They proposed the Scale Dot-ProductAttention method in their paper:Attention(Q,K, V ) = softmax(QK⊤√dk)V, (2.1)where K(the keys) denotes the relative importance of the inputs in the se-quence , Q(the queries) represents the particular output of that sequence,V (the values) is the input sequence itself, and dk is the dimensions of both152.2. GRAPH NEURAL NETWORKSQ and K.16Chapter 3Random Box GraphsThe objective of my research is to assess the feasibility of GNN in solvinginterval and box graph editing/completion. To evaluate our GNN’s capa-bility from various perspectives, we would need a large collection of randominterval/box graphs with different properties. A practical approach to ob-tain such data collection is to develop a random model to generate instancegraphs. We relied on the approach presented in the paper “An Evolutionof Interval Graphs” [Sch90]. Scheinerman proposed and discussed a modelfor generating random interval graphs with controllable parameters. In thischapter, we will develop a probability model for box graphs, building uponScheinerman’s model, and analyze various perspectives of our model.Definition 3.1. The random model for box graphs with size n and boxicityb is denoted by B(n, r, b). Each vertex of the graph is associated with b axis-parallel intervals, resulting in a total of bn random intervals I1, I2, . . . , Ibn.Each of these intervals is determined by first selecting its center value x uni-formly at random between 0 and 1, then decide its radius value ρ uniformlyat random between 0 and r.When b = 1, the model described in Definition 3.1 corresponds to arandom interval graph proposed by Scheinerman [Sch90]. The subsequentLemma 3.2, which is introduced by this author, forms a critical foundationfor our model with b = 2. For completeness, we include the lemma andprovide a proof with details filled in.Lemma 3.2. [Sch90, Theorem 2.1] Let u, v ∈ V be two arbitrary verticesof a random interval graph G(V,E). The probability of {u, v} ∈ E is:P (u ∼ v) =2r − 7r26 , 0 ≤ r ≤ 122r4−8r3+24r2−8r+112r2, 12 ≤ r ≤ 11− 112r2, r ≥ 1.(3.1)Suppose intervals [x±ρ] and [y±σ] are assigned to u and v respectively,with x and y chosen from [0, 1] uniformly at random, ρ and σ chosen from17Figure 3.1: A plot highlighting the area where all the (x, y) in the area willensure |x− y| ≤ t for some t ∈ [0, 1].[0, r] uniformly at random. Here, r > 0 is a controllable parameter. To provethis lemma, we need to first prove the following two propositions establishedin Scheinerman’s paper [Sch90].Proposition 3.3.P (|x− y| ≤ t) ={2t− t2, 0 ≤ t ≤ 11, t ≥ 1. (3.2)Proof. When t ≥ 1, it is always true that |x− y| ≤ t, therefore P (|x− y| ≤t) = 1. When 0 ≤ t ≤ 1, to ensure |x− y| ≤ t, where x and y are uniformlydistributed random variables between 0 and 1, (x, y) has to lie between thetwo lines y = x + t and y = x − t, as the highlighted area shown in Figure3.1. The probability of such event isP (|x− y| ≤ t) = area between y = x+ t and y = x− tarea of [0, 1]× [0, 1] square=1− 2 · 12 · (1− t)21= 2t− t2.Proposition 3.4.P (ρ+ σ ≤ t) ={t22r2, 0 ≤ t ≤ r1− 12( t−2rr )2, r ≤ t ≤ 2r.(3.3)18Proof. To ensure ρ+σ ≤ t, where ρ and σ are uniformly distributed randomvariables between 0 and r, (ρ, σ) has to fall below the line σ = t−ρ, as shownin Figure 3.2(when 0 ≤ t ≤ r) and in Figure 3.3(when r ≤ t ≤ 2r). Theprobability of such event isFigure 3.2: A plot highlighting the area where all the (ρ, σ) in the area willensure ρ+ σ ≤ t for some 0 ≤ t ≤ r.P (ρ+ σ ≤ t) ={area of t×t trianglearea of [0,r]×[0,r] square , 0 ≤ t ≤ rarea of [0,r]×[0,r] square−area of (2r−t)×(2r−t) trianglearea of [0,r]×[0,r] square , r ≤ t ≤ 2r=t22r2, 0 ≤ t ≤ rr2− (2r−t)22r2, r ≤ t ≤ 2r={t22r2, 0 ≤ t ≤ r1− 12( t−2rr )2, r ≤ t ≤ 2r.(3.4)Proof. Now we use the two propositions to prove Lemma 3.2, we getP (u ∼ v) = P (|x− y| ≤ ρ+ σ)=∫ 2rt=0P (|x− y| ≤ ρ+ σ|ρ+ σ = t) dP (ρ+ σ ≤ t)=∫ r0 (2t− t2)( tr2 )dt+∫ 2rr (2t− t2)(2r−tr2 )dt, 0 ≤ r ≤ 12∫ r0 (2t− t2)( tr2 )dt+∫ 1r (2t− t2)(2r−tr2 )dt+∫ 2r12r−tr2dt, 12 ≤ r ≤ 1∫ 10 (2t− t2)( tr2 )dt+∫ r1tr2dt+∫ 2rr2r−tr2dt, r ≥ 119Figure 3.3: A plot highlighting the area where all the (ρ, σ) in the area willensure ρ+ σ ≤ t for some r ≤ t ≤ 2r.=2r − 7r26 , 0 ≤ r ≤ 122r4−8r3+24r2−8r+112r2, 12 ≤ r ≤ 11− 112r2, r ≥ 1Expanding upon the above proof, we generalize Lemma 3.2 to the follow-ing Theorem 3.5 on the edge probability of a random box graph generatedwith model B(n, r, 2). Here, each vertex of the graph is associated withb = 2 intervals Ixi and Iyi, i = 0, 1, . . . , n.Theorem 3.5. Let u, v ∈ V be two arbitrary vertices of a random box graphG(V,E), generated from the 2-dimensional model B(n, r, 2). Let (Ixu, Iyu) bethe pair of random intervals associated with vertex u ∈ V, and (Ixv, Iyv) bethe pair of random intervals associated with vertex v ∈ V. If ∀u ∈ V, Ixuand Iyu are independent, the probability of {u, v} ∈ E isP (Ixu ∩ Ixv ̸= ø)P (Iyu ∩ Iyv ̸= ø)20=(2rx − 7r2x6 )(2ry −7r2y6 ), 0 ≤ rx, ry ≤ 12(2rx − 7r2x6 )(2r4y−8r3y+24r2y−8ry+112r2y), 0 ≤ rx ≤ 12 , 12 ≤ ry ≤ 1(2rx − 7r2x6 )(1− 112r2y ), 0 ≤ rx ≤12 , ry ≥ 1(2r4x−8r3x+24r2x−8rx+112r2x)(2ry − 7r2y6 ),12 ≤ rx ≤ 1, 0 ≤ ry ≤ 12(2r4x−8r3x+24r2x−8rx+112r2x)(2r4y−8r3y+24r2y−8ry+112r2y), 12 ≤ rx, ry ≤ 1(2r4x−8r3x+24r2x−8rx+112r2x)(1− 112r2y), 12 ≤ rx ≤ 1, ry ≥ 1(1− 112r2x)(2ry − 7r2y6 ), rx ≥ 1, 0 ≤ ry ≤ 12(1− 112r2x)(2r4y−8r3y+24r2y−8ry+112r2y), rx ≥ 1, 12 ≤ ry ≤ 1(1− 112r2x)(1− 112r2y), rx, ry ≥ 1.(3.5)The most natural model is when all intervals along the b-dimensionsshare the same r value. When b = 2, this will result in P (Ixu ∩ Ixv ̸= ø) =P (Iyu ∩ Iyv ̸= ø). Depending on the desired distribution of the boxes, onecould adjust rx and ry accordingly. Havingrxry> 1 will result in boxes beingmore sparsely distributed along the x−direction, and vice-versa.It is sometimes beneficial to consider when the two intervals Ixu and Iyuassociated with an arbitrary vertex u are dependent. One way to considerthis is to put restriction on the area of the boxes.Theorem 3.6. Consider a random model B(n, r, 2, A) for box graphs withsize n, boxicity 2. Each vertex of the graph is associated with 2 axis-parallelintervals that form a box with area less than or equal to A. For each intervalI1, I2, . . . , In along one of the 2 dimensions, a radius value is chosen from[0, r] uniformly at random. Radius of intervals In+1, . . . , I2n along the otherdimension are chosen uniformly at random from [0, A4r ]. All intervals’ centerpoints are chosen uniformly at random from [0, 1]. The probability of twoarbitrary boxes intersecting isP (Iyu ∩ Iyv ̸= ø | Ixu ∩ Ixv ̸= ø)P (Ixu ∩ Ixv ̸= ø)21=(2rx − 7r2x6 )(A2rx− 7(A4rx)26 ), 0 ≤ rx, A4rx ≤ 12(2rx − 7r2x6 )(2( A4rx)4−8( A4rx)3+24( A4rx)2−2 Arx+112( A4rx)2), 0 ≤ rx ≤ 12 , 12 ≤ A4rx ≤ 1(2rx − 7r2x6 )(1− 112( A4rx)2), 0 ≤ rx ≤ 12 , A4rx ≥ 1(2r4x−8r3x+24r2x−8rx+112r2x)( A2rx −7( A4rx)26 ),12 ≤ rx ≤ 1, 0 ≤ A4rx ≤ 12(2r4x−8r3x+24r2x−8rx+112r2x)(2( A4rx)4−8( A4rx)3+24( A4rx)2−2 Arx+112( A4rx)2), 12 ≤ rx, A4rx ≤ 1(2r4x−8r3x+24r2x−8rx+112r2x)(1− 112( A4rx)2), 12 ≤ rx ≤ 1, A4rx ≥ 1(1− 112r2x)( A2rx −7( A4rx)26 ), rx ≥ 1, 0 ≤ A4rx ≤ 12(1− 112r2x)(2( A4rx)4−8( A4rx)3+24( A4rx)2−2 Arx+112( A4rx)2), rx ≥ 1, 12 ≤ A4rx ≤ 1(1− 112r2x)(1− 112( A4rx)2), rx,A4rx≥ 1.(3.6)Without loss of generality, suppose the radius of the intervals along thex axis are chosen uniformly at random from [0, rx], and to ensure the areaof the box is less than or equal to A, the radius of the intervals along yaxis have to be chosen from [0, A4rx ]. Along with Equation 3.5, we can deriveEquation 3.6.We now examine the vertex degree and number of edges in a randomgraph G(V,E) generated using model B(n, r, b). Understanding these valueswill help us decide how to generate training data for our GNNmodel. We willprove that under certain conditions, these values are concentrated aroundtheir expect values p(n−1)(expected vertex degree) and p(n2)(expected num-ber of edges). Different formula of p(probability of two boxes intersecting)have been established in Equation 3.2, 3.5, and 3.6.Lemma 3.7. (McDiarmid’s inequality[McD89]) Suppose a function f :X1×X2× · · · ×Xn → R satisfies the “bounded differences property”, whichstates that: assume we have positive constants c1, c2, . . . , cn such that ∀i ∈[1, n], and x1 ∈ X1, x2 ∈ X2, . . . , xn ∈ Xn,supx′i∈Xi∣∣f(x1, . . . , xi−1, xi, xi+1, . . . , xn)− f(x1, . . . , xi−1, x′i, xi+1, . . . , xn)∣∣22≤ ci.Then ∀ϵ > 0,P (|f(X1, X2, . . . , Xn)− E(f(X1, X2, . . . , Xn))| ≥ ϵ) ≤ e(− 2ϵ2∑ni=1c2i)With McDiarmid’s inequality, we can derive the proofs for Theorem 3.8and Theorem 3.9.Theorem 3.8. Let Xi be the random variable representing the degree ofnode i in a random graph G(V,E) generated by model B(n, r, b). Assume pis a constant, where p is the probability of the assigned boxes of two arbitraryvertices intersecting.P(|Xi − E(Xi)| ≥√E(Xi))→ 0 as n→∞.Proof. Each vertex in a graph of size n = |V | has maximum degree of n− 1.The degree of a vertex is the sum of variables Cij ,Xi =n∑j=1Cij ,whereCij ={1, if {i, j} ∈ E0, otherwise.(3.7)Since Xi is a function of Cij , we could apply McDiarmid’s inequalitywith ci = 1. For any ϵ > 0,P (|Xi − E(Xi)| ≥ ϵ) ≤ e(− 2ϵ2∑n−1i=112)= e(− 2ϵ2n−1).To guarantee the bound e(− 2ϵ2n−1)converges to 0 as n→∞, we must haveϵ2 approaching infinity faster than n − 1. Thus, we take ϵ = (E(Xi)) 12+β,for some β > 0,P(|Xi − E(Xi)| ≥ (E(Xi)) 12+β)→ 0 as n→∞.This leads to the desired conclusionP(|Xi − E(Xi) ≥√E(Xi))→ 0 as n→∞.233.1. THE CONNECTIVITY THRESHOLDSimilarly, we observe the behaviour of the total number of edges in arandom graph generated by model B(n, r, b).Theorem 3.9. Suppose X is the size of the edge set E in G(V,E) generatedusing model B(n, r, b). Assume the probability p of two arbitrary vertices’assigned boxes intersecting is a constant. ThenP(|X − E(X)| ≥ (E(X)) 32)→ 0 as n→∞.Proof. Let Xi be the random variable representing the state of vertex i inG(V,E) regarding the assigned boxes, and the function f(X1, X2, · · · , Xn) =X.Here, we can apply McDiarmid’s inequality. Since each vertex has at mostn− 1 neighbours, ci = n− 1. For any ϵ > 0,P (|X − E(X)| ≥ ϵ) ≤ e(− 2ϵ2∑ni=1(n−1)2)≈ e(− 2ϵ2n3).To guarantee the bound e(− 2ϵ2n3)converges to 0 as n → ∞, we must haveϵ2 approaches infinity faster than n3. Thus, for some β > 0, we take ϵ =(E(X))32+β. As the result,P(|X − E(X)| ≥ (E(X)) 32+β)→ 0 as n→ 0,which leads to the desired conclusionP(|X − E(X)| ≥ (E(X)) 32)→ 0 as n→∞.Hence, we have proved that under certain conditions, the vertex degreeand number of edges in a random box graph generated by model B(n, r, b)are concentrated around their expect values. This forms the foundation forgenerating suitable data for our GNN model.3.1 The Connectivity ThresholdConnectedness is another factor that has an impact on the behaviour ofour training data. In this section, we examine the threshold of connectednessof our random model B(n, r, b). Throughout this section, we assume that243.1. THE CONNECTIVITY THRESHOLDthe limit of our model parameter limn→∞ r(n) → 0. Scheinerman proveda lemma on the probability of the two intervals assigned to two arbitraryvertices in G intersecting under this assumption, where G is generated withmodel B(n, r, 1). We provide the detailed proof and expand on the generalcase of random graphs generated with B(n, r, 2). Similar to the above proofs,x and y still denote the center points of intervals, where ρ and σ denote theradius of intervals.Lemma 3.10. [Sch90] When 2r ≤ x ≤ 1− 2r, for a fixed ρ, P ([xi− ρi, xi+ρi] ∩ [xj − ρj , xj + ρj ] ̸= ø) = r + 2ρi.Proof. Since the center of the interval ranges from 0 to 1, and the radiusranges from 0 to r, all pairs (center, radius) must lie in the 1× r box shownin Figure 3.4Figure 3.4: Area representing the event when two random intervals intersectin a interval graph.Suppose a node is assigned interval [xi−ρi, xi+ρi], and we want to com-pute the probability of another node’s interval [xj − ρj , xj + ρj ] intersectingwith [xi − ρi, xi + ρi]. As illustrated in Figure 3.4, when xj lies within therange [xi − ρi, xi + ρi], two intervals overlap for any ρj . When xj > xi + ρi,for the two intervals to overlap, ρj has to be at least as great as xj−(xi+ρi).When xj < xi − ρi, for the two intervals to overlap, ρj has to be at least asgreat as (xi − ρi)− xj . Thus,P ([xi−ρi, xi + ρi] ∩ [xj − ρj , xj + ρj ] ̸= ø)=2× r22 + 2rρi1× r253.1. THE CONNECTIVITY THRESHOLD=r2 + 2rρir= r + 2ρi.This is the shaded area shown in Figure 3.4With this proved, we can now examine the probability of the two boxesassigned to two arbitrary vertices in G overlapping, where G is generatedwith model B(n, r, 2) as limn→∞ r(n)→ 0.Theorem 3.11. Let ([xi±ρi], [xj±ρj ]) represent the pair of intervals alongone side of two arbitrary boxes, and ([yi±σi], [yj ±σj ]) represent the pair ofintervals along the other side of the same two boxes. When 2rx < xi, xj <1− 2rx and 2ry < yi, yj < 1− 2ry, for fixed ρi, ρj , σi and σj , the probabilityof the two boxes overlapping isP (((xi±ρi)∩ (xi±ρj) ̸= ø)∩ ((yi±σi)∩ (yj±σj) ̸= ø)) = (rx+2ρ)(ry+2σ).Proof. Applying Theorem 3.10 to both x, y direction:P ((xi ± ρi) ∩ (xj ± ρj) ̸= ø) = rx + 2ρi,P ((yi ± σi) ∩ (yj ± σj) ̸= ø) = ry + 2σi.Since the boxes were chosen randomly and uniformly, the above two proba-bilities are independent. Hence,P (((xi ± ρi) ∩ (xj ± ρj) ̸= ø) ∩ ((yi ± σi) ∩ (yj ± σj) ̸= ø))= P ((xi ± ρi) ∩ (xj ± ρj) ̸= ø)P ((yi ± σi) ∩ (yj ± σj) ̸= ø)= (rx + 2ρi)(ry + 2σi).When there is a restriction on the area of the boxes, the probabilitybecomes dependent on the area.Theorem 3.12. When we restrict the area of all boxes to be less than orequal to A,P ((xi±ρi)∩ (xi±ρj)) and P ((yi±σi)∩ (yj±σj)) are dependent.Hence,P (((xi ± ρi) ∩ (xj ± ρj) ̸= ø) ∩ ((yi ± σi) ∩ (yj ± σj) ̸= ø))= P ((yi±σi)∩(yj±σj) ̸= ø|(xi±ρi)∩(xj±ρj) ̸= ø)P ((xi±ρi)∩(xj±ρj) ̸= ø)≤ (rx + 2ρi)(A4σi+ 2σi).263.1. THE CONNECTIVITY THRESHOLDProof. Without loss of generality, suppose we fix (xi ± ρi), (xj ± ρj), thenA = 2σi ∗ 2ρi ≤ 2ry ∗ 2ρi ⇒ ry ≥ A4σi.Hence,P ((yi ± σi) ∩ (yj ± σj) ̸= ø|(xi ± ρi) ∩ (xj ± ρj) ̸= ø) = ry + 2σi≤ A4σi+ 2σi.Overall,P (((xi±ρi)∩(xj±ρj) ̸= ø)∩((yi±σi)∩(yj±σj) ̸= ø)) ≤ (rx+2ρi)(A4σi+ 2σi).With the above result, the connectivity threshold could be established.The following theorem is proved by Scheinerman [Sch90] for graphs gener-ated by B(n, r, 1). We include a more detailed proof to the theorem and webelieve that a similar threshold could also be established on box graphs.Theorem 3.13. [Sch90, Theorem 5.1] Suppose c = limn→∞ nrlog(n) exists. Ifc < 1 then almost all interval graphs have at least one isolated vertex. Ifc > 1 then almost all interval graphs do not have an isolated vertex.Proof. Suppose c < 1, and node i is assigned interval [xi−ρi, xi+ρi]. DefineXi to be the indicator value of the existence of an isolated vertex,Xi ={1, if d(i) = 0, xi ∈ [13 , 23 ]0, otherwise.(3.8)ThenE(Xi) = P (d(i) = 0, xi ∈[13,23])= P (d(i) = 0 |xi ∈[13,23])P (xi ∈[13,23])=[1r∫ r0(1− (r + 2ρi))n−1dρi](13)=(1− r)n − (1− 3r)n6rn.273.1. THE CONNECTIVITY THRESHOLDLet X =∑Xi. Take c =nrlog(n) , we haveE(X) = E(X1 +X2 + · · ·+Xn)= E(X1) + E(X2) + · · ·+ E(Xn)= n(1− r)n − (1− 3r)n6rn=n(1− r)n − n(1− 3r)n6c log(n)=n(1− log(n)n)n − n(1− 3 log(n)n )n6c log(n)≈ ne−c log(n) − ne−3c log(n)6c log(n)≈ n1−c − n1−3c6c log(n)→∞, as n→∞.Now we compute the second moment E(X2) = E(X)+n(n−1)E(X1X2)in order to use Chebyshev’s inequality.E(X1X2) = E(X1X2|1 ̸∼ 2)P (1 ̸∼ 2) + E(X1X2|1 ∼ 2)P (1 ∼ 2)=[(13)2 1r2∫ r0∫ r0(1− 2r − 2ρ1 − 2ρ2)n−2dρ1dρ2][1−O(r)] + 0=1−O(r)36r2n(n− 1) [(1− 2r)n − (1− 6r)n].ThenE(X2) =n(1− r)n − n(1− 3r)n6rn+1−O(r)36r2n(n− 1) [(1− 2r)n − (1− 6r)n],andE(X)2 =n2((1− r)n − (1− 3r)n)236r2n2.As we can see, E(X2) ∼ E(X)2, which means V ar(X) is relatively small.Applying Chebyshev’s inequality, for any real number k > 0,P (|X − E(X)| ≥ k√V ar(X)) ≤ 1k2.This implies that X is concentrated around its expect value E(X), and asshown above E(X)→∞ when n→∞, we could derive thatP (X > 0)→ 1.283.1. THE CONNECTIVITY THRESHOLDTherefore, when c < 1, it is guaranteed that all interval graphs will have atleast one isolated vertex.Now, in the case when c > 1, Scheinerman [Sch90] introduces the con-cept of a “broken end.”A broken end is defined as an endpoint of an intervalthat is not contained within any other interval.We first claim that there will be no broken end in ([0, r] ∪ [1− r]) whenc > 1. SupposeZi =1, if the right end point of vertex iis a broken end in([0, r] ∪ [1− r]),0, otherwise.(3.9)To derive an upper bound, we consider the extreme case when the intervalcenter xi = r(or 1 − r). Thus, we take an upper bound as shown in Figure3.5 and obtainE(Zi) ≤ r(1− r2)n−1=c log(n)n(1− c log(n)2n)n−1≈ c log(n)n(c log(n)2n)n=c log(n)n(c log(n)2n) 2nc log(n)c log(n)2≈ c log(n)ne−c log(n)2=c log(n)nn−c2= O(log(n)n32).Let Z =∑Zi, thenE(Z) =∑E(Zi)= nO(log(n)n32)→ 0 as n→∞.Now, our focus lies in determining the probability that the right endpointof vertex i’s interval is a broken end that falls within [r, 1− r]. This event is293.1. THE CONNECTIVITY THRESHOLDrepresented by the shaded area in Figure 3.6.Figure 3.5: Area representing the event when c > 1 and a right end pointof node i is a broken end in ([0, r] ∪ [1− r]).Figure 3.6: Shaded area representing the event when c > 1 and a right endpoint of node i is a broken end in [r, 1− r].Since we are considering only the right end point as a broken end, wecan focus on xi+ρi, as the interval center of another vertex xj ̸= xi+ρi. For[xi±ρi]∩ [xj±ρj ] ̸= ø, ρj has to be less than xj− (xi+ρi) and (xi+ρi)−xj .To calculate the probability of xi + ρi being a right broken end, we need toconsider the shaded area beside the two triangles. That isP (xi + ρi is a right broken end) =r − 2× r221× r=r − r2r= 1− r.303.1. THE CONNECTIVITY THRESHOLDWhen this right broken end lies in [r, 1 − r], we call this event Xi, andE(Xi) = (1− 2r)(1− r)n−1(1− r)n. SoE(X) =∑E(Xi) ≈ n(1− r)n= n(1− c log(n)n)n = ne−c log(n)= nelog(n−c) = n1−c → 0 as n→∞, where c > 1.Hence, if c > 1, almost all interval graphs have no isolated vertex.31Chapter 4GNN-Based Approach toInterval and Box GraphCompletion and EditingIn this chapter, we will describe the design of our GNN model tailored tosolve interval and box graph completion and editing problems, and discussthe details of our model and experimental results.4.1 Model ArchitectureOur GNN employs a graph convolutional architecture inspired by theGraphSAGE model[HYL17] with several modifications to suit the specificrequirements of our problem at hand.In our model M(n, b) : G → G′, given input graph G and a n × 2b fea-ture matrix xin for all vertices, we can reproduce a interval/box graph G′with the predicted n × 2b output feature matrix xfinal. Each row xini ={(lmi , rmi )},m = 1, 2, . . . , b in xin represents the assigned interval/box of ver-tex i in G, while each row xfinali = {(lmi , rmi )},m = 1, 2, . . . , b in xfinalencodes the interval/box of vertex i in G′, i = 1, 2, . . . , n. Here, lm and rmdenote the left and right end points of intervals along each dimension.The model establishes connections e′ij between vertices i and j based ontheir xfinali , xfinalj . For i, j = 1, . . . n, all e′ij form the adjacency matrix E′for predicted interval/box graph G′, that will be compared with the adja-cency matrix E of the original input graph G. The generated loss are usedfor backpropagation in our model.Our model consists of two modules: an encoder and a decoder. Theencoder is responsible for mapping the input graph to a hidden representa-324.1. MODEL ARCHITECTUREtion of vertices, while the decoder reconstructs a graph using the predictedrepresentations of vertices. In the following two sections, we will provide adetailed explanation of these two modules.Figure 4.1: A flowchart of our GNN model.4.1.1 EncoderThe encoder is made of two SageConv() layers and an attention layer,where the two SageConv() layers serve as the main building blocks for cap-turing the graph structure. These layers effectively aggregate informationfrom the local graph neighborhoods to capture the structural informationencoded in the graph.The first SageConv() layer takes a n×m input feature matrix xin andtransforms it into a n × hiddendim hidden representation matrix x′ withmean aggregation methodx′i =W1xi +W2 ·meanj∈N(i)xj , where W1,W2 are weights.The second SageConv() layer further refines the hidden representation,using the output from last layer as input, and outputs an enhanced hiddenrepresentation for vertices.Attention AggregationWe implement a specific attention aggregation layer to effectively cap-ture the structural information of interval and box graphs. Our aggre-gation method will apply a variation of the Scale Dot-Product Attention334.1. MODEL ARCHITECTUREmethod(Equation 2.1) by Vaswani et al.[VSP+17]. Each row xini in the in-put feature matrix xin of interval graph data has two entries that representthe two endpoints of the assigned interval of vertex i. Before aggregation,each interval represented by row xini is used to calculate that interval’s cen-ter point ci, for i = 1, . . . n. Each interval center ci is updated according tothe vertex’s connectedness with its d-neighbourhood , Nd(i):Md(i) =∑j∈Nd(i)(cj − ci)∑j∈Nd(i) 1, d = 1, 2, 3, 4, . . . , (4.1)cupdatei = ci +M1(i)−N∑d=2(Md(i)).By adding M1(i), the interval center of node i is moved closer to the in-terval center of all the neighbouring nodes that are adjacent to i. Similarly,by subtractingMd(i), the center of i is moved farther from all nodes that arenot adjacent to it. Parameter N is adjusted according to the neighborhoodsample size for each vertex.After the center calculation, each cupdatei is concatenated to its originalfeature vector xini as an extra entry. We will denote this updated featurematrix as xupdate, with each row xupdatei = (xini , cupdatei ). Then, we willapply the attention mechanism to the updated feature vectors. Node i ∈ Vin G(V,E) has attention vector:ai = LeakyRelu(wTi · [xupdatei , xupdatej ]), j ∈ Nd(i).Then we compute the neighbourhood information fNd(i) of node i andaggregate it to its feature vectorfNd(i) =∑j∈Nd(i) aj × xupdatej∑j∈Nd(i) aj, (4.2)xouti = Concat(xupdatei , fNd(i)).The output feature matrix xout is composed of the set of all xouti , wherei = 1, . . . , n. The flowchart in the Figure 4.2 depicts the process of thisattention aggregation.We apply the same format of attention aggregation to each dimensionof the boxes assigned to vertices in box graphs. However, instead of having344.1. MODEL ARCHITECTUREFigure 4.2: A flowchart of our attention aggregation process of node i.only one center point calculated for the one dimensional interval, we calcu-late two center points that represents the centers of the two intervals alongthe two dimensions of the box. Both of the calculated center values are thenconcatenated to the input feature vector of each node.To decide the maximum depth of a seed node’s d-neighborhood our GNNmodel would assess, we initially examine the diameter of the generated ran-dom interval and box graphs, as illustrated in Tables 4.1 and 4.2. We havechosen the ceiling of the average diameters for most graphs as the maxi-mum depth, except for interval graphs with a edge probability of 1100 . Inthe case of interval graphs with this edge probability, the average diame-ter is too high to be used as the depth for our model. Instead, we choosethe 2-neighborhood. Beyond this distance, the d-neighborhood lacks suffi-cient size to provide crucial information for our GNN to learn, striking abalance between the information learned and the associated learning cost.Figure 4.3 illustrates the ratio of the average d-neighborhood size sd of our354.1. MODEL ARCHITECTURErandomly generated interval graphs with edge probability p = 1100 , to theexpected neighborhood size in an Erdos-Renyi graph with edge probability1100 . Specifically, this ratio is calculated aslog10.24 sdd , where 10.24 is the ex-pected degree of each node in an Erdos-Renyi graph with edge probability1100 . Beyond the 2-neighborhood, this ratio is less than 0.8, and we interpretit as an insufficient neighborhood size for our model.edge probability 453423121314151101100Average diameter 2 2 2.97 3 4 5 6.8 12.3 60.3Table 4.1: Average diameter of random interval graphs with different den-sities.edge probability 453423121314151101100Average diameter 2 2 2 2.81 3 3.3 4 5 20.9Table 4.2: Average diameter of random box graphs with different densities.4.1.2 DecoderThe decoder comprises four Linear() layers that reduce the dimensionof the learned representations of vertices to the desired output dimension.The output feature vectors are used to calculate the adjacency matrix ofthe output graph. It simply applies a linear transformation to the incomingdata:y = xAT + b.The decoder takes the hidden representation obtained from the encoderas input and applies activation functions to introduce non-linearity into themodel. The dimensions of the Linear() layers are carefully designed tomap the hidden representations to the same dimension of interval/box rep-resentation required to recover the output graph, while ensuring a sufficientnumber of learning parameters.All linear layers together reduce the dimension of the feature vector ofeach vertex to 2 for interval graphs, and 4 for boxgraphs. Lastly, adjacencymatrix E′ is recovered according to these output vectors. Each entry e′ij inE′ is calculated as364.1. MODEL ARCHITECTUREFigure 4.3: A bar plot of the ratio of the average neighborhood size of ourrandomly generated interval graphs with edge probability p = 1100 , to theexpected neighborhood size in a Erdos Renyl graph with edge probabilityp = 1100 . The red line represents when ratio= 0.8.e′ij ={1, if xfinali ∩ xfinalj ̸= ø0, otherwise(4.3)Here, xfinali denotes row i of the final output feature matrix xfinal, whichstands for the predicted interval/box for vertex i.4.1.3 Loss FunctionsInterval and Box Graph Editing Our loss function for interval andbox graph editing problem is defined asLoss =n∑i=1√√√√ n∑j=1(e′ij − eij)2374.1. MODEL ARCHITECTUREOnce the adjacency matrix E′ of predicted graph G′ is obtained, theloss function calculates the euclidean distance between the feature vectorsof each vertex in the predicted graph G′ the input graph G.The edge set difference quantifies the dissimilarity between the predictedgraph structure and the input graph structure. This difference is computedby comparing the adjacency matrix of the predicted graph with the adja-cency matrix of the input graph. The squared difference provides a measureof how well the predicted graph aligns with the input graph structure. Thegoal is to minimize the loss as much as possible.Interval and Box Graph Completion In the interval graph completionproblem, we are only allowed to add edges. To apply our model to thisproblem, we distinguish between the addition and deletion of edges in ourloss function. We adjust our loss function by punishing the deletion of edges,which can be achieved by adding two new parameters αadd and αdel to ourmodel.Loss = αadd n∑i=1√√√√ n∑j=1(eaddij )2+ αdel n∑i=1√√√√ n∑j=1(edelij )2 , (4.4)whereeaddij ={1, if dij = 10, otherwise,and edelij ={1, if dij = −10, otherwise.(4.5)dij are entries of the matrix D, which measures the difference betweenthe adjacency matrix E of the original input graph and the adjacency matrixE′ of the predicted graph. It is calculated asD = E′ − E.The entries eaddij and edelij , where i, j ∈ 1, . . . , n, represent the additionof edges and deletion of edges respectively. This allows us to distinguishbetween the loss incurred due to the addition and deletion of edges. By ad-justing αadd and αdel, we could manipulate the proportion of edge additionand deletion to fulfill our purpose. In the interval and box graph comple-tion experiment, we have chosen αadd = 0.01 and αdel = 0.99 to maximizeaddition of edges during the recovery process.384.2. THE GENERATION OF TRAINING DATASET4.2 The Generation of Training DatasetWe generated data by using the random model B(n, r, b) introduced inChapter 3, with n = 1024. For both the training and testing data, we haveselected r values that provide a wide range of edge probabilities p, illustratedin Table 4.3(for interval graphs) and Table 4.4(for box graphs). As proven inTheorem 3.9, we can ensure that the produced graphs have average numberof edges p(n2).r 0.633 0.554 0.453 0.303 0.187 0.135 0.106 0.051 0.005p 453423121314151101100Table 4.3: r value with its corresponding edge probability p value in intervalgraphs generated with model B(n, r, 1).rx = ry 0.888 0.787 0.665 0.498 0.367 0.303 0.264 0.176 0.051p 453423121314151101100Table 4.4: r value with its corresponding edge probability p value in boxgraphs generated with model B(n, r, 2). This is under the assumption thatrx for x-parallel intervals and ry for y-parallel intervals are equal.The training dataset comprises 100 randomly generated interval/boxgraphs for each r value, while the test dataset includes 30 graphs for eachr value. Subsequently, all intervals associated with vertices are randomizedafter the graphs are generated. In the context of our research problem,we also introduce variations to a specified percentage of edges in the testdataset. Specifically, 0.1%, 1%, 5%, 10%, and 20% of the edges in test graphsare modified by altering their entries in the adjacency matrix from 0 to 1or from 1 to 0. The specific format of the file for the generated data aredetailed in appendix A.The chosen percentages are to ensure that the modified graph remainsapproximately the closest representation of the original interval/box graph.This approach allows the original graph to serve as the “ground truth” forperformance evaluation. We can assess our model’s performance by eval-uating the proportion of edges of the predicted graph that differ from theinput graph. This evaluation metric will then be compared to the actual394.3. RESULTSpercentage of edges that were altered before input, providing insights intothe model’s ability to reconstruct the minimal interval/box graph.4.3 ResultsIn our experiment, we evaluate the performance of our GNN by modeledited percentage calculated asModel Edited Percentage =Iadd + Idel|EG| .|EG| represents the number of edges in the original input graph G. Iaddand Idel represent number of edges added and number of edges removed,respectively. We haven’t identified a more suitable metric that aligns betterwith the problem setting. Consequently, we could explore the differencesbetween the output interval/box graph and the input graph.Performance on Interval Graph Editing and CompletionOur GNN produces results for interval graph editing shown in Table4.5, and interval graph completion shown in Table 4.6. In both tables, theinitial columns depicts the percentage of editing applied to the test graphsreferencing the “ground truth” graphs. The remaining entries in the tablerepresent the average model edited percentage between the recovered graphsand the input graphs.Overall, our GNN demonstrates its effectiveness in solving interval graphediting and completion problems, as evidenced in Table 4.5 and Table 4.6.Cells highlighted in these tables indicate when our GNN successfully recon-structs the interval graph with a model edited percentage difference of lessthan 5% compared to the percentage of editing applied to test graphs refer-encing the “ground truth” graphs. The best-case scenario results in a 0%difference between the model edited percentage and the editing percentageapplied to the test graphs. It is crucial to acknowledge that certain resultsmay deviate below the expected edited percentage of the graph due to thechallenge of guaranteeing that the edited test graphs are indeed the closestapproximation to our designated “ground truth.”404.3. RESULTSp/Modified % 45342312131415110110020% 21% 22% 20% 21% 23% 28% 32% 53% 59%10% 20% 20% 18% 19% 23% 27% 31% 51% 57%5% 18% 21% 19% 18% 22% 25% 29% 48% 55%1% 16% 15% 13% 14% 20% 22% 27% 49% 52%0.1% 12% 11% 10% 10% 18% 20% 25% 44% 48%Table 4.5: Result of GNN on interval graph editing in terms of model editedpercentage.p/Modified % 45342312131415110110020% 18% 19% 17% 17% 20% 25% 28% 45% 61%10% 17% 17% 15% 15% 20% 24% 27% 43% 58%5% 15% 18% 16% 14% 19% 21% 26% 41% 56%1% 13% 12% 10% 11% 17% 18% 24% 38% 52%0.1% 8% 8% 7% 8% 15% 17% 22% 36% 49%Table 4.6: Result of GNN on interval graph completion in terms of modeledited percentage.In our experiment, we explored different formats for representing inter-vals associated with vertices in the input graph. We employed three distinctapproaches:1. The center and radius of the interval [c, ρ].2. The left and right endpoints of the interval [c− ρ, c+ ρ].3. The combination of left and right endpoints, along with the center andradius of the interval [c− ρ, c+ ρ, c, ρ].Surprisingly, we observed that the choice of input feature vector formatdid not significantly impact the performance of our GNN model. Through-out all experiments, we consistently used the left and right endpoints of theinterval [c− ρ, c+ ρ] as the input feature vectors of all vertices.414.3. RESULTSp/Modified % 45342312131415110110020% 30% 29% 30% 29% 33% 37% 40% 61% 73%10% 29% 28% 28% 27% 32% 35% 38% 58% 70%5% 28% 26% 27% 25% 31% 34% 37% 55% 67%1% 26% 24% 23% 23% 30% 33% 36% 52% 64%0.1% 24% 22% 20% 20% 28% 30% 33% 50% 61%Table 4.7: Result of GNN on box graph editing in terms of model editedpercentage.p/Modified % 45342312131415110110020% 37% 38% 37% 36% 37% 46% 49% 66% 76%10% 35% 37% 35% 34% 37% 43% 46% 64% 72%5% 34% 35% 34% 32% 35% 42% 44% 61% 70%1% 32% 34% 32% 30% 32% 40% 42% 57% 68%0.1% 28% 32% 30% 29% 28% 38% 40% 54% 67%Table 4.8: Result of GNN on box graph completion in terms of model editedpercentage.Performance on Box Graph Editing and CompletionResults of our model for box graph editing are shown in Table 4.7, andthese for box graph completion are shown in Table 4.8. The evaluationmetric remains consistent with that employed for interval completion andediting problems.Although the pattern of performance aligns with that observed in in-terval graph completion and editing, it is important to highlight that theperformance on box graph completion and editing is relatively suboptimal.Our GNN’s ability to recover box graphs is limited, with the best-case sce-nario achieving only a 9% difference between the model edited percentageand the editing percentage applied to the test graphs. Instances where thesedifferences are less than 10% are highlighted in Table 4.7 and Table 4.8.In all the experiments, as the editing percentage applied to the testgraphs decreases, the corresponding model edited percentage exhibits aslower decrease. This observation implies a reduction in the recovery rate,424.3. RESULTSsuggesting that our GNN is not highly sensitive to changes in the test graphs.In the rest of this section, we will analyze the result focusing on three keyaspects: assessing the correlation between the GNN’s performance and thegraph edge probability, the impact of graph boxicity on GNN’s performance,and evaluating the GNN’s performance in both completion and editing.Graph edge probabilityFor sparse graphs, especially in extreme cases when edge probabilityp = 1100 , the results are not as ideal as those ones on denser graphs. Thisdiscrepancy arises from several factors.In our model edited percentage calculation, the denominator |EG| repre-sents the number of edges in the original input graph. We speculate that asthe graph edge probability decreases, this denominator decreases at a higherrate compared to the numerator Iadd + Idel. This suggests a limitation inthe learning capacity of our GNN model on sparse graphs.The inherent nature of GNN is to acquire information from edges. Asthe edge probability of the graph decreases, there are fewer edges availablefor GNN to extract information from. This diminishes the learning processfor GNN in sparse graphs, impacting its performance negatively.In the initial stages of our experiment, we did not employ any data fil-tering techniques on the input graphs. By analyzing the adjacency matricesof the graphs, we found that sparse graphs of edge probability p = 1100 nor-mally contain isolated components. Table 4.9 and Table 4.10 present theaverage number of isolated components of various sizes for random intervaland box graphs generated using the B(n, r, b) model. We suspect that thepresence of isolated vertices not only results in poor performance but alsocontributes to fluctuations in loss.Consequently, we implemented data filtering before feeding the graphsinto the GNN model. In our experiment, we excluded all isolated verticesprior to inputting the data into our GNN. Table 4.11, Table 4.12, Table 4.13,and Table 4.14 illustrate the impact of data filtering on GNN’s performanceacross four tasks when the graph edge probability p = 1100 , measured interms of model edited percentage. Figures 4.4 and 4.5 provide a compari-son of the training loss over steps with and without the application of data434.3. RESULTSp/component size 4534231213141511011001 0 0 0 0 0 0 0 0 0.672-100 0 0 0 0 0 0 0 0 3.10101-300 0 0 0 0 0 0 0 0 2.57301 and above 1 1 1 1 1 1 1 1 0.90Table 4.9: Average number of isolated components with different sizes forrandom interval graphs.p/component size 4534231213141511011001 0 0 0 0 0 0 0 0 4.512-100 0 0 0 0 0 0 0 0 0.20101-300 0 0 0 0 0 0 0 0 0.00301 and above 1 1 1 1 1 1 1 1 1.00Table 4.10: Average number of isolated components with different sizes forrandom box graphs.filtering. Note that these results were generated during the initial phase ofour model development, prior to the application of the attention aggregationmethod or parameter adjustments.As indicated by the results, the integration of data filtering enhances theconvergence curve of loss and improves model performance. Prior to filter-ing out isolated vertices, the loss in the four sets of experiments exhibitsfluctuations. Post data filtering, the loss values converge, resulting in en-hanced performance in terms of model edited percentage. In summary, wecan infer that, within the defined parameters of our model and dataset, thepresence of isolated vertices in sparse graphs adversely affects our model’sperformance.Editing and CompletionOur experiments highlight the difference between editing and completionfor interval and box graphs, as well as its impact to the performance of ourGNN approach. The performance on interval graph completion is betterthan the performance on interval graph editing. We observed that solutions444.3. RESULTSFiltering/Modified % With data filtering Without data filtering20% 74% 84%15% 71% 80%5% 69% 79%1% 68% 77%0.1% 64% 73%Table 4.11: Comparison of GNN’s performance on interval editing, withgraph edge probability p = 1100 , with and without data filtering, in terms ofmodel edited percentage.Filtering/Modified % With data filtering Without data filtering20% 70% 78%15% 66% 76%5% 65% 75%1% 62% 73%0.1% 58% 68%Table 4.12: Comparison of GNN’s performance on interval completion, withgraph edge probability p = 1100 , with and without data filtering, in terms ofmodel edited percentage.to interval graph editing is primarily achieved through the addition of edges.As a result, maximizing edge additions simplifies the task for GNN, reducingit from two operations to predominantly one operation, thereby enhancingperformance.It is surprising to observe that the box graph completion yields worseresults than the box graph editing. Our model appears to face greater diffi-culty in recovering intervals for box graph completion compared to editing.The recovery process in box graph editing typically involves a small numberof modifications, with a significant proportion being deletions rather thanadditions of edges. This may be attributed to the fact that, in a box graph,only one set out of the two sets of intervals along the two dimensions needs tobe non-intersecting for the two nodes to not have an edge between them. Incontrast, interval graphs have only one dimension, requiring non-intersectionacross all intervals along all dimensions. As a result, when maximizing the454.3. RESULTSFiltering/Modified % With data filtering Without data filtering20% 78% 89%15% 76% 87%5% 74% 85%1% 73% 81%0.1% 69% 78%Table 4.13: Comparison of GNN’s performance on box editing, with graphedge probability p = 1100 , with and without data filtering, in terms of modeledited percentage.Filtering/Modified % With data filtering Without data filtering20% 86% 94%15% 84% 92%5% 82% 90%1% 80% 89%0.1% 77% 86%Table 4.14: Comparison of GNN’s performance on box completion, withgraph edge probability p = 1100 , with and without data filtering, in terms ofmodel edited percentage.addition of edges, the performance of our GNN tends to suffer.Graph BoxicityAs mentioned, the performance of GNN on box graph related tasks arenot as ideal as it is on interval graph related tasks. This discrepancy canbe attributed to the increased dimensionality associated with box graphs ascompared to interval graphs. In our experiment design, intervals along thesetwo dimensions are treated as independent variables. As boxicity increase,it becomes harder for GNN to learn the right model to predict both intervalscorrectly and it leads to inferior results.464.3. RESULTSParameter/Edited % θ applied θ not applied20% 59% 67%15% 57% 65%5% 55% 64%1% 52% 60%0.1% 48% 55%Table 4.15: Result of GNN on highly sparse interval graph editing withlearnable distance parameter during aggregation, with graph edge probabil-ity p = 1100 , in terms of model edited percentage.Original neighbor distance Learned average θ Average θd1 1.65 1.652 2.83 1.42Table 4.16: Learned neighbourhood distance by GNN in interval editing,with graph edge probability p = 1100 , in terms of model edited percentage.4.3.1 Learnable neighbourhood distance parameterIn order to address the sub-optimal outcomes observed in sparse graphswith edge probability p = 1100 , we embarked on a novel design approach. Inthis updated configuration, we introduce a set of additional learnable dis-tance parameters Θ = (θdij |i = 1, 2, . . . , n, j = 1, 2, . . . , n−1, d = 1, 2, 3, 4, . . . ),one for each node, to emphasize the use of center calculation (Equation 4.1)in our attention aggregation method. The revised formula is as follows:Md(i) =∑j∈Nd(i)θdijd × (cj − ci)∑j∈Nd(i)θdijd, d = 1, 2, 3, 4, . . .Here, θdij represents the learned distance parameter for every node j in thed-neighborhood of node i. Subsequently, we determine the scaling parame-terθdijd , which scales the center calculation process by the learned distancesθdij .The average learned θdij values and their corresponding scaling param-eter for 1-neighborhood and 2-neighborhood of all nodes are presented inthe Table 4.16 for a randomly selected interval graph with edge probability474.3. RESULTSp = 1100 . It is evident that the learned distance parameter θdij surpassesthe actual neighborhood distance d. This improves the center calculation inthe aggregation process in both aspects—centers pulling closer and pushingfurther away. Results in Table 4.15 highlights the effectiveness of our GNNin learning a suitable distance parameter for center distance calculation, ef-fectively leveraging information from neighborhood at different distances.While the results obtained are still not yet optimal, there is clear evi-dence of improvement in the interval graph editing. The learned distanceparameter enhances our GNN’s ability to understand the importance of dis-tances between intervals’ centers of neighboring vertices. This improvementcontributes to the GNN’s capability to predict intervals that reconstructsthe desired graph more accurately.484.3. RESULTSFigure 4.4: Training loss over steps for: A) Interval graph editing with datafiltering(top left), B) Interval graph editing without data filtering(top right),C)Interval graph completion with data filtering(bottom left), D)Intervalgraph completion without data filtering(bottom right).494.3. RESULTSFigure 4.5: Training loss over steps for: A) Box graph editing with datafiltering(top left), B) Box graph editing without data filtering(top right),C)Box graph completion with data filtering(bottom left), D)Box graph com-pletion without data filtering(bottom right).50Chapter 5ConclusionsThis thesis leverages deep learning to address the graph editing/completionproblem, specifically focusing on interval graphs and box graphs. The inter-val and box graph editing/completion problems hold significance in variousapplications, such as scheduling, resource allocation, and network design.We have designed a Graph Neural Network (GNN) model to address intervaland box graph editing/completion problems as an alternative to traditionalapproaches, introducing an aggregation method with attention mechanismthat enhances the capture of structural information crucial for our task. Ad-ditionally, we formulated a random model for generating interval and boxgraphs to train our model. Throughout our exploration, we encountered aspectrum of results.Some aspects of our research yielded quite promising outcomes, demon-strating the power of our GNN model in addressing graph editing challenges.Our GNN model achieved a minimal difference of 0% for interval graph re-lated tasks, and 9% for box graph related tasks, between the model editedpercentage and the editing percentage applied to test graphs.However, it is important to acknowledge that not all aspects of our re-search produced outstanding results. Specifically, we observed that it is chal-lenging for our GNN model to handle sparse graphs. To improve our model’sperformance in such scenarios, we applied data filtering which removes iso-lated vertices from our training data. At the same time, the introduction ofa learnable distance parameter to the attention aggregation process resultedin an improvement in the performance of the interval editing. Overall, ourresearch has established a foundation for future exploration and refinement.Looking ahead, the direction for future work is clear. We must continueto refine and expand our methodologies, striving for even better results andbroader applicability. In our experiments, we have only included isolatedvertices in our data filtering process. The impact of isolated components re-mains untested. To address this, it is necessary to develop a random model51similar to B(n, r, b) with control over the existence, size, number, and struc-ture of isolated components. This will enable the assessment of GNN’sfeasibility in handling these isolated components for interval and box graphcompletion.Furthermore, there are properties of random graphs generated with modelB(n, r, b) that we have not yet explored. Understanding the relationship be-tween the parameter r and the bound d of the diameter of the graph wouldsignificantly assist in determining the neighborhood sampling size in the ag-gregation process of our GNN model, and potential leads to improvementin model’s performance. Partial results have been obtained using a charac-terization of the diameter of interval graphs in terms of dominating path1.This indicates that unlike the situation in an Erdos-Renyi graph, the modelB(n, r, b) undergoes a series of phase transitions in terms of its diameter.1Personal communication with Dr. Jim Nastos and Dr. Congsong Zhang52Bibliography[AQSL22] Baole Ai, Zhou Qin, Wenting Shen, and Yong Li. Structureenhanced graph neural networks for link prediction. arXivpreprint arXiv:2201.05293, 2022. → pages 12[BCB14] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.Neural machine translation by jointly learning to align andtranslate. arXiv preprint arXiv:1409.0473, 2014. → pages 15[BNBYF+01] Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, JosephNaor, and Baruch Schieber. A unified approach to approx-imating resource allocation and scheduling. Journal of theACM (JACM), 48(5):1069–1090, 2001. → pages 6[DHH96] Xiaotie Deng, Pavol Hell, and Jing Huang. Linear-time repre-sentation algorithms for proper circular-arc graphs and properinterval graphs. SIAM Journal on Computing, 25(2):390–403,1996. → pages 8[FBSBH17] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur.Protein interface prediction using graph convolutional net-works. Advances in neural information processing systems,30, 2017. → pages 11[GH64] Paul C Gilmore and Alan J Hoffman. A characterization ofcomparability graphs and of interval graphs. Canadian Jour-nal of Mathematics, 16:539–548, 1964. → pages 1, 5[Gol04] Martin Charles Golumbic. Algorithmic graph theory and per-fect graphs. Elsevier, 2004. → pages 6[GSP09] Roger Guimera` and Marta Sales-Pardo. Missing and spuriousinteractions and the reconstruction of complex networks. Pro-ceedings of the National Academy of Sciences, 106(52):22073–22078, 2009. → pages 153Bibliography[Ham20] William L Hamilton. Graph representation learning. Morgan& Claypool Publishers, 2020. → pages 10[HOSM17] Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and YujiMatsumoto. Knowledge transfer for out-of-knowledge-baseentities: A graph neural network approach. arXiv preprintarXiv:1706.05674, 2017. → pages 11[HPTV07] Pinar Heggernes, Christophe Paul, Jan Arne Telle, and Yn-gve Villanger. Interval completion with few edges. In Proceed-ings of the thirty-ninth annual ACM symposium on Theory ofcomputing, pages 374–381, 2007. → pages 1[HSTV05] Pinar Heggernes, Karol Suchan, Ioan Todinca, and YngveVillanger. Minimal interval completions. In Algorithms–ESA2005: 13th Annual European Symposium, Palma de Mallorca,Spain, October 3-6, 2005. Proceedings 13, pages 403–414.Springer, 2005. → pages 1, 8[HYL17] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductiverepresentation learning on large graphs. Advances in neuralinformation processing systems, 30, 2017. → pages 13, 14, 32[KL11] Myunghwan Kim and Jure Leskovec. The network comple-tion problem: Inferring missing nodes and edges in networks.In Proceedings of the 2011 SIAM international conference ondata mining, pages 47–58. SIAM, 2011. → pages 1[KNG+20] Abdullah Khanfor, Amal Nammouchi, Hakim Ghazzai,Ye Yang, Mohammad R Haider, and Yehia Massoud. Graphneural networks-based clustering for social internet of things.In 2020 IEEE 63rd International Midwest Symposium on Cir-cuits and Systems (MWSCAS), pages 1056–1059. IEEE, 2020.→ pages 12[KST99] Haim Kaplan, Ron Shamir, and Robert E Tarjan. Tractabil-ity of parameterized completion problems on chordal, stronglychordal, and proper interval graphs. SIAM Journal on Com-puting, 28(5):1906–1922, 1999. → pages x, 1, 5, 8, 9[KW52] Jack Kiefer and Jacob Wolfowitz. Stochastic estimation ofthe maximum of a regression function. The Annals of Math-ematical Statistics, pages 462–466, 1952. → pages 1054Bibliography[KW16] Thomas N Kipf and Max Welling. Semi-supervised classi-fication with graph convolutional networks. arXiv preprintarXiv:1609.02907, 2016. → pages 13[LB62] C Lekkeikerker and Johan Boland. Representation of a fi-nite graph by a set of intervals on the real line. FundamentaMathematicae, 51:45–64, 1962. → pages 6[LdC10] Isabel Cristina Lopes and JM Vale´rio de Carvalho. An inte-ger programming model for the minimum interval graph com-pletion problem. Electronic Notes in Discrete Mathematics,36:583–590, 2010. → pages 1[McD89] Colin McDiarmid. On the method of bounded differences.Surveys in combinatorics, 141(1):148–188, 1989. → pages 22[MRS95] Berndt Mu¨ller, Joachim Reinhardt, and Michael T Strick-land. Neural networks: an introduction. Springer Science &Business Media, 1995. → pages 9[Mu¨l23] Emmanuel Mu¨ller. Graph clustering with graph neural net-works. Journal of Machine Learning Research, 24:1–21, 2023.→ pages 12[New04] Mark EJ Newman. Detecting community structure in net-works. The European physical journal B, 38:321–330, 2004.→ pages 7[NG13] James Nastos and Yong Gao. Familial groups in social net-works. Social Networks, 35(3):439–450, 2013. → pages 7[PC06] Sheng-Lung Peng and Chi-Kang Chen. On the interval com-pletion of chordal graphs. Discrete applied mathematics,154(6):1003–1010, 2006. → pages 1[RAK91] Ramamurthy Ravi, Ajit Agrawal, and Philip Klein. Or-dering problems approximated: single-processor schedulingand interval graph completion. In Automata, Languages andProgramming: 18th International Colloquium Madrid, Spain,July 8–12, 1991 Proceedings 18, pages 751–762. Springer,1991. → pages 855Bibliography[Rob69] F. S. Roberts. On the boxicity and cubicity of a graph. InW. T. Tutte, editor, Recent Progress in Combinatorics, pages301–310. Academic Press, New York, 1969. → pages 5[RST06] Ivan Rapaport, Karol Suchan, and Ioan Todinca. Minimalproper interval completions. In International Workshop onGraph-Theoretic Concepts in Computer Science, pages 217–228. Springer, 2006. → pages 1[Sch90] Edward R Scheinerman. An evolution of interval graphs. Dis-crete Mathematics, 82(3):287–302, 1990. → pages iii, 17, 18,25, 27, 29[SKB+18] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, RianneVan Den Berg, Ivan Titov, and Max Welling. Modeling rela-tional data with graph convolutional networks. In The Seman-tic Web: 15th International Conference, ESWC 2018, Herak-lion, Crete, Greece, June 3–7, 2018, Proceedings 15, pages593–607. Springer, 2018. → pages 1[ST06] Karol Suchan and Ioan Todinca. Minimal interval comple-tion through graph exploration. In Algorithms and Computa-tion: 17th International Symposium, ISAAC 2006, Kolkata,India, December 18-20, 2006. Proceedings 17, pages 517–526.Springer, 2006. → pages 8[TY84] Robert E Tarjan and Mihalis Yannakakis. Simple linear-timealgorithms to test chordality of graphs, test acyclicity of hy-pergraphs, and selectively reduce acyclic hypergraphs. SIAMJournal on computing, 13(3):566–579, 1984. → pages 8[VHPT09] Yngve Villanger, Pinar Heggernes, Christophe Paul, andJan Arne Telle. Interval completion is fixed parametertractable. SIAM Journal on Computing, 38(5):2007–2020,2009. → pages 1[VSP+17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszko-reit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and IlliaPolosukhin. Attention is all you need. Advances in neuralinformation processing systems, 30, 2017. → pages 15, 34[WCP+22] Lingfei Wu, Peng Cui, Jian Pei, Liang Zhao, and Le Song.Graph neural networks. Springer, 2022. → pages 10, 1156Bibliography[ZC18] Muhan Zhang and Yixin Chen. Link prediction based ongraph neural networks. Advances in neural information pro-cessing systems, 31, 2018. → pages 1, 12[ZCC+23] Peiliang Zhang, Jiatao Chen, Chao Che, Liang Zhang, Bo Jin,and Yongjun Zhu. Iea-gnn: Anchor-aware graph neural net-work fused with information entropy for node classificationand link prediction. Information Sciences, 634:665–676, 2023.→ pages 12[ZCZ+19] Fan Zhou, Chengtai Cao, Kunpeng Zhang, Goce Trajcevski,Ting Zhong, and Ji Geng. Meta-gnn: On few-shot node clas-sification in graph meta-learning. In Proceedings of the 28thACM International Conference on Information and Knowl-edge Management, pages 2357–2360, 2019. → pages 12[ZLT+23] Huaisheng Zhu, Dongsheng Luo, Xianfeng Tang, Junjie Xu,Hui Liu, and SuhangWang. Self-explainable graph neural net-works for link prediction. arXiv preprint arXiv:2305.12578,2023. → pages 157Appendices58Appendix ATraining Data FormatFor each graph generated, two CSV files are provided. One file recordsthe graph’s structure(Table A.1), containing three columns: Head, Tail, andLink. Head and Tail represent the indices of the two end nodes for all pos-sible node pairs in the graph, while Link is assigned either 0 or 1 to indicatenon-edge and edge, respectively.The other file contains the input feature vector for each node. Entriesare separated by ’|’. In the case of interval graphs(Table A.2), each node isassigned a single interval, represented by two endpoints in the format:[interval left end|interval right end]For box graphs(Table A.3), nodes have two intervals, which are repre-sented using four entries. Additionally, a fifth dimension is included to de-note the area of the box. While this area information is not utilized in ourthesis experiment, it is retained for potential future experiments involvingarea-related restrictions:[[x-interval]|[y-interval]|Area]All interval endpoints are preserved with precision to 16 decimal placessince these intervals center and radius fall within the [0, 1] range, and thislevel of precision allows for distinguishing subtle differences.59Appendix A. Training Data FormatTable A.1: Example of the CSV file recording node feature of a intervalrepresentation of the graph in Figure 2.1.NodeID intervals1 0.4745980364758175|0.85784938293758482 0.7578493509475878|0.90853641243567353 0.0365178354784638|0.35684210965843654 0.2258769438162756|0.50714983675209845 0.4645930764708175|0.6847012903675084Table A.2: Example of the CSV file recording edges and non-edges of ainterval representation of the graph in Figure 2.1, as well as a box represen-tation of the graph in Figure 2.2.head tail link1 2 11 3 01 4 11 5 12 3 02 4 02 5 03 4 13 5 04 5 160Appendix A. Training Data FormatTableA.3:ExampleoftheCSVfilerecordingnodefeatureofaboxrepresentationofthegraphinFigure2.2.NodeIDboxes10.4745980364758175|0.6278493829375848|0.2358469845700132|0.6650014795831684|0.065768504200885820.5878493509475878|1.0285364124356735|0.1601478569210349|0.3719703468103849|0.093347430626427330.1365178354784638|0.3668421096584365|0.4570468128125846|0.6571641634123441|0.046091883527708740.4058769438162756|0.5771498367520984|0.5648845154815151|1.0044541200472971|0.075286357820637150.5445930764708175|0.7847012903675084|0.5025413251486401|0.6625415480247146|0.038417367737846761Appendix BVisualization of SampleGraphsFigure B.1: Visualization of a random interval graph with edge probabilityp = 1100 , n = 1024.62Appendix B. Visualization of Sample GraphsFigure B.2: Visualization of a random box graph with edge probability1100 , n = 1024.63
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Gao, Yong
A graph neural network approach to interval and box graph completion problems
Text
Dataset
Software