PaperlayerView exact revision on arXiv

Source-linked AI summary

GEMSEC: Graph Embedding with Self Clustering

Benedek Rozemberczki, Ryan Davies, Rik Sarkar, Charles Sutton

arXiv:1802.03997v3cs.SI

TL;DR

Existing graph embeddings do not explicitly preserve social communities, motivating GEMSEC’s joint embedding-and-clustering approach. GEMSEC adds clustering and social-network regularization to sequence-based neighborhood preservation, and the experiments report strong clustering and recommendation performance with efficient, robust behavior.

  • Problem

    Existing sequence-based graph embeddings preserve sampled graph proximity but lack an explicit preference for social communities.

  • Method

    GEMSEC jointly learns node embeddings and clusters by extending sequence-based negative-log-likelihood optimization with a clustering cost and smoothness regularization.

  • Results

    GEMSEC outperforms reported neighborhood-based, multi-scale, and community-aware embedding baselines on clustering quality, while also supporting recommendation tasks.

  • Takeaways & Limitations

    The joint formulation lets embedding and clustering inform each other, producing separated communities aligned with network neighborhoods.

Abstract

from arXiv · show

Modern graph embedding procedures can efficiently process graphs with millions of nodes. In this paper, we propose GEMSEC -- a graph embedding algorithm which learns a clustering of the nodes simultaneously with computing their embedding. GEMSEC is a general extension of earlier work in the domain of sequence-based graph embedding. GEMSEC places nodes in an abstract feature space where the vertex features minimize the negative log-likelihood of preserving sampled vertex neighborhoods, and it incorporates known social network properties through a machine learning regularization. We present two new social network datasets and show that by simultaneously considering the embedding and clustering problems with respect to social properties, GEMSEC extracts high-quality clusters competitive with or superior to other community detection algorithms. In experiments, the method is found to be computationally efficient and robust to the choice of hyperparameters.

I. INTRODUCTION

GEMSEC jointly learns node embeddings and clusters, extending sequence-based embedding with clustering and social-network regularization to produce separated communities and strong empirical performance.

  • Community detection groups nodes that connect more densely internally than to the rest of a network, while embeddings place nodes in a feature space for machine-learning tasks.Embedding distances represent structural differences and support labeling, regression, link prediction, and visualization.
  • Sequence-based methods use sampled node sequences, such as random walks, to place graph-proximate nodes nearby, but do not explicitly preserve social communities.DeepWalk and Node2Vec are cited as popular examples.
  • On Zachary’s Karate club graph, GEMSEC produces more tightly clustered communities than the depicted comparison embedding.The figure distinguishes the instructor’s and president’s groups by node color.
  • GEMSEC jointly considers embedding and clustering, allowing the two solutions to inform each other while separating clusters in the embedding space.Its objective extends sequence-based neighborhood preservation with a clustering cost.
  • Smoothness regularization aligns clusters with network neighborhoods, producing more coherent community detection when socially similar nodes have overlapping friend groups.The regularization incorporates social-network knowledge into the optimization.
  • GEMSEC is evaluated against neighborhood-based, multi-scale, and community-aware embedding methods, with reported gains in clustering quality, recommendation tasks, and computational efficiency.The paper also reports robustness to hyperparameter changes and linear runtime in graph size.

II. RELATED WORK

Related work establishes sequence-based node embedding and community-aware alternatives, while GEMSEC extends the former with an efficient, controllable clustering objective.

  • Metric and network embedding research represents discrete structures in trees, vector spaces, or richer spaces such as hyperbolic geometries.
  • Sequence-based node embeddings learn vector features from sampled graph sequences and support prediction, visualization, link prediction, and community detection.Sampling strategies include truncated and second-order random walks, skips, and diffusion graphs.
  • Earlier community-aware methods use nonnegative matrix factorization or Gaussian-mixture assumptions, whereas GEMSEC is more scalable, sampling-method independent, and computationally efficient.M-NMF adds a modularity constraint, DANMF is hierarchical, and ComE models communities with Gaussian mixtures.
  • III. GRAPH EMBEDDING WITH SELF CLUSTERING: A node embedding maps each graph node v to a d-dimensional feature representation, with neighborhood windows NS(v) sampled from graph sequences.The experiments use unweighted first- and second-order random walks for node sampling.
  • III. GRAPH EMBEDDING WITH SELF CLUSTERING: The sequence-based objective minimizes the negative log-likelihood of sampled neighborhoods using conditional factorization and symmetric pairwise feature interactions.A softmax over pairwise dot products defines the neighborhood probability.
  • III. GRAPH EMBEDDING WITH SELF CLUSTERING: The resulting optimization combines neighborhood preservation with clustering, while its partition term constrains embedding volume and its neighborhood term attracts nodes with similar sampled contexts.

A. Learning to Cluster

GEMSEC augments sequence-based embedding with a clustering cost that jointly optimizes node representations and cluster centers. The objective balances neighborhood preservation with proximity to the nearest cluster center, while initialization affects optimization behavior.

  • Learning to Cluster: GEMSEC minimizes a loss over node embeddings f and cluster-center positions µ, combining neighborhood preservation with a k-means-like clustering cost.The clustering weight is controlled by γ.
  • Learning to Cluster: Each cluster center µc is a d-dimensional embedding-space vector, and nodes are assigned according to distance from their nearest center.
  • Learning to Cluster: Evaluating the partition function over all source nodes has O(|V|^2) runtime, so GEMSEC approximates it with negative sampling.Negative sampling is described as a form of noise-contrastive estimation.
  • Learning to Cluster: A high clustering weight γ can pull a node toward a center that does not contain its graph neighbors, producing an incorrect cluster assignment.Figure 2a illustrates this failure mode with a white node captured by blue nodes.
  • Learning to Cluster: Empty clusters receive zero center-gradient updates, so initialization can leave a cluster center empty and substantially affect clustering performance.The method initializes cluster centers and embedding weights from the same uniform distribution.

B. GEMSEC algorithm

GEMSEC uses an efficient sampled training procedure with annealed clustering and learning-rate coefficients. It combines random-walk sequence features, gradient updates, and negative sampling to make optimization tractable.

  • GEMSEC algorithm: GEMSEC starts with a low clustering weight γ0 ∈ [0, 1] and anneals it to 1 so clustering does not overpower graph information.The clustering coefficient follows an exponential annealing rule.
  • GEMSEC algorithm: The algorithm initializes model weights, repeatedly samples vertex sequences, shuffles vertices before each epoch, and updates parameters with an optimizer.The implementation uses a variant of stochastic gradient descent, Adam.
  • GEMSEC algorithm: The learning rate α is annealed linearly from α0 toward αF during training.
  • GEMSEC algorithm: Sequences have length l and use context window size ω to extract features for the embedding updates.
  • GEMSEC algorithm: Negative sampling draws k noise samples for each positive sample, making the first cost term tractable during gradient descent.

C. Smoothness Regularization for coherent community detection

GEMSEC adds social-network regularization to align embeddings and clusters with community structure. Neighborhood overlap supplies edge weights that encourage more coherent communities and sharper cluster boundaries.

  • Smoothness Regularization for coherent community detection: GEMSEC uses regularization to incorporate social-network properties when the clustering objective and underlying communities do not align.
  • Smoothness Regularization for coherent community detection: The regularization term Λ penalizes embedding distances across sampled edges according to a social-network edge weight function w.
  • Smoothness Regularization for coherent community detection: Neighborhood overlap, defined as the fraction of common neighbors relative to the union of neighbor sets, is used as the edge weight.Experiments on real data identify neighborhood overlap as a strong indicator of relation strength.
  • Smoothness Regularization for coherent community detection: The target matrix M represents connectivity using the number of paths of length at most ω between node pairs.
  • Smoothness Regularization for coherent community detection: On the barbell graph, regularized optimization produces sharper communities than the fuzzy target matrix and sampled DeepWalk approximation.Figure 3 compares the graph, target matrix, DeepWalk output, and regularized output.

IV. EXPERIMENTAL EVALUATION

The evaluation measures GEMSEC variants on cluster quality, scalability, robustness, and downstream predictive performance. Across all reported measures, GEMSEC performs at least as well as existing methods.

  • IV. EXPERIMENTAL EVALUATION: GEMSEC outperforms or matches existing methods across cluster quality, scalability, robustness, and downstream predictive performance measures.

A. Datasets

The evaluation uses newly collected real-world social-network datasets from Facebook and Deezer, covering varied graph characteristics and user-interest information.

  • The study uses public-API social-network datasets collected specifically for evaluating GEMSEC.
  • Facebook graphs represent mutual-like networks among verified pages, including television shows, politicians, athletes, and artists.
  • Deezer graphs contain user friendship networks from Croatia, Hungary, and Romania, with genres curated from users’ liked songs.

B. Standard parameter settings

The experiments use fixed random-walk, embedding, clustering, and optimization settings, with selected learning-rate and regularization values determined through parameter choices.

  • Experiments use random walks of length 80, with five truncated random walks per source node.
  • The embeddings use a window size of 5, 16 dimensions, and 20 extracted cluster centers.
  • Noise contrastive estimation uses 10 negative examples, and the initial clustering-cost coefficient is selected from 10^-1, 10^-2, and 10^-3.
  • The smoothness regularization hyperparameter is 0.0625, with Jaccard’s coefficient used as the penalty weight.

C. Cluster Quality

GEMSEC variants achieve strong clustering quality on Facebook datasets, with Smooth GEMSEC2 outperforming the baselines in modularity and smoothness improving clustering outcomes.

  • Cluster quality is evaluated by modularity on Facebook page networks, assuming each node belongs to a single community.
  • The comparison includes neighborhood-based, multi-scale, and community-aware embedding methods, including DeepWalk, LINE, Node2vec, Walklets, ComE, M-NMF, and DANMF.
  • Figure 3 contrasts DeepWalk target and reconstructed matrices, showing sharper communities with regularized optimization than with standard DeepWalk.
  • Smooth GEMSEC2 outperforms the baselines in mean modularity on the Facebook datasets, using ten repeated embedding experiments with errors reported as two standard deviations.
  • Smooth GEMSEC, GEMSEC2, and Smooth GEMSEC2 consistently outperform neighborhood-conserving and competing community-aware embedding methods.
  • Smoothness regularization has a sometimes non-significant but definitely positive effect on the clustering performance of DeepWalk, GEMSEC, and GEMSEC2.

D. Sensitivity Analysis for hyperparameters

The sensitivity analysis evaluates clustering quality under hyperparameter changes using modularity and finds GEMSEC variants broadly robust, especially with smoothness regularization.

  • The analysis measures the mean modularity of ten experiments for each perturbed hyperparameter setting.
  • GEMSEC variants produce high-quality clusters across a wide range of parameter settings.
  • Smoothness regularization makes GEMSEC models more robust to hyperparameter changes, particularly when varying the number of clusters.
  • Above a threshold, truncated-walk length and the number of walks per source node have only a marginal effect on community-detection performance.
  • Figure 4 presents cluster-quality sensitivity to parameter changes measured by modularity.

E. Music Genre Recommendation

GEMSEC2 significantly outperforms other methods on Deezer music-genre prediction across three countries, while GEMSEC’s optimization runtime grows linearly with graph size.

  • GEMSEC2 significantly outperforms the other methods on all three countries’ Deezer datasets, with advantages ranging from 3.03% to 4.95%.Performance is measured using F1 scores from 10 experimental repetitions.
  • Smooth GEMSEC2 has lower accuracy but outperforms DeepWalk, LINE, Node2Vec, Walklets, ComE, M-NMF, and DANMF on all datasets.
  • Doubling the graph size doubles GEMSEC’s optimization time, indicating linear runtime growth.Clustering and regularization increase cost but retain similar growth.
  • GEMSEC learns node embeddings and clustering jointly, with smoothness regularization incorporating social network properties.
Loading 1802.03997v3…