Abstract
Ontology matching is a critical task for achieving semantic interoperability in the Semantic Web. This paper introduces a novel graph-based matching framework centered on Affinity-Preserving Random Walks (APRW). Unlike traditional random walks that suffer from the "Internet Democracy" problem—where low-affinity outlier nodes exert undue influence—our approach utilizes an absorbing node to maintain the relative strength of structural affinities. We further propose the Mapping-Oriented Random Walk (MORW), which dynamically incorporates 1-to-1 matching constraints during the iteration process using the Stable Marriage algorithm. Experimental results on the Ontology Alignment Evaluation Initiative (OAEI) benchmarks demonstrate that MORW achieves state-of-the-art performance, rivaling systems that utilize extensive external resources while remaining purely structural and lexical.
Introduction
The independent development of ontologies often leads to semantic heterogeneity, where different graphs describe the same domain using divergent labels or structures. Reconciling these differences is typically framed as a graph-matching problem. However, standard random walk algorithms (e.g., PageRank) often fail due to the "Internet Democracy" effect: row-normalization of transition probabilities can artificially inflate the importance of outlier nodes with few connections, potentially obscuring true "inlier" mappings. This paper addresses this challenge by preserving affinity through an absorbing node and enforcing logical constraints dynamically.
Methodology
The proposed matching process operates on an association graph where nodes represent candidate pairs (e.g., matching a class in Ontology A to one in Ontology B) and edges represent structural affinities.
Affinity-Preserving Random Walk (APRW)
To mitigate the Internet Democracy problem, we introduce an absorbing node. Instead of standard row-normalization, we identify the maximum degree ($d_{max}$) in the graph. For nodes with fewer connections, the "missing" probability mass is directed to the absorbing node. Once a walker enters this node, it remains there, effectively filtering out weak evidence and preserving the relative affinity of strong candidate matches.
Mapping-Oriented Random Walk (MORW)
While most systems apply 1-to-1 constraints as a post-processing step, MORW integrates them into the walk itself. We utilize a "personalized jump" vector that is updated iteratively. By applying the Stable Marriage algorithm during the walk, the system identifies likely true mappings and biases the random walk to "jump" toward these nodes. This reinforcement mechanism suppresses noise and strengthens high-quality matches in real-time.
Experimental Evaluation
The approach was evaluated using datasets from the Ontology Alignment Evaluation Initiative (OAEI), specifically the Benchmark-Biblio 2012 and Benchmark-Biblioc 2013 datasets. These ontologies, described in OWL-DL, encompass complex bibliographic relations including classes, properties, and hierarchical structures.
Results and Discussion
The MORW model was compared against several baselines, including the Vector Space Model (VSM) and Row-Normalized Random Walks (RNRW), as well as top-tier OAEI participants.
As shown in the results, MORW achieved an F-measure of 0.866 on the 2012 benchmark and 0.864 on the 2013 benchmark. Notably, it significantly outperformed RNRW, which suffered from the Internet Democracy problem, yielding F-measures 10-20% lower than MORW. Furthermore, MORW proved competitive with resource-heavy systems like MapSSS and YAM++, despite MORW's reliance solely on internal structural and lexical data (TF-IDF).
Conclusion
This paper demonstrates that preserving structural affinity and dynamically enforcing matching constraints can significantly enhance ontology alignment. The use of an absorbing node effectively filters outliers, while the integration of the Stable Marriage algorithm provides a powerful guiding signal for the random walk. Future work will explore the integration of supervised learning to refine transition probabilities and the selective use of external background knowledge for extremely sparse ontologies.
Summary updated