Clustering with multi-layer graphs: a spectral perspective
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 (objects) with different edges (pairwise relationships). In this paper, we address the problem of combining different layers...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
IEEE
2012
|
| _version_ | 1797105831958806528 |
|---|---|
| author | Dong, X Frossard, P Vandergheynst, P Nefedov, N |
| author_facet | Dong, X Frossard, P Vandergheynst, P Nefedov, N |
| author_sort | Dong, X |
| collection | OXFORD |
| description | 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 (objects) with different edges (pairwise relationships). In this paper, we address the problem of combining different layers of the multi-layer graph for an improved clustering of the vertices compared to using layers independently. We propose two novel methods, which are based on a joint matrix factorization and a 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 layers, is used for clustering the vertices. We evaluate our approaches by experiments with several real world social network datasets. Results demonstrate the superior or competitive performance of the proposed methods compared to state-of-the-art techniques and common baseline methods, such as co-regularization and summation of information from individual graphs. |
| first_indexed | 2024-03-07T06:53:01Z |
| format | Journal article |
| id | oxford-uuid:fd2c0919-75ec-4132-ba9d-c2f4b1935e9a |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:53:01Z |
| publishDate | 2012 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:fd2c0919-75ec-4132-ba9d-c2f4b1935e9a2022-03-27T13:26:51ZClustering with multi-layer graphs: a spectral perspectiveJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:fd2c0919-75ec-4132-ba9d-c2f4b1935e9aSymplectic ElementsIEEE2012Dong, XFrossard, PVandergheynst, PNefedov, NObservational 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 (objects) with different edges (pairwise relationships). In this paper, we address the problem of combining different layers of the multi-layer graph for an improved clustering of the vertices compared to using layers independently. We propose two novel methods, which are based on a joint matrix factorization and a 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 layers, is used for clustering the vertices. We evaluate our approaches by experiments with several real world social network datasets. Results demonstrate the superior or competitive performance of the proposed methods compared to state-of-the-art techniques and common baseline methods, such as co-regularization and summation of information from individual graphs. |
| spellingShingle | Dong, X Frossard, P Vandergheynst, P Nefedov, N Clustering with multi-layer graphs: a spectral perspective |
| title | Clustering with multi-layer graphs: a spectral perspective |
| title_full | Clustering with multi-layer graphs: a spectral perspective |
| title_fullStr | Clustering with multi-layer graphs: a spectral perspective |
| title_full_unstemmed | Clustering with multi-layer graphs: a spectral perspective |
| title_short | Clustering with multi-layer graphs: a spectral perspective |
| title_sort | clustering with multi layer graphs a spectral perspective |
| work_keys_str_mv | AT dongx clusteringwithmultilayergraphsaspectralperspective AT frossardp clusteringwithmultilayergraphsaspectralperspective AT vandergheynstp clusteringwithmultilayergraphsaspectralperspective AT nefedovn clusteringwithmultilayergraphsaspectralperspective |