LGAN: An Efficient High-Order Graph Neural Network via the Line Graph Aggregation

• URL: http://arxiv.org/abs/2512.10735v1
• Date: Thu, 11 Dec 2025 15:23:46 GMT
• Title: LGAN: An Efficient High-Order Graph Neural Network via the Line Graph Aggregation
• Authors: Lin Du, Lu Bai, Jincheng Li, Lixin Cui, Hangyuan Du, Lichi Zhang, Yuting Chen, Zhao Li,
• Abstract summary: We propose a novel Graph Aggregation Network (LGAN) that constructs a line graph from the induced subgraph centered at each node to perform the higher-order aggregation.<n>We theoretically prove that the LGAN possesses the greater expressive power than the 2-WL under injective aggregation assumptions.<n> Empirical evaluations on benchmarks demonstrate that the LGAN outperforms state-of-the-art k-WL-based GNNs, while offering better interpretability.
• Score: 12.813630209382426
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Unifying approach to uniform expressivity of graph neural networks [4.640835690336653]
  Graph Neural Networks (GNNs) are often analysed via correspondence to the Weisfeiler-Leman (WL) algorithm and fragments of first-order logic.<n>Standard GNNs are limited to performing aggregation over immediate neighbourhoods or over global read-outs.<n>To increase their expressivity, recent attempts have been made to incorporate substructural information (e.g. cycle counts and subgraph properties)
  arXiv  Detail & Related papers  (2026-02-20T18:18:48Z)
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [29.47675861430167]
  We argue that using well-defined computational models, such as a modified CONGEST model with clearly specified preprocessing and postprocessing, offers a more sound framework for analyzing GNN expressiveness.<n>We show that allowing unrestricted preprocessing or incorporating externally computed features, while claiming that these precomputations enhance the expressiveness, can sometimes lead to problems.<n>Despite these negative results, we also present positive results that characterize the effects of virtual nodes and edges from a computational model perspective.
  arXiv  Detail & Related papers  (2024-10-02T08:01:50Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  We take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain.<n>We prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests [30.558563815430418]
  Subgraph neural networks (GNNs) have emerged as an important direction for developing expressive graph neural networks (GNNs) This paper conducts a systematic study of general node-based subgraph GNNs through the lens of Subgraph Weisfeiler-Lehman Tests (SWL) We prove that any node-based subgraph GNN falls into one of the six SWL equivalence classes, among which $mathsfSSWL$ achieves the maximal expressive power.
  arXiv  Detail & Related papers  (2023-02-14T14:42:54Z)
• A Practical, Progressively-Expressive GNN [27.267362661067285]
  Message passing neural networks (MPNNs) have become a dominant flavor of graph neural networks (GNNs) in recent years. MPNNs come with notable limitations; they are at most as powerful as the 1-dimensional Weisfeiler-Leman (1-WL) test in distinguishing graphs in a graph isomorphism testing frame-work. We propose the (k, c)(=)-SETWL hierarchy with greatly reduced complexity from k-WL, achieved by moving from k-tuples of nodes to sets with =k nodes defined over =c connected components in
  arXiv  Detail & Related papers  (2022-10-18T01:27:21Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels [25.736529232578178]
  Graph neural networks (GNNs) have achieved tremendous success in graph mining. MPGNNs, as the prevailing type of GNNs, have been theoretically shown unable to distinguish, detect or count many graph substructures. We propose GSKN, a GNN model with a theoretically stronger ability to distinguish graph structures.
  arXiv  Detail & Related papers  (2021-04-07T08:50:34Z)
• Breaking the Expressive Bottlenecks of Graph Neural Networks [26.000304641965947]
  Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to measure the expressiveness of graph neural networks (GNNs) In this paper, we improve the expressiveness by exploring powerful aggregators.
  arXiv  Detail & Related papers  (2020-12-14T02:36:46Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  We study tradeoffs of computational cost and expressive power of Graph Neural Networks (GNNs) We show that a new model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. In several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNNs.
  arXiv  Detail & Related papers  (2020-12-06T03:42:54Z)
• Learning to Drop: Robust Graph Neural Network via Topological Denoising [50.81722989898142]
  We propose PTDNet, a parameterized topological denoising network, to improve the robustness and generalization performance of Graph Neural Networks (GNNs) PTDNet prunes task-irrelevant edges by penalizing the number of edges in the sparsified graph with parameterized networks. We show that PTDNet can improve the performance of GNNs significantly and the performance gain becomes larger for more noisy datasets.
  arXiv  Detail & Related papers  (2020-11-13T18:53:21Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.