Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Fatemi, Bahare
Doctor of Philosophy - PhD
University of British Columbia
The world around us is composed of objects each having relations with other objects. The objects and relations form a (hyper)graph with objects as nodes and relations between objects as (hyper)edges. When learning, the underlying structure representing the relations between the nodes is either given explicitly in the training set or is implicit and needs to be inferred. This dissertation studies graph representation learning with both explicit and implicit structures. For explicit structure, we first tackle the challenge of enforcing taxonomic information while embedding entities and relations. We prove that some fully expressive models cannot respect subclass and subproperty information. With minimal modifications to an existing knowledge graph completion method, we enable the injection of taxonomic information. A second challenge is in representing explicit structures in relational hypergraphs that contain relations defined on an arbitrary number of entities. While techniques, such as reification, exist that convert non-binary relations into binary ones, we show that current embedding-based methods do not work well out of the box for knowledge graphs obtained through these techniques. We introduce embedding-based methods that work directly with relations of arbitrary arity. We also develop public datasets, benchmarks, and baselines and show experimentally that the proposed models are more effective than the baselines. We further bridge the gap between relational algebra and knowledge hypergraphs by proposing an embedding-based model that can represent relational algebra operations. Having introduced novel architectures for explicitly graph-structured data, we further investigate how models with relational inductive biases can be developed and applied to problems with implicit structures. Graph representation learning models work well when the structure is explicit. However, this structure may not always be available in real-world applications. We propose the Simultaneous Learning of Adjacency and graph neural network Parameters with Self-supervision, or SLAPS, a method that provides more supervision for inferring a graph structure through self-supervision. An experimental study demonstrates that SLAPS scales to large graphs with hundreds of thousands of nodes and outperforms several baselines on established benchmarks.
Representation Learning with Explicitand Implicit Graph StructuresbyBahare FatemiB.Sc., Amirkabir University of Technology, 2015M.Sc., The University of British Columbia, 2017A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)April 2023© Bahare Fatemi 2023The following individuals certify that they have read, and recommend to theFaculty of Graduate and Postdoctoral Studies for acceptance, the disserta-tion entitled: Representation learning with explicit and implicit graph structuressubmitted by Bahare Fatemi in partial fulfillment of the requirements forthe degree of Doctor of Philosophy in Computer Science.Examining Committee:David Poole, Professor, Computer Science, UBCSupervisorLeonid Sigal, Professor, Computer Science, UBCSupervisory Committee MemberJeff Clune, Associate Professor, Computer Science, UBCUniversity ExaminerDaniel J. McDonald, Associate Professor, Statistics, UBCUniversity ExaminerAdditional Supervisory Committee Members:Frank Wood, Associate Professor, Computer Science, UBCSupervisory Committee MemberWilliam L. Hamilton, Adjunct Professor, Computer Science, McGillSupervisory Committee MemberiiAbstractThe world around us is composed of objects each having relations withother objects. The objects and relations form a (hyper)graph with objectsas nodes and relations between objects as (hyper)edges. When learning, theunderlying structure representing the relations between the nodes is eithergiven explicitly in the training set or is implicit and needs to be inferred.This dissertation studies graph representation learning with both explicitand implicit structures. For explicit structure, we first tackle the challengeof enforcing taxonomic information while embedding entities and relations.We prove that some fully expressive models cannot respect subclass and sub-property information. With minimal modifications to an existing knowledgegraph completion method, we enable the injection of taxonomic information.A second challenge is in representing explicit structures in relational hyper-graphs that contain relations defined on an arbitrary number of entities.While techniques, such as reification, exist that convert non-binary rela-tions into binary ones, we show that current embedding-based methods donot work well out of the box for knowledge graphs obtained through thesetechniques. We introduce embedding-based methods that work directly withrelations of arbitrary arity. We also develop public datasets, benchmarks,and baselines and show experimentally that the proposed models are moreeffective than the baselines. We further bridge the gap between relational al-gebra and knowledge hypergraphs by proposing an embedding-based modelthat can represent relational algebra operations. Having introduced novel ar-chitectures for explicitly graph-structured data, we further investigate howmodels with relational inductive biases can be developed and applied toproblems with implicit structures. Graph representation learning modelswork well when the structure is explicit. However, this structure may notalways be available in real-world applications. We propose the Simulta-neous Learning of Adjacency and graph neural network Parameters withSelf-supervision, or SLAPS, a method that provides more supervision forinferring a graph structure through self-supervision. An experimental studydemonstrates that SLAPS scales to large graphs with hundreds of thousandsof nodes and outperforms several baselines on established benchmarks.iiLay SummaryOn a day-to-day basis, we make predictions about the world to help us makeinformed decisions. For instance, we predict whether we will like a moviebefore deciding to watch it or whether it will rain before taking an umbrellawhen going outside. This research develops computational techniques andrepresentations that use available data about the world to make predictionsabout unknown events. In particular, this research makes predictions aboutthe world when there is a notion of structure in the data: that is datapoints are related to each other with different types of relationships. Forinstance, predicting if each member of the family will like the movie giventheir relationships with each other and some of the movies they have likedbefore. This research can exploit the given or hidden relationships amongthe data points for making a better prediction.iiiPrefaceIn what follows, the contribution of all authors for each publication resultingfrom this research is explained in detail.1. Bahare Fatemi, Siamak Ravanbakhsh, and David Poole. ImprovedKnowledge Graph Embedding Using Background Taxonomic Informa-tion, Proceedings of the AAAI Conference on Artificial Intelligence,2019 ([39]).The idea of enforcing taxonomic information into entity and relationembeddings started in our lab meetings. David Poole and I spentseveral weekly meetings discussing if existing models can enforce tax-onomic information. We proved that most successful models for linkprediction are not able to enforce taxonomic information. We spentmore meetings on how to design a model that can provably enforcetaxonomies. I designed and implemented the final model in our discus-sions and also conducted experiments to analyze the model. SiamakRavanbakhsh helped us with his thorough feedback in the process,suggesting relevant work, and also proofreading and editing the paperbefore submission. This work is discussed in Chapter 3.2. Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole.Knowledge Hypergraphs: Prediction Beyond Binary Relations, Pro-ceedings of the International Joint Conferences on Artificial Intelli-gence, 2020 ([40]).After studying previous work on knowledge graph completion, DavidPoole and I started questioning whether current models can handlebeyond binary (n-ary) relations. At the same time, I discussed theidea of designing models for n-ary relations with Perouz Taslakianand David Vazquez and they were both interested in collaborating onthis project. The whole team met weekly and discussed the updatespresented by me. I was mainly responsible for creating datasets, base-lines, and new models for knowledge hypergraph completion. Duringthe whole process, I received constructive feedback on proposed mod-ivPrefaceels and experimental and theoretical analyses from all the authors.Sections 4.1 and 4.2 are entirely based on this publication.3. Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole.Knowledge Hypergraph Embedding Meets Relational Algebra, Journalof Machine Learning Research, 2023 ([42]).After finishing our previous work (Knowledge Hypergraphs: PredictionBeyond Binary Relations), the team continued working on designingcompletion models. The initial idea of proposing an embedding modelbased on relational algebra came from David Poole. I was mainly re-sponsible for designing a model that can capture relational algebraoperations, studying whether the current version of the model cancapture such operations, and modifying the model to reflect our theo-retical analysis. I also implemented and conducted experiments on theproposed model. The whole team met regularly to discuss the theoret-ical and experimental analyses. Section 4.3 discusses this publication.4. Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. SLAPS:Self-Supervision Improves Structure Learning for Graph Neural Net-works, Advances in Neural Information Processing Systems (NeurIPS),2021 ([41]).This work was done during my internship at Borealis AI. When I joinedBorealis AI for my internship, Mehran had a proposal on extendingthe applicability of graph neural networks to implicit graph structures.Initially, I did a literature review on this problem. Layla, Mehran, andI discussed related work and potential ideas in our weekly meeting.After careful studying of existing models, we identified the supervisionstarvation problem and came up with the idea of using self-supervisionto improve upon existing models. I was responsible for designing andimplementing SLAPS and also conducting thorough theoretical andexperimental analyses. Chapter 5 is entirely based on this publication.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivList of Software Packages . . . . . . . . . . . . . . . . . . . . . . . xixAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Machine Learning and Structure . . . . . . . . . . . . . . . . 11.2 Learning with Explicit Structure . . . . . . . . . . . . . . . . 21.3 Learning with Implicit Structure . . . . . . . . . . . . . . . . 42 Background and Notation . . . . . . . . . . . . . . . . . . . . 52.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Learning on Graphs . . . . . . . . . . . . . . . . . . . . . . . 62.2.1 Types of Graphs . . . . . . . . . . . . . . . . . . . . . 62.2.2 Tasks on Graphs . . . . . . . . . . . . . . . . . . . . . 92.3 Knowledge Graphs and Hypergraphs . . . . . . . . . . . . . 112.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 112.3.2 Knowledge Graph Completion Methods . . . . . . . . 122.4 Graph Neural Networks . . . . . . . . . . . . . . . . . . . . . 142.4.1 Motivation and Intuition . . . . . . . . . . . . . . . . 14viTable of Contents2.4.2 Graph Convolutional Networks . . . . . . . . . . . . . 142.5 Ranking-based Evaluation Metrics . . . . . . . . . . . . . . . 173 Incorporating Ontological Information . . . . . . . . . . . . 183.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 193.3 Background and Notation . . . . . . . . . . . . . . . . . . . . 213.4 Tensor Factorization and Taxonomies . . . . . . . . . . . . . 223.5 Proposed Variation: SimplE+ . . . . . . . . . . . . . . . . . 233.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . 243.6.1 Effect of Non-negativity Constraints on Entity Em-beddings . . . . . . . . . . . . . . . . . . . . . . . . . 263.6.2 Sparse Relations . . . . . . . . . . . . . . . . . . . . . 273.6.3 Knowledge Graphs with no Redundant Triples . . . . 293.7 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 Incorporating n-ary Relations . . . . . . . . . . . . . . . . . . 324.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.2 Knowledge Hypergraph Completion: HSimplE and HypE . . 354.2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . 364.2.2 Proposed Methods . . . . . . . . . . . . . . . . . . . . 374.2.3 Objective Function and Training . . . . . . . . . . . . 414.2.4 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . 424.2.5 Baselines . . . . . . . . . . . . . . . . . . . . . . . . . 434.2.6 Experiments . . . . . . . . . . . . . . . . . . . . . . . 454.2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . 484.3 Knowledge Hypergraph Completion with Relational Algebra:ReAlE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . 524.3.2 ReAlE: A Basic Embedding Algorithm . . . . . . . . 544.3.3 Theoretical Analysis . . . . . . . . . . . . . . . . . . . 574.3.4 Full expressivity . . . . . . . . . . . . . . . . . . . . . 574.3.5 Representing Relational Algebra with ReAlE . . . . . 574.3.6 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . 614.3.7 Experiments . . . . . . . . . . . . . . . . . . . . . . . 644.3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 684.4 Conclusion and Limitations . . . . . . . . . . . . . . . . . . . 68viiTable of Contents5 Implicit Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 725.3 Proposed Method: SLAPS . . . . . . . . . . . . . . . . . . . 745.3.1 Generator . . . . . . . . . . . . . . . . . . . . . . . . 745.3.2 Adjacency Processor . . . . . . . . . . . . . . . . . . 765.3.3 Classifier . . . . . . . . . . . . . . . . . . . . . . . . . 775.3.4 Using only the first three components leads to super-vision starvation . . . . . . . . . . . . . . . . . . . . . 785.3.5 Self-supervision . . . . . . . . . . . . . . . . . . . . . 795.3.6 SLAPS . . . . . . . . . . . . . . . . . . . . . . . . . . 815.4 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . 825.4.1 Baselines . . . . . . . . . . . . . . . . . . . . . . . . . 825.4.2 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . 825.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 845.5.1 Comparative Results . . . . . . . . . . . . . . . . . . 855.5.2 The Effectiveness of Self-supervision . . . . . . . . . . 875.5.3 Experiments with Noisy Graphs . . . . . . . . . . . . 905.5.4 Analyses of the Learned Adjacency . . . . . . . . . . 905.5.5 Ablation Studies . . . . . . . . . . . . . . . . . . . . . 925.6 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946 Conclusion and Future Work . . . . . . . . . . . . . . . . . . 956.1 Future Work for Learning with Explicit Structures . . . . . . 956.2 Future Work for Learning with Implicit Structures . . . . . . 986.3 Combining Explicit and Implicit Graph Structures . . . . . . 99Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100AppendicesA Proofs for Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . 117B Proofs and Implementation Details for Chapter 4 . . . . . 120B.1 Proofs for HypE and HSimplE . . . . . . . . . . . . . . . . . 120B.2 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . . 123B.2.1 Full Expressivity of ReAlE . . . . . . . . . . . . . . . 123B.2.2 Full Expressivity of Some Baselines . . . . . . . . . . 126viiiTable of ContentsB.2.3 Representing Relational Algebra with ReAlE . . . . . 127B.2.4 Representing Relational Algebra with HypE . . . . . 133B.3 Implementation Details . . . . . . . . . . . . . . . . . . . . . 137C Supplementary Material for Chapter 5 . . . . . . . . . . . . 139C.1 Supervision Starvation in Erdo˝s-Re´nyi and Scale-free net-works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139C.2 Implementation Details . . . . . . . . . . . . . . . . . . . . . 141C.2.1 kNN Implementation . . . . . . . . . . . . . . . . . . 142C.3 More Experiments and Analysis . . . . . . . . . . . . . . . . 142C.3.1 Symmetrization . . . . . . . . . . . . . . . . . . . . . 142C.3.2 Fixing a prior graph manually instead of using self-supervision . . . . . . . . . . . . . . . . . . . . . . . . 144C.3.3 Why not compare the learned graph structures withthe original ones? . . . . . . . . . . . . . . . . . . . . 146Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148ixList of Tables2.1 Summary of notation with examples. . . . . . . . . . . . . . . 53.1 We conduct experiments on sport and location datasets.These datasets are subsets of NELL dataset [100] and areintroduced by Wang et al. [146]. The subsumptions in sportand location datasets are listed in this table. . . . . . . . . 253.2 Statistics of the datasets used in the experiments. In thistable, |E| represents the number of entities, |R| representsthe number of relations in the dataset, and #train, #valid,and #test denote number of triples in the train, validation,and test sets respectively. . . . . . . . . . . . . . . . . . . . . 253.3 Results of SimplE+ with different non-linearity functions inproducing non-negative embeddings on wn18 dataset with-out incorporating subsumptions. ReLU outperforms otherchoices, and therefore moving forward we use ReLU for non-negativity constraints in SimplE+. . . . . . . . . . . . . . . . 263.4 Results of SimplE+ with different non-linearity functions inproducing non-negative embeddings on fb15k dataset with-out incorporating subsumptions. ReLU outperforms otherchoices, and therefore moving forward we use ReLU for non-negativity constraints in SimplE+. . . . . . . . . . . . . . . . 263.5 Results on wn18 for SimplE and SimplE+ without incor-porating subsumptions. As the results indicate, the non-negativity constraint on entity embeddings deteriorates themodel’s performance but allows us to be able to guaranteeenforcing subsumptions (as shown in Theorem 3.5). . . . . . . 273.6 Results on fb15k for SimplE and SimplE+ without incor-porating subsumptions. As the results indicate, the non-negativity constraint on entity embeddings deteriorates themodel’s performance but allows us to be able to guaranteeenforcing subsumptions (as shown in Theorem 3.5). . . . . . . 27xList of Tables3.7 Results comparing logical inference, SimplE, and SimplE+on sport dataset. The best results are in bold. mrr andhit@k for k > 1 is not applicable for logical inference as iteither predict the correct entity or not (SimplE and SimplE+predict a ranking). The results demonstrate the effectivenessof SimplE+ in the presence of subsumptions. . . . . . . . . . 313.8 Results comparing logical inference, SimplE, and SimplE+on location dataset. The best results are in bold. mrr andhit@k for k > 1 is not applicable for logical inference as iteither predict the correct entity or not (SimplE and SimplE+predict a ranking). The results demonstrate the effectivenessof SimplE+ in the presence of subsumptions. . . . . . . . . . 314.1 Statistics of the datasets used in the experiments. In thistable, |E| represents the number of entities, |R| representsthe number of relations in the dataset, and #train, #valid,and #test denote number of triples in the train, validation,and test sets respectively. . . . . . . . . . . . . . . . . . . . . 444.2 Number of tuples with different arities in different datasets. . 444.3 Knowledge hypergraph completion results on jf17k, fb-autoand m-fb15k for baselines and the proposed method. Theprefixes ‘r’ and ‘m’ in the model names stand for reificationand multi-arity respectively. Both our methods outperformthe baselines on all datasets. Results for jf17k dataset is anaverage of three runs. . . . . . . . . . . . . . . . . . . . . . . 454.4 Knowledge graph completion results on wn18 for baselinesand HypE. Note that in knowledge graphs (binary relations),HSimplE and SimplE are equivalent, both theoretically andexperimentally. The results show that our methods outper-form the baselines. . . . . . . . . . . . . . . . . . . . . . . . 474.5 Knowledge graph completion results on fb15k for baselinesand HypE. Note that in knowledge graphs (binary relations),HSimplE and SimplE are equivalent, both theoretically andexperimentally. The results show that our methods outper-form the baselines. . . . . . . . . . . . . . . . . . . . . . . . 474.6 Breakdown performance of hit@10 across relations with dif-ferent arities on jf17k dataset along with their statistics. . . 48xiList of Tables4.7 Knowledge hypergraph completion results on jf17k, fb-autoand m-fb15k for baselines and the proposed method. Ourmethod ReAlE outperforms (or is competitive to) the base-lines on all datasets. The higher is better for all columns. Tomeasure the stability of ReAlE, we ran it on jf17k 10 timeswith the best hyperparameters and the standard deviationof mrr is 0.0004. This shows that ReAlE is not sensitive todifferent runs (different random seeds) . . . . . . . . . . . . . 654.8 Breakdown performance of mrr across composite relations(based on a sequence of primitive operations) and of varyingdepths on the rel-er dataset along with their statistics. Thehigher is better. . . . . . . . . . . . . . . . . . . . . . . . . . 664.9 Knowledge hypergraph completion results on jf17k, fb-autoand m-fb15k for baselines and the proposed method for afixed embedding dimension of 200, negative ratio of 10, andbatch size of 128. Our method ReAlE (Small) outperformsthe baselines on all datasets with these settings. . . . . . . . . 694.10 Knowledge hypergraph completion results for ReAlE on jf17kfor different σ (nonlinear function). . . . . . . . . . . . . . . 695.1 Statistics of the datasets used in the experiments. . . . . . . . 835.2 Results of SLAPS and the baselines on established node clas-sification benchmarks presenting accuracy. † indicates resultshave been taken from Franceschi et al. [47]. ‡ indicates re-sults have been taken from Stretcu et al. [134]. Bold andunderlined values indicate the best and the second-best meanperformances respectively. OOM indicates out of memory.OOT indicates out of time (we allowed 24h for each run).NA indicates not applicable. Appendix C.2 provides imple-mentation details of SLAPS and baselines. . . . . . . . . . . . 845.3 Results on classification datasets presenting accuracy. † in-dicates results have been taken from Franceschi et al. [47].Bold and underlined values indicate best and the second-bestmean performances respectively. . . . . . . . . . . . . . . . . 865.4 Classification accuracy results on the mnist dataset with lowlabel rates as proposed by Jiang et al. [68]. Bold values in-dicate best mean performances. Underlined values indicatesecond best mean performance. All the results for baselinehave been taken from [68]. . . . . . . . . . . . . . . . . . . . . 87xiiList of TablesC.1 Best set of hyperparameters for different datasets chosen onthe validation set. . . . . . . . . . . . . . . . . . . . . . . . . 143xiiiList of Figures2.1 An example of a (directed) graph with 8 nodes and 9 edges.In this example, the nodes are ordered as e1, e2, e3, e4, e5,e6, e7, and e8. The adjacency matrix associated to the graphand the node ordering is A. . . . . . . . . . . . . . . . . . . . 72.2 An example of a weighted graph with 8 nodes and 9 edges. Inthis example, the nodes are ordered as e1, e2, e3, e4, e5, e6, e7,and e8. The adjacency matrix associated to the graph and thenode ordering is A. Each edge in the graph is accompaniedby a positive number as the weight of the edge. . . . . . . . . 82.3 An example of a node attributed graph with 8 nodes and 9edges. In this example, the nodes are ordered as e1, e2, e3,e4, e5, e6, e7, and e8. The adjacency matrix associated tothe graph and the node ordering is A. Here, each node isaccompanied by a vector as features for the nodes. . . . . . . 82.4 An example of a relational graph with 8 nodes, 9 edges, and 3relations. In this example, the nodes are ordered as e1, e2, e3,e4, e5, e6, e7, and e8, the relations areR = {r1, r2, r3}, γ(r1) ={(e2, e3), (r6, e7), (e8, e6)}, γ(r2) = {(e3, e4), (r2, e6), (e5, e7)},and γ(r3) = {(e1, e2), (r5, e3), (e6, e5)}. . . . . . . . . . . . . . 92.5 An example of a hypergraph with 8 nodes and 3 hyperedges.In this example, the nodes are ordered as e1, e2, e3, e4, e5,e6, e7, and e8 and the order of the nodes in a hyperedge isdenoted as left to right. . . . . . . . . . . . . . . . . . . . . . 102.6 An example of a relational hypergraph with 8 nodes and 4hyperedges. In this example, the nodes are ordered as e1,e2, e3, e4, e5, e6, e7, and e8, the order of the nodes in eachhyperedge is denoted as left to right, and arity for r1, r2,and r3 is 3, 3, and 2 respectively. Also, γ(r1) = {(e1, e2, e3)},γ(r2) = {(e3, e5, e4), (e8, e7, e6)}, and γ(r3) = {(e6, e5)}. . . . . 10xivList of Figures3.1 hit@1 of SimplE, SimplE+, and logical inference when theyare trained on different fractions (percentages) of the train-ing data on sport dataset. The results indicate that whentraining data is scarce, logical inference outperforms (or ison-par with) SimplE, as SimplE does not see enough triplesto be able to learn meaningful embeddings. As the amountof training data increases, SimplE starts to outperform logi-cal inference as it can better generalize to unseen cases thanpure logical inference. The gap between these two methodsbecomes larger as the amount of training data increases. Forall tested fractions, SimplE+ outperforms both SimplE andlogical inference as it uses both the generalization power ofSimplE and the inference power of logical rules. . . . . . . . . 283.2 This experiment shows the loss value for SimplE and SimplE+at each training epoch on sport dataset. Models are testedwith the exact number of parameters and initialization. Theresults show that SimplE+ requires fewer epochs than SimplEto converge. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.1 (a) Relation FliesBetween with arity 3 defined on three tuples.(b) Reifying non-binary relations by creating three additionalentities e1, e2, and e3. (c) Converting non-binary relationsinto cliques using star-to-clique. In this example, the threefacts in the original graph (a) show that Air Canada has aflight from Montreal to Los Angeles and from Vancouver toNew York. Figures (b) and (c) show two methods of convert-ing this ternary relation into binary ones. . . . . . . . . . . . 344.2 Visualization of HSimplE and HypE architectures. (a) φθfor HSimplE transforms entity embeddings by shifting thembased on their position and combining them with the relationembedding. (b) f (e , i) for HypE takes an entity embeddingand the position the entity appears in the given tuple, andreturns a vector. (c) φθ takes as input a tuple and outputsthe score of HypE for the tuple. . . . . . . . . . . . . . . . . . 38xvList of Figures4.3 These experiments show that HypE outperforms HSimplEwhen trained with fewer parameters, and when tested onsamples that contain at least one entity in a position neverencountered during training on jf17k dataset. (a) mrr ofHypE and HSimplE for different embedding dimensions. (b)Results of m-CP, HSimplE, and HypE on the missing posi-tions test set (containing 1,806 test samples). . . . . . . . . . 464.4 An example of a knowledge hypergraph. Train set containssold(drew , alex , book), buyer(alex , book), sold(mike, sam, tv),and bought(sam,mike, tv). Relation bought can be obtainedby applying a renaming operation to relation sold . Similarly,relation buyer is a projection of relation sold . Learning theserelational algebra operations can help the model generalizeto the tuples in the test set. The test responses, from top tobottom, are drew , tv , and mike. . . . . . . . . . . . . . . . . 514.5 A schematic of the entity and relation embeddings in ReAlE:the embedding dimension d is divided into nw windows of sizew . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.6 MRR of ReAlE for different number of windows nw on jf17kwith fixed values for negative ratio, batch size, and embeddingdimension of 10, 128, and 200 respectively. The total numberof parameters for each value of nw is fixed. . . . . . . . . . . . 675.1 Overview of SLAPS. At the top, a generator receives the nodefeatures and produces a non-symmetric, non-normalized ad-jacency having (possibly) both positive and negative values(Section 5.3.1). The adjacency processor makes the valuespositive, symmetrizes, and normalizes the adjacency (Sec-tion 5.3.2). The resulting adjacency and the node featuresgo into GNNC which predicts the node classes (Section 5.3.3).At the bottom, some noise is added to the node features. Theresulting noisy features and the generated adjacency go intoGNNDAE which then denoises the features (Section 5.3.5). . . 755.2 Using a two-layer GCN, the predictions made for the labelednodes are not affected by the dashed (starved) edge. . . . . . 78xviList of Figures5.3 Comparing SLAPS, SLAPS2s and kNN-GCN on cora withdifferent generators. Although SLAPS2s does not use thenode labels in learning an adjacency matrix, it outperformskNN-GCN. SLAPS outperforming SLAPS2s indicates thatlearning the adjacency using both self-supervision and thetask-specific node labels results in higher predictive accuracy. 885.4 The performance of SLAPS with MLP graph generator as afunction of λ. SLAPS with λ = 0 corresponds to removingself-supervision. The results indicate that with removing self-supervision, the model performance is somewhat poor. Assoon as λ becomes positive, both models see a large boostin performance showing that self-supervision is crucial to thehigh performance of SLAPS. . . . . . . . . . . . . . . . . . . 895.5 Performance comparison when noisy graphs are provided asinput (ρ indicates the percentage of perturbations). Theresults indicate that self-supervision consistently provides aboost in performance, especially for higher values of ρ . . . . 915.6 The odds of two nodes in the test set sharing the same labelas a function of the edge weights learned by SLAPS. For bothcora and citeseer, nodes that are connected with higheredge weights are more likely to share the same label comparedto nodes with lower or zero edge weights. This shows that thelearned edge weights are highly predictive of the same classness. 925.7 The performance of SLAPS on cora as a function of k inkNN. The results show that the value of k plays a major rolein model performance. . . . . . . . . . . . . . . . . . . . . . . 93B.1 An example of an embedding where |τ | = 5, α = 4 and f3 isthe third fact in τ . . . . . . . . . . . . . . . . . . . . . . . . 120B.2 An example of an embedding where |τ | = 5, α = 4 and f3 isthe third fact in τ . . . . . . . . . . . . . . . . . . . . . . . . 121B.3 An example of a ReAlE embedding assignments for true tu-ples τ0 = r1(xa , xb , xc), τ1 = r2(xa , xc), τ2 = r1(xc , xb , xd )and τ3 = r1(xd , xc , xa). Here, the number of true tuplesλ = nw = 4, maximum arity ω = 3. Cells that are set tozero are left empty for better readability. As an example,given that xb is in position 1 of τ2, we set cell 2×ω+ 1 = 7 ofxb to 1. We further set the value of r1 at positions [1][7] to K . 124xviiList of FiguresB.4 Proof of Theorem B.2: If at least one value of each vectorf (xi , 1) is different than zero (Ki ¿ 0) and the value of atmost one position i can be non-zero (the d columns in thefigure), then by the pigeon-hole principle, we will run out ofindices as we have more entities in the knowledge hypergraph.In the above image, the entity xd+1. . . . . . . . . . . . . . . 137C.1 The performance of SLAPS on cora and citeseer with dif-ferent adjacency symmetrizations. . . . . . . . . . . . . . . . 144C.2 The performance of SLAPS and regularization toward a man-ually defined prior structure on cora and citeseer whenusing the MLP generator. . . . . . . . . . . . . . . . . . . . . 145C.3 Two example graph structures. Node colors indicate the classlabels. Solid lines indicate homophilous edges and dashedlines indicate non-homophilous edges. The two graphs exhibitthe same degree of homophily yet there is no overlap betweentheir edges. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147xviiiList of Software Packages• SimplE+– Description: An embedding model for link prediction in knowl-edge graphs with the ability to enforce taxonomies.– Used in: Chapter 3.– Paper: Bahare Fatemi, Siamak Ravanbakhsh, and David Poole.Improved Knowledge Graph Embedding Using Background Taxo-nomic Information, Proceedings of the AAAI Conference on Ar-tificial Intelligence, 2019.– URL:∗ https://github.com/baharefatemi/SimplE∗ https://github.com/baharefatemi/SimplE-plus– Languages and Tools: Python and PyTorch.• HypE– Description: An embedding model for link prediction in knowl-edge hypergraphs.– Used in: Chapter 4.– Paper: Bahare Fatemi, Perouz Taslakian, David Vazquez, andDavid Poole. Knowledge Hypergraphs: Prediction Beyond BinaryRelations, Proceedings of the International Joint Conferences onArtificial Intelligence, 2020.– URL: https://github.com/baharefatemi/HypE– Languages and Tools: Python and PyTorch.• ReAlE– Description: An embedding model for link prediction in knowl-edge hypergraphs.xixList of Software Packages– Used in: Chapter 4.– Paper: Bahare Fatemi, Perouz Taslakian, David Vazquez, andDavid Poole. Knowledge Hypergraph Embedding Meets RelationalAlgebra, Under review at Journal of Machine Learning Research,2022.– URL: https://github.com/baharefatemi/ReAlE– Languages and Tools: Python and PyTorch.• SLAPS– Description: A framework for simultaneous Learning of adja-cency and graph neural network parameters with self-supervisionfor semi-supervised node classification.– Used in: Chapter 5.– Paper: Bahare Fatemi, Layla El Asri, and Seyed MehranKazemi. SLAPS: Self-Supervision Improves Structure Learningfor Graph Neural Networks, Advances in Neural Information Pro-cessing Systems (NeurIPS), 2021.– URL: https://github.com/BorealisAI/SLAPS-GNN– Languages and Tools: Python and PyTorch.xxAcknowledgementsFirst and foremost, I would like to express my sincerest gratitude to myPhD supervisor and mentor, David Poole, for giving me this opportunityto pursue a PhD under his supervision. I am tremendously grateful for hiscontinuous support, inspiring discussions, and constant feedback, and forgiving me the freedom to pursue a variety of research directions during myPhD. His guidance and support both in academia and life have been trulyinvaluable.My deepest acknowledgment goes to all my collaborators and internshiphosts from Google Research, Facebook AI Research, Borealis AI, McGill,and Element AI: Perouz Taslakian, David Vazquez, Adriana Romero, MichalDrozdzal, Mehran Kazemi, Deepak Ramachandran, Siamak Ravanbakhsh,Simon Prince, Layla El Asri, Quentin Duval, and Rohit Girdhar. I am grate-ful for the funding they provided for the projects and all the support andencouragement they gave me. Without their guidance, constant feedback,and valuable ideas, this thesis would not have been achievable.My deep and sincere gratitude to my family for their continuous andunparalleled love, help, and support. I am grateful to my brother and hiswife, Hossein and Fatemeh, for always being there for me as a friend. I amforever indebted to my parents, Mahmoud and Esmat, for giving me theopportunities and experiences that have made me who I am. They selflesslyencouraged me to explore new directions in life and seek my own destiny.Finally, and above all, I cannot begin to express my unfailing gratitudeand love to my husband, Mehran, who has supported me throughout thisprocess and has constantly encouraged me when the tasks seemed arduousand insurmountable.xxiDedicationWomen, Life, FreedomDedicated to the women of Iran.xxiiChapter 1Introduction1.1 Machine Learning and StructureOn a day-to-day basis, we make predictions about the world. We predictthe upcoming weather by checking the weather forecast to plan and dressfor the day accordingly. In the financial sector and investment within thestock market and businesses, people make predictions about the share valuesof different companies and decide on buying and selling shares. Physicianspredict the diseases, nutrition deficiencies, and drug side effects for eachpatient and decide on what actions to take based on these predictions.Artificial intelligence [113, 123] studies methods for understanding theworld, making predictions for unobserved events, and using predictions fordecision making. A formal description of a world is often called a model ofthe world. An artificial intelligence system builds a model of the world tobe able to make predictions about it and use prediction results in decisionmaking. Machine learning is a sub-field of artificial intelligence. Its goal isto construct models of the world based on past experiences.The world around us is composed of different objects each having var-ious relations with the other objects. The objects and relations form a(hyper)graph with objects as nodes and relations between objects as (hy-per)edges in the graph. For instance, a social network is in the form ofa graph with users as nodes and interactions between users as edges. Inchemistry, molecules form graphs with atoms as nodes and their bonds witheach other as edges. The dependency parse tree of a text and the abstractsyntax tree of a program form a graph as well. With modern technologyand the rise of the internet, graphs are everywhere: we can see graphs morefrequently as the world wide web, street maps, and knowledge bases used insearch engines.The ubiquity of such a graph-structured description of the world callsfor the development of effective methods that make use of and learn tounderstand information represented in this structural form. The machinelearning community has long noticed the importance of structure in data.The primary form of data in the subfield of graph representation learning [57]11.2. Learning with Explicit Structureis in the form of nodes and edges among them.A common approach for applying machine learning to discrete data, suchas text and graphs, is through learning embeddings. Word, sentence, andparagraph embeddings [13, 73, 98, 111], which vectorize words, sentences,and paragraphs using context information, are widely used in a variety ofnatural language processing tasks from syntactic parsing to sentiment analy-sis. In graph representation learning, the goal is to combine given propertiesof nodes and edges as well as the structure into representations. The em-beddings are later used for different tasks e.g., for node classification [e.g.,41, 58, 83], link prediction [e.g., 15, 39, 76, 139], and graph classification [e.g.,37, 167].This thesis is structured in two parts: Chapters 3 and 4 introducesembedding-based models for a variety of learning tasks with explicitly graph-structured data, i.e., datasets that are given to us in the form of entitiesand their relations. Chapter 5 explores the topic of learning with implicitstructure in the form of structural inductive biases, applied to tasks such asnode classification. In this part, we are not given an explicitly structureddataset, but we develop models that infer or make use of hidden structures inthe data to achieve improved generalization compared to using unstructureddeep models.1.2 Learning with Explicit StructureThe underlying structure representing the relations between the nodes issometimes given in the task. Such entity-relationships are often representedin the form of triples of relationship(head , tail) with head and tail repre-senting entities and a relationship between the two entities. The triple rep-resentation can be expressed in the form of a graph, with nodes as entitiesand directed edges from the head node to the tail node labeled with therelationship between them.One instance of an explicit structure is knowledge graphs. Knowledgegraphs contain knowledge about the world and provide a structured repre-sentation of the knowledge in the form of a graph. Such graph structureshave applications in several tasks such as search [130], automatic questionanswering [45, 160], relation extraction [115], and recommender systems [18].A large number of knowledge graphs have been created and are publiclyavailable, such as yago [135], dbpedia [6], nell [19], freebase [14], andGoogle Knowledge Vault [34]. Since accessing and storing all the knowledge(true triples) in the world is difficult, knowledge graphs are incomplete; the21.2. Learning with Explicit Structuregoal of link prediction in knowledge graphs (or knowledge graph completion)is to predict unknown true triples or relationships between entities based onexisting ones.In graph representation learning, embedding-based methods [104, 106,147] use embeddings for entities and relationships to generalize from exist-ing data. The embeddings are learned such that their interaction throughmathematical operations best predicts the (probability of the) existence ofthe observed triples. These approaches learn embeddings for entities andrelations. To find out if r(h, t) is a fact (i.e., is true), such models define afunction that embeds relationship r and entities h and t , and produces theprobability that r(h, t) is true. Embedding-based methods have been usedin several reasoning tasks in knowledge graphs.The contributions of this thesis for this part are guided by the followingresearch questions:Research Question 1 Can we develop and implement efficient embedding-based models that can enforce taxonomic information of ontologies in thelearned embeddings space?Embedding-based models rely on a large number of annotated triples tolearn useful representations of entities and relationships. However, in manydomains, often there exists other information in ontologies that specify themeaning of the symbols used in a knowledge base. Ontology can includetaxonomic (subclass and subproperty) information. The provided taxonomicinformation can be exploited as extra information to help the embedding-based model learn a useful representation for entities and relationships. Ourmain contribution to addressing this question is a novel embedding-basedmodel that we call SimplE+ and is introduced in Chapter 3. SimplE+ canenforce taxonomic information into the learned embeddings and achievesadvantages over earlier state-of-the-art methods both in terms of efficiencyand predictive accuracy for knowledge graph completion.Research Question 2 Can embedding-based models for knowledge graphcompletion incorporate n-ary relations?Most of the existing embedding-based methods can only handle relationswith at most two arguments but in the real world, there exist relations withmore than two arguments. The number of arguments a relation takes iscalled arity of the relation. For instance, the relation sells(S ,B , I ,P ,T ),which is true when the entity S , the seller, sells item I to buyer B for price31.3. Learning with Implicit StructureP at time T , has arity five. There are approaches to converting higher-arity relations to binary ones, however, one contribution of this thesis isshowing in Section 4.1 that current embedding-based methods do not workwell in the presence of such conversion approaches. Another contribution ofthis thesis is introducing datasets, baselines, and evaluation metrics for thetask of knowledge completion with n-ary relations. We show that to handlehigher-arity relations, we need to devise new methods that can handle suchentities. In Sections 4.2 and 4.3 we introduce embedding-based models thatdemonstrate significant improvement over the proposed baselines.1.3 Learning with Implicit StructureHaving introduced novel architectures for explicitly graph-structured datain Chapters 3 and 4 of this thesis, Chapter 5 investigates how models withstructural and compositional inductive biases — in particular graph neuralnetworks — can be developed and applied to problems with the implicit orhidden structure.Research Question 3 Can we extend the applicability of models that workwith structural inductive biases to problems where a graph structure is notreadily available?Graph neural networks (GNNs) are a class of neural network modelssuitable for processing graph-structured data. GNNs learn embeddings fornodes in the graph based on feature information available for the nodes aswell as the structure of the graph. GNNs work well when the graph struc-ture is provided. However, this structure may not always be available inreal-world applications. One solution to this problem is to infer a task-specific latent structure and then apply a GNN to the inferred graph. Weidentify a supervision starvation problem in such approaches in which theedges between pairs of nodes that are far from labeled nodes receive insuffi-cient supervision; this results in learning poor structures away from labelednodes and hence poor generalization. So the task-specific supervision maybe insufficient for learning both the structure and the GNN parameters. In(Chapter 5) of this thesis, we propose the simultaneous learning of a graphstructure and graph neural network parameters with self-supervision. Acomprehensive experimental study demonstrates that the proposed modelscales to large graphs with hundreds of thousands of nodes and outperformsseveral models that have been proposed to learn a task-specific graph struc-ture on established benchmarks.4Chapter 2Background and NotationIn this chapter, we provide an introduction to the topics and notation thatare used throughout this thesis. Additional background will be introducedwhere necessary in later chapters.2.1 NotationWe use lowercase letters to denote scalars, bold lowercase letters to denotevectors, bold uppercase letters to denote matrices, and calligraphic lettersto denote sets.Let R denote the space of real numbers and Rn denote the n-dimensionalreal space. The space of matrices of real numbers with n rows and m columnsis denoted by Rn×m . Otherwise, we use symbol × for the multiplication oftwo scalars. Following Python notation, for a vector v , we represent its i thelement as v [i ]. For a matrix M , we represent the i th row as M [i ] and theelement at the i th row and j th column as M [i ][j ]. I represents an identitymatrix.We use Re(x ) and Im(x ) to denote the real and imaginary parts of acomplex vector x . The element-wise conjugate of the complex vector a + ibis defined as a + ib = a − ib (where i = √−1).The notation is summarized with examples in Table 2.1.Table 2.1: Summary of notation with examples.Examples Descriptionsx , y , and z Lowercase letters denote scalar.x , y , and z Bold lowercase letters denote vectors.X , Y , and Z Bold uppercase letters denote matrices.X , Y, Z Calligraphic letters denote sets.v [i ] The i th element of a vector v .M [i ] The vector at the i th row of matrix M .M [i ][j ] The element at the i th row and j th column of matrix M .52.2. Learning on GraphsThe variadic function concat takes input a sequence of vectors v 1, . . . , v kand outputs the concatenation of its input vectors. We define the variadicfunction to be the sum of the element-wise product of its input vectors,namely (v 1, v 2, . . . , v k ) =∑`i=1 v 1[i ]×v 2[i ]×· · ·×v k [i ] where each vectorv i has the same length.The 1D convolution operator ∗ takes as input a vector v ∈ Rn , a vectorω ∈ Rm as the convolution weight filter, and a stride s (n should be divisibleby s) and outputs a vector of size n/s. The operation ∗ is the standard 1Dconvolution as defined in torch.nn.Conv1D function in PyTorch [109]. Byconvention, if index j is outside the range of v , v [j ] = 0. The x -th index ofthe output of the 1D convolution (v ∗ ω) is defined as follows, where strideis implicit in the convolution function.(v ∗ ω)[x ] =m−1∑i=0v [x × s + i ]× ω[i ]A permutation function on {1, . . . ,n} is a bijection pi : {1, . . . ,n} →{1, . . . ,n}. For example, if pi has 1 7→ 2, 2 7→ 1, and 3 7→ 3, then,(xpi(1), xpi(2), xpi(3)) = (x2, x1, x3).2.2 Learning on Graphs2.2.1 Types of GraphsA directed graph with n nodes is denoted as G = {V,A}. V = {e1, . . . , en}is a set of nodes and A is a set of ordered pairs of edges. One can impose anordering on V and represent A as a matrix A ∈ {0, 1}n×n and G as {V,A}.We refer to A as adjacency matrix. When A[i ][j ] = 1, there is a directededge in the graph from node ei to node ej . When A[i ][j ] = 0, there is noedge in the graph from node ei to node ej . If a G has m edges, A has mnon-zero values. Figure 2.1 shows an example of a graph with 8 nodes and9 edges and the adjacency matrix associated to the graph. An undirectedgraph has a symmetric adjacency matrix, i.e., A[i ][j ] = A[j ][i ]. In thisthesis, we mainly work with directed graphs. Hereafter, we use the termgraph to refer to a directed graph.A weighted graph is a graph with a function from edges into positivenumbers. When V is ordered, the edges and their corresponding weights canbe represented as an adjacency matrix A ∈ Rn×n with non-negative values.The weight of the edge from node ei to node ej is denoted by A[i ][j ]. WhenA[i ][j ] = 0, there is no edge in the graph from node ei to node ej . The62.2. Learning on Graphse1e2e6e5e3e4e8e70 1 0 0 0 0 0 00 0 1 0 0 1 0 00 0 0 1 0 0 0 00 0 0 0 0 0 0 00 0 1 0 0 0 1 00 0 0 0 1 0 1 00 0 0 0 0 0 0 00 0 0 0 0 1 0 0e1e2e3e4e5e6e7e8e1 e2 e3 e4 e5 e6 e7 e8A =Figure 2.1: An example of a (directed) graph with 8 nodes and 9 edges. Inthis example, the nodes are ordered as e1, e2, e3, e4, e5, e6, e7, and e8. Theadjacency matrix associated to the graph and the node ordering is A.number of positive values in A is m. Figure 2.2 shows an example of aweighted graph with 8 nodes and 9 edges.A node attributed graph is a graph with a function from nodes V into Rf .When V is ordered, the attributes can be represented as matrix X ∈ Rn×fwhose i -th row correspond to a vector of f descriptive attributes as featuresfor node ei and G can be represented as {V,A,X }. We refer to X as nodefeatures. In this thesis, an attributed graph refers to a node attributedgraph. An example of an attributed graph is cora [127]. cora is a citationnetwork with nodes as publications and edges as citations. Each node (eachpublication) in the dataset is described by a binary-valued word vector.The i -th value in the vector is 1 if the i -th word in the dictionary appearsanywhere in the document and is 0 otherwise. Figure 2.3 shows an exampleof a node attributed graph.A relational graph is G = {V,R, γ} where V is a set of nodes, R is aset of relations, γ is a function from R into sets of ordered pairs of nodes.There is an edge from ei to ej with relation r , written as r(ei , ej ), when(ei , ej ) ∈ γ(r). An example of a relational graph is the wordnet datasetwith nodes as words and relations for instance hyperonymy and hyponymsand edges indicating what words are hypernym or hyponym of each other.Figure 2.4 shows an example of a relational graph with R = {r1, r2, r3}. Theγ function for each relation is defined as γ(r1) = {(e2, e3), (r6, e7), (e8, e6)},γ(r2) = {(e3, e4), (r2, e6), (e5, e7)}, and γ(r3) = {(e1, e2), (r5, e3), (e6, e5)}.A hypergraph is a G = {V,A} where V is a set of nodes and A is a subsetof the power sets of V. Figure 2.5 shows an example of a hypergraph with72.2. Learning on Graphse1e2e6e5e3e4e8e70 0.7 0 0 0 0 0 00 0 0.5 0 0 1.1 0 00 0 0 0.3 0 0 0 00 0 0 0 0 0 0 00 0 1.5 0 0 0 1.0 00 0 0 0 0.1 0 0.8 00 0 0 0 0 0 0 00 0 0 0 0 0.3 0 0e1e2e3e4e5e6e7e8e1 e2 e3 e4 e5 e6 e7 e8A =0.7 0.51.50.30.11.00.80.31.1Figure 2.2: An example of a weighted graph with 8 nodes and 9 edges. Inthis example, the nodes are ordered as e1, e2, e3, e4, e5, e6, e7, and e8. Theadjacency matrix associated to the graph and the node ordering is A. Eachedge in the graph is accompanied by a positive number as the weight of theedge.e1e2e6e5e3e4e8e70 1 0 0 0 0 0 00 0 1 0 0 1 0 00 0 0 1 0 0 0 00 0 0 0 0 0 0 00 0 1 0 0 0 1 00 0 0 0 1 0 1 00 0 0 0 0 0 0 00 0 0 0 0 1 0 0e1e2e3e4e5e6e7e8e1 e2 e3 e4 e5 e6 e7 e8A =0.3 … 10.2 … -0.30 … -0.10.1 … 00 … 00.6 … 1.40.6 … 2.50.7 … 3.4Figure 2.3: An example of a node attributed graph with 8 nodes and 9 edges.In this example, the nodes are ordered as e1, e2, e3, e4, e5, e6, e7, and e8.The adjacency matrix associated to the graph and the node ordering is A.Here, each node is accompanied by a vector as features for the nodes.82.2. Learning on Graphse1e2e6e5e3e4e8e7r3 r1r3r2r3r2r1r1r2Figure 2.4: An example of a relational graph with 8 nodes, 9 edges, and 3relations. In this example, the nodes are ordered as e1, e2, e3, e4, e5, e6, e7,and e8, the relations are R = {r1, r2, r3}, γ(r1) = {(e2, e3), (r6, e7), (e8, e6)},γ(r2) = {(e3, e4), (r2, e6), (e5, e7)}, and γ(r3) = {(e1, e2), (r5, e3), (e6, e5)}.8 nodes and 3 hyperedges.A relational hypergraph is a G = {V,R, arity , γ} where V is a set ofnodes, R is a set of relations, arity is a function from R to natural numbers,γ is a function from R into sets of tuples of nodes, such that the tuples inγ(r) are all of length arity(r). We write (e1, . . . , ek ) ∈ γ(r) as r(e1, . . . .ek ).We call r(e1, . . . .ek ) a tuple. A tuple with k = 2 is called a triple. The headof a triple r(e1, e2) is the first argument of the relation, e1, and the tail refersto the second argument of the relation, e2. Figure 2.6 shows an example ofa relational hypergraph with 8 nodes and 4 hyperedges. In this example,there are 3 relations r1, r2, and r3 with arities 3, 3 and 2 respectively. Thereis one tuple in γ(r1) as (e1, e2, e3). The tuples in γ(r2) are (e3, e5, e4) and(e8, e7, e6) and the only tuple (triple) in γ(r3) is (e6, e5).There are also combinations of the different types of graphs like an at-tributed relational graph or a weighted relational hypergraph.2.2.2 Tasks on GraphsVarious tasks can be defined on different types of graphs. Node classification,link prediction, graph classification, and subgraph classification are examplesof tasks on graphs. In this thesis, we focus on node classification and linkprediction.92.2. Learning on Graphse1e2e6e5e3e4e8e7Figure 2.5: An example of a hypergraph with 8 nodes and 3 hyperedges. Inthis example, the nodes are ordered as e1, e2, e3, e4, e5, e6, e7, and e8 andthe order of the nodes in a hyperedge is denoted as left to right.e1e2e6e5e3e4e8e7r1 r2r2r3Figure 2.6: An example of a relational hypergraph with 8 nodes and 4hyperedges. In this example, the nodes are ordered as e1, e2, e3, e4, e5, e6,e7, and e8, the order of the nodes in each hyperedge is denoted as left toright, and arity for r1, r2, and r3 is 3, 3, and 2 respectively. Also, γ(r1) ={(e1, e2, e3)}, γ(r2) = {(e3, e5, e4), (e8, e7, e6)}, and γ(r3) = {(e6, e5)}.102.3. Knowledge Graphs and HypergraphsNode classification. In a node classification task, the graph is accom-panied by a set of labels (labels are sometimes called classes) and a partialfunction from nodes to labels. C corresponds to the labels and |C| corre-sponds to the number of labels. The goal, here, is to predict the labels forthe unlabeled nodes. Semi-supervised learning is an approach to machinelearning that combines a small number of labeled data with a large amountof unlabeled data during training. Semi-supervised node classification ingraphs is defined as when a small number of nodes in the graph are labeled.Link prediction. In the link prediction task, the goal is to use existingedges among the nodes and, if applicable the relations to predict new edgesin the graph.2.3 Knowledge Graphs and Hypergraphs2.3.1 DefinitionA world consists of a finite set of entities E , a finite set of relations R. Thearity for each relation is fixed. The function arity , given a relation r , outputsthe number of arguments that the relation takes. The arity for relation ris also denoted as |r |. The function arity is the same as in a relationalhypergraph.Let τ be a set of tuples – the ground truth – specifying all of the tuplesthat are true. If a tuple is not in τ , it is false. If τ represents the set of truetuples in the real world, then the following tuple is in τ .FliesBetween(AirCanada,Vancouver ,NewYork)An example of a triple in τ is the following.CapitalCityOfCountry(Paris,France)An example of a tuple that is not in τ isFliesBetween(AirCanada,SanFransisco,NewYork)and an example of a triple that is not in τ is as follows.CapitalCityOfCountry(Paris,Germany)We do not observe the ground truth τ ; we only observe a subset, τ ′. Aknowledge hypergraph is a relational hypergraph G = {V,R, arity , γ} with112.3. Knowledge Graphs and HypergraphsV = E that stores τ ′. For a knowledge hypergraph, τ ′ is the union of alltuples r(ei , . . . , ej ) such that r ∈ R and (ei , . . . , ej ) ∈ γ(r). A knowledgegraph is a relational graph and is a special case of a knowledge hypergraphwhere all relations have arity 2: ∀r ∈ R : arity(r) = 2. Link prediction inknowledge hypergraphs or knowledge (hyper)graph completion is the prob-lem of predicting the missing tuples in τ ′, that is, finding the tuples τ \ τ ′.As benchmarks for knowledge hypergraphs contain only positive tuplesand for contrastive learning of knowledge hypergraphs, we also need nega-tive tuples, we follow the literature [e.g., 15, 76, 139] and generate a set ofnegative tuples for each positive tuple. The function Tneg , given a positivetuple x ∈ τ ′, generates a set of negative tuples corresponding to x (Thedetails of Tneg are discussed later).An embedding is a function that given an entity or a relation it providesone or more vectors, matrices, or higher-order tensors of numbers over afield (typically the real numbers). We use bold for embeddings, so that, xis the embedding of entity x in a vector and X is the embedding of entityx in a matrix. r is the embedding of relation r in a vector, and R is theembedding of relation r in a matrix. An embedding-based model defineswhether to represent entities or relations into vectors or matrices.For the task of knowledge hypergraph completion, an embedding-basedmodel with parameters θ defines a scoring function φθ that takes a tuple asinput and generates a prediction, e.g., a score (or a probability) of the tuplebeing true. A model is fully expressive if given any set τ , there exists anassignment of values to θ that separates the true tuples from the false onesi.e., there exists a β such that x ∈ τ iff φθ(x ) > β.2.3.2 Knowledge Graph Completion MethodsTensor factorization approaches have shown promising results for the taskof knowledge graph completion [15, 105, 106, 140]. Such approaches learnembeddings for entities and relations. Their scoring function φθ for a tripler(h, t) takes the embedding of entities h and t and relation r and outputs aprediction. Here, we explain some important tensor factorization approachesthat are of central importance to the topics covered in this thesis. All thefollowing scoring functions contain a non-linearity σ - e.g., σ : R → [0, 1]can be the sigmoid or logistic function.Canonical Polyadic (CP). CP decomposition [59] is one generalizationof the matrix singular value decomposition [8] to tensors in multi-linearalgebra. CP can be used for link prediction in knowledge graphs. CP embeds122.3. Knowledge Graphs and Hypergraphseach entity e as two vectors e+ and e−, and each relation r as a single vectorr ; it defines its score function as follows:φθ(r(ei , ej )) = σ( (r , e+i , e−j ))The two embeddings e+ and e− for an entity e are learned independently(and are unrelated to) each other. This independence of the two learnedentity embeddings causes CP to perform poorly for knowledge graph com-pletion [139].DistMult. DistMult [158] is one of the simplest knowledge graph em-bedding approaches. For each entity e and relations r , it learns only oneembedding e and r . It defines its scoring function asφθ(r(ei , ej )) = σ( (r , e i , e j )). (2.1)Since Equation 2.1 is commutative, it cannot distinguish between the sameentity appearing as in the first or the second argument of a triple. Therefore,it can only model symmetric relations.ComplEx. ComplEx [140] extends DistMult by considering complex val-ues instead of real values for embedding vectors of entities and relations. Itdefines the scoring function φθ, such that the embedding of each entity andeach relation is a vector of complex numbers.ComplEx defines the probability of any triple r(ei , ej ) asφθ(r(ei , ej )) = σ(Re( (r , e i , e j ))).Note that, if the tail did not use the conjugate, it would be equivalentto DistMult [157]. Trouillon et al. [141] prove that ComplEx is fully expres-sive. In particular, they prove that any assignment of ground truth can bemodeled by ComplEx embeddings of length |E| × |R|.SimplE. SimplE [76] introduces an enhancement of CP to allow the twoembeddings of each entity to be learned dependently. SimplE considers twoembeddings for each relation: one for the relation r ∈ R itself and one forits inverse. We use r+ to denote the “forward” embedding of r and r− todenote the embedding of its inverse. The embedding r = concat(r+, r−) fora relation is a concatenation of these two parts. Similarly, the embeddingfor each entity e ∈ E has two parts: its embedding as a head e+ and as atail e− – that is e = concat(e+, e−). Using this notation, SimplE calculates132.4. Graph Neural Networksthe probability of a triple r(h, t) being true in both forward and backwarddirections usingφθ(r(ei , ej )) = σ(12( (r+, e+i , e−j ) + (r−, e+j , e−i )))Kazemi and Poole [76] prove SimplE is fully expressive and provide abound on the size of the embedding vectors: For any truth assignmentτ ′ ⊆ R×E ×E , there exists a SimplE model with embedding vectors of sizemin(|E| × |R|, |τ ′|+ 1) that represent the assignment.2.4 Graph Neural Networks2.4.1 Motivation and IntuitionGraph neural networks (GNNs) are a class of neural network models suitablefor processing graph-structured data. The key idea in GNNs is to learnembeddings for nodes in the graph based on feature information availablefor the nodes as well as the structure of the graph. The main differencebetween GNNs and the models studied in Section 2.3.2 is that GNNs learnembeddings for nodes based on the graph structure – the neighbors and theneighbors of the neighbors etc. – and node features but the previous modelsdirectly learn node embeddings.One feature of GNNs is the neural message passing. The message passingin GNNs is defined such that at each layer, each node sends messages to itsneighboring nodes. After the messages are sent, each node receives themessages from its neighboring nodes and aggregates them to update itsembedding.The variants of GNNs differ in how they define a function to combine thegraph structure and node features to send messages and how to aggregatethe messages on one node to get updated embeddings. Next, we describegraph convolutional networks [83], a specific type of GNNs which has beenused in this thesis.2.4.2 Graph Convolutional NetworksWe first summarize a graph convolutional networks (GCNs) [83] by statingits input, intermediate outputs, and final output. We then explain thecomponents of a GCN.Input. The input to a GCN is a weighted attributed graph G = {V,A,X }.142.4. Graph Neural NetworksIntermediate outputs. Each layer in a GCN computes extra attributes,called embeddings, for each node. Let H (l) ∈ Rn×dl denote the node em-bedding for layer l with n as the number of nodes and dl as the number ofattributes per node in layer l . Here, H (l) is computed using the parametersof the layer W (l), and the previous layer node embeddings H (l−1). Theinput node embeddings H (0) is X , the provided node attributes.Final output. The final output of a GCN is the node embeddings for thelast layer, H (L).We now explain the components of a GCN.Self-loops. Each node receives messages from its neighboring nodes. Theneighboring information is stored in the adjacency matrix A. GCN connectseach node to itself to enable a node to send messages to itself enabling theaccumulation of information. Summing the adjacency matrix A with anidentity matrix I is equal to connecting each node to itself. The adjacencymatrix A plus connecting each node to itself is denoted by (A + I ).Normalization. GCN normalizes the adjacency matrix A in such a waythat the messages sent across the edges incorporate the degree of the nodesin the messages.Let D be a diagonal degree matrix for (A + I ) defined asD [i ][i ] = 1 +∑jA[i ][j ]with non-diagonal values as 0. For directed graphs where the adjacency isnot necessarily symmetric, the following corresponds to a row normalizedadjacency matrix with self-loops. The edge weights in each row of the ad-jacency matrix are divided by the degree of the node corresponding to therow. The value of (A + I )[i ][j ] is normalized in Aˆ using the degree of thenode ei asAˆ[i ][j ] =(A + I )[i ][j ]D [i ][i ].Row-normalization in matrix notation is defined asAˆ = D−1(A + I ).For undirected graphs where the adjacency is symmetric, the followingcorresponds to a row-and-column normalized adjacency matrix with self-loops. Using the row-and-column normalization, (A + I )[i ][j ] is normalized152.4. Graph Neural NetworksasAˆ[i ][j ] =(A + I )[i ][j ]√D [i ][i ]×D [j ][j ] .The matrix notation of the row-and-column normalization is defined asAˆ = D−12 (A + I )D−12 . (2.2)GCN layer. Each layer of a GCN aggregates the incoming messages toall nodes and computes node embeddings based on the received messages.Each GCN layer has learnable weight parameters. The weight parametersfor layer l in a GNN is denoted by W (l) ∈ Rdl−1×dl . Layer l computes nodeembeddings H (l) ∈ Rn×dl using the previous layer node embeddings H (l−1)and its weight parameters W (l). The input node embeddings H (0) is X ,the provided node attributes. The GCN model defines the message passingfunction asH (l)[i ] = σ ∑j∈N (i)∪{i}(Aˆ[i ][j ] H (l−1)[j ])W (l)where σ is an activation function such as ReLU [103], H (l)[i ] is the embed-ding of the node ei at layer l , N (i) is the set of indices of neighboring nodesfor node ei according to A, and H(l−1)[j ] is the embedding of the node ei atlayer l−1. j ∈ N (i)∪{i} corresponds to adding self-loops to the adjacency.The message passing function of GCN in matrix notation isH (l) = σ(AˆH (l−1)W (l)). (2.3)A GCN with L layers has parameters W (1), . . . ,W (L) with each W (l)as the weight matrix for layer l . These L layers are stacked on top of eachother to output H (L) as the final node embeddings to be used for tasks onnodes.Node classification using a GCN. For node classification using GCNs,we set dL (the second dimension in the weight parameter of the last layer inGCN) to the number of labels |C| and apply a softmax function to H (L) sothat its elements in each row lie in the range of [0, 1] and sum to 1 to reflectprobabilities.softmax(H (L)[i ][j ]) =H (L)[i ][j ]∑c∈C H(L)[i ][c](2.4)162.5. Ranking-based Evaluation MetricsThe value softmax(H (L)[i ][j ]) denotes the output probability of the node ibeing classified as label j .2.5 Ranking-based Evaluation MetricsGiven a knowledge hypergraph defined on τ ′, let τ ′train , τ′test , and τ′valid de-note the train, test, and validation sets, respectively, so that τ ′ = τ ′train unionsqτ ′test unionsq τ ′valid where unionsq is disjoint set union. We use two evaluation metrics:hit@k and Mean Reciprocal Rank (mrr). Both these measures rely on theranking of a tuple x ∈ τ ′test within a set of corrupted tuples. For each tupler(e1, . . . , ek ) in τ′test and each entity position i in the tuple, we generate|E| − 1 corrupted tuples by replacing the entity ei with each of the entitiesin E \ {ei}. For example, by corrupting entity ei , we would obtain a newtuple r(e1, . . . , eci , . . . , ek ) where eci ∈ E \ {ei}. Let the set of corruptedtuples for position i , plus r(e1, . . . , ek ), be denoted by θi(r(e1, . . . , ek )). Letranki(r(e1, . . . , ek )) be the ranking of r(e1, . . . , ek ) within θi(r(e1, . . . , ek ))based on the score φθ(x ) for each x ∈ θi(r(e1, . . . , ek )). In an ideal knowledgehypergraph prediction method, ranki(r(e1, . . . , ek )) is 1 among all corruptedtuples. For a tuple x , let |x | denote the number of entities in the tuple. z isthe number of prediction tasks and is computed as follows.z =∑x∈τ ′test|x |We then compute the mrr as follows.mrr =1z∑x∈τ ′test|x |∑i=11ranki(x )hit@k measures the proportion of tuples in τ ′test that rank among the top kin their corresponding corrupted sets. Following the literature, we remove allcorrupted tuples that are in τ ′ from our computation of mrr and hit@k.17Chapter 3Incorporating OntologicalInformationThe ideas and results presented in this chapter have been published inFatemi et al. [39].3.1 IntroductionIn a knowledge graph, embeddings of entities and relationships are usedto generalize from existing data. These embeddings are often formulated interms of tensor factorization models [15, 76, 106, 140]. Here, the embeddingsare learned such that their interaction through (tensor-)products best pre-dicts the (probability of the) existence of the observed triples; see [104, 147]for details and discussion. Tensor factorization methods have been success-ful, yet they rely on a large number of annotated triples to learn usefulrepresentations. There is often other information in ontologies that specifiesthe meaning of the symbols used in a knowledge base. One type of ontologi-cal information is represented in a hierarchical structure called a taxonomy.For example, Donald Trump is the Wikidata [2] entry for Q22686. Wikidatacontains the information that Donald Trump held the position of presidentof the United States and that he is a human, but does not contain infor-mation that he is a person, a mammal, and an animal, because these areimplied by taxonomic knowledge. Being told that mammals are chordates,lets us conclude that Donald Trump is also a chordate, without needing tohave triples specifying this about multiple mammals. We could also haveinformation about subproperties, such as that holding the position of presi-dent of the United States is a subproperty of being the head of state, whichin turn is a subproperty of being a leader.This chapter is about combining taxonomic information in the form ofsubclass and subproperty into knowledge graph embedding models. We showthat some of the well-known existing embedding-based models that are fullyexpressive cannot reflect such constraints for all legal entity embeddings.183.2. Related WorkWe propose a model that is provably fully expressive and can represent suchtaxonomic information, and evaluate its performance on real-world datasets.3.2 Related WorkIncorporating background knowledge in knowledge graph embedding meth-ods has been the focus of several studies. Here, we categorize these ap-proaches by emphasizing the shortcomings that are addressed in this chap-ter; see [107] for a review of knowledge graph embedding methods.Soft rules. There is a large family of link prediction models based on softfirst-order logic rules [e.g., 30, 77, 117]. These models either receive a set ofhandcrafted logic rules as input or learn the rules from data. Each rule is at-tached with a (typically learned) weight showing some notion of confidenceof the model for the correctness of the rule. Different models define differentsemantics over the rules and their weights to predict new information. Whilethese models can be easily integrated with background taxonomic informa-tion, they typically cannot generalize to unseen cases beyond their rules.Exceptions include Fatemi et al. [38], Kazemi and Poole [75] which combine(stacked layers of) soft rules with entity embeddings, but these models haveonly applied to property prediction for entities. Approaches based on path-constrained random walks [e.g., 85] suffer from similar limitations as theyhave been shown to be a subset of probabilistic logic-based models [74].Augmentation by grounding of the rules. One simple way to incor-porate a set of rules in a knowledge graph is to augment the knowledgegraph with their groundings [126] before learning the embedding e.g., forevery human x in the knowledge base, adding chordate(x ) to the knowl-edge base. Demeester et al. [31] address the computational inefficiency ofthis approach through lifted rule injection. However, in addition to beinginefficient, the resulting model does not guarantee the subsumption in thecompleted knowledge graph.Augmentation through post-processing. A simple approach is to aug-ment the knowledge graph after learning the embedding using an existingmethod [146, 152]. That is, as a post-processing step we can modify theoutput of knowledge graph completion so as to satisfy the ontological con-straints. The drawback of this approach is that the background knowledgedoes not help learn a better representation.193.2. Related WorkRegularized embeddings. Rockta¨schel et al. [120] regularize the learnedembeddings using first-order logic rules. In their work, every logic rule isgrounded based on observations, and a differentiable term is added to theloss function for every grounding. For example, grounding the rule ∀x :human(x ) → animal(x ) would result in a very large number of loss termsto be added to the loss function in a large knowledge graph. This methodas well as other approaches in this category (e.g., Rockta¨schel et al. [119];Wang et al. [146]; Wang and Cohen [149]) do not scale beyond a few entitiesand rules, because of the very large number of regularization terms added tothe loss function [31]. Guo et al. [54] proposed a method for incorporatingentailment into ComplEx called RUGE which models rules based on t-normfuzzy logic, which imposes an independence assumption over the atoms.Such an independence assumption is not necessarily true, especially in thecase of subsumption, e.g., in human(x ) → animal(x ) for which the leftand the right part of the subsumption are dependent. In addition to beinginefficient, the resulting model of the regularized embedding approaches doesnot guarantee the subsumption in the completed knowledge graph.Constrained matrix factorization. Rockta¨schel et al. [120] and De-meester et al. [31] incorporate background ontologies into the embeddingslearned by matrix factorization. While these methods address the problemsof the two categories above, they are inadequate due to the use of matrixfactorization. Application of matrix factorization for knowledge graph com-pletion [118] learns a distinct embedding for each head-tail combination. Inaddition to its prohibitive memory requirement, since entities do not havetheir own embeddings, some regularities in the knowledge graph are ignored;for example, this representation is oblivious to the fact that rk (hi , tj ) andrm(hl , tj ) share the same tail.Constrained translation-based methods. In translation-based meth-ods, the relation between two entities is represented using an affine trans-formation, often in the form of translation. KALE [53] is a model in thiscategory that constrains the representation to accommodate logical rules,albeit after costly propositionalization. Wang et al. [147] and Kazemi andPoole [76] show that a variety of existing translation-based methods are notfully expressive, putting a severe limitation on the kinds of knowledge graphsthat can be modeled using translation-based approaches.203.3. Background and NotationRegion-based representation. Gutie´rrez-Basulto and Schockaert [55]propose representing relations as convex regions in a 2k -dimensional space,where k is the length of the entity embeddings. A relation between two em-beddings is deemed true if the corresponding point is in the convex region ofthe relation. Although this framework allows Gutie´rrez-Basulto and Schock-aert [55] to incorporate a subset of existential rules by restricting the convexregions of relations, they did not propose a practical method for learning,and their method is restricted to a subset of existential rules.Proposed method. The contribution of this work is to prove that someof the well-known existing embedding-based models for knowledge graphcompletion that are fully expressive cannot reflect taxonomic information inthe form of subclass and subproperty for all legal entity embeddings. Wethen propose a knowledge graph embedding model that is provably fullyexpressive and can represent such taxonomic information in the learnedembeddings.3.3 Background and NotationIt is common to have structure over the symbols used in the triples [see e.g.,128]. The Web Ontology Language (OWL) [60] defines (among many othermeta-relations) subproperties and subclasses, where p1 is a subproperty ofp2 if ∀x , y : p1(x , y) → p2(x , y), that is whenever p1 is true, p2 is also true.Classes can be defined either as a set with a class assertion (often called“type”) between an entity and a class, e.g., saying x is in class C usingtype(x ,C ) or in terms of the characteristic function of the class, a functionthat is true of the element of the class. If c is the characteristic function ofclass C , then x is in class c is written c(x , true). For representations thattreat entities and properties symmetrically, the two ways to define classesare essentially the same. C1 is a subclass of C2 if every entity in class C1is in class C2, that is, ∀x : type(x ,C1) → type(x ,C2) or ∀x : c1(x , true) →c2(x , true). If we treat true as an entity, then subclass can be seen as aspecial case of subproperty. For the rest of the chapter, we will refer tosubsumption in terms of subproperty (and so also of subclass).trivial subsumption is when p1 and p2 are both subproperty of eachother i.e., p1 and p2 are the same. A non-trivial subsumption is one whichis not symmetric; p1 is a subproperty of p2 and there exists at least onepair of entities (x , y) that is true of p2 and is not true of p1. Let E∗ be theset of entities when an adversary chooses legal embeddings for the entities213.4. Tensor Factorization and Taxonomiesaccording to the representation used. We define enforcing a subsumption ashaving the subsumption to hold over E∗.3.4 Tensor Factorization and TaxonomiesIn this section, we study some of the well-known existing models for knowl-edge graph completion and their ability to enforce taxonomies. Proofs arein Appendix A starting at Page 117.ComplEx. ComplEx [140] is a knowledge graph embedding model and isexplained in Section 2.3.2. The following theorem proves that we cannot useComplEx to enforce prior knowledge about taxonomies.Theorem 3.1 ComplEx cannot enforce non-trivial subsumptions.The intuition behind the proof is to start with a non-trivial subsumptionand a pair of entities that the subsumption hold for the pair and anotherentity with a specific embedding that causes a contradiction to the subsump-tion assumed.Ding et al. [33] proposed a method which they call ComplEx-NNE+AERto incorporate a weaker notion of subsumption in ComplEx. For a subsump-tion ∀ h, t ∈ E∗ : r(h, t)→ s(h, t), they suggest adding soft constraints to theloss function to encourage Re(r ) ≤ Re(s ) and Im(r ) = Im(s ) (Equation 4in [33]). When the constraints are satisfied, ComplEx-NNE+AER ensures∀h, t ∈ E : φθ(r(h, t)) ≤ φθ(s(h, t)). This is a weaker notion than the def-inition in Section 3.3 which requires ∀ h, t ∈ E∗ : φθ(r(h, t)) ≤ φθ(s(h, t))(that is, E∗ is replaced with E).Theorem 3.2 ComplEx-NNE+AER cannot satisfy its constraints and befully expressive if symmetry constraints are allowed.SimplE. SimplE [76] achieves one of the state-of-the-art results in knowl-edge graph completion and is explained in Section 2.3.2. The followingtheorem shows the limitation of SimplE when it comes to enforcing sub-sumption.Theorem 3.3 SimplE cannot enforce non-trivial subsumptions.The intuition behind the proof for this theorem is similar to that ofTheorem 3.1.223.5. Proposed Variation: SimplE+Neural Network Models for Knowledge Graphs. The neural net-work models [e.g., 34, 124, 132] are very flexible, and so without explicitmechanisms to enforce subsumption, they cannot be guaranteed to obeyany subsumption knowledge.3.5 Proposed Variation: SimplE+In this section, we propose a slight modification on SimplE so that theresulting method can enforce subsumption. The modification is restrictingentity embeddings to be non-negative – that is ∀e ∈ E : e+, e− ≥ 0 , wherethe inequality is element-wise. Next, we show that the resulting model isfully expressive and is able to enforce subsumption.Theorem 3.4 (Expressivity) For any truth assignment over entities Eand relations R containing |τ ′| true triples, there exists a SimplE+ modelwith embeddings vectors of size min(|E| × |R|+ 1, |τ ′|+ 1) that represent theassignment.Theorem 3.5 (Subsumption) SimplE+ guarantees subsumption using in-equality constraints.Objective function and training Given the function φθ, that maps atriple to the probability or score of the triple being true, ideally we wouldlike to minimize the following regularized negative log-likelihood function:L(θ, τ ′train) = −∑x ′∈τ ′trainlog(φθ(x ′))− ∑x∈Tneg (x ′)log(1− φθ(x ))+ Ω(θ)Where θ corresponds to all parameters of a SimplE+ model (entityand relation embeddings) and Ω(θ) is a regularization term. We use L2-regularization in our experiments. Here, Tneg(x ) generates a set of negativesamples corresponding to x by randomly “corrupting” the head or tail of thetriple – i.e., replacing it with a random entity (introduced in Section 2.3.1).Enforcing the subsumptions. In order to enforce ∀h, t ∈ E∗ : r(h, t)→s(h, t), we should have φθ(s(h, t)) ≥ φθ(r(h, t)). For that, we add an equal-ity constraint r = s − δr , where δr is a non-negative vector that specifieshow r differs from s. We learn δr for all relations r which are in such a233.6. Experimental Resultssubsumption. This equality constraint guarantees the inequality constraintof φθ(s(h, t)) ≥ φθ(r(h, t)).Enforcing non-negativity. To enforce the element-wise non-negativityof a vector, such as δr (a non-negative vector for relation r) or h (a non-negative vector for entity h), we apply a non-linearity function with non-negativitive output to its elements. Here, we experiment with three differentchoices of non-linearity σ defined on every element of the vector as follows.I) exponential σ(x ) = ex ; II) logistic σ(x ) = (1 + e−x )−1; and III) rectifiedlinear unit (ReLU) The exponential function is always positive, so it ensuresthat the output of the non-linearity is always non-negative. The logisticfunction is a sigmoid function, which means that it has an S-shaped curve.This means that the output of the non-linearity will be close to zero fornegative inputs, and it will be close to one for positive inputs. The ReLUfunction is a piecewise linear function, which means that it is linear forpositive inputs and zero for negative inputs. We experiment with thesethree different choices of non-linearity to see which one performs best onour task.σ(x ) = max(x , 0).3.6 Experimental ResultsThe objective of our empirical evaluations is two-fold: First, we investi-gate the practical implication of non-negativity constraints in terms of theeffectiveness of training and the quality of final results. Second, we eval-uate the practical benefit of incorporating prior knowledge in the form ofsubsumptions in sparse data regimes.Datasets. We conducted experiments on the standard benchmarks wn18,fb15k, sport and location. wn18 is a subset of wordnet [99] andfb15k is a subset of freebase [14]. sport and location datasets areintroduced by Wang et al. [146], who created them using NELL [100]. Thesubsumptions in sport and location datasets are listed in Table 3.1. Ta-ble 3.2 gives a summary of these datasets. For evaluation on wn18 andfb15k, we split the existing triples into the same train, validation, and testsets using the same split as Bordes et al. [15].243.6. Experimental ResultsTable 3.1: We conduct experiments on sport and location datasets.These datasets are subsets of NELL dataset [100] and are introducedby Wang et al. [146]. The subsumptions in sport and location datasetsare listed in this table.SubsumptionssportAtheleLedSportsTeam(x , y)→ AthletePlaysForTeam(x , y)AthletePlaysForTeam(x , y)→ PersonBelongsToOrganization(x , y)CoachesTeam(x , y)→ PersonBelongsToOrganization(x , y)OrganizationHiredPerson(x , y)→ PersonBelongsToOrganization(y , x )PersonBelongsToOrganization(x , y)→ OrganizationHiredPerson(y , x )locationCapitalCityOfCountry(x , y)→ CityLocatedInCountry(x , y)StateHasCapital(x , y)→ CityLocatedInState(y , x )Table 3.2: Statistics of the datasets used in the experiments. In this table,|E| represents the number of entities, |R| represents the number of relationsin the dataset, and #train, #valid, and #test denote number of triples inthe train, validation, and test sets respectively.Dataset |E| |R| #train #valid #testwn18 40,943 18 141,442 5,000 5,000fb15k 14,951 1,345 483,142 50,000 59,071sport 1039 5 1312 - 307location 445 5 384 - 100253.6. Experimental ResultsTable 3.3: Results of SimplE+ with different non-linearity functions in pro-ducing non-negative embeddings on wn18 dataset without incorporatingsubsumptions. ReLU outperforms other choices, and therefore moving for-ward we use ReLU for non-negativity constraints in SimplE+.wn18Function σ mrr hit@1 hit@3 hit@10SimplE+-Exponential 0.866 0.829 0.925 0.897SimplE+-Logistic 0.854 0.836 0.863 0.885SimplE+-ReLU 0.937 0.936 0.938 0.939Table 3.4: Results of SimplE+ with different non-linearity functions in pro-ducing non-negative embeddings on fb15k dataset without incorporatingsubsumptions. ReLU outperforms other choices, and therefore moving for-ward we use ReLU for non-negativity constraints in SimplE+.fb15kFunction σ mrr hit@1 hit@3 hit@10SimplE+-Exponential 0.575 0.468 0.640 0.773SimplE+-Logistic 0.425 0.294 0.491 0.694SimplE+-ReLU 0.725 0.658 0.770 0.8413.6.1 Effect of Non-negativity Constraints on EntityEmbeddingsNon-negativity has been a subject studied in various research fields. Inmany NLP-related tasks, non-negativity constraints are studied to learnmore interpretable representations for words [101]. In matrix factorization,non-negativity constraints are used to produce more coherent and indepen-dent factors [87]. To get non-negativity constraint on the embedding ofentities, we simply apply an element-wise non-linearity σ : R→ R≥0 beforeevaluation.Tables 3.3 and 3.4 shows the result of SimplE+ with for different choicesof σ: exponential, logistic, and ReLU (defined in Section 3.5). ReLU out-performs other choices, and therefore moving forward we use ReLU for non-negativity constraints.263.6. Experimental ResultsTable 3.5: Results on wn18 for SimplE and SimplE+ without incorporatingsubsumptions. As the results indicate, the non-negativity constraint onentity embeddings deteriorates the model’s performance but allows us to beable to guarantee enforcing subsumptions (as shown in Theorem 3.5).wn18Model mrr hit@1 hit@3 hit@10ComplEx 0.941 0.936 0.945 0.947SimplE 0.942 0.939 0.944 0.947SimplE+ 0.937 0.936 0.938 0.939Table 3.6: Results on fb15k for SimplE and SimplE+ without incorporatingsubsumptions. As the results indicate, the non-negativity constraint onentity embeddings deteriorates the model’s performance but allows us to beable to guarantee enforcing subsumptions (as shown in Theorem 3.5).fb15kModel mrr hit@1 hit@3 hit@10ComplEx 0.692 0.599 0.759 0.840SimplE 0.727 0.660 0.773 0.838SimplE+ 0.725 0.658 0.770 0.841Next, we evaluate the effect of the non-negativity constraint on the per-formance of the algorithm. Tables 3.5 and 3.6 show our result on wn18and fb15k datasets. Note that this is effectively comparing SimplE+ withSimplE and ComplEx, without accommodating any subsumptions. As theresults indicate, this constraint deteriorates the model’s performance in mostcases except for hit@10 on fb15k. As adding this constraint allow us to domore with guaranteeing to enforce subsumption (as shown in Theorem 3.5),we continue to use it in our experiments.3.6.2 Sparse RelationsIn this section, we study the scenario of learning relations that appear in afew triples in the knowledge graph. In particular, we observe the behavior ofvarious methods as the number of training triples varies. We train SimplE,273.6. Experimental Results Proportion Figure 3.1: hit@1 of SimplE, SimplE+, and logical inference when they aretrained on different fractions (percentages) of the training data on sportdataset. The results indicate that when training data is scarce, logical in-ference outperforms (or is on-par with) SimplE, as SimplE does not seeenough triples to be able to learn meaningful embeddings. As the amountof training data increases, SimplE starts to outperform logical inference asit can better generalize to unseen cases than pure logical inference. The gapbetween these two methods becomes larger as the amount of training dataincreases. For all tested fractions, SimplE+ outperforms both SimplE andlogical inference as it uses both the generalization power of SimplE and theinference power of logical rules.SimplE+, and logical inference on fractions of the sport training set andtest them on the full test set. Logical inference refers to inferring new triplesbased only on the subsumptions and training triples.Figure 3.1 shows the hit@1 of the three methods when they are trainedon different fractions (percentages) of the training data. According to Fig-ure 3.1, when training data is scarce, logical inference performs better than(or on-par with) SimplE, as SimplE does not see enough triples to be ableto learn meaningful embeddings. As the amount of training data increases,SimplE starts to outperform logical inference as it can better generalize tounseen cases than pure logical inference. The gap between these two meth-ods becomes larger as the amount of training data increases. For all testedfractions, SimplE+ outperforms both SimplE and logical inference as it usesboth the generalization power of SimplE and the inference power of logicalrules.In order to test the effect of incorporating taxonomical information on283.7. Limitationsthe number of epochs required for training to converge, we tested SimplEand SimplE+ on the sport dataset with the same set of parameters andthe same initialization and plotted the loss function for each epoch. Theplot in Figure 3.2 shows that SimplE+ requires fewer epochs than SimplEto converge.3.6.3 Knowledge Graphs with no Redundant TriplesTensor factorization techniques rely on large amounts of annotated data.When background knowledge is available, we might expect a knowledgegraph to not include redundant information. For instance, if we have thefollowing triple in a knowledge graph:CapitalCityOfCountry(Paris,France)and the following rule is specified:∀h, t ∈ E∗ : CapitalCityOfCountry(h, t)→ CityLocatedInCountry(h, t)Given this, the triple CityLocatedInCountry(Paris,France) is redundant.Similar to the experiment for incorporating background knowledge in [76],we remove all redundant triples from the training set and compare Sim-plE with SimplE+ and logical inference. The obtained results in Tables 3.7and 3.8 demonstrate that SimplE+ outperforms SimplE and logical inferenceon both sport and location datasets with a large margin. As an example,SimplE+ gains ~90% and 230% improvement over SimplE in terms of hit@1for sport and location datasets respectively. These results represent theclear advantage of SimplE+ over SimplE when background taxonomic infor-mation is available.3.7 LimitationsOur proposed model can incorporate subproperties into embeddings. How-ever, it is not able to incorporate all ontological information. For instance,it is not able to incorporate the following rules:• Range information: range rules are in the form of ∀h, t ∈ E∗ : r(h, t)→c1(t , true) which enforces type c1 for tail of relation r , e.g., if we knowParis is located in France, we can infer France is a country.293.8. Conclusion 02004006008001000120014001600180020000 20 40 60 80 100Loss ValueIteration numberSimplESimplE+Figure 3.2: This experiment shows the loss value for SimplE and SimplE+at each training epoch on sport dataset. Models are tested with the exactnumber of parameters and initialization. The results show that SimplE+requires fewer epochs than SimplE to converge.• Domain information: domain rules are in the form of ∀h, t ∈ E∗ :r(h, t) → c2(h, true) which enforces type c2 for head of relation r ,e.g., if we know Paris is located in France, we can infer Paris is a city.• Transitivity: transitivity rules are in the form of ∀h, t , z ∈ E∗ : r(h, z )∧s(z , t) → t(h, t), e.g., if we know Paris is the capital of France andFrance is a country in Europe, we can infer that France is located inEurope.3.8 ConclusionIn this chapter, we proposed SimplE+, a fully expressive tensor factorizationmodel for knowledge graph completion when background taxonomic infor-mation (in terms of subclasses and subproperties) is available. We showedthat existing fully expressive models cannot provably respect subclass andsubproperty information. Then we proved that by adding non-negativityconstraints to entity embeddings of SimplE, one of the state-of-the-art ten-sor factorization approaches, we can build a model that is not only fullyexpressive but also able to enforce subsumptions. Experimental results onbenchmark knowledge graphs demonstrate that SimplE+ is simple yet effec-tive. On our benchmarks, SimplE+ outperforms SimplE and offers a fasterconvergence rate when background taxonomic information is available.303.8. ConclusionTable 3.7: Results comparing logical inference, SimplE, and SimplE+ onsport dataset. The best results are in bold. mrr and hit@k for k > 1 isnot applicable for logical inference as it either predict the correct entity ornot (SimplE and SimplE+ predict a ranking). The results demonstrate theeffectiveness of SimplE+ in the presence of subsumptions.sportModel mrr hit@1 hit@3 hit@10Logical inference - 0.288 - -SimplE 0.230 0.184 0.234 0.324SimplE+ 0.404 0.349 0.440 0.508Table 3.8: Results comparing logical inference, SimplE, and SimplE+ onlocation dataset. The best results are in bold. mrr and hit@k for k > 1is not applicable for logical inference as it either predict the correct entityor not (SimplE and SimplE+ predict a ranking). The results demonstratethe effectiveness of SimplE+ in the presence of subsumptions.locationModel mrr hit@1 hit@3 hit@10Logical inference - 0.270 - -SimplE 0.190 0.130 0.210 0.315SimplE+ 0.440 0.430 0.440 0.45031Chapter 4Incorporating n-aryRelationsThis chapter is structured in three sections. Section 4.1 discusses n-ary rela-tions in knowledge hypergraphs and why converting them to binary relationsas in knowledge graphs does not work. Section 4.2 introduces link predic-tion models for knowledge hypergraphs inspired by link prediction modelsfor knowledge graphs, benchmarks, baselines, and evaluation metrics for thistask. Section 4.3 explores the gap between relational algebra foundationsand machine learning techniques for knowledge hypergraph completion. Theresults presented in this chapter have been published in Fatemi et al. [40, 42].4.1 IntroductionKnowledge hypergraphs are knowledge bases that store information aboutthe world in the form of tuples describing relations among entities. Knowl-edge graphs are a specific form of knowledge hypergraphs that representrelations between exactly two entities. Knowledge hypergraphs thus gen-eralize knowledge graphs by allowing multi-argument relations. Knowledgehypergraphs are similar to relational databases. In relational databases,each table describes tuples about one specific relation. Each table has thenumber of columns equal to the arity of the relation.Knowledge hypergraphs are incomplete because curating and storing allthe true information in the world is difficult. The goal of link predictionin knowledge hypergraphs (or knowledge hypergraph completion) is to pre-dict unknown relationships among entities based on existing ones. In thischapter, we are interested in the problem of link prediction in knowledgehypergraphs. Our motivation for studying link prediction in these more so-phisticated knowledge structures is based on the fact that much knowledgein the world is in the form of relations among more than two entities.Link prediction in knowledge graphs is studied extensively in the litera-ture [e.g., 15, 76, 140, 158]. In these studies, knowledge graphs are defined324.1. Introductionas directed graphs having nodes as entities and labeled edges as relations;edges are directed from the head entity to the tail entity. The commondata structure for representing knowledge graphs is a set of triples of theform relation(head , tail) that represents information as a collection of binaryrelations.Embedding-based models (discussed in Section 2.3.2) learn embeddingsfor entities and relations and to predict whether a triple relation(head , tail)is true, such models define a scoring function φθ that uses embeddings ofrelation, head , and tail and outputs the probability of the triple being true.Such embedding-based methods make the strong assumption that all rela-tions are binary. One might hypothesize that for predicting new links in aknowledge hypergraph, we can convert n-ary relations to binary ones usingconversion techniques such as reification or star-to-clique [153] and then ap-plying existing models for link prediction on knowledge graphs on them. Inwhat follows, we explain the challenges that arise when coupling conversiontechniques with knowledge graph completion models. We motivate our workby outlining that converting non-binary relations into binary ones and thenapplying known link prediction methods does not yield satisfactory results.Reification is one common approach to converting higher-arity relationsinto binary ones. For each relation r with arity k , reification forms k newbinary relations r1 . . . rk . For each tuple, reification constructs an entitycorresponding to the tuple. It converts a tuple r(e1, . . . , ek ) to a set oftriples r1(e, e1), . . . , rk (e, ek ) with a new entity e.For instance, for the relation FliesBetween with arity 3, reification forms3 binary relations as follows: FliesBetweenAirline, FliesBetweenDeparture,and FliesBetweenArrival . Assume we want to reify the following tuple withthe relation FliesBetween.FliesBetween(AirCanada,Vancouver ,NewYork)For reifying this tuple, reification defines a new entity e.g., AC 548 specif-ically for this tuple. The tuple is then converted to the following set of triplesusing the binary relations corresponding to FliesBetween, entity AC 548, andthe existing entities in the tuple.FliesBetweenAirline(AC 548,AirCanada)FliesBetweenDeparture(AC 548,Vancouver)FliesBetweenArrival(AC 548,NewYork)334.1. IntroductionUnited AirlineLos AngelesVancouverNew YorkMontrealAir Canada(a)United AirlineLos AngelesVancouverNew YorkMontrealAir Canadae1e3e2(b)United AirlineLos AngelesVancouverNew YorkMontrealAir Canada(c)Figure 4.1: (a) Relation FliesBetween with arity 3 defined on three tuples.(b) Reifying non-binary relations by creating three additional entities e1,e2, and e3. (c) Converting non-binary relations into cliques using star-to-clique. In this example, the three facts in the original graph (a) show thatAir Canada has a flight from Montreal to Los Angeles and from Vancouverto New York. Figures (b) and (c) show two methods of converting thisternary relation into binary ones.The example in Figure 4.1a shows three facts that pertain to the relationFliesBetween. When we reify the hypergraph in this example (Figure 4.1b),we add three reified entities e1, e2, and e3 (brown square nodes). In termsof representation, the binary relations created are equivalent to the originalrepresentation. Reification is complete and does not lose information duringthe conversion and because of this, the reification process is reversible.It is noteworthy to mention that freebase represents the relationsamong entities using triples with reification. We reverse the reification pro-cess (we explain the reverse reification process in Section 4.2.4) in freebaseand notice that 61% of the relations are defined on more than two entities(are beyond binary). Wen et al. (2016) observe that in the original free-base more than 1/3rd of the entities participate in non-binary relations(i.e., defined on more than two entities).Another conversion approach is star-to-clique, which forms(k2)binaryrelations for each relation with arity k . It converts a tuple defined on kentities into(k2)tuples with distinct relations between all pairwise entities inthe tuple. For instance, for the tuple above, it forms the following 3 binaryrelations: FliesBetweenAirlineDeparture, FliesBetweenAirlineArrival , andFliesBetweenDepartureArrival . It converts the tuple to the following triples.FliesBetweenAirlineDeparture(AirCanada,Vancouver)344.2. Knowledge Hypergraph Completion: HSimplE and HypEFliesBetweenAirlineArrival(AirCanada,NewYork)FliesBetweenDepartureArrival(Vancouver ,NewYork)The challenge with reification arises when converting higher-arity rela-tions to binary ones and then applying existing embedding-based methods.This is because we introduce new entities that the model never encountersduring training and we do not have a learned embedding for these entities,and current embedding-based methods require an embedding for each entityto be able to make a prediction during evaluation. Applying the star-to-clique method to a hypergraph is problematic. This is because it is impossi-ble to construct the original tuples from the triples after start-to-clique con-version. Figure 4.1c shows the result of applying star-to-clique to the origi-nal hypergraph in Figure 4.1a, in which the tuple FliesBetween(AirCanada,NewYork, LosAngeles) might be interpreted as being true since the corre-sponding entities are connected by edges, whereas looking at the originalhypergraph, there is not a hyperedge connecting AirCanada, NewYork , andLosAngeles.4.2 Knowledge Hypergraph Completion:HSimplE and HypEIn this section, we introduce two embedding-based models that perform linkprediction directly on knowledge hypergraphs without converting them tographs. Both proposed models are based on the idea that predicting theexistence of a relation between a set of entities depends on the position ofthe entities in the relation; otherwise, if the positions of the entities are notincorporated when making a prediction, the model has the assumption thatall relations are symmetric. Learning entity embeddings for each positionindependently does not work well, as it does not let the information flowbetween the embeddings for the different positions of the same entity. Theinformation flow problem between different embeddings for an entity is sim-ilar to the reason why CP performs poorly and how SimplE resolves theissue - see Section 2.3.2).The first model we propose is HSimplE. For a given entity, HSimplE shiftsthe entity embedding by a value that depends on the position of the entityin the given relation. Our second model is HypE, which in addition to learn-ing entity embeddings, learns positional (convolutional) embeddings; thesepositional embeddings are disentangled from entity representations and areused to transform the representation of an entity based on its position in354.2. Knowledge Hypergraph Completion: HSimplE and HypEa relation. This makes HypE more robust to changes in the position of anentity within a tuple. We show that both HSimplE and HypE are fullyexpressive. To evaluate our models, we introduce two new datasets fromsubsets of freebase, and develop baselines by extending existing modelson knowledge graphs to work with hypergraphs.The contributions of this section are as follows.• Showing that current techniques to convert a knowledge hypergraphto a knowledge graph do not yield satisfactory results for the linkprediction task.• Introducing HypE and HSimplE, two models for knowledge hyper-graph completion.• Introducing a set of baselines for knowledge hypergraph completion byextending some of the knowledge graph completion models to n-aryrelations.• Collecting two new datasets containing multi-arity relations from sub-sets of freebase, which can serve as new evaluation benchmarks forknowledge hypergraph completion methods. We also show that ourproposed methods outperform baselines.4.2.1 Related WorkExisting methods that relate to our work in this section can be grouped intothe following three main categories.Knowledge graph completion. Embedding-based models for knowledgegraph completion such as translational [15, 151], bilinear [76, 158], and deepmodels [132] have proved to be effective for knowledge graphs where allrelations are binary. In Section 4.2.6, we extend some of the models in thiscategory to knowledge hypergraphs and compare their performance with theproposed methods.Knowledge hypergraph completion. Soft-rule models [30, 77] can han-dle variable arity relations and have the advantage of being interpretable.However, they can only learn a subset of patterns [107]. Guan et al. [51]propose an embedding-based method based on the star-to-clique approach.The caveats of this approach are discussed earlier. m-TransH [153] extendsTransH [151] to knowledge hypergraph completion. Kazemi and Poole [76]364.2. Knowledge Hypergraph Completion: HSimplE and HypEprove that TransH, and consequently m-TransH, are not fully expressive andhave restrictions in the type of relations they can model (See Lemma 4.3.1for a detailed discussion). In contrast, we prove that our proposed modelsare fully expressive.Learning on hypergraphs. Hypergraph learning has been employed tomodel high-order correlations among data in many tasks, such as in videoobject segmentation [65] and modeling image relationships and image rank-ing [66]. There is also a line of work extending graph neural networks tohypergraph neural networks [44] and hypergraph convolution networks [156].These models are designed for undirected hypergraphs, with edges that arenot labeled (no relations), while knowledge hypergraphs are directed andlabeled graphs. As there is no clear or easy way of extending these modelsto our knowledge hypergraph setting, we do not consider them as baselinesfor our experiments.Learning with tabular data. Tabular data is similar to the data storedin knowledge hypergraphs. There are several models proposed to work withtabular data. Some are based on variants of ensemble decision trees. Amongensembling methods, random forests [61] use randomly selected featuresfrom random subsets of data to grow many trees. XGBoost [22] and Light-GBM [80] are the two ensemble decision tree approaches that dominatemost of the recent data science competitions. Some more recent models fortabular data are based on deep learning approaches [5]. These models aredesigned for classification tasks on tabular data.4.2.2 Proposed MethodsOur proposed methods explore different approaches to how a prediction canbe affected by the embeddings of the relation and entities in the tuple aswell as the role of the entities in the tuple. For instance, when makingpredictions for Sold(Drew ,Alex ,Book) indicating whether Drew sold Alex aBook or making predictions for Sold(Alex ,Drew ,Book) indicating whetherAlex sold Drew a Book , the entity embeddings for Drew and Alex andthe relation embedding for Sold should be used as well as the positions ofDrew and Alex in the tuples. This is because the first position in the Soldrelation corresponds to the seller and the second position corresponds to thebuyer (and the third position contains the item). As another example, inFigure 4.1a, Montreal is the departure city; but it may appear in a differentposition (e.g., arrival city) in another tuple. This means that the way we374.2. Knowledge Hypergraph Completion: HSimplE and HypE(a) (b) (c)Figure 4.2: Visualization of HSimplE and HypE architectures. (a) φθ forHSimplE transforms entity embeddings by shifting them based on their posi-tion and combining them with the relation embedding. (b) f (e , i) for HypEtakes an entity embedding and the position the entity appears in the giventuple, and returns a vector. (c) φθ takes as input a tuple and outputs thescore of HypE for the tuple.use Montreal’s embedding for making predictions may need to vary basedon the position it appears in within the tuple.When using the embedding of an entity to make a prediction, if theprediction does not depend on the positions of the entities in the tuple, thenthe relation has to be symmetric (which is not the case for most relationse.g., Sold relation). DistMult [158] (discussed in Section 2.3.2) does notdistinguish among an entity appearing in different positions in its scoringfunction and can only model symmetric relations.On the other hand, if for each entity, we learn multiple independententity embeddings, each corresponding to when the entity appears in thatspecific position, information about one position will not interact with thatof others. For instance, canonical polyadic [59] has this information flowproblem as it learns multiple independent embeddings for cases when anentity appears in different positions (discussed in Section 2.3.2). It shouldbe noted that in several embedding-based methods for knowledge graphcompletion, such as ComplEx [140] and SimplE [76], the prediction dependson the position of each entity in the tuple.In what follows, we propose two embedding-based methods for link pre-diction in knowledge hypergraphs. The first model is inspired by SimplEand has its roots in knowledge graph completion; the second model takes afresh look at knowledge completion as a multi-arity problem, without firstsetting it up within the frame of binary relation prediction.384.2. Knowledge Hypergraph Completion: HSimplE and HypEHSimplEHSimplE is an embedding-based method for link prediction in knowledgehypergraphs that is inspired by SimplE [76] (see Section 2.3.2 for a detailedexplanation of SimplE). SimplE learns two embedding vectors e+ and e− foran entity e (one for each possible position of the entity), and two embeddingvectors r+ and r− for a relation r (with one relation embedding as theinverse of the other). SimplE computes the score of a triple as follows withthe () function computing the sum of the element-wise product of its inputvectors.φθ(r(ei , ej )) = (r+, e+i , e−j ) + (r−, e+j , e−i ) (4.1)Here, we provide another view of the same scoring function Equation 4.1.This view helps us extend SimplE to higher arity relations. Function concatreturns the concatenation of its input vectors. len(e ) returns the length ofvector e . circshift(v , x ) circularly shifts the elements in vector v to the leftby x steps. Formally, for a vector v ∈ Rn , indexed 0 . . .n − 1, a circularshift of size x is a permutation pi of the n entries in the tuple such that thefollowing holds for indices in the output of the circular shift.∀i 0 ≤ i ≤ n − 1 : pi(i) = (i + x ) modulo nAs an example, for v = [5, 2, 4, 1] and x = 2, circshift(v , x) is [4, 1, 5, 2].The following equation shows a different view of the same scoring function ofSimplE as in Equation 4.1. Let e 1 be concat(e+1 , e−1 ), e 2 be concat(e+2 , e−2 ),and r be concat(r+, r−).φθ(r(ei , ej )) = (r , e i , circshift(e j, len(e 2)/2)) (4.2)Equation 4.1 and Equation 4.2 are equal, because in Equation 4.2, wecircularly shift e 2 to align its indices with that of e 1 to get the same outputas in Equation 4.1.In HSimplE, we adopt the idea of having different representations for anentity based on its position in a relation and updating all these representa-tions from a single training tuple. We do this by representing each entitye as a single vector e (instead of multiple vectors as in SimplE), and eachrelation r as a single vector r . Conceptually, each e can be seen as theconcatenation of the different representations of e based on every possibleposition. For example, in a knowledge hypergraph where the relation withmaximum arity is α, an entity can appear in α different positions; hence394.2. Knowledge Hypergraph Completion: HSimplE and HypEe will be the concatenation of α vectors, one for each possible position.HSimplE scores a tuple using the following function.φθ(r(ei , ej , . . . , ek )) = (r , e i , shift(e j, len(e j)/α), . . . ,shift(ek, len(ek) · (α− 1)/α))) (4.3)Here, α = maxr∈R(|r |) is the maximum arity of the relations in theknowledge hypergraph. We observe that for knowledge graphs (α = 2),Equation 4.3 reduces to Equation 4.2 showing that SimplE is a special in-stance of HSimplE. The architecture of HSimplE is summarized in Fig-ure 4.2a.HypEHSimplE learns an embedding for each entity and relation. When an entityappears in a specific position in a tuple, HSimplE circularly shifts the embed-ding to project it to the latent space of the position. HypE, in addition tolearning entity embeddings, learns positional (convolutional) embeddings;these positional embeddings are disentangled from entity representationsand are used to transform the representation of an entity based on its posi-tion in a relation. This makes HypE more robust to changes in the positionof an entity within a tuple.HypE learns a single representation for each entity, a single represen-tation for each relation, and positional convolutional weight filters for eachpossible position. When an entity appears in a specific position, the appro-priate positional filters are first used to transform the embedding of eachentity in the given fact; these transformed entity embeddings are then com-bined with the embedding of the relation to producing a score, i.e., theprobability of the input tuple to be true. The architecture of HypE is sum-marized in Figures 4.2b and 4.2c.Let n denote the number of filters per position, l the filter length, d theembedding dimension, and s the stride of a convolution. Let W i ∈ Rn×l bethe convolutional filters associated with position i , and let W i [j ] ∈ Rl bethe j -th row of W i . We denote by P ∈ Rnq×d the projection matrix, whereq = b(d − l)/sc+ 1 is the feature map size. For a given tuple with an entitye appearing in the i -th position, we use the following function as definedbelow to map the embedding vector e to eˆ ∈ Rnq .eˆ = concat(e ∗W i [1], . . . , e ∗W i[n])404.2. Knowledge Hypergraph Completion: HSimplE and HypEFunction f is used afterward as multiplication of the vector eˆ and matrixP . It returns a vector of size d .f (e , i) = eˆPThus, each entity embedding e appearing at position i in a given tuple isconvolved with the set of position-specific filters W i to give n feature mapsof size q . All n feature maps corresponding to an entity are concatenatedinto a vector of size nq and projected to the embedding space through mul-tiplication by P . The projected vectors of entities and the embedding of therelation are combined by inner-product to define φθ:φθ(r(e1, . . . , e|r |)) = (r , f (e 1, 1), . . . , f (e |r |, |r |)). (4.4)The advantage of learning positional filters disentangled from entity em-beddings is two folds: On one hand, learning a single vector per entity keepsentity representations simple and disentangled from its position in a givenfact. On the other hand, unlike HSimplE, HypE learns positional filtersfrom all entities that appear in the given position; overall, this separation ofrepresentations for entities, relations, and positions facilitates the represen-tation of knowledge bases having facts with an arbitrary number of entities.It also gives HypE additional robustness, such as in the case when we test atrained HypE model on a tuple that contains an entity in a position neverseen before at train time. We discuss this in Section 4.2.6.Both HSimplE and HypE are fully expressive — an important propertythat has been the focus of several studies [39]. A model that is not fullyexpressive can embed assumptions that may not be reflected in reality.Theorem 4.1 (Expressivity) For any ground truth over entities E andrelations R containing |τ | true tuples and α = maxr∈R(|r |) , there exists aHypE and a HSimplE model with embedding vectors of size max(α|τ |, α) thatrepresents that ground truth.The proof is in Appendix B.1.4.2.3 Objective Function and TrainingBoth HSimplE and HypE are trained using stochastic gradient descent withmini-batches. As there are only positive instances available and negativeinstances are also needed for training the model, we generate negative ex-amples. For negative sample generation, we follow the contrastive approach414.2. Knowledge Hypergraph Completion: HSimplE and HypEof [15] for knowledge graphs and extend it to knowledge hypergraphs: foreach tuple, we produce a set of negative samples of size N |r | by replacingeach of the entities with N random entities in the tuple, one at a time. Here,N is the ratio of negative samples in our training set and is a hyperparam-eter. For training both models, we define the following cross-entropy loss:L(θ, τ ′train) =∑x ′∈τ ′train−log(eφθ(x′)eφθ(x ′) +∑x∈Tneg (x ′)eφθ(x))(4.5)4.2.4 DatasetsWe conduct experiments on a total of 5 datasets. For the experimentson datasets with binary relations, we use two standard benchmarks forknowledge graph completion: wn18 [16] and fb15k [15] (introduced inSection 3.6). The experiments on knowledge hypergraph completion areconducted on three datasets. The first is jf17k proposed by Wen et al.(2016) which contain train and test sets; as no validation set is proposed forjf17k, we randomly select 20% of the train set as validation. We also createtwo datasets fb-auto and m-fb15k from freebase. In what follows, weexplain how these two datasets are created.Dataset Creation. We downloaded freebase [14] from [1]. Note thatfreebase uses reification to represent relations with triples; Relations infreebase have three parts separated with a ‘.’ e.g., the following is a re-lation in freebase: film.performance.actor. The first and second partsshow the relation name and the third part shows the role in the relation.Here are three examples of binary relations in freebase.• film.performance.actor(/m/04q4bd8, /m/07yyhx)• film.performance.character(/m/04q4bd8, /m/0qzpnz5)• film.performance.film(/m/04q4bd8, /m/04mxv5p)From the Knowledge Graph Search API link, the entities /m/07yyhx,/m/0qzpnz5, and /m/04mxv5p refer to actress “Kathlyn Williams”, character“Queen Isabel of Bourbon”, and movie “The Spanish Dancer” respectively.The entity /m/04q4bd8 is a reified entity.To obtain a knowledge hypergraph H from freebase, we perform aninverse reification process by following the steps below.424.2. Knowledge Hypergraph Completion: HSimplE and HypE1. From freebase, We start with all triples without numbers or enu-merations. This is because our focus is on entities. Handling numbersor enumerations is a different area and is considered a future work.2. Extract the relation names from the first two parts of the relations andthe mapping from roles to positions. For instance, film.performanceis a relation name with its first argument as an actor, the secondargument as a character, and the third argument as a film.3. Join the triples in freebase that have the same relation name andthe same entity in the first position (the first entity refers to the reifiedentity). The role (the third part of the relation) identifies the positionin the resulting relation. For example, we convert the three tuplesabove to a tuple with a relation of arity 3 as:film.performance(/m/07yyhx, /m/0qzpnz5, /m/04mxv5p)with the first, second, and third positions representing the actor, char-acter, and movie of the performance respectively in H .4. Create the fb-auto dataset by selecting the facts from H whose sub-ject is ‘automotive’ (the first part of relation names is ‘automative’.The ‘automative’ is selected to get a dataset with different statisticscompared to the two other datasets).5. Create the m-fb15k dataset by following a strategy similar to thatproposed by [15]: select the facts in H that pertain to entities presentin the Wikilinks database [129].6. Split the facts in each of fb-auto and m-fb15k randomly into train,test, and validation sets.See Tables 4.1 and 4.2 for statistics of the datasets.4.2.5 BaselinesTo compare our results to that of existing work, we first design simple base-lines that extend current models to work with knowledge hypergraphs. Weonly consider models that admit a simple extension to higher-binary rela-tions for the link prediction task. The baselines for this task are grouped intothe following categories: (1) methods that work with binary relations andthat are easily extendable to higher-arity, namely r-SimplE, m-DistMult, andm-CP; (2) existing methods that can handle higher-arity relations, namelym-TransH. Below we give some details about methods in category (1).434.2. Knowledge Hypergraph Completion: HSimplE and HypETable 4.1: Statistics of the datasets used in the experiments. In this table,|E| represents the number of entities, |R| represents the number of relationsin the dataset, and #train, #valid, and #test denote number of triples inthe train, validation, and test sets respectively.Dataset |E| |R| #train #valid #testjf17k 29,177 327 77,733 – 24,915fb-auto 3,410 8 6,778 2,255 2,180m-fb15k 10,314 71 415,375 39,348 38,797Table 4.2: Number of tuples with different arities in different datasets.number of tuples with respective arityDataset arity=2 arity=3 arity=4 arity=5 arity=6jf17k 56,322 34,550 9,509 2,230 37fb-auto 3,786 0 215 7,212 0m-fb15k 82,247 400,027 26 11,220 0r-SimplE. To test the performance of a model trained on reified data, weconvert higher-arity relations in the train set to binary relations throughreification. We then use SimplE (that we call r-SimplE) on this reified data.In this setting, at test time higher-arity relations are first reified to a setof binary relations; this process creates new auxiliary entities for which themodel has no learned embeddings. To embed the auxiliary entities for theprediction step, we use the observation we have about them at test time. Forexample, a relation with arity greater than two r(e1, e2, e3) is reified at testtime by adding a new entity e ′ and converting the higher-arity tuple to threebinary facts: r1(e′, e1), r2(e ′, e2), and r3(e ′, e3). When predicting the tailentity of r1(e′, ?), we use the other two reified facts to learn an embeddingfor entity e ′. Because e ′ is added only to help represent the higher-arityrelations as a set of binary relations, we only need to do tail prediction forreified relations. We do not reify binary relations.m-DistMult. DistMult [158] defines a score function as follows.φθ(r(ei , ej )) = (r , e i , e j )444.2. Knowledge Hypergraph Completion: HSimplE and HypETable 4.3: Knowledge hypergraph completion results on jf17k, fb-autoand m-fb15k for baselines and the proposed method. The prefixes ‘r’ and‘m’ in the model names stand for reification and multi-arity respectively.Both our methods outperform the baselines on all datasets. Results forjf17k dataset is an average of three runs.jf17k fb-auto m-fb15kModel mrr hit@1 hit@3 hit@10 mrr hit@1 hit@3 hit@10 mrr hit@1 hit@3 hit@10r-SimplE 0.102 0.069 0.112 0.168 0.106 0.082 0.115 0.147 0.051 0.042 0.054 0.070m-DistMult 0.463 0.372 0.510 0.634 0.784 0.745 0.815 0.845 0.705 0.633 0.740 0.844m-CP 0.391 0.298 0.443 0.563 0.752 0.704 0.785 0.837 0.680 0.605 0.715 0.828m-TransH [153] 0.444 0.370 0.475 0.581 0.728 0.727 0.728 0.728 0.623 0.531 0.669 0.809HSimplE (Ours) 0.472 0.378 0.520 0.645 0.798 0.766 0.821 0.855 0.730 0.664 0.763 0.859HypE (Ours) 0.494 0.408 0.538 0.656 0.804 0.774 0.823 0.856 0.777 0.725 0.800 0.881To accommodate non-binary relations, we redefine this function as follows.φθ(r(ei , . . . , ej )) = (r , e i , . . . , e j )m-CP. Canonical Polyadic decomposition [59] is a tensor decompositionapproach. We refer to the version that only handles binary relations as CP.CP embeds each entity e as two vectors e (1) and e (2), and each relation r asa single vector r ; it defines the score function φθ(r(ei , ej )) = (r , e (1)i , e (2)j ).We call the version of CP that accommodates relations of any arity m-CP. m-CP embeds each entity e as α different vectors e (1), . . . , e (α), whereα = maxr∈R(|r |); it computes the score of a tuple as follows.φθ(r(ei , . . . , ej )) = (r , e (1)i , . . . , e (|r |)j )4.2.6 ExperimentsThis section summarizes our experiments.Knowledge Hypergraph Completion ResultsThe results of our experiments, summarized in Table 4.3, show that bothHSimplE and HypE outperform the proposed baselines across the threeknowledge hypergraph datasets jf17k, fb-auto, and m-fb15k. They fur-ther demonstrate that reification for the r-SimplE model does not work well;this is because the reification process introduces auxiliary entities for whichthe model does not learn appropriate embeddings because these auxiliaryentities appear in very few facts. Comparing the results of r-SimplE against454.2. Knowledge Hypergraph Completion: HSimplE and HypE(a) (b)Figure 4.3: These experiments show that HypE outperforms HSimplE whentrained with fewer parameters, and when tested on samples that contain atleast one entity in a position never encountered during training on jf17kdataset. (a) mrr of HypE and HSimplE for different embedding dimensions.(b) Results of m-CP, HSimplE, and HypE on the missing positions test set(containing 1,806 test samples).HSimplE, we can also see that extending a model to work with hypergraphsworks better than reification when high-arity relations are present.The ability of knowledge sharing through the learned position-dependentconvolution filters suggests that HypE would need fewer parameters thanHSimplE to obtain good results. To test this, we train both models withdifferent embedding dimensions. Figure 4.3a shows the mrr on the test setfor each model with different embedding sizes. Based on the mrr result, wecan see that HypE outperforms HSimplE by 24% for embedding dimension50, implying that HypE works better under a constrained budget.Disentangling the representations of entity embeddings and positionalfilters enables HypE to better learn the role of position within a relation be-cause the learning process considers the behavior of all entities that appearin a given position at the time of training. This becomes especially impor-tant in the case when some entities never appear in certain positions in thetrain set, but you still want to be able to reason about them no matter whatposition they appear in at test time. To test the effectiveness of our modelsin this more challenging scenario, we created a missing positions test set byselecting the tuples from our original test set that contain at least one entityin a position it never appears in within the training dataset. The results onthese experiments (Figure 4.3b) show that (1) both HSimplE and HypE out-perform m-CP (which learns different embeddings for each entity-positionpair), and more importantly, (2) HypE significantly outperforms HSimplE464.2. Knowledge Hypergraph Completion: HSimplE and HypETable 4.4: Knowledge graph completion results on wn18 for baselines andHypE. Note that in knowledge graphs (binary relations), HSimplE and Sim-plE are equivalent, both theoretically and experimentally. The results showthat our methods outperform the baselines.wn18Model mrr hit@1 hit@3 hit@10CP [59] 0.074 0.049 0.080 0.125TransH [151] - - - 0.867m-TransH [153] 0.671 0.495 0.839 0.923DistMult [158] 0.822 0.728 0.914 0.936HSimplE (Ours) and SimplE [76] 0.942 0.939 0.944 0.947HypE (Ours) 0.934 0.927 0.940 0.944Table 4.5: Knowledge graph completion results on fb15k for baselines andHypE. Note that in knowledge graphs (binary relations), HSimplE and Sim-plE are equivalent, both theoretically and experimentally. The results showthat our methods outperform the baselines.fb15kModel mrr hit@1 hit@3 hit@10CP [59] 0.326 0.219 0.376 0.532TransH [151] - - - 0.585m-TransH [153] 0.351 0.228 0.427 0.559DistMult [158] 0.654 0.546 0.733 0.824HSimplE (Ours) and SimplE [76] 0.727 0.660 0.773 0.838HypE (Ours) 0.725 0.648 0.777 0.856for this challenging test set, leading us to believe that disentangling entityand position representations may be a better strategy for this scenario.Knowledge Graph Completion ResultsTo show that HSimplE and HypE work well also on the more commonknowledge graphs, we evaluate them onwn18 and fb15k. Tables 4.4 and 4.5shows link prediction results on wn18 and fb15k. Baseline results are takenfrom the original papers except that of m-TransH, which we implementourselves. Instead of tuning the parameters of HypE to get potentiallybetter results, we follow the Kazemi and Poole (2018) setup with the samegrid search approach by setting n = 2, l = 2, and s = 2. This results inall models in Tables 4.4 and 4.5 having the same number of parameters,474.2. Knowledge Hypergraph Completion: HSimplE and HypETable 4.6: Breakdown performance of hit@10 across relations with differentarities on jf17k dataset along with their statistics.ArityModel 2 3 4-5-6 Allr-SimplE 0.478 0.025 0.017 0.168m-DistMult 0.495 0.648 0.809 0.634m-CP 0.409 0.563 0.765 0.560m-TransH [153] 0.411 0.617 0.826 0.596HSimplE (Ours) 0.497 0.699 0.745 0.645HypE (Ours) 0.466 0.693 0.858 0.656# train tuples 36,293 18,846 6,772 61,911# test tuples 10,758 10,736 3,421 24,915and thus makes them directly comparable to each other. Note that forknowledge graph completion (all binary relations) HSimplE is equivalent toSimplE, both theoretically and experimentally (as shown in Section 4.2.2).The results show that on wn18 and fb15k, HSimplE and HypE outperformall baselines.Ablation Study on Different AritiesWe break down the performance of models across different arities. As thenumber of test tuples in higher arities (4-5-6) is much less than in smallerarities (2-3), we used equivalent size bins to show the decomposed results fora reasonable number of test tuples. Table 4.6 shows the hit@10 results ofthe models for bins of arity 2, 3, and 4-5-6 in jf17k. The proposed modelsoutperform the state-of-the-art and baselines in all arities. We highlightthat r-SimplE and HSimplE are quite different models for relations havingarity > 2.4.2.7 ConclusionsKnowledge hypergraph completion is an important problem that has re-ceived little attention. Having introduced two new knowledge hypergraphdatasets, baselines, and two new methods for link prediction in knowledgehypergraphs, we hope to kindle interest in the problem. Unlike graphs,hypergraphs have a more complex structure that opens the door to morechallenging questions such as: how do we effectively predict the missingentities in a given (partial) tuple?484.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlE4.3 Knowledge Hypergraph Completion withRelational Algebra: ReAlESection 4.2 introduces link prediction models for knowledge hypergraphsinspired by link prediction models for knowledge graphs, benchmarks, base-lines, and evaluation metrics for this task. This section explores the gapbetween relational algebra foundations and machine learning techniques forknowledge hypergraph completion.Relational databases have been a successful model for data storage, andhave relied on query languages for information retrieval. Most of thesequery languages are based on relational algebra, a mathematical formaliza-tion at the core of relational models. This work takes a look at knowledgehypergraph completion through the lens of relational algebra and its coreoperations. We explore the gap between relational algebra foundations andmachine learning techniques for knowledge completion.Recent research [e.g., 10, 138] has highlighted the importance of rela-tional inductive biases in building learning agents that learn entity-independentrelational semantics and reason in a compositional manner. In this work,we explore the foundations of knowledge hypergraph completion; we aim todesign a model for reasoning in knowledge hypergraphs that is simple, ex-pressive, and can represent high-level abstractions in terms of the operationsof relational databases. We hypothesize that models that can reason aboutrelations in terms of relational algebra operations have better generalizationpower.Constraint vs. query languages. To understand the role of relationalalgebra, and to understand its relationships to other foundations, it is im-portant to understand the distinction between constraint and query lan-guages. In relational databases, constraints and queries play complemen-tary roles. Constraints specify restrictions to impose on the database, whilequeries extract information that may not be explicitly encoded. In otherwords, constraints imply that some combination of tuples must be false,while queries help us determine what else must be true. Both constraintsand queries can be written as (a subset of) first-order logic rules. Considerthe following example. Suppose the data tells us that Sam lives with Sally(which we write as LivesWith(Sam,Sally)) and Sally lives in Paris (writtenas LivesIn(Sally ,Paris)). A query language would let us state that someonelives in the same city as a person they live with, which would let us inferLivesIn(Sam,Paris). The constraint that someone only lives in one city494.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEmakes us reject the statement LivesIn(Sally ,Berlin).Unlike in constraint languages, defining one relation in terms of othersin a query language does not have side effects – i.e. the representation ofa relation r does not affect the truth of relations not defined in terms of r ,which is crucial when we want to capture multiple inference patterns jointly.We can think of a query language as being similar to a directed graphicalmodel and a constraint language as an undirected graphical model. In adirected graphical model, we add a new random variable by using existingvariables as its parents. Adding the variable does not change the distributionof the parents. Whereas, in an undirected graphical model, adding a newvariable can change the distribution of other variables; indeed for relationalundirected models (in particular Markov logic networks), it has been provedthat it is impossible to add a new variable without changing the distributionover the existing variables except in trivial cases [17]. A learning model thatis based on a query language (e.g. one with relational algebra foundations)can easily capture multiple inference patterns jointly, a challenge underlinedby Abboud et al. [3] who state that “capturing multiple inference patternsjointly is significantly more challenging [than capturing them singly].” Thisis true of languages that include constraints, but not of query languages.Relational algebra. Relational algebra is a formalization of queries anddefines relations (views) at the core of relational databases. It consists ofseveral primitive operations that can be combined to synthesize all otheroperations used. The primitive operations are renaming, projection, selec-tion, set union, set difference, and Cartesian product. Each such operationtakes relations as input and returns a relation as output. Renaming changesthe order of the entities in a relation. Projection takes a relation and somepositions as input and returns a new relation with the entities in specificpositions removed from each tuple. Selection returns a subset of tuples fora relation that satisfies a given condition. Set union takes as input two rela-tions of the same arity and returns a new relation containing the tuples thatappear in at least one of the relations. Set difference also gets two relationsof the same arity as input and returns a new relation containing tuples fromthe first relation that do not appear in the second relation. Cartesian producttakes two relations and returns a relation in which the tuples are the con-catenation of the tuples of the input relations. One non-primitive operationis join, which is a Cartesian product followed by selection and projection;selecting the elements in the Cartesian product with matching values on cor-responding attributes, and projecting onto the different attributes. Another504.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEdrewmike sam tvsam mike tvalexbuyeralex? sam tv? bookbuyer?sambookFigure 4.4: An example of a knowledge hypergraph. Train set con-tains sold(drew , alex , book), buyer(alex , book), sold(mike, sam, tv), andbought(sam,mike, tv). Relation bought can be obtained by applying a re-naming operation to relation sold . Similarly, relation buyer is a projectionof relation sold . Learning these relational algebra operations can help themodel generalize to the tuples in the test set. The test responses, from topto bottom, are drew , tv , and mike.non-primitive operation is set intersection, which can be defined in terms ofset union and set difference.Relational Algebra in Knowledge Hypergraphs. In a knowledgehypergraph, the relational algebra operations can describe how relationsdepend on each other. To illustrate the connection between relational al-gebra operations and relations in knowledge hypergraphs, consider the ex-ample in Figure 4.4 that shows tuples from a train and test splits of aknowledge hypergraph. The train set contains tuples sold(drew , alex , book),buyer(alex , book), sold(mike, sam, tv), and bought(sam,mike, tv). The rela-tions in the example feature the two primitive relational algebra operationsrenaming and projection. Relation bought is a renaming of sold . Relationbuyer is a projection of relation sold . If a model is able to represent these twooperations, it can potentially learn at train time that a tuple bought(X ,Y , I )(person X bought from person Y item I ) is implied by tuple sold(Y ,X , I )(person Y sold to person X item I ); or that a tuple buyer(X , I ) (personX is the buyer of item I ) is implied by the tuple sold(Y ,X , I ). An em-bedding model that cannot represent the operations renaming and projectionwould not be able to learn that relation bought in Figure 4.4 is a renam-514.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEing of relation sold . It would thus be difficult for such a model to reasonabout the relationship between these two relations. In contrast, a modelthat can represent renaming and projection operations is potentially able todetermine that bought(alex , drew , book) is true because the train set con-tains sold(drew , alex , book) and bought is a renaming of sold , buyer(sam, tv)is true because the train set contains sold(mike, sam, tv) and buyer is a pro-jection of sold , and sold(mike, sam, tv) is true because the train set containsbought(sam,mike, tv) and sold is a renaming of bought .Designing reasoning methods that can capture the relational semantics interms of relational algebra is especially important in the context of knowl-edge hypergraphs, where relations can be defined on an arbitrary number ofentities. Domains with beyond-binary relations provide multiple methods ofexpressing the same underlying notion, as seen in the above example whererelations sold and bought encode the same information. Since all relations ina knowledge graph are binary (have arity 2), many of the relational algebraoperations (such as projection, which change the arity of the relation; forinstance, buyer with arity 2 is a projection of sold with arity 3), are notapplicable to this setting. This also highlights the importance of knowledgehypergraphs as a data model that encodes rich relational structures ripe forfurther exploration.The main contributions of this section are summarized as follows.• We introduce ReAlE, an embedding-based method for knowledge hy-pergraph completion that can provably represent the relational algebraoperations renaming, projection, set union, selection, and set difference,• A framework for generating synthetic knowledge hypergraphs, whichis based on the Erdo˝s-Re´nyi random graph generation model and cangenerate relations by repeated application of primitive relational alge-bra operations.• Experimental results that show that ReAlE outperforms or is compa-rable to the state-of-the-art on well-known public datasets, and thesynthesized dataset.4.3.1 Related WorkExisting work for knowledge hypergraph completion can be grouped intothe following categories.524.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEStatistical relational learning. Models under the umbrella of statisti-cal relational learning [116] can handle variable arity relations and explicitlymodel the inter-dependencies of relations. Our work is complementary tothese approaches in that ReAlE is an embedding-based model that repre-sents relational algebra operations implicitly, rather than representing themexplicitly.Translational models. Translational models for knowledge hypergraphsare extensions of approaches for binary relations and have restrictions onthe types of relations they can model (see Section 4.3.3). One of the earliestmodels in this category is m-TransH [153], which extends TransH [151] toknowledge hypergraph embedding. RAE [168] extends m-TransH by addingthe relatedness of values – the likelihood that two values co-participate in acommon instance – to the loss function. NaLP [51] uses a similar strategyto RAE, but models the relatedness of values based on the roles they playin different tuples. Models in this category have restrictions on the typesof relations they can model (see Section 4.3.3). Liu et al. [97] discuss theselimitations, and we address them more formally in Section 4.3.3. Morerecently, Abboud et al. [3] proposed a fully expressive translational modelbased on box embedding [91].Tensor factorization models. Models in this category extend tensorfactorization models for knowledge graph completion to knowledge hyper-graph completion. GETD [97] extends Tucker [7] to n-ary relations. Thememory complexity of GETD grows exponentially with the arity of relations.HypE [40] which is motivated by SimplE [76] disentangles the embeddings ofrelations from the positions of its arguments and thus the memory complex-ity grows linearly with the arity of the relations. HypE is fully expressivebut cannot represent relational algebra operations (See Section 4.3.3).Key-value pair based models. Galkin et al. [48], Guan et al. [52], andRosso et al. [121] assume that a tuple is composed of a triple (binary rela-tion), plus a list of attributes in the form of key-value pairs. This problemis slightly different as we consider all information as part of one tuple. Theyevaluate their models on datasets for which they obtain the tuple attributesfrom external data sources using heuristics and thus their results are notcomparable to ours.534.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEGraph neural network models. These approaches extend graph neuralnetworks to hypergraph neural networks [44, 156]. G-MPNN [155] furtherextends these models to knowledge hypergraphs (directed and labeled hy-peredges). G-MPNN utilizes message passing in knowledge hypergraphs butthe scoring function assumes relations are symmetric, and thus has restric-tions in modeling the non-symmetric relations and is not fully expressive.Rule capturing models. The closest work to ours is BoxE [3], which isable to represent a subset of first-order logic rules and is also a translationalmodel. ReAlE differs from BoxE in two ways. First, theoretical analysisof BoxE only concerns binary relations, while we capture inference patternsfor relations defined on any number of entities; some of the relational alge-bra relations (e.g, projection) do not make sense with only binary relations.Second, we analyze the theoretical aspects of the proposed model in termsof relational algebra, a query language in which a relation is defined in termsof others without affecting other relations. In contrast, first-order logic rulesin BoxE are a mixture of constraints (mutual exclusion and anti-symmetry)and rules that imply what else must be true (e.g., symmetry and intersec-tion). Capturing multiple patterns from first-order logic does not necessarilyprovide evidence for the rest of the first-order logic. Capturing the primitiveoperations of relational algebra is important as all other operations are com-posed of multiple primitive operations. We compare our model empiricallywith BoxE in Section 4.3.7.Proposed method. Reasoning in hypergraphs is a relatively underex-plored area that has recently gained more attention. Knowledge hypergraphsare isomorphic to relational databases and relational algebra is the calculusof queries in relational models. In this work, we design a model based onrelational algebra operations. Besides the theoretical contributions, we showempirically how basing our model on relational algebra operations gives usimprovements compared to existing work.4.3.2 ReAlE: A Basic Embedding AlgorithmReAlE (Relational Algebra Embedding) is a knowledge hypergraph com-pletion model that has parameters θ and a scoring function φθ. We mo-tivate our model bottom-up by first describing an intuitive model for thistask (Equation 4.6); we then discuss why this formulation does not workwell and adjust it in ReAlE (Equation 4.7). Given a tuple r(x1, . . . , xn),544.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEr(x1,...,xn)|r|. . . . . . 0 nw-1. . . . . . r[1][0]xi[0] xi[1] xi[w-1] xi[d-1]r[1][w-1]r[1][1] r[1][d-1]Figure 4.5: A schematic of the entity and relation embeddings in ReAlE:the embedding dimension d is divided into nw windows of size w .determining whether it is true or false depends on the relation and the en-tities involved; it also depends on the position of each entity in the tuple,as the role of an entity changes with its position and relation. For ex-ample, the role of alex is different in the tuples sold(drew , alex , book) andsold(alex , drew , book) as its position is different. The role of alex is alsodifferent in the tuples sold(drew , alex , book) and bought(drew , alex , book) asthe relation is different.An intuitive model to decide whether a tuple is true or not is one thatembeds each entity xi ∈ E into a vector x i ∈ [0, 1]d of length d , and therelation r into a matrix R ∈ R|r |×d , where the i th row in R operates over theentity at position i . Each relation r has a learnable bias term br as a partof the relation embedding as a relation-dependent constant that does notdepend on any entities and allows the model. Such a model defines the fol-lowing scoring function, where σ is a nonlinear function that is differentiablealmost everywhere.φ◦θ(r(x1, . . . , xn)) = σ(br +|r |∑i=1d−1∑k=0x i [k ]× R[i ][k ]) (4.6)Instead of performing a single version of the above scoring function,we found it beneficial to consider multiple versions of the scoring functionand use the output of all of the functions to obtain the final predictiveperformance. Scores from multiple versions of Equation 4.6 are summed toproduce the final score for the input tuple. The idea of using an ensembleof models [32] allows each of the scoring functions to focus on a different554.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEaspect of the problem. This is similar to ideas for having multiple heads inself-attention layers [142].Here, we introduce the concept of windows, a range of indices wherebyelements within the same window are used in one scoring function. Thenumber of embedding elements for each entity in a window, the window size,is a hyperparameter (see Figure 4.5). Let w denote the window size, nw =b dw c the number of windows, and bjr the learnable bias term of relation r forthe j th window, for all j = 0, . . . ,nw −1. Equation 4.7 defines ReAlE’s scoreof a tuple r(x1, x2, . . . , xn), where σ is a monotonically-increasing nonlinearfunction that is differentiable almost everywhere.φθ(r(x1, . . . , xn)) =nw−1∑j=0σ(bjr +|r |∑i=1w−1∑k=0x i [jw + k ]× R[i ][jw + k ]) (4.7)Learning ReAlE model. To learn a ReAlE, we follow the same precedureas for learning HSimplE and HypE as explained in Section 4.2.3. For aReAlE models with parameters θ (including relation and entity embeddings)and φθ as the function in the Equation 4.7, we minimize the cross-entropyloss defined in Section 4.2.3. Algorithm 1 shows a high-level description ofhow we train a ReAlE model.Algorithm 1: Learning ReAlEInput: Tuples τ ′train , loss function L, scoring function φθOutput: Embeddings x and r for all entities and relations in τ ′train .Initialize x and r (at random)for every batch τ ′batch of tuples in τ′train dofor tuple t in τ ′batch doGenerate negative tuples Tneg(t)for t ′ ∈ {t} ∪ Tneg(t) doCompute φθ(t′) (Equation 4.7)end forend forCompute the loss L(θ, τ ′batch) (Equation 4.5)Compute the gradient of the loss with respect to x and rUpdate embeddings x and r through back-propagationend for564.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlE4.3.3 Theoretical AnalysisTo better understand the expressive power of ReAlE and the types of rea-soning it can perform, we analyze the extent of its expressivity and itscapacity to represent relational algebra operations without the operationsbeing known or given to the learner. Relational algebra allows for quantifi-cation, in particular, statements that are true for all entities or statementsthat are true for at least one. To allow for such statements, we introducethe notion of variables, which, following the convention of Datalog, we writein upper case, e.g., X1, . . . ,Xn . We use lower case x1, . . . , xn to denote par-ticular entities. To make a meaningful statement, each variable is quantifiedusing ∀ (the statement is true for all assignments of entities to the variable)and ∃ (the statement is true if there exists an assignment of an entity to thevariable). Here, x¯ is a sequence of particular entities, and X¯ is a sequence ofvariables. We use ¬ as negation, ∧ as conjunction (and), and ∨ as disjunc-tion (or). In relational algebra, each relation has a unique definition andthere are no cyclic or recursive definitions.For any x¯ and any relation r , we define the relation complement functionf as f (φθ(r(x¯ ))) = φθ(¬r(x¯ )). This function depends on the choice of thenonlinearity σ of the scoring function in Equation 4.7. For example, if σ isthe Sigmoid function, then f (φθ(r(x¯ ))) = 1−φθ(r(x¯ )); if it is the hyperbolictangent (tanh), then f (φθ(r(x¯ ))) = −φθ(r(x¯ )).In this section, we state the theorems and differ all the proofs to Ap-pendix B.2 starting at Page 123.4.3.4 Full expressivityThe two results in this section state that ReAlE is fully expressive and thatsome other models are not.Theorem 4.2 (Full Expressivity) For any ground truth over entities Eand relations R containing λ true tuples with α = maxr∈R(|r |) as the max-imum arity over all relations in R, there is a ReAlE model with nw = λ,w = α, d = max(αλ, α), and σ(x ) = 11+exp(−x) that accurately separates thetrue tuples from the false ones.Theorem 4.3 m-TransH, RAE, and NaLP are not fully expressive.4.3.5 Representing Relational Algebra with ReAlEHere, we describe some primitive operations and prove how closely ReAlEcan represent each.574.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlERenamingRenaming changes the order of one or more entities in a relation. A renamingoperation can be written as the following logical rule, where t is defined interms of s and pi defines a permutation function.∀X1 . . . ∀Xn t(X1, . . . ,Xn)↔ s(Xpi(1), . . . ,Xpi(n)) (4.8)For example, ∀ X ∀ Y ∀ I bought(X ,Y , I ) ↔ sold(Y ,X , I ) representsrenaming relation (person X bought I from person Y ) into relation (personY sold I to person X ).Theorem 4.4 (Renaming) Given permutation function pi, and relation s,there exists a parametrization for relation t in ReAlE such that for entitiesx1, . . . , xn , with arbitrary embeddings,φθ(t(x1, . . . , xn)) = φθ(s(xpi(1), xpi(2), . . . , xpi(n)))ProjectionProjection takes a relation as input and removes some entities correspondingto some specific positions in the relation. A projection operation that definest as a projection of s can be written as the following (for m < n).∀X1 . . . ∀Xm t(X1, . . . ,Xm) ↔ ∃Xm+1 . . . ∃Xn s(X1, . . . ,Xm , . . . ,Xn)(4.9)Note that projection can be paired with renaming to allow for arbitrarysubsets and ordering of arguments. For example, ∀X ∀I seller(X , I ) ↔∃P bought(P ,X , I ).Theorem 4.5 (Projection) For any relation s on n arguments there existsa parametrization for relation t on m < n arguments in ReAlE such thatfor any arbitrary sequence x1, . . . , xnφθ(t(x1, . . . , xm)) ≥ φθ(s(x1, . . . , xn))Inequality is the best we can hope for because multiple tuples with re-lation s might project to the same tuple with relation t . The score of thetuple with relation t should thus be greater than or equal to the maximumscore for s.584.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlESelectionSelection returns the subset of tuples of a relation that satisfies a given con-dition. Here, we consider equality conditions whereby a selection operationreduces the number of arguments, and has two forms defining t as a selectionof s.∀X1 . . . ∀Xn t(X1, . . . ,Xp−1,Xp+1, . . . ,Xq , . . . ,Xn)↔ ∃Xp s(X1, . . . ,Xn) ∧ (Xp = Xq) (4.10)∀X1 . . . ∀Xn t(X1, . . . ,Xp−1,Xp+1, . . . ,Xn)↔ ∃Xp s(X1, . . . ,Xn) ∧ (Xp = c) for fixed c (4.11)For example, ∀X ∀Y sold coffee(X ,Y ) ↔ ∃I sold(X ,Y , I ) ∧ (I = coffee).Observe that selecting tuples with the condition Xp = Xq for arbitrary pand q is equivalent to first renaming the tuple so that Xp is in position n andXq is in position n − 1; and then performing a selection with the conditionXn−1 = Xn or Xn = c. Thus, we show the selection operation for the casewhen Xn−1 = Xn and Xn = c.Theorem 4.6 (Selection 1) For arbitrary relation s, there exists a parametriza-tion for relation t in ReAlE such that for arbitrary entities x1, . . . , xnφθ(t(x1, . . . , xn−1)) = φθ(s(x1, . . . , xn−1, xn−1)) (4.12)Theorem 4.7 (Selection 2) For arbitrary relation s and for a fixed con-stant c, there exists a parametrization for relation t in ReAlE such that forarbitrary entities x1, . . . , xnφθ(t(x1, . . . , xn−1)) = φθ(s(x1, . . . , xn−1, c))Set unionSet union operates on relations of the same arity, and returns a new relationcontaining the tuples that appear in at least one of the relations. A set unionoperation can be written as the following logical rule, with relation t as theunion of s and r .∀X¯ t(X¯ )↔ s(X¯ ) ∨ r(X¯ ) (4.13)594.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEFor instance, relation traded is defined as a set union of relations sold andbought in the following example.∀X1 ∀X2 ∀I traded(X1,X2, I )↔ sold(X1,X2, I ) ∨ bought(X1,X2, I )For a ReAlE model to be able to represent the set union operation, firstobserve that any score for a tuple t that represents the union of relations rand s depends on how dependent the two relations r and s are. For example,if s is a subset of r , then the score of t is equal to that of r . But since wedo not know about such dependence relations in the data, then a reasonablebound for the score of t is at least as high as the maximum score of eitherr or s, as the following lemma states.Theorem 4.8 (Set Union) For arbitrary relations s and r with the samearity, there exists a parametrization for relation t in ReAlE such that forarbitrary entity set x¯φθ(t(x¯ )) ≥ max(φθ(s(x¯ )), φθ(r(x¯ )))Set differenceSet difference operates on relations of the same arity, and returns a newrelation containing the tuples from the left relation that do not appear inthe right one. The set difference operation can be written as the followinglogical rule, where relation t is set difference of s and r .∀X¯ t(X¯ )← s(X¯ ) ∧ ¬r(X¯ ) (4.14)The following shows an example of a set difference.∀X ∀Y needs filter(X ,Y )← bought coffee(X ,Y ) ∧ ¬bought filter(X ,Y )Similar to set union, the score of a set difference operator depends onhow dependent the relations r and s are. For the same reasons, the best wecan hope for in this case is to show that the score of t is smaller than thatof both s and ¬r (since t(X¯ ) is true only when both s(X¯ ) and ¬r(X¯ ) aretrue, then the scores of the latter two must be higher). In the lemma thatfollows, f is the relation complement function described in the introductionof Section 4.3.3. Here, we assume that f exists for the selected σ.Theorem 4.9 (Set Difference) For arbitrary relations r and s with thesame arity, if f is a linear relation complement function and f (σ(x )) =604.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEσ(c ∗ x ) with c as a constant, there exists a parametrization for relation tin ReAlE such that for arbitrary entities x1, . . . , xnφθ(t(x¯ )) ≤ min(φθ(s(x¯ )), f (φθ(r(x¯ ))))The intuition behind the proof of Theorems 4.4 to 4.9 is to come up witha parametrization for the resulting relation t based on the relation(s) in theoperation such that the operation hold.Joint representation of operationsThe following theorems establish the ability of ReAlE to jointly capture therelational algebra operations discussed above. This is of interest, particu-larly because capturing multiple inference patterns jointly has been deemedchallenging in some existing methods [3]. In our case, the parametrizationsdo not interfere with each other, as each rule (operation) defines the relationin the head without side effects on the relations in the body.Theorem 4.10 (Composition) For an arbitrary set of relations Sr andarbitrary non-empty composition of operations Sop from the set renaming,projection, selection, set union, and set difference, there exists a parametriza-tion for relation t in ReAlE with t as the resulting relation of applying Sopto Sr .Theorem 4.11 (Joint representation) ReAlE is able to jointly representa set of relations each being either the result of a relational algebra operationrenaming, projection, selection, set difference, set union, or a composition ofthese operations.4.3.6 DatasetsReal-world Datasets.We use three the real-world datasets introduced in Section 4.2.4 for ourexperiments: jf17k [153], and fb-auto and m-fb15k [40].Synthetic DatasetTo study and evaluate the generalization power of models in a controlledenvironment, we generate a synthetic dataset. This practice has becomecommon in recent years, with the creation of several procedurally gen-erated benchmarks to study the generalization power of models in differ-ent tasks. Examples of such datasets include CLEVR [72] for images and614.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlETextWorld [28] for text data, and GraphLog [131] for graph data. To createa benchmark for analyzing the relational algebraic generalization power ofReAlE for hypergraph completion, we consider the following criteria. (1)Completeness: The benchmarks must contain the desired relational algebraoperations; in our case: renaming, projection, selection, set union, and setdifference, (2) Diversity : The benchmark must contain a variety of relationsthat are the result of repeated application of relational algebra operationshaving varying depths, (3) Compositional generalization: The benchmarkmust contain relations that are the result of repeated application of oper-ations of different types. To synthesize a dataset that satisfies the aboveconditions, we extend the Erdo˝s-Re´nyi model [36] for generating randomgraphs to directed edge-labeled hypergraphs. We use this hypergraph gen-eration model to first generate a given number of true tuples; we then applythe five relational algebra operations to these tuples (repeatedly and recur-sively) to obtain new tuples with varying depths. In what follows, we discussthe details of our dataset generation algorithm.Knowledge Hypergraphs. A knowledge hypergraph is a directed hyper-graph H = (V ,E ,R) with nodes (entities) V , edges (tuples) E , and edgelabels (relations) R such that:• every edge in the hypergraph consists of an ordered sequence of nodes,• every edge has a label ri ∈ R, and• edges with the same label are defined on the same number of nodes.Observe that in knowledge hypergraphs, edges having the same labelform a uniform directed hypergraph (all edges defined on the same numberof nodes). We can thus think of H as the combination of |R| directed uniformhypergraphs.Extending Erdo˝s-Re´nyi to Knowledge Hypergraphs. In the Erdo˝s-Re´nyi model, all graphs with a fixed number of nodes and edges are equallylikely. Equivalently, in such a random graph, each edge is present in thegraph with a fixed probability p, independent of other edges. In this section,we describe a method of generating a random knowledge hypergraph inspiredby the Erdo˝s-Re´nyi process.Let n be the (predefined) number of nodes in the hypergraph and nr bethe number of relations. We let R be a list of relations defined in terms of624.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEarity and a probability that influences the number of tuples generated forthat given relation. More formally,R = {(ki , pi)|ki = arity , 0 ≤ pi ≤ 1,∀i = 0, . . . ,nr}The expected number of edges generated for a given relation ri is mi =ki !(nki)pi . As the process of including edges in the graph is a Binomial, wecan compute this expected value by sampling from the following probabilitydensity.P(mi) =(Nmi)pi(1− pi)N−miwhere N = ki !(nki)is the number of possible ki -uniform (directed) edges inthe hypergraph.The running time of Algorithm 2 depends on the number of nodes n andthe arity ki of each relation. Let k = maxki∈Rki . Thus the running time ofAlgorithm 2 is O(|R|nk ).Algorithm 2: generate knowledge hypergraph(V , R)edge list = []n = len(V )for r , (k , p) in enumerate(R) doN = k !(nk)m = random.binomial(N , p) {result of flipping a coin N times withprobability of success p}edge count = 0while edge count <= m doedge = random.sample(V , k) {select k vertices from V at random}if edge not in edge list thenedge list.append([r ] + edge)edge count = edge count + 1end ifend whileend forreturn edge listDataset Generation. To evaluate a model on how well it represents re-lational algebra operations, we generate a set of ground-truth true tuples,each of which is the result of repeated application of a primary relationalalgebra operation to an existing tuple (hyperedge). The operations we areinterested in are renaming, projection, selection, set union and set difference.634.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEAlgorithm 3: generate ground truth(V , R, n derived tuples)E = generate knowledge hypergraph(V , R)for i in range(n derived tuples) doop = randomly select one primary operationtuple = randomly select one hyperedge from Eapply op to tupleadd tuple to the set of edges Eend forFinally, the complete algorithm to generate the train, valid, and test setsof the synthetic dataset is described in Algorithm 4 below.Algorithm 4: synthesize dataset(V , R, n derived tuples)ground truth = generate ground truth(V , R,n derived tuples)relational data = sub-sample from ground truthtrain, valid, test = randomly split relational data into train, valid andtest4.3.7 ExperimentsWe organize our experiments into three groups with different objectives.The goal of the first set of experiments is to evaluate the proposed methodon real datasets and compare its performance to that of existing work. Oursecond goal is to test the ability of ReAlE to represent the relational algebraoperations. The final set of experiments is an ablation study that examinesthe effect of window size.Results on Real DatasetsWe evaluate ReAlE on the three public datasets jf17k, fb-auto, and m-fb15k and compare its performance to existing models. On fb-auto andm-fb15k, ReAlE outperforms all existing models. These results are encour-aging considering that m-fb15k is the largest of all three datasets. ReAlEis comparable to BoxE on jf17k. Results are summarized in Table 4.7.Overall, ReAlE is competitive on all benchmarks and is state-of-the-art onfb-auto and m-fb15k.644.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlETable 4.7: Knowledge hypergraph completion results on jf17k, fb-autoand m-fb15k for baselines and the proposed method. Our method ReAlEoutperforms (or is competitive to) the baselines on all datasets. The higheris better for all columns. To measure the stability of ReAlE, we ran it onjf17k 10 times with the best hyperparameters and the standard deviationof mrr is 0.0004. This shows that ReAlE is not sensitive to different runs(different random seeds)jf17k fb-auto m-fb15kModel mrr hit@1 hit@3 hit@10 mrr hit@1 hit@3 hit@10 mrr hit@1 hit@3 hit@10m-DistMult [40] .463 .372 .510 .634 .784 .745 .815 .845 .705 .633 .740 .844m-CP [40] .392 .303 .441 .560 .752 .704 .785 .837 .680 .605 .715 .828m-TransH [153] .444 .370 .475 .581 .728 .727 .728 .728 .623 .531 .669 .809RAE [168] .310 .219 .334 .504 - - - - - - - -NaLP [51] .366 .290 .391 .516 - - - - - - - -GETD [97] .151 .104 .151 .258 .367 .254 .422 .601 - - - -HSimplE [40] .472 .378 .520 .645 .798 .766 .821 .855 .730 .664 .763 .859HypE [40] .494 .408 .538 .656 .804 .774 .823 .856 .777 .725 .800 .881G-MPNN [155] .501 .425 .537 .660 - - - - .779 .732 .805 .894BoxE [3] .553 .467 .596 .711 .844 .814 .863 .898 .761 .702 .791 .877ReAlE (Ours) .559 .482 .594 .705 .873 .852 .886 .909 .801 .755 .823 .901Results on Synthetic DatasetsTo evaluate our model in a controlled environment, we create a syntheticdataset whose statistics (e.g., number of entities, number of relations, num-ber of tuples per relation) are proportional to that of jf17k. We call thissynthetic dataset rel-er. We break down the performance of our modelbased on the type of relational algebra operation and its depth. As a firststep of the synthetic dataset generation, we create a list of tuples at ran-dom. The relations involved in these tuples are called elementary relations,as they are not generated based on any relational algebra operation. Wethen create a set of tuples that are based on composite relations: relationsthat are built from previously defined elementary and composite relations.We let the type of a composite relation be the last operation applied. Wedecompose our results by type in Table 4.8.Note that the choice of the last operation for defining the type does notchange the overall performance of the model; it merely helps us break downthe performance to gain insight. As there is no obvious way of defining thetype of a composite relation, we experimented with letting it be determinedby the first, last, or all operations; our experiments showed little variationbetween the results.654.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlETable 4.8: Breakdown performance of mrr across composite relations (basedon a sequence of primitive operations) and of varying depths on the rel-erdataset along with their statistics. The higher is better.Operation type DepthModel All elementary renaming project set union set difference 1 2 3 4m-TransH [153] .387 .166 .447 .652 .459 .464 .531 .499 .352 .03HypE [40] .689 .335 .877 .856 .888 .894 .881 .872 .897 .976BoxE [3] .695 .327 .916 .852 .900 .918 .885 .904 .908 .976ReAlE (Ours) .709 .336 .882 .877 .932 .923 .887 .950 .945 .938#test tuples 5378 1833 458 762 1676 649 2075 1204 245 21We define the depth of a relation recursively. An elementary relation hasa depth of 0. A relation that is the result of a unary operation (e.g., projec-tion or renaming) has a depth of one plus the depth of the input relation. Fora relation that is the result of a binary operation (e.g., set union or set differ-ence), the depth is one plus the maximum depth of the input relations. Theresults of our experiments on rel-er are summarized in Table 4.8 and showthat our proposed model outperforms the state-of-the-art in almost all cases.As the decomposed performance shows, the improvement to the general re-sult is due mostly to improvements in the performance of the operations aswell as improvements for elementary relations. These results confirm thatour theoretical findings are in line with the practical results. We do not havetuples for the selection operation in the test set because, by nature, selectiongenerates very few tuples; and as the split of train/test/validation in rel-eris done at random, the chance of having selection tuples in the test set isvery low and did not occur when we synthesized the dataset (selection tuplesare still present in the train data).Ablation Study on Varying Number of WindowsHere, we compare the performance of ReAlE with different numbers of win-dows nw . The negative ratio, batch size, and embedding dimension are fixedto 10, 128, and 200 respectively for this experiment. Here, the total num-ber of parameters for each value of nw is fixed. The outcome of the studyis summarized in Figure 4.6. Number of windows nw of 1 is the same asEquation 4.6. Increasing nw means having more models in the ensemblelearner. As we increase the number of learners, the performance (MRR) onthe test set increases and it plateaus when having a large number of win-dows. This result confirms the importance of having multiple learners as664.3. Knowledge Hypergraph Completion with Relational Algebra: ReAlEFigure 4.6: MRR of ReAlE for different number of windows nw on jf17kwith fixed values for negative ratio, batch size, and embedding dimensionof 10, 128, and 200 respectively. The total number of parameters for eachvalue of nw is fixed.an ensemble model. Therefore, window size or the number of windows is asensitive hyperparameter that needs to be tuned for the best performance.ReAlE with a fixed negative ratio and batch sizeThe results reported in Table 4.7 were obtained by running experimentsusing the BoxE setup: the negative ratio and batch size were tuned for eachmodel. Here, we follow the setup used by all other baselines to report theirresults and run experiments by fixing the negative ratio to 10 and batch sizeto 128. We summarize the results for the baselines and ReAlE in Table 4.9.ReAlE (Small) refers to a ReAlE model that has a negative ratio of 10 anda batch size of 128 (called Small because it has a smaller negative ratio andbath size compared to the best set of hyperparameters).Results of ReAlE with different non-linear functionsFollowing the last experiment with a fixed negative ratio and batch size, wetried different non-linear functions (σ). The results of the different nonlinearfunctions are in Table 4.10. As sigmoid is the winner for jf17k, we onlyexperiment with sigmoid for the remaining datasets.Do the learned embeddings follow the theoretical findings?Our theoretical analysis shows that ReAlE is able to represent a large subsetof relational algebra operations. Here, we further investigate whether, inpractice, the embeddings learned by ReAlE follow the theoretical results.674.4. Conclusion and LimitationsWe thus first look at the relations in rel-er that are the result of therenaming operation and observe the embeddings that ReAlE generates foreach. If relation t is a renaming of relation s, one possible parametrizationfor the embedding of t is the one proposed in the proof of Theorem 4.4.Analysing multiple examples of relations t representing renaming of s inrel-er, we observe that in all cases, the embedding of relations t is theclosest to the parametrization proposed in the proof compared to all otherrelation embeddings. We did the same analysis with the rest of the opera-tions (and their respective theorems), and the same holds for all. The resultsin Table 4.8 show the breakdown performance for each operation: furtherevidence for learnability of the operations in ReAlE.4.3.8 ConclusionIn this section, we introduce ReAlE for reasoning in knowledge hypergraphs.To design a powerful method, we build on the primitives of relational alge-bra, which is the calculus of relational models. We prove that ReAlE canrepresent the primitive relational algebra operations renaming, projection,selection, set union, and set difference, and is fully expressive. The resultsof our experiments on real and synthetic datasets are consistent with thetheoretical findings.4.4 Conclusion and LimitationsIn this chapter, we study the problem of knowledge hypergraph completion.We show that converting knowledge hypergraphs to knowledge graphs andusing knowledge graph embedding-based models is not effective. We pro-pose real and synthetic datasets, baselines, evaluation metrics, and models(HSimplE, HypE, and ReAlE) for knowledge hypergraph completion. De-spite being effective, the proposed models can only take one single entity ineach position in a tuple. However, in some applications, a position shouldcontain a set of entities. Another limitation of the proposed models is thatthey can only predict one entity at a time in a tuple. We need to extendthese models to be able to predict multiple missing entities in a tuple.684.4. Conclusion and LimitationsTable 4.9: Knowledge hypergraph completion results on jf17k, fb-autoand m-fb15k for baselines and the proposed method for a fixed embeddingdimension of 200, negative ratio of 10, and batch size of 128. Our methodReAlE (Small) outperforms the baselines on all datasets with these settings.jf17k fb-auto m-fb15kModel mrr hit@1 hit@3 hit@10 mrr hit@1 hit@3 hit@10 mrr hit@1 hit@3 hit@10m-DistMult [40] .463 .372 .510 .634 .784 .745 .815 .845 .705 .633 .740 .844m-CP [40] .392 .303 .441 .560 .752 .704 .785 .837 .680 .605 .715 .828m-TransH [153] .444 .370 .475 .581 .728 .727 .728 .728 .623 .531 .669 .809GETD [97] .151 .104 .151 .258 .367 .254 .422 .601 - - - -HSimplE [40] .472 .378 .520 .645 .798 .766 .821 .855 .730 .664 .763 .859HypE [40] .494 .408 .538 .656 .804 .774 .823 .856 .777 .725 .800 .881G-MPNN [155] .501 .425 .537 .660 - - - - .779 .732 .805 .894ReAlE (Small) .530 .454 .563 .677 .861 .836 .877 .908 .801 .755 .823 .901Table 4.10: Knowledge hypergraph completion results for ReAlE on jf17kfor different σ (nonlinear function).jf17kModel mrr hit@1 hit@3 hit@10ReAlE (σ as exponent) (Ours) 0.394 0.311 0.428 0.548ReAlE (σ as tanh) (Ours) 0.512 0.430 0.548 0.667ReAlE (σ as sigmoid) (Ours) 0.530 0.454 0.563 0.67769Chapter 5Implicit GraphsThe results presented in this chapter have been published in Fatemi et al.[41].Having introduced novel architectures for explicitly graph-structureddata in Chapters 3 and 4 of this thesis, Chapter 5 investigates how modelswith relational inductive biases - in particular graph neural networks - canbe developed and applied to problems with implicit or hidden graph struc-tures. Graph neural networks require a graph structure in the input but insome applications, there is no graph structure of nodes readily available. Insuch applications, there are node features available in the input, but thereis no graph structure of nodes readily available. However, the assumptionis that there is a latent structure connecting the nodes. If we can infer thelatent structure, we will be able to use models such as graph neural networksand that can improve the accuracy of prediction tasks.5.1 IntroductionThe problem of learning with implicit graph structures arises in many real-world applications. For instance, when predicting whether the stock of dif-ferent companies will arise or fall, we might not have access to the graphstructure that tells us how different companies are related. However, expe-rience has shown that when the stock of one company changes, the stocks ofthe other related companies also change [43]. We assume that this change isbecause of a latent structure connecting different companies. The aim hereis to learn the latent structure to help us improve the accuracy of the task.Graph representation learning has grown rapidly and found applicationsin domains where a natural graph of the data points (i.e., explicit graphstructure) is available [20, 78]. Graph neural networks (GNNs) [125] (seeSection 2.4 for a detailed description) have been a key component in theresearch in this area.Node classification in a graph is defined as when we have an explicitgraph structure with a set of nodes and edges and each node is accom-panied by a set of features (or we can use feature extraction techniques705.1. Introductionto collect features for nodes). The goal of node classification is to predictlabels (classes) for the nodes. In the semi-supervised node classificationsetup, a small number of nodes are labeled and a large number of nodes areunlabeled during training. GNNs have shown promising results for semi-supervised node classification when the available graph structure exhibits ahigh degree of homophily (i.e., connected nodes often belong to the sameclass) [172].We study the applicability of GNNs to (semi-supervised) classificationproblems where a graph structure is not readily available. The existing ap-proaches for (semi-supervised) classification (see Section 5.2 for a detaileddiscussion of the related work) with a hidden structure often take one of thefollowing approaches. 1. Similarity graph: these approaches select a similar-ity metric and set the edge weight between two nodes to be their similarity.2. Latent graph learning: these approaches learn the GNN parameters anda graph structure simultaneously. In both approaches, one main goal is toconstruct or learn a graph structure with a high degree of homophily withrespect to the labels to aid the GNN classification. The latent graph learn-ing approach often results in higher predictive performance compared to theformer approach (see, e.g., [23, 47]).We identify a supervision starvation problem in the latent graph learn-ing approaches in which the edges between pairs of nodes that are far fromlabeled nodes receive insufficient supervision; this results in learning poorstructures away from labeled nodes and hence poor generalization. We pro-pose a solution for this problem by adopting a multi-task learning frameworkin which we supplement the classification task with a self-supervised task.The self-supervised task is based on the hypothesis that a graph structurethat is suitable for predicting the node features is also suitable for predictingthe node labels. It works by masking some input features (or adding noiseto them) and training a separate GNN aiming at updating the adjacencymatrix in such a way that it can recover the masked (or noisy) features.The task is generic and can be combined with several existing latent graphlearning approaches.In this chapter, we propose the Simultaneous Learning of Adjacencyand GNN Parameters with Self-supervision, or SLAPS, that adopts theproposed self-supervised task. We provide a comprehensive experimentalstudy on nine datasets (thirteen variations) of various sizes and from variousdomains and perform thorough analyses to show the merit of SLAPS. Ourmain contributions include:• Identifying a supervision starvation problem for latent graph learning.715.2. Related Work• Proposing a solution for the identified problem through self-supervision.• Developing SLAPS, a latent graph learning model that adopts theself-supervised solution.• Providing comprehensive experimental results showing SLAPS sub-stantially outperforms existing latent graph learning baselines fromvarious categories on various benchmarks.• Providing an implementation for latent graph learning that scales tographs with hundreds of thousands of nodes.5.2 Related WorkExisting methods that relate to this work can be grouped into the followingcategories (see Zhu et al. [176] for a full survey).Fully connected graph. One approach for inferring a graph structure isto start with a fully connected graph and assign edge weights using the avail-able meta-data or employ the GNN variants that provide weights for eachedge via an attention mechanism [143, 165]. This approach has been usedin computer vision [e.g., 136], natural language processing [e.g., 171], andfew-shot learning [e.g., 49]. The space complexity of a fully connected graphgrows rapidly (a graph with n nodes requires n2 space for storing a fullyconnected graph) making such approaches applicable to small-sized graphs.There are studies trying to make improvements around computational andmemory efficiency of creating a fully connected graphs as in [24, 84, 148].Zhang et al. [166] propose to define local neighborhoods for each node andonly assume that these local neighborhoods are fully connected. Their ap-proach relies on an initial graph structure to define the local neighborhoods.Similarity graph. Another approach for inferring a graph structure isto select a similarity metric and set the edge weight between two nodes tobe their similarity [11, 122, 137]. To obtain a sparse structure with lessspace complexity, one may create a k-nearest neighbors (kNN) similaritygraph and connect each node to only its k most similar nodes. Anotherapproach for getting sparsity is to only connect pairs of nodes whose simi-larity surpasses some predefined threshold or do sampling on the graph. Asan example, Gidaris and Komodakis [50] create a (fixed) kNN graph usingthe cosine similarity of the node features. Wang et al. [150] extend this725.2. Related Workidea by creating a fresh graph in each layer of the GNN based on the nodeembedding similarities in that layer. Instead of choosing a single similaritymetric, Halcrow et al. [56] fuse several (potentially weak) measures of sim-ilarity. The quality of the predictions of these methods depends heavily onthe choice of the similarity metric(s).Latent graph learning. Instead of a similarity graph based on the ini-tial features, one may use a graph generator with learnable parameters.Li et al. [90] create a fully connected graph based on a bilinear similarityfunction with learnable parameters. Franceschi et al. [47] learn a Bernoullidistribution for each possible edge and graph structures are created throughsampling from these distributions. Yang et al. [159] update the input struc-ture to increase homophily based on the labels and model predictions. [23]propose an iterative approach that iterates over projecting the nodes to alatent space and constructing an adjacency matrix from the latent represen-tations multiple times. A common approach in this category is to learn aprojection of the nodes to a latent space where node similarities correspondto edge weights or edge probabilities. Wu et al. [154] project the nodes toa latent space by learning weights for each of the input features. Cosmoet al. [27], Jiang et al. [68], Qasim et al. [114] use a multi-layer perceptronfor projection. Yu et al. [163], Zhao et al. [170] use a GNN for projection;it uses the node features and an initial graph structure. Kazi et al. [79]create different graph structures in different layers by using separate GNNprojectors, where the input to the GNN projector in a layer is the projectedvalues and the generated graph structure from the previous layer. In ourexperiments, we compare with several approaches from this category.Leveraging domain knowledge. In some applications, one may leveragedomain knowledge to guide the model toward learning specific structures.For example, Johnson et al. [71] leverage abstract syntax trees and regularlanguages in learning graph structures of Python programs that aid rea-soning for downstream tasks. Jin et al. [70] guide the structure learningfor robustness to adversarial attacks through the domain knowledge thatclean adjacency matrices are often sparse and low-rank and exhibit featuresmoothness along the connected nodes. Other examples in this categoryinclude [67, 114]. In our work, we experiment with general-purpose datasetswithout access to domain knowledge.735.3. Proposed Method: SLAPSProposed method. Our model falls within the latent graph learning cat-egory. We supplement the training with a self-supervised objective to in-crease the amount of supervision in learning a structure. Our self-supervisedtask is inspired by, and similar to, the pre-training strategies for GNNs[63, 64, 69, 162, 173] (specifically, we adopt the multi-task learning frame-work of You et al. [162]), but it differs from this line of work as we useself-supervision for learning a graph structure whereas the above methodsuse it to learn better (and, in some cases, transferable) GNN parameters.5.3 Proposed Method: SLAPSSLAPS consists of four components: 1) generator, 2) adjacency processor,3) classifier, and 4) self-supervision. Figure 5.1 illustrates these components.In the next three subsections, we explain the first three components. Then,we point out a supervision starvation problem for a model based only onthese components. Then we describe the self-supervision component as asolution to the supervision starvation problem and the full SLAPS model.5.3.1 GeneratorThe generator is a function G : Rn×f → Rn×n with parameters θG whichtakes the node features X ∈ Rn×f as input and produces a matrix A˜ ∈ Rn×nas output. We consider the following two generators and leave experimentingwith more sophisticated graph generators (e.g., [92, 95, 161]) and modelswith tractable adjacency computations (e.g., [25]) as future work.Full parameterization (FP). For this generator, we have its parametersθG to be a matrix of size n × n i.e., θG ∈ Rn×n . The generator function isdefined as follows.A˜ = GFP (X ;θG) = θGThat is, the generator ignores the input node features and directly op-timizes the adjacency matrix. FP is similar to the generator in [47] exceptthat they treat each element of A˜ as the parameter of a Bernoulli distribu-tion and sample graph structures from these distributions. FP is simple andflexible for learning any adjacency matrix but adds n2 parameters whichlimits scalability and makes the model susceptible to overfitting.745.3. Proposed Method: SLAPSNode featuresGenerator1.0 -0.2 0.40 1.0 ... 0.5...0 0.5 1.0GNNCNon-symmetric, non-normalized adjacencySymmetric, normalized adjacencyDenoised featuresAdjacency Processor0.3 0 0.10 0.2 ... 0.2...0.1 0.2 0.3GNNDAENoisy FeaturesAdd NoiseFigure 5.1: Overview of SLAPS. At the top, a generator receives the nodefeatures and produces a non-symmetric, non-normalized adjacency having(possibly) both positive and negative values (Section 5.3.1). The adjacencyprocessor makes the values positive, symmetrizes, and normalizes the ad-jacency (Section 5.3.2). The resulting adjacency and the node features gointo GNNC which predicts the node classes (Section 5.3.3). At the bottom,some noise is added to the node features. The resulting noisy features andthe generated adjacency go into GNNDAE which then denoises the features(Section 5.3.5).MLP-kNN. This generator has a multi-layer perceptron (MLP) followedby a k-nearest neighbors (kNN). The MLP takes the node features X asinput and produces a matrix with updated node representations X ′ as out-put. The MLP is defined as the function MLP : Rn×f → Rn×f ′ . To obtaina sparse structure, we apply a kNN function to the output of the MLP. Wecreate a kNN similarity graph by connecting each node to only its k mostsimilar nodes. The kNN function is defined as kNN : Rn×f ′ → Rn×n . Pa-rameters of this generator, θG, correspond to the weights of a multi-layerperceptron (MLP). Using this generator, A˜ is defined as follows.A˜ = GMLP(X ;θG) = kNN(MLP(X ;θG))Initialization and variants of MLP-kNN. Let AkNN represent an ad-jacency matrix created by applying a kNN function on the initial node fea-tures X . One smart initialization for θG is to initialize it in a way that thegenerator initially generates AkNN (i.e., A˜ = AkNN before training starts).This can be trivially done for the FP generator by initializing its parametersθG to AkNN . For MLP-kNN, we consider two variants. For both variants,we have the following properties.755.3. Proposed Method: SLAPS• We keep the input dimension the same throughout the layers i.e.,f = f ′.• We initialize the weight matrices θG with the identity matrix to ensurethat the output of the MLP is initially the same as its input and thekNN graph created on the output is equivalent to AkNN (Alternatively,one may use other MLP variants but pre-train the weights to outputAkNN before the main training starts).The only difference between the two variants is that in one variant,hereafter referred to as MLP-D, we consider MLPs with diagonal weightmatrices i.e., except the main diagonal, all other parameters in the weightmatrices are zero. However, in the other variant, hereafter referred to simplyas MLP, the weight matrices can be arbitrary. MLP-D can be thought ofas assigning different weights to different features and then computing nodesimilarities.Back-propagation through the kNN operation. To back-propagatethrough the kNN operation, we followed the straight-thorugh estimator pro-posed by Bengio et al. [12]. This strategy only flows gradients toward non-zero values in the output of a hard threshold function which is a kNN inour method. As discussed by Bengio et al. [12], this estimator is biased, butit works well because it enforces a prior that for a given input, most of thefactors in the model are irrelevant and would be represented by zeros in therepresentation. Bengio et al. [12] also investigated multiplying the gradientby the derivative of the sigmoid, but they found that better results wereobtained without multiplying the derivative of the sigmoid.5.3.2 Adjacency ProcessorThe output of the generator A˜ may have both positive and negative valuesand may be non-symmetric and non-normalized. We let µ be a functionwith a non-negative range applied element-wise on its input. µ(A˜) maps theoutput of the generator to non-negative values. The expression 12(µ(A˜) +µ(A˜)T ) makes the resulting matrix µ(A˜) symmetric. To understand thereason for taking the mean of µ(A˜) and µ(A˜)T , assume A˜ is generated byGMLP. If vj is among the k most similar nodes to vi and vice versa, then thestrength of the connection between vi and vj will remain the same. However,if, say, vj is among the k most similar nodes to vi but vi is not among the top765.3. Proposed Method: SLAPSk for vj , then taking the average of the similarities reduces the strength of theconnection between vi and vj . Finally, once we have a symmetric adjacencywith non-negative values, we normalize 12(µ(A˜) + µ(A˜)T ) by computing itsdegree matrix D and multiplying it from left and right to D−12 . This is thesame normalization as introduced in Equation 2.2 for symmetric matrices.We let A be defined as follows.A =12D−12 (µ(A˜) + µ(A˜)T )D−12In our experiments, when using an MLP generator, we let µ be theReLU [102] function applied element-wise on the elements of A˜. Whenusing the fully-parameterized (FP) generator, applying ReLU results in agradient flow problem as any edge whose corresponding value in A˜ becomesless than or equal to zero stops receiving gradient updates. For this reason,for FP we apply the ELU [26] function to the elements of A˜ and then adda value of 1.5.3.3 ClassifierThe classifier is a function GNNC : Rn×f ×Rn×n → Rn×|C| with parametersθGNNC . It takes the node features X and the normalized adjacency A as in-put and provides for each node the probability for each class. n correspondsto the number of nodes, C corresponds to the classes, and |C| corresponds tothe number of classes. We use a two-layer GCN (a GCN layer is defined inEquation 2.3) followed by a softmax function in the classifier. A two-layerGCN has parameters θGNNC = {W (1),W (2)}. The classifier predicts labelsYˆ for nodes as:Yˆ = GNNC(A,X ;θGNNC) = softmax(AReLU(AX W(1))W (2)) (5.1)where the softmax function is applied row-wise and is defined assoftmax(H [i ][j ]) =exp(H [i ][j ])∑c∈C exp(H [i ][c]).Let YL be the set of labeled node indices and Y ∈ Rn×|C| be a binarymatrix indicating labels of the nodes. If node i is labeled (i.e., i ∈ YL), Y [i ]is a one-hot encoding of the label for the node (Y [i ] is a vector with onlyone value of 1 indicating the label for the node and the rest of the valuesare zeros). If node i is not labeled (i.e., i /∈ YL), then Y [i ] is a vectorof zeros (Y [i ] for i /∈ YL does not affect the loss function). The following775.3. Proposed Method: SLAPSUnlabelledStarved edgeUnlabelled LabelledLabelledUnlabelledUnlabelledFigure 5.2: Using a two-layer GCN, the predictions made for the labelednodes are not affected by the dashed (starved) edge.equation shows the classification loss based on cross-entropy error over alllabeled examples for the node classification task.LC = −∑i∈YL∑Cc=1 Y [i ][c]× log(Yˆ [i ][c])|YL| (5.2)5.3.4 Using only the first three components leads tosupervision starvationOne may create a model using only the three components described so farcorresponding to the top part of Figure 5.1. As we will explain here, how-ever, this model may suffer severely from supervision starvation. The sameproblem also applies to many existing approaches for latent graph learn-ing, as they can be formulated as a combination of variants of these threecomponents.Consider a scenario during training where two unlabeled nodes vi and vjare not directly connected to any labeled nodes according to the generatedstructure. Then, since a two-layer GCN makes predictions for the nodesbased on their two-hop neighbors, the classification loss (i.e., LC ) is not af-fected by the edge between vi and vj and this edge receives no supervision1.Figure 5.2 provides an example of such a scenario. Let us call the edges thatdo not affect the loss function LC (and consequently do not receive supervi-sion) as starved edges. These edges are problematic because although theymay not affect the training loss, the predictions at the test time depend onthese edges and if their values are learned without enough supervision, themodel may make poor predictions at test. A natural question concerning1While using more layers may relatively alleviate this problem, deeper GCNs typicallyproduce inferior results, e.g., due to oversmoothing [89, 108] – see Section 5.5.5 (Paragraph“Increasing the number of layers”) for empirical evidence.785.3. Proposed Method: SLAPSthe extent of the problem caused by such edges is the proportion of starvededges. The following theorem formally establishes the extent of the prob-lem for Erdo˝s-Re´nyi graphs [36]; in Appendix C.1, we extend this result tothe Baraba´si–Albert model [4] and scale-free networks [9]. An Erdo˝s-Re´nyigraph with n nodes and m edges is a graph chosen uniformly at randomfrom the collection of all graphs which have n nodes and m edges.Theorem 5.1 Let G(n,m) be an Erdo˝s-Re´nyi graph with n nodes and medges. Assume we have labels for q nodes selected uniformly at random. Theprobability of an edge being a starved edge with a two-layer GCN is equal tothe following:(1− qn)(1− qn − 1)2q∏i=1(1− m − 1(n2)− i )We defer the proof to Appendix C.1. To put the numbers from thetheorem in perspective, let us consider three established benchmarks forsemi-supervised node classification namely cora, citeseer, and pubmed.For an Erdo˝s-Re´nyi graph with similar statistics as the cora dataset (n =2708, m = 5429, q = 140), the probability of an edge being a starved edgeis 59.4% according to the above theorem. For citeseer and pubmed, thisnumber is 75.7% and 96.7% respectively. While Theorem 5.1 is stated forErdo˝s-Re´nyi graphs, the identified problem also applies to natural graphs.For the original structures of cora, citeseer, and pubmed, for example,48.8%, 65.2%, and 91.6% of the edges are starved edges.5.3.5 Self-supervisionOne possible solution to the supervision starvation problem is to define aprior graph structure and regularize the learned structure toward it. Thisleads the starved edges toward the prior structure as opposed to neglectingthem. The choice of the prior is important as it determines the inductivebias incorporated into the model. We define a prior structure based on thefollowing hypothesis:Hypothesis 1 A graph structure that is suitable for predicting the nodefeatures is also suitable for predicting the node labels.We first explain why the above hypothesis is reasonable for an extreme casethat is easy to understand and then extend the explanation to the generalcase. Consider an extreme scenario where one of the node features is thesame as the node labels. A graph structure that is suitable for predicting795.3. Proposed Method: SLAPSthis feature exhibits homophily for it. Because of the equivalence betweenthis feature and the labels, the graph structure also exhibits homophily forthe labels, so it is also suitable for predicting the labels. In the general (non-extreme) case, there may not be a single feature that is equivalent to thelabels but a subset of the features may be highly predictive of the labels. Agraph structure that is suitable for predicting this subset exhibits homophilyfor the features in the subset. Because this subset is highly predictive of thelabels, the structure also exhibits a high degree of homophily for the labels,so it is also suitable for predicting the node labels.Next, we explain how to design a suitable graph structure for predictingthe features and how to regularize toward it. One could design such a struc-ture manually (e.g., by handcrafting a graph that connects nodes based onthe collective homophily between their individual features) and then penalizethe difference between this prior graph and the learned graph. Alternatively,in this section, we take a learning-based approach based on self-supervisionwhere we not only use the learned graph structure for the classification task,but also for denoising the node features. The self-supervised task encour-ages the model to learn a structure that is suitable for predicting the nodefeatures.Our self-supervised task is based on denoising autoencoders [144]. LetGNNDAE : Rn×f ×Rn×n → Rn×f be a GNN with parameters θGNNDAE thattakes node features and a generated adjacency as input and provides updatednode features with the same dimension as output. We train GNNDAE suchthat it receives a noisy version X˜ of the features X as input and produces thedenoised features X as output. Let idx represent the indices correspondingto the elements of X to which we have added noise, and X idx represent thevalues at these indices. During training, we minimize:LDAE = L(X idx ,GNNDAE(X˜ ,A;θGNNDAE)idx ) (5.3)where A is the generated adjacency matrix and L is a loss function. Here,idx is defined with one of the following options.• For datasets where the features consist of binary vectors, idx consistsof r percent of the indices of X whose values are 1 and rη percent ofthe indices whose values are 0, both selected uniformly at random ineach epoch. Both r and η (corresponding to the negative ratio) arehyperparameters. In this case, we add noise by setting the 1s in theselected mask to 0s and L is the binary cross-entropy loss.• For datasets where the input features are continuous numbers, idxconsists of r percent of the indices of X selected uniformly at random805.3. Proposed Method: SLAPSin each epoch. We add noise by either replacing the values at idx with0 or by adding independent Gaussian noises to each of the features.In this case, L is the mean-squared error loss.Note that the self-supervised task in Equation 5.3 is generic and canbe added to different GNNs as well as latent graph learning models. Itcan be also combined with other techniques in the literature that encouragelearning more homophilous structures or increase the amount of supervision.In our experiments, we test the combination of our self-supervised task (andkNN-GCN) with two techniques from the literature namely self-training [89]and AdaEdge [21]. These two techniques are explained below.Self-training. Self-training helps the model “see” more labeled nodes. Forself-training, we first train a model using the existing labels in the trainingset. Then, we use this model to make predictions for the unlabeled nodesthat were not in the train, validation, or test sets. We consider the labelpredictions for the top ζ most confident unlabeled nodes as ground truthlabels and add them to the training labels. Finally, we train a model fromscratch on the expanded set of labels. Here, ζ is a hyperparameter tunedusing the dev set.AdaEdge. AdaEdge helps iteratively create graph structure with higherdegrees of homophily. For AdaEdge, in the case of kNN-GCN, we first traina kNN-GCN model. Then we change the structure of the graph from thekNN graph to a new graph by following these steps: 1) add edges betweennodes with the same class predictions if both prediction confidences surpassa threshold, 2) remove edges between nodes with different class predictionsif both prediction confidences surpass a threshold. Then, we train a GCNmodel on the new structure and repeat the steps above to generate a newstructure. We do this iteratively until a new structure does not provide aboost in performance on the validation set. For SLAPS, we follow a similarapproach except that the initial model was a SLAPS model instead of akNN-GCN model.5.3.6 SLAPSOur final model is trained to minimize the weighted sum of the classifica-tion loss LC (defined in Equation 5.2) and the denoising autoencoder lossLDAE (defined in Equation 5.3) as follows.L = LC + λLDAE815.4. Experimental SetupHere, λ is a hyperparameter controlling the relative importance of the twolosses.5.4 Experimental SetupIn this section, we report the baselines and the datasets used in our exper-iments. We defer the implementation details and the best hyperparametersettings for our model on all the datasets to Appendix C.2.5.4.1 BaselinesWe compare our proposal to several baselines with different properties. Thefirst baseline is a multi-layer perceptron (MLP) which does not take thegraph structure into account. We also compare against MLP-GAM* [134]which learns a fully connected graph structure and uses this structure tosupplement the loss function of the MLP toward predicting similar labels forneighboring nodes. Our third baseline is label propagation (LP) [174], a well-known model for semi-supervised learning. Similar to [47], we also considera baseline named kNN-GCN where we create a kNN graph based on thenode feature similarities and feed this graph to a GCN; the graph structureremains fixed in this approach. We also compare with prominent existinglatent graph learning models including LDS [47], GRCN [163], DGCNN[150], and IDGL [23]. In [23], another variant named IDGL-ANCH is alsoproposed that reduces time complexity through anchor-based approximation[96]. We compare against the base IDGL model because it does not sacrificeaccuracy for time complexity, and because anchor-based approximation ismodel-agnostic and could be combined with other models too. We feeda kNN graph to the models requiring an initial graph structure. We alsoexplore how adding self-training and AdaEdge impact the performance ofkNN-GCN as well as SLAPS.5.4.2 DatasetsWe use three established benchmarks in the GNN literature namely cora,citeseer, and pubmed [127] as well as the ogbn-arxiv dataset [62] that isorders of magnitude larger than the other three datasets and is more chal-lenging due to the more realistic split of the data into train, validation, andtest sets. For these datasets, we only feed the node features to the modelsand not their original graph structure. Following Franceschi et al. [47] andChen et al. [23], we also experiment with several classification (non-graph)825.4. Experimental SetupTable 5.1: Statistics of the datasets used in the experiments.Dataset Nodes Edges Classes Features Label ratecora 2,708 5,429 7 1,433 0.052citeseer 3,327 4,732 6 3,703 0.036pubmed 19,717 44,338 3 500 0.003ogbn-arxiv 169,343 1,166,243 40 128 0.537wine 178 0 3 13 0.112cancer 569 0 2 30 0.035digits 1,797 0 10 64 0.05620news 9,607 0 10 236 0.021mnist 10,000 0 10 784 0.1, 0.2 and 0.3datasets available in scikit-learn [110] including wine, cancer, digits, and20news. Furthermore, following Jiang et al. [68], we also provide results onmnist [86].For cora and citeseer, the LDS model uses the train data for learningthe parameters of the classification GCN, half of the validation for learningthe parameters of the adjacency matrix (in their bi-level optimization setup,these are considered as hyperparameters), and the other half of the valida-tion set for early stopping and tuning the other hyperparameters. Besidesexperimenting with the original setups of these two datasets, we also con-sider a setup that is closer to that of LDS: we use the train set and half of thevalidation set for training and the other half of validation for early stoppingand hyperparameter tuning. We name the modified versions cora390 andciteseer370 respectively where the number proceeding the dataset nameshows the number of labels from which gradients are computed. We followa similar procedure for the scikit-learn datasets.Jiang et al. [68] show that learning a latent graph structure of the inputexamples can help with semi-supervised image classification. In particu-lar, they create three versions of the mnist dataset each consisting of arandomly selected subset with 10,000 examples in total. The first versioncontains 1000, the second contains 2000, and the third version contains 3000labeled examples for training. All three variants use an extra 1000 labelsfor validation. The other examples are used as test examples.The statistics of the datasets used in the experiments can be found in Ta-ble 5.1.835.5. ExperimentsTable 5.2: Results of SLAPS and the baselines on established node clas-sification benchmarks presenting accuracy. † indicates results have beentaken from Franceschi et al. [47]. ‡ indicates results have been taken fromStretcu et al. [134]. Bold and underlined values indicate the best and thesecond-best mean performances respectively. OOM indicates out of mem-ory. OOT indicates out of time (we allowed 24h for each run). NA indicatesnot applicable. Appendix C.2 provides implementation details of SLAPSand baselines.Model cora citeseer cora390 citeseer370 pubmed ogbn-arxivMLP 56.1± 1.6† 56.7± 1.7† 65.8± 0.4 67.1± 0.5 71.4± 0.0 54.7± 0.1MLP-GAM* 70.7‡ 70.3‡ − − 71.9‡ −LP 37.6± 0.0 23.2± 0.0 36.2± 0.0 29.1± 0.0 41.3± 0.0 OOMkNN-GCN 66.5± 0.4† 68.3± 1.3† 72.5± 0.5 71.8± 0.8 70.4± 0.4 49.1± 0.3LDS − − 71.5± 0.8† 71.5± 1.1† OOM OOMGRCN 67.4± 0.3 67.3± 0.8 71.3± 0.9 70.9± 0.7 67.3± 0.3 OOMDGCNN 56.5± 1.2 55.1± 1.4 67.3± 0.7 66.6± 0.8 70.1± 1.3 OOMIDGL 70.9± 0.6 68.2± 0.6 73.4± 0.5 72.7± 0.4 72.3± 0.4 OOMkNN-GCN + AdaEdge 67.7± 1.0 68.8± 1.0 72.2± 0.4 71.8± 0.6 OOT OOTkNN-GCN + self-training 67.3± 0.3 69.8± 1.0 71.1± 0.3 72.4± 0.2 72.7± 0.1 NASLAPS (FP) 72.4± 0.4 70.7± 0.4 76.6± 0.4 73.1± 0.6 OOM OOMSLAPS (MLP) 72.8± 0.8 70.5± 1.1 75.3± 1.0 73.0± 0.9 74.4± 0.6 56.6± 0.1SLAPS (MLP-D) 73.4± 0.3 72.6± 0.6 75.1± 0.5 73.9± 0.4 73.1± 0.7 52.9± 0.1SLAPS (MLP) + AdaEdge 72.8± 0.7 70.6± 1.5 75.2± 0.6 72.6± 1.4 OOT OOTSLAPS (MLP) + self-training 74.2± 0.5 73.1± 1.0 75.5± 0.7 73.3± 0.6 74.3± 1.4 NA5.5 ExperimentsIn this section, we report the key experiments and their results. The exper-iments in this section investigate the following questions:• Q1. How effective is the proposed method? We answer this by com-paring SLAPS to the state-of-the-art and obvious baselines.• Q2. What is the effect of self-supervision in SLAPS? Does self-supervision help the supervision starvation problem?• Q3. What if instead of no graph structure, we have a noisy graph inthe input with added and removed edges?• Q4. How is the quality of the learned adjacency by SLAPS? Is thegraph homophilous?• Q5. What is the effect of k in k-nearest neighbors (kNN) and thenumber of layers of GCN in SLAPS?845.5. ExperimentsSection 5.5.1 provides a comprehensive experimental study on 9 datasetswith 13 variations of various sizes and from various domains (Q1). Sec-tion 5.5.2 investigates the effectiveness of self-supervision in SLAPS (Q2).Section 5.5.3 verifies whether self-supervision is helpful when a noisy struc-ture is provided as input (Q3). Section 5.5.4 analyzes the learned adjacencyby SLAPS and investigates the quality of the adjacency (Q4). Finally, Sec-tion 5.5.5 provides ablation studies for SLAPS on different values for k inkNN and also experiments with deeper GCNs (Q5). More experimentalanalyses are presented in Appendix C.3.5.5.1 Comparative ResultsThe results of SLAPS and the baselines on our benchmarks are reportedin Tables 5.2 and 5.3. We start by analyzing the results in Table 5.2 first.Starting with the baselines, we see that learning a fully connected graphin MLP-GAM* makes it outperform MLP. kNN-GCN significantly outper-forms MLP on cora and citeseer but underperforms on pubmed andogbn-arxiv. Furthermore, both self-training and AdaEdge improve theperformance of kNN-GCN. This shows the importance of the similarity met-ric and the graph structure that is fed into GCN; a low-quality structurecan harm model performance. LDS outperforms MLP but the fully pa-rameterized adjacency matrix of LDS results in memory issues for pubmedand ogbn-arxiv. As for GRCN, it was shown in the original paper thatGRCN can revise a good initial adjacency matrix and provide a substantialboost in performance. However, as evidenced by the results, if the initialgraph structure is somewhat poor, GRCN’s performance becomes on parwith kNN-GCN. IDGL is the best performing baseline.In addition to the aforementioned baselines, we also experimented withGCN, GAT, and Transformer (encoder only) architectures applied on fullyconnected graphs. GCN always learned to predict the majority class. Thisis because, after one fully connected GCN layer, all nodes will have the sameembedding and become indistinguishable. GAT also showed similar behav-ior. We believe this is because the attention weights are (almost) random atthe beginning (due to random initialization of the model parameters) result-ing in nodes becoming indistinguishable and GAT cannot escape from thatstate. The skip connections of Transformer helped avoid the problem ob-served for GCN and GAT and we were able to achieve better results (∼ 40%accuracy on cora). However, we observed severe overfitting (even with verysmall models and with high dropout probabilities).SLAPS consistently outperforms the baselines in some cases by large855.5. ExperimentsTable 5.3: Results on classification datasets presenting accuracy. † indicatesresults have been taken from Franceschi et al. [47]. Bold and underlinedvalues indicate best and the second-best mean performances respectively.Model wine cancer digits 20newsMLP 96.1± 1.0 95.3± 0.9 81.9± 1.0 30.4± 0.1kNN-GCN 93.5± 0.7 95.3± 0.4 95.4± 0.4 46.3± 0.3LDS 97.3± 0.4† 94.4± 1.9† 92.5± 0.7† 46.4± 1.6†IDGL 97.0± 0.7 94.2± 2.3 92.5± 1.3 48.5± 0.6SLAPS (FP) 96.6± 0.4 94.6± 0.3 94.4± 0.7 44.4± 0.8SLAPS (MLP) 96.3± 1.0 96.0± 0.8 92.5± 0.7 50.4± 0.7SLAPS (MLP-D) 96.5± 0.8 96.6± 0.2 94.2± 0.1 49.8± 0.9margins. Among the generators, the winner is dataset-dependent with MLP-D mostly outperforming MLP on datasets with many features and MLPoutperforming on datasets with small numbers of features. Using the soft-ware that was publicly released by the authors, the baselines that learna graph structure fail on ogbn-arxiv2; our implementation, on the otherhand, scales to such large graphs. Adding self-training helps further improvethe results of SLAPS. Adding AdaEdge, however, does not seem effective,probably because the graph structure learned by SLAPS already exhibits ahigh degree of homophily (see Section 5.5.4).In Table 5.3, we only compared SLAPS with the best performing base-lines from Table 5.2 (kNN-GCN, LDS and IDGL). We also included an MLPbaseline for comparison. On three out of four datasets, SLAPS outperformsthe LDS and IDGL baselines. For the digits dataset, interestingly kNN-GCN outperforms the learning-based models. This could be because theinitial kNN structure for this dataset is already a good structure. Amongthe datasets on which we can train SLAPS with the FP generator, 20newshas the largest number of nodes (9,607 nodes). In this dataset, we observedthat an FP generator suffers from overfitting and produces weaker resultscompared to other generators due to its large number of parameters.Following Jiang et al. [68], we also conduct experiments on the threevariants of the mnist dataset to measure the performance of SLAPS. Wecompare against GLCN [68] as well as the baselines in the GLCN paperincluding manifold regularization [11], label propagation, deep walk [112],2We note that IDGL-ANCH also scales to ogbn-arxiv.865.5. ExperimentsTable 5.4: Classification accuracy results on the mnist dataset with lowlabel rates as proposed by Jiang et al. [68]. Bold values indicate best meanperformances. Underlined values indicate second best mean performance.All the results for baseline have been taken from [68].Model mnist 1000 mnist 2000 mnist 3000ManiReg 92.74± 0.3 93.96± 0.2 94.62± 0.2LP 79.28± 0.9 81.91± 0.8 83.45± 0.5DeepWalk 94.55± 0.3 95.04± 0.3 95.34± 0.3GCN 90.59± 0.3 90.91± 0.2 91.01± 0.2GAT 92.11± 0.4 92.64± 0.3 92.81± 0.3GLCN 94.28± 0.3 95.09± 0.2 95.46± 0.2SLAPS 94.66± 0.2 95.35± 0.1 95.54± 0.0graph convolutional networks (GCN), and graph attention networks (GAT).The results are reported in Table 5.4. From the results, it can be viewed thatSLAPS outperforms GLCN and all the other baselines on the 3 variants.Compared to GLCN, on the three variants SLAPS reduces the error by7%, 5%, and 2% respectively, showing that SLAPS can be more effectivewhen the labeled set is small and providing more empirical evidence forTheorem 5.1.5.5.2 The Effectiveness of Self-supervisionThis section investigates the effectiveness of self-supervision in SLAPS.Learning a structure only using self-supervision. To provide moreinsight into the value provided by the self-supervision task and the general-izability of the adjacency learned through this task, we conduct experimentswith a variant of SLAPS named SLAPS2s that is trained in two stages. Wefirst train the GNNDAE model by minimizing LDAE described in in Equa-tion 5.3. Recall that LDAE depends on the parameters θG of the generatorand the parameters θGNNDAE of the denoising autoencoder. After every tepochs of training, we fix the adjacency matrix, train a classifier with thefixed adjacency matrix, and measure classification accuracy on the valida-tion set. We select the epoch that produces the adjacency providing the bestvalidation accuracy for the classifier. Note that in SLAPS2s , the adjacencymatrix only receives gradients from the self-supervised task in Equation 5.3.875.5. ExperimentsFP MLP MLP-D64666870727476Accuracy72.4 72.873.472.169.370.9kNN-GCNSLAPSSLAPS-2sFigure 5.3: Comparing SLAPS, SLAPS2s and kNN-GCN on cora with dif-ferent generators. Although SLAPS2s does not use the node labels in learn-ing an adjacency matrix, it outperforms kNN-GCN. SLAPS outperformingSLAPS2s indicates that learning the adjacency using both self-supervisionand the task-specific node labels results in higher predictive accuracy.Figure 5.3 shows the performance of SLAPS and SLAPS2s on cora andcompares them with kNN-GCN. Although SLAPS2s does not use the nodelabels in learning an adjacency matrix, it outperforms kNN-GCN (8.4% im-provement when using an FP generator). With an FP generator, SLAPS2seven achieves competitive performance with SLAPS; this is mainly becauseFP does not leverage the supervision provided by GCNC toward learn-ing generalizable patterns that can be used for nodes other than those inthe training set. These results corroborate the effectiveness of the self-supervision task for learning an adjacency matrix. Besides, the results showthat learning the adjacency using both self-supervision and the task-specificnode labels results in higher predictive accuracy.The value of λ. Figure 5.4 shows the performance of SLAPS3 on coraand citeseer with different values of λ (λ is a hyperparameter controllingthe importance of the self-supervised task). When λ = 0, correspondingto removing self-supervision, the model performance is somewhat poor. Assoon as λ becomes positive, both models see a large boost in performanceshowing that self-supervision is crucial to the high performance of SLAPS.Increasing λ further provides larger boosts until it becomes so large that theself-supervision loss dominates the classification loss and the performance3The generator used in this experiment is MLP; other generators produced similarresults.885.5. Experiments0.0 0.1 1.0 10.0 100.06667686970717273AccuracyCoraCiteseerFigure 5.4: The performance of SLAPS with MLP graph generator as afunction of λ. SLAPS with λ = 0 corresponds to removing self-supervision.The results indicate that with removing self-supervision, the model perfor-mance is somewhat poor. As soon as λ becomes positive, both models seea large boost in performance showing that self-supervision is crucial to thehigh performance of SLAPS.deteriorates. Note that with λ = 0, SLAPS with the MLP generator becomesa variant of the model proposed by Cosmo et al. [27], but with a differentsimilarity function.Is self-supervision actually solving the supervision starvation prob-lem? In Figure 5.4, we showed that self-supervision is key to the highperformance of SLAPS. Here, we examine if this is because self-supervisionindeed addresses the supervision starvation problem. For this purpose, wecompared SLAPS with and without self-supervision on two groups of testnodes on cora: 1) those that are not connected to any labeled nodes aftertraining, and 2) those that are connected to at least one labeled node af-ter training. The nodes in group one have a high chance of having starvededges. We observed that adding self-supervision provides 38.0% improve-ment for the first group and only 8.9% improvement for the latter. Sinceself-supervision mainly helps with nodes in group 1, this provides evidencethat self-supervision is an effective solution to the supervision starvationproblem.The effect of the training set size. According to Theorem 5.1, a smallerq (corresponding to the training set size) results in more starved edges in895.5. Experimentseach epoch. To explore the effect of self-supervision as a function of q ,we compared SLAPS with and without supervision on cora and citeseerwhile reducing the number of labeled nodes per class from 20 to 5. Weused the FP generator for this experiment. With 5 labeled nodes per class,adding self-supervision provides 16.7% and 22.0% improvements on coraand citeseer respectively, which is substantially higher than the corre-sponding numbers when using 20 labeled nodes per class (10.0% and 7.0%respectively). This provides empirical evidence for Theorem 5.1. Note thatthe results on cora390 and citeseer370 datasets provide evidence thatthe self-supervised task is effective even when the label rate is high.5.5.3 Experiments with Noisy GraphsThe performance of GNNs highly depends on the quality of the input graphstructure and deteriorates when the graph structure is noisy [see e.g., 29,46, 177]. So far, we have investigated the effectiveness of SLAPS whenno graph structure is available in the input. Here, we verify whether self-supervision is also helpful when a noisy structure is provided as input. To-ward this goal, we experiment with cora and citeseer and provide noisyversions of the input graph as input. The provided noisy graph structureis used only for initialization; it is then further optimized by SLAPS. Weperturb the graph structure by removing ρ percent of the edges in the orig-inal structure (selected uniformly at random). We calculate the number ofremoved edges and add the same number of edges to the graph with ran-dom weights. Figure 5.5 shows the performance of SLAPS with and withoutself-supervision (λ = 0 corresponds to no supervision). We also report theresults of vanilla GCN on these perturbed graphs for comparison. It can beviewed that self-supervision consistently provides a boost in performance,especially for higher values of ρ.5.5.4 Analyses of the Learned AdjacencyIn this section, we analyze the learned adjacency by SLAPS in two ways.First, we experiment with a noisy graph to investigate whether SLAPS canrecover the original graph. Second, we measure the homophily in the graphlearned by SLAPS.Noisy graphs. Following the experiment in Section 5.5.3, we comparedthe learned and original structures by measuring the number of random905.5. ExperimentsCora=25%Cora=50%Citeseer=25%Citeseer=50%45505560657075AccuracySLAPSSLAPS ( =0)GCNFigure 5.5: Performance comparison when noisy graphs are provided asinput (ρ indicates the percentage of perturbations). The results indicatethat self-supervision consistently provides a boost in performance, especiallyfor higher values of ρedges added during perturbation but removed by the model and the num-ber of edges removed during the perturbation but recovered by the model.For cora, SLAPS removed 76.2% and 70.4% of the noisy edges and re-covered 58.3% and 44.5% of the removed edges for ρ = 25% and ρ = 50%respectively while SLAPS with λ = 0 only removed 62.8% and 54.9% ofthe noisy edges and recovered 51.4% and 35.8% of the removed edges. Thisprovides evidence on self-supervision being helpful for structure learning.Homophily. As discussed, a properly learned graph for semi-supervisedclassification with GNNs exhibits high homophily. To verify the quality ofthe learned adjacency with respect to homophily, for every pair of nodes inthe test set, we compute the odds of the two nodes sharing the same label asa function of the normalized weight of the edge connecting them. Figure 5.6represents the odds for different weight intervals (recall that A is row andcolumn normalized). For both cora and citeseer, nodes’ connected withhigher edge weights are more likely to share the same label compared tonodes with lower or zero edge weights. Specifically, when Aij ≥ 0.1, vi andvj are almost 2.5 and 2.0 times more likely to share the same label on coraand citeseer respectively. This shows that the learned edge weights arehighly predictive of the same classness.915.5. Experiments[0.0, 0.0](0.0, 0.01)[0.01, 0.03)[0.03, 0.05)[0.05, 0.08)[0.08, 0.1)[0.1,inf)Edge weight interval0.51.01.52.02.5OddsCoraCiteseerFigure 5.6: The odds of two nodes in the test set sharing the same labelas a function of the edge weights learned by SLAPS. For both cora andciteseer, nodes that are connected with higher edge weights are more likelyto share the same label compared to nodes with lower or zero edge weights.This shows that the learned edge weights are highly predictive of the sameclassness.5.5.5 Ablation StudiesImportance of k in kNN. Figure 5.7 shows the performance of SLAPSon cora for three graph generators as a function of k in kNN. For all threecases, the value of k plays a major role in model performance. The FPgenerator is the least sensitive because, in FP, k only affects the initializa-tion of the adjacency matrix but then the model can change the numberof neighbors of each node. For MLP and MLP-D, however, the number ofneighbors of each node remains close to k (but not necessarily equal as theadjacency processor can add or remove some edges) and the two generatorsbecome more sensitive to k . For larger values of k , the extra flexibility ofthe MLP generator enables removing some of the unwanted edges throughthe function µ or reducing the weights of the unwanted edges resulting inMLP being less sensitive to large values of k compared to MLP-D.Increasing the number of layers. In Section 5.3.4, we described howsome edges may receive no supervision during latent graph learning. Wepointed out that while increasing the number of layers of the GCN may al-leviate the problem to some extent, deeper GCNs typically provide inferior925.6. Limitations100 101 102k57.560.062.565.067.570.072.5AccuracyFPMLPMLP-DFigure 5.7: The performance of SLAPS on cora as a function of k in kNN.The results show that the value of k plays a major role in model performance.results due to issues such as oversmoothing [see, e.g., 89, 108]. We empir-ically tested deeper GCNs for latent graph learning to see if simply usingmore layers can obviate the need for the proposed self-supervision. Specifi-cally, we tested SLAPS without self-supervision (i.e., λ = 0) with 2, 4, and6 layers on cora. We also added residual connections that have been shownto help train deeper GCNs [88]. The accuracies for 2, 4, and 6-layer modelsare 66.2%, 67.1%, and 55.8% respectively. It can be viewed that increasingthe number of layers from 2 to 4 provides an improvement. This mightbe because the benefit provided by a 4-layer model in terms of alleviatingthe starved edge problem outweighs the increase in oversmoothing. How-ever, when the number of layers increases to 6, the oversmoothing problemoutweighs and the performance drops significantly. Further increasing thenumber of layers resulted in even lower accuracies.5.6 LimitationsIn this section, we discuss some of the limitations of the proposed model.Firstly, in cases where nodes do not have input features but an initial noisystructure of the nodes is available, our self-supervised task cannot be readilyapplied. One possible solution is to first run an unsupervised node embed-ding model such as DeepWalk [112] to obtain node embeddings, then treatthese embeddings as node features and run SLAPS. Secondly, the FP graph935.7. Conclusiongenerator is only applicable to the transductive setting (can only be used fora single fixed graph). This is because FP directly optimizes the adjacencymatrix. However, our other two graph generators (MLP and MLP-D) canbe applied in the inductive setting where the graph is not fixed (e.g., inevolving graphs).5.7 ConclusionWe proposed SLAPS: a model for learning the parameters of a graph neuralnetwork and a graph structure of the nodes’ connectivities simultaneouslyfrom data. We identified a supervision starvation problem that emerges forgraph structure learning, especially when training data is scarce. We pro-posed a solution to the supervision starvation problem by supplementing thetraining objective with a self-supervised task. We showed the effectivenessof our model through a comprehensive set of experiments and analyses.94Chapter 6Conclusion and Future WorkIn the first part of this thesis, we investigated how we can exploit explicitstructures of graphs when making a prediction. In such cases, the data isin the form of entities with relations among the entities given. For suchstructures, in Chapter 3, we propose a novel model for learning embeddingsfor entities and relations such that they obey taxonomies. We showed howenforcing given subsumptions can lead to better performance for link predic-tion in knowledge graphs. In Chapter 4, we further investigated the knowl-edge hypergraph completion problem. We introduced datasets, baselines,novel methods, and metrics for link prediction in knowledge hypergraphs.We study the connections between knowledge hypergraphs and relationalalgebra and show how introducing a model based on relational algebra op-erations can give us improvement on benchmarks.In Chapter 5, we extended the applicability of graph learning to appli-cations where the assumption is that there is a latent structure between theentities but that is not given to us. For such implicit structures, we pro-pose a model to learn the parameters of a prediction model and the latentstructure simultaneously from the data. We identified a supervision starva-tion problem in existing models and proposed a solution to the supervisionstarvation based on self-supervision.This work opens up several directions for future research. The followingprovides an overview of these directions.6.1 Future Work for Learning with ExplicitStructuresIncorporating Ontological Information. In Chapter 3, we proposed amodel that can learn embeddings for entities and relationships while enforc-ing subproperties into embeddings. One possible extension for SimplE+ is tobe able to further incorporate ontological background information and rulessuch as range information, symmetry, transitivity, domain, etc. As an ex-ample, range rules are in the form of ∀h, t ∈ E∗ : r(h, t)→ c1(t , true) which956.1. Future Work for Learning with Explicit Structuresenforces type c1 for tail of relation r , e.g., if we know Sam has a master’sdegree from UBC , we can infer that UBC is an educational institution.Relational hypergraphs for natural language processing (NLP).We studied the theory and application of knowledge hypergraphs. Onepossible direction is to use the learned ideas in knowledge hypergraphs forNLP applications. In natural language, sentences can have an arbitrarynumber of words and therefore can be modeled using relational hyperedges.Different tasks in NLP can be then mapped to their graph variant. Forinstance, a corpus of facts can be used as a knowledge hypergraph andtasks that use a corpus e.g., question answering [93] can be mapped to linkprediction in the knowledge hypergraph.Combining relational learning and set learning. Current knowledgegraph and hypergraph completion methods can handle tuples r(e1, . . . , en)with only one entity at each position k with k : 1 ≤ k ≤ n in the tuple. How-ever, there might be cases with a set of entities at some of the positions in thetuple e.g., “Alex bought potatoes, tomatoes, and bananas from Walmart”.One workaround to handle a tuple r(e1, . . . , {ek1, . . . , eki}, . . . , en) with a setof entities at position k is to convert it to a set of tuples r(e1, . . . , ek1, . . . , en),. . . , r(e1, . . . , eki , . . . , en) but this workaround loses this information thatthese set of tuples all true together. Another method to handle the tuples isto reify them to a set of tuples by adding a new entity e ′. The set of tupleswith reification will be r(e ′, e1, . . . , ek1, . . . , en), . . . , r(e ′, e1, . . . , eki , . . . , en).A future direction is to explore current methods that can convert tuples withsets in some positions to tuples with only one entity at a position and evalu-ate their performance and devise new methods if current conversion methodsfail. Ideas in learning with sets [e.g., 164] can be combined with ideas inknowledge hypergraphs to make such models applicable to a wide range ofapplications.Relational representation learning at scale. Link prediction task inknowledge hypergraphs can be defined as predicting multiple entities at thesame time as in r(e0, ?, ?). One example of this question can be “where andto whom did Justin Trudeau marry?” as in the following tuple:MarriedTo(JustinTrudeau, ?, ?)In which we need to output 2 entities corresponding to whom and locationto complete this partial tuple. One way of outputting m entities at once966.1. Future Work for Learning with Explicit Structuresthat gives the highest probability in a partial tuple is iterating throughall possible combinations of entities of which there are |E|m with |E| asthe number of entities in the knowledge hypergraph. This is not scalableto partial tuples with relations of high arities and many entities missing.Therefore, one open problem, that mainly arises in knowledge hypergraphs,is how to efficiently predict the missing entities in a given partial tuple. Tothe best of our knowledge, the only work in this line is proposed in [169],which uses indexing methods to filter entities that are not probable to appeartogether. Their proposed indexing method is based on heuristics that filterentities that never appeared in the same tuple in the train set. We plan toinvestigate a method that can learn what tuples of entities are a probableanswer to the question instead of filtering the pairs that did not appear intrain time.Incorporating negative examples. Current datasets used as bench-marks for knowledge graph completion contain only positive tuples. Toturn the link prediction problem into a classification problem with positiveand negative examples, for each positive tuple, m negative tuples are createdbased on a negative sampling strategy. The number of negative examplesgenerated per positive example introduces a bias for models in terms of theprior probability of tuples being true. Since the number m does not typ-ically reflect the true prior probability of tuples, current knowledge graphembedding methods output uncalibrated probabilities. Current embedding-based models for knowledge graph completion use a probabilistic loss suchas log-likelihood for training but the evaluation process is ranking-basedsuch as mrr and hit@k. One future direction is to create a ground truthof facts containing both positive and negative examples. This set is proba-bly difficult to construct for both train and test but it is feasible to createone as a test set. We can use such a test set for evaluating various knowl-edge graph completion methods based on probabilistic metrics instead ofranking-based methods. After comparing current models on a ground truthcontaining both positive and negative examples, one possible future workis to look further into training approaches that encourage more calibratedprobabilities.Beyond ranking. Currently, knowledge (hyper)graphs are coupled withranking-based evaluation metrics. That is, for each missing entity in thetuple, they rank the entities from the most probable to the least probableto fill the blank. However, in some applications, we are not interested in the976.2. Future Work for Learning with Implicit Structuresranking of the entities but in the probability of a tuple. For instance, weare interested to find out the probability of the tupleLocatedIn(Berlin,France),indicating the probability of city Berlin being located in France. Beingable to extend the evaluation metrics beyond ranking and use probabilisticmetrics will enable the use of knowledge (hyper)graphs for more tasks.6.2 Future Work for Learning with ImplicitStructuresImplicit relations for temporal and multi-modal data. In Chap-ter 5, we proposed learning a static graph structure from data. However,in some applications with temporal data, there are multiple graph struc-tures each associated with one timestamp. For instance, in dynamic simu-lation [82], each timestamp refers to a different graph structure that is ob-tained by adding or removing edges from the previous timestamp. Besidestemporal data, there might be other forms of data available to be exploitedfor learning a graph structure. For instance, in some applications, data isavailable across a wide range of modalities, from visual data in the form ofimages and video, natural language data in the form of text, audio data suchas sounds, as well as other forms of sensory data such as smell forms of datamight be available to be used for learning a graph structure. Being able tolearn the latent structure of the world in the presence of multi-modal datais a potential extension to the proposed model.Beyond symmetry. Most of the models developed for learning with animplicit graph use a kNN function. The kNN algorithm uses a similaritymetric to find the k-nearest neighbors for each node and most similaritymetrics are symmetric e.g., distance metrics. The adjacency matrix gener-ated by kNN is not necessarily symmetric as one node can be among the topk similar nodes of the other node but not the other way around. However,our experiments in Appendix C.3.1 shows that symmetrization of the out-put of the kNN improves the result. Our hypothesis for why symmetrizationimproves the results is that the similarity metric used in the kNN is symmet-ric and therefore symmetrization of the output is more compatible with thesimilarity metric in kNN. Models learning a symmetric graph structure canonly learn symmetric edges (edges with no direction). One future direction986.3. Combining Explicit and Implicit Graph Structuresis to use a non-symmetric similarity metric so that the edges in the graphstructure can have direction and therefore be non-symmetric.Implicit multi-relations. The latent structure learned in SLAPS is agraph with only one type of relation. However, some graphs in the world aremore complex and contain more than one type of relations e.g., knowledgegraphs often have a various number of relations. Being able to learn a graphstructure with multiple types of relations can lead to more realistic andeffective results in some applications with complex latent graphs.Interpretability. Latent graph learned with SLAPS boosts the perfor-mance compared to various baselines. However, the learned graph is notinterpretable. In some applications, interpretability [94] is of high impor-tance, and being able to study the learned graph and investigate what it haslearned is essential. Learning interpretable graphs are a future direction.6.3 Combining Explicit and Implicit GraphStructuresThe structure in some real-world applications is not completely explicit orcompletely implicit: the graph is partially given and partially latent. Allthe challenges and future directions discussed for explicit and implicit graphstructures discussed so far should be combined in one system to be able toreflect the partially given graph.99Bibliography[1] Freebase api. https://developers.google.com/freebase, 2019.[2] Wikidata. https://www.wikidata.org/wiki/Wikidata:Main_Page,2019.[3] Ralph Abboud, I˙smail I˙lkan Ceylan, Thomas Lukasiewicz, and Tom-maso Salvatori. Boxe: A box embedding model for knowledge basecompletion. In Proceedings of the Thirty-Fourth Annual Conferenceon Advances in Neural Information Processing Systems (NeurIPS),2020.[4] Re´ka Albert and Albert-La´szlo´ Baraba´si. Statistical mechanics of com-plex networks. Reviews of modern physics, 74(1):47, 2002.[5] Sercan O¨ Arik and Tomas Pfister. Tabnet: Attentive interpretabletabular learning. In Proceedings of the AAAI Conference on ArtificialIntelligence, volume 35, pages 6679–6687, 2021.[6] So¨ren Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann,Richard Cyganiak, and Zachary Ives. Dbpedia: A nucleus for a webof open data. In The semantic web, pages 722–735. Springer, 2007.[7] Ivana Balazˇevic´, Carl Allen, and Timothy M Hospedales. Tucker:Tensor factorization for knowledge graph completion. arXiv preprintarXiv:1901.09590, 2019.[8] Sudipto Banerjee and Anindya Roy. Linear algebra and matrix anal-ysis for statistics, volume 181. Crc Press Boca Raton, 2014.[9] Albert-La´szlo´ Baraba´si and Re´ka Albert. Emergence of scaling inrandom networks. science, 286(5439):509–512, 1999.[10] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti,100BibliographyDavid Raposo, Adam Santoro, Ryan Faulkner, et al. Relational in-ductive biases, deep learning, and graph networks. arXiv preprintarXiv:1806.01261, 2018.[11] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regu-larization: A geometric framework for learning from labeled and un-labeled examples. JMLRR, 7(Nov):2399–2434, 2006.[12] Yoshua Bengio, Nicholas Le´onard, and Aaron Courville. Estimatingor propagating gradients through stochastic neurons for conditionalcomputation. arXiv preprint arXiv:1308.3432, 2013.[13] Piotr Bojanowski, Edouard Grave, Armand Joulin, and TomasMikolov. Enriching word vectors with subword information. arXivpreprint arXiv:1607.04606, 2016.[14] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and JamieTaylor. Freebase: a collaboratively created graph database for struc-turing human knowledge. In ACM ICMD, 2008.[15] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason We-ston, and Oksana Yakhnenko. Translating embeddings for modelingmulti-relational data. In NIPS, 2013.[16] Antoine Bordes, Xavier Glorot, Jason Weston, and Yoshua Bengio. Asemantic matching energy function for learning with multi-relationaldata. Machine Learning, 94(2):233–259, 2014.[17] David Buchman and David Poole. Representing aggregators in rela-tional probabilistic models. In Proc. Twenty-Ninth AAAI Conferenceon Artificial Intelligence (AAAI-15), 2015.[18] Robert Burke. Knowledge-based recommender systems. encyclopediaof library and information systems. New York, NY, USA, pages 180–200, 2000.[19] Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Este-vam R Hruschka Jr, and Tom M Mitchell. Toward an architecture fornever-ending language learning. In AAAI, 2010.[20] Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Re´, andKevin Murphy. Machine learning on graphs: A model and compre-hensive taxonomy. arXiv preprint arXiv:2005.03675, 2020.101Bibliography[21] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mea-suring and relieving the over-smoothing problem for graph neural net-works from the topological view. In Proceedings of the AAAI Confer-ence on Artificial Intelligence, volume 34, pages 3438–3445, 2020.[22] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boostingsystem. In Proceedings of the 22nd acm sigkdd international conferenceon knowledge discovery and data mining, pages 785–794, 2016.[23] Yu Chen, Lingfei Wu, and Mohammed J. Zaki. Deep iterative andadaptive learning for graph neural networks. In Neural InformationProcessing Systems (NeurIPS), 2020.[24] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, XingyouSong, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis,David Belanger, Lucy Colwell, et al. Masked language modeling forproteins via linearly scalable long-context transformers. arXiv preprintarXiv:2006.03555, 2020.[25] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, XingyouSong, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, AfrozMohiuddin, Lukasz Kaiser, et al. Rethinking attention with perform-ers. arXiv preprint arXiv:2009.14794, 2020.[26] Djork-Arne´ Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fastand accurate deep network learning by exponential linear units (elus).arXiv preprint arXiv:1511.07289, 2015.[27] Luca Cosmo, Anees Kazi, Seyed-Ahmad Ahmadi, Nassir Navab, andMichael Bronstein. Latent patient network learning for automaticdiagnosis. arXiv preprint arXiv:2003.13620, 2020.[28] Marc-Alexandre Coˆte´, A´kos Ka´da´r, Xingdi Yuan, Ben Kybartas, Ta-vian Barnes, Emery Fine, James Moore, Matthew Hausknecht, LaylaEl Asri, Mahmoud Adada, et al. Textworld: A learning environmentfor text-based games. In Workshop on Computer Games, pages 41–75.Springer, 2018.[29] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, andLe Song. Adversarial attack on graph structured data. arXiv preprintarXiv:1806.02371, 2018.[30] Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. Problog: Aprobabilistic prolog and its application in link discovery. IJCAI, 2007.102Bibliography[31] Thomas Demeester, Tim Rockta¨schel, and Sebastian Riedel.Lifted rule injection for relation embeddings. arXiv preprintarXiv:1606.08359, 2016.[32] Thomas G Dietterich. Ensemble methods in machine learning. InInternational workshop on multiple classifier systems, pages 1–15.Springer, 2000.[33] Boyang Ding, Quan Wang, Bin Wang, and Li Guo. Improving knowl-edge graph embedding using simple constraints. In Proceedings of the56th Annual Meeting of the Association for Computational Linguistics,2018.[34] Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao,Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang.Knowledge vault: A web-scale approach to probabilistic knowledgefusion. In ACM SIGKDD, 2014.[35] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradientmethods for online learning and stochastic optimization. JMLR, 12(Jul):2121–2159, 2011.[36] Paul Erdo˝s and Alfred Re´nyi. On random graphs. Publicationes Math-ematicae Debrecen, 6:290–297, 1959.[37] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli.A fair comparison of graph neural networks for graph classification.arXiv preprint arXiv:1912.09893, 2019.[38] Bahare Fatemi, Seyed Mehran Kazemi, and David Poole. A learningalgorithm for relational logistic regression: Preliminary results. arXivpreprint arXiv:1606.08531, 2016.[39] Bahare Fatemi, Siamak Ravanbakhsh, and David Poole. Improvedknowledge graph embedding using background taxonomic information.In AAAI, 2019.[40] Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole.Knowledge hypergraphs: Prediction beyond binary relations. InIJCAI-20, 2020. Main track.[41] Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. Slaps:Self-supervision improves structure learning for graph neural networks.Advances in Neural Information Processing Systems, 34, 2021.103Bibliography[42] Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole.Knowledge hypergraph embedding meets relational algebra. Journalof Machine Learning Research, 24(105):1–34, 2023.[43] Fuli Feng, Xiangnan He, Xiang Wang, Cheng Luo, Yiqun Liu, and Tat-Seng Chua. Temporal relational ranking for stock prediction. ACMTransactions on Information Systems (TOIS), 37(2):1–30, 2019.[44] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao.Hypergraph neural networks. In AAAI, 2019.[45] David Ferrucci, Eric Brown, Jennifer Chu-Carroll, James Fan, DavidGondek, Aditya A Kalyanpur, Adam Lally, J William Murdock, EricNyberg, John Prager, et al. Building watson: An overview of thedeepqa project. AI magazine, 31(3):59–79, 2010.[46] James Fox and Sivasankaran Rajamanickam. How robust are graphneural networks to structural noise? arXiv preprint arXiv:1912.10206,2019.[47] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He.Learning discrete structures for graph neural networks. In ICML, 2019.[48] Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Us-beck, and Jens Lehmann. Message passing for hyper-relational knowl-edge graphs. arXiv preprint arXiv:2009.10847, 2020.[49] Victor Garcia and Joan Bruna. Few-shot learning with graph neuralnetworks. arXiv preprint arXiv:1711.04043, 2017.[50] Spyros Gidaris and Nikos Komodakis. Generating classificationweights with gnn denoising autoencoders for few-shot learning. InProceedings of the IEEE Conference on Computer Vision and PatternRecognition, pages 21–30, 2019.[51] Saiping Guan, Xiaolong Jin, Yuanzhuo Wang, and Xueqi Cheng. Linkprediction on n-ary relational data. In The World Wide Web Confer-ence, pages 583–593, 2019.[52] Saiping Guan, Xiaolong Jin, Jiafeng Guo, Yuanzhuo Wang, and XueqiCheng. Neuinfer: Knowledge inference on n-ary facts. In Proceedingsof the 58th Annual Meeting of the Association for Computational Lin-guistics, pages 6141–6151, 2020.104Bibliography[53] Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo. Jointlyembedding knowledge graphs and logical rules. In EMNLP, pages192–202, 2016.[54] Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo. Knowl-edge graph embedding with iterative guidance from soft rules. InAAAI, 2018.[55] Vı´ctor Gutie´rrez-Basulto and Steven Schockaert. From knowledgegraph embedding to ontology embedding: Region based representa-tions of relational structures. arXiv preprint arXiv:1805.10461, 2018.[56] Jonathan Halcrow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi.Grale: Designing networks for graph learning. In Proceedings of the26th ACM SIGKDD International Conference on Knowledge Discov-ery & Data Mining, pages 2523–2532, 2020.[57] William L Hamilton. Graph representation learning. Synthesis Lec-tures on Artifical Intelligence and Machine Learning, 14(3):1–159,2020.[58] William L Hamilton, Zhitao Ying, and Jure Leskovec. Inductive rep-resentation learning on large graphs. Advances in neural informationprocessing systems, 30, 2017.[59] Frank L Hitchcock. The expression of a tensor or a polyadic as a sum ofproducts. Journal of Mathematics and Physics, 6(1-4):164–189, 1927.[60] Pascal Hitzler, Markus Kro¨tzsch, Bijan Parsia, Peter F. Patel-Schneider, and Sebastian Rudolph, editors. OWL 2 Web OntologyLanguage Primer (Second Edition). W3C Recommendation 11 De-cember 2012, 2012. URL http://www.w3.org/TR/owl2-primer/.[61] Tin Kam Ho. The random subspace method for constructing decisionforests. IEEE transactions on pattern analysis and machine intelli-gence, 20(8):832–844, 1998.[62] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren,Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph bench-mark: Datasets for machine learning on graphs. Advances in neuralinformation processing systems, 33:22118–22133, 2020.105Bibliography[63] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang,Vijay Pande, and Jure Leskovec. Strategies for pre-training graphneural networks. In ICLR, 2020.[64] Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, and YizhouSun. Gpt-gnn: Generative pre-training of graph neural networks. InProceedings of the 26th ACM SIGKDD International Conference onKnowledge Discovery & Data Mining, pages 1857–1867, 2020.[65] Yuchi Huang, Qingshan Liu, and Dimitris Metaxas. Video objectsegmentation by hypergraph cut. In CVPR, 2009.[66] Yuchi Huang, Qingshan Liu, Shaoting Zhang, and Dimitris N Metaxas.Image retrieval via probabilistic hypergraph ranking. In CVPR, 2010.[67] Soobeom Jang, Seong-Eun Moon, and Jong-Seok Lee. Brain sig-nal classification via learning connectivity structure. arXiv preprintarXiv:1905.11678, 2019.[68] Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph learning-convolutional networks. InProceedings of the IEEE/CVF Conference on Computer Vision andPattern Recognition, pages 11313–11320, 2019.[69] Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang, ZitaoLiu, and Jiliang Tang. Self-supervised learning on graphs: Deep in-sights and new direction. arXiv preprint arXiv:2006.10141, 2020.[70] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jil-iang Tang. Graph structure learning for robust graph neural networks.arXiv preprint arXiv:2005.10203, 2020.[71] Daniel D Johnson, Hugo Larochelle, and Daniel Tarlow. Learninggraph structure with a finite-state automaton layer. arXiv preprintarXiv:2007.04929, 2020.[72] Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: A diagnosticdataset for compositional language and elementary visual reasoning. InProceedings of the IEEE Conference on Computer Vision and PatternRecognition, pages 2901–2910, 2017.106Bibliography[73] Armand Joulin, Edouard Grave, Piotr Bojanowski, and TomasMikolov. Bag of tricks for efficient text classification. arXiv preprintarXiv:1607.01759, 2016.[74] Seyed Mehran Kazemi and David Poole. Bridging weighted rules andgraph random walks for statistical relational models. Frontiers inRobotics and AI, 5:8, 2018.[75] Seyed Mehran Kazemi and David Poole. Relnn: A deep neural modelfor relational learning. In Proceedings of the AAAI conference on ar-tificial intelligence, volume 32, 2018.[76] Seyed Mehran Kazemi and David Poole. Simple embedding for linkprediction in knowledge graphs. In NIPS, 2018.[77] Seyed Mehran Kazemi, David Buchman, Kristian Kersting, SriraamNatarajan, and David Poole. Relational logistic regression. In KR,2014.[78] Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Ak-shay Sethi, Peter Forsyth, and Pascal Poupart. Representation learn-ing for dynamic graphs: A survey. JMLR, 2020.[79] Anees Kazi, Luca Cosmo, Nassir Navab, and Michael Bronstein. Dif-ferentiable graph module (dgm) for graph convolutional networks.arXiv preprint arXiv:2002.04999, 2020.[80] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Wei-dong Ma, Qiwei Ye, and Tie-Yan Liu. Lightgbm: A highly efficientgradient boosting decision tree. Advances in neural information pro-cessing systems, 30, 2017.[81] Diederik P Kingma and Jimmy Ba. Adam: A method for stochasticoptimization. arXiv preprint arXiv:1412.6980, 2014.[82] Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, andRichard Zemel. Neural relational inference for interacting systems.In International Conference on Machine Learning, pages 2688–2697.PMLR, 2018.[83] Thomas N. Kipf and Max Welling. Semi-supervised classification withgraph convolutional networks. In ICLR, 2017.107Bibliography[84] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: Theefficient transformer. arXiv preprint arXiv:2001.04451, 2020.[85] Ni Lao and William W Cohen. Relational retrieval using a combinationof path-constrained random walks. JML, 81(1):53–67, 2010.[86] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist hand-written digit database. ATT Labs [Online]. Available:http://yann.lecun.com/exdb/mnist, 2, 2010.[87] Daniel D Lee and H Sebastian Seung. Learning the parts of objectsby non-negative matrix factorization. Nature, 401(6755):788, 1999.[88] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deep-gcns: Can gcns go as deep as cnns? In Proceedings of the IEEE/CVFInternational Conference on Computer Vision, pages 9267–9276, 2019.[89] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graphconvolutional networks for semi-supervised learning. In AAAI, 2018.[90] Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang.Adaptive graph convolutional neural networks. arXiv preprintarXiv:1801.03226, 2018.[91] Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and AndrewMcCallum. Smoothing the geometry of probabilistic box embeddings.In International Conference on Learning Representations, 2018.[92] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash,William L Hamilton, David Duvenaud, Raquel Urtasun, and Richard SZemel. Efficient graph generation with graph recurrent attention net-works. arXiv preprint arXiv:1910.00760, 2019.[93] Bill Yuchen Lin, Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, XiangRen, and William W Cohen. Differentiable open-ended commonsensereasoning. arXiv preprint arXiv:2010.14439, 2020.[94] Zachary C Lipton. The mythos of model interpretability: In machinelearning, the concept of interpretability is both important and slippery.Queue, 16(3):31–57, 2018.[95] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky.Graph normalizing flows. In NeurIPS, pages 13556–13566, 2019.108Bibliography[96] Wei Liu, Junfeng He, and Shih-Fu Chang. Large graph constructionfor scalable semi-supervised learning. In ICML, 2010.[97] Yu Liu, Quanming Yao, and Yong Li. Generalizing tensor decomposi-tion for n-ary relational knowledge bases. In Proceedings of The WebConference 2020, pages 1104–1114, 2020.[98] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and JeffDean. Distributed representations of words and phrases and their com-positionality. In Advances in neural information processing systems,pages 3111–3119, 2013.[99] George A Miller. Wordnet: a lexical database for english. Communi-cations of the ACM, 38(11):39–41, 1995.[100] T. Mitchell, W. Cohen, E. Hruschka, P. Talukdar, J. Betteridge,A. Carlson, B. Dalvi, M. Gardner, B. Kisiel, J. Krishnamurthy, N. Lao,K. Mazaitis, T. Mohamed, N. Nakashole, E. Platanios, A. Ritter,M. Samadi, B. Settles, R. Wang, D. Wijaya, A. Gupta, X. Chen,A. Saparov, M. Greaves, and J. Welling. Never-ending learning. InAAAI, 2015.[101] Brian Murphy, Partha Talukdar, and Tom Mitchell. Learning effectiveand interpretable semantic models using non-negative sparse embed-ding. Proceedings of COLING 2012, pages 1933–1950, 2012.[102] Vinod Nair and Geoffrey E Hinton. Rectified linear units improverestricted boltzmann machines. In Icml, 2010.[103] Vinod Nair and Geoffrey E Hinton. Rectified linear units improverestricted boltzmann machines. In Icml, 2010.[104] Dat Quoc Nguyen. An overview of embedding models of entitiesand relationships for knowledge base completion. arXiv preprintarXiv:1703.08098, 2017.[105] Dat Quoc Nguyen, Kairit Sirts, Lizhen Qu, and Mark Johnson.Stranse: a novel embedding model of entities and relationships inknowledge bases. In NAACL-HLT, 2016.[106] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. Factorizingyago: scalable machine learning for linked data. In ACM WWW, 2012.109Bibliography[107] Maximilian Nickel, Kevin Murphy, Volker Tresp, and EvgeniyGabrilovich. A review of relational machine learning for knowledgegraphs. Proceedings of the IEEE, 104(1):11–33, 2016.[108] Kenta Oono and Taiji Suzuki. Graph neural networks exponentiallylose expressive power for node classification. In ICLR, 2020.[109] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Ed-ward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, LucaAntiga, and Adam Lerer. Automatic differentiation in pytorch, 2017.[110] Fabian Pedregosa, Gae¨l Varoquaux, Alexandre Gramfort, VincentMichel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Pret-tenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machinelearning in python. JMLR, 12:2825–2830, 2011.[111] Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove:Global vectors for word representation. In EMNLP, 2014.[112] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Onlinelearning of social representations. In ACM SIGKDD, 2014.[113] David L Poole and Alan K Mackworth. Artificial Intelligence: foun-dations of computational agents. Cambridge University Press, 2010.[114] Shah Rukh Qasim, Jan Kieseler, Yutaro Iiyama, and Maurizio Pierini.Learning representations of irregular particle-detector geometry withdistance-weighted graph networks. The European Physical Journal C,79(7):1–11, 2019.[115] Meng Qu, Xiang Ren, Yu Zhang, and Jiawei Han. Weakly-supervisedrelation extraction by pattern-enhanced embedding learning. In Pro-ceedings of the 2018 World Wide Web Conference, pages 1257–1266.International World Wide Web Conferences Steering Committee, 2018.[116] Luc De Raedt, Kristian Kersting, Sriraam Natarajan, and DavidPoole. Statistical relational artificial intelligence: Logic, probability,and computation. Synthesis Lectures on Artificial Intelligence andMachine Learning, 10(2):1–189, 2016.[117] Matthew Richardson and Pedro Domingos. Markov logic networks.Machine learning, 62(1-2):107–136, 2006.110Bibliography[118] Sebastian Riedel, Limin Yao, Andrew McCallum, and Benjamin MMarlin. Relation extraction with matrix factorization and universalschemas. In Proceedings of the 2013 Conference of the North AmericanChapter of ACL: Human Language Technologies, pages 74–84, 2013.[119] Tim Rockta¨schel, Matko Bosˇnjak, Sameer Singh, and SebastianRiedel. Low-dimensional embeddings of logic. In Proceedings of theACL 2014 Workshop on Semantic Parsing, pages 45–49, 2014.[120] Tim Rockta¨schel, Sameer Singh, and Sebastian Riedel. Injecting logi-cal background knowledge into embeddings for relation extraction. InProceedings of the 2015 Conference of the North American Chapterof the Association for Computational Linguistics: Human LanguageTechnologies, pages 1119–1129, 2015.[121] Paolo Rosso, Dingqi Yang, and Philippe Cudre´ Mauroux. Beyondtriplets: hyper-relational knowledge graph embedding for link predic-tion. In Proceedings of The Web Conference 2020, pages 1885–1896,2020.[122] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality re-duction by locally linear embedding. science, 290(5500):2323–2326,2000.[123] Stuart J Russell and Peter Norvig. Artificial intelligence: a modernapproach. Malaysia; Pearson Education Limited,, 2016.[124] Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski,Razvan Pascanu, Peter Battaglia, and Tim Lillicrap. A simple neuralnetwork module for relational reasoning. In NIPS, pages 4967–4976,2017.[125] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner,and Gabriele Monfardini. The graph neural network model. IEEETransactions on Neural Networks, 20(1):61–80, 2008.[126] Hanie Sedghi and Ashish Sabharwal. Knowledge completion for gener-ics using guided tensor factorization. Transactions of the Associationof Computational Linguistics, 6:197–210, 2018.[127] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, BrianGalligher, and Tina Eliassi-Rad. Collective classification in networkdata. AI magazine, 29(3):93–93, 2008.111Bibliography[128] Yoav Shoham. Why knowledge representation matters. Communica-tions of the ACM, 59(1):47–49, 2016.[129] Sameer Singh, Amarnag Subramanya, Fernando Pereira, and An-drew McCallum. Wikilinks: A large-scale cross-document coreferencecorpus labeled via links to wikipedia. University of Massachusetts,Amherst, Tech. Rep. UM-CS-2012, 15, 2012.[130] Amit Singhal. Introducing the knowledge graph: things, not strings,2012.[131] Koustuv Sinha, Shagun Sodhani, Joelle Pineau, and William L Hamil-ton. Evaluating logical generalization in graph neural networks. arXivpreprint arXiv:2003.06560, 2020.[132] Richard Socher, Danqi Chen, Christopher D Manning, and AndrewNg. Reasoning with neural tensor networks for knowledge base com-pletion. In NIPS, 2013.[133] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever,and Ruslan Salakhutdinov. Dropout: a simple way to prevent neuralnetworks from overfitting. JMLR, 15(1):1929–1958, 2014.[134] Otilia Stretcu, Krishnamurthy Viswanathan, Dana Movshovitz-Attias,Emmanouil Platanios, Sujith Ravi, and Andrew Tomkins. Graphagreement models for semi-supervised learning. In NeurIPS, pages8713–8723, 2019.[135] Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: acore of semantic knowledge. In WWW, 2007.[136] Mohammed Suhail and Leonid Sigal. Mixture-kernel graph attentionnetwork for situation recognition. In Proceedings of the IEEE Inter-national Conference on Computer Vision, pages 10363–10372, 2019.[137] Joshua B Tenenbaum, Vin De Silva, and John C Langford. A globalgeometric framework for nonlinear dimensionality reduction. science,290(5500):2319–2323, 2000.[138] Komal Teru, Etienne Denis, and William L Hamilton. Inductive re-lation prediction by subgraph reasoning. In International Conferenceon Machine Learning, pages 9448–9457. PMLR, 2020.112Bibliography[139] The´o Trouillon and Maximilian Nickel. Complex and holographicembeddings of knowledge graphs: a comparison. arXiv preprintarXiv:1707.01475, 2017.[140] The´o Trouillon, Johannes Welbl, Sebastian Riedel, E´ric Gaussier, andGuillaume Bouchard. Complex embeddings for simple link prediction.In ICML, pages 2071–2080. PMLR, 2016.[141] The´o Trouillon, Christopher R Dance, E´ric Gaussier, Johannes Welbl,Sebastian Riedel, and Guillaume Bouchard. Knowledge graph comple-tion via complex tensor factorization. JMLR, 18(1):4735–4772, 2017.[142] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, LlionJones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attentionis all you need. In Advances in Neural Information Processing Systems,pages 5998–6008, 2017.[143] Petar Velicˇkovic´, Guillem Cucurull, Arantxa Casanova, AdrianaRomero, Pietro Lio, and Yoshua Bengio. Graph attention networks.In ICLR, 2018.[144] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-AntoineManzagol. Extracting and composing robust features with denoisingautoencoders. In ICML, pages 1096–1103, 2008.[145] Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye,Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. Deep graph library:Towards efficient and scalable deep learning on graphs. arXiv preprintarXiv:1909.01315, 2019.[146] Quan Wang, Bin Wang, Li Guo, et al. Knowledge base completionusing embeddings and rules. In IJCAI, pages 1859–1866, 2015.[147] Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graphembedding: A survey of approaches and applications. TKDE, 29(12):2724–2743, 2017.[148] Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and HaoMa. Linformer: Self-attention with linear complexity. arXiv preprintarXiv:2006.04768, 2020.[149] William Yang Wang and William W Cohen. Learning first-order logicembeddings via matrix factorization. In IJCAI, pages 2132–2138,2016.113Bibliography[150] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bron-stein, and Justin M Solomon. Dynamic graph cnn for learning on pointclouds. Acm Transactions On Graphics (tog), 38(5):1–12, 2019.[151] Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowl-edge graph embedding by translating on hyperplanes. In AAAI, 2014.[152] Zhuoyu Wei, Jun Zhao, Kang Liu, Zhenyu Qi, Zhengya Sun, andGuanhua Tian. Large-scale knowledge base completion: Inferring viagrounding network sampling over selected instances. In ICKM, pages1331–1340. ACM, 2015.[153] Jianfeng Wen, Jianxin Li, Yongyi Mao, Shini Chen, and RichongZhang. On the representation and embedding of knowledge bases be-yond binary relations. In IJCAI, 2016.[154] Xuan Wu, Lingxiao Zhao, and Leman Akoglu. A quest for structure:Jointly learning the graph structure and semi-supervised classification.In CIKM, pages 87–96, 2018.[155] Naganand Yadati. Neural message passing for multi-relational orderedand recursive hypergraphs. Advances in Neural Information Process-ing Systems, 33, 2020.[156] Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Anand Louis,and Partha Talukdar. Hypergcn: Hypergraph convolutional networksfor semi-supervised classification. arXiv preprint arXiv:1809.02589,2018.[157] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.Embedding entities and relations for learning and inference in knowl-edge bases. arXiv preprint arXiv:1412.6575, 2014.[158] Bishan Yang, Wen tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.Embedding entities and relations for learning and inference in knowl-edge bases. CoRR, abs/1412.6575, 2015.[159] Liang Yang, Zesheng Kang, Xiaochun Cao, Di Jin, Bo Yang, andYuanfang Guo. Topology optimization based graph convolutional net-work. In IJCAI, pages 4054–4061, 2019.[160] Xuchen Yao and Benjamin Van Durme. Information extraction overstructured data: Question answering with freebase. In Proceedings of114Bibliographythe 52nd Annual Meeting of the Association for Computational Lin-guistics (Volume 1: Long Papers), pages 956–966, 2014.[161] Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and JureLeskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint arXiv:1802.08773, 2018.[162] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. Whendoes self-supervision help graph convolutional networks? arXivpreprint arXiv:2006.09136, 2020.[163] Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yim-ing Yang. Graph-revised convolutional network. In ECML PKDD,2020.[164] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poc-zos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Ad-vances in neural information processing systems, 30, 2017.[165] Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, andDit-Yan Yeung. Gaan: Gated attention networks for learning on largeand spatiotemporal graphs. arXiv preprint arXiv:1803.07294, 2018.[166] Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert:Only attention is needed for learning graph representations. arXivpreprint arXiv:2001.05140, 2020.[167] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen.An end-to-end deep learning architecture for graph classification. InThirty-Second AAAI Conference on Artificial Intelligence, 2018.[168] Richong Zhang, Junpeng Li, Jiajie Mei, and Yongyi Mao. Scalableinstance reconstruction in knowledge bases via relatedness affiliatedembedding. In Proceedings of the 2018 World Wide Web Conference,pages 1185–1194, 2018.[169] Richong Zhang, Junpeng Li, Jiajie Mei, and Yongyi Mao. Scalableinstance reconstruction in knowledge bases via relatedness affiliatedembedding. In Proceedings of the 2018 World Wide Web Conference,pages 1185–1194. International World Wide Web Conferences SteeringCommittee, 2018.115[170] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang,and Neil Shah. Data augmentation for graph neural networks. arXivpreprint arXiv:2006.06830, 2020.[171] Hao Zhu, Yankai Lin, Zhiyuan Liu, Jie Fu, Tat-seng Chua, andMaosong Sun. Graph neural networks with generated parameters forrelation extraction. arXiv preprint arXiv:1902.00756, 2019.[172] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu,and Danai Koutra. Beyond homophily in graph neural networks: Cur-rent limitations and effective designs. Advances in Neural InformationProcessing Systems, 33, 2020.[173] Qikui Zhu, Bo Du, and Pingkun Yan. Self-supervised training of graphconvolutional networks. arXiv preprint arXiv:2006.02380, 2020.[174] Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled andunlabeled data with label propagation. 2002.[175] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. InProceedings of the 20th International conference on Machine learning(ICML-03), pages 912–919, 2003.[176] Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, andLiang Wang. Deep graph structure learning for robust representations:A survey. arXiv preprint arXiv:2103.03036, 2021.[177] Daniel Zu¨gner, Amir Akbarnejad, and Stephan Gu¨nnemann. Adver-sarial attacks on neural networks for graph data. In Proceedings of the24th ACM SIGKDD International Conference on Knowledge Discov-ery & Data Mining, pages 2847–2856, 2018.116Appendix AProofs for Chapter 3Theorem 3.1 ComplEx cannot enforce non-trivial subsumptions.Proof Assume the non-trivial subsumption ∀h, t ∈ E∗ : r(h, t) → s(h, t).Based on the subsumption, we have φθ(s(h, t)) ≥ φθ(r(h, t)), and there areentities a, b ∈ E∗ such that φθ(s(a, b)) > φθ(r(a, b)). Let a ′ be an entitysuch that a ′ = −a . Then φθ(s(a ′, b)) = 1 − φθ(s(a, b)) and φθ(r(a ′, b)) =1−φθ(r(a, b), so φθ(s(a ′, b) < φθ(r(a ′, b)), a contradiction to the subsump-tion we assumed.Theorem 3.2 ComplEx-NNE+AER cannot satisfy its constraints and befully expressive if symmetry constraints are allowed.Proof In ComplEx a relation r is symmetric for all possible entities if andonly if Im(r ) = 0 (Trouillon et al. [140], Section 3). In order to satisfyconstraints for ∀h, t ∈ E : r(h, t) → s(h, t), Ding et al. [33] assign Im(r ) =Im(s ). Therefore, if relation r is symmetric, it enforces relation s to be sym-metric too which is not generally true. As a counter-example, r might bethe married to relation, which is symmetric (so the Im(married to) = 0),but s is the knows relation, and ∀h, t ∈ E : married to(h, t) → knows(h, t)is true in real-world, but setting the Im(knows) = Im(married to) will im-ply knows is symmetric, which is not true (for instance many people knowcelebrities but celebrities do not know those many people).Theorem 3.3 SimplE cannot enforce non-trivial subsumptions.Proof Consider ∀ h, t ∈ E∗ : r(h, t) → s(h, t) as a non-trivial subsump-tion. So we have φθ(s(h, t)) ≥ φθ(r(h, t)), and there are entities a, b ∈ E∗such that φθ(s(a, b)) > φθ(r(a, b)). Let a′ be an entity such that a ′ = −a .Then φθ(s(a′, b)) = 1 − φθ(s(a, b)) and φθ(r(a ′, b)) = 1 − φθ(r(a, b)), soφθ(s(a′, b)) < φθ(r(a ′, b) a contradiction to the subsumption we assumed.117Appendix A. Proofs for Chapter 3Theorem 3.4 (Expressivity) For any truth assignment over entities Eand relations R containing |τ ′| true triples, there exists a SimplE+ modelwith embeddings vectors of size min(|E| × |R|+ 1, |τ ′|+ 1) that represent theassignment.Proof Assume ri is the i -th relation in R and ej is the j -th entity in E .For a vector a we define (a)i as the i -th element of a. We define (r+i )n = 1if n div |E| = i except the last element (r+i )|E||R| = −1, and for each entitysi we define (e+j )n = 1 if n mod |E| = j or n = |E|× |R| and 0 otherwise. Inthis setting, for each ri and ej product of r i and e i is 0 everywhere exceptfor the element at (i × |E|+ j ) and the last element in the embeddings. Inorder for the triple ri(ej , ek ) to hold, we define (e−k ) to be a vector where allelements are 0 except the (i × |E| + j )-th element which is 2. This provesthat SimplE+ is fully expressive with the bound of |E| × |R| + 1 for size ofthe embeddings.We use induction to prove the bound |τ ′| + 1. Let |τ ′| = 0 (base ofinduction). We can have embedding vectors of size 1 for each entity andrelation, setting the value for entities to 1 and to relations to -1. Then (r+, h+, t+) + (r−, t−, h−) is negative for every entities h and t andrelation r . So there exists an assignment of size 1 that represent this groundtruth.Let’s assume for any ground truth where |τ ′| = n− 1, there exists an as-signment of values to embedding vectors of size n that represent the groundtruth (assumption of induction). We must prove for any ground truth where|τ ′| = n, there exist an assignment of values to embedding vectors of sizen + 1 that represent this ground truth.Let r(h, t) be one of the n true facts. Consider a modified ground truthwhich is identical to the ground truth with n true facts, except that r(h, t)is assigned false. The modified ground truth has n − 1 true facts and basedon the assumption of the induction, we can represent it using some embed-ding vectors of size n. Let q = (r+, h+, t+) + (r−, t−, h−). We add anelement to the end of all embedding vectors and set it to 0. This increasesthe vector size to n + 1 but does not change any scores. Then we set h to1, r to 1 and t to q + 1. This ensures this triple is true for the new vectors,and no other probability of triple is affected.118Appendix A. Proofs for Chapter 3Theorem 3.5 (Subsumption) SimplE+ guarantees subsumption using in-equality constraints.Proof Assume ∀h, t ∈ E∗ : r(h, t) → s(h, t) as a non-trivial subsump-tion. As legal entity embeddings in SimplE+ have non-negative elements, byadding the element-wise inequality constraint s ≥ r , we force φθ(s(h, t)) ≥φθ(r(h, t)) for all h, t ∈ E∗ which is forcing the subsumption.119Appendix BProofs and ImplementationDetails for Chapter 4B.1 Proofs for HypE and HSimplETheorem 4.1 (Expressivity) For any ground truth over entities E andrelations R containing |τ | true tuples and α = maxr∈R(|r |) , there exists aHypE and a HSimplE model with embedding vectors of size max(α|τ |, α) thatrepresents that ground truth.The following proofs the theorem for HypE.Proof To prove the theorem, we show an assignment of embedding valuesfor each entity and relation in τ such that the scoring function of HypE isas follows:φθ(x ) ={1 if x ∈ τ0 otherwiseWe begin the proof by first describing the embeddings of each of theentities and relations in HypE; we then proceed to show that with such anembedding, HypE can represent any world accurately.Let us first assume that |τ | > 0 and let fp be the pth fact in τ . We leteach entity e ∈ E be represented with a vector of length α|τ | in which thepth block of α-bits is the one-hot representation of e in fact fp : if e appearsin fact fp at position i , then the ith bit of the pth block is set to 1, and to0 otherwise. Each relation r ∈ R is then represented as a vector of length τwhose pth bit is equal to 1 if fact fp is defined on relation r , and 0 otherwise.ej ... ... ... ... ... ... ... ... 0 1 0 0 ... ... ... ... ... ... ... ...⍵2 0 1 0 0 ... ... 1 ... ...τ 𝛼ej ∗ ⍵2 ... ... 1 ... ...Figure B.1: An example of an embedding where |τ | = 5, α = 4 and f3 is thethird fact in τ120B.1. Proofs for HypE and HSimplEei ... ... 1 ... ... ... ... 0 ... ... ... ... 0 ... ... ... ... ... ... ...f3= r(ei , ej , ek) |τ| = 5 𝛼 = 4ej ... ... 0 ... ... ... ... 1 ... ... ... ... 0 ... ... ... ... ... ... ...ek ... ... 0 ... ... ... ... 0 ... ... ... ... 1 ... ... ... ... ... ... ...r ... ... 1 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...Figure B.2: An example of an embedding where |τ | = 5, α = 4 and f3 is thethird fact in τHypE defines convolutional weight filters for each entity position within atuple. As we have at most α possible positions, we define each convolutionalfilter ωi as a vector of length α where the ith bit is set to 1 and all othersto 0, for each i = 1, 2, . . . , α. When the scoring function φθ is applied tosome tuple x , for each entity position i in x , convolution filter ωi is appliedto the entity at position i in the tuple as a first step; the () function isthen applied to the resulting vector and the relation embedding to obtain ascore.Given any tuple x , we want to show that φθ(x ) = 1 if x ∈ τ and 0otherwise.First assume that x = fp is the pth fact in τ that is defined on relation rand entities where ei is the entity at position i . Convolving each ei with ωiresults in a vector of length |τ | where the pth bit is equal to 1 (since bothωi and the pth block of ei have a 1 at the ith position) (See Figure B.1.Then, as a first step, function () computes the element-wise multiplicationbetween the embedding of relation r (that has 1 at position p) and all ofthe convolved entity vectors (each having 1 at position p); this results in avector of length |τ | where the pth bit is set to 1 and all other bits set to 0.Finally, () sums the outcome of the resulting products to give us a scoreof 1.To show that φθ(x ) = 0 when x /∈ τ , we prove the contrapositive, namelythat if φθ(x ) = 1, then x must be a fact in τ . We proceed by contradiction.Assume that there exists a tuple x /∈ τ such that φθ(x ) = 1. This meansthat at the time of computing the element-wise product in the () function,there was a position j at which all input vectors to () had a value of 1.This can happen only when (1) applying the convolution filter wj to eachof the entities in x produces a vector having 1 at position j , and (2) theembedding of relation r ∈ x has 1 at position j .The first case can happen only if all entities of x appear in the j th fact121B.1. Proofs for HypE and HSimplEfj ∈ τ ; the second case happens only if relation r ∈ x appears in fj . Butif all entities of x , as well as its relation, appear in fact fj , then x ∈ τ ,contradicting our assumption. Therefore, if φθ(x ) = 1, then x must be afact in τ .To complete the proof, we consider the case when |τ | = 0. In this case,since there are no facts, all entities and relations are represented by zero-vectors of length α. Then, for any tuple x , φθ(x ) = 0. This completes theproof.The following proofs the theorem for HSimplE.Proof To prove the theorem, we follow the same strategy as Theorem 1 byshowing an assignment of embedding values for each entity and relation inτ such that the scoring function of HSimplE is as follows:φθ(x ) ={1 if x ∈ τ0 otherwiseWe begin the proof by first describing the embeddings of each of theentities and relations in HSimplE; we then proceed to show that with suchan embedding, HSimplE can represent any world accurately.Let us first assume that |τ | > 0. We let each entity e ∈ E be representedwith a vector of length α|τ | in which the pth block of |τ |-bits indicatesentities that appeared in position p in the facts. In an entity embedding,the ith bit in the j th block is set to 1 if the entity appears in position j inthe ith fact. Each relation r ∈ R is then represented as a vector of lengthα ∗ τ whose pth bit is equal to 1 if fact fp is defined on relation r , and 0otherwise.Given any tuple x , we want to show that φθ(x ) = 1 if x ∈ τ and 0otherwise.First assume that x = fi is the ith fact in τ that is defined on relation rand entities e1, e2, . . . , where ep is the entity at position p. Shifting each epresults in a vector where the ith bit is equal to 1 (see Figure B.2). Then, asa first step, function () computes the element-wise multiplication betweenthe embedding of relation r (that has 1 at position i) and all of the shiftedentity vectors (each having 1 at position i). Finally, () sums the outcomeof the resulting products to give us a score of 1.To show that φθ(x ) = 0 when x /∈ τ , we prove the contrapositive, namelythat if φθ(x ) = 1, then x must be a fact in τ . We proceed by contradiction.Assume that there exists a tuple x /∈ τ such that φθ(x ) = 1. This meansthat at the time of computing the element-wise product in the () function,122B.2. Theoretical Analysisthere was a position i at which all input vectors to () had a value of 1.This can happen only when (1) applying the shift operation to each of theentities in x produces a vector having 1 at position i , and (2) the embeddingof relation r ∈ x has 1 at position i .The first case can happen only if all entities of x appear in the ith factfi ∈ τ ; the second case happens only if relation r ∈ x appears in fi . But ifall entities and relations of x appear in fact fi , then x ∈ τ , contradicting ourassumption. Therefore, if φθ(x ) = 1, then x must be a fact in τ .To complete the proof, we consider the case when |τ | = 0. In this case,since there are no facts, all entities and relations are represented by zero-vectors of length α. Then, for any tuple x , φθ(x ) = 0.B.2 Theoretical AnalysisThe current section groups the theoretical analysis of our work into fourparts. In particular, Appendix B.2.1 proves that ReAlE is fully expressive.Appendix B.2.2 proves that m-TransH, RAE, and NaLP are not fully expres-sive (G-MPNN scoring function and its non-expressiveness were discussed inSection 4.3.1). Appendix B.2.3 shows how closely ReAlE can represent rela-tional algebra operations. Appendix B.2.4 further proves that HypE cannotrepresent all relational algebra operations (in particular, we show that HypEcannot represent selection). For completeness, we restate the theorems.B.2.1 Full Expressivity of ReAlEThe following result proves that there exists a setting of the parametersfor which ReAlE can separate true and false tuples for arbitrary input. Inparticular, we show it for the case where σ is the sigmoid function.Theorem 4.2 (Full Expressivity) For any ground truth over entities Eand relations R containing λ true tuples with α = maxr∈R(|r |) as the max-imum arity over all relations in R, there is a ReAlE model with nw = λ,w = α, d = max(αλ, α), and σ(x ) = 11+exp(−x) that accurately separates thetrue tuples from the false ones.Proof Let τ = {τ0, τ1, . . . , τλ−1} be all the true tuples defined over E andR.To prove the theorem, we show an assignment of embedding values for eachof the entities and relations in τ such that the scoring function of ReAlE is123B.2. Theoretical Analysisr1K KK KK Kr2KKbrj = K/2 - 3Kbrj = K/2 - 2Kxaxbxcxd 11 11 11 1 1111KKKFigure B.3: An example of a ReAlE embedding assignments for true tuplesτ0 = r1(xa , xb , xc), τ1 = r2(xa , xc), τ2 = r1(xc , xb , xd ) and τ3 = r1(xd , xc , xa).Here, the number of true tuples λ = nw = 4, maximum arity ω = 3. Cellsthat are set to zero are left empty for better readability. As an example,given that xb is in position 1 of τ2, we set cell 2× ω + 1 = 7 of xb to 1. Wefurther set the value of r1 at positions [1][7] to K .as follows.φθ(τ){≥ 1−  if τ ∈ T< λ otherwiseHere,  is an arbitrary small value such that  < 12+λ2. Observe that λ(the number of true tuples) is positive. So, for any value of λ, λ and 1− never meet (As  < 12+λ2and also  < 11+λ , therefore λ < 1− ).We first consider the case where λ > 0. Let K = 2× σ−1(1− ). Then,σ(K2 ) = 1−  and σ(−K2 ) = .We begin the proof by first describing an assignment of the embeddingsof each of the entities and relations in ReAlE; we then proceed to show thatwith such an embedding, ReAlE accurately separates the true tuples fromthe false ones.We consider the embeddings of entities to be nw = λ blocks of size weach, such that each block i is conceptually associated with true tuple τi forall 0 ≤ i < λ. Then, for a given entity xm at position m of tuple τi , we setthe value xm [iw + m] to 1, for all 0 ≤ i < λ. All other values in xm areset to zero. For the relation embeddings, first, recall that these embeddingsare matrices of dimension |r | × wλ, and we consider each of the |r | rows ofthis matrix to be λ blocks of size w , where |r | > 1 is the arity of the givenrelation. If a given relation r appears in true tuple τi , we set the |r | valuesat position [iw + k ][iw + k ] to K , for all 0 ≤ k < |r | and 0 ≤ i < λ; all othervalues in the relation embedding are set to zero. Finally, we set all the biasterms in our model to bjr =K2 − |r | ×K , for all 0 ≤ j < λ. As an example,124B.2. Theoretical Analysisconsider Figure B.3, in which the first, third and fourth tuples τ0, τ1 and τ3are defined on relation r1; thus the embedding of r1 has K in the diagonalof the first, third and fourth 3× 3 blocks. The tuple τ0 has entity xb at itssecond position; hence the embedding of xb has a 1 in its second position.We claim that with such an assignment, the score of tuples that are true is≥ 1−  and < λ otherwise.To see why this assignment works, first, observe that our scoring functionφθ is a summation of λ sigmoids; each sigmoid is defined on an embeddingblock where we sum the bias term with the sum of pairwise product betweenthe entity and relation embeddings of the given block.Let τp = r(x1, . . . , xm) be a true tuple and observe the embeddings of itsentities and relations. The blocks at position p of the embeddings of eachof x1, . . . , xm contain exactly one value 1 each (with the rest being zero);and the block at position p of the relation embedding for r contains K s inthe diagonal and zeros elsewhere. With such an assignment, the block atposition p will contribute the following sigmoid to the scoring function.σ (bpr + |r |K ) = σ(K2− (|r |K ) + (|r |K ))= σ(K2)= 1−  (B.1)All other blocks q 6= p in τp will contribute to the scoring function inone of two ways, depending on whether or not r is a relation in τq .If the relation r of τp is also the relation in τq (e.g., r1 is a relation inτ0, τ2 and τ3 in Figure B.3), then when we multiply the |r | w -sized blocksat position q of the relation embedding to their corresponding entity blocksat position q (the inner double-summation in the scoring function Equa-tion 4.7), there will be at most c < |r | instances where K (in the relationembedding) is multiplied by 1 (in the entity embedding). This is becauseotherwise, the fact at position q is the same as the fact at position p inτ , indicating there is a duplicate in our set of facts. More precisely, for allblocks q 6= p in τp such that r is the relation of τq , the block at position pwill contribute the following sigmoid to the scoring function.σ (bqr + cK ) = σ(K2− |r |K + cK)= σ(K2− (r − c)K)< (B.2)If r is not a relation in τq , then the block at position q of the relationembedding is all zeros. In this case,σ (bqr + 0) = σ(K2− (|r |K ))<  (B.3)125B.2. Theoretical AnalysisIn the end, the score of any true tuple φθ(τp) will be the sum of λsigmoids such that exactly one of these sigmoids (block at position p) hasa value 1 − , while the other λ − 1 sigmoids are < . The score of a truetuple τp can thus be bounded as follows.φθ(τp) >= 1−  (B.4)In the case of a false tuple, all the sigmoids will yield values <  (as theywill be of the forms in either of Equation B.2, or Equation B.3). The scoreof a false tuple τf can thus be bounded as follows.φθ(τf ) < λ (B.5)To complete the proof, we consider the case when λ = 0. In this case,we let the entity and relation embeddings be blocks of arbitrary size andset all values to zero. We set the bias terms as before. Then, the score ofany tuple will be φθ(τf ) <  (Equation B.5), which is what we want. Thiscompletes the proof.B.2.2 Full Expressivity of Some BaselinesThe following results prove that some of the baselines are not fully expres-sive and have severe restrictions on the types of relations they can model.Liu et al. [97] discuss some of these limitations, and here we address themmore formally.Theorem 4.3 m-TransH, RAE, and NaLP are not fully expressive andhave restrictions on the relations these approaches can represent.The proof of the above theorem follows from Lemma 4.3.1 and 4.3.2below.Lemma 4.3.1 m-TransH and RAE are not fully expressive and have re-strictions on what relations these approaches can represent.Proof Kazemi and Poole (2018) prove that TransH [151] is not fully ex-pressive and explore its restrictions. As m-TransH reduces to TransH forbinary relations, it inherits all its restrictions and is not fully expressive.RAE also follows the same strategy as m-TransH in modeling the relations.Therefore, both m-TransH and RAE are not fully expressive.126B.2. Theoretical AnalysisLemma 4.3.2 NaLP is not fully expressive.Proof NaLP first concatenates the embeddings of entities and the embed-ding of their corresponding roles in the tuples, then applies to them thefollowing functions: 1D convolution, projection layer, minimum, and an-other projection layer. Looking carefully at the output of the model, theNaLP scoring function for a tuple r(x1, . . . , xn) is in the form of |P 1x 1 +· · ·+ P nx n + r |1 with P i as learnable diagonal matrices with some sharedparameters. In the binary setup (n = 2), the score function of NaLP is|P 1x 1 + P 2x 2 + r |1. Kazemi and Poole (2018), however, proved that trans-lational methods having a score function of |P 1x 1−αP 2x 2+r |i are not fullyexpressive and have severe restrictions on what relations these approachescan represent. NaLP has the same score function with α = −1 and i = 1and therefore is not fully expressive.B.2.3 Representing Relational Algebra with ReAlETheorem 4.4 (Renaming) Given permutation function pi, and relation s,there exists a parametrization for relation t in ReAlE such that for entitiesx1, . . . , xn , with arbitrary embeddingsφθ(t(x1, . . . , xn)) = φθ(s(xpi(1), xpi(2), . . . , xpi(n)))Proof To prove the above statement, we show that given entity embeddingsx 1, . . . , x n and an embedding for s, there exists a parametrization for t thatsatisfies the above equality.We claim that the following settings for t are enough to show the theo-rem.1. T [pi(i)][k ] = S [i ][k ] ∀ 1 ≤ i ≤ n, ∀ 0 ≤ k < d , and2. bjt = bjs ∀ 0 ≤ j < nwTo see why, we simply expand the score function of s and replace thevalues for s by that of t as described, to obtain the score for t .127B.2. Theoretical Analysisφθ(s(xpi(1), xpi(2), . . . , xpi(n)))=nw−1∑j=0σ(bjs +|s|∑i=1w−1∑k=0x pi(i)[j × w + k ]× S [i ][j × w + k ])=nw−1∑j=0σ(bjt +|s|∑i=1w−1∑k=0x pi(i)[j × w + k ]× T [pi(i)][j × w + k ])=nw−1∑j=0σ(bjt +|t |∑i=1w−1∑k=0x i [j×w +k ]×T [i ][j×w +k ]) = φθ(t(x1, x2, . . . , xn))Theorem 4.5 (Projection) For any relation s on n arguments there existsa parametrization for relation t on m < n arguments in ReAlE such thatfor any arbitrary sequence x1, . . . , xnφθ(t(x1, . . . , xm)) ≥ φθ(s(x1, . . . , xn))Proof To prove the above statement, we first expand the score function ofeach side of the inequality.φθ(t(x1, . . . , xm)) =nw−1∑j=0σ(bjt +m∑i=1w−1∑k=0x i [j ×w + k ]×T [i ][j ×w + k ])(B.6)φθ(s(x1, . . . , xn))=nw−1∑j=0σ(bjs +m∑i=1w−1∑k=0x i [j × w + k ]× S [i ][j × w + k ]+n∑i=m+1w−1∑k=0x i [j × w + k ]× S [i ][j × w + k ]) (B.7)The theorem holds with the following assignments.128B.2. Theoretical Analysis1. T [i ][k ] = S [i ][k ] ∀ 1 ≤ i ≤ m, ∀ 0 ≤ k < d , and2. bjt = bjs +n∑i=m+1w−1∑k=0max(0,S [i ][k ]) ∀ 0 ≤ j < nwTheorem 4.6 (Selection 1) For arbitrary relation s, there exists a parametriza-tion for relation t in ReAlE such that for arbitrary entities x1, . . . , xn−1φθ(t(x1, . . . , xn−1)) = φθ(s(x1, . . . , xn−1, xn−1))Proof To prove the above statement, we first expand the score function ofφθ for the right side of the equality.φθ(s(x1, . . . , xn−1, xn−1))=nw−1∑j=0σ(bjs +n−2∑i=1w−1∑k=0x i [j × w + k ]× S [i ][j × w + k ]+w−1∑k=0x n−1[j × w + k ]× S [n − 1][j × w + k ]+w−1∑k=0x n−1[j × w + k ]× S [n][j × w + k ])= (grouping terms)nw−1∑j=0σ(bjs +n−2∑i=1w−1∑k=0x i [j × w + k ]× S [i ][j × w + k ]+w−1∑k=0x n−1[j × w + k ]× (S [n − 1][j × w + k ] + S [n][j × w + k ]))(B.8)For the theorem to hold, the above score has to be equal to that of t ,which is described as follows.φθ(t(x1, . . . , xn−1))=nw−1∑j=0σ(bjt +n−2∑i=1w−1∑k=0x i [j × w + k ]× T [i ][j × w + k ]+w−1∑k=0x n−1[j × w + k ]× T [n − 1][j × w + k ]) (B.9)129B.2. Theoretical AnalysisThe scores in Equation B.8 and Equation B.9 are equal when the em-bedding and bias of t are set as follows.1. T [i ][k ] = S [i ][k ] ∀ 1 ≤ i ≤ n − 2, ∀ 0 ≤ k < d , and2. T [n − 1][k ] = S [n − 1][k ] + S [n][k ] ∀ 0 ≤ k < d , and3. bjt = bjs ∀ 0 ≤ j < nwTheorem 4.7 (Selection 2) For arbitrary relation s and for a fixed con-stant c, there exists a parametrization for relation t in ReAlE such that forarbitrary entities x1, . . . , xn−1φθ(t(x1, . . . , xn−1)) = φθ(s(x1, . . . , xn−1, c))Proof Using similar score expansions as in the proof of Theorem 4.6, wecan rewrite the scores of the two relations as follows.φθ(s(x1, . . . , xn−1, c))=nw−1∑j=0σ(bjs +n−2∑i=1w−1∑k=0x i [j × w + k ]× S [i ][j × w + k ]+w−1∑k=0x n−1[j × w + k ]× S [n − 1][j × w + k ]+w−1∑k=0c [j × w + k ]× S [n][j × w + k ])(B.10)φθ(t(x1, . . . , xn−1))=nw−1∑j=0σ(bjt +n−2∑i=1w−1∑k=0x i [j × w + k ]× T [i ][j × w + k ]+w−1∑k=0x n−1[j × w + k ]× T [n − 1][j × w + k ]) (B.11)The scores in Equation B.10 and Equation B.11 are equal when the embed-ding and bias of t are as set follows.130B.2. Theoretical Analysis1. T [i ][k ] = S [i ][k ] ∀ 1 ≤ i ≤ n − 1, ∀ 0 ≤ k < d , and2. bjt = bjs +∑w−1k=0 S [n][j × w + k ]× c [j × w + k ] ∀ 0 ≤ j < nwTheorem 4.8 (Set Union) For arbitrary relations s and r with the samearity, there exists a parametrization for relation t in ReAlE such that forarbitrary entity set x¯φθ(t(x¯ )) ≥ max(φθ(s(x¯ )), φθ(r(x¯ )))Proof Given that ReAlE embeds entities in non-negative vectors and exam-ining the scoring functions of each of the relations t , r , s, it can be observedthat the above inequality holds by setting the following values.1. T [i ][k ] = max(S [i ][k ],R[i ][k ]) ∀ 1 ≤ i < |x¯ | and 0 ≤ k < d .2. bjt = max(bjs , bjr ) ∀ 0 ≤ j < nw .In the lemma that follows, recall that the relation complement function(if it exists) is some linear function f (φθ(r(x¯ ))) = φθ(¬r(x¯ )) for arbitraryrelation r and entities x¯ that also has the form f (σ(x )) = σ(c × x ) with cas a constant. For instance, when σ is sigmoid, f (x ) = 1 − x and c = −1(f (σ(x )) = 1− σ(x ) = σ(−x )) and when σ is tanh, f (x ) = −x and c = −1(f (σ(x )) = −σ(x ) = σ(−x )).Theorem 4.9 (Set Difference) For arbitrary relations r and s with thesame arity, if f is a linear relation complement function and f (σ(x )) =σ(c × x ) with c as a constant, there exists a parametrization for relation tin ReAlE such that for arbitrary entities x1, . . . , xnφθ(t(x¯ )) ≤ min(φθ(s(x¯ )), f (φθ(r(x¯ ))))ProofAs f is the relation complement, we have:φθ(¬r(x1, . . . , xn)) = f (φθ(r(x1, . . . , xn)))131B.2. Theoretical AnalysisAs f is linear, we can distribute it inside the summation as follows:f (φθ(r(x1, . . . , xn))) =nw−1∑j=0f (σ(bjr +|r |∑i=1w−1∑k=0x i [jw + k ]× R[i ][jw + k ]))Now, as f (σ(x )) = σ(c × x ), we can distribute it inside the σ as follows:f (φθ(r(x1, . . . , xn))) =nw−1∑j=0σ(bjr × c +|r |∑i=1w−1∑k=0x i [jw + k ]×R[i ][jw + k ]× c)Therefore, for the above inequality to hold, the bias terms and embeddingvalues of t must be at most that of each of s and the complement of thescore of r . Examining the scoring functions of each of the relations t , r , s,it can be observed that the lemma holds when the following is set.1. T [i ][k ] = min(S [i ][k ],R[i ][k ]× c) ∀ 1 ≤ i < |x¯ | and 0 ≤ k < d .2. bjt = min(bjs , bjr × c) ∀ 0 ≤ j < nw .The following theorem establishes the ability of ReAlE to jointly capturethe relational algebra operations discussed above. This is of interest, partic-ularly as Abboud et al. [3] claimed ”Capturing multiple inference patternsjointly is significantly more challenging [than capturing them singly].” Herethe parametrizations do not interfere with each other; each relation has itsown parametrization.Theorem 4.10 (Composition) For an arbitrary set of relations Sr andarbitrary non-empty composition of operations Sop from the set renaming,projection, selection, set union, and set difference, there exists a parametriza-tion for relation t in ReAlE with t as the resulting relation of applying Sopto Sr .Proof Given any operation in Sop composed of k primitive operations, weprove the theorem by induction on k for arbitrary k .Base case: For one operation (k = 1), according to Theorems 4.4 to 4.9,ReAlE is able to represent single operations for arbitrary relation(s) as inputto the operation. So the base case holds.132B.2. Theoretical AnalysisInduction step (operation k to k + 1): Assume a parametrization existsfor all compositions of length k . Now consider an operation composed ofk + 1 operations from Sop . If we ignore the last operation in the sequence,we know by the induction hypothesis that there exists a parametrization fora relation that represents the composition of the first k operations. Addingthe (k + 1)st relation back to the sequence, the preceding theorems (The-orems 4.4 to 4.9) show that we can define a parametrization for this lastoperation based on that of the previous that is independent of the parame-ters of the first k operations. This completes the proof.Theorem 4.11 (Joint Representation) ReAlE is able to jointly repre-sent a set of relations each being the result of a relational algebra operationsrenaming, projection, selection, set difference, and set union or a compositionof the operations.Proof All the parametrizations proposed in the proofs of Theorems 4.4to 4.10 are solely based on defining the parametrization of the output rela-tion t based on the input relation(s) without changing that of other relations(including t). Since each relation t uses its own parametrization without af-fecting any parameters of other relations, then all such relations can berepresented concurrently. This proves the theorem.B.2.4 Representing Relational Algebra with HypESo far, we showed that ReAlE is fully expressive and can represent the re-lational algebra operations renaming, projection, selection, set union, and setdifference. We also showed that most other models for knowledge hyper-graph completion are not fully expressive. In this section, we show thateven as HypE ([40]) is fully expressive in general, it cannot represent somerelational algebra operations (namely, selection) while at the same time re-taining its full expressivity. In special cases, such as when all tuples arefalse, it obviously can, however, we show that in the general case it cannot.We proceed by first showing in Theorem B.1 that HypE cannot representselection for arbitrary entity and relation embeddings while retaining fullexpressivity. Now, one might think that even if representing selection is notpossible for all embeddings, there might be some embedding space for whichHypE would be able to represent selection. In Theorem B.2 we show thatwhen the embedding size is less than the number of entities (as it usually is133B.2. Theoretical Analysisthe case), then there is no setting for which HypE would be able to representselection.HypE embeds an entity xi and a relation r in vectors x i ∈ Rd and r ∈ Rdrespectively, where d be the embedding size. In what follows, we let f (x , p)be a function that computes the convolution of the embedding of entity xwith the corresponding convolution filters associated with position p andoutputs a vector (see [40] for more details). We let φHθ be the HypE scoringfunction.Theorem B.1 (HypE Selection 1 (a)) For arbitrary relation s and arbi-trary embeddings for entities x1, . . . , xn−1, there exists no parametrizationfor relation t in HypE such thatφHθ (t(x1, . . . , xn−1)) = φHθ (s(x1, . . . , xn−1, xn−1)) (B.12)ProofTo see why there is no parametrization for t that satisfies Equation B.12,we first expand the left and right sides of the equation as follows.φHθ (t(x1, . . . , xn−1)) = φHθ (s(x1, . . . , xn−1, xn−1))d∑i=1t [i ]× f (x1, 1)[i ]× · · · × f (xn−1,n − 1)[i ] =d∑i=1s [i ]× f (x1, 1)[i ]× · · · × f (xn−1,n − 1)[i ]× f (xn−1,n)[i ]For this equation to hold, the following should hold for arbitrary entitiesx1, . . . , xn−1, and ∀ 1 ≤ i ≤ d .or{f (x1, 1)[i ]× · · · × f (xn−1,n − 1)[i ] = 0t [i ] = s [i ]× f (xn−1,n)[i ](B.13)For an entity x at position p in a tuple, the output of function f (x , p)depends on the embedding of entity x and the convolution filters associatedwith position p. Note that these convolution filters are shared among allrelations in the knowledge hypergraph and are not specific to relation s ort .As we want Equation B.13 to hold for arbitrary entity embeddings, itis easy to see that there exists at least one setup for convolution filters andentity embeddings for which none of the factors in the product f (xi , 1)[i ]×· · · × f (xn−1,n − 1)[i ] is zero.134B.2. Theoretical AnalysisNow consider such an embedding setting. The only way Equation B.13 issatisfied is when we set t [i ] = s [i ]× f (xn−1,n)[i ] for all 1 ≤ i ≤ d . Observethat by setting the embedding of relation t to the embedding of s timesf (xn−1,n) for a particular entity xn−1, we have effectively set it to a fixedvalue. Now consider an entity xk such that f (xk ,n) 6= f (xn−1,n), and applythe selection t to xk by replacing xn−1 with xk in Equation B.12. The equalitycondition in the equation will not hold, because none of the conditions inEquation B.13 hold. Therefore, in this setup, t fails to represent s forarbitrary entity embeddings.Given that relation t should represent selection of s for all the entities inthe hypergraph, setting it to a fixed value will make it incapable of repre-senting selection for arbitrary entities. We can thus conclude that there is noparametrization for HypE such that it can represent selection for arbitraryembeddings of relations and entities.We now show that when the embedding size is less than the number ofentities |E| in the hypergraph, there is no setting for which HypE would beable to represent selection without losing full expressivity.Theorem B.2 (HypE Selection 1 (b)) For arbitrary relation s, there ex-ists no parametrization for relation t in HypE having scoring function φHθsuch that for arbitrary entities x1, . . . , xn and embedding dimension d < |E|,where |E| is the number of entities in the knowledge hypergraph, HypE re-mains fully expressive andφHθ (t(x1, . . . , xn−1)) = φHθ (s(x1, . . . , xn−1, xn−1))ProofConsider |s| = 2 and |t | = 1 and tuples t(xj ) and s(xj , xj ) such thatrelation t is a selection of s. We will show that when the embedding dimen-sion d of the entities is smaller than the number of entities in the knowledgehypergraph, there is no parametrization of HypE that gets t to represent swhile retaining full expressivity.For the sake of contradiction, assume that the lemma statement is false.Then there exists a parametrization for t such that HypE is fully expressiveand thatφHθ (t(xj )) = φHθ (s(xj , xj ))135B.2. Theoretical AnalysisExpanding the score function for s and t we getd∑i=1t [i ]× f (xj , 1)[i ] =d∑i=1s [i ]× f (xj , 1)[i ]× f (xj , 2)[i ]⇒d∑i=1f (xj , 1)[i ]× (t [i ]− s [i ]× f (xj , 2)[i ]) = 0For this equation to hold for arbitrary entities x1, x2, . . . , xn , it shouldhold for all 1 ≤ i ≤ d and all 1 ≤ j ≤ |E| for which s(xj , xj ) is true.Assuming that d < |E|, we need to have the following hold for all 1 ≤ j ≤ |E|and 1 ≤ i ≤ d .or{f (xj , 1)[i ] = 0t [i ] = s [i ]× f (xj , 2)[i ](B.14)We claim that to satisfy the above equation simultaneously for all pos-sible i and j , there must be at least one entity xk for which the convolutionfunction returns a zero vector; that is, f (xk , 1)[i ] = 0 for all 0 ≤ i ≤ d .To see why this is true, assume the contrary; that is, for each convolutionfilter f (xj , 1) has at least one bit that is different than zero for arbitraryentity xj . Without loss of generality, let the j th bit f (xj , 1)[j ] = Kj , for all1 ≤ j ≤ |E| and Kj ∈ R∗. Then, to satisfy Equation B.14 at index j , wemust set t [j ] = s [j ]× f (xj , 2)[j ]. As Equation B.14 must be satisfied for allentities, then all other entities xk with k 6= j must have their j -th bit set tozero. Thus f (xk , 1)[j ] = 0 for all 0 ≤ j ≤ d and j 6= k . See Figure B.4. Sincewe have d < |E|, and by the pigeon-hole principle, there must be at least oneentity xd+1 such that f (xd+1, 1) = 0 for all 1 ≤ i ≤ d . This contradicts theoriginal assumption, and thus there exists at least one k for which f (xk , 1)returns a zero vector.This would further imply that any tuple having xk in the first positionwill have a score φHθ of zero. This would be regardless of the relation inthe tuple, or whether or not it is true. This violates the full-expressivity ofHypE, thus contradicting the original assumption that the lemma statementis False. Therefore, when d < |E|, there is no parametrization for t suchthat HypE represents selection while retaining full expressivity.136B.3. Implementation DetailsK1 0 0 0 0 ……. 0 00 K2 0 0 0 ……. 0 00 0 0 0 0 ……. 0 Kd0 0 0 0 0 ……. 0 0… ….0 0 K3 0 0 ……. 0 0⨉⨉⨉⨉Figure B.4: Proof of Theorem B.2: If at least one value of each vector f (xi , 1)is different than zero (Ki ¿ 0) and the value of at most one position i can benon-zero (the d columns in the figure), then by the pigeon-hole principle, wewill run out of indices as we have more entities in the knowledge hypergraph.In the above image, the entity xd+1.B.3 Implementation DetailsWe implement ReAlE in PyTorch [109] and use Adagrad [35] as the optimizerand dropout [133] to regularize the model. We perform early stopping andhyperparameter tuning based on the mrr on the validation set. We fix themaximum number of epochs to 1000 and embedding size to 200. We tunelr (learning rate) and w (window size) using the sets {0.05, 0.08, 0.1, 0.2},and {1, 2, 4, 5, 8} (first five divisors of 200). We tune σ (nonlinear function)using the set {tanh, sigmoid , exponent} for the jf17k dataset. As sigmoidoutperforms tanh and exponent on jf17k, we only tried sigmoid for otherdatasets. For the experiment on rel-er and also in Section 4.3.7 (ReAlEwith a fixed negative ratio and batch size), we fixed the negative ratio andbatch size of all baselines and our model to 10 and 128 respectively.Reported results for the baselines on jf17k, fb-auto, and m-fb15k aretaken from the original paper except for that of GETD [97] and BoxE [3] onm-fb15k. The original paper of GETD only reports results for arity 3 and4 as trained and tested separately in the corresponding arity. However, inour experimental setup, we train and test in a dataset containing relationsof different arities. For that, we train and test GETD. As GETD learns atensor of dimension |r | for each relation r , it needs d |r | (with d as embeddingsize) number of parameters. The original paper proposes smart strategies toreduce the number of parameters to be learned by the model. However, westill need to store the relation embedding and thus need to store d |r | floating-point numbers for each relation r . Because of our memory limitation (12GBGPU), we could only train the GETD model for embedding size of less than137B.3. Implementation Details10.The sign “-” in Table 1 indicates that the corresponding paper has notprovided the results.For the experiment on the synthetic dataset, we compare our modelwith m-TransH 4 [153], HypE 5 [40], and BoxE 6 [3], which are the onlycompetitive baselines that have provided the code.For all the experiments we use a single 12GB GPU (NVIDIA Tesla P100PCIe 12 GB).4https://github.com/wenjf/multi-relational_learning5https://github.com/ElementAI/HypE6https://github.com/ralphabb/BoxE138Appendix CSupplementary Material forChapter 5C.1 Supervision Starvation in Erdo˝s-Re´nyi andScale-free networksWe start by defining some new notation that helps simplify the proofs andanalysis in this section. We let lv be a random variable indicating that v is alabeled node, with lv indicating that its negation, cv ,u be a random variableindicating that v is connected to u with an edge, with cv ,u indicating itsnegation, and clv be random variable indicating that v is connected to atleast one labeled node with clv indicating its negation (i.e., it indicates thatv is connected to no labeled nodes).Theorem 5.1 Let G(n,m) be an Erdo˝s-Re´nyi graph with n nodes and medges. Assume we have labels for q nodes selected uniformly at random. Theprobability of an edge being a starved edge with a two-layer GCN is equal tothe following:(1− qn)(1− qn − 1)2q∏i=1(1− m − 1(n2)− i )Proof To compute the probability of an edge being a starved edge, wefirst compute the probability of the two nodes of the edge being unlabeledthemselves and then the probability of the two nodes not being connected toany labeled nodes. Let v and u represent two nodes connected by an edge.With n nodes and q labels, the probability of a node being labeled isqn . Therefore, Pr(lv ) = (1 − qn ) and Pr(lu | lv ) = (1 − qn−1). Therefore,Pr(lv ∧ lu) = (1− qn )(1− qn−1).Since there is an edge between v and v , there are m−1 edges remaining.Also, there are(n2) − 1 pairs of nodes that can potentially have an edgebetween them. Therefore, the probability of v being disconnected from thefirst labeled node is 1 − m−1(n2)−1. If v is disconnected from the first labeled139C.1. Supervision Starvation in Erdo˝s-Re´nyi and Scale-free networksnode, there are still m−1 edges remaining and there are now (n2)−2 pairs ofnodes that can potentially have an edge between them. So the probabilityof v being disconnected from the second node given that it is disconnectedfrom the first labeled node is 1 − m−1(n2)−2. With similar reasoning, we cansee that the probability of v being disconnected from the i -th labeled nodegiven that it is disconnected from the first i − 1 labeled nodes is 1− m−1(n2)−i.We can follow similar reasoning for u. The probability of u being dis-connected from the first labeled node given that v is disconnected from all qlabeled nodes is 1− m−1(n2)−q−1. That is because there are still m − 1 edges re-maining and(n2)−q−1 pairs of nodes that can potentially be connected withan edge. We can also see that the probability of u being disconnected fromthe i -th labeled node given that it is disconnected from the first i−1 labelednodes and that v is disconnected from all q labeled nodes is 1− m−1(n2)−q−i.As the probability of the two nodes being unlabeled and not being con-nected to any labeled nodes in the graph are independent, their joint prob-ability is the multiplication of their probabilities computed above and it isequal to (1− qn )(1− qn−1)∏2qi=1(1− m−1(n2)−i ).Baraba´si–Albert and scale-free networks. We also extend the aboveresult for Erdo˝s-Re´nyi graphs to the Baraba´si–Albert [9] model. SinceBaraba´si–Albert graph generation results in scale-free networks with a scaleparameter γ = −3, we present results for the general case of scale-free net-works as it makes the analysis simpler and more general. In what follows,we compute the probability of an edge being a starved edge in a scale-freenetwork.Let G be a scale-free network with n nodes, q labels (selected uniformly atrandom), and scale parameter γ. Then, if we select a random edge betweentwo nodes v and u, the probability of the edge between them being a starvededge is:Pr(lv ) ∗ Pr(lu |lv ) ∗ Pr(clv |cv ,u , lv , lu) ∗ Pr(clu |cv ,u , lv , lu , clv ).Each of these terms can be computed as follows ((ab)represents thenumber of combinations of selecting b items from a set with a items):• Pr(lv ) = (1− qn )140C.2. Implementation Details• Pr(lu |lv ) = (1− qn−1)• Pr(clv |cv ,u , lu , lv ) =∑n−1k=1 kγ (n−q−2k−1 )(n−2k−1)∑n−1k=1 kγFor a large enough network, Pr(clu |cv ,u , lv , lu , clv ) can be approximatedas Pr(clu |cv ,u , lv , lu) and it can be computed similarly as the previous case.With the derivation above, for a scale-free network with n = 2708 andq = 140 (corresponding to the stats from cora), the probability of an edgebeing a starved edge for γ = −3 is 0.87 and for γ = −2 is 0.76 .C.2 Implementation DetailsWe implemented our model in PyTorch [109]. We used deep graph li-brary (DGL) [145] for the sparse operations, and used Adam [81] as theoptimizer. We performed early stopping and hyperparameter tuning basedon the accuracy on the validation set for all datasets except wine and can-cer. For these two datasets, the validation accuracy reached 100 percentwith many hyperparameter settings, making it difficult to select the best setof hyperparameters. Instead, we used the validation cross-entropy loss forthese two datasets.We fixed the maximum number of epochs to 2000. We use two-layerGCNs for both GNNC and GNNDAE as well as for baselines and two-layerMLPs throughout the chapter (for experiments on ogbn-arxiv, althoughthe original paper uses models with three layers and with batch normaliza-tion after each layer, to be consistent with our other experiments we usedtwo layers and removed the normalization). We used two learning rates,one for GCNC as lrC and one for the other parameters of the models aslrDAE . We tuned the two learning rates from the set {0.01, 0.001}. Weadded dropout layers with dropout probabilities of 0.5 after the first layer ofthe GNNs. We also added dropout to the adjacency matrix for both GNNCand GNNDAE as dropoutC dropoutDAE respectively and tuned the valuesfrom the set {0.25, 0.5}. We set the hidden dimension of GNNC to 32 for alldatasets except for ogbn-arxiv for which we set it to 256. We used cosinesimilarity for building the kNN graphs and tuned the value of k from theset {10, 15, 20, 30}. We tuned λ (λ controls the relative importance of thetwo losses) from the set {0.1, 1, 10, 100, 500}. We tuned r and η from thesets {1, 5, 10} and {1, 5} respectively. The best set of hyperparameters foreach dataset chosen on the validation set is in Table C.1.141C.3. More Experiments and AnalysisFor GRCN [163], DGCNN [150], and IDGL [23], we used the code re-leased by the authors and tuned the hyperparameters as suggested in theoriginal papers. The results of LDS [47] are directly taken from the originalpaper. For LP [175], we used scikit-learn python package [110].All the results for our model and the baselines are averaged over 10 runs.We report the mean and standard deviation. We ran all the experiments ona single GPU (NVIDIA GeForce GTX 1080 Ti).For self-training, we considered the label predictions for the top ζ mostconfident unlabeled nodes as ground truth labels and added them to thetraining labels. Here, ζ is a hyperparameter. We tuned its value from theset {50, 100, 200, 300, 400, 500}.C.2.1 kNN ImplementationFor our MLP generator, we used a kNN operation to sparsify the generatedgraph. Here, we explain how we implemented the kNN operation to avoidblocking the gradient flow. Let M ∈ Rn×n with M ij = 1 if vj is amongthe top k similar nodes to vi and 0 otherwise, and let S ∈ Rn×n withS ij = Sim(X′i ,X′j ) for some differentiable similarity function Sim (we usedcosine). Then A˜ = kNN(X ′) = M#S where # represents the Hadamard(element-wise) product. With this formulation, in the forward phase ofthe network, one can first compute the matrix M using an off-the-shelf k-nearest neighbors algorithm and then compute the similarities in S onlyfor pairs of nodes where M ij = 1. In our experiments, we compute exactk-nearest neighbors; one can approximate it using locality-sensitive hashingapproaches for larger graphs (see, e.g., [56, 84]). In the backward phase ofour model, we compute the gradients only with respect to those elementsin S whose corresponding value in M is 1 (i.e., those elements S ij suchthat M ij = 1); the gradient with respect to the other elements is 0. SinceS is computed based on X ′, the gradients flow to the elements in X ′ (andconsequently to the weights of the MLP) through S .C.3 More Experiments and AnalysisC.3.1 SymmetrizationIn the adjacency processor, we used the following equation:A = D−12(µ(A˜) + µ(A˜)T2)D−12142C.3. More Experiments and AnalysisTable C.1: Best set of hyperparameters for different datasets chosen on thevalidation set.Dataset Generator lrC lrDAE dropoutc dropoutDAE k λ r ηcora FP 0.001 0.01 0.5 0.25 30 10 10 5cora MLP 0.01 0.001 0.25 0.5 20 10 10 5cora MLP-D 0.01 0.001 0.25 0.5 15 10 10 5citeseer FP 0.01 0.01 0.5 0.5 30 1 10 1citeseer MLP 0.01 0.001 0.25 0.5 30 10 10 5citeseer MLP-D 0.001 0.01 0.5 0.5 20 10 10 5cora390 FP 0.01 0.01 0.25 0.5 20 100 10 5cora390 MLP 0.01 0.001 0.25 0.5 20 10 10 5cora390 MLP-D 0.001 0.001 0.25 0.5 20 10 10 5citeseer370 FP 0.01 0.01 0.5 0.5 30 1 10 1citeseer370 MLP 0.01 0.001 0.25 0.5 30 10 10 5citeseer370 MLP-D 0.01 0.01 0.25 0.5 20 10 10 5pubmed MLP 0.01 0.01 0.5 0.5 15 10 10 5pubmed MLP-D 0.01 0.01 0.25 0.25 15 100 5 5ogbn-arxiv MLP 0.01 0.001 0.25 0.5 15 10 1 5ogbn-arxiv MLP-D 0.01 0.001 0.5 0.25 15 10 1 5wine FP 0.01 0.001 0.5 0.5 20 0.1 5 5wine MLP 0.01 0.001 0.5 0.25 20 0.1 5 5wine MLP-D 0.01 0.01 0.25 0.5 10 1 5 5cancer FP 0.01 0.001 0.5 0.25 20 0.1 5 5cancer MLP 0.01 0.001 0.5 0.5 20 1.0 5 5cancer MLP-D 0.01 0.01 0.5 0.5 20 0.1 5 5digits FP 0.01 0.001 0.25 0.5 20 0.1 5 5digits MLP 0.01 0.001 0.25 0.5 20 10 5 5digits MLP-D 0.01 0.001 0.5 0.25 15 0.1 5 520news FP 0.01 0.01 0.5 0.5 20 500 5 520news MLP 0.001 0.001 0.25 0.5 20 500 5 520news MLP-D 0.01 0.01 0.25 0.25 20 100 5 5mnist (1000) MLP 0.01 0.01 0.5 0.5 15 10 10 5mnist (2000) MLP-D 0.01 0.001 0.5 0.5 15 100 10 5mnist (3000) MLP 0.01 0.01 0.5 0.5 15 10 5 5143C.3. More Experiments and AnalysisCora Citeseer646668707274Accuracy72.870.572.569.070.267.6MeanMaxNoneFigure C.1: The performance of SLAPS on cora and citeseer with dif-ferent adjacency symmetrizations.which symmetrized the adjacency matrix by taking the average of µ(A˜) andµ(A˜)T . Here we also consider two other choices: 1) max(µ(A˜), µ(A˜)T ), and2) not symmetrizing the adjacency (i.e., using µ(A˜)). Figure C.1 comparesthese three choices on cora and citeseer with an MLP generator (othergenerators produced similar results). On both datasets, symmetrizing theadjacency provides a performance boost. Compared to mean symmetriza-tion, max symmetrization performs slightly worse. This may be becausemax symmetrization does not distinguish between the case where both viand vj are among the k most similar nodes of each other and the case whereonly one of them is among the k most similar nodes of the other.C.3.2 Fixing a prior graph manually instead of usingself-supervisionSo far, we validated Hypothesis 1 by adding a self-supervised task to en-courage learning a graph structure that is appropriate for predicting thenode features, and showing in our experiments how this additional taskhelps improve the results. Here, we provide more evidence for the validityof Hypothesis 1 by showing that we can obtain good results even when regu-larizing the learned graph structure toward a manually fixed structure thatis appropriate for predicting the node features.Toward this goal, we experimented with cora and citeseer and createda cosine similarity graph as our prior graph Aprior where the edge weightscorrespond to the cosine similarity of the nodes. We sparsified Aprior byconnecting each node only to the k most similar nodes. Then, we added144C.3. More Experiments and AnalysisCora Citeseer646668707274Accuracy72.870.570.7 70.4SLAPSManually Defined PriorFigure C.2: The performance of SLAPS and regularization toward a man-ually defined prior structure on cora and citeseer when using the MLPgenerator.a term λ||A − Aprior ||F to the loss function where λ is a hyperparameter,A is the learned graph structure (i.e., the output of the graph generator),and ||.||F shows the Frobenius norm. Note that Aprior exhibits homophilywith respect to the node features because the node features in cora andciteseer are binary, so two nodes that share the same values for morefeatures have a higher similarity and are more likely to be connected.The results can be viewed in Figure C.2. According to the results, wecan see that regularizing toward a manually designed Aprior also providesgood results but falls short of SLAPS with self-supervision. The superiorityof the self-supervised approach compared to the manual design could be dueto two reasons.• Some of the node features may be redundant (e.g., they may be de-rived from other features) or highly correlated. These features cannegatively affect the similarity computations for the prior graph inAprior . As an example, consider three nodes with seven binary features[0, 0, 0, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0] and [1, 1, 1, 1, 1, 1, 1] respectively andassume the last two features for each node are always equivalent andare computed based on a logical and of the 4th and 5th features7.Without these two features, the first node is more similar to the sec-ond than the third node, but when considering these derived features,7For the first node in the example, the 4th and 5th features are both 1 so their logicaland is also 1 and so the last two features for this node are both 1. The computation forthe other two nodes is similar.145C.3. More Experiments and Analysisit becomes more similar to the third node. This change in node sim-ilarities affects the construction of Aprior which can deteriorate theoverall performance of the model. The version of SLAPS with theself-supervised task, on the other hand, is not affected by this prob-lem as much because the model can learn to predict the derived nodefeatures based on other features and without heavily relying on thegraph structure.• While many graph structures may be appropriate for predicting thenode features, in the manual approach we only regularize toward oneparticular such structure. Using the self-supervised task, however,SLAPS can learn any of those structures; ideally, it learns the one thatis more suited for the downstream task due to the extra supervisioncoming from the downstream task.C.3.3 Why not compare the learned graph structures withthe original ones?A comparison between the learned graph structures using SLAPS (or otherbaselines) and the original graph structure of the datasets we used may notbe sensible. We explain this using an example. Before getting into theexample, we remind the reader that the goal of structure learning for semi-supervised classification with graph neural networks is to learn a structurewith a high degree of homophily. Following Zhu et al. [172], we define theedge homophily ratio as the fraction of edges in the graph that connect nodesthat have the same class label.Figure C.3 demonstrates an example where two graph structures for thesame set of nodes have the same edge homophily ratio (0.8 for both) buthave no edges in common. For our task, it is possible that the original graphstructure (e.g., the citation graph in cora) corresponds to the structure onthe left but SLAPS (or any other model) learns the graph on the right,or vice versa. While both these structures may be equally good8, they donot share any edges. Therefore, measuring the quality of the learned graphusing SLAPS by comparing it to the original graph of the datasets may notbe sensible. However, if a noisy version of the initial structure is providedas input for SLAPS, then one may expect that SLAPS recovers a structuresimilar to the cleaned original graph and this is indeed what we demonstratein Section 5.5.4 (Paragraph “Noisy graphs”)8We are disregarding the features for simplicity sake.146C.3. More Experiments and Analysis 1 2 3 4 6 7 8 9 1 2 3 4 6 7 7 9 5 10 10 5 Figure C.3: Two example graph structures. Node colors indicate the classlabels. Solid lines indicate homophilous edges and dashed lines indicate non-homophilous edges. The two graphs exhibit the same degree of homophilyyet there is no overlap between their edges.147IndexAdaEdge, 81attributed graph, 7directed graph, 6embedding, 12enforcing a subsumption, 22fully expressive, 12graph, xiv, 6, 7graph neural networks, 14head, 9hypergraph, xiv, 7, 10knowledge graph, 12knowledge hypergraph, 11knowledge hypergraphcompletion, 32latent graph learning, 71link prediction, 11, 32mean reciprocal rank, 17node attributed graph, xiv, 7, 8node classification, 11non-trivial subsumption, 21primitive operations, 50reification, 33relational algebra, 50relational graph, xiv, 7, 9relational hypergraph, xiv, 9, 10scoring function, 12self-training, 81semi-supervised learning, 11semi-supervised nodeclassification, 11similarity graph, 71star-to-clique, 34starved edges, 78tail, 9triple, 9trivial subsumption, 21tuple, 9undirected graph, 6weighted graph, xiv, 6, 8148
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Poole, David L. (David Lynton), 1958-
Representation learning with explicit and implicit graph structures
Text