[efferifick]

I am really interested in GNN in the context of compilers.

* Predicting the color of a node in a graph, could be used for example speculative devirtualization.

* Predicting edges weight could give us a better estimate of hot basic blocks statically.

* Running performance experiments is as easy as running the benchmark and introducing some metric of performance which you can give back to the GNN to learn from.

Imagine also for debugging and IDEs. I haven't played with copilot, but I imagine that something like guessing the graph based on node labels and on some edges is feasible using GNN? This means that the IDE could try to match the name of your variables, the control flow, and the name of the function to other known functions and could potentially point out differences. Potentially giving us a way to fix logic errors, or better algos. E.g., "Mmm... it looks like you are implementing your own bubble sort from scratch. Would you like to click here and use <insert better sort>."

I am not an expert on GNN, but if anyone has resources for someone to learn more about the state of the art of GNNs (a link to a literature review or something similar) do let me know.

[davidatbu]

> I haven't played with copilot, but I imagine that something like guessing the graph based on node labels and on some edges is feasible using GNN?

Copilot is based on OpenAI Codex, which is based on GPT-3, which is a transformer model.

Although technically, transformers are mostly GNNs that are "fully connected" (in the graph theory sense), I don't think that supports your speculation here about how GNNs could be used for code analysis since the "tokens" that GPT-3 is trained on are not programming-language syntactic constructs, but sub-word units obtained from natural language (something like WordPiece).

I will say though, I am equally excited by the exact prospect you raised of using something like GNNs for code analysis.

My hunch is that if somebody can figure out a way to make training hierarchical/graph based neural networks very fast, we'll observe the same gains that we did with transformers. But hierarchical/graph based models don't lend themselves to efficient computation.

[legothief]

I'm also quite excited about that - there's existing research, quite a few papers that are using graph-based models for MLOnCode: https://proceedings.neurips.cc/paper/2021/file/c2937f3a1b3a1... https://arxiv.org/abs/2203.05181 https://arxiv.org/abs/2005.02161 https://arxiv.org/abs/2012.07023 https://arxiv.org/abs/2005.10636v2 https://arxiv.org/abs/2106.10918

Definitely check them out! There are also tools that were made available by some of the authors: https://github.com/google-research/python-graphs

[algo_trader]

Are these papers somehow "curated" or "recommended"?!

Unfortunately, GNNs are lagging LLMs in the code domain. Maybe because

a. LLMs and transformers rulezz OR b. there is far more source code than there are compiled code graphs

[davidatbu]

I wouldn't rule out the fact that transformers are very amenable to parallel computation as the reason

[davidatbu]

Thank you!! I've been looking to get my feet wet with SoTA research for MLONCode, so this is very helpful!

[refulgentis]

Are graph neural networks designed to solve graph problems like this, or are they a "graph problem"? Or both? :p

[efferifick]

Mmm... maybe I'm mistaken. Thanks for the opportunity to reflect a bit more about this. I was remembering this video [0] which talks about Graph Embeddings. In the video, the speaker talks specifically about node classification. Assuming the classes are target functions, this could potentially be used for speculative devirtualization.

Definitely not an expert, just excited to have more tools on which to work with graph data!

[0] Graph Embeddings - Neo4J. Talk by Alicia Frame. https://www.youtube.com/watch?v=oQPCxwmBiWo

[plonk]

I learned them as a generalisation of CNNs where the data is stored in any graph, CNNs being a special case where the graph has a grid structure. Convolutions spread information from nodes to their neighbours. It's just implemented differently because the data isn't a neat 4D array anymore.

In that way, GNNs solve graph problems, the same way CNNs solve image processing problems. Training the GNN is more of an optimisation problem.

Edit: maybe graph theory can help with training on very large graphs but I don't know enough about that.

[lmeyerov]

Yeps, that's a GCN, and probably the most popular GNN is indeed a RGCN :)

The transformer comment is interesting. They're very close, and in general, the tricks people use elsewhere are getting translated to GNNs: convolution, attention, ... . But scaling is still happening, so recent couple of years have gotten folks doing 1M-1B level, but not yet LLM scale yet. Critically, the scaling work is relatively recent -- good GPU impl, good samplers, etc -- and with a good trajectory.

We tracked GNNs for years but stayed away until heterogeneity + scaling started to get realistic for commercial workloads, and that's finally happening. Major credit to folks like deepmind, michael bronstein, early graphsage / jure, various individual researchers, and now aws+nvidia engineers for practical engineering evolutions here.

[MonkeyMalarky]

Coming from a position of knowing nothing about graph neural networks, this is the best description I've seen so far in this thread.

[jcims]

Somewhere in my HN history is this same question and I can't say I've got a conclusive answer. My partially confident takeaway is that GNNs describe the architecture of the neural network itself, much in the same way that convolutional or recurrent are terms used to describe other network architectures.

There are two confusing parts for me

1 - The words network and graph are nearly synonymous in this context, and IIRC most neural network architectures are actually graphs that fit some specific pattern. I don't know what makes a 'graph neural network' special (my guess is it has to do with how the layers relate but i don't know)

2 - I almost always see a mention of a graph-related use cases in the context of GNNs. I don't know if there is a fundamental reason for that or if it just so happens that people who have huge graphs worth applying ML to are actually just have really good intuition about how graphs can be leveraged and go that route.

[posterboy]

I have no idea to be honest but I think it relates to the idea of representing the computation in a reasonably comprehendable way.

Either that or networks that can solve specific problems on graph structures by more or less general and hence reusable methods. Which could go ways towards the former point, I guess, but that's also dealt eith elsewhere. Just give g-scholar a search and see

[legothief]

In my mind, GNNs are designed to solve graph problems, in the usual case, with message passing, that enables (I'd emphasise the aggregation step) to "do ML on graphs".

[pca006132]

> Potentially giving us a way to fix logic errors, or better algos. E.g., "Mmm... it looks like you are implementing your own bubble sort from scratch. Would you like to click here and use <insert better sort>."

I think this already exists in software engineering research, but iirc they were comparing against some code snippets gathered from other open source project or use language models instead of GNN.

[yobbo]

> "Mmm... it looks like you are implementing your own bubble sort from scratch. Would you like to click here and use <insert better sort>."

Theoretically, it should be possible. There might not exist demos of these sorts of networks yet.

[moonchild]

There was some interesting work done on using ML for autovectorisation. Pldi keynote from a year or two ago iirc.

[mhh__]

Facebook published a paper on using ML to generate PGO data statically.