Reproducing Confidence-Based Subgraph Matching for Heterophilic Graph Neural Networks: An Independent Reconstruction and Reproducibility Audit

Authors

  • Samaneh Ghods Department of Mathematics, Se. C., Islamic Azad University, Semnan, Iran Author

Abstract

Confidence-based Subgraph Matching (ConSM) is a two-stage framework for graph neural networks that estimates task-relevant edge agreement from local subgraph structure and then uses the resulting edge scores in a sign-aware propagation objective. This study provides a critical analysis and independent reconstruction of ConSM, with particular emphasis on reproducibility under heterophily. We consolidate the method's mathematical formulation, clarify its graph-theoretic and spectral motivation, and reframe several stronger theoretical statements as proof sketches or informal propositions with their assumptions made explicit. The independent CPU-oriented reconstruction approximates the optimal-transport/Monge stage by nearest-reference assignment and reference-wise pooling. Across three recorded seeds (n=3), the reconstruction obtained 79.4 ± 1.4% test accuracy on Cora and 69.2 ± 2.5% on Citeseer. Raw per-seed values were not retained in the active reproducibility record, so they are not reconstructed or imputed here; the reported mean±SD therefore represents the complete seed-level evidence currently available. Recorded single-run results on Actor, Chameleon, and Squirrel were below the corresponding GCN baselines, consistent with possible sensitivity to transport quality, data versions, confidence calibration, optimization settings, and random splits. We retain these negative results and analyze the Chameleon failure mode rather than treating it as an implementation detail to be hidden. Results reported in the verified source literature on edge classification, depth robustness, link prediction, label scarcity, and leakage-free evaluation are summarized separately from independently generated evidence. Finally, we outline local confidence gates, unbalanced transport, probability calibration, and node-wise filter mixtures as future directions rather than validated improvements. The manuscript is explicitly scoped as a reproducibility audit: it establishes what can be supported by the present evidence and provides a limitations-based validation roadmap for follow-up studies rather than presenting unavailable experiments as completed evidence.

 

Downloads

Download data is not yet available.

References

[1] D. Bo, X. Wang, C. Shi, and H. Shen, "Beyond low-frequency information in graph convolutional networks," in Proceedings of the AAAI Conference on Artificial Intelligence, 2021, vol. 35, 5 ed., pp. 3950-3957, doi: 10.1609/aaai.v35i5.16514.

[2] T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks," in Proceedings of the International Conference on Learning Representations (ICLR), 2017. [Online]. Available: https://arxiv.org/abs/1609.02907.

[3] P. Veličković, "Graph attention networks," in Proceedings of the International Conference on Learning Representations (ICLR), 2018. [Online]. Available: https://arxiv.org/abs/1710.10903.

[4] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra, "Beyond homophily in graph neural networks: Current limitations and effective designs," in Advances in Neural Information Processing Systems, 2020, vol. 33, pp. 7793-7804. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2020/hash/58ae23d878a47004366189884c2f8440-Abstract.html.

[5] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, "How powerful are graph neural networks?," in Proceedings of the International Conference on Learning Representations (ICLR), 2019. [Online]. Available: https://arxiv.org/abs/1810.00826.

[6] Y. Choi, J. Choi, T. Ko, H. Byun, and C. K. Kim, "Finding heterophilic neighbors via confidence-based subgraph matching for semi-supervised node classification," in Proceedings of the 31st ACM International Conference on Information & Knowledge Management (CIKM '22), 2022, pp. 283-292, doi: 10.1145/3511808.3557324.

[7] Y. Choi and C. K. Kim, "Identifying heterophilic neighbors via confidence-based subgraph matching for graph neural networks," Artificial Intelligence, vol. 358, p. 104575, 2026, doi: 10.1016/j.artint.2026.104575.

[8] Y. Rong, W. Huang, T. Xu, and J. Huang, "DropEdge: Towards deep graph convolutional networks on node classification," in Proceedings of the International Conference on Learning Representations (ICLR), 2020. [Online]. Available: https://arxiv.org/abs/1907.10903.

[9] L. Zhao and L. Akoglu, "PairNorm: Tackling oversmoothing in GNNs," in Proceedings of the International Conference on Learning Representations (ICLR), 2020. [Online]. Available: https://arxiv.org/abs/1909.12223.

[10] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li, "Simple and deep graph convolutional networks," in Proceedings of the 37th International Conference on Machine Learning (ICML), PMLR, 2020, vol. 119, pp. 1725-1735. [Online]. Available: https://proceedings.mlr.press/v119/chen20v.html.

[11] Q. Li, Z. Han, and X. M. Wu, "Deeper insights into graph convolutional networks for semi-supervised learning," in Proceedings of the AAAI Conference on Artificial Intelligence, 2018, vol. 32, 1 ed., pp. 3538-3545, doi: 10.1609/aaai.v32i1.11604.

[12] J. Zhu, Y. Yan, M. Heimann, L. Zhao, L. Akoglu, and D. Koutra, "Heterophily and graph neural networks: Past, present and future," IEEE Data Engineering Bulletin, vol. 46, no. 2, pp. 84-97, 2023. [Online]. Available: https://par.nsf.gov/biblio/10435541.

[13] D. Luo et al., "Learning to drop: Robust graph neural network via topological denoising," in Proceedings of the 14th ACM International Conference on Web Search and Data Mining (WSDM), 2021, pp. 935-944, doi: 10.1145/3437963.3441734.

[14] O. Stretcu, K. Viswanathan, D. Movshovitz-Attias, E. Platanios, S. Ravi, and A. Tomkins, "Graph agreement models for semi-supervised learning," in Advances in Neural Information Processing Systems, 2019, vol. 32. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2019/hash/4772c1b987f1f6d8c9d4ef0f3b764f7a-Abstract.html.

[15] X. Li, "Finding global homophily in graph neural networks when meeting heterophily," in Proceedings of the 39th International Conference on Machine Learning (ICML), PMLR, 2022, vol. 162, pp. 13242-13256. [Online]. Available: https://proceedings.mlr.press/v162/li22ad.html.

[16] J. Klicpera, A. Bojchevski, and S. Günnemann, "Predict then propagate: Graph neural networks meet personalized PageRank," in Proceedings of the International Conference on Learning Representations (ICLR), 2019. [Online]. Available: https://arxiv.org/abs/1810.05997.

[17] M. Cuturi and A. Doucet, "Fast computation of Wasserstein barycenters," in Proceedings of the 31st International Conference on Machine Learning (ICML), PMLR, 2014, vol. 32, 2 ed., pp. 685-693. [Online]. Available: https://proceedings.mlr.press/v32/cuturi14.html.

[18] G. Peyré and M. Cuturi, "Computational optimal transport," Foundations and Trends in Machine Learning, vol. 11, no. 5-6, pp. 355-607, 2019, doi: 10.1561/2200000073.

[19] R. Sinkhorn and P. Knopp, "Concerning nonnegative matrices and doubly stochastic matrices," Pacific Journal of Mathematics, vol. 21, no. 2, pp. 343-348, 1967, doi: 10.2140/pjm.1967.21.343.

[20] H. Xu, D. Luo, H. Zha, and L. Carin, "Gromov-Wasserstein learning for graph matching and node embedding," in Proceedings of the 36th International Conference on Machine Learning (ICML), PMLR, 2019, vol. 97, pp. 6932-6941. [Online]. Available: http://proceedings.mlr.press/v97/xu19b.html.

[21] H. Han et al., "Node-wise filtering in graph neural networks: A mixture of experts approach," arXiv preprint, 2024. [Online]. Available: https://arxiv.org/abs/2406.03464.

[22] G. Pirrò, "Heterophily-aware Personalized PageRank for node classification," in Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI), 2025, pp. 6075-6083, doi: 10.24963/ijcai.2025/676.

[23] Y. Wang, Z. Wo, W. Wang, X. Fu, and M. Shao, "Leveraging Personalized PageRank and higher-order topological structures for heterophily mitigation in graph neural networks," in Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI), 2025, pp. 6506-6514, doi: 10.24963/ijcai.2025/724.

[24] K. J. Chen, W. Mu, and Z. Liu, "HeRB: Heterophily-resolved structure balancer for graph neural networks," arXiv preprint, 2025. [Online]. Available: https://arxiv.org/abs/2504.17276.

[25] J. Lin, X. Guo, S. Zhang, D. Zhou, Y. Zhu, and J. Shun, "When heterophily meets heterogeneity: Challenges and a new large-scale graph benchmark," in Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025, doi: 10.1145/3711896.3737421.

[26] X. Zheng et al., "Graph neural networks for graphs with heterophily: A survey," IEEE Transactions on Knowledge and Data Engineering, vol. 38, no. 7, pp. 4385-4404, 2026, doi: 10.1109/TKDE.2026.3680353.

[27] Y. Choi, J. Choi, T. Ko, J. Kim, and C. K. Kim, "Sheaf Graph Neural Networks via PAC-Bayes Spectral Optimization," in Proceedings of the AAAI Conference on Artificial Intelligence, 2026, vol. 40, 25 ed., pp. 20570-20578, doi: 10.1609/aaai.v40i25.39193.

[28] Y. Choi, T. Ko, J. Choi, and C. K. Kim, "Beyond Binary: Improving signed message passing in graph neural networks for multi-class graphs," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 47, no. 11, pp. 9535-9549, 2025, doi: 10.1109/TPAMI.2025.3581218.

[29] D. K. Hammond, P. Vandergheynst, and R. Gribonval, "Wavelets on graphs via spectral graph theory," Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129-150, 2011, doi: 10.1016/j.acha.2010.04.005.

[30] T. N. Kipf and M. Welling, "Variational graph auto-encoders," arXiv preprint, 2016. [Online]. Available: https://arxiv.org/abs/1611.07308.

[31] O. Platonov, "A critical look at the evaluation of GNNs under heterophily: Are we really making progress?," in Proceedings of the International Conference on Learning Representations (ICLR), 2023. [Online]. Available: https://arxiv.org/abs/2302.11640.

[32] G. PyTorch, "Planetoid dataset documentation," PyTorch Geometric documentation, 2026.

Publication Timeline

Published

Issue

Section

Articles

How to Cite

Ghods, S. (2026). Reproducing Confidence-Based Subgraph Matching for Heterophilic Graph Neural Networks: An Independent Reconstruction and Reproducibility Audit. Journal of Artificial Intelligence, Applications and Innovations, 1-19. https://aiaijournal.com/index.php/aiai/article/view/109