Custom Layout For Factor Graphs

1

Greetings all,

I am using GraphViz as part of a project to visualize the probabilistic graphical models which are used in the Julia software package RxInfer.jl: https://rxinfer.ml/. These are Factor Graphs (most generally speaking) and “Forney Style” Factor Graphs more particularly. Note: the actual object used in memory is a “factor graph”, NOT a Forney style factor graph.

I have created a GitHub issue in the relevant project which specifies the details of my use case. That can be found here: Improving Graph Visualization Functionality · Issue #233 · ReactiveBayes/GraphPPL.jl · GitHub.

I would like to implement custom layout algorithms for use with a “raw model” and “Forney Factor Graph” representation, respectively. See the above GitHub issue for details. Indeed, the main GraphViz documentation has a page devoted to this issue: Writing Layout Plugins | Graphviz.

I’ve read this page, however I still don’t have a sense of what the next steps would be to actually get to work on making a custom layout. It looks like I need to fill in certain boilerplate C functions. I can’t seem to find out where these functions are located and otherwise how to take the next steps, as I say.

I realise that this is a very nebulous, Ill-posed question (apologies). However I feel that this is the best I can do just now. I’m very happy to provide clarification and elaboration on whatever you think may be relevant.

Many thanks,

Fraser

2

As an alternative to diving right into custom layout algorithms, I’d suggest starting with dot to see how close it can get you toward your goal. My alternative, for each desired output type (raw, FFG, …)

  • identify where there are options in the diagramming “standard”. i.e. does every FFG diagram look identical or have people taken liberties?
  • pick one, existing diagram and try reproducing it using dot. Do it by hand, don’t jump into any programming, yet. The goal is to determine where dot “works”, where it “fails”, and where it is awkward or sketchy.
  • repeat with more complex target diagrams, to enhance your understanding of Graphviz in general, dot in specific, and to flesh-out the “works”, “fails”, “sketchy” list. Feel welcome to come back to the forum to get dot advice.
  • Now, decision time:
    • If dot can fully produce your desired graphs, start programming, yea!
    • If not, some alternatives:
      • A dot | postprocessor | neato -n “pipeline” This would allow dot to do get close, tweak the result to fix the things that dot gets “wrong” for your needs, then neato to finish up (neato -n will be explained later)
      • Don’t use dot, write just a node placement algorithm that would feed neato -n. Essentially, this is what all the existing layout engines do.
      • Make enhancements to Graphviz that would address the “fails/sketchy” list (see Issues · graphviz / graphviz · GitLab) There may already be issues that would get you closer and would help others.
      • write a custom layout engine
      • Abandon Graphviz and consider a different diagramming package

neato -n allows you to specify node positions or node and edge positions and neato produces the image. see FAQ | Graphviz and FAQ | Graphviz

Feel free to post an example target graph here and we can see how close dot can get.

3

Thank you very much @steveroush!

Apologies for this late reply, I got sidetracked. I’ll try to provide some additional context and then address each of your points.

I should clarify an important point about the three kinds of graphs that I am considering. To start, the software package RxInfer.jl: https://rxinfer.ml/ uses “reactive message passing” to instantiate a paradigm for approximate Bayesian Inference. This kind of message passing is analytically described on a Forney-style factor graph (FFG). There are usually constraints of one kind or another to consider, hence one usually talks of “constrained” Forney-style factor graphs: (CFFG). In both cases, FFGs and CFFGs are used to describe the analytic message-passing procedure. This is what one sees in almost all papers on the subject. Indeed, the following two papers provide a relatively comprehensive overview of what these two kinds of graphs are, and how one would go about conducting the message passing procedure: [2306.08014] Realising Synthetic Active Inference Agents, Part I: Epistemic Objectives and Graphical Specification Language and [2306.02733] Realising Synthetic Active Inference Agents, Part II: Variational Message Updates.

Here’s the rub… RxInfer.jl itself does not actually instantiate or use FFGs or CFFGs. The message passing procedure is actually carried out on a “plain old” factor graph. Again, a “raw” factor graph is just a bipartite graph. The two node sets are factor nodes and variable nodes, respectively. Nevertheless, the message-passing procedure is formally (abstractly) equivalent in the respective cases that either use a “raw” factor graph or an FFG/CFFG.

Given these considerations, my collaborators and I want to build visualization capabilities for the “raw”, FFG and CFFG models. Again, only the “raw” model actually exists in memory, the equivalent FFG/CFFG is “merely” a nice mathematical abstraction. To simplify things, we have decided to break the project down into three stages: “Raw model”, “FFG” and “CFFG”. At present, we only care about visualizing the raw/plain model.

I have already built the initial functionality to create a GraphViz graph from an RxInfer model. Indeed, the following is a simple example of a coin-toss model - designed to infer the (unknown) bias of the coin:

coin_model_analytic
coin_model_analytic1352×405 27.5 KB

Instantiating this model in RxInfer, we have:

coin_model_RxInf
coin_model_RxInf1058×641 84.1 KB

This has created the above model and conditioned the model on three data points or “flips” of the coin. For context, the “gppl_model” is the underlying “raw” factor graph.

Using the existing visualization functionality, we can plot the graph with GraphPlot:

coin_existing_viz
coin_existing_viz433×682 37.6 KB

Now I have written a function called “generate_dot”, which takes in the raw model - gppl_model - and outputs the associated DOT code as a Julia string. I then have another function called “show_gv” which executes this DOT string and consequently constructs the GraphViz visualization. Here is what it looks like with the neato layout:

coin_my_viz_neato
coin_my_viz_neato519×762 40.5 KB

I’ve made it such that white circles are “variable” nodes and grey squares are “factor” nodes. Here is the same vgraph again, only now with the dot layout:

coin_my_viz_dot

I find the output of the dot layout to be undesirable. The neato spring-style layout is very much what we would like to go for, regarding the raw model. In any case, we would ultimately like to be able to write a custom layout for the raw model.

Indeed, neato seems to be fine for our initial contribution, however it seems to run into trouble for larger model graphs. Here is the result of a neato layout for a much larger graph, for a completely different model - note that this graph is cyclic, that’s probably relevant somehow…

linr_my_viz_neato
linr_my_viz_neato977×739 64.1 KB

It’s too big to see all at once, but some of the nodes clearly overlap in undesirable ways. I have tried to manipulate everything that I can but I can’t seem to stop some of the nodes from overlapping. This is one of the reasons that I think it would be best to go for a custom layout.

Your comments about a “postprocessor pipeline” intrigue me. Perhaps that could be used to address the overlap issues I seem to be having with neato? Perhaps neato -n is best for this, I can’t believe that I missed that option!

In any case, I do want to be able to write a custom layout engine for our use case. The means of getting started on that are completely opaque to me now, I didn’t find the associated documentation page to be all that helpful. I should note that we are also going to be using TikZ for this project. Indeed, TikZ is best for creating “paper-ready” visualizations, however we also really like GraphViz and we want to continue with it.

Insofar as any of the above constitutes an “actual question”, I’m interested in anyone’s thoughts regarding how to avoid the overlaps that vanilla neato seems to produce. I’m also eager to hear any other comments/suggestions of any other kind!

Lastly, this recent presentation here introduces RxInfer.jl and all the associated ideas that I have mentioned here: https://www.youtube.com/watch?v=KuluqEzFtm8. There are even three videos with one of the authors of the above papers: https://www.youtube.com/watch?v=nuUWmwrz6cI and: https://www.youtube.com/watch?v=YNsUMgOQYpk and finally: https://www.youtube.com/watch?v=N7QSuazEEhE. I figure it’s best to give more context than less just now.

Many thanks again @steveroush and thank you for your time.

Fraser

4

Thank you for your interest in Graphviz.

If you are considering writing a new layout generator, then twopigen or osage are smaller examples that you could read and perhaps use as a template for your own algorithm.

Are you also thinking of writing a tikz driver? A driver has a bunch of entry points like “draw a polygon” “draw this piece of text” but does not know about constraints like “a is left of b” which is how I imagine tikz works. gvrender_core_svg.c would be a good intermediate example to look over.

5
6

In addition to what others have said, if you want to start hacking on this within Graphviz, I would start by copy-pasting an existing layout plugin:

$ git clone https://gitlab.com/graphviz/graphviz
$ cd graphviz
$ cp -r plugin/neato_layout plugin/foo_layout
$ # edit plugin/Makefile.am to add foo to the SUBDIRS
$ # edit configure.ac to add plugin/foo/Makefile to the AC_CONFIG_FILES
$ # edit stuff in plugin/foo to change names and describe your algorithm

Alternatively you could hack your layout into plugin/neato_layout/gvlayout_neato_layout.c as another option. Provided your new layout isn’t too specific to your use case, we’d probably be happy to accept it upstream if you want to contribute it.