TL;DR
This work proposes LIGR (Label Informativeness-Guided Rewiring), which maximizes an information-theoretic measure quantifying how much neighbors’ labels reveal about node labels, suitable for applications requiring interpretability (biological networks, social graphs).
Graph Neural Networks (GNNs) achieve strong predictive performance on graph-structured data across domains such as chemistry, biology, and network analysis, yet they provide no intrinsic explanation of their predictions. This limits their adoption in high-stakes and safety-critical settings. Counterfactual explanations address this by revealing the minimal structural modifications that would change a model's prediction. On graphs, however, such a modification is hard to produce. The search space is discrete and combinatorial, and a valid answer must respect categorical node and edge types together with domain rules such as chemical valency in the case of molecular graphs. Existing explainers give up one of two things. Either edits are not held on the data manifold, or the search does not span the full edit space. We propose Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I), which gives up neither. A discrete denoising diffusion model with a novel discrete inversion scheme enables distribution-aware edits leveraging the whole domain edit space. We further address the incomplete and inconsistent evaluation of graph counterfactuals by deriving a framework of explanation desiderata and applying it to every method under one shared protocol. Across four benchmarks, GDCE-I outperforms related work by a large margin on the defined framework. For the molecular domain, we further qualitatively show that GDCE-I attains interpretable in-distribution solutions.
The information flow in the graph neural networks (GNNs) is fundamentally constrained by over-squashing, where structural bottlenecks impede long range information propagation. Graph-rewiring methods, which modify graph topology, have been extensively used to alleviate this. However, existing approaches often introduce prohibitive structural and computational bottlenecks, fail to preserve the critical properties of original graphs, and increase the edge counts massively. We introduce a novel method Schreier-Coset Graph Rewiring , a group-theoretic rewiring method that augments the input graph with a Schreier-Coset graph derived from a special linear group. Our method provides theoretical guarantees, a graph that exhibits spectral gap and a bounded effective resistance, creating a low-resistance bypass for long-range communication. Empirical evaluations demonstrate that SCGR reduces effective resistance by 5-40% across various learning tasks, effectively mitigating connectivity bottlenecks while maintaining competitive accuracy.
Graph Neural Networks exhibit a puzzling numerical fragility under mixed-precision training, failing significantly more often than MLPs or CNNs. This failure is inherently tied to graph structure, with heterophilic graphs and high-degree nodes being particularly vulnerable. We identify the root cause as catastrophic cancellation during neighborhood aggregation. When neighboring node embeddings point in opposite directions, their sum collapses toward zero and amplifies floating-point errors by orders of magnitude. We formalize this through the cancellation ratio ?, proving that it is fundamentally governed by graph topology, including heterophily, node degree, and network depth. Consequently, we propose Aggregation-Aware Representation Learning (AARL) to learn numerically stable and cancellation-resistant representations without sacrificing expressiveness. Unlike naive approaches that enforce neighbor alignment and destroy discriminative power, AARL maintains representation diversity while ensuring numerically safe aggregation. Experiments on diverse benchmarks demonstrate that AARL substantially improves training stability under low precision while preserving or improving classification accuracy.
Building on GraphLawPH, the first knowledge graph of Philippine Republic Acts, this study benchmarks three graph neural network (GNN) architectures—GAT, GCN, and GraphSAGE—and compares them to a high-dimensional Legal-BERT baseline to determine their suitability for statutory legal embedding. Using a corpus of 12,124 Republic Acts linked by 3,721 citation edges, the researchers evaluate the models as high-fidelity semantic compressors that reduce dimensionality by 91.7% while maintaining extreme representational alignment. Performance was rigorously assessed on semantic similarity detection and community discovery using retrieval metrics and structural alignment scores. The results reveal a 3.1% graph-gain for GAT in semantic retrieval (MRR=0.7870) and a massive 2,680% modularity improvement for GCN (0.4227) over the text-only baseline (0.0152), meeting established benchmarks for substantial community structure. These findings resolve the Sparsity Paradox for the corpus’s 81.79% isolated nodes, proving that transferable inductive biases from the connected minority effectively preserve semantic integrity across the entire legal graph. This study provides the first empirical benchmark for Philippine statutory GNNs, delivering guidance for selecting architectures that balance local semantic precision with global structural coherence.
Graph classification plays a central role in many scientific disciplines. While classical kernel-based methods and graph neural networks achieve strong predictive performance, they often require substantial computational resources. Hyperdimensional Computing (HDC) has recently emerged as an efficient and noise-resilient alternative, providing lightweight models that are attractive for resource-constrained settings. Within this context, GraphHD is a representative HDC-based approach for graph classification; however, its encoding process can become costly on large graphs and its standard configuration relies on a single centrality choice (PageRank) for node-to-hypervector assignment. In this work, we go beyond PageRank in GraphHD by systematically evaluating alternative centrality measures (degree, closeness, betweenness, Katz, and eigenvector) and by introducing two new encoding variants. GraphHD-Level preserves quantitative structural information by mapping centrality values to level-hypervectors, whereas GraphHD-Order simplifies the algorithm by eliminating edge encoding and aggregating node hypervectors directly. Experiments on six widely used benchmarks from cheminformatics and bioinformatics (MUTAG, ENZYMES, PROTEINS, DD, NCI1, and PTC\_FM) show that replacing PageRank with alternative centralities yields similar F1-scores while offering notable runtime savings, and that GraphHD-Order remains competitive with the original GraphHD baseline while providing consistent speedups in encoding time.
Conformal prediction (CP) provides distribution-free uncertainty quantification, and its extension to graphs is an active research direction. Diffused Adaptive Prediction Sets (DAPS) is a widely used graph-aware diffusion baseline, propagating Adaptive Prediction Sets (APS) non-conformity scores along edges with a uniform coefficient $\lambda$. We identify a fundamental shortcoming of this design: the uniform low-pass diffusion presupposes graph homophily and proves detrimental on heterophilic graphs, enlarging the mean prediction-set size by up to 10.6% relative to plain APS. To mitigate this, we propose HeAD-CP, a family of node-wise diffusion variants whose coefficients are determined by a label-free local-homophily estimate derived from the GNN softmax. Three variants, namely signed-$\gamma$, edge-compatibility, and a DAPS-baseline-with-correction, are most effective at extreme heterophily, intermediate heterophily, and moderate-to-high homophily, respectively, and all preserve the marginal coverage guarantee. On ten benchmarks, the HeAD-CP family stays at or below plain APS on every dataset, while DAPS exceeds APS on six. The post-hoc oracle over the family improves over DAPS on 8/10 datasets at $p<0.01$ (paired Wilcoxon), with the largest gains on heterophilic graphs (10.3% on Texas); on the two homophilic datasets where DAPS still wins (CiteSeer, PubMed), it retains a marginal advantage of at most 0.002, statistically insignificant on CiteSeer ($p=0.23$). Designing a calibrated label-free selector that approaches this oracle is the main outstanding empirical question.