Interactive graph visualization
tangjeff0 opened this issue · 17 comments
READER BEWARE: this is a rabbithole and perhaps the most exciting part about knowledge graphs. Continue at your own risk.
I'm skeptical any of these would be quite good enough out of the box for the Roam/Athens use case. But at the implementation level, these are some usable libraries today:
- Roam uses cytoscape, I believe.
- Org-roam uses Graphviz.
- More JS libraries: https://neo4j.com/developer/tools-graph-visualization/
In terms of what I want from a graph in general, and not just what is available today, here is a rambling list of stuff:
Read-level features for a global overview, e.g. https://twitterverse.net/:
- can visualize a large number of nodes in a tractable way (Roam already cannot do this), probably with multiple algorithms and views
- many variables could be used as parameters to the algorithm
- number of inbound and/or outbound links (neighbors)
- content size: word count or number of blocks
- content itself (i.e. NLP and sentiment analysis)
- based on these parameters, algorithm would be able to cluster nodes, depict node size, and zoom
- zoom (no not that Zoom!)
- perhaps switch between 2D/3D/VR
Read+Write at the local page level:
- page preview of course
- to incrementally expand a page's "peripheral vision" to 1/2/3/N hops away
- to arbitrarily query subgraphs using set/boolean logic. I believe this combined with previous point would feed into complex permissions, e.g. share [[Page X]] and all nodes at most 3 hops away excluding [[Page Y]]
Links, mainly from Discord. Some more relevant than others.
- visualizations using Wikipedia data
- Codex for literature analysis
- dimensonality reduction
- is it possible that a hypergraph is a better data model
- noahtren: plotting based on NLP
- Go Links
- Hive Plots
- Les Misérables Co-occurrence matrix
- Walrus
- RemNote Tree & Graph Viz by David Dohan
- Kantian corpus viz
- Bible corpus viz
- Elm lang dependency viz
- https://www.yworks.com/products/yed
- http://www.biofabric.org/gallery/pages/SuperQuickBioFabric.html
- git contributor visualization: https://www.youtube.com/watch?v=P_02QGsHzEQ
- https://quid.com/
- https://infranodus.com/
- Garnet https://news.ycombinator.com/item?id=11230547
- cola.js https://ialab.it.monash.edu/webcola/
- https://www.anishathalye.com/2019/12/12/constraint-based-graphic-design/
@tangjeff0 Regarding knowledge graphs, I would like to add DMX – The Context Machine @ dmx.berlin/.
I was about to jump in to say that there's lots of traction in the Clojure world regarding Vega / Vega Lite at the moment. But that lead me to a question:
This issue might be about graph as used describing nodes and edges?
Plotting libraries for XY graphs and similar might be a different subject.
to incrementally expand a page's "peripheral vision" to 1/2/3/N hops away
This would be fantastic. Roam's graph view is already unusable for me for my private KB.
I really like the idea of expanding "peripheral vision". I think it could solve the problem of "contextualizing where you are relative to your whole knowledge base", which helps:
- Load many notes into short-term memory, to prompt noticing new connections and inconsistencies
- Navigate by first moving to the "rough neighborhood" of the idea, in case you forgot the right search term
- Promote a vague feeling of confidence that notes are well organized
I'm envisioning a "google maps style" interface, where you navigate to a note by:
- Zooming out until your destination note enters your periphery
- Zooming back in to that destination note
Basically, I want something like Supreme Commander's Minimap
To enable this, I think we need to solve these problems:
Multiple hierarchies clutter a visualization
I'm ~80% sure that graphs with multiple overlapping hierarchies will always be hard to visualize in space, because tons of edges have no choice but to cross. Even 4 hops away might already be too much for non-trivial, multi-hierarchy knowledge bases.
Mind Maps and Google Maps work because they have a single hierarchy of "large piece of land" -> "small pieces of land". Zooming in traverses down leafs, and zooming out traverses up to the root. A camera is a spanning tree starting from the node that's the center of attention. The rules are simple, and you don't have overlapping hierarchies cluttering the camera in unpredictable ways.
One workaround is to focus on one hierarchy at a time. For example, if you're making decisions about company staffing, you can somehow focus on just the "org chart" spanning tree. If you're making decisions about project prioritization, you can focus on just the "project/task" spanning tree.
Visualizing one hierarchy at a time also opens up specialized tree visualizations such as Voronoi Treemaps
Distance in the visualization should match intuitive relatedness in your brain
For the navigation to be useful, ideas that feel related to another idea should be close to each other in the visualization.
Physics spring/repulsion layouts seem to work for single hierarchies, but not for complex graphs. Two ideas that seem related might end up far away in the visualization, because the layout of the dense hierarchies dilutes the layout of the smaller ones. An example would be the [[DONE]] node in Roam being a hub that forces it's children away from each other.
Some of my intuitions here are:
- ideas with many mutual ideas are close
- ideas with picky mutual ideas are closer
To elaborate on 2) - Alice and Bob are close because they both work at [[Company X]] (a picky idea, since not just anyone can work at Company X). Alice and Charles are not close just because they're both [[People]] (a promiscuous idea, since lots of things are People).
I think expanding peripheral vision should roughly correspond to increasing the "relatedness radius" around the center of attention.
One method of periphery expansion is to expand each node 1 level deeper. This might clutter the visualization if you expand the [[DONE]] node though - it'd introduce too many irrelevant nodes.
Applying intuition 2) to expanding periphery - [[DONE]] is a promiscuous idea, so is it needs a larger "relatedness radius" before revealing it's links in the visualization.
One way to apply this is to have "expanding periphery" be like pumping water through the edges of currently visualized nodes. If a node has only a few links (a picky idea), it doesn't require much more pressure for the water to flow through it's links. If a node has many links (promiscuous), it requires a lot of pressure to pump through each link.
Another analogy is that a visualization represents the pages and links you'd traverse if you cloned yourself and started exploring from the center of attention. Pages with many links have more cognitive overload, so it requires more attention to navigate past them.
Visualization should be somewhat stable and consistent
Associating an idea spatially makes it easier to remember (Method of Loci), but if the visualization changes drastically, the spatial associations are discarded.
I believe this is why Roam's 1-hop page-specific graph visualization isn't actually useful for navigation - the notes move around every time you navigate, so the spatial associations are too ephemeral to memorize and reuse. The Brain's visualization also seems to have this issue.
With paper mind mapping on the other hand, an idea almost seems to occupy a physical location in space, because it's hard to erase/move nodes. The space is the scaffolding that contextualizes the ideas.
To solve this issue, I think the visualization needs to be somewhat consistent, at least for the duration of one "session".
Really enjoying this thread. Graph visualizations do get really messy, especially in this context, where you'll have a ton of edges and (potentially) a fair amount of duplicate vertices.
Some thoughts:
First, vertex annotation helps solve for graph legibility. Adjusting vertex size based on degree is a great first step. We can also annotate nodes at the ontology level and the display level.
Ontology level
You can map vertex labels to icons, colors, and other semantically meaningful visual indicators. For instance, you can infer concept type with an entity classifier, and then map the different entity types to icons that would appear close to the node: i.e. geographic concepts -> globe icon, intellectual concepts -> book icons, people -> stick icons.
Linkurious and KeyLines, and Palantir (even though Palantir isn't actually a graph) all use this design pattern.
In the vein of focusing on one hierarchy at a time, users could also use the icons to drill down on specific types of context: i.e. reduce the graph to the relationships between financial concepts and emotional concepts.
You can also extend the markdown language so folks could, say, represent the importance of a concept to them by adding extra brackets when they instantiated the concept -- or at some later point. You could do a bunch of things with that, like add a star next to the vertex for each bracket, change the vertex's color, etc.
Display level
You could allow users to add annotations to vertex while they interact with the visualization to help them build their own map of the map, as it were. For instance, users could add a "bookmark" to a vertex that is relevant to their current line of inquiry.
Louvain (very fast) and Girvan-Newmann (not so fast) could be options for identifying hierarchy in bi-directional graphs
Louvain and Girvan-Newmann return a set of hierarchical communities (optimized for modularity) for each record; these steps can correspond to incremental network views (as communities merge at each step). Those communities would play nicely with something like the Voronoi treemaps mentioned above.
This ^ leads into..
Linear approaches to graph visualization
Traditional graph layout algorithms create "hairballs" that are hard to interpret. Martin Krzywinski. developed a method for what he calls "rational network visualization" called hive plots. Nice interactive example here.
Hive plots assign vertices to one of three or more axes (which can be divided into segments) and ordered based on meaningful attributes (i.e. centrality). This approach has a lot of advantages:
The biggest advantage to this approach (beyond a user being able to accurately infer something about a vertex/community/whatever based on its position) is that userscan optimize network layout based on attributes they care about; put all of concept/document type X on this axis, type Y on this axis, group by betweenness centrality (used to identify bridge ideas) etc.
You can also do cool stuff with cooccurrence matrices.
Last, on the challenge of identifying vertices that are relevant to a given vertex, even if they're multiple degrees separated:
-
You could run weighted shortest path queries to identify vertices that are multiple degrees away from the vertex you're interested in of type (x). I.e. what are the most interesting concept y nodes related to my concept x node. You can weight edges by number of concept cooccurences or have multiple edge types with different weights (this would be hard without user annotation).
-
You could use network metrics like triangle counts to identify a nodes key neighbors (kind of like a top 8 on MySpace.)
-
You can use node embeddings (i.e. node2vec) to do a query like give me the top N closest vertices to my vertex based on how close they are in vector space. You can then allow the user to customize that query for their use case -- give me top N and exclude vertex of type X, or document containing this term, or so an so forth. I love node2vec. It works really well.
Node2vec only draws from network structure but stellargraph has algorithms that draw from network structure & vertex features so you get even better recommendations.
I do suggest you have a quick look at vega for this, at least for a prototype. As a visual specification is in json there is a very nice mapping to clojure data structures. In that regard, also have a look at the clojure oz library for vega.
Another thing that might be useful: running community detection on the graph and coloring the nodes according to their community.
Also: please please stay away from 3D/VR. I teach data visualisation, and... well: just don't.
In response to tntmarket's ideas above regarding a complex graph suffering from a lot of crossing edges: you could also run something like tSNE on the nodes and let that algorithm define the location of the nodes on the screen, without showing the actual links. These could for example only be shown if hovering over a node.
There is quite outdated tool (in Flash) called RelFinder. I fell in love with it, immediately. Please consider adding similar functionality to Athens = discovering all connections between a list of pages (including the faceted search). It is very different from shortest-path finder. Here is a Youtube video:
https://www.youtube.com/watch?v=G0r1G-duPcQ
Thanks.
Will re-open when after v1 is complete
There is something that can be a source of inspiration for visualizing the graph in a number of useful ways. It's Tinderbox app for MacOS.
The features I would love to see implemented are:
- agents;
- timeline view.
It's probably out of scope of this specific conversation but I feel like graph visualization is a subset of a more abstract projecting data into something visual/interactive task, which is good to keep in mind to be more creative about the solution.
I'm neither a coder nor a data expert in any way, but I've been dreaming about this sort of functionality for about 6 years. TheBrain was just too clunky in the text-editing side of things, even if it was visually beautiful. Gephi and Linkurious weren't really what I was after either. I spent (too much) time trying to learn Javascript to use d3js force diagrams to map out my notes and blog posts, but it was just too far beyond my capabilities.
I ended up just using OneNote, but would love to get out of it for many reasons, so I'm extremely thrilled to see the recent explosion of tools that integrate notes and visualization. I just found out about Roam yesterday, quickly moved past it due to closed source, extortionate fees, and an embarrassingly useless graphing implementation.
I just want to say that coming across Athens, and specifically this discussion thread, has filled me with joy that my dreams may finally be coming to reality of having a powerful yet simple, open-source, etc... knowledge tool that allows for excellent text-based entry (like Roam) but also a proper appreciation of data visualization techniques. I have tons of ideas documented from my d3js boondoggle of how I'd want the map to work - tooltips/preview, zoom, filters, search, centering on nodes, only showing nodes that are x amount of hops away, etc.. - and you clearly have all those bases covered, and more.
In all likelihood I'll be transitioning all of my cluttered notes from OneNote to Obsidian (since they use basic markdown files) in the coming days, organizing and reformatting them with links etc... and then probably moving them over to Athens once you guys are up and running because of the open ethos (and probably superior technical capabilities as well).
Sorry if this clutters the topical discussion thread - I just wanted to share my appreciation for what you are doing. You guys really know what you're talking about and I cant wait to see and use it. I'll be at the front of the line to use it and will be eager to give thoughtful feedback on it all.
The only thing I'll suggest for now is to keep it as simple as possible (or allow for the user to customize what they see) - most of the links in the original post are to diagrams that look extremely impressive visually, but are absolutely useless for any sort of actual knowledge transfer (and as jandot said above - stay away from 3D). I think various filters based on tags and other metadata, and customizing how many hops away you can see will work very well.
Thank you very much for your hard work - this is a really important project.
JesseToday at 5:57 PM
manually creating graph layouts is the most undervalued strategy
https://www.dropbox.com/s/c6nlk53jlhetqai/toothbrush_diagrams.mov?dl=0
Dropbox
toothbrush_diagrams.mov
Shared with Dropbox
https://github.com/JesseAldridge/electric_toothbrush
GitHub
JesseAldridge/electric_toothbrush
Simple client/server notetaking tool inspired by Notational Velocity - JesseAldridge/electric_toothbrush
I tried pitching this to the Obsidian people but they didn't get on board lol
Jeff TangToday at 6:05 PM
pitch us
JesseToday at 6:07 PM
I mean the demo video pretty well captures it
the short version: graphs are a better way to represent knowledge
auto graph layout is too hard though
so build a tool oriented around easy editing of graph layouts
Jeff TangToday at 6:10 PM
where's the demo?
JesseToday at 6:10 PM
https://www.dropbox.com/s/c6nlk53jlhetqai/toothbrush_diagrams.mov?dl=0
Dropbox
toothbrush_diagrams.mov
Shared with Dropbox
discord unfurls the link annoyingly
if you click anything other than the giant image it wants you to click you can watch it :slight_smile:
Jeff TangToday at 6:15 PM
oh i thought it was on github
JesseToday at 6:15 PM
it's open source yes
so also on github
Jeff TangToday at 6:15 PM
haha sorry so much confusion i meant i thought the link to the video was on github
but it was here all along
JesseToday at 6:16 PM
🌈
most annoying thing about the tool is it crashes if you type too fast
but it works 95% of the time which is just enough to make me too lazy to fix it
Jeff TangToday at 6:18 PM
this is really cool
how could you see this working with athens
JesseToday at 6:20 PM
I don't actually know what athens is lol
I just know that I'm no longer interested in using text files to manage knowledge
I'm hoping somebody else will build a "graph first" knowledge management tool for me
Jeff TangToday at 6:22 PM
cool well add your wants/thoughts here #21
It's probably out of scope of this specific conversation but I feel like graph visualization is a subset of a more abstract projecting data into something visual/interactive task, which is good to keep in mind to be more creative about the solution.
@Nek It doesn't seem to me to practically be outside the scope of this discussion. At best, keeping in mind that we don't have to limit ourselves in the long run to a single interactive graph visualization might lower the stakes in choosing a small handful of ones to polish for the time being.
Themes for these would be very useful, and might be the thing that stirs up hype for tools for thought in the general public.
I've really enjoyed using Obsidian's graph view. It has dynamic filtering and is very fast for large graphs. One thing that would be amazing would be a color gradient for nodes or edges based on centrality. I have some experience with social network analysis but am more of a data scientist than an SWE. Let me know if I can provide clarification!
Wow, I'm just discovering Athens and this thread. I must say that I am really enthusiastic about what it will become.
I've always dreamt of a system where my knowledge and a lot of people's one could live in a virtual N-dimensional Space. It would be really helpful to make projections of e-brains from an N-dimension space to a 3D-space, and navigate through it to rediscover things from an unexplored-yet perspective. I could map ideas & concepts to mental places and boost my brain.
An interesting tool I already use, that may inspire you if you don't know it yet is : Open Knowledge Maps
It computes a dataset of research publications given keywords, and cluster them in bubbles. It really helps to make useful discoveries and their data visualisation tool is quiet interesting.
Here you'll find their visual representation of the computed "graph"/"bubbles" for the term "Networked Thoughts"
I really hope it may help.