RGE: A Repulsive Graph Rectification for Node Classification via Influence

Jaeyun Song, Sungyub Kim, Eunho Yang
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:32331-32348, 2023.

Abstract

In real-world graphs, noisy connections are inevitable, which makes it difficult to obtain unbiased node representations. Among various attempts to resolve this problem, a method of estimating the counterfactual effects of these connectivities has recently attracted attention, which mainly uses influence functions for single graph elements (i.e., node and edge). However, in this paper, we argue that there is a strongly interacting group effect between the influences of graph elements due to their connectivity. In the same vein, we observe that edge groups connecting to the same train node exhibit significant differences in their influences, hence no matter how negative each is, removing them at once may have a rather negative effect as a group. Based on this motivation, we propose a new edge-removing strategy, Repulsive edge Group Elimination (RGE), that preferentially removes edges with no interference in groups. Empirically, we demonstrate that RGE consistently outperforms existing methods on the various benchmark datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-song23f, title = {{RGE}: A Repulsive Graph Rectification for Node Classification via Influence}, author = {Song, Jaeyun and Kim, Sungyub and Yang, Eunho}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {32331--32348}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/song23f/song23f.pdf}, url = {https://proceedings.mlr.press/v202/song23f.html}, abstract = {In real-world graphs, noisy connections are inevitable, which makes it difficult to obtain unbiased node representations. Among various attempts to resolve this problem, a method of estimating the counterfactual effects of these connectivities has recently attracted attention, which mainly uses influence functions for single graph elements (i.e., node and edge). However, in this paper, we argue that there is a strongly interacting group effect between the influences of graph elements due to their connectivity. In the same vein, we observe that edge groups connecting to the same train node exhibit significant differences in their influences, hence no matter how negative each is, removing them at once may have a rather negative effect as a group. Based on this motivation, we propose a new edge-removing strategy, Repulsive edge Group Elimination (RGE), that preferentially removes edges with no interference in groups. Empirically, we demonstrate that RGE consistently outperforms existing methods on the various benchmark datasets.} }
Endnote
%0 Conference Paper %T RGE: A Repulsive Graph Rectification for Node Classification via Influence %A Jaeyun Song %A Sungyub Kim %A Eunho Yang %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-song23f %I PMLR %P 32331--32348 %U https://proceedings.mlr.press/v202/song23f.html %V 202 %X In real-world graphs, noisy connections are inevitable, which makes it difficult to obtain unbiased node representations. Among various attempts to resolve this problem, a method of estimating the counterfactual effects of these connectivities has recently attracted attention, which mainly uses influence functions for single graph elements (i.e., node and edge). However, in this paper, we argue that there is a strongly interacting group effect between the influences of graph elements due to their connectivity. In the same vein, we observe that edge groups connecting to the same train node exhibit significant differences in their influences, hence no matter how negative each is, removing them at once may have a rather negative effect as a group. Based on this motivation, we propose a new edge-removing strategy, Repulsive edge Group Elimination (RGE), that preferentially removes edges with no interference in groups. Empirically, we demonstrate that RGE consistently outperforms existing methods on the various benchmark datasets.
APA
Song, J., Kim, S. & Yang, E.. (2023). RGE: A Repulsive Graph Rectification for Node Classification via Influence. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:32331-32348 Available from https://proceedings.mlr.press/v202/song23f.html.

Related Material