Learning on Non-Euclidean Graph Structures

This direction is split into other directions: graph-to-grid transformation, graph structural irregularity. Its last version stays readable and citable here.

Version 1 of 1458 papers488 conceptsfrozen 2026-10-04

Most of our modern machine learning toolkit was built for a world of grids and sequences. Images are regular grids of pixels; text is a linear sequence of tokens. In these domains, we benefit from a "Euclidean" structure: we know exactly where a neighbor is (one pixel to the right, one word ahead), and every sample in a dataset typically has the same dimensions.

Graphs—representing everything from social networks to molecular bonds—shatter these assumptions. As Edwin Hancock points out in Spectral Approaches to Learning in the Graph Domain, graphs lack a canonical ordering of elements and vary wildly in size and topology. This "non-Euclidean" nature is the central challenge of the field: how do you perform computation on data that has no fixed coordinates, no consistent neighborhood size, and no natural "average"?

The Absence of a Canonical Order

In an image, the top-left pixel is always the top-left pixel. In a graph, there is no "first" node. Any ordering we impose is arbitrary. This lack of a natural grid means that standard operations like convolution or pooling cannot be applied directly.

Joseph JaJa and Yu Jin argue in Learning Graph-Level Representations with Gated Recurrent Neural Networks that this irregularity necessitates specialized architectures. If you try to feed a graph into a standard Recurrent Neural Network (RNN), you must first decide which node to show the model first. Because there is no "correct" answer, the model's output might change simply because you shuffled the input list, even though the graph itself remains identical.

The Geometry of Relationships

Beyond the ordering problem, graphs do not inhabit a "flat" space. In Euclidean geometry, the distance between two points is a straight line. In the graph domain, "distance" is often topological—how many hops away is one node from another?

This makes even basic statistics difficult. As Xiaoyang Guo and Anuj Srivastava explain in A Quotient Space Formulation for Statistical Analysis of Graphical Data, you cannot simply "average" two graphs by adding their adjacency matrices. To find a mean or variance, you must account for the fact that graphs reside in a "quotient space" where different representations might refer to the same underlying structure. This geometric complexity is why Antonis Vasileiou and Christopher Morris found that standard generalization theories often produce "vacuous" results when applied to graphs; the math simply doesn't translate without a proper metric for measuring the distance between two non-Euclidean structures.

Adapting Operations to Irregularity

To bridge this gap, researchers have had to reinvent fundamental ML operations:

  • Pooling: In a CNN, pooling is easy: you just take a 2x2 square of pixels and shrink it. In a graph, there is no "square." Graph U-Nets solve this by using a trainable projection vector to "rank" nodes and select the most important ones to keep, effectively creating a learned downsampling method. Xing Gao further refined this in iPool by using information-theoretic measures to ensure that the "coarsened" graph retains the most vital structural data.
  • Attention: Standard Transformers compare every token to every other token. On a large graph, this is computationally impossible. Seongjun Yun and colleagues developed the Deformable Graph Transformer, which dynamically samples only the most relevant neighbors, mimicking the way deformable convolutions in computer vision adapt to the shape of an object.
  • Augmentation: You can't just "rotate" a graph to create new training data. Hongyu Guo proposed ifMixup, which pads graphs with dummy nodes to force them into a consistent size, allowing for the linear interpolation of features and edges—a creative "hack" to bring Euclidean-style data augmentation to the graph world.

The Scaling Frontier

As the field moves toward "Foundation Models," the non-Euclidean nature of graphs remains the primary bottleneck. While we can scale language models by simply adding more text, Neural Scaling Laws on Graphs shows that "data volume" in graphs is a multi-dimensional concept involving node counts, edge counts, and structural complexity.

The goal, as framed by Xin Wang in Automated Graph Machine Learning, is to move away from "manual alchemy"—where researchers hand-design architectures for specific graph types—toward automated systems that can navigate the irregular, non-Euclidean landscape on their own. By understanding the fundamental ways graphs break Euclidean rules, we can build models that are not just accurate, but truly "graph-native."

Papers in this version

Showing 60 of 458 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_learning_on_non_euclidean_graph_structur_6c599c64,
  title = {Learning on Non-Euclidean Graph Structures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-on-non-euclidean-graph-structures/rdr_6c599c64991545c3a88e43b10e1d60d4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_learning_on_non_euclidean_graph_structur_6c599c64_v1,
  title = {Learning on Non-Euclidean Graph Structures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-on-non-euclidean-graph-structures/rdr_6c599c64991545c3a88e43b10e1d60d4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}