Segmented Graph-Bert for Graph Instance Modeling

Jiawei ZhangarXiv 2020 · OpenReview

Abstract

In graph instance representation learning, both the diverse graph instance sizes and the graph node orderless property have been the major obstacles that render existing representation learning models fail to work. In this paper, we will examine the effectiveness of GRAPH-BERT on graph instance representation learning, which was designed for node representation learning tasks originally. To adapt GRAPH-BERT to the new problem settings, we re-design it with a segmented architecture instead, which is also named as SEG-BERT (Segmented GRAPH-BERT) for reference simplicity in this paper. SEG-BERT involves no node-order-variant inputs or functional components anymore, and it can handle the graph node orderless property naturally. What's more, SEG-BERT has a segmented architecture and introduces three different strategies to unify the graph instance sizes, i.e., full-input, padding/pruning and segment shifting, respectively. SEG-BERT is pre-trainable in an unsupervised manner, which can be further transferred to new tasks directly or with necessary fine-tuning. We have tested the effectiveness of SEG-BERT with experiments on seven graph instance benchmark datasets, and SEG-BERT can out-perform the comparison methods on six out of them with significant performance advantages.

Introduction

Most Graph Neural Networks (GNNs) excel at node-level tasks in massive, static graphs. However, "graph instance modeling"—where the goal is to classify or represent an entire small graph (e.g., a protein or a movie collaboration network)—presents two major hurdles: diverse graph sizes and the node orderless property. Unlike images with fixed pixel grids, graph instances in a single dataset can vary from a few nodes to hundreds. Furthermore, there is no inherent "first" or "last" node in a graph; a model must be permutation-invariant to produce consistent results regardless of node indexing.

Methods

The authors introduce SEG-BERT, which adapts the original GRAPH-BERT model through several key innovations designed to handle these challenges.

Order-Invariant Embeddings

To ensure the model doesn't rely on arbitrary node indices, relative positional embeddings were removed. Instead, SEG-BERT uses four types of initial embeddings:

  • Raw Features: Node attributes (if available).
  • Adjacency Neighborhood: Local connectivity patterns.
  • Node Degree: Captures local importance.
  • Weisfeiler-Lehman (WL) Codes: Captures the node's structural role within the global graph.

Segmented Architecture

To handle varying graph sizes, the model uses an "input portal" of size $k$. Three strategies fit graphs into this portal:

  1. Full-Input: Pads all graphs to the size of the largest one in the set.
  2. Padding/Pruning: Pads small graphs and truncates larger ones to a fixed $k$.
  3. Segment Shifting: Breaks large graphs into segments of size $k$ and slides the model across them, balancing efficiency with data integrity.
SEG-BERT Architecture Overview

Training Pipeline

The model uses unsupervised pre-training (reconstructing node attributes and graph structure) to learn general graph properties, followed by supervised fine-tuning for specific classification tasks. The integration of "Graph Residual" terms (G-Res) helps retain structural information across deep Transformer layers.

Results and Discussion

SEG-BERT was evaluated on seven classic graph classification benchmarks, including social graphs (IMDB-B, IMDB-M, COLLAB) and bio-graphs (MUTAG, PROTEINS, PTC, NCI1).

Performance Benchmarks

SEG-BERT outperformed all comparison baselines (including WL kernels, DGCNN, and CapsGNN) on 6 out of 7 datasets. On the IMDB-Binary dataset, SEG-BERT achieved a significant accuracy of 77.20%, compared to 71.69% for previous deep learning models like GCAPS-CNN.

Training and Testing Accuracy on IMDB Dataset

Strategy and Pre-training Efficiency

The "Full-Input" and "Segment Shifting" strategies generally yielded the highest accuracy as they preserve all graph data. Additionally, the unsupervised pre-training phase proved crucial for capturing structural nuances, especially in datasets lacking raw node attributes.

Conclusion

SEG-BERT demonstrates that Transformer-based architectures, when properly adapted with segmented inputs and order-invariant structural embeddings, can significantly outperform traditional convolutional GNNs in graph instance modeling. While the "Full-Input" strategy can be computationally expensive for very large graphs, the flexibility of segment shifting offers a viable path forward. Future research may explore cross-domain transfer learning, such as pre-training on social graphs to improve biological graph classification.

Summary updated

Abstract

In graph instance representation learning, both the diverse graph instance sizes and the graph node orderless property have been the major obstacles that render existing representation learning models fail to work. In this paper, we will examine the effectiveness of GRAPH-BERT on graph instance representation learning, which was designed for node representation learning tasks originally. To adapt GRAPH-BERT to the new problem settings, we re-design it with a segmented architecture instead, which is also named as SEG-BERT (Segmented GRAPH-BERT) for reference simplicity in this paper. SEG-BERT involves no node-order-variant inputs or functional components anymore, and it can handle the graph node orderless property naturally. What's more, SEG-BERT has a segmented architecture and introduces three different strategies to unify the graph instance sizes, i.e., full-input, padding/pruning and segment shifting, respectively. SEG-BERT is pre-trainable in an unsupervised manner, which can be further transferred to new tasks directly or with necessary fine-tuning. We have tested the effectiveness of SEG-BERT with experiments on seven graph instance benchmark datasets, and SEG-BERT can out-perform the comparison methods on six out of them with significant performance advantages.
BibTeX
@misc{zhang2020segmented,
  author = {Jiawei Zhang},
  title = {{Segmented Graph-Bert for Graph Instance Modeling}},
  year = {2020},
  eprint = {2002.03283},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.03283},
}
Figure