Given a graph and set of input labels, Uniform Metric Labeling (UML) assigns every node to a label, so that the assignment minimizes: (i) the total dissimilarity between each node and its assigned label, and (ii) the sum of edge weights between neighbors at different labels. The problem has attracted significant attention due to its numerous applications in image processing, language modeling and hypertext classification. In the data management community, UML has been applied for tasks related to social networks. Although there exist several experimental evaluations of UML algorithms, they focus exclusively on computer vision tasks for relatively small graphs with specific topology, representing images (e.g., each node corresponds to a pixel that is connected to its four or eigh...[ Read more ]

Given a graph and set of input labels, Uniform Metric Labeling (UML) assigns every node to a label, so that the assignment minimizes: (i) the total dissimilarity between each node and its assigned label, and (ii) the sum of edge weights between neighbors at different labels. The problem has attracted significant attention due to its numerous applications in image processing, language modeling and hypertext classification. In the data management community, UML has been applied for tasks related to social networks. Although there exist several experimental evaluations of UML algorithms, they focus exclusively on computer vision tasks for relatively small graphs with specific topology, representing images (e.g., each node corresponds to a pixel that is connected to its four or eight neighboring pixels). This is the first comparison for large unstructured graphs commonly found in social networks, biological databases, etc. We evaluate eight representative UML algorithms on solution quality, efficiency, convergence speed and scalability, using three real datasets with diverse properties. Based on our experimental results, we provide guidelines for the selection of the best method depending on the problem characteristics.