Uniform Metric Labeling

MPhil Thesis Defence


Title: "Uniform Metric Labeling"

By

Mr. Hao WU


Abstract

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, bio-logical 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.


Date:			Thursday, 14 February 2019

Time:			3:00pm - 5:00pm

Venue:			Room 4472
 			Lifts 25/26

Committee Members:	Prof. Dimitris Papadias (Supervisor)
 			Dr. Ke Yi (Chairperson)
 			Dr. Raymond Wong


**** ALL are Welcome ****