Asynchronous Algorithmic Alignment with Cocycles

Andrew Dudzik, Tamara von Glehn, Razvan Pascanu, Petar Velickovic

Abstract

Classical algorithms, such as Dijkstra’s or Bellman-Ford, are fundamentally sparse and asynchronous, yet standard Graph Neural Networks (GNNs) operate through synchronous, global updates. This mismatch forces GNNs to learn inefficient "identity" operations for inactive nodes, hindering generalization. This paper introduces a formal mathematical framework using category theory—specifically monoids and 1-cocycles—to design "asynchrony-invariant" GNNs. By ensuring node updates satisfy specific algebraic conditions, we achieve closer algorithmic alignment, resulting in superior performance and out-of-distribution robustness on the CLRS-30 benchmark.

Introduction

Algorithmic alignment suggests that a neural network generalizes better when its structural components mirror the underlying logic of the task it is intended to solve. While GNNs are naturally suited for graph-based reasoning, a significant discrepancy remains: standard GNNs are inherently synchronous. In every layer, every node aggregates messages and updates its state simultaneously. In contrast, most classical algorithms are asynchronous; only a subset of nodes undergoes meaningful state changes at any given step.

When a synchronous GNN attempts to emulate an asynchronous algorithm, it must learn to perform the identity function for the majority of nodes at each step. This requirement imposes a significant learning burden. To address this, we propose a framework that shifts GNN design from a global, synchronous perspective to a node-centric, asynchrony-invariant view using the language of monoids and cocycles.

Theoretical Framework: Cocycles and Monoids

To redefine how GNNs process information, we utilize tools from abstract algebra and category theory. We treat node states and messages as elements of a monoid—a set equipped with an associative binary operation and an identity element. This structure allows us to model "instruction queues" where the specific timing or ordering of operations can vary without altering the final result.

The 1-Cocycle Condition

The core of our contribution is the application of the 1-cocycle condition from group cohomology. A node update function that satisfies this condition ensures that the final output remains mathematically identical regardless of how incoming messages are grouped or when they are processed.

To visualize this, consider the analogy of "addition with carry." When adding a sequence of numbers, the "carry" bit must be passed correctly whether you add the numbers two at a time, all at once, or in staggered groups. A 1-cocycle-compliant GNN node generates "arguments" for its neighbors that remain consistent across different synchronization regimes, effectively making the network robust to the "stuttering" of updates.

Levels of Asynchrony Invariance

We categorize GNN architectures into three levels of increasing invariance:

  1. Level 1 (L1): Employs a commutative aggregator (e.g., sum or max). This ensures the model is invariant to the order of incoming messages within a single step.
  2. Level 2 (L2): Incorporates an associative and idempotent update function (e.g., max). Idempotence is crucial; it allows a node to be invariant to repeated calls or redundant updates.
  3. Level 3 (L3): Utilizes a "monoid multimorphism" for the message function. This allows the network to handle partial updates correctly, ensuring that the composition of messages over time equals the message of the composed input.

To implement L3, we utilize a Log-Semiring Bilinear Layer. This acts as a smooth approximation of "tropical" algebra (max-plus), which is the natural mathematical language for dynamic programming algorithms.

Experimental Evaluation

We evaluated our framework using the CLRS-30 benchmark, a suite of 30 classical algorithms designed to test neural algorithmic reasoning. Our experiments focused on out-of-distribution (OOD) performance, where models are tested on graphs significantly larger than those encountered during training.

Key Results

  • Hierarchy Validation: Experimental performance strictly followed the theoretical levels. L3 models (log-semiring) outperformed L2 (max-max), and both significantly surpassed standard L1 GNNs.
  • Robustness and Generalization: Asynchrony-invariant models demonstrated a superior ability to capture the underlying logic of algorithms. This was particularly evident in OOD scenarios, where L3 models maintained high accuracy on large-scale graphs that caused standard GNNs to fail.
  • Variance Reduction: For highly sequential algorithms like Depth First Search (DFS), the L3 architecture significantly reduced performance variance, leading to more stable and reliable training.

Discussion and Insights

A critical insight of this work is that a GNN does not need to be executed asynchronously to benefit from these properties. By constructing a synchronous GNN that is invariant to asynchrony, we create a model that is inherently more robust. Furthermore, this framework provides a rigorous theoretical justification for existing successful architectures, such as PathGNNs, which we demonstrate to be a specific instance of a 1-cocycle-compliant GNN.

Limitations and Future Work

While the use of tropical algebra (max-plus) aligns perfectly with many algorithms, it often results in sparse gradients, making training difficult. Our use of the "logsumexp" approximation mitigates this, but direct training of "hard" tropical layers remains an open challenge. Additionally, while this work focuses on isotropic GNNs (where messages depend only on the sender), extending cocycle theory to anisotropic GNNs (where messages depend on both sender and receiver) is a primary objective for future research.

Finally, while we have focused on making GNNs invariant to the update schedule, future work could explore learning an optimal "scheduler" to determine which nodes should update at any given time to maximize computational efficiency.

Summary updated

BibTeX
@inproceedings{dudzik2023asynchronous,
  author = {Andrew Dudzik and Tamara von Glehn and Razvan Pascanu and Petar Velickovic},
  title = {{Asynchronous Algorithmic Alignment with Cocycles}},
  booktitle = {LoG},
  year = {2023},
  url = {https://openreview.net/forum?id=ba4bbZ4KoF},
}
Figure