Graph in Graph Neural Network

Jiongshu Wang, Siyang Song, Liru Chen, Jing Yang, Jiankang Deng, Hatice GunesOpenReview 2022 · OpenReview

Abstract

Existing Graph Neural Networks (GNNs) are limited to processing graphs where each vertex is represented by a vector or a single value, which restricts their ability to describe complex objects. We propose the Graph in Graph Neural (GIG) Network, the first GNN capable of processing graph-style data (GIG samples) whose vertices are themselves represented by graphs. The GIG network utilizes a GIG sample generation (GSG) module to encode input data, followed by stacked hidden layers that alternate between local vertex-level updates (GVU) and global context-aware updates (GGU). Experimental results show that GIG generalizes well across generic graph tasks and real-world multi-graph data, achieving state-of-the-art results on 13 out of 14 evaluated datasets.

Introduction: The Structural Compression Problem

In traditional GNN architectures, a vertex is typically treated as a point in space described by a feature vector. While effective for simple data, this approach struggles with complex, multi-component objects. For example, in a video of a human performing an action, a standard GNN might represent each frame as a vertex. To do so, the complex arrangement of human joints within that frame must be flattened into a single vector. This "structural compression" loses the vital spatial relationships between joints.

Comparison between standard GNNs (top) and the proposed GIG network (bottom) for human skeleton data.

The GIG Network addresses this by using a nested graph representation: a global graph where each vertex contains its own local graph. This allows the model to preserve fine-grained structural cues without losing the hierarchical context.

Methodology: The GIG Architecture

The GIG Network introduces a three-part pipeline to handle these nested structures:

  1. GIG Sample Generation (GSG) Layer: This module transforms raw data into a "GIG sample." It defines Proxy Vertices—local proxies that summarize the internal graph of a vertex and global proxies that facilitate communication across the network.
  2. GIG Hidden Layers: These layers consist of two interleaved modules:
  3. GIG Vertex-level Updating (GVU): This updates the edges and vertices within each individual graph-vertex, focusing on local structural information.
  4. Global-level GIG Sample Updating (GGU): This allows different graph-vertices to communicate via the proxy vertices, making the local representations global context-aware.
  5. GIG Output Layer: A final pass that combines local and global updates to produce the final prediction.
The GIG Network architecture, highlighting the GSG, GVU, and GGU modules and the proxy vertex mechanism.

A key strength of this architecture is its flexibility; the GVU and GGU modules can "wrap" around existing GNN backbones like GatedGCN or GAT, upgrading them to handle nested structures.

Experimental Evaluation and Key Results

The authors evaluated GIG across 14 datasets covering graph classification (MNIST, CIFAR10, TU datasets, OGBG-PPA), regression (ZINC, AQSOL), node classification (PATTERN, CLUSTER), link prediction (TSP), and action recognition (NTU RGB+D).

The GIG Network achieved state-of-the-art (SOTA) performance on 13 out of 14 datasets. Notable highlights include:

  • Action Recognition: On the NTU RGB+D (X-View) dataset, GIG-CTR-GCN reached 97.1% accuracy, outperforming specialized skeleton-based models.
  • Generic Benchmarks: On the CLUSTER node classification task, GIG improved the GatedGCN baseline from 76.08% to 79.34%.
  • Molecular Data: On ZINC-full, GIG achieved a Mean Absolute Error (MAE) of 0.029, a significant improvement over standard GNN baselines.

Discussion and Insights

The core insight of this work is that preserving internal structure is fundamentally more powerful than vectorization. Ablation studies confirmed that even with a similar parameter count, the graph-in-graph approach consistently outperforms flattened versions. The "Proxy Strategy" effectively manages computational complexity by acting as a communication hub, avoiding the need for dense connections between every node in every sub-graph.

While the model is robust to hyperparameters, the current limitation lies in the GSG Layer, which often requires task-specific engineering to format the initial GIG sample. Future work will focus on developing automated graph representation learning to replace this manual step and extending the architecture to multi-modal data.

Summary updated

Abstract

Most existing Graph Neural Networks (GNNs) frequently suffer from two limitations: (i) they can only process graphs whose vertices are represented by vectors or single values; and (ii) they assume each input graph is independent from others during the propagation. In this paper, we propose \textbf{the first GNN model (called Graph in Graph Neural Network (GIG)) that can process graphs whose vertices are also represented by graphs}. Considering that the relationship between different graphs may contain crucial task-related cues, we further propose a GIG graph relationship modelling (GRM) strategy that integrates multiple target graph samples as a global graph, each of whose vertex describes a target graph sample. We then applies the GIG model to jointly process the combined graph samples (i.e., the global graph), where additional task-specific relationship cues among graph samples can be extracted in an end-to-end manner. The experimental results show that the proposed GIG model and the GRM strategy generalize well on various graph analysis tasks, providing new state-of-the-art results on five out of seven benchmark graph datasets. Importantly, not only its vertex/edge updating functions are flexible to be customized from different existing GNNs but also it is robust to different settings. Our code is provided in the supplementary material for reproducibly purpose.
BibTeX
@misc{wang2022graph,
  author = {Jiongshu Wang and Siyang Song and Liru Chen and Jing Yang and Jiankang Deng and Hatice Gunes},
  title = {{Graph in Graph Neural Network}},
  year = {2022},
  eprint = {2407.00696},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.00696},
  howpublished = {OpenReview},
}
Figure