=Paper=
{{Paper
|id=Vol-1520/paper11
|storemode=property
|title=Seeking Divisions of Domains on Semantic Networks by Evolutionary Bridging
|pdfUrl=https://ceur-ws.org/Vol-1520/paper11.pdf
|volume=Vol-1520
|dblpUrl=https://dblp.org/rec/conf/iccbr/GoncalvesMCC15
}}
==Seeking Divisions of Domains on Semantic Networks by Evolutionary Bridging==
https://ceur-ws.org/Vol-1520/paper11.pdf
113
Seeking Divisions of Domains on Semantic
Networks by Evolutionary Bridging
João Gonçalves, Pedro Martins, António Cruz, and Amílcar Cardoso
CISUC, Department of Informatics Engineering, University of Coimbra
{jcgonc,pjmm}@dei.uc.pt
antonioc@student.dei.uc.pt
amilcar@dei.uc.pt
Abstract. Computational Creativity systems based on Conceptual Blend-
ing (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.
1 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 evolu-
tionary 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 com-
putational concept generation techniques, such as CB and Bisociative Knowledge
Discovery, among other applications. As the amount of available knowledge dra-
matically 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 ci-
tations 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.
114
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.
M2
M1
(a) (b)
Fig. 1: Two domains connected by a single concept (left: adapted from [1]) and
the juxtaposition of two frames of reference in Koestler's Bisociation (right:
adapted from [4]).
A similar work by Nagel et al. [6] introduces a formalised spreading activa-
tion 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 juxta-
pose 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, de ned 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 of-
fer 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.
115
The cardinality of each graph structure is identi ed by the symbol #. Thus,
#S is the number of nodes existing in the graph S and we denote this quan-
tity 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 = {Nb }. Then, a unique path will
ow from one sub-graph to the other through the bridge node which has the
unique index b ∈ {1 . . . #S}. 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 ∈ {1 . . . #S} 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 de ned in (1):
1
|#S −#S | · log(#S0 + #S1 ) · 2−β(db −2) , if db ≥ 2
α #S0 +#S1 +1
f (S0 , S1 , db ) = 0 1 (1)
0, otherwise.
The tness function receives as arguments the sub-graphs S0 , S1 and the de-
gree 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 pe-
nalisation 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
116
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
speci c 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 de ne 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 48 59 69 77
37 47 58 68 76
46 57 67
56
Fig. 2: A combination of random translation movements (a random walk) starting at
the red node and given time, eventually leads to the green node. Best viewed in colour.
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 ∈ [0, 1[ represents a previous output of an uniform pseudo
random number generator. The number of nodes #S in the graph S is repre-
sented by the parameter s. The parameter γ ∈]0, +∞[ 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 γ → +∞, the translation tends to move each bridge node to
117
8
10
7
8
6
5
6
Percent
Percent
4
3 4
2
2
1
0 0
0 25 50 75 100 0 25 50 75 100
% of supergraph size % of supergraph size
(a) γ = 0.1 (b) γ = 2
Fig. 3: Probability Density Functions for two values of γ when using the bridge
jump mutation function (2).
one of the connected neighbours. For γ ∈]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 {Ni }, i ∈ {0, . . . #Si − 1} in the sub-graph
{Nk }, k ∈ {0, 1}. 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 , in-
cluding 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 itera-
tion of the function createSubgraphs() the algorithm expands from the current
neighbourhood of Oi . Thus, the function expandOneLevel() executes an equiv-
alent single iteration of a breadth rst search at the same deepness level. All the
nodes and edges are obtained from the graph S .
118
Algorithm 1 Function createSubgraphs()
function createSubgraphs(Nb , S )
{S0 , S1 } ← 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
≥ τ ∨ #S0 = 0 ∨ #S1 = 0
end function
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 sub-
graphs 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 τ ∈ 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 sub-
1 100
2000+2000 = 0.025% to 2000+2000 = 2.5%, a
graphs size to intersection ratio from
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 signi cant.
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
119
dragon_right_leg dragon_left_wing
dragon_left_leg dragon_right_wing
dragon_torso
dragon_tail
dragon_right_arm red
pw pw
pw pw reptiles
pw
pw team_color
color
dragon_left_arm
pw
isa
4.0
pw
food_consumption
dragon
dragon_head pw
taxonomicq
made_of
horse_head
food_consumption strength
creature
defense strength
flesh horse_left_front_leg
taxonomicq
pw
made_of
pw
2.0 horse
defense
pw
horse_right_front_leg
pw
pw horse_torso
pw
isa color pw
team_color
horse_left_back_leg
horse_right_back_leg
horse_tail
equines green brown
(a) 89 node graph. (b) Horse-Dragon graph.
Fig. 4: Structure of the 89 node and Horse-Dragon graphs. The highest rated
nodes are shown coloured. Best viewed in colour.
Blending, supplied by the authors of [8]. This semantic graph contains 32 rela-
tions 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 de nes 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
3
mutation rate of 100%, no crossover and a maximum number of 10 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 sub-
graphs included the nodes labelled 17, 95 and the bridge node with label 56.
Afterwards, we proceeded with the experiments on the three semantic graphs.
Table 1: Fitness scores f for the four highest rated bridge nodes of the Horse-
Dragon semantic graph.
f degree(Nb ) label(Nb ) #S0 #S1
3.989 2 creature 15 15
3.989 2 esh 15 15
0.249 3 4 15 15
0.249 3 2 15 15
120
Fig. 5: Optimal sub-graph con guration of the 111 node test graph showing bridge
node (red), intersection nodes (pink) and the two created sub-domains (green and cyan)
each with a depth of 8 nodes starting at the bridge node. Calculated with intersection
tolerance τ = 0. Best viewed in colour.
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 in uences 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 in-
tersect between themselves. However, both should contain a minimum amount
of knowledge and relations to be useful for CB and Bisociative Knowledge Dis-
covery. 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
121
Table 3: Fitness score f for 22 bridge
Table 2: Fitness scores f of the highest
nodes, from the Perception semantic
rated bridge nodes for the Perception se-
graph with τ = 0.1.
mantic graph when varying τ .
f degree(Nb ) label(Nb ) #S0 #S1 #(S0 ∩ S1 )
τ f degree(Nb ) label(Nb ) #S0 #S1 #(S0 ∩ S1 )
7.70 2 Times 1919 1991 98
0.00 4.35 2 panther 47 46 0
0.05 7.07 2 Jerry Springer 586 586 7 7.52 2 Athens 1474 1522 62
0.10 7.70 2 Times 1919 1991 98 7.07 2 Jerry Springer 586 586 7
0.15 8.19 2 Jesus Christ 2173 2199 119 7.03 2 sloth 1242 1177 32
0.20 8.27 2 Pulp Fiction 2121 2132 186 6.98 2 herd 714 729 4
0.25 8.30 2 wrestling 2264 2281 291 6.96 2 fox 984 1031 27
0.33 8.63 2 ashes 3039 3054 943
6.78 2 pilot 529 522 11
0.50 8.95 2 emerald 3868 3868 3868
5.79 2 aquarium 949 820 13
0.75 8.95 2 chromosome 3868 3868 3868
4.99 2 fridge 427 514 1
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) aquarium bridge (c) fridge bridge node.
node.
Fig. 6: Three examples of bridging nodes and their neighborhood present in Table 3.
4 Conclusions
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 seman-
tic graphs and the identi cation 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
122
new insights between those domains. Lastly, by using a high performance algo-
rithm, 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 (CENTRO-
07-0224-FEDER-002003) and from the Future and Emerging Technologies (FET)
programme within the Seventh Framework Programme for Research of the Eu-
ropean 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. InProceedings of the
3rd International Conference on Computational Creativity, pages 3340, 2012.
4. Arthur Koestler. The Act of Creation. New York:Macmillan, 1964.
5. Tobias Kötter, Kilian Thiel, and Michael R Berthold. Domain bridging associations
support creativity. 2010.
6. Uwe Nagel, Kilian Thiel, Tobias Kötter, Dawid Piatek, and Michael R. Berthold.
Biso-
Towards discovery of subgraph bisociations. In Michael R. Berthold, editor,
ciative Knowledge Discovery, volume 7250 of Lecture Notes in Computer Science,
pages 263284. Springer Berlin Heidelberg, 2012.
7. F Pereira. Creativity and arti cial intelligence: a conceptual blending approach.
Berlin: Mouton de Gruyter, 2007.
8. Paulo Ribeiro, Francisco C. Pereira, Bruno Marques, Bruno Leitão, and Amílcar
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.