Learning Graph Structure with a Finite-State Automaton Layer(arxiv.org)
arxiv.org
Learning Graph Structure with a Finite-State Automaton Layer
https://arxiv.org/abs/2007.04929
5 comments
Is a way to understand the general theme here as, "For the class of static analyses representable by ~datalog relations, we can increasingly infer them, with potential applications for verification + synthesis?"
I would say that’s becoming increasingly plausible, but it’s not exactly what the authors show in this paper. In order to translate from Datalog queries, you would need to show how to encode arbitrary propositional formulae as a graph reachability problem. This appears to be possible following Reps et al. [1], but is still far away from becoming a push-button solution. Here, they are proposing a new architecture which is capable of inferring abstract relations between program states (e.g. variables), trained on a synthetic dataset of pairwise relations, and empirically showing its generalization performance on those specific tasks.
This is a promising early result, but does not show how to encode arbitrary static analyses at runtime. The authors have related work (Shrivastava et al. [2]) applying few-shot learning to source code, which (just speculating) might be amenable to a graph representation, by accepting as input (1) a graph program and (2) static analysis / reachability query, and returning the answer (a la NLP question-answering, but for code). It might also be possible to synthesize new static analyses from a dataset of labeled examples. Maybe you can reach out to the authors to discuss their broader goals for this work?
[1]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61....
[2]: https://arxiv.org/pdf/2003.11768v1.pdf
This is a promising early result, but does not show how to encode arbitrary static analyses at runtime. The authors have related work (Shrivastava et al. [2]) applying few-shot learning to source code, which (just speculating) might be amenable to a graph representation, by accepting as input (1) a graph program and (2) static analysis / reachability query, and returning the answer (a la NLP question-answering, but for code). It might also be possible to synthesize new static analyses from a dataset of labeled examples. Maybe you can reach out to the authors to discuss their broader goals for this work?
[1]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61....
[2]: https://arxiv.org/pdf/2003.11768v1.pdf
This is in the subfield of "neural program synthesis" right? Or do they call it something else usually?
Yes, “program synthesis” or “program induction” are the broader topics, which span automata theory, type theory and (more recently) representation learning. Prior work has relied on classical algorithms like proof search, SMT solvers and learning automata. Recently there has been a lot of progress in applying statistical learning algorithms to program synthesis, as researchers began to realize it shares a lot in common with linear algebra and graph representation learning. I wrote a blog post about some of those connections in case you’re interested in learning more:
http://breandan.net/2020/06/30/graph-computation/
http://breandan.net/2020/06/30/graph-computation/
Thank you for a blog, very much enjoyed reading it!
By any chance do you know how Graphcore generates beautiful graph plots ? (seems like this are graph plots)
link: https://www.graphcore.ai/hs-fs/hubfs/Graphcore%20open%20sour...
By any chance do you know how Graphcore generates beautiful graph plots ? (seems like this are graph plots)
link: https://www.graphcore.ai/hs-fs/hubfs/Graphcore%20open%20sour...
