라지 그래프를 위한 노드별 프로그램 셋 (Node-Level Program Sets for Large-Graph Node Classification)

1. 문제 (Problem)

ProgNet [Interpretable Graph Classification 참조]은 여러 개의 작은 그래프에 대한 그래프 분류 설정에서 GDL program 기반 vocabulary의 효과를 보였다. 그러나 실세계의 핵심 그래프 데이터 상당수는 인용 네트워크, 소셜 네트워크, 지식 그래프처럼 하나의 큰 그래프이며, 중심 태스크는 노드 분류(node classification) 와 링크 프레딕션(link prediction) 이다.

핵심 아이디어는 프로그램 아이디어를 이 설정으로 옮기는 것이다: 노드별로 그 노드를 기술하는 GDL program 셋을 추출하고, 기존 노드 임베딩 기반 분류에 노드 임베딩 + 프로그램 셋 정보를 결합하는 형태로 활용한다.

이때 두 가지 열린 질문이 있다.

  1. 노드에 대한 프로그램 셋을 어떻게 뽑을 것인가 — 노드의 N-hop 이웃에 기존 마이닝 알고리즘을 적용할 수 있으나, “포함” 관계가 그래프 분류와 반대가 된다. 그래프 분류에서는 program이 그래프에 포함되는 형태였다면, 여기서는 노드가 프로그램(의 매칭)에 포함되는 형태다.
  2. 무엇이 좋은 셋인가 — 노드를 대표하는 의미 있는 정보(엘리먼트)가 무엇이어야 하는지에 대한 기준이 아직 없다.

표현형은 subgraph + feature range의 결합이어야 한다. feature가 없으면 프로그램이 subgraph와 동일해져 GDL의 표현력 이점이 사라지므로, feature가 풍부한 대규모 그래프 데이터가 필요하다.

풀어야 할 과제는 세 가지다.

  1. 속도: 노드 100만~1000만 규모에서는 병렬화가 필수다. 현행 구현(PLD)은 노드 약 4만 개 규모부터 급격히 느려진다.
  2. 좋은 셋의 선택 기준: 어떤 프로그램들이 노드를 잘 대표하는가.
  3. 분류 아키텍처: 노드별 프로그램 셋을 입력으로 받았을 때, 노드 분류/링크 프레딕션을 위한 아키텍처를 어떻게 설계할 것인가.

이 방향은 미해결 과제인 구조 + feature-range aware 임베딩 문제와 직결되어 있다 — 이 임베딩이 해결되면 본 방향을 바로 진행할 수 있다.

2. 목표 (Goal)

하나의 큰 그래프에서 노드별 GDL program 셋을 추출하고, 이를 활용한 해석 가능한 노드 분류/링크 프레딕션 프레임워크를 설계한다.