Node Classification with Bounded Error Rates

Pivithuru Wijegunawardana, Ralucca Gera, Sucheta Soundarajan

Research output: Chapter in Book/Entry/PoemConference contribution


Node classification algorithms are widely used for the task of node label prediction in partially labeled graph data. In many problems, a user may wish to associate a confidence level with a prediction such that the error in the prediction is guaranteed. We propose adopting the Conformal Prediction framework [17] to obtain guaranteed error bounds in node classification problem. We show how this framework can be applied to (1) obtain predictions with guaranteed error bounds, and (2) improve the accuracy of the prediction algorithms. Our experimental results show that the Conformal Prediction framework can provide up to a 30% improvement in node classification algorithm accuracy while maintaining guaranteed error bounds on predictions.

Original languageEnglish (US)
Title of host publicationComplex Networks XI - Proceedings of the 11th Conference on Complex Networks, CompleNet 2020
EditorsHugo Barbosa, Ronaldo Menezes, Jesus Gomez-Gardenes, Bruno Gonçalves, Giuseppe Mangioni, Marcos Oliveira
Number of pages13
ISBN (Print)9783030409425
StatePublished - 2020
Event11th International Conference on Complex Networks, CompleNet 2020 - Exeter, United Kingdom
Duration: Mar 31 2020Apr 3 2020

Publication series

NameSpringer Proceedings in Complexity
ISSN (Print)2213-8684
ISSN (Electronic)2213-8692


Conference11th International Conference on Complex Networks, CompleNet 2020
Country/TerritoryUnited Kingdom


  • Bounded error rates
  • Conformal prediction
  • Node classification

ASJC Scopus subject areas

  • Applied Mathematics
  • Modeling and Simulation
  • Computer Science Applications


Dive into the research topics of 'Node Classification with Bounded Error Rates'. Together they form a unique fingerprint.

Cite this