Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914010621804544 |
|---|---|
| author | Shahriari-Mehr, Firooz Aliakbari, Javad Amat, Alexandre Graell i Panahi, Ashkan |
| author_facet | Shahriari-Mehr, Firooz Aliakbari, Javad Amat, Alexandre Graell i Panahi, Ashkan |
| contents | We present an analysis of the transductive node classification problem, where the underlying graph consists of communities that agree with the node labels and node features. For node classification, we propose a novel optimization problem that incorporates the node-specific information (labels and features) in a spectral graph clustering framework. Studying this problem, we demonstrate a synergy between the graph structure and node-specific information. In particular, we show that suitable node-specific information guarantees the solution of our optimization problem perfectly recovering the communities, under milder conditions than the bounds on graph clustering alone. We present algorithmic solutions to our optimization problem and numerical experiments that confirm such a synergy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20231 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective Shahriari-Mehr, Firooz Aliakbari, Javad Amat, Alexandre Graell i Panahi, Ashkan Machine Learning Optimization and Control We present an analysis of the transductive node classification problem, where the underlying graph consists of communities that agree with the node labels and node features. For node classification, we propose a novel optimization problem that incorporates the node-specific information (labels and features) in a spectral graph clustering framework. Studying this problem, we demonstrate a synergy between the graph structure and node-specific information. In particular, we show that suitable node-specific information guarantees the solution of our optimization problem perfectly recovering the communities, under milder conditions than the bounds on graph clustering alone. We present algorithmic solutions to our optimization problem and numerical experiments that confirm such a synergy. |
| title | Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2508.20231 |