In network theory, collective classification is the simultaneous prediction of the labels for multiple objects, where each label is predicted using information about the object's observed features, the observed features and labels of its neighbors, and the unobserved labels of its neighbors. Collective classification problems are defined in terms of networks of random variables, where the network structure determines the relationship between the random variables. Inference is performed on multiple random variables simultaneously, typically by propagating information between nodes in the network to perform approximate inference. Approaches that use collective classification can make use of relational information when performing inference. Examples of collective classification include predicting attributes (ex. gender, age, political affiliation) of individuals in a social network, classifying webpages in the World Wide Web, and inferring the research area of a paper in a scientific publication dataset.
Motivation and background.
Traditionally, a major focus of machine learning is to solve classification problems. (For example, given a collection of e-mails, we wish to determine which are spam, and which are not.) Many machine learning models for performing this task will try to categorize each item independently, and focus on predicting the class labels separately. However, the prediction accuracy for the labels whose values must be inferred can be improved with knowledge of the correct class labels for related items. For example, it is easier to predict the topic of a webpage if we know the topics of the webpages that link to it. Similarly, the chance of a particular word being a verb increases if we know that the previous word in the sentence is a noun; knowing the first few characters in a word can make it much easier to identify the remaining characters. Many researchers have proposed techniques that attempt to classify samples in a joint or collective manner, instead of treating each sample in isolation; these techniques have enabled significant gains in classification accuracy.
Example.
Consider the task of inferring the political affiliation of users in a social network, where some portion of these affiliations are observed, and the remainder are unobserved. Each user has local features, such as their profile information, and links exist between users who are friends in this social network. An approach that does not collectively classify users will consider each user in the network independently and use their local features to infer party affiliations. An approach which performs collective classification might assume that users who are friends tend to have similar political views, and could then jointly infer all unobserved party affiliations while making use of the rich relational structure of the social network.
Definition.
Consider the semi supervised learning problem of assigning labels to nodes in a network by using knowledge of a subset of the nodes' labels. Specifically, we are given a network represented by a graph formula_1 with a set of nodes formula_2 and an edge set formula_3 representing relationships among nodes. Each node formula_4 is described by its attributes: a feature vector formula_5 and its label (or class) formula_6.
formula_2 can further be divided into two sets of nodes: formula_8, the set of nodes for which we know the correct label values (observed variables), and formula_9, the nodes whose labels must be inferred. The collective classification task is to label the nodes in formula_9 with a label from a label set formula_11.
In such settings, traditional classification algorithms assume that the data is drawn independently and identically from some distribution (iid). This means that the labels inferred for nodes whose label is unobserved are independent of each other. One does not make this assumption when performing collective classification. Instead, there are three distinct types of correlations that can be utilized to determine the classification or label of formula_12:
Collective classification refers to the combined classification of a set of interlinked objects using the three above types of information.
Methods.
There are several existing approaches to collective classification. The two major methods are iterative methods and methods based on probabilistic graphical models. 
Iterative methods.
The general idea for iterative methods is to iteratively combine and revise individual node predictions so as to reach an equilibrium. When updating predictions for individual nodes is a fast operation, the complexity of these iterative methods will be the number of iterations needed for convergence. Though convergence and optimality is not always mathematically guaranteed, in practice, these approaches will typically converge quickly to a good solution, depending on the graph structure and problem complexity. The methods presented in this section are representative of this iterative approach.
Label propagation.
A natural assumption in network classification is that adjacent nodes are likely to have the same label (i.e., contagion or homophily). The predictor for node formula_19 using the label propagation method is a weighted average of its neighboring labels formula_20
Iterative Classification Algorithms (ICA).
While label propagation is surprisingly effective, it may sometimes fail to capture complex relational dynamics. More sophisticated approaches can use richer predictors.
Suppose we have a classifier formula_21 that has been trained to classify a node formula_22 given its features formula_23 and the features formula_24 and labels formula_20 of its neighbors formula_26. Iterative classification applies uses a local classifier for each node, which uses information about current predictions and ground truth information about the node's neighbors, and iterates until the local predictions converge to a global solution. Iterative classification is an “algorithmic framework,” in that it is agnostic to the choice of predictor; this makes it a very versatile tool for collective classification.
Collective classification with graphical models.
Another approach to collective classification is to represent the problem with a graphical model and use learning and inference techniques for the graphical modeling approach to arrive at the correct classifications. Graphical models are tools for joint, probabilistic inference, making them ideal for collective classification. They are characterized by a graphical representation of a probability distribution formula_27, in which random variables are nodes in a graph formula_1. Graphical models can be broadly categorized by whether the underlying graph is directed (e.g., Bayesian networks or collections of local classifiers) or undirected (e.g., Markov random fields (MRF)). 
Gibbs sampling.
Gibbs sampling is a general framework for approximating a distribution. It is a Markov chain Monte Carlo algorithm, in that it iteratively samples from the current estimate of the distribution, constructing a Markov chain that converges to the target (stationary) distribution.
The basic idea for Gibbs Sampling is to sample for the best label estimate for formula_29 given all the values for the nodes in formula_26 using local classifier formula_31 for a fixed number of iterations. After that, we sample labels for each formula_6 and maintain count statistics for the number of times we sampled label formula_33 for node formula_29. After collecting a predefined number of such samples, we output the best label assignment for node formula_29 by choosing the label that was assigned the maximum number of times to formula_29 while collecting samples.
Loopy belief propagation.
For certain undirected graphical models, it is possible to efficiently perform exact inference via message passing, or belief propagation algorithms. These algorithms follow a simple iterative pattern: each variable passes its "beliefs" about its neighbors' marginal distributions, then uses the incoming messages about its own value to update its beliefs. Convergence to the true marginals is guaranteed for tree-structured MRFs, but is not guaranteed for MRFs with cycles.
Statistical relational learning (SRL) related.
Statistical relational learning is often used to address collective classification problems. A variety of SRL methods has been applied to the collective classification setting. Some of the methods include direct methods such probabilistic relational models (PRM), coupled conditional models such as link-based classification,
and indirect methods such as Markov logic networks (MLN) and Probabilistic Soft Logic (PSL).
Applications.
Collective classification is applied in many domains which exhibit relational structure, such as:
References.
 ;templatestyles src="Reflist/styles.css" / ;