Support Vector Machines for Indefinite Similarity Measures

This direction is merged into another direction: positive semi-definite constraint. Its last version stays readable and citable here.

Version 1 of 19 papers15 conceptsfrozen 2026-10-04

In classical kernel methods, the "Mercer condition" is a strict gatekeeper. It mandates that a similarity function must be Positive Semidefinite (PSD) to ensure that the resulting optimization problem is convex and well-behaved. However, many natural measures of similarity—such as the Kullback-Leibler divergence, string edit distances, or meta-paths in heterogeneous networks—are indefinite. They are symmetric, but they possess negative eigenvalues that break the standard quadratic programming machinery of Support Vector Machines (SVMs).

Recent research suggests that instead of forcing these "messy" kernels into a PSD mold through mathematical surgery, we should embrace their indefinite nature directly.

The Cost of Mathematical Conformity

When faced with an indefinite kernel, the traditional approach is to transform it: one might "clip" the negative eigenvalues to zero or "flip" them to their absolute values. While this restores the Mercer condition, it comes at a high price. Haiming Xu and Hui Xue argue in Solving Indefinite Kernel Support Vector Machine with Difference of Convex Functions Programming that these transformations distort the original similarity structure of the data.

By preserving the negative eigenvalues, models can leverage specific similarity information that would otherwise be discarded as "noise." In fact, Chenguang Wang and colleagues demonstrated in Text Classification with Heterogeneous Information Network Kernels that directly optimizing indefinite kernels can effectively denoise similarity data, leading to superior performance in complex domains like text classification.

Bypassing the Duality Gap

The primary reason we prefer PSD kernels is that they guarantee the dual problem (the one SVMs usually solve) is convex. When the kernel is indefinite, the dual problem becomes non-convex, and a "duality gap" emerges—the solution to the dual problem no longer matches the solution to the original primal problem.

To solve this, researchers have shifted the focus back to the primal formulation. Hui Xue and Haiming Xu show that by optimizing the primal objective directly, one can avoid the duality gap entirely (Multiple Indefinite Kernel Learning for Feature Selection). They utilize Difference of Convex (DC) functions programming, which decomposes a non-convex objective into two convex parts, allowing for efficient optimization even when the underlying similarity measure is mathematically "ill-behaved."

The 1-Norm Solution for Convexity

Perhaps the most elegant way to handle indefinite kernels is to change the objective function itself. Ibrahim Alabdulmohsin and Xin Gao have shown that the 1-norm SVM—which uses an $\ell_1$-norm penalty on weights—is naturally suited for this task (Support vector machines with indefinite kernels).

Unlike the standard 2-norm SVM, which results in a quadratic program, the 1-norm SVM can be formulated as a linear program. Crucially, this linear programming formulation remains convex regardless of whether the kernel matrix is positive semidefinite. This provides a "rare trifecta" for practitioners:

  1. Global Optimality: The problem remains convex, avoiding local minima.
  2. Accuracy: It matches or exceeds the performance of non-convex solvers.
  3. Sparsity: The $\ell_1$ penalty produces solutions that are significantly sparser, making the resulting models faster and more interpretable (Large margin classification with indefinite similarities).

Robustness and Generalization

Beyond classification accuracy, indefinite formulations offer unique advantages in security and robustness. Ambra Demontis and Battista Biggio explored the use of the Infinity-norm SVM (I-SVM) to defend against adversarial label-flipping attacks (Infinity-Norm Support Vector Machines Against Adversarial Label Contamination). By using an $\ell_\infty$ regularizer within a linear programming framework, the model distributes weights more evenly across training samples, preventing a few malicious data points from exerting undue influence on the decision boundary.

Similarly, Fanghui Liu and Johan Suykens extended these ideas to Indefinite Kernel Logistic Regression (Indefinite Kernel Logistic Regression With Concave-Inexact-Convex Procedure). Their work confirms that preserving the original similarity structure is often more critical for generalization than maintaining a traditional convex landscape.

By moving away from the rigid requirements of Mercer's theorem and utilizing primal optimization or linear programming, these methods allow machine learning models to work with the data as it is, rather than as the math demands it to be.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_support_vector_machines_for_indefinite_s_866d68e5,
  title = {Support Vector Machines for Indefinite Similarity Measures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/support-vector-machines-for-indefinite-similarity-measures/rdr_866d68e5636744068147ecbee6fd1dda},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_support_vector_machines_for_indefinite_s_866d68e5_v1,
  title = {Support Vector Machines for Indefinite Similarity Measures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/support-vector-machines-for-indefinite-similarity-measures/rdr_866d68e5636744068147ecbee6fd1dda/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}