Dynamic Graph Neural Networks (DGNNs) suffer from a significant scalability bottleneck due to high computational demands resulting from their innate design to aggregate information both over graph topology and over time. While graph coarsening has successfully mitigated these costs for static graph neural networks, its potential remains largely untapped in the dynamic setting. Bridging this gap is particularly challenging because different DGNN architectures in literature aggregate information across structural topologies and temporal dimensions in different manners. %Hence, we require a coarsening method that can adapt to the complexity of a system evolving over time in different manners. In this work, we first group popular DGNNs into two general categories based on their topological and temporal message passing patterns. We then derive appropriate coarsening criteria for both classes of DGNNs with a goal to maximize the connectivity in the coarsened graph. Specifically, we aim to maximize the spectral gap of a generalized combinatorial Laplacian matrix in each case. In order to determine the quality of the candidate node-pairs to merge in an efficient manner, we derive an estimated change in eigenvalues from first principles using the Matrix Perturbation Theory. This leads to a naturally efficient algorithm Spectral-gap Aware Coarsening of Dynamic networks (SACoD). Experimental results demonstrate that our coarsening technique significantly accelerates dynamic GNN training and inference without compromising predictive performance, offering a practical path toward scalable dynamic graph learning.
Hieu Vu, Rares-Mihail Neagu, Bijaya Adhikari· Proceedings of the 32nd ACM...· 0 citations
Contrastive Conformal HGNN (CCF-HGNN) is proposed that accounts for uncertainty in hypergraph-based models by explicitly regularizing on the hypergraph structure for guaranteed and robust uncertainty estimates.
Akash Choudhuri, Bijaya Adhikari· Proceedings of the 32nd ACM...· 0 citations
Hypergraph representation learning has gained immense popularity over the last few years due to its applications in real-world domains like social network analysis, recommendation systems, biological network modeling, and knowledge graphs. However, hypergraph neural networks (HGNNs) lack rigorous uncertainty estimates, which limits their deployment in critical applications where the reliability of predictions is crucial. To bridge this gap, we propose Contrastive Conformal HGNN (CCF-HGNN) that accounts for uncertainty in hypergraph-based models by explicitly regularizing on the hypergraph structure for guaranteed and robust uncertainty estimates. CCF-HGNN accounts for epistemic uncertainty in HGNN predictions by producing a prediction set that leverages the topological structure and provably contains the true label with a pre-defined coverage probability. It also accounts for aleatoric uncertainty by leveraging contrastive learning on the structure of the hypergraph. To enhance the power of the predictions, CCF-HGNN performs an additional auxiliary task of hyperedge degree prediction with an end-to-end differentiable sampling-based approach. Extensive experiments on real-world hypergraph datasets demonstrate the superiority of CCF-HGNN by improving the efficiency of prediction sets while maintaining valid coverage.
Akash Choudhuri, Bijaya Adhikari· Proceedings of the 32nd ACM...· 0 citations
Experimental results demonstrate that the coarsening technique significantly accelerates dynamic GNN training and inference without compromising predictive performance, offering a practical path toward scalable dynamic graph learning.
Hieu Vu, Rares-Mihail Neagu, Bijaya Adhikari· Proceedings of the 32nd ACM...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
