“GRAPH CONVOLUTIONAL NETWORKS”. It is one of the most popular GNN

Last time I explained how GNN works. It gathers information from neighbors and aggregates them to predict classes we are interested in. Today, I would like to go deeper with one of the most popular GNN called “GRAPH CONVOLUTIONAL NETWORKS” or “GCN”(1). Let us start step by step.

1. Adjacency Matrix

As you know, a graph has edges or links among nodes. Therefore, a graph can be specified with an adjacency matrix A and node features H. A adjacency matrix is very useful to present the relationship among nodes. If a graph has a link from node “i” to node “j”, the element of A, whose row is “i” and column is “j” is “1”, otherwise “0”. It is shown in the chart below. If a node has a link to itself, diagonal elements are “1” in adjacency matrix.

2. Gather information from neighbors

Let us explain the chart below. 1. The node, which is red in the chart, gathers information from each neighbor. 2. The information is aggregated to update the node. The way for aggregation can be sum or average. 

As I said above, a graph can be specified with an adjacency matrix A and node features H or X. I introduce W as a matrix to show learnable weights and D is a matrix to show us the degree of A. It is noted that diagonal elements are “1” in adjacency matrix here. σ is a non linear function.

In GCN, the way to gather information is as follows (1).

It means that information from neighbors are weighted based on the degree of the sender (green one) and the receiver (red one) as well.  All information is aggregated to update the receiver (red one).

In the formula below, GCN is also considered more generally that the features of the neighborhood are directly aggregated with fixed weights (2).

“Cuv” is considered as the importance of node v to node u. It is a constant that directly depends on the entries in an adjacency matrix A.

That’s it! Hope you can understand how GCN works. In the next article, I would like to solve the problem with GCN. Stay tuned!

(1) SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS, Thomas N. Kipf & Max Welling, 22 Feb 2017

(2) Geometric Deep Learning Grids, Groups, Graphs, Geodesics, and Gauges, p79, Michael M. Bronstein, Joan Bruna, Taco Cohen, Petar Veličković, 4 May 2021

Notice: ToshiStats Co., Ltd. and I do not accept any responsibility or liability for loss or damage occasioned to any person or property through using materials, instructions, methods, algorithms or ideas contained herein, or acting or refraining from acting as a result of such use. ToshiStats Co., Ltd. and I expressly disclaim all implied warranties, including merchantability or fitness for any particular purpose. There will be no duty on ToshiStats Co., Ltd. and me to correct any errors or defects in the codes and the software.

Graph Neural Networks are very flexible to design models for data analysis

Last time, I introduced Graph Neural Networks (GNN) as a main model to analyze complex data. Let us see how GNN works in detail.

1. What Does Graph Data Look like?

Unlike tabular data, the graph has edges between nodes. It is very interesting because many things have inter relationship with each other, such as…

• Investors behavior are affected each other in financial markets
• Rumors are spread and impact people’s decisions in social network
• Consumers may like the products which are already popular in the market
• One marketing strategy affects the results of other marketing strategies in the company
• In the board game called “Go”, some part of results affect other parts of results on Go board

These structures are shown just like the graph below. It is based on the karate club data(1). Each node means each member in the club. The graph(2) shows us four groups in the club. There are edges between nodes and these structures are very important in analyzing data.

2. How can GNN models be trained?

Each node is expressed as vectors (example : [0 1 0 0 5]). It is called “node features” or just “features” in machine learning. When models are trained, each node takes the information from neighbors and is updated based on this information. Yes, it looks simple! One of the ways to take the info from neighbors is the “sum” of information from neighbors. Another is to take the average. We iterate these updates until the loss function can be converged.

It is noted that we can sum up or take the average in the same manner even if the structures of the graph are changed. This is why GNN is very flexible to design the models. 

3. How can the predictions from GNN models be obtained?

After training of models, we can obtain predictions based on the graph. In GNN, there are three kinds of predictions.

• node prediction : Each node should be classified according to labels. For example, in the Karate club above, each member should be classified as the member in one of the four teams shown in the chart above.
• graph prediction : Based on the whole structure of the graph, it should be classified. For example, a new antibiotic may be classified whether it works well or not for treatments against certain diseases.
• link prediction : When each node means each customer or each product, the edges between customers and products can mean the purchase in the past. If we can create better node features based on graph structures, recommendations can be provided to inform which products you may like more accurately.

Hope you can understand how GNN works well. It is very flexible to design. Next, I would like to explain what kind of GNN models are popular in the industries. Stay tuned!

(1) Wayne W. Zachary. An information flow model for conflict and fission in small groups. Journal of
anthropological research, pp. 452–473, 1977.

(2) SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS, 22 Feb 2017, Thomas N. Kipf & Max Welling

Notice: ToshiStats Co., Ltd. and I do not accept any responsibility or liability for loss or damage occasioned to any person or property through using materials, instructions, methods, algorithms or ideas contained herein, or acting or refraining from acting as a result of such use. ToshiStats Co., Ltd. and I expressly disclaim all implied warranties, including merchantability or fitness for any particular purpose. There will be no duty on ToshiStats Co., Ltd. and me to correct any errors or defects in the codes and the software.

Graph Neural Networks can be a game changer in Machine Learning!

Happy new year! As new year comes, I’m thinking about what to do about AI this year. After exploring various things, I decide to concentrate on “Graph Neural Networks” in 2022. I’ve heard the name “Graph Neural Networks” before, but since the success stories have been reported in several applications last year, I think it is the right time to work on it in 2022.

Graph is often represented by a diagram connecting dots, just like this.

Dots are called “nodes” and there are “edges” between nodes. They are very important in “Graph Neural Networks” or “GNN” in short.

These can be expressed intuitively with Graph. So they can be analysed by GNN.

• Social network
• Molecular structure of the drug
• Structure of the brain
• Transportation system
• Communications system

If you have a structure that emphasizes relationships between nodes or dots, you can express it in Graph and use GNN for analysis. Due to its complexity, GNN hasn’t appeared much as an AI application, but in last year, I think we’ve seen a lot of success results. It seems that the number of papers on GNN published is increasing steadily.

In August of last year, DeepMind and Google researchers released that they predicted the arrival time at the destination using Google Map data and improved the accuracy. The roads were graphed by segment and analyzed using “Graph Neural Networks”. The structure of the model itself seems to be unexpectedly simple. For details, please see 3.2 Model Architecture in the research paper (1).

There are many other successful cases. Especially in the field of drug discovery, it seems to be expected.

Theoretically, “Graph Neural Networks” is a fairly broad concept and seems to have various models. The theoretical framework is also deepening with the participation of leading researchers, and research is likely to accelerate further in 2022.

So, “Graph Neural Networks” is a very interesting to me. When I find good examples, I would like to update it here. Stay tuned!

１）ETA Prediction with Graph Neural Networks in Google Maps, 25 Aug 2021

Notice: ToshiStats Co., Ltd. and I do not accept any responsibility or liability for loss or damage occasioned to any person or property through using materials, instructions, methods, algorithms or ideas contained herein, or acting or refraining from acting as a result of such use. ToshiStats Co., Ltd. and I expressly disclaim all implied warranties, including merchantability or fitness for any particular purpose. There will be no duty on ToshiStats Co., Ltd. and me to correct any errors or defects in the codes and the software