notesum.ai

Published at May 13

Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks

NeurIPS

Released Date: May 13, 2024

Authors: Arjun Subramonian¹, Jian Kang², Yizhou Sun¹

Aff.: ¹University of California, Los Angeles; ²University of Rochester

Arxiv: https://openreview.net/pdf/6df0c4ad9ea96a2a6aab1a1f14255a2734b0942d.pdf

Refer to caption

Hypothesis	Papers
(H1) Neighborhoods of low-degree nodes contain insufficient or overly noisy information for effective representations.	[34], [52], [54], [14], [65], [31], [32], [35], [33], [21], [29], [19], [28], [55], [67], [47], [11], [8], [20], [66], [56]
(H2) High-degree nodes have a larger influence on GNN training because they have a greater number of links with other nodes, thereby dominating message passing.	[45], [52], [65], [22], [63], [28], [62]
(H3) High-degree nodes exert more influence on the representations of and predictions for nodes as the number of GNN layers increases.	[65], [6], [27], [11], [64]
(H4) In semi-supervised learning, if training nodes are picked randomly, test predictions for high-degree nodes are more likely to be influenced by these training nodes because they have a greater number of links with other nodes.	[45], [63], [18]
(H5) Representations of high-degree nodes cluster more strongly around their corresponding class centers, or are more likely to be linearly separable.	[39], [49], [26]
(H6) Neighborhoods of high-degree nodes contain more homophilic links, enhancing their representations.	[29], [55]
(H7) Nodes with different degrees are not necessarily mapped to distinct representations.	[53]
(H8) Low-degree nodes have class-imbalanced training samples, yielding worse generalization.	[60]
(H9) High-degree nodes are more likely to be labeled during training and thus GNNs generalize better for them.	[9]
(H10) Representations of high-degree nodes have higher variance.	[28]
(H11) Low-degree nodes are more likely to be sampled during training/inference.	[47]