{"id":303,"date":"2020-05-26T20:14:37","date_gmt":"2020-05-26T20:14:37","guid":{"rendered":"http:\/\/localhost\/wordpress\/?p=303"},"modified":"2021-05-29T17:46:50","modified_gmt":"2021-05-29T17:46:50","slug":"introduction-to-graph-convolutional-networks","status":"publish","type":"post","link":"http:\/\/localhost\/wordpress\/introduction-to-graph-convolutional-networks\/","title":{"rendered":"Introduction to Graph Convolutional Networks"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t

Graph Convolutional Network (GCN) - High level<\/h2>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t

The study of graphs have received a lot of attention over the years due to their ability to represent data. From Dijkstra’s algorithm to determine the shortest path between two points, plotting genomes, and even social networks graphs can play an important part in visualizing data. This is where the study of Graph Convolution Networks comes in.\u00a0 An example can be showed as such:<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t<\/a>\n\t\t\t\t\t\t\t\t\t\t\t
Figure 1: a Facebook Friendship network. Color indicates the political viewpoint of each friend; 10% of these political stances are predicted by graph convolutional network, the rest were input as part of the training sequence<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t

An application of a Graph Convolution Network (GCN) can be shown as follows:<\/p>

Given a Facebook users friends history (i.e links, shares, relationships, and such), we can create an unstructured graph of how they are related (as shown on the left-hand side, color: gray)<\/p>

Using a GNC community clustering algorithm we can classify each person in the left-hand graph by their political stances.<\/p>

Other examples can range from fraud detection, computer vision and so much more! These GCN’s are very powerful for learning on graphs. Formally, a graph convolution\u00a0network<\/em>\u00a0(GCN)\u00a0<\/strong>operates of a given graph G = (V,E)\u00a0 where V represents the Vectors<\/em> and E represents the Edges.\u00a0<\/em><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t

Background: Graphs and Convolutions and Machine Learning!<\/h2>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t

Graphs:<\/h4>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t

In mathematics, a graph is essentially a structure of objects that are interconnected. As seen in figure 2 almost every graph has vertices and edges at minimum.\u00a0<\/p>

There are a wide range of graphs Null , Connected, Bipartite, Weighted, and Directed to name a few. Each of these graphs can be extremely useful for visualizing data.<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t

\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t<\/a>\n\t\t\t\t\t\t\t\t\t\t\t
Figure 2: A simple graph with six vertices and seven edges<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t

A down side to graphs are that comparing two graphs could be [katex] N^2[\/katex] time because we need to check every Node and vertices. Not only that the graph can grow exponentially based on how many edges a new vertices takes on.<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t

Convolutions<\/h4>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t<\/a>\n\t\t\t\t\t\t\t\t\t\t\t
Figure 3: the convolution of the function f(x) interacting with a pulse, g(x)<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t

Turning over to Convolutions, given two function\u00a0F(x)\u00a0<\/em> and\u00a0G(x)<\/em> a convolution is a mathematical operation that produces a different function that shows how\u00a0G(x)<\/em> and F(x)\u00a0<\/em>interact with each other. Figure 3 represents a one dimensional convolution of a sliding function (red) interacting with a static function (blue). It is given by the function [katex]f(x) * g(x) = \u00a0\\int^{+\\infty}_{-\\infty} f(y) – g(x -y) \\, dy[\/katex]<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t

Figure 4 shows the visualization of a two dimensional Convolution, which is commonly used in image processing and classification to reduce data size with minimal feature loss. We can combine the\u00a0 region of interest (dark blue) by using different kernel techniques<\/a>.This in turn allows us to change the image without huge data loss<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t

\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t
Figure 4: A convolution of a 4 x 4 image produces a 2 x 2 image<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t
#Load imports\nimport numpy as np\nimport cv2\nfrom matplotlib import pyplot as plt\nfrom scipy import ndimage\n\n# get grayscale image\nimage = cv2.imread("---image_location---", cv2.IMREAD_GRAYSCALE)\n\n# show image \nplt.imshow(image, cmap='gray', vmin=0, vmax=255)\n\n# define kernel \nkernel = (1\/9) * np.array([[1, 1, 1],\n                           [1, 1, 1],\n                           [1, 1, 1]])\n                           \n# apply kernel\nfiltered = cv2.filter2D(src=image, kernel=kernel, ddepth=-1)\n\n# show new image\nplt.imshow(filtered, cmap='gray', vmin=0, vmax=255) <\/code><\/pre>