PaperlayerView exact revision on arXiv

Source-linked AI summary

Prediction and Clustering in Signed Networks: A Local to Global Perspective

Kai-Yang Chiang, Cho-Jui Hsieh, Nagarajan Natarajan, Ambuj Tewari, Inderjit S. Dhillon

arXiv:1302.5145v2cs.SIcs.LG

TL;DR

The paper asks how local and global social-balance structure can support sign prediction and clustering in signed networks. It develops imbalance, higher-order-cycle, and low-rank methods, and reports that global approaches achieve performance and computational gains over local ones. The authors also provide theoretical guarantees and connect Katz link prediction to social balance.

  • Problem

    Signed-network analysis needs methods for positive and negative relationships, because unsigned-network techniques do not straightforwardly extend to sign prediction and clustering.

  • Method

    The paper combines social-imbalance measures, supervised higher-order-cycle features, and low-rank modeling for sign prediction and clustering.

  • Results

    Global low-rank methods generally outperform local triad- and cycle-based methods in prediction and clustering, with reported performance and computational gains.

  • Takeaways & Limitations

    The results support using global balance structure as an effective perspective for analyzing signed networks.

  • Takeaways & Limitations

    High-order-cycle features can become computationally infeasible beyond ℓ = 5 and difficult to interpret.

Abstract

from arXiv · show

The study of social networks is a burgeoning research area. However, most existing work deals with networks that simply encode whether relationships exist or not. In contrast, relationships in signed networks can be positive ("like", "trust") or negative ("dislike", "distrust"). The theory of social balance shows that signed networks tend to conform to some local patterns that, in turn, induce certain global characteristics. In this paper, we exploit both local as well as global aspects of social balance theory for two fundamental problems in the analysis of signed networks: sign prediction and clustering. Motivated by local patterns of social balance, we first propose two families of sign prediction methods: measures of social imbalance (MOIs), and supervised learning using high order cycles (HOCs). These methods predict signs of edges based on triangles and \ell-cycles for relatively small values of \ell. Interestingly, by examining measures of social imbalance, we show that the classic Katz measure, which is used widely in unsigned link prediction, actually has a balance theoretic interpretation when applied to signed networks. Furthermore, motivated by the global structure of balanced networks, we propose an effective low rank modeling approach for both sign prediction and clustering. For the low rank modeling approach, we provide theoretical performance guarantees via convex relaxations, scale it up to large problem sizes using a matrix factorization based algorithm, and provide extensive experimental validation including comparisons with local approaches. Our experimental results indicate that, by adopting a more global viewpoint of balance structure, we get significant performance and computational gains in prediction and clustering tasks on signed networks. Our work therefore highlights the usefulness of the global aspect of balance theory for the analysis of signed networks.

1 Introduction

The paper develops signed-network algorithms from social balance theory’s local patterns and global structure, targeting sign prediction and clustering. It argues that global methods provide performance and computational gains over local approaches.

  • 1 Introduction: The paper targets sign prediction and clustering in signed networks using a local-to-global perspective grounded in social balance theory.The motivation is that signed relationships require methods beyond straightforward extensions of unsigned-network algorithms.
  • 1 Introduction: Global methods are reported as superior to local methods on synthetic and real-world data sets.The paper frames this comparison as evidence for adopting a more global algorithmic viewpoint.
  • 1 Introduction: The authors propose sign prediction methods based on social imbalance measures, higher-order cycles, and low-rank modeling.Higher-order cycles broaden the local view beyond triangles, while low-rank modeling uses global balance structure.
  • 1 Introduction: The Katz measure, widely used for unsigned link prediction, receives a social-balance interpretation that yields a sign-prediction method.This connects an unsigned-network measure to signed-network prediction through balance theory.
  • 1 Introduction: The paper provides theoretical guarantees for sign prediction and signed-network clustering under mild structural conditions on balanced networks.It also presents a more detailed and unified treatment of earlier preliminary versions.

2 Signed Networks and Social Balance

This section defines signed networks and social balance, then connects local balance patterns in cycles and triads to global cluster structure. It identifies sign prediction and clustering as the paper’s two core inference tasks.

  • 2 Signed Networks and Social Balance: A signed network uses positive, negative, and unknown relationship entries, with zeros treated as unobserved signs rather than absent relationships.The paper focuses mainly on homogeneous, undirected signed networks.
  • 2 Signed Networks and Social Balance: Social balance defines a triad as balanced when it contains an even number of negative edges, extending the friend-enemy patterns of balance theory.The same even-negative-edge criterion is generalized to balanced ℓ-cycles.
  • 2 Signed Networks and Social Balance: A possibly incomplete network is balanced when its missing entries can be assigned signs so that the resulting complete network is balanced.This definition treats balance as a missing-value estimation problem.
  • 2 Signed Networks and Social Balance: Balanced networks have a global two-cluster structure with positive within-cluster edges and negative between-cluster edges.The theorem also allows the special case in which all edges are positive.
  • 2 Signed Networks and Social Balance: Weak balance generalizes balance by allowing complete networks to partition into k clusters with positive within-cluster and negative between-cluster edges.When k = 2, weak balance reduces to the classical balance characterization.
  • 2 Signed Networks and Social Balance: The paper focuses on two inference problems: predicting unknown relationship signs and partitioning network nodes into clusters.These tasks connect the local and global formulations of signed-network balance.

3 Local Methods: Exploiting Triads

The local approach predicts missing signs by comparing the imbalance induced by assigning positive or negative values to a query edge. It also derives supervised features from signed configurations around common neighbors and notes important scope constraints.

  • 3 Local Methods: Exploiting Triads: The cited equivalence between the local definitions holds only for complete graphs.This scope condition constrains how the local characterization transfers to incomplete networks.
  • 3 Local Methods: Exploiting Triads: For a missing query edge, the method constructs positive- and negative-assignment graphs and predicts the sign producing lower measured imbalance.Efficient computation of this comparison is a design requirement for the imbalance measure.
  • 3 Local Methods: Exploiting Triads: For triangles, imbalance prediction reduces to computing an entry of the squared signed adjacency matrix.The paper identifies this as a special case of a more general result.
  • 3 Local Methods: Exploiting Triads: Supervised local prediction uses features counting the 16 signed configurations of common neighbors around a candidate edge.These configurations correspond to a supervised k-cycle method with k = 3 and can be expressed using positive- and negative-edge matrices.
  • 3 Local Methods: Exploiting Triads: The imbalance-based formulation is limited to undirected networks, whereas learned balance-motivated feature weights can handle directed graphs.The directed-graph extension weakens reliance on the original social-balance formulation.

4 Going Global: Exploiting Longer Cycles

The paper extends balance-based sign prediction from short cycles to longer-cycle measures and high-order features, while addressing the resulting computational burden. It also connects the Katz rule to signed-network balance and uses logistic regression to predict edge signs from cycle-based features.

  • Measures of Social Imbalance: µ∞(A) > 0 iff the signed network A is unbalanced, for any positive coefficient sequence making the infinite sum well-defined.The result applies both to sums over simple cycles and to the modified sums over all cycles.
  • Measures of Social Imbalance: The all-cycle imbalance formulation avoids NP-complete simple-cycle enumeration while preserving the same unbalanced-network characterization.The modified definition sums over all cycles rather than only simple cycles.
  • Katz Measure Works for Signed Networks: With geometrically decaying weights β_ℓ = β^ℓ and β < 1/∥A∥2, the imbalance-based signed-edge prediction rule becomes the Katz prediction rule in closed form.This gives Katz a balance-theoretic interpretation for signed-network link prediction.
  • High-Order Cycle Features: Fourth-order cycle features yield 64 directed, signed variants, and general ℓ-cycle constructions yield 4^(ℓ−1) features.Each sign choice and transpose choice contributes four possibilities per matrix factor.
  • Reducing the Number of Features: High-order-cycle features grow exponentially with ℓ, making values beyond ℓ = 5 computationally infeasible and difficult to interpret.The experiments therefore use supervised HOC methods with ℓ ≤ 5.
  • Reducing the Number of Features: Ignoring edge directions and symmetrizing products reduces the ℓth-order feature count from O(4^ℓ) to O(2^ℓ), while retaining longer-cycle information for small ℓ.The feature count remains exponential, but construction becomes easier for small cycle orders.
  • Learning the Weights: The supervised HOC approach uses logistic regression to learn weights for cycle-imbalance features and predicts an edge sign from whether its positive probability exceeds 0.5.The feature map assigns cycle-based features to each queried vertex pair.

5 Fully Global: Low Rank Modeling

The paper uses the global structure of weakly balanced signed networks to formulate sign prediction as low-rank matrix completion and to support clustering from completed matrices. It establishes rank and recovery guarantees, then motivates scalable matrix factorization because convex methods require uniform sampling and do not scale well.

  • Complete k-weakly balanced networks have adjacency-matrix rank 1 when k ≤2 and rank k when k > 2.
  • 5.1 Sign Prediction via Convex Relaxation: Under bounded k, uniform sampling, and |Ω| ≥ Cτ^4n log^2 n, trace-norm minimization perfectly recovers the network with probability at least 1 − n^-3.
  • 5.1 Sign Prediction via Convex Relaxation: When group imbalance τ is constant, exact recovery requires only O(n log^2 n) observed entries.
  • 5.3 Sign Prediction via Matrix Factorization: Convex relaxation and SVP require uniform sampling and cannot scale to very large datasets, motivating gradient-based matrix factorization for large real networks.
  • 5.3 Sign Prediction via Matrix Factorization: The squared loss used in matrix factorization can penalize large correctly signed values, although only sign consistency matters for completion.
  • Clustering: The completed matrix's eigenvectors identify identical clusters under the recovery assumptions, providing a guarantee of perfect clustering.

6 Experimental Results

Experiments across synthetic and real-world signed networks show that global low-rank methods generally outperform local cycle-based methods for sign prediction, while also improving computational efficiency. The results support using global balance structure for prediction and clustering.

  • Evidence of Local and Global Patterns: Real networks exhibit stronger low-rank approximations than corresponding random networks, supporting low-rank modeling for sign prediction.For every tested small rank k, real networks have smaller observed-entry completion error than random networks.
  • Synthetic Datasets: On strongly balanced networks, MOI-∞ performs comparably to LR-SVP and LR-ALS, but global methods outperform cycle-based methods on general weakly balanced networks.MOI-based prediction is most appropriate when the underlying network has two balanced groups.
  • Synthetic Datasets: Global methods achieve high accuracy under weak balance and noise, while LR-SVP perfectly recovers the ground truth below noise level 0.05.LR-ALS also achieves perfect recovery at a smaller noise level.
  • Synthetic Datasets: LR-ALS performs best in most synthetic settings, including cases where observed entries are not uniformly distributed.It remains effective on power-law-distributed graphs, where LR-SVP is less accurate.
  • Real-life Datasets: Higher-order cycles improve prediction accuracy and reduce false-positive rates consistently across the three real networks.These results motivate moving from local cycle information toward fully global network structure.
  • Real-life Datasets: Global methods outperform cycle-based methods on real datasets, with LR-SIG and LR-SH further improving on LR-ALS.HOC-5 improves HOC-3 by less than 1.5%, whereas global methods improve HOC-5 by more than 2% across all datasets.

7 Related Work

Prior work established structural balance and weak balance in signed networks, while related research developed scalable analysis, prediction, matrix-completion, clustering, and correlation-clustering methods.

  • Structural-balance theory defined balanced triads and global organization in signed networks, while weak balance permits all-negative triads and yields mutually antagonistic groups.
  • The study evaluates its proposed clustering approach against signed Laplacian clustering on partially observed synthetic networks, with better performance reported both without and with noise.
  • Large-scale signed-network analysis became feasible only after real networks became more accessible, enabling computational studies of local and global structure.
  • Sign prediction relates to unsigned structural link prediction but requires methods that account for relationship signs rather than only node similarity.
  • Global sign prediction is closely related to low-rank matrix completion, with convex, projection, and factorization methods offering different algorithmic trade-offs.
  • Signed-network clustering draws on specialized approaches because weak balance does not apply to unsigned networks, while correlation clustering is NP-hard to optimize.

8 Conclusions and Future Work

The paper combines local cycle-based and global low-rank approaches for signed-network prediction and clustering, finding stronger and faster performance from global modeling. Future work includes extending balance analysis to heterogeneous signed networks.

  • The paper proposes MOI and HOC sign-prediction methods from local triads and cycles, then models prediction and clustering through low-rank matrix completion.
  • Matrix-factorization sign prediction outperforms MOIs and HOCs while requiring less running time, and matrix-completion clustering compares favorably with signed Laplacian clustering.
  • Future work should examine whether balance relationships, measurements, and local-to-global structure extend to heterogeneous signed networks.
Loading 1302.5145v2…