Optimization Framework for Semi-supervised Attributed Graph Coarsening

Manoj Kumar, Subhanu Halder, Archit Kane, Ruchir Gupta, Sandeep Kumar
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:2064-2075, 2024.

Abstract

In data-intensive applications, graphs serve as foundational structures across various domains. However, the increasing size of datasets poses significant challenges to performing downstream tasks. To address this problem, techniques such as graph coarsening, condensation, and summarization have been developed to create a coarsened graph while preserving important properties of the original graph by considering both the graph matrix and the feature or attribute matrix of the original graph as inputs. However, existing graph coarsening techniques often neglect the label information during the coarsening process, which can result in a lower-quality coarsened graph and limit its suitability for downstream tasks. To overcome this limitation, we introduce the Label-Aware Graph Coarsening (LAGC) algorithm, a semi-supervised approach that incorporates the graph matrix, feature matrix, and some of the node label information to learn a coarsened graph. Our proposed formulation is a non-convex optimization problem that is efficiently solved using block successive upper bound minimization(BSUM) technique, and it is provably convergent. Our extensive results demonstrate that the LAGC algorithm outperforms the existing state-of-the-art method by a significant margin.

Cite this Paper

BibTeX
@InProceedings{pmlr-v244-kumar24a, title = {Optimization Framework for Semi-supervised Attributed Graph Coarsening}, author = {Kumar, Manoj and Halder, Subhanu and Kane, Archit and Gupta, Ruchir and Kumar, Sandeep}, booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence}, pages = {2064--2075}, year = {2024}, editor = {Kiyavash, Negar and Mooij, Joris M.}, volume = {244}, series = {Proceedings of Machine Learning Research}, month = {15--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/kumar24a/kumar24a.pdf}, url = {https://proceedings.mlr.press/v244/kumar24a.html}, abstract = {In data-intensive applications, graphs serve as foundational structures across various domains. However, the increasing size of datasets poses significant challenges to performing downstream tasks. To address this problem, techniques such as graph coarsening, condensation, and summarization have been developed to create a coarsened graph while preserving important properties of the original graph by considering both the graph matrix and the feature or attribute matrix of the original graph as inputs. However, existing graph coarsening techniques often neglect the label information during the coarsening process, which can result in a lower-quality coarsened graph and limit its suitability for downstream tasks. To overcome this limitation, we introduce the Label-Aware Graph Coarsening (LAGC) algorithm, a semi-supervised approach that incorporates the graph matrix, feature matrix, and some of the node label information to learn a coarsened graph. Our proposed formulation is a non-convex optimization problem that is efficiently solved using block successive upper bound minimization(BSUM) technique, and it is provably convergent. Our extensive results demonstrate that the LAGC algorithm outperforms the existing state-of-the-art method by a significant margin.} }
Endnote
%0 Conference Paper %T Optimization Framework for Semi-supervised Attributed Graph Coarsening %A Manoj Kumar %A Subhanu Halder %A Archit Kane %A Ruchir Gupta %A Sandeep Kumar %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-kumar24a %I PMLR %P 2064--2075 %U https://proceedings.mlr.press/v244/kumar24a.html %V 244 %X In data-intensive applications, graphs serve as foundational structures across various domains. However, the increasing size of datasets poses significant challenges to performing downstream tasks. To address this problem, techniques such as graph coarsening, condensation, and summarization have been developed to create a coarsened graph while preserving important properties of the original graph by considering both the graph matrix and the feature or attribute matrix of the original graph as inputs. However, existing graph coarsening techniques often neglect the label information during the coarsening process, which can result in a lower-quality coarsened graph and limit its suitability for downstream tasks. To overcome this limitation, we introduce the Label-Aware Graph Coarsening (LAGC) algorithm, a semi-supervised approach that incorporates the graph matrix, feature matrix, and some of the node label information to learn a coarsened graph. Our proposed formulation is a non-convex optimization problem that is efficiently solved using block successive upper bound minimization(BSUM) technique, and it is provably convergent. Our extensive results demonstrate that the LAGC algorithm outperforms the existing state-of-the-art method by a significant margin.
APA
Kumar, M., Halder, S., Kane, A., Gupta, R. & Kumar, S.. (2024). Optimization Framework for Semi-supervised Attributed Graph Coarsening. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:2064-2075 Available from https://proceedings.mlr.press/v244/kumar24a.html.

Related Material