Source-linked AI summary
word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data
Martin Grohe
TL;DR
Vector embeddings make structured data compatible with standard machine learning, but their theoretical foundations remain comparatively underdeveloped. The paper surveys practical embedding methods and develops connections centered on Weisfeiler-Leman algorithms and homomorphism vectors. It concludes by identifying theoretical relationships, expressiveness boundaries, computational challenges, and open directions for relational-data embeddings.
Problem
Structured-data embeddings are widely used, yet theoretical understanding is limited, especially for structural information beyond graph distances.
Method
The paper surveys practical embedding techniques and connects them to Weisfeiler-Leman algorithms and homomorphism vectors as theoretical frameworks.
Results
The paper establishes theoretical connections among embedding techniques, Weisfeiler-Leman methods, homomorphism vectors, kernels, and GNN expressiveness.
Takeaways & Limitations
These connections provide tools for analyzing structural embeddings and motivate future research on querying and embedding higher-arity relational data.
Takeaways & Limitations
Theoretical expressiveness remains bounded: for every k, non-isomorphic CFI graphs exist that k-WL does not distinguish.
Abstract
from arXiv · showhide
Vector representations of graphs and relational structures, whether hand-crafted feature vectors or learned representations, enable us to apply standard data analysis and machine learning techniques to the structures. A wide range of methods for generating such embeddings have been studied in the machine learning and knowledge representation literature. However, vector embeddings have received relatively little attention from a theoretical point of view. Starting with a survey of embedding techniques that have been used in practice, in this paper we propose two theoretical approaches that we see as central for understanding the foundations of vector embeddings. We draw connections between the various approaches and suggest directions for future research.
1 Introduction
The paper frames vector embeddings as numerical representations that make structured data usable with standard machine learning, while highlighting major theoretical gaps concerning expressivity, complexity, dimension, and structural information.
- Vector representations convert symbolic structured data into numerical vectors required by typical machine-learning algorithms.
- Existing embedding research is broad but predominantly empirical and application-specific, with limited theory for structural information beyond graph distances.
- The paper studies expressivity, asking which properties of objects embeddings preserve and whether latent-space geometry represents meaningful relations.
- Embedding design raises complexity questions about computation, efficient algorithms, and retrieving semantic information through queries.
- Choosing latent dimension involves a potential trade-off between high expressivity and low dimension, possibly reflecting an inherent low-dimensional structure.
- The paper focuses on structural embeddings for graphs, relational structures, and their nodes, connecting Weisfeiler-Leman methods with homomorphism vectors.
2 Embedding Techniques
The paper surveys metric, similarity-based, neural, and relational embedding techniques, then relates their design choices to theoretical notions of kernels, invariance, and expressiveness.
- 2.1 From Metric Embeddings to Node Embeddings: Node embeddings commonly approximate graph distances or similarities, using methods such as multidimensional scaling, Isomap, and Laplacian eigenmaps.
- 2.1 From Metric Embeddings to Node Embeddings: Cosine-similarity objectives minimize ∥XX⊤−S∥F, with the basic Frobenius-norm problem solvable through singular value decomposition.
- 2.1 From Metric Embeddings to Node Embeddings: Figure 2 contrasts node embeddings derived from adjacency-matrix SVD, similarity-matrix SVD, and node2vec.
- 2.1 From Metric Embeddings to Node Embeddings: DeepWalk and node2vec interpret short random walks as word-like co-occurrence sequences, extending word2vec ideas to graphs.
- 2.2 Graph Neural Networks: GNNs use shared message-passing parameters to handle arbitrary graph sizes and isomorphism invariance, but their expressiveness is limited.
- 2.3 Knowledge Graph and Relational Structure Embeddings: Knowledge-graph methods encode relations geometrically, including TransE translations and RESCAL bilinear forms fitted against relation adjacency matrices.
- 2.3 Knowledge Graph and Relational Structure Embeddings: Higher-arity relational embeddings remain comparatively underexplored, with incidence-structure transformations and tuple-as-sentence approaches offered as alternatives.
- 2.4 Graph Kernels: Kernel embeddings connect positive-semidefinite similarity functions with inner products in potentially infinite-dimensional Hilbert spaces.
3 The Weisfeiler-Leman Algorithm
The Weisfeiler-Leman algorithm iteratively refines node colours to capture structural information, with variants for labels, weights, matrices, and higher-dimensional tuples. Its expressiveness connects to logic, algebraic fractional isomorphism, graph kernels, homomorphism counts, and GNNs, while remaining limited for some non-isomorphic graphs.
- 3.1 1-Dimensional Weisfeiler-Leman: 1-WL iteratively refines an initial node colouring until nodes sharing a colour have matching neighbour counts for every colour.The algorithm returns the resulting stable colouring.
- 3.1 1-Dimensional Weisfeiler-Leman: 1-WL provides certificates of non-isomorphism when two graphs have different numbers of vertices of some colour, but it misses some non-isomorphic graphs.It fails on a 6-cycle and two disjoint triangles, although it distinguishes almost all graphs in a precise probabilistic sense.
- 3.2 Variants of 1-WL: Weighted 1-WL refines nodes using sums of edge weights, and matrix WL applies this idea to a weighted bipartite graph representing matrix entries.The matrix version was used for dimension reduction in linear programs with many symmetries or regularities.
- 3.3 Higher-Dimensional WL: k-WL colours k-tuples rather than vertices, propagating information between tuples that differ in one coordinate, with runtime O(n^(k+1) log n).Higher-dimensional WL is more powerful than 1-WL, but remains unable to distinguish certain non-isomorphic CFI graphs for every fixed k.
- 3.4 Logical and Algebraic Characterisations: 1-WL has logical and algebraic characterisations: k-WL corresponds to bounded-variable counting logic, while fractional isomorphism corresponds exactly to indistinguishability by 1-WL.Fractional isomorphisms are computable in polynomial time, unlike the integer formulation associated with graph isomorphism.
- 3.5 and 3.6: WL colours can be viewed as rooted trees, linking local structure aggregation to homomorphism counts and explaining why standard GNNs are at most as expressive as 1-WL.Higher-dimensional GNNs provide an invariant architecture designed to increase expressiveness.
4 Counting Homomorphisms
The paper presents homomorphism counts as structural graph embeddings and develops their connections to Weisfeiler-Leman indistinguishability, logical equivalence, graph similarity, and node embeddings.
- Homomorphism vectors: Homomorphism counts capture structural information through substructure patterns such as walks, paths, cycles, and trees.Walks are homomorphic images of paths, while paths are embedded path graphs.
- Homomorphism vectors: Homomorphism vectors embed a graph G by counting homomorphisms from each graph F in a chosen class F into G.The feature space dimension equals the size of F; infinite classes yield potentially infinite-dimensional embeddings and associated kernels.
- Indistinguishability: Cycle homomorphism counts equal adjacency-matrix power traces, so equality of all cycle counts characterizes co-spectral graphs.For a cycle C_k, hom(C_k, G) = trace(A^k), linking homomorphism counts to adjacency eigenvalues.
- Indistinguishability: For paths, equality of homomorphism vectors is equivalent to a rational solution of the graph-isomorphism equations without the nonnegativity constraint.For trees, the corresponding characterization uses a nonnegative rational solution, also called fractional isomorphism.
- Node embeddings: Homomorphism-based node embeddings correspond to 1-WL and can, in principle, support direct query answering while remaining structural rather than distance-based.The correspondence extends to graph neural networks, and the node embedding is inductive rather than tied to one fixed graph.
5 Similarity
The paper examines whether homomorphism-based embeddings can induce meaningful graph similarity measures, connecting them to matrix-norm distances while highlighting computational and semantic limitations. It also identifies relaxed distances and equivalences as promising directions for further study.
- Homomorphism embeddings may induce natural similarity measures when combined with suitable inner products on the latent space.
- Similarity can be assessed by comparing adjacency matrices after optimally permuting rows and columns to account for graph isomorphism.
- ℓ1-based distances have edit-distance interpretations, measuring edge flips needed to obtain an isomorphic graph or the maximum flips incident to one vertex.
- The semantic relevance of graph distances depends on application context, and matrix-based measures are not clearly generalisable to relational structures.
- Matrix-norm graph distances are highly intractable, with even tree distances being NP-hard to compute and hard to approximate.Cut-distance is comparatively better behaved and can be approximated within a factor of 2.
- Relaxing permutations to doubly stochastic matrices yields efficiently solvable convex minimisation problems for many norms, but only pseudo-metrics.Nonisomorphic graphs can have relaxed distance zero when they are fractionally isomorphic.
6 Concluding Remarks
The paper surveys graph and relational-structure embeddings and develops Weisfeiler-Leman and homomorphism-vector approaches to clarify their theory and practical connections. It concludes that similarity measures, higher-arity relations, and querying embedded data remain open challenges.
- The paper surveys embedding techniques and develops Weisfeiler-Leman and homomorphism-vector approaches that generate embeddings and clarify methods such as graph neural networks.
- Many questions remain open, particularly concerning similarity measures for graphs and relational structures.
- Database research needs embeddings for higher-arity relations and semantics for answering queries approximately under imprecision and randomness.