Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network

• URL: http://arxiv.org/abs/2502.14536v2
• Date: Thu, 28 Aug 2025 08:34:59 GMT
• Title: Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network
• Authors: Jannik Irmai, Maximilian Moeller, Bjoern Andres,
• Abstract summary: The NP-hard maximum value preordering problem is a joint relaxation and a hybrid of the clique partition problem (a clustering problem) and the partial ordering problem.<n>We introduce a linear-time 4-approximation algorithm that constructs a maximum dicut of a subgraph and define local searchs.<n>We apply these algorithms to the task of jointly clustering and partially ordering the accounts of published social networks, and compare the output and efficiency qualitatively and quantitatively.
• Score: 8.436874393402158
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The NP-hard maximum value preordering problem is both a joint relaxation and a hybrid of the clique partition problem (a clustering problem) and the partial ordering problem. Toward approximate solutions and lower bounds, we introduce a linear-time 4-approximation algorithm that constructs a maximum dicut of a subgraph and define local search heuristics. Toward upper bounds, we tighten a linear program relaxation by the class of odd closed walk inequalities that define facets, as we show, of the preorder polytope. We contribute implementations of the algorithms, apply these to the task of jointly clustering and partially ordering the accounts of published social networks, and compare the output and efficiency qualitatively and quantitatively.

Related papers

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering [0.0]
  We present a tailored branch-and-cut algorithm for biclustering problems.<n>We show that the proposed algorithm can solve instances 20 times larger than those handled by general-purpose solvers.
  arXiv  Detail & Related papers  (2024-03-17T21:43:19Z)
• Constrained Hierarchical Clustering via Graph Coarsening and Optimal Cuts [1.5591858554014466]
  We study the problem of clustering words in a hierarchical fashion. In particular, we focus on the problem of clustering with horizontal and vertical structural constraints. We show that the resulting approach compares very well with respect to existing algorithms and is computationally light.
  arXiv  Detail & Related papers  (2023-12-07T10:52:06Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
  We make the first attempt to establish lower complexity bounds of first-order FOMs for solving a composite non-smooth optimization problem. We find that our method and the proposed IPG method are almostimprovable.
  arXiv  Detail & Related papers  (2023-07-14T19:59:18Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  We propose a class of non-text and non-smooth problems with textitrank regularization to promote sparsity in optimal solution. We show that our algorithms are able to achieve a singular convergence of $Ofrac(t2)$, which is exactly same as Nesterov's optimal convergence for first-order methods on smooth convex problems.
  arXiv  Detail & Related papers  (2023-07-04T16:55:41Z)
• Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
  In this paper, we develop an effective method for a set of candidate algorithms. At the inner level, given a subject, we utilize off-the-the-art constraints. The proposed method significantly improves the score of other algorithms.
  arXiv  Detail & Related papers  (2023-05-26T21:49:37Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Near-Optimal Correlation Clustering with Privacy [37.94795032297396]
  Correlation clustering is a central problem in unsupervised learning. In this paper, we introduce a simple and computationally efficient algorithm for the correlation clustering problem with provable privacy guarantees.
  arXiv  Detail & Related papers  (2022-03-02T22:30:19Z)
• Faster Deterministic Approximation Algorithms for Correlation Clustering and Cluster Deletion [5.584060970507507]
  Correlation clustering is a framework for partitioning datasets based on pairwise similarity and dissimilarity scores. In this paper we prove new relationships between correlation clustering problems and edge labeling problems related to the principle of strong partitioningic closure. We develop new approximation algorithms for correlation clustering that have deterministic constant factor approximation guarantees and avoid the canonical linear programming relaxation.
  arXiv  Detail & Related papers  (2021-11-20T22:47:19Z)
• Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming [5.126924253766052]
  We show that the proposed method exhibits a linear convergence rate for solving sharp instances with a high probability. We also propose an efficient coordinate-based oracle for unconstrained bilinear problems.
  arXiv  Detail & Related papers  (2021-11-10T04:56:38Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  Adversarial examples are a widely studied phenomenon in machine learning models. We propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-11-19T08:49:10Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
  We propose several algorithms to solve saddle-point problems using zeroth-order oracles. Our analysis shows that our convergence rate for the term is only by a $log n$ factor worse than for the first-order methods. We also consider a mixed setup and develop 1/2th-order methods that use zeroth-order oracle for the part.
  arXiv  Detail & Related papers  (2020-09-21T14:26:48Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)
• The {0,1}-knapsack problem with qualitative levels [2.0943517417159763]
  A variant of the classical knapsack problem is considered in which each item is associated with an integer weight and a qualitative level. We show that this relation defines a preorder. We propose a dynamic programming algorithm to compute the entire set of non-dominated rank cardinality vectors.
  arXiv  Detail & Related papers  (2020-02-12T09:00:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.