João Gama

Antoine Cornuéjols

2 WG3 -Resource Aware Distributed Knowledge Discovery

The challenge of ubiquitous computing

Two major technological evolutions have the potential to deeply modify our relationship with our environment:

• With the advent of widely available and cheap computer power, inanimate things are coming to life. Simple objects that surround us are gaining sensors, computational power, and actuators, and are changing from static, inanimate objects into adaptive, reactive systems that have thus the potential to become more useful and efficient. Smart Devices

• In parallel, the explosion of networks of all kinds, from long distance high bandwidth ones to local low bandwidth wifi systems, offers new unknown possibilities for the development and self-organization of communities of intelligent communicating appliances. Networks

It is now possible to envision having intelligent appliances and, in general, ambient intelligence aimed at easing our life. [START_REF]Ambient Intelligence -The Evolution of Technology, Communication and Cognition Towards the Future of Human-Computer Interaction[END_REF] gives illustrative and futurist scenarios. But this requires to know how to embed these new heterogeneous appliances with the right kind of sensors and of intelligence in order to give them the capability to sense their environment and be able to communicate and cooperate, while at the same time be able to interact gracefully and naturally with human users. Furthermore, these intelligent items, and the networks they will be part of, require the ability to adapt continuously to ever changing environmental conditions and needs of the users. The pervasiveness of mobile phones in the population attracts the attention of the actors in this sector to the wealth of data that could be extracted from simple measurements automatically sent by the phones during their lifetime.

It is therefore clear that a wide spectrum of learning abilities is in demand for these new developments to take place. First, smart devices adaptable to a diversity of users and ready to accompany them for years, will need to:

• be able to sense their environment and receive data from other devices, and make sense of the gathered data. This is related to feature selection, data cleaning and data fusion issues. Sensing and Acting • be able to adapt continuously to changing environmental conditions (including their own condition) and evolving user habits and needs. This touches both short-term and real-time adaptiveness and longer term capability for incremental learning and changes detection. Adaptation

• be capable of predictive self-diagnosis. A significant and useful intelligence characteristic is diagnostics -not only after failure has occurred, but also predictive (before failure) and advisory (providing maintenance instructions). The development of such self-configuring, self-optimizing, and self-repairing systems is a major scientific and engineering challenge.

To meet this challenge, Autonomic Computing requires extensive use of AI techniques such as automated real-time reasoning and decision making, machine learning, and planning. Thus, Autonomic Computing promises to be a major application area for AI, a driver for basic research, and a cross-pollinator across many sub-fields of AI.

Sel-Diagnosis

• be resource-aware because of the real-time constraint and of limited computer, battery power and communication resources. Indeed, the development of ambient intelligence forces us to enter the world of limited rationality where the availability of time, computer and communication resources must enter the reasoning process. Resource awareness The last twenty years or so have witnessed large progress in machine learning and in its capability to handle real-world applications. Nevertheless, machine learning so far has mostly centered on one-shot data analysis from homogeneous and stationary data, and on centralized algorithms. Nowadays we are faced with tremendous amount of distributed data that could be generated from the ever increasing number of smart devices. In most cases, this data is transient, and may not be stored in permanent relations. A large part, if not the whole of the theory of machine learning (e.g. PAC learning model), relies on the assumption that the data points are independent and identically distributed, meaning that the underlying generative process is stationary.

Example: Forecast of Electrical Load

An illustrative Problem. Electricity distribution companies usually set their management operators on SCADA/DMS products (Supervisory Control and Data Acquisition / Distribution Management Systems). One of their important tasks is to forecast the electrical load (electricity demand) for a given subnetwork of consumers. Load forecast is a relevant auxiliary tool for operational management of an electricity distribution network, since it enables the identification of critical points in load evolution, allowing necessary corrections within available time, and planning strategies for different horizon.

In this context, data is collected from a set of sensors distributed all around the network. Sensors can send information at different time scales, speed, and granularity. Data continuously flow eventually at high-speed, in a dynamic and time-changing environment. Data mining in this context requires continuously processing of the incoming data monitoring trends, and detecting changes. Traditional one-shot systems, memory based, trained from fixed training sets and generating static models are not prepared to process the high detailed data available, they are not able to continuously maintain a predictive model consistent with the actual state of the nature, nor are they ready to quickly react to changes. Moreover, with the evolution of hardware components, these sensors are acquiring computational power. The challenge will be to run the predictive model in the sensors itself.

A World in Movement.

The constraints we have enumerated implies to switch from one-shot singleagent learning tasks to a lifelong and spatially pervasive perspective. In the novel lifelong perspective induced by ubiquitous environments, finite training sets, static models, and stationary distributions will have to be completely thought anew. In that context, Data Mining approaches involving fixed training sets, static models and evaluation strategies are obsolete.

All these aspects entails the new characteristics for the data: Data Characteristics • Data are made available through unlimited streams that continuously flow, eventually at high-speed, over time;

• The underlying regularities may evolve over time rather than be stationary

• The data can no longer be considered as independent and identically distributed.

• The data is now often spatially as well as time situated.

But does the existence of ubiquitous environments really change the problem of machine learning? Wouldn't simple adaptations to existing learning algorithms suffice to cope with the new needs described in the foregoing? These new concerns might indeed appear rather abstract, and with no visible direct impact on machine learning techniques. Quite to the contrary, however, even very basic operations that are at the core of learning methods are challenged in the new setting. For instance, consider the standard approach to cluster variables (columns in a work-matrix). In a batch scenario, where all data is available and stored in a working matrix, we can apply any clustering algorithm over the transpose of the working matrix. In a scenario where data evolves over time, this is not possible, because the transpose operator is a blocking operator [START_REF] Barbara | Requirements for clustering data streams[END_REF]: the first output tuple is available only after preocessing all the input tuples. Now, think of the computation of the entropy of a collection of data when this collection comes as a data stream which is no longer finite, the domain of variables can be huge, and where the number of classes of objects is not known a priori; or think on continuous maintenance the k-most frequent items. And then, what becomes of statistical computations when the learner can only afford a one pass on each data piece because of time and memory constraints and has to decide on the fly what is relevant and must be further processed and what is redundant or not representative and could be discarded. These are but two examples of a clear need for new algorithmic approaches in the KDubiq framework.

Data Mining is thus faced with new challenges. All of them share common issues: distributed continuously flow of data generated by evolving distributions, the domains involved (the set of attribute-values) can be also huge, and computation resources (processing power, storage, bandwidth, and battery power) are limited.

In short, machine learning algorithms will have to enter the world of limited rationality, e.g. rational decisions are not feasible in practice due to the finite computational resources. To reshape, ubiquitous data mining implies new requirements to be considered. The new constraints include:

Limited Resources • The algorithms will have to use limited computational resources (in terms of computations, space and time)

• The algorithms will have only a limited direct access to data and may have to communicate with other agents on limited bandwidth resources.

• In a community of smart devices geared to ease the life of users in real time, answers will have to be ready in an anytime protocol.

• Overall, data gathering and data (pre-)processing will be distributed.

In this chapter we discuss algorithm issues related to advanced data analysis in dynamic environments using devices with limited resources. In the contexts we are interested in data is distributed data, flowing eventually at high-speed. We identify the limitations of the current Machine Learning theory and practice and identify the most desirable characteristics for a learning algorithm in these scenarios. The analysis follow three main dimensions: learning in resource aware devices, distributed data, and continuous flow of data. These dimensions define the organization of the chapter.

The Challenge of Limited Resources

Ubiquitous environments mark the end of the area of the single and unlimited learning agent paradigm. The fact that a multitude of simple and situated agents are now to form a new kind of anytime responsive system implies a profound reexamination of the data processing and data mining tasks. The main point here is the degree of autonomy of the agents. We would like to maximize the level of autonomy, requiring the ability to process their own data, and make local decisions. Most important, agents might communicate with neighbors, minimizing communication costs, to make collective and rational decisions.

Autonomy Traditional data mining applications call for an off-line centralized data analysis processing over an existing (very) large database. In Ubiquitous Data Mining (UDM), every one of the assumptions that underlie this picture are challenged. Indeed, in this setting, data is transient, obtained through a web of, possibly heterogeneous, sensors with limited computational, memory and communication bandwidth capabilities. Furthermore, both for reasons of scarce resources and because of real-time demands, data must be processed, at least partly, on the fly and locally. Applications in fusion of environmental sensor measures, in the analysis of information gathered by web/blog crawlers that independently sip through collections of texts and links, in analysis and control of distributed communication networks have been already cited. But many more are coming fast in scientific, business and industrial contexts.

These new constraints challenge the existing data mining techniques and require a significant research effort to overcome their current limitations.

Resource Limitation First of all, at the level of each individual device or agent, the limitations on both computing power, memory space and time will constrain the type of processing that can be done. For instance, floating point operations may be unavailable, and processing power may be severely limited beyond the one required to run the normal operations of the device. Therefore, algorithms for local data mining must require very low complexity processes, possibly at the cost of degraded output. In many settings, sensor nodes and computing units (e.g. handheld devices) lack sufficient memory to run classical data mining techniques which require that the results of the intermediate processing steps be resident in memory over the processing time of the running algorithm. Data, often coming in the form of continuous streams, will have either to be partitioned into subsets small enough as to be tractable, or processed on a one-pass only basis. Furthermore, the locally available data may be too restricted to permit an informed enough data mining process, and queries will have to be addressed to other agents. Similarly, it is possible to envision cases where one device will have to recruit the computing power of other less busy agents to meet its own needs. In all these cases, this will require that the individual devices have sufficient self-monitoring capabilities so as to know when to ask for additional information or for help in the form of computing power.

Integration Secondly, at a more integrated level, several issues will need to be addressed. To begin with, at quite a basic level, the heterogeneity of the individual devices will introduce problems of communication when the set of measurements and the formats in which they are expressed will differ among agents. For instance, in sensor networks, work on a sensor model language called sensorML has been started as part of the Opengeospatial Consortium. It uses XML to encode and describe sensor models. The whole process ranging from input to output and associated parameters are described using this language. Apart from the issue of heterogeneousness of the devices, the whole system will have to be responsive even in face of faulty or missing measurements, drifting characteristics of the sensors and generally haphazardous malfunctions. Furthermore, measured data might well be redundant on one side, but also different in their own right because issued from different locations and aimed at different tasks. These characteristics will require that methods for the management of the system be developed. With regards to learning, meta-learning methods will be needed in order to distribute learning processes when needed and to integrate the results on a anytime basis. Since the architecture of the system may well not incorporate a global master device, these management capabilities will have themselves to be distributed and part of the self-aware computing capacities of the individual agents. In this respect, much remains to be done, and we do not have, at this time, a mature methodology to meet that challenge.

Bandwidth Limitation The limited communication bandwidth between the agents poses other questions. In-network knowledge integration is an open research issue in Ubiquitous Data Mining. It has impact on many problems like: merging of clustering models, of classification decisions and frequent patterns mining. Controlling the accuracy of the resulted integrated knowledge is fast becoming a critical research question. Exchange of data should not be done without some form of preprocessing that clean the data, selects a right degree of precision, remove outliers and generally filter out irrelevant or non representative measurements. Techniques exist for preprocessing data in data mining, however, they often assume that data is available in its entirety and that sufficient computing power and memory space is available. As will be seen in more details in the sections devoted to data streaming, algorithms have to be completely reconsidered in the limited rationality and lifelong setting. At the other end of the learning process, the results of learning that have to be stored or shared between agents should require only compact transmissions and storage.

Overall, new techniques for intelligent sampling, to use generate synopsis and summarized information, and to output approximate solutions are required. But this brings a new problem. Since the degree of approximation is dependent on the specifics of the ubiquitous system and on the application, ubiquitous data mining systems must be able to adapt to the characteristics of the problem and to their own limitations. In other words, they must be self-aware to a certain degree in order to optimize their own parameters and deliver on-time the best possible analysis. In the field of data mining per se, a powerful meta-learning approach has been developed since the 90s, that of ensemble learning [START_REF] Schapire | Strength of weak learnability[END_REF]. The technique makes use of the combination of multiple models learned by weak learners in order to boost the overall performance of the learning system. In the context of ubiquitous data mining, it is tempting to view these ensemble learning techniques as means to turn the curse of distributed and limited data mining algorithms into a strength, by using local models as base learners. Nevertheless, so far, few works [START_REF] Oza | Online Ensemble Learning[END_REF] have addressed the problem of incremental, online, and distributed maintenance of ensembles of decision models [START_REF] Kargupta | Orthogonal Decision Trees[END_REF].

A lifelong perspective for Machine Learning

Aside the computational and communication problems inherent in ubiquitous environments, there are issues linked to the nature of the data themselves. As soon as one is contemplating lifelong learning tasks with data originating from various places, new problems arise. Mostly, they resort to two categories of questions. The first one is related to the fact that data are geographically situated. The second is related to the temporal nature of the data generation of which several aspects are important for learning. Namely, data now arrive in streams and can only be processed on a one-pass basis, data is no longer i.i.d. and the underlying regularities may change over time.

In the following, these two categories of problems are examined in turn.

Mining spatially tagged data. There are now several data generation environments where the nodes generating the data are spatially spread and interrelated and where these relations are meaningful and important for data mining tasks. New types of applications are thus emerging in health services, in environmental monitoring or in distributed and real-time control of vehicles. It is also possible to record characteristics of the landscape itself as in satellite recordings and to monitor the spatial location of objects. The latter has become very popular with the emergence of mobile phones, GPS and RFID. In sensor networks, for instance, sensors are often explicitly spatially related to each other and this spatial information can be considered as a king of meta tagging of the data. In other applications, where, for instance, the agents themselves are moving (e.g. vehicles on roads), GPS information can accompany the set of measurements made. In all of these applications, the spatial information is essential in the processing of the data and the discovery of meaningful regularities. So far, works on spatial data mining has been scarce even though applications in satellite remote sensing and geographical databases have spurred a growing interest in methods and techniques to augment databases management and mining with spatial reasoning capabilities.

The time situation of data. The fact that, in ubiquitous environments, data are produced on a real-time basis, or, at least, in a sequential fashion, and that the environment and the task at hand may change over time, profoundly modifies the underlying assumptions on which rest most of the existing learning techniques and demands the development of new principles and new algorithms.

In the following, we discuss these new set of issues along two main directions. The first one deals with the sequential nature of data, the fact that it comes as streams of indefinite length and must be processed with limited resources. The second ones discusses the consequences of the fact that data can no longer be considered as independently and identically distributed.

Distributed Data Mining

The combination of distributed systems and the pervasive/ubiquitous computing paradigms can lead into the area of distributed data mining. It is a broad area characterized by combinations of multiple learning algorithms as well as multiple learning problems. These learning problems are also directed by constraints such as security, privacy, communication costs and energy restrictions. Autonomous Agents The idea of ubiquitous knowledge discovery and autonomous agents is closely related. An agent need to be able to discover, sense, learn, and act on its own. The research on agents is extensive. There are basically two types of agent architectures, one in which the agents are tied to one node and one in which the agents move between nodes. In systems such as Objectspace's Voyager, the agents move between the machines, while a peer-to-peer system such as JXTA only allows agents to be tied to the nodes. In both systems the agents either reside or migrate to nodes that are prepared for receiving. Distributed objects can be seen as a premise for agents: only some additional characteristics need to be adorned to the distributed object. It has been noted that agents normally differ from machine learning algorithms in that the nature of the problems addressed by the agents are larger than those traditionally associated with machine learning [START_REF] Davies | Agent-Based Knowledge Discovery[END_REF]. Intelligent agents are more involved software than just an agent, which can be compared to a distributed object. The term distributed object perhaps belongs to systems in which the focus is more on the distributed system than on the interaction between the agents. One such example is the Java Agents for Meta-Learning (JAM) system developed by Stolfo et al. [START_REF] Stolfo | JAM: Java agents for meta-learning over distributed databases[END_REF]. The agent can communicate with other agents using the Knowledge Query and Manipulation Language (KQML) [START_REF] Finin | KQML as an Agent Communication Language[END_REF] together with the Knowledge Interchange Formalism (KVI) [START_REF] Genesereth | Knowledge Interchange Format, Version 3.0 Reference Manual[END_REF] agent information exchange format. These communications and associated exchange formats allow the agent to express first order requests. A complementary system for agent corporation is the Open Agent Architecture (OOA) [START_REF] Martin | The Open Agent Architecture: a framework for building distributed software systems[END_REF]. In some cases the agents will query other agents and perhaps exchange examples or models. To exchange an example sounds simple, but it requires that the data format is agreed to and understood on both sides of the exchange. Research in general purpose languages for model exange is recent. An example is the Predictive Model Markup Language (PMML), a XML mark up language to describe statistical and data mining models.

The strong limitations of the first scenario is discussed in [START_REF] Park | Data Mining Handbook, chapter Distributed Data Mining: Algorithms, Systems, and Applications[END_REF]. The authors point out 'a mismatch between the architecture of most off-the-shelf data mining algorithms and the needs of mining systems for distributed applications'. Such mismatch may cause a bottleneck in many emerging applications. Some hardware limitations related to the limited bandwidth channels. Most important, in applications like monitoring, centralized solutions introduce delays in event detection and reaction, that can make mining systems useless.

Sensor Networks

Restrictions like size and power source will define how complex is the processing performed in the sensors. We may have in one extreme centralized systems and in the other extreme completely distributed systems, where almost all the intelligent processing is performed in the sensors. The solution considered in Ubuiquitous Data Mining can broadly be seen as belonging to one of the following categories: data-centric, process-based or network-based:

Categories for Ubiquitous Data Mining • Data-centric solutions

The data is preprocessed before the actual learning phase takes place. It could be in the form of processing a subset of data such as sampling and load shedding. It also could be in the form of dimensionality reduction such as sketching. Finally it could be by summarizing the streaming data such as aggregation and creating data synopsis [START_REF] Babcock | Models and issues in data stream systems[END_REF] .

• Process-based solutions The focus of this category of approaches is to deal with the actual processing of the algorithm. Approximation and randomized algorithms are the traditional solutions used in this category [START_REF] Muthukrishnan | Data streams: algorithms and applications[END_REF]. Recently, sliding windows is used in a two-fold objective. The first is to capture the most recent output. The other objective is solve the problem of concept drift.

• Network-based solutions Different networking approaches can provide approximate results taking into consideration the limitations of ubiquitous computing environments. Peer-to-Peer (P2P) computing [START_REF] Datta | Distributed data mining in peer-to-peer networks[END_REF], clustering of sensor nodes and efficient routing [START_REF] Younis | Heed: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[END_REF], and grid computing [START_REF] Cannataro | Distributed data mining on the grid[END_REF] are typical approaches used in this category. In P2P computing, the data mining algorithm is executed locally onboard a sensor node or a handheld device. The algorithm allows message exchange in order to integrate local results. Approximate global model could be computed accordingly. Clustering of sensor nodes aims at prolonging the network life-time by choosing nodes with highest energy to be the cluster heads. Cluster heads then collect and aggregate data to be sent to the base station. In grid computing, a so-called knowledge grid is built to benefit from the services provided by the grid in the distributed data mining process. These services include information and resource management, communication and authentication.

Sensor networks can be used to detect the occurrence of complex events patterns with spatial and temporal characteristics. Traditionally, sensor networks communicate sensed data to a central server that runs offline data mining algorithms. In the KDUbiq perspective, analysis should be done done in situ using local information. The main difference is the conceptual framework. Current Data Mining techniques assume iid examples, static models, finite training sets, unrestricted resources. Even ignoring resources, they might be applied with high maintenance costs: retraining models from time to time. KDubiq approach (dynamic models that evolve over time, incorporating change detection mechanisms, taking into account the resources available) is the most appropriate option.

An Illustrative Example: Distributed Clustering. The scenario is in a sensor network where each sensor produce a continuous stream of data. Suppose we have m distributed sites, and each site i has a data source S t i at time t. The goal is to continuously maintain a k-means clustering of the points in S t = ∪ m i S t i . The distributed algorithm presented in Conquering the Divide: Continuous Clustering of Distributed Data Streams [START_REF] Graham Cormode | Conquering the divide: Continuous clustering of distributed data streams[END_REF] is based on the Furthest Point clustering. The base idea consists of selecting randomly the first cluster center c 1 among data points. Subsequent k -1 cluster centers are chosen as the points that are more distant from the previous centers c 1 , c 2 , ..., c i-1 , by maximizing the minimum distance to the centers. This algorithm requires k passes over training points. It has an interesting property. It ensures a 2-approximation of the optimal clustering. A skeleton of the proof is: Suppose a k + 1 iteration, producing k + 1 points separated by a distance at least D. The optimal k clustering must have a diameter at least D. By the triangular inequality the chosen clustering has diameter at most 2D. Based on the Furthest Point algorithm the authors developed a one pass clustering algorithm: the Parallel Guessing Clustering. The base idea consists of picking an arbitrary point as the first center, and for each incoming point p compute r p = min c∈C d(p, c). If r p > R Set C = C ∪ p. This strategy would be Ok, if we know R, the problem is that R is unknown in advance! The solution proposed in [START_REF] Graham Cormode | Conquering the divide: Continuous clustering of distributed data streams[END_REF] consists of making multiple guesses for R as (1 + ǫ/2), (1 + ǫ/2) 2 , (1 + ǫ/2) 3 , and run the algorithm in parallel. If a guess R generates more than k centers, implies R is smaller than the optimal radius (R o ). For a guess of R ≥ 2R o that find k or fewer centers, and generate a valid clustering.

Each local site maintains a Parallel Guessing Algorithm using its own data source. Whenever it reachs a solution, it sends to the coordinator the k centers and the radius R i . Each local only re-send information when the centers change. The coordinator site maintains a Furthest Point Algorithm over the centers sent by local sites.

Data Streams Data stream mining techniques use the above approaches in different data mining strategies including clustering, classification, frequent pattern discovery, time series analysis and change detection [START_REF]Learning from Data Streams -Processing techniques in Sensor Networks[END_REF]. While few of these techniques are resource-aware when applying the above solution approaches, others are not. This problem needs to be addressed in order to realize UDM algorithms in real-life applications. For example if a data stream mining technique uses an approximate solution to preserve the available memory with constant factor, the algorithm may run out of memory due to the extremely low availability of it in a ubiquitous computing environment. However, if the algorithm is resourceaware, the approximation factor can change over time in order to cope with the critically low availability of memory. The same analogy applies to the different available resources. This has been demonstrated in [START_REF] Gaber | A framework for resource-aware knowledge discovery in data streams: a holistic approach with its application to clustering[END_REF]. The area of adaptation and resource-awareness is still open. Many data stream mining algorithms are required to be resource-aware and adaptive in order to realize its applicability in ubiquitous computing environments.

Knowledge Discovery from Data Streams

In the last two decades, machine learning research and practice has focused on batch learning usually with small datasets. In batch learning, the whole training data is available to the algorithm, that outputs a decision model after processing the data eventually (or most of the times) multiple times. The rationale behind this practice is that examples are generated at random accordingly to some stationary probability distribution. Most learners use a greedy, hill-climbing search in the space of models.

Static versus Streaming

What distinguishes current data sets from earlier ones are the continuous flow of data and the automatic high-speed data feeds. We do not just have people who are entering information into a computer. Instead, we have computers entering data into each other [START_REF] Muthukrishnan | Data streams: algorithms and applications[END_REF]. Nowadays there are applications in which the data is best modeled not as persistent tables but rather as transient data streams. In some applications it is not feasible to load the arriving data into a traditional DataBase Management Systems (DBMS), and traditional DBMS are not designed to directly support the continuous queries required in these applications [START_REF] Babcock | Models and issues in data stream systems[END_REF].

Streaming Algorithms

Algorithms that process data streams deliver approximate solutions, providing a fast answer using few memory resources. They relax the requirement of an exact answer to an approximate answer within a small error range with high probability. In general, as the range of the error decreases the space of computational resources goes up. In some applications, mostly database oriented, an approximate answer should be within an admissible error margin. Some results on tail inequalities provided by statistics are useful to accomplish this goal. The basic general bounds on the tail probability of a random variable (that is, the probability that a random variable deviates greatly from its expectation) include the Markov, Chebyshev and Chernoff inequalities [START_REF] Motwani | Randomized Algorithms[END_REF].

Data Streams Management Systems developed a set of techniques that store compact stream summaries enough to approximately solve queries. All these approaches require a trade-off between accuracy and the amount of memory used to store the summaries, with an additional constrain of small time to process data items [START_REF] Muthukrishnan | Data streams: algorithms and applications[END_REF]. The most common problems end up to compute quantiles, frequent item sets, and to store frequent counts along with error bounds on their true frequency.

In the streaming model (see [START_REF] Muthukrishnan | Data streams: algorithms and applications[END_REF]), the input elements a 1 , a 2 , . . . , a j , . . . arrive sequentially, item by item and describe an underlying function A. Streaming models differ on how a i describe A. We can distinguish between:

1. Insert Only Model: once an element a i is seen, it can not be changed.

Insert-Delete Model: elements a i can be deleted or updated

From the viewpoint of a data streams management system, several research issues emerge. For instance, one such issue is related to the need of approximate query processing techniques in order to evaluate queries that require unbounded amount of memory. Sampling techniques have been used to handle situations where the flow rate of the input stream is faster than the query processor. One important question is raised by the existence of of blocking operators (e.g. aggregation and sorting) in the presence of unending streams. It is essential to identify them and to find ways to circumvent their blocking effect. The following table summarizes the main differences between traditional and stream data processing: When the samples of data are both spatially and time situated, data points can no longer be considered as independently and identically distributed, a fact that is compounded when the underlying generative process is itself changing over time.

One consequence is that the statistical theory of learning [START_REF] Vapnik | The nature of statistical learning theory[END_REF] does not hold anymore. In particular, the inductive criteria that are based on additive measures of cost (e.g. the empirical risk and the real risk associated with a candidate hypothesis) are no longer satisfactory. The question then becomes: how to replace this fundamental theory? Works on weak long term correlations exist in statistics, but they are still far from answering the challenge that faces machine learning in this respect.

Ordering Effects One interesting question concerns ordering effects: the fact that the result of a (on-line) learning session may depend on the order of presentation of the data points. This has usually been considered as a nuisance that one should try to get rid of. However, the order of the data points can clearly convey potentially useful information about the evolution of the underlying generative process, or even, this order could result from a clever and helpful teacher. In this case, one should on the contrary try to take advantage from this source of information. Apart from a few works in constructive induction and some pioneering works in inductive logic programming, almost everything remains to be done in this direction. Reasoning about the evolution of the learning process is also a potential research line that remains almost unexplored.

Concretely, data streams require that the learners be endowed with on-line or incremental learning capabilities. This means in particular that they should be able to process the data sequentially as they arrive and that they should be able to produce either decisions or hypotheses about the surrounding world in an anytime fashion. Since, their memory is limited and because the underlying generative process, or the task at hand, may change, they have to be able to measure the relevance of a piece of information over time, and be able to forget no longer relevant data pieces.

Questions about how to sample and summarize the data, how to carry on on-line learning are discussed below.

Where we Are

Recent developments in Machine Learning point out directions for learning in ubiquitous environments. For example, in [START_REF] Hulten | Catching up with the data: research issues in mining data streams[END_REF] the authors present a general method to learn from arbitrarily large databases. The method consists of deriving an upper bound for the learner's loss as a function of the number of examples used in each step of the algorithm. Then use this to minimize each step's number of examples, while guaranteeing that the model produced does not differ significantly from the one that would be obtained with infinite data. This general methodology has been successfully applied in k-means clustering [START_REF] Hulten | Catching up with the data: research issues in mining data streams[END_REF], decision trees [START_REF] Domingos | Mining High-Speed Data Streams[END_REF][START_REF] Hulten | Mining time-changing data streams[END_REF][START_REF] Gama | Accurate decision trees for mining highspeed data streams[END_REF], etc. The proposed method can be useful to solve one aspect of Learning in ubiquitous environments. Nevertheless many others remain unsolved. For example, learning from distributed data, we need efficient methods in minimizing the communication overheads between nodes. Work in this direction appears in [START_REF] Bar-Or | Hierarchical decision tree induction in distributed genomic databases[END_REF].

illustrative Algorithm. We have pointed out the necessity of new algorithms for clustering variables in the stream setting. The Online Divisive-Agglomerative Clustering (ODAC) system [START_REF] Rodrigues | Hierarchical clustering of time series data streams[END_REF] continuously maintains a treelike hierarchy of clusters that evolves with data. ODAC uses a top-down strategy. The splitting criterion is a correlation-based dissimilarity measure among time series, splitting each node by the farthest pair of streams, which defines the diameter of the cluster. In stationary environments expanding the structure leads to a decrease in the diameters of the clusters. The system uses a merge operator, that agglomerates two sibling clusters, in order to react to changes in the correlation structure between time series. The splitting and merge operators are triggered in response to changes in the diameters of existing clusters. The system is designed to process thousands of data streams that flow at high-rate. The main features of the system include update time and memory consumption that do not depend on the number of examples in the stream. Moreover, the time and memory required to process an example decreases whenever the cluster structure expands.

Approximation and Randomization techniques has been used to solve distributed streaming learning problems. Approximation allows answers that are correct within some fraction ǫ of error, while randomization allows a probability δ of failure. The base idea consists of mapping a very large input space to a small synopsis of size O( 1 ǫ 2 log( 1 δ )). Approximation and Randomization techniques has been used to solve problems like measuring the entropy of a stream, association rule mining frequent items [START_REF] Manku | Approximate frequency counts over data streams[END_REF], k-means clustering for distributed data streams using only local information [START_REF] Graham Cormode | Conquering the divide: Continuous clustering of distributed data streams[END_REF], etc.

illustrative Algorithm. Hash functions as been used to project attributes with huge domains into lower space dimensions. The Count-Min Sketch has been used to approximately solve point queries, range queries, and inner product queries. Here we present a simple couting example: How many times an item in high-speed stream as been seen so far.

A Count-Min Sketch is an array of w × d in size. Given a desired probabilty level (δ), and an admissible error (ǫ), w = 2/ǫ and d = log(1/δ). Each entry x in the stream, is mapped to one bucket per row. It uses d hash functions to map vector entries to [1..w]. At any time, the estimate x[j] is given by taking min k CM [k, h k (j)]. The important properties of this estimate are:

x[j] ≤ x[j] and xi ≤ ǫ × ||x i || 1 , with probability 1 -δ.
The idea of the agent's limited rationality lead us to ensemble models used to collectively solve problems. In [START_REF] Kargupta | Orthogonal Decision Trees[END_REF], the authors proposed a method that offer an effective way to construct a redundancy-free, accurate, and meaningful representation of large decision-tree ensembles often created by popular techniques such as Bagging, Boosting, Random Forests and many distributed and data stream mining algorithms.

Online, Anytime and Real-time Learning

The challenge problem for data mining is the ability to continuously maintain an accurate decision model. This requires learning algorithms that can modify the current model whenever new data is available at the rate of data arrival. Moreover, they should forget older information when data is outdated. In this context, the assumption that examples are generated at random according to a stationary probability distribution does not hold, at least in complex systems and for large periods of time.

In the presence of a non-stationary distribution, the learning system must incorporate some form of forgetting past and outdated information. Learning from data streams require incremental learning algorithms that take into account these changes in the data generating process. Solutions to these problems require new sampling and randomization techniques, and new approximate, incremental and decremental algorithms. In [START_REF] Hulten | Catching up with the data: research issues in mining data streams[END_REF], the authors identify desirable properties of learning systems that are able to mine continuous, high-volume, open-ended data streams as they arrive. Learning systems should be able to process examples and answering queries at the rate they arrive. Overall, some desirable properties for learning in data streams include: incrementality, online learning, constant time to process each example, single scan over the training set, and taking drift into account.

Cost-Performance Management Incremental learning is one fundamental aspect for the process of continuously adaptation of the decision model. The ability to update the decision model whenever new information is available is an important property, but it is not enough. Another required operator is the ability to forget past information [START_REF] Kifer | Detecting change in data streams[END_REF]. Some data stream models allow delete and update operators. Sliding windows models require forgetting old information. In all these situations the incremental property is not enough. Learning algorithms need forgetting operators that reverse learning: decremental unlearning [START_REF] Cauwenberghs | Incremental and decremental support vector machine learning[END_REF].

The incremental and decremental issues requires a continuous maintenance and updating of the decision model as new data is available. Of course, there is a trade-off between the cost of update and the gain in performance we may obtain. The update of model depends of the complexity of its representation language. For instance, very simple models, using few free-parameters, are easy to adapt in face of changes. Small and potentially insignificant variations in the data will not result in unwarranted changes in the learned regularities. The variance of the hypothesis class is said to be limited. However, the downside is an associated high bias. The hypothesis space cannot accommodate a large variety of data dependencies. This is known as the bias-variance tradeoff. This tradeoff is fundamental in classical one-shot learning. It becomes even more so in on-line learning. In addition, the more complex the hypothesis space (the larger the number of effective parameters), the more costly are the update operations. Effective means of controlling it must be devised. Continuous learning therefore requires efficient control strategies in order to optimize the trade-off between the gain in performance and the cost of updating. To this aim, incremental and decremental operators have been proposed, including sliding windows methods.

An illustrative example is the case of ensemble learning techniques, such as boosting, that rely on learning multiple models. Theoretical results show that it is thus possible to obtain arbitrary low errors by increasing the number of models. To achieve a linear reduction of the error, we need an exponential increase in the number of models. Finding the Breakeven point, that is the point where costs equalize benefits, and not going behind that, is a main challenge.

Monitoring Learning When data flows over time, and, at least, in case of large periods of time, the assumption that the examples are generated at random according to a stationary probability distribution becomes highly unlikely. In complex systems and for large time periods, we should expect changes in the distribution of the examples. A natural approach for these incremental tasks are adaptive learning algorithms, incremental learning algorithms that take into account concept drift.

Concept drift means that the concept related to the data being collected may shift from time to time, each time after some minimum permanence. Changes occur over time. The evidence for changes in a concept are reflected in some way in the training examples. Old observations, that reflect the past behavior of the nature, become irrelevant to the current state of the phenomena under observation and the learning agent must forget that information.

The nature of change is diverse. Changes may occur in the context of learning, due to changes in hidden variables, or in the characteristic properties of the observed variables. In fact, it is usual to distinguish between:

• Changes in the underlying distribution over the instance descriptions (denoted D X , the distribution over the description space X ).

• Changes in the conditional distribution of the label w.r.t. the description (denoted D Y|X , where Y is the label space). This is usually called "concept drift".

• Changes in both of the distributions.

In the former case, the change affects the space of the available instances, but not the underlying regularity. This, however, may require changes in the decision rules in order to optimize the decision process over the dense regions of the instance space. In the second case, the identified decision rule has to be adapted. In open worlds, learning systems should be able to extend their representation by learning new concepts from the observations that do not match the current representation of the world. This is a difficult task. It requires to identify the unknown, that is, the limits of the current model. In that sense, the unknown corresponds to an emerging pattern that is different from noise, or drift in previously known concepts.

Issues and Challenges in Learning from Distributed Data Streams

Streaming data and domains offer a nice opportunity for a symbiosis between Streaming Data Management Systems and Machine Learning. The techniques developed to estimate synopsis and sketches require counts over very high dimensions both in the number of examples and in the domain of the variables. The techniques developed in data streams management systems can provide tools for designing Machine Learning algorithms in these domains. On the other hand, Machine Learning provides compact descriptions of the data than can be useful for answering queries in DSMS.

Incremental Learning and Forgetting. In most applications, we are interested in maintaining a decision model consistent with the current status of the nature. This lead us to the sliding window models where data is continuously inserted and deleted from a window. Learning algorithms must have operators for incremental learning and forgetting. Incremental learning and forgetting are well defined in the context of predictive learning. The meaning or the semantics in other learning paradigms (like clustering) are not so well understood, very few works address this issue.

Change Detection. Concept drift in the predictive classification setting is a well studied topic. In other learning scenarios, like clustering, very few works address the problem. The main research issue is how to incorporate change detection mechanisms in the learning algorithm for different paradigms.

Feature Selection and Pre-processing. Selection of relevant and informative features, discretization, noise and rare events detection are common tasks in Machine Learning and Data Mining. They are used in a one-shot process. In the streaming context the semantics of these tasks changes drastically. Consider the feature selection problem. In streaming data the concept of irrelevant or redundant features are now restricted to a certain period of time. Features previously considered irrelevant may become relevant, and vice-versa to reflect the dynamics of the process generating data. While in standard data mining, an irrelevant feature could be ignored forever, in the streaming setting we need still monitor the evolution of those features. Recent work based on the fractal dimension [START_REF] Barbara | Using the fractal dimension to cluster datasets[END_REF] could point interesting directions for research.

Ubiquity in the Feature Space. In the static case, similar data can be described with different schemata. In the case of dynamic streams, the schema of the stream can also change. We need algorithms that can deal with evolving feature spaces over streams. There is very little work in this area, mainly pertaining to document streams. For example, in sensor networks, the number of sensors is variable (usually increasing) over time. For instance, clustering of data coming through streams on different sensing and computing sites is a growing field of research that brings completely new algorithms (see for instance [START_REF] Kargupta | Data Mining: Next Generation Challenges and Future Directions, chapter Existential Pleasures of Distributed Data Mining[END_REF][START_REF] Aggarwal | Data Streams -Models and Algorithms[END_REF]).

Evaluation Methods and Metrics. An important aspect of any learning algorithm is the hypothesis evaluation criteria. Most of evaluation methods and metrics were designed for the static case and provide a single measurement about the quality of the hypothesis. In the streaming context, we are much more interested in how the evaluation metric evolves over time. Results from the sequential statistics [START_REF] Wald | Sequential Analysis[END_REF] may be much more appropriate.

There is a fundamental difference between learning from small datasets and large datasets. As pointed-out by some researchers [START_REF] Brain | The need for low bias algorithms in classification learning from large data sets[END_REF], current learning algorithms emphasize variance reduction. However, learning from large datasets may be more effective when using algorithms that place greater emphasis on bias management.

Where We Want to Go: Emerging Challenges and Future Issues

KDUbiq points out to systems and algorithms with high level of autonomy. These systems address the problems of data processing, modeling, prediction, clustering, and control in changing and evolving environments. They self-evolve their structure and knowledge on the environment. In contrast to the main stream in Machine Learning theory and practice, KDubiq points out a world in movement where things evolve in time and space. The main difference is the conceptual framework. Current DM techniques assume a static world, that we can monitor using unrestricted resources. If we ignore resource constraints, they might be applied with high maintenance costs (retraining models from time to time). In the KDubiq perspective the world is in movement; any learning task requires decision models that evolve over time, incorporating change detection mechanisms, and taking into account the resources available. The relevant point is not what we can do more, but what we can better.

The definition of standards to represent and exchange models, incorporation of domain knowledge, vizualization, the definition of processes and systemic approaches, are traditional issues in data mining that are reinforced from the emerging applications like bioinformatics, semantic Web, sensor networks, radio frequency identification, etc.

The main lesson we, researchers in knowledge discovery, can learn from the challenges that ubiquity poses is that learning algorithms are limited. Real world is much greater even than a network of computers. The design of learning algorithms must take memory, space, time, communication, etc into account.

Simple objects that surround us are changing from static, inanimate objects into adaptive, reactive systems with the potential to become more and more useful and efficient. Smart things associated with all sort of networks offers new unknown possibilities for the development and self-organization of communities of intelligent communicating appliances. Learning in these contexts must be non pervasive, and become invisible.

  Most learning algorithms use blind methods that adapt the decision model at regular intervals without considering whether changes have really occurred. Much more interesting is explicit change detection mechanisms. The advantage is that they can provide meaningful description (indicating change-points or small time-windows where the change occurs) and quantification of the changes. The main research issue is how to incorporate change detection mechanisms in the learning algorithm. Embedding change detection methods in the learning algorithm is a requirement in the context of continuous flow of data. The level of granularity of decision models is a relevant property, because if can allow partial, fast and efficient updates in the decision model instead of rebuilding a complete new model whenever a change is detected. The ability to recognize seasonal and re-occurring patterns is an open issue. Novelty Detection. Novelty Detection refers to the automatic identification of unforeseen phenomena embedded in a large amount of normal data. It corresponds to the appearance of a new concept (e.g. a new label or a new cluster) from unlabelled data. Learning algorithms must then be able to identify and learn new concepts. Novelty is always a relative concept with regard to our current knowledge. Intelligent agents that act in dynamic environments must be able to learn conceptual representations of such environments. Those conceptual descriptions of the world are always incomplete. They correspond to what it is known about the world. This is the open world assumption as opposed to the traditional closed world assumption, where what is to be learnt is defined in advance.


Maksim Koptelov

Albrecht Zimmermann

What can connectivity characteristics of networks tell us about the quality of link predictions?

Link prediction in networks works better when those networks are connected and not sparse. But can we use common connectivity characteristics to decide once a network is well enough connected to allow a random walk process to predict links best? Recent results in our work on link prediction lead us to ask this question and we attempt to shed some light on it. We do this by combining networks stemming from different data sources into networks combining different numbers of layers, and connecting their connectivity characteristics to the AUC that can be achieved by a random walk algorithm for link prediction. What we find is that it seems to be very important to reduce the radius and diameter of the network as much as possible, and get close to having a single connected component in the network. We also argue that the five benchmark data sets that have been used in the literature on drug-target activity prediction might be too easy to allow meaningful evaluations.

1 All nodes are shared between all layers 2 Each node is present only in a single layer 3 Inter-layer edges, that cross layers, are only between nodes and their counterparts 4 Diagonal couplings for which all possible inter-layer edges are present 5

Introduction

As a rule of thumb, having more data in a learning or mining setting is better. There are a number of qualifiers to this statement, however: unreliable data, noisy data, the curse of dimensionality, strongly correlated descriptors can all turn the addition of data from a boon to an impediment.

The motivation for the work described in this paper can be found in work on drug-target activity prediction that we published recently [START_REF] Koptelov | Link prediction in multi-layer networks and its application to drug design[END_REF], which started from the rule of thumb. In that problem setting, the goal is to predict the likelihood that a drug and a target interact, based on information of their other interactions (and the interactions of other drugs and targets). The network induced by introducing edges between interacting entities (drugs or targets) is often spare and not fully connected, limiting how well additional interactions can be predicted. This is typically alleviated in the literature by adding additional information, e.g. about entities' similarities [START_REF] Buza | Aladin: A new approach for drug-target interaction prediction[END_REF] or interactions of entities of the same type, e.g. drug-drug ones. When this is done, choices are made about which similarity measure to use or which additional networks to use or discard. The typical configuration in the literature consists of a three-layer network: the interaction layer, as well as one each connecting drugs to drugs and targets to targets, respectively.

The hypothesis of our work was a simple one: instead of making those choices, we would use all networks at our disposal and let the prediction algorithm sort things out. The random walk algorithm we proposed, Newermine, did exactly that on a large and sparse interaction network, IUPHAR: as we showed experimentally, running Newermine on a six-layer network from IUPHAR and the five additional networks which are available gave superior results to using any three-layer network we could construct. We tentatively explained this result with the fact that only the six-layer network formed a fully connected component while having the same sparsity as some of the better-performing three-layer networks.

Further results, however, call this assumption into question. Performing the same kind of experimental evaluation in a number of networks that have become the de facto benchmark standard in the field [START_REF] Yamanishi | Prediction of drug-target interaction networks from the integration of chemical and genomic spaces[END_REF][START_REF] Davis | Comprehensive analysis of kinase inhibitor selectivity[END_REF], we found that using only the three layers selected in the original publications, Newermine consistently performed better than six-or eight-layer networks.

There are at least two possible explanations for this: 1) some of the networks do not provide reliable information, or 2) once the network has a certain structure that is sufficient for the success of the random walk, adding additional layers does not help anymore. To shed some light on this issue, we present a systematic exploration of how combining different networks into multi-layer networks affects connectivity characteristics of the resulting network and whether we can use those characteristics to tentatively explain the quality of the derived link predictions.

Definitions

A graph is a tuple G =< V, E >, where V = {v 1 , v 2 , ..., v n } denotes a set of vertices or nodes, and E ⊆ V × V a set of edges defined by distinct vertex pairs (u, v) ∈ V × V with u = v (without self-loops). We also use the notion of a bipartite graph, which we define as a graph the vertices of which can be divided into two classes V 1 and V 2 such that there is no edge between vertices of the same class:

G =< V 1 ∪ V 2 , E >, E ⊂ V 1 × V 2 .
We address weighted and unweighted graphs in the same manner. We define a weighted graph as one with a labeling function for edges E → A e with A e ∈ [0, 1], where 0 means no interaction between vertices, 1 confirmed interaction, and an intermediate value represents interaction probability. An unweighted graph is one where every edge is labeled by 1.

To exploit different sources of information in one single structure, we employ multi-layer networks. We define a multi-layer network as a weighted graph where more than one edge (u, v) can exist for a pair of vertices u, v. Multi-layer networks can be decomposed into disjunct set of graphs G l that contain at most a single edge for each pair of vertices, called layers or just networks. As we wrote above, our original setting is a bipartite one. To combine it with the multi-layer framework, we define a bipartite multi-layer graph as a multi-layer network the vertices of which can be divided into two classes, and where exactly one of the layers is a bipartite graph. Note, according to the classification of Kivelä et al. [START_REF] Kivelä | Multilayer networks[END_REF], the multi-layer networks used in this work are not node-aligned 1 , not layerdisjoint 2 , have diagonal couplings 3 which are categorical 4 , and the number of layers can be any.

Link prediction via random walk

A long-established method for exploring a network is the random walk [?], which proceeds roughly as follows: starting from a randomly selected node, it performs walks along edges of the graph at random. In every step, the edge to follow is chosen uniformly from all outgoing links (in the case of an unweighted graph) or proportional to link weights (in the case of a weighted graph). Node importance is based on how frequently the walker visits the node: a node with higher frequency is considered more important than a node with a low value.

This idea can be modified in a number of ways to improve network exploration: the walker can be constrained to perform at most max steps steps, to not visit any of the last c vertices it encountered, or with small probability 1 -β the process can be restarted at any time to avoid getting trapped by those vertices it mustn't visit. The product of the probabilities of edges the walker traversed gives the cumulative probability of a path between two nodes and can be used to predict a link between a starting node and an end node: if the path probability is greater than a given threshold, a new edge is predicted.

To extend this approach to multi-layer graphs, one needs to add how to choose the layer to walk in. We propose to select a network uniformly at random from the set of networks, and multiply the path strength by

1 |{G i l }|+|{G j p }|+|{G k lp }| .
Repeat the process until a user-defined target vertex is reached or the maximum number of steps have been performed. Due to the randomized nature, random walks are usually repeated several times to derive more robust estimates.

In our prior work, we have adapted a PageRank algorithm to the setting using an arbitrary number of layers.

The data

As mentioned in the introduction, there are several drug-target interaction data sets, five in total, that have been used in prior work on drug-target interaction prediction [START_REF] Chen | Drug-target interaction prediction by random walk on the heterogeneous network[END_REF][START_REF] Zheng | Collaborative matrix factorization with multiple similarities for predicting drug-target interactions[END_REF][START_REF] Lim | Improved genome-scale multi-target virtual screening via a novel collaborative filtering approach to cold-start problem[END_REF][START_REF] Buza | Aladin: A new approach for drug-target interaction prediction[END_REF], and can be considered benchmarks. We downloaded the original data of four of those datasets (Enzyme, GPCR, IC, NR) from the supplementary information of Yamanishi et al.'s work [START_REF] Yamanishi | Prediction of drug-target interaction networks from the integration of chemical and genomic spaces[END_REF] 5 , and the fifth (Kinase) from the supplementary information of Davis et al.'s work [START_REF] Davis | Comprehensive analysis of kinase inhibitor selectivity[END_REF] 6 .

The original representation of these data consists of 3 networks: a drug similarity network obtained by the use of the SimComp score that we will refer to as DS(sc), a target similarity network obtained by the use of the Smith-Waterman score (TS(sw)), and a drug-target interaction network (DT) constructed from the KEGG BRITE [START_REF] Kanehisa | Kegg for linking genomes to life and the environment[END_REF], BRENDA [START_REF] Schomburg | Brenda, enzyme data and metabolic information[END_REF], SuperTarget [START_REF] Günther | Supertarget and matador: resources for exploring drug-target relationships[END_REF], and DrugBank [START_REF] Wishart | Drugbank: a comprehensive resource for in silico drug discovery and exploration[END_REF] databases. We have augmented this representation by constructing additional networks:

a drug-drug interaction network based on DrugBank (DB), a target-target interaction network based on BioGrid [START_REF] Stark | Biogrid: a general repository for interaction datasets[END_REF] (BG), a drug similarity network based on similarities calculated using the Tanimoto coefficient on binary vectors constructed from the presence/absence of frequent subgraphs (DS(sg)), and two target similarity networks calculated using the Tanimoto coefficient on feature vectors constructed from the presence/absence frequent substrings (TS(ss)) and Prosite motifs(TS(mot)) 7 .

The IUPHAR multi-layer network 8 we constructed and used in our earlier work is not a standard benchmark for drug-target activity prediction in the literature, however.

IUPHAR -an open-access database of drugs, biological targets and their in-

teractions. We used version 2017.5 (released on 22/08/2017). The full dataset has 8978 drugs, 2987 proteins, and 17198 interactions (edges) between them 9 . In order to satisfy the designed setting conditions, we removed duplicate interactions (based on different affinity measures), leaving 12456 interactions in total. For existing interactions, we label an edge with 1 if the negative logarithm of the affinity measure is ≥ 5, non-interacting otherwise. 10 We treat all affinity measures available in the data (pKi, pIC50, pEC50, pKd, pA2, pKB) as equivalent. drugs were mapped between networks by numerical identifiers provided by IUPHAR as well as by INN (International Non-proprietary Name) and Common name attributes. Proteins were mapped by IUPHAR identifiers as well as by Human Entrez Gene attribute. 12As the preceding listing shows, not all drugs and proteins contained in IUPHAR are available in DB and BG. In addition, not all proteins and drugs are annotated with molecular information so that not all entities will be connected in the similarity networks.

Experimental evaluation

As we wrote above, our earlier work indicated that using eight networks leads to better results than using three networks [START_REF] Koptelov | Link prediction in multi-layer networks and its application to drug design[END_REF]. In this section, we first explore whether the same holds for the benchmark data sets. We then explore how many and which combinations of networks allow for best performance before discussing the connectivity characteristics of those best-performing combinations. Finally, we evaluate our newly derived insights on the IUPHAR data.

Link prediction in benchmark data sets

In this section, we report the results of Newermine, the random-walk based method we have proposed in [START_REF] Koptelov | Link prediction in multi-layer networks and its application to drug design[END_REF], on the benchmark data sets. We use optimal parameter setting (η = 0.2, β = 0.7) defined for this method. Unlike the evaluation framework used in [START_REF] Koptelov | Link prediction in multi-layer networks and its application to drug design[END_REF], we performed a 5x5-fold cross-validation, with each fold containing 20% of all drug-target interactions, acting as test set for link prediction once, while the method is run on the other 80%. The process is repeated 5 times, the results are averaged among all runs. We switched to a 5x5-fold cross-validation to allow comparison to state-of-the-art methods in order to be able to compare the results in the future work.

Table 1 reports both area under the ROC curve (AUC) and area under the precision-recall curve (AUPR), both for using the three layers proposed in the literature, and the eight layers that result from augmenting those networks with the additional information we outlined above.

As we can see, using all layers clearly underperforms compared to using only the three that have been proposed in the literature.

How many/which networks are useful for link prediction?

The question to ask in light of these results is: "Why?" We can formulate at least two plausible working hypotheses: There are diminishing returns to adding additional layers. To arrive at a network that can be exploited for link predictions by a random walk process, it is necessary to create as few connected components as possible, and a network that is as dense as possible. But once the entire network consists of a single connected component, and paths between any two vertices are short, it might be impossible to improve the state of the network.

Either of these effects, or, even worse, a combination of the two, can lead a random walk process astray. Similar to how adding noisy attributes or ones that are strongly correlated with attributes that are already present can degrade the performance of a predictor for vectorial data, adding non-reliable or redundant edges can undermine link prediction.

Connectivity characteristics and redundancy

We start with exploring the second hypothesis. Table 2 illustrates the main characteristics of the different data sets and we can see that IUPHAR is not like the others: significantly less dense, with a much higher number of distinct connected components. Sparsity refers to the number of edges in the network, divided by the maximal number of edges possible. Notably, the Kinase network is also different since it is the only one that is already connected.

And as Table 3 shows, adding two additional networks boosts the density of the benchmark data sets and turns them into a single connected component, whereas even the best-case situation for IUPHAR still results in a sparse, fragmented network. The reason for this is, as mentioned before, that even in the case of the rich similarity networks there are missing connections. The reader will also notice that the three-layer IUPHAR combination indicates fewer vertices since we removed isolated vertices, i.e. those not connected to any other vertex in any layer. This is probably a first indication for why using three layers for the IUPHAR network is not enough -it does not explain, however, why adding additional layers degrades link prediction performance on the benchmark data sets. To gain more insight into this question, we present a number of connectivity characteristics of derived multi-layer networks in Tables 45678. For reasons of space constraints and readability, we do not show the complete list but only representative results. The first column lists which additional networks have been added to the LT network (which is always present and therefore omitted). The tables then list, in order, the number of layers that the network has (|L|), its sparsity, i.e. the number of existing edges divided by the maximum possible number of edges, the number of connected components (CC), where by connected component we assume a graph any two vertices of which are connected to each other by a path, and which is connected to no additional vertices in the supergraph, the radius of the network, i.e. the minimum shortest path between any two different vertices in the network, its diameter, the maximum shortest path between any two different vertices, the number of edges of the flattened graph (|E|), the clustering coefficient (C coef ), the number of existing closed triangles divided by the maximum possible number of open and close triangles, and the transitivity (T r), the number of existing closed triangles divided by the number of connected triples.

Finally, the right-most two columns list the AUC and AUPR scores for link prediction via Newermine. It should be noted that connectivity characteristics such as clustering coefficient and transitivity are typically not defined for multilayer networks -we therefore report these measures for a flattened network: when there is an edge available between any two nodes, they are treated as connected, no matter the network the edge occurs in. It should also be mentioned also that in networks having more than one connected component, we compute and report radius and diameter values for the largest such component in terms of the number of vertices. For a network with the number of CC = 1 that giant component is equal to the network itself. What we see for every data set except Kinase is that reducing the number of connected components improves link prediction, especially once only a single connected component remains. For all of these benchmark data sets, the latter is achieved at the latest once the network contains three layers.

There seems to be a secondary effect of decreasing the diameter to two: for Enzyme, GPCR, and IC, the final bump in AUC comes once the network moves from a diameter of three to one of two. This decrease in the diameter goes together with a clear increase in the value of the clustering coefficient. Notably, however, we achieve better results on NR for a diameter of three than one of two. Once those two aspects -the number of connected components and the diameter -have been addressed, there does not seem to be anything to be gained from adding additional networks. Notably, making the multi-layer network significantly denser does not result in additional gains but instead reduces quality.

Reliability/informativeness of networks

We would suspect that this degradation of link prediction quality is related to the first hypothesis that we formulated above: that certain networks simply provide better information.

Tables 4 -8 also show that not all multi-layer networks that lead to similar or even the same connectivity characteristics allow for the same performance of Newermine. In each table, we have indicated the best-performing layer combination (or combinations) in bold and the layer combination found in the literature -using SimComp for drug similarity and Smith-Waterman for target similarity -in italics. As we can see, for Enzyme, GPCR, and IC, the combination used in the literature does indeed give best results. But while Smith-Waterman seems to encode vital information about target similarity, the SimComp score can be replaced by a very simple similarity measure, the Tanimoto coefficient over a vector of frequent subgraphs, i.e. subgraphs mined in an unsupervised manner!

The results are even more interesting for the other two data sets: for NR, using the SimComp/Smith-Water does not give best results -instead combining BioGrid information about target-target interactions with SimComp drug similarity results in the highest AUC. The reason for that could be in the fact that NR is too small in terms of the number of vertices and the number of edges for the evaluation framework we use (when we remove 20% of edges the network might become destructed too much what results in such unpredictable behavior). And there is an explanation for Kinase also. As we already wrote above, it is different, particularly because it already consists of a single connected component. Adding subgraph-based drug similarity to the interaction network is enough to achieve the highest AUC, with the SimComp/Smith-Waterman combination not only behind that two-layer network but also behind a number of others that do not use the TS(sw) network.

How does this transfer to IUPHAR?

After having explored how connectivity characteristics on benchmark data sets align with the quality of link prediction, we obviously want to come back to our original problem settings -link prediction on the IUPHAR data set -and see whether we can observe similar behavior.

In Table 9, we list the connectivity characteristics of the best-performing network combinations for IUPHAR, one for each number of layers from two to six. There is an exception for four layers where the AUC was virtually indistinguishable. We had neither DS(sc) nor TS(sw) networks for the IUPHAR set.

There are a number of interesting observations here. 1. The first is that we were wrong in our Newermine publication -the best layer combination does not contain all six layers but only five, the BioGrid layer seems to reduce the quality of the information in the multi-layer network. 2. The second is that the importance of reducing radius and diameter holdfive and nine are the two lowest values we can achieve on IUPHAR. 3. The third observation is that the exception to this rule is the three-layer setting -this setting, so common in the literature, seems to be the single worst setting for IUPHAR and the improvement on it therefore easiest. 4. Fourth, once radius and diameter have been driven down, the number of connected components seems to matter less, a phenomenon we could not observe on the smaller benchmark data sets. 5. Finally, there were several other combinations that achieved a radius of five and a diameter of nine, without leading to best AUC. The difference is that the "winning" combinations have lower average distance between vertices (not shown).

Conclusion

This is very consciously a workshop paper, intended to provoke discussion and additional work to explore this issue further. As such, we do not have clear conclusions to draw. What seems to emerge from our experimental data, however, is that the most important issue to pay attention to when augmenting networks for link prediction is to add data that reduces the radius and diameter of the final network as much as possible. We have to admit, however, that those results are also preliminary in the sense that, for running time reasons, we did not in fact test all layer combinations for all networks. To base our insights on firmer ground, we will do this for a future publication. [START_REF] Kivelä | Multilayer networks[END_REF] We would add that the five benchmark data sets that are being widely used in the literature on drug-target activity prediction might not be the best choice. They are all small, can easily augmented to form only a single connected component and achieve minimal diameter. This is doubly true for the Kinase data set that forms a single connected component to begin with.

Similarly to how data sets in other fields have become outdated and are rarely used nowadays -e.g. the Iris data set for machine learning and clustering, or the Mutagenicity data set for ILP and substructure mining -it might be time to retire these networks and curate new benchmarks.

2 .

 2 DrugBank (DB) -an open-access database of drug-drug interactions. We used version 5.0.11 (released 20-12-2017). It has 658079 interactions of 3138 distinct drugs. 242922 of these interactions involve 1254 distinct drugs that are present in IUPHAR. The database was also used as a source of 2D representations of drugs to compute drug similarities. 3. BioGrid (BG) -an open-access database of protein-protein interactions mined from a corpus of biomedical literature. We used version 3.4.154 (25/10/2017). It has 1482649 interactions of 67372 distinct proteins. Only 15410 of these interactions involve proteins present in IUPHAR (1925 distinct proteins). 4. NCBI Protein database -The National Center for Biotechnology Information proteins database 11 was used to obtain amino acids sequences to represent targets. The data was parsed from the website of NCBI and mapped to IUPHAR using the RefSeq attribute (human protein sequence identifier) available in IUPHAR. The database was accessed 20/12/2017.

Table 1 .

 1 Three layer results, eight-layer results of Newermine link predictions on the benchmark data 1. Certain networks are less reliable/informative than others. Drug-Bank information, for instance, is arguably anecdotal since interactions are based on published results in the literature, whereas similarity edges are reliable: the molecular information about a compound exists and has been translated into a similarity value in a transparent manner. But not all similarities are equal: the SimComp score takes chemical aspects into account that the use of frequent subgraphs might miss. 2.

	Data set 3 layers	8 layers
		AUC AUPR AUC AUPR
	Enzyme 0.844 0.15 0.655 0.15
	GPCR 0.81 0.22 0.674 0.112
	IC	0.76 0.26 0.61 0.09
	NR 0.635 0.26 0.489 0.15
	Kinase 0.61 0.13 0.553 0.08

Table 2 .

 2 Basic properties of Benchmark and IUPHAR data sets

	Data set Drugs Targets |V | |E| Sparsity CC
	Enzyme 445	664 1109 2926 0.005 44
	GPCR 223	95	318 635 0.013 19
	IC	210	204	414 1476 0.017 3
	NR	54	26	80	90	0.028 10
	Kinase	68	442	510 1527 0.016 1
	IUPHAR 8137 2502 10639 12456 0.00017 443

Table 3 .

 3 Basic properties of three-layer networks

	Data set Drugs Targets Layers |V |	|E| Sparsity CC
	Enzyme 445	664	3	1109 321832 0.524 1
	GPCR 223	95	3	318 29853 0.592 1
	IC	210	204	3	414 44127 0.516 1
	NR	54	26	3	80	1846	0.584 1
	Kinase 442	1527	3	510 101266 0.780 1
	IUPHAR 7025 2010	3	9126 1786917 0.0215 103

Table 4 .

 4 Connectivity characteristics of different network combinations for the Enzyme data set

	Networks	|L| Sparsity CC Giant component	Flattened graph	AUC AUPR
					Radius Diameter	|E|	C coef	T r
	BG	2	0.007 12	6	10	4153 0.1599 0.0562 0.24 0.01
	DB	2	0.018 14	5	10	10856 0.2127 0.435 0.66	0.1
	DS(sg)	2	0.166	1	2	3	101716 0.7298 0.971 0.82 0.14
	DS(sc)	2	0.166	1	2	3	101716 0.7298 0.971 0.82 0.14
	DS(sg),TS(sw)	3 0.524	1	2	2	321832 0.9825 0.9838 0.84 0.15
	DS(sc),TS(sw)	3	0.524	1	2	2	321832 0.9825 0.9838 0.84 0.15
	DS(sg),DB,TS(sw),TS(ss) 5	0.895	1	2	2	321832 0.9825 0.9838 0.74 0.09
	DS(sg),DB,TS(sw),TS(mot) 5	0.895	1	2	2	321832 0.9825 0.9838 0.74 0.09
	DS(sc),DB,TS(sw),TS(ss) 5	0.895	1	2	2	321832 0.9825 0.9838 0.74 0.10
	DS(sc),DB,TS(sw),TS(mot) 5	0.895	1	2	2	321832 0.9825 0.9838 0.74 0.09

Table 5 .

 5 connectivity characteristics of different network combinations for the GPCR data set

	Networks	|L| Sparsity CC Giant component	Flattened graph	AUC AUPR
					Radius Diameter |E|	C coef	T r
	BG	2	0.013 14	6	12	650 0.0251 0.0078 0.28 0.02
	DB	2	0.087	7	5	9	4369 0.3706 0.5779 0.65 0.19
	DS(sg)	2	0.504	1	2	3	25388 0.8771 0.9764 0.77 0.22
	DS(sc)	2	0.504	1	2	3	25388 0.8771 0.9764 0.77 0.22
	DS(sg),TS(sw)	3 0.592	1	2	2	29853 0.9546 0.9694 0.80 0.21
	DS(sc),TS(sw)	3	0.592	1	2	2	29853 0.9546 0.9694 0.80 0.22
	DS(sg),DB,TS(sw),TS(ss) 5	0.755	1	2	2	29853 0.9546 0.9694 0.73 0.17
	DS(sg),DB,TS(sw),TS(mot) 5	0.755	1	2	2	29853 0.9546 0.9694 0.74 0.17
	DS(sc),DB,TS(sw),TS(ss) 5	0.755	1	2	2	29853 0.9546 0.9694 0.74 0.18
	DS(sc),DB,TS(sw),TS(mot) 5	0.755	1	2	2	29853 0.9546 0.9694 0.74 0.18

Table 6 .

 6 connectivity characteristics of different network combinations for the IC data set

	Networks	|L| Sparsity CC Giant component	Flattened graph	AUC AUPR
					Radius Diameter |E|	C coef	T r
	BG	2	0.019	3	5	9	1583 0.0958 0.034 0.32 0.02
	DB	2	0.107	3	4	7	6666 0.3639 0.6033 0.63 0.14
	DS(sg)	2	0.481	1	2	3	23421 0.9169 0.9367 0.71 0.16
	DS(sc)	2	0.481	1	2	3	23421 0.9169 0.9367 0.72 0.17
	DS(sg),TS(sw)	3 0.516	1	2	2	44127 0.9469 0.9414 0.76 0.26
	DS(sc),TS(sw)	3	0.516	1	2	2	44127 0.9469 0.9414 0.76 0.27
	DS(sg),DB,TS(sw),TS(ss) 5	0.819	1	2	2	44127 0.9469 0.9414 0.67 0.15
	DS(sg),DB,TS(sw),TS(mot) 5	0.819	1	2	2	44127 0.9469 0.9414 0.67 0.15
	DS(sc),DB,TS(sw),TS(ss) 5	0.819	1	2	2	44127 0.9469 0.9414 0.68 0.15
	DS(sc),DB,TS(sw),TS(mot) 5	0.819	1	2	2	44127 0.9469 0.9414 0.67 0.16

Table 7 .

 7 connectivity characteristics of different network combinations for the NR data set

	Networks	|L| Sparsity CC Giant component	Flattened graph	AUC AUPR
					Radius Diameter |E| C coef	T r
	BG	2	0.043	2	4	6	137 0.2241 0.2318 0.26 0.04
	DB	2	0.107	3	3	5	339 0.2717 0.3026 0.5	0.10
	DS(sg)	2	0.481	1	2	3	1521 0.8648 0.9452 0.61 0.22
	DS(sc)	2	0.481	1	2	3	1521 0.8648 0.9452 0.63 0.28
	DS(sg),TS(sw)	3	0.584	1	2	2	1846 0.9096 0.9295 0.60 0.20
	DS(sc),TS(sw)	3 0.584	1	2	2	1846 0.9096 0.9295 0.63 0.26
	DS(sg),BG	3	0.496	1	2	3	1568 0.7892 0.9413 0.66 0.19
	DS(sc),BG	3 0.496	1	2	3	1568 0.7892 0.9413 0.69 0.22
	DS(sg),DB,TS(sw),TS(ss) 5	0.766	1	2	2	1846 0.9096 0.9295 0.51 0.13
	DS(sg),DB,TS(sw),TS(mot) 5	0.766	1	2	2	1846 0.9096 0.9295 0.48 0.12
	DS(sc),DB,TS(sw),TS(ss) 5	0.766	1	2	2	1846 0.9096 0.9295 0.53 0.15
	DS(sc),DB,TS(sw),TS(mot) 5	0.766	1	2	2	1846 0.9096 0.9295 0.52 0.16

Table 8 .

 8 connectivity characteristics of different network combinations for the Kinase data set

	Networks	|L| Sparsity CC Giant component	Flattened graph	AUC AUPR
					Radius Diameter	|E|	C coef	T r
	BG	2	0.019	1	4	6	2433 0.1447 0.0459 0.36 0.04
	DB	2	0.017	1	5	10	1615 0.0363 0.0285 0.56 0.13
	DS(sg)	2 0.038	1	2	4	3700 0.7136 0.5108 0.66 0.17
	DS(sc)	2	0.039	1	2	3	3805 0.7319 0.5451 0.65 0.16
	DS(sg),DB	3	0.039	1	2	4	3701 0.7137 0.5111 0.65 0.16
	DS(sc),DB	3	0.040	1	2	3	3805 0.7319 0.5451 0.64 0.14
	DS(sg),BG	3	0.039	1	3	6	4606 0.5234 0.4938 0.65 0.12
	DS(sc),BG	3	0.040	1	3	6	4711	0.532 0.5272 0.64 0.11
	DS(sg),TS(sw)	3	0.779	1	2	3	101161 0.954 0.9847 0.61 0.14
	DS(sc),TS(sw)	3 0.780	1	2	3	101266 0.9578 0.9848 0.61 0.13
	DS(sg),DB,TS(sw),TS(ss) 5	1.516	1	2	3	101162 0.9541 0.9847 0.58 0.12
	DS(sg),DB,TS(sw),TS(mot) 5	1.516	1	2	3	101162 0.9541 0.9847 0.58 0.12
	DS(sc),DB,TS(sw),TS(ss) 5	1.517	1	2	3	101266 0.9578 0.9848 0.58 0.11
	DS(sc),DB,TS(sw),TS(mot) 5	1.517	1	2	3	101266 0.9578 0.9848 0.58 0.11

Table 9 .

 9 connectivity characteristics of different network combinations for the IUPHAR data set

	Networks	|L| Sparsity CC Giant component	Flattened graph	AUC
			Radius Diameter	|E|	C coef	T r
	DS(sg)	2 0.5147 69	5	9	23272066 0.7992 0.9996 0.5781
	DB, BG	3 0.0033 87	7	14	143922 0.1285 0.5118 0.5255
	DS(sg), DB, TS(ss)	4 0.4780 14	5	9	24929849 0.9003 0.9992 0.5805
	DS(sg), DB, TS(mot)	4 0.4780 14	5	9	24929849 0.9003 0.9992 0.5800
	DS(sg), DB, TS(ss), TS(mot) 5 0.5095 14	5	9	24929849 0.9003 0.9992 0.5812
	all	6 0.4719 1	5	9	24932609 0.8802 0.9992 0.5783

An open-access database is available at http://prosite.expasy.org

https://zimmermanna.users.greyc.fr/supplementary-material.html

in drugs.csv, interactions.csv, and targets and families.csv, respectively

Cutoff proposed by researchers from CERMN (http://cermn.unicaen.fr)

https://www.ncbi.nlm.nih.gov/protein/

Global Query Cross-Database Search System gene identifiers: https://www.ncbi. nlm.nih.gov/gene