Random Probing for Structural Self-Interactions in Graph Neural Networks

Saku Peltonen; H. Çağrı Bilgi; Kubilay Atasu

cs.LGOct 13, 2026

Random Probing for Structural Self-Interactions in Graph Neural Networks

Authors: Saku Peltonen, H. Çağrı Bilgi, Kubilay Atasu

Organizations: ETH Zurich · TU Delft

Abstract

Graph Neural Networks (GNNs) fundamentally lack the ability to capture structural properties defined by node self-interactions, such as cycle counts, subgraph centrality, and heat kernel signatures. Existing solutions often rely on computationally expensive higher-order architectures or hand-crafted features. In this work, we introduce DIAL, a message-passing layer that gives nodes access to graph structure through the diagonal of graph-derived operators. Our approach uses randomized probing to provide nodes with learnable, permutation equivariant access to diagonal entries. We prove that our approach can express important structural features, including cycle counts, subgraph centrality, and heat kernel signatures. The proposed method can be integrated directly into message passing layers. Experiments on molecular property prediction, cycle counting, and pattern detection demonstrate the effectiveness of DIAL across a range of graph learning tasks.

Figures & tables

Panel of Figure 1 — Figure 1: Message-passing view of Hutchinson’s diagonal estimator. We illustrate triangle counting for all nodes simultaneously using random probes and ordinary message passing. Left: The arrowed paths show a subset of length-3 messages received at $v_{1}$ and $v_{4}$ . After propagation, node $v$ observes $(A^{3}z)_{v}=\sum_{u}(A^{3})_{vu}z_{u}$ , which mixes self-returning messages with messages originating elsewhere. Without identifying information, standard message passing cannot isolate the diagonal term. Right: Hutchinson’s estimator correlates the propagated value with the original probe $z_{v}$ . Since $\mathbb{E}[z_{v}z_{u}]=0$ for $u\neq v$ and $\mathbb{E}[z_{v}^{2}]=1$ , the non-diagonal terms vanish in expectation, yielding $\mathbb{E}[z_{v}(A^{3}z)_{v}]=(A^{3})_{vv}$ . For an adjacency matrix, this diagonal entry counts length-3 closed walks at $v$ , i.e., twice the number of triangles incident to $v$ .

Figure 2: Graph-angle structural encodings compared to Laplacian positional encodings. Left : Laplacian PE represents node

i

\Phi_{i,:}

, the row of eigenvector coordinates (in practice only a subset). This captures relative position in the graph: nodes 0 and 1 are close to each other so their encodings are similar, whereas nodes 4 and 5 are in different components so their encodings can be very different. Right : graph angles represent node

i

((P_{\mu_{j}})_{ii})_{j=1}^{q}

, where

\mu_{1},\ldots,\mu_{q}

are the distinct (Laplacian) eigenvalues. Graph angles are an example of a structural encoding: unlike eigenvectors, graph angles assign the same representation to automorphic nodes (such as 4 and 5). They are also invariant to basis and sign choices.

Method	Test MAE
GCN [ 23 ]	$0.469\pm 0.002$
GIN [ 1 ]	$0.209\pm 0.018$
GSN with cycles [ 3 ]	$\boldsymbol{0.115\pm 0.012}$
GIN + random ID [ 1 ]	$0.279\pm 0.023$
SignNet (8 smallest) [ 5 ]	$0.1034\pm 0.0056$
SignNet (full) [ 5 ]	$0.0853\pm 0.0026$

Table 1: Test MAE for logP prediction on ZINC; lower is better. For SignNet, BasisNet, and SPE, “8 smallest” uses the eigenvectors corresponding to the eight smallest eigenvalues of the normalized Laplacian, whereas “full” uses the complete eigenbasis. Best within each block is bolded.

Method	Complexity		Synthetic (norm. MAE)
Method	Space	Time	3-Cycle	4-Cycle	5-Cycle	6-Cycle
Base GNN	$O(N)$	$O(LN\bar{d})$	0.3515	0.2742	0.2088	0.1555
ID-GNN [ 29 ]	$O(Ns)$	$O(LNs\bar{d})$	0.0006	0.0022	0.0490	0.0495
NGNN [ 30 ]	$O(Ns)$	$O(LNs\bar{d})$	0.0003	0.0013	0.0402	0.0439
GNN-AK+ [ 31 ]	$O(Ns)$	$O(LNs\bar{d})$	0.0004	0.0041	0.0133	0.0238
PPGN [ 8 ]	$O(N^{2})$	$O(LN^{3})$	0.0003	0.0009	0.0036	0.0071

Table 2: Normalized MAE for node-level cycle counting. Complexities assume fixed hidden width;

N

is the number of nodes,

\bar{d}

the average degree,

s

the maximum extracted subgraph size,

r

the number of probes,

L

the number of learned layers or blocks, and

K

the propagation depth. Inference space excludes graph storage. The lower block contains the random-probe methods; best results are bolded separately in the final two blocks. R-PEARL and DIAL are reported as mean

\pm

standard deviation.

Method	2-Cycle	3-Cycle	4-Cycle	5-Cycle	6-Cycle	S-G	B-C	Macro F1
R-PEARL [ 17 ]	$15.48\pm 7.59$	$41.21\pm 5.42$	$66.05\pm 0.52$	$55.13\pm 0.80$	$54.74\pm 0.60$	$70.54\pm 1.09$	$62.56\pm 2.49$	$52.24$
DIAL (Ours)	$\boldsymbol{91.07\pm 3.33}$	$\boldsymbol{82.44\pm 4.48}$	$\boldsymbol{79.72\pm 1.50}$	$\boldsymbol{72.10\pm 2.21}$	$\boldsymbol{74.83\pm 2.95}$	$\boldsymbol{78.68\pm 2.79}$	$\boldsymbol{66.07\pm 1.48}$	$\boldsymbol{77.84}$

Table 3: Pattern detection on synthetic directed graphs. We report minority-class F1 scores in percent for node-level binary labels; higher is better. The detected patterns include directed cycles of length

2

–

6

, scatter-gather motifs (S-G), and bicliques (B-C). Both methods use

K=4

and six learned probe-aggregation layers. Best in each column is bolded.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	#Graphs (train/val/test)	Avg. nodes	Avg. edges	Node inputs	Edge inputs
ZINC	10,000 / 1,000 / 1,000	23.16	49.83	Atom type (28 cat.)	Bond type (3 cat.)
Cycle counting	1,500 / 1,000 / 2,500	18.80	62.68	Constant	None
Directed pattern detection	1 / 1 / 1	8,192.00	23,630.67	Constant	None
CIFAR10 superpixels	45,000 / 5,000 / 10,000	117.63	941.07	RGB + coordinates (5D)	Spatial distance (1D)

Appendix

Table 4: Statistics and input features for the datasets with fixed train/validation/test splits. Average node and edge counts are computed over the full dataset. DrugOOD uses shift-dependent five-way splits and is described in the text.

Dataset	Epochs	Train (s/epoch)	Inference (s)	Total train (h)	Peak mem. (GiB)
ZINC	2000	$15.15\pm 0.03$	$0.91\pm 0.01$	8.42	9.94
Directed pattern detection	150	$0.171\pm 0.000$	$0.078\pm 0.000$	0.01	10.67
Cycle counting	2000	$1.191\pm 0.009$	$0.952\pm 0.011$	0.66	5.11

Appendix

Table 5: Per-epoch training and inference time for DIAL on each main benchmark used in the paper. Total training time is a projection, computed as the mean per-epoch training time multiplied by the reported number of training epochs.

		ID		OOD
Domain	Method	Val	Test	Val	Test
Assay	No PE	$\boldsymbol{92.92\pm 0.14}$	$92.89\pm 0.14$	$71.02\pm 0.79$	$71.68\pm 1.10$
	PEG	$92.51\pm 0.17$	$92.57\pm 0.22$	$70.86\pm 0.44$	$71.98\pm 0.65$
	SignNet	$92.26\pm 0.21$	$92.43\pm 0.27$	$70.16\pm 0.56$	$72.27\pm 0.97$
	BasisNet	$88.96\pm 1.35$	$89.42\pm 1.18$	$71.19\pm 0.72$	$71.66\pm 0.05$
	SPE	$92.84\pm 0.20$	$\boldsymbol{92.94\pm 0.15}$	$71.26\pm 0.62$	$\boldsymbol{72.53\pm 0.66}$

Appendix

Table 10: DrugOOD binding-affinity prediction results (AUROC, %). Baseline results are taken from Kanatsoulis et al. [17] and reported as mean

\pm

standard deviation over five seeds. Best point estimates for each domain are bolded.

Explore similar work

Structure-Feature Aligned Graph Learning via Alternating Constrained Optimization
Jul 13, 2026Chengcheng Yan, Qingsong WangGraph Neural Networks Graph Representation Learning
College of Artificial Intelligence, Shaoxing Institute of Technology, Shaoxing, 312000, China. · School of Mathematics and Computational Science, Xiangtan University, Xiangtan, 411105, China.
Invariant-Stratified Propagation for Expressive Graph Neural Networks
Mar 2, 2026Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe +1Graph Neural Networks GNN Expressivity
Department of Mechanical Engineering, University of Melbourne, Melbourne, Australia · School of Computing, Australian National University, Canberra, Australia · Data61, CSIRO, Canberra, Australia
Edge-Girth as a Structural Edge Feature for Graph Neural Networks
Sep 1, 2026Lilian Marey, Charlotte LaclauGraph Neural Networks Graph Representation Learning
LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France

Jul 13, 2026J/K move · Enter open · S save

Structure-Feature Aligned Graph Learning via Alternating Constrained Optimization

Chengcheng Yan, Qingsong Wang

College of Artificial Intelligence, Shaoxing Institute of Technology, Shaoxing, 312000, China. · School of Mathematics and Computational Science, Xiangtan University, Xiangtan, 411105, China.

Graph Neural Networks Graph Representation Learning Node Classification

Open paper AskPDF arXiv

We introduce a constrained two-view framework for node prediction that aligns structure-conditioned GNN embeddings with a structure-free feature prior learned by an anchor model. Conventional Graph Neural Networks (GNNs) couple feature transformation and neighborhood aggregation, which renders them vulnerable to topology noise and heterophilous connections. To decouple this dependency, our framework utilizes an independent anchor network to capture intrinsic attribute features via a self-supervised reconstruction objective. Furthermore, we propose a Channel-Split Adaptive Gated GNN (CSAG-GNN) that dynamically routes representations between global spectral smoothing and local spatial discrimination through a node-wise gating mechanism. We propose a stable cyclic alternating optimization strategy to solve the resulting coupled bi-level objective, preventing mutual representation drift during training. Empirical results on both homophilous and heterophilous benchmarks show balanced performance gains and structural robustness over competitive baselines.

Abstract

Explore similar work

Structure-Feature Aligned Graph Learning via Alternating Constrained Optimization

Invariant-Stratified Propagation for Expressive Graph Neural Networks

Edge-Girth as a Structural Edge Feature for Graph Neural Networks