GripNet: Graph Information Propagation on Supergraph for Heterogeneous Graphs

Hao Xu, Shengqi Sang, Peizhen Bai, Laurence T. Yang, Haiping LuarXiv 2020 · arXiv

Introduction

Real-world data often manifests as complex heterogeneous graphs where nodes and edges represent diverse entities and relationships. Traditional Graph Representation Learning (GRL) methods, such as Relational Graph Convolutional Networks (RGCN), frequently encounter bottlenecks in scalability, semantic squashing, and the integration of multi-modal attributes. GripNet addresses these challenges by introducing a "divide and conquer" strategy that organizes heterogeneous graphs into a structured "supergraph."

The Supergraph Architecture

GripNet reimagines a heterogeneous graph as a Directed Acyclic Graph (DAG) of semantically coherent subgraphs. This architecture consists of two primary components:

  1. Supervertex: A subgraph containing nodes of a single category (e.g., proteins or books).
  2. Superedge: A directed information path between supervertices, typically represented as a bipartite subgraph.

By defining a clear flow of information from peripheral categories toward a target category, GripNet avoids the "loopy" propagation that often leads to over-smoothing in standard GNNs. This segregation also allows for flexible embedding dimensions; less critical categories can use memory-saving low dimensions while target categories use more expressive ones.

The GripNet architecture: (A) Input heterogeneous graph, (B) Supergraph abstraction, and (C) The internal structure of a GripNet layer.

The GripNet Layer

Each supervertex processes information through a modular layer designed for multi-source integration. The External Aggregation module pulls embeddings from parent supervertices, while the Internal Feature Layer processes local node attributes (such as text or labels). Finally, the Internal Aggregation module uses graph convolutions to synthesize these inputs, capturing the specific local structure of the category.

Experimental Evaluation

GripNet was evaluated across seven large-scale datasets, including the PoSE-series for biomedical interactions and the Freebase-series for knowledge graph integration. To enhance link prediction, the authors introduced Categorized Negative Sampling (CNS), which samples "fake" edges from within the same category to force the model to learn finer semantic distinctions.

Performance and Scalability

GripNet achieved state-of-the-art results in both link prediction (AUROC) and node classification (Micro-F1). Notably, the model demonstrated superior efficiency; it was significantly faster per epoch than RGCN and maintained a much lower GPU memory footprint.

A key finding from the Freebase experiments is GripNet's ability to leverage increasing heterogeneity. As more node types are added to the graph, GripNet’s performance improves more significantly than baseline models, suggesting it effectively integrates diverse data sources rather than being overwhelmed by them.

Micro-F1 performance as a function of the number of node types, demonstrating GripNet's superior data integration capabilities.

Conclusion and Future Work

GripNet provides a scalable and semantically aware framework for heterogeneous graph representation. By segregating different node types into a supergraph, it prevents information noise and handles raw attributes effectively. While current implementations require manual supergraph design based on domain knowledge, future work may involve automated discovery of optimal supergraph structures and the removal of the acyclic constraint to model bidirectional feedback loops.

Summary updated

BibTeX
@misc{xu2020gripnet,
  author = {Hao Xu and Shengqi Sang and Peizhen Bai and Laurence T. Yang and Haiping Lu},
  title = {{GripNet: Graph Information Propagation on Supergraph for Heterogeneous Graphs}},
  year = {2020},
  eprint = {2010.15914},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.15914},
}
Figure