[HN Gopher] Computation Graphs and Graph Computation
___________________________________________________________________
Computation Graphs and Graph Computation
Author : bmc7505
Score : 45 points
Date : 2020-07-18 02:20 UTC (1 days ago)
(HTM) web link (breandan.github.io)
(TXT) w3m dump (breandan.github.io)
| Kednicma wrote:
| This is a big post. I'll point out what is especially interesting
| in terms of equivalences.
|
| 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/
| bmc7505 wrote:
| Interesting! I was not aware of the connection to Chu spaces,
| will have a look into that! Algebraic topology seems to have a
| endless trove of many interesting dualities. I did find the
| connection between topological ordering and boolean matrix
| multiplication to be really interesting. I was taught a queue-
| based algorithm as an undergrad, so learning about this was a
| pleasant surprise.
| bmc7505 wrote:
| Hi HN, author here! This post discusses some research I and my
| colleagues at McGill have been working on recently, borrowing
| ideas from graph theory and linear algebra to model computation.
| If any of these topics interests you, feel free drop me an email
| at bre@ndan.co -- would love to get your feedback about GPGPU
| compilation, boolean function analysis, abstract rewriting
| systems or any of the topics discussed. Thanks!
| jix wrote:
| I haven't read everything, but it does contain a section about
| something I'm quite familiar with:
|
| 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).
| brzozowski wrote:
| Thanks for your feedback! I like the WL algorithm for its
| simplicity, but agree there are specific cases it does not
| handle well. It is meant to illustrate a simple message passing
| algorithm, and is not a particularly efficient implementation.
| Will clarify this point, thanks!
| Kinrany wrote:
| The article starts with details from the author's biography of
| dubious relevance, and there's no table of contents.
| bmc7505 wrote:
| Agreed, the biographical details are not super relevant would
| help to have a ToC. I have added one to the intro. Thanks for
| reading!
| goodmattg wrote:
| Intriguing post! Back in my undergrad days I wrote a course
| thesis on Syntactic Tree Kernels applied to the problem of
| determining duplicate question on Quora. Like you, I am convinced
| that using graphs to link semantics with structure is under-
| explored:
|
| 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.
___________________________________________________________________
(page generated 2020-07-19 23:00 UTC)