원문 초록
In this paper, we introduce position graphs, a graph-based reasoning framework based on the formalization of position spaces. This framework utilizes two strict partial orders, representing horizontal and vertical alignment and precedence, to model the relative positions of discrete tokens. Unlike general qualitative spatial calculi, position graphs are constrained by a chain condition and compatibility requirements that focus on rows and columns. We provide a comprehensive theoretical analysis of this representation, beginning with a characterization of graph consistency. Conditions to ensure the consistency of position graphs are established. Furthermore, we investigate the computational complexity of structural pattern discovery, modeled as the induced subgraph isomorphism problem. We demonstrate that this problem remains NP-complete even within the restricted class of position graphs. While initially motivated by document processing, this work focuses on the underlying mathematical properties and algebraic consistency of position-based constraints, providing a formal logical layer that is independent of specific data extraction techniques.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.25719v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
최대 독립 집합을 위한 Dual-GNN 다중 수준 조 정
Dual-GNN Multilevel Coarsening for Maximum Independent Set
최대 독립 집합(maximum independent set, MIS) 문제는 스케줄링, 자원 할당, 네트워크 분석 등에 응용되는 기본적인 NP-hard 조합 최적화(combinatorial optimization) 문제이다. 정확 솔버(exact solver)는 고품질 해 또는 최적성 증명(optimality certificate)을 제공할 수 있으나, 계산 비용은 그래프 크기에 따라 급격히 증가한다. 반면 수작업 휴리스틱(hand-crafted heuristic)은 보장을 희생하는 대신 확장성(scalability)을 개선한다. 학습 기반 방법은 그래프 인스턴스 간 구조적 패턴을 활용하는 대안을 제공하지만, 독립 집합을 직접 예측하면 대규모 그래프에서 전역 조율(global coordination)이 어려워질 수 있다. 우리는 대신 학습을 이용해 다중 수준 그래프 조 정(multilevel graph coarsening)을 안내하고, 최종 의사 결정에는 조합 탐색(combinatorial search)을 유지한다. Dual-GNN 다중 수준 조 정 프레임워크는 Partition GNN으로 후보 수축(contraction)을 점수화하고, Representative GNN으로 각 최종 클러스터에 대해 상위 k개의 지역 독립 집합 상태를 선택한다. 최대 2,000개 정점(vertex)을 갖는 Erdős–Rényi 그래프 실험에서 유리한 품질–실행 시간 트레이드오프(quality–runtime trade-off)를 보여준다. 인증된 최적해가 있는 500정점 인스턴스에서, 본 방법은 평균 독립 집합 크기 19.20을 달성하며 이는 최적값 19.30의 99.5%에 해당한다. 정확 해법의 평균 벽시계 시간(wall-clock time) 643.57초를 3.41초로 줄여 약 189배 속도 향상(speedup)을 얻는다. 1,000 및 2,000 정점의 더 큰 그래프에서는 평가된 모든 방법 중 최고의 평균 해 품질을 달성한다. 또한 가장자리 확률(edge probability) $p=0.35$인 Erdős–Rényi 그래프에서만 학습했음에도, 학습된 조 정 정책은 보지 못한 그래프 밀도와 구조적으로 다른 그래프 계열 모두에 효과적으로 일반화(generalize)된다.
피드백 기반 단어 추론을 위한 그래프 기반 추론: 조토(Jotto) 문제를 위한 확장 가능한 프레임워크
Graph-Based Inference for Feedback-Driven Word Deduction: A Scalable Framework for the Jotto Problem
조토(Jotto) 문제를 기반으로 한 피드백 기반 단어 추론(word deduction) 프레임워크가 제안되며, 문제 공간은 모든 유효한 단어가 노드에 해당하고 에지 가중치가 두 단어 간의 공통 글자 수로 정의되는 가중치 그래프로 표현된다. 마지막으로, 게임플레이는 피드백을 사용하여 그래프의 비호환 공간을 반복적으로 좁혀 나가는 반복적 제약 조건 전파 메커니즘으로 정의되며, 구조화되고 해석 가능한 방식으로 가설 공간의 축소를 용이하게 한다. 문제 공간이 통상적으로 고정된 길이의 이소그램(isogram)에 대해 정의되던 기존 접근법과 달리, 제안된 프레임워크는 가변 길이 단어(3글자에서 8글자 사이)로 일반화되고 글자가 반복되는 경우로 자연스럽게 확장되어, 현실적인 조토 문제 사례들을 최초로 단일화된 프레임워크 내에서 다룰 수 있게 한다. 또한 제안된 프레임워크의 적용 가능성과 솔버 동역학은 각각 대화형 구현과 정성적 사례 연구를 통해 논의된다. 약 3,000건의 시뮬레이션 게임플레이 시나리오에 대한 대규모 자동화 테스트를 통해 단어 길이가 길어질수록 기대 반복 횟수가 감소한다는 새로운 수렴 행동을 규명한다. 통계적 검정을 통해 로그 관계를 검증하는 강력한 상관관계를 확인하며, 이는 회귀 모델링과 적합도 검정을 통해서도 검증된다. 초기 문제 정의 외에도, 본 정식화는 해석 가능성을 갖춘 피드백 기반 추론(inference)을 위한 유효한 패러다임으로서의 그래프 가지치기(pruning)와, 이것이 기호 추론 및 대화형 지능형 시스템과 맺는 연관성을 제시한다.
팩터 그래프를 통한 서브샘플링을 위한 진화 인식 MSA 추론
Evolution-Aware MSA Reasoning for Subsampling via Factor Graphs
다중 서열 정렬(MSA)은 단백질 언어 모델에 명시적인 진화적 맥락을 제공하지만, 깊이가 크기 때문에 제한된 토큰 예산 하에서는 서브샘플링이 불가피하다. 무작위 선택, 동일성(identity) 기반 필터링, 다양성 중심 샘플링 등 기존 전략은 효과적인 휴리스틱이지만, 부분집합에 보존되는 진화적 신호에 대한 제어가 제한적이다. 본 연구에서는 MSA 서브샘플링을 명시적 최적화 문제로 재구성하며, 쿼리 동일성과 다양성을 포함한 핵심 진화 지표를 제어 가능한 목표로 취급한다. 이 관점을 바탕으로 친화력 전파(Affinity Propagation) 기반 팩터 그래프 접근법인 AP-REASONER를 제안한다. 진화 인식 단항(unary) 팩터, exemplar 일관성 팩터, 두 개의 제어 노브를 갖춘 AP-REASONER는 메시지 전달(message passing)을 통한 팩터 그래프 추론으로 고정 예산 MSA 부분집합을 추론한다. 장거리 접촉 예측 및 conformational 앙상블 예측 실험에서 AP-REASONER는 구조 민감 하위 작업에서 기준선 서브샘플러보다 우수한 성능을 보이며, 대안적 단백질 conformation의 제어 가능한 복원을 가능하게 한다. 이러한 결과는 MSA 서브샘플링을 제어 가능한 최적화 문제로 모델링할 때의 가치를 부각하며, 팩터 그래프 추론이 휴리스틱 선택에 대한 효과적인 대안임을 보여준다.
Active Directory 보안 강화를 위한 실용적 그래프 최적화 및 AI 기반 모델
Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening
Microsoft의 Active Directory(AD)는 IT 관리자가 Windows 도메인 네트워크 내에서 보안 권한을 관리하고 접근을 제어할 수 있게 하는 디렉터리 서비스이다. 많은 조직의 핵심 관리 시스템인 AD는 적대자의 주요 공격 대상이 되었다. 공격 그래프를 강화하는 많은 해결책이 존재하지만, 이러한 노력은 AD 공격 그래프에 특화된 여러 핵심적인 실용적 과제를 해결하는 데 미흡하다. 첫째, 기존 모델은 그래프가 정적이라고 가정하는 경우가 많지만, 실제 AD 환경은 매우 동적이다. 둘째, 대부분의 제안된 해결책은 취약점을 제거하는(엣지 제거) 방어적 조치에 한정되어 있으며, 보다 능동적인 방어 메커니즘은 대체로 연구되지 않았다. 셋째, 모든 조치가 실행 가능한 것은 아니므로, 실용적인 end-to-end 모델은 우선순위 결정 과정에 시스템 관리자의 피드백을 반드시 포함해야 한다. 본 논문은 이러한 한계를 해결하기 위해 게임 이론적 및 최적화 기반 의사결정 모델들을 연구하고 제안하는 것을 목표로 한다. 첫째, 최단 경로 수와 Domain Admin에 도달 가능한 노드 수를 최소화하는 원칙에 기반한 허니팟/디코이 배치 모델을 제안한다. 둘째, 이 모델을 기반으로 AD 그래프의 동적/시간적 특성을 고려하는 방어 전략을 도입하며, 목표는 최악의 경우 사고 대응 시간을 최대화하는 디코이 배치 위치를 찾는 것이다. 셋째, 각 고위험 공격 경로에 대해 IT 관리자에게 조치 판단을 요청하는 적응형 우선순위 모델을 도입한다. 마지막으로, 유사한 위험 특성을 가진 엣지에 시스템 관리자의 결정을 일반화하는 일반적인 적응형 엣지 제거 정책을 찾음으로써 시스템 관리자의 승인 부담을 최소화하는 end-to-end 적응형 우선순위 모델을 도입한다. 우리는 제안한 모든 모델의 기반이 되는 문제들이 계산적으로 난해함을 보인다.
제약 다중 소스 추론을 통한 배전 시스템의 확장 가능한 토폴로지 추론
Enabling Scalable Topology Inference in Distribution Systems via Constrained Multi-Source Inference
정확한 배전 시스템 토폴로지는 정전 위치 파악, 전압 분석, 배전망 운영에 필수적이지만, 이질적이고 불완전한 전력 유틸리티 데이터로 인해 실무에서 신뢰할 수 있는 연결 기록을 유지하는 것은 여전히 어렵다. 기존 토폴로지 식별 방법은 주로 전기적 유사성 또는 공간 기록만에 의존하는 경우가 많으며, 이는 밀집된 피더와 불일치하는 메타데이터 조건에서 신뢰성을 잃는다. 본 논문은 배전 토폴로지 식별을 제약 추론 문제로 공식화하여, 공간적 실현 가능성과 물리적 운영 제약을 강제하면서 이질적 증거를 사용해 유틸리티가 제공한 기본 토폴로지를 정제한다. 처음부터 연결성을 재구성하는 대신, 제안된 프레임워크는 불일치하는 할당을 탐지하고, 확장성을 보장하기 위해 제약된 이웃 내에서 국소적 재연결을 수행하며, 물리적 실현 가능성을 반복적으로 강제하여 운영상 일관된 토폴로지 추정치를 생성한다. 또한, 반증 기반 신뢰도 지표는 대안적 실현 가능 할당 대비 각 추론된 연결이 얼마나 강하게 뒷받침되는지 평가하여, 유틸리티가 시스템 전체 관측 가능성을 유지하면서 검증 노력의 우선순위를 정할 수 있게 한다. 이 프레임워크는 미국 대형 유틸리티와 협력하여 $8{,}000$개 이상의 AMI(Advanced Metering Infrastructure) 미터로 구성된 세 개 피더의 운영 데이터를 사용해 검증되었다. 결과는 전역 추론 접근법에 비해 계산 노력을 크게 줄이면서 $95\%$ 이상의 토폴로지 재구성 정확도를 보여준다. 연구는 또한 상관관계 기반 방법만으로는 밀집된 도시 피더에서 모호한 할당을 초래하는 반면, 전기 측정과 공간·운영 제약을 결합하면 현실적인 배포 조건에서 강건하고 확장 가능한 토폴로지 복구가 가능함을 보여준다.
엣지 특징 Graph Isomorphism Network를 이용한 NR-V2X 차량 통신의 저지연 릴레이 선택
Low-Latency Relay Selection in NR-V2X Vehicular Communications via Graph Isomorphism Networks with Edge Features
밀집된 도시 환경에서 C-V2X 네트워크의 핵심 요구사항은 신뢰할 수 있는 저지연 상향링크 연결성이며, 이러한 환경에서는 빠른 채널 변화와 차폐로 인해 차량-인프라 직접 링크가 자주 저하된다. 다중 홉 릴레이를 통해 커버리지를 복구할 수 있지만, 무선, 용량, 라우팅 제약 하에서의 릴레이 링크 활성화는 NP-hard 최적화 문제가 되며, 일반적으로 혼합 정수 선형 계획(MILP)으로 풀지만 그래프 크기에 따라 실행 시간이 급격히 증가한다. 본 논문은 실시간 릴레이 선택을 위한 엣지 인식 Learning-to-Optimise 프레임워크를 제안한다. 각 V2X 스냅샷은 방향 그래프로 모델링되며, 노드 특징은 차량 상태와 트래픽 수요를 인코딩하고, 엣지 특징은 무선 링크 용량을 포착한다. 오프라인 MILP 오라클이 최적 릴레이 구성을 생성하여 엣지 특징 Graph Isomorphism Network(GINE)을 지도 학습하고, 단일 순전파로 엣지 수준 릴레이 활성화를 가능하게 하며, 추론 지연을 엄격하게 제한한다. 학습과 정확한 최적화를 연결하기 위해, GINE 예측이 MILP 탐색 공간을 가지치기하는 하이브리드 GINE-Pruned MILP(GP-MILP) 전략도 제안한다. OSM-SUMO-GEMV$^2$ 파이프라인으로 생성된 대규모 데이터셋 실험에서 GINE은 링크 수준에서 MILP 결정과 밀접하게 일치(정확도 0.9589, 검증 F1-score 0.9544)하며, 1-hop MILP 기준선 대비 일관된 end-to-end 연결성 향상을 보여준다(RSU 4개일 때 최대 9.2%, RSU 2개일 때 12%). 추론 지연은 엄격하게 제한되며, 평가된 모든 인스턴스가 5~ms 이내에 완료된다. 또한 GP-MILP는 MILP 동등 솔루션(동일 목적 함수값)을 보존하면서 그래프 인스턴스의 98% 이상에서 30~ms 미만의 솔버 실행 시간을 달성하여, MILP 수준 최적화를 엄격한 NR-V2X 지연 예산과 호환되게 한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.