Efficient Constrained Graph Search for Post-hoc Error Correction in Binary Classifiers

Qinwu Xu

cs.LGJan 8, 2024

Efficient Constrained Graph Search for Post-hoc Error Correction in Binary Classifiers

Authors: Qinwu Xu

Organizations: Leidos Holdings Inc.; The University of Texas at Austin

Abstract

This study develops a graph search algorithm to find the optimal discrimination path for the binary classification problem. The objective function is defined as the difference of variations between the true positive (TP) and false positive (FP). It uses the depth first search (DFS) algorithm to find the top-down paths for discrimination. It proposes a dynamic optimization procedure to optimize TP at the upper levels and then reduce FP at the lower levels. To accelerate computing speed while improving accuracy, it proposes a reduced histogram algorithm with variable bin size instead of looping over all data points to find the feature threshold of discrimination. The algorithm is applied on top of a Support Vector Machine (SVM) model for a binary classification problem on whether a person is fit or unfit. It significantly improves TP and reduces FP of the SVM results (e.g., reduced FP by 90% with a loss of only 5% TP). The graph search auto-generates 39 ranked discrimination paths within 9 seconds on an input of 328,464 objects, using a dual-core laptop computer with a processor of 2.59 GHz.

Figures & tables

Panel of Figure 1 — Figure 1: Overview of the graph-search algorithm with dynamic optimization and reduced-histogram threshold search. Left: Pseudocode of the complete graph-search procedure. Upper middle: Flow chart of the search procedure. Upper right: Dynamic optimization during graph search. Lower right: Reduced-histogram representation for efficient feature-threshold search.

Panel of Figure 2 — Figure 2: FP reduction example. Left: base SVM alarms 11 FP and 20 TP objects. Right: the correction rule removes 10 FP while losing one TP.

Panel of Figure 3 — Figure 3: TP improvement example. Left: base SVM negative predictions. Right: graph-search correction rescues 27 false negatives with three additional false positives.

Node	Depth	$\Delta$ FP	FP reduction	$\Delta$ TP	TP loss
2	1	820	43.52%	259	14.20%
7	2	607	32.22%	178	9.76%
28	3	330	17.52%	51	2.80%

Table 1: FP reduction and TP loss at three graph-search levels.

Binary Classification

Binary classification assigns examples to one of two classes while balancing accuracy, calibration, class imbalance, and the costs of different errors.

See all 66 papers

Extremely Fast and Compact Binary Graph Representations via Randomized Operator Sketching
Sep 26, 2026Srajan Agarwal, Megha P, Bikas C Das +2Graph Representation Learning Randomized Sketching
School of Data Science, IISER Thiruvananthapuram, India · Department of Physical Sciences, IISER Berhampur, India
Extreme Binary Classification: Extreme Value Theory for Extreme Constraint on False Negative
Oct 7, 2026Samuel Gruffaz, Muhammad Fawad, Jaakko NevalainenBinary Classification
Tampere university, Finland
Fast, Parallel, Query-Efficient Binary Classification
Jul 5, 2026Ishani Karmarkar, Liam O'Carroll, Aaron SidfordBinary Classification Classification
Stanford University

Sep 26, 2026J/K move · Enter open · S save

Extremely Fast and Compact Binary Graph Representations via Randomized Operator Sketching

Srajan Agarwal, Megha P, Bikas C Das, Zakaria Laskar+1

School of Data Science, IISER Thiruvananthapuram, India · Department of Physical Sciences, IISER Berhampur, India

Graph Representation Learning Randomized Sketching Node Classification

Open paper AskPDF arXiv

Graph neural networks typically rely on dense, floating-point node representations, which can impose substantial memory and computational costs. Binary graph hashing offers an alternative by encoding node information as compact bit strings. However, existing approaches either sacrifice global topological information for computational efficiency or incur substantial generation costs. We introduce an ultra-fast, entirely algebraic hashing method that constructs binary node representations directly from graph structure, without requiring node features or gradient-based training. Our method approximates a high-order structural transition matrix using randomized column sampling inspired by the Nyström method and combines it with an efficient label-safe semantic propagation mechanism. The resulting continuous representations are discretized through column-wise thresholding to obtain compact binary codes. Experiments on ten node classification datasets show that the proposed method consistently improves classification accuracy over existing feature-free binary baselines while requiring sub-second code generation on many datasets. The resulting binary representations are also naturally suited to event-driven computation, making them compatible with neuromorphic spiking neural networks and gradient-free learning rules. These results demonstrate that simple algebraic approximations can provide an efficient alternative to learned pipelines for discrete graph representation learning.

Abstract

Binary Classification

Explore similar work

Extremely Fast and Compact Binary Graph Representations via Randomized Operator Sketching

Extreme Binary Classification: Extreme Value Theory for Extreme Constraint on False Negative

Fast, Parallel, Query-Efficient Binary Classification