Letting Attention Decide Which Motif Shortcuts to Keep

Graph neural networks pass messages along edges, one pair of nodes at a time. They therefore miss structure that involves several nodes at once, such as triangles, feed-forward loops or small rings. A common fix is to add "motif edges", which connect two nodes whenever they sit together inside a small recurring pattern. The literature disagrees about what these extra edges do once networks get deep. One camp finds that motif edges act as shortcuts. They shrink the graph's effective diameter and make every node's representation converge to the same vector sooner. This collapse is called over-smoothing. That camp therefore deletes every motif edge that is not also a real edge. The other camp diffuses information along all motif edges and reports that this reduces over-smoothing. Both camps make the keep-or-delete decision once, by hand, for every edge of a given type.

We propose to make that decision learned and local. The model starts from a broad dictionary of candidate motif types: all connected 3- and 4-node patterns. It then learns two things end to end. The first is a sparse gate per motif type, which acts as automated motif discovery. The second is a per-edge attention weight, meaning a content-dependent weight on each neighbor's message. Crucially, the per-edge score draws on both node features and the edge's motif-membership counts, so it does not depend on features alone. The central question is empirical and falsifiable. When attention is allowed to keep or suppress each motif shortcut, does it recover the hand-built rule that deletes all non-edge shortcuts, does it keep all of them, or does it find a selective middle ground that resists over-smoothing better than either?

Core Claim

Our claim is that motif shortcuts are neither good nor bad as a class. Each one is a candidate long-range edge, and whether it helps depends on whether it links nodes with the same label. The deciding signal should come from structure, not from features alone. Graph Attention is Not Always Beneficial proves that attention computed purely from node features helps only when structural noise exceeds feature noise. When features are noisy, it amplifies the corruption, which the authors call the "broken filter" regime. Motif shortcuts are exactly a source of structural noise. A feature-only attention layer placed over the union of real and motif edges should therefore fail where it is most needed. Our scoring function mixes a feature term with a term computed from motif-membership counts, through a learned per-node gate. If the claim holds, three things should follow. The learned retention pattern should differ measurably from the hard mask used by A Sparse-Motif Ensemble Graph Convolutional Network against Over-smoothing. Accuracy at 16 to 32 layers should degrade no faster on the motif-augmented graph than on the base graph. The structural term should matter most precisely when feature noise is high.

The scoring rule is the one place where notation helps. Let $c_{ij} \in \mathbb{R}^M$ count how many instances of each of the $M$ candidate motif types contain both node $i$ and node $j$. Let $\pi \in [0,1]^M$ be the learned per-type gates. Let $\mathbf{W}$, $\mathbf{a}$ and $\mathbf{h}$ be the usual projection, attention vector and node states. Let $\phi$ be a small multilayer perceptron, and let $g_i \in [0,1]$ be a per-node gate predicted from $\mathbf{h}_i$. The unnormalized score on a candidate edge $(i,j)$ is

$$e_{ij} = g_i \,\mathrm{LeakyReLU}\big(\mathbf{a}^T[\mathbf{W}\mathbf{h}_i \,\|\, \mathbf{W}\mathbf{h}_j]\big) + (1-g_i)\,\phi(\pi \odot c_{ij}).$$

These scores are softmax-normalized over $i$'s neighborhood in the union graph. Any edge whose gated counts $\pi \odot c_{ij}$ are all zero and that is not in the original adjacency drops out entirely. A hard-concrete sparsity penalty, a standard way to learn near-binary gates by gradient descent, pushes most entries of $\pi$ to zero. The surviving motif types are the "discovered" motifs.

Relation to Prior Work

Three lines of work motivate the gap without filling it. The first applies motifs against over-smoothing with fixed operators. SMEGCN (Jiang et al.) runs degree-normalized convolutions over triangle and chain channels. It prunes every non-edge shortcut with $\mathbf{A} \odot \mathbf{A}_k$, an element-wise product that keeps a motif edge only if it is also a real edge, and it scales to 30 layers. GCN-MPPR instead diffuses predictions with a precomputed personalized-PageRank matrix built from seven triangle motifs and keeps all shortcuts. Both fix the motif set by hand and both are content-blind. Our proposal tests the boundary between them rather than choosing a side.

The second line combines motifs with attention, but only to pool whole subgraphs. MA-GCNN and SUGAR weight whole subgraphs against each other for graph classification. DeepGraph reaches 48 layers in a Graph Transformer by masking some attention heads to handcrafted substructures, and it names automated substructure discovery as an open problem. None of the three weights individual node-to-node messages along motif edges.

The third line is closest. hpGAT blends feature similarity with a structural proximity term inside attention, which is the same mixing idea we use. Its structure comes from global matrix-factorization communities, however, and it avoids depth by staying at two layers. We reuse its mixing idea. We change the structural source to local, gated motif counts, and we study the deep regime it avoids.

Two papers constrain the design. The broken-filter result above is the reason for the structural term. Revisiting Over-smoothing in Graph Neural Networks shows that shallow models still win on Cora and Citeseer, and that stacking anti-smoothing tricks can hurt. We therefore treat feature-rich citation graphs as a sanity check, not as the main arena. Are we measuring oversmoothing in graph neural networks correctly? warns that Dirichlet energy alone is a poor proxy. Graph Substructure Networks supplies the motif-counting machinery we reuse for $c_{ij}$.

Research Program

We will build the candidate edge set from all connected 3-node patterns (open path, triangle) and 4-node patterns (path, star, cycle, tailed triangle, chordal cycle, clique). Counts come from orbit counting of the kind used in Graph Substructure Networks, precomputed once per graph. Edges gated off at test time can be pruned for inference. We will measure the cost honestly and report wall-clock time against GCN-MPPR's reported timings. The model stacks the layer above with residual connections. Understanding convolution on graphs via energies shows such connections are needed before a network can enter a sharpening rather than smoothing regime.

The analysis has three parts. The first is a retention audit. For each trained model and each depth, we record the attention mass placed on real edges, on motif edges that are also real edges, and on non-edge shortcuts. We split the shortcut mass by whether the shortcut joins same-label or different-label nodes. This directly answers whether attention learns the hard mask, keeps everything, or learns a label-aligned subset.

The second part is a smoothing profile. For each depth, we track Dirichlet energy, mean pairwise distance and per-layer linear-probe accuracy. The probe guards against the measurement critique, because a frozen linear classifier on each layer shows whether class information survives even when the distance metrics look collapsed.

The third part is a motif-recovery test on contextual stochastic block models, the synthetic graph family used by Ma and Zhang, in which labels and noisy Gaussian features are planted on a random graph. We additionally plant a label-informative motif type, for example 4-cycles within classes, among distractor motifs. We then check whether $\pi$ selects it as structural and feature noise are varied independently.

Baselines

The do-nothing reference is a residual GCN and a residual GAT on the original adjacency at matched depth. These show what motifs add at all. GAT's reported Cora accuracy is 83.0% (Graph Attention Networks). We include Cora only as a shallow-regime check, and expect a two-layer model to remain competitive there.

The strongest motif-plus-over-smoothing competitor is SMEGCN with its hard sparse-motif mask. It reports 80.39% accuracy on Wisconsin, against 74.51% for its best baseline (Jiang et al.). We will rerun it, not just quote it, under three settings: its native triangle and chain channels, the same 3- and 4-node dictionary we use, and our splits and tuning budget. That way, any gain cannot come from a bigger dictionary alone. Beating it means higher mean accuracy over ten splits on the heterophilic graphs at the best depth for each method, with non-overlapping confidence intervals. On Wisconsin specifically, it also means exceeding the 80.39% figure under SMEGCN's own protocol.

For the keep-all-shortcuts camp we rerun GCN-MPPR. It reports about 93.4% on Amazon Photo against 91.1% for PPNP (GCN-MPPR). Beating it means matching or exceeding that accuracy at comparable training time.

Two depth-oriented baselines use the missing-feature protocol. PairNorm reports 74.5% on Cora with all features missing on unlabeled nodes, against 42.3% for vanilla SGC (PairNorm). DSGNN reports 77.1% on Pubmed with missing features at 10 layers (Revisiting Over-smoothing). Both will be run on our backbone.

Three ablations isolate the key ingredient. The first is feature-only attention over the full union graph, which sets $g_i = 1$. The second is structure-only scoring, which sets $g_i = 0$. The third replaces learned $\pi$ with all gates fixed at one. Every method gets the same hyperparameter search budget: the same number of random-search trials, the same depth grid of 2, 4, 8, 16 and 32 layers, and the same GPU type. No reported result was found on Lacuna for any attention-over-motif-edges node classifier, so these ablations are where the comparison is genuinely new.

Why not just…?

Why not just use SMEGCN's hard mask with a larger motif dictionary and learned channel weights? This is the most serious threat. It is cheap and already shown to scale to 30 layers. A learned per-channel weight, in the style of the pattern ensemble in PXGL, also gives a form of motif selection. The mask, however, makes it impossible for any non-edge shortcut to carry information, even one that links same-label nodes several hops apart. That may be exactly what heterophilic and missing-feature graphs need. The retention audit settles the question. If our model's attention on non-edge shortcuts falls to near zero and accuracy matches the masked dictionary baseline, the hard mask was right and we will report that. The proposal claims a gain only if label-aligned shortcuts receive substantial mass and that mass buys accuracy at depth.

Why not just run GAT over the union of real and motif edges? This is our first ablation. Ma and Zhang's analysis predicts it will work when features are clean and break when features are noisy, because its scores depend only on the features (Graph Attention is Not Always Beneficial). The synthetic sweep over feature noise, together with the missing-feature protocol, tests this directly. If the ablation matches the full model even at high feature noise, the structural term is unnecessary and the contribution shrinks to "motif edges plus GAT".

Why not just append motif counts as node features to a shallow GAT and skip depth entirely? This approach from Graph Substructure Networks adds the same expressivity, and shallow models often win, as Elinas and Bonilla report. We include it as a baseline with the same dictionary. Our answer is limited to regimes where receptive field matters. Count features describe a node's own neighborhood but cannot move information from distant same-label nodes. The missing-feature and heterophilic settings are where this should show. If the shallow count-feature GAT wins there too, deep motif propagation is not worth its cost.

Why not just add DropEdge or PairNorm to a motif GCN? DropEdge drops edges uniformly, so it removes useful and destructive shortcuts at the same rate. PairNorm rescales features without deciding which messages to send. Both will be combined with the all-gates-on motif GCN. Because combinations of anti-smoothing tricks have been shown to interfere, each will be reported alone as well as in combination.

Proposed Experiments

The main node-classification suite has two parts. The heterophilic part covers Wisconsin, Texas, Cornell and Chameleon. The homophilic and large part covers Cora, Citeseer, Pubmed, Amazon Photo, Amazon Computers, CoauthorCS and ogbn-arxiv. Each runs at depths 2 through 32 under the standard protocol and under the missing-feature protocol, with ten splits each. Training time and memory are reported next to accuracy.

We also include a transfer check across domains, motivated by the claim in Wu that the useful motifs differ by domain. We train on PPI, where GAT reports micro-F1 0.973, and on social graphs, then compare which motif types survive the gates. Different domains should select different patterns, such as cycles in biological graphs and cliques in social ones. If the same types survive everywhere, the gates are not discovering anything domain-specific.

Three checks decide the outcome. On the synthetic block models, learned gates must recover the planted motif type above chance, and the structural term's share $1-g$ must rise as feature noise rises. On the real heterophilic graphs, accuracy at 16 or more layers must drop by no more on the motif-augmented graph than on the base graph, while a residual GCN on the same augmented graph should drop faster, replicating SMEGCN's shortcut-acceleration finding. Finally, the full model must beat the masked-dictionary SMEGCN baseline in the heterophilic or missing-feature regime at matched budget. If the third check fails while the retention audit shows near-zero shortcut mass, we will report the result as evidence that the hard mask is close to optimal. That would itself resolve the disagreement between SMEGCN and GCN-MPPR.