Graph Representation via Subgraph and Homomorphism Counting

34 concepts30 papers1 proposal

Graphs are inherently non-Euclidean. Unlike images or text, they cannot be easily fed into standard machine learning models because they lack a fixed grid or sequence. To apply standard classifiers like Support Vector Machines or neural networks, we must map graphs into fixed-length numerical vectors—a process known as graph vectorization.

The core intuition behind subgraph frequency vectorization is simple: a graph can be characterized by its constituent parts. If we count how frequently various small "template" graphs (such as triangles, paths, or trees) appear within a larger target graph, we can construct a structural profile. This profile acts as a coordinate vector in a high-dimensional space, where each axis corresponds to a specific sub-pattern.

The Theoretical Foundation: Lovász and Homomorphisms

Why does counting small patterns give us a valid representation of a whole graph? The mathematical justification traces back to a profound result in graph theory developed by László Lovász: two graphs are isomorphic if and only if they have the exact same number of graph homomorphisms from all possible pattern graphs. A homomorphism is a structure-preserving map from a pattern graph to a target graph.

In Lovász Meets Weisfeiler and Leman, Dell et al. formalized this connection, showing how homomorphism counts align perfectly with classical graph isomorphism heuristics. Instead of counting all possible patterns—which is computationally intractable—modern approaches restrict the query set to specific families of patterns. For instance, Welke et al. demonstrated that by carefully selecting a bounded set of pattern graphs, one can construct "expectation-complete" embeddings that distinguish non-isomorphic graphs in polynomial time, breaking the traditional trade-off between expressiveness and speed. Similarly, Nguyen et al. leveraged these counts to build Graph Homomorphism Convolution (GHC), providing a permutation-invariant, theoretically universal framework for graph neural networks.

In his exploration of graph similarity, Martin Grohe highlights that comparing these "homomorphism density" profiles allows us to define a continuous measure of structural resemblance without needing to explicitly align nodes (Some Thoughts on Graph Similarity). However, this mapping comes with a catch: determining whether an arbitrary vector of numbers corresponds to a valid graph's homomorphism counts is highly complex, a challenge analyzed by Böker et al..

The Algorithmic Engine: Subtree Kernels and Weisfeiler-Leman

Counting arbitrary subgraphs is generally NP-hard. To make this approach practical, researchers focus on patterns that can be counted efficiently, such as trees or random walks.

The Weisfeiler-Leman (WL) graph isomorphism test serves as a powerful engine for this purpose. The WL test iteratively relabels a node based on the multiset of its neighbors' labels. Crucially, each unique label generated after $h$ iterations corresponds to a specific subtree pattern of height $h$ rooted at that node. By aggregating these labels across the entire graph, we can count the frequencies of these subtree patterns.

Borgwardt et al. utilized this insight to develop fast subtree kernels, reducing the computational complexity to linear time relative to the number of edges. This allows standard kernel methods to scale to massive graphs. As noted by Gärtner et al., these subtree pattern kernels enable standard learning algorithms to process structured data naturally by evaluating the inner product of these pattern frequency vectors. Extensions of this idea, such as those proposed by Da San Martino et al., convert more complex structures like directed acyclic graphs into trees to exploit the efficiency of subtree kernels.

Alternatively, instead of trees, one can count matching sequences of nodes via random walks. Nikolentzos et al. integrated this into deep learning by designing Random Walk Graph Neural Networks, which use differentiable kernels to compare input graphs against a set of learnable template graphs based on shared walk patterns. In natural language processing, Nguyen et al. applied random walk graph kernels to measure the structural similarity between local instance graphs and global type-level patterns, ensuring consistent information extraction.

From Global Graphs to Local Node Features

While counting subgraphs naturally yields a single vector for an entire graph, the same intuition can be localized to individual nodes. A node's identity in a network is largely defined by the shape of its immediate neighborhood.

To capture this, the Decomposition Feature Enhancement Procedure (DEEP) introduced by Tran-Van et al. maps whole-graph decomposition kernels down to the node level. By breaking a node's local neighborhood into sub-structures and counting them, the authors create expressive node-level features. This local fragment matching is also central to the Conjunctive Disjunctive Node Kernel proposed by Sperduti et al., which compares shared structural fragments within local neighborhoods to preserve local identity.

Similarly, the declarative language kLog, introduced by Frasconi et al., utilizes a kernel that decomposes relational data graphs into pairs of neighborhood subgraphs to measure structural similarity for linear classification. In social networks, Wang et al. demonstrated that decomposing local neighborhoods into discrete subtree patterns via the WL algorithm provides critical topological context for predicting user actions.

Geography of Graph Space and Applications

Vectorizing graphs via pattern frequencies allows us to map out the "geography" of large graph collections. For example, Ugander et al. analyzed massive social networks by treating them as collections of small, induced subgraphs, mapping them into a coordinate system where each axis represents a specific subgraph frequency. This revealed structural boundaries and extremal properties of real-world networks. In a similar vein, Abrahão et al. used a high-dimensional structural feature space to evaluate how closely different community detection algorithms match real-world network communities.

The practical utility of this paradigm spans multiple domains. In bioinformatics, Huan et al. successfully classified protein structural families by mining coherent, statistically significant 3D subgraphs and tallying their occurrences into fixed-length vectors. For molecular data, Blockeel et al. bypassed exhaustive pattern searches by using a randomized library of sampled subgraphs to generate bitvectors for classification.

Finally, this explicit, count-based representation offers unique advantages for privacy. Because the representation does not rely on continuous, iterative message-passing, Indri et al. showed that one can inject noise directly into homomorphism densities to achieve formal Differential Privacy guarantees while preserving the structural expressivity required for downstream molecular property prediction tasks.

Key Foundational Work

Image Classification with Segmentation Graph Kernels (2007) — contributed 1 concept elements to this direction.
Accurate Classification of Protein Structural Families Using Coherent Subgraph Analysis (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_subgraph_frequency_vectorization_8e5924ce,
  title = {subgraph frequency vectorization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subgraph-frequency-vectorization/rdr_8e5924ce7c7245cf9ebe5126e364c4d0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_subgraph_frequency_vectorization_8e5924ce_v1,
  title = {subgraph frequency vectorization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subgraph-frequency-vectorization/rdr_8e5924ce7c7245cf9ebe5126e364c4d0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake