PaperlayerView exact revision on arXiv

Source-linked AI summary

Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds

Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, Nikolai Nefedov

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

TL;DR

The paper asks how to analyze and cluster entities when relationships are represented by multiple graph layers. It converts each layer into a subspace and merges them on a Grassmann manifold, yielding a representative low-dimensional representation. Experiments show competitive or superior clustering performance relative to baseline and state-of-the-art methods, while the framework is intended to extend to other multi-layer learning tasks.

  • Problem

    The paper addresses how to combine diverse relationship information across multiple graph layers for analyzing and clustering their shared vertices.

  • Method

    The method represents individual graph layers as subspaces and merges them on a Grassmann manifold into a representative subspace used for clustering.

  • Results

    The proposed clustering methods generally outperform baseline approaches and achieve significant improvements over clustering individual graph layers, with performance competitive to state-of-the-art techniques.

  • Takeaways & Limitations

    The framework provides a low-dimensional summarization of multi-layer graph information that can support clustering and other learning tasks involving multiple subspaces.

Abstract

from arXiv · show

Relationships between entities in datasets are often of multiple nature, like geographical distance, social relationships, or common interests among people in a social network, for example. This information can naturally be modeled by a set of weighted and undirected graphs that form a global multilayer graph, where the common vertex set represents the entities and the edges on different layers capture the similarities of the entities in term of the different modalities. In this paper, we address the problem of analyzing multi-layer graphs and propose methods for clustering the vertices by efficiently merging the information provided by the multiple modalities. To this end, we propose to combine the characteristics of individual graph layers using tools from subspace analysis on a Grassmann manifold. The resulting combination can then be viewed as a low dimensional representation of the original data which preserves the most important information from diverse relationships between entities. We use this information in new clustering methods and test our algorithm on several synthetic and real world datasets where we demonstrate superior or competitive performances compared to baseline and state-of-the-art techniques. Our generic framework further extends to numerous analysis and learning problems that involve different types of information on graphs.

I. INTRODUCTION

The paper addresses clustering in multi-layer graphs by combining diverse graph relationships through subspace representations on a Grassmann manifold. It links this framework to prior graph, subspace, and multi-view learning approaches while reporting a simple, competitive layer-merging solution.

  • Motivation: Multi-layer graphs represent different relationship types with shared vertices and layer-specific edges, motivating methods that combine complementary information.The paper frames this combination as a way to improve understanding of data structure and inter-entity relationships.
  • Approach: The proposed framework models each graph layer as a subspace on a Grassmann manifold and merges these subspaces into one representative subspace.The representative subspace summarizes information from the individual layers.
  • Approach: Spectral clustering is applied to the representative subspace to obtain a unified clustering of vertices across graph layers.The objective is to improve on clustering performed independently on individual layers.
  • Related work and novelty: The work explicitly connects Grassmann-manifold subspace analysis with graph-based learning and relates projection distance to HSIC and K-L divergence.This provides a unified view of these distance-related concepts.
  • Contributions: The layer-merging framework provides a simple yet competitive solution for clustering multi-layer graphs and may extend to other multi-layer or multi-view learning tasks.The paper also discusses relationships between layers as relevant to efficient and adaptive learning algorithms.

III. SUBSPACE REPRESENTATION FOR GRAPHS

The paper represents graph connectivity through a low-dimensional spectral subspace derived from the normalized graph Laplacian. Clustering then uses the embedded vertex coordinates, with multiple graph layers later treated as multiple such subspaces.

  • Graph construction: The normalized graph Laplacian is used because its eigenvalues lie between 0 and 2, facilitating comparisons across graph layers.The graph is weighted and undirected, with adjacency and degree matrices defining the Laplacian.
  • Spectral clustering: Spectral clustering partitions vertices into k subsets by minimizing a trace objective involving the graph Laplacian.The solution matrix contains the k eigenvectors associated with the smallest eigenvalues.
  • Spectral clustering: Applying k-means to normalized rows of the eigenvector matrix produces the final vertex clustering.The rows serve as embedded coordinates for the vertices.
  • Spectral subspace representation: A graph’s k-dimensional spectral embedding uses the first k eigenvectors of its graph Laplacian, with each row representing one vertex’s coordinates.This low-dimensional representation captures vertex connectivity and can support clustering or other graph analyses.
  • Extension to multi-layer graphs: Representing each graph layer as a subspace transforms multi-layer graph analysis into the problem of combining multiple subspaces.This representation preserves information about connectivity in the original graph.

IV. MERGING SUBSPACES VIA ANALYSIS ON THE GRASSMANN MANIFOLD

The paper represents graph-layer subspaces as points on a Grassmann manifold and uses principal-angle geometry, especially projection distance, to compare them.

  • Grassmann manifold representation: A Grassmann manifold G(k, n) contains the k-dimensional linear subspaces of R^n, each represented by an orthonormal matrix whose columns span it.The paper maps each graph-layer subspace to a manifold point.
  • Subspace distances: Principal angles quantify the geometric closeness between two subspaces and support distances including the Riemannian and projection distances.The paper selects projection distance for subsequent multi-subspace analysis.
  • Projection distance: The projection distance uses all principal angles, avoiding assumptions about the data distribution while treating each angle as informative.This motivates its use as an unbiased distance measure.
  • Projection distance: The subspace-to-projection mapping span(Y) → YY′ preserves distinctness, allowing projection distance to quantify differences between subspaces.The squared distance can also be related to the Frobenius norm between the corresponding projection matrices.
  • Projection distance: Identical subspaces have projection distance 0.

B. Generic merging framework

The generic framework builds spectral subspaces for each graph layer and merges them into a representative subspace that balances cross-layer proximity with graph connectivity preservation.

  • Layer representations: Each graph layer is represented by the first k eigenvectors of its graph Laplacian, producing a k-dimensional spectral subspace.Here n is the number of vertices and k is the target number of clusters.
  • Generic merging framework: The representative subspace is required to remain close to all individual layer subspaces while preserving vertex connectivity across graph layers.
  • Generic merging framework: The optimization combines summed projection distances to layer subspaces with Laplacian quadratic forms over the graphs.The regularization parameter α controls the trade-off between these terms.
  • Optimization solution: The merged problem becomes a trace minimization with a modified Laplacian, whose first k eigenvectors provide the solution by the Rayleigh-Ritz theorem.The modified Laplacian can be computed using efficient eigenvalue algorithms.
  • Generic merging framework: Minimizing only the Laplacian term averages layer information, whereas minimizing only projection distance does not guarantee a meaningful merged subspace.

C. Discussion of the distance function

The paper gives information-theoretic and statistical-learning interpretations of projection distance, supporting the representative subspace as a summary of multilayer graph information.

  • Information-theoretic interpretation: Under certain conditions, squared projection distance has the same form as symmetrized K-L divergence between distributions associated with subspaces.
  • Statistical-learning interpretation: Using spectral embeddings, rows of layer subspaces are treated as samples governed by vertex-connectivity information in the corresponding graphs.
  • Statistical-learning interpretation: Projection distance can be interpreted as negative statistical dependence between the random variables associated with two graph layers.
  • Interpretation: A smaller projection distance therefore corresponds to greater similarity between the information represented by two graph-layer subspaces.
  • Implication: The representative subspace summarizes individual graph layers, captures intrinsic vertex relationships, and provides a low-dimensional representation for multilayer graph analysis.The framework can also incorporate relative importance among graph layers.

V. CLUSTERING ON MULTI-LAYER GRAPHS

The paper applies its multilayer subspace-merging framework to clustering vertices, using the representative subspace as a low-dimensional form for graph analysis.

  • Multilayer graph clustering: The representative subspace from the preceding framework is used in the paper’s application to clustering vertices in a multilayer graph.

A. Clustering algorithm

SC-ML merges subspace representations from multiple graph layers into a representative subspace, then applies spectral clustering to obtain unified vertex clusters.

  • A. Clustering algorithm: SC-ML computes a representative subspace containing information from multiple graph layers before final clustering.The framework summarizes layer information prior to the k-means step.
  • A. Clustering algorithm: The algorithm computes normalized Laplacians and subspace representations for each input graph layer.
  • A. Clustering algorithm: SC-ML derives the first k eigenvectors of a modified Laplacian, row-normalizes them, and clusters the resulting vectors with k-means.
  • A. Clustering algorithm: Algorithm 2 directly generalizes single-graph spectral clustering to multi-layer graphs.

B. Analysis of the proposed algorithm

The analysis links clustering quality to relationships among layer subspaces on the Grassmann manifold. SC-ML can be weakened when less informative layers are close together and dominate the representative subspace.

  • Subspace relationships: Minimizing projection distance is interpreted as maximizing dependence between representative and individual subspace variables related to cluster assignments.
  • Subspace relationships: The objective’s distance term pulls the representative subspace toward individual subspaces that are close on the Grassmann manifold.
  • Toy examples: Toy examples use three-layer graphs with unit edge weights and colored vertices indicating three groundtruth clusters.
  • Limitations: When two lower-quality layers are close while the most informative layer is distant, ignoring layer quality can produce unsatisfactory clustering.
  • Assumptions: SC-ML assumes most individual subspaces are informative and reasonably close, providing complementary rather than contradictory information.

VI. EXPERIMENTAL RESULTS

The experimental section evaluates SC-ML on synthetic and real-world multi-layer graphs using clustering criteria and comparisons with other methods.

  • VI. EXPERIMENTAL RESULTS: The evaluation covers several synthetic and real-world datasets, comparative algorithms, and three clustering evaluation criteria.
  • VI. EXPERIMENTAL RESULTS: The experimental section describes datasets, comparison algorithms, implementation choices, and resulting performance discussions.
  • VI. EXPERIMENTAL RESULTS: The regularization parameter is selected for the best possible clustering performance through empirical trials.

A. Datasets

The evaluation uses synthetic, mobile-phone, and bibliographic multi-layer graphs, and compares SC-ML with single-layer, summed-layer, spectral-kernel, and co-regularization methods.

  • Datasets: The synthetic dataset contains three R2 point clouds forming “N”, “R”, and “C”, with five Gaussian-mixture classes of 500 points each.Each point cloud yields a 5-nearest-neighbor graph weighted by reciprocal Euclidean distance.
  • Datasets: The NRC dataset represents 136 users with graphs based on GPS proximity, Bluetooth scanning, and phone communication.
  • Datasets: The Cora subset contains 292 papers from three fields, using title, abstract, and citation relationships as graph layers.The clustering goal is to recover the three field-based clusters.
  • Datasets: Spy plots visualize nonzero adjacency-matrix entries for the synthetic, NRC, and Cora datasets using groundtruth-consistent vertex orderings.
  • Clustering algorithms: Comparisons include SC-Single, SC-Sum, SC-KSum, SC-CoR, and SC-ML.SC-Single uses the best-performing individual layer, while SC-Sum aggregates normalized adjacency matrices.
  • Clustering algorithms: SC-ML uses α=0.64 for the synthetic dataset and α=0.44 for both real-world datasets.

C. Results and discussions

SC-ML and SC-CoR generally outperform baseline clustering methods, while SC-ML offers a one-step representative-subspace solution with stable parameter behavior. Compared with SC-CoR, SC-ML avoids modifying individual subspaces and requires only one eigenvalue problem.

  • Clustering performance: SC-ML and SC-CoR generally outperform baseline approaches across the synthetic, NRC, and Cora datasets.Performance is evaluated using Purity, NMI, and RI; the NRC dataset is more challenging because its ground truth is approximate.
  • Clustering performance: SC-Sum and SC-KSum provide limited improvement because summation can smooth out layer-specific information and penalize clustering performance.Their behavior is similar to building a simple average graph across layers.
  • Merging mechanisms: SC-CoR requires sensible initialization and an alternating optimization process, whereas SC-ML finds the representative subspace in one step.SC-CoR optimizes one subspace representation at each step and does not guarantee convergence of all representations to one Grassmann-manifold point.
  • Merging mechanisms: SC-ML combines multilayer information by finding a globally representative subspace without modifying the individual subspaces.This contrasts with SC-CoR, which iteratively updates individual subspace representations.
  • Computational comparison: SC-ML solves an eigenvalue problem only once, unlike SC-CoR, which requires eigenvalue problems MN times.Here, M is the number of graph layers and N is the number of iterations needed for SC-CoR to converge.
  • Parameter sensitivity: SC-ML performs best when α is between 0.4 and 0.6 and remains reasonably stable across parameter choices.It outperforms SC-CoR across a large α range on the synthetic and NRC datasets, while offering a larger effective range on Cora.

VII. CONCLUSIONS

The paper presents a Grassmann-manifold framework for summarizing multilayer graph information through representative subspaces and applies it to clustering. The authors conclude that the approach is efficient and competitive, while identifying alternative subspace representations and prior information as open directions.

  • Conclusions: The framework transforms information from individual graph layers into subspaces on a Grassmann manifold.A representative subspace summarizes the multiple subspaces through Grassmann-manifold distance analysis.
  • Conclusions: Under appropriate and realistic assumptions, the framework provides an efficient multilayer-graph clustering solution competitive with state-of-the-art techniques.The framework is also described as applicable to various learning tasks involving multiple subspace representations.
  • Open problems: The spectral-clustering-inspired subspace representation is not the only possible representation of graph information.The conclusion identifies eigenvectors of a graph’s modularity matrix as an alternative and leaves the most appropriate representation as an open problem.
  • Open problems: Prior information about the consistency of multilayer data is identified as a possible route to better clustering performance.The conclusion presents this as an open research direction rather than an established result.
Loading 1303.2221v1…