Computation Graphs and Graph Computation

I found the frequent self-quotes odd and the self-congratulatory introduction more odd. An example of the lack of target audience would be the section “what are graphs?” It starts with a paragraph which seems to be for someone who has never heard of graphs (yet it doesn’t actually define what a graph is, but maybe that’s because there’s so much variety in what different things may be graphs). It also calls graphs “data structures” which I don’t think I would agree with. It’s then followed by a big list of links and then a paragraph referencing Kotlin∇ and talking about trees and such even though the previous paragraph seems to be for someone who doesn’t know what a graph is.

I found other sections weird. E.g. the author seems to think that it is important to treat a matrix as a function between vector spaces but somehow misses the main point (this function must be linear and the numbers in a matrix are in some sense unimportant because they are relative to some basis). Then there’s a section about raising matrices to a power except when you look at it you realise it’s actually a product of different matrices and actually the topic just changed halfway through the paragraph.

The “matrix multiplications” in the section on data flow graphs don’t make sense to me, even with the random extra rules given above (the third entry in S' the second row should be 5, but this causes the next row to not have the idempotence property the author wants). It also seems to be confusing matrices with manipulating random numbers in a grid.

I don’t want to be overly negative. There’s probably some good stuff in here but at the moment it just appears to be a dump of the author’s notes and thoughts.

The article says "We compute the hashcode of the entire graph by hashing the multiset of WL labels. With one round, we’re just comparing the degree histogram. The more rounds we add, the more likely we are to detect a symmetry-breaker:", which is not correct.

Repeatedly re-labeling a graph by assigning a unique label to each unique neighborhood histogram, until the corresponding partition reaches a fixpoint would compute the one-dimensional Weisfeiler-Lehman refinement. But there are many non-isomorphic graphs that you cannot tell apart with this! It cannot tell apart any two regular graphs of the same size and degree, and you can easily run into those in practice.

Even if the code would repeat this process until a fixpoint is reached, instead of hoping that 10 iterations suffice, non-isomorphic graphs that result in the same WL partition means that "The more rounds we add, the more likely we are to detect a symmetry-breaker" doesn't hold.

There are also more efficient ways of computing this.

Now apart from one-dimensional WL refinement, where you compute a label from the neighborhood of individual vertices, there is also k-dimensional WL refinement, which very roughly speaking looks at all length k sequences of vertices and computes statistics for those. Here it is true that as k reaches |V| you will be able to tell apart any two non-isomorphic graphs, but only because if k=|V| you're trying all permutations! There is no fixed k that will tell apart any two graphs.

If you want to perform graph isomorphism tests in practice, I'd recommend Traces: http://pallini.di.uniroma1.it/

It combines two-dimensional WL refinement with a recursive search to tell apart all graphs, while using computational group theory algorithms to efficiently prune the search space for graphs with many symmetries. It is very efficient in practice.

It is described in https://arxiv.org/abs/0804.4881 (also linked from the website) and also has references for everything I wrote (modulo any mistakes I made while summarizing).

A square matrix on the Booleans is indeed also equivalent to a directed graph, as explained. It is also equivalent to a Chu space [0], specifically a sort of unitary Chu transformation.

We can specialize slightly. Let our square matrices be upper triangular; that is, let the lower triangle not including the diagonal be all 0/false. Then the corresponding graph is a DAG. (Apologies if this was in the article; I saw hints of it, but never the direct statement!) The corresponding Chu space has poset structure. These three facts are all related by fourth fact that the matrix's rows are labels for a topological sorting of the DAG, and the fifth fact that DAGs are equivalent to posets; we obtain a sixth fact that posets are equivalent to upper triangular Boolean matrices.

[0] http://chu.stanford.edu/

From that experience, one thing I would consider adding to your system is physical units. I independently discovered that physics units (Ohms, inerita, etc.) can be described as a vector. The other thing that is missing is out there and would be a boon is a real-time element for design. So many of the UIs are blocky in their design, meaning you sketch for a while, then press a large, heavy compile button, and wait for your results... To counteract this frustration, I have been undertaking experiments in real-time compiling. Please contact me if you're looking or a co-conspirator! I have been conceiving and part-time developing an environment where you can model systems continuously in real-time (or faster). Each time you make a change, it runs a number of tests and in fact, your changes don't have to be "complete." The system can iterate in the direction you send it and converge to your spec.

https://github.com/goodmattg/quora_kaggle

https://goodmattg.github.io/articles/2017-09/Syntactic-Tree-...

Further, as someone who came out of the the graph signal processing world (Ribeiro, Gama, et. al.), and with recent experience in types and functional programming (Pierce, etc.), I too admire the beauty of using types and graphs, but as you note, hardware implementation is a fundamental constraint to production. Perhaps the IPU units from Graphcore are a move towards this? I could use clarification on your points regarding next steps in low-level languages and hardware.

> Graphs are not only useful as cognitive aides, but are suitable data structures for a wide variety of tasks, particularly on modern parallel processing hardware.

I hope you mean by parallel processing, on a single machine. Reasoning on distributed graphs are difficult to do. The semantic we community could talk for days about what doesn't work.

> Sets: datasets, multisets, posets, alphabets

I guess by alphabets you mean dictionaries.

When you talk about types as graphs I guess you mean nested Objects with collection attributes/types

Where I agree with you is that graphs feel more natural than other structures because our brain is a gigantic graph of neurons.

I don't agree that the web is a directed graph. Not even the semantic web because of a lack of data quality, ridiculous ontologies, and a massive amount of parrtaly duplicating the same instances.

I wouldn't include formula or code parsing because in such cases they are just a means to an end.

What I would include on the other hand are execution plans of data bases which are used for query optimization. You might want to talk here to someone at Oracle.

That all being said, I'd like to reiterate on talking to the semantic web community. Maybe start networking at the ISWC conference first. I always dreamt of every ody's personal knowledge graph where explicit data is linked through everybody's individual ontology into something that is particularly understandable for the creator of the specific ontology.

They definitely need someone with a different perspective. The vuys from Cambridge Semantics are quite good.

The author boasted that he made some correct predictions about certain events such as Microsoft acquiring GitHub in 2018. Well I bet he made other predictions too in the past that didn't come true, but they didn't get any mention. Hindsight bias is a real thing.

Idea for next article: explainer of human cognitive biases (https://en.wikipedia.org/wiki/List_of_cognitive_biases)

[Futamura Projections]: https://en.wikipedia.org/wiki/Partial_evaluation#Futamura_pr...

https://www.cs.utexas.edu/~pingali/CS395T/2009fa/papers/ferr....

Like, I'm pretty sure writing a generic "differential function" is one of the first things you teach to undergrads taking a LISP class - isn't "differential programming" as mentioned here just the same concept baked in PLs ?