Graph Neural Networks – An Overview

Yeah, you probably right. I am always puzzled about how much math to include and how deep to go on an introductory article. Thanks for your feedback

I was, and still am, intrigued by the idea of Boltzmann machines, which form a complete graph between a number of "neurons". With the right weights they could be shaped into any architecture. They could be shaped into a fancy recurrent network, or a multi-layer linear network, or anything in between. Indeed, with the right training algorithm the computer could learn how to structure the "neurons" it is given. I don't think we know any such training algorithm though.

They're also not very efficient, because every "feed forward step" you would have to use a matrix that is N*N (where N is the number of neurons), which is a worst case scenario. Maybe with sparse matrices it could be reasonably efficient if most weights were zero. I don't think sparse matrices are used much in machine learning currently.

These are my thoughts as a machine learning novice.

There's been some work in this area. In practice, finding a good topology is hard, and graph or sparse matrix operations require a pretty significant level of sparsity before they're more efficient than just including every weight in a sense matrix and setting some parameters to zero.

Any DAG you choose is equivalent to a network with some number of dense layers with some of the weights zeroed, so you aren't losing any modeling capability by sticking with dense networks. The current trend of massively overparameterizing networks and training them for a long time in the zero error regime (so-called "double dip" error) exploits this idea a little. With sufficient regularization, you bias the network toward a _simple_ explanation -- one where most weights are near zero, effectively the same as having chosen an optimal topology from the beginning.

If you're talking about cyclic directed graphs, those are implemented in places too, but they're extremely finicky to get right. You start having to worry about a time component to any signal propagation, you have to worry about feedback loops and unbounded signals, they're harder to get to converge during training, and so on. Afaik there isn't a solid theoretical reason why you might want to add cycles since the layered approach can already handle arbitrary problems (not that we shouldn't keep investigating -- I'm sure some people know more than me on the topic, and I don't think there's any definitive proof that cycles are always worse either, so it seems like it might be worth investigating even from a practical point of view).

> therefore the layered topology must have some mathematical superiority

Isn't it just that backpropagation on the layered topology is relatively straightforward?

That's not to say you can't write a backpropagation on an arbitrary digraph, but as you get to more and more complex digraphs, things will get harder.

I could be wrong on this.

The vanishing gradient problem makes this hard. ResNets and LSTMs use additional connections to help with this (and ironically that makes them more graph like).

Spiking neural nets are a lot like these "sparse dags"

> At which NLP tasks are they state the art? The only one where they are really competitive is dependency parsing. (from my own disjonction of cases)

At tasks that actually involve graphs presumably. https://arxiv.org/pdf/1901.00596.pdf https://paperswithcode.com/task/graph-classification has a bunch of GNNs ranked #1

> Also were there any new real SOTA on any NLP tasks since last summer? I feel like accuracy progress has frozen..

That's pretty normal for winter/spring, it's not conference season.

> Also were there any new real SOTA on any NLP tasks since last summer? I feel like accuracy progress has frozen..

Just in the last week there are two papers which claim SOTA on different tasks.

Microsoft released Turing NLG (https://www.microsoft.com/en-us/research/blog/turing-nlg-a-1...) recently which claims SOTA on a couple tasks, it seems like the same transformer architecture, but with more layers and parameters, made feasible by training efficiency improvements. The biggest one seems to be partitioning how the model learns across different processes instead of replicating those states, which significantly improves communication, memory overhead, and training speed.

Deepmind released the Compressive Transformer (https://deepmind.com/blog/article/A_new_model_and_dataset_fo...) which claims SOTA on two other "long-range" benchmarks. My understanding of the improvement here is that instead of discarding older states, in the traditional attention layer, the compressive transformer learns which states to keep, and which states to remove.

I think these are two good examples of paper archetypes -- one where SOTA is achieved through more layers/training data/neurons (and the more interesting contribution is the improvements to model parallelism in training), and one where SOTA is achieved through a new/improved model architecture.

I wonder, for most industrial practitioners, how much either paper is useful though. The Microsoft paper helps for training billion parameter models, but most won't train a model that deep; the Deepmind paper helps for training models over very long sequences, but most people aren't using book-length sequences.*

* I remember reading somewhere that the attention mechanisms tend to only remember around 5 states (would love to see a source or study on this), which is pretty short, so would be interesting to try this model and see if the compressed transformer/attention mechanism can remember longer sequences.

Graph NNs aren't really used for SOTA NLP tasks.

On the other hand, larger and larger transformer networks are constantly improving.

Assuming you are in the Northern Hemisphere so "last summer" means Julyish, then Google's T5[1] and Microsoft Turing-NLG[2] come to mind.

I find keeping an eye on HuggingFace's models list[3] is useful for this.

[1] https://arxiv.org/abs/1910.10683

[2] https://www.microsoft.com/en-us/research/blog/turing-nlg-a-1...

[3] https://github.com/huggingface/transformers#model-architectu...

Can you please share an example? I am in genomics and looking to get closer to the drug chemistry.

Look into RDFs and Ontology w.r.t. NNs. A very rich (though unproductive) history.