Source-linked AI summary
Optimal Transport for structured data with application on graphs
Titouan Vayer, Laetitia Chapel, Rémi Flamary, Romain Tavenard, Nicolas Courty
TL;DR
표준 optimal transport는 feature를 비교하지만 구조 정보를 활용하지 않기 때문에 structured object 사이의 거리를 계산하기 어렵다. 이 논문은 feature와 구조를 함께 비교하는 Fused Gromov-Wasserstein distance를 도입하고, 6개 vector-attributed dataset 중 4개에서 최상의 결과를 포함해 graph classification에서 뛰어난 성능을 보고한다.
문제
표준 optimal transport는 structural information을 활용하지 않고 feature representation만 비교하기 때문에 structured object 사이의 거리 계산은 간단하지 않다.
방법
Fused Gromov-Wasserstein distance는 feature와 구조 정보를 함께 운반하고, 두 정보의 기여도를 조절하면서 node 수가 서로 다른 graph도 지원한다.
결과
FGW는 6개 vector-attributed graph dataset 중 4개에서 최상의 성능을 보이고, discrete labeled graph에서는 경쟁 방법을 능가하며, non-attributed social graph에서는 GW가 graph kernel보다 우수하다.
핵심 시사점 및 한계
FGW는 graph analysis를 위한 metric framework를 제공하며 classification과 barycentric graph clustering을 지원한다.
핵심 시사점 및 한계
이 접근법은 shortest-path structural distance와 feature distance를 사용하며, 매우 큰 graph로 확장하기 위해서는 scalability to very large graphs를 고려한 optimization complexity 감소가 여전히 필요하다.
Abstract
from arXiv · showhide
This work considers the problem of computing distances between structured objects such as undirected graphs, seen as probability distributions in a specific metric space. We consider a new transportation distance (i.e. that minimizes a total cost of transporting probability masses) that unveils the geometric nature of the structured objects space. Unlike Wasserstein or Gromov-Wasserstein metrics that focus solely and respectively on features (by considering a metric in the feature space) or structure (by seeing structure as a metric space), our new distance exploits jointly both information, and is consequently called Fused Gromov-Wasserstein (FGW). After discussing its properties and computational aspects, we show results on a graph classification task, where our method outperforms both graph kernels and deep graph convolutional networks. Exploiting further on the metric properties of FGW, interesting geometric objects such as Fréchet means or barycenters of graphs are illustrated and discussed in a clustering context.
1. 서론
이 논문은 그래프를 확률분포로 표현하여 특징 정보와 구조 정보를 함께 포착하는 구조화 데이터용 수송 거리를 제안한다. 이 프레임워크는 두 정보 사이의 조정 가능한 절충을 통해 서로 다른 특징 공간과 구조 공간에 걸친 비교를 지원한다.
- 동기: 구조화 데이터는 특징 정보와 구조 정보를 결합하며, 그래프, 시계열, 트리, 이미지 등을 포괄한다.그래프는 관계로 연결된 속성 노드로 기술된다.
- 관련 연구: Weisfeiler-Lehman kernel 을 포함한 기존 kernel은 특징과 구조적 유사성을 결합하는 문제를 다룬다.
- 기여: 제안하는 프레임워크는 구조화 데이터를 확률 측도로 표현하고, 특징 정보와 구조 정보를 모두 최적 수송 문제에 통합한다.비방향성 labeled graph를 포함한 일반적인 구조화 machine-learning 데이터를 대상으로 한다.
- 기존 수송 거리의 한계: Standard optimal transport는 특징 표현을 비교하지만 구조 정보를 직접 활용할 수 없으며, Gromov-Wasserstein은 서로 다른 ground space에서 구조를 비교한다.노드는 순서가 없고 구조적 유사성에는 isometry 기반 개념이 필요하므로 graph structure를 비교하기 어렵다.
- 기여: trade-off parameter는 특징과 구조의 중요도를 조절하며, 두 정보가 서로 다른 차원의 공간에 존재하는 경우에도 적용된다.
2. 확률 측도로서의 구조화 데이터
구조화 데이터는 정점 feature와 그래프별 structural similarity를 결합한 가중치 부여 무방향 labeled graph로 모델링된다. 완전한 표현은 feature space와 structure space의 곱공간 위에서 fully supported probability measure로 주어지며, vertex weight는 상대적 중요도를 부호화한다.
- 그래프 표현: 무방향 labeled graph는 feature metric space의 vertex feature a_i와 그래프별 similarity function C로 측정되는 structural representation x_i를 결합한다.Structure space는 암묵적으로 정해지며, C 또는 pairwise node similarity 행렬을 알면 충분하다.
- 가중 구조화 데이터: vertex weight h_i를 할당하면 구조화 데이터 S = (G, h_G)가 생성되며, weight는 정점의 상대적 중요도를 나타낸다.Weight는 probability simplex에 속하며 데이터에 대한 a priori 정보를 부호화할 수 있다.
- 확률 측도 표현: 구조화 객체는 structure space와 feature space의 곱공간 위의 fully supported probability measure µ = Σ_i h_iδ_(x_i,a_i)로 표현된다.주변분포 µ_X와 µ_A는 각각 structure component와 feature component를 나타낸다.
- Weight 해석: 모든 vertex weight가 같으면 구조화 데이터는 underlying graph와 exactly the same information을 담는다.반대로 서로 다른 weight는 segmented-image area ratio와 같은 추가적인 중요도 정보를 보존한다.
3. 구조화 데이터에 대한 Fused Gromov-Wasserstein 접근법
이 절에서는 노드 feature와 그래프 내 구조를 jointly 매칭하는 optimal-transport distance인 Fused Gromov-Wasserstein (FGW)을 소개한다. FGW의 interpolation 및 metric 특성을 정립한 뒤, 이를 structured-data barycenter와 scalable optimization으로 확장한다.
- Interpolation 특성: α가 0에 가까워지면 FGW는 feature에 대한 Wasserstein distance를 복원하고, α가 1에 가까워지면 structure에 대한 Gromov-Wasserstein distance를 복원한다.따라서 FGW는 단일 interpolation parameter를 통해 Wasserstein과 Gromov-Wasserstein distance를 모두 일반화한다.
- Metric 특성: q = 1일 때 FGW는 distance-matrix 가정하에서 metric이고, q > 1일 때는 triangle inequality가 2^(q−1)만큼 완화된 semi-metric이다.q = 1일 때 zero distance는 그래프 사이에 weight, feature, structure를 보존하는 bijection이 존재함을 의미한다.
- 응용: FGW는 unsupervised이며 nearest-neighbor, kernel, embedding, representative-set 방법을 지원하고, optimal node mapping을 통해 similarity를 드러낸다.이 mapping 기반 해석은 end-to-end neural-network 접근법과 대조된다.
- FGW barycenters: FGW는 feature representation과 structure matrix를 jointly 최적화하여 structured-data barycenters를 Fréchet means로 정의한다.barycenter objective는 structure와 features에 대해 jointly convex이지만 couplings에 대해서는 그렇지 않으며, 변형 방법에서는 두 구성요소 중 하나를 고정할 수 있다.
- Optimization: q = 2일 때 FGW 계산은 명시적인 O(m^2n^2) tensor 구성을 피하고, O(mn^2 + m^2n) complexity를 달성하며 classical OT subproblems를 이용한 conditional-gradient updates를 수행한다.barycenters는 couplings, structure, features에 대해 번갈아 최적화하는 block coordinate descent로 계산한다.
4. 실험 결과
벡터 특성이 부여된 그래프, 이산 레이블 그래프, 특성이 없는 그래프 벤치마크 전반에서 FGW는 높은 분류 성능을 보이며, 검증에서는 특성과 구조 정보를 결합하는 중간 범위의 α 값이 선택된다. 또한 FGW는 그래프를 클러스터링하고 의미 있는 클러스터 barycenter를 복원할 수 있다.
- 벡터 특성 그래프: FGW는 6개 벡터 특성 그래프 데이터셋 중 4개에서 가장 우수한 성능을 보이며, 나머지 2개에서는 최상위 방법들의 오차 막대 범위에 속한다.비교에는 Table 1의 평균 정확도를 사용한다.
- 이산 레이블 그래프: WL attributes를 사용한 FGW는 이산 레이블 그래프에서 모든 경쟁 방법과 raw features를 사용한 FGW보다 우수하다.WL attributes는 최단 경로 구조만 사용하는 raw features보다 이웃 레이블을 더 세밀하게 인코딩한다.
- 특성이 없는 그래프: GW는 특성이 없는 social graph에서 SPK와 GK를 크게 능가하며, social graph 분류에 GW를 적용한 최초의 보고 결과를 제시한다.정확도는 Table 3에 보고되어 있다.
- FGW, W, GW 간 비교: Validation은 일관되게 α를 0과 1 사이에서 엄밀히 선택하며, 이는 feature와 structural information이 모두 필요함을 나타낸다.선택된 trade-off는 순수한 Wasserstein 및 순수한 Gromov-Wasserstein endpoint를 배제한다.
- 클러스터링과 barycenter: FGW k-means는 40개의 community graph를 네 그룹으로 클러스터링하고, 무작위 초기화에서 최종 centroid까지 graph barycenter를 변화시킨다.각 그룹에는 10개의 그래프가 포함되며, 각 centroid는 30개 노드로 고정된다.
5. 논의 및 결론
이 논문은 라벨이 있는 구조화 데이터의 거리로 FGW를 도입하고, 임의의 크기를 갖는 그래프에서 유효한 거리임을 증명하며, 분류와 그래프 기반 k-means에서의 유용성을 보인다. 향후 연구로 대안적 또는 학습된 구조·특징 거리, 딥러닝 응용, 계산 복잡도 감소를 제시한다.
- 5. 논의 및 결론: FGW는 구조화 데이터, 나아가 임의의 크기를 갖는 그래프에 대한 거리를 정의한다.그래프의 특징과 구조를 결합하는 확률 측도로 운송 거리를 일반화한다.
- 5. 논의 및 결론: FGW는 그래프 분류에서 대부분의 경우 state-of-the-art 성능에 도달하거나 이를 능가하며, 그래프 기반 k-means를 위한 프레임워크를 제공한다.
- 5. 논의 및 결론: 향후 연구에서는 그래프 구조와 특징에 대해 대안적 거리 또는 end-to-end 학습 거리를 사용하고, 그래프 딥러닝 설정에 FGW를 적용하며, 계산 복잡도를 줄일 수 있다.잠재적 응용으로는 그래프 간 거리가 필요한 graph autoencoder가 있다.
6. 보충 자료
보충 자료에서는 FGW의 수송 표기법을 형식화하고, 보간, metric, triangle inequality 성질을 확립한다. 교차 검증 결과, FGW는 일반적으로 W 및 GW와 비슷하거나 더 우수한 성능을 보였으며, 그렇지 않은 경우에도 차이는 통계적으로 유의하지 않았다.
- 표기법과 정식화: 보충 정식화에서는 FGW에 사용되는 admissible couplings, feature-distance matrices, structure matrices, 그리고 쌍별 구조적 유사도를 측정하는 tensor를 정의한다.FGW의 최솟값은 compact한 coupling 집합에서 연속 함수를 최소화하므로 잘 정의된다.
- 보간 성질: FGW는 Wasserstein distance와 Gromov-Wasserstein distance 사이를 보간한다. α가 0에 가까워지면 W를 recover하고, α가 1에 가까워지면 GW를 recover한다.또한 Wasserstein loss와 Gromov-Wasserstein loss를 단순히 보간한 값으로부터 하한을 갖는다.
- Metric 성질: FGW는 q = 1에서 metric이고 q > 1에서 semi-metric이며, q > 1일 때 triangle inequality는 2^q−1의 factor만큼 완화된다.q = 1에서는 distance가 triangle inequality를 만족하고, q > 1에서는 coefficient 2^q−1을 갖는 완화된 형태를 만족한다.
- 교차 검증 결과: 교차 검증 결과, 여러 dataset에서 FGW score는 대체로 W와 GW 모두보다 크거나 같았으며, 예외는 통계적으로 유의하지 않았다.Nested 10-fold 교차 검증으로 α를 [0, 1] 내에서 선택했으며, 실험은 dataset마다 10회, MUTAG와 PTC에서는 50회 반복했다.