Abstract

Most existing graph-based semi-supervised classification methods use pairwise similarities as edge weights of an undirected graph with images as the nodes of the graph. Recently several new graph con- struction methods produce, however, directed graph (asymmetric similar- ity between nodes). A simple symmetrization is often used to convert a directed graph to an undirected one. This, however, loses important struc- tural information conveyed by asymmetric similarities. In this paper, we propose a novel symmetric co-linkage similarity which captures the essen- tial relationship among the nodes in the directed graph. We apply this new co-linkage similarity in two important computer vision tasks for image cat- egorization: ob ject recognition and image annotation. Extensive empirical studies demonstrate the effectiveness of our method.