Overview of “Graph Neural Networks: Foundations, Frontiers, and Applications”

Introduction

We will provide an overview of “Graph Neural Networks: Foundations, Frontiers, and Applications” published by Springer in 2022.

Introduction

1. Representation Learning: This chapter first explains what representation learning is and why it is necessary. Among the various methods of learning representations, this chapter focuses on deep learning methods. Deep learning methods are methods formed by the composition of multiple nonlinear transformations with the aim of producing more abstract and ultimately more useful representations. We summarize representation learning techniques in different domains, focusing on unique challenges and models for different data types such as images, natural language, audio signals, and networks. Finally, I will summarize this chapter.

2. Graph Representation Learning: Graph Representation Learning aims to assign nodes in a graph to low-dimensional representations, effectively preserving the graph structure. Recently, significant progress has been made towards this new graph analysis paradigm. In this chapter, we will first summarize the motivation for learning graph representations. Then, we systematically provide a comprehensive overview of numerous graph representation learning methods, mainly covering traditional graph representation learning, modern graph representation learning, and graph neural networks.

3. Graph Neural Networks: Deep Learning has become one of the most dominant approaches in Ar- tificial Intelligence research today. Although conventional deep learning techniques have achieved huge successes on Euclidean data such as images, or sequence data such as text, there are many applications that are naturally or best represented with a graph structure. This gap has driven a tide in research for deep learning on graphs, among them Graph Neural Networks (GNNs) are the most successful in coping with various learning tasks across a large number of application domains. In this chapter, we will systematically organize the existing research of GNNs along three axes: foundations, frontiers, and applications. We will introduce the fundamental aspects of GNNs ranging from the popular models and their expressive powers, to the scalability, interpretability and robustness of GNNs. Then, we will discuss vari- ous frontier research, ranging from graph classification and link prediction, to graph generation and transformation, graph matching and graph structure learning. Based on them, we further summarize the basic procedures which exploit full use of vari- ous GNNs for a large number of applications. Finally, we provide the organization of our book and summarize the roadmap of the various research topics of GNNs

Foundations of Graph Neural Networks

4. Graph Neural Networks for Node Classification: Graph Neural Networks are neural architectures specifically designed for graph-structured data, which have been receiving increasing attention recently and applied to different domains and applications. In this chapter, we focus on a funda- mental task on graphs: node classification. We will give a detailed definition of node classification and also introduce some classical approaches such as label propaga- tion. Afterwards, we will introduce a few representative architectures of graph neu- ral networks for node classification. We will further point out the main difficulty— the oversmoothing problem—of training deep graph neural networks and present some latest advancement along this direction such as continuous graph neural net- works.

5. The Expressive Power of Graph Neural Networks: The success of neural networks is based on their strong expressive power that allows them to approximate complex non-linear mappings from features to predictions. Since the universal approximation theorem by (Cybenko, 1989), many studies have proved that feed-forward neural networks can approximate any func- tion of interest. However, these results have not been applied to graph neural net- works (GNNs) due to the inductive bias imposed by additional constraints on the GNN parameter space. New theoretical studies are needed to better understand these constraints and characterize the expressive power of GNNs. In this chapter, we will review the recent progress on the expressive power of GNNs in graph representation learning. We will start by introducing the most widely-used GNN framework— message passing— and analyze its power and limitations. We will next introduce some recently proposed techniques to overcome these limita- tions, such as injecting random attributes, injecting deterministic distance attributes, and building higher-order GNNs. We will present the key insights of these tech- niques and highlight their advantages and disadvantages.

6. Graph Neural Networks: Scalability: Over the past decade, Graph Neural Networks have achieved remarkable success in modeling complex graph data. Nowadays, graph data is increasing expo- nentially in both magnitude and volume, e.g., a social network can be constituted by billions of users and relationships. Such circumstance leads to a crucial question, how to properly extend the scalability of Graph Neural Networks? There remain two major challenges while scaling the original implementation of GNN to large graphs. First, most of the GNN models usually compute the entire adjacency matrix and node embeddings of the graph, which demands a huge memory space. Second, training GNN requires recursively updating each node in the graph, which becomes infeasible and ineffective for large graphs. Current studies propose to tackle these obstacles mainly from three sampling paradigms: node-wise sampling, which is ex- ecuted based on the target nodes in the graph; layer-wise sampling, which is im- plemented on the convolutional layers; and graph-wise sampling, which constructs sub-graphs for the model inference. In this chapter, we will introduce several repre- sentative research accordingly.

7. Interpretability in Graph Neural Networks: Interpretable machine learning, or explainable artificial intelligence, is ex- periencing rapid developments to tackle the opacity issue of deep learning tech- niques. In graph analysis, motivated by the effectiveness of deep learning, graph neural networks (GNNs) are becoming increasingly popular in modeling graph data. Recently, an increasing number of approaches have been proposed to provide ex- planations for GNNs or to improve GNN interpretability. In this chapter, we offer a comprehensive survey to summarize these approaches. Specifically, in the first section, we review the fundamental concepts of interpretability in deep learning. In the second section, we introduce the post-hoc explanation methods for understand- ing GNN predictions. In the third section, we introduce the advances of developing more interpretable models for graph data. In the fourth section, we introduce the datasets and metrics for evaluating interpretation. Finally, we point out future direc- tions of the topic.

8. Graph Neural Networks: Adversarial Robustness: Graph neural networks have achieved impressive results in various graph learning tasks and they have found their way into many applications such as molec- ular property prediction, cancer classification, fraud detection, or knowledge graph reasoning. With the increasing number of GNN models deployed in scientific ap- plications, safety-critical environments, or decision-making contexts involving hu- mans, it is crucial to ensure their reliability. In this chapter, we provide an overview of the current research on adversarial robustness of GNNs. We introduce the unique challenges and opportunities that come along with the graph setting and give an overview of works showing the limitations of classic GNNs via adversarial example generation. Building upon these insights we introduce and categorize methods that provide provable robustness guarantees for graph neural networks as well as prin- ciples for improving robustness of GNNs. We conclude with a discussion of proper evaluation practices taking robustness into account.

Frontiers of Graph Neural Networks

9. Graph Neural Networks: Graph Classification: Recently, graph neural networks emerged as the leading machine learn- ing architecture for supervised learning with graph and relational input. This chapter gives an overview of GNNs for graph classification, i.e., GNNs that learn a graph- level output. Since GNNs compute node-level representations, pooling layers, i.e., layers that learn graph-level representations from node-level representations, are crucial components for successful graph classification. Hence, we give a thorough overview of pooling layers. Further, we overview recent research in understand- ing GNN’s limitations for graph classification and progress in overcoming them. Finally, we survey some graph classification applications of GNNs and overview benchmark datasets for empirical evaluation.

10. Graph Neural Networks: Link Prediction: Link prediction is an important application of graph neural networks. By predicting missing or future links between pairs of nodes, link prediction is widely used in social networks, citation networks, biological networks, recommender sys- tems, and security, etc. Traditional link prediction methods rely on heuristic node similarity scores, latent embeddings of nodes, or explicit node features. Graph neu- ral network (GNN), as a powerful tool for jointly learning from graph structure and node/edge features, has gradually shown its advantages over traditional methods for link prediction. In this chapter, we discuss GNNs for link prediction. We first in- troduce the link prediction problem and review traditional link prediction methods. Then, we introduce two popular GNN-based link prediction paradigms, node-based and subgraph-based approaches, and discuss their differences in link representation power. Finally, we review recent theoretical advancements on GNN-based link pre- diction and provide several future directions.

11. Graph Neural Networks: Graph Generation: In this chapter, we first review a few classic probabilistic models for graph generation including the Erdo ̋s–Re ́nyi model and the stochastic block model. Then we introduce several representative modern graph generative models that lever- age deep learning techniques like graph neural networks, variational auto-encoders, deep auto-regressive models, and generative adversarial networks. At last, we con- clude the chapter with a discussion on potential future directions.

12. Graph Neural Networks: Graph Transformation: Many problems regarding structured predictions are encountered in the process of “transforming” a graph in the source domain into another graph in target domain, which requires to learn a transformation mapping from the source to target domains. For example, it is important to study how structural connectivity influences functional connectivity in brain networks and traffic networks. It is also common to study how a protein (e.g., a network of atoms) folds, from its primary structure to tertiary structure. In this chapter, we focus on the transformation problem that involves graphs in the domain of deep graph neural networks. First, the problem of graph transformation in the domain of graph neural networks are formalized in Section 12.1. Considering the entities that are being transformed during the trans- formation process, the graph transformation problem is further divided into four categories, namely node-level transformation, edge-level transformation, node-edge co-transformation, as well as other graph-involved transformations (e.g., sequence- to-graph transformation and context-to-graph transformation), which are discussed in Section 12.2 to Section 12.5, respectively. In each subsection, the definition of each category and their unique challenges are provided. Then, several representa- tive graph transformation models that address the challenges from different aspects for each category are introduced.

13. Graph Neural Networks: Graph Matching: The problem of graph matching that tries to establish some kind of struc- tural correspondence between a pair of graph-structured objects is one of the key challenges in a variety of real-world applications. In general, the graph matching problem can be classified into two categories: i) the classic graph matching problem which finds an optimal node-to-node correspondence between nodes of a pair of in- put graphs and ii) the graph similarity problem which computes a similarity metric between two graphs. While recent years have witnessed the great success of GNNs in learning node representations of graphs, there is an increasing interest in explor- ing GNNs for the graph matching problem in an end-to-end manner. This chapter focuses on the state of the art of graph matching models based on GNNs. We start by introducing some backgrounds of the graph matching problem. Then, for each category of graph matching problem, we provide a formal definition and discuss state-of-the-art GNN-based models for both the classic graph matching problem and the graph similarity problem, respectively. Finally, this chapter is concluded by pointing out some possible future research directions.

14. Graph Neural Networks: Graph Structure Learning: Due to the excellent expressive power of Graph Neural Networks (GNNs) on modeling graph-structure data, GNNs have achieved great success in various applications such as Natural Language Processing, Computer Vision, recommender systems, drug discovery and so on. However, the great success of GNNs relies on the quality and availability of graph-structured data which can either be noisy or unavailable. The problem of graph structure learning aims to discover useful graph structures from data, which can help solve the above issue. This chapter attempts to provide a comprehensive introduction of graph structure learning through the lens of both traditional machine learning and GNNs. After reading this chapter, readers will learn how this problem has been tackled from different perspectives, for different purposes, via different techniques, as well as its great potential when combined with GNNs. Readers will also learn promising future directions in this research area.

15. Dynamic Graph Neural Networks: The world around us is composed of entities that interact and form re- lations with each other. This makes graphs an essential data representation and a crucial building-block for machine learning applications; the nodes of the graph correspond to entities and the edges correspond to interactions and relations. The entities and relations may evolve; e.g., new entities may appear, entity properties may change, and new relations may be formed between two entities. This gives rise to dynamic graphs. In applications where dynamic graphs arise, there often exists important information within the evolution of the graph, and modeling and exploit- ing such information is crucial in achieving high predictive performance. In this chapter, we characterize various categories of dynamic graph modeling problems. Then we describe some of the prominent extensions of graph neural networks to dy- namic graphs that have been proposed in the literature. We conclude by reviewing three notable applications of dynamic graph neural networks namely skeleton-based human activity recognition, traffic forecasting, and temporal knowledge graph com- pletion.

16. Heterogeneous Graph Neural Networks: Heterogeneous graphs (HGs) also called heterogeneous information net- works (HINs) have become ubiquitous in real-world scenarios. Recently, employing graph neural networks (GNNs) to heterogeneous graphs, known as heterogeneous graph neural networks (HGNNs) which aim to learn embedding in low-dimensional space while preserving heterogeneous structure and semantic for downstream tasks, has drawn considerable attention. This chapter will first give a brief review of the recent development on HG embedding, then introduce typical methods from the perspective of shallow and deep models, especially HGNNs. Finally, it will point out future research directions for HGNNs.

17. Graph Neural Networks: AutoML: Graph neural networks (GNNs) are efficient deep learning tools to analyze networked data. Being widely applied in graph analysis tasks, the rapid evolution of GNNs has led to a growing number of novel architectures. In practice, both neural architecture construction and training hyperparameter tuning are crucial to the node representation learning and the final model performance. However, as the graph data characteristics vary significantly in the real-world systems, given a specific scenario, rich human expertise and tremendous laborious trials are required to identify a suit- able GNN architecture and training hyperparameters. Recently, automated machine learning (AutoML) has shown its potential in finding the optimal solutions automat- ically for machine learning applications. While releasing the burden of the manual tuning process, AutoML could guarantee access of the optimal solution without ex- tensive expert experience. Motivated from the previous successes of AutoML, there have been some preliminary automated GNN (AutoGNN) frameworks developed to tackle the problems of GNN neural architecture search (GNN-NAS) and train- ing hyperparameter tuning. This chapter presents a comprehensive and up-to-date review of AutoGNN in terms of two perspectives, namely search space and search algorithm. Specifically, we mainly focus on the GNN-NAS problem and present the state-of-the-art techniques in these two perspectives. We further discuss the open problems related to the existing methods for future research.

18. Graph Neural Networks: Self-supervised Learning: Although deep learning has achieved state-of-the-art performance across numerous domains, these models generally require large annotated datasets to reach their full potential and avoid overfitting. However, obtaining such datasets can have high associated costs or even be impossible to procure. Self-supervised learning (SSL) seeks to create and utilize specific pretext tasks on unlabeled data to aid in alleviating this fundamental limitation of deep learning models. Although initially applied in the image and text domains, recent interest has been in leveraging SSL in the graph domain to improve the performance of graph neural networks (GNNs). For node-level tasks, GNNs can inherently incorporate unlabeled node data through the neighborhood aggregation unlike in the image or text domains; but they can still benefit by applying novel pretext tasks to encode richer information and nu- merous such methods have recently been developed. For GNNs solving graph-level tasks, applying SSL methods is more aligned with other traditional domains, but still presents unique challenges and has been the focus of a few works. In this chapter, we summarize recent developments in applying SSL to GNNs categorizing them via the different training strategies and types of data used to construct their pretext tasks, and finally discuss open challenges for future directions.

Broad and Emerging Applications with Graph Neural Networks

19. Graph Neural Networks in Modern Recommender Systems: Graph is an expressive and powerful data structure that is widely applica- ble, due to its flexibility and effectiveness in modeling and representing graph struc- ture data. It has been more and more popular in various fields, including biology, finance, transportation, social network, among many others. Recommender system, one of the most successful commercial applications of the artificial intelligence, whose user-item interactions can naturally fit into graph structure data, also receives much attention in applying graph neural networks (GNNs). We first summarize the most recent advancements of GNNs, especially in the recommender systems. Then we share our two case studies, dynamic GNN learning and device-cloud collabora- tive Learning for GNNs. We finalize with discussions regarding the future directions of GNNs in practice.

20. Graph Neural Networks in Computer Vision: Recently Graph Neural Networks (GNNs) have been incorporated into many Computer Vision (CV) models. They not only bring performance improve- ment to many CV-related tasks but also provide more explainable decomposition to these CV models. This chapter provides a comprehensive overview of how GNNs are applied to various CV tasks, ranging from single image classification to cross- media understanding. It also provides a discussion of this rapidly growing field from a frontier perspective.

21. Graph Neural Networks in Natural Language Processing: Natural language processing (NLP) and understanding aim to read from unformatted text to accomplish different tasks. While word embeddings learned by deep neural networks are widely used, the underlying linguistic and semantic struc- tures of text pieces cannot be fully exploited in these representations. Graph is a natural way to capture the connections between different text pieces, such as enti- ties, sentences, and documents. To overcome the limits in vector space models, re- searchers combine deep learning models with graph-structured representations for various tasks in NLP and text mining. Such combinations help to make full use of both the structural information in text and the representation learning ability of deep neural networks. In this chapter, we introduce the various graph representations that are extensively used in NLP, and show how different NLP tasks can be tackled from a graph perspective. We summarize recent research works on graph-based NLP, and discuss two case studies related to graph-based text clustering, matching, and multi- hop machine reading comprehension in detail. Finally, we provide a synthesis about the important open problems of this subfield.

22. Graph Neural Networks in Program Analysis: Program analysis aims to determine if a program’s behavior complies with some specification. Commonly, program analyses need to be defined and tuned by humans. This is a costly process. Recently, machine learning methods have shown promise for probabilistically realizing a wide range of program analyses. Given the structured nature of programs, and the commonality of graph represen- tations in program analysis, graph neural networks (GNN) offer an elegant way to represent, learn, and reason about programs and are commonly used in machine learning-based program analyses. This chapter discusses the use of GNNs for pro- gram analysis, highlighting two practical use cases: variable misuse detection and type inference.

23. Graph Neural Networks in Software Mining: Software Mining encompasses a broad range of tasks involving software, such as finding the location of a bug in the source code of a program, generating nat- ural language descriptions of software behavior, and detecting when two programs do basically the same thing. Software tends to have an extremely well-defined struc- ture, due to the linguistic confines of source code and the need for programmers to maintain readability and compatibility when working on large teams. A tradition of graph-based representations of software has therefore proliferated. Meanwhile, advances in software repository maintenance have recently helped create very large datasets of source code. The result is fertile ground for Graph Neural Network rep- resentations of software to facilitate a plethora of software mining tasks. This chap- ter will provide a brief history of these representations, describe typical software mining tasks that benefit from GNNs, demonstrate one of these tasks in detail, and explain the benefits that GNNs can provide. Caveats and recommendations will also be discussed.

24. GNN-based Biomedical Knowledge Graph Mining in Drug Development: Drug discovery and development (D3) is an extremely expensive and time consuming process. It takes tens of years and billions of dollars to make a drug suc- cessfully on the market from scratch, which makes this process highly inefficient when facing emergencies such as COVID-19. At the same time, a huge amount of knowledge and experience has been accumulated during the D3 process during the past decades. These knowledge are usually encoded in guidelines or biomedi- cal literature, which provides an important resource containing insights that can be informative of the future D3 process. Knowledge graph (KG) is an effective way of organizing the useful information in those literature so that they can be retrieved efficiently. It also bridges the heterogeneous biomedical concepts that are involved in the D3 process. In this chapter we will review the existing biomedical KG and introduce how GNN techniques can facilitate the D3 process on the KG. We will also introduce two case studies on Parkinson’s disease and COVID-19, and point out future directions.

25. Graph Neural Networks in Predicting Protein Function and Interactions: Graph Neural Networks (GNNs) are becoming increasingly popular and powerful tools in molecular modeling research due to their ability to operate over non-Euclidean data, such as graphs. Because of their ability to embed both the inher- ent structure and preserve the semantic information in a graph, GNNs are advancing diverse molecular structure-function studies. In this chapter, we focus on GNN- aided studies that bring together one or more protein-centric sources of data with the goal of elucidating protein function. We provide a short survey on GNNs and their most successful, recent variants designed to tackle the related problems of pre- dicting the biological function and molecular interactions of protein molecules. We review the latest methodological advances, discoveries, as well as open challenges promising to spur further research.

26. Graph Neural Networks in Anomaly Detection: Anomaly detection is an important task, which tackles the problem of dis- covering “different from normal” signals or patterns by analyzing a massive amount of data, thereby identifying and preventing major faults. Anomaly detection is ap- plied to numerous high-impact applications in areas such as cyber-security, finance, e-commerce, social network, industrial monitoring, and many more mission-critical tasks. While multiple techniques have been developed in past decades in address- ing unstructured collections of multi-dimensional data, graph-structure-aware tech- niques have recently attracted considerable attention. A number of novel techniques have been developed for anomaly detection by leveraging the graph structure. Re- cently, graph neural networks (GNNs), as a powerful deep-learning-based graph rep- resentation technique, has demonstrated superiority in leveraging the graph structure and been used in anomaly detection. In this chapter, we provide a general, compre- hensive, and structured overview of the existing works that apply GNNs in anomaly detection.

27. Graph Neural Networks in Urban Intelligence: In recent years, smart and connected urban infrastructures have undergone a fast expansion, which increasingly generates huge amounts of urban big data, such as human mobility data, location-based transaction data, regional weather and air quality data, social connection data. These heterogeneous data sources convey rich information about the city and can be naturally linked with or modeled by graphs, e.g., urban social graph, transportation graph. These urban graph data can enable intelligent solutions to solve various urban challenges, such as urban facility plan- ning, air pollution, etc. However, it is also very challenging to manage, analyze, and make sense of such big urban graph data. Recently, there have been many studies on advancing and expanding Graph Neural Networks (GNNs) approaches for var- ious urban intelligence applications. In this chapter, we provide a comprehensive overview of the graph neural network (GNN) techniques that have been used to em- power urban intelligence, in four application categories, namely, (i) urban anomaly and event detection, (ii) urban configuration and transportation planning, (iii) ur- ban traffic prediction, and (iv) urban human behavior inference. The chapter also discusses future directions of this line of research. The chapter is (tentatively) orga- nized as follows.