arXiv:2412.15695

Hypergraph clustering using Ricci curvature: an edge transport perspective

Olympio Hacquard

제출 2024-12-20

원문 초록

In this paper, we introduce a novel method for extending Ricci flow to hypergraphs by defining probability measures on the edges and transporting them on the line expansion. This approach yields a new weighting on the edges, which proves particularly effective for community detection. We extensively compare this method with a similar notion of Ricci flow defined on the clique expansion, demonstrating its enhanced sensitivity to the hypergraph structure, especially in the presence of large hyperedges. The two methods are complementary and together form a powerful and highly interpretable framework for community detection in hypergraphs.

함께 살펴볼 논문

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

arXiv:2609.30277v2cs.LG공통 태그 Clustering, Community Detection

고정된 확산 없는 고정점: 수렴하는 테스트 시점 연산을 위한 암시적 신경 층

Fixed Points Without Fixed Diffusion: Implicit Neural Sheaves for Convergent Test-Time Computation

암시적 그래프 신경망(IGNN)은 노드 표현을 그래프 신경 연산자의 고정점(fixed point)으로 정의하여 실질적으로 무한한 깊이의 전파, 반복(iteration) 독립적인 매개변수화, 유연한 테스트 시점 연산(test-time computation)을 가능하게 합니다. 그러나 이러한 이점은 평형점이 유일하며 고정점 반복을 통해 도달할 수 있는지 여부에 달려 있습니다. 기존의 구조들은 이러한 보장을 얻기 위해 순환 업데이트에 제약을 가하는 경우가 많아 평형 상태에서 사용 가능한 변환을 제한했습니다. 이는 핵심적인 질문을 제기합니다: IGNN이 평형 정식화의 고유한 강점을 유지하면서 더 풍부한 엣지 의존적 변환을 통해 표현력을 얻을 수 있을까요? 본 논문에서는 적응형 신경 층(neural-sheaf) 전파를 갖춘 준동차(subhomogeneous) 심층 평형 아키텍처인 SheafDEQ를 소개합니다. 학습된 행렬 값 층 제한 사상(sheaf restriction map)은 이웃한 표현들을 정렬, 혼합 또는 반전시킬 수 있습니다. 완만한 정칙성 조건 하에서, SheafDEQ가 임의의 양의 초기 상태로부터 고정점 반복을 통해 전역적으로 도달 가능한 유일한 평형점을 가짐을 증명합니다. 나아가 축약성(contractivity)은 유계된 통신 지연(staleness) 하에서도 수렴을 보장합니다. 본 연구는 반복적인 비국소적 집계가 필요한 분산 추론(inference) 태스크와 연결 재구성이 점차 커뮤니티 간 상호작용을 선호하게 되는 커뮤니티 탐지 태스크에서 SheafDEQ를 평가합니다. SheafDEQ는 Sums, MNIST Terrain, Coordinates 태스크 및 연결성이 점차 이종친화적(heterophilic)으로 변하는 커뮤니티 탐지에서 암시적 베이스라인보다 향상된 성능을 보입니다. 또한 SheafDEQ는 평형 보장이 없는 순환 모델들과 비교해도 경쟁력을 유지합니다. 연속 반복 진단 결과 유한 구간(finite-horizon) 대조군과 달리 100회 반복까지 잔차가 감소하고 테스트 정확도가 유지됨을 확인하였으며, 지연 업데이트 실험에서는 유계된 통신 지연에 대해 낮은 민감도를 나타냈습니다.

arXiv:2609.28262v1cs.CV공통 태그 Clustering, Sensitivity

RAMP: 엣지 CPU 비전 모델을 위한 강건한 적응형 혼합 정밀도 양자화

RAMP: Robust Adaptive Mixed-Precision Quantization for Edge CPU Vision Models

엣지 CPU에 심층 학습 모델을 배포할 때는 계산 및 메모리 제약이 병목이 된다. 혼합 정밀도 양자화는 정확도를 유지하면서 추론 지연을 줄일 수 있다고 기대된다. 그러나 양자화는 층 유형마다 서로 다르게 영향을 미치므로, 정확도 손실이 최소화되고 지연 감소가 최대화되는 위치를 찾는 것이 중요하며, 그 효과는 전체 배포에 걸쳐 누적되어 상당한 이득 또는 허용 불가능한 과제 성능 저하로 이어진다. 이러한 식별은 민감도 지표, 즉 모든 후보 정책의 과제 정확도를 평가하지 않고 층별 열화를 추정하는 대리 지표에 의존한다. 그럼에도 널리 쓰이는 지표는 최신 아키텍처에서 체계적으로 실패한다. 우리는 서로 뚜렷이 다른 네 개의 신경망에 걸친 층별 INT8 양자화에 대한 13개 민감도 지표의 체계적 실증 연구를 제시하고, 그로부터 얻은 정책을 두 ARM64 플랫폼에서 검증한다. 그래디언트 기반 민감도 방법은 8개 모델-하드웨어 구성 중 4개에서 실패하고, 가중치 기반 통계는 2개에서 실패한다. 반면 Jensen-Shannon Divergence는 치명적 실패가 전혀 없으며, 안전하게 양자화할 수 없는 층을 안정적으로 분리한다. 민감도 지표만으로는 정책이 정의되지 않으며, 그 단계에 흔히 쓰이는 고정 임계값은 최신 아키텍처의 고도로 치우친 분포에서 취약하다. 우리는 K-Means 클러스터링으로 이를 해결하여 거의 무손실 정확도와 전체 정밀도 모델 대비 평균 $1.81\times$ 속도 향상을 달성한다. 마지막으로, 민감도와 관계없이 속도 향상이 미미한 층을 양자화에서 제외하는 것이 역효과를 낼 수 있음을 밝힌다. 이는 계산 그래프 단편화를 유발하고 연산자 융합(operator fusion)을 비활성화하기 때문이다. 우리 결과는 GPU 접근이나 그래디언트 계산 없이 이질적 엣지 CPU에 양자화된 비전 모델을 배포하는 실무자와 연구자에게 구체적인 할당 정책을 제공한다.

arXiv:2607.21039v1cs.LG공통 태그 Clustering, Community Detection

Grassmann 다양체 상의 정규화 최적화: 이론, 알고리즘 및 응용

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications

스펙트럴 방법은 커뮤니티 탐지, 클러스터링, 그래프 학습에서 가장 널리 사용되는 기법 중 하나이다. 그러나 그 성능은 근본적인 스펙트럴 부분공간의 정확한 추정에 크게 의존하며, 노이즈, 이상치, 또는 모델 교란이 존재할 경우 상당히 악화될 수 있다. 이 한계를 해결하기 위해, 우리는 rank-$K$ 투영 행렬의 강건한 추정을 위한 정규화 투영 행렬 근사(Regularized Projection Matrix Approximation, RPMA) 프레임워크를 제안한다. RPMA는 정규화 항을 통합하여 고전적인 스펙트럴 투영을 확장하며, 더 강건하고 희소하며 해석 가능한 투영 추정치를 생성한다. 우리는 제안된 모델을 rank-$K$ 투영 행렬의 다양체 상의 최적화 문제로 공식화하고, Grassmann 다양체와의 기하학적 동등성을 활용한다. 이 다양체 특성화를 바탕으로, 1차 및 2차 최적성 조건을 유도하고, 정규화된 선행 고유공간의 국소 안정성을 확립하며, 충분히 작은 정규화 하에서 임계점 경관의 안정성을 특성화한다. 결과적인 비볼록 최적화 문제를 효율적으로 풀기 위해, 역추적 선 탐색(backtracking line search)을 갖춘 Riemann 그래디언트 투영 알고리즘과, 반복적인 고유값 분해를 피하는 보다 효율적인 Cayley--Sherman--Morrison--Woodbury(Cayley--SMW) 그래디언트 방법을 개발한다. 합성 및 실제 데이터셋에 대한 광범위한 실험은 RPMA가 투영 행렬의 복원 정확도를 크게 향상시키며, 노이즈가 있는 환경에서 커뮤니티 탐지 및 클러스터링을 위한 기존 스펙트럴 투영 방법보다 일관되게 우수한 성능을 보임을 입증한다.

arXiv:2607.09441v1math.ST공통 태그 Clustering, Community Detection

다항 시간 내 준최적 노드-프라이빗 커뮤니티 추정

Near-optimal node-private community estimation in polynomial-time

이 논문에서 우리는 Klopp & Zadik (2026)의 미해결 문제를 해결하여, 확률적 블록 모델(stochastic block model)에서의 정확 복원(exact recovery)에 대해 그들의 지수 시간 노드-프라이빗 알고리즘의 성능에 근접하는, 높은 확률을 보장하는 다항 시간 노드-프라이빗 알고리즘을 제시한다. 우리의 결과는 페널티 가능도 함수에 대해 명시적으로 구성된 립시츠 대리 함수(Lipschitz surrogate)와, 다항 시간 내에 지수 메커니즘(exponential mechanism)으로부터 커뮤니티 레이블을 샘플링하는 신중하게 고안된 수용-기각 알고리즘(accept-reject algorithm)을 포함한다. 우리는 제안 알고리즘의 프라이버시, 실행 시간, 유용성을 엄밀하게 분석하며, 커뮤니티 수 K가 노드 수 n에 대해 로그 수준으로 증가하는 경우에도 프라이버시 매개변수 epsilon이 log(n)으로 증가할 때 정확 복원에 대한 미니맥스 수렴률을 달성할 수 있음을 보임으로써, 이 설정에서 프라이버시 비용에 관해 알려진 하한과 일치함을 증명한다.

arXiv:2606.30249v1cs.LG공통 태그 Clustering, Community Detection

이종친화 그래프에서 비지도 커뮤니티 탐지를 위한 곡률 유도 시프 확산

Curvature-Guided Sheaf Diffusion for Unsupervised Community Detection on Heterophilic Graphs

연결된 노드가 서로 다른 클래스에 속하는 경우가 많은 이종친화(heterophilic) 그래프에서의 커뮤니티 탐지는 비지도 방법에 있어 어려운 문제이다. 고전적인 모듈성(modularity) 및 스펙트럼 방법은 특징(feature)에 무관하고, 심층 그래프 클러스터링 방법은 불투명한 대조적(contrastive) 또는 생성적(generative) 메커니즘에 의존한다. 본 논문에서는 각 에지의 이산 Forman--Ricci 곡률을 단일 위상 신호로 활용하여 엔드투엔드 파이프라인의 모든 단계에 전파하는 완전 비지도 커뮤니티 탐지 알고리즘인 Curvature-Guided Sheaf Diffusion(CGSD)을 제안한다. CGSD는 세 가지 구체적인 기여를 한다: (i) 에지 메시지를 $σ(κ_e)$로 게이팅하고 세 가지 레이블 없는 구조적 손실(모듈성, 반붕괴, 곡률 가중 재구성)로 학습되는 곡률 게이팅 시프 확산 인코더; (ii) Ng--Jordan--Weiss 적용 전 임베딩의 $k$-NN 친화도를 $σ(ακ_{e^*})$로 재가중하는 곡률 인식 스펙트럴 클러스터러(CSpec); (iii) 9개의 완전 비지도 기준선(baseline)에 대한 통합 레이블 없는 평가. 다섯 개의 이종친화 벤치마크(Cora, Cornell, Texas, Wisconsin, Chameleon)에서 CGSD는 Wisconsin과 Chameleon에서 1위를 차지하고 나머지 세 개에서도 9개의 비지도 기준선(baseline)과 경쟁력 있는 성능을 보인다. 최강 기준선(baseline) 대비 성능 향상은 인코더가 아닌 클러스터러에서 비롯된다: 동일한 임베딩에서 CSpec은 $K$-Means의 평균 NMI $0.091$을 $0.107$로 개선한다($+15\%$, 대응 $t$-검정 $p=0.008$). 그 메커니즘은 해석 가능하다: 커뮤니티 내부 및 커뮤니티 간 곡률 분포가 시각적으로 뚜렷하게 분리된다. 코드는 https://github.com/woodywff/cgsd에 오픈소스로 공개되어 있다.

토론

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