arXiv:2312.14847

Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant

Sam Alexander Martino, João Morado, Chenghao Li, Zhenghao Lu, Edina Rosta

제출 2023-12-22

원문 초록

Traditional clustering algorithms often struggle to capture the complex relationships within graphs and generalise to arbitrary clustering criteria. The emergence of graph neural networks (GNNs) as a powerful framework for learning representations of graph data provides new approaches to solving the problem. Previous work has shown GNNs to be capable of proposing partitionings using a variety of criteria, however, these approaches have not yet been extended to work on Markov chains or kinetic networks. These arise frequently in the study of molecular systems and are of particular interest to the biochemical modelling community. In this work, we propose several GNN-based architectures to tackle the graph partitioning problem for Markov Chains described as kinetic networks. This approach aims to minimize how much a proposed partitioning changes the Kemeny constant. We propose using an encoder-decoder architecture and show how simple GraphSAGE-based GNNs with linear layers can outperform much larger and more expressive attention-based models in this context. As a proof of concept, we first demonstrate the method's ability to cluster randomly connected graphs. We also use a linear chain architecture corresponding to a 1D free energy profile as our kinetic network. Subsequently, we demonstrate the effectiveness of our method through experiments on a data set derived from molecular dynamics. We compare the performance of our method to other partitioning techniques such as PCCA+. We explore the importance of feature and hyperparameter selection and propose a general strategy for large-scale parallel training of GNNs for discovering optimal graph partitionings.

함께 살펴볼 논문

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

arXiv:2607.13218v1cs.DS공통 태그 Clustering, graph partitioning

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

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)$-근사를 얻는다.

arXiv:2607.01539v3cs.NE공통 태그 Clustering

MMAO-Cls: 특징 선택과 분류기 튜닝을 동시에 수행하는 대사 다중 에이전트 최적화

MMAO-Cls: Metabolic Multi-Agent Optimization for Joint Feature Selection and Classifier Tuning

본 논문은 대사 다중 에이전트 최적화기(MMAO)가 분류 모델 선택을 위한 신뢰할 만한 외부 루프 최적화기로 기능할 수 있는지를 연구한다. 각 에이전트가 이진 특징 마스크와 분류기 하이퍼파라미터를 함께 인코딩하고, 개별 에너지, 공동 예산, 역할 변동, 생애주기 교체가 래퍼 학습의 정확도-복잡도 트레이드오프에 대응되는 혼합 공간 구현인 MMAO-Cls를 제안한다. 구현은 특징 정보 사전분포로부터 특징 예산 적응을 도출하고, 검증 보상을 부분집합의 간결성과 학습-검증 과적합 격차로 함께 정규화하여 강화되었다. 각각 3개의 시드로 7개의 표준 정형 데이터 벤치마크에서 MMAO-Cls를 평가하고, RandomSearch, GA-lite, PSO-lite, 내생적 비공유 제거 변형과 비교한다. 종합 검증 목적함수에서 MMAO-Cls는 GA-lite($0.9446$)에 이어 2위($0.9433$)이다. 보류된 테스트 성능에서는 평균 점수 $0.8882$를 달성하여 RandomSearch($0.8808$)와 GA-lite($0.8857$)를 능가하고, PSO-lite($0.8874$) 및 비공유 제거 변형($0.8900$)에는 근접하며, 비교된 모든 방법 중 보류 데이터 기준 평균 특징 부분집합이 가장 간결하다(특징 비율 $0.4881$). 쌍체 검정 결과 이러한 차이는 아직 통계적으로 유의하지 않다. 결과는 MMAO가 분류와 간결한 혼합 공간 탐색에 적용 가능함을 뒷받침하지만, 공동 공유가 보류 데이터 성능에 기여하는 정도는 해결되지 않은 채 남아 있다.

arXiv:2607.05420v2cs.DL공통 태그 Clustering

AI가 분류할 때: 공공행정이란 무엇인가?

When AI Classifies: What Counts as Public Administration?

본 연구는 학술 표현의 대안적 체계들이 행정학(PA)과 인공지능 관련 행정학(AI-in-PA) 학술 연구를 어떻게 식별하고 특징짓는지를 고찰한다. 핵심 질문은 어떤 체계가 행정학에 대한 확정적 분류를 제공하는가가 아니라, 학술 분류의 대안적 체계들이 행정학의 지적 경계를 식별하고 표현하는 방식에서 어떻게 다른가이다. 본 연구는 Web of Science와 OpenAlex에 대한 탐색적·비교 분석을 통해 저자 정의 방식, 인용 기반 방식, AI 지원 방식의 표현에 기초한 다섯 가지 접근법을 비교한다. 분석 결과는 말뭉치 규모, 출판 유형, DOI 이용 가능성, 출판 매체, 시간적 양상, 주제 구조에서 상당한 차이와 제한적인 중복이 있음을 보여 준다. 대안적 접근법들은 동일한 문헌의 더 크거나 더 작은 부분집합을 식별하는 데 그치지 않고 실질적으로 서로 다른 학술 집합을 식별하기 때문에 서로 구별되는 표현을 만들어 내는 경향이 있다. 연구 결과는 알고리즘에 의한 지식 조직화가 학제 간 학술 연구가 분류되고 연결되고 이해되는 방식에, 그리고 인식론적으로는 그 가시성, 구조, 지적 정체성이 표현되는 방식에 영향을 미침을 시사한다. AI 기반 학술 분류는 중립적이지 않고 해석적이며 잠재적으로 자기강화적이어서 학문 분야 경계의 진화와 적응을 제약할 수 있다. 따라서 인간 전문가의 판단은 여전히 필수적이며, AI 지원 학술 분류에 의해 대체되기보다는 보완된다.

arXiv:2607.21426v2cs.LG공통 태그 Clustering

건설적·협력적 멀티태스킹을 위한 의미 인식 태스크 클러스터링

Semantic-Aware Task Clustering for Constructive and Cooperative Multi-Tasking

협력적 멀티태스크 의미 통신(cooperative multi-task semantic communication, CMT-SemCom)은 공유 표현을 활용하여 태스크 실행 성능을 향상시킨다. 그러나 [1]에서 보인 바와 같이, 협력적 멀티태스킹은 태스크 간 의미적 관계에 따라 건설적일 수도 있고 파괴적일 수도 있다. 건설적 협력을 보장하기 위해, 우리는 CMT-SemCom을 위한 의미 인식 태스크 클러스터링 방법을 제안한다. 짧은 초기 학습 단계 이후 의미적으로 정렬된 태스크가 한 번 클러스터링되고, 이후 발견된 그룹 내에서만 엔드투엔드(end-to-end, E2E) 공동 학습이 수행되는 순차적 다단계 최적화 문제를 수식화했다. 구체적으로, 이 문제는 두 단계로 분해된다: (i) 계층적 밀도 기반 공간 클러스터링(hierarchical density-based spatial clustering)을 활용한 의미 클러스터링 문제, (ii) 클러스터 내 E2E CMT-SemCom 학습 문제. 시뮬레이션 결과는 제안된 프레임워크가 파괴적 협력과 부정적 전이(negative transfer)를 효과적으로 완화하며, 클러스터링되지 않은 멀티태스킹 및 개별 학습 기준선 대비 정확도 향상을 달성함을 보여준다.

토론

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