Uncertainty-Constrained Trustworthiness for Graph Learning

Graph learning has been increasingly deployed in critical and sensitive domains, raising pressing demands for trustworthiness-robustness, fairness, and beyond. However, these properties are often undermined by various perturbations, which induce distributional uncertainty and compromise the trustworthiness of graph learning. To address this, we propose DICT, a novel framework that models distributional uncertainty to achieve trustworthy graph learning. Specifically, DICT formulates a unified optimization objective that captures perturbation-induced distributional shifts in graph topology, node features, and labels, and minimizes the worst-case risk over the uncertainty set. However, directly optimizing this objective in its primal form leads to an infinite-dimensional problem. To make this problem tractable, we integrate strong duality and local Lipschitz continuity of the loss, reformulating the objective as a finite-dimensional min-max problem. We focus on robustness and fairness as primary instantiations of DICT because they are not only critical in real-world applications, but also provide transferable modeling principles for broader trustworthiness objectives. By formulating fairness in the form of an uncertainty set, DICT pioneers unified robustness and fairness within a single optimization framework. Extensive experiments across diverse benchmarks and backbones demonstrate that DICT consistently improves both robustness and fairness, validating the effectiveness and adaptability of the DICT framework.

Graph learning has become an important tool for making predictions from connected data, such as social networks, financial records, and healthcare graphs. However, real-world graphs are often noisy and incomplete, with missing links, imperfect node information, or uncertain labels. Such perturbations can make real-world data differ from the data used for training, making trustworthy prediction difficult. We propose DICT, a framework that treats these perturbations as uncertainty in the data distribution. Instead of training a graph model only on the observed graph, DICT asks the model to perform well under a family of nearby possible graphs. To make this practical, we convert this worst-case training problem into a simpler objective that penalizes models that are too sensitive to small changes in graph structure, node features, and labels. Our results show that DICT improves both robustness and fairness across multiple graph datasets and model architectures. This matters because trustworthy graph learning should not only make accurate predictions, but also remain robust and fair when real-world data are noisy, incomplete, or biased.