Scaling Graph Propagation Kernels for Predictive Learning.

Area of Science:

• Graph Neural Networks
• Machine Learning
• Data Mining

Background:

• Real-world data often exhibits graph structures, necessitating efficient relational information capture for analysis.
• Collective Classification (CC) aims to assign labels to nodes in a graph by leveraging their relationships.
• Current deep learning models for CC, often based on Weisfeiler-Lehman (WL) kernels, struggle to capture information from large node neighborhoods due to computational limits.

Purpose of the Study:

• To propose an efficient framework, I-HOP, for Collective Classification (CC) that scales to larger node neighborhoods.
• To overcome the limitations of existing differentiable graph kernels in capturing extensive relational information.
• To address the exponential decay of original node information in WL kernels with increasing neighborhood size.

Main Methods:

• Introduced I-HOP, a framework coupling differentiable kernels with iterative inference for scalable CC.
• Leveraged historical neighborhood summaries in each iteration to process larger neighborhoods efficiently.
• Developed a solution to mitigate the exponential decay of original node information in Weisfeiler-Lehman (WL) kernels.

Main Results:

• I-HOP demonstrated an exponential reduction in time and space complexity compared to standard differentiable graph kernels.
• The framework successfully captured and summarized information from larger neighborhoods iteratively.
• Extensive evaluations on 11 datasets confirmed improved results and robustness of the I-HOP framework.

Conclusions:

• I-HOP offers a scalable and robust solution for Collective Classification on graph-structured data.
• The iterative approach effectively addresses the neighborhood size limitations of traditional graph kernels.
• The proposed method enhances the ability to capture complex relational information in large graph neighborhoods.