Collective classification

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 ${\displaystyle G}$ with a set of nodes ${\displaystyle V}$ and an edge set ${\displaystyle E}$ representing relationships among nodes. Each node ${\displaystyle v_i\in V}$ is described by its attributes: a feature vector ${\displaystyle x_i\in X}$ and its label (or class) ${\displaystyle y_i\in Y}$.

${\displaystyle V}$ can further be divided into two sets of nodes: ${\displaystyle L}$, the set of nodes for which we know the correct label values (observed variables), and ${\displaystyle U}$, the nodes whose labels must be inferred. The collective classification task is to label the nodes in ${\displaystyle U}$ with a label from a label set ${\displaystyle L=\{L_1,\cdots L_q\}}$.

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 ${\displaystyle v}$:

1. The correlations between the label of ${\displaystyle v}$ and the observed attributes of ${\displaystyle v}$. Traditional iid classifiers which make use of feature vectors are an example of approaches that use this correlation.
2. The correlations between the label of ${\displaystyle v}$ and the observed attributes (including observed labels) of nodes in the neighborhood of ${\displaystyle v}$.
3. The correlations between the label of ${\displaystyle v}$ and the unobserved labels of objects in the neighborhood of ${\displaystyle v}$.

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 ${\displaystyle V_i}$ using the label propagation method is a weighted average of its neighboring labels ${\displaystyle Y_{N_i}}$

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 ${\displaystyle h}$ that has been trained to classify a node ${\displaystyle v_i}$ given its features ${\displaystyle X_i}$ and the features ${\displaystyle X_{N_i}}$ and labels ${\displaystyle Y_{N_i}}$ of its neighbors ${\displaystyle N_i}$. 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 ${\displaystyle P}$, in which random variables are nodes in a graph ${\displaystyle G}$. 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 ${\displaystyle y_i}$ given all the values for the nodes in ${\displaystyle N_i}$ using local classifier ${\displaystyle f}$ for a fixed number of iterations. After that, we sample labels for each ${\displaystyle y_i\in Y}$ and maintain count statistics for the number of times we sampled label ${\displaystyle l}$ for node ${\displaystyle y_i}$. After collecting a predefined number of such samples, we output the best label assignment for node ${\displaystyle y_i}$ by choosing the label that was assigned the maximum number of times to ${\displaystyle y_i}$ 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:

• Social network analysis, where collective approaches to node classification tasks such as detecting malicious users can utilize information about relationships between nodes.
• Entity resolution, where one can make use of co-authorship relationships to identify authors of papers.
• Named entity recognition, where some approaches treat this as a text sequence labeling problem and jointly infer the labels of every word in a sentence, typically by using a conditional random field which models a linear chain of dependencies between the labels of adjacent words in the sentence.
• Document classification, where for example inter-document semantic similarities can be collectively utilized as signals that certain documents belong to the same class.
• Computational biology, where graphical models such as Markov random fields are utilized to jointly infer relations between biological entities such as genes.
• Computer vision, where for example collective classification can be applied to recognizing multiple objects simultaneously.