[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)