We first define and experiment the hub-authority core (or HA-core) of a directed network. It depends on two a and h parameters expressing requirements on hub and authority degrees which have to be fulfilled within the core. The definition of these interrelated degrees is inspired by the standard definition of hub and authorities centrality scores (HITS). We investigate the HA-cores on citation networks and discuss how they relates to these scores. We discuss then how the methodology of ab- stract closed pattern mining, previously defined on non-directed attributed networks, may be applied to directed networks using hub-authority cores. We use these cores to investigate a well known attributed network representing the advice exchanges within a law firm.

Collective learning considers how agents, in a community sharing a learning purpose, may benefit from exchanging hypotheses and observations to learn efficiently as a community as well as individuals. The community forms a communication network and each agent has access to observations. We address the question of a protocol, i.e. a set of agent's behaviours, which guarantees the hypotheses retained by the agents take into account all the observations in the community. We present and investigate the protocol WAVES which displays such a guarantee in a turn-based scenario: at the beginning of each turn, agents collect new observations and interact until they all reach this consistency guarantee. We investigate and experiment WAVES on various network topologies and various experimental parameters. We present results on learning efficiency, in terms of computation and communication costs, as well as results on learning quality, in terms of predictive accuracy for a given number of observations collected by the community.

We address collaborative decision in the Multi-Agent Consistency-based online learning of relational action models. This framework considers a community of agents, each of them learning and rationally acting following their relational action model. It relies on the idea that when agents communicate, on a utility basis, the observed effect of past actions to other agents, this results in speeding up the online learning process of each agent in the community. In the present article, we discuss how collaboration in this framework can be extended to the individual decision level. More precisely, we first discuss how an agent's ability to predict the effect of some action in its current state is enhanced when it takes into account all the action models in the community. Secondly, we consider the situation in which an agent fails to produce a plan using its own action model, and show how it can interact with the other agents in the community in order to select an appropriate action to perform. Such a community aided action selection strategy will help the agent revise its action model and increase its ability to reach its current goal as well as future ones.

We address the problem of finding local patterns and local rules in an attributed graph. A (global) closed pattern is the most specific attribute pattern shared by the vertices of the (possibly simplified) subgraph induced by some attribute pattern. A local closed pattern is the maximal attribute pattern associated to a particular dense region of this subgraph. As such local regions, we are in particular interested in k-communities of pattern subgraphs. In this case we show that there is a closure operator such that, given a pattern q subgraph and a k-community in this subgraph, returns the local closed pattern shared by all the members of the community. We then consider how to generate triples (c, e, l) where c is a (global) closed pattern whose subgraph contains e as a k-community, and l is the corresponding local closed pattern. This leads to implication rules expressing what new attributes are specific of the k-community e in the pattern c subgraph.

We address the problem of finding local patterns and related local knowledge in an attributed graph. Our approach consists in extending the methodology of frequent closed pattern mining to the case in which the set of objects, in which are to be found the patterns support sets, is the set of vertices of a graph, typically representing a social network. We propose an algorithm to enumerate triples (c,e,l) where c is a (global) closed pattern which leads in the region e of the graph to a local closed pattern l and define a basis of implication rules expressing what new attributes l\c appear when focussing in this region. We discuss how to apply this methodology to the detection of frequent k-communities.

Multi Agent Relational Action Learning considers a community of agents, each rationally acting following some relational action model. The observed effect of past actions that led an agent to revise its action model can be communicated, upon request, to another agent, speeding up its own revision. We present a frame-work for such collaborative relational action model revision.

We address the problem of finding patterns in an attributed graph. Our approach consists in extending the standard methodology of frequent closed pattern mining to the case in which the set of objects, in which are found the pattern supports, is the set of vertices of a graph, typically representing a social network. The core idea is then to define graph abstractions as subsets of the vertices satisfying some connectivity property within the corresponding induced subgraphs. Preliminary experiments illustrate the reduction in closed patterns we obtain as well as what kind of abstract knowledge is found via abstract implications rules.

We investigate here relational concept learning from examples when we only have a partial information regarding examples: each such example is qualified as ambiguous as we only know a set of its possible complete descriptions. A typical such situation arises in rule learning when truth values of some atoms are missing in the example description while we benefit from background knowledge. We first give a sample complexity result for learning from ambiguous examples, then we propose a framework for relational rule learning from ambiguous examples and describe the learning system LEAR. Finally we discuss various experiments in which we observe how LEAR copes with increasing degrees of incompleteness.

BACKGROUND: Identification of protein structural cores requires isolation of sets of proteins all sharing a same subset of structural motifs. In the context of an ever growing number of available 3D protein structures, standard and automatic clustering algorithms require adaptations so as to allow for efficient identification of such sets of proteins. RESULTS: When considering a pair of 3D structures, they are stated as similar or not according to the local similarities of their matching substructures in a structural alignment. This binary relation can be represented in a graph of similarities where a node represents a 3D protein structure and an edge states that two 3D protein structures are similar. Therefore, classifying proteins into structural families can be viewed as a graph clustering task. Unfortunately, because such a graph encodes only pairwise similarity information, clustering algorithms may include in the same cluster a subset of 3D structures that do not share a common substructure. In order to overcome this drawback we first define a ternary similarity on a triple of 3D structures as a constraint to be satisfied by the graph of similarities. Such a ternary constraint takes into account similarities between pairwise alignments, so as to ensure that the three involved protein structures do have some common substructure. We propose hereunder a modification algorithm that eliminates edges from the original graph of similarities and gives a reduced graph in which no ternary constraints are violated. Our approach is then first to build a graph of similarities, then to reduce the graph according to the modification algorithm, and finally to apply to the reduced graph a standard graph clustering algorithm. Such method was used for classifying ASTRAL-40 non-redundant protein domains, identifying significant pairwise similarities with Yakusa, a program devised for rapid 3D structure alignments. CONCLUSIONS: We show that filtering similarities prior to standard graph based clustering process by applying ternary similarity constraints i) improves the separation of proteins of different classes and consequently ii) improves the classification quality of standard graph based clustering algorithms according to the reference classification SCOP.

In the Relational Reinforcement learning framework, we propose an algorithm that learns an action model allowing to predict the resulting state of each action in any given situation. The system incrementally learns a set of first order rules: each time an example contradicting the current model (a counter-example) is encountered, the model is revised to preserve coherence and completeness, by using data-driven generalization and specialization mechanisms. The system is proved to converge by storing counter-examples only, and experiments on RRL benchmarks demonstrate its good performance w.r.t state of the art RRL systems.

This article addresses collaborative learning in a multi-agent system: each agent revises incrementally its beliefs B (a concept representation) to keep it consistent with the whole set of information K (the examples) that he has received from the environment or other agents. In SMILE this notion of consistency was extended to a group of agents and a unique consistent concept representation was so maintained inside the group. In the present paper, we present iSMILE in which the agents still provide examples to other agents but keep their own concept representation. We will see that iSMILE is more time consuming and loses part of its learning ability, but that when agents cooperate at classification time, the group benefits from the advantages of ensemble learning.

In many applications there is a need to represent a large number of data by clustering them in a hierarchy of classes. Our basic representation is a Galois lattice, a structure that exhaustively represents the whole set of concepts that are distinguishable given the instance set and the representation language. What we propose here is a method to reduce the size of the lattice, and thus simplify our view of the data, while conserving its formal structure and exhaustivity. For that purpose we use a preliminary partition of the instance set, representing the association of a "type" to each instance. By redefining the notion of extent of a term in order to cope, to a certain degree (denoted as /spl alpha/), with this partition, we define a particular family of Galois lattices denoted as alpha Galois lattices. We also discuss the related implication rules defined as inclusion of such /spl alpha/-extents.

This paper deals with the representation of multi-valued data by clustering them in a small number of classes organized in a hierarchy and described at an appropriate level of abstraction. The contribution of this paper is three fold. First, we investigate a partial order, namely nesting, relating Galois lattices. A nested Galois lattice is obtained by reducing (through projections) the original lattice. As a consequence it makes coarser the equivalence relations defined on extents and intents. Second we investigate the intensional and extensional aspects of the languages used in our system ZooM. In particular we discuss the notion of α-extension of terms of a class language £. We also present our most expressive language £3, close to a description logic, and which expresses optionality or/and multi-valuation of attributes. Finally, the nesting order between the Galois lattices corresponding to various languages and extensions is exploited in the interactive system ZooM. Typically a ZooM session starts from a propositional language £2 and a coarse view of the data (through α-extension). Then the user selects two ordered nodes in the lattice and ZooM constructs a fine-grained lattice between the antecedents of these nodes. So the general purpose of ZooM is to give a general view of concepts addressing a large data set, then focussing on part of this coarse taxonomy.

MOTIVATION: To predict the consensus secondary structure, possibly including pseudoknots, of a set of RNA unaligned sequences. RESULTS: We have designed a method based on a new representation of any RNA secondary structure as a set of structural relationships between the helices of the structure. We refer to this representation as a structural pattern. In a first step, we use thermodynamic parameters to select, for each sequence, the best secondary structures according to energy minimization and we represent each of them using its corresponding structural pattern. In a second step, we search for the repeated structural patterns, i.e. the largest structural patterns that occur in at least one sequence, i.e. included in at least one of the structural patterns associated to each sequence. Thanks to an efficient encoding of structural patterns, this search comes down to identifying the largest repeated word suffixes in a dictionary. In a third step, we compute the plausibility of each repeated structural pattern by checking if it occurs more frequently in the studied sequences than in random RNA sequences. We then suppose that the consensus secondary structure corresponds to the repeated structural pattern that displays the highest plausibility. We present several experiments concerning tRNA, fragments of 16S rRNA and 10Sa RNA (including pseudoknots); in each of them, we found the putative consensus secondary structure.

Finding certain regularities in a text is an important problem in many areas, e.g. in the analysis of biological molecules such as nucleic acids or proteins. In the latter case, the text may be sequences of amino acids or a linear coding of three-dimensional structures, and the regularities then correspond to lexical or structural motifs common to two, or more, proteins. We first recall an earlier algorithm that found these regularities in a flexible way. Then we introduce a generalized version of this algorithm designed for the particular case of protein three-dimensional structures, since these structures present a few peculiarities that make them computationally harder to process. Finally, we give some applications of our new algorithm on concrete examples.

In previous work, we have shown that a set of characteristics, defined as (code frequency) pairs, can be derived from a protein family by the use of a signal-processing method. This method enables the location and extraction of sequence patterns by taking into account each (code frequency) pair individually. In the present paper, we propose to extend this method in order to detect and visualize patterns by taking into account several pairs simultaneously. Two 'multifrequency' methods are described. The first one is based on a rewriting of the sequences with new symbols which summarize the frequency information. The second method is based on a clustering of the patterns associated with each pair. Both methods lead to the definition of significant consensus sequences. Some results obtained with calcium-binding proteins and serine proteases are also discussed.

In this paper, we present methods to detect and localize patterns in biologically related protein sequences (family). The patterns common to the sequences of the family are detected by using Fourier analysis. No previous scales (codes) are needed, they are actually produced as a result of the analysis procedure, together with the frequencies of the Fourier decompositions. Characteristic features of the family are thus expressed as (code-frequency) pairs. Various tools are proposed in order to localize the patterns, to compare the codes, and to evaluate the proximity of an arbitrary sequence to the investigated family. The general strategy is illustrated on a family composed of calcium-binding proteins.