Graph Analysis and Applications in Clustering and Content-based Image Retrieval
|Tila||Julkaistu - 9 elokuuta 2019|
|Nimi||Tampere University Dissertations|
Cluster structure is a common phenomenon in many real-world graphs, for example, social networks. Finding the clusters in a large graph is important to understand the underlying relationships between the nodes. Graph clustering is a technique that partitions nodes into clus- ters such that connections among nodes in a cluster are dense and connections between nodes in diﬀerent clusters are sparse. Various approaches have been proposed to solve graph clustering problems. A common approach is to optimize a predeﬁned clustering metric using diﬀerent optimization methods. However, most of these optimization problems are NP-hard due to the discrete set-up of the hard-clustering. These optimization problems can be relaxed, and a sub-optimal solu- tion can be found. A diﬀerent approach is to apply data clustering
algorithms in solving graph clustering problems. With this approach, one must ﬁrst ﬁnd appropriate features for each node that represent the local structure of the graph. Limited Random Walk algorithm uses the random walk procedure to explore the graph and extracts ef- ﬁcient features for the nodes. It incorporates the embarrassing parallel paradigm, thus, it can process large graph data eﬃciently using mod- ern high-performance computing facilities. This thesis gives the details of this algorithm and analyzes the stability issues of the algorithm.
Based on the study of the cluster structures in a graph, we deﬁne the authenticity score of an edge as the diﬀerence between the actual and the expected number of edges that connect the two groups of the neighboring nodes of the two end nodes. Authenticity score can be used in many important applications, such as graph clustering, outlier detection, and graph data preprocessing. In particular, a data clus- tering algorithm that uses the authenticity scores on mutual k-nearest neighborhood graph achieves more reliable and superior performance comparing to other popular algorithms. This thesis also theoretically proves that this algorithm can asymptotically ﬁnd the complete re- covery of the ground truth of the graphs that were generated by a stochastic r-block model.
Content-based image retrieval (CBIR) is an important application in computer vision, media information retrieval, and data mining. Given a query image, a CBIR system ranks the images in a large image database by their “similarities” to the query image. However, because of the ambiguities of the deﬁnition of the “similarity”, it is very diﬃ- cult for a CBIR system to select the optimal feature set and ranking algorithm to satisfy the purpose of the query. Graph technologies have been used to improve the performance of CBIR systems in var- ious ways. In this thesis, a novel method is proposed to construct a visual-semantic graph—a graph where nodes represent semantic concepts and edges represent visual associations between concepts. The constructed visual-semantic graph not only helps the user to locate the target images quickly but also helps answer the questions related to the query image. Experiments show that the eﬀorts of locating the target image are reduced by 25% with the help of visual-semantic graphs.
Graph analysis will continue to play an important role in future data analysis. In particular, the visual-semantic graph that captures important and interesting visual associations between the concepts is worthyof further attention.