Improving Message-Passing and Representation Learning of Graph Neural Networks

Abstract

Graph Neural Networks (GNNs) achieve substantial improvement in analyzing graph-structured datasets under semi-supervised settings, where few labels are available during the training. The discriminative power of GNNs stems from the message-passing scheme, where they utilize information from neighboring nodes. Generally, under the graphs with strong homophily, features from the adjacent nodes can be used to guide decision boundary (e.g., neural networks) more precisely. Nonetheless, they fail to achieve satisfying results under heterophilous graphs, where most edges connect two nodes with different labels.

In the first paper, we analyze the performance of GNNs based on the multiple propagation schemes theoretically. For example, flipping the sign of edges is rooted in a strong theoretical foundation, and attains significant performance enhancements. Nonetheless, they assume a binary class scenario and they may suffer from confined applicability. Here, we extend the prior understandings to multi-class scenarios and point out two drawbacks: In case two nodes belong to different classes but have a high similarity, signed propagation can decrease the discrimination power of the GNNs, (2) signed message also increases the prediction uncertainty (e.g., conflict evidence) which can impede the stability of the algorithm.

In the second paper, we focus on finding the heterophilous edges, which can degrade the overall quality of GNNs significantly. To achieve this, we employ a confidence ratio as a hyper-parameter, assuming that some of the edges are disassortative (heterophilic). Here, we suggest the two-phased algorithm, (1) determining edge coefficients through subgraph matching using a supplementary module, and (2) the application of modified label propagation. Specifically, our supplementary module identifies a certain proportion of task-irrelevant edges based on a given confidence ratio. Further, the improved label propagation mechanism prevents two nodes with smaller weights from being closer effectively.

Lastly, we introduce the limitation of GNNs from another perspective, where they suffer from sparsity in initial node features. This can result in overfitting of the first projection matrix (or hyperplane), where the dimensions with zero inputs are not updated during training. To address this issue, we propose a novel data augmentation strategy, which flips the initial features and the hyperplane simultaneously. To the best of our knowledge, this is the first attempt to mitigate the overfitting problem caused by input features.

그래프 신경망 (Graph Neural Networks, GNNs)은 반지도 학습 설정에서 그래프 구조 데이터를 분석하는 데 상당한 개선을 이루어냅니다. 이 설정에서는 훈련 중에 사용 가능한 레이블이 적습니다. GNNs의 판별력은 메시지 전달 방식에서 비롯되며, 이 방식에서는 인접한 노드들로부터 정보를 활용합니다. 일반적으로, 강한 동질성을 가진 그래프에서는 인접한 노드들로부터 얻은 특징들이 결정 경계(예: 신경망)를 더 정확하게 안내하는 데에 사용될 수 있습니다. 그러나 노드들 간의 대부분의 엣지가 서로 다른 레이블을 가지는 이질성 그래프의 경우에는 만족스러운 결과를 얻기 어렵습니다.

첫 번째 논문에서는 GNNs의 성능을 다중 전파 방식을 기반으로 이론적으로 분석합니다. 예를 들어, 엣지의 부호를 뒤집는 것은 강력한 이론적 기반에 근거하며, 상당한 성능 향상을 이룰 수 있습니다. 그러나 이들은 이진 클래스 시나리오를 가정하며, 적용 범위가 제한될 수 있습니다. 여기서 우리는 이전의 이해를 다중 클래스 시나리오로 확장하고 두 가지 단점을 지적합니다: (1) 만약 두 노드가 서로 다른 클래스에 속하지만 높은 유사성을 가진다면, 부호화된 전파(signed propagation)는 GNNs의 판별력을 감소시킬 수 있습니다. 또한, 부호화된 메시지는 예측의 불확실성(예: 충돌 증거)을 증가시키며, 이는 알고리즘의 안정성을 저해할 수 있습니다.

두 번째 논문에서는 GNNs의 전반적인 품질을 크게 저하시킬 수 있는 이질성 엣지를 찾는 데에 초점을 맞춥니다. 이를 위해 우리는 하이퍼파라미터로서의 신뢰도 비율을 사용하여 일부 엣지가 이질성인 경우를 가정합니다. 여기서 우리는 두 단계의 알고리즘을 제안합니다. (1) 보충 모듈을 사용하여 서브그래프 매칭을 통해 엣지 계수를 결정하고, (2) 수정된 레이블 전파를 적용합니다. 구체적으로, 보충 모듈은 주어진 신뢰도 비율에 따라 일부 작업과 관련 없는 엣지를 식별합니다. 더 나아가, 개선된 레이블 전파 메커니즘은 가중치가 작은 두 노드가 효과적으로 가까이 위치하는 것을 방지합니다.

마지막으로, 우리는 GNNs의 또 다른 한계를 다른 관점에서 소개합니다. 초기 노드 특징의 희소성으로 인해 첫 번째 투영 행렬 (또는 초평면)의 과적합 문제가 발생할 수 있습니다. 여기서 우리는 이 문제를 해결하기 위해 새로운 데이터 증강 전략을 제안합니다. 이 전략은 초기 특징과 초평면을 동시에 뒤집습니다. 우리의 지식으로는 이것이 입력 특징으로 인한 과적합 문제를 완화하기 위한 최초의 시도입니다.