Domain Bridging Associations Support Creativity Tobias Kotter, Kilian Thiel, and Michael R. Berthold Nycomed-Chair for Bioinformatics and Information Mining, University of Konstanz, Box M712, 78484 Konstanz, Germany Tobias.Koetter@uni-Konstanz.de Abstract. This paper proposes a new approach to support creativity through assisting the discovery of unexpected associations across di erent domains. This is achieved by integrating information from heterogeneous domains into a single network, enabling the interactive discovery of links across the corresponding information resources. We discuss three di erent pattern of domain crossing associations in this context. 1 Data-driven Creativity Support The amount of available data scientists have access to (and should consider when making decisions) continues to grow at a breath-taking pace. To make things worse, scientists work increasingly in interdisciplinary teams where information needs to be considered not only from one research eld but from a wide variety of di erent domains. Finding the relevant piece of information in such environments is dicult since no single person knows all of the necessary details. In addition, individuals do not know exactly where to look or what to look for. Classical information retrieval systems enforce the formulation of questions or queries which, for unfamiliar domains or domains that are completely unknown, is dicult if not impossible. Methods that suggest unknown and interesting pieces of information, potentially relevant to an already-known domain can help to nd a focus or encourage new ideas and spark new insights. Such methods do not necessarily answer given queries in the way traditional information retrieval systems do, but instead suggest interesting and new information, ultimately supporting creativity and outside-the-box thinking. In [1] Weisberg stipulates that a creative process is based on the ripeness of an idea and the depth of knowledge. According to Weisberg this means that the more one knows, the more likely it is that innovation is produced. According to Arthur Koestler [2] a creative act, such as producing innovation, is performed by operating on several planes, or domains of information. In order to support creativity and help trigger new innovations, we propose the integration of data from various di erent domains into one single network, thus enabling to model the concept of domain-crossing associations. These domain-bridging associations do not generate new hypotheses or ideas automatically, but aim to support creative thinking by discovering interesting relations 200 Fig. 1. Association vs. Bisociation between seemingly unconnected concepts, therefore helping to fuse diverse domains. 2 Bisociation and Bisociative Networks The term bisociation has been introduced by Arthur Koestler in [2]. He introduced bisociation as a theory to describe the creative act in humor, science and art. In contrast to an association representing a relation between concepts within one domain, a bisociation fuses the information in multiple domains by nding a (usually indirect) connection between them (see Fig 1). Generally a domain can be seen as a set of concepts from the same eld or area of knowledge. A popular example of a Bisociation is the theory of gravity by Isaac Newton, which fuses the previously Aristotelian two-world system of sub-lunar and super-lunar physics. Even though not all creative discoveries are based on bisociation, many of them have been made by associating semantically distant concepts. Once such a connection has been found, it is no longer an unexpected connection and frequently even turns into \common sense". A citation of Henri Poincare also describes the combination of semantically distant concepts: \Among chosen combinations the most fertile will often be those formed of elements drawn from domains which are far apart... Most combinations so formed would be entirely sterile; but certain among them, very rare, are the most fruitful of all." In order to nd bisociations, data from di erent domains has to be integrated. Bisociative Networks (BisoNets) [3] aim to address this problem by supporting the integration of both semantically meaningful information as well as loosely coupled information fragments. They are based on a exible k-partite graph structure, which consists of nodes representing units of information or concepts and edges representing their relations. Each partition of a BisoNet contains a certain type of concepts or relations e.g. terms, documents, genes or experiments. BisoNets model the main characteristics of the integrated information repositories without storing all the more detailed data underneath this piece of information. By focusing on the concepts and their relations alone, BisoNets therefore allow huge amounts of data to be integrated. 201 3 Patterns of Bisociation Once the information in forms of concepts and relations is combined in the network it can be analyzed and mined for new, unexpected, and hopefully interesting pieces of information to support creative discoveries. One way of doing this is by identifying interesting patterns in the BisoNets. One class of patterns is bisociation. A formal de nition of a bisociation in the context of BisoNets is the following1: \A bisociation is a link that connects concepts from two or more domains, which are unconnected depending on the speci c view by which the domains are de ned." A domain in a BisoNet is a set of concepts. Depending on the view, a domain can either consist of concepts of one type, or bundle concepts of many types. So far, we have considered two di erent view types, one depending on the user's interest and a second depending on the applied graph analysis algorithms. The rst view creates the domain according to the user's speci cations. Thereby the subjective view of the data plays an important role; the elds of knowledge vary and hence are di erently de ned for each user. The second view is de ned by the structure of the graph, e.g. the level of detail and is extracted by the a graph summarization or abstraction algorithm, leading to a user-independent view. Di erent types of such algorithmic views can be de ned. Once the domains have been de ned by a given view, the main part of a bisociation, the link that connects concepts from di erent domains, can be identi ed. A link can be a single concept, a sub graph or any other type of relation. Fig. 2. Example of a Bisociative Network Figure 2 depicts an example BisoNet. The view is the surrounding frame that de nes the domains. Each domain is depicted in a di erent shade and contains concept types represented by dotted lines. The concepts and relations of the BisoNet are depicted as circles whereas links connect concepts and their relations. An example of a bisociation that connects concepts from di erent domains is depicted by the bold path in the network. The di erent types of bisociation are described in more detail below. 1 Result from discussions within the EU FP7 Project BISON. 202 Gene Protein Ice Fig. 3. Bridging concept example Gene Text Disease Gene1 Gene7 ... ... Term1 Term6 ... ... Doc1 Doc2 Fig. 4. Bridging graph example Soldiers Horse alters Gate protects Troy no entry passes Structure Add on Bloodbrain barrier protects Brain no entry passes alters Prodrug Trojan Horse Fig. 5. Example of structural similarity Bridging Concepts Bridging concepts are mostly ambiguous concepts or metaphors. In contrast to ambiguous concepts, which can lead to incorrect conclusions, metaphors can lead to new discoveries by connecting seemingly unrelated subjects. Bridging concepts are often used in humor [2] and riddles [4]. Bridging concepts connect dense sub graphs from di erent domains. Figure 3 depicts the homonym Ice as an example of a bridging concept. Ice is the name of a gene but also the name of the protein it encodes. Thus the concept belongs to the gene and the protein domain. Bridging Graphs Bridging graphs are sub-graphs that connect concepts from di erent domains. They lead to new insights by connecting domains that at rst glance do not appear to have anything in common. An example of a bridging graph is the discovery of Archimedes while he was having a bath. As he got into the tub he noticed that the level of the water rose. By connecting the rise of the water level with his body as he immersed into the water he realized that this e ect can be used in general to determine the volume of a body and is today known as the Archimedes' Principle. A bridging graph could also connect two concepts from the same domain via a connection running through a previously unknown domain. Figure 4 depicts a bridging graph that connects several genes of the same domain via documents that all describe the same disease. Structural similarity Bisociations based on structural similarity are represented by sub graphs of two di erent domains with a similar structure. This is the most abstract pattern of bisociation discussed here, which potentially leads to new discoveries by linking domains that do not have any connection. Figure 5 depicts the structural similarity between a prodrug that passes the blood-brain 203 barrier and the soldiers that pass the gate of Troy hidden in a wooden horse. In both scenarios the barrier can only be passed by altering the appearance of the intruder. 4 Conclusion and Future work In this paper we discuss a new approach that aims to support creative thinking, ultimately leading to new insights. Bisociative networks (BisoNets) provide an environment that fosters the curiosity to dig deeper into newly discovered insights by allowing to discover new connections between concepts and bridging the gap between previously unconnected domains. We have discussed three di erent notions of bisociation: bridging concepts, bridging graphs and structural similarity. In addition to de ning more patterns of bisociation we will evaluate existing graph-mining algorithms to nd di erent types of bisociations such as betweenness centralities [5] to discover bridging concepts or minimum spanning trees [6] to identify bridging graphs. Structural similarity might be discovered by using role detection algorithms [7] or graph kernels that take the neighborhood of each node into account. Acknowledgment We would like to thank the members of the EU Bison project for many fruitful discussions during the development of BisoNets. The work presented in this paper was supported by a European Commission grant under the 7th Framework Programme FP7-ICT-2007-C FET-Open, project no. BISON-211898. References 1. R.W. Weisberg. Creativity and knowledge: A challenge to theories. Handbook of creativity, 226:251, 1999. 2. Arthur Koestler. The Act of Creation. Macmillan, 1964. 3. Michael R. Berthold, Fabian Dill, Tobias Kotter, and Kilian Thiel. Supporting creativity: Towards associative discovery of new insights. In Proceedings of PAKDD 2008, 2008. 4. John M. Dienhart. A linguistic look at riddles. Journal of Pragmatics, 31(1):95 { 125, 1999. 5. Ulrik Brandes. A faster algorithm for betweenness centrality. Journal of Mathemat- ical Sociology, 25:163{177, 2001. 6. Joseph B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7, 1956. 7. Stephen P. Borgatti and Martin G. Everett. Two algorithms for computing regular equivalence. Social Networks, 15(4):361{376, December 1993.