Improving Community Detection Performance in Heterogeneous Music Network by Learning Edge-Type Usefulness Distribution

Zheng Gao, Chun Guo, Shutian Ma, Xiaozhong Liu

TL;DR

This paper introduces a genetic algorithm-based approach to learn an Edge-type Usefulness Distribution (ETUD), which weights different types of interactions (e.g., "plays" vs. "bookmarks") in a music network. By learning these weights, the authors effectively convert complex heterogeneous networks into weighted homogeneous ones, allowing standard community detection algorithms to achieve significantly higher recommendation accuracy and lower search costs.

What Problem Does This Paper Address?

Modern music streaming services (MSS) like Spotify or Pandora generate "heterogeneous" networks—graphs where nodes represent different things (users, songs, artists, albums) and edges represent different behaviors (playing a song, adding to a playlist, following an artist).

Traditional community detection algorithms (like Louvain or Walktrap) were designed for "homogeneous" networks where all edges are identical. When applied to music, these methods often fail because they treat a casual "comment" the same as a repeated "play." While some heterogeneous-specific methods exist, they are often highly specialized and difficult to adapt to general recommendation tasks. The authors sought a way to bridge this gap: a method to "flatten" the complexity of a heterogeneous network into a format that classic, robust algorithms can handle without losing the semantic nuances of user behavior.

Methods

The core contribution is the ETUD (Edge-type Usefulness Distribution) framework, which uses a Genetic Algorithm (GA) to evolve the optimal weights for different edge types.

  1. Representation: Each "chromosome" in the GA is a vector of weights, where each weight corresponds to an edge type (e.g., user→song: plays).
  2. Fitness Function: To determine if a set of weights is "good," the authors use them to transform the network and then run a Personalized PageRank. The "fitness" is measured by how well the resulting song rankings match actual user listening history, calculated using NDCG@10 (Normalized Discounted Cumulative Gain).
  3. Evolutionary Process: The GA performs selection (via bootstrap sampling), cross-over (exchanging weights between chromosomes), and mutation (randomly perturbing weights) over several generations until the weights stabilize.
  4. Normalization: Because some edge types are semantically independent (e.g., artist→album vs. user→song), the authors group "dependent" edge types and normalize their weights so they are comparable within their specific context.

By multiplying the original edge counts by these learned ETUD weights, the heterogeneous graph becomes a weighted homogeneous graph ready for standard community detection.

Datasets

The researchers validated their model using a real-world dataset from Xiami Music, a major Chinese streaming service.

  • Nodes: ~168,000 total (including ~54k songs, ~38k users, and ~17k albums).
  • Edges: ~5.2 million total across 16 different types (e.g., user→song plays, playlist→song includes, user→artist comment).
  • Ground Truth: User listening history, where songs are labeled with scores (1–4) based on play count quartiles. 70% of the data was used for training (learning ETUD) and 30% for validation.

Key Insights and Ideas

  • Not All Edges are Equal: The model confirmed that certain behaviors are far more predictive of interest than others. For example, the "plays" edge type was found to be significantly more important for recommendation than "comments" or "bookmarks."
  • GA as an Optimizer for Non-Differentiable Tasks: The authors chose a Genetic Algorithm because the relationship between edge weights and final community-based rankings is mathematically "messy" and hard to differentiate, making standard gradient descent impractical.
  • The "Bridge" Strategy: Instead of inventing a brand-new community detection algorithm, this paper focuses on data transformation. This allows practitioners to keep using well-vetted tools like Louvain or Infomap while gaining the benefits of heterogeneous data awareness.

Key Results

The authors tested ETUD against six classic algorithms (DeepWalk, LINE, node2vec, Louvain, Infomap, and BigClam). In every single case, adding ETUD weights improved performance:

  • Searching Cost: This metric simulates how many "communities" a user would have to jump through to find their favorite songs. ETUD significantly reduced this cost across all baselines. For example, with the Infomap algorithm, the search cost for the top 100 songs dropped from ~19,784 to ~15,997.
  • Recommendation Accuracy (NDCG): Within-community recommendation accuracy saw a major boost. For the LINE algorithm, NDCG@5 jumped from 0.4883 to 0.5153. For DeepWalk, it rose from 0.6932 to 0.7529.

Limitations and Future Work

  • Computational Complexity: Genetic algorithms can be computationally expensive and slow to converge, especially as the number of edge types and the size of the network grow.
  • Static Weights: The current model learns a global distribution of edge usefulness. However, different users might value interactions differently (e.g., one user's "bookmarks" might be more meaningful than another's "plays").
  • Future Directions: The authors suggest exploring Reinforcement Learning (RL) as a more sophisticated alternative to Genetic Algorithms for estimating the ETUD in the future.

Summary updated

Abstract

With music becoming an essential part of daily life, there is an urgent need to develop recommendation systems to assist people targeting better songs with fewer efforts. As the interactions between users and songs naturally construct a complex network, community detection approaches can be applied to reveal users’ potential interests on songs by grouping relevant users & songs to the same community. However, as the types of interaction could be heterogeneous, it challenges conventional community detection methods designed originally for homogeneous networks. Although there are existing works on heterogeneous community detection, they are mostly task-driven approaches and not feasible for specific music recommendation. In this paper, we propose a genetic based approach to learn an edge-type usefulness distribution (ETUD) for all edge-types in heterogeneous music networks. ETUD can be regarded as a linear function to project all edges to the same latent space and make them comparable. Therefore a heterogeneous network can be converted to a homogeneous one where those conventional methods are eligible to use. We validate the proposed model on a heterogeneous music network constructed from an online music streaming service. Results show that for conventional methods, ETUD can help to detect communities significantly improving music recommendation accuracy while simultaneously reducing user searching cost.
BibTeX
@inproceedings{gao2022improving,
  author = {Zheng Gao and Chun Guo and Shutian Ma and Xiaozhong Liu},
  title = {{Improving Community Detection Performance in Heterogeneous Music Network by Learning Edge-Type Usefulness Distribution}},
  booktitle = {Iconference},
  year = {2022},
  doi = {10.1007/978-3-030-96960-8\_5},
}

Loading related content...

Figure