{"id":18002,"date":"2018-10-12T10:41:49","date_gmt":"2018-10-12T14:41:49","guid":{"rendered":"https:\/\/www.crim.ca\/blogue\/deep-learning-applied-to-graphs-extraction-and-processing-of-graph-information-by-convolutional-neural-networks\/"},"modified":"2023-06-14T10:00:52","modified_gmt":"2023-06-14T14:00:52","slug":"deep-learning-applied-to-graphs-extraction-and-processing-of-graph-information-by-convolutional-neural-networks","status":"publish","type":"blogue","link":"https:\/\/www.crim.ca\/en\/blogue\/deep-learning-applied-to-graphs-extraction-and-processing-of-graph-information-by-convolutional-neural-networks\/","title":{"rendered":"Deep learning applied to graphs: Extraction and processing of graph information by convolutional neural networks"},"content":{"rendered":"
\n

Graphs \u2014 frequently used in the fields of transport, telecommunication, biology, sociology and others \u2014 allow, in the simplest cases, an exploration of data and their connectivity from a simple visual analysis. However, in most applications, for example in the classic case of the representation of social networks, the graphs obtained contain an immense quantity of nodes and connexions between them. When that\u2019s the case, simple visual analyzes can quickly become complex. The use of machine learning on massive data graphs is a solution for numerous analytical and predictive approaches such as clustering for community detection, social link inference, vertex classification without a label, etc.<\/p>\n

Deep learning is inspired by the functioning and architecture of brain systems: it uses artificial neural networks capable of solving complex problems with training. Deep learning seeks to learn through an algorithm composed of various layers of artificial neurons. The higher the number, the more the algorithm can handle with complex problems. In the context of large data volume processing, the use of deep learning and more specifically convolutional neural networks seems to be appropriate. Indeed, unlike multilayer perceptrons, convolutional neural networks limit the number of connections between neurons from one layer to another, which has the advantage of reducing the number of parameters to be learned.<\/p>\n

Recent research is concerned with the application of convolutional neural networks to graphs. Convolutional neural networks are generally used for processing data defined in a Euclidean space (finite dimensional vector space) such as images structured on a regular grid formed by ordered pixels. However, graphs have no set structure or order allowing them to be processed in this way by convolutional neural networks.<\/p>\n

A recent method called \u201cDeep Graph Convolutional Neural Network\u201d (DGCNN) proposed by M.Zhang et al. (2018) [1] exposes a new architecture of convolutional neural networks for graph processing.<\/p>\n

\n
\n
\"\"<\/div>\n<\/div>
DGCNN Architecture [1]<\/figcaption><\/figure>\n

This new architecture proposes the addition of two steps (graph convolutions and Sortpooling) to allow graphs to be processed by traditional convolutional neural networks [1].<\/p>\n

Graph convolution layers<\/h2>\n

Weisfeiler-Lehman Subtree kernel :<\/h3>\n

The extraction of information from the DGCNN method graphs is inspired by the Weisfeiler-Lehman subtree kernel method (WL)[2]. This method is a subroutine aimed at extracting features from sub-trees at several scales for graph classification. Its operation is determined as follows:<\/p>\n

\n
\n
\"\"<\/div>\n<\/div>
Subtree kernel Weisfeiler-Lehman [2]<\/figcaption><\/figure>\n

The basic idea of WL is to concatenate the color of a vertex with the colors of its neighbors at 1 jump thus contenance the signature WL of the vertex (b), then to sort the signature strings lexicographically to attribute new colors \u00a9. Vertices with the same signature are given the same new color (d). The procedure is iterated until the colors converge or reach a maximum iteration h. In the end, vertices with the same converged color thus share the same structural role in the graph and are no longer distinguished. WL is used to check the isomorphism of graphs, because if two graphs are isomorphic, they will have the same set of WL colors at each iteration. The core of the WL subtree uses this idea to measure the similarity between two graphs G and G\u2019: after iteration, the similarity is determined by the calculation of the kernel function (e)[2].<\/p>\n

The DGCNN method differs from of WL. In fact, it doesn\u2019t use the WL sub-tree method as such but uses a soft WL version. In this method, the kernel function isn\u2019t calculated and the use of colors is not the same: the DGCNN method concatenates the colors obtained in the form of a tensor\u00a0Zt\u00a0<\/em>(with\u00a0t = 1, .., h<\/em>) horizontally in a tensor\u00a0Z1: h<\/em>\u00a0(h being the number of iteration \/ convolution performed) [1].<\/p>\n

SortPooling<\/h3>\n

The major innovation of the DGCNN method is a new layer named SortPooling. SortPooling takes as input the characteristics of unordered vertices of a graph from the convolutions of graphs. Then, instead of summarizing the features of the vertices (causing a loss of information) as traditional pooling layers do, SortPooling classifies them in a consistent order and produces a sorted graph representation with a fixed size, so that traditional convolutional neural networks can read the vertices in a coherent order and be trained on this representation.<\/p>\n

Therefore, the main function of the SortPooling layer is to sort feature descriptors, each representing a vertex, in a coherent order, before feeding them into convolutional and dense layers of a single dimension. For the classification of images, pixels are naturally arranged following their spatial order, whereas to classify text, the alphabetical order is used to sort the words. For graphs, the SortPooling layer classifies the vertices according to their structural role in the graph as established by the WL subtree kernel method.<\/p>\n

Formally, the outputs of the convolutional layers of the\u00a0Zt<\/em>\u00a0graph are used to sort the vertices. The layer of SortPooling takes as input a tensor\u00a0Z1: h<\/em>\u00a0of size\u00a0\ud835\udc5b * \u03a3\ud835\udc50\ud835\udc61<\/em>, where each line is a vertex feature descriptor and each column is a feature channel. The output of SortPooling is a tensor \ud835\udc58 * \u03a3\ud835\udc50\ud835\udc61, where k is an integer to define. In the SortPooling layer, the input\u00a0Z1: h<\/em>\u00a0is first sorted by line according to\u00a0Zh<\/em>.<\/p>\n

More precisely, a coherent order is imposed on the vertices of the graphs, which makes it possible to form traditional neural networks on the representations of sorted graphs. The order of vertices based on\u00a0Zh<\/em>\u00a0is calculated first by sorting the vertices using the last channel of\u00a0Zh<\/em>\u00a0in descending order. Such an order is similar to the lexicographic order. The SortPooling layers acts as a bridge between graph convolution layers and traditional neural network layers by backpropagating loss gradients and thus integrating graph representation and learning into one end-to-end architecture [1].<\/p>\n

DGCNN in practice<\/h3>\n

Detailed information for using the DGCNN algorithm is on the authors\u2019\u00a0<\/em>Git<\/em><\/a>.<\/em><\/p>\n

Non Input dataset<\/h3>\n

The input data of the DGCNN method must have a specific format. Several steps are needed in order to obtain the appropriately formatted data. The datasets tested by the authors (available on the\u00a0platform<\/a>\u00a0of the University of Dortmund) are reference datasets suitable for graph kernel technics. Datasets can be described by several text files: firstly, the obligatory text files for the continuation of method where n = total number of nodes, m = total number of edges and N = number of graphs :<\/p>\n

(1) _A.txt (m rows) fragmented adjacency matrix (diagonal block) for all graphs, each row corresponds to (row, column) resp. (node_id, node_id)<\/p>\n

(2) _graph_indicator.txt (n rows) column vector of graph identifiers for all nodes of all graphs, the value in the\u00a0i-<\/em>th line is the graph_id of the node with node_id\u00a0i<\/em><\/p>\n

(3) _graph_labels.txt (N rows) class labels for all graphs in the dataset, the value in the\u00a0i<\/em>-th row is the graph class label with graph_id\u00a0i<\/em><\/p>\n

(4) _node_labels.txt (n rows) column vector of the node labels, the value in the\u00a0i<\/em>-th line is the node with node_id\u00a0i<\/em><\/p>\n

Then the optional text files:
\n(5) _edge_labels.txt (m lines) labels for the edges in _A.txt<\/p>\n

(6) _edge_attributes.txt (m lines) attributes for the edges in _A.txt<\/p>\n

(7) _node_attributes.txt (n rows) node attribute matrix, the comma separated values in the i-th row are the attribute vector of the node with node_id\u00a0i<\/em><\/p>\n

(8) _graph_attributes.txt (N rows) the regression values for all the charts in the dataset, the value in the\u00a0i<\/em>-th row is the graph attribute with graph_id\u00a0i<\/em><\/p>\n

The data contained in these files are only of numeric type: more precisely, the values can either be discrete or continuous. The data contained in these files are not directly usable by the DGCNN algorithm. The algorithm requires them to be transformed into a final single text file organized as follows:<\/p>\n

N
\nn l
\nt m d<\/em><\/p>\n

Where\u00a0N<\/em>\u00a0is the number of graphs,\u00a0n<\/em>\u00a0is the number of nodes per graph,\u00a0l<\/em>\u00a0is the label of the graph,\u00a0t<\/em>\u00a0is the label of the current node,\u00a0m<\/em>\u00a0is the number of neighboring node of the current node (followed by the labels of each of these neighboring nodes) and finally\u00a0d<\/em>\u00a0are the features of the current node (not mandatory). This transformation also includes generation of ten training samples and ten other test samples (each sample being a text file).<\/p>\n

Launch of DGCNN algorithm<\/h3>\n
\n
\n