Concepts of Neighbors and their Application to Instance-based Learning on Relational Data

International audienceKnowledge graphs and other forms of relational data have become awidespread kind of data, and powerful methods to analyze and learn fromthem are needed. Formal Concept Analysis (FCA) is a mathematical frameworkfor the analysis of symbolic datasets, which has been extended to graphsand relational data, like Graph-FCA. It encompasses various tasks such aspattern mining or machine learning, but its application generally relies onthe computation of a concept lattice whose size can be exponential withthe number of instances. We propose to follow an instance-based approachwhere the learning effort is delayed until a new instance comes in, and aninference task is set. This is the approach adopted in k-Nearest Neighbors,and this relies on a distance between instances. We define a conceptualdistance based on FCA concepts, and from there the notion of concepts ofneighbors, which can be used as a basis for instance-based reasoning. Thosedefinitions are given for both classical FCA and Graph-FCA. We provide efficient algorithms for computing concepts of neighbors, and we demonstrate their inference capabilities by presenting three different applications: query relaxation, knowledge graph completion, and relation extraction