Graph neural network

YuTing Liu, Ming Zhang, Ma Chicheng, Bai Bo, Zhiheng Zhou, Kai Yan, Guanghui Wang, Yan Gui-yingScientia 2020 · DOI

Abstract

In recent years, with the emergence of massive data, graph structure data that can represent complex relationships between objects has received more and more attention and has brought great challenges to existing algorithms. As deep topology information can be revealed, graph neural network models have been widely used in many fields such as communication, life sciences, and finance. This paper reviews the basic models, algorithms, applications and recent developments of existing graph neural networks in recent years, and proposes problems for further research.

Introduction: The Challenge of Non-Euclidean Data

Traditional deep learning has achieved remarkable success in processing "Euclidean" data, such as images (regular pixel grids) and text (linear sequences). However, a vast amount of real-world data is structured as graphs—irregular sets of nodes and edges where the number of neighbors varies for every point. Examples include social networks, molecular structures, and citation webs. Standard convolutional neural networks (CNNs) struggle with these structures because they lack a fixed grid. Graph Neural Networks (GNNs) have emerged to fill this gap, providing a unified framework to capture deep topological information.

Methodological Taxonomy

GNN research can be broadly categorized into three primary families: spatial-based, spectral-based, and generative-based models.

Figure 1: Evolution of node features across graph layers.

Spatial-based Models

Spatial-based models are the most intuitive extension of CNNs to graphs. They define "convolution" through message passing, where a node's state is updated by aggregating information from its immediate neighbors.

Figure 2: The message passing and aggregation process for individual nodes.

The evolution of these models has moved from basic GNNs to gated versions (like GGS-NN) that utilize GRU-like units to manage long-range dependencies across the graph topology.

Spectral-based Models

Spectral models leverage graph signal processing and the Graph Laplacian to perform convolutions in the frequency domain. While early models like SpectralGCN were computationally intensive, the field has shifted toward efficient approximations. ChebNets and the now-standard Graph Convolutional Network (GCN) simplify the mathematics to a first-order approximation, making them practical for large-scale applications.

Generative-based Models

Beyond classification, generative GNNs learn to synthesize new graph structures. Techniques include Graph Autoencoders (VGAE) for link prediction and Graph Adversarial Networks (GraphGAN) for creating realistic network topologies or novel chemical molecules.

Key Insights and Theoretical Challenges

  • The Over-smoothing Problem: Unlike deep CNNs, GNNs often perform worse as depth increases. After just a few layers, node representations can become too similar—a phenomenon known as over-smoothing where features converge to a mean.
  • Inductive vs. Transductive Learning: There is a significant shift toward inductive models that can generalize to entirely unseen nodes or graphs, moving away from transductive models that require a fixed graph structure during training.
  • The Power of the Laplacian: The spectral approach provides the theoretical foundation for graph convolutions, even as spatial methods dominate practical implementations for dynamic, massive graphs.

Benchmarks and Performance

GNNs have set new standards across various domains:

  • Isomorphism Detection: Early models like GoriGNN achieved 100% accuracy on specific isomorphism (同构) detection tasks.
  • Bioinformatics: LGNN models reached 90% accuracy in predicting secondary protein structures, significantly outperforming traditional sequence-based methods.
  • Scalability: GraphRNN can generate graphs up to 50 times larger than previous generative models while maintaining structural integrity.
  • Node Classification: On citation datasets like Cora and Citeseer, GCN-based methods consistently achieve accuracies in the high 70% to low 80% range.

Future Research Directions

The authors identify several critical frontiers for GNN research:

  1. Dynamic Graphs: Developing models that can handle evolving structures and update in real-time.
  2. Interpretability: Moving beyond "black box" predictions to understand the logic behind specific node or link classifications, especially in high-stakes fields like medicine.
  3. Deep Architectures: Overcoming the over-smoothing trap to build deeper, more expressive models.
  4. Adversarial Robustness: Protecting models against "structure attacks" where small, malicious changes to edges can flip predictions.
  5. Scalability: Efficiently processing graphs with billions of nodes through advanced sampling and distributed training techniques.

Summary updated

Abstract

In recent years, with the emergence of massive data, graph structure data that can represent complex relationshipsbetween objects has received more and more attention and has brought great challenges to existing algorithms.As a deep topology information can be revealed, graph neural network models have been widely used in many fields such as communication,life sciences, and finance. This paper reviews the basic models, algorithms, applications and recent developments of existing graph neuralnetworks in recent years, and proposes problems for further research.
BibTeX
@inproceedings{liu2020graph,
  author = {YuTing Liu and Ming Zhang and Ma Chicheng and Bai Bo and Zhiheng Zhou and Kai Yan and Guanghui Wang and Yan Gui-ying},
  title = {{Graph neural network}},
  booktitle = {Scientia},
  year = {2020},
  doi = {10.1360/n012019-00133},
}
Figure