구조적 보존과 그래프 신경망의 논리적 표현력
Structural Preservation and the Logical Expressiveness of Graph Neural Networks
한국어 초록
그래프 신경망(GNN)과 논리 형식 체계(logical formalisms) 사이의 연결은 집계(aggregation), 결합(combination), 활성화 함수(activation functions) 유형과 같은 아키텍처 선택을 고정함으로써 확립되어 왔다. 이러한 선택은 논리 공식(logical formulae)을 동등한 GNN으로, 그리고 역으로 GNN을 동등한 공식으로 번역할 수 있음을 보임으로써, 논리 형식 체계와 긴밀한 대응을 얻을 수 있는 GNN의 제한된 클래스를 정의한다. 본 논문에서는 임베딩(embedding, 확장), 단사 준동형사상(injective homomorphism), 준동형사상(homomorphism)과 같은 구조적 성질(structural properties) 하에서 보존되는 GNN 분류기 클래스의 논리적 표현력을 확립함으로써 의미론적(semantic) 관점을 취한다. 우리는 각각의 이러한 성질에 대해 GNN 클래스를 특성화(characterise)하는 등급 모달 논리(graded modal logic)의 단편(fragment)이 존재함을 보인다. 특히, 임베딩, 단사 준동형사상, 준동형사상 하에서의 보존은 각각 존재 등급 모달 논리(existential graded modal logic), 그 존재-긍정(existential-positive) 단편, 존재-긍정 모달 논리(existential-positive modal logic)에 대응한다. 이 결과들은 특정 아키텍처 선택과 무관하게 광범위한 GNN 클래스의 표현력을 특성화하지만, 우리는 또한 이러한 클래스 각각이 동일한 표현력을 갖는 GNN 아키텍처를 허용함을 보인다. 기술적으로, 우리 접근법은 유계 높이(bounded height) 트리에 대한 새로운 준전순(well-quasi-order) 결과를 사용하여, 언래블링 불변(unravelling-invariant) 클래스의 유한 표현(finite representations)을 산출한다.
원문 초록
Bridges between graph neural networks (GNNs) and logical formalisms have been established by fixing architectural choices, such as the types of aggregation, combination, and activation functions. These choices define restricted classes of GNNs for which tight correspondences with logical formalisms can be obtained, by showing that logical formulae can be translated into equivalent GNNs and, conversely, that GNNs can be translated into equivalent formulae. In this paper we take a semantic perspective by establishing the logical expressiveness of classes of GNN classifiers that are preserved under structural properties: embeddings (extensions), injective homomorphisms, and homomorphisms. We show that, for each such property, there exists a fragment of graded modal logic characterising the class of GNNs. In particular, preservation under embeddings, injective homomorphisms, and homomorphisms corresponds to existential graded modal logic, its existential-positive fragment, and existential-positive modal logic, respectively. These results characterise the expressiveness of broad classes of GNNs independently of specific architectural choices, but we also show that each of these classes admits a GNN architecture of the same expressiveness. Technically, our approach uses a new well-quasi-order result for trees of bounded height, yielding finite representations of unravelling-invariant classes.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.17882v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
잠재 구조 학습: 그래프 데이터 증강을 위한 특징 중심 접근법
Learning the Latent Structure: A Feature-Centric Approach to Graph Data Augmentation
그래프 구조 데이터는 복잡한 관계를 모델링하는 데 핵심적인 역할을 합니다. 그러나 실제 그래프는 데이터 수집 및 관측의 제약으로 인해 불완전한 경우가 많으며, 이는 현대 그래프 학습 파이프라인의 효과를 심각하게 제한합니다. 기존 그래프 데이터 증강(Graph Data Augmentation, GDA) 방식들은 다운스트림 성능 향상을 위해 그래프 구조를 정제하고자 시도하지만, 대개 레이블 의존적이고 계산 비용이 많이 들며 본질적으로 트랜스덕티브(transductive)하여 실제 환경에서의 적용 가능성이 제한됩니다. 본 연구에서는 명시적인 구조 모델링을 우회하고 임베딩(embedding) 공간에서 직접 작동하는 새로운 특징(feature) 중심 그래프 데이터 증강 프레임워크를 제안합니다. 자기지도 역마스킹(inverse masking) 과정을 통해, 본 방법은 관측된 그래프와 완전한 그래프 사이의 잠재적 연결을 포착하여 정제된 노드(node) 표현을 통해 관측되지 않은 구조적 신호를 복원할 수 있도록 합니다. 노이즈가 많고 희소한 지도 신호 하에서의 강건성을 향상하기 위해, 효과적인 학습(training)과 일반화를 위한 메시지 정규화기(message regularizer) 및 부트스트랩 전략을 도입합니다. 여러 도메인에 걸친 10개의 그래프 데이터셋에서 평가한 결과, 우리의 접근 방식인 SelfAug는 인덕티브(inductive) 및 콜드 스타트(cold-start) 설정 모두에서 정확도와 효율성 측면에서 최첨단(SOTA) 방법들을 일관되게 능가하며, 실제 그래프 학습 시나리오를 위한 확장 가능하고 일반화 가능한 솔루션으로서의 잠재력을 입증합니다.
학습 기반 재봉 패턴 솔기 대응 재구성
Learning-based Seam Correspondence Reconstruction in Sewing Patterns
디지털 재봉 패턴은 일반적으로 명시적인 봉합(stitch) 주석 없이 분리된 2D 패널로 구성되어, 후속 3D 모델링이 노동 집약적인 전문가 지정에 의존하게 만든다. 본 논문에서는 2D 패널 기하 정보만으로 거친 수준의 패널 연결성과 세밀한 솔기 대응(seam correspondence)이라는 2단계 봉합(stitching) 정보를 재구성하는 그래프 기반 학습 프레임워크를 제안한다. 거친 수준에서는 해부학적 신체 영역과 연관된 패널 의미를 예측하여 패널 연결성을 추론하고, 신체 구조 및 의류 설계 관례와의 일관성을 강제한다. 재구성된 패널 그래프를 바탕으로, 그래프 메시지 전달(graph message passing)을 통해 국소 솔기 기하와 전역 의류 컨텍스트를 공동으로 인코딩하는 잠재 엣지 표현을 학습하여 패널 쌍 간의 세밀한 솔기 대응을 추론한다. 결과적으로 얻은 엣지 임베딩(embedding)은 이후 상세한 솔기 대응으로 디코딩된다. 본 방법은 다대일 대응, 패널 내부 솔기, 곡선 솔기를 포함한 복잡한 재봉 패턴 토폴로지를 지원한다. 실험 결과, 높은 봉합 정확도와 다양한 의류 스타일에 걸친 강한 일반화 성능을 보여준다.
동적 그래프의 노드 친화도를 이용한 기관 주식 보유 예측
Institutional Equity Holdings Prediction Using Node Affinities of Dynamic Graphs
SEC Form 13F 제출 자료에 공개된 기관 주식 보유는 대형 투자 운용사의 포트폴리오 결정에 대한 풍부한 시계열 기록을 제공한다. 그러나 공시 지연, 보고 노이즈, 기관 행동의 강한 지속성(persistence) 때문에 미래 배분을 예측하고 미래 수요를 모델링하는 것은 여전히 어렵다. 우리는 시간적 그래프 머신러닝을 사용하여 이러한 작업을 위한 최초의 벤치마크를 도입하며, 전처리된 제출 자료에서 추출한 운용사와 증권의 이산 시간(temporal) 이분 그래프(bipartite graph)에서 보유 예측을 노드 친화도(node affinity) 예측, 즉 포트폴리오 비중 예측으로 정식화한다. 99명의 운용사와 S&P 500 지수(2013--2025년 48분기에 걸친 503개 증권, 209,351개의 시간적 엣지)로 구성된 샘플링된 데이터셋에서, Virtual State를 사용하는 Node Affinity 예측 모델(NAVIS)은 특징(features) 포함 시 최첨단 테스트 Normalized Discounted Cumulative Gain(NDCG) 0.9127(미포함 시 0.9121)을 달성하여, 모든 동적 그래프 표현 학습 경쟁 모델을 상당한 마진으로, 모든 휴리스틱 방법을 능가한다. 주목할 만하게, 단순한 지수 이동 평균(Exponential Moving Average) 기준선이 0.8882를 달성하여 NAVIS를 제외한 모든 동적 그래프 모델과 Persistent Forecast(0.8891)를 제외한 모든 휴리스틱을 능가하며, 이는 기관 포트폴리오의 강한 평활성(smoothness)과 지속성을 부각한다. 도메인 특화 노드 특징은 극히 미미한 향상(<1.2%)만 제공하며, 이는 13F 소유권 그래프의 시간적 및 구조적 신호가 이미 예측 가능한 정보의 대부분을 포착하고 있음을 시사한다. 실제 13F 데이터에 대해 특징 유무 모두에서 노드 친화도 예측 설정 하에 Temporal Graph Benchmark(TGB) 모델 무리를 벤치마킹함으로써, 본 연구는 보유 예측 및 포트폴리오 배분에서 시간적 그래프 머신러닝을 위한 재현 가능한 기반을 제공한다.
지식 그래프와 그래프 신경망의 만남: 종합 서베이
Knowledge Graphs Meet Graph Neural Networks: A Comprehensive Survey
그래프 신경망(GNN)은 그래프 구조 데이터를 모델링하는 고유한 능력으로 인해 지식 그래프(KG) 분야에서 강력한 패러다임으로 부상하였다. 그러나 지식 그래프 기술 파이프라인 전반에 걸친 GNN 기반 방법론에 대한 체계적인 리뷰는 아직 부족한 실정이다. 이러한 공백을 해소하기 위해, 본 논문에서는 GNN 기반 지식 그래프 기술에 대한 새로운 2단계 분류 체계를 제안한다: KG 기술 파이프라인 관점과 GNN 기반 관점이 그것이다. 구체적으로, 지식 그래프 기술 파이프라인은 지식 그래프 구축, 지식 그래프 임베딩, 지식 추론, 지식 그래프 응용을 포함한다. 한편, GNN 기반 관점은 GCN, GAT, HGNN 등의 GNN 모델을 활용하여 지식 그래프 기술을 새롭게 범주화한다. 이어서 지식 그래프 생애주기 내 다양한 태스크의 특성에 기반하여 GNN 기술의 이점을 분석한다. 나아가 제안된 분류 체계에 따라 지식 그래프를 위한 다양한 GNN 기반 모델을 상세히 검토하고, 각각의 강점과 한계를 정리한다. 마지막으로, 아직 해결되지 않은 과제들을 논의하고 향후 연구를 위한 유망한 방향을 제시한다.
부호 그래프 사전학습 및 프롬프트 학습
Signed Graph Pre-Training and Prompt Learning
부호 그래프(signed graph)는 엣지가 양수이거나 음수일 수 있으며 방향성을 가질 수도 있는 신뢰-불신 네트워크, 금융 상관관계 시스템, 생물학적 상호작용 그래프 및 기타 여러 도메인에서 발생합니다. 부호 그래프 신경망이 특정 태스크에 특화된 학습(training)을 향상시켰지만, 부호 그래프에서의 그래프 전이학습(transfer learning)은 여전히 미진한 상태입니다. 본 논문에서는 부호 그래프를 위한 선구적인 위상학 기반 그래프 사전학습(pre-training) 및 프롬프트(prompt) 학습 프레임워크인 TopoSIGN을 소개합니다. TopoSIGN은 자기 부호 라플라시안(magnetic signed Laplacian)을 기반으로 구축된 구조적 인코더와 Dowker 복합체 지속성 이미지(Dowker-complex persistence images)를 통해 부호 위상을 요약하는 새로운 지속성 호몰로지(persistent-homology) 브랜치를 결합합니다. 융합된 임베딩(embedding)은 이후 프롬프트 학습 함수로 전달됩니다. 합성 및 실제 데이터셋(dataset)에 대한 실험 결과는 부호 그래프에서 유용한 구조적 정보를 추출하는 TopoSIGN의 효능뿐만 아니라, 제안된 일반 프레임워크의 적응성과 유연성을 입증합니다.
VQIL: 그래프 상의 섭동 반응 순위화를 위한 가시적 양자 간섭 학습
VQIL: Visible Quantum Interference Learning for Perturbation Response Ranking on Graphs
국소적 섭동(perturbation)이 네트워크에 미치는 영향을 학습하는 것은 시스템의 반응을 유발하거나 흡수하는 구성 요소를 식별하는 데 중요합니다. 본 연구에서는 이를 시드 조건부 반응 순위화(seed-conditioned response ranking) 문제로 정의합니다. 즉, 하나의 시드 노드(node)에서 섭동이 발생했을 때 다른 모든 노드를 반응 강도에 따라 순위화하는 것입니다. 이는 모델(model)에 상호작용 토폴로지만 주어지고 섭동이 전파되는 방식을 지배하는 메커니즘을 데이터로부터 학습해야 할 때 특히 어렵습니다. 본 논문에서는 시드 조건부 순위화를 위한 학습 가능한 세게디 양자 워크(Szegedy quantum walk)인 VQIL(Visible Quantum Interference Learning)을 제안합니다. 워크 연산자가 학습(training) 전반에 걸쳐 유니터리(unitary) 상태를 유지하는 동안, 에지 가중치, 링크 위상, 노드별 위상 회전이 역전파(backpropagation)를 통해 엔드투엔드로 최적화됩니다. 노드 점수는 양자 워크 진폭의 기하학적 감쇠 코히런트 합(coherent sum)에서 얻어지며, 이를 통해 최종 제곱 노름(squared-norm) 판독 전에 양자 간섭이 가능해집니다. 학습된 각 매개변수(parameter)는 명명된 에지 또는 노드에 연결되어 있으므로, 학습된 모델은 전파 메커니즘에서 개별 그래프 구성 요소의 역할에 대해 직접 검사 가능한 가설을 제공합니다. 전기적 매개변수를 모델에 제공하지 않은 6개 송전망에 대한 교류 조류(AC power-flow) 섭동 실험에서, VQIL은 스피어만 순위 상관계수를 학습되지 않은 워크의 0.147에서 0.831로 향상시켰으며 동일하게 학습된 무작위 워크 모델의 성능을 능가했습니다. Perturb-seq 지도 신호가 있는 5개 단백질-단백질 상호작용 네트워크에 대한 유전자 섭동 실험에서 VQIL은 순위 상관계수를 0.171에서 0.620으로 향상시켜 가장 강력한 고전적 및 신경망 기반 학습 베이스라인들을 능가했습니다. 이러한 결과는 학습 가능한 양자 워크 간섭이 그래프 상에서 시드 조건부 반응 순위를 학습하기 위한 확장 가능하고 해석 가능한 귀납적 바이어스(inductive bias)를 제공함을 보여줍니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.