Source-linked AI summary
Relational inductive biases, deep learning, and graph networks
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, Razvan Pascanu
TL;DR
Modern AI struggles with combinatorial generalization, the ability to construct new inferences, predictions, and behaviors from known elements. This paper advocates integrating relational inductive biases with deep learning through graph networks, providing support for structured representations, relational reasoning, and improved generalization.
Problem
Modern AI remains limited in combinatorial generalization, the ability to construct new inferences, predictions, and behaviors from known elements.
Method
The paper analyzes relational inductive biases in deep learning and presents graph networks as a unified framework for computations over graph-structured data.
Results
Graph networks provide support for combinatorial generalization and suggest that explicit structure combined with flexible learning is viable for improving sample efficiency and generalization.
Takeaways & Limitations
The paper argues that integrating structured representations with flexible learning is a promising path toward more generalizable and interpretable AI.
Takeaways & Limitations
Graph networks cannot naturally represent recursion, control flow, and conditional iteration without additional assumptions.
Abstract
from arXiv · showhide
Artificial intelligence (AI) has undergone a renaissance recently, making major progress in key domains such as vision, language, control, and decision-making. This has been due, in part, to cheap data and cheap compute resources, which have fit the natural strengths of deep learning. However, many defining characteristics of human intelligence, which developed under much different pressures, remain out of reach for current approaches. In particular, generalizing beyond one's experiences--a hallmark of human intelligence from infancy--remains a formidable challenge for modern AI. The following is part position paper, part review, and part unification. We argue that combinatorial generalization must be a top priority for AI to achieve human-like abilities, and that structured representations and computations are key to realizing this objective. Just as biology uses nature and nurture cooperatively, we reject the false choice between "hand-engineering" and "end-to-end" learning, and instead advocate for an approach which benefits from their complementary strengths. We explore how using relational inductive biases within deep learning architectures can facilitate learning about entities, relations, and rules for composing them. We present a new building block for the AI toolkit with a strong relational inductive bias--the graph network--which generalizes and extends various approaches for neural networks that operate on graphs, and provides a straightforward interface for manipulating structured knowledge and producing structured behaviors. We discuss how graph networks can support relational reasoning and combinatorial generalization, laying the foundation for more sophisticated, interpretable, and flexible patterns of reasoning. As a companion to this paper, we have released an open-source software library for building graph networks, with demonstrations of how to use them in practice.
1 Introduction
The introduction argues that combinatorial generalization—constructing new inferences, predictions, and behaviors from known building blocks—should be a top priority for AI. It advocates combining structured representations and computations with deep learning’s flexibility, especially through relationally biased systems that operate on graphs.
- Motivation: Combinatorial generalization enables limitless compositions of a small set of elements into new inferences, predictions, and behaviors.The paper presents this ability as a key signature of human intelligence.
- Motivation: Structured representations and relational reasoning support human-like generalization by modeling entities, their interactions, and rules for composing them.The paper defines structured representations as capturing compositions and structured computations as operating over elements and their composition as a whole.
- Challenges: Modern deep learning has achieved rapid advances with minimal a priori assumptions, but struggles with structured reasoning, transfer beyond training conditions, and learning from small amounts of experience.These challenges are presented as demanding combinatorial generalization.
- Approach: The paper rejects a choice between structure and flexibility, advocating integrative approaches that combine their complementary strengths.This position is compared to biology’s joint use of nature and nurture.
- Contribution: Graph networks provide a framework for entity- and relation-based reasoning that unifies and extends graph-operating methods while learning representations and structure.Their relational inductive biases guide learning about entities and relations without requiring those representations to be specified in advance.
2 Relational inductive biases
Relational inductive biases constrain how entities and relations interact, helping learning prioritize solutions and generalize while potentially harming performance when mismatched. Standard deep-learning components express different such biases, but no default component handles arbitrary relational structure, motivating explicit entity–relation representations and interaction rules.
- Inductive biases: Inductive biases prioritize some solutions or interpretations over others, improving search and desirable generalization when appropriate but causing suboptimal performance when overly strong or mismatched.They impose assumptions about either the data-generating process or the solution space.
- Relational inductive biases: Relational inductive biases impose constraints on relationships and interactions among entities in a learning process.Analyzing them requires identifying entities, relations, and rules for composing them and computing their implications.
- Deep-learning components: Fully connected, convolutional, and recurrent layers encode distinct relational structures through connectivity, locality, stationarity, and reuse across processing steps.Recurrent layers apply the same update rule repeatedly over sequence steps, while convolutional layers reuse local kernels across inputs.
- Need for relational models: No default deep-learning component operates on arbitrary relational structure, so models need explicit entity and relation representations, interaction rules, and grounding in data.Entities generally lack a natural order, making invariance to ordering except where relations define it an important desired property.
3 Graph networks
The graph networks (GN) framework defines graph-to-graph functions for relational reasoning, generalizing several graph-based neural approaches and supporting compositional architectures. GNs represent entities as nodes, relations as edges, and system-level properties as global attributes, while reusing functions across graph elements to support combinatorial generalization.
- Graph networks framework: The GN framework defines functions for relational reasoning over graph-structured representations and generalizes graph neural network, MPNN, and NLNN approaches.It supports constructing complex architectures from simple building blocks.
- Graph networks framework: A GN block is a graph-to-graph module that computes over an input graph and returns an output graph.The framework emphasizes customizable architectures that express desired relational inductive biases.
- Graph representation: GNs represent entities as nodes, relations as edges, and system-level properties as global attributes.The graph is a directed, attributed multi-graph that can include multiple edges and self-edges.
- Combinatorial generalization: Per-edge and per-node functions are reused across all edges and nodes, allowing one GN to operate on graphs with different sizes and shapes.This reuse supports combinatorial generalization across varying numbers of nodes and edges and different edge connectivities.
4 Design principles for graph network architectures · 4.1 Flexible representations · 4.2 Configurable within-block structure
The graph-network framework supports learnable graph-to-graph approximators with flexible attribute and graph representations. Its within-block functions and information flow can be configured to express diverse architectures, including recurrent, message-passing, and attention-based variants.
- 4 Design principles for graph network architectures: The GN framework is agnostic to attribute representations and functional forms, while deep-learning implementations provide learnable graph-to-graph function approximators.This flexibility allows graph networks to serve as a general architectural framework rather than a single fixed model.
- 4.1 Flexible representations: Graph networks flexibly represent both attributes and graph structure, allowing global, node, and edge attributes to use vectors, tensors, sequences, sets, or graphs.The appropriate representation depends on the problem, such as image patches for images or word sequences for text.
- 4.1 Flexible representations: GN outputs can be tailored to tasks by focusing on edges, nodes, globals, or combinations of these outputs.The resulting outputs can be passed to other deep-learning components, and edge-focused, node-focused, and graph-focused networks support interaction decisions, physical reasoning, and graph-property prediction.
- 4.1 Flexible representations: GN inputs may specify relational structure explicitly or require entities and relations to be inferred or assumed from unstructured data.Examples include knowledge graphs and physical systems with known interactions, versus visual scenes, text corpora, source code, and multi-agent systems.
- 4.1 Flexible representations: Instantiating all possible directed edges when relations are unavailable can be prohibitive because the number of possible edges grows quadratically with the number of nodes.This motivates more sophisticated methods for inferring sparse structure from unstructured data.
- 4.2 Configurable within-block structure: Within a GN block, each mapping function’s input signature determines whether it uses global, node, and edge information, while the mapping functions determine the corresponding updates.MLPs commonly implement functions for vector attributes, CNNs suit tensor feature maps, and RNNs can provide recurrent updates with hidden state.
- 4.2 Configurable within-block structure: The GN formalism expresses diverse architectures through alternative function choices and within-block configurations, including MPNNs, NLNNs, and other graph-network variants.MPNNs map message, aggregation, update, and readout operations into GN functions; NLNNs use weighted neighbor aggregation, and multi-headed self-attention can be interpreted as typed edges.
- 4.2 Configurable within-block structure: NLNN attention updates each node using a normalized weighted sum of functions of neighboring node attributes, and can focus on interactions most relevant to the downstream task.The published NLNN formalism computes pairwise attention weights between nodes without explicitly including edges.
4.3 Composable multi-block architectures
Graph networks support composable architectures because each GN block maps a graph of edge, node, and global elements to the same structured form. This interface enables stacked, encode-process-decode, recurrent, and skip-connected designs with shared or unshared processing.
- Composable GN blocks: GN blocks preserve edge, node, and global graph elements, allowing one block’s output to serve directly as another block’s input.Elements not explicitly updated are passed through unchanged.
- Composable GN blocks: Arbitrary GN blocks can be composed with either unshared functions and parameters or shared ones analogous to unrolled recurrent processing.Shared configurations reuse the same functions and parameters across blocks.
- Encode-process-decode: Encode-process-decode architectures transform an input graph into a latent graph, apply a shared core M times, and decode the resulting graph.The encoder, core, and decoder can respectively represent initial interactions, repeated dynamics updates, and final readouts.
- Recurrent GN architectures: Recurrent GN architectures maintain a hidden graph while processing observed and producing output graphs at each step, supporting graph-sequence prediction such as dynamical-system trajectories.GN blocks are reused across time steps, and the core may also repeat shared internal sub-steps within each step.
- Additional design techniques: Additional designs include graph skip connections, gated merging of input and hidden graphs, and composition of distinct recurrent GN blocks around other GN blocks.Skip connections concatenate a block’s input and output graphs, while gating can replace simple concatenation.
4.4 Implementing graph networks in code
Graph networks are implemented with shared edge and node functions that support parallel computation, natural batching, and improved sample efficiency. The released TensorFlow/Sonnet library demonstrates a common GN architecture across shortest-path, sorting, and physical-prediction tasks.
- Implementation: Shared φe and φv functions allow edge and node computations to run in parallel, giving graph networks a naturally parallel structure.The nodes and edges can also be treated like the batch dimension in mini-batch training.
- Software library: The open-source TensorFlow/Sonnet library provides demonstrations for creating, manipulating, and training GNs on shortest-path, sorting, and physical-prediction tasks.Each demo uses the same GN architecture, illustrating its flexibility across graph-structured problems.
- Demonstrations: The shortest-path demo trains a GN through message-passing steps to label nodes and edges on the shortest path between two nodes.The model progressively refines its shortest-path prediction over the sequence of steps.
- Demonstrations: The sorting and physics demos use message passing to predict list order and future states of random mass-spring systems, respectively.Physics predictions can be fed back as inputs to roll out future trajectories over 50 timesteps.
- Implementation: Several independent graphs can be batched as disjoint components of a larger graph, with additional bookkeeping for their separate computations.This enables batching computations across multiple graphs without changing the graph-network formulation.
- Implementation: Reusing φe and φv improves sample efficiency because training examples correspond to edges and nodes across all graphs.A four-ball scene with all pairwise spring connections supplies twelve (4 × 3) contact-interaction examples.
4.5 Summary
Graph networks combine flexible representations, configurable within-block structure, and composable multi-block architectures. This framework is applicable across perception, language, and symbolic reasoning.
- Graph networks are built around flexible representations, configurable within-block structure, and composable multi-block architectures.These design principles combine into a highly flexible framework applicable across multiple domains.
5 Discussion
The paper argues that graph networks provide a structured foundation for combinatorial generalization and interpretable reasoning, while emphasizing their representational limits and unresolved challenges in acquiring and adapting graphs. More broadly, it advocates integrating deep learning with structured representations and complementary approaches toward human-like intelligence.
- Combinatorial generalization: Graph networks support combinatorial generalization by applying shared computations across entities and relations, enabling reasoning about novel systems assembled from familiar components.This entity- and relation-centric organization supports generalization across physical systems, decision-making tasks, optimization problems, planning problems, and unseen data.
- Limitations: Graph networks and message-passing networks cannot be guaranteed to distinguish certain non-isomorphic graphs, motivating alternatives that preserve more structural information.Covariant compositional networks were proposed as one such alternative to permutation-invariant approaches.
- Limitations: Graphs do not straightforwardly represent recursion, control flow, or conditional iteration, for which programs and computer-like processing can provide greater expressivity.Representing these notions minimally requires additional assumptions, such as interpreting abstract syntax trees.
- Open questions: Important open questions include converting raw sensory data into graphs and adaptively adding, removing, or splitting graph structure during computation.The paper notes that fully connected graphs are one approach for sensory data, while context-dependent structural changes remain under active investigation.
- Interpretability: Because graph-network entities and relations often correspond to human-understandable objects, their behavior can support more interpretable analysis and visualization.The paper connects this interpretability to the cognitive assumption that the world is composed of objects and relations.
- Broader agenda: The broader takeaway is to blend deep learning with structured representations and pursue complementary directions including programs, abstraction-focused model-based learning, meta-learning, and multi-agent interaction.The authors frame graph networks as a stepping stone toward human-like intelligence rather than a complete solution.
Appendix: Formulations of additional models
This appendix presents additional examples showing how published networks fit within the framework defined by Equation 1.
- Appendix: Formulations of additional models: The appendix provides further examples of published networks.These examples extend the paper’s discussion of model formulations.
- Appendix: Formulations of additional models: The examples demonstrate how published networks can fit the framework defined by Equation 1.The appendix uses Equation 1 as the organizing formulation.
- Appendix: Formulations of additional models: The appendix focuses on relating existing network architectures to the paper’s defined formulation.Its purpose is to show compatibility between published networks and the Equation 1 framework.
Interaction networks
Interaction Networks and the Neural Physics Engine use a full graph network without the global attribute to update edge properties. The formulation applies a neural network to concatenated edge and sender/receiver node attributes, with an extension producing global predictions.
- Interaction networks: Interaction Networks and the Neural Physics Engine use a full GN without the global attribute to update edge properties.This describes their graph-network configuration for edge updates.
- Interaction networks: The edge update is φe (ek, vrk, vsk, u) := fe (ek, vrk, vsk) = NNe ([ek, vrk, vsk]).The global input u is omitted from the edge-update function.
- Interaction networks: The work also extended the formulation to output global rather than per-node predictions.The extension changes the prediction scope from individual nodes to global outputs.
Non-pairwise interactions
GGS-NN generalizes graph updates by assigning each edge a type and applying type-specific neural networks. Its recurrent node updates use a GRU, followed by a global decoder that aggregates final node states.
- GGS-NN assigns each edge a type t_k ∈ {1, .., T} in a slightly generalized update formulation.
- The edge-update function applies a type-specific neural network NNe,tk to the source node state v_sk.
- Updates are applied recurrently with a GRU-based node network, then a global decoder computes a weighted sum of embedded final node states.Each NNe,tk has specific parameters.
- CommNet is presented in a slightly more general form described by Hoshen (2017).
Attention-based approaches
Attention-based approaches factor edge updates into a scalar pairwise interaction that produces an unnormalized attention term and a vector-valued non-pairwise term. The section relates this formulation to Transformer self-attention, multi-headed attention, Vertex Attention Interaction Networks, Graph Attention Networks, and relative position encodings.
- Attention-based approaches: Attention-based approaches factor φe into scalar pairwise and vector-valued non-pairwise terms, denoted αe(vrk, vsk) and βe(vsk), respectively.The scalar term returns the unnormalized attention value, while the vector-valued term depends on the sender vertex.
- Attention-based approaches: Transformer single-headed self-attention implements the non-local formulation using neural-network functions for query, key, and β terms.These functions can have different parameters and possibly different architectures.
- Attention-based approaches: Transformer multi-headed attention computes Nh parallel attention outputs with separately parameterized functions, then passes them to fv and concatenates them.The heads are indexed by h and use functions NNαquery, NNαkey, and NNβ.
- Attention-based approaches: Vertex Attention Interaction Networks resemble single-headed self-attention but use Euclidean distance for attentional similarity and shared parameters across attention-input embeddings.They also use the input node feature in the node-update function.
- Attention-based approaches: Graph Attention Networks resemble multi-headed self-attention but use a neural network as the attentional similarity metric with shared parameters across attention-input embeddings.The supplied passage identifies this as a similarity to multi-headed self-attention.
- Attention-based approaches: Shaw et al. extend multi-headed self-attention with relative position encodings representing spatial distances between nodes in a sequence or metric space.In graph-network notation, the relative encoding can be expressed as an edge attribute ek.
Belief Propagation embeddings
The section shows how Dai et al.’s structure2vec algorithm fits into the framework through a slight modification of the main update equation. In this formulation, edge features represent messages, with shared parameters for edge and node updates.
- Belief Propagation embeddings: Structure2vec can be incorporated into the framework by slightly modifying the main Equation 1.The paper presents this as a brief summary of Dai et al. (2016)’s general algorithm.
- Belief Propagation embeddings: Edge features represent messages between their receiver and sender, while one parameter set is learned for both edge and node updates.This modification uses the same learned parameters across the two update types.