  A signed graph is a graph where each edge receives a sign, positive or
negative. The signed graph model has been used in many real applications, such
as protein complex discovery and social network analysis. Finding cohesive
subgraphs in signed graphs is a fundamental problem. A k-plex is a common model
for cohesive subgraphs in which every vertex is adjacent to all but at most k
vertices within the subgraph. In this paper, we propose the model of
size-constrained antagonistic k-plex in a signed graph. The proposed model
guarantees that the resulting subgraph is a k-plex and can be divided into two
sub-k-plexes, both of which have positive inner edges and negative outer edges.
This paper aims to identify all maximal antagonistic k-plexes in a signed
graph. Through rigorous analysis, we show that the problem is NP-Hardness. We
propose a novel framework for maximal antagonistic k-plexes utilizing set
enumeration. Efficiency is improved through pivot pruning and early termination
based on the color bound. Preprocessing techniques based on degree and
dichromatic graphs effectively narrow the search space before enumeration.
Extensive experiments on real-world datasets demonstrate our algorithm's
efficiency, effectiveness, and scalability.
