This paper explains how very large network structures can be reduced, or consolidated, to an assemblage of chordless cycles (cyclic structures without cross connecting links), that is called a trace, for storage and later retreival. After developing a basic mathematical framework, it illustrates the reduction process using a most general (with directed and undirected links) network. A major theme of the paper is that this approach appears to model actual biological memory, as well as o ering an attractive digital solution.
A central tenet of database theory is that it is the
relationships between various entities that constitute real
information. It is the foundation of the relational model [
We will contend that retrieval of information from a storage medium is not a single, uni ed operation; that there are at least two distinct phases. First the desired information must be identi ed and located within the storage medium. We call this \information access" and address it in Section 3. Then it must be read out or, in the case of biological memory, reconstituted. This latter step we call \recall" and discuss it in Section 4.
However, this paper is less concerned with actual retrieval than discovering graph structures which facilitate this process. In Section 2.3 we introduce the concept of \chordless 2017, Copyright is with the authors. Published in the Workshop Proceedings of the EDBT/ICDT 2017 Joint Conference (March 21, 2017, Venice, Italy) on CEUR-WS.org (ISSN 1613-0073). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0 cycles" which we believe play a prominent role in the representation of biological information, and which we believe can be exploited in computer applications as well. In Section 2.1 we sketch the mathematical foundations for this notion, which is based on concepts of \closure". In Section 2.2 we present computer code that will reduce any network to its constituent chordless cycles. Then in Section 2.3 we can describe the desirable properties of representing information by these cycles and indicate their role in biological memory.
Our goal in this paper is to use some relatively abstract graph-theoretic concepts to e ectively model, and bring together, both biological and computer applications. 2.
Our basic understanding of the world, whether visual, oral, or tactile, is neural in nature. The representation of data in regular arrays is, to a large extent, an artifact of computer architecture and the ease of algebraic manipulation. So we begin with the assumption that all \information" is a graph structure of some form.
To our knowledge, there has been no agreement as to what
neural con gurations correspond to any speci c empirical
sensations or mental concepts; but there have been many
studies documenting that all perception and cognition
correlate with neural activity, even detailing its occurrence with
speci c locations within the brain [
The most general mathematical model of neural activity appears to be a directed graph. So the fundamental assumption of this paper is that, at its most basic level, information retrieval involves locating and obtaining rich directed graph structures based on simpler representations which serve as query keys. We are not retrieving array-type information to display on a spread sheet.
For this paper we assume that the network structure is the \information", independent of any edge or node labels. 2.1
Information and knowledge are essentially relational.
Elements, or neurons, are related to other elements. To our
knowledge, neurons are not \labeled". In contrast, most
subgraph matching algorithms assume their nodes, or elements,
are labeled [
There seem to be many di erent kinds of relationships; however, we abstract them all by a single relational symbol, . By y: we mean the set of all elements related to y. For set valued operators, such as , we use a su x notation. It helps remind us that they are not scalar valued functions. If we represent information as a network N , y: would denote the neighbors of y in N . So one can read y: simply as y's neighbors. (For mathematical convenience we assume is re exive, so y 2 y: .) Visually, represents the edges of the graph, or relational network. (We use the terms node and element and graph and network interchangeably.) It is unknown whether information networks are directed or undirected. To assume a measure of generality we will assume they are mixed, with some links being directed and some undirected. While Figure 1 is far too small to be a real information network, we will use it to illustrate concepts of this paper. Arrow heads denote directed edges; if there are a b c d e f g h i j k l m n o p q r s t u v w x y z
A
D B
C
E F none the link is bi-directional, or symmetric.
An important principle for interpreting information
networks is the concept of \closure". Closure is well de ned in
mathematics [
As de ned by (1), an element z in y closure, y:', is relationally connected to no more elements than y itself. Consequently, those elements within a network which are contained in the closure of other elements contribute very little to the information content conveyed by the network. They can be combined with little loss of information. We say that y has subsumed z, or equivalently that z belongs to y. By y: we mean all nodes, z that belong to y, that is have been combined. Readily y 2 y: . The pseudo code for a process we call \reduction", and denote by !, is shown below in Figure 2. The outer loop terminates when every element y is } }
}
while there exist subsumable nodes
{
for_each y in N
{
get {y}.nbhd
for_each z in {y}.nbhd - {y}
{
if ({z}.nbhd contained_in {y}.nbhd
{ // z is subsumed by y
combine z with y
add z to {y}.beta
}
itself a closed set. A network with this property is said to
be irreducible. A C++ version of this code has been applied
to a variety of social networks [
Figure 3 illustrates the trace T of the network N of Figure 1. Emboldened solid links, or edges, connect the nodes that a b c d e f g h i j k l m n o p q r s t u v w x y z
A D B
C
E F remain in T after the reduction process; thiner dashed lines connect the nodes that have been combined with others.. Dashed lines enclose the 7 non-trivial -sets; for example c: = fa; b; cg and z: = fv; y; z; D; Cg.
Observe that a new link (f; c) was created to preserve path connectivity through b. We also see that ' and are distinct operators since although c:' = c: , g:' g: .
Of the original 32 nodes, only 17 remain after reduction which represents a considerable storage compaction.
The reduction process, !, has a number of desirable
computational properties. Because the closure operator, ', is
local (it need only interrogate adjacent elements), it can be
executed as a parallel process. (The code of Figure 2 that
we have actually used is sequential1 , but it is evident how
to convert the outer loop.) This is particularly important
for biological information storage and retrieval. The
parallel application of a similar closure based process within the
visual pathway is described in [
We have devoted considerable space to a description of ! because, in addition to preparing information for storage, we believe it plays a prominent role in retrieval as described in the next sections.
In the literature devoted to human \memory", there has
been considerable research suggesting that there is a process
that converts short-term memory into long-term memory. It
is usually called \consolidation" [
A chordless cycle is most easily visualized as a string of pearls with no cross connections. More precisely, a chordless cycle is a sequence < y1; y2; : : : ; yn; y1 > of elements yi; 1 i n of length n 4 where there exist no links (chords) of the form (yi; yk) k 6= i 1, i; k 6= 1; n.2 It is better to just think of them as paths with no single edge cross connections. In Figure 3, the sequence, or path, < c; g; m; i; d; c > is a chordless cycle of length 5 The sequence < n; q; p; u; z; A; B; x; t; n > is a chordless cycle of length 9.
If the relation between elements is symmetric, it can be
proven [
When is symmetric, ! readily preserves path
connectivity within T . It also preserves the distance between elements
as measured by shortest paths [
Symmetry of the relation is a powerful property. But, to better model real relationships we have relaxed this constraint throughout to allow directed (non-symmetric) connections. Under these conditions the preceding characterization of irreducible networks is no longer valid. For instance, the node f in Figure 3 is not an element of a chordless cycle.
In the case of non-symmetric networks we must ensure
path connectivity through subsumed nodes. Let y subsume
z, i:e: z: y: . For all x such that z 2 x: we ensure
that y 2 x: . This is always true when is symmetric, but
required the creation of the edge (f; c) in Figure 3. In this
case, we can show [
Are chordless cycles really fundamental in the representation of biological information?
We can provide no de nitive answer to that question. We
can point out that protein polymer molecules composed of
chordless cycles exist in every cell of our bodies [
If we count [
These are only indications that chordless cycle structures might be an important component of relational information 1 1 2 2 7 7 8 8 3 3 4 4 5
6 5 6 representation. The following sections will show how they can be involved with the retrieval process.
Information cannot be retrieved unless it is rst
identied and located within storage. Pointers and URLs identify
storage locations. But, lacking these, one must search based
on the \content" of the desired information. An early, and
still common, mechanism is to attach key words or hash
tags to the information, which are then used to create an
easily searchable index [
As access speeds have increased so dramatically, both of the preceding access techniques have often been superceded by simple linear search and comparison.
But, this still presumes that the \content identi cation" is based on speci c terms, or tokens. If important information is based on relationships, as we have asserted in Section 1, then such token based search is rather limited.
Suppose we wish to retrieve within a relational network. We may assume that the search key, K, is itself relational. It might look like Figure 6, but very much larger! Imagine \sliding" an unlabeled 600 irreducible subgraph around over an irreducible million node network to nd a match, if one exists.
A method that we are beginning to explore involves the network providing information about its own irreducible structure. To do this we label each edge with the length of the \shortest" chordless cycle of which it is a member. This is not an arti cial data label, but an element of the network representation itself. Thus, in the irreducible network of Figure 3, the edge (q; p) would be labeled with a 7 because it is a member of the chordless 7-cycle < q; p; k; g; c; d; i; m; q >. This same edge is a member of longer cycles such as the 9-cycle, < q; p; u; z; A; B; x; t; n; q >, but we only label with respect to the shortest.
The edge (m; q) would be labeled with a 4, as would the edge (m; p). Each edge in the reduced search key, K:!, of Figure 7 must be labeled with a 4.
Each edge label of the search key must be exactly equal to the corresponding edge label in the larger network. So, based solely on the edge labeling, the only possible matches for this reduced key of Figure 7 in the reduced network of Figure 3 are the 4-cycles < g; m; p; k; g >, < n; q; m; i; n > and < w; A; B; x; w >.
Edge labeling with respect to shortest chordless cycle length eliminates fruitless search expansion, but it can't indicate likely places to begin the comparison. The central retrieval problem is identifying likely nodes within the larger network to initiate the search comparison.
We believe that the solution lies with the imbedded \triangles". Even though they are not chordless cycles of length 4 of which an irreducible network is comprised, they do exist, provided each edge is a member of a distinct chordless cycle of length 4. In the reduced network of Figure 3 there is one embedded triangle, that is < q; p; m; q >, with associated cycle labels < 7; 4; 4 >. There is no embedded triangle in the reduced search key of Figure 7. This is unusual; but it is because the search key is \too small". Our observation is that most reduced networks of 20 nodes, or more, have at least one embedded triangle. The network of Figure 4 has ve, with associated cycle lengths of < 8; 6; 4 >, < 12; 5; 5 >, < 12; 7; 4 >, < 14; 10; 7 > and < 16; 8; 6 >. If the reduced search key contains any embedded triangle, it must match one of these.
In our JMC approach to information access, we 1) associate with each edge (functional relationship) in the length of the shortest chordless cycle to which it belongs; and 2) create an external index of shortest length triples corresponding to embedded triangles. Assuming the search key is su cently well speci ed to include an embedded triangle, we rst search this index of triples to identify one, or more, plausible search regions within the multi-million node reduced network constituting the data store.
This access mechanism is now being implemented, so its
actual e cency is still unknown. We believe it has
considerable promise. More uncertain is whether the edge labeling
and triangle index can be maintained in real time as the
network changes dynamically [
The approach described in this section seems quite appropriate to biological recall as well. We see \Mary" in the market. This is a visual experience involving many relationships. A rapid, almost instantaneous, search through our
Reduction of K by ! yields its trace K:!, as shown in Figure 7. It is a simple cycle on the nodes < 4; 3; 6; 7; 4 >.
Comparing Figure 7 with the trace of Figure 3, we see the obvious subgraph matching: 3 $ m, 4 $ g, 6 $ p and 7 $ k. In this small example there is only one possible matching chordless cycle. In the kinds of large networks we envision this is not so simple!
Imagine a 1,000 node seach key which reduces to a key
trace K:!, of say, 600 nodes. To nd a matched subgraph
in a reduced network of several million nodes is a
combinatorialy impossible task. All subgraph matching algorithms,
known to the author, assume some form of node and/or
edge labeling to initiate the search location and to control
the expanding search [
We suppose that a reduced trace, T = N :!, or a portion of it, has been identi ed as in the preceding section. During the reduction process, !, used to consolidate the network information we need not store only the resulting trace. We can also represent various steps in the reduction process. Our own code, for example, records y: for each retained node y. Thus, if the trace of Figure 3 was accessed given the key of Figure 7 then we would know that c: = fa; b; cg. Moreover, we know the order in which a and b were subsumed by c.
From this, a very close approximation of the original network of Figure 1 can be recreated. But, there will still be some loss of information. For instance, the connection between f and b would be lost. More complete information could be stored with each subsuming node, though at some increased storage expense. Alternatively, the complete information network, N , could be stored, with the trace network, T , separately stored as an easily searchable index.
It is our belief that with information structures of this size, retrieval of close approximations, i:e: the trace itself, will be su cient for most applications. 4.1
Biological recall is likely to be somewhat di erent from
a largely deterministic computer recall. There is some
evidence that biological organisms only store an abbreviated
trace and that the memory, as we experience it, is somehow
\recreated" [
In [
Such a semi-random \retrieval" process may be completely
inappropriate in computer applications, but it seems to model
biological recall rather well. Our memories often are
confused with respect to detail, even when they they are
generally correct. It also supports the notion of \re-consolidation"
which asserts than long-term memories are repeatedly
rewritten, unless deliberately distorted in our (semi)conscious
mind [
The representation of complex networks by a trace comprised of chordless cycles has a rm, well de ned basis. We know that there exists an e ective procedure ! to reduce a network N to its trace T by local and easily parallelizable code, such as might be found in the visual pathway. It is also known that such chordless cycle assemblages exist as protein polymers in all the cells of the body, including synapses.
Clearly, there are signi cant advantages, in terms of many fewer nodes and links, to representing network data in this fashion. Readily, real information stores, whether computer generated or biological, may have di erentiated (i:e: labeled) nodes and links. Nevertheless, this rst treatment of the problem as a purely abstract, graph theoretic issue has value. It provides a theoretical basis for more applied work.
We have suggested that subsets of the stored information can be identi ed and retreived by similarly reducing the search key. Then, in Section 3, using graph-theoretic properties arising from the fact that irreducible networks consisting of chordless cycles, we have sketched an access method that might support retrieval based solely on relational structure. In biological organisms, this or an associative memory approach may be used.
The next to last paragraph of Section 4.1 mentions a reconstruction process " which functions as a kind of inverse operator to !. This may be the most important observation of the paper. We are just beginning to explore it. If there is a way, given a trace T , to reconstruct a network N 0 which closely approximates the original network N , this could have profound implications for both computed and biological applications.