PaperlayerView exact revision on arXiv

Source-linked AI summary

Clustering with Multi-Layer Graphs: A Spectral Perspective

Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, Nikolai Nefedov

arXiv:1106.2233v1cs.LGcs.CVcs.SIstat.ML

TL;DR

The paper asks how to combine multiple graph layers that represent different modalities while improving clustering over independent-layer approaches. It constructs a joint spectrum using joint matrix factorization and graph regularization, then applies spectral clustering. Across real-world social-network datasets, the methods outperform baseline methods on three clustering metrics and are competitive with a state-of-the-art technique.

  • Problem

    The problem is to combine multiple graph layers sharing vertices but containing different edges into a joint spectrum that supports effective clustering.

  • Method

    The paper combines graph Laplacian spectra through joint matrix factorization and graph-based spectral regularization, using the resulting joint spectrum for spectral clustering.

  • Results

    Across several real-world social-network datasets, the proposed methods outperform baseline methods on three clustering metrics and are very competitive with a state-of-the-art technique.

  • Takeaways & Limitations

    The joint-spectrum concept provides a framework for analyzing multimodal data represented by multi-layer graphs and extending spectral analysis to multi-dimensional cases.

Abstract

from arXiv · show

Observational data usually comes with a multimodal nature, which means that it can be naturally represented by a multi-layer graph whose layers share the same set of vertices (users) with different edges (pairwise relationships). In this paper, we address the problem of combining different layers of the multi-layer graph for improved clustering of the vertices compared to using layers independently. We propose two novel methods, which are based on joint matrix factorization and graph regularization framework respectively, to efficiently combine the spectrum of the multiple graph layers, namely the eigenvectors of the graph Laplacian matrices. In each case, the resulting combination, which we call a "joint spectrum" of multiple graphs, is used for clustering the vertices. We evaluate our approaches by simulations with several real world social network datasets. Results demonstrate the superior or competitive performance of the proposed methods over state-of-the-art technique and common baseline methods, such as co-regularization and summation of information from individual graphs.

I. INTRODUCTION

The paper addresses clustering when users are represented by multiple graph layers that capture different interaction modalities. It proposes combining their spectra into a joint spectrum for spectral clustering, motivated by complementary and uneven information across layers.

  • Motivation: Multi-layer graphs share vertices but use different edges to represent modalities such as proximity, movement similarity, and phone communication.The MIT example uses Saturday-night proximity, physical movement similarity, and phone communication layers.
  • Approach: The proposed methods combine multiple Laplacian spectra through joint matrix factorization and graph regularization, then use the resulting representation for clustering.The factorization shares eigenvectors across layers, while regularization treats eigenvectors from one graph as functions on another.
  • Results: Experiments on real-world social-network datasets show that the proposed methods outperform baseline methods on three clustering metrics and are competitive with a state-of-the-art technique.The comparisons include methods such as summation of information from individual graphs.
  • Significance: The joint-spectrum concept is presented as useful for analyzing multimodal data represented by multi-layer graphs and for generalizing spectral analysis to multi-dimensional cases.This broader significance is stated beyond the reported clustering improvements.
  • Motivation: Phone-call links can be more reliable indicators of friendship, but their sparsity and disconnected components make global clustering difficult.The proximity and movement layers can provide information for users that phone-call data leaves isolated.
  • Problem: The paper seeks a joint spectrum that combines information from multiple graph layers and supports effective spectral clustering of the shared vertices.The target is a unified clustering based on a combination of layer-specific information.

III. SPECTRAL CLUSTERING

Spectral clustering represents graph vertices using eigenvectors of a Laplacian and applies K-means to that low-dimensional embedding. The normalized version used here relies on the random-walk Laplacian and its eigenvectors associated with the smallest eigenvalues.

  • Spectral clustering: Spectral clustering uses the graph Laplacian spectrum to construct a low-dimensional representation of graph vertices.For a weighted undirected graph, the Laplacian is formed from the degree matrix and adjacency matrix.
  • Spectral clustering: The paper adopts normalized spectral clustering based on the random-walk Laplacian Lrw.This choice preserves the method’s connection to random-walk processes on graphs.
  • Algorithm: The algorithm computes the first k eigenvectors of Lrw, representing each vertex by the corresponding row of the eigenvector matrix.These eigenvectors correspond to the k smallest eigenvalues.
  • Algorithm: K-means clusters the vertex representations in the k-dimensional embedding space to produce the final assignment.The embedding converts the graph clustering problem into clustering points in Euclidean space.
  • Interpretation: The spectral embedding is the key representation because it can reveal intrinsic relationships among vertices and make the clustering task easier.The paper connects its effectiveness to normalized graph cuts, random walks, and perturbation theory.

IV. CLUSTERING WITH GENERALIZED EIGEN-DECOMPOSITION

This method constructs a joint spectrum by approximating every graph Laplacian with shared eigenvectors and layer-specific eigenvalue matrices, then clusters vertices from the resulting embedding.

  • IV. CLUSTERING WITH GENERALIZED EIGEN-DECOMPOSITION: The method approximates each graph Laplacian using shared joint eigenvectors and a layer-specific eigenvalue matrix.The shared eigenvectors form the joint spectrum across layers.
  • IV. CLUSTERING WITH GENERALIZED EIGEN-DECOMPOSITION: Its objective combines reconstruction error across layers, norm regularization for numerical stability, and a constraint making Q the inverse of P.Parameters α and β balance these three terms.
  • IV. CLUSTERING WITH GENERALIZED EIGEN-DECOMPOSITION: Because the objective is not jointly convex in P and Q, the algorithm alternates optimization over the two variables and seeks a local minimum.Initialization uses eigenvectors from the most informative graph layer, and each variable is solved with limited-memory BFGS.
  • IV. CLUSTERING WITH GENERALIZED EIGEN-DECOMPOSITION: The first k columns of P form the spectral embedding, whose vertex rows are clustered with the K-means algorithm.P is the computed set of joint eigenvectors shared by the graph layers.
  • IV. CLUSTERING WITH GENERALIZED EIGEN-DECOMPOSITION: Unlike a related adjacency-matrix factorization approach, this method factorizes graph Laplacian matrices to obtain a shared spectrum.The comparison concerns both the approximated matrices and the factorization procedure.

V. CLUSTERING WITH SPECTRAL REGULARIZATION

The second method regularizes spectral representations across layers while weighting layers by their respective importance, preserving layer-specific information for clustering.

  • V. CLUSTERING WITH SPECTRAL REGULARIZATION: The method treats graph layers according to their respective importance rather than combining them equally.This design is intended to preserve the specificities of individual layers during clustering.
  • V. CLUSTERING WITH SPECTRAL REGULARIZATION: Algorithm 2 computes each layer’s random-walk Laplacian from its weighted adjacency matrix before solving for a joint eigenvector matrix.The input contains M weighted adjacency matrices and a target number of clusters k.
  • V. CLUSTERING WITH SPECTRAL REGULARIZATION: The algorithm embeds each vertex using a row of the first k columns of the joint eigenvector matrix and applies K-means to those representations.The output is the resulting cluster assignment.
  • V. CLUSTERING WITH SPECTRAL REGULARIZATION: The resulting layer-sensitive representation is designed to preserve information specific to each graph layer in the clustering process.

A. Intuition

The intuition is that low-frequency Laplacian eigenvectors provide smooth graph embeddings, so joint eigenvectors can represent connectivity across layers while retaining layer-specific characteristics.

  • A. Intuition: The first eigenvector has eigenvalue 0 and is the constant vector, while subsequent normalized eigenvectors are orthogonal to it.These conditions remove the trivial constant solution and normalize the remaining eigenvectors.
  • A. Intuition: A one-dimensional mapping seeks vertex values that keep connected vertices close while enforcing orthogonality to the constant vector and unit norm.The edge weights determine the smoothness objective over the mapping.
  • A. Intuition: The Fiedler vector, corresponding to the second-smallest Laplacian eigenvalue, solves the constrained mapping problem.Its mapping keeps strongly connected vertices close on the line.
  • A. Intuition: Eigenvectors associated with sufficiently small eigenvalues are smooth on the graph and can represent graph connectivity in a low-dimensional spectral embedding.Spectral clustering uses the first k such eigenvectors to form the embedding.
  • A. Intuition: The proposed joint eigenvectors are intended to be smooth across all layers while highlighting differences among their graph structures.This motivates combining spectra rather than treating every layer identically.

B. Jointly smooth spectrum computation

Spectral regularization constructs joint eigenvectors by keeping each function close to an eigenvector from one layer while enforcing smoothness on another, then uses the resulting spectrum for clustering.

  • B. Jointly smooth spectrum computation: The regularization method computes a jointly smooth spectrum by solving an optimization problem across two graph layers.
  • B. Jointly smooth spectrum computation: Each optimization balances closeness to an eigenvector from G(1) against smoothness on G(2), with λ controlling the trade-off.The resulting function is intended to be smooth on both graphs.
  • B. Jointly smooth spectrum computation: The optimization has a closed-form solution, and solving the problems for the nonconstant eigenvectors yields the joint spectrum.The first k joint eigenvectors form the spectral embedding used for clustering.
  • B. Jointly smooth spectrum computation: G(1) supplies the eigenvectors, whereas G(2) supplies the graph structure used for regularization.The framework therefore naturally starts with the more informative layer as G(1).
  • B. Jointly smooth spectrum computation: For more than two layers, the procedure starts with the most informative layer and selects the next layer by maximizing mutual information between layer-specific cluster-membership distributions.

C. Discussion

The paper motivates spectral regularization as a way to combine graph layers by propagating spectral information across their structures. SC-SR transforms eigenvectors from one layer using another layer's regularization before clustering the resulting embedding.

  • C. Discussion: Spectral regularization combines two graph layers by propagating eigenvector information through neighboring vertices.The method is interpreted through label propagation and disagreement minimization across graph structures.
  • C. Discussion: After regularization, SC-SR represents each vertex by a row of the new low-dimensional embedding and applies K-means to obtain cluster assignments.The algorithm outputs clusters formed from the regularized spectral embedding.
  • C. Discussion: SC-SR starts from the random-walk Laplacian eigenvectors of one graph layer and regularizes them using another layer.The algorithm computes the first k eigenvectors, solves the spectral regularization problem for each, and replaces them in the embedding.
  • C. Discussion: The regularization update balances each vertex's initial value against values propagated from neighboring vertices through parameter α.The initial values come from the first graph's relaxed graph-cut solution, while α controls the trade-off between fidelity and propagation.
  • C. Discussion: The disagreement interpretation penalizes differences from the initial solution and inconsistency with the second graph's edge structure.Large-weight edges favor similar normalized function values at their endpoints.

VI. SIMULATION RESULTS

The simulation section evaluates the proposed and comparison clustering algorithms on datasets using three clustering benchmarking metrics.

  • VI. SIMULATION RESULTS: The experiments describe the datasets and clustering algorithms before comparing their performance with three benchmarking metrics.The section introduces the simulation setup and evaluation procedure.

A. Datasets

The evaluation uses three real-world datasets with multi-layer graphs representing mobile-phone and bibliographic relationships. The datasets differ in difficulty and are paired with several comparison algorithms and implementation choices.

  • A. Datasets: The experiments use three real-world social-network datasets: two mobile-phone datasets and one bibliographic dataset.Each dataset is used to construct multiple graph layers for clustering evaluation.
  • A. Datasets: The MIT Reality Mining dataset contains 87 mobile users and three layers based on physical locations, Bluetooth scans, and phone calls.Users are clustered into 6 groups using self-reported affiliations as ground truth.
  • A. Datasets: The Nokia dataset contains around 200 users in Lausanne and uses physical distance, Bluetooth, and phone-call information to construct multiple layers.Its ground truth consists of 8 email-affiliation groups.
  • A. Datasets: The Cora dataset contains 292 research papers from Natural Language Processing, Data Mining, and Robotics communities.Its layers use title and abstract cosine similarities together with citation relationships.
  • A. Datasets: MIT and Nokia are harder to cluster than Cora because affiliations are not fully reflected in physical proximity or phone communication.The authors retain these imperfect ground-truth affiliations because they are the best available indicators for the mobile datasets.
  • A. Datasets: The comparison includes co-regularization, modularity maximization, spectral summation, kernel K-means, averaged-Laplacian spectral clustering, SC-GED, and SC-SR.SC-GED balances approximation error with stability, while SC-SR recursively combines layers using spectral regularization.

C. Evaluation criteria and Results

Clustering quality is evaluated with Purity, NMI, and RI across three datasets. Combining graph layers improves performance over independent layers, with SC-SR generally strongest or competitive and computationally cheaper than CoR.

  • C. Evaluation criteria and Results: Purity, Normalized Mutual Information, and Rand Index compare computed clusters with intended ground-truth classes.The criteria assess clustering performance from different angles.
  • C. Evaluation criteria and Results: Properly combining multiple graph layers improves clustering quality compared with using layers independently.The result is reported across the three datasets and benchmarking criteria.
  • C. Evaluation criteria and Results: SC-SR achieves superior or competitive performance across the evaluation criteria, while SC-GED provides weaker improvements over individual layers.Among competitors, CoR performs strongly, whereas CD and baseline combinations are generally intermediate.
  • C. Evaluation criteria and Results: SC-SR's regularized combination improves benchmark results as more layers are combined, particularly for NMI.The authors attribute this to maximizing mutual information between graph layers.
  • C. Evaluation criteria and Results: SC-SR computes the relevant eigenvector process once for the most informative layer, whereas CoR repeats it across original and modified Laplacians for n M(M−1)⁄2 times.The comparison identifies a substantial computational reduction for SC-SR.
  • C. Evaluation criteria and Results: The MIT confusion matrices show SC-SR best reveals the six intended classes, with diagonal entries representing correctly identified objects.Columns denote predicted clusters and rows denote intended classes.

VII. RELATED WORK

Related work spans graph-based learning, spectral clustering, and methods for combining multiple graph views. The paper distinguishes its spectral-domain combination of graph layers from prior averaging, convex-combination, and regularization approaches.

  • Foundations: Graph-based learning and spectral clustering provide the methodological foundations for analyzing pairwise relationships and graph spectra.The literature includes general graph data processing, spectral graph theory, and spectral clustering.
  • Multiple-graph methods: Multiple-graph research includes optimal combined kernels, mixed random walks, signal-domain regularization, and other graph-layer combination methods.Existing approaches commonly combine graph information through averaging, convex combinations, or regularization frameworks.
  • Positioning: The paper works in the graph spectral domain, where prior methods largely combine information in the signal domain or treat layers equally or through weighted sums.Its SC-SR method instead uses spectral regularization and assigns different roles to graph layers.
  • Positioning: The related literature motivates extending spectral techniques from single graphs to clustering with multiple graph layers.The paper frames this as a distinction from methods that apply spectral techniques to individual graphs while combining layers elsewhere.

VIII. CONCLUSION

The paper develops two methods for clustering multi-layer graphs by finding a joint spectrum shared across graph layers. It reports improved clustering benchmarks on three social-network datasets and identifies joint-spectrum analysis as a broader direction for graph processing.

  • Problem: The paper addresses clustering when data are represented by a multi-layer graph.The conclusion frames the task as extending single-graph spectral techniques to multi-layer data.
  • Methods: It proposes joint matrix factorization and graph-based spectral regularization to find a joint spectrum shared by all graph layers.The second approach weights layers according to respective importances measured from an information-theoretic perspective.
  • Results: The methods improve clustering benchmarks on three social-network datasets.The conclusion reports these improvements as an outcome of the proposed methodologies.
  • Implications: The joint-spectrum concept suggests a way to generalize classical spectral analysis to multi-dimensional graph-processing tasks.The paper identifies this broader graph-processing application as a focus for future work.
Loading 1106.2233v1…