LGAN: An Efficient High-Order Graph Neural Network via the Line Graph Aggregation
This addresses the problem of inefficient and less interpretable high-order graph learning for researchers and practitioners in graph machine learning, offering a novel method with theoretical and empirical improvements.
The paper tackles the limitations of existing Graph Neural Networks (GNNs) in expressivity and computational cost by proposing LGAN, which uses line graph aggregation to achieve higher-order expressivity with lower complexity, outperforming state-of-the-art k-WL-based GNNs on benchmarks.
Graph Neural Networks (GNNs) have emerged as a dominant paradigm for graph classification. Specifically, most existing GNNs mainly rely on the message passing strategy between neighbor nodes, where the expressivity is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. Although a number of k-WL-based GNNs have been proposed to overcome this limitation, their computational cost increases rapidly with k, significantly restricting the practical applicability. Moreover, since the k-WL models mainly operate on node tuples, these k-WL-based GNNs cannot retain fine-grained node- or edge-level semantics required by attribution methods (e.g., Integrated Gradients), leading to the less interpretable problem. To overcome the above shortcomings, in this paper, we propose a novel Line Graph Aggregation Network (LGAN), that constructs a line graph from the induced subgraph centered at each node to perform the higher-order aggregation. We theoretically prove that the LGAN not only possesses the greater expressive power than the 2-WL under injective aggregation assumptions, but also has lower time complexity. Empirical evaluations on benchmarks demonstrate that the LGAN outperforms state-of-the-art k-WL-based GNNs, while offering better interpretability.