The General Review of Graph Neural Network
Yingbo Li, AI Team
Over the past few years, algorithms of deep learning applied on the graph-structured data have been extensively researched. At the same time, many of them have also been used in industrial applications. Compared to the traditional neural network, the Graph Neural Network (GNN) can process large-scale data using its graph structure, including both the homogeneous graph and the heterogeneous graph, conduct the node recommendation, edge recommendation and the embedding generation.
Deep learning has been the most significant fundamental technology and is changing all the domains of technologies and industries that it touches. The booming of deep learning originated from the success of image classification by the algorithm, AlexNet. Since AlexNet, deep learning has been extensively applied in the research and industrial applications of image classification, image object recognition, machine translation, and time series prediction. In addition, deep learning is used to learn the embeddings of images, text and any other data source to reveal the internal relations and representations of multiple kinds of information. Consequently, researchers often use the embeddings to build recommendation and retrieval systems for text and images.
Another popular technology, Knowledge Graph (KG) was also booming in the past years. KGis composed of nodes and edges between them in the form of relational triplets. KG was originally used in the research of Web Semantics, and coined by Google in 2012. The currentpopular KG databases include Cyc, OpenCyc, Freebase, Wikidata, DBpedia, Yago, Google’s Knowledge Graph, Microsoft’s Satori and Facebook Social Graph. For example, Google’s Knowledge Graph contains 570 million nodes and 35,000 edge types. Since Facebook connects people, the personal information and interests are the nodes of Facebook Social Graph, and different people with the same information and interests are associated together. Facebook Social Graph is also enhanced by Wikipedia information. With the development of years, KG has been commonly applying in the applications of question answering, recommendation systems, and information retrieval. In the recommendation system based on KG, the embedding approach and path approach are the most popular. The embedding based solution, reserving graph structure of KG, normally embeds nodes and edges into vector spaces and then recommends by the similarity to the query. While the path-based approach depends on hand-designed graph edges and uses the meta-path feature to recommend for the query.
As a typical application of the deep learning on graph structured data, Graph Neural Network(GNN), has been widely used in the embedding learning to build the recommendation system \cite{demb1} \cite{demb2}. The successful algorithms GNN algorithms for node classification, edge predication and embedding learning, include Graph Convolutional Network (GCN), Relational Graph Convolutional Networks (R-GCNs), Graph Attention Network (GAT), Graphsage, and Pinsage. GCN is one of the most successful pioneer algorithms in GNN, which aggregates the information from neighborhood nodes into the target node by approximating the graph Laplacian. Compared to GCN, which is designed for the homogeneous graph, R-GCNs can work for the heterogeneous graph with multiple kinds of nodes with multiple features. In GAT the contributions of neighborhood nodes to the target node are different because of applying attention mechanism by exploiting the graph structure. Graphsage for homogeneous graphs is different from GCN because the contributing neighborhood nodes are subsampled neighborhood nodes with a prefixed size when updating the information of the target node by mean, sum or maxpooling aggregator. While Pinsage for heterogeneous graphs develops the following aspects compared to Graphsage: on-the-fly convolutions, producer-consumer minibatch construction, efficient MapReduce inference and the neighbor subsumpling by random walk. However, Pinsage only has the capability to generate the embedding of one kind of node in the bipartite heterogeneous graph, while ignores the other kind of nodes.
We will make a thorough comparison and study to above algorithms in the future articles.
