Thanks for your comments! I enjoyed reading about STKs, which I had not heard about before. I know lots of people are interested in applying kernel methods to graphs, and it seems like a important area of research. As your post discusses, one of the problems with defining an algebraically valid graph kernel arises with Mercer's symmetric condition. As far as I know, defining a valid convolutional kernel on graphs is still an active area of research. Hamilton (2020) discusses this problem in the notes from his recent GRL seminar here:

https://cs.mcgill.ca/~wlh/comp766/files/chapter6_draft_mar29...

> I am convinced that using graphs to link semantics with structure is under-explored.

I hope you continue to explore this direction! Designing better semantic parsing algorithms seems really important for knowledge retrieval. I would love to learn more about natural language parsing in general (e.g. grounding, PCFGs, HMMs), this is one area I feel we could learn a lot from in programming languages research.

> 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.

Not very familiar with the Graphcore architecture, although their engineers have tried to explain it to me several times. I think this is going to be a co-design problem, but we can start to realize some progress by compiling to pure BLAS primitives. GPGPU-based approaches seem like a good start.