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

Jul 13, 2026

Structure-Feature Aligned Graph Learning via Alternating Constrained Optimization

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.

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

Ask PDF

Mar 2, 2026

Invariant-Stratified Propagation for Expressive Graph Neural Networks

Graph Neural Networks (GNNs) face fundamental limitations in expressivity and capturing structural heterogeneity. Standard message-passing architectures are constrained by the 1-dimensional Weisfeiler-Leman (1-WL) test, unable to distinguish graphs beyond degree sequences, and aggregate information uniformly from neighbors, failing to capture how nodes occupy different structural positions within higher-order patterns. While methods exist to achieve higher expressivity, they incur prohibitive computational costs and lack unified frameworks for flexibly encoding diverse structural properties. To address these limitations, we introduce Invariant-Stratified Propagation (ISP), a framework comprising both a novel WL variant (ISP-WL) and its efficient neural network implementation (ISPGNN). ISP stratifies nodes according to graph invariants, processing them in hierarchical strata that reveal structural distinctions invisible to 1-WL. Through hierarchical structural heterogeneity encoding, ISP quantifies differences in nodes' structural positions within higher-order patterns, distinguishing interactions where participants occupy different roles from those with uniform participation. We provide formal theoretical analysis establishing enhanced expressivity beyond 1-WL, convergence guarantees, and inherent resistance to oversmoothing. Extensive experiments across graph classification, node classification, and influence estimation demonstrate consistent improvements over standard architectures and state-of-the-art expressive baselines.

Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe +1

Department of Mechanical Engineering, University of Melbourne, Melbourne, Australia · School of Computing, Australian National University, Canberra, Australia · Data61, CSIRO, Canberra, Australia

Graph Neural Networks GNN Expressivity

Ask PDF

Sep 1, 2026

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

Graph neural networks (GNN) based on message passing are provably no more powerful than the one-dimensional Weisfeiler--Leman colour-refinement test (1-WL): two graphs it cannot tell apart receive identical representations, however deep or wide the network. A common remedy augments node or edge features with precomputed structural descriptors, most often counts of a fixed small subgraph such as triangles or longer cycles, but such counts require committing in advance to the size of the substructure counted, a choice usually made blind to the data. We study a descriptor that avoids this choice. The edge-girth of an edge is the length of a shortest cycle through it, and its multiplicity is the number of such shortest cycles; together they form a per-edge invariant that reports cycles of arbitrary length, computable exactly by a single breadth-first search per edge. Injected into a gated message-passing architecture, EGAGNN, it reaches a test MAE a factor three below the closest gated comparator on the ZINC-12k regression benchmark at 104k parameters; against bounded cycle-counting descriptors under the same architecture, it matches only a dictionary counting cycles up to length eight, using twice as many channels, while a dictionary capped at length four performs no better than no structural information at all. On graph discrimination we prove a matching limitation: on graphs where every edge sees the same number of shortest cycles of the same length, the descriptor becomes constant and any model built on it collapses back to the 1-WL bound. This holds without exception across all 400 pairs of the BREC benchmark: not one of the 90 such pairs is distinguished.

Lilian Marey, Charlotte Laclau

LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France

Graph Neural Networks Graph Representation Learning GNN Expressivity

Ask PDF