Typed Graph Networks

Pedro H. C. Avelar, Henrique Lemos, Marcelo O. R. Prates, Marco Gori, Luís C. LambarXiv 2019 · arXiv

Abstract

Typed Graph Networks (TGNs) provide a unifying formalization for graph-based neural architectures, simplifying the representation of complex relational data by assigning "types" to vertices. By treating edges, hyperedges, and global attributes as distinct node types, TGNs naturally support hypergraphs and generalize various Graph Neural Network (GNN) variants. This paper details the TGN formalization and demonstrates its expressiveness across several combinatorial optimization tasks.

Introduction

Deep learning on relational data has seen a proliferation of architectures, including Message-Passing Neural Networks (MPNNs), Relational Networks, and Graph Networks. While frameworks like DeepMind's "Graph Network" have attempted to unify these models, they often impose a rigid ontology of nodes, edges, and global attributes. Such structures struggle with higher-order relations like hyperedges. We propose Typed Graph Networks (TGNs), which move away from hardcoded ontologies toward a flexible, type-centric approach.

The TGN Formalization

The core innovation of TGNs is the partitioning of a graph's vertices into $N$ distinct types. In this framework, "everything is a node." Edges and global attributes are not distinct architectural primitives but are instead modeled as specific vertex types. A global attribute, for example, is simply a node type that connects to every other node in the graph.

Message Passing and Updates

Communication in a TGN is governed by type-specific parameters. Each vertex type $i$ possesses its own embedding space, an update function $\phi_i$, and message-generation functions $\mu_{ij}$ for communicating with type $j$. Connectivity is defined via adjacency matrices between types. This allows for natural hypergraph support; for instance, a "clause" node in a SAT problem can connect to an arbitrary number of "literal" nodes.

The TGN message-passing and update cycle across time steps.

Experimental Evaluation

To evaluate the expressiveness of the TGN formalization, the authors implemented solvers for several combinatorial problems using a custom Python/TensorFlow library. The library allows users to define networks via simple dictionaries mapping type names to embedding sizes and message functions.

Boolean Satisfiability (SAT)

By defining "Literal" and "Clause" types, the TGN framework successfully replicated NeuroSAT capabilities. The model achieved approximately 85% accuracy on complementary SAT/UNSAT instances by passing messages between these two distinct node types.

Training curves for the NeuroSAT task, illustrating the convergence of loss and accuracy over epochs.

Decision TSP and Centrality

The TGN framework successfully modeled the Decision Traveling Salesperson Problem (TSP), achieving 80% test accuracy. Furthermore, it reached 89% accuracy in predicting graph centrality rankings. These results underscore the flexibility of the type-centric approach in mapping problem-specific ontologies directly to network structures without architectural boilerplate.

Conclusion

Typed Graph Networks offer a streamlined perspective on GNN architecture, reducing the need for complex hardcoding when dealing with non-standard relational data. While current implementations are restricted to specific update and message functions (e.g., LSTMs and MLPs), the underlying formalization provides a powerful and intuitive abstraction for future research in combinatorial optimization and relational reasoning.

Summary updated

BibTeX
@misc{avelar2019typed,
  author = {Pedro H. C. Avelar and Henrique Lemos and Marcelo O. R. Prates and Marco Gori and Luís C. Lamb},
  title = {{Typed Graph Networks}},
  year = {2019},
  eprint = {1901.07984},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.07984},
}
Figure