[RFC] 7 Graph Rework

[ghost]

This Discussion is meant as a Place to discuss the RFC 7 Graph Rework

[hikchoi]

Great work! I need to sit down and read it once more to give any meaningful feedback, but I just want to leave this paper I found the other day here that I find relevant to this discussion:

Bahareh Sarrafzadeh, Adam Roegiest, and Edward Lank. 2020. Hierarchical Knowledge Graphs: A Novel
Information Representation for Exploratory Search Tasks. ACM Transactions on Information Systems 4, TOIS,
Article 1 (April 2020)

[entityleak]

The most obvious thing I feel that's missing right now is inter-note links. Showing only a hierarchy tree doesn't really add much- a nested text list would do the same thing basically. Would love to see this implemented <3 !!

[funnym0nk3y]

That is soo true! I fiddled a little bit with obsidian and it allowed me to get insights I did not have with dendron. All in all I'd like to have a combination of both worlds.

Where a hierarchical graph excells:

• Picking up generaliziations e.g having matrices as a parent and then special matricies as children
• Generalizing via schemata like programming languages and then for each a Int child.

Where a non-hierarchical graph excells:

• Making connections between the children, e.g. between different implementations of Int in a programming language.
• Forming multi-parent notes. Sometimes it is not clear (or impossible) to define what parent and what child is. That totally depends on the focus.

I got that crazy idea in my head that one could combine both principles in a somewhat 3 dimensional graph. Or at least allow nodes to have multiple parents. AFAIK that is currently not possible due to the implicite nature of the graph through file names.

On the other hand side getting the graph just through links can get the directionallity wrong. I don't want to write empty notes to just get a graph edge like in the picture above a node that says "Every Programming language has Ints, see "C int", Python int", etc.".

Therefore I'd like to propose to make the graph explicit. Or at least not purely implicite.

[hydrosquall]

On a vision for a 3d graph: it can can tricky to navigate if it's fully unstructured, but things can work out if you're opinionated about what goes into a "layer" (a slice of time, a category, etc)

https://twitter.com/round/status/1219893959578681344?s=20

[funnym0nk3y]

Yeah, I can totally see that. I first thought of clustering them like stars and galaxies. But having multiple parents could make the view quite unintuitive. The advantage in such a case would be in partial views. I can't think of anything that needs a full view of every note. That would allow breaking it down and showing only notes e.g up to three hops away.

[zackbatist]

I am still in the process of importing my notes and refactoring them from my previous setup, and I'm noticing a few things that might be relevant for this discussion.

First, I think that it may be beneficial to put more emphasis on defining and describing different kinds of relationships. Currently only one kind of structural relationship exists (child -- IS_A --> parent, i.e. cat --> mammal), and semantic values are known only to the user. This is fine for forming naive hierarchies, but may not be sufficient when drawing non-hierarchical relationships with semantic value.

Relationships that cut across branches are generally applied as wiki links. However, these links lack defined semantic value. They are literally just a link and an implied inverse backlink, with nothing said about the relationships that they embody. Describing and specifying the parameters of various relationships that might exist within a vault might prove useful for navigating the web of notes in a targeted or question-driven manner.

I think one possible way forward is to define relationship patterning in the schema yml files. For example, if notes under the specified branch link to notes under another specified branch, those notes have a particular relationship. So let's say I have a hierarchy containing a genealogical taxonomy as one of my branches (i.e. mammals, fish, reptiles on top level; cat, dog and whale under mammals; salmon and trout under fish; iguana under reptiles), a second branch contains physical attributes, a third contains aspects of environments, and a fourth contains behavioural attributes. I could specify that any note under the genealogical taxonomy branch that relates to any note under the physical attributes branch is related by the relationship HAS. Whereas any relationship between notes in the genealogical taxonomy and the environments hierarchy is defined by INHABITS, and any relationship between the genealogical taxonomy and the behavioural attributes is described as BEHAVES_LIKE. I could then query for all animals that live in water through a cypher query that looks something like¹:

MATCH [a] -- [INHABITS] --> [environments: water]
RETURN a

And the result would be a list like salmon, trout and whale. I could further specify what kind of water through structural relationships under the environment hierarchy, which may look like water on the top level, with children sea, river, lake, etc.

In the example above it may seem that a distinction is being made between what seems like a primary set of notes and sets of what could be described as attributes with lesser centrality. But this is simply a bias creeping in from the directionality of the relationships and my stated emphasis on the animals. If I were a behaviourist then I might emphasize the behaviours, and the relationship to animals might be something like EXHIBITED_BY.

In all cases, there is a distinction between structural and semantic links. Structural links frame the ways in which semantic links may be created, especially in a batched manner, via rules defined in the schema. Semantic links are applied as wiki links, and perhaps there could be a better way of delimiting the section of text within a note to which the link applies -- possibly by using markdown-style links, which specify the text that masks the link in the square brackets immediately prior to the curved brackets (i.e. [text to be related](link to other note)), or through further atomizing the contents of a note (see my next comment, which I will submit as a separate point in the discussion)².

I would also suggest expanding the number of structural links available to the user. Currently only IS_A is available, but I could also imagine relationships denoting equivalency (aka LIKE), opposition (IS_NOT), or others that may require further imagination. This could lead to the ability to cascade relationships across a network, for example by relating note A to note B while note B has a structural relationship of equivalency to note C, thereby indirectly or automatically generating a carry-over relationship between A to C.

Footnotes

1. I'm a bit foggy on how this should actually look and don't care to look up proper syntax, but just mean to illustrate the point. ↩

2. There has been some work on this through semantic markdown that people keep referring to, but it seems that work has stalled so a new approach might be worth pursuing. ↩

[zackbatist]

I would also like to point out that semantic linking is already tacitly ​supported via the ability to stylize tags using custom ​CSS.

[zackbatist]

I think it is generally a bad idea to count headers as children, although I was tempted by that prospect earlier. They are not independent entities, they can not exist on their own, and they can not have their own YAML front matter to specify crucial metadata such as note-level UUIDs, date created, etc. But they may still be explicitly defined and related to the notes that they are a part of via a structural relationship (see my earlier post), which may makes them kind of like pseudo-children.

​I think that the approach taken by Obsidian might be worth emulating; essentially assign UUIDs to all elements within a note, such as headers, paragraphs and footnotes. Each of these internal UUIDs can be linked to the note's UUID via a structural relationship (perhaps CONTAINS or PART_OF], and may be prefixed by something that indicates that kind of element it is, for instance f123 is a footnotes, h456 is a header, p789 is a paragraph.

This would be useful for assembling footnotes from ​throughout a hierarchy. I'm inspired by how some books assemble endnotes for each chapter, for each section, or for the entire book (and by some recent struggles getting pandoc/latex endnotes to work as I want, sigh).

Of ​course, the scope of what constitutes each kind of element would have to be explicitly defined. For example, the scope of a header might be defined as the ​next n lines up to the next header of equal or higher status, i.e. an h2 contains all h3-h6 under it up to the next h2 or h1.

Additionally, because headers are not restricted by issues derived from the file system (i.e. character length and uniqueness), they are really useful for templates. I could imagine a handy situation of querying all headers of the same character string, which appear in all notes under a hierarchy through prior implementation of a template. In this case, UUIDs would have to be derived based on the properties of the string, kind of like a hashing function (which I know basically nothing about).

[kevinslin]

Summary

Awesome work on the RFC and thanks for putting this together. I think there's a lot here so probably makes sense to break up the work in chunks. The first phase can be the graph backend + rendering. We can save embedding for a second phase (maybe do enough work to make sure that what we do in phase1 is compatible with embeddings).

I put some of my high level thoughts below. I think the output for the first phase should be a graph renderer that is built into Dendron (instead of a separate extension as we have today).

As part of that work, we should figure out the minimal feature set that rendering should support.

Graph Backend

• src: https://wiki.dendron.so/notes/e53cb939-88f1-4892-9e8d-e98551923995.html

I think it makes sense to do a db based approach. My main question is choice of local db. Do you know how GUN compares to pouchdb? https://github.com/pouchdb/pouchdb

I'm asking because we're considering using pouch to help with caching, filtering and querying of local data.
Like GUN, it runs local first and can sync with a remote. It connects to and speaks couchdb in the backend so its well documented. The downside is that it's not based on a graph model.

It's hard to predict the future but the current use cases for dendron are primarily document focused so I'm leaning a document focused db over a graph enabled one but open to changing my mind on this.

Graph Rendering

• src: https://wiki.dendron.so/notes/582157ea-fdea-475f-9ae3-5b79d790f371.html

For this, I'm guessing we'll use d3 or some higher level library built on top of d3. I know our friends at Foam have a graph implementation, I think its built on top of d3. Might be good to talk to them about it.

For minimal feature set for the first version

1. What customization Options are wanted/needed
   • Coloring
   • Add metadata to edges #stretch-goal
   • Highlighting
   • Hiding
2. What types of Filters
   • Hierarchal Structure
   • Schema
   • Local graph (show immediate neighbors) #new
   • Edge based graphs
   • Regex based (eg. hide/show nodes that match regex) #new #stretch-goal
   • Tags
   • Links
   • Location
   • Text
3. What Interactions do we want?
   • Just clicking on Nodes
   • The ability to move Nodes from One Hierarchy to another?
   • Creating a Schema from Selected Nodes? #stretch-goal

Graph Embedding

• src: https://wiki.dendron.so/notes/84fbcc64-7646-4a4d-80b9-1a2c866567a4.html

Simple solution is a svg. Obsidian has an interactive graph on published pages. Not sure yet if people would find that useful since you can achieve the same thing with a list of backlinks.

Other

I like @zackbatist idea of adding additional metadata to the edges. This can result in rich querying capabilities down the line. I added it as a stretch goal of v1.

In terms of having headers as children, I think it'll become messy. Rather, I would parse the body of a note as a tree instead of a blob of text which we can now run tree operations on.

[ghost]

Summary

Thank you for your kind feedback @kevinslin

Graph Backend

1. Choice of Database:
   • GunDB:
     It can be seen as a synchronization protocol.
     If we see it that way, we can synchronize the information from the backend with the Plugin using Gun.
   • Pouchdb:
     It could be used to store the data in the backend.
2. Data Structure:
   • Here I would recommend going with Graphology.
     Wrapping the current Nodes maybe as the attributes of the Graphology Reference implementation.

Sadly I have not much information about pouchdb, but what I know is that GunDB is more like a Graph synchronization protocol.
So they could even be combined, making PouchDB the store of value and allowing GunDB to connect the different parts of dendron.
Naturally, this would depend on if a Webview could connect to a Websocket the engine provides.
We are leaving the Plugin out of the scope for refreshing the graph view.

Additionally, even using one of these DBs wouldn't prevent us from adjusting our Datastrucktures to factor in the Graphology spec.
Implementing this spec would allow us to pass the Graph object into the Layout algorithm to render them using d3.

Furthermore their is a parser and writer for Graphology that turns Graphology graphs into the gram text format Graphology Gram, which would make it easier to embed the graph.

Graph Rendering

Yes, I'm all for going with D3.js for it. If we implement the Graphology Data structure as a wrapper for the Current Nodes, we can loop over all Nodes and edges to add them to the graph, or use some parts of the Standard Library from it to Filter the Nodes beforehand for rendering only the local Node with its edges.

To your point about interactions, If I click on a node, what does happen?
Does the Corresponding note get opened? Or do I highlight the Node in the graph to maybe grey out all edges and Nodes that are not linked with this Node?
How does it interact for a local Graph? Do additional edges and Nodes get loaded when I click on a Node?

[kpathakota]

Re: If I click on a node what happens?

The default expectation here is that the corresponding note opens and the node in the graph is centered.

Improvements to consider:

1. Greying out non-connected nodes.
2. Focusing the selected node so it's centered on the graph and all the other connections are moved closer to the note (so the graph re-arranges).

[holajoyce]

this is a neat example of graph representation, that can proabably work with a sqlite backing store. Mode analytics demo, docs I like that it has different node sizes, different colorings of nodes for different cluster, the edges have different widths depending on weights.

[funnym0nk3y]

Is a proper graph DB like OrientDB or Neo4j with a server even an option? Or should it run in node like pouchDB?

[hfellerhoff]

Hey everyone! I'm Henry, and I'm working on the graph redesign this summer. I've put together a design document with some notes on the current library recommendation as well as a tentative roadmap if you would like to take a look: https://wiki.dendron.so/notes/6e87249b-358f-4f4b-8049-dff6e6a8463b.html

Look forward to any feedback you may have!

[ghost]

Better Graph View–Design

Overall

1. Will keyboard navigation and interaction be a first class Functionality?

• Select Nodes per Keyboard
• Quick Navigation between Nodes / Input fields?

2. What accessibility options will be taken?

• Screen readers?

Implementation

Graph Structure One of the benefits of going with a Next.js-centered approach is we get all the benefits of React and global state. Since notes will be loaded into the global Redux store already, querying them and creating the graph structure should be fairly straightforward.

Questions:

1. How could I get the Graph Data without myself using some form of React?

• My main problem with this is that there is no mention of the Graph data is represented in the backend, in the Library Research, there is the mention of Graphology that could be used but marked as unclear if needed. I would say Yes, especially to get the data in a Framework agnostic format that does not require a framework.
• Secondly, I'm worried that if we want to Provide an endpoint like /api/graph. We, make it harder to get the data in a way that is framework agnostic.
  • Yes I think of Cytoscape.js as a Framework as well.

2. Are their at least ways planed to use the Graph Data Structure if I don't want to publish my site using Next.Js?

• I mean accesing the Graph Data Structure inside a Pod. Without the need to build the Graph up myself?

Styling Styling in Cytoscape is done through a style object, which is a CSS-like style array. There are two clear options for styling: either a dedicated CSS stylesheet or a config file with various options. Since the Cytoscape styling method is slightly abstracted from direct CSS, it may be easier to use a config file and lightly parse it into a useable form.

Questions:

1. That is all good and fine, but how does it look with the integration of VSCode themes?

• This is something that should be treated first-class in my eyes for User Experience.
• Not everyone wants to choose a Theme for their Editor and then Notice that some Extensions functionality does not follow it.
• Will this be Part of Stage One or Stage 2?

Tasks

Stage 1: Replacing Markdown Links

Questions:

1. Which Layout will be used?

• Is it going to be user seletable?
• Will it be open to configuration by the user?

Stage 2: Core Features

Questions:

1. Filtering:
2. How are the plans for this? I don't know Redux for this as a warning.
   - How are the nodes getting filtered?
3. How could one query the nodes based on Connections between two Nodes?
4. How would filtering based on schemas Work?
   - Like show all that are Journals between 2020.01.01 and 2020.03.31
5. Can I filter nodes based on their Connection to a Tag.
6. Syling:
7. How easily could Dendron Schemas manipulate that styling if desired?
8. If Schemas get the possibility to define a custom Icon and color for themself like proposed in Rfc / 712 Schema Improvements / UI Optiones to attach these to the Graph Node?
9. Can I style Nodes based on Links to other Nodes?
   - Use Case would be Tags
   • This could be improved by extending Schemes or notes with a Tag Type for example.
10. What Options are planned for styling?
    - Could booth options mentioned in the styling point of Implementation be used?
    • Which format will the possible styling config file have?
      - Can MetaData be used for styling?

[hfellerhoff]

Hey @flammehawk , thanks for the great and in-depth feedback. I'll answer what I can, and I'm sure @kevinslin can weigh in on the points I may not be able to answer.

Keyboard Navigation

I updated the design doc with information on this and on general accessibility. Essential keyboard navigation will be added once the first integration is complete, with support for navigating up and down between hierarchies, cycling between child nodes, and opening notes. As we implement new features, keyboard navigation will added to support those features.

Creating an accessible <canvas /> element is difficult, but there are a couple of canvas accessibility ideas shared by Mozilla that we will look into implementing.

Graph Structure & Data Accessibility

This is an area where @kevinslin can add more, but there are a couple of different ways to get data to create a graph outside of Next.js. We offer a GraphViz export pod that can export note data in a graph format supported by many visualization libraries and applications. In addition, Cytoscape is a pure JS library, meaning that the same/similar logic used in the Next.js site could be taken and implemented across any site.

Layout

Cytoscape comes with a number of in-built and community-built layout plugins. The current chosen layout is cytoscape.js-euler, as it has good performance while creating an intuitive graph. Support for in-built layout algorithms would definitely be a possibility (something like breadthfirst could be interesting), and other plugins could be added by community request/implementation.

Styling

Since custom styling will be (most likely) implemented with an external CSS file, custom styling will likely be accomplished with some implementation of custom classes. Since Cytoscape allows for adding custom classes to elements, automatically adding classes to elements in a syntax like .graph__schema__[ID] or .graph__tag__[NAME] (following BEM) could be a straightforward way to allow for a completely customizable graph.

Good catch with VSCode theme support – I'll add that as a component of the styling step in stage 2 of development.

Filtering

We have access to the full note data through Redux when rendering the graph, so I'd like to include filtering based on metadata and other common note attributes. In addition, this note data contains a list of outgoing links, which makes it possible to filter based on tags.

I can get you more details on filtering based on schemas soon. We could definitely implement some sort of hierarchy filter in the full graph view, e.g. filter by languages.javascript and only show that node and child nodes.

[hydrosquall]

UX feedback on the release as of 6/08/21 (Exporting from the #feedback channel on discord)

This is so exciting! I'm so happy to see this running smoothly and to have the power to reposition my nodes. Here is a first batch of UX challenges I encountered around dealing with a complex nodes layout, and some ideas for how to wrangle with them.

1. The initial layout for my graph had a lot of overlapping text labels, which I'll need to reposition to have a readable graph. Some other graph layout tools deal with this by giving you "power tools" to change the positions of more than one node in your tree at once, like a brush (see this Blender plugin) https://twitter.com/specoolar/status/1388964982788956163

2. Aside from the ability to move my nodes around, I'm keen to reduce the # of items in the graph to a relevant. Once you have a set of nodes selected, you could trigger operations ranging from (isolate just these nodes, exclude these nodes, keep everything that's descended from these nodes, etc. (There's a similar interaction in https://microsoft.github.io/SandDance/app/, querying some rows using the magnifying class, and choose between isolating or excluding your selection. It would be nicer to multi-select the nodes with either a brush or shift click than having to write a query though).

3. I'm also curious what people would make of the ability to roll up / expand subgraphs. Cytoscape offers a plugin for this ( http://ivis-at-bilkent.github.io/cytoscape.js-expand-collapse/demo.html ) . This is a more challenging problem to go after, but one could conceivably cross this idea the way geographic maps handle auto-rollup based on zoom level (e.g. having a mode with multiple levels of detail): https://leaflet.github.io/Leaflet.markercluster/example/marker-clustering-realworld.388.html

[ScriptAutomate]

Update to the RFC link: RFC 7 Graph Rework

Some reference links provided by community members, in case they can help with the ongoing discussion of graph rework, improvements, and embed support:

• https://observablehq.com/@d3/force-directed-graph
• https://observablehq.com/@icarofonseca/design-theory-mindmap

These came from an issue opened here: dendronhq/dendron-site#395