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.
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:
- 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.
- GIG Hidden Layers: These layers consist of two interleaved modules:
- GIG Vertex-level Updating (GVU): This updates the edges and vertices within each individual graph-vertex, focusing on local structural information.
- Global-level GIG Sample Updating (GGU): This allows different graph-vertices to communicate via the proxy vertices, making the local representations global context-aware.
- GIG Output Layer: A final pass that combines local and global updates to produce the final prediction.
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