# Affinity Propagation Clustering Using Path Based Similarity
## 2 Method
### Affinity Propagation Clustering Using Path-Based Similarity  
To discuss the necessity of introducing path-based similarity, we first give an illustrative example in Figure 1. In the figure, there are 202 samples distributed with two curves and each curve correspond to a cluster. Samples \"e1\" and \"e2\" are two exemplars identified by running APC on the toy dataset plotted in the figure. From Figure 1, we can clearly see sample \"a\" is closer to exemplar \"e2\" than to \"e1\". Based on the non-exemplar samples assignment rule of APC and adopted similarity in Equation (1), non-exemplar sample \"a\" will be assigned to the upper cluster whose exemplar is \"e2\". Similarly, \"b\" will be viewed as a member of the lower cluster whose exemplar is \"e1\". However, from Figure 1, we could say \"a\" and \"e1\" should be in the lower cluster, \"b\" and \"e2\" should be in the upper cluster. This occurs principally because APC assigns non-exemplar samples to a cluster based their distance (or similarity) from the exemplar (or center sample) in each cluster. Although this rule is widely used in center-based clustering techniques (i.e., \(k\)-means and \(k\)-median [26]) and other variants of APC [16; 17], the rationality of this rule for samples distributed with complex structure is not as well as expected. Our additional examples in the following Experiment Section further confirm this issue. To address the issue in Figure 1, we suggest a path-based similarity to explore the underlying structure of samples and assign a non-exemplar to its most similar exemplar based on the path-based similarity between them. Suppose \(\mathbf{G}\in\mathbb{R}^{n\times n}\) is a distance matrix of a fully connected graph, \(\mathbf{x}_{i}\) corresponds to the \(i\)-th node of the graph, and \(\mathbf{G}(i,j)\) encodes the distance from \(i\) to \(j\). \(e\) is an exemplar and serves as the start node. Let \(\mathcal{Z}_{e}=\{e\}\) and \(\mathcal{V}_{e}=\{\mathcal{V}-e\}\), where \(\mathcal{V}\) includes all nodes of the graph described by \(\mathbf{G}\). Initially, the length of path from \(e\) to node \(i\in\mathcal{V}_{e}\) is specified as \(\mathbf{P}(e,i)=\mathbf{G}(e,i)\) and \(\mathbf{P}(e,e)=0\). At first, we find the node that has largest path-based similarity \(e\) as below:  
\[\mathbf{P}(e,i)=min_{i\in\mathcal{V}_{e}}\mathbf{P}(e,i) \tag{8}\]  
Next, we update \(\mathcal{Z}_{e}=\mathcal{Z}_{e}\bigcup i\) and \(\mathcal{V}_{e}=\mathcal{V}_{e}-i\). For \(j\in\mathcal{V}_{e}\), we define its largest path-based similarity to \(e\) by taking into account nodes in \(\mathcal{Z}_{e}\) as follow:  
\[\mathbf{P}(e,j)=min_{j\in\mathcal{V}_{e},j\in\mathcal{Z}_{e}}\left\{\mathbf{G }(e,j),max\left\{\mathbf{P}(e,i),\mathbf{G}(i,j)\right\}\right\} \tag{9}\]  
Equation (9) means that if the longest segment (\(\mathbf{P}(e,i)\) or \(\mathbf{G}(i,j)\)) in the path connecting \(e\) and \(j\) is smaller than \(\mathbf{G}(e,j)\),the shortest one from these longest segments is chosen as the path-based similarity between \(e\) and \(j\); otherwise, \(\mathbf{G}(e,j)\) is taken as the path-based similarity between them. \(\mathbf{P}(e,j)\) reflects the biggest difference inside the path and accounts for the distribution of exemplar and non-exemplar samples. In this way, we can get the path-based similarity between \(e\) and \(j\), and then append \(j\) into \(\mathcal{Z}_{e}\). By iteratively removing a node \(j\) from \(\mathcal{V}_{e}\), appending \(j\) into \(\mathcal{Z}_{e}\) and updating \(\mathbf{P}(e,j)\) using Equation (9), we can find the path-based similarity between \(e\) and all the other \(n-1\) samples. Similarly, we can repeatedly utilizes Equations (8) and (9) to find path-based similarity between another exemplar and the left \(n-1\) samples. Suppose there are \(k\) exemplars, \(\mathbf{P}\in\mathbb{R}^{k\times n}\), \(\mathbf{P}\) encodes the path-based similarity between \(k\) exemplars and \(n\) samples. APC based on path-based similarity (APC-PS) is summarized in Algorithm 1.