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 \to 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 \text{EdgeConservation}(f) + (1-\alpha) \cdot \text{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.