PaperlayerView exact revision on arXiv

Source-linked AI summary

Relation Strength-Aware Clustering of Heterogeneous Information Networks with Incomplete Attributes

Yizhou Sun, Charu C. Aggarwal, Jiawei Han

arXiv:1201.6563v1cs.DB

TL;DR

The paper addresses clustering in heterogeneous information networks when attributes are incomplete and link types have unequal semantic importance. It introduces a probabilistic model and iterative algorithm that jointly learns object clusters and relation strengths, reporting effective, efficient, and scalable performance across real and synthetic data.

  • Problem

    Clustering is challenging because object attributes may be incomplete and different link types may have different semantic importance.

  • Method

    GenClus uses a probabilistic model with user-specified attributes and learned relation strengths, alternating between clustering and link-weight optimization.

  • Results

    The experiments on real and synthetic data demonstrate the method’s effectiveness and efficiency, while four-thread parallelization improves execution time by a factor of 3.19.

  • Takeaways & Limitations

    The approach supports clustering heterogeneous networks with incomplete attributes while adapting the influence of different semantic link types to the clustering purpose.

  • Takeaways & Limitations

    The paper does not determine the best number of clusters K and treats it as a separate model-selection problem.

Abstract

from arXiv · show

With the rapid development of online social media, online shopping sites and cyber-physical systems, heterogeneous information networks have become increasingly popular and content-rich over time. In many cases, such networks contain multiple types of objects and links, as well as different kinds of attributes. The clustering of these objects can provide useful insights in many applications. However, the clustering of such networks can be challenging since (a) the attribute values of objects are often incomplete, which implies that an object may carry only partial attributes or even no attributes to correctly label itself; and (b) the links of different types may carry different kinds of semantic meanings, and it is a difficult task to determine the nature of their relative importance in helping the clustering for a given purpose. In this paper, we address these challenges by proposing a model-based clustering algorithm. We design a probabilistic model which clusters the objects of different types into a common hidden space, by using a user-specified set of attributes, as well as the links from different relations. The strengths of different types of links are automatically learned, and are determined by the given purpose of clustering. An iterative algorithm is designed for solving the clustering problem, in which the strengths of different types of links and the quality of clustering results mutually enhance each other. Our experimental results on real and synthetic data sets demonstrate the effectiveness and efficiency of the algorithm.

1. INTRODUCTION

Heterogeneous information networks combine multiple object and link types, but clustering them is difficult when attributes are incomplete and relations have unequal semantic importance. The paper proposes GenClus, a probabilistic model and iterative algorithm that jointly learns clustering assignments and relation strengths, with experiments demonstrating effectiveness and efficiency.

  • Heterogeneous information networks contain diverse objects, relations, and attributes, supporting applications such as customer, voter, and weather-pattern segmentation.
  • Incomplete or absent attribute observations can prevent purely attribute-based methods from correctly identifying object clusters.
  • Different link types carry different semantic meanings and may contribute unequally to clustering for a given purpose.
  • GenClus models attributes probabilistically and learns relation-specific importance weights while clustering heterogeneous objects in a common hidden space.
  • An iterative algorithm alternates between optimizing clustering results and link-type strengths, which mutually enhance each other.

2. PROBLEM DEFINITION

The paper formulates heterogeneous-network clustering as learning soft memberships for all objects from selected attributes and typed links. The problem setting emphasizes incomplete observations, unequal relation strengths, and the need to learn both cluster memberships and relation importance.

  • 2.1 The Data Structure: A heterogeneous information network is a directed graph whose typed objects and links encode distinct semantic roles and relations.
  • 2.2 The Clustering Problem: The model maps every object into a unified hidden space using a user-specified attribute subset and links from different types.
  • 2.2 The Clustering Problem: Objects may have partial or missing attributes, making interpolation difficult and limiting purely attribute-based clustering.
  • 2.2 The Clustering Problem: Different link types can have different strengths when propagating cluster information, so their importance must be learned automatically.
  • 2.2 The Clustering Problem: The formal objectives are to learn a soft membership matrix for all objects and importance weights for every link type.
  • 2.2 The Clustering Problem: The number of clusters K is not determined by this paper and is treated as a separate model-selection problem.

3. THE CLUSTERING MODEL

The model represents incomplete attributes with mixture models and enforces structural consistency through link-aware membership probabilities. It learns relation-type strengths jointly with clustering, while accommodating asymmetric links and regularizing the strength parameters.

  • Attribute Modeling: The model treats each object’s attribute observations as mixture-model data, with cluster membership probabilities serving as component mixing proportions.It supports text attributes with categorical distributions and numerical attributes with Gaussian distributions.
  • Unified Probabilistic Model: The joint likelihood combines the generative probability of observed attributes with the probability of cluster configurations given the network structure.The model estimates clustering configurations and component parameters from both attribute observations and network links.
  • Structural Consistency: Structural consistency increases when linked objects have similar membership vectors and decreases as link weights or learned relation strengths increase.The feature function is designed to reflect both input link weights and learned importance values for relation types.
  • Structural Consistency: The asymmetric cross-entropy feature function allows link direction to matter, as in citation networks where one object’s relation to another need not be reciprocal.The proposed feature function satisfies the stated similarity, strength, and asymmetry criteria.
  • Unified Probabilistic Model: A Gaussian prior regularizes the learned relation strengths, with γ constrained to nonnegative values and σ set to 0.1 in the experiments.The regularized objective combines the attribute and structural terms while discouraging overfitting of γ.

4. THE CLUSTERING ALGORITHM

GenClus alternates between optimizing object cluster memberships and learning nonnegative strengths for link types. It combines attribute-based EM updates with pseudo-log-likelihood-based link-strength optimization and is approximately linear in network size for sparse networks.

  • Alternating optimization: GenClus alternates cluster optimization with link type strength learning until convergence, allowing clustering results and relation strengths to mutually improve.The outer process updates Θ and γ, while the cluster step optimizes Θ and β and the strength step optimizes γ.
  • Cluster optimization: The cluster optimization step uses both link information and available attributes to estimate memberships and attribute parameters.An EM algorithm updates hidden observation labels, cluster memberships, and attribute parameters for categorical and Gaussian attributes.
  • Link type strength learning: The strength-learning step assigns lower weights to link types whose connected objects are inconsistent with current clusters and higher weights to more consistent types.With clustering parameters fixed, the objective retains structural consistency and regularization terms that depend on γ.
  • Approximate optimization: Because the exact partition function is intractable, GenClus replaces the full likelihood with a pseudo-log-likelihood based on each object and its out-link neighbors.The approximation factorizes the likelihood into conditional probabilities that depend only on neighboring objects, with each link counted once in the selected local patch.
  • Algorithm integration: GenClus uses EM inside the cluster step and Newton-Raphson inside the strength step, with an all-1 initialization that initially treats link types equally.The integrated algorithm has an outer alternating iteration and two corresponding inner optimization iterations.
  • Complexity: The overall time complexity is O(t(t1(Kd1|V|+K|E|)+t2|R|2.376)), and is approximately linear in the number of objects when the network is sparse.Here t, t1, and t2 denote outer and inner iteration counts, while |R| is the number of relations.

5. EXPERIMENTAL RESULTS

Experiments on real and synthetic heterogeneous networks evaluate GenClus for clustering accuracy, link prediction, learned relation strengths, mutual learning, efficiency, and parallelization. GenClus generally outperforms baselines, adapts to incomplete attributes and relation heterogeneity, and scales through efficient and parallelizable computation.

  • Experimental Setup: GenClus was evaluated on two real DBLP networks and synthetic weather sensor networks using NMI and link prediction accuracy.The DBLP data contain papers and authors from four research areas; the sensor networks model temperature and precipitation patterns.
  • Clustering Accuracy: GenClus is more robust than NetPLSA on the harder ACP network, where some object types lack text attributes.NetPLSA produced almost random predictions for authors in the ACP network.
  • Clustering Accuracy: 17 out of 18 cases favored GenClus over k-means and spectral clustering, while GenClus was more stable under varying observations and required no manually specified combination weights.The baselines used interpolation for incomplete attributes, and the spectral method assigned equal weights to network and attribute components.
  • Link Prediction Accuracy: GenClus achieved the best link prediction accuracy across the tested similarity functions, with asymmetric −H(θj, θi) performing especially well.The asymmetric function was particularly effective when out-link and in-link neighbors differed.
  • Relation Strength Analysis: Learned relation strengths reflected network semantics: ⟨P, A⟩ received weight 13.30 versus 3.13 for ⟨P, C⟩ in the ACP network.In the AC network, ⟨A, C⟩ was more important than ⟨A, A⟩; for weather sensors, T-typed neighbors were more trusted than P-typed neighbors.
  • Mutual Learning and Efficiency: The experiments supported mutual improvement between clustering quality and learned relation strengths, while EM execution scaled with network size and improved 3.19-fold using four parallel threads.The EM component was identified as the bottleneck and as easy to parallelize.

6. RELATED WORK

Prior work combines attributes and links for clustering, but existing approaches generally assume homogeneous data or treat all relations similarly. GenClus instead assigns relation-specific importance weights to reflect their semantic relevance to a clustering purpose.

  • Existing clustering methods often require homogeneous network links, objects, and attributes, limiting their applicability to heterogeneous information networks.
  • Attribute-link methods use distinct philosophies: combining similarity measures, modeling links equally, or smoothing attribute-based assignments.
  • These approaches do not model different relation types as having different importance for a specified clustering purpose.
  • GenClus treats linked objects as more likely to share cluster memberships and assigns each relation type a distinct importance weight.

7. CONCLUSIONS

GenClus clusters heterogeneous information networks with mixed object, link, and attribute types, while accommodating incomplete attributes and learning relation importance for the clustering purpose. Experiments report advantages over competing methods and study case applications and efficiency.

  • GenClus clusters heterogeneous networks containing different link and attribute types, including numerical and text attributes.
  • The method uses a specified subset of attributes and supports nodes with incomplete attribute information.
  • GenClus learns the importance of semantic link types to meet the user’s clustering demand.
  • Experiments report advantages over competing methods through case studies and an algorithm-efficiency study.

A. EM ALGORITHM PROOF

The EM algorithm alternates between estimating hidden observation-level cluster labels and updating model parameters. The updates use the expected objective and constrained maximization of its parameters.

  • In the E-step, hidden cluster-label probabilities for observations are derived from the current parameters.
  • The Q function is formed as the conditional expectation of the complete objective under the current hidden-variable distribution.
  • In the M-step, parameters Θ and β are updated by maximizing the Q function with Lagrangian multipliers.
  • The update for each object’s θ parameter fixes the other parameters and β at their previous-iteration values.
  • The indicator 1{v∈V_X} equals 1 when object v contains attribute X and otherwise equals 0.
  • The β parameters are updated for each cluster using a corresponding maximization rule.

B. CONCAVITY PROOF

The concavity proof establishes that the relevant objective has negative-definite curvature. It combines positive-semidefinite covariance matrices with a positive-definite diagonal term under negative weights.

  • The function g′_2(γ) defined in Eq. (14) is shown to be concave.
  • Its Hessian is characterized through covariance terms involving the normalization function of the conditional distribution.
  • Each conditional covariance matrix is positive semidefinite, while the diagonal σ^2 I term is positive definite.
  • Their negatively weighted linear combination is negative definite, supporting the concavity conclusion.

C. SYNTHETIC WEATHER NETWORK GENERATOR

The generator creates synthetic weather sensor networks by combining spatial nearest-neighbor links, temperature and precipitation attributes, and probabilistic weather-pattern memberships. User-specified network parameters control sensor counts, neighborhood structure, cluster patterns, and attribute observations.

  • Network construction: Sensors are network objects, temperature and precipitation are attributes, and links represent k-nearest-neighbor relationships.Each sensor follows a mixture model of different weather patterns.
  • Weather-pattern generation: K weather patterns are Gaussian distributions over temperature and precipitation, each specified by a mean and covariance matrix; the circle is divided into K equal rings.
  • Network construction: The generator uses #T temperature sensors, #P precipitation sensors, and k nearest neighbors as input parameters.
  • Network construction: Sensor locations are randomly assigned within a unit circle, with an out-link to each of the k nearest sensors of the relevant type.
  • Weather-pattern generation: Cluster membership depends on each sensor’s reciprocal distance to the center for each weather region.
  • Attribute generation: Attribute observations are controlled by #obs and generated from a mixture model using coefficients determined by cluster membership.
Loading 1201.6563v1…