Seeking Divisions of Domains on Semantic Networks by Evolutionary Bridging

Abstract

Computational Creativity systems based on Conceptual Blending (CB) and Bisociation theories operate on input knowledge to reveal seemingly unrelated information. The input spaces or domains can be of various sources and contain vast amounts of knowledge. It is central a process that selects useful building blocks of semantic data that does not narrow the search space of the creative algorithm. It is also vital that the data selection process is of high performance in order to handle a large knowledge base in a useful time. With those objectives in mind, we propose an evolutionary high performance algorithm that extracts two semantic sub-graphs from a knowledge base to be used as building blocks in computational blending processes.

Introduction

A creative process can be seen as a form of heuristic search for a construct on a vast semantic space of concepts and domains. In this paper we propose an evolutionary approach inspired by the work of Nagel [ 6 ] for selecting two domains from a broader knowledge structure using high performance algorithms. This allows a faster extraction of a more concise representation of the data to be used in computational concept generation techniques, such as CB and Bisociative Knowledge Discovery, among other applications. As the amount of available knowledge dramatically expands each year, high performance algorithms are required to cope with the extraction of new insights, together with growth of multidisciplinary knowledge bases. In [ 3 ] Jur†i£, based on the ABC model by Swanson [ 11 ] [ 10 ], proposes the CrossBee system for supporting creativity insight in knowledge discovery of literature. In the ABC model, Swanson remarks that reference citations and other bibliographic indications potentially reveal new knowledge, which is not clearly intended neither logically exposed in the literature. That is, ABC exposes the A =) B =) C logical consequence, being B the term which relates the remaining terms A and C. Using this idea, CrossBee tries to explore bridging terms linking two apparently disconnected literature domains. In CrossBee, the bridge terms contain relations between two terms, each from a dierent domain, that were mined from a literature knowledge base. The terms are extracted from various sections in the literature texts, such as bibliography, citations, logical consequences and other references present in the texts. Having the literature containing the terms from A referencing terms regarding B, and Copyright © 2015 for this paper by its authors. Copying permitted for private and academic purposes. In Proceedings of the ICCBR 2015 Workshops. Frankfurt, Germany. simultaneously the literature C also references terms from B, then a unintended modus ponens inference suggest a hidden relation between A and C. Hence, the system following closely the ABC idea by Swanson.

M1

M2 (a) (b)

A similar work by Nagel et al. [ 6 ] introduces a formalised spreading activation algorithm to identify bridging concepts in a semantic graph (Fig. 1a). The bridging terms interconnect nodes from disjoint semantic domains, following an identical idea to CrossBee. However, the main intention in this case is to juxtapose two apparently unrelated domains through a single term [ 5 ]. This notion of pairing two disjoint frames of reference using a singular connection was put forth by Koestler and named Bisociation [ 4 ] in his work, The Act of Creation [ 4 ]. There, Arthur Koestler attempts to describe creative behaviour present in humour, arts and science. This model consists on the perceiving of a situation or idea ... in two self-consistent but habitually incompatible frames of reference (M1 and M2) as shown in Fig. 1b. For instance, in humour, bisociations could relate the unforeseen transformation from one meaning to another [ 7 ]. In their paper, Nagel explores a search space, dened using a bisociation score, which rates individually each bridging node subdividing the semantic graph in two completely disjoint sets. However, their approach does not allow a tolerance of the intersection between the two domains. Thus, it is in a sense a hard margin solution and in our opinion, it terminates the search prematurely in real world problems, as underlined in their conclusion. However, their highly formalised work served as a basis for our present approach. In the following section, we offer our evolutionary approach in the form of a Genetic Algorithm (GA), inspired by the work of Nagel. 2

Algorithm

The purpose of the algorithm is to identify two partially overlapping sub-graphs S0 and S1 of a larger semantic graph S. Given their structure, interrelations and arrangement within the larger graph, we believe the sub-graphs could be seen as domains of knowledge in the broader semantic graph.

The cardinality of each graph structure is identied by the symbol #. Thus, #S is the number of nodes existing in the graph S and we denote this quantity as the size of the graph. Each sub-graph represents a network of highly interconnected nodes, which if belonging to a semantic graph, could represent a domain of related concepts [ 1 ]. Both sub-graphs share at least a single node Nb, the bridge node, and the sub-graphs should be balanced [ 6 ] regarding a split through the bridge node. The size of both sub-graphs #S0 and #S1 should be maximized, with only the condition of S0 \ S1 = fNbg. Then, a unique path will ow from one sub-graph to the other through the bridge node which has the unique index b 2 f1 : : : #Sg. When this happens, the unique bridge node may represent a possible bisociation which juxtaposes one domain (sub-graph) into the other (Fig. 1b).

A degree di of a node Ni with i 2 f1 : : : #Sg represents the number of incident edges to that given node. Nodes with d = 2 represent a single relationship between two concepts, being these the most likely candidates for a bridge node [ 6 ]. The reasoning behind this choice is the interest in mapping two domains over a single and clear semantic relationship, through the bridge node. In this case, any concept from one sub-graph can be projected onto any other concept from the other sub-graph, oering a foundation for further transformations of concepts using processes from bisociation and CB [ 7 ].

Otherwise nodes with d 3 map a more vague set of relations between connected concepts. Intuitively, the view of an idea in two distinctly but opposing views is more ne tuned to two set of concepts (two domains) connected by a single node [ 6 ]. A simple example which demonstrates this idea is seen in Fig. 1a. On the other hand, highly interconnected nodes express a deeply related network of information or domain. Using the above criteria, the discrete function which rates the optimality (tness) of the bridge node Nb is dened in (1):

The tness function receives as arguments the sub-graphs S0; S1 and the degree of the bridge node Nb as the variable db. The parameter controls how similar in size the sub-graphs S0 and S1 are required to be, with increasing exhibiting greater size similarity. The parameter is used to control the penalisation given to bridge nodes with a degree d > 2, with the penalisation exponentially proportional to the value of . If the degree of node being rated is 1, that is, a terminal node with a single relation, then f is set to 0 in order to prevent the GA to select terminal nodes as bridge.

Globally, a GA evolves a population of chromosomes where each chromosome represents a bridge node and two sub-graphs of the initial semantic network. Each time a new individual is created with a given bridge node, a breadth rst search is executed starting in the latter node and into neighbouring nodes. The dual diusion process (a sort of spreading activation) progresses radially until a given expansion depth is reached when both sub-graphs intersect, or all the nodes in the network have been explored. From this expansion, we calculate a performance score representing this graph division which will represent the chromosome in the global tness landscape. Thus, the GA evolves subdivisions of the semantic network aiming to nd the bridging node that maximises the size of the sub-graphs found.

A GA was chosen in order to relax the search for global optima. Given a specic graph, the search space can be of very high complexity which is likely when handling large semantic networks. The optimisation task is represented by the tness function and the genetic operators embody the transformations that move the bridge node through the semantic graph. By using a GA, it is easy to parallelise the search algorithm with the following steps: tness functions are evaluated in parallel threads; new individuals which will dene the next generation are created in parallel threads; the generation of random chromosomes for the initial population and when the GA stagnates is executed in parallel threads.

38 37 48 47 46 59 58 57 56 69 68 67 77 76 In our GA we use entirely the mutation operator. Using Fig. 2 as an example, it can be seen that the fundamental operation required to traverse the search space (the graph) is the translation of the bridge node. Thus, the search algorithm samples stochastically (walks randomly) the locations in the graph that maximise the tness function. The mutation changes the location of the bridge node using the connected nodes (neighbourhood) recursively. In order to allow the bridge node to jump to distant sections of the graph, we use a quadratic random number generator. The probability function controlling the locality behaviour of this process decreases with the increasing number of jumps the bridge node is allowed to make. This number is given in (2).

j(r; s) = r s + 1 (2) The parameter r 2 [0; 1[ represents a previous output of an uniform pseudo random number generator. The number of nodes #S in the graph S is represented by the parameter s. The parameter 2]0; +1[ controls the average jump distance (translation deepness) the mutation applies to the bridge node.

If >> 1, the mutation tends to move the bridge node towards nearby nodes (Fig. 3b). When ! +1, the translation tends to move each bridge node to one of the connected neighbours. For 2]0; 1[, particularly nearby 0, tends to translate the bridge node to distantly connected nodes (Fig. 3a) and, in a sense, promote a random search of the tness landscape. The case where = 1 forces a straightforward stochastic search whereby each bridge node can be moved to any other node position of the domain S with constant probability.

After the mutation has been applied to the chromosome, the expansion of sub-graphs from the full domain is executed again from the newly calculated bridge node. When this completes, two new sub-graphs divide part (or all) of the domain with roots at the bridge node and depth d(0:::1). This expansion is a type of breadth rst search starting at the node Nb so that the rst nodes to explore are the nearby nodes. The main idea behind this reasoning is shown in Algorithm 1. Using two pairs of open (to expand) and closed (already expanded) nodes, the algorithm inserts the visited nodes in the two sub-graphs which will represent the sub-domains S0 and S1. An example of the process is seen in (Fig. 5) from where two dierent coloured sub-graphs emerge (Fig. 5). The function nodes(Si) returns the set of nodes fNig; i 2 f0; : : : #Si 1g in the sub-graph fNkg; k 2 f0; 1g. The variables Oi and Ci represent respectively the set of open (to visit) and closed (already visited) nodes related to the sub-graph i. The function split(Nb; S) divides the neighbourhood of the bridge node Nb in two sets of nodes as evenly as possible. When the neighbourhood of Nb is odd, a randomly chosen set Si receives the additional node so that in the worst case, the dierence of cardinality between S0 and S1 is 1.

The function expandOneLevel (Si; Oi; Ci; S) cycles through all the nodes in the set Oi, inserts each visited node in the set Ci and in the sub-graph Si, including the connected edges. Then it extracts the neighbourhood of each visited node and inserts the neighbour nodes in the set Oi, so that in the next iteration of the function createSubgraphs () the algorithm expands from the current neighbourhood of Oi. Thus, the function expandOneLevel() executes an equivalent single iteration of a breadth rst search at the same deepness level. All the nodes and edges are obtained from the graph S. Algorithm 1 Function createSubgraphs() function createSubgraphs(Nb; S) fS0; S1g split(Nb; S) O0 nodes(S0) O1 nodes(S1) C0 Nb C1 Nb I ; repeat expandOneLevel(S0; O0; C0; S) expandOneLevel(S1; O1; C1; S) I S0 \ S1

#I until #S0+#S1 end function

_ #S0 = 0 _ #S1 = 0

Starting at the bridge node Nb the expansion grows radially throughout the connected nodes, creating the sub-graphs while visiting the explored nodes until the sub-graphs intersect. For a graph in structure similar to Fig. 1a, the subgraphs are expected to intersect only in the bridge node. However, in real cases, while the expansion is taking place, the intersection can suddenly show a small amount of nodes when in comparison with the size of both sub-graphs S0 and S1. When this happens, the algorithm may not be able to nd a clean (and useful) division of the graph S.

Using a similar idea to Soft Margin in [ 2 ], we include the parameter 2 R0+ to allow more than one bridge node connecting the sub-graphs S0 and S1. With = 0, the intersection I between the sub-graphs is allowed to contain only the bridge node, as in Nagel. When the ratio of the intersection to both sub-graphs size increases above , the algorithm stops and returns the most recently created sub-graphs starting at node Nb. In sum, represents the trade-o between the penalization of highly interconnected sub-graphs and the maximisation of the size of those sub-graphs.

Consider the following example: after a 5 level expansion, the intersection of the two sub-graphs with a size of 2000 nodes each, suddenly increases from 1 (the bridge node only) to 100. This means that the fth iteration raised the subgraphs size to intersection ratio from 2000+1 2000 = 0:025% to 20001+002000 = 2:5%, a 100 fold increase. It may happen that the sub-graphs contain useful knowledge and for this reason, they should not be discriminated. Depending on the situation at hand, the parameter chosen to control the ratio may or not be signicant. 3

Results and discussion

The feasibility of our algorithm was tested using three semantic graphs. The rst, shown in Fig. 4a, was generated exclusively to test the theory supporting the algorithm. It contains 89 nodes and 106 unlabelled directed edges. The second is from the Horse-Dragon experiment, a well known semantic graph in Conceptual

dragon_left_leg dragon_right_leg dragon_left_wing dragon_right_wing dragon_torso dragon_tail dragon_right_arm red reptiles 2.0 pw pw pw defense strength dragon flesh defense pw tceoalmor_color isa fo d_consumption made_oftaxonomicq

horse

(b) Horse-Dragon graph.

Blending, supplied by the authors of [ 8 ]. This semantic graph contains 32 relations between 32 attributes of the animals horse and dragon, such as physical parts, health resistance and some taxonomic properties (Fig. 4b). The last is the Perception semantic graph from [ 9 ]. The author of Perception denes his knowledge base as a summary of manually annotated common sense concepts and their relations. It contains 3892 nodes and 345463 edges. Unless otherwise stated, the parameters used for the graph division algorithm were = 0, = 4, = 4 and = 2. The GA evolved a population of 103 chromosomes with a mutation rate of 100%, no crossover and a maximum number of 103 evolved generations.

Before the experiments, we validated the algorithm with a 111 node graph (Fig. 5) containing 188 directed edges. After the conclusion of the GA, the two sub-graphs S0 (green) and S1 (cyan) are juxtaposed through the bridge node with the label 56. The GA stopped when the intersection between the subgraphs included the nodes labelled 17, 95 and the bridge node with label 56. Afterwards, we proceeded with the experiments on the three semantic graphs.

Our algorithm reported a high amount of possible bridge nodes in the 89 node graph (Fig. 4a). From those, the 3 highest scored nodes are shown coloured, where the node in red scored 50% higher than the green nodes.

The Horse-Dragon [ 8 ] semantic graph is shown in Fig. 4b with the four highest rated chromosomes presented in Table 1. The majority of the nodes are terminal (d = 1) where a small number of highly interconnected nodes ( d 2) are clearly visible (Fig. 4b) labelled as horse and dragon. The best chromosomes generated by the GA produced were the two pairs of sub-graphs with each pair linked by the nodes with label creature and esh .

In order to study our algorithm with a more complex and practical problem, we researched the Perception [ 9 ] knowledge base with two experiments. For the rst, we did a study regarding the eect of in the size of the two sub-graphs. As shown in Table 2, the parameter highly inuences the size of both sub-graphs. Having the Perception graph 3892 nodes, for certain values, one or both of the sub-graphs contain more than half the nodes from Perception. Therefore, a compromise has to be made so that both sub-graphs do not drastically intersect between themselves. However, both should contain a minimum amount of knowledge and relations to be useful for CB and Bisociative Knowledge Discovery. From Table 2, an interesting improvement in the size of the sub-graphs happens when changes from 0:05 to 0:1. With 0:5 the tness function f does not increase, implying that the limit of the graph has been reached as the size of both sub-graphs are equal and maximum.

For the second experiment, we set = 0:1 in order to limit the intersection between the two sub-graphs to 10% of their combined size. A list of results is present in Table 3, with all the bridge nodes having degree of 2. The tness declines with the increasing unbalancing between the sub-graphs S0 and S1. In Figs (6) we show some of the structures of the nearby connections. It is interesting to observe the relations between connected domains for the sloth, aquarium and fridge nodes. We nd the last case peculiar, as we did not knew of a heavy and cool (or cold?) trance band. For the remaining bridge nodes, we leave their insight to the reader’s judgement.

(a) sloth bridge node.

(b) node.

aquarium bridge (c) fridge bridge node. In this work we proposed an evolutionary approach to support computational concept generation systems and knowledge discovery. Building on the work of Nagel [ 6 ], our work allows the discovery of knowledge divisions in large semantic graphs and the identication of possible key concepts which interconnect the sub-graphs. The algorithm supports various parameters to ne tune this division process in accordance with real world knowledge bases, so that dierent relations between knowledge domains can be researched and hopefully, give possibility to new insights between those domains. Lastly, by using a high performance algorithm, the exploratory process can be done in useful time. In the future we expect to improve our approach by experimenting with graph similarity. It would also be interesting to use a form of feedback loop by integrating a concept generating algorithm. This way, the system would direct its search towards bridging nodes and sub-graphs that would be more useful to the task that follows the GA.

Acknowledgements. The authors acknowledge the nancial support from the iCIS (Intelligent Computing in the Internet of Services) project (CENTRO07-0224-FEDER-002003) and from the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under the ConCreTe FET-Open project (grant number 611733) and the PROSECCO FET-Proactive project (grant number 600653).

References

1. Michael R . Berthold, editor. Bisociative Knowledge Discovery . Volume 7250 of Lecture Notes in Computer Science , Springer Berlin Heidelberg, 2012 .

2. Corinna Cortes and Vladimir Vapnik . Support-vector networks . Machine Learning , 20 ( 3 ): 273297 , 1995 .

3. Matja” Jur†i£, Bojan Cestnik, Tanja Urban£i£, and Nada Lavra£. Cross-domain literature mining: Finding bridging concepts with crossbee . In Proceedings of the 3rd International Conference on Computational Creativity , pages 3340 , 2012 .

4. Arthur Koestler . The Act of Creation . New York:Macmillan, 1964 .

5. Tobias Ktter , Kilian Thiel, and Michael R Berthold. Domain bridging associations support creativity . 2010 .

6. Uwe Nagel , Kilian Thiel, Tobias Ktter, Dawid Piatek, and Michael R. Berthold . Towards discovery of subgraph bisociations . In Michael R. Berthold, editor, Bisociative Knowledge Discovery , volume 7250 of Lecture Notes in Computer Science , pages 263284 . Springer Berlin Heidelberg, 2012 .

7. F Pereira . Creativity and articial intelligence: a conceptual blending approach . Berlin: Mouton de Gruyter, 2007 .

8. Paulo Ribeiro , Francisco C. Pereira, Bruno Marques, Bruno Leitªo, and Amlcar Cardoso . A model for creativity in creature generation . In Proceedings of the 4th Conference on Games Development (GAME ON'03) . EuroSIS / University of Wolverhampton, 2003 .

9. Tom De Smedt. Modeling Creativity: Case Studies in Python . Uitgeverij UPA University Press Antwerp, 2013 .

10. Don R Swanson. Fish oil, raynaud's syndrome, and undiscovered public knowledge . Perspectives in biology and medicine , 30 ( 1 ): 718 , 1986 .

11. Don R Swanson. Two medical literatures that are logically but not bibliographically connected . Journal of the American Society for Information Science , 38 ( 4 ): 228 233 , 1987 .