I'm a big fan of the smart replies in Allo and Inbox so this was a fun read. I did something similar in grad school where I and some other students manually labeled a handful of sentences and then used graph-based semi-supervised learning to label the rest for the purposes of using it as a training dataset. It would be neat to hear what technology they used for the graph-based learning; perhaps Cayley? We used Python's igraph at the time but it was pretty slow. It would also be interesting to try this in Neo4j.