Structural Graph Embeddings via Homomorphism Counting

This direction is split into other directions: subgraph pattern analysis. Its last version stays readable and citable here.

Version 1 of 166 papers79 conceptsfrozen 2026-10-04

Standard Graph Neural Networks (GNNs) often struggle with a fundamental limitation: they are only as expressive as the Weisfeiler-Leman (WL) graph isomorphism test. This means they cannot distinguish between certain non-isomorphic graphs, such as those differing only in their number of cycles or cliques. To overcome this, a growing body of research suggests that we should represent graphs not just by their adjacency matrices, but by the frequency of small, recurring structural patterns.

The Graph as a Vector of Patterns

The core intuition behind this direction is that a graph's identity is defined by its constituent parts. Just as a molecule is defined by its functional groups, a graph can be decomposed into a vector of counts representing how many times specific "pattern graphs" (like triangles, paths, or stars) appear within it.

Martin Grohe posits in word2vec, node2vec, graph2vec, X2vec that this approach provides a robust theoretical basis for structural embeddings. Instead of learning black-box features, we map a graph into a feature space where each dimension corresponds to a specific sub-pattern. This transformation allows researchers to compare complex networks through a fixed-dimensional numerical framework.

Why Homomorphisms Matter

While "subgraph counting" is the intuitive goal, the mathematical engine often used is the graph homomorphism. A homomorphism is a map from a pattern graph $F$ to a target graph $G$ that preserves edge relationships. Unlike subgraph isomorphisms, homomorphisms are often easier to count and possess elegant mathematical properties.

Holger Dell, Martin Grohe, and Gaurav Rattan bridged combinatorial theory and machine learning in Lovász Meets Weisfeiler and Leman, showing that the WL algorithm is intimately tied to counting homomorphisms from trees. By expanding the set of patterns beyond trees to include cycles or cliques, we can strictly increase the expressive power of our models. Pascal Welke and colleagues further demonstrated in Expectation-Complete Graph Representations with Homomorphisms that by carefully choosing these patterns, we can distinguish any two non-isomorphic graphs in expectation while maintaining polynomial-time efficiency.

From Global Counts to Local Roles

Structural counting isn't just for classifying whole graphs; it can also define the "role" of an individual node. A node's structural identity can be captured by its orbit—its specific position within a motif. For example, a node might be the "center" of a star motif or a "bridge" in a chain.

Giorgos Bouritsas and Michael M. Bronstein introduced Graph Substructure Networks (GSN) in Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. By augmenting node features with counts of these orbits, they ensure that nodes are differentiated not just by their presence in a subgraph, but by their relative symmetry and functional position. This provides a granular structural language that Derek Greene and Eoghan Cunningham use in Surrogate explanations for role discovery on graphs to explain why a node is assigned a specific role, such as identifying interdisciplinary researchers in citation networks.

The Complexity of Counting

A natural question arises: how many patterns do we need to count, and how complex must they be? Matthias Lanzinger and Pablo Barcelo provided a definitive answer in On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters. They proved that the expressive power required to count a specific pattern is tied directly to the treewidth of that pattern. This allows researchers to precisely calibrate the trade-off between a model's complexity and its ability to "see" specific topological features like triangles or cycles.

Motif Densities as Graph Moments

Beyond simple counting, these patterns can be viewed as "moments" of an underlying generative process. Ali Azizpour and Santiago Segarra treat graph datasets as mixtures of different graphons (continuous limits of dense graphs). In From Moments to Models, they use motif densities—the normalized frequency of patterns—to disentangle these mixtures. Because graphs sampled from the same generative model will exhibit similar motif densities, these counts act as robust structural signatures that can cluster graphs by their global properties more effectively than standard latent embeddings.

Applications and Robustness

This structural approach has proven highly effective in domains where topology is paramount:

  • Biology: Na-Na Guan and colleagues use graphlet interactions to predict drug-miRNA pairs in GISMMA, capturing indirect relationships that simple similarity measures miss.
  • Privacy: Patrick Indri and Thomas Gärtner use noisy homomorphism densities to create embeddings that satisfy Differential Privacy while remaining effective for molecular property prediction in On the trade-off between expressivity and privacy.
  • Network Alignment: Ashley Wang demonstrates in Degree Matrix Comparison for Graph Alignment that even simple local fingerprints—like a sorted vector of a node's neighbors' degrees—can achieve near-perfect alignment accuracy without any external node attributes.

Papers in this version

Showing 60 of 66 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_structural_graph_embeddings_via_homomorp_f0f12e2f,
  title = {Structural Graph Embeddings via Homomorphism Counting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-graph-embeddings-via-homomorphism-counting/rdr_f0f12e2f100140b3ba3bb5ad7e616d82},
  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_structural_graph_embeddings_via_homomorp_f0f12e2f_v1,
  title = {Structural Graph Embeddings via Homomorphism Counting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-graph-embeddings-via-homomorphism-counting/rdr_f0f12e2f100140b3ba3bb5ad7e616d82/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}