Rongqing Jiang, Xuebo Liu, Shengxin Liu, Yutong Wang, Min Zhang, Shimin Tao, Daimeng Wei, Min Zhang. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Extracting cohesive subgraphs from complex networks is a fundamental task in graph analytics and is essential for understanding biological, social, and web graphs. The edge-based γ-quasi-clique model offers a flexible alternative by identifying subgraphs whose edge densities exceed a specified threshold γ. However, finding the exact maximum edge-based quasi-clique is computationally challenging, as the problem is NP-hard and lacks the hereditary property. These characteristics limit the effectiveness of conventional pruning methods and the development of efficient reduction rules. As a result, existing algorithms, such as QClique and FPCE, struggle to scale to large graphs. In this paper, we revisit the problem and propose a novel iterative framework that reformulates the problem as a sequence of hereditary subproblems, enabling more effective pruning and reduction strategies and improving the worst-case time complexity. Furthermore, we redesign the iterative process and introduce a novel heuristic to further improve practical efficiency. Extensive experiments on 253 large-scale real-world graphs demonstrate that our proposed algorithm EQC-Pro outperforms existing methods by up to four orders of magnitude.

Cohesive subgraph mining has been extensively studied and finds numerous graph mining applications such as link farm identification, community detection, and product recommendation. Among various cohesive subgraph structures, the$k$-truss is particularly notable for its strong structural cohesiveness based on triangles. However, the classical$k$-truss problem aims to find the$k$-truss with the maximum number of vertices, which is often extremely large and complex in practice. To fully leverage the benefits of the$k$-truss, we consider a novel problem called theminimum$k$-truss problem, which seeks to identify a$k$-truss with the minimum number of vertices, where$k\geq 2$is a positive integer. We first formally prove the NP-hardness of the problem. We then design a baseline algorithmMTEnumthat is based on the vertex enumeration and a heuristic method for computing an upper bound. Despite these efforts,MTEnumstill faces practical efficiency issues which may be due to the fact that the$k$-truss lacks the hereditary property. To address this issue, we develop a novel decomposition-based frameworkDSA, which elegantly transforms the problem into a sequence of problems that are based on a new cohesive subgraph model callededge-based$s$-plex ($s$-eplex). With the hereditary property of$s$-eplex, we design a branch-and-bound algorithm with several customized techniques for the newly formulated problem. Extensive experiments demonstrate the effectiveness of our studied problem and the efficiency of our proposed algorithmDSA. In particular,DSAruns up to five orders of magnitude faster than the baselineMTEnum.

Cohesive subgraph mining is a fundamental problem in graph theory with numerous real-world applications, such as social network analysis and protein-protein interaction modeling. Among various cohesive subgraphs, the γ-quasi-clique is widely studied for its flexibility in requiring each vertex to connect to at least a γ proportion of other vertices in the subgraph. However, solving the maximum γ-quasi-clique problem is NP-hard and further complicated by the lack of the hereditary property, which makes designing efficient pruning strategies challenging. Existing algorithms, such as DDA and FastQC, either struggle with scalability or exhibit significant performance declines for small values of γ. In this paper, we propose a novel algorithm, IterQC, which reformulates the maximum γ-quasi-clique problem as a series of k-plex problems that possess the hereditary property. IterQC introduces a non-trivial iterative framework and incorporates two key optimization techniques: (1) the pseudo lower bound (pseudo LB) technique, which leverages information across iterations to improve the efficiency of branch-and-bound searches, and (2) the preprocessing technique that reduces problem size and unnecessary iterations. Extensive experiments demonstrate that IterQC achieves up to four orders of magnitude speedup and solves significantly more graph instances compared to state-of-the-art algorithms DDA and FastQC.

The problem of fair allocation of indivisible goods studies allocating a set of m goods among n agents in a fair manner. While fairness is a fundamental requirement in many real-world applications, it often conflicts with (economic) efficiency. This raises a natural and important question: How can we identify the most welfare-efficient allocation among all fair allocations? This paper gives an answer from the perspective of computational complexity. Specifically, we study the problem of maximizing utilitarian social welfare (the sum of agents' utilities) under two widely studied fairness criteria: envy-freeness up to any item (EFX) and envy-freeness up to one item (EF1). We examine both normalized and unnormalized valuations, where normalized valuations require that each agent's total utility for all items is identical.

The s -bundle, as a cohesive subgraph model which relaxes the clique, remains connected whenever fewer than n-s vertices are removed, where n is the number of vertices inside. Finding the largest s -bundle is a fundamental problem and has diverse applications in various fields such as social network analysis, graph visualization, and bioinformatics. Existing studies for solving the problem follow the same branch-and-bound framework and improve the efficiency by developing pruning techniques. As a result, all share the same worst-case time complexity of O* (2 n ), where O* suppresses the polynomial factors. In this paper, we propose a new branch-and-bound algorithm, called SymBD, which achieves improved theoretical guarantees and practical performance. It adopts the existing Symmetric-BK branching strategy whose performance highly depends on the ordering of vertices. We explore various vertex orderings for improving the performance. In particular, we propose two novel vertex orderings based on the local vertex connectivity. With the proposed vertex orderings, SymBD improves the worst-case time complexity to O* (λ n s ) where λ s is strictly less than 2. To further boost the practical efficiency, we introduce a heuristic algorithm for computing a large initial solution and a divide-and-conquer strategy. Extensive experiments on 664 graphs demonstrate that our algorithm is up to five orders of magnitude faster than existing solutions.

Community search has widespread applications in areas such as advertising, friend recommendation, and protein complex identification. In this paper, we revisit the Size-bounded Community Search (SCS) problem, which aims to identify a connected subgraph containing a query vertex q and between l and h vertices, while maximizing the minimum degree of the subgraph. Existing state-of-the-art exact solutions for SCS face challenges in practical efficiency due to ineffective strategies for searching candidate solutions and suboptimal method for finding optimal solution. To address these challenges, we propose a novel branch-and-bound algorithm that efficiently locating a subset of candidate solutions with favorable structural properties, forming the basis for three progressively refined frameworks to determine the optimal solution. Furthermore, we enhance practical performance through a new heuristic, two reduction rules, and a query decomposition technique. Extensive experiments on 12 large real-world graphs demonstrate that our most efficient framework significantly outperforms state-of-the-art methods, achieving an average speedup of two orders of magnitude while consistently identifying communities with higher cohesion.

Finding cohesive subgraphs from a directed graph is a fundamental approach to analyze directed graph data. We consider a new model called directed$(k,\ell )$-plex for a cohesive directed subgraph, which is generalized from the concept of$k$-plex that is only applicable to undirected graphs. Directed$(k,\ell )$-plex (or DPlex) has the connection requirements on both inbound and outbound directions of each vertex inside, i.e., each vertex disconnects at most$k$vertices and is meanwhile not pointed to by at most$\ell$vertices. In this paper, we study the maximum DPlex search problem which finds a DPlex with the most vertices. We formally prove the NP-hardness of the problem. We then design a heuristic algorithm calledDPHeuris, which finds a DPlex with the size close to the maximum one and runs practically fast in polynomial time. Furthermore, we propose a branch-and-bound algorithm calledDPBBto find the exact maximum DPlex and develop effective graph reduction strategies for boosting the empirical performance. We also consider the problem of querying personalized maximum DPlex, and design a new method calledDPBBQfor the problem. Finally, we conduct extensive experiments on real directed graphs. The experimental results show that (1) our heuristic method can quickly find a near-optimal solution and (2) our branch-and-bound method runs up to six orders of magnitude faster than other baselines.

The$k$-vertex connected ($k$-VC) subgraph, which remains connected with fewer than$k$vertices being removed, is an essential structure in graph mining. It has found many applications, such as survivable network design and web search optimization. However, existing studies focus on mining maximal$k$-VCs, which are excessively large yet less cohesive in real applications. In this paper, we study theminimum$k$-VC search (MinVC)problem, seeking to find a$k$-VC with the minimum number of vertices. We formally prove that this problem is NP-hard and then propose two algorithms to obtain the exact solution. The basic method, calledEnum, follows a branch-and-bound framework with some pruning rules, which directly enumerates all possible vertex sets. Nonetheless, it suffers from the efficiency issues due to the non-hereditary property of the$k$-VC model. To address this challenge, we propose an advanced method, calledVCtoB, which divides theMinVCproblem into several new sub-problems, called thefixed-size$k$-VCproblems. Each of them can be solved efficiently by exploiting the hereditary property of the$s$-bundle model. Finally, our empirical experiments on 139 real-world networks demonstrate thatVCtoBachieves performance improvement of up to six orders of magnitude over the baseline.

The fair allocation of resources to agents is a fundamental problem in society and has received significant attention and rapid developments from the game theory and artificial intelligence communities in recent years. The majority of the fair division literature can be divided along at least two orthogonal directions: goods versus chores, and divisible versus indivisible resources. In this survey, besides describing the state of the art, we outline a number of interesting open questions in three mixed fair division settings: (i) indivisible goods and chores, (ii) divisible and indivisible goods (i.e., mixed goods), and (iii) fair division of indivisible goods with subsidy.

Finding cohesive subgraphs from a directed graph is a fundamental approach to analyze directed graph data. We consider a new model called directed$(k,\ell)$-plex for a cohesive directed subgraph, which is generalized from the concept of$k$-plex that is only applicable to undirected graphs. Directed$(k,\ell)$-plex has the connection requirements on both inbound and outbound directions of each vertex inside, i.e., each vertex disconnects at most$K$vertices and is meanwhile not pointed to by at most$\ell$vertices. In this paper, we study the maximum directed$(k, \ell)$-plex search problem which finds a directed$(k, \ell)$-plex with the most vertices. We formally prove the NP-hardness of the problem. We then design a heuristic algorithm called DPHeuris, which finds a directed$(k, \ell)$-plex with the size close to the maximum one and runs practically fast in polynomial time. Furthermore, we propose a branch-and-bound algorithm called DPBB to find the exact maximum directed$(k, \ell)$-plex and develop effective graph reduction strategies for boosting the empirical performance. Finally, we conduct extensive experiments on real directed graphs. The experimental results show that (1) our heuristic method can quickly find a near-optimal solution and (2) our branch-and-bound method runs up to six orders of magnitude faster than other baselines.

We introduce the Self-Exemplar Illumination Equalization Network, designed specifically for effective portrait shadow removal. The core idea of our method is that partially shadowed portraits can find ideal exemplars within their non-shadowed facial regions. Rather than directly fusing two distinct classes of facial features, our approach utilizes non-shadowed regions as an illumination indicator to equalize the shadowed regions, generating deshadowed results without boundary-merging artifacts. Our network comprises cascaded Self-Exemplar Illumination Equalization Blocks (SExmBlock), each containing two modules: a self-exemplar feature matching module and a feature-level illumination rectification module. The former identifies and applies internal illumination exemplars to shadowed areas, producing illumination-corrected features, while the latter adjusts shadow illumination by reapplying the illumination factors from these features to the input face. Applying this series of SExmBlocks to shadowed portraits incrementally eliminates shadows and preserves clear, accurate facial details. The effectiveness of our method is demonstrated through evaluations on two public shadow portrait datasets, where it surpasses existing state-of-the-art methods in both qualitative and quantitative assessments.

Fair division considers the allocation of scarce resources among agents in such a way that every agent gets a fair share. It is a fundamental problem in society and has received significant attention and rapid developments from the game theory and artificial intelligence communities in recent years. The majority of the fair division literature can be divided along at least two orthogonal directions: goods versus chores, and divisible versus indivisible resources. In this survey, besides describing the state of the art, we outline a number of interesting open questions and future directions in three mixed fair division settings: (i) indivisible goods and chores, (ii) divisible and indivisible goods (mixed goods), and (iii) indivisible goods with subsidy which can be viewed like a divisible good.

k -plexes relax cliques by allowing each vertex to disconnect to at most k vertices. Finding a maximum k -plex in a graph is a fundamental operator in graph mining and has been receiving significant attention from various domains. The state-of-the-art algorithms all adopt the branch-reduction-and-bound (BRB) framework where a key step, called reduction-and-bound (RB), is used for narrowing down the search space. A common practice of RB in existing works is SeqRB, which sequentially conducts the reduction process followed by the bounding process once at a branch. However, these algorithms suffer from the efficiency issues. In this paper, we propose a new alternated reduction-and-bound method AltRB for conducting RB. AltRB first partitions a branch into two parts and then alternatively and iteratively conducts the reduction process and the bounding process at each part of a branch. With newly-designed reduction rules and bounding methods, AltRB is superior to SeqRB in effectively narrowing down the search space in both theory and practice. Further, to boost the performance of BRB algorithms, we develop efficient and effective pre-processing methods which reduce the size of the input graph and heuristically compute a large k -plex as the lower bound. We conduct extensive experiments on 664 real and synthetic graphs. The experimental results show that our proposed algorithm kPEX with AltRB and novel preprocessing techniques runs up to two orders of magnitude faster and solves more instances than state-of-the-art algorithms.

We consider the fair division problem of indivisible items. It is well-known that an envy-free allocation may not exist, and a relaxed version of envy-freeness, envy-freeness up to one item (EF1), has been widely considered. In an EF1 allocation, an agent may envy others' allocated shares, but only up to one item. In many applications, we may wish to specify a subset of prioritized agents where strict envy-freeness needs to be guaranteed from these agents to the remaining agents, while ensuring the whole allocation is still EF1. Prioritized agents may be those agents who are envious in a previous EF1 allocation, those agents who belong to underrepresented groups, etc. Motivated by this, we propose a new fairness notion named envy-freeness with prioritized agents EFprior, and study the existence and the algorithmic aspects for the problem of computing an EFprior allocation. With additive valuations, the simple round-robin algorithm is able to compute an EFprior allocation. In this paper, we mainly focus on general valuations. In particular, we present a polynomial-time algorithm that outputs an EFprior allocation with most of the items allocated. When all the items need to be allocated, we also present polynomial-time algorithms for some well-motivated special cases.

The k-core, which refers to the induced subgraph with a minimum degree of at least k, is widely used in cohesive subgraph discovery and has various applications. However, the k-core in real-world graphs tends to be extremely large, which hinders its effectiveness in practical applications. This challenge has motivated researchers to explore a variant of the k-core problem known as the minimum k-core search problem. This problem has been proven to be NP-Hard, and most of the existing studies naturally either deal with approximate solutions or suffer from inefficiency in practice. In this paper, we focus on designing efficient exact algorithms for the minimum k-core search problem. In particular, we develop an iterative-based framework that decomposes an instance of the minimum k-core search problem into a list of problem instances on another well-structured graph pattern. Based on this framework, we propose an iterative-based branch-and-bound algorithm, namely IBB, with additional pruning and reduction techniques. We show that, with a n-vertex graph, IBB runs in cn nO(1) time for some c < 2, achieving better theoretical performance than the trivial bound of 2n nO(1). Finally, our experiments on real-world graphs demonstrate that IBB is up to three orders of magnitude faster than the state-of-the-art algorithms on real-world datasets.

We study the problem of designing truthful and fair mechanisms when allocating a mixture of divisible and indivisible goods. We first show that there does not exist an EFM (envy-free for mixed goods) and truthful mechanism in general. This impossibility result holds even if there is only one indivisible good and one divisible good and there are only two agents. Thus, we focus on some more restricted settings. Under the setting where agents have binary valuations on indivisible goods and identical valuations on a single divisible good (e.g., money), we design an EFM and truthful mechanism. When agents have binary valuations over both divisible and indivisible goods, we first show there exist EFM and truthful mechanisms when there are only two agents or when there is a single divisible good. On the other hand, we show that the mechanism maximizing Nash welfare cannot ensure EFM and truthfulness simultaneously.

With the proliferation of location-based services, geo-textual data is becoming ubiquitous. Objects involved in geo-textual data include geospatial locations, textual descriptions or keywords, and various attributes (e.g., a point-of-interest has its expenses and users' ratings). One prominent type of spatial keyword queries is to find, for a query consisting of a location and keywords, a set of objects that covers all the keywords and is of good quality according to some criteria. Existing studies define the criteria either based on the geospatial information of the objects solely or simply treat the geospatial and attribute information of the objects together without differentiation. As a result, they cannot provide users flexibility to express finer grained preferences on the objects. In this paper, we propose a new criterion which is to find a set of objects where the distance (defined based on the geospatial information) is at most a threshold specified by users and the cost (defined based on the attribute information) is optimized. We develop a suite of three algorithms including an exact algorithm and two approximation algorithms with provable guarantees for the problem. We conducted extensive experiments on real datasets which verified the efficiency and effectiveness of proposed algorithms.

With the proliferation of location-based services, geo-textual data is becoming ubiquitous. Objects involved in geo-textual data include geospatial locations, textual descriptions or keywords, and various attributes (e.g., a point-of-interest has its expenses and users' ratings). Many types of spatial keyword queries have been proposed on geo-textual data. Among them, one prominent type is to find, for a query consisting of a query location and some query keywords, a set of multiple objects such that the objects in the set collectively cover all the query keywords, and the object set is of good quality according to some criterion. Existing studies define the criterion either based on the geospatial information of the objects solely, or simply treat the geospatial information and the attribute information of the objects together without differentiation though they may have different semantics and scales. As a result, they cannot provide users flexibility to express finer grained preferences on the objects. In this paper, we propose a new criterion which is to find a set of objects where the distance (defined based on the geospatial information) is at most a threshold specified by users and the cost (defined based on the attribute information) is optimized. We develop a suite of two algorithms including an exact algorithm and an approximation algorithm with provable guarantees for the problem. We conducted extensive experiments on both real and synthetic datasets, which verified the efficiency and effectiveness of proposed algorithms.

Mining maximal subgraphs with cohesive structures from a bipartite graph has been widely studied. One important cohesive structure on bipartite graphs is k-biplex, where each vertex on one side disconnects at most k vertices on the other side. In this paper, we study the maximal k-biplex enumeration problem which enumerates all maximal k-biplexes. Existing methods suffer from efficiency and/or scalability issues and have the time of waiting for the next output exponential w.r.t. the size of the input bipartite graph (i.e., an exponential delay). In this paper, we adopt a reverse search framework called bTraversal, which corresponds to a depth-first search (DFS) procedure on an implicit solution graph on top of all maximal k-biplexes. We then develop a series of techniques for improving and implementing this framework including (1) carefully selecting an initial solution to start DFS, (2) pruning the vast majority of links from the solution graph of bTraversal, and (3) implementing abstract procedures of the framework. The resulting algorithm is called iTraversal, which has its underlying solution graph significantly sparser than (around 0.1% of) that of bTraversal. Besides, iTraversal provides a guarantee of polynomial delay. Our experimental results on real and synthetic graphs, where the largest one contains one billion edges, show that our algorithm is up to four orders of magnitude faster than existing algorithms.

We study fair resource allocation when the resources contain a mixture of divisible and indivisible goods, focusing on the well-studied fairness notion of maximin share fairness (MMS). With only indivisible goods, a full MMS allocation may not exist, but a constant multiplicative approximate allocation always does. We analyze how the MMS approximation guarantee would be affected when the resources to be allocated also contain divisible goods. In particular, we show that the worst-case MMS approximation guarantee with mixed goods is no worse than that with only indivisible goods. However, there exist problem instances to which adding some divisible resources would strictly decrease the MMS approximation ratios of the instances. On the algorithmic front, we propose a constructive algorithm that will always produce an \alpha-MMS allocation for any number of agents, where \alpha takes values between 1/2 and 1 and is a monotonically increasing function determined by how agents value the divisible goods relative to their MMS values.

We study the problem of fair division when the resources contain both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to the mixed goods setting. In this work, we propose a new fairness notion envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents. We also propose efficient algorithms to compute an EFM allocation for two agents and for n agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-free requirement, instead asking for ϵ-envy-freeness for mixed goods (ϵ-EFM), and present an algorithm that finds an ϵ-EFM allocation in time polynomial in the number of agents, the number of indivisible goods, and 1/ϵ.

Growing mobile data usage has led to end users paying substantial data costs, while Internet service providers (ISPs) struggle to upgrade their networks to keep up with demand and maintain high quality-of-service (QoS). This problem is particularly severe for smaller ISPs with less capital. Instead of simply upgrading their network infrastructure, ISPs can pool their networks to provide a good QoS and attract more users. Such a vISP (virtual ISP), for example, Google's Project Fi, allows users to access any of its partner ISPs' networks. We provide the first systematic analysis of a vISP's economic impact, showing that the vISP provides a viable solution for smaller ISPs attempting to attract more users, but may not maintain a positive profit if users' data demands evolve. To do so, we consider users' decisions of whether to defect from their current ISP to the vISP, as well as existing ISPs' decisions on whether to partner with the vISP. We derive the vISP's dependence on user behavior and partner ISPs: users with very light or very heavy usage are the most likely to defect, while ISPs with heavy-usage customers can benefit from declining to partner with the vISP. Our analytical results are verified with extensive numerical simulations.