Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective

• URL: http://arxiv.org/abs/2508.20231v1
• Date: Wed, 27 Aug 2025 19:22:35 GMT
• Title: Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective
• Authors: Firooz Shahriari-Mehr, Javad Aliakbari, Alexandre Graell i Amat, Ashkan Panahi,
• Abstract summary: 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.<n>For node classification, we propose a novel optimization problem that incorporates the node-specific information in a spectral graph clustering framework.
• Score: 50.3088702686312
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• DREAM: Dual-Standard Semantic Homogeneity with Dynamic Optimization for Graph Learning with Label Noise [53.55187452152358]
  This paper proposes a novel method, Dual-Standard Semantic Homogeneity with Dynamic Optimization (DREAM) for reliable, relation-informed optimization on graphs with label noise.<n>Specifically, we design a relation-informed dynamic optimization framework that iteratively reevaluates the reliability of each labeled node in the graph.
  arXiv  Detail & Related papers  (2026-01-24T12:54:18Z)
• Cluster-based Graph Collaborative Filtering [55.929052969825825]
  Graph Convolution Networks (GCNs) have succeeded in learning user and item representations for recommendation systems. Most existing GCN-based methods overlook the multiple interests of users while performing high-order graph convolution. We propose a novel GCN-based recommendation model, termed Cluster-based Graph Collaborative Filtering (ClusterGCF)
  arXiv  Detail & Related papers  (2024-04-16T07:05:16Z)
• GraphRARE: Reinforcement Learning Enhanced Graph Neural Network with Relative Entropy [21.553180564868306]
  GraphRARE is a framework built upon node relative entropy and deep reinforcement learning. An innovative node relative entropy is used to measure mutual information between node pairs. A deep reinforcement learning-based algorithm is developed to optimize the graph topology.
  arXiv  Detail & Related papers  (2023-12-15T11:30:18Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Reasoning Graph Networks for Kinship Verification: from Star-shaped to Hierarchical [85.0376670244522]
  We investigate the problem of facial kinship verification by learning hierarchical reasoning graph networks. We develop a Star-shaped Reasoning Graph Network (S-RGN) to exploit more powerful and flexible capacity. We also develop a Hierarchical Reasoning Graph Network (H-RGN) to exploit more powerful and flexible capacity.
  arXiv  Detail & Related papers  (2021-09-06T03:16:56Z)
• Seeing All From a Few: Nodes Selection Using Graph Pooling for Graph Clustering [37.68977275752782]
  noisy edges and nodes in the graph may make the clustering results worse. We propose a novel dual graph embedding network(DGEN) to improve the robustness of the graph clustering to the noisy nodes and edges. Experiments on three benchmark graph datasets demonstrate the superiority compared with several state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2021-04-30T06:51:51Z)
• Graph InfoClust: Leveraging cluster-level node information for unsupervised graph representation learning [12.592903558338444]
  We propose a graph representation learning method called Graph InfoClust. It seeks to additionally capture cluster-level information content. This optimization leads the node representations to capture richer information and nodal interactions, which improves their quality.
  arXiv  Detail & Related papers  (2020-09-15T09:33:20Z)
• Smoothness Sensor: Adaptive Smoothness-Transition Graph Convolutions for Attributed Graph Clustering [10.905770964670191]
  We propose a smoothness sensor for attributed graph clustering based on adaptive smoothness-transition graph convolutions. As an alternative to graph-level smoothness, a novel fine-gained node-wise level assessment of smoothness is proposed. Experiments show that the proposed methods significantly outperform 12 other state-of-the-art baselines in terms of three different metrics.
  arXiv  Detail & Related papers  (2020-09-12T08:12:27Z)
• Structure-Feature based Graph Self-adaptive Pooling [65.4188800835203]
  We propose a novel graph self-adaptive pooling method to deal with graph data. Our method is effective in graph classification and outperforms state-of-the-art graph pooling methods.
  arXiv  Detail & Related papers  (2020-01-30T13:58:49Z)
• Graph Inference Learning for Semi-supervised Classification [50.55765399527556]
  We propose a Graph Inference Learning framework to boost the performance of semi-supervised node classification. For learning the inference process, we introduce meta-optimization on structure relations from training nodes to validation nodes. Comprehensive evaluations on four benchmark datasets demonstrate the superiority of our proposed GIL when compared against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-01-17T02:52:30Z)

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.