YOU MUST EAT THIS GRAPH NEWS, GRAPH OMAKASE. 4weeks september

Transformers Meet Directed Graphs

[https://arxiv.org/pdf/2302.00049.pdf]

It is safe to say that we are living in the era of transformers, and many places are utilizing transformers regardless of data type. However, it is exceptionally difficult to use in graph data.

I think the reasons are 1. isomorphism 2. topology type. In this paper, we consider the above two as limitations and apply a new PE (Positional Encoding) method to solve them. We propose a PE idea that can apply directionality to the existing Laplacian matrix by borrowing the idea of Magnetic Laplacian, which is a PE suitable for directed graphs.

Of course, the performance is better than other PEs, but the best way to look at it is to read the narrative from why the Transformer architecture fails on poisonous graphs, to the various PEs and topologies to overcome it, to the main reasons for the performance improvement.

These narratives are written in the appendix of the paper, so you can enjoy the paper more by reading the appendix with the perspective of “why?” after reading the main body of the paper.

A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware

[https://arxiv.org/pdf/2306.14052.pdf]

If you have deepened your thinking about graph modeling and designed graph deep learning accordingly, and then encountered a barrier to performance improvement, this paper will be completely helpful. I strongly recommend it to those who are confused about where to start when improving the performance of graph deep learning.

It is divided into three categories: 1. Algorithm 2. Commercial-off-the-Shelf (COTS) 3. Customized Hardware, so it is a very well-written paper in terms of guidance that you can think of it as a dinner plate of graph omakase menu because you can proceed with meta-analysis of the current situation of Omakase subscribers and follow the methodology accordingly. If you are a GNN beginner, I think it is a paper that you can print and leave and read.

Community detection with node attributes in multilayer networks

[https://www.nature.com/articles/s41598-020-72626-y]

Community detection algorithms. When you study network science, you come across a lot of algorithms, and I used to think it was the most practical of them all.

I said “practical” in the past tense at above sentence because I’ve encountered a number of limitations, just to name three: 1. It’s difficult to explain the results to clients. 2. difficult to apply to large amounts of data 3. it is difficult to apply node and edge attributes. Collectively, they are difficult to apply to business and products.

In this post, I will try to compensate for the third of the above three limitations, the difficulty of applying node characteristics, by incorporating an introduction to EM(expectation maximization) into the algorithm. Simply put, there is one parameter to balance the graph topology and graph characteristics. You can think of it as using EM to optimize this parameter.

The experimental objective is ambiguous, but in the end the performance is good. The performance aspect of course plays an important role in proving the excellence of the paper, but from my point of view, when evaluating the results of an algorithm called community detection, there are three things that should be evaluated: how the partitioning is evaluated, how the results change depending on the hyper-parameter, and how other theories are applied to community detection.

This paper scratches the surface of 1. Difficulty explaining results to customers and 3. Difficulty applying node and edge characteristics, which I have always regretted. I recommend you to read it if you have similar thoughts as me.

Amazon at WSDM: The future of graph neural networks

[https://www.amazon.science/blog/amazon-at-wsdm-the-future-of-graph-neural-networks]

There are two parts: how GNNs are represented in vector space and how graph modeling affects GNN performance. I liked the latter of these two chapters, the GNN performance and graph modeling correlation, because it clarifies the importance of graph modeling, which has been emphasized repeatedly in the past, with the following rationales.

1.GNN models that can tolerate variations in how the underlying data is modeled will go a long way toward reducing the effort required to develop successful GNN-based approaches. 2.For domains for which there are multiple ways to model the underlying data via a graph, it often takes a lot of trial and error to develop successful GNN-based approaches because we need to consider the interplay between graph and GNN models.

With data driven vs. model driven approaches being a hot topic these days, you could say that what I’m talking about in the former, data driven, is written from a graph perspective. However, unlike other data perspectives, you have to design the data topology yourself, so planning on how and what to design based on is more important than other data. After all, the weights are updated based on the topology.

If you look at the title of this post, you can see that it is The future of graph neural networks. It is difficult to predict the future, but I think it is possible to infer from the experience and wisdom of people who have been in the field for a long time. I hope you will accept the perspective of the author, who is a guru in this field, and introduce it to Omakase subscribers.