[HN Gopher] Learning Graph Structure with a Finite-State Automat... ___________________________________________________________________ Learning Graph Structure with a Finite-State Automaton Layer Author : brzozowski Score : 67 points Date : 2020-07-18 15:04 UTC (7 hours ago) (HTM) web link (arxiv.org) (TXT) w3m dump (arxiv.org) | ilaksh wrote: | This is in the subfield of "neural program synthesis" right? Or | do they call it something else usually? | brzozowski wrote: | 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/ | lmeyerov wrote: | 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?" | brzozowski wrote: | 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 ___________________________________________________________________ (page generated 2020-07-18 23:00 UTC)