A graph theory-based approach for partitioning knowledge bases

The growing interest in using structured methodologies for design and development is a clear signal of the maturation of knowledge-based systems technology. The objective of this paper is to explore ‘modularization’ – one of the cardinal principles of good design – as it applies to knowledge-baed systems. Drawing upon the fact that graphs have routinely been used to pictorially depict different approaches to knowledge representation, this paper argues that the problem of modularizing a knowledge case corresponds to one of decomposing its equivalent graph with nodes depicting objects / frames / rules, and edges depicting relationships between them. The problem of finding cohesive, minimally coupled decompositions of this graph is made particularly interesting because it is not meaningful to assign cardinal weights to the labelled edges (or relationships) for minimum cost partitioning, and difficult to assess the similarity of different nodes (or objects / frames / rules) for purposes of clustering. A lexicographic ordering of edge types can however be, and often is specified, as are structural properties for each of the subgraphs. The paper proposes a formulation of the decomposition problem as one of partitioning the graph of a knowledge base using a ‘pseudo-cost’ construct that ensures internal structural properties of subgraphs while operationalizing lexicographic priority in the placement of partition boundaries. It also demonstrates how a heuristic algorithm for partitioning knowledge bases can be developed by using this construct and appropriately adapting any of the procedures currently available for minimum cost graph partitioning.