Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· 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.
The definition of directed graph wide-sense stationarity is revisited, and the surrogate signals preserve covariance under the stationary assumption to demonstrate the feasibility of the scheme to detect irregular node covariance and benchmark the method against conventional schemes using the symmetrized graph.
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
This work proposes Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I), a discrete denoising diffusion model with a novel discrete inversion scheme that enables distribution-aware edits leveraging the whole domain edit space and qualitatively shows that GDCE-I attains interpretable in-distribution solutions.