# Exploratory Data Analysis and Searching Cliques in Graphs
## 2 The Auxiliary Graph Based on Distances
If \(\alpha(i)=1\), then the nodes \(\{O^{\prime}_{1},O^{\prime}_{i}\}\) and \(\{O^{\prime}_{1},O^{\prime}_{t}\}\) of the auxiliary graph \(G\) are adjacent in the clique \(\Delta\) and so the triangle with vertices \(O^{\prime}_{1},O^{\prime}_{t},O^{\prime}_{t}\) is flat. The object \(O^{\prime}_{i}\) is close to the straight line of the objects \(O^{\prime}_{1},O^{\prime}_{t}\). We can draw the same conclusion when \(\alpha(i)=t\). For the remaining part of the proof we may assume that \(\alpha(i)\
eq 1\) and \(\alpha(i)\
eq t\). In this situation the unordered pairs \(\{O^{\prime}_{1},O^{\prime}_{t}\}\) and \(\{O^{\prime}_{1},O^{\prime}_{\alpha(i)}\}\) are adjacent nodes in the clique \(\Delta\) and so the quadrangle with nodes \(O^{\prime}_{1}\), \(O^{\prime}_{i}\), \(O^{\prime}_{\alpha(i)}\), \(O^{\prime}_{t}\) is flat. Consequently, the triangle with vertices \(O^{\prime}_{1}\), \(O^{\prime}_{i}\), \(O^{\prime}_{t}\) is flat. Summarizing our considerations we can say that the objects \(O^{\prime}_{1},\ldots,O^{\prime}_{t}\) form an approximately \(1\)-dimensional linear manifold. Therefore, one can locate approximately \(1\)-dimensional linear manifolds formed by objects via locating cliques in the auxiliary graph \(G\). Using the definition, checking the flatness of the quadrangle with vertices \(O_{p}\), \(O_{q}\), \(O_{r}\), \(O_{s}\) requires computing the areas of four triangles. We will point out that this task can be accomplished by computing the areas of two triangles. Set \(\delta\) to be the maximum of the distances  
\[\delta(p,q),\delta(p,r),\delta(r,s),\delta(s,p),\delta(p,r),\delta(q,s).\]  
For the sake of definiteness, suppose that the distance of the vertices \(O_{p}\), \(O_{r}\) is equal to \(\delta\). The flatness of the quadrangle with vertices \(O_{p}\), \(O_{q}\), \(O_{r}\), \(O_{s}\) can be checked by checking the flatness of the triangles with vertices \(O_{p}\), \(O_{r}\), \(O_{q}\) and \(O_{p}\), \(O_{s}\), \(O_{r}\). Next, we describe a situation in which the auxiliary graph exhibit properties that we consider undesirable. Let us consider a large square \(S\). As a first thought experiment we identify the vertices \(A_{1}\), \(A_{2}\), \(A_{3}\), \(A_{4}\) of the square \(S\) with the object \(O_{1}\), \(O_{2}\), \(O_{3}\), \(O_{4}\). The associated auxiliary graph has six nodes and it contains only one clique, that is only isolated nodes. None of the \(15\) possible edges appear within it. In the second thought experiment we use eight objects \(O_{1},\ldots,O_{8}\). The objects \(O_{1}\), \(O_{2}\) are placed very close to the vertex \(A_{1}\). The objects \(O_{3}\), \(O_{4}\) are placed very close to the vertex \(A_{3}\). The objects \(O_{7}\), \(O_{8}\) are placed very close to the vertex \(A_{4}\). The associated auxiliary graph has \(28\) nodes and it contains four cliques whose vertices are \(\{O_{1},O_{2}\}\), \(\{O_{3},O_{4}\}\), \(\{O_{5},O_{6}\}\), \(\{O_{7},O_{8}\}\). On the other hand, the eight objects \(O_{1},\ldots,O_{8}\) do not form an approximately \(1\)-dimensional manifold. Consequently, we modify the definition of the auxiliary graph \(G\). The nodes of \(G\) are the unordered pairs \(\{O_{i},O_{j}\}\) for each \(i\), \(j\), \(1\leq i<j\leq m\) provided that the distance of the object \(O_{i}\), \(O_{j}\) exceeds a fixed predefined threshold value \(\theta\). In notation  
\[V=\{\{O_{i},O_{j}\}:\ \delta(i,j)\geq\theta,\ 1\leq i<j\leq m,\}.\]  
Using any exact or heuristic method for clique search, one could locate big cliques in the \(G\) or the \(H\) graph, thus finding a big (nearly) \(1\)-dimensional subset of the whole data set. Another approach would be coloring the complement graph. That way the data set can be clustered into (nearly) \(1\)-dimensional subsets.