The EDGE Language: Extended General Einsums for Graph Algorithms

Joel S. Emer; John D. Owens; Michael Pellauer; Nandeeka Nayak; Serban D. Porumbescu; Toluwanimi O. Odemuyiwa

arxiv: 2404.11591 · v3 · pith:P7TOEY4Fnew · submitted 2024-04-17 · 💻 cs.DS

The EDGE Language: Extended General Einsums for Graph Algorithms

Toluwanimi O. Odemuyiwa , Serban D. Porumbescu , Nandeeka Nayak , Michael Pellauer , Joel S. Emer , John D. Owens This is my paper

Pith reviewed 2026-05-24 01:34 UTC · model grok-4.3

classification 💻 cs.DS

keywords graph algorithmsEinsum notationtensor algebragraph-matrix dualityalgorithmic abstractionunified notationgraph computation

0 comments

The pith

The EDGE language expresses graph algorithms as extended Einsum tensor expressions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes EDGE as a single mathematical notation that writes graph algorithms using tensor algebra. It starts from the fact that graphs correspond directly to matrices and adds targeted extensions to standard Einsum notation so that typical graph operations become simple algebraic statements. A reader would care because the notation is meant to let people compare algorithms side by side, separate the description of what to compute from the details of how to compute it, and generate new algorithm variants simply by rewriting the expression.

Core claim

EDGE extends Einsum notation to support the operations common in graph algorithms while retaining the graph-matrix duality in which a graph is treated as a 2D tensor; any graph algorithm can therefore be written as one compact EDGE expression that can be compared, factored, or transformed algebraically.

What carries the argument

The EDGE language, which adds extensions to Einsum notation to capture graph operations while preserving the tensor-algebra foundation.

If this is right

Researchers can compare different algorithms and different implementations of the same algorithm by writing both as EDGE expressions.
Developers can separate the concerns of what to compute (the EDGE expression) from the lower-level details of how to compute it.
New algorithmic variants of a problem can be discovered by performing algebraic manipulations and transformations on a given EDGE expression.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same notation could be used inside tensor compilers to automatically generate specialized graph kernels from high-level expressions.
Seemingly unrelated graph algorithms might turn out to share identical or closely related EDGE forms, revealing hidden structural similarities.
The approach could be tested by taking a collection of textbook graph algorithms and checking whether each fits inside the stated EDGE extensions without remainder.

Load-bearing premise

The described extensions to Einsum notation are sufficient to express all common graph-algorithm operations without needing further ad-hoc additions.

What would settle it

A standard graph algorithm that cannot be written in EDGE without introducing new operations outside the extensions given in the paper.

Figures

Figures reproduced from arXiv: 2404.11591 by Joel S. Emer, John D. Owens, Michael Pellauer, Nandeeka Nayak, Serban D. Porumbescu, Toluwanimi O. Odemuyiwa.

**Figure 1.** Figure 1: Uncompressed 2D tensors, 𝐴 and 𝐵, where locations containing zero are empty. This also shows the tensor data spaces of 𝐴 and 𝐵, which are the set of data values at each coordinate of each tensor. EDGE expression, at the next level of concern, we can algebraically manipulate these Einsums (via substitution, reassociation, induction, etc.) to generate new variations of the original Einsum. Next, we can explo… view at source ↗

**Figure 2.** Figure 2: Fibertree representations of the uncompressed tensors in Figure [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: A directed graph, 𝐺, and some representations. The matrix values contain the edge ID, while the vertices are labelled alphabetically. tensor data spaces of 𝑀 ×𝐾 and 𝑁 ×𝐾, respectively. A projection into the tensor data space retrieves the corresponding value at a given point or region in the tensor. We have found this abstraction useful in describing transformations on tensors, such as partitioning, witho… view at source ↗

**Figure 4.** Figure 4: The example graph in Figure [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

**Figure 5.** Figure 5: Our view of the complex design space in tensor algebra. Shaded boxes indicate [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗

**Figure 6.** Figure 6: One common approach to factoring the design space in tensor algebra. Shaded boxes with side borders [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗

**Figure 7.** Figure 7: An instance of a factored design space with our extended general Einsums for graph algorithms. [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗

**Figure 8.** Figure 8: An example mapping for tiled dense matrix-matrix multiplication. [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗

**Figure 9.** Figure 9: Two example loop nests for Equation (18). Example 3: Single Operand Reduction Suppose we want to reduce the 𝑘 rank of a tensor by selecting the minimum value within the 𝑘 rank: 𝑍𝑚 = 𝐴𝑚,𝑘 :: Ü 𝑘 min (18a) (18b) At each point in the output tensor, we copy the corresponding 𝐴𝑚,𝑘 into the output location. If multiple 𝐴𝑚,𝑘 values correspond to the same 𝑚 location—which will be the case when the same 𝑚 fiber in … view at source ↗

**Figure 10.** Figure 10: (Top Left) A directed graph, 𝐺, with edge weights in red. (Top Right) A fibertree representation of the graph, 𝐺𝑠,𝑑 . The leaf values contain the edge weight. (Bottom Left) Resulting tensor, 𝑊 , that records the minimum outgoing edge weight for each vertex in the graph (see Equation (43)). (Bottom Right) Resulting tensor, 𝑁, that records the destination vertex ID of the outgoing edge with the minimum edge… view at source ↗

**Figure 11.** Figure 11: The two input graphs, 𝑊 and 𝐺, involved in the Einsum expression that finds the neighbors of the minimum weighted vertex (see Equation (45)). Red circles indicate the intersection of the 𝑑 rank, when 𝑠 = 0, between 𝑊 and 𝐺. The result is in output tensor 𝑍. 𝑍 does not contain vertex 𝑠 = 5 as its minimum weighted neighbor, vertex 6, has no neighbors. The values in 𝑍 indicate the cost of going from vertex 𝑠… view at source ↗

**Figure 12.** Figure 12: Top half: An EDGE expression using populate, where 𝑌 is a filtered version of 𝐴 that contains only 𝐴’s maximum three values (Eq. (47)). We show example input tensors 𝐴 and 𝑌, and a specific mapping specification on how execution should walk the 𝐷 iteration space. Bottom Half: The state of 𝑌 and its mutable 𝑑 rank after execution has processed certain points in the iteration space. Here, ≪ denotes the popu… view at source ↗

**Figure 13.** Figure 13: Execution steps after processing iteration space point [PITH_FULL_IMAGE:figures/full_fig_p042_13.png] view at source ↗

**Figure 14.** Figure 14: Grammar for the tensor declaration and initialization sections of the [PITH_FULL_IMAGE:figures/full_fig_p051_14.png] view at source ↗

**Figure 15.** Figure 15: Grammar for the Extended Einsum section of the [PITH_FULL_IMAGE:figures/full_fig_p051_15.png] view at source ↗

read the original abstract

In this work, we propose a unified abstraction for graph algorithms: the Extended General Einsums language, or EDGE. The EDGE language expresses graph algorithms in the language of tensor algebra, providing a rigorous, succinct, and expressive mathematical framework. EDGE leverages two ideas: (1) the well-known foundations provided by the graph-matrix duality, where a graph is simply a 2D tensor, and (2) the power and expressivity of Einsum notation in the tensor algebra world. In this work, we describe our design goals for EDGE and walk through the extensions we add to Einsums to support more complex operations common in graph algorithms. Additionally, we provide a few examples of how to express graph algorithms in our proposed notation. We hope that a single, mathematical notation for graph algorithms will (1) allow researchers to more easily compare different algorithms and different implementations of a graph algorithm; (2) enable developers to factor complexity by separating the concerns of what to compute (described with the extended Einsum notation) from the lower level details of how to compute; and (3) enable the discovery of different algorithmic variants of a problem through algebraic manipulations and transformations on a given EDGE expression.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

EDGE proposes some Einsum extensions for graphs with examples, but without semantics or rewrite rules the claims about algebraic manipulations and variant discovery do not hold up.

read the letter

The main takeaway is that this is a notation proposal that combines the graph-as-matrix view with extended Einsums, but the paper supplies no grammar, semantics, or transformation rules, so the advertised benefits of algebraic manipulation stay out of reach. The authors describe design goals, list some extensions for operations common in graphs, and show a handful of examples. That part is clear enough and gives a concrete way to write certain algorithms in tensor notation. The examples are the strongest part of what is presented, as they illustrate how the extensions might apply without obvious immediate gaps in the cases shown. The work is new in the specific combination and the choice of extensions, though it rests on two established ideas. The soft spot is exactly where the abstract makes its strongest claims. It says the notation provides a rigorous framework that lets researchers compare algorithms, factor complexity, and discover variants through manipulations. Without rewrite rules or a way to check that transformations preserve meaning, those steps cannot be demonstrated or verified. The stress-test note is on target here; the abstract alone already shows the gap, and nothing in the description suggests the full text closes it with formal content. This paper is aimed at people working on high-level graph abstractions or tensor compilers who might want a shared shorthand. A reader interested in notation ideas could pick up the examples and see if they spark something. Someone expecting a usable framework with provable properties will find the central argument unsupported. It is worth sending to peer review because notation work can still be useful to discuss even in preliminary form, but the authors will need to add the missing formal layer or scale back what the notation is said to enable.

Referee Report

2 major / 1 minor

Summary. The paper proposes the EDGE (Extended General Einsums) language as a unified abstraction for graph algorithms. It extends Einsum notation using the graph-matrix duality to express graph algorithms in tensor algebra, describes design goals and extensions for complex graph operations, provides examples, and claims this will enable easier algorithm comparison, complexity factoring by separating what from how, and variant discovery via algebraic manipulations.

Significance. If accompanied by formal semantics and rewrite rules that demonstrably support the claimed manipulations, EDGE could provide a useful unified notation for graph algorithms, aiding comparison and implementation separation in graph theory and tensor algebra. The proposal builds on established ideas but currently offers only informal descriptions and examples.

major comments (2)

[Abstract] Abstract: the claim that EDGE supplies a 'rigorous' mathematical framework supporting 'algebraic manipulations and transformations' for variant discovery is unsupported, as the manuscript supplies neither a grammar nor denotational semantics nor rewrite rules for the described extensions.
[Extensions] Section describing the extensions: without explicit transformation rules or a semantics that preserves meaning under the listed operations, it is impossible to verify that the notation remains unambiguous or that complexity factoring and variant discovery are actually enabled by the extensions.

minor comments (1)

The manuscript would benefit from an explicit comparison table or section contrasting EDGE with existing notations such as GraphBLAS or standard tensor libraries to clarify the precise scope of the proposed extensions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments highlighting the need for formal foundations. We agree that the current informal presentation does not fully substantiate the claims of a rigorous framework enabling algebraic manipulations, and we will revise the manuscript accordingly by adding explicit syntax, semantics, and rewrite rules.

read point-by-point responses

Referee: [Abstract] Abstract: the claim that EDGE supplies a 'rigorous' mathematical framework supporting 'algebraic manipulations and transformations' for variant discovery is unsupported, as the manuscript supplies neither a grammar nor denotational semantics nor rewrite rules for the described extensions.

Authors: We acknowledge that the abstract overstates the rigor of the current presentation. The manuscript grounds EDGE in the graph-matrix duality and illustrates extensions via examples, but does not supply a grammar, denotational semantics, or rewrite rules. In revision we will add a dedicated section defining the syntax of EDGE, a denotational semantics mapping expressions to tensor operations, and a small set of sound rewrite rules (e.g., associativity and distributivity transformations) that demonstrate how algebraic manipulation can produce algorithmic variants. These additions will directly support the abstract claim. revision: yes
Referee: [Extensions] Section describing the extensions: without explicit transformation rules or a semantics that preserves meaning under the listed operations, it is impossible to verify that the notation remains unambiguous or that complexity factoring and variant discovery are actually enabled by the extensions.

Authors: The observation is correct: the extensions section currently relies on descriptive text and examples rather than formal rules. To address this we will extend the section with (1) a compositional semantics that assigns meaning to each new operator while preserving equivalence to the underlying tensor expression, and (2) a collection of explicit transformation rules (including rules for re-association and operator reordering) together with brief proofs that the rules preserve semantics. These rules will illustrate both complexity factoring and variant discovery, allowing verification of the claimed benefits. revision: yes

Circularity Check

0 steps flagged

Notation proposal with no derivation chain or load-bearing reductions

full rationale

The paper introduces the EDGE notation by describing design goals, extensions to Einsum, and examples of expressing graph algorithms. It relies on the established graph-matrix duality and standard Einsum notation but presents no equations, predictions, fitted parameters, uniqueness theorems, or algebraic derivations. No steps reduce by construction to inputs, self-citations, or ansatzes. The work is a descriptive framework proposal, self-contained without any circular derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The proposal rests on two background ideas treated as given and introduces the EDGE notation itself as the new contribution.

axioms (2)

domain assumption A graph is simply a 2D tensor (graph-matrix duality)
Explicitly listed as one of the two foundational ideas in the abstract.
domain assumption Einsum notation provides a rigorous and expressive base that can be extended for graph algorithms
The paper builds all extensions on this existing tensor notation.

invented entities (1)

EDGE language (Extended General Einsums) no independent evidence
purpose: Unified abstraction and notation for graph algorithms
New syntactic and semantic extensions proposed in the paper.

pith-pipeline@v0.9.0 · 5756 in / 1296 out tokens · 24095 ms · 2026-05-24T01:34:56.045373+00:00 · methodology

discussion (0)

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Fast and Fusiest: An Optimal Fusion-Aware Mapper for Accelerator Design
cs.AR 2026-02 unverdicted novelty 7.0

FFM finds optimal fused mappings for tensor accelerators over 10,000 times faster than prior mappers while cutting energy-delay product by up to 1.8x versus hand-tuned designs.
Mambalaya: Einsum-Based Fusion Optimizations on State-Space Models
cs.AR 2026-04 unverdicted novelty 6.0

Mambalaya delivers 4.9x prefill and 1.9x generation speedups on Mamba layers over prior accelerators by systematically fusing inter-Einsum operations.