Graph Embedding

Maps high-dimensional, sparse adjacency matrices into a compact, dense vector of typically 50 to 300 dimensions. This transformation preserves the graph's topological structure while making it computationally tractable for downstream machine learning models. The goal is to minimize reconstruction error, ensuring that nodes with similar local neighborhoods end up close together in the latent space.

The fundamental objective is to encode the graph's structure into the embedding space. This is achieved by defining a similarity function in the original graph (e.g., first-order proximity, second-order proximity via shared neighbors, or random walk co-occurrence) and then optimizing the embeddings so that the dot product or cosine similarity between two vectors approximates this original similarity.

Embedding techniques operate at multiple granularities:

• Node Embeddings: Represent individual entities (e.g., a person, a paper).
• Edge Embeddings: Represent relationships, often derived by combining the embeddings of the incident nodes (e.g., via Hadamard product).
• Graph Embeddings: Represent an entire subgraph or the whole graph as a single fixed-length vector for graph classification tasks.

Transductive methods (e.g., DeepWalk, node2vec) generate embeddings only for nodes seen during training. Adding a new node requires retraining the entire model. Inductive methods, primarily Graph Neural Networks (GNNs) like GraphSAGE, learn an aggregation function that generates an embedding for any unseen node based on its local neighborhood features and structure, enabling dynamic, evolving graphs.

Algorithms like DeepWalk and node2vec treat truncated random walks on a graph as the equivalent of sentences in a language. They then apply a skip-gram model (originally from NLP) to learn node embeddings by predicting the context (neighboring nodes) within these walks. node2vec extends this with biased walks that interpolate between Breadth-First Search (BFS) and Depth-First Search (DFS) to capture homophily and structural equivalence.

Used primarily for Knowledge Graph Embeddings, these models interpret relationships as translations in the embedding space. The seminal model, TransE, operates on the principle that for a valid triple (head, relation, tail), the equation head + relation ≈ tail should hold. Scoring functions based on this translational distance are used to rank the plausibility of missing links for knowledge base completion.

The systematic application of link prediction to populate missing facts in enterprise knowledge graphs. Combines embedding-based scoring with logical rules to infer new triples. Key approaches:

• Rule injection: Constrains embeddings to satisfy Horn clauses (e.g., bornIn(x,y) ∧ locatedIn(y,z) → nationality(x,z))
• Type-aware embeddings: Incorporates entity type hierarchies to prevent nonsensical predictions
• Temporal embeddings: Models time-aware relations for evolving facts (e.g., CEO tenure periods)

Graph embeddings enable fuzzy entity matching by representing records as vectors where cosine similarity approximates semantic equivalence. Techniques include:

• Siamese GNNs: Twin networks that learn distance metrics between entity pairs
• Locality-Sensitive Hashing (LSH): Buckets similar embeddings for efficient approximate nearest neighbor search at scale
• Contrastive learning: Trains embeddings to pull matching records together and push non-matching records apart in vector space