Multilayer Graph Signal Clustering

Mireille El Gheche, Pascal Frossard

Abstract

OrthoNet is a novel framework for clustering nodes in multilayer networks by fusing multiple connectivity views with high-dimensional node features. It leverages Riemannian geometry for robust graph aggregation and a deep learning approach that enforces spectral clustering constraints implicitly via a Cholesky decomposition trick. This allows for efficient, end-to-end unsupervised training and generalization to unseen nodes, outperforming traditional methods on complex real-world datasets.

Introduction

In real-world scenarios, data is rarely isolated. For instance, in a social network, users are linked through various interaction types (friendships, professional ties, shared interests) and possess rich attributes like textual profiles or images. Traditional clustering methods often fail to integrate these disparate data types effectively, either ignoring node features or failing to account for the multilayer nature of the graph.

Graph partitioning involves grouping nodes based on connectivity patterns across one or more layers.

Fusing these sources is mathematically challenging because graph structures and node features exist in different spaces. Spectral clustering, the gold standard for graph grouping, requires an orthogonality constraint to prevent cluster representations from collapsing. However, this constraint is typically computationally expensive to enforce in deep learning pipelines. OrthoNet addresses these challenges by combining geometric graph aggregation with a constrained deep embedding approach.

Methodology

The OrthoNet pipeline consists of two primary stages:

1. Layer Aggregation via the SPD Manifold

Rather than using a simple arithmetic average of Laplacian matrices—which can be sensitive to noise—OrthoNet computes the geometric mean of the matrices. By treating these matrices as points on a Symmetric Positive Definite (SPD) manifold, the shared topology across layers is better preserved, resulting in a more robust representative graph.

2. Deep Spectral Embedding with Implicit Constraints

The core of OrthoNet is a neural network trained to learn node embeddings by reformulating the spectral clustering objective into a differentiable cost function. To satisfy the orthogonality constraint without costly projection steps, the authors employ a Cholesky decomposition trick. By normalizing the network's output by its own Cholesky factor, the constraint is satisfied implicitly, enabling standard gradient descent optimization while ensuring the learned features are perfectly suited for K-means clustering.

Experimental Results

OrthoNet was evaluated against state-of-the-art methods (e.g., SC-ML, GMC, SpectralNet) on synthetic and real-world datasets including IMDB, Yelp, and 100 Leaves.

Spectral-based methods like OrthoNet can identify complex, non-linearly separable clusters that traditional methods miss.

Key performance highlights include:

  • Yelp Dataset: OrthoNet achieved a Normalized Mutual Information (NMI) of 0.7910, significantly outperforming SpectralNet (0.6810).
  • 100 Leaves Dataset: The model reached a Purity of 0.9712, compared to 0.6987 for K-means.
  • Generalization: Training on 70% of nodes and testing on the remaining 30% showed minimal performance degradation, indicating that the model learns a functional mapping rather than a simple lookup table.

Discussion and Key Insights

  • Geometric Robustness: The Riemannian geometric mean prevents noisy layers from dominating the fused graph representation, ensuring a more accurate global view of node relationships.
  • Functional Mapping: By using a neural network, OrthoNet bypasses the traditional "batch" requirement of spectral clustering, allowing it to embed new nodes post-training.
  • Feature-Structure Synergy: The graph structure acts as a form of supervision for feature learning, mapping nodes with similar connectivity to nearby points in the latent space.

Conclusion and Future Work

OrthoNet demonstrates the power of fusing multilayer graph structures with node features for superior clustering. While the $O(N^3)$ complexity of the SPD mean calculation is a current limitation for very large graphs, future work will explore faster approximations and the integration of Graph Convolutional Networks (GCNs) to further enhance local neighborhood exploitation.

Summary updated

BibTeX
@article{gheche2020multilayer,
  author = {Mireille El Gheche and Pascal Frossard},
  title = {{Multilayer Graph Signal Clustering}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2020},
  url = {https://openreview.net/forum?id=04pWWEarDni},
}
Figure