Читать книгу Artificial Intelligence and Quantum Computing for Advanced Wireless Networks - Savo G. Glisic - Страница 89

Let G = (V, E) be an undirected graph with vertex set V = {v₁, …, v_n}. In the following, we assume that the graph G is weighted, that is, each edge between two vertices v_i and v_j carries a non‐negative weight w_ij ≥ 0. The weighted adjacency matrix of the graph is the matrix W = (w_ij)_{i, j = 1, …, n} . If w_ij = 0, this means that the vertices v_i and v_j are not connected by an edge. As G is undirected, we require w_ij = w_ji . The degree of a vertex v_i ∈ V is defined as

Note that, in fact, this sum only runs over all vertices adjacent to v_i , as for all other vertices v_j the weight w_ij is 0. The degree matrix D is defined as the diagonal matrix with the degrees d₁ , …, d_n on the diagonal. Given a subset of vertices A⊂V, we denote its complement V\A by . We define the indicator vector I_A = (f₁, …, f_n)′ ∈ ℝⁿ as the vector with entries f_i = 1 if v_i ∈ A and f_i = 0 otherwise. For convenience, we introduce the shorthand notation i ∈ A for the set of indices {i ∣ v_i ∈ A}, in particular when dealing with a sum like ∑_{i ∈ A} w_ij . For two not necessarily disjoint sets A, B ⊂ V we define

We consider two different ways of measuring the “size” of a subset ⊂A:

Intuitively, ∣A∣ measures the size of A by its number of vertices, whereas vol(A) measures the size of A by summing over the weights of all edges attached to vertices in A. A subset A ⊂ V of a graph is connected if any two vertices in A can be joined by a path such that all intermediate points also lie in A. A subset A is called a connected component if it is connected and if there are no connections between vertices in A and . The nonempty sets A₁ , …, A_k form a partition of the graph if A_i ∩ A_j = ∅ and A₁∪ … ∪A_k = V.

Similarity graphs: There are several popular constructions to transform a given set x₁ , …, x_n of data points with pairwise similarities s_ij or pairwise distances d_ij into a graph. When constructing similarity graphs, the goal is to model the local neighborhood relationships between the data points.

The ε‐neighborhood graph: Here, we connect all points whose pairwise distances are smaller than ε. As the distances between all connected points are roughly of the same scale (at most ε), weighting the edges would not incorporate more information about the data to the graph. Hence, the ε‐neighborhood graph is usually considered an unweighted graph.

k ‐nearest neighbor graphs: Here, the goal is to connect vertex v_i with vertex v_j if v_j is among the k‐nearest neighbors of v_i . However, this definition leads to a directed graph, as the neighborhood relationship is not symmetric. There are two ways of making this graph undirected. The first way is to simply ignore the directions of the edges, that is, we connect v_i and v_j with an undirected edge if v_i is among the k‐nearest neighbors of v_j or if v_j is among the k‐nearest neighbors of v_i . The resulting graph is what is usually called the k‐nearest neighbor graph. The second choice is to connect vertices v_i and v_j if both of the following are true: (i) v_i is among the k‐nearest neighbors of v_j and (ii) v_j is among the k‐nearest neighbors of v_i . The resulting graph is called the mutual k‐nearest neighbor graph. In both cases, after connecting the appropriate vertices, we weight the edges by the similarity of their endpoints.

The fully connected graph: Here, we simply connect all points with positive similarity with each other, and we weight all edges by s_ij . As the graph should represent the local neighborhood relationships, this construction is useful only if the similarity function itself models local neighborhoods. An example of such a similarity function is the Gaussian similarity function s(x_i, x_j) = exp (−‖x_i − x_j‖²/(2σ²)), where the parameter σ controls the width of the neighborhoods. This parameter plays a similar role as the parameter ε in the case of the ε‐neighborhood graph.

Graph Laplacians: The main tools for spectral clustering are graph Laplacian matrices. There exists a whole field dedicated to the study of those matrices, called spectral graph theory. In this section, we want to define different graph Laplacians and point out their most important properties. Note that in the literature there is no unique convention that governs exactly which matrix is called “graph Laplacian.” Usually, every author just calls “his” matrix the graph Laplacian. Hence, a lot of care is needed when reading the literature on graph Laplacians.

In the following, we always assume that G is an undirected, weighted graph with weight matrix W, where w_ij = w_ji ≥ 0. When using the eigenvectors of a matrix, we will not necessarily assume that they are normalized. For example, the constant vector 1 and a multiple a1 for some a ≠ 0 will be considered the same eigenvectors. Eigenvalues will always be ordered in ascending order, respecting multiplicities. By “the first k eigenvectors” we refer to the eigenvectors corresponding to the k smallest eigenvalues.

The unnormalized graph Laplacian is defined as L = D − W.

The following proposition summarizes the most important facts needed for spectral clustering.