Various methods embed knowledge graphs with the goal of predicting missing edges. Inference patterns are the logical relationships that occur in a graph. To make proper predictions, models trained by embedding methods must capture inference patterns. There are several theoretical analyses studying pattern-capturing capabilities. Unfortunately, these analyses are challenging and many embedding methods remain unstudied. Also, they do not quantify how accurately a pattern is captured in real-world datasets. Existing empirical studies have studied a small subset of simple inference patterns, and the analysis methods used have varied depending on the models evaluated. In this paper, we present a model-agnostic method to empirically quantify how patterns are captured by trained embedding models. We collect the most plausible predictions to form a new graph, and use it to globally assess pattern-capturing capabilities. For a given pattern, we study positive and negative evidence, i.e., edges that the pattern deems correct and incorrect based on the partial completeness assumption. As far as we know, it is the first time negative evidence is analyzed. Our experiments show that several models effectively capture the positive evidence of inference patterns. However, the performance is poor for negative evidence, which entails that models fail to learn the partial completeness assumption. We also identify new inference patterns not studied before. Surprisingly, models generally achieve better performance in these new patterns that we introduce.

Link prediction models assign scores to predict new, plausible edges to complete knowledge graphs. In link prediction evaluation, the score of an existing edge (positive) is ranked w.r.t. the scores of its synthetically corrupted counterparts (negatives). An accurate model ranks positives higher than negatives, assuming ascending order. Since the number of negatives are typically large for a single positive, link prediction evaluation is computationally expensive. As far as we know, only one approach has proposed to replace rank aggregations by a distance between sample positives and negatives. Unfortunately, the distance does not consider individual ranks, so edges in isolation cannot be assessed. In this paper, we propose an alternative protocol based on posterior probabilities of positives rather than ranks. A calibration function assigns posterior probabilities to edges that measure their plausibility. We propose to assess our alternative protocol in various ways, including whether expected semantics are captured when using different strategies to synthetically generate negatives. Our experiments show that posterior probabilities and ranks are highly correlated. Also, the time reduction of our alternative protocol is quite significant: more than 77% compared to rank-based evaluation. We conclude that link prediction evaluation based on posterior probabilities is viable and significantly reduces computational costs.

In link prediction evaluation, an embedding model assigns plausibility scores to unseen triples in a knowledge graph using an input partial triple. Performance metrics like mean rank are useful to compare models side by side, but do not shed light on their behavior. Interpreting link prediction evaluation and comparing models based on such interpretation are appealing. Current interpretation methods have mainly focused on single predictions or other tasks different from link prediction. Since knowledge graph embedding methods are diverse, interpretation methods that are applicable only to certain machine learning approaches cannot be used. In this paper, we propose a model-agnostic method for interpreting link prediction evaluation as a whole. The interpretation consists of Horn rules mined from the knowledge graph containing the triples a model deems plausible. We combine precision and recall measurements of mined rules using Fβ score to quantify interpretation accuracy. To maximize interpretation accuracy when comparing models, we study two approximations to the hard problem of merging rules. Our quantitative study shows that interpretation accuracy serves to compare diverse models side by side, and that these comparisons are different from those using ranks. Our qualitative study shows that several models globally capture expected semantics, and that models make a common set of predictions despite of redundancy reduction.

Completion methods learn models to infer missing (subject, predicate, object) triples in knowledge graphs, a task known as link prediction. The training phase is based on samples of positive triples and their negative counterparts. The test phase consists of ranking each positive triple with respect to its negative counterparts based on the scores obtained by a learned model. The best model ranks all positive triples first. Metrics like mean rank, mean reciprocal rank and hits at k are used to assess accuracy. Under this generic evaluation protocol, we observe several shortcomings: 1) Current metrics assume that each measurement is upper bounded by the same constant value and, therefore, are oblivious to the fact that, in link prediction, each positive triple may have a different number of negative counterparts, which alters the difficulty of ranking positive triples. 2) Benchmarking datasets contain anomalies (unrealistic redundancy) that allegedly simplifies link prediction; however, current instantiations of the generic evaluation protocol do not integrate anomalies, which are just discarded based on a user-defined threshold. 3) Benchmarking datasets have been randomly split, which typically alters the graph topology and results in the training split not resembling the original dataset. 4) A single model is typically kept based on its accuracy over the validation split using a given metric; however, since metrics aggregate ranks into a single value, there may be no significant differences among the ranks produced by several models, which must be all evaluated in the test phase. In this paper, we contribute to the evaluation of link prediction as follows: 1) We propose a variation of the mean rank that considers the number of negative counterparts. 2) We define the anomaly coefficient of a predicate and integrate such coefficient in the protocol. 3) We propose a downscaling algorithm to generate training splits that reflect the original graph topology based on a nonparametric, unpaired statistical test. 4) During validation, we discard a learned model only if its output ranks are significantly different than other ranks based on a nonparametric, paired statistical test. Our experiments over seven well-known datasets show that translation-based methods (TransD, TransE and TransH) significantly outperform recent methods, which entails that our understanding of the accuracy of completion methods for link prediction is far from perfect.

Even though knowledge graphs have proven very useful for several tasks, they are marked by incompleteness. Completion algorithms aim to extend knowledge graphs by predicting missing (subject, predicate, object) triples, usually by training a model to discern between correct (positive) and incorrect (negative) triples. However, under the open-world assumption in which a missing triple is not negative but unknown, negative triple generation is challenging. Although negative triples are known to drive the accuracy of completion models, its impact has not been thoroughly examined yet. To evaluate accuracy, test triples are considered positive and negative triples are derived from them. The evaluation protocol is thus impacted by the generation of negative triples, which remains to be analyzed. Another issue is that the knowledge graphs available for evaluation contain anomalies like severe redundancy, and it is unclear how anomalies affect the accuracy of completion models. In this paper, we analyze the impact of negative triple generation during both training and testing on translation-based completion models. We examine four negative triple generation strategies, which are also used to evaluate the models when anomalies in the test split are included and discarded. In addition to previously-studied anomalies like near-same predicates, we include another anomaly: knowledge present in the test that is missing from the training split. Our main conclusion is that the most common strategy for negative triple generation (local-closed world assumption) can be mimicked by a combination of a naive and a immediate neighborhood strategies. This result suggests that completion models can be learned independently for certain subgraphs, which would render completion models useful in the context of knowledge graph evolution. Although anomalies are considered harmful since they artificially increase the accuracy of completion models, our results show otherwise for certain knowledge graphs, which calls for further research efforts.

Students taking introductory programming courses are typically required to complete assignments and expect timely feedback to advance their learning. With the current popularity of these courses in both traditional and online versions, graders are seeing themselves overwhelmed by the sheer amount of student programs they have to handle, and the quality of the educational experience provided is often compromised for promptness. Thus, there is a need for automated approaches to effectively increase grading productivity. Existing approaches in this context fail to support flexible grading schemes and customization based on the assignment at hand. This paper presents a data-driven approach for clustering recurrent program statements performing similar but not exact semantics across student programs, which we refer to as core statements. We rely on structural graph clustering over the program dependence graph representations of student programs. Such clustering is performed over the graph resulting from the pairwise approximate graph alignments of programs. Core statements help graders understand solution variations at a glance and, since they group program statements present in individual student programs, can be used to propagate feedback, thus increasing grading productivity. Our experimental results show that, on average, we discover core statements covering more than 50% of individual student programs, and that program statements grouped by core statements are semantically cohesive, which ensures effective grading.

The popularity of knowledge graphs has led to the development of techniques to refine them and increase their quality. One of the main refinement tasks is completion (also known as link prediction for knowledge graphs), which seeks to add missing triples to the graph, usually by classifying potential ones as true or false. While there is a wide variety of graph completion techniques, there is no standard evaluation setup, so each proposal is evaluated using different datasets and metrics. In this paper we present AYNEC, a suite for the evaluation of knowledge graph completion techniques that covers the entire evaluation workflow. It includes a customisable tool for the generation of datasets with multiple variation points related to the preprocessing of graphs, the splitting into training and testing examples, and the generation of negative examples. AYNEC also provides a visual summary of the graph and the optional exportation of the datasets in an open format for their visualisation. We use AYNEC to generate a library of datasets ready to use for evaluation purposes based on several popular knowledge graphs. Finally, it includes a tool that computes relevant metrics and uses significance tests to compare each pair of techniques. These open source tools, along with the datasets, are freely available to the research community and will be maintained.

Knowledge Graphs (KGs) contain large amounts of structured information. Due to their inherent incompleteness, a process known as KG completion is often carried out to find the missing triples in a KG, usually by training a fact checking model that is able to discern between correct and incorrect knowledge. After the fact checking model has been trained and evaluated, it has to be applied to a set of candidate triples, and those that are considered correct are added to the KG as new knowledge. However, this process needs a set of candidate triples of a reasonable size that represents possible new knowledge, in order to be evaluated by the fact checking task and, if considered to be correct, added to the KG, enriching it. Current approaches for selecting candidate triples for their correctness checking either use the full set possible missing candidate triples (and thus provide no filtering) or apply very basic rules to filter out unlikely candidates, which may have a negative effect on the completion performance as very few candidate triples are filtered out. In this paper we present CHAI, a method for producing more complex rules that are able to filter candidate triples by combining a set of criteria to optimize a fitness function. Our experiments show that CHAI is able to generate rules that, when applied, yield smaller candidate sets than similar proposals while still including promising candidate triples.

Currently, there is a "boom" in introductory programming courses to help students develop their computational thinking skills. Providing timely, personalized feedback that makes students reflect about what and why they did correctly or incorrectly is critical in such courses. However, the limited number of instructors and the great volume of submissions instructors need to assess, especially in Massive Open Online Courses (MOOCs), prove this task a challenge. One solution is to hire graders or create peer discussions among students, however, feedback may be too general, incomplete or even incorrect. Automatic techniques focus on: a) Functional testing, in which feedback usually does not sufficiently guide novices, b) Software verification to find code bugs, which may confuse novices since these tools usually skip true errors or produce false errors, and c) Comparing using reference solutions, in which a large amount of reference solutions or pre-existing correct submissions are usually required. This paper presents a semantic-aware technique to provide personalized feedback that aims to mimic an instructor looking for code snippets in student submissions. These snippets are modeled as subgraph patterns with natural language feedback attached to them. Submissions are transformed into extended program dependence graphs combining control and data flows. We leverage subgraph matching techniques to compute the adequate personalized feedback. Also, constraints correlating patterns allow performing fine-grained assessments. We have evaluated our method on several introductory programming assignments and a large number of submissions. Our technique delivered personalized feedback in milliseconds using a small set of patterns, which makes it appealing in real-world settings.

We are witnessing an increasing popularity of the Web of Data, which exposes a large variety of web sources that provide their data using RDF. Ontological models are used as the schema to organize this data. These models are usually shared by several communities and, to devise them, there is usually an agreement amongst those communities. As a result, it is common to have more than one ontological model to understand some RDF data; therefore, there might be a gap between the ontological models and the RDF data, which is not negligible in practice. In this article, the authors present a technique to automatically discover ontological models from raw RDF data. It is based on the intensive usage of a set of SPARQL 1.1 structural queries that are generic and independent from the RDF data. The final result of the authors' technique is an ontological model that is derived from the RDF data, and includes types and properties, subtypes, domains and ranges of properties and subproperties. The authors have conducted experiments with millions of triples that prove that their technique is suitable to deal with Big RDF Data. As far as they know, this is the first technique to discover such ontological models in the context of RDF data and the Web of Data.

The increasing popularity of the Web of Data is motivating the need to integrate semantic-web ontologies. Data exchange is one integration approach that aims to populate a target ontology using data that come from one or more source ontologies. Currently, there exist a variety of systems that are suitable to perform data exchange among these ontologies; unfortunately, they have uneven performance, which makes it appealing assessing and ranking them from an empirical point of view. In the bibliography, there exist a number of benchmarks, but they cannot be applied to this context because they are not suitable for testing semantic-web ontologies or they do not focus on data exchange problems. In this paper, we present MostoBM, a benchmark for testing data exchange systems in the context of such ontologies. It provides a catalogue of three real-world and seven synthetic data exchange patterns, which can be instantiated into a variety of scenarios using some parameters. These scenarios help to analyze how the performance of data exchange systems evolves as the exchanging ontologies are scaled in structured and/or data. Finally, we provide an evaluation methodology to compare data exchange systems side by side and to make informed and statistically sound decisions regarding: 1) which data exchange system performs better; and 2) how the performance of a system is influenced by the parameters of our benchmark.

Data translation, also known as data exchange, is an integration task that aims at populating a target model using data from a source model. This task is gaining importance in the context of semantic-web ontologies due to the increasing interest in graph databases and semantic-web agents. Currently, there are a variety of semantic-web technologies that can be used to implement data translation systems. This makes it difficult to assess them from an empirical point of view. In this paper, we present a benchmark that provides a catalogue of seven data translation patterns that can be instantiated by means of seven parameters. This allows us to create a variety of synthetic, domain-independent scenarios one can use to test existing data translation systems. We also illustrate how to analyse three such systems using our benchmark. The main benefit of our benchmark is that it allows to compare data translation systems side by side within a homogeneous framework.