Graph Alignment (Network Alignment) is the global optimization problem of finding a node mapping between two networks that maximizes the topological and attribute overlap — determining how two different graphs "fit together" structurally, with critical applications in de-anonymizing social networks, transferring functional annotations between biological networks, and integrating heterogeneous knowledge bases that describe the same entities with different graph structures.

What Is Graph Alignment?

• Definition: Given two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, graph alignment seeks a mapping $f: V_1 o V_2$ that maximizes a combined objective of topological consistency (mapped edges in $G_1$ correspond to edges in $G_2$) and attribute similarity (mapped nodes have similar features). The objective is: $max_f alpha cdot ext{EdgeConservation}(f) + (1-alpha) cdot ext{NodeSimilarity}(f)$, where $alpha$ balances structural and attribute-based alignment.
• Global vs. Local Alignment: Local alignment methods match individual nodes based on their immediate neighborhoods (degree, neighbor attributes). Global alignment methods optimize the overall structural correspondence considering the entire graph topology — a node is matched not just because it looks locally similar but because its global position in the network is consistent with the overall mapping.
• Anchor Nodes: When some node correspondences are known in advance (anchor nodes or seed nodes), the alignment problem becomes significantly easier — the known mappings constrain the search space and propagate alignment information to neighboring nodes. Many practical alignment algorithms begin with a small set of anchor nodes and iteratively expand the alignment.

Why Graph Alignment Matters

• Social Network De-anonymization: The seminal Narayanan & Shmatikov attack demonstrated that an anonymized social graph (Netflix viewing history) could be de-anonymized by aligning it with a public graph (IMDb ratings) — matching user nodes across networks to recover private identities. This proved that graph structure alone leaks identity, motivating differential privacy for graph data.
• Biological Network Integration: Different experimental techniques produce different interaction networks for the same set of proteins — PPI networks from yeast two-hybrid, co-expression networks from RNA-seq, genetic interaction networks from synthetic lethality screens. Graph alignment integrates these complementary views by finding the consistent node mapping across networks, producing a unified interaction map.
• Knowledge Base Fusion: Large knowledge graphs (Wikidata, Freebase, DBpedia) describe overlapping sets of entities with different schemas and relationships. Aligning these knowledge bases identifies equivalent entities (entity resolution) and merges complementary knowledge, creating a more complete knowledge graph than any individual source.
• Cross-Lingual Transfer: In multilingual NLP, word co-occurrence graphs in different languages can be aligned to discover translation equivalences — words that occupy structurally similar positions in their respective language graphs are likely translations of each other, enabling unsupervised bilingual dictionary induction.

Graph Alignment Methods

Graph Alignment is superimposing networks — overlaying one complex relational structure onto another to discover where they match and where they diverge, enabling cross-network knowledge transfer, privacy attacks, and multi-source data integration through structural correspondence.