Graph Neural Networks: Powering the Next Generation of AI with Graph Representation Learning

Introduction

Graphs are everywhere. From the intricate wiring of the brain to the complex web of social connections, many real-world phenomena are best described in terms of entities and their relationships. As such, graphs are a powerful abstraction for modeling data across domains ranging from biology to physics to economics. However, most machine learning algorithms are designed to operate on fixed-size vectors and struggle to handle the variable-size, non-Euclidean structure of graph data.

Enter graph neural networks (GNNs) – a new class of deep learning models that has emerged as the most effective framework for representation learning on graphs. By designing neural network architectures that can operate directly on graph structures, GNNs can learn rich, expressive embeddings of nodes and edges that enable state-of-the-art performance on tasks such as node classification, link prediction, and graph classification.

The key idea behind GNNs is to recursively aggregate information from a node‘s graph neighborhood to compute its embedding – a fixed-size vector representation that captures both the node‘s features and its role in the broader graph context. As Andrew Ng, one of the pioneers of deep learning, has emphasized, "AI is the new electricity" – a general-purpose technology that will transform every industry. And GNNs are quickly becoming one of the most powerful tools in the AI toolbox, with the potential to revolutionize how we analyze and extract insights from the wealth of graph-structured data in the world.

Graphs: A Universal Language for Complex Systems

At a fundamental level, a graph $G=(V,E)$ is a mathematical object consisting of a set of nodes $V$ and a set of edges $E$ that connect pairs of nodes. For example, in a social network graph, nodes represent people and edges represent friendships or interactions between them (Fig. 1). Each node can be associated with its own attributes (e.g. age, gender, interests of a person) and each edge can also have attributes (e.g. type or strength of a social tie).

Figure 1: Example of a social network graph. (Source: Introduction to Graph Neural Networks)

Graphs provide a general language for describing the structure and dynamics of a wide range of complex systems:

• In biology, graphs can model protein-protein interaction networks, gene regulatory networks, and anatomical brain networks
• In chemistry, graphs can represent the structure of molecules, with nodes as atoms and edges as chemical bonds
• In social networks, graphs can capture the patterns of connections and influence between people and organizations
• In knowledge bases and recommendation engines, graphs can express the semantic relationships between entities and concepts

The expressive power of graphs lies in their ability to capture not just the properties of individual entities, but also the rich relational context in which they are embedded. However, this expressiveness comes at a cost: graphs can vary greatly in size, topology, and attributes, making them challenging to analyze with traditional machine learning approaches that expect fixed-length vector inputs.

The Rise of Graph Neural Networks

The field of graph neural networks has exploded in recent years, with over 5,000 papers published on the topic in the past 5 years alone (Fig 2). This rapid growth has been driven by a combination of factors:

• The increasing availability of graph-structured data across domains
• The success of deep learning in domains like computer vision and natural language processing, which has motivated the development of architectures for other data types
• Theoretical breakthroughs in defining differentiable graph operations that can be used as building blocks for end-to-end learning
• Empirical results demonstrating that GNNs can outperform traditional graph analytics approaches (e.g. kernel methods, random walk embeddings) on a variety of tasks

Figure 2: Number of publications on graph neural networks over time. (Source: Papers With Code)

At a high level, GNNs can be viewed as a powerful framework for learning node embeddings – low-dimensional vector representations that capture the local graph structure and features around each node. These node embeddings can then be used as input to downstream machine learning models for tasks such as node classification, community detection, or link prediction. Some key advantages of the GNN paradigm include:

1. Inductive Representation Learning: GNNs can learn a general function that maps the structure and features of a node‘s local neighborhood to an embedding vector. This allows GNNs to generate embeddings for previously unseen nodes and graphs, enabling inductive reasoning about new data points.

2. Compositionality: GNNs build up more global representations by iteratively aggregating local information. Deep, multi-layer GNNs can learn to capture long-range dependencies and higher-order graph structures that are hard to specify by hand.

3. Flexibility: The GNN framework is highly general and modular, encompassing a wide variety of architectures that can be adapted to different types of graphs (e.g. directed, weighted, heterogeneous graphs with multiple edge types) and problem settings (e.g. semi-supervised, multi-task, multi-relational learning).

As a result of these attractive properties, GNNs have quickly become the dominant approach for machine learning on graphs, with state-of-the-art performance across a range of benchmark tasks. Table 1 shows a comparison of GNNs with other leading graph embedding approaches on the node classification task for several standard datasets:

Table 1: Performance (accuracy) of GNNs and other graph embedding methods on node classification benchmarks. (Sources: Kipf & Welling 2017, Hamilton et al. 2017, Veličković et al. 2018, Lai et al. 2017, Perozzi et al. 2014, Grover & Leskovec 2016)

GNNs such as Graph Convolutional Networks (GCN), GraphSAGE, and Graph Attention Networks (GAT) are able to outperform popular non-GNN embedding approaches like DeepWalk and node2vec by directly incorporating graph structure in the encoder architecture. Furthermore, large-scale industrial applications of GNNs have demonstrated significant impact in production systems for recommender engines, question answering, and fraud detection.

Anatomy of a Graph Neural Network

Under the hood, graph neural networks operate by recursively propagating information along graph edges to compute expressive node embeddings. At each propagation step $t$, the embedding $h_v^{(t)}$ of node $v$ is updated based on aggregating information from its graph neighborhood $N(v)$:

$$
\begin{align}
a_v^{(t)} &= \text{AGGREGATE}^{(t)}({h_u^{(t-1)} : u \in N(v)}) \
h_v^{(t)} &= \text{COMBINE}^{(t)}(h_v^{(t-1)}, a_v^{(t)})
\end{align}
$$

The AGGREGATE function pools information from the node‘s neighbors, while the COMBINE function merges the node‘s previous embedding with the aggregated neighborhood information. By stacking $T$ propagation layers, the final node embeddings $h_v^{(T)}$ can capture structural information from the $T$-hop neighborhood around each node.

Different GNN architectures can be viewed as particular parameterizations of the AGGREGATE and COMBINE functions (Fig. 3):

• Graph Convolutional Network (GCN)
  • AGGREGATE: Take weighted sum of neighbor embeddings
  • COMBINE: Apply linear transformation and ReLU activation
• GraphSAGE
  • AGGREGATE: Apply aggregator (e.g. mean, max, LSTM) to neighbor embeddings
  • COMBINE: Concatenate node embedding with aggregated embeddings and apply nonlinearity
• Graph Attention Network (GAT)
  • AGGREGATE: Take weighted sum of neighbor embeddings with attention-based weights
  • COMBINE: Apply linear transformation and ReLU activation to concatenated node and aggregated embeddings
• Gated Graph Neural Network (GGNN)
  • AGGREGATE: Take sum of neighbor embeddings
  • COMBINE: Apply GRU cell to update node embeddings based on aggregated messages

Figure 3: Computation graph of a GNN layer. The AGGREGATE and COMBINE steps can be instantiated in different ways to yield different GNN architectures. (Source: Image source

By learning the parameters of the aggregation and combination functions in an end-to-end fashion, GNNs can optimize the node embeddings for the specific downstream prediction task. For example, to perform graph classification, the learned node embeddings are often pooled into a graph-level embedding vector which is then passed to a softmax classifier. The entire GNN model can then be trained by gradient descent to minimize the cross-entropy loss on the graph labels.

Applications and Impact

Graph neural networks have already been deployed in a variety of high-impact applications in both industry and the sciences. Some prominent use cases include:

• Recommender Systems: GNNs can be used to generate embeddings of users and items in a bipartite interaction graph, enabling more accurate and scalable recommendation engines. Pinterest has deployed GNNs in production to power pin recommendations for hundreds of millions of users (Ying et al. 2018).

• Drug Discovery: GNNs can learn representations of molecular graphs to predict chemical properties and bioactivity, accelerating the discovery of new therapeutic drugs. GNNs have achieved state-of-the-art performance on tasks such as molecular property prediction and virtual screening (Ramsundar et al. 2019).

• Traffic Forecasting: GNNs can model road networks and predict traffic speeds based on historical patterns and real-time conditions. GNNs have been shown to outperform other deep learning approaches for traffic speed forecasting by 10-15% on real-world datasets (Yu et al. 2018).

• Fake News Detection: GNNs can capture the propagation patterns of news and information in social networks to help detect misinformation. GNN-based approaches have achieved over 90% accuracy in classifying fake news stories based on their spread in simulated social networks (Monti et al. 2019).

Beyond these examples, GNNs are also being actively explored for applications ranging from computer vision (e.g. point cloud classification, visual question answering) to natural language processing (e.g. knowledge graph completion, text classification with graph-of-word representations) to program verification (e.g. finding bugs in source code).

Frontiers and Future Directions

While the past few years have seen rapid progress in the field of graph neural networks, there remain many exciting open problems to tackle:

• Scalability: Real-world graphs can contain billions of nodes and edges, posing major computational challenges for GNNs. Recent work has explored techniques such as sampling, graph partitioning, and distributed training to scale GNNs to massive graphs (Zeng et al. 2019).

• Expressivity: GNNs based on local message passing have limited ability to capture long-range dependencies and may suffer from over-smoothing with many propagation layers. Several approaches have been proposed to increase the expressivity of GNNs, including higher-order GNNs (Morris et al. 2019), position-aware GNNs (You et al. 2019), and message passing with aggregation functions learned by graph isomorphism networks (Maron et al. 2019).

• Heterogeneity: Most existing GNNs assume homogeneous graphs with a single type of node and edge, but many real-world graphs are heterogeneous with multiple node and edge types, each with its own attributes. Extending GNNs to leverage the rich type information in heterogeneous graphs is an important direction (Wang et al. 2019).

• Dynamicity: Graphs in applications are often dynamic and evolving over time. Designing GNNs that can efficiently update embeddings based on incremental changes to the graph structure is critical for learning in dynamic environments (Manessi et al. 2020).

• Theory: While empirically successful, most GNNs lack strong theoretical guarantees and may behave unexpectedly out of distribution. A rigorous theoretical understanding of the expressive power, generalization, and stability properties of GNNs is an active area of investigation (Keriven & Peyré 2019, Garg et al. 2020).

As we continue to push the boundaries of graph representation learning, it is also important to consider the ethical implications of GNNs and their applications. The expressive power of GNNs to capture signals of homophily and social influence may risk amplifying biases and filter bubbles if not carefully designed. Developing GNNs that are fair, accountable, and aligned with human values is a critical direction for future research (Bose & Hamilton 2019).

Conclusion

Graph neural networks have emerged as a powerful and flexible framework for machine learning on graph-structured data. By learning to aggregate information from local graph neighborhoods, GNNs can generate expressive node embeddings that enable state-of-the-art performance on a variety of prediction tasks. GNNs have already demonstrated significant real-world impact, with successful applications ranging from recommender systems to drug discovery to traffic forecasting.

But the graph neural networks are still rapidly evolving, with new architectures, scaling techniques, and application areas being developed every day. As the field matures, we expect GNNs to become an indispensable tool in the machine learning ecosystem, powering new breakthroughs across science, engineering, and beyond. If deep learning was the driving force of AI‘s resurgence in the 2010s, graph representation learning may well define the frontier of AI in the 2020s and beyond.