B Kamsu-Foguem
email: bernard.kamsu-foguem@enit.fr

G Tchuenté-Foguem

C Foguem

Conceptual graph operations for formal visual reasoning in the medical domain

Keywords: Knowledge representation, Conceptual graphs, Visual reasoning, Formal semantics, Clinical guidelines and protocols, Heart failure

Objective. -Conceptual graphs (CGs) are used to represent clinical guidelines because they support visual reasoning with a logical background, making them a potentially valuable representation for guidelines. Materials and methods. -Conceptual graph formalism has an essential and basic component: a formal vocabulary that drives all of the other mechanisms, notably specialization and projection. The graph's theoretical operations, such as projection, rules, derivation, constraints, probabilities and uncertainty, support diagrammatic reasoning. Results. -A conceptual graph's graphical user interface includes a multilingual vocabulary management, some query and decision-making facilities and visual graph representations that are simple and interesting for user interactions. The described proposition using the Conceptual Graph user interface (CoGui) improves the performance of the actors in the diagnostic context of heart failure with preserved ejection fraction. Discussion. -CGs capture the essential features of the medical processes underlying clinical reasoning. CGs are indeed useful as a way for the physician to represent guidelines, and well-defined semantic representations allow users to have a maximal understanding of the knowledge reasoning process. Conclusion. -CG operations of visual representations that uncover some of the actual complexities of clinicians' reasoning have been tested in clinical guideline comprehension and used to translate text and diagrammatic guidelines into computer interpretable representations.

Introduction: background and significance

Currently, computer systems are ubiquitous in the medical domain and are important components in health information systems. Especially within the field of medical decision-making, these systems are designed to support the decision-making of junior and senior clinicians by providing a comprehensive monitoring of data analysis and understandable therapy recommendations [START_REF] German | An architecture for linking medical decision-support applications to clinical databases and its evaluation[END_REF]. Intelligent patient monitoring systems estimate the patient's health status with its evolution and make therapy management suggestions [START_REF] Klimov | Intelligent querying, visualization, and exploration of the time-oriented data of multiple patients[END_REF]. The graphical user interface supports the display of information for the native target platform on different workstations and the transmission of commands. These associated user interfaces can provide a clinician a discrete overview of a patient's status (through clinical phases) with the detection of clinically meaningful abnormalities (e.g., a state of decreased blood volume known as hypovolemia). In such situations, the progression of hemodynamic abnormality is represented by a sequence of clinical phases, which reflect the involved predominant physiological process (e.g., increased pericardial pressure, vasodilatation, and hypotension) [START_REF] Kamsu-Foguem | User-centered visual analysis using a hybrid reasoning architecture for intensive care units[END_REF]. Clinical guidelines are a valuable means of standardizing and improving health care. The computerization of the guideline execution process is a basic step towards its pervasive use in health care systems. Therefore, some projects focus on the direct execution of guidelines for related tasks, such as the recognition of care providers' intentions and assessing their actions (for a review see [START_REF] Isern | Computer-based execution of clinical guidelines: a review[END_REF]). These projects encompass the description of a machine-readable language for sharing clinical guidelines and for useful and flexible automated assistance in the execution of these guidelines. In automation initiatives, the guideline support architecture includes, among other modules, a temporal-abstraction module, a task-specific reasoning module and a domain-specific knowledge basis. As a knowledge-driven guideline enactment, the expressiveness of modern ontology languages is used to provide the semantics required to support the execution of clinical guidelines [START_REF] Isern | Ontology-driven execution of clinical guidelines[END_REF]. Meanwhile, there are some issues that restrict their application, such as therapeutic recommendations that do not illustrate very comprehensive expressions. One of the most fundamental questions is how to specify a visual language. Indeed, many approaches have been used in textual logic formalisms for reasoning with a declarative specification of control. Another option is the direct incorporation of visual expressions into a logical formalism, thus connecting the reasoning capabilities of logical systems with the expressiveness of graphical communication. The roots of formal visual reasoning date back to Charles Sanders Peirce and his existential graphs, which are a visual notation for first-order logic [START_REF] Roberts | The existential graphs of Charles S. Peirce (Approaches to semiotics[END_REF]. Sowa's work defines a formal reasoning system of well-formed diagrams as conceptual graphs that can be used as a valid basis of formal proofs [START_REF] Sowa | Conceptual structures: information processing in mind and machine[END_REF]. The work of Chein and Mugnier extends this idea by integrating graph theory operations into conceptual graph formalism, thus obtaining the ability to visually specify consistent knowledge representations and formal reasoning [START_REF] Chein | Graph-based knowledge representation: computational foundations of conceptual graphs[END_REF]. These authors formulate valid transformation rules for reasoning with conceptual graph operations that are defined by mapping them to predicate calculus theory. Thus, graphical reasoning rules are just as powerful and valid as their textual counterparts. For this reason, we are interested in using visual expressions as a means of logical reasoning instead of the desire to use logic for reasoning about visual expressions. Therefore, our work is considerably concerned with the formal syntactic specifications of diagrams that are well-founded and complete with respect to logical semantics, precisely in the context of medical knowledge representation. The remainder of this paper is organized as follows: Section 2 presents materials and methods with conceptual graph formalism. Section 3 provides useful reasoning principles from effective CGP modeling applications. Sections 4 and 5 present discussions with concluding statements about the proposed formal visual approach for the medical domain.

Materials and methods

Conceptual graph formalism

Formal vocabulary with support

A support is a 3-tuple S = (T C , T R , I) [START_REF] Sowa | Knowledge representation: logical, philosophical, and computational foundations[END_REF]. T C and T R are two partially ordered finite sets, respectively, of concept types and relations types. T R is partitioned into subsets T R 1 . . .T R k of relation types of arity 1. . .k, respectively (k ≥ 1). Both orders on T C and T R are denoted by ≤ (x ≤ y means that x is a subtype of y). I is a countable set of individual markers describing specific entities. T C , T R and I are pairwise disjoints. All supports also possess the marker *, known as a generic marker describing an unspecified entity. The set I ∪ {*} is partially ordered in the following manner: * is the greatest element and elements of I are pairwise incomparable.

Definition of a simple conceptual graph

A simple conceptual graph G, defined over a support S, is a finite bipartite multigraph (V = (V C , V R ), E, L) [START_REF] Chein | Graph-based knowledge representation: computational foundations of conceptual graphs[END_REF]:

• V C and V R are the node sets, respectively, of the concepts nodes and of the relations nodes; • E is the multi-set of edges. Edges incident to a relation node are totally ordered; • each node has a label given by the mapping l. A relation node r is labeled by type (r), an element of T R , and the degree of r must be equal to the arity of type (r); • a concept node c is labeled by a pair (type (c), marker (c)), where type (c) is an element of T C known as its type, and marker (c) is an element of I ∪ {*}.

Conceptual graph operations

Conceptual graph operations provide operational mechanisms, such as inference mechanisms, allowing for manipulations to which the knowledge-based system is dedicated. For instance, to perform automatic reasoning, the conceptual graph operations allow for the representation of derivation rules and for the effective application of these rules to a set of facts with constraints. This application is useful for specifying and sharing decision and eligibility criteria, patient state definitions, conditions, and system actions.

The fundamental operation for performing these reasoning mechanisms is the projection, which leads to a calculation in the specialization between two graphs. Indeed, the projection search of a graph G (request graph) in a graph H (context graph) can be observed as the inclusion search of the knowledge represented by G in H. Intuitively, the existence of a projection from G to H means that the knowledge represented by G is contained in (or implied by) the knowledge represented by H, and the projection operation is a global view of a specialization operation sequence (the elementary specialization operations [disjoint sum, join, restrict, relation simplify and copy] that is graphically and logically defined in [START_REF] Mugnier | On generalization/specialization for conceptual graphs[END_REF]). The reasoning processes are logically founded because the projection is well-founded and complete with respect to the deduction in first-order logic [START_REF] Chein | Conceptual graphs: fundamental notions[END_REF]. Another essential point is that the reasoning processes operate directly on the defined pieces of knowledge and can be visually explained to the end user. Within our work, the projection operation is used to search for the existence or absence of certain states/plans in a CGP representation. In Fig. 1, a projection is feasible because the concept "Surgical Plan" is a specialization of the concept "Therapeutic Plan" and because the "Infected Pancreatic Necrosis" concept is a specific type of "Disease". The context graph can be interpreted as "There is an Infected Pancreatic Necrosis revealed by a Diagnostic Plan, and a Surgical Plan treats this disease (Infected Pancreatic Necrosis, the most severe form of acute pancreatitis, which is responsible for most cases of pancreatitis-related morbidity and mortality)". The request can be interpreted as "is there a Therapeutic Plan treating a disease?" The projection graph provides the response, which can be interpreted as "There is Surgical Plan that is treating an Infected Pancreatic Necrosis". The current medical philosophy is to perform surgery in a later phase of the acute necrotizing pancreatitis when the intensive non-surgical treatment fails [START_REF] Uomo | Nonsurgical treatment of infected pancreatic necrosis: a falling myth or a still impassable frontier[END_REF]. An example of a projection operation is described in the following (Fig. 1).

This conceptual graph projection can be extended with an implementation of a depth-attenuated distance (between types in the vocabulary) or graph transformations, allowing for an approximate search [START_REF] Achour | A UMLS-based knowledge acquisition tool for rule-based clinical decision support system development[END_REF][START_REF] Genest | A content-search information retrieval process based on conceptual graphs[END_REF].

Graph rules and derivation

The conceptual graph rules allow for the addition of new knowledge. The graph rule is composed of a hypothesis and a conclusion and is used in the classical way. Given a simple graph, if the hypothesis of the rule projects to the graph, then the information contained in the conclusion is added to the graph.

Logical semantics: it has previously been demonstrated that conceptual graph rules can be described by means of a first-order logic augmented with temporal operators [START_REF] Baget | Extensions of simple conceptual graphs: the complexity of rules and constraints[END_REF]. A conceptual rule R (G 1 ⇒ G 2 ) is a pair of -abstractions (x 1 ,. . .,x n G 1 ,kx 1 ,. . .,x n G 2 ), where x 1 ,. . .,x n , known as connection points, enable one to link concept vertices of the same label of G 1 and G 2 . The logical interpretation of a conceptual rule R (G 1 ⇒ G 2 ) is defined as follows:

(R) = ∀x 1 . . . ∀x n (x 1 . . . x n G 1 ) ⇒ (x 1 . . . x n G 2 ). The semantic (provided in [Sowa 84]) maps each simple conceptual graph G into a first-order logic formula (G). When a rule is applied in a forward chaining to a conceptual graph, the information of the rule is added to the conceptual graph.

Rules are categorized as static rules and dynamic rules.

Static rules

Static rules express some immutable domain laws, and their utilization completes word descriptions. For a medical knowledge model to support common-sense query processing, it must provide a set of rules of deduction, known as axioms. Some specific mathematical relations (such as symmetry, transitivity) can be defined with static rules expressing knowledge, which is valid every time and reflects the common sense of the medical domain. For example, the notion of a symmetric relation is described with the conceptual graph type, which semantically characterizes the class of all relations that are symmetric. For this purpose, a rewrite rule is implemented to reflect the semantics of a symmetric relation. According to the rule notation in conceptual graphs, the explicit representation of this symmetry property of a relation is shown in Fig. 2. The logical interpretation of the conceptual graph rule R for a symmetry property of a relation is defined as follows:

(R) = ∀x, ∀y

(Concept Type (x) ∧ symmetric relation (x, y) ∧ ConceptType (y) ⇒ ConceptType (x) ∧ symmetric relation (y, x) ∧ Concept Type (y)).
In Fig. 3, another rule is presented in the style of the diagrammatic representation of conceptual graphs. More formally, this rule says: "for all treatments x, protocols y and diseases z, if y has for object z, then x and y are pertaining to a common disease z".

Dynamic rules

Dynamic rules define possible transitions from one word to another. The successor of a valid word is obtained by a single application of a transformation rule on this word. The condition of an ICU patient often changes, and the medical support that he/she requires can vary at any time. Therefore, it is vital to review major medical measurements frequently and to change the treatment settings accordingly with respect to the application of a guideline. Capturing CGPs in ICUs also includes treating time-oriented, dynamically changing, and vague information and data due to the time critical situation, which asks for time critical actions. Likewise, dynamic graph rules are useful to explicitly express some temporal properties, which include concurrent, cyclical and sequential actions (e.g., to perform history and physical examinations before ordering certain tests). Experimental results will show the major rules according to the efficiency of the execution devices corresponding to medical decision-making, such as a respiratory monitoring expert system that recommends action be taken to avoid breathing complications [START_REF] Guyet | Knowledge construction from time series data using a collaborative exploration approach[END_REF]. Rules are of the form: "If qualitative state then action", where qualitative state can be a symbolic representation of a change in pulmonary arterial pressure over time (e.g., "pressure is rising rapidly", Fig. 4). Pulmonary hypertension is present when the mean pulmonary artery pressure exceeds 25 mm Hg (3300 Pa) at rest or 30 mm Hg (4000 Pa) with exercise [START_REF] Nauser | Diagnosis and treatment of pulmonary hypertension[END_REF]. More generally, it is possible to model the fact that (1) a state in the guideline is active, (2) an action has been performed or (3) the patient has a specific clinical condition.

Medical rules such as IF [Diagnosis: Infection] THEN [Order] → (Object) → [Therapy Plan: X] certainly have a dynamic interpretation: if at a time interval [t1 t2] a diagnosis of a state (e.g., a qualitative state of rising fever, or a rising concentration of antibodies) of infection has been reached, then the therapy plan X for diagnostics of the infection should be started after t2. Some specific heuristics are defined with rules expressing knowledge, which are valid only after a longer time period and reflect very individual experiences with patients. Due to the correspondence between conceptual graphs and RDFS (resource description framework schema) language [START_REF] Yao | Automated conversion between different knowledge representation formats[END_REF], conceptual graph rules can also be represented in SWRL (Semantic Web Rule Language [START_REF] Horrocks | OWL rules: a proposal and prototype implementation[END_REF]) rules and vice versa without losing their semantic meaning. Rules expressed in formalisms such as RuleML (Rule Markup Language [START_REF] Park | Rule identification using ontology while acquiring rules from Web pages[END_REF]) or SWRL additionally allow for one to specify the actions to take, knowledge to derive, or constraints to enforce. This approach suffers from a series of drawbacks due to the expressiveness and visual capabilities of SWRL. In addition, there are some mappings between subsets of CGs and subsets of description logics (DLs) [START_REF] Borgida | On the relative expressiveness of description logics and predicate logics[END_REF][START_REF] Motik | Representing ontologies using description logics, description graphs, and rules[END_REF] and its different versions, including Web Ontology Language-DL (OWL-DL) [START_REF] Ruiz | Supporting concurrent ontology development: framework, algorithms and tool[END_REF], because of their common ancestral existential graphs.

Positive and negative constraints

A constraint defines conditions for a simple graph to be valid. It is composed of a conditional part and a mandatory part. Roughly speaking, a graph satisfies a constraint if for every projection of its conditional part, its mandatory part also projects on the graph [START_REF] Baget | Extensions of simple conceptual graphs: the complexity of rules and constraints[END_REF]. We consider positive and negative constraints. A positive constraint expresses a property such as "if information A is present, then information B must also be present". For example, "any patient with impaired lung function must have a medical assistance to maintain artificial oxygen and normal carbon dioxide levels or patients should be managed in the intensive care environment if they have any cardiovascular instability, are unable to maintain an airway, have obtundation or acute abdominal symptoms" [START_REF] Magee | Management of decompensated diabetes. Diabetic ketoacidosis and hyperglycemic hyperosmolar syndrome[END_REF]. A negative constraint expresses a property such as "if information A is present, then information B must be absent". An example of a negative constraint is "a patient must not receive two incompatible treatments". Another example is "a therapy failure context that leads to a rather unsatisfactory situation in which the treatment is incompatible with the current diagnosis". In Fig. 5, the first part of the previous example fits to the "therapy failure context" box because it describes a situation in which the therapeutic plan (start 2/3/2012 and end 5/6/2012) is unsatisfactory because the disease is not regressive (no amelioration in the state of a patient) and because the second part contains an incompatibility with the current diagnosis.

More generally, conflict contexts express that data are viewed to be inconsistent or that medical plans may raise conflicts and that certain links between them are then not allowed due to their characteristics. The semantic verification of a guideline representation consists in checking that the guideline representation Fig. 5. A negative constraint modeling an incompatibility. respects a set of constraints given by a medical expert. This verification is performed by means of the projection operation of conceptual graphs.

The mechanism of the semantic verification of a conceptual graph consists of checking that a projection from any positive constraint exists and that a projection from any negative constraint does not exist in this conceptual graph [START_REF] Baget | Extensions of simple conceptual graphs: the complexity of rules and constraints[END_REF]. Thus, it becomes easy to visually show to the user where the anomalies occur with the identification of the constraints that are not satisfied in terms of conceptual graphs, which is very similar to the manner CGPs are modeled. In turn, this fact simplifies the application of our approach because the medical expert does not have to take care of the technical details of a complex logic formula. Additionally, it is possible to study the refinement restoring the coherence and completeness of a conceptual graph knowledge base, which is not semantically valid with respect to constraints [START_REF] Dibie-Barthélemy | A semantic validation of conceptual graphs[END_REF].

Modeling probabilities and uncertainty

Conceptual graphs support the modeling of probabilistic or uncertain knowledge: knowledge about which we are not completely sure, or where we can only make predictive statements based on our past observations. There are at least two different ways to consider probabilistic situations from a knowledge point-of-view. One is that we know for certain that the situation will exist in a certain percentage of the time. Another is that there is some causal relationship between the situation and some other situation(s). Complex and multifactorial metabolic changes very often lead to damage and the functional impairment of many organs, such as blood vessels (angiopathy) or the hypomagnesemia in diabetes mellitus. During diabetes, metabolic remodeling precedes the microangiopathy (retinopathy, neuropathy, nephropathy or cardiomyopathy) and the hypomagnesemia that may manifest as arrhythmias, muscle weakness, convulsions, stupor, and agitation. In particular, it is possible to represent in a conceptual graph form probabilistic situations, such as the "hypomagnesemia may be present in up to 90 percent of patients with uncontrolled diabetes [START_REF] Regg | Hyperosmolar hyperglycemic state[END_REF]" (Fig. 6). Unless the patient is in renal failure, the administration of magnesium is safe and physiological [START_REF] Kitabchi | Hyperglycemic crises in diabetes mellitus: diabetic ketoacidosis and hyperglycemic hyperosmolar state[END_REF]. An important feature of a conceptual graph system for probabilistic reasoning is that its active relations (computer codes with pragmatic intent) can glean probabilities from available external sources, either from tables, previously performed correlations or by the data mining of relevant information from databases [START_REF] Delugach | Grounded Conceptual Graph Models[END_REF].

In addition, Thomopoulos et al. have introduced an extension of the conceptual graph model suitable for the representation of Fig. 6. Example of probabilistic effect modeling. data, which are modeled using fuzzy sets [START_REF] Thomopoulos | Representation of weakly structured imprecise data for fuzzy querying[END_REF]. This extension introduces a new way of comparing conceptual graphs, which uses a more flexible comparison of fuzzy conceptual graphs and allows us to exploit the semantic similarity of knowledge in prediction methods. From reasoning and problem solving viewpoints, the resulting advantage is the ability to reach conclusions from some modeled situations even if some of the conditions are not really precise or uncertain [START_REF] Buche | Fuzzy concepts applied to the design of a database in predictive microbiology[END_REF].

Results

The proposed methodology is implemented in the Conceptual Graph user interface (CoGui). CoGui is a user-friendly tool for building conceptual graph knowledge bases with a semantic query mechanism as well as an inference and verification services, which are provided by the projection operation, inference rules and constraints [START_REF]CoGui (Conceptual Graphs user interface)[END_REF].

Verification of CGPs' properties

CoGui provides a tool suite for formal specification and automatic model-based verification [START_REF] Carloni | Introducing reasoning into an industrial knowledge management tool[END_REF]. The verification approach, in the sense of formal evidence, consists of proving properties by implementing a set of reasoning mechanisms (backward, forward and consistency checking). In other words, functionalities for proving the CGP's logical properties will result in the application of graph rules and constraints to other graphs representing the process of the CGP until we obtain the graph describing the property. The demonstration of a property is performed in two steps [START_REF] Kamsu-Foguem | Requirements modeling and formal analysis using graph operations[END_REF]. It consists of applying the effective rules to the graph describing a process of the CGP and then considers domain constraints to establish the consistency of the resulting graph. Finally, such proof shall be established because there is a projection of the property in the last graph constructed.

Interpretation of the verification findings

The purpose of verification is to prove (or disprove) that a CGP or its model satisfies specified properties, and it is instructive to interpret failures of proof. Failures of proof relating to the result of a model do not satisfy a property, can highlight a failure (redundancy, inconsistency, incompleteness) in the considered model and can help remove undesirable situations that interfere with a coherent approach to interventions [START_REF] Foguem | Using conceptual graphs for clinical guidelines representation and knowledge visualization[END_REF]. For example, contradictions in the model can mean some interesting ideas about the review and update of the protocol. These contradictions may reflect conflicting or infeasible specifications in the current functioning, the confusion of terminology and objectives or the limits of resource capacity. In the formalization of our case studies, we considered failures resulting in proof verification as a means to discover problems and then we acquired new knowledge to supplement or redefine the description of the processes implemented by the protocol.

Details of the implementation

The implementation of this model in the CoGui software allows the automatic processing of reasoning that can be viewed as graph operations: response to a question by selecting a subgraph, enrichment of knowledge through the insertion of a sub-graph or verification of a knowledge base with constraints checking. In our contextual case, trained physicians can use the CoGui editing tool to translate structured textual form of information into an executable model of formalized knowledge (production rules for typical medical procedures).

Furthermore, the integration of the CoGui software tool into the work processes of all users requires a socio-technical approach taking into account the human, organizational and technological factors that influence the "usability", adoption and ownership by clinicians.

Beyond the work processes of clinicians, the consideration of the attributes associated to local context in the deployment of a medical information system greatly affect the success or failure of the system. In particular, in our context, the following factors have a positive impact on physician performance:

• system integration with other applications in the clinical information system; • the incorporation of the objectives of quality, safety and efficiency of care, useful feedback to the clinician; • presentation by the system of elements and recommendations that can assist the clinicians in addressing complex problems; • their possible insertion points in the clinical work processes through reviews, documented policies and procedures.

The semantic verification of a compliance checking between clinical guidelines and specified requirements consists in checking that the clinical guideline models respects a set of specifications described in a target list of medical procedures. This verification is done by means of the reasoning operations of conceptual graphs (specifically semantic graph mapping). Structure-preserving mappings between two conceptual graph structures are the major formal procedures for different reasoning mechanisms with conceptual graph operations (projection, rules and constraints), and there are based on the logical subsumption when considering the logical formulas associated with conceptual graphs.

However, the running time of conceptual graph operations is in general exponential, for numerous special classes of graphs (e.g. Acyclic graphs, Planar graphs, Permutation graphs), the conceptual graph operations have polynomial-time algorithms, and in practice it can habitually be solved efficiently [START_REF] Arvind | Isomorphism testing: perspectives and open problems[END_REF]. It has been showed that the query evaluation and query containment problems of relational structures and databases are equivalent to the fundamental reasoning (i.e. semantic graph mapping) with conceptual graph operations, in the case of conjunctive, positive and non-recursive queries [START_REF] Chein | Graph-based knowledge representation: computational foundations of conceptual graphs[END_REF].

Diagnosis of heart failure with preserved ejection fraction

The evaluation is conducted using a conceptual graph modelling applied to the diagnosis of Heart failure in the Elderly. The importance of early identification of a Heart failure in elderly patients cannot be overemphasized. Particularly, the appropriate analysis of some features of heart failure with preserved ejection fraction (HFpEF) is an essential health issue. Four clinical queries have been established with a geriatric specialist and a co-author of this document. These queries are inspired by the diagnostic flow chart for heart failure with preserved ejection fraction [START_REF] Keulenaer | Heart failure with preserved ejection fraction[END_REF] and the diagnostic criteria take account of clinical evaluation of haemodynamic and muscular pump performances. The specific details of these queries are inseparable from the level of complexity facing geriatricians and cardiologists today (Table 1).

A number of nine physicians have participated in the evaluation of the proposed approach for semantic modelling and visual reasoning of medical knowledge with conceptual graph representation. The average consistency mark for query types answered with CoGui and classical textual way are compared with this preliminary evaluation done in the geriatric context. This is performed on patients with HFpEF to assess diagnosis and analysis elements to be taken into account together with the improvement of its interpretation to adapt to various clinical situations. CoGui has encouragingly greater consistency marks for all types of queries when compared to classical way with textual documents (Table 2).

According to the obtained results associated with the gathered opinions of the nine participating physicians, we can conclude the described proposition using the CoGui software improves the performance of the actors in the diagnostic context of heart failure with preserved ejection fraction.

Discussion

In this section, we report on our observations during the modeling phase of the guideline. The proposed conceptual graph approach is currently being tested in a French Hospital Center. We have currently used this approach for guideline representation only in collaboration with the medical doctors of this hospital. During the modeling phase with conceptual graphs, the preliminary results observed demonstrated that end-users have an easier time constructing usable guidelines and that this manner of representing machine-readable guidelines is interesting for enabling appropriate decision support. The formalization of such guidelines in the conceptual graphs formalism is easily performed by knowledge engineers in a close collaboration with medical domain experts. This formal medical knowledge representation enables us to provide an unambiguous scheme of the medical decision process (causal and revision contexts), to draw the medical domain expert's or knowledge engineer's attention to data entries that do not exactly fit into the current view of the patient's situation (e.g., it supports reminder messages about conflict contexts when a graph constraint is violated), and to support the decision process by providing knowledge that is suitable for use in a plan of action for a patient. In addition, intuitive and visual descriptions have been shown to improve understanding and self-management in patients with chronic diseases [START_REF] Frøisland | Improving diabetes care for young people with type 1 diabetes through visual learning on mobile phones: mixed-methods study[END_REF].

Comparison to alternative clinical models

The conceptual graph models have advantages over framebased models in expressing certain forms of modeling (e.g. mapping properties into nested contexts) and in providing a visual reasoning that facilitates an intuitive understanding. In addition, conceptual graphs can be easily translated into the terminology of some other approaches in knowledge engineering, such as Resource Description Framework Schema (RDFS) [START_REF] Yao | Automated conversion between different knowledge representation formats[END_REF] and the Web Ontology Language (OWL) [START_REF] Horrocks | OWL rules: a proposal and prototype implementation[END_REF] mainly applied in connection with the Semantic Web framework [START_REF] Shadbolt | The semantic web revisited[END_REF]. As a result, it generates the possibility to interact and exchange the modeled knowledge with internal and external collaborators.

In fact, modern terminologies (e.g., SNOMED-CT and NCI Thesaurus) are being formalized using Description Logics (DLs) [START_REF] Baader | The description logic handbook: theory, implementation, applications[END_REF]. Since DLs and CGs are both rooted in semantic networks and logically founded, the question of their relationships has often been asked. As well as similarities between DLs and CGs, there are specific interesting features: cycles, n-ary relations, and type-hierarchy for CGs, the style of symbolic, variable-free formulas, variety of constructors with different levels of expressiveness for DLs. Besides visual reasoning facilities, the syntactical possibilities of the graphs, including identity, graphs that contain circles, graphs that are not connected, etc., allow graphs to be constructed that do not have counterparts in DLs [START_REF] Dau | A diagrammatic reasoning system for the description logic[END_REF].

The work of Carloni et al. connects topic maps and conceptual graphs. They show that the topic maps (and especially those describing the domain ontology and annotation base) can be reliably linked to a subfamily of conceptual graphs [START_REF] Carloni | Introducing reasoning into an industrial knowledge management tool[END_REF]. The transformation from topic maps to conceptual graphs is formal and reversible, which allows, on one hand, integration of graphical reasoning outcomes into a knowledge management tool based on topic maps and, on the other hand, enrichment of this tool by conceptual graph operations (constraints and rules) for consistent verification and inference of useful knowledge.

Evaluation through experiences with clinicians

The formalized knowledge modeling approach can be implemented on various parts of clinical activities (prevention, diagnosis, treatment, medical follow-up of patients, etc.). Meanwhile, we are primarily interested in the management of acute or chronic diseases (cardiovascular diseases, diabetes, neurodegenerative diseases, etc.). In the purpose to standardized practices for doctors in the same country and across the world, medical guidelines are established to benefit from emerging medical advances, latest discoveries in others scientific fields and societal evolution. These recommendations and guidelines based on evidence-healthcare, quality, consistency and costs, are generated by associations of experts ("consensus conferences") that disseminate up-to-date knowledge and best practices.

These guidelines are not static and need to be revisited when a discovery is done or new practices from a doctor or some doctors are approved by their colleagues during international or national consensus conferences or diseases consortium. The continued training of doctors allows also changes or new strategies for the prevention, diagnosis and treatment of diseases. The process of knowledge formalization requires the analysis, adaptation and progressive structuring of clinical guidelines and validation of resulting knowledge bases. This structuring process also allows identifying the ambiguities that need to be resolved; it also helps to identify incompleteness of guidelines on certain clinical situations. These situations already need to be carefully examined and in many cases require explicit recommendations that pertain to the type of information collected and the type of clinical guidelines being used.

For instance, with regard to conceptual graph modelling applied on diagnosis of Heart failure in the Elderly, the continuous identifications of some features of HFpEF is important. Conceptual graphs allow us to make dynamic knowledge modelling with visual interactions and this can contribute to providing appropriate medical care for this disease. HFpEF is the clinical syndrome of heart failure associated with normal or near-normal systolic function. HFpEF is particularly common in older hypertensive women, and hypertension plays a key role in its pathophysiology [START_REF] Chen | Heart failure with preserved ejection fraction in older adults[END_REF]. Despite these worrisome epidemiological trends, pathophysiological mechanisms underlying HFpEF and diagnostic or therapeutic strategies remain uncertain. Treatment of HFpEF remains empirical and centered around the control of blood pressure and volume status [START_REF] Oghlakian | Treatment of heart failure with preserved ejection fraction: have we been pursuing the wrong paradigm?[END_REF].

The formal knowledge representation with conceptual graph formalism is used to describe and understand the knowledge elements extracted from clinical recommendations or expert advice as in the example above. In view of the reasoning operations through conceptual graph knowledge representation, we are in a dynamic process that invites the reader to participate in the construction of semantic modeling which facilitates identification of ambiguities, inconsistencies and incompleteness. Furthermore, the integrated management of clinical guidelines, as the management of the entire medical knowledge representation, is a pro-active process that has to be reactivated at regular intervals to keep up with the dynamic collaborations among the members of the medical scientific community in order to improve certain procedures in complex disease management.

Conclusion

In this document, we present an approach using the expressive power of visualization within conceptual graph formalism, and these graph operations are used as a valid basis of formal reasoning. This process defines a formal reasoning system of well-formed diagrams and specifies semantic relationships between these diagrams. Reasoning with diagrammatic representations enables a system to draw inferences from diagrammatic information, to solve problems posed diagrammatically, and to communicate visual findings and lessons learned [START_REF] Anderson | Diagram processing: computing with diagrams[END_REF]. The rigorous formalization of CGPs with diagrams of CGs is performed, and visual transformation procedures are applied. Therefore, provable CGP properties, defined by health care organizations, can be established using only visual procedures. The proposed approach makes a casual assessment of their potential benefit to the formal modeling of CGPs that can assist with the detection and the explanation of new and potentially threatening events. For example, the physician's attention can be drawn to significant changes in the patient's clinical signals, and the diagnostic conclusions provided by the CGP's recommendations can be translated into CGs according to the particular setting (e.g. diagnosis of HFpEF). Likewise, the reasoning process can follow the user's natural cognitive processes and structures [START_REF] Patel | Cognitive psychological studies of representation and use of clinical practice guidelines[END_REF][START_REF] Arocha | Identifying reasoning strategies in medical decision making: a methodological guide[END_REF]. The advanced focus will be on the wide spread deployment of proposed reasoning systems for the interaction between the CoGui tool and an intelligent monitoring system with large biomedical ontologies alignment [START_REF] Ba | Large-scale biomedical ontology matching with Ser-vOMap[END_REF] in operating rooms and intensive care units. Further validation tests should be planned before evaluating the developed user interface during clinical testing in the operating theater. We are also interested in the emerging trends impacting on electronic healthcare reports in decision-making [START_REF] Bricon-Souf | Theme C: medical information systems and databases -results and future work[END_REF]. In addition, in other medical applications [START_REF] Kamsu-Foguem | Conceptual graph-based knowledge representation for supporting reasoning in African traditional medicine[END_REF][START_REF] Foguem | Verifying a medical protocol with temporal graphs: The case of a nosocomial disease[END_REF], we have emphasized the temporal reasoning formalization in conceptual graphs.

Fig. 1 .

 1 Fig. 1. Example of a projection search.

Fig. 2 .

 2 Fig.2. The CG rule that encodes for the symmetry property of symmetric relations.

Fig. 3 .

 3 Fig. 3. Example of a static rule in a diagrammatic representation of CGs.

Fig. 4 .

 4 Fig. 4. Example of a dynamic rule of the form "If a qualitative state, then action".

Bernard

  Kamsu-Foguem: he has a PhD in Computer Science and Engineering from the University of Montpellier 2 in 2004. He got the "accreditation to supervise research", abbreviated HDR from INPT in 2013. His current interests are in Knowledge Discovery and Data Mining, Knowledge Representation, Formal Visual Reasoning, Ontology-based Semantic Analysis, Knowledge Exploitation for Collaboration, Decision Support Systems and Intelligent Systems. Application domains include Continuous Improvement process and Health Information Systems. He is a reviewer for a large number of international scientific journals such as Computers in Biology and Medicine, Knowledge Management Research & Practice, Interacting with Computers, Sensors, Engineering Applications of Artificial Intelligence and Knowledge-Based Systems. He is a member of the thematic group: e-Health of InterOP-VLab (International Virtual Laboratory for Enterprise Interoperability). Germaine Tchuenté-Foguem: she has a Master of Advanced Studies from the University of Yaoundé I (Cameroon) in 2007, in the domain of synchronization in dynamic distributed systems. She has a Research Master in automatic and decisional systems obtained in 2010 from ENIT-INPT of Tarbes (France) on Fuzzy logic in competence management. She is preparing a PhD thesis focused on a knowledge-based information system for visual support in critical decisionmaking. She currently takes an active interest in Computer information system(s) (e.g. algorithmic processes), information and communication technology, Data Warehouse, Data mining (Sequential rule mining, Sequential pattern mining or Association rule mining), Knowledge acquisition and Knowledge discovery.Clovis Foguem (MD): he is grounded in medical research applications of ICT.He is an Internal Medicine and Geriatric medical doctor and has undertaken a PhD on "Olfaction and Elderly: study of the olfactory (CN I) and trigeminal (CN V) sensitivities interactions in a geriatric population; constants and pathological specificities". He is also particularly interested in neurodegenerative diseases (as Parkinson disease or Lewy Body dementia), elderly epilepsy and whether pathogenic inflammatory or autoimmune responses can contribute to these disorders in the elderly. Moreover he is also interested in medical knowledge representation and medical clinic design guidelines. For his work on "Olfaction and Elderly", Dr C.Foguem was laureate of Health Research Award for emerging health researchers from the corporate foundation "Groupe Pasteur Mutualité" in 2011. Former Faculty of Medicine's Clinical Instructor, he is now Hospital Practitioner in France. He is peer-reviewer of many scientist journals among which: Clinical Interventions in Aging; Degenerative Neurological and Neuromuscular Disease; International Medical Case Reports Journal; Neuroscience and Neuroeconomics; Clinical Medicine Insights; Journal of the Pancreas; International Scholars Journals (ISJ); Cancer Therapy; Indian Journal of Critical Care Medicine and, African Journal of Environmental Science and Technology.

Table 1

 1 Instances of the four clinical queries used in the preliminary evaluation.

	Complexity	Instances of queries
	Easy evaluation	To find the symptoms or clinical signs of heart
		failure (left-sided failure, right-sided failure or
		biventricular failure)
	Moderate evaluation	To verify the preserved haemodynamic pump
		performance in transthoracic echocardiography:
		LVEF > 50%, LVEDVI > 97 mL/m 2
	Hard evaluation	To control the dysfunction of muscular pump
		performance resulting in impaired relaxation,
		suction and filling [blood flow Doppler, tissue
		Doppler imaging, Magnetic Resonance Imaging
		(MRI), invasive haemodynamic measurements and
		in some instance blood biomarkers (Natriuretic
		brain protein -BNP -and N-terminal pro-brain
		natriuretic peptide -NT-proBNP)]
	Hardest evaluation	To establish a diagnosis of heart failure with
		preserved ejection fraction
	Table 2
	Average consistency mark per query type in the evaluation.
	Complexity	Average consistency mark
		CoGui	Classical way
	Easy evaluation	7/9 = 0.78	6/9 = 0.67
	Moderate evaluation	8/9 = 0.89	4/9 = 0.45
	Hard evaluation	8/9 = 0.89	6/9 = 0.67
	Hardest evaluation	8/9 = 0.89	6/9 = 0.67

Disclosure of interest

The authors declare that they have no conflicts of interest concerning this article.


Glenn Merlet
email: glenn.merlet@gmail.com

Thomas Nowak
email: thomas.nowak@ens.fr

Hans Schneider

Sergeȋ Sergeev
email: sergiej@gmail.com

Generalizations of Bounds on the Index of Convergence to Weighted Digraphs*

Keywords: maximum walks, max algebra, nonnegative matrices, matrix powers, index of convergence, weighted digraphs I

Sequences of maximum-weight walks of a growing length in weighted digraphs have many applications in manufacturing and transportation systems, as they encode important performance parameters. It is well-known that they eventually enter a periodic regime if the digraph is strongly connected. The length of their transient phase depends, in general, both on the size of digraph and on the magnitude of the weights. In this paper, we show that certain bounds on the transients of unweighted digraphs, such as the bounds of Wielandt, Dulmage-Mendelsohn, Schwarz, Kim and Gregory-Kirkland-Pullman, remain true for critical nodes in weighted digraphs.

the whole system, i.e., the maximum of the transients of all edges (transitions) of the system. The bounds established in the works mentioned above were systematized and improved in a more recent work of Merlet et al. [START_REF] Merlet | Generalizations of bounds on the index of convergence to weighted digraphs[END_REF]. This begs the question which parts of the system are likely to have small resp. large local transients. The main idea here is as follows. The transient of the whole system, or in other words, the transient at a general node depends on the magnitudes of the weights associated with relevant connections (being time lags in some applications), and such transient can be arbitrarily big even for the systems with just two nodes [START_REF] Cohen | Analyse du comportement périodique de systèmes de production par la théorie des dioïdes[END_REF]. The bounds on such transient, given in the above mentioned works, can be rather complicated since they involve both the dimension of the system and the magnitudes of weights. However, this is not true for the so-called critical nodes. For these nodes, the present work (being a short version of [START_REF] Merlet | Generalizations of bounds on the index of convergence to weighted digraphs[END_REF]) presents new bounds that depend only on the system dimension as well as some graph-theoretic parameters.

More precisely, it is shown that six known bounds for the index of convergence, i.e., transient, of unweighted digraphs also apply to weighted digraphs, namely to the transients at critical nodes. Critical nodes are those that are included in a cycle of maximim mean weight (a more precise definition given in Section II.B).

To the authors' knowledge, this note (being a short version of [START_REF] Merlet | Generalizations of bounds on the index of convergence to weighted digraphs[END_REF] presents the first genuine extensions of the transience bounds for unweighted graphs to the weighted case. That is, the known bounds for unweighted graphs are recovered when specializing the bounds of this work to unweighted digraphs.

All other known bounds on the transients of weighted digraphs apply to the general transient of a system. They usually appear as the maximum of two expressions, the first of them being somewhat similar to the bounds discussed in this paper (although in general higher than at least one of them), and the second usually more complicated and depending on the magnitude of the weights. For instance, see [START_REF] Merlet | Weak CSR expansions and transience bounds in max-plus algebra[END_REF]. These general bounds are higher and hence less precise than those that will be presented in this note. In turn, the bounds presented in this note do not apply to the whole system but only to its "well-behaved" critical part.

The origin of the first of the bounds discussed in this note lies in Wielandt's well-known paper [START_REF] Wielandt | Unzerlegbare, nicht negative Matrizen[END_REF] where an upper bound for the exponent of a primitive nonnegative matrix was asserted without proof 5 . Dulmage and Mendelsohn [START_REF] Dulmage | Gaps in the exponent set of primitive matrices[END_REF] provided a proof of this result by interpreting it in terms of digraphs and they sharpened the result by using as additional information in the hypotheses the length of the smallest cycle of the digraph 6 . Schwarz [START_REF] Schwarz | On a sharp estimation in the theory of binary relations on a finite set[END_REF] generalized Wielandt's result to apply to all strongly connected digraphs by using Wielandt's bound for the cyclicity classes of the digraph, see also Shao and Li [START_REF] Shao | On the index of convergence of an irreducible Boolean matrix[END_REF]. Kim's [START_REF] Kim | An extension of the Dulmage-Mendelsohn theorem[END_REF] bound encompasses the first three and can be proved using Dulmage and Mendelsohn's bound in the cyclicity classes. Two other bounds generalized in this paper are the one due to Kim [START_REF] Kim | An extension of the Dulmage-Mendelsohn theorem[END_REF], and the one established by Gregory-Kirkland-Pullman [START_REF] Gregory | A bound on the exponent of a primitive matrix using Boolean rank[END_REF], both based on the concept of Boolean rank.

The six bounds mentioned above are stated in Theorem 2.2 and Theorem 2.4 after the requisite definitions. The main results of this paper and [START_REF] Merlet | Generalizations of bounds on the index of convergence to weighted digraphs[END_REF] are the generalizations of these bounds to weighted digraphs, as stated in Main Theorem 1 and Main Theorem 2. The proofs of these main results are sketched in Section III. For the full proofs, the reader is referred to [START_REF] Merlet | Generalizations of bounds on the index of convergence to weighted digraphs[END_REF]. Section IV is to give a brief summary of this work and to sketch a couple of directions for further research.

II. PRELIMINARIES AND STATEMENT OF RESULTS

A. Digraphs, walks, and transients

A walk in a digraph G = (N, E) is a sequence W = (i 0 , i 1 , . . . , i t ) of successive nodes in G. We denote the length of walk W by ℓ(W ). A cycle is a closed walk in which no node except the start and the end node appear more than once. A path is a walk in which no node appears more than once. A walk is empty if its length is 0.

To a digraph G = (N, E) with N = {1, . . . , n}, we associate its adjacency matrix, which is the Boolean matrix A = (a i,j ) ∈ B n×n defined by i,j = 1 if and only if G contains a walk of length t from i to j.

a i,j = 0 if (i, j) / ∈ E 1 if (i, j) ∈ E . (1)
Let G be a digraph with associated matrix A ∈ B n×n . The sequence of Boolean matrix powers A ⊗t is eventually periodic, that is, there exists a positive p such that

A ⊗(t+p) = A ⊗t (2)
for all t large enough. Call each such p an eventual period.

The set of nonnegative t satisfying (2) is the same for all eventual periods p. We call the least such t the transient (of periodicity) of G; we denote it by T (G). See [START_REF] Brualdi | Combinatorial Matrix Theory[END_REF] for general introduction to the theory of digraphs and [START_REF] Li | The index set problem for Boolean (or nonnegative) matrices[END_REF] for a survey on their transients. 7The digraph associated with A ⊗t will be further denoted by G t . Such graphs will be further referred to as the powers of G.

For a strongly connected digraph G, its cyclicity is defined as the greatest common divisor of the lengths of all cycles of G. The cyclicity d of G can be equivalently defined as the least eventual period p in [START_REF] Akian | Discrete max-plus spectral theory[END_REF]. If d = 1, then G is called primitive, otherwise it is called imprimitive. Let us recall the following basic observation from [START_REF] Brualdi | Combinatorial Matrix Theory[END_REF]. We denote the greatest common divisor of a and b by gcd(a, b). In particular, G d has exactly d strongly connected components, each of cyclicity 1. The node sets of these components are called the cyclicity classes of G. In terms of walks, nodes i and j belong to the same cyclicity class if and only if there is a walk from i to j whose length is a multiple of d. More generally, for each i and j there is a number s : 0 ≤ s ≤ d -1 such that the length of every walk connecting i to j is congruent to s modulo d. This observation defines the circuit of cyclic classes, being crucial for the description of G t in the periodic regime.

We will be interested in the following bounds on T (G). Prior to the formulation, let us introduce the Wielandt number

Wi(n) = 0 if n = 1 (n -1) 2 + 1 if n > 1 (3)
in honor of the first paper on the subject by Wielandt [START_REF] Wielandt | Unzerlegbare, nicht negative Matrizen[END_REF].

We denote the number of nodes of a digraph G by |G|. We also use the girth of G, which is the smallest length of a nonempty cycle in G, and denote it by g(G).

Theorem 2.2: Let G be a strongly connected digraph with n nodes, cyclicity d, and girth g. The following upper bounds on the transient of G hold: (i) (Wielandt [START_REF] Wielandt | Unzerlegbare, nicht negative Matrizen[END_REF], [START_REF] Wielandt | s proof of the exponent inequality for primitive nonnegative matrices[END_REF]

) If d = 1, then T (G) ≤ Wi(n); (ii) (Dulmage-Mendelsohn [10]) If d = 1, then T (G) ≤ (n -2) • g + n; (iii) (Schwarz [19], [20]) T (G) ≤ d • Wi n d + (n mod d); (iv) (Kim [13]) T (G) ≤ n d -2 • g + n.
Remark 2.3: The bound of Kim can be shown to imply the other three bounds in Theorem 2.2.

There are improvements of Theorem 2.2 in terms of the factor rank of a matrix A ∈ B n×n (also known as the Boolean rank or Schein rank). Factor rank of A is the least number r such that

A = r α=1 x α ⊗ y T α (4)
with Boolean vectors x 1 , y 1 , . . . , x r , y r ∈ B n . The factor rank of A is at most n since (4) holds when choosing r = n and the y α to be the unit vectors.

The following bounds involving the factor rank were established:

Theorem 2.4: Let G be a strongly connected primitive digraph with girth g, and let the associated matrix of G have factor rank r. The following upper bounds on the index of convergence of G hold:

(i) (Gregory-Kirkland-Pullman [START_REF] Gregory | A bound on the exponent of a primitive matrix using Boolean rank[END_REF])

T (G) ≤ Wi(r) + 1; (ii) (Kim [13]) T (G) ≤ (r -2) • g + r + 1.
In fact, the bounds in Theorem 2.4 also hold for nonprimitive matrices and that the analogous stronger bounds of Schwarz and Kim with the factor rank instead of n are true; we prove it in Main Theorem 2.

B. Weighted digraphs and max algebra

In a weighted digraphG, every edge (i, j) ∈ E is weighted by some weight a i,j . We consider the case of nonnegative weights a i,j ∈ R + and define weight of a walk W = (i 0 , i 1 , . . . , i t ) as the product

p(W ) = a i0,i1 • a i1,i2 • • • a it-1,it . (5)
Another common definition is letting edge weights be arbitrary reals and the weight of walks be the sum of the weights of its edges. One can navigate between these two definitions by taking the logarithm and the exponential.

By max algebra we understand the set of nonnegative real numbers R + equipped with the usual multiplication a × b = a • b and tropical addition a ⊕ b = max(a, b). This arithmetic is extended to matrices and vectors in the usual way, which leads to max-linear algebra, i.e. the theory of max-linear systems [START_REF] Akian | Max-plus algebras[END_REF], [START_REF] Butkovič | Max-Linear Systems: Theory and Algorithms[END_REF]. The product of two matrices

A ∈ R m×n + and B ∈ R n×q + is defined by (A ⊗ B) i,j = max 1≤k≤n a i,k •b k,j , which defines the max-algebraic matrix powers A ⊗t = A ⊗ . . . ⊗ A t times
. The (i, j)th entry of A ⊗t will be denoted by a (t) i,j . Boolean matrices are a special case of max-algebraic matrices.

The walks of maximum weight in G are closely related with the entries of max-algebraic powers of the associated nonnegative matrix of weights A = (a i,j ). Conversely, one can associate a weighted digraph G(A) to every square maxalgebraic matrix A. The connection between max-algebraic powers and weights of walks is based on the following fact called the optimal walk interpretation of max-algebraic matrix powers: a (t) i,j is the maximum weight of all walks of length t from i to j, or 0 if no such walk exists.

Let us also define the maximum geometric cycle mean:

λ(A) = max p(C) 1/ℓ(C) | C is a cycle in G(A) (6)
Set λ(A) = 0 if no nonempty cycle in G(A) exists. The cycles at which the maximum geometric cycle mean is attained are called critical, and so are all nodes and edges that belong to them. The critical graph, denoted by G c (A) = N c (A), E c (A) , consists of all critical nodes and edges. Cohen et al. [START_REF] Cohen | Analyse du comportement périodique de systèmes de production par la théorie des dioïdes[END_REF] have first proved that the sequence of max-algebraic matrix powers of an irreducible matrix A with λ(A) = 1 eventually periodic. Note that the case λ(A) = 1 can be reduced to this case by considering the matrix à = A/λ(A), which has λ( Ã) = 1. In the weighted case, the least nonnegative t satisfying (2) is called the transient of A.

In the present paper, we generalize all the bounds in Theorem 2.2 to the weighted case. We do this not by giving bounds on the transient of A, but by giving bounds on the transients of the critical rows and columns of A. Hereby, the transient of row i is the least t such that a

(t+p) i,j = a (t)
i,j for all j. The transient of a column j is defined analogously. In the Boolean case, all rows and columns are critical, hence we are really generalizing the Boolean bounds.

The following is the first main result of the paper.

Main Theorem 1:

Let A ∈ R n×n
(i) (Wielandt bound) Wi(n) (ii) (Dulmage-Mendelsohn bound) (n -2) • g(H) + |H| (iii) (Schwarz bound) d • Wi n d + (n mod d) (iv) (Kim bound) n d -2 • g(H) + n
The first two bounds also hold in the case when A is reducible.

For any k ∈ N c (A), we denote by T k (A) the transient of the kth row, i.e. the maximum transient of the sequences a (t) k,j with j ∈ N . We will just write it as T k if A is clear from the context.

Remark 2.5: Like in the Boolean case, the bound of Schwarz (resp. Kim) is tighter than the bound of Wielandt (resp. Dulmage and Mendelsohn) when the corresponding component of G is imprimitive. Further, the bound of Wielandt is never tighter than that of Dulmage and Mendelsohn when g(H) ≤ n -1. Unlike for the unweighted graphs, the case g(H) = n is non-trivial and will be treated below. Likewise, the bound of Schwarz is never tighter than the bound of Kim when g(H) d

≤ n d -1, but the case g(H) d
= n d has to be treated separately. Here we prefer to deduce the bound of Kim from the bound of Dulmage and Mendelsohn in the same way as the bound of Schwarz is derived from the bound of Wielandt (similar to the approach of Shao and Li [START_REF] Shao | On the index of convergence of an irreducible Boolean matrix[END_REF]).

In max algebra, the factor rank of A R n×n + is the least number r such that (4) holds for some x 1 , y 1 , . . . , x r , y r ∈ R n + . In our next main result, we show that the results of Main Theorem 1 can be improved by means of factor rank, thus obtaining a max-algebraic extension of Theorem 2. (i) Wi (r) + 1;

(ii) (r -2) • g(H) + h + 1. (iii) d • Wi r d + (r mod d) + 1; (iv) r d -2 • g(H) + r + 1.
The first two bounds apply to reducible matrices as well. Remark 2.6: All parameters appearing in the bounds of Main Theorem 1 only depend on the unweighted digraphs underlying G(A) and G c (A), but the factor rank r of Main Theorem 2 depends on the values of A, i.e., on the weights on G(A).

We prove that T k (A) for a critical index k is less than any of the quantities in Main Theorem 1 and Main Theorem 2. Applying the result to the transposed matrix A T , we see that the bounds also hold for the transients of the columns.

Our proofs do not use the results of Theorem 2.2 or Theorem 2.4 for the Boolean case and hence, in particular, we give new proofs for those classical results.

III. PROOF SKETCHES

In this section, we give proof sketches for the Main Theorems 1 and 2. The detailed proofs can be found in the full version of the paper [START_REF] Merlet | Generalizations of bounds on the index of convergence to weighted digraphs[END_REF].

A. Proof of Dulmage-Mendelsohn bound

We begin by recalling a result of Nachtigall [START_REF] Nachtigall | Powers of matrices over an extremal algebra with applications to periodic graphs[END_REF] concerning the transients of critical rows. The bound is formulated in terms of the shortest critical cycle that a node lies on. It shows that a stronger form of the Weighted Dulmage-Mendelsohn bound holds if k lies on a critical cycle of length g(H). However, if k does not lie on a shortest critical cycle of H, then it is worse. Our proof of the Dulmage-Mendelsohn bound relies on transfering Nachtigall's bound for nodes on a shortest cycle of H to the remaining nodes. Denote by A k• the kth row of A.

Lemma 3.1 (Nachtigall [17]): Let k be a critical node on a critical cycle of length ℓ. Then T k ≤ (n -1) • ℓ and ℓ is an eventual period of A ⊗t k•

The following result enables us to use the bound of Lemma 3.1 for nodes that do not lie on a critical cycle of minimal length. Its proof relies on the existence of a maxbalancing [START_REF] Schneider | Max-balancing weighted directed graphs and matrix scaling[END_REF] of matrix A.

Lemma 3.2: Let k and l be two indices of N c (A), and suppose that there exists a walk from k to l, of length r and with all edges critical.

(i) If t ≥ T l (A), then A ⊗(t+r) k• = A ⊗t l• . (ii) T k (A) ≤ T l (A) + r.
To prove the Dulmage-Mendelsohn bound, let C be a cycle in H of length ℓ(C) = g(H). By Lemma 3.1, T k ≤ (n -1) • g(H) for all nodes k of C. Let now k be any node in H. There exist walks in H from k to C of length at most |H| -g(H). Application of Lemma 3.2 now concludes the proof.

B. Proof of Kim bound

Set D = A ⊗d . The cyclicity classes of G(A) are strongly connected components of G(D), and the corresponding principal sub matrix of G(D) is completely reducible, i.e. it has no edge between two different strongly connected components. Obviously, any cycle in G(A) has to go through every cyclicity class. Thus, d divides g(H) and if k belongs to H the girth of its strongly connected components in G c (D) is at most g(H)/d.

Call a cyclicity class of G(A) small if it contains the minimal number of nodes amongst cyclicity classes. Let m be the number of nodes in any small class. By the weighted Dulmage-Mendelsohn bound, we have

T k (D) ≤ (m -2) • g(H)/d + m for each critical node k of H in a small class. Because T k (A) ≤ d • T k (D), this implies T k (A) ≤ (m -2) • g(H) + d • m for all critical nodes k of H in small classes.
We distinguish the cases (A) m ≤ ⌊n/d⌋ -1 and (B) m = ⌊n/d⌋. Note that m ≥ ⌊n/d⌋ + 1 is not possible.

In case (A), a crude estimation for all critical k in small classes is T k ≤ ⌊n/d⌋ -2 • g(H) + n -d. Because every critical node has paths consisting of critical edges to a small class of length at most d -1, Lemma 3.2 proves the Kim bound in case (A).

In case (B), there are at least d -(n mod d) small classes. There hence is a path of length at most (n mod d) consisting of critical edges to a small class. Hence, again by Lemma 3.2,

T k ≤ ⌊n/d⌋ -2 • g(H) + d • ⌊n/d⌋ + (n mod d) = ⌊n/d⌋ -2 • g(H) + n .
This concludes the proof in case (B).

C. Proof of Wielandt bound

If g(H) ≤ n -1, then the Wielandt bound follows from the Dulmage-Mendelsohn bound. It remains to treat the case that g(H) = n, i.e., G c (A) is a Hamiltonian cycle. We prove a result on cycle removal and insertion (Theorem 3.4) which implies the Wielandt bound for matrices with a critical Hamiltonian cycle. It relies on the following elementary application of the pigeonhole principle.

Lemma 3.3: Let x 1 , . . . , x n be integers. There exists a nonempty subset I of {1, . . . , n} such that i∈I x i is a multiple of n.

One can use this lemma for cycle decomposition arugments that lead to the following theorem.

Theorem 3.4: Let G be a digraph with n nodes. For any Hamiltonian cycle C H in G and any walk W , there is a walk V that has the same start and end node as W , is formed by removing cycles from W and possibly inserting copies of C H , and has a length satisfying (n -1) 2 + 1 ≤ ℓ(V ) ≤ (n -1) 2 + n and ℓ(V ) ≡ ℓ(W ) (mod n).

Theorem 3.4 can be used to prove the Wielandt bound in the case the critical graph is a Hamiltonian cycle.

D. Proof of Schwarz bound

The Schwarz bound is deduced from the Wielandt bound in the same way as the Kim bound is deduced from the i j k l n+α n+β n+γ

x α,i y α,j x β,j y β,k x γ,k y γ,l Fig. 1. A walk in G(Z)

Dulmage-Mendelsohn bound. That is, by regarding D = A ⊗d and using the Wielandt bound in small cyclicity classes.

E. Proof of the bounds involving the factor rank

In this subsection, we sketch the proof of Main Theorem 2. Let x α , y α ∈ R n + , for α = 1, . . . , r, be the vectors in factor rank representation [START_REF] Brualdi | Combinatorial Matrix Theory[END_REF]. Further, Let X and Y be the n × r matrices whose columns are vectors x α and y α for α = 1, . . . , r, and consider the (n + r) × (n + r) matrix Z defined by

Z = 0 n×n X Y T 0 r×r , (7)
Then we have

Z ⊗2 = A 0 n×r 0 r×n B , (8)
where the r × r matrix B is given by

b α,β = n i=1 y α,i • x β,i , for α, β = 1, . . . , r. (9)
We will apply the bounds of Main Theorem 1 to the critical nodes of B and transfer the result to the critical nodes of A, thanks to the following observation, which can be proved using Lemma 3.2.

Lemma 3.5:

If (k, n + β) is an edge of G c (Z), then T k (A) ≤ T β (B) + 1.
To use this lemma, we need to study the links between G c (Z), G c (A) and G c (B). If A is irreducible, then so are Z and B. Moreover G(B) and G(A) have the same cyclicity. By construction, G(Z) is a bipartite graph, so every walk in G(Z) alternates between nodes in {1, . . . , n} and nodes in {n + 1, . . . , n + r}. Figure 1

depicts an example of a walk in G(Z).

As all closed walks in G(Z) are of even length, the cyclicity of any component of G c (Z) is even, i.e. it is divisible by two. Hence each component G of G c (Z) splits into two components of (G c (Z)) 2 such that the (disjoint) union of their node sets is exactly the node set of G. We call these two components related. For a component H of (G c (Z)) 2 , the related component will be denoted by H ′ .

Each closed walk of G(Z) and, therefore, each component of G c (Z) contains nodes both from {1, . . . , n} and from {n + 1, . . . , n + r}. Hence, if H and H ′ is a pair of related components of (G c (Z)) 2 then one of them (say, H) contains a node in {1, . . . , n} and the other (H ′ ) contains a node in {n+1, . . . , n+r}. Since there are no edges between the two )). This allows us to transfer the bounds of Main Theorem 1 used for B to bounds on A via Lemma 3.5, adding only an additive constant of 1.

i 1 i 2 i 3 i 4 i 5 n+α1 n+α2 n+α3 n+α4 n+α5 G(Z) i 1 i 2 i 3 i 4 i 5 G(A) α 1 α 2 α 3 α 4 α 5 G(B)
components of G(Z ⊗2 ), H is a subgraph of G(A) and H ′ is a subgraph of G(B). Further as (G c (Z)) 2 = G c (Z ⊗2 ), H and H ′ are components of G c (Z ⊗2 ). As G c (Z ⊗2 )

IV. CONCLUSION

We proved that the six bounds on the transient of nonweighted directed graphs continue to hold for critical nodes in the weighted case. To the authors' knowledge, these are the first genuine extensions of unweighted graph transients to the weighted case. This is the main idea of the present contribution. Because they also hold in the nonweighted case, they are independent of the specific weights. More specifically, they only depend on the underlying digraph and the critical digraph. Contrasting this with the fact that the global transient of weighted digraphs can be unbounded even with fixed digraph and critical digraph, our results show that the difference between transients of critical and noncritical nodes can be arbitrarily large. This insight can give guidelines during system design.

Precision of these bounds is one of the possible directions for further research. Namely, it would be interesting to describe, in the most preise and concise way, which weighted digraphs (or associated max-algebraic matrices) attain these bounds. Some preliminary results in this direction are given in [START_REF] Merlet | Generalizations of bounds on the index of convergence to weighted digraphs[END_REF], Section 8. For instance, Figure 3 displays an example from the work of Schwarz [START_REF] Schwarz | On a sharp estimation in the theory of binary relations on a finite set[END_REF] and its weighted Comparison between the bounds is discussed in Remark 2.5. This cmparison is very similar to the well-known unweighted (Boolean) case, and rather straightforward. For future research, it would be desirable to run numerical experiments to get some statistics of how the transients of critical rows and columns typically behave.

Conversely, one can

  associate a digraph to every square Boolean matrix. The connectivity in G is closely related to the Boolean matrix powers of A. By the Boolean algebra we mean the set B = {0, 1} equipped with the logical operations of conjunction a ∧ b = a ⊗ b == a • b and disjunction a ∨ b = a ⊕ b = max(a, b), for a, b ∈ B. The Boolean multiplication of two matrices A ∈ B m×n and B ∈ B n×q is defined by (A ⊗ B) i,j = n k=1 (a i,k ∧ b k,j ), and then we also have Boolean matrix powers A ⊗t = A ⊗ . . . ⊗ A t times . The (i, j)th entry of A ⊗t is denoted by a (t) i,j . The relation between Boolean powers of A and connectivity in G is based on the following fact: a (t)

Theorem 2 . 1 ([ 4 ,

 214 Theorem 3.4.5]): Let G be a strongly connected graph with cyclicity d. For each k ≥ 1, graph G k consists of gcd(k, d) isolated strongly connected components, and every component has cyclicity d/gcd(k, d).

+

  be irreducible and let k ∈ N c (A) be a critical node. Denote by d the cyclicity of G(A), by H the strongly connected component of the critical graph G c (A) containing k, and by |H| the number of nodes in H. The following quantities are upper bounds on the transient of the kth row and the kth column:

4 .

 4 Main Theorem 2: Let A ∈ R n×n + be irreducible. Denote by d the cyclicity of G(A) and by r the factor rank of A. Let k ∈ N c (A) be critical. Denote by H the component of the critical graph G c (A) containing k. The following upper bounds on the transient of the kth row and kth column hold:

Fig. 2 .

 2 Fig. 2. Correspondence between closed walks of G(Z), G(A) and G(B)

Fig. 3 .

 3 Fig. 3. Schwarz's example (left) and its max-algebraic version (right)

  consists of only such components and the cycles not belonging to such components have a strictly smaller geometric mean, it follows that H is a component of G c (A), H ′ is a component of G c (B) and, moreover, G c (A) and G c (B) do not have components that are not formed this way. Take a closed walk C in H. Each edge of C results from a path of G

c (Z) of length 2, and inserting these path in C we obtain a closed walk of G c (Z) (see Figure

2

, left). This walk contains nodes from both H and H ′ . In Z ⊗2 it splits in two closed walks of G c (Z ⊗2 ) of the same length (see Figure

2

, right). One of these closed walks is C and the other is a closed walk C of H ′ (since H and H ′ are isolated in G c (Z ⊗2

Wielandt's proof was published later in[START_REF] Wielandt | s proof of the exponent inequality for primitive nonnegative matrices[END_REF].

Denardo [9] later rediscovered their result.

In the literature, T (G) is often called the index of convergence, or its exponent if G is primitive.

*The full version of this work will appear in Discrete Applied Mathematics. This work was partially supported by EPSRC grant RRAH15735, RFBR grant 12-01-00886, and RFBR-CNRS grant 11-0193106. It was initiated when the second author was with the Laboratoire