More Like this

1. Generative Risk Minimization for Out-of-Distribution Generalization on Graphs

   Wang, Song; Tan, Zhen; Zhu, Yaochen; Zhang, Chuxu; Li, Jundong (February 2025, Transactions on machine learning research)

   Out-of-distribution (OOD) generalization on graphs aims at dealing with scenarios where the test graph distribution differs from the training graph distributions. Compared to i.i.d. data like images, the OOD generalization problem on graph-structured data remains challenging due to the non-i.i.d. property and complex structural information on graphs. Recently, several works on graph OOD generalization have explored extracting invariant subgraphs that share crucial classification information across different distributions. Nevertheless, such a strategy could be suboptimal for entirely capturing the invariant information, as the extraction of discrete structures could potentially lead to the loss of invariant information or the involvement of spurious information. In this paper, we propose an innovative framework, named Generative Risk Minimization (GRM), designed to generate an invariant subgraph for each input graph to be classified, instead of extraction. To address the challenge of optimization in the absence of optimal invariant subgraphs (i.e., ground truths), we derive a tractable form of the proposed GRM objective by introducing a latent causal variable, and its effectiveness is validated by our theoretical analysis. We further conduct extensive experiments across a variety of real-world graph datasets for both node-level and graph-level OOD generalization, and the results demonstrate the superiority of our framework GRM. 

   more » « less
2. Improvements on Uncertainty Quantification for Node Classification via distance-based Regularization

   Alan Hart, Russell; Yu, Linlin; Lou, Yifei; Chen, Feng (December 2023, Thirty-seventh Annual Conference on Neural Information Processing Systems)

   Deep neural networks have achieved significant success in the last decades, but they are not well-calibrated and often produce unreliable predictions. A large number of literature relies on uncertainty quantification to evaluate the reliability of a learning model, which is particularly important for applications of out-of-distribution (OOD) detection and misclassification detection. We are interested in uncertainty quantification for interdependent node-level classification. We start our analysis based on graph posterior networks (GPNs) that optimize the uncertainty cross-entropy (UCE)-based loss function. We describe the theoretical limitations of the widely-used UCE loss. To alleviate the identified drawbacks, we propose a distance-based regularization that encourages clustered OOD nodes to remain clustered in the latent space. We conduct extensive comparison experiments on eight standard datasets and demonstrate that the proposed regularization outperforms the state-of-the-art in both OOD detection and misclassification detection. 

   more » « less
3. Subgraph Neural Networks

   Alsentzer, Emily; Finlayson, Samuel; Li, Michelle; Zitnik, Marinka (January 2020, Advances in neural information processing systems)

   null (Ed.)

   Deep learning methods for graphs achieve remarkable performance on many node-level and graph-level prediction tasks. However, despite the proliferation of the methods and their success, prevailing Graph Neural Networks (GNNs) neglect subgraphs, rendering subgraph prediction tasks challenging to tackle in many impactful applications. Further, subgraph prediction tasks present several unique challenges: subgraphs can have non-trivial internal topology, but also carry a notion of position and external connectivity information relative to the underlying graph in which they exist. Here, we introduce SubGNN, a subgraph neural network to learn disentangled subgraph representations. We propose a novel subgraph routing mechanism that propagates neural messages between the subgraph's components and randomly sampled anchor patches from the underlying graph, yielding highly accurate subgraph representations. SubGNN specifies three channels, each designed to capture a distinct aspect of subgraph topology, and we provide empirical evidence that the channels encode their intended properties. We design a series of new synthetic and real-world subgraph datasets. Empirical results for subgraph classification on eight datasets show that SubGNN achieves considerable performance gains, outperforming strong baseline methods, including node-level and graph-level GNNs, by 19.8% over the strongest baseline. SubGNN performs exceptionally well on challenging biomedical datasets where subgraphs have complex topology and even comprise multiple disconnected components. 

   more » « less
4. Controlling Neural Collapse Enhances Out-of-Distribution Detection and Transfer Learning

   Harun, MY; Gallardo, J; Kanan, C (July 2025, Proc. International Conference on Machine Learning (ICML))

   Out-of-distribution (OOD) detection and OOD generalization are widely studied in Deep Neural Networks (DNNs), yet their relationship remains poorly understood. We empirically show that the degree of Neural Collapse (NC) in a network layer is inversely related with these objectives: stronger NC improves OOD detection but degrades generalization, while weaker NC enhances generalization at the cost of detection. This trade-off suggests that a single feature space cannot simultaneously achieve both tasks. To address this, we develop a theoretical framework linking NC to OOD detection and generalization. We show that entropy regularization mitigates NC to improve generalization, while a fixed Simplex ETF projector enforces NC for better detection. Based on these insights, we propose a method to control NC at different DNN layers. In experiments, our method excels at both tasks across OOD datasets and DNN architectures. 

   more » « less
5. Implicit Subgraph Neural Network

   Zhong, Yongjian; Zhu, Liao; Vu, Hieu; Adhikari, Bijaya (July 2025, Forty-second International Conference on Machine Learning)

   Subgraph neural networks have recently gained prominence for subgraph-level predictive tasks, but existing methods either use simple pooling over graph convolutional networks that fail to capture essential subgraph properties or rely on rigid subgraph definitions that limit performance; moreover, they cannot model long-range dependencies between and within subgraphs—an important limitation given real-world networks’ diverse structures. To address this, we propose the first implicit subgraph neural network that captures dependencies across subgraphs and integrates label-aware subgraph-level information, formulating implicit subgraph learning as a bilevel optimization problem and introducing a provably convergent algorithm requiring fewer gradient estimations than standard bilevel methods, achieving superior performance on real-world benchmarks. 

   more » « less