Empirical Performance of Edge-Level Ego-Network Augmented MP-GNNs on Strongly Regular Graphs

Abstract

Abstract: We present a novel edge-level ego-network encoding for learning on graphs that can boost Message Passing Graph Neural Networks (MP-GNNs) by providing additional node and edge features or extending message-passing formats. The proposed encoding is sufficient to distinguish Strongly Regular Graphs, a family of challenging 3-WL equivalent graphs. We show theoretically that such encoding is more expressive than node-based sub-graph MP-GNNs. In an empirical evaluation on four benchmarks with 10 graph datasets, our results match or improve previous baselines on expressivity, graph classification, gr

Research Question

What is the empirical performance difference between MP-GNNs augmented with edge-level ego-network encodings and standard MP-GNNs on downstream tasks involving strongly regular graphs, evaluated using metrics such as classification accuracy and convergence speed?

Verification Level

Descriptive public verification status only; aggregate claim counts are public, but individual claim records are not exposed here.

Truth-Engine Gate Verdict

This record has not completed Gate 2 of the verification pipeline (a type-checked Lean4 proof for mathematical claims, or a sealed-sandbox reproduction for empirical claims). It is a literature synthesis only. VERIFIED requires an attached reproducible artifact (Lean4 proof source, or repro script and results) before this status can be set; it is not derived from review score or claim count.

Quality Tier

Descriptive public triage only; this tier does not alter current publication or DOI behavior.

Quality Dimensions

Automated triage signals derived from public fields; not human peer review or independent validation.

Correction Record

Public corrections are additive records. Current status does not claim the synthesis is error-free.

Provenance