Graph embedding
Graph embedding is a concept in graph theory and computer science with two primary interpretations. In classical graph theory, it refers to a representation of a graph on a surface (such as a plane or sphere) or in higher-dimensional space where vertices are mapped to distinct points and edges to non-intersecting curves, preserving adjacency relations without crossings; this is central to topics like planarity and genus.[1] In the modern machine learning context, also known as graph representation learning, it involves mapping nodes, edges, or substructures of a graph G = (V, E) into a low-dimensional vector space of dimension d (where d \ll |V|), such that the structural properties and relational information of the original graph are preserved as much as possible. This process transforms high-dimensional, sparse graph data into dense, continuous embeddings that facilitate downstream machine learning tasks by enabling efficient computation on relational structures.[2][3] The classical notion of graph embedding dates back to the 19th century with studies on planar graphs, evolving through key results like Kuratowski's theorem in 1930; detailed historical context is provided in the Fundamentals section. In parallel, the development of representation learning techniques traces back to the early 2000s, when initial efforts focused on dimensionality reduction for non-relational data using similarity graphs, such as Laplacian eigenmaps for manifold learning. A significant shift occurred around 2010 with the advent of direct graph embedding methods that leverage auxiliary information and deep learning to capture complex network proximities, addressing challenges in scalability and expressiveness for large-scale graphs.[2] By the mid-2010s, foundational algorithms like DeepWalk (2014), which applies random walks and SkipGram models to learn node representations preserving second-order proximity, and node2vec (2016), which introduces biased random walks for flexible neighborhood exploration, established random walk-based approaches as a cornerstone.[2] Graph embedding methods in representation learning are broadly categorized into several paradigms, including matrix factorization techniques that decompose graph adjacency or Laplacian matrices to capture global similarities (e.g., LINE for edge preservation); random walk-based methods that sample paths to model local microstructures; deep learning approaches such as Graph Convolutional Networks (GCNs, 2017) for message passing on node features and Graph Attention Networks (GATs, 2017) for weighted neighbor aggregation; and edge reconstruction models like TransE (2013) for knowledge graph embeddings via translational distances. More recent advancements incorporate graph isomorphism networks (GINs, 2019) for distinguishing graph structures and graph transformers (e.g., Graphormer, 2021) for long-range dependencies.[2][3] Detailed discussions of topological and geometric embeddings appear in their respective sections. These embeddings, particularly in the representation learning sense, enable a wide array of applications across domains, including node-level tasks like classification and clustering in social networks, edge-level predictions such as link prediction and recommendation in e-commerce systems, and graph-level analyses like molecular property prediction in bioinformatics or visualization in network analysis. In knowledge graphs, embeddings support entity resolution and relation inference, while in dynamic settings, they aid anomaly detection in temporal networks.[2][3] Trends in representation learning since 2020 have emphasized self-supervised and contrastive learning paradigms to reduce reliance on labeled data, with methods like InfoGraph (2020) maximizing mutual information between graph views, alongside extensions to heterogeneous, multimodal, and temporal graphs for real-world scenarios involving diverse data modalities or evolving structures. As of 2025, further advancements include the integration of large language models (LLMs) with knowledge graph embeddings to enhance semantic understanding and reasoning.[3][4]Fundamentals
Definition and Terminology
In graph theory, particularly within topological graph theory, a graph embedding refers to a representation of a graph G = (V(G), E(G)) on a host structure, such as a surface or Euclidean space, where vertices are mapped to distinct points and edges to curves or line segments connecting those points, such that adjacency is preserved: for vertices u, v \in V(G), if (u, v) \in E(G), then the images f(u) and f(v) are adjacent via the image of the edge under the mapping f. In such embeddings, edges may intersect only at shared endpoints (vertices), ensuring no improper crossings in the interior. This preservation extends to non-adjacency conditions in certain contexts, where non-adjacent vertices map to non-adjacent points in the host.[5] Key terminology includes the crossing number of a graph, denoted \operatorname{cr}(G), which is the minimum number of edge crossings over all possible drawings of G in the plane.[6] The genus of a graph g(G) is the smallest integer g such that G admits an embedding without crossings on an orientable surface of genus g (e.g., a sphere for g=0, a torus for g=1).[7] A straight-line embedding represents edges as straight line segments between vertex points, as guaranteed for any planar graph by Fáry's theorem. Minor-closed families are classes of graphs closed under taking minors (subgraphs obtained by deleting vertices/edges and contracting edges), such as the family of planar graphs, which exclude K_5 and K_{3,3} as minors.[8] Embeddings are typically required to be injective, meaning no two vertices map to the same point, distinguishing them from immersions, where the mapping is locally injective but edges may cross without overlapping interiors (though vertices remain distinct). The concept originates from topology and early graph theory studies in the 1930s, particularly investigations into planar graphs by Kazimierz Kuratowski, who characterized non-planar graphs via forbidden subdivisions, and Hassler Whitney, who introduced combinatorial approaches to planarity.[5] It is important to distinguish these topological and geometric embeddings from the notion of graph embedding in machine learning and representation learning, where the term refers to mapping nodes (and sometimes edges or subgraphs) into low-dimensional vector spaces to capture structural similarities for tasks like node classification or link prediction, often via methods such as random walks or graph neural networks.[9] In contrast, graph theory embeddings focus on spatial or surface placements preserving combinatorial or geometric properties without dimensional reduction for computation.[6]Historical Context
The concept of graph embedding originated in the field of topology during the early 20th century, where mathematicians sought to characterize graphs that could be drawn on a plane without edge crossings. In 1930, Kazimierz Kuratowski established a foundational result by proving that a graph is non-planar if and only if it contains a subdivision of K_5 or K_{3,3}, providing a forbidden subgraph criterion for planarity.[10] This theorem marked a pivotal milestone in understanding the embeddability of graphs in the plane. Two years later, in 1932, Hassler Whitney offered a dual characterization of planar graphs using cycle spaces and abstract duality, further solidifying the topological foundations of graph embeddings.[11] These early contributions by Kuratowski and Whitney shifted focus from geometric drawings to abstract combinatorial properties, influencing subsequent developments in graph theory. Building on these topological insights, mid-20th-century research emphasized constructive and computational aspects of embeddings. In 1948, István Fáry demonstrated that every planar graph admits a straight-line embedding in the plane without crossings, bridging abstract planarity with explicit geometric realizations.[12] This result complemented earlier work and highlighted the feasibility of non-curved representations. By the 1960s and 1970s, attention turned to embeddings on higher-genus surfaces, culminating in the 1968 solution to the Heawood conjecture by Gerhard Ringel and J. W. T. Youngs, who proved the map color theorem for orientable surfaces by constructing explicit genus embeddings for complete graphs.[13] Concurrently, the computational turn arrived with the 1974 linear-time planarity testing algorithm by John Hopcroft and Robert Tarjan, which efficiently determines embeddability and produces an embedding when possible, enabling practical applications in algorithm design. Frank Harary played a key role in this era through his standardization of graph theory terminology and exploration of embeddings in topological contexts, as detailed in his influential 1969 textbook. From the 2000s onward, graph embedding evolved into an interdisciplinary tool, particularly in machine learning for representation learning on networks. This shift was propelled by the need to encode graph structures into low-dimensional vector spaces for tasks like node classification and link prediction. A seminal advancement came in 2014 with Bryan Perozzi et al.'s DeepWalk, which adapted word2vec techniques to generate node embeddings via random walks on graphs, capturing structural similarities in social and biological networks.[14] This work marked the transition from pure mathematical topology and algorithms to data-driven AI applications, fostering a surge in scalable embedding methods for large-scale graphs.Topological Embeddings
Combinatorial Embeddings
In combinatorial graph theory, an embedding of a graph is specified abstractly by a rotation system, which consists of a cyclic ordering of the edges incident to each vertex, independent of any geometric realization. This system defines the facial walks of the embedding by tracing cycles formed by successive edges in the rotations and their reverses, thereby determining the faces and the associated dual graph.[15] A key property of such embeddings on orientable surfaces is the generalized Euler characteristic, given byV - E + F = 2 - 2g,
where V is the number of vertices, E the number of edges, F the number of faces, and g the genus of the surface. Additionally, the handshaking lemma for faces holds: the sum of the degrees of the faces equals $2E, ensuring that each edge bounds exactly two faces. An embedding is valid if the rotation system produces closed facial walks and satisfies the Euler characteristic for some genus g \geq 0.[15][16] Two combinatorial embeddings are equivalent if there exists a homeomorphism of the underlying surface that preserves the rotation systems at each vertex. For planar graphs (embeddable on the sphere, where g=0), Whitney's theorem establishes that every 3-connected graph admits a unique embedding up to reflection and homeomorphism of the sphere.[17] Representative examples illustrate these concepts: a cycle graph C_n (for n \geq 3) embeds combinatorially on the sphere with two faces (the interior and exterior), satisfying Euler's formula with V = n, E = n, and F = 2. In contrast, the complete graph K_5 cannot embed on the sphere but admits multiple combinatorial embeddings on the torus (g=1), such as a rectangular embedding where faces are quadrilaterals.[15][18]