Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· pp. 3895-3906· 0 citations· 38 references
TL;DR
This work proposes a novel and practical framework for dependence testing in labeled graphs via mutual information over a structure-weighted joint label distribution and demonstrates that the proposed test is a statistically sound and an effective tool for uncovering nontrivial dependencies in graph data.
Abstract
Many real-world systems—ranging from protein structures to financial networks—are naturally represented as labeled graphs, where both topology and node attributes carry critical information. A fundamental question in analyzing such data is whether two graphs (or subgraphs) exhibit statistical dependence, which may indicate shared generative mechanisms or latent interactions. Unlike classical dependence testing, the graph setting introduces unique challenges: dependence can manifest through structural similarity, label correlation, or their interplay, potentially reinforcing or obscuring each other. We propose a novel and practical framework for dependence testing in labeled graphs via mutual information over a structure-weighted joint label distribution. This approach jointly captures topological and attribute-based signals while remaining robust to imperfect or noisy node alignments. We provide theoretical guarantees with explicit error bounds and validate our method on both synthetic and real-world datasets, including protein structures from the lipocalin family, and recurring motifs in the Cora citation network. Our results demonstrate that the proposed test is a statistically sound and an effective tool for uncovering nontrivial dependencies in graph data.
Directed networks arise across biological, social, informational, and engineered systems, yet most analyses treat directedness as a binary property: a network is either a directed acyclic graph (DAG) or it is not. This binary classification obscures the rich spectrum of hierarchical, recurrent, and modular structure present in real systems. In this paper, we empirically evaluate the DAG-ness framework, a four-component measure that quantifies acyclicity, flow alignment, cyclic locality, and pathway complexity across a corpus of 107 networks drawn from twelve structurally diverse domains. Rather than aligning with traditional disciplinary boundaries, our results reveal unexpected cross-domain convergence: diverse systems resolve into four universal structural archetypes. We find that macroscopic acyclicity is pervasive even in feedback-rich systems, and that domains as disparate as neural connectomes and abstract informational networks frequently converge on identical topological constraints. These findings demonstrate that DAG-ness provides a unified, interpretable, and domain-agnostic lens for understanding the hidden laws of directed structure in complex systems.
Non-parametric statistical testing is based on surrogate data generation that randomizes chosen features in the empirical data. In the graph setting, graph signal processing (GSP) brings forward versatile schemes; e.g., to preserve smoothness of graph signals as measured by the Dirichlet energy. However, how to deal with directed graphs remains an active area of research. We begin by revisiting the definition of directed graph wide-sense stationarity. The surrogate signals preserve covariance under the stationary assumption. We demonstrate the feasibility of the scheme to detect irregular node covariance and benchmark our method against conventional schemes using the symmetrized graph. We also investigate how the level of asymmetry affects the detection performance, thus assessing the advantages of the presented approach. Finally, we show results for a real-world graph extracted from the Freeman EIES social network dataset.
Chun Hei Michael Chan, Alexandre Cionca, D. Ville· 0 citations
Tabular data are central to many real-world applications, yet deep learning models often underperform compared to tree-based methods due to limited relational inductive bias. We propose a unified framework that models each tabular instance as an instance-level statistical feature graph to enable learning with Graph Neural Networks (GNNs). In this representation, features are treated as nodes, and edges encode pairwise statistical relationships derived from Z-score similarity, covariance, Pearson correlation, or Euclidean distance. This formulation explicitly captures inter-feature dependencies rather than relying solely on implicitly learned interactions. We evaluate the framework across four classification and four regression datasets spanning diverse domains and feature dimensionalities. Results demonstrate competitive and, in several cases, superior performance compared to strong baselines including Random Forests, XGBoost, and multilayer perceptrons. Correlation- and covariance-based edge constructions consistently provide robust performance across tasks. Furthermore, empirical analysis indicates that performance gains become more pronounced in higher-dimensional datasets, suggesting that graph-based representations are particularly effective at modeling complex feature interactions. Overall, this work provides a systematic examination of statistical graph construction for tabular learning and highlights the potential of GNNs as a structured alternative to conventional tabular models.
Shashank Parmar· 2026 International Conferenc...· 0 citations
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).
Rucha Bhalchandra Joshi, Subhankar Mishra· Data mining and knowledge di...· 0 citations
Many real-world processes can be represented as compositions of functions along a directed acyclic graph (DAG). In causal modelling, these correspond to the underlying mechanisms; in engineering, to multiple fidelity levels; and in gene-regulatory networks, to transcription factors. These functions are partially observed across the DAG, with noisy and heterogeneously sampled measurements, posing significant challenges for reconstruction, uncertainty propagation, and inference. To tackle these challenges, we place priors over functions and naturally arrive at Deep Gaussian Processes over DAGs. We theoretically study their prior-collapse behaviour, and the effect of graph topology and intermediate observations on the preservation of information. We obtain almost-sure lower bounds on the asymptotic frequency of depths at which the distinction between inputs is preserved, identify broad kernel classes for which these hold, and prove an observation by \cite{dunlop2018} on the role of input connections. We offer a structured variational approximation that retains graph dependencies, preserves compositional uncertainty, and captures the explaining-away behaviour of colliders. Finally, we empirically validate our theoretical results and our methodology, and model a latent-collider DAG, a protein signalling network, and a multi-fidelity heavy-ion collision emulation task, attaining state-of-the-art performance while recovering low-fidelity contributions and yielding interpretability of the simulator hierarchy.
Federico L Perlino, Oliver Hamelijnck, A. M. Johansen et al.· 0 citations
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.