Search

Given a relational database and training examples for a target relation, relational learning algorithms learn a Datalog program that defines the target relation in terms of the existing relations in the database. We demonstrate CastorX, a relational learning system that performs relational learning over heterogeneous databases. The user specifies matching attributes between (heterogeneous) databases through matching dependencies. Because the content in these attributes may not match exactly, CastorX uses similarity operators to find matching values in these attributes. As the learning process may become expensive, CastorX implements sampling techniques that allow it to learn efficiently and output accurate definitions.

This article presents a platform for interactive graph mining and relational machine learning called GraphVis. The platform combines interactive visual representations with state-of-the-art graph mining and relational machine learning techniques to aid in revealing important insights quickly as well as learning an appropriate and highly predictive model for a particular task (e.g., classification, link prediction, discovering the roles of nodes, and finding influential nodes). Visual representations and interaction techniques and tools are developed for simple, fast, and intuitive real-time interactive exploration, mining, and modeling of graph data. In particular, we propose techniques for interactive relational learning (e.g., node/link classification), interactive link prediction and weighting, role discovery and community detection, higher-order network analysis (via graphlets, network motifs), among others. GraphVis also allows for the refinement and tuning of graph mining and relational learning methods for specific application domains and constraints via an end-to-end interactive visual analytic pipeline that learns, infers, and provides rapid interactive visualization with immediate feedback at each change/prediction in real-time. Other key aspects include interactive filtering, querying, ranking, manipulating, exporting, as well as tools for dynamic network analysis and visualization, interactive graph generators (including new block model approaches), and a variety of multi-level network analysis techniques.

Relational program verification is a variant of program verification where one can reason about two programs and as a special case about two executions of a single program on different inputs. Relational program verification can be used for reasoning about a broad range of properties, including equivalence and refinement, and specialized notions such as continuity, information flow security or relative cost. In a higher-order setting, relational program verification can be achieved using relational refinement type systems, a form of refinement types where assertions have a relational interpretation. Relational refinement type systems excel at relating structurally equivalent terms but provide limited support for relating terms with very different structures. We present a logic, called Relational Higher Order Logic (RHOL), for proving relational properties of a simply typed $\lambda$-calculus with inductive types and recursive definitions. RHOL retains the type-directed flavour of relational refinement type systems but achieves greater expressivity through rules which simultaneously reason about the two terms as well as rules which only contemplate one of the two terms. We show that RHOL has strong foundations, by proving an equivalence with higher-order logic (HOL), and leverage this equivalence to derive key meta-theoretical properties: subject reduction, admissibility of a transitivity rule and set-theoretical soundness. Moreover, we define sound embeddings for several existing relational type systems such as relational refinement types and type systems for dependency analysis and relative cost, and we verify examples that were out of reach of prior work., Comment: Submitted to ICFP 2017

The queries issued to search engines are often ambiguous or multifaceted, which requires search engines to return diverse results that can fulfill as many different information needs as possible; this is called search result diversification . Recently, the relational learning to rank model, which designs a learnable ranking function following the criterion of maximal marginal relevance, has shown effectiveness in search result diversification [Zhu et al. 2014]. The goodness of a diverse ranking model is usually evaluated with diversity evaluation measures such as α-NDCG [Clarke et al. 2008], ERR-IA [Chapelle et al. 2009], and D#-NDCG [Sakai and Song 2011]. Ideally the learning algorithm would train a ranking model that could directly optimize the diversity evaluation measures with respect to the training data. Existing relational learning to rank algorithms, however, only train the ranking models by optimizing loss functions that loosely relate to the evaluation measures. To deal with the problem, we propose a general framework for learning relational ranking models via directly optimizing any diversity evaluation measure . In learning, the loss function upper-bounding the basic loss function defined on a diverse ranking measure is minimized. We can derive new diverse ranking algorithms under the framework, and several diverse ranking algorithms are created based on different upper bounds over the basic loss function. We conducted comparisons between the proposed algorithms with conventional diverse ranking methods using the TREC benchmark datasets. Experimental results show that the algorithms derived under the diverse learning to rank framework always significantly outperform the state-of-the-art baselines.

Learning novel relations from relational databases is an important problem with many applications in database systems and machine learning. Relational learning algorithms leverage the properties of the database schema to find the definition of the target relation in terms of the existing relations in the database. However, the same data set may be represented under different schemas for various reasons, such as efficiency and data quality. Unfortunately, current relational learning algorithms tend to vary quite substantially over the choice of schema, which complicates their off-the-shelf application. We demonstrate Castor , a relational learning system that efficiently learns the same definitions over common schema variations. The results of Castor are more accurate than well-known learning systems over large data.

Many analysis tasks involve linked nodes, such as people connected by friendship links. Research on link-based classification (LBC) has studied how to leverage these connections to improve classification accuracy. Most such prior research has assumed the provision of a densely labeled training network. Instead, this article studies the common and challenging case when LBC must use a single sparsely labeled network for both learning and inference, a case where existing methods often yield poor accuracy. To address this challenge, we introduce a novel method that enables prediction via “neighbor attributes,” which were briefly considered by early LBC work but then abandoned due to perceived problems. We then explain, using both extensive experiments and loss decomposition analysis, how using neighbor attributes often significantly improves accuracy. We further show that using appropriate semi-supervised learning (SSL) is essential to obtaining the best accuracy in this domain and that the gains of neighbor attributes remain across a range of SSL choices and data conditions. Finally, given the challenges of label sparsity for LBC and the impact of neighbor attributes, we show that multiple previous studies must be re-considered, including studies regarding the best model features, the impact of noisy attributes, and strategies for active learning.

The most common approach in predictive modeling is to describe cases with feature vectors (aka design matrix). Many machine learning methods such as linear regression or support vector machines rely on this representation. However, when the underlying data has strong relational patterns, especially relations with high cardinality, the design matrix can get very large which can make learning and prediction slow or even infeasible. This work solves this issue by making use of repeating patterns in the design matrix which stem from the underlying relational structure of the data. It is shown how coordinate descent learning and Bayesian Markov Chain Monte Carlo inference can be scaled for linear regression and factorization machine models. Empirically, it is shown on two large scale and very competitive datasets (Netflix prize, KDDCup 2012), that (1) standard learning algorithms based on the design matrix representation cannot scale to relational predictor variables, (2) the proposed new algorithms scale and (3) the predictive quality of the proposed generic feature-based approach is as good as the best specialized models that have been tailored to the respective tasks.

Latent relational search is a novel entity retrieval paradigm based on the proportional analogy between two entity pairs. Given a latent relational search query {(Japan, Tokyo), (France, ?)}, a latent relational search engine is expected to retrieve and rank the entity “Paris” as the first answer in the result list. A latent relational search engine extracts entities and relations between those entities from a corpus, such as the Web. Moreover, from some supporting sentences in the corpus, (e.g., “Tokyo is the capital of Japan” and “Paris is the capital and biggest city of France”), the search engine must recognize the relational similarity between the two entity pairs. In cross-language latent relational search, the entity pairs as well as the supporting sentences of the first entity pair and of the second entity pair are in different languages. Therefore, the search engine must recognize similar semantic relations across languages. In this article, we study the problem of cross-language latent relational search between Japanese and English using Web data. To perform cross-language latent relational search in high speed, we propose a multi-lingual indexing method for storing entities and lexical patterns that represent the semantic relations extracted from Web corpora. We then propose a hybrid lexical pattern clustering algorithm to capture the semantic similarity between lexical patterns across languages. Using this algorithm, we can precisely measure the relational similarity between entity pairs across languages, thereby achieving high precision in the task of cross-language latent relational search. Experiments show that the proposed method achieves an MRR of 0.605 on Japanese-English cross-language latent relational search query sets and it also achieves a reasonable performance on the INEX Entity Ranking task.

Many web-applications can be characterized as "relational". In this paper we introduce and evaluate WebRB , a visualdomain-specific language for building such applications. WebRB addresses the limitations of the conventional "imperative-embedding" approach typically used to build relational web-applications. We describe the WebRB language, present extended examples of its use, and discuss the WebRB visual editor, libraries, and runtime. We then evaluate WebRB by comparing it to alternative approaches, and demonstrate its effectiveness in building relational web-applications.

We perform an experimental comparison of the graph-based multi-relational data mining system, Subdue, and the inductive logic programming system, CProgol, on the Mutagenesis dataset and various artificially generated Bongard problems. Experimental results indicate that Subdue can significantly outperform CProgol while discovering structurally large multi-relational concepts. It is also observed that CProgol is better at learning semantically complicated concepts and it tends to use background knowledge more effectively than Subdue. An analysis of the results indicates that the differences in the performance of the systems are a result of the difference in the expressiveness of the logic-based and the graph-based representations. The ability of graph-based systems to learn structurally large concepts comes from the use of a weaker representation whose expressiveness is intermediate between propositional and first-order logic. The use of this weaker representation is advantageous while learning structurally large concepts but it limits the learning of semantically complicated concepts and the utilization background knowledge.

In this paper, we describe the challenges inherent to the task of link prediction , and we analyze one reason why many link prediction models perform poorly. Specifically, we demonstrate the effects of the extremely large class skew associated with the link prediction task. We then present an alternate task --- anomalous link discovery (ALD) --- and qualitatively demonstrate the effectiveness of simple link prediction models for the ALD task. We show that even the simplistic structural models that perform poorly on link prediction can perform quite well at the ALD task.

We analyze publication patterns in theoretical high-energy physics using a relational learning approach. We focus on four related areas: understanding and identifying patterns of citations, examining publication patterns at the author level, predicting whether a paper will be accepted by specific journals, and identifying research communities from the citation patterns and paper text. Each of these analyses contributes to an overall understanding of theoretical high-energy physics.

Efficiency and Scalability have always been important concerns in the field of data mining, and are even more so in the multi-relational context, which is inherently more complex. The issue has been receiving an increasing amount of attention during the last few years, and quite a number of theoretical results, algorithms and implementations have been presented that explicitly aim at improving the efficiency and Scalability of multi-relational data mining approaches. With this article we attempt to present a structured overview.

Graph-based relational learning (GBRL) differs from logic-based relational learning, as addressed by inductive logic programming techniques, and differs from frequent subgraph discovery, as addressed by many graph-based data mining techniques. Learning from graphs, rather than logic, presents representational issues both in input data preparation and output pattern language. While a form of graph-based data mining, GBRL focuses on identifying novel, not necessarily most frequent, patterns in a graph-theoretic representation of data. This approach to graph-based data mining provides both simplifications and challenges over frequency-based approaches. In this paper we discuss these issues and future directions of graph-based relational learning.

The past few years have witnessed an significant interest in probabilistic logic learning, i.e. in research lying at the intersection of probabilistic reasoning, logical representations, and machine learning. A rich variety of different formalisms and learning techniques have been developed. This paper provides an introductory survey and overview of the state-of-the-art in probabilistic logic learning through the identification of a number of important probabilistic, logical and learning concepts.

The Eighth Workshop on Mining and Learning with Graphs (MLG)1was held at KDD 2010 in Washington DC. It brought together a variete of researchers interested in analyzing data that is best represented as a graph. Examples include the WWW, social networks, biological networks, communication networks, and many others. The importance of being able to effectively mine and learn from such data is growing, as more and more structured and semi-structured data is becoming available. This is a problem across widely different fields such as economics, statistics, social science, physics and computer science, and is studied within a variety of sub-disciplines of machine learning and data mining including graph mining, graphical models, kernel theory, statistical relational learning, etc. The objective of this workshop was to bring together practitioners from these various fields and areas to foster a rich discussion of which problems we work on, how we frame them in the context of graphs, which tools and algorithms we apply and our general findings and lessons learned. This year's workshop was very successful with well over 100 attendees, excellent keynote speakers and papers. This is a rapidly growing area and we believe that this community is only in its infancy. We hope that the readers will join us next year for MLG 2011.

Inductive logic programming (ILP) is concerned with learning relational descriptions that typically have the form of logic programs. In a transformation approach, an ILP task is transformed into an equivalent learning task in a different representation formalism. Propositionalization is a particular transformation method, in which the ILP task is compiled to an attribute-value learning task. The main restriction of propositionalization methods such as LINUS is that they are unable to deal with nondeterminate local variables in the body of hypothesis clauses. In this paper we show how this limitation can be overcome., by systematic first-order feature construction using a particular individual-centered feature bias. The approach can be applied in any domain where there is a clear notion of individual. We also show how to improve upon exhaustive first-order feature construction by using a relevancy filter. The proposed approach is illustrated on the “trains” and “mutagenesis” ILP domains.

Although the relational model for databases provides a great range of advantages over other data models, it lacks a comprehensive way to handle incomplete and uncertain data. Uncertainty in data values, however, is pervasive in all real-world environments and has received much attention in the literature. Several methods have been proposed for incorporating uncertain data into relational databases. However, the current approaches have many shortcomings and have not established an acceptable extension of the relational model. In this paper, we propose a consistent extension of the relational model. We present a revised relational structure and extend the relational algebra. The extended algebra is shown to be closed, a consistent extension of the conventional relational algebra, and reducible to the latter.

Codd proposed the use of two interpretations of nulls to handle missing information in relational databases that may lead to a 4-valued logic [Codd86, Codd87]. In a more general model, three interpretations of nulls are necessary [Roth, Zani]. Without simplification, this may lead to a 7-valued logic, which is too complicated to be adopted in relational databases. For such a model, there is no satisfactory simplification to a 4-valued logic. However, by making a straightforward simplification and using some proposed logical functions, a 3-valued logic can handle all three interpretations.

By far the two most important database models used in data management today are the relational and the entity-relationship models. In the database development cycle, entity-relationship modeling precedes the relational model work. Yet, in most textbooks and therefore in the classroom the relational model is presented before the entity-relationship model. The student is left to retrofit the entity-relationship model to the relational model. This paper advocates reversing this order of presentation so as to be in line with the database development cycle. The major benefit lies in taking advantage of this sequence to improve teaching the relational model. Assuming a prior treatment of conceptual modeling, examples and principles of the entity-relationship model are used to illustrate, elaborate, and even explain relational model concepts.

This paper proposes a specific four-valued logic (4VL) as a means of handling missing data in Relational Data Base Management systems. The proposed 4VL is a minor variant of the standard 4VL in which the “least true” condition is interpreted as “inapplicable” rather than “false”. The use of this 4VL is defended on the grounds that by defining several additional unary operators, the 4VL can be rendered intuitively manageable. The proposed unary operators contribute to the conceptual utility of the 4VL by providing an explicit way for users to relate familiar results of two-valued logic to analogous results in 4VL.

Statistical Relational Learning (SRL) is concerned with building statistical models for relational data. While SRL approaches have shown much potential in complex real-world application domains, their computational complexity remains a major issue and often limits their practical applicability. This thesis is concerned with relatively simple yet efficient SRL techniques. We show how expressivity and generality can be traded for efficiency by restricting model complexity and developing special-purpose inference and learning algorithms that take advantage of such restrictions, as well as by tailoring models to specific application domains.

Bioinformatics is an application domain where information is naturally represented in terms of relations between heterogenous objects. Modern experimentation and data acquisition techniques allow the study of complex interactions in biological systems. This raises interesting challenges for machine learning and data mining researchers, as the amount of data is huge, some information can not be observed, and measurements may be noisy. This report presents a review on the ACM SIGKDD 2009 Workshop on Statistical Relational Learning and Mining in Bioinformatics (StReBio'09) which was held in Paris on June 28th, 2009. The aim of this workshop was to provide a forum to share challenges, results and ideas at the frontier between the field of statistical relational learning and the field of bioinformatics.

The translation of the one-to-one relationship from the Entity/Relationship model to the relational model while preserving one-to-one correspondence between the members of the participating entity sets is a topic that has been neglected in introductory database textbooks. In this paper, we provide a simple method, intended for students taking a first course in relational database design, that accomplishes this without introducing nulls or violating the relational model.

Daphne Koller discusses probabilistic relational modeling, artificial intelligence, and her new work with biologists.

A prototyped data mining system, DBLearn, has been developed, which efficiently and effectively extracts different kinds of knowledge rules from relational databases. It has the following features: high level learning interfaces, tightly integrated with commercial relational database systems, automatic refinement of concept hierarchies, efficient discovery algorithms and good performance. Substantial extensions of its knowledge discovery power towards knowledge mining in object-oriented, deductive and spatial databases are under research and development.

Relational algebras as developed by Codd and his followers are extended by noting an equivalence with functional languages. This leads to higher order relations, recursive definitions of relations, and the use of higher order relations as recursive data structures. This equivalence on the one hand enables the technology of databases to be used within the context of applicative languages, and on the other hand removes the adhoc mechanisms used for higher order operations in relational databases. This leads from 4th to 5th generation data management, exploiting the mathematical foundations of functional languages and logic programming, and the technology of relational database.

This paper discusses the semantic issues related to null values problem in relational databases. We argue that the proposed set of maybe operations with the three valued logic is still not adequate and needs further enhancements.

A methodology for designing and implementing program construction systems using relational data bases is presented. Relations are the only data structures used by them and in the definition of interfaces between subsystems. A special-purpose relational database manager (RDB) has been designed for this application.Two large projects using this approach are described. ART (Ada-Relational-Translator) is an experimental compiler-interpreter for ADA in which all subsystems, including parser, semantic analyzer, interpreter and kernel, use relations as their only data structure; the relational approach has been pushed to the upmost to achieve fast prototyping. MML (Multi-Micro Line) is a tool-set for constructing program programs for multi-microprocessors targets, in which relations are used for allocation and configuration control. Both experiences confirm the validity of the approach for managing team work in evolving projects.

Although the relational representation of Entity-Relationship (ER) structures gained extensive coverage, scarce attention has been paid to the issue of correctness for such representations. Several mappings have been proposed for the representation of both ER and extended ER (EER) structures by relational schemas. The informal nature of most of these proposals, however, does not allow a precise evaluation of their correctness, nor a comparison of the various mappings. We propose a canonical relational representation for EER structures and prove its correctness. We claim that a relational schema represents correctly an EER structure if it has equivalent information-capacity with the corresponding canonical representation. The second problem addressed by this paper is the normalization of relational schemas that represent EER structures. We examine the conditions required by this process and show that ignoring these conditions leads to erroneous analyses and inappropriate design decisions. We show that, under these conditions, the canonical relational representation of any (unrestricted) EER structure has an (information-capacity) equivalent Boyce-Codd Normal Form schema.

This report provides a brief overview of the method of programming in a relational calculus. This is a style of programming in which entire relations are manipulated as data, and in which the program itself is represented as a relation. This report describes the use of the relational operators to manipulate both data and functions, and introduces an improved notation for relational programming. (AUthor)

The relational model of data, originally introduced by Codd in [1], has three components: (1) a set of objects (relations, domains, etc.); (2) a set of operators (union, project, etc.); (3) a set of general integrity rules. The purpose of this paper is to provide a formal definition of each of these three components.

A relational knowledge base model and an architecture which manipulates the model are presented. An item stored in the relational knowledge base is called a term. A unification operation on terms in the relational knowledge base is used as the retrieval mechanism. The relational knowledge base architecture we propose consists of a number of unification engines, several disk systems, a control processor, and a multiport page-memory. The system has a knowledge compiler to support a variety of knowledge representations.

A relational implementation of IRDS using SQL demonstrates how the flexibility of the relational environment enhances the extensibility of the IRDS while at the same time providing more powerful dictionary capabilities than are typically found in relational systems.

In the DB field, there are two interpretations (or perceptions or schools of thought) concerning the relational model : (a) one interpretation considers that the relational model contribution to the DB field essentially consists in the presentation of a clear and simple notion of (flat) file, and that many users will be very satisfied to describe their data structures as tables; (b) another interpretation considers the relational model as a (reasonable) support for a (weak) entity relationship model.

There has been some technical and justified criticism of the treatment of missing information in the data sublanguage SQL and in IBM's Database 2 system (a relational database management system). Some of this criticism has been directed (by mistake) at the relational model. The purpose of this paper is to clarify and extend the treatment of missing information by the relational model. The clarification places heavy emphasis on the semantic aspects of missing information. The extension, which is relatively minor, provides a systematic approach (independent of data type) to dealing with the inapplicability of certain properties to some objects. This extension does not invalidate any part of the present version of the relational model.

A relational associative processor called RAP has been designed to provide hardware support for the use and manipulation of a relational data base. In this paper, we describe the relational operations provided by the RAP hardware, and devise a representative approach to providing the same relational operations with conventional software and hardware. Analytic models are constructed for both RAP and the conventional system. All simplifying assumptions are made to favor the conventional system. The execution times of several of the operations are shown to be improved with RAP by several orders of magnitude.