Node Classification in Social Networks

Smriti Bhagat; Graham Cormode; S. Muthukrishnan

Source-linked AI summary

Node Classification in Social Networks

Smriti Bhagat, Graham Cormode, S. Muthukrishnan

arXiv:1101.3291v1Jan 17, 2011cs.SIphysics.soc-ph

TL;DR

The chapter addresses how to extend partial node labels across large graphs. It surveys local iterative classifiers and random-walk label propagation, presenting a common perspective that reveals shared iterative matrix formulations and relationships between the approaches. It also emphasizes that classification quality cannot generally be guaranteed without assumptions about hidden labels and that scalability remains a challenge.

Problem
Given a partially labeled graph, the central problem is to infer labels for all nodes, but the task is underspecified without assumptions about the process generating hidden labels.
Method
The chapter surveys iterative local-classifier and random-walk approaches, analyzing their similarities through a common framework.
Results
Many surveyed methods can be viewed as generating labels from random-walk occupancy probabilities, with outputs represented as probability distributions over labels.
Takeaways & Limitations
The common perspective connects random-walk methods with iterative approaches using simple classifiers and highlights similarities across techniques.
Takeaways & Limitations
The literature includes methods that do not scale to large social-network graphs, and general label-quality guarantees are unavailable without strong generative assumptions.

Abstract

from arXiv · show

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.

1. Introduction

Node classification addresses incomplete and noisy labels in large social-network graphs by inferring labels for unlabeled nodes. The chapter surveys iterative local-classifier methods and random-walk methods within a common framework.

Social-network labels include demographics, beliefs, interests, affiliations, recommendations, and other information associated with users.
Missing labels are common because user-provided information may be misleading, outdated, distorted, or partial, limiting applications such as recommendations.
The node classification problem is to infer high-quality labels for every node from a graph in which only some nodes are labeled.
Expert or incentivized labeling does not scale from small social groups to networks containing hundreds of thousands or millions of individuals.
Graph-based classification uses node and neighborhood features because social links can encode similarity through homophily and co-citation regularity.
The survey divides methods into iterative traditional classifiers using graph-derived features and random-walk methods that propagate labels through the network.

2. Problem Formulation

The chapter formulates node classification by representing online and other networks as weighted graphs with partially observed node labels. It emphasizes that graph construction, label types, and structural assumptions shape the classification problem.

2.1 Representing data as a graph: Online networks are modeled as graphs G(V, E, W), where nodes represent users or other entities, edges encode relationships or shared activity, and labels describe node properties.The framework covers Facebook, LinkedIn, Netflix, YouTube, and Flickr data.
2.1 Representing data as a graph: Modeling choices determine which network features are captured, while data collection and preparation are treated as outside the survey’s scope.The presentation assumes that network data is already available.
2.1 Representing data as a graph: Graph representations can differ in node, edge, and label semantics, as illustrated by user graphs and alternative video graphs derived from the same YouTube data.Video nodes may connect through shared playlists or co-viewing, with labels such as tags, views, upload time, owners, and ratings.
2.1 Representing data as a graph: Edges may be directed or undirected depending on whether interactions are reciprocal, and edge weights can encode connection strength or similarity.Friendship links are reciprocal, whereas subscriptions and wall posts are directed; weights may count co-viewed videos or interactions.
2.1 Representing data as a graph: When explicit links are absent, graphs may be induced using homophily or co-citation regularity, linking entities with similar characteristics or shared references.Advocated constructions include fully connected distance-weighted graphs, k-nearest-neighbor graphs, and ε-weighted graphs.
2.1 Representing data as a graph: An ε-weighted graph retains only edges whose weights exceed threshold ε, while kNN graphs connect nodes according to nearest-neighbor relations.Directed kNN graphs have outdegree k; symmetric variants can give nodes degree less than k.
2.1 Representing data as a graph: The surveyed methods assume non-negative edge weights and wij = 0 for node pairs that are not connected, but otherwise make few assumptions about graph structure or weight distributions.This leaves directionality, symmetry, and weight behavior largely determined by the chosen representation.
2.1 Representing data as a graph: Because users disclose only partial information, labels initially occur on a subset of nodes and may be binary, numeric, categorical, or free-text, with single- or multi-value formats.Datasets may contain many label categories or only one recorded label, and classification typically seeks values for unlabeled nodes.

3. Methods using Local Classifiers

Local-classifier methods build node and neighborhood features, train a classifier on labeled nodes, and iteratively update predictions as newly inferred labels change link features. The framework includes several classifier choices and has clear propagation and convergence boundaries.

3. Methods using Local Classifiers: Iterative local-classifier methods use neighborhood information to generate features, then apply traditional classifiers to infer labels for unlabeled nodes.Examples include Naïve Bayes and decision trees.
3. Methods using Local Classifiers: Node features describe known attributes, while link features aggregate neighboring labels, such as label frequencies, directional counts, node degrees, and connectivity.For YouTube videos, views, upload time, and ratings are node features; neighboring tag counts are link features.
3. Methods using Local Classifiers: ICA initializes features and trains a classifier, applies it to unlabeled nodes, and repeats prediction as newly assigned labels alter neighborhood-derived features.The classifier may optionally be retrained at each iteration using current labels and features.
3. Methods using Local Classifiers: Iterations may continue until labels stabilize or for a fixed or sufficiently large number of steps, because arbitrary local classifiers are not guaranteed to reach stability.A large fraction of unchanged labels is another possible stopping rule.
3. Methods using Local Classifiers: Local iteration can propagate labels through successive neighborhoods: in the illustrated example, node X receives ‘18’ first, then node Y receives it in the next iteration.Further iterations propagate the labeling farther.
3. Methods using Local Classifiers: If a connected component contains no initially labeled node, label-only propagation leaves every node in that component unlabeled regardless of iteration count.This is a structural limitation of methods that base labeling solely on labels from other nodes.
3. Methods using Local Classifiers: The framework has been instantiated with different classifiers, including Naïve Bayes, probability voting, and nearest-neighbor approaches.Probability voting applies a weighted neighborhood average, while nearest-neighbor classification can use labeled nodes across the entire graph.
3. Methods using Local Classifiers: Linked-document experiments reported significant improvement from adding link features beyond using text features alone.This supports the use of neighboring-document information within the iterative classification perspective.

4. Random Walk based Methods

Random-walk methods assign labels from the limiting destinations of walks through a graph, with variants differing in transition rules and treatment of labeled nodes. The chapter relates these methods to iterative propagation, matrix formulations, and adsorption, showing shared convergence and unification properties.

Random Walk Formulation: Random-walk labeling assigns a node the aggregate probability of reaching labeled nodes as the walk converges.The graph is commonly assumed to be label connected so unlabeled nodes can reach labeled nodes.
Random Walk Formulation: Transition matrix P determines edge movement probabilities and absorbing states, where a walk remains permanently once it arrives.In label-propagation variants, labeled nodes are absorbing, preserving their initial labels.
Label Propagation: Label propagation is equivalent to iterative neighborhood averaging when labeled-node distributions remain fixed and unlabeled nodes repeatedly average neighbors.The iterative algorithm converges to the same labeling as the corresponding random walk and matrix equation.
Adsorption: Adsorption represents labeled nodes with absorbing shadow vertices, allowing their labels to propagate while the original labeled nodes are treated as unlabeled.Its transition matrix combines non-shadow transitions with transitions to shadow vertices.
Adsorption: Setting α_i = 0 for initially labeled nodes makes them absorbing and recovers the original label-propagation algorithm, unifying earlier random-walk methods.The adsorption output is a linear combination of initial labels and remains a probability distribution under row-stochastic transitions.

5. Applying Node Classification to Large Social Networks

Large social networks make direct matrix-based node-classification methods computationally expensive. The chapter therefore describes iterative, simulation, acceleration, and distributed-computation strategies for obtaining approximate or converged labelings at scale.

Scalability Challenges: Millions of nodes, billions of edges, and thousands of labels can make direct matrix-equation solutions computationally expensive.The chapter motivates scalable alternatives for social-network datasets of this size.
Iteration: When m ≪ n, iterative computation can obtain the n × m stationary label-probability matrix without forming the full n × n stationary distribution.The method iterates label probabilities until convergence or an adequate approximation is reached.
Iteration: Power iteration converges exponentially quickly, so approximately tens to a hundred iterations can provide a close enough approximation.The difference from the limiting solution decreases by a constant factor each iteration.
Random Walk Simulation: Random-walk simulation estimates stationary distributions by sampling walk endpoints and can avoid storing the graph as a matrix.It requires access to adjacency lists of visited nodes and has been applied when data cannot fit in memory.
Second-order Methods: Second-order updates combine the current and previous iterations, and have been shown to converge faster for 1 ≤ β ≤ 2.The parameter β weights the current update in the reformulated iteration.
Distributed Computation: Map-Reduce can distribute local and random-walk iterations by having nodes collect neighbor information and compute updated labels across machines.One Map-Reduce round computes one iteration, so only a moderate number of rounds may be needed for convergence.

6. Related approaches

This section surveys relational, optimization, spectral, clustering, and partitioning approaches to node classification. These methods model graph dependencies explicitly or exploit graph structure, but can face inference, modeling, or scalability constraints.

Statistical Relational Learning: Statistical Relational Learning treats node classification as modeling correlations among graph objects, including through PRMs and RMNs.PRMs use directed Bayesian networks, whereas RMNs use undirected Markov networks.
Statistical Relational Learning: Relational models infer unlabeled-node distributions P(Xu|Xl), but node dependencies prevent compact closed-form marginals.Loopy belief propagation provides a common approximate inference strategy and lacks general convergence guarantees.
Optimization and Partitioning: Metric Labeling formulates graph labeling as minimizing costs over node assignments and pairwise relationships, with guaranteed approximation results.Applying it to social-network classification requires metrics for labels and missing-label cases, while the resulting linear program may challenge modern solvers.
Optimization and Partitioning: Spectral methods can recover labels under random graph-generation assumptions, but modified models better represent sparse social-network graphs.For arbitrary underlying graphs, almost all labels may not be recoverable with high probability, although simple algorithms may recover a constant fraction.
Optimization and Partitioning: Clustering and graph-partitioning methods assign common labels within clusters, using edge similarity, minimum cuts, or spectral graph methods.Minimum-cut classification is motivated by cases where the minimum cut produces the smallest classification error; image segmentation connects normalized partitioning to graph-Laplacian eigenvectors.

7. Variations on Node Classification

The chapter extends node classification to graphs with disagreement edges, inferred edge weights or labels, and constrained multi-label outputs. These variations adapt labeling objectives to richer relationships and practical storage limits.

Dissimilarity in Labels: Dissimilarity-aware labeling allows edges to encode either affinity or disagreement rather than assuming every link connects similar nodes.The resulting quadratic program can be extended to multiple classes but may not scale to huge graphs.
Edge Labeling: Edge-labeling methods infer whether relationships are positive or negative using social theories such as Balance and Status.Balance emphasizes consistency of signs within triads, while Status interprets edge signs through relative social rank; the theories can disagree on some cases.
Edge Labeling: Other edge-labeling formulations infer influence probabilities or probability distributions over arbitrary interaction labels.Influence probabilities quantify neighbors’ subsequent actions, while interaction labels can represent email, posts, photo tags, or video messages.
Space-Constrained Labeling: Space-constrained labeling limits each node’s output to k labels, either by pruning computed distributions or summarizing them through a label hierarchy.Hierarchy-based selection aims to avoid redundant labels and better represent the computed distribution.

8. Concluding Remarks

The chapter unifies many node-classification methods through random-walk occupancy probabilities while concluding that reliable classification quality remains unresolved. It identifies scalability, common evaluation, model connections, and hypothesis testing as open challenges.

Concluding Remarks: The survey finds that iterative and random-walk methods, along with several other approaches, can generate labels from random-walk occupancy probabilities.The commonality is motivated by both linear-algebraic and optimization perspectives.
Future Directions and Challenges: Without strong assumptions about the process generating hidden labels, the chapter cannot quantify the quality of inferred labelings theoretically.It therefore advocates evaluation by withholding known labels and comparing the imputed labels with them.
Future Directions and Challenges: The literature lacks adequate scalability for some methods and sufficiently broad comparisons among scalable methods on common baselines.Some techniques were tested only on graphs of a few thousand nodes or not at all, while existing comparisons used relatively small datasets.
Future Directions and Challenges: Random-walk and iterative approaches are comparatively easy to implement and distribute through Map-Reduce, motivating large-graph common-test-set evaluations.The proposed evaluations would compare method behavior across large graphs derived from social networks.
Future Directions and Challenges: Classical graph, optimization, and spectral methods require evaluation for both accuracy and scalability on large social-network graphs.The chapter specifically raises whether metric labeling, spectral partitioning, and inference can be implemented within Map-Reduce.
Future Directions and Challenges: Future work could connect loopy belief propagation with known iterative algorithms in special relational-model cases and develop hybrid labeling methods.The chapter also calls for testing assumptions such as homophily, balance, and status at large scale.