Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models

Benedek Rozemberczki; Rik Sarkar

Source-linked AI summary

Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models

Benedek Rozemberczki, Rik Sarkar

arXiv:2005.07959v22020년 5월 16일cs.LGcs.DMcs.SIstat.ML

TL;DR

그래프 이웃 특징은 단순 집계로 포착하기 어려운 다양하고 잠재적으로 무한한 속성 분포를 이룬다. 이 논문은 random walk 가중 characteristic function을 사용해 노드 및 그래프 표현을 생성하는 FEATHER를 제안하며, 경쟁력 있는 성능과 견고한 transfer learning, 입력 크기에 대한 선형적 실용 확장성을 보고한다.

문제
이웃 속성은 평균과 같은 단순 선형 집계로 표현하기 어려운 다양하고 알려지지 않았으며 무한한 분포를 가질 수 있다.
방법
FEATHER는 학습되거나 이산화된 지점에서 random walk 가중 characteristic function을 효율적으로 계산해 이웃 특징 분포를 표현하고 parametric classifier를 지원한다.
결과
FEATHER 변형들은 유사한 embedding 및 graph neural network 모델과 경쟁력 있는 성능을 보였고, 견고한 transfer learning을 지원했으며, 실제로 입력 크기에 따라 선형적으로 확장되었다.
시사점 및 한계
FEATHER는 이론적으로 graph isomorphism 일관성을 보장하고 데이터 손상에 견고하며 classification task에 실용적으로 적용 가능한 효율적인 노드 및 그래프 표현을 제공한다.
시사점 및 한계
평가는 social network와 web graph로 제한되었으며, biological dataset과 다른 유형의 데이터셋은 향후 검증 과제로 남았다.

Abstract

from arXiv · show

In this paper, we propose a flexible notion of characteristic functions defined on graph vertices to describe the distribution of vertex features at multiple scales. We introduce FEATHER, a computationally efficient algorithm to calculate a specific variant of these characteristic functions where the probability weights of the characteristic function are defined as the transition probabilities of random walks. We argue that features extracted by this procedure are useful for node level machine learning tasks. We discuss the pooling of these node representations, resulting in compact descriptors of graphs that can serve as features for graph classification algorithms. We analytically prove that FEATHER describes isomorphic graphs with the same representation and exhibits robustness to data corruption. Using the node feature characteristic functions we define parametric models where evaluation points of the functions are learned parameters of supervised classifiers. Experiments on real world large datasets show that our proposed algorithm creates high quality representations, performs transfer learning efficiently, exhibits robustness to hyperparameter changes, and scales linearly with the input size.

1 서론

이 논문은 다양한 노드 이웃 feature 분포를 표현하기 위한 characteristic function을 도입하고, FEATHER에서 random walk tie strength를 사용해 효율적인 node embedding과 parametric classifier를 생성한다. 또한 이론적 성질을 정립하고 노드 및 그래프 분류 과제에서 FEATHER를 평가한다.

기여: Characteristic function은 여러 feature에 동시에 적용할 수 있어 노드 수준 machine learning 과제를 위한 통합된 이웃 표현을 지원한다.이웃 feature는 node classification, link prediction, community detection에 유용하다는 점에서 동기가 부여된다 [15].
동기: Characteristic function은 분포를 알 수 없거나 무한할 수 있는 이질적 attribute에 대해 단순한 선형 집계 가 갖는 한계를 해결한다.여러 노드와 attribute에 걸쳐 이웃을 표현하고 비교하는 통합된 방법을 제공한다.
본 연구: FEATHER는 r-scale random-walk tie strength를 사용해 characteristic function에 가중치를 부여하고, 이웃 feature 분포로부터 Euclidean node embedding을 효율적으로 생성한다.Tie strength는 source에서 출발한 길이 r인 random walk가 target에 도달할 확률로 정의된다.
기여: 이 논문은 동형 그래프가 동일한 평균 풀링 characteristic-function 표현을 갖는다는 것을 증명하고, FEATHER에 기반한 미분 가능한 parametric model을 개발한다.이 모델에는 학습된 evaluation point를 사용하는 softmax regression과 graph neural network 변형이 포함된다.
평가: FEATHER는 실제 social graph와 web graph에서 노드 라벨링에서 최대 4.6%, 그래프 분류에서 12.0%까지 비교 가능한 비지도 방법보다 우수한 성능을 보인다.평가에는 Facebook, Deezer, Twitch, Wikipedia, GitHub 데이터셋이 포함되며 graph neural network, 이웃 보존 방법, attribute node-embedding 방법과 비교한다.

2 관련 연구

선행 연구는 heat diffusion wavelet의 characteristic function, 노드 및 전체 그래프 임베딩, 통계적 그래프 fingerprint를 아우른다. FEATHER는 정점 특징 분포를 매개변수화된 다중 스케일 descriptor로 생성한다는 점에서 graph neural network의 forward pass와도 관련된다.

Characteristic function은 heat diffusion wavelet [10]에 이전부터 적용되어 왔으며, tie strength가 균일하고 특징 유형이 제한된다고 가정했다.
Node embedding method는 유사성을 근사적으로 보존하면서 정점을 Euclidean space에 표현하며, neighborhood-preserving, attributed, structural 접근법을 포함한다 [25] [15].
Whole-graph embedding과 statistical graph fingerprint는 structural feature matrix, graph Laplacian eigenvalue 또는 graph-scanning information을 사용해 그래프를 Euclidean space에 표현한다 [26] [8] [12].
FEATHER는 tie-strength-weighted vertex feature를 평가해 parameterized, multi-scale descriptor를 생성한다는 점에서 graph neural network의 forward pass [17] [22]와 유사하다 [1].이 연결은 FEATHER를 정점 특징을 기술하는 multi-scale graph neural network 유사 절차로 규정한다.

3 그래프의 특성 함수

이 절에서는 이웃 내 노드 특징 분포를 설명하기 위해 속성 그래프에 정의된 특성 함수를 소개한다. 또한 r-스케일 랜덤 워크 가중 변형을 제안하고, 선형 시간 계산 알고리즘을 제시하며, 강건성과 동형 그래프 표현 특성을 확립한다.

이웃 내 노드 특징 분포를 설명하기 위해 속성 그래프에 특성 함수를 정의한다.
제안한 r-스케일 랜덤 워크 가중 특성 함수는 모든 노드에 대해 선형 시간에 계산할 수 있다.
이 절에서는 이러한 특성 함수의 강건성과 동형 그래프를 표현하는 능력을 증명한다.

3.1 노드 feature 분포 특성화

이 절에서는 multiscale feature 분포를 위한 노드 수준 characteristic function을 정의하고, random walk transition probability로 정점에 가중치를 부여한다. FEATHER는 노드, feature, scale 전반에서 이러한 함수를 효율적으로 샘플링해 node embedding을 생성한다.

Characteristic-function 구조: 실수부와 허수부는 각각 cosine 및 sine wave의 가중합이며, evaluation point θ는 시간으로, feature 값은 각주파수로 작용한다.실수부는 짝함수이고 허수부는 홀함수이며, 둘 다 [-1,1]에 속한다.
Random-walk 가중치: Scale r에서 characteristic function은 r-step random-walk transition probability를 사용해 source node 이웃의 feature 분포를 나타낸다.이 probability는 normalized adjacency matrix D−1A의 rth power의 원소와 같다.
Node embedding: 함수 domain에서 d개의 evaluation point를 샘플링하면 모든 노드에 대한 compact representation을 얻으며, 비슷한 행은 유사한 local feature 분포를 나타낸다.이 representation은 node embedding으로 작용하며, 전체 그래프의 time complexity는 O(|E| ·d ·r), memory complexity는 O(|V | · d)이다.
Multiple feature: FEATHER는 하나의 node feature에서 k개의 real-valued feature vector로 일반화하여, 각 feature와 scale마다 별도의 characteristic-function representation을 계산한다.Embedding 저장 complexity는 O(|V | · d · r · k)이고, 전체 computation은 O((|E| + |V |) · d · r2 · k)이다.
FEATHER 알고리즘: FEATHER는 그래프의 normalized adjacency matrix를 사용해 r까지의 모든 scale에서 모든 node feature에 대한 characteristic-function embedding을 계산한다.이 알고리즘은 sparsity를 고려하며 node embedding matrix Z를 반환한다.

3.2 이론적 특성

r-scale random-walk 가중 characteristic function은 국소적인 feature corruption에 강건하며, graph isomorphism에 불변인 mean-pooled graph descriptor를 산출한다. 이러한 descriptor는 graph-level 비교와 machine learning을 지원한다.

강건성: 한 노드에서 발생한 feature corruption은 corruption의 크기와 무관하게 characteristic-function 값의 변화를 tie strength로 제한한다.이 bound는 cosine 함수 간 최대 절댓값 차이가 2라는 사실에서 따른다.
Graph descriptor: Mean-pooled characteristic function은 구조적 특성을 통해 전체 graph를 특징짓고 비교한다.pooled real part와 imaginary part는 graph-level descriptor로 정의된다.
Graph descriptor: 이렇게 얻은 graph descriptor는 graph-level machine-learning algorithm의 feature로 사용할 수 있다.
Isomorphism 불변성: Mean-pooled degree characteristic function은 isomorphic graph에서 동일하다.이는 graph isomorphism이 두 normalized adjacency matrix와 degree vector를 연결하는 permutation matrix를 유도하기 때문에 성립한다.

3.3 Parametric characteristic functions

Parametric characteristic-function 모델은 classifier 가중치와 함께 evaluation point를 공동으로 학습해 downstream node classification에 가장 판별적인 scale을 선택한다. 이 모델에는 labeled node에서 최적화되는 softmax 및 single-hidden-layer neural 변형이 포함된다.

3.3 Parametric characteristic functions: 학습된 evaluation point는 random-walk characteristic function을 task-adaptive하게 만들어 downstream classification에 가장 판별적인 값을 선택한다.Algorithm 1은 normalized adjacency matrix를 사용하는 graph neural network의 forward pass로 해석할 수 있다.
3.3 Parametric characteristic functions: softmax classifier는 characteristic-function representation과 trainable weight β를 결합해 node-class distribution을 출력한다.representation Z는 trainable evaluation point e_Θ를 사용해 Algorithm 1로 계산되며, β의 shape은 (2·k·d·r)×C이다.
3.3 Parametric characteristic functions: neural characteristic-function 모델은 trainable matrix β_0과 β_1, 그리고 element-wise ReLU activation을 사용하는 하나의 hidden feed-forward layer를 추가한다.각 matrix의 shape은 각각 (2·k·d·r)×h와 h×C이다.
3.3 Parametric characteristic functions: FEATHER-N과 FEATHER-L은 모두 labeled training node에 대한 log-loss를 최소화하고, gradient descent로 evaluation point와 classifier weight를 최적화한다.최적화되는 parameter는 neural 모델의 경우 e_Θ와 함께 softmax 모델의 β, neural 모델의 β_0, β_1이다.
3.3 Parametric characteristic functions: softmax 모델과 neural 모델의 trainable parameter 수는 각각 O(k · r · d · C)과 O(k · r · d · h + C · h)이다.softmax 모델은 upstream FEATHER representation 뒤에 logistic regression을 적용한 경우와 parameter 수가 같다.

4 실험 평가 · 4.1 데이터셋 · 4.2 노드 분류

FEATHER는 노드 및 그래프 분류를 위해 이질적인 소셜 네트워크 및 웹 그래프 데이터셋에서 평가되며, 실험은 표현 품질, 전이 학습, 확장성, 강건성을 중점적으로 검증한다. 노드 분류에서 비지도 FEATHER는 micro-averaged test AUC 기준으로 proximity-preserving, structural, attributed node embedding보다 0.4%–4.6% 높은 성능을 보인다.

4 실험 평가: FEATHER는 노드 및 그래프 분류에 대해 평가되며, 실험에서는 전이 학습, 확장성, 강건성도 검증한다.
4.1 데이터셋: 평가에는 공개 데이터셋과 자체 수집한 소셜 네트워크 및 웹 그래프 데이터셋이 사용되며, 기술 통계는 Table 1에 요약되어 있다.데이터셋은 크기, 밀도, feature 수 측면에서 이질적이다.
4.1.1 노드 수준 데이터셋: 노드 수준 데이터셋은 크기, 밀도, feature 수가 서로 다르며 Wikipedia Crocodiles, Twitch Social Networks, Deezer Europe에서 binary 또는 multi-class classification을 지원한다.과제에는 그래프 구조와 선호 artist를 바탕으로 Wikipedia 페이지 인기도, 성인 콘텐츠 스트리밍, 사용자 성별을 예측하는 작업이 포함된다.
4.1.2 그래프 수준 데이터셋: 그래프 수준 평가는 크기, 밀도, diameter가 다양한 소규모 비귀속 소셜 그래프를 사용하며, Reddit Threads, Twitch Egos, GitHub Repos 등이 포함된다.이 데이터셋은 thread와 non-thread 식별, gamer 행동 분류와 같은 그래프 분류 과제를 지원한다.
4.2 노드 분류: 노드 분류 비교에는 FEATHER 변형, neighbourhood 기반 embedding, structural embedding, attributed embedding, 그리고 경쟁력 있는 graph neural network architecture가 포함된다.비지도 baseline은 동일한 free-parameter 수와 기본 Karate Club 또는 Node2Vec 설정을 사용한다.
4.2.1 실험 설정: FEATHER 변형은 그래프를 neighbourhood, structural, generic vertex attribute와 결합한다. 비지도 모델은 feature당 16개의 evaluation point, r = 2, logistic regression을 사용한다.Neighbourhood feature는 normalized adjacency matrix의 32차원 Truncated SVD embedding을 사용하고, structural feature는 log degree와 clustering coefficient를 사용한다.

4.3 그래프 분류

FEATHER graph descriptor는 세 데이터셋에서 supervised 및 unsupervised graph classification method보다 우수하며, AUC가 유의하게 1.1%–12.0% 향상된다. Deezer Egos에서는 FEATHER의 불리함이 유의하지 않다.

그래프 분류: 비교에서는 unsupervised 및 supervised FEATHER를 implicit matrix factorization, spectral fingerprinting, graph neural network model과 비교한다.평균 test AUC와 standard error는 10개의 seeded 20%/80% train-test split에서 계산했다.
그래프 분류: Supervised model은 one-hot으로 인코딩한 degree, clustering coefficient, eccentricity를 사용하고, 그 뒤에 pooling과 fully connected layer를 배치한 two graph-convolutional layers를 적용한다.학습은 learning rate 0.01과 batch size 32를 사용해 10 epochs 동안 Adam [21]으로 log-loss를 최소화한다.
그래프 분류: Unsupervised FEATHER는 logistic regression 전에 permutation-invariant mean, maximum 또는 minimum aggregation을 사용해 node characteristic-function feature를 pooling한다.Node representation은 log-transformed degree를 사용하며, r = 5, d = 25이고 evaluation point는 [0, 5]에서 균일하게 초기화한다.
그래프 분류: FEATHER는 Reddit Threads, Twitch Egos, Github Repos에서 supervised 및 unsupervised graph classification method보다 우수하며, AUC가 유의하게 1.1%–12.0% 향상된다.세 데이터셋 모두에서 향상은 α = 1% 수준에서 유의하다.
그래프 분류: Deezer Egos에서는 FEATHER의 불리함이 유의하지 않다.

4.4 민감도 분석

민감도 분석 결과, 더 큰 random-walk scale과 더 많은 characteristic-function evaluation point가 예측 성능을 향상시키지만 한계 이득은 감소한다. Supervised model은 특히 higher-order neighborhood에서 더 큰 이점을 얻으며, evaluation point가 적을 때 더 효율적이다.

실험 설정: 분석에는 log-transformed degree feature를 사용한 Facebook Page-Page, 표준 20%/80% 분할, 그리고 10 seeded split에 대한 평균 test AUC가 사용된다.Scale과 evaluation-point 효과는 각각 25 evaluation point 또는 scale 5를 사용해 별도로 변화시켰으며, evaluation point는 [0, 5]에서 균등하게 초기화했다.
Random-walk scale: Higher-order neighborhood는 classification 성능을 향상시키지만 scale에 따른 한계 이득은 감소하며, one-hop neighborhood를 넘어서는 경우 supervised model이 unsupervised variant보다 상당히 우수하다.First-hop neighbor만 사용할 때는 supervised variant와 unsupervised variant의 성능 차이가 거의 나타나지 않는다.
Evaluation point 수: Characteristic-function evaluation point가 많을수록 downstream performance가 향상되지만, supervised model은 한계 이득이 감소하고 neural model은 더 적은 point로도 좋은 성능에 도달한다.Evaluation point 수가 적을 때 supervised model이 더 효율적이다.

4.5 Transfer learning · 4.6 실행 시간 성능

FEATHER의 characteristic-function feature는 Twitch 그래프 간에 전이되며, supervised neural model이 unsupervised 및 shallow 변형보다 우수한 성능을 보인다. 또한 실행 시간은 입력 크기와 random-walk scale에 따라 예측 가능하게 증가한다. 이러한 결과는 transfer learning의 유용성과 제안한 실행 시간 복잡도 분석을 뒷받침한다.

4.5 Transfer learning: Transfer learning에서는 각 model을 완전히 라벨링된 source graph에서 학습하고, target variable과 node-feature set을 공유하는 target graph에서 평가했다.모든 model에 대해 r = 5 및 d = 25개의 characteristic-function evaluation point를 사용했으며, log-transformed degree centrality를 포함했다.
4.5 Transfer learning: Transfer-learning 평가는 Twitch Germany, Spain, Portugal을 target graph로 사용했으며, 10회의 실험 반복에서 얻은 mean AUC로 예측 성능을 측정했다.결과는 r-scale random-walk-weighted characteristic-function feature를 transfer-learning 설정에서 사용할 수 있음을 보여준다.
4.5 Transfer learning: Transfer learning에서 Neural FEATHER는 unsupervised FEATHER와 shallow FEATHER-L model보다 우수했으며, Portuguese user에서 평균 AUC가 2.1–3.3% 더 높았다.Figure 4는 German, Spanish, Portuguese Twitch target graph에서 10회의 seeded experiment로 얻은 mean AUC 값을 보고한다.
4.5 Transfer learning: 하나의 structural feature만 사용하는 characteristic function도 대부분의 Twitch transfer scenario에서 random guessing보다 우수했다.공유된 structural feature는 log-transformed node degree centrality였다.
4.6 실행 시간 성능: node, edge, feature 또는 characteristic-function evaluation point의 수를 두 배로 늘리면 예상 FEATHER 실행 시간도 두 배가 되었다.Figure 5는 synthetic Erdős–Rényi graph에서 10회 반복하여 평균 logarithmic runtime을 측정했다.
4.6 실행 시간 성능: random-walk scale을 증가시키면 실행 시간이 늘어났지만, 작은 r 값에서는 quadratic increase가 뚜렷하지 않았다.실행 시간 실험에서는 graph size, edge count, feature count, evaluation-point count 및 random-walk scale을 변화시켰다.

5 결론 및 향후 연구 방향

이 논문은 attributed graph에서 characteristic-function representation을 선형 시간에 계산하는 방법으로 FEATHER를 제안하며, data corruption에 대한 강건성과 graph isomorphism 일관성을 이론적으로 보인다. 실험에서는 경쟁력 있는 classification 성능과 강건한 transfer learning을 확인했으며, 향후 연구에서는 더 폭넓은 graph model과 graph type을 대상으로 한다.

결론: FEATHER는 대규모 attributed graph에서 random walk 가중 characteristic function을 r개 스케일로 선형 시간에 계산해 node의 Euclidean vector-space representation을 생성한다.또한 data corruption에 대한 강건성과 isomorphic graph에서 동일한 representation을 보임을 증명한다.
결론: 실세계 node 및 graph classification dataset 전반에서 FEATHER 변형들은 유사한 embedding 및 graph neural network model과 비교해 경쟁력이 있으며, transfer learning도 효율적이고 강건하다.Sensitivity analysis와 node-classification 결과는 supervised FEATHER model이 unsupervised representation보다 우수함을 보여준다.
향후 연구 방향: 향후 연구에서는 FEATHER의 forward pass를 temporal, multiplex, heterogeneous graph neural network에 통합하고, learned permutation-invariant node pooling을 개발하며, social graph와 web graph를 넘어 평가할 수 있다.이러한 방향은 multi-scale vertex feature extraction, node-feature aggregation, empirical coverage를 확장한다.