=Paper=
{{Paper
|id=Vol-2022/paper52
|storemode=property
|title=
Using Metagraph Approach for Complex Domains Description
|pdfUrl=https://ceur-ws.org/Vol-2022/paper52.pdf
|volume=Vol-2022
|authors=Valeriy M. Chernenkiy,Yuriy E. Gapanyuk,Georgiy I. Revunko
|dblpUrl=https://dblp.org/rec/conf/rcdl/ChernenkiyGR17
}}
==
Using Metagraph Approach for Complex Domains Description
==
https://ceur-ws.org/Vol-2022/paper52.pdf
Using metagraph approach for complex domains description
© Valeriy M. Chernenkiy, © Yuriy E. Gapanyuk, © Georgiy I. Revunkov,
© Yuriy T. Kaganov, © Yuriy S. Fedorenko, © Svetlana V. Minakova
Bauman Moscow State Technical University,
Moscow, Russia
chernen@bmstu.ru, gapyu@bmstu.ru, revunkov@bmstu.ru,
kaganov.y.t@bmstu.ru, fedyura11235@mail.ru, morgana_93@mail.ru
Abstract. This paper proposes an approach for complex domains description using complex network
models with emergence. The advantages of metagraph approach are discussed. The formal definitions of the
metagraph data model and metagraph agent model is given. The examples of data metagraph and metagraph
rule agent are discussed. The metagraph and hypergraph models comparison is given. It is shown that the
hypergraph model does not fully implement the emergence principle. The metagraph and hypernetwork
models comparison is given. It is shown that the metagraph model is more flexible than hypernetwork model.
Two examples of complex domains description using metagraph approach are discussed: neural network
representation and modeling the polypeptide chain synthesis. The textual representation of metagraph model
using predicate approach is given.
Keywords: metagraph, metavertex, metaedge, hypergraph, hypernetwork, neural network, polypeptide
chain, lambda architecture.
1 Introduction authors [2]. According to [2]: 𝑀𝐺 = 〈𝑉, 𝑀𝑉, 𝐸, 𝑀𝐸 〉,
where 𝑀𝐺 – metagraph; V – set of metagraph vertices;
Currently, models based on complex networks are MV – set of metagraph metavertices; E – set of metagraph
increasingly used in various fields of science from edges, ME – set of metagraph metaedges.
mathematics and computer science to biology and A metagraph vertex is described by the set of
sociology. This is not surprising because the domains are attributes: 𝑣𝑖 = {𝑎𝑡𝑟𝑘 }, 𝑣𝑖 ∈ 𝑉, where 𝑣𝑖 – metagraph
becoming more and more complex. vertex; 𝑎𝑡𝑟𝑘 – attribute.
Therefore, now it is important to offer not only a A metagraph edge is described by the set of attributes,
model that is capable of storing and processing Big Data the source and destination vertices and edge direction
but also a model that is capable of handling the flag: 𝑒𝑖 = 〈𝑣𝑆 , 𝑣𝐸 , 𝑒𝑜, {𝑎𝑡𝑟𝑘 }〉, 𝑒𝑖 ∈ 𝐸, 𝑒𝑜 = 𝑡𝑟𝑢𝑒|𝑓𝑎𝑙𝑠𝑒,
complexity of data. That is why the development of a where 𝑒𝑖 – metagraph edge; 𝑣𝑆 – source vertex
universal model for complex domains description is an (metavertex) of the edge; 𝑣𝐸 – destination vertex
actual task. (metavertex) of the edge; eo – edge direction flag
One of the varieties of such models is “complex (eo=true – directed edge, eo=false – undirected edge);
networks with emergence”. The emergent element means atrk – attribute.
a whole that cannot be separated into its component parts.
The metagraph fragment: 𝑀𝐺𝑖 = {𝑒𝑣𝑗 }, 𝑒𝑣𝑗 ∈ (𝑉 ∪
As far as the authors know, currently there are two
“complex networks with emergence” models: 𝑀𝑉 ∪ 𝐸 ∪ 𝑀𝐸), where 𝑀𝐺𝑖 – metagraph fragment; 𝑒𝑣𝑗
hypernetworks and metagraphs. The hypernetwork – an element that belongs to union of vertices,
model is mature and it helps to understand many aspects metavertices, edges and metaedges.
of complex networks with an emergence. The metagraph metavertex: 𝑚𝑣𝑖 =
But from the author's point of view, the metagraph 〈{𝑎𝑡𝑟𝑘 }, 𝑀𝐺𝑗 〉, 𝑚𝑣𝑖 ∈ 𝑀𝑉, where 𝑚𝑣𝑖 – metagraph
model is more flexible and convenient for use in metavertex belongs to set of metagraph metavertices MV;
information systems. 𝑎𝑡𝑟𝑘 – attribute, 𝑀𝐺𝑗 – metagraph fragment.
This paper discusses the metagraph model and Thus, a metavertex in addition to the attributes
compares it with other complex graph models. includes a fragment of the metagraph. The presence of
private attributes and connections for a metavertex is
2 Complex networks models comparison distinguishing feature of a metagraph. It makes the
In this section, the metagraph model will be formally definition of metagraph to be holonic – a metavertex may
described and it will be compared with hypergraph and include a number of lower-level elements and in turn,
hypernetwork models. may be included in a number of higher level elements.
From the general system theory point of view, a
2.1 Metagraph model formalization metavertex is a special case of the manifestation of the
emergence principle, which means that the metavertex
A metagraph is a kind of complex network model,
with its private attributes and connections becomes a
proposed by A. Basu and R. Blanning [1] and then
whole that cannot be separated into its component parts.
adapted for information systems description by the
The example of metagraph is shown in figure 1.
342
e7 and metavertices are added. Thus, metaedge allows
binding the stages of nested metagraph fragment
e8 development to the steps of the process described with
mv1 mv2 metaedge.
e1 e4
vv22 2.2 Metagraph and hypergraph models comparison
vv44
vv11 e2
e6 In this section, the hypergraph model will be
e3 vv33 e5 vv55 examined and compared with metagraph model.
According to [3]: 𝐻𝐺 = 〈𝑉, 𝐻𝐸 〉, 𝑣𝑖 ∈ 𝑉, ℎ𝑒𝑗 ∈ 𝐻𝐸,
where 𝐻𝐺 – hypergraph; 𝑉 – set of hypergraph vertices;
mv3 𝐻𝐸 – set of non-empty subsets of 𝑉 called hyperedges;
𝑣𝑖 – hypergraph vertex; ℎ𝑒𝑗 – hypergraph hyperedge.
Figure 1 Example of metagraph A hypergraph may be directed or undirected. A
hyperedge in an undirected hypergraph only includes
This example contains three metavertices: mv1, mv2, vertices whereas, in a directed hypergraph, a hyperedge
and mv3. Metavertex mv1 contains vertices v1, v2, v3 and defines the order of traversal of vertices. The example of
connecting them edges e1, e2, e3. Metavertex mv2 an undirected hypergraph is shown in figure 3.
contains vertices v4, v5 and connecting them edge e6. This example contains three hyperedges: he1, he2, and
Edges e4, e5 are examples of edges connecting vertices he3. Hyperedge he1 contains vertices v1, v2, v4, v5.
v2-v4 and v3-v5 respectively and they are contained in Hyperedge he2 contains vertices v2 and v3. Hyperedge he3
different metavertices mv1 and mv2. Edge e7 is an contains vertices v4 and v5. Hyperedges he1 and he2 have
example of an edge connecting metavertices mv1 and a common vertex v2. All vertices of hyperedge he3 are
mv2. Edge e8 is an example of an edge connecting vertex also vertices of hyperedge he1.
v2 and metavertex mv2. Metavertex mv3 contains Comparing metagraph and hypergraph models it
metavertex mv2, vertices v2, v3 and edge e2 from should be noted that the metagraph model is more
metavertex mv1 and also edges e4, e5, e8 showing the expressive then the hypergraph model. According to
holonic nature of the metagraph structure. Figure 1 figures 1 and 3 it is possible to note some similarities
shows that metagraph model allows describing complex between the metagraph metavertex and the hypergraph
data structures and it is the metavertex that allows hyperedge, but the metagraph offers more details and
implementing emergence principle in data structures. clarity because the metavertex explicitly defines
The vertices, edges, and metavertices are used for metavertices, vertices and edges inclusion, whereas the
data description and the metaedges are used for process hyperedge does not. The inclusion of hyperedge he3 in
description. hyperedge he1 in fig. 3 is only graphical and informal,
The metagraph metaedge: 𝑚𝑒𝑖 = because according to hypergraph definition a hyperedge
〈𝑣𝑆 , 𝑣𝐸 , 𝑒𝑜, {𝑎𝑡𝑟𝑘 }, 𝑀𝐺𝑗 〉, 𝑚𝑒𝑖 ∈ 𝑀𝐸, 𝑒𝑜 = 𝑡𝑟𝑢𝑒|𝑓𝑎𝑙𝑠𝑒, inclusion operation is not explicitly defined.
where 𝑚𝑒𝑖 – metagraph metaedge belongs to set of
metagraph metaedges ME; 𝑣𝑆 – source vertex
(metavertex) of the metaedge; 𝑣𝐸 – destination vertex vv11 vv22 vv44 vv55 he3 he1
(metavertex) of the metaedge; eo – metaedge direction
flag (eo=true – directed metaedge, eo=false – undirected
metaedge); 𝑎𝑡𝑟𝑘 – attribute, 𝑀𝐺𝑗 – metagraph fragment. vv33
The example of directed metaedge is shown in figure 2.
... ... VE
VS Vi e7 he2
e8
mv1 mv1 mv2 mv1 mv2
e1 e1 e4 e1 e4
v22 v22 v22
vv11 e2 vv11 e2
vv44
e6 vv11 e2
vv44
e6
Figure 3 Example of undirected hypergraph
e3 vv33 e3 vv33 e5 vv55 e3 vv33 e5 vv55
Thus the metagraph is a holonic graph model whereas
mv3
the hypergraph is a near flat graph model that does not
fully implement the emergence principle. Therefore,
Figure 2 Example of directed metaedge hypergraph model doesn’t fit well for complex data
structures description.
The directed metaedge contains metavertices vS, …
vi, … vE and connecting them edges. The source vertex 2.3 Metagraph and hypernetwork models
contains a nested metagraph fragment. During the comparison
transition to the destination vertex, the nested metagraph The amazing fact is that the hypernetwork model was
fragment becomes more complex, as new vertices, edges, invented twice. The first time the hypernetwork model
was invented by Professor Vladimir Popkov with
Proceedings of the XIX International Conference colleagues in 1980s. Professor V. Popkov proposes
“Data Analytics and Management in Data Intensive several kinds of hypernetwork models with complex
Domains” (DAMDID/RCDL’2017), Moscow, Russia,
October 10–13, 2017
343
formalization and therefore only main ideas of hypergraph model the hypernetwork model is a full
hypernetworks will be discussed in this section. model with emergence. Consider the differences between
According to [4] given the hypergraphs 𝑃𝑆 ≡ the hypernetwork and metagraph models.
𝑊𝑆0 , 𝑊𝑆1 , 𝑊𝑆2 , ⋯ 𝑊𝑆𝐾 . The hypergraph 𝑃𝑆 ≡ 𝑊𝑆0 is According to the definition of a hypernetwork it is a
called primary network. The hypergraph 𝑊𝑆𝑖 is called a a layered description of graphs. It is assumed that the
secondary network of order i. Also given the sequence of hypergraphs may be divided into homogeneous layers
mappings between networks of different orders: 𝑊𝑆𝐾 and then mapped with mappings or combined with
Ф𝐾 Ф𝐾−1 Ф1 hypersimplices. Metagraph approach is more flexible. It
→ 𝑊𝑆𝐾−1 → ⋯ 𝑊𝑆1 → 𝑃𝑆. Then the hierarchical
allows combining arbitrary elements that may be layered
abstract hypernetwork of order K may be defined as
or not using metavertices.
𝐴𝑆 𝐾 = 〈𝑃𝑆, 𝑊𝑆1 , ⋯ 𝑊𝑆𝐾 ; Ф1 , ⋯ Ф𝐾 〉. The emergence in
Comparing the hypernetwork and metagraph models
this model occurs because of the mappings Ф𝑖 between
we can make the following notes:
the layers of hypergraphs.
• Hypernetwork model may be considered as
The second time the hypernetwork model was
“horizontal” or layer-oriented. The emergence
proposed by Professor Jeffrey Johnson in his monograph
appears between adjoining levels using
[5] in 2013. The main idea of Professor J. Johnson variant
hypersimplices. The metagraph model may be
of hypernetwork model is the idea of hypersimplex (the
considered as “vertical” or aspect-oriented. The
term is adopted from polyhedral combinatorics).
emergence appears between any levels using
According to [5], a hypersimplex is an ordered set of
metavertices.
vertices with an explicit n-ary relation and hypernetwork
is a set of hypersimplices. In the hierarchical system, the • In hypernetwork model, the elements are organized
using hypergraphs inside layers and using mappings
hypersimplex combines k elements at the N level (base)
with one element at the N+1 level (apex). Thus, or hypersimplices between layers. In metagraph
hypersimplex establishes an emergence between two model, metavertices are used for organizing elements
adjoining levels. both inside layers and between layers. Hypersimplex
The example of hypernetwork that combines the may be considered as a special case of metavertex.
ideas of two approaches is shown in figure 4. • Metagraph model allows organizing the results of
previous organizations. The fragments of the flat
graph may be organized into metavertices,
vv55 vv66 he3 WS1 metavertices may be organized in higher-level
metavertices and so on. The metavertex organization
is more flexible than hypersimplex organization
hyper- Ф1
because hypersimplex assumes base and apex usage
simplex PS and metavertex may include general form graph.
• Metavertex may represent a separate aspect of the
he1 vv44 vv33 vv11 vv22 he2 organization. The same fragments of the flat graph
may be included in different metavertices whether
these metavertices are used for modeling different
Figure 4 Example of hypernetwork aspects.
Thus, we can draw a conclusion that metagraph
The primary network 𝑃𝑆 is formed by the vertices of model is more flexible than hypernetwork model.
hyperedges ℎ𝑒1 and ℎ𝑒2. The first level 𝑊𝑆1 of However, it must be emphasized that the
secondary network is formed by the vertices of hypernetwork and metagraph models are only different
hyperedge ℎ𝑒3. Mapping Ф1 is shown with an arrow. The formal descriptions of the same processes that occur in
hypersimplex is emphasized with the dash-dotted line. the networking with the emergence.
The hypersimplex is formed by the base (vertices 𝑣3 and From the historical point of view, the hypernetwork
𝑣4 of 𝑃𝑆) and apex (vertex 𝑣5 of 𝑊𝑆1). model was the first complex network with an emergence
The hypernetwork model became popular for model and it helps to understand many aspects of
complex domains description. For example, Professor complex networks with an emergence.
Konstantin Anokhin [6] proposes a new fundamental
theory of the organization of higher brain functions. 3 Metagraph model processing
According to this theory, biological neural networks The metagraph model is designed for complex data
(connectomes) are organized into cognitive and process description. But it is not intended for data
hypernetworks (cognitomes). Vertices of cognitome transformation. To solve this issue, the metagraph agent
form COGs (Gognitive Groups). Each COG may be (𝑎𝑔 𝑀𝐺 ) designed for data transformation is proposed.
represented as hypersimplex. The base of COG is a set of There are two kinds of metagraph agents: the metagraph
the vertices of underlying neural networks, and its apex function agent (𝑎𝑔 𝐹 ) and the metagraph rule agent (𝑎𝑔 𝑅 ).
is a vertex possessing a new quality at the macrolevel of Thus 𝑎𝑔 𝑀𝐺 = 𝑎𝑔 𝐹 |𝑎𝑔 𝑅 .
cognitive hypernetworks. Thus, apex combines the base The metagraph function agent serves as a function
elements and emergence appears. with input and output parameter in form of metagraph:
It should be noted that unlike the relatively simple 𝑎𝑔 𝐹 = 〈𝑀𝐺𝐼𝑁 , 𝑀𝐺𝑂𝑈𝑇 , 𝐴𝑆𝑇〉, (1)
344
where 𝑎𝑔 𝐹 – metagraph function agent; 𝑀𝐺𝐼𝑁 – input 1 in given example). Figure 5 shows both cases
parameter metagraph; 𝑀𝐺𝑂𝑈𝑇 – output parameter corresponding to the start metagraph fragment and to the
metagraph; 𝐴𝑆𝑇 – abstract syntax tree of metagraph start rule.
function agent in form of metagraph.
mv1 mv2 mv3
The metagraph rule agent is rule-based: ag R =
〈MG, R, AG ST 〉, R = {ri }, ri : MGj → OP MG , where 𝑎𝑔 𝑅 – v31
e31
v32 v31
e31
v32 v31
e31
v32
MG1
metagraph rule agent; 𝑀𝐺 – working metagraph, a e32 e33 e32
v33 v34 v33
metagraph on the basis of which the rules of agent are
performed; 𝑅 – set of rules 𝑟𝑖 ; 𝐴𝐺 𝑆𝑇 – start condition MG=MG1
e3
(metagraph fragment for start rule check or start rule); e1
e2
e4
𝑀𝐺𝑗 – a metagraph fragment on the basis of which the start=true
rule is performed; 𝑂𝑃𝑀𝐺 – set of actions performed on antecedent consequent
actions
metagraph.
rule 1
The antecedent of the rule is a condition over start=true
metagraph fragment, the consequent of the rule is a set of conditions
...
actions performed on metagraph. Rules can be divided
rule N
into open and closed.
The consequent of the open rule is not permitted to metagraph rule agent 1
change metagraph fragment occurring in rule antecedent.
In this case, the input and output metagraph fragments Figure 5 Example of metagraph rule agent
may be separated. The open rule is similar to the template
that generates the output metagraph based on the input The distinguishing feature of metagraph agent is its
metagraph. homoiconicity which means that it can be a data structure
The consequent of the closed rule is permitted to for itself. This is due to the fact that according to
change metagraph fragment occurring in rule antecedent. definition metagraph agent may be represented as a set
The metagraph fragment changing in rule consequent of metagraph fragments and this set can be combined in
cause to trigger the antecedents of other rules bound to a single metagraph. Thus, the metagraph agent can
the same metagraph fragment. But incorrectly designed change the structure of other metagraph agents.
closed rules system can lead to an infinite loop of
metagraph rule agent. 4 The examples of complex domains
If the agent contains only open rules it is called an description using metagraph approach
open agent. If the agent contains only closed rules it is In this section, we give two examples of complex
called a closed agent. domains description using metagraph approach.
Thus, metagraph rule agent can generate the output
metagraph based on the input metagraph (using open 4.1 Using metagraph approach for neural network
rules) or can modify the single metagraph (using closed representation
rules). The example of metagraph rule agent is shown in
figure 5. This subsection is based on our paper [7]. We begin
The metagraph rule agent “metagraph rule agent 1” is with simple perceptron representation using metagraph
represented as a metagraph metavertex. According to the model. According to the Rosenblatt perceptron model
definition it is bound to the working metagraph MG1 – a [8], a conventional perceptron consists of three elements:
metagraph on the basis of which the rules of the agent are S, A and R.
performed. This binding is shown with edge e4. The layer of sensors (S) is an array of input signals.
The metagraph rule agent description contains inner The associative layer (A) is a collection of intermediate
metavertices corresponds to agent rules (rule 1 … rule elements which are triggered if a particular set of input
N). Each rule metavertex contains antecedent and signals is activated at the same time. The adder (R) is
consequent inner vertices. In given example mv2 started when a particular collection of A-elements is
metavertex bound with antecedent which is shown with activated concurrently.
edge e2 and mv3 metavertex bound with consequent According to the notation adopted in the M. Minsky
which is shown with edge e3. Antecedent conditions and and S. Papert perceptron model [8], the value of a signal
consequent actions are defined in form of attributes on an A-element can be represented as a boolean
bound to antecedent and consequent corresponding predicate φ(S), and the value of a signal in the adder layer
vertices. as a predicate ψ(A, W). According to [8], a function that
The start condition is given in form of attribute takes either 0 or 1 is regarded as a boolean predicate.
“start=true”. If the start condition is defined as a start Depending on the particular type of perceptron, the
metagraph fragment then the edge bound start metagraph form of predicates φ(S) and ψ(A, W) can be different.
fragment to agent metavertex (edge e1 in given example) Usually, predicate φ(S) is used to check whether the total
is annotated with attribute “start=true”. If the start input signal from sensors exceeds a certain threshold or
condition is defined as a start rule than the rule not. Also predicate ψ(A, W) (where W is a weight vector)
metavertex is annotated with attribute “start=true” (rule is used to see if the weighted sum from A-elements
exceeds a particular threshold.
345
In our case, the actual form of predicates is not • 𝑎𝑔 𝑀𝑅 – the agent responsible for the execution of the
important. What is important is that the structure of φ(S) network.
and ψ(A, W) can be represented as an abstract syntactic In figure 7 the agents are shown as metavertices by
tree. Then we can represent the perceptron structure as a dotted-line ovals.
combination of metagraph function agents. Each The network-creating agent 𝑎𝑔 𝑀𝐶 implements the
predicate can be represented as a kind of the formula 1: rules of creating an original neural network topology.
𝜑𝐹 = 〈S, A, 𝐴𝑆𝑇 𝜑 〉, 𝜓 𝐹 = 〈〈{𝜑𝐹 }, 𝑊 〉, R, 𝐴𝑆𝑇 𝜓 〉. This The agent holds both the rules of creating separate
representation is shown in figure 6. neurons and rules of connecting neurons into a network.
Ψ
Ψ In particular, the agent generates abstract syntactic trees
Φ
Φ of metagraph function agents 𝜑𝐹 and 𝜓 𝐹 .
SS ASTΦ
AST Φ
A
A ASTΨ
AST Ψ
RR The network-modification agent 𝑎𝑔 𝑀𝑂 holds the
W rules of modification the network topology in process of
{-1;0;1}
operation. It is especially important for neural networks
with variable topology such as HyperNEAT and SOINN.
The network-learning agent 𝑎𝑔 𝑀𝐿 implements a
Figure 6 The perceptron representation as a particular learning algorithm. As a result of learning the
combination of metagraph function agents changed weights are written in the metagraph
An A-element can be represented as a function agent representation of the neural network. It is possible to
𝜑𝐹 . The input parameter is the value vector S, the output implement a few learning algorithms by using different
parameter is the value vector A. The description of the sets of rules for agent 𝑎𝑔 𝑀𝐿 .
perceptron is similar to the description of the function The network-executing agent 𝑎𝑔 𝑀𝑅 is responsible for
agent 𝜓 𝐹 . The input parameter is a the metagraph the start and operation of the trained neural network.
representation of a tuple holding the description of A- The agents can work separately or jointly which may
elements as agent-functions 𝜑𝐹 and vector W. The output be especially important in the case of variable topologies.
parameter is the amplitude of output signal R. For example when a HyperNEAT or SOINN network is
The description of functions can contain other trained, agent 𝑎𝑔 𝑀𝐿 can call the rules of agent 𝑎𝑔 𝑀𝑂 to
parameters, e.g., threshold values, but we assume that change the network topology in the process of learning.
these parameters are included in the description of the In fact, each agent uses its rules to implement a
abstract syntactic tree. specific program “machine”. The use of the metagraph
Thus, we can describe the perceptron structure as a approach allows us to implement the “multi-machine”
combination of metagraph function agents. Now we principle: a few agents having different goals implement
describe neural network operation using metagraph rule different operations on the same data structure.
agents which are shown in figure 7. Thus, we can draw a conclusion that metagraph
approach helps to describe both the structure of separate
neurons and the structure of neural network operation.
agMO agML
4.2 Using metagraph approach for modeling the
polypeptide chain synthesis
MC
agMC
ag agMR
Molecular biology is considered to be one of the most
difficult to study topics of biological science. It's hard to
The metagraph believe that the complexity of functioning of the
representation biological cell invisible to the human eye exceeds the
complexity of functioning of a large ERP-system, which
of a neural network
can contain thousands of business processes. The
difficulty of studying biological processes is also due to
Figure 7 The structure of metagraph rule agents for the fact that in studying it is impossible to abstract from
neural network operation representation the physical and chemical features that accompany these
The metagraph representation of neural network may processes. Therefore, the development of learning
be created similarly to the previously reviewed software that helps to better understand even one
perceptron approach. Such a representation is a separate complex process is a valid task.
task that depends on neural network topology. We will review the process of synthesis of a
In order to provide a neural network operation the polypeptide chain which is also called “translation” in
following agents are used: molecular biology. Translation is an essential part of the
• 𝑎𝑔 𝑀𝐶 – the agent responsible for the creation of the protein biosynthesis. This process is very valid from an
network; educational point of view because protein biosynthesis is
considered in almost all textbooks of molecular biology.
• 𝑎𝑔 𝑀𝑂 – the agent responsible for the modification of
The translation process is very complicated and in
the network;
this section, we review it in a simplified way.
• 𝑎𝑔 𝑀𝐿 – the agent responsible for the learning of the
The first main actor of the translation process is
network;
messenger RNA or mRNA, which may be represented as
346
a chain of codons. The second main actor of the input and output metagraph fragments don’t contain
translation process is ribosome consisting of the large common elements.
subunit and the small subunit. The small subunit is While processing codons of mRNA agent ag RB
responsible for reading information from mRNA and sequentially adds fragments of the polypeptide chain PK
large subunit is responsible for generating fragments of to the output metagraph MGP . Vertices PK are connected
the polypeptide chain. with undirected edges.
According to [9] the translation process consists of The process represented in figure 8 is very high-level.
three stages. But metagraph approach allows representing related
The first stage is initiation. At this stage, the ribosome processes with different levels of abstraction.
assembles around the target mRNA. The small subunit is For example, for each codon or peptide, we can link
attached at the start codon. metavertex with its inner representation. And we can
The second stage is elongation. The small subunit modify this representation during translation process
reads information from the current codon. Using this using metagraph agents.
information, the large subunit generates the fragment of Thus, the metagraph approach allows us to represent
the polypeptide chain. After that ribosome moves a model of polypeptide chain synthesis which can be the
(translocates) to the next mRNA codon. basis for the learning software.
The third stage is termination. When the stop codon
is reached, the ribosome releases the synthesized 5 The textual representation of metagraph
polypeptide chain. Under some conditions, the ribosome model
may be disassembled.
In previous sections, the formal definition and
In this section, we use metagraph approach for
graphical examples of metagraph model were defined.
translation process modeling. The representation is
But to successfully operate with metagraph model we
shown in figure 8.
also need textual representation. As such a
e1 e eK+1 eN representation, we use a logical predicate model that is
meRNA СSTART ... K-1 CK ... CSTOP MGP
close to logical programming languages e.g. Prolog.
PSTART Logical predicates used in this section and boolean
MGP MGP ... predicates used in subsection 4.1 should not be confused.
PSTART PSTART PK
The classical Prolog uses following form of
... predicate: 𝑝𝑟𝑒𝑑𝑖𝑐𝑎𝑡𝑒(𝑎𝑡𝑜𝑚1 , 𝑎𝑡𝑜𝑚2 , ⋯ , 𝑎𝑡𝑜𝑚𝑁 ). We
agM agM agM ... used an extended form of predicate where along with
PK PSTOP atoms predicate can also include key-value pairs and
nested predicates: 𝑝𝑟𝑒𝑑𝑖𝑐𝑎𝑡𝑒(𝑎𝑡𝑜𝑚, ⋯ , 𝑘𝑒𝑦 = 𝑣𝑎𝑙𝑢𝑒,
Figure 8 The representation of the polypeptide chain ⋯ , 𝑝𝑟𝑒𝑑𝑖𝑐𝑎𝑡𝑒(⋯ ), ⋯ ). The mapping of metagraph
synthesis (translation) process based on metagraph model fragments into predicate representation is shown
approach in Table 1.
The mRNA is shown in figure 8 as metaedge Table 1 The textual representation of metagraph model
𝑚𝑒𝑅𝑁𝐴 = 〈𝐶𝑆𝑇𝐴𝑅𝑇 , 𝐶𝑆𝑇𝑂𝑃 , 𝑒𝑜 = 𝑡𝑟𝑢𝑒, {𝑎𝑡𝑟𝑘 }, 𝑀𝐺𝑅𝑁𝐴 〉,
№ Metagraph representation Textual representation
where 𝐶𝑆𝑇𝐴𝑅𝑇 – source metavertex (start codon); 𝐶𝑆𝑇𝑂𝑃 –
mv1
destination metavertex (stop codon); eo=true – directed Metavertex(Name=mv1, v1,
1
metaedge; 𝑎𝑡𝑟𝑘 – attribute, 𝑀𝐺𝑅𝑁𝐴 – metagraph vv11 vv22 vv33 v2, v3)
fragment, containing inner codons of mRNA (𝐶𝐾 ) linked
with edges. e1
e1
The codon (shown in figure 8 as an elementary 2 vv11 vv22 ↔ vv11 vv22 Edge(Name=e1, v1, v2)
vertex) may also be represented as metavertex,
containing inner vertices and edges according to the e1 (eo=false)
required level of detail. e1 Edge(Name=e1, v1, v2,
3 vv11 vv22 ↔ vv11 vv22
Ribosome may be represented as metagraph rule eo=false)
agent agRB = 〈meRNA , R, 𝐶𝑆𝑇𝐴𝑅𝑇 〉, R = {ri }, ri : CK → PK , 1. Edge(Name=e1, v1, v2,
e1 (eo=true)
where 𝑚𝑒𝑅𝑁𝐴 – mRNA metaedge representation used as e1 eo=true)
4
working metagraph; 𝑅 – set of rules 𝑟𝑖 ; 𝐶𝑆𝑇𝐴𝑅𝑇 – start vv11 vv22 ↔ vv11 vv22 2. Edge(Name=e1, vS=v1,
codon used as start agent condition; 𝐶𝐾 – codon on the vE=v2, eo=true)
mv2
basis of which the rule is performed; 𝑃𝐾 – the added Metavertex(Name=mv2, v1,
e1
fragment of polypeptide chain. vv22 v2, v3,
The antecedent of the rule approximately corresponds 5 vv11 e2 Edge (Name=e1, v1, v2),
to the small subunit of ribosome modeling. The Edge(Name=e2, v2, v3),
e3 vv33
Edge(Name=e3, v1, v3))
consequent of the rule approximately corresponds to the
large subunit of ribosome modeling.
Agent ag RB is open agent generating output
metagraph MGP based on input metaedge 𝑚𝑒𝑅𝑁𝐴 . The
347
mv2 Metavertex(Name=mv2, v1, Case 3 also shows metagraph edge which fully
e1 v2, v3, Edge(Name=e1, complies with the formal definition of undirected edge
vv22 vS=v1, vE=v2, eo=true), including direction flag parameter.
6 vv11 e2 Edge(Name=e2, vS=v2,
vE=v3, eo=true), Case 4 shows an example of directed edge. Direction
e3 vv33 Edge(Name=e3, vS=v1, flag parameter is also used. The source and destination
vE=v3, eo=true)) vertices may be represented as predicate atom parameters
me1 Metaedge(Name=me1, (case 4.1) or as predicate key-value parameters (case
mv3 vS=v2, vE=mv3,
7 vv22 mv4
... ... 4.2).
Metavertex(Name=mv4, …
), eo=true) Case 5 shows an example of metavertex mv1 which
Metagraph(Name=mg0, contains three nested vertices v1, v2 and v3 joined with
mg0 Vertex(Name=v2, …), undirected edges e1, e2, and e3. Edges are represented
mv5 Metavertex(Name=mv3, … with separate predicates that are nested to the metavertex
... ),
8 Metavertex(Name=mv5, …
predicate. Case 6 is similar to case 5 unless edges e1, e2,
me1
mv4
mv3 ), Metaedge(Name=me1, and e3 are directed.
vv22
... ... vS=v2, vE=mv3, Case 7 shows an example of directed metaedge me1
Metavertex(Name=mv4, … which joins vertex v2 and metavertex mv3 and contains
), eo=true))
metavertex mv4. The metaedge is represented as a
attribute
9 =
Attribute(count, 5)
predicate with the name “Metaedge”.
count 5
Case 8 shows an example of metagraph fragment mg0
v1 which contains vertex v2, metavertices mv3 and mv5 and
attribute metaedge me1 which joins vertex v2 and metavertex mv3
count
=
55 and contains metavertex mv4. The metagraph fragment
Vertex(Name=v1,
10 Attribute(count, 5), is represented as a predicate with the name “Metagraph”,
attribute
= mv2
Attribute(reference, mv2)) the vertex as a predicate with the name “Vertex”.
reference
reference ... The attribute may be represented as a special case of
metavertex containing name and value. Case 9 shows
Agent(Name= metagraph simple numeric attribute representation. Case 10 shows
agent 1’, an example of vertex v1 containing numeric attribute and
WorkMetagraph=mg1, reference attribute that refers to the metavertex mv2. The
Rules(
Rule(Name=rule 1’, attribute is represented as a predicate with the name
mv1 mv2 start=true, “Attribute”.
vv11
(k=1)
(k=1)
e1(flag=main)
Sum
Sum
(k=3)
(k=3)
mg
mg11
Condition Case 11 shows an example of metagraph rule agent
vv22 (WorkMetagraph=mv1, “metagraph agent 1” representation (the predicate with
(k=2)
(k=2)
Vertex(Name=v1,
start=true
start=true
Attribute(k, $k1)), the name “Agent” is used). As a work metagraph mg1 is
11 used (parameter “WorkMetagraph”). The “Rules”
antecedent
antecedent consequent
consequent
Vertex(Name=v2,
rule
rule 11
Attribute(k, $k2)), predicate contains rules definition (nested predicate
... Edge(v1, v2, Attribute(flag, “Rule” is used). As a start rule “rule 1” is used which is
rule
rule N main)))
defined by “start=true” parameter. Predicate “Condition”
N
metagraph
metagraph agent
agent 11
Action
(WorkMetagraph=mv2, corresponds to the rule condition. Parameter
Add(Vertex(Name=Sum, “WorkMetagraph” contains a reference to the tested
Attribute(k, metavertex mv1. The condition tests that metavertex mv1
Eval($k1+$k2)))))
), Rule(…) … )) contains vertices v1 and v2 with attribute k. Founded
values of k attribute of vertices v1 and v2 are assigned to
Case 1 shows the example of metavertex mv1 which the $k1 and $k2 variables. Vertices v1 and v2 should be
contains three nested disjoint vertices v1, v2, and v3. The joined with edge containing attribute “flag=main”. If
predicate corresponds to metavertex, nested vertices are condition holds and metagraph fragment is found then
isomorphic to atoms that are parameters of the predicate. actions are performed (actions are defined by predicate
As the name of the predicate, “Metavertex” is used as the “Action”). Parameter “WorkMetagraph” contains a
corresponding element of metagraph model. Key-value reference to the result metavertex mv2. The example
parameter “Name” is used to set the name of metavertex. action contains adding new elements (that is defined by
This case is the simplest, since nested vertices are predicate “Add”). The vertex “Sum” is added containing
disjoint, and metavertex in this case is isomorphic to the attribute “k=$k1+$k2”. Predicate “Eval” is used to
hypergraph hyperedge. define the calculated expression.
Case 2 shows metagraph edge which may be Thus, we defined a predicate description of all the
represented as a special case of metavertex containing main elements of metagraph data model.
source and destination vertices. This case is also The proposed predicate model is homoiconic. Since
isomorphic to the hypergraph hyperedge. The metagraph predicate approach is used both for metagraph data
edge is represented as a predicate with the name “Edge”. model definition and for metagraph agents definition
The source and destination vertices are represented as then high-level metagraph agents may change the
predicate atom parameters. structure of low-level metagraph agents by modifying
their predicate definition.
348
The textual representation of metagraph model may Data approach, in particular with the lambda
be used for storing metagraph model elements in architecture.
relational or NoSQL databases.
It should be noted that metagraph model is well References
compatible with the Big Data approach. Nowadays the [1] Basu A., Blanning R. Metagraphs and their
lambda architecture described in [10] is considered to be applications. Springer, New York (2007)
a classic approach. [2] E. Samohvalov, G. Revunkov, Yu. Gapanyuk,
The textual representation of metagraph model is the “Metagraphs for describing semantics and
base for processing metagraph data on all layers of the pragmatics of information systems,” in Herald of
lambda architecture. On the batch layer, the textual Bauman Moscow State Technical University, vol.
representation is used for storing in master dataset. On 1(100), pp.83-99, (2015)
the serving layer, the textual representation helps to
construct the batch views. On the speed layer, the textual [3] Vitaly I. Voloshin. Introduction to Graph and
representation helps to construct the real-time views. Hypergraph Theory. Nova Science Publishers, Inc.,
Batch and real-time views may be constructed using (2009)
metagraph agents. [4] Akhmediyarova, A.T., Kuandykova, J.R.,
Kubekov, B.S., Utepbergenov, I.T., Popkov, V.K.:
6 Conclusion Objective of Modeling and Computation of City
Electric Transportation Networks Properties. In:
Nowadays complex network models have become
International Conference on Information Science
popular for complex domains description.
and Management Engineering (Icisme 2015), pp.
The metagraph model is a kind of complex network
106–111, Destech Publications, Phuket (2015)
model. The emergence in metagraph model is established
using metavertices and metaedges. [5] Johnson, J.: Hypernetworks in the Science of
The hypergraph model does not fully implement the Complex Systems. Imperial College Press, London
emergence principle. (2013)
The hypernetwork model fully implements the [6] Anokhin, K.V.: Cognitom: theory of realized
emergence principle using hypersimplices. The degrees of freedom in the brain. In: The Report
metagraph model is more flexible than hypernetwork Given at Fifth International Conference on
model. Cognitive Science, Kaliningrad (2012)
For metagraph model processing, the metagraph [7] Fedorenko, Yu.S., Gapanyuk, Yu.E. Multilevel
function agents and the metagraph rule agents are used. neural net adaptive models using the metagraph
Two examples of complex domains description using approach. Optical Memory and Neural Networks.
metagraph approach are discussed: neural network Volume 25, Issue 4, pp. 228–235 (2016)
representation and modeling the polypeptide chain [8] Minsky, M.L., Papert, S.A. Perceptrons. The MIT
synthesis. Metagraph approach helps to describe Press (1988)
complex domains in a unified way. [9] Samish, I. Computational Protein Design. Springer
The textual representation of metagraph model may Science+Business Media, New York (2017)
be used for storing metagraph model elements in
[10] Marz, N., Warren, J. Big Data. Principles and best
relational or NoSQL databases.
The metagraph model is well compatible with the Big practices of scalable realtime data systems.
Manning, New York (2015)
349