arXiv:2110.08385

Robust Correlation Clustering with Asymmetric Noise

Jimit Majmudar, Stephen Vavasis

제출 2021-10-15

원문 초록

Graph clustering problems typically aim to partition the graph nodes such that two nodes belong to the same partition set if and only if they are similar. Correlation Clustering is a graph clustering formulation which: (1) takes as input a signed graph with edge weights representing a similarity/dissimilarity measure between the nodes, and (2) requires no prior estimate of the number of clusters in the input graph. However, the combinatorial optimization problem underlying Correlation Clustering is NP-hard. In this work, we propose a novel graph generative model, called the Node Factors Model (NFM), which is based on generating feature vectors/embeddings for the graph nodes. The graphs generated by the NFM contain asymmetric noise in the sense that there may exist pairs of nodes in the same cluster which are negatively correlated. We propose a novel Correlation Clustering algorithm, called \anormd, using techniques from semidefinite programming. Using a combination of theoretical and computational results, we demonstrate that $\texttt{$\ell_2$-norm-diag}$ recovers nodes with sufficiently strong cluster membership in graph instances generated by the NFM, thereby making progress towards establishing the provable robustness of our proposed algorithm.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.22590v1math.OC공통 태그 Clustering, Combinatorial Optimization

DRP-FLR: 스마트 그리드 유연 부하 조절을 위한 수요 반응 잠재력의 데이터 기반 평가

DRP-FLR: Data-Driven Assessment of Demand Response Potential for Flexible Load Regulation in Smart Grids

AI 워크로드와 재생에너지 자원의 급속한 증가는 전력 시스템의 수급 불균형을 악화시켜, 효율적 배분을 위해 설계된 기존 부하 조절 방식이 부적절해지게 하며, 스마트 그리드에서 부하 제어 가능성을 확보하기 위한 수요 반응(DR) 메커니즘의 필요성을 촉발한다. 그러나 기존 DR 중심 접근법은 전기 요금 또는 거주자 편의성 최적화에만 초점을 맞추어 시스템 수준의 균형에 대한 이점이 제한적이다. 다른 접근법들은 이질적 에너지 개체의 다양하고 동적인 소비 패턴을 간과하여 상당한 과조절 또는 저조절을 초래한다. 따라서 우리는 DRP-FLR을 제안한다. 첫째, DRP-FLR은 외생적 지식(예: 개체 정보, 예측 시점)을 역사적 부하 표현에 임베딩하여 정확한 단기 부하 예측을 달성한다. 다음으로, 역사적 부하 곡선을 클러스터링하여 개체별 부하 패턴 프로파일을 구성하고, 예측된 부하와 패턴 프로파일을 매칭하여 DR 잠재력을 추정한다. 마지막으로, DRP-FLR은 유연 부하 조절을 혼합 정수 최적화 문제로 공식화하고 MILP 솔버로 이를 풀어 DR 활용, 참여자 경제적 이익, 재생에너지 수용을 공동으로 최적화하면서 수급 균형과 경제적 실현 가능성을 강제한다. 지역 그리드와 캠퍼스 마이크로그리드에서의 실험은 DRP-FLR이 조절 편차를 36.63%-91.87% 감소시키고 참여자 이익을 평균 44.66% 개선함을 보여준다.

arXiv:2607.24288v1cs.CV공통 태그 Clustering, Combinatorial Optimization

확장 가능한 양자 향상 의료 이미지 분할을 위한 슈퍼픽셀 기반 QUBO

Superpixel-Based QUBO for Scalable Quantum-Enhanced Medical Image Segmentation

이차 무제약 이진 최적화(QUBO)는 의료 컴퓨팅 문제를 위한 강력한 프레임워크로 부상했다. 이진 결정 변수는 임상적 선택을 자연스럽게 표현하므로, QUBO 공식화는 양자 어닐링(quantum annealing) 하드웨어에 잘 맞다. 그러나 근본적인 확장성(scalability) 과제가 실용적 배포를 제한한다. 문제 크기는 입력 차원에 따라 급격히 증가하여 계산 병목을 만들고, 응용을 단순화된 시나리오로 제한한다. 본 논문은 계층적 문제 축소를 통해 이 과제를 해결하며, 이는 의료 이미지 분할에서 입증된다. 픽셀 수준 QUBO 공식화는 256×256 이미지에 65,000개 이상의 변수를 생성하여, 기존 접근법이 42×42 해상도로 다운샘플링하고 픽셀 정보의 97%를 버리도록 만든다. simple linear iterative clustering(SLIC)을 사용해 픽셀을 지각적으로 의미 있는 영역으로 묶는 슈퍼픽셀 기반 QUBO 프레임워크를 제안하고, min-cut과 smoothness 목적함수를 결합한 영역 인접 그래프(RAG) 위에서 분할을 QUBO로 공식화한다. INbreast 유방촬영 유방암 영상에 대한 검증 결과, 분할 품질이 4.2% 향상되었음(평균 IoU 0.76 대 0.73)을 보였으며, 계산 속도는 33배 향상(0.67초 대 21.97초), 문제 크기는 97.3% 감소(1764에서 48 변수)하였다. 이는 모두 다운샘플링된 버전이 아닌 전체 해상도 영상을 처리하면서 달성되었다. 축소된 문제 크기는 또한 현재 양자 어닐러의 연결성 한계 내에 잘 들어맞아, 역사적으로 양자 하드웨어에서 픽셀 수준 QUBO 분할의 직접 배포를 막아온 임베딩(embedding) 오버헤드를 제거한다.

arXiv:2607.21368v1cs.CV공통 태그 Clustering, Combinatorial Optimization

실시간 군중 추적을 위한 증분 최적 할당

Incremental Optimal Assignment for Real-Time Crowd Tracking

밀집 군중에서의 다중 객체 추적은 매 비디오 프레임마다 검출과 궤적 간의 이분 할당 문제를 풀어야 한다. 고전적인 헝가리안 알고리즘은 이를 $O(N^3)$ 시간에 해결하지만, 수백 명의 사람이 있는 대규모 장면에서는 병목이 된다. 우리는 군중 추적 비용 행렬의 블록 희소(block-sparse) 구조를 활용하는 \emph{증분} 할당 알고리즘을 제안한다 — 각 군중 클러스터 내부에서는 조밀하고, 클러스터 간에는 거의 0에 가깝다. 헝가리안 알고리즘과 동일한 최적 $N \times N$ 할당을 계산하지만, 증분 전략을 통해 수행한다: 한 번에 한 사람씩 추가하며, $n-1$단계 이후 이중 잠재(dual potentials)가 $(n-1)\times(n-1)$ 부분 문제에 대해 \emph{정확히 최적}이라는 사실을 활용한다 — 이는 헝가리안 알고리즘이 $N$번의 외부 반복 동안 유지하는 중간 실행 가능성(intermediate feasibility)보다 엄격히 더 강한 조건이다. 따라서 각 새 단계는 인증된 최적 시작점에서 단 한 번의 증강 경로(augmenting path) 탐색만 필요하다. 이는 반복적인 전체 행렬 스캔을 피하면서 동일한 전역 최적 결과를 보장한다. 대각 재정렬 불변(diagonal-reordering invariant)은 데이터 구조를 컴팩트하고 캐시 친화적으로 유지한다. $N \in [200, 5000]$ 범위의 사람들이 밀집 클러스터로 구성된 현실적인 군중 벤치마크에서, 우리 알고리즘은 헝가리안 기준선 대비 \textbf{3.7--6.5$\times$} 속도 향상을 달성하며, 헝가리안과 동일한 증명 가능한 최적 매칭을 생성한다. 속도 향상은 $N$에 따라 증가하며 $N=3000$을 넘어서도 안정적으로 유지되어, 경기장 출구나 대규모 공공 행사와 같은 대규모 군중 장면에 특히 적합하다.

arXiv:2607.13728v1cs.IR공통 태그 Clustering, Combinatorial Optimization

벡터 검색을 위한 Cluster with Auctions

Cluster with Auctions for Vector Search

대규모 근사 최근접 이웃(approximate nearest neighbor) 검색은 인덱싱을 위해 파티셔닝에 일반적으로 의존한다. 데이터베이스 벡터가 클러스터로 파티셔닝되고, 각 쿼리에 대해 프로빙(probing) 함수가 스캔할 클러스터를 선택한다. 쿼리 프로빙 함수와 데이터베이스 파티션은 별개의 개체로 취급되는 경우가 드물며, 대부분의 기법은 데이터베이스 벡터와 동일한 할당 함수를 사용해 쿼리를 배정한다. 이는 특히 데이터베이스와 쿼리 분포가 다를 때 최적이 아니다. 본 논문은 균형 잡힌 데이터베이스 파티션과 신경망 기반 프로빙 함수를 공동으로 학습함으로써 이 한계를 해결하는 CwA(Cluster with Auctions)를 제안한다. CwA는 쿼리 분포에 대해 검색 성능을 직접 최적화하며, 목적 함수를 최소화하기 위해 (i) 프로빙 함수의 신경망에 대한 경사하강법과 (ii) 데이터베이스 벡터에 대한 클러스터 할당의 대규모 조합 최적화, 두 단계를 번갈아 수행한다. 후자는 파티션을 설계상 균형화하는 병렬화 가능한 경매(auction) 알고리즘으로 해결한다. CwA의 확장성을 더 높이기 위해, 파티션의 세분성을 높이는 클러스터의 데카르트 곱(Cartesian product)으로 방법을 확장한다. 데이터베이스와 쿼리 분포가 다른 경우, CwA는 동일한 재현율에서 최신(state-of-the-art) 방법 대비 최대 4.7$\times$의 처리량(throughput)을 달성한다. 분포 내(in-distribution, ID) 설정에서도 CwA로 학습한 단순한 선형 프로빙 함수조차 경쟁하는 딥 신경망 기법들보다 우수한 성능을 보인다.

arXiv:2607.13217v1cs.DS공통 태그 Clustering, Combinatorial Optimization

계층적 $\mathcal{F}$-클러스터링: 트리 및 유계 직경 그래프로의 클러스터링의 근사와 난해성

Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

계층적 클러스터링(Hierarchical Clustering) 문제의 다음과 같은 변형을 고려한다. 일반적으로 계층적 클러스터링을 구축할 때는 각 클러스터가 단일 원소(singleton)가 될 때까지 데이터를 재귀적으로 분할한다. 우리는 재귀 과정의 중단 조건을 완화하여, 남은 클러스터가 클래스 $\mathcal{F}$에 속하는 그래프가 되는 시점에 멈추도록 한다. 이 문제를 계층적 $\mathcal{F}$-클러스터링이라 하며, 임의의 해법의 품질은 수정된 Dasgupta의 클러스터링 목적 함수로 측정한다. $\mathcal{F}$의 두 가지 자연스러운 선택인 트리와 유계 직경(bounded diameter) 그래프를 연구한다. 트리로의 클러스터링과 유계 직경 그래프로의 클러스터링에 대해 각각 최초의 다항 시간 $\mathcal{O}(\log n\cdot\log\log n)$ 및 $\mathcal{O}(\log n)$ 근사 알고리즘을 제시한다. 주요 기술적 기여는 선형 계획법(linear programming)에 기반한 이러한 문제의 근사를 위한 프레임워크이다. 실제로 우리의 접근법을 적용할 수 있는 그래프 클래스 $\mathcal{F}$를 특성화하고, 이 클래스가 트리와 유계 직경 그래프를 모두 포함함을 보인다. 그러나 우리의 아이디어는 이들에 국한되지 않으며 다른 구조에도 유용할 수 있다. 넓게 말하면, 우리의 프레임워크는 대응하는 평면(flat) 클러스터링 문제—$p_{\mathcal{F}}$-Partitioning이라 부르는—가 자연스러운 ILP 정식화와 증명 가능한 근사 보장을 갖는 라운딩(rounding) 절차를 함께 허용할 때 적용된다. 직관적으로, 터미널(terminal)이라 불리는 정점 집합이 주어졌을 때 문제는 각 터미널에 대해 정점 의존적 구조적 술어(predicate)를 만족하도록 하는 간선 집합을 제거하는 것이다. 그런 다음 이러한 요소들을 사용하여 앞서 언급한 근사 보장을 갖는 클러스터링 트리를 구축한다. 이 결과를 보완하기 위해, 트리로의 계층적 클러스터링과 유계 직경 그래프로의 계층적 클러스터링 모두 소규모 집합 확장 가설(Small Set Expansion Hypothesis) 하에서 임의의 상수 배수 이내로 근사될 수 없음을 보인다.

arXiv:2607.13218v1cs.DS공통 태그 Clustering, Combinatorial Optimization

수요가 있는 그래프 분할: 일반화된 컨던턴스와 그 응용

Graph Partitioning with Demands: Generalized Conductance and its Applications

본 논문에서는 일반적인 수요 모델 하에서 다양한 그래프 분할 문제를 연구한다. 각 문제에서 용량 함수 $c\colon E\to \mathbb{N}$와 수요 함수 $w\colon V\times V\to \mathbb{N}$가 주어진 그래프 $G=(V,E,c,w)$가 주어진다. 우리의 주요 관심사는 컷 $(S, \bar{S})$를 찾아 다음 양을 최소화하는 문제이다. \[ ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}. \] 여기서 $c( S, \bar{S} )$는 $S$와 $S$의 여집합 $\bar{S}$ 사이의 간선 비용이며, $w( S, V )=w( S )+w( S, \bar{S} )$는 $S$ 내부의 내부 수요 $w( S )$와 $S$의 꼭짓점과 $\bar{S}$의 꼭짓점 사이의 수요 $w( S, \bar{S} )$의 합이다. $ψ_w( S )$를 컷 $(S, \bar{S})$의 \emph{generalized conductance}(일반화된 컨던턴스)라 하고, $ψ_w( S )$를 최소화하는 과제를 Generalized Conductance Problem(일반화된 컨던턴스 문제)라 부른다. 주요 기여는 이 목적함수에 대해 $\mathcal{O}(\log n)$-근사 보장을 갖는 알고리즘을 제시하는 것이다. 이 결과는 양방향 환원을 통해 달성된다. 먼저 잘 알려진 Generalized $k$-Multicut Problem으로 환원하고, 이어서 잘릴 수 있는 수요량에 대한 추가 상한 제약이 있는 고전 Sparsest-Cut Problem의 제약 변형으로 환원한다. 더 나아가, 위 절차가 수요가 있는 그래프 분할(Graph Partitioning with Demands)에 대해 $\mathcal{O}(\log n)$-이기준 근사를 얻는 데 사용될 수 있음을 보인다. 여기서 목표는 $G\setminus C$의 모든 연결 성분 $H$에 대해 $w( H )\leq ρ\cdot w( V )$를 만족하는 최소 비용의 간선 부분집합 $C$를 찾는 것이다. 이는 차례로 수요가 있는 계층적 클러스터링(Hierarchical Clustering with Demands)—그래프를 점점 더 세분화된 클러스터로 분할하는 컷의 계층을 찾는 문제—에 대한 $\mathcal{O}(\log n)$-근사를 제공한다. 곱셈형 수요 함수(multiplicative demand functions)의 경우 이러한 보장을 $\mathcal{O}(\sqrt{\log n})$로 개선하며, 트리(tree)의 경우 모든 목적함수에 대해 $\mathcal{O}(1)$-근사를 얻는다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.