Abstract
This paper introduces a novel recursive neural network (RNN) architecture designed to process Directed Acyclic Graphs with Labelled Edges (DAGs-LE). By encoding edge information directly into the state transition function via edge-weighted aggregation, the model overcomes the rigid "positional" constraints of traditional graph networks. This allows for the processing of nodes with variable numbers of children and unordered structures, such as chemical compounds. We provide theoretical proofs demonstrating that this architecture is a universal approximator for functions on DAGs and a generalization of existing positional models.
Introduction
In the early development of recursive neural networks, architectures were primarily optimized for Directed Positional Acyclic Graphs (DPAGs). In these structures, the specific "position" of a child node (e.g., "left child" vs. "right child") is critical to the state transition. However, many real-world data structures, such as molecular graphs or protein networks, do not possess a natural ordering of neighbors. Forcing an arbitrary order on these neighbors introduces artificial constraints and hinders the learning of structural symmetries. Furthermore, standard positional models often struggle with nodes that have a high or varying out-degree. This work addresses these limitations by proposing a model that is invariant to child ordering while effectively utilizing edge labels.
The Proposed Architecture
The core of the proposed model is a new state transition function, $\tilde{f}$, which computes a node's state based on its children in a manner independent of their number and order. This is achieved through edge-weighted aggregation. Instead of assigning children to fixed slots, the model computes a weighted sum of the children's states, where weights are determined by the labels of the connecting edges.
As illustrated in Figure 1, both the state transition function $\tilde{f}$ and the output function $g$ are implemented using multi-layer perceptrons (MLPs). The state of a node $v$ is calculated by combining the node's own label with the aggregated state of its children. Mathematically, the total contribution of the children is defined as: $$\overline{\mathbf{X}}(ch[v]) = \frac{1}{|ch[v]|} \sum_{i=1}^{|ch[v]|} \left( \sum_{j=1}^{k} \mathbf{H}_j \mathbf{L}_{(v, ch_i[v])}^{(j)} \right) \mathbf{X}_{ch_i[v]}$$ Here, $\mathbf{L}$ represents the edge label and $\mathbf{H}$ represents weight matrices. This formulation ensures that the contribution of each child is modulated by the specific properties of the link, maintaining parameter stability regardless of the node's out-degree.
Theoretical Foundations
The paper establishes several key theoretical properties of the DAGs-LE framework:
- Permutation Invariance: The summation-based aggregation naturally ensures the model is invariant to the order of a node's children, a critical requirement for general graph processing.
- Generalization of DPAGs: The authors prove that DAGs-LE is a generalization of older positional models. Any positional graph can be represented as a labeled-edge graph by encoding positions into edge labels.
- Universal Approximation: A primary contribution is the proof (Theorem 3) that this architecture is a universal approximator for measurable functions on the space of graphs. Given sufficient hidden units, the network can represent any continuous function mapping a graph to a real-valued output.
- Computational Power: Theorems 1 and 2 establish that the framework can represent any standard DPAG and simulate standard recursive neural networks, confirming it as a more flexible and powerful superset of existing models.
Conclusion and Future Work
While this work provides a robust theoretical foundation for processing DAGs with labeled edges, several avenues for future research remain. The current model is specifically designed for acyclic graphs; extending this logic to cyclic graphs is a significant challenge that points toward the development of modern Graph Neural Networks (GNNs). Additionally, while the model is parameter-efficient regarding out-degree, the computational overhead of nested summations for high-dimensional edge labels warrants further empirical investigation. Future work should also focus on applying these theoretical advantages to practical tasks such as molecular property prediction and social network analysis.
Summary updated