Data Mining: The Textbook

19.4. COLLECTIVE CLASSIFICATION

647

approach is identical to that used in spectral clustering except that the class information is incorporated within the embedding. The second method directly learns an n × k class probability matrix Z with an optimization formulation related to spectral clustering. This class probability matrix Z is similar to that derived in label propagation. Interestingly, the second method is also closely related to label propagation.

19.4.3.1 Supervised Feature Generation with Spectral Embedding

Let G = (N, A) be the undirected graph with weight matrix W . The approach consists of the following steps, the first of which is to augment G with class-based supervision:

1. 
   Add an edge with weight μ between each pair of nodes with the same label in G. If an edge already exists between a pair of such nodes, then the two edges are consolidated by adding μ to the weight of the existing edge. The resulting graph is denoted by G+. The parameter μ controls the level of supervision from existing labels.
   

2. 
   Use the spectral embedding approach of Sect. 19.3.4 to generate an r-dimensional embedding of the augmented graph G+.
   

3. 
   Apply any multidimensional classifier, such as a nearest neighbor classifier, on the embedded data.
   

The value of μ may be tuned with the use of cross-validation. Note that this approach does not directly learn the class probabilities. Rather, it creates a feature representation that implicitly incorporates both the homophily effects and the existing label information. This feature representation is sensitive to both network locality and label distribution. Therefore, it can be used to design an effective multidimensional classifier.

19.4.3.2 Graph Regularization Approach

The graph regularization approach learns the labels of the nodes directly with an optimiza-tion formulation related to spectral clustering. let Z be an n × k matrix of optimization variables, in which the ( i, c)th entry denotes the propensity of node i to belong to label c. When the (i, c)th entry is large, it indicates that node i is more likely to belong to label c. Therefore, for the ith row of Z, the index of the largest of the k entries provides a pre-diction of the class label of node i. The column-vector Z_c denotes the cth column of Z for c ∈ {1 . . . k}. Furthermore, Y is an n × k binary matrix containing the label information. If the ith node is labeled, then exactly one entry in the ith row of Y is 1, corresponding to the relevant class label. Other entries are 0. For unlabeled nodes, all entries in the corresponding row of Y are 0. The cth column of Y is denoted by the column vector Y_c.

This approach directly uses the weighted matrix W of an undirected graph G = (N, A) (e.g., Fig. 19.9) rather than a directed transition graph. The variables in the matrix Z are derived with an optimization formulation related to spectral clustering. Each n-dimensional vector Z_c is viewed as a 1-dimensional embedding of the n nodes. The goal of this optimiza-tion formulation is two-fold, which is reflected in the two additive terms of the objective function:

1. 
   Smoothness (homophily) objective: For each class c ∈ {1 . . . k}, the nodes connected with high-weight edges should be mapped to similar values in Z_c. This goal is iden-tical to the unsupervised objective function in spectral clustering. In this case, the symmetric Laplacian Ls is used because of its better convergence properties:
   

Ls = I − Λ−1/2W Λ−1/2

(19.37)

648 CHAPTER 19. SOCIAL NETWORK ANALYSIS

Here, Λ is a diagonal matrix in which the ith diagonal entry contains the sum of the ith row entries of the n×n weight matrix W . For brevity, we denote the normalized weight matrix by S = Λ−1/2W Λ−1/2. Therefore, the smoothness term O_s in the objective function may be written as follows:

k				k