# CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment

### 저자

Songyang Chen, Yu Liu, Lei Zou, Zexuan Wang, Youfang Lin

### 개요

본 논문은 비지도 그래프 정렬 문제를 다룬다. 기존 연구는 노드 임베딩 기반 유사도 측정 또는 Gromov-Wasserstein 학습을 통한 최적 수송 문제 해결 방식으로 나뉘지만, 모델의 표현력과 예측 정확도 간의 관계는 미흡하게 연구되었다.  본 논문은 모델의 표현력을 두 가지 측면(정렬된/정렬되지 않은 노드 쌍 구분 능력, 일대일 매칭 및 상호 정렬 보장 능력)에서 분석하고, 이를 바탕으로 더 강력한 표현력을 가진 하이브리드 접근 방식인 CombAlign을 제안한다. CombAlign은 OT 기반 학습을 위한 교차 차원 특징 상호작용, Weisfeiler-Lehman 검정에서 영감을 받은 임베딩 기반 방법, 그리고 임베딩 기반 모듈에서 얻은 비균일 주변 분포를 OT의 사전 정보로 활용한다.  또한, 앙상블 학습 전략을 사용하여 OT 및 임베딩 기반 예측을 결합하고 최대 가중치 매칭 문제로 축소하는 전통적인 알고리즘 기반 개선 방법을 제안하여 일대일 매칭 및 상호 정렬 속성을 보장하고 예측 정확도를 향상시킨다. 실험 결과, 최첨단 기법에 비해 14.5% 향상된 정렬 정확도를 보였다.

### 시사점, 한계점

- **시사점:**

    - 그래프 정렬 문제에서 모델의 표현력에 대한 이론적 분석과 실험적 검증을 통해 모델 성능 향상에 대한 새로운 방향을 제시하였다.

    - OT 기반 학습과 임베딩 기반 방법을 결합한 하이브리드 접근 방식인 CombAlign을 제안하여 기존 방법보다 우수한 성능을 달성하였다.

    - 비균일 주변 분포를 OT의 사전 정보로 활용하는 기법은 향후 다른 그래프 관련 문제에도 적용될 수 있다.

    - 전통적인 알고리즘 기반의 개선 방법을 통해 일대일 매칭 및 상호 정렬 속성을 보장하고 정확도를 향상시켰다.

- **한계점:**

    - 제안된 CombAlign의 복잡도가 기존 방법보다 높을 수 있다.

    - 대규모 그래프에 대한 확장성에 대한 추가적인 연구가 필요하다.

    - 특정 유형의 그래프에 대해서는 성능이 저하될 가능성이 있다.

    - 이론적 분석이 특정 가정에 기반하여 이루어졌으므로, 다양한 조건에 대한 추가적인 분석이 필요하다.

[PDF 보기](https://arxiv.org/pdf/2406.13216)

For the site tree, see the [root Markdown](https://slashpage.com/haebom.md).