When aligning two different networks—whether they are multilingual knowledge graphs, database schemas, or social networks—our first instinct is to look at textual labels. If a node in Graph A is labeled "User_123" and a node in Graph B is labeled "User_123", they probably match. But what happens when labels are missing, encrypted, or written in entirely different languages?
The key insight behind structural similarity propagation is that topology is a signature. If an entity in one graph corresponds to an entity in another, their local neighborhoods must share a structural configuration. This creates a recursive definition of similarity: two nodes are similar if their neighboring nodes are also similar. By treating graph alignment as a diffusion process, similarity scores can "flood" through the edges of a network, resolving identities based purely on relational architecture.
The Similarity Flooding Mechanism
To operationalize this recursive intuition, classical alignment frameworks model the matching process as a fixpoint computation over a graph.
Consider the framework introduced by Wei Hu et al. in GMO: A Graph Matching for Ontologies. They represent schemas as bipartite graphs where similarity scores are iteratively updated using a matrix-based process. In each iteration, when two entities (such as classes) are found to be similar, a fraction of their similarity score propagates to their associated properties and neighboring nodes. This recursive logic allows similarity to flow across different entity types until the scores stabilize.
Mathematically, this can be framed as a system of linear equations where the similarity of a node pair is a function of the similarities of its adjacent pairs. As demonstrated by Fatiha Saïs et al. in LN2R a knowledge based reference reconciliation system: OAEI 2010 results, running an iterative solver allows confidence in attribute-level matches to propagate globally. This network effect ensures that local structural consistency drives the entire system toward a globally optimal alignment.
[Node A1] <--- initial seed match ---> [Node B1]
| |
(edge) (edge)
v v
[Node A2] <--- propagated similarity -> [Node B2]
Propagating from Seed Matches
In many real-world scenarios, we are not matching entirely blind; we possess a small set of known correspondences, or "seed alignments." Structural propagation acts as a force multiplier for these seeds, expanding a partial mapping across the rest of the network.
In their work on De-anonymizing Social Networks, Arvind Narayanan et al. demonstrated that anonymous users could be re-identified by leveraging a small set of known mappings from an auxiliary graph. The algorithm looks at the neighbors of already-mapped nodes: if an anonymous node shares a significant number of connections with nodes whose identities are already resolved, that identity propagates to the anonymous node.
This neighborhood-centric expansion can be executed via highly scalable heuristics. For example, Simon Lacoste-Julien proposed a simple greedy matching framework (SIGMa: simple greedy matching for aligning large knowledge bases) that treats alignment like a fire propagation process. By evaluating only the local neighborhoods of newly matched entities, the algorithm avoids the prohibitive computational cost of exhaustive pairwise comparisons across massive datasets. Similarly, Qian Zheng et al. utilized an iterative "Link Flooding Algorithm" in RiMOM2013 results for OAEI 2013 to propagate instance-level matches through RDF triples, progressively resolving sparse datasets by identifying groups where most components already match.
Robustness to Missing Metadata
The defining advantage of topology-based alignment is its resilience to the absence of surface features. In GMO: A Graph Matching for Ontologies, Wei Hu et al. proved that structural matching algorithms could maintain an F-measure as high as 0.95 even when all property and class names were replaced with completely random strings.
However, unconstrained propagation can introduce noise; an incorrect initial match can cascade across the network, corrupting downstream alignments. To preserve precision in weakly informative scenarios, long-running ontology matching systems like Lily—developed across multiple evaluation campaigns by researchers such as Wenyu Wang in Lily results for OAEI 2016 and Yunyan Hu et al. in Lily results for OAEI 2020—introduce strict filtering and termination conditions. By constraining the flooding process, these systems ensure that similarity only spreads through highly confident structural pathways, preventing error accumulation.
Bridging Classical Flooding and Deep Learning
While classical methods rely on explicit matrix iterations, modern entity alignment frequently employs Graph Neural Networks (GNNs) and joint knowledge embeddings. Remarkably, these paradigms share the same underlying mechanics.
Zequn Sun et al. formally bridged this gap in What Makes Entities Similar? A Similarity Flooding Perspective for Multi-sourced Knowledge Graph Embeddings. They proved that popular neural entity alignment models are mathematically equivalent to classical similarity flooding. By reframing embedding learning as a search for a structural similarity fixpoint, they showed that GNNs inherently discover isomorphic subgraphs by aggregating relational contexts into vector spaces.
To handle real-world graphs that are non-isomorphic or structurally divergent, advanced architectures expand their receptive fields. For instance, the AliNet framework by Zequn Sun et al. (Knowledge Graph Alignment Network with Gated Multi-Hop Neighborhood Aggregation) introduces gated multi-hop neighborhood aggregation. This allows the model to look beyond immediate neighbors to find structural commonalities across disparate graphs.
When training labels are completely unavailable, local structural fingerprints like graphlets can be used to automatically bootstrap high-quality pseudo-labels. As shown by Yang Zhou et al. in Effective Federated Graph Matching, comparing these local structural fingerprints allows supervised alignment networks to function in entirely unsupervised, privacy-preserving federated environments. Whether implemented via classical matrix iterations or modern neural message passing, the core principle remains identical: the shape of a network is its most reliable identity.
Key Foundational Work
The Results of Falcon-AO in the OAEI 2006 Campaign (2006) — contributed 2 concept elements to this direction.
GMO: A Graph Matching for Ontologies (2005) — contributed 2 concept elements to this direction.
Result of Ontology Alignment with RiMOM at OAEI'06 (2006) — contributed 1 concept elements to this direction.