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.
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.
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