Home Linear Algebra for Graph Convolutional Networks
Author: Elona Erez
Graphs are an important framework for many systems and applications in AI, such as social networks, recommendation systems, traffic systems, molecular search and more. One of the leading models for graphs in the literature is graph convolutional networks. One of the landmark paper for this model is “Semi-supervised Classification with Graph Convolutional Networks” by Thomas N. Kipf and Max Welling.
While reading this paper, I realized that I will need to read a bit more about linear algebra to fully understand some of the derivations. In this series of posts, I am going to explore the mathematical background, especially that related to linear algebra, required to grasp the central concepts of graph convolutional networks.
Let’s start with a very gentle introduction to graph theory.
In mathematics, a graph ? = (?,?) contains a set of nodes ? and a set of ? edges that connect the nodes. The easiest way to understand is by an example:
In this example, the set of nodes is: ? = {1,2,3,4,5}.
The set of edges is: ? = {?,?,?,?,?}.
Another way to represent an edge is by the nodes it connects, for example: ? = (1,5) ? = (2,5).
As we will see later, it is convenient to imagine the graph as representing different locations in a city, and the edges as tubes through which water can flow.
An example of a graph in everyday life is a road map:
In this map, the nodes are cities and the edges represent roads that connect different cities. The graph representing the map can be illustrated as below:
A graph can be directed and undirected. In the examples above, an edge does not have any particular direction. For the city map examples, that means that cars can travel in both directions of each road — both from New York to Boston and from Boston to New York. In contrast, we can have a directed graph. For the first example, a directed version of the graph is:
The arc (I will call a directed edge an arc, but there are also other common terminologies) is directed from node 1 to node 5. Therefore, we can stream water only from node 1 to 5, but not in the other direction. However, we have arcs between nodes 1 and 2 in both directions, we can stream water in both directions.
Another type of graph is a weighted graph. In a weighted graph, each edge has a weight associated with it. The weight may represent capacity, for example, the amount of water that can flow through a tube per unit time. The weight may also represent cost, for example, the cost of using the tube for streaming a certain amount of water. Of course, we may have 2 sets of weights (or more), where the first set represents the capacity and the second set represents the cost. In the following illustration we have a single weight for each edge. In general, weights can be also negative, but that would not normally make sense for capacity. In this example, 3 units of water can flow between node 1 and 5 per unit time.
Of course, a graph can be both directed and weighted.
There are other types or graphs you may be interested in — cyclic graphs and acyclic graphs, planar graphs and nonplanar graphs and more, but we won’t get into them just now, since we won’t need them for our derivations here.
In the next post, I will discuss more applications of graph theory and connections to AI.
I would like to extend my thanks to the following people for fruitful discussions: Efrat Ben-Zeev, Avidan Akerib, Daphna Idelson, Amir Gottlieb , and Samuel Lifsches.
