JOURNAL OF LA A Comprehensive Survey on Graph Neural …

1 JOURNAL OF LATEX CLASS FILES, VOL. XX, NO. XX, AUGUST 20191A Comprehensive Survey on Graph NeuralNetworksZonghan Wu, Shirui Pan,Member, IEEE, Fengwen Chen, Guodong Long,Chengqi Zhang,Senior Member, IEEE, Philip S. Yu,Fellow, IEEEA bstract Deep learning has revolutionized many machinelearning tasks in recent years, ranging from image classificationand video processing to speech recognition and natural languageunderstanding. The data in these tasks are typically representedin the Euclidean space. However, there is an increasing numberof applications where data are generated from non-Euclidean do-mains and are represented as graphs with complex relationshipsand interdependency between objects. The complexity of graphdata has imposed significant challenges on existing machinelearning algorithms.

2 Recently, many studies on extending deeplearning approaches for Graph data have emerged. In this Survey ,we provide a Comprehensive overview of Graph Neural networks(GNNs) in data mining and machine learning fields. We proposea new taxonomy to divide the state-of-the-art Graph neuralnetworks into four categories, namely recurrent Graph neuralnetworks, convolutional Graph Neural networks, Graph autoen-coders, and spatial-temporal Graph Neural networks. We furtherdiscuss the applications of Graph Neural networks across variousdomains and summarize the open source codes, benchmark datasets, and model evaluation of Graph Neural networks. Finally,we propose potential research directions in this rapidly Terms Deep Learning, Graph Neural networks, graphconvolutional networks, Graph representation learning, graphautoencoder, network embeddingI.

3 INTRODUCTIONTHE recent success of Neural networks has boosted re-search on pattern recognition and data mining. Manymachine learning tasks such as object detection [1], [2],machine translation [3], [4], and speech recognition [5], whichonce heavily relied on handcrafted feature engineering toextract informative feature sets, has recently been revolution-ized by various end-to-end deep learning paradigms, , convolutional Neural networks (CNNs) [6], recurrent neuralnetworks (RNNs) [7], and autoencoders [8]. The success ofdeep learning in many domains is partially attributed to therapidly developing computational resources ( , GPU), theavailability of big training data , and the effectiveness of deeplearning to extract latent representations from Euclidean data ( , images, text, and videos).

4 Taking image data as anZ. Wu, F. Chen, G. Long, C. Zhang are with Centre for Artificial Intelli-gence, FEIT, University of Technology Sydney, NSW 2007, Australia (E-mail: Pan is with Faculty of Information Technology, Monash University,Clayton, VIC 3800, Australia (Email: S. Yu is with Department of Computer Science, University of Illinois atChicago, Chicago, IL 60607-7053, USA (Email: author: Shirui received Dec xx, 2018; revised Dec xx, , we can represent an image as a regular grid inthe Euclidean space. A convolutional Neural network (CNN)is able to exploit the shift-invariance, local connectivity, andcompositionality of image data [9]. As a result, CNNs canextract local meaningful features that are shared with the entiredata sets for various image deep learning effectively captures hidden patterns ofEuclidean data , there is an increasing number of applicationswhere data are represented in the form of graphs.)))

5 For ex-amples, in e-commence, a Graph -based learning system canexploit the interactions between users and products to makehighly accurate recommendations. In chemistry, moleculesare modeled as graphs, and their bioactivity needs to beidentified for drug discovery. In a citation network , papersare linked to each other via citationships and they need tobe categorized into different groups. The complexity of graphdata has imposed significant challenges on existing machinelearning algorithms. As graphs can be irregular, a Graph mayhave a variable size of unordered nodes, and nodes from agraph may have a different number of neighbors, resultingin some important operations ( , convolutions) being easyto compute in the image domain, but difficult to apply tothe Graph domain.

6 Furthermore, a core assumption of existingmachine learning algorithms is that instances are independentof each other. This assumption no longer holds for Graph databecause each instance (node) is related to others by links ofvarious types, such as citations, friendships, and , there is increasing interest in extending deeplearning approaches for Graph data . Motivated by CNNs,RNNs, and autoencoders from deep learning, new general-izations and definitions of important operations have beenrapidly developed over the past few years to handle the com-plexity of Graph data . For example, a Graph convolution canbe generalized from a 2D convolution. As illustrated in Figure1, an image can be considered as a special case of graphswhere pixels are connected by adjacent pixels.

7 Similar to 2 Dconvolution, one may perform Graph convolutions by takingthe weighted average of a node s neighborhood are a limited number of existing reviews on the topicof Graph Neural networks (GNNs). Using the termgeometricdeep learning, Bronstein et al. [9] give an overview of deeplearning methods in the non-Euclidean domain, includinggraphs and manifolds. Although it is the first review on GNNs,this Survey mainly reviews convolutional GNNs. Hamiltonet al. [10] cover a limited number of GNNs with a focuson addressing the problem of network embedding. Battagliaet al. [11] positiongraph networksas the building [ ] 4 Dec 2019 JOURNAL OF LATEX CLASS FILES, VOL. XX, NO. XX, AUGUST 20192(a) 2D Convolution.

8 Analogousto a Graph , each pixel in an imageis taken as a node where neigh-bors are determined by the filtersize. The 2D convolution takesthe weighted average of pixel val-ues of the red node along withits neighbors. The neighbors of anode are ordered and have a fixedsize.(b) Graph Convolution. To get ahidden representation of the rednode, one simple solution of thegraph convolutional operation isto take the average value of thenode features of the red nodealong with its neighbors. Differ-ent from image data , the neigh-bors of a node are unordered andvariable in 1: 2D Convolution vs. Graph learning from relational data , reviewing part of GNNsunder a unified framework.

9 Lee et al. [12] conduct a partialsurvey of GNNs which apply different attention summary, existing surveys only include some of the GNNsand examine a limited number of works, thereby missingthe most recent development of GNNs. Our Survey providesa Comprehensive overview of GNNs, for both interested re-searchers who want to enter this rapidly developing field andexperts who would like to compare GNN models. To cover abroader range of methods, this Survey considers GNNs as alldeep learning approaches for Graph contributionsOur paper makes notable contributionssummarized as follows: New taxonomyWe propose a new taxonomy of graphneural networks. Graph Neural networks are categorizedinto four groups: recurrent Graph Neural networks, convo-lutional Graph Neural networks, Graph autoencoders, andspatial-temporal Graph Neural networks.

10 Comprehensive reviewWe provide the most compre-hensive overview of modern deep learning techniques forgraph data . For each type of Graph Neural network , weprovide detailed descriptions on representative models,make the necessary comparison, and summarise the cor-responding algorithms. Abundant resourcesWe collect abundant resources ongraph Neural networks, including state-of-the-art models,benchmark data sets, open-source codes, and practicalapplications. This Survey can be used as a hands-on guidefor understanding, using, and developing different deeplearning approaches for various real-life applications. Future directionsWe discuss theoretical aspects ofgraph Neural networks, analyze the limitations of exist-ing methods, and suggest four possible future researchdirections in terms of model depth, scalability trade-off,heterogeneity, and of our surveyThe rest of this Survey isorganized as follows.