Abstract When dealing with large graphs, such as those that arise in the context of online social networks, a subset of nodes may be labeled. These labels can indicate demographic values, interest, beliefs or other characteristics of the nodes (users). A core problem is to use this information to extend the labeling so that all nodes are assigned a label (or labels). In this chapter, we survey classification techniques that have been proposed for this problem. We consider two broad categories: methods based on iterative application of traditional classifiers using graph information as features, and methods which propagate the existing labels via random walks. We adopt a common perspective on these methods to highlight the similarities between different approaches within and across the two categories. We also describe some extensions and related directions to the central problem of node classification.
Introduction
In the ecosystem of Online Social Networks (OSNs), user profiles are frequently incomplete. While a user might provide their geographic location, they may omit their interests, age, or political affiliations. However, these missing "labels" are essential for the functionality of modern digital platforms, powering recommendation engines, targeted advertising, and large-scale sociological research.
The node classification problem addresses this gap: given a graph where only a fraction of nodes are labeled, how can we accurately and efficiently infer labels for the remaining population? This task is complicated by the massive scale of modern networks and the inherent noise in user-generated data. To solve this, researchers leverage two fundamental social phenomena: homophily (the tendency of similar individuals to associate) and co-citation regularity (the tendency of similar individuals to connect to the same external entities).
Taxonomy of Classification Techniques
Techniques for node classification generally fall into two primary schools of thought: iterative local classifiers and random walk-based diffusion methods.
1. Iterative Local Classifiers
These methods, exemplified by the Iterative Classification Algorithm (ICA), treat node classification as an extension of traditional machine learning. The distinguishing feature is the use of "link features"—aggregate statistics derived from a node’s neighbors—as model inputs. Because the labels of a node's neighbors are initially unknown or subject to change as the algorithm progresses, the process is iterative. The classifier updates labels across the graph until the assignments stabilize or reach a predefined convergence threshold.
2. Random Walk-Based Methods
These methods view label assignment as a diffusion process across the graph structure.
- Label Propagation: In this model, labeled nodes act as "absorbing states." A random walk starting from an unlabeled node continues until it hits a labeled node, effectively pulling the label from the known to the unknown.
- Graph Regularization: Similar to Personalized PageRank, this approach allows labels on even the initially labeled nodes to shift slightly. This ensures a "smoother" global labeling that accounts for the overall graph topology rather than just immediate neighbors.
- Adsorption: This serves as a general framework that introduces "shadow nodes." It balances three factors: the node's initial label, the influence of its neighbors, and a "dummy" label that represents uncertainty or a random restart.
A Unifying Perspective
A significant contribution of recent research is the demonstration that these seemingly disparate methods are mathematically related. Local "voting" schemes and global "random walks" can both be expressed as iterative matrix-vector multiplications. Specifically, the Adsorption framework has been shown to unify several propagation methods as special cases, proving that many popular algorithms are essentially solving specific systems of linear equations.
Scalability and Real-World Application
Because these algorithms rely heavily on local neighborhood information, they are "embarrassingly parallel." This makes them ideal for implementation within distributed computing frameworks like Map-Reduce. For networks with billions of edges, such as those found on Facebook, LinkedIn, or YouTube, scalability is achieved by distributing the graph and performing local updates in parallel.
However, these methods rely on the "Label Connected" assumption: there must be a path from every unlabeled node to at least one labeled node. In practice, if a graph component is entirely unlabeled, it remains impossible to classify using these structural methods alone.
Key Findings and Empirical Observations
Surveys of the literature reveal several critical insights into the performance of these models:
- The Power of Simplicity: Simple weighted voting and nearest-neighbor classifiers often achieve high accuracy (70-90%) for demographic labels, suggesting that the local graph structure is a very strong signal.
- Efficiency of Iteration: Most iterative methods reach a stable state within tens to a hundred iterations. This is significantly more computationally efficient than direct matrix inversion, which scales at $O(n^3)$.
- Feature Importance: In social contexts, "link features" (the attributes of one's friends) are often more predictive of behavior and identity than a node's own individual attributes.
Limitations and Future Directions
Despite the maturity of the field, several challenges remain. Many sophisticated methods, such as Metric Labeling or Spectral Partitioning, have yet to be proven at the scale of millions of nodes. Furthermore, the lack of standardized, large-scale benchmarks makes head-to-head comparisons difficult.
Future work is expected to focus on Hybrid Models that combine the attribute-handling strengths of local classifiers with the structural robustness of random walks. Additionally, there is a pressing need for stronger theoretical guarantees regarding the quality of inferred labels, moving beyond the often unrealistic assumptions currently used in generative label models.
Summary updated