graph alignment
**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**
| Method | Approach | Key Feature |
|--------|----------|-------------|
| **IsoRank** | Spectral + neighbor voting | Eigenvalue-based global alignment |
| **GRAAL (Graph Aligner)** | Graphlet-degree signature matching | Topology-based, no attributes needed |
| **FINAL** | Matrix factorization with attribute consistency | Attribute + topology jointly |
| **REGAL** | Implicit embedding alignment | Scalable to million-node graphs |
| **Neural Alignment (PALE, DeepLink)** | Cross-network GNN embedding | Learned alignment from anchor nodes |
**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.