Skip to contents

Hypergraph Spectral Clustering

Source: R/clustering.R
spectral_clustering.Rd

Detect node communities in psychometric hypergraphs using hypergraph spectral clustering.

Usage

spectral_clustering(
  psych_hg,
  K = 2,
  weighted_l = FALSE,
  norm_laplacian = TRUE,
  seed = 42,
  n_init = 10
)

Arguments

psych_hg

A psychHypergraph object produced by build_hypergraph.

K

Integer specifying the number of clusters.

weighted_l

Logical; if TRUE, construct a weighted incidence matrix using O-information values. If FALSE, use a binary incidence matrix.

norm_laplacian

Logical; if TRUE, use the normalized hypergraph Laplacian proposed by Zhou et al. (2006).

seed

Random seed used for K-means initialization.

n_init

Number of random K-means starts.

Value

An object of class "psychHypergraphClustering" containing:

membership

Cluster assignment vector.

membership_matrix

Binary node-by-cluster membership matrix.

eigenvalues

Smallest Laplacian eigenvalues.

eigenvectors

Corresponding eigenvectors.

laplacian

Hypergraph Laplacian matrix.

embed_vectors

Spectral embedding used for clustering.

clusters

List of nodes belonging to each cluster.

summary

Cluster size summary.

parameters

Analysis settings and clustering information.

Details

The implementation follows the normalized hypergraph Laplacian framework proposed by Zhou, Huang, and Schölkopf (2006), where clustering is performed in a low-dimensional spectral embedding obtained from the hypergraph Laplacian. This function is similar to hypergraph community detection module HySC in python library hypergraphx (HGX).

Nodes are first embedded using the eigenvectors associated with the smallest non-trivial eigenvalues of the Laplacian matrix, and then partitioned into communities using K-means clustering.

Let \(H\) denote the hypergraph incidence matrix, \(D_v\) the node degree matrix, and \(D_e\) the hyperedge degree matrix.

The normalized hypergraph Laplacian is defined as:

$$ L = I - D_v^{-1/2} H D_e^{-1} H^T D_v^{-1/2} $$

Spectral clustering proceeds as follows:

  1. Construct the incidence matrix.

  2. Compute the hypergraph Laplacian.

  3. Extract the smallest eigenvectors.

  4. Normalize rows of the embedding matrix.

  5. Apply K-means clustering.

Nodes that do not participate in any hyperedge are treated as isolated nodes and assigned cluster membership 0.

References

Zhou, D., Huang, J., & Schölkopf, B. (2007). Learning with Hypergraphs: Clustering, Classification, and Embedding. In B. Schölkopf, J. Platt, & T. Hofmann (Eds), Advances in Neural Information Processing Systems 19 (pp. 1601-1608). The MIT Press. https://doi.org/10.7551/mitpress/7503.003.0205

See also

suggest_k, plot.psychHypergraphClustering

Examples

if (FALSE) { # \dontrun{

cl <- spectral_clustering(
  psych_hg = hg,
  K = 3
)

cl

plot(cl)

} # }