Jan 2025· IEEE Transactions on Pattern Analysis and Machine Intelligence· Vol PP· 2 citations· 55 references
MedicineComputer Science
TL;DR
DeltaGNN is introduced, to the best of the authors' knowledge, among the first scalable (featuring linear computational and memory complexity overhead) and generalizable (capable of effectively handling graphs with diverse homophily, density, and topology) architectures for long-range and short-range interaction detection.
Abstract
Graph Neural Networks (GNNs) are popular deep learning models designed to process graph-structured data through recursive neighborhood aggregations in the message passing process. When applied to semi-supervised node classification, the message-passing enables GNNs to understand short-range spatial interactions, but also causes them to suffer from over-smoothing and over-squashing. These challenges hinder model expressiveness and prevent the use of deeper models to capture long-range node interactions (LRIs) within the graph. Popular solutions for LRIs detection are either too expensive to process large graphs due to high time complexity or fail to generalize across diverse graph structures. To address these limitations, we propose a mechanism called information flow control, which leverages a novel connectivity measure, called information flow score, to address over-smoothing and over-squashing with linear computational overhead, supported by theoretical evidence. Building on this mechanism, we introduce DeltaGNN, to the best of our knowledge among the first scalable (featuring linear computational and memory complexity overhead) and generalizable (capable of effectively handling graphs with diverse homophily, density, and topology) architectures for long-range and short-range interaction detection. We benchmark our model across 10 real-world datasets, including graphs with varying sizes, topologies, densities, and homophilic ratios, showing superior performance with limited computational complexity.
This work proposes a novel Adaptive Dual-level Collaborative GNN associated with an adaptive dual-level collaborative mechanism, and shows that the ADC-GNN can inject the learned high-level information back into the node level, forming a closed-loop, bidirectional optimization process.
Graph neural networks typically propagate information through repeated message-passing layers, coupling the distance over which information travels with the number of nonlinear transformations applied. This coupling can make deep architectures difficult to optimize and can lead to over-smoothing, over-squashing, and the loss of long-range information. Linearized Graph Sequence Models (LGSMs) address this issue by separating information depth from processing depth and treating the successive propagation states of each node as a sequence. However, existing LGSMs construct these sequences using fixed graph operators, limiting their ability to adapt propagation to the input graph, node features, and downstream task. We introduce HOPPER, an end-to-end learnable extension of LGSM that learns how hop sequences should be extracted before they are processed by a modern state-space model. Our framework supports feature-conditioned, structure-aware, graph- and hop-adaptive propagation mechanisms while preserving permutation equivariance. Standard adjacency-based and non-backtracking LGSM sequences arise as special cases of our proposed extractor family. We show that HOPPER is state-of-the-art or competitive across the ECHO-Synth benchmark, and that varying the maximum neighborhood size of message backtracking cancellation (i.e. structural memory window) can optimize accuracy on the LRIM physics-based long-range dependency benchmark. These results demonstrate that learnable sequence extraction provides a flexible and effective approach to long-range graph representation learning.
CoRe-GNN is proposed, which performs both propagations in parallel at each layer: a coarsened inter-cluster term capturing long-range structure, and a local intra-cluster term preserving per-node discriminability.
Antonin Joly, Nicolas Keriven, Aline Roumy· 0 citations
Study of the efficacy of GNN layers in a slew of regression contexts from rank ordering, error minimization and insight extraction shows that deep convolutional GNNs, particularly GEN, are more effective at these tasks than attention-based GNNs, while other classical, theoretically-inspired GNNs remain competitive and efficient.
Keith G. Mills, Aedan J. DeFrates, Joong Ho Kim· arXiv.org· 0 citations
A Hypergraph-enhanced graph contrastive learning framework for Graph Out-Of-Distribution detection (termed HGOOD), which constructs two branches to hierarchically mine graph compact semantics in a comprehensive manner and introduces a cross-branch prototype contrast that aligns the captured graph patterns with their cross-branch clustering prototypes to enhance the semantic manifold of the in-distribution graph.
Xuan-Ting Fan, Chenyu Wang, Yue-Yue Gao et al.· 0 citations
This work proposes $\partial$lift (DiffLift), a general framework for learning graph liftings to hypergraphs and cellular- and simplicial complexes in an end-to-end fashion and shows that $\partial$lift outperforms existing lifting methods on multiple benchmarks for graph and node classification across different TNN architectures.
J. L. Franco, Gabriel Duarte, Alexander Nikitin et al.· 2 citations
A weeklong summer workshop brought higher education faculty to campus to explore how AI and machine learning materials can be adapted for their classrooms.
