Research map / Graph learning / GNN architectures
Graph Structure Inference with BAM: Neural Dependency Processing via Bilinear Attention
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a supervised neural network (BAM) that maps observational data matrices of arbitrary shape to a three-class edge classification (skeleton, moralized, no edge) using a bilinear attention mechanism on SPD covariance matrices, followed by a second network for v-structure/CPDAG orientation.
Problem
Graph structure inference from observational data: score-based and constraint-based methods scale poorly, need large samples, or depend on thresholds; existing supervised causal learners either predict edges separately or are limited to DAG outputs and fixed shapes.
Approach
A shape-invariant neural network with bilinear attention operating on covariance matrices in the SPD manifold (attention matrices act as adaptable weights on each covariance channel), with an SPD activation and Log-Eig layer, trained on Chebyshev-polynomial SEM data to predict skeleton/moralized/no-edge classes; orientation to CPDAG is handled by a second network over immoralities plus Meek rules.
Key results
- BAM consistently outperforms competing undirected graph estimators (PC, GLASSO, AVICI, etc.) across dependencies, dimensions and sample sizes on synthetic SEM data.
- Ablation: removing the bilinear attention layer raises loss from 0.173 to 0.202, and removing both bilinear and LogEig raises it to 0.271.
- For CPDAG estimation, selective immorality testing outperforms testing all moralizations (e.g., Chebyshev d=20 AUC 0.85 vs 0.69 at M=200).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Test only immoralities identified by the first network rather than testing all possible moralizations | BAM CPDAG estimation · CPDAG estimation, Chebyshev dependencies, M=200, d=10, 20, 50, 100 | AUC: d=10: 0.73 ± 0.03 -> 0.79 ± 0.09; d=20: 0.69 ± 0.02 -> 0.85 ± 0.05; d=50: 0.71 ± 0.02 -> 0.78 ± 0.05; d=100: 0.70 ± 0.01 | Helped |
| Test only immoralities identified by the first network rather than testing all possible moralizations | BAM CPDAG estimation · CPDAG estimation, Linear dependencies, M=200, d=10, 20, 50, 100 | AUC: d=10: 0.67 ± 0.03 -> 0.71 ± 0.06; d=20: 0.63 ± 0.06 -> 0.72 ± 0.02; d=50: 0.63 ± 0.04 -> 0.69 ± 0.06; d=100: 0.68 ± 0.03 | Helped |
| Test only immoralities identified by the first network rather than testing all possible moralizations | BAM CPDAG estimation · CPDAG estimation, sin dependencies, M=200, d=10, 20, 50, 100 | AUC: d=10: 0.63 ± 0.08 -> 0.69 ± 0.16; d=20: 0.62 ± 0.07 -> 0.68 ± 0.09; d=50: 0.60 ± 0.06 -> 0.62 ± 0.07; d=100: 0.64 ± 0.04 | Helped |
| Test only immoralities identified by the first network rather than testing all possible moralizations | BAM CPDAG estimation · CPDAG estimation, cos dependencies, M=200, d=10, 20, 50, 100 | AUC: d=10: 0.67 ± 0.07 -> 0.71 ± 0.04; d=20: 0.64 ± 0.05 -> 0.74 ± 0.05; d=50: 0.62 ± 0.07 -> 0.65 ± 0.11; d=100: 0.59 ± 0.05 | Mixed |
| Test only immoralities identified by the first network rather than testing all possible moralizations | BAM CPDAG estimation · CPDAG estimation, x3 dependencies, M=200, d=10, 20, 50, 100 | AUC: d=10: 0.58 ± 0.05 -> 0.56 ± 0.03; d=20: 0.50 ± 0.10 -> 0.55 ± 0.17; d=50: 0.56 ± 0.09 -> 0.54 ± 0.09; d=100: 0.57 ± 0.05 | Mixed |
| Add BAM (ablation) | FULL undirected graph estimation model · Undirected graph estimation, Chebyshev dependencies | loss: 0.202 ± 0.005 -> 0.173 ± 0.007 | Helped |
| Add BAM and LogEig (ablation) | −BAM −LogEig undirected graph estimation model · Undirected graph estimation, Chebyshev dependencies | loss: 0.271 ± 0.012 -> 0.173 ± 0.007 | Helped |
| Add observational attention (ablation) | −obs. att. undirected graph estimation model · Undirected graph estimation, Chebyshev dependencies | loss: 0.189 ± 0.006 -> 0.173 ± 0.007 | Helped |
| Add observational attention and dense layers (ablation) | −obs. att. −Dense undirected graph estimation model · Undirected graph estimation, Chebyshev dependencies | loss: 0.205 ± 0.006 -> 0.173 ± 0.007 | Helped |
Surprising findings
- In high-dimensional setting (d=100, M=50), no evaluated algorithm, including BAM, beat a zero-graph baseline in SHD for CPDAG estimation.
- Covariance-based SPD processing alone yields relatively good results, but the embedding layer's nonlinearity contributes, and direct SPD-space predictions without LogEig are problematic.
Limitations
- Undirected output only; directionality requires a second network and Meek rules, with less pronounced advantage in CPDAG estimation.
- Performance degrades on random Fourier feature and MLP dependencies in some regimes, and high-dimensional (d>M) CPDAG estimation remains poor.
- Training is on Erdos-Renyi graphs with Chebyshev SEMs; robustness under noise and confounding is untested.
Experimental setup
Datasets: Simulated Chebyshev-polynomial SEM data on Erdos-Renyi graphs Synthetic test dependencies (linear, sin, cos, x^2, x^3, MLP, random Fourier features) Alternative graph models (Watts-Strogatz, ERGM, configuration, geometric)
Benchmarks: synthetic SEM graphs with varied dependency functions, dimensions and sample sizes
Metrics: AUC accuracy SHD SID loss
Baselines: PC PC-HSIC RCoT RCIT CCDR GES GIES LiNGAM MMPC CAM SAM GLASSO
Builds on: AVICI GLASSO Kossen et al. axial attention for observational data SPD neural networks (SPDNet) Meek rules
Closest papers by meaning
- Out-of-Distribution Generalization on Graphs via Progressive Inference (AAAI 2025 · similarity 0.87)
- Quantifying Distributional Invariance in Causal Subgraph for IRM-Free Graph Generalization (NeurIPS 2025 · similarity 0.86)
- Neural Gaussian Similarity Modeling for Differential Graph Structure Learning (AAAI 2024 · similarity 0.86)
- Graph Contrastive Invariant Learning from the Causal Perspective (AAAI 2024 · similarity 0.86)
- A Graph Dynamics Prior for Relational Inference (AAAI 2024 · similarity 0.86)
- Contextual Structure Knowledge Transfer for Graph Neural Networks (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.