Multilayer Graph Clustering with Optimized Node Embedding
- URL: http://arxiv.org/abs/2103.16534v1
- Date: Tue, 30 Mar 2021 17:36:40 GMT
- Title: Multilayer Graph Clustering with Optimized Node Embedding
- Authors: Mireille El Gheche, Pascal Frossard
- Abstract summary: multilayer graph clustering aims at dividing the graph nodes into categories or communities.
We propose a clustering-friendly embedding of the layers of a given multilayer graph.
Experiments show that our method leads to a significant improvement.
- Score: 70.1053472751897
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We are interested in multilayer graph clustering, which aims at dividing the
graph nodes into categories or communities. To do so, we propose to learn a
clustering-friendly embedding of the graph nodes by solving an optimization
problem that involves a fidelity term to the layers of a given multilayer
graph, and a regularization on the (single-layer) graph induced by the
embedding. The fidelity term uses the contrastive loss to properly aggregate
the observed layers into a representative embedding. The regularization pushes
for a sparse and community-aware graph, and it is based on a measure of graph
sparsification called "effective resistance", coupled with a penalization of
the first few eigenvalues of the representative graph Laplacian matrix to favor
the formation of communities. The proposed optimization problem is nonconvex
but fully differentiable, and thus can be solved via the descent gradient
method. Experiments show that our method leads to a significant improvement
w.r.t. state-of-the-art multilayer graph clustering algorithms.
Related papers
- Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data.
The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
arXiv Detail & Related papers (2024-01-12T17:57:07Z) - Homophily-Related: Adaptive Hybrid Graph Filter for Multi-View Graph
Clustering [29.17784041837907]
We propose Adaptive Hybrid Graph Filter for Multi-View Graph Clustering (AHGFC)
AHGFC learns the node embedding based on the graph joint aggregation matrix.
Experimental results show that our proposed model performs well on six datasets containing homophilous and heterophilous graphs.
arXiv Detail & Related papers (2024-01-05T07:27:29Z) - Addressing Heterophily in Node Classification with Graph Echo State
Networks [11.52174067809364]
We address the challenges of heterophilic graphs with Graph Echo State Network (GESN) for node classification.
GESN is a reservoir computing model for graphs, where node embeddings are computed by an untrained message-passing function.
Our experiments show that reservoir models are able to achieve better or comparable accuracy with respect to most fully trained deep models.
arXiv Detail & Related papers (2023-05-14T19:42:31Z) - Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
gradient scarcity occurs when learning graphs by minimizing a loss on a subset of nodes causes edges between unlabelled nodes that are far from labelled ones to receive zero gradients.
We give a precise mathematical characterization of this phenomenon, and prove it also emerges in bilevel optimization.
To alleviate this issue, we study several solutions: we propose to resort to latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, or optimizing on a larger graph than the original one with a reduced diameter.
arXiv Detail & Related papers (2023-03-24T12:37:43Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
We propose a bi-level optimization approach for learning the optimal graph structure.
We also explore a low-rank approximation model for further reducing the time complexity.
arXiv Detail & Related papers (2022-05-06T03:37:00Z) - Scaling Up Graph Neural Networks Via Graph Coarsening [18.176326897605225]
Scalability of graph neural networks (GNNs) is one of the major challenges in machine learning.
In this paper, we propose to use graph coarsening for scalable training of GNNs.
We show that, simply applying off-the-shelf coarsening methods, we can reduce the number of nodes by up to a factor of ten without causing a noticeable downgrade in classification accuracy.
arXiv Detail & Related papers (2021-06-09T15:46:17Z) - A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
We propose a robust framework for adversarial graph embedding, named AGE.
AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution.
Based on this framework, we propose three models to handle three types of graph data.
arXiv Detail & Related papers (2021-05-22T07:05:48Z) - Multilayer Clustered Graph Learning [66.94201299553336]
We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph.
Experiments show that our method leads to a clustered clusters w.r.t.
We learn a clustering algorithm for solving clustering problems.
arXiv Detail & Related papers (2020-10-29T09:58:02Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications.
In this formalism, a link prediction problem is converted to a graph classification task.
We propose to seek a radically different and novel path by making use of the line graphs in graph theory.
In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
arXiv Detail & Related papers (2020-10-20T05:54:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.