A Graph Diffusion Algorithm for Lexical Similarity Evaluation

Karol Mikula, Mariana Sarkociová Remešíková · 2025

Read A Graph Diffusion Algorithm for Lexical Similarity Evaluation by Karol Mikula, Mariana Sarkociová Remešíková (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-06816.txt.

Introduction

Karol Mikula and Mariana Sarkociova Remesikova present an algorithm for measuring language similarity in this 2025 paper. The input is a list of concepts with translations in many languages. Each reference language belongs to a known cluster. The goal is to place a target language against those clusters.

For each concept, distances between translations are computed from sound transcriptions. A weighted directed graph is built with languages as nodes. A diffusion equation on that graph then assigns each language a set of scores. Scores run from zero to one and read as cluster membership shares. A case study on European languages shows the method at work. It suits regions where languages have mixed through long contact.

Catalog record

CREATORKarol Mikula, Mariana Sarkociová Remešíková
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-06816

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Graph Diffusion Algorithm for Lexical Similarity Evaluation Karol Mikula, Mariana Sarkociová Remešíková Abstract In this paper, we present an algorithm for evaluating lexical similarity between a given language and several reference language clusters. As an input, we have a list of concepts and the corresponding translations in all considered languages. Moreover, each reference language is assigned to one of c c language clusters. For each of the concepts, the algorithm computes the distance between each pair of translations. Based on these distances, it constructs a weighted directed graph, where every vertex represents a language. After, it solves a graph diffusion equation with a Dirichlet boundary condition, where the unknown is a map from the vertex set to ℝ c \mathbb{R}^{c} . The resulting coordinates are values from the interval [ 0 , 1 ] [0,1] and they can be interpreted as probabilities of belonging to each of the clusters or as a lexical similarity distribution with respect to the reference clusters. The distances between translations are calculated using phonetic transcriptions and a modification of the Damerau-Levenshtein distance. The algorithm can be useful in analyzing relationships between languages spoken in multilingual territories with a lot of mutual influences. We demonstrate this by presenting a case study regarding various European languages. Keywords data classification, lexical similarity, graph diffusion, weighted graph Laplacian, phonetic distance 1 Introduction Lexical similarity is one of the key criteria in examining relationships between languages. Given two languages and a list of concepts, it measures the ratio of similar corresponding terms in that particular part of vocabulary. The resemblance can be measured using various characteristics of words and various metrics based on those characteristics. In computational linguistics, there are several common approaches to lexical similarity evaluation. One of the basic properties of any word is its etymology and the etymology based lexical similarity has been used for decades in lexicostatistics. This discipline is based on the ideas of Morris Swadesh [ 28 , 29 ] and typically uses his list of basic concepts, the so-called Swadesh list. This approach has been widely applied in classifying languages and supporting hypotheses regarding their origin, for example in the works of Dyen et al. [ 6 ] , Gray and Atkinson [ 9 ] , Kassian et al. [ 14 ] , Petroni and Serva [ 25 ] . Besides etymology, phonetic similarities are often explored and used to classify languages and dialects. The related algorithms measure distances between phonetic transcriptions of words or sentences, most typically using Levenshtein distance or some of its modifications, less commonly the Euclidean distance or some other metric. Some examples are classification of Irish Gaelic dialects by Kessler [ 15 ] , Norwegian dialects by Heeringa [ 10 ] , Dutch dialects by Nerbonne et al. [ 22 ] and Indonesian languages by Nasution et al. [ 21 ] . Another example is prediction of mutual intelligibility of Chinese dialects by Tang and Van Heuven [ 30 ] or exploring the similarity of a Native American language with several other well-known languages in the work of Daniels et al. [ 4 ] . To mention some other approaches, a character-based classification of Japanese dialects and Slavic languages can be found in the work of Sato and Heffernan [ 27 ] . A completely different procedure is proposed in the paper of Lin [ 17 ] , where the similarity of words is evaluated based on the context in which they typically appear. The main motivation for our work was exploring the similarity in specific subsets of the lexis and between languages that are spoken in multilingual territories. Such languages often contain parts of vocabulary that are in discordance with their standard overall classification. Identifying these parts can help understand the language and its evolution and possibly even provide an insight in the way of life of their speakers and their relationships with other ethnic groups. The algorithm that we present is based on solving the stationary diffusion equation with a boundary condition on a weighted directed graph. The vertices of the graph represent the languages included in the experiment, which are of three different types. The first group consists of languages with known classification and these are divided into several clusters (language branches). The second group contains languages that we want to classify because we assume a notable foreign influence or resemblance with languages from different branches and we want to analyze it. Finally, for each of the involved language clusters, we add one hypothetical language which is used to set the boundary condition of the model. Given a list of concepts, we solve our model equation for each concept individually. The edge weights are re-computed in each step based on the phonetic distance between the corresponding words. As the solution, we obtain a Euclidean graph that reflects the similarities between all corresponding words from all considered non-hypothetical languages. The overall lexical similarity between languages is then evaluated based on all individual results. Our procedure is inspired by the work of Mikula et al. [ 19 ] that introduces a clustering and classification algorithm based on non-stationary non-linear diffusion on graphs, with no boundary condition. The algorithm was successfully applied in classification of Natura 2000 habitats using satellite images. The vertices of the involved graph correspond to the samples measured by a satellite. Based on similarity of the measured features, the coordinates of the samples in the feature space are evolved by diffusion, either forward or backward. As a result, new measurements could be classified and inserted in the already existing clusters. Contrarily to the satellite imaging measurements, in case of words and languages, it is not straightforwardly clear what the feature space should be. In our case, each experiment includes languages from several distinct clusters (language families or branches). Therefore, we set the features of a word to be its probabilities of belonging to each of the clusters. Or, in other words, the values of the features represent the similarity distribution of each classified word with respect to the reference language clusters. The overall output of our algorithm is also understood in this way – rather than providing the lexical similarity in the form of the ratio of similar words, we obtain the lexical similarity distribution for the given language and the considered language clusters. There are many algorithms for clustering and classification operating with probabilities and it is also not uncommon to use the graph Laplacian for clustering on graphs, see e.g. [ 1 , 5 , 32 ] . However, to the best of our knowledge, the procedure described in this paper has not been previously used. Its advantages are its simple and elegant formulation and a rather non-complicated implementation. Equally importantly, our clustering and classification algorithm only needs a low-key input: any type of data and an arbitrary way of measuring the distances between them. The data need not be expressed in any feature coordinate system, they are simply elements of a data set. Our paper consists of several parts. First, we formulate the basic mathematical model. After, since our experiments use the phonetic transcription of words, we describe the semi-metric used for measuring the distance between such transcriptions. Finally, we

Read the complete text