Discovering Knowledge in Bipartite Graphs with Formal Concept Analysis

Since the 1970s knowledge based approaches are a crucial part of artificial intelligence (AI) research. In this work we investigate data sets in the form of bipartite graphs, i.e., graphs where a bipartition of the vertex set respecting the edge set can be found, for knowledge. To this end we first relate those bipartite graphs to the structure formal context, as used in formal concept analysis (FCA). This link enables us to employ the whole tool-set of FCA to bipartite graphs and therefore, notably, to bipartite social networks. In particular, notions for formal concepts, orderings of those, and implicational bases. All these then can be considered as aspects of knowledge in bipartite graphs. For the most part of our work we focus on implicational knowledge and how to compute all valid implications in a bipartite graph, also called theory. The common approach here is to compute a minimal basis of implications due to the possibly exponential size of the theory. Although our approach is mathematically elegant, it opened an immense number of a computational problems. First of all the size of common data sets is to large for classical algorithms from FCA. We overcome this limitation in our work by employing ideas from probably approximately correct (PAC) learning. This led to the development of PAC implicational bases. Furthermore, we developed a PAC exploration method, based on the attribute exploration algorithm, which is able to compute a basis of implications for implicit data sets in a PAC fashion. In experiments on PAC bases we encountered a dependency on the distribution of data in high dimensional attribute space. In order to express this observation in terms of a measure we developed a novel approach for measuring the intrinsic dimension of a data set. The goal here was to incorporate the particular set of features employed by a machine learning or knowledge procedure, like formal concepts, into the measure. In the later part of our work we point our attention to the order structures in bipartite social networks. We provide a first notion for individuality in social networks and clones, i.e., exchangeable vertices with respect to the concept structure. Finally, we show how to employ a social network of (local) domain experts to conduct a collaborative attribute exploration, and conclude our work by pointing out different tasks and applications as well as possible next steps.