The standard evaluation protocol for measuring the quality of Knowledge Graph Completion methods - the task of inferring new links to be added to a graph - typically involves a step which ranks every entity of a Knowledge Graph to assess their fit as a head or tail of a candidate link to be added. In Knowledge Graphs on a larger scale, this task rapidly becomes prohibitively heavy. Previous approaches mitigate this problem by using random sampling of entities to assess the quality of links predicted or suggested by a method. However, we show that this approach has serious limitations since the ranking metrics produced do not properly reflect true outcomes. In this paper, we present a thorough analysis of these effects along with the following findings. First, we empirically find and theoretically motivate why sampling uniformly at random vastly overestimates the ranking performance of a method. We show that this can be attributed to the effect of easy versus hard negatives. Second, we propose a framework that uses relational recommenders to guide the selection of candidates for evaluation. We provide both theoretical and empirical justification of our methodology, and find that simple and fast methods work extremely well, matching advanced neural approaches. Even when a large portion of the true candidates for a property are missed, the estimation of the ranking metrics on a downstream model barely deteriorates. With our proposed framework, we can reduce the time and computation needed similar to random sampling strategies while vastly improving the estimation; on ogbl-wikikg2, we show that accurate estimations of the full ranking can be obtained in 20 seconds instead of 30 minutes. We conclude that considerable computational effort can be saved by effective preprocessing and sampling methods and still reliably predict performance accurately of the true performance for the entire ranking procedure. We make our code available to the community¹. ¹Accessible at https://github.com/Filco306/are-we-wasting-time.

Graphs are ubiquitous in real-world applications, ranging from social networks to biological systems, and have inspired the development of Graph Neural Networks (GNNs) for learning expressive representations. While most research has centered on static graphs, many real-world scenarios involve dynamic, temporally evolving graphs, motivating the need for Continuous-Time Dynamic Graph (CTDG) models. This paper provides a comprehensive review of Graph Representation Learning (GRL) on CTDGs with a focus on Self-Supervised Representation Learning (SSRL). We introduce a novel theoretical framework that analyzes the expressivity of CTDG models through an Information-Flow (IF) lens, quantifying their ability to propagate and encode temporal and structural information. Leveraging this frame-work, we categorize existing CTDG methods based on their suitability for different graph types and application scenarios. Within the same scope, we examine the design of SSRL methods tailored to CTDGs, such as predictive and contrastive approaches, highlighting their potential to mitigate the reliance on labeled data. Empirical evaluations on synthetic and real-world datasets validate our theoretical insights, demonstrating the strengths and limitations of various methods across long-range, bi-partite and community-based graphs. This work offers both a theoretical foundation and practical guidance for selecting and developing CTDG models, advancing the understanding of GRL in dynamic settings.

The sets of possible heads and tails for relations in a Knowledge Graph and a type taxonomy of participating entities are important aspects of a Knowledge Graph and constitute a large portion of a Knowledge Graph’s ontology. Making the ontology explicit helps to ensure consistency of the knowledge represented in the graph and allows for less costly maintenance and update of graph content. However, Knowledge Graphs are often conveniently formed without an explicitly described ontology, using only (head, relation, tail)-tuples. For such graphs without predefined structure, we propose learning an ontology and a hierarchical type taxonomy from the graph itself, taking advantage of the reciprocity of entity types and sets of possible heads (relational domains) and tails (relational ranges). Experiments on real-world datasets validate our approach and demonstrate the promise for leveraging machine learning methodologies to efficiently generate taxonomies and ontologies jointly for Knowledge Graphs (Our implementation can be found at https://tinyurl.com/5n6sw6yj).

In this paper, we report experiments on Few- and Zero-shot Knowledge Graph completion, where the objective is to add missing relational links between entities into an existing Knowledge Graph with few or no previous examples of the relation in question. While previous work has used pre-trained embeddings based on the structure of the graph as input for a neural network, nobody has, to the best of our knowledge, addressed the task by only using textual descriptive data associated with the entities and relations, much since current standard benchmark data sets lack such information. We therefore enrich the benchmark data sets for these tasks by collecting textual description data to provide a new resource for future research to bridge the gap between structural and textual Knowledge Graph completion. Our results show that we can improve the results for Knowledge Graph completion for both Few- and Zero-shot scenarios with up to a two-fold increase of all metrics in the Zero-shot setting. From a more general perspective, our experiments demonstrate the value of using textual resources to enrich more formal representations of human knowledge and in the utility of transfer learning from textual data and text collections to enrich and maintain knowledge resources.

In this paper, we propose a novel way of representing graphs for processing in Graph Neural Networks. We reduce the dimensionality of the input data by using Random Indexing, a Vector Symbolic Architectural framework; we implement a new trainable neural layer, also inspired by Vector Symbolic Architectures; we leverage the sparseness of the incoming data in a Sparse Neural Network framework. Our experiments on a number of publicly available datasets and standard benchmarks demonstrate that we can reduce the number of parameters by up to two orders of magnitude. We show how this parsimonious approach not only delivers competitive results but even improves performance for node classification and link prediction. We find that this holds in particular for cases where the graph lacks node features.