Rare Features on Graphs: Prune by Where They Sit, Not How Often They Occur

Many graph datasets describe each node with a long, sparse vector of word or token counts. Most of those words are rare: they appear on a handful of nodes, and many appear on only one. In ordinary text classification, the standard fix is to drop them with a count cutoff, and this works well. Graph neural networks (GNNs) complicate that rule. A GNN is a model that updates each node by repeatedly averaging it with its neighbors. That averaging erases differences between nearby nodes, and when many layers are stacked every node ends up looking the same, a failure called over-smoothing. Whether a rare word survives this averaging depends much less on how many nodes carry it than on where those nodes are. If five papers that cite one another share a rare word, that word is a coherent community marker, and averaging preserves it. If five unrelated papers scattered across the graph share it, averaging dilutes it to nothing. Before it disappears, it adds variance that makes the representation look diverse without helping prediction.

We propose to measure each input feature by two numbers, its occurrence count and its graph smoothness (how much its values change across edges). We will test whether the second number, not the first, decides which rare features help and which hurt, and whether the harm from graph-scattered features grows with depth. The practical output is a pruning rule applied to input columns before training. It needs one pass over the edges per feature, never touches the graph structure, and has a depth-dependent threshold derived from the averaging operator itself. It also yields a falsifiable prediction: on heterophilic graphs, where linked nodes tend to belong to different classes, the rule should reverse and keep exactly the scattered features that homophilic graphs should discard.

Core Claim

Let $x_j \in \mathbb{R}^N$ be column $j$ of the node feature matrix over $N$ nodes. Let $L = I - D^{-1/2} A D^{-1/2}$ be the normalized graph Laplacian, where $A$ is the adjacency matrix and $D$ the degree matrix. The feature's graph frequency is its Rayleigh quotient:

$$\lambda_j = \frac{x_j^\top L x_j}{x_j^\top x_j},$$

which is 0 for a feature constant across connected nodes and approaches 1 or more for a feature that flips across every edge. This number links the two senses of "frequency" in the research file. For a singleton feature on node $u$, $\lambda_j = e_u^\top L e_u = 1$ exactly (ignoring self-loops), so every singleton has the highest graph frequency a one-node signal can have. The singleton removal that Saif et al. found nearly free in text classification is therefore a special case of cutting high-$\lambda$ features. For a feature with count 2 or more, $\lambda_j$ separates co-located occurrences from scattered ones, and a count cutoff cannot draw that distinction.

For a linear propagation model such as Simple Graph Convolution, the output is $S^K X W$, where $S$ is the propagation matrix, $K$ the number of hops, and $W$ the weight matrix. Right-multiplication by $W$ commutes with the graph filter, so feature $j$ reaches the output with energy attenuated roughly as $(1-\lambda_j)^{2K}$, by the standard low-pass reading of $S$ (Luan et al.). Two consequences follow. First, features with large $\lambda_j$ contribute almost nothing at depth. They still take first-layer parameters and still add gradient noise, the same failure Kawahara et al. describe, where rare features accidentally co-occur with a label. Second, the $\lambda$ threshold worth keeping should fall as $K$ grows. Our central claim is that, at matched feature budgets on homophilic graphs, a smoothness-aware cutoff beats a count cutoff, and that the gap widens with depth.

Relation to Prior Work

The frequency-pruning literature motivates the question and constrains the design. Count-cutoff selection acts as regularization in maximum-entropy models (Wang). Higher document-frequency thresholds improve transfer across domains (Choi et al.). A minimum document frequency stops rare tokens from receiving explosive TF-IDF weights (STAVICTA Group). Keeping the top-$L$ most frequent molecular substructures beats hash folding and supervised selection (Dablander et al.). All of these treat rows as independent, and the research file flags that gap. We keep their central lesson, that simple unsupervised thresholds are hard to beat, and change the statistic being thresholded.

Korhonen et al. showed that raw relative-frequency thresholds beat hypothesis tests built on global averages. This is a real constraint, because an obvious refinement of our rule would compare $\lambda_j$ to its value under randomly placed occurrences. We therefore treat the raw-$\lambda$ threshold as the main method and the permutation-calibrated version only as a secondary variant that must earn its place.

The over-smoothing literature supplies the mechanism and the diagnostics. The filterbank GNN of Luan et al. adds a high-pass channel to aggregation and gains about 10% on Texas and Cornell. It defines frequency only on the spectrum of the embeddings and never asks which input columns carry high-frequency content. We ask exactly that, and we predict that on heterophilic graphs the high-$\lambda$ input features are the ones feeding its high-pass channel. PairNorm keeps total pairwise distance constant across layers and helps most when feature vectors are missing. It drops whole node vectors and never prunes columns. Zhang et al. show that effective rank of the representation matrix tracks accuracy far better than Dirichlet energy, and they warn that high rank is necessary but not sufficient. Our hypothesis gives a concrete instance of that warning: scattered rare features should inflate shallow-layer effective rank while contributing nothing to accuracy.

The closest work that connects the two directions is DYNAMO-GAT (Chakraborty et al., 2024; 2025; A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks). It prunes attention edges between nodes whose features are overly correlated, which destabilizes the collapsed state and lets networks reach 128 layers. It works on graph edges in latent space, needs node-by-node covariance, and acknowledges trouble on sparse graphs where pruning can disconnect components. Our method prunes input columns, costs one pass over the edges per column, and never alters connectivity. The two interventions are complementary, and we will test them together.

Research Program

The first stage is descriptive. For Cora, Citeseer, Pubmed and CoauthorCS, all of which carry bag-of-words or keyword features, we compute $(\text{count}_j, \lambda_j)$ for every column and map the joint distribution. This answers a question the literature has not asked: within a fixed count, how widely does graph smoothness vary? If rare features all sit at high $\lambda$, count and smoothness are redundant and the project reduces to confirming count cutoffs on graphs. We will report that outcome as a negative result. Our expectation is that counts of 2 to 10 span nearly the full $\lambda$ range, because citation neighborhoods share specialized vocabulary.

The second stage is interventional. We split features into quadrants (rare or common, crossed with smooth or scattered) and remove each quadrant in turn at matched column counts. For every removal we measure test accuracy and the layer-wise effective rank and numerical rank from Zhang et al., across depths 2, 4, 8, 16, 32 and 64 for GCN, GAT and SGC.

The third stage turns the findings into a rule. We keep a feature if $\lambda_j < \tau(K)$, with a count floor of 1 as the only frequency component. The threshold follows the attenuation argument above: $\tau(K)$ is chosen so that $(1-\tau)^{2K}$ equals a fixed retained-energy fraction $\epsilon$. That leaves a single hyperparameter $\epsilon$ shared across depths. For heterophilic graphs we test the mirrored rule, which keeps features with high $\lambda_j$ and routes them to a high-pass channel.

Baselines

The naive reference point is training on the full feature matrix with no pruning, at each depth. It shows how much the long tail costs at all.

The strongest competitor on the pruning question is a tuned document-frequency cutoff. This is the rule Saif et al. and Wang found effective, and it is the Sort & Slice principle of Dablander et al. applied to words. We sweep its threshold over the same grid as $\epsilon$, choose it on the same validation split, and compare at identical retained column counts. We found no reported result on Lacuna for count-cutoff pruning of Cora or Citeseer features in GNNs, so we will produce this number ourselves. Beating it means higher mean test accuracy at matched budget, outside the seed-to-seed spread, at depths of 8 or more, with no loss at depth 2.

A random column-pruning baseline at the same budget checks that any gain is not simply the effect of fewer inputs. The key ablation compares smoothness-only pruning against count-only pruning against the joint rule. It isolates whether $\lambda_j$ carries information beyond the count.

For the over-smoothing question, the strongest reported methods are the following. On Cora, DYNAMO-GAT reports 83.21% accuracy (Chakraborty et al., 2024) and stable accuracy up to 128 layers. For missing features, PairNorm with SGC reaches 74.5% on Cora versus 42.3% for vanilla SGC (Zhao & Akoglu). On Texas and Cornell, the filterbank GNN improves GCN by roughly 10% (Luan et al.). We rerun PairNorm, the filterbank GNN, an initial-residual GCN, and DYNAMO-GAT where code permits, on the same splits and with the same tuning budget, both with and without our pruning.

We do not expect column pruning alone to beat DYNAMO-GAT at 128 layers. The claim to test is additive: pruning on top of each method raises its accuracy at every depth, and matches DYNAMO-GAT's depth robustness at a fraction of its cost when combined with PairNorm.

Why not just…?

Why not just use a count cutoff, since it already removes singletons? This is the main threat, because every singleton already has $\lambda = 1$. If count and $\lambda$ are strongly correlated in the stage-one map, or the joint rule does not beat the tuned count cutoff at matched budget, the smoothness criterion adds nothing and we will say so. The rule can only win on features that occur 2 to 10 times, so we report accuracy separately for pruning decisions in that band, where the two rules disagree.

Why not just compress the features with PCA or SVD? A dense projection mixes smooth and scattered columns into every component, so it cannot remove the scattered ones. Dablander et al. found that frequency slicing beat more complex selection methods. We add PCA to the matched output dimension, and a "graph-aware PCA" that applies SVD to $SX$, as baselines. If the graph-aware PCA matches our rule, the useful ingredient is prefiltering the features rather than selecting them, and the proposal should be reframed around that.

Why not just add residual connections or PairNorm and leave the features alone? Both keep embeddings from collapsing, but neither removes input noise. Zhao & Akoglu report little peak-accuracy gain on feature-rich graphs, and Chakraborty et al. argue that residuals do not change convergence to the collapsed state. The factorial design of pruning crossed with each fix tests this directly. If pruning adds nothing once PairNorm or residuals are present, the contribution is diagnostic only.

Why not just prune edges, as DYNAMO-GAT does? Edge pruning risks disconnecting sparse graphs (Chakraborty et al., 2025) and needs node-pair covariance. Column pruning avoids both problems. Whether the two are redundant is an empirical question that the combined runs answer.

Proposed Experiments

The decisive homophilic test covers Cora, Citeseer, Pubmed and CoauthorCS. We run GCN, GAT and SGC at depths 2 through 64, with 10 seeds each on the standard splits. Pruning methods are compared at retained-column fractions of 25%, 50% and 75%. The prediction is that the joint rule beats the count cutoff by a margin that grows with depth. A flat or shrinking margin refutes the depth mechanism.

The rank test uses the same runs. We predict that removing the scattered-rare quadrant lowers effective rank at layers 1 and 2 but raises accuracy, whereas removing the smooth-rare quadrant lowers both. That pattern would show rank inflation without useful information, the failure mode Zhang et al. warn about.

The reversal test runs on Texas and Cornell with GCN and the filterbank GNN. If removing high-$\lambda$ features hurts there, while removing them helps on the homophilic graphs, the effect is spectral and not a generic denoising effect. The missing-feature test repeats the PairNorm protocol on Cora and Citeseer, with pruning applied to the observed nodes' features.

Finally, we report the wall-clock cost of computing all $\lambda_j$ against DYNAMO-GAT's covariance step on Pubmed. We do not extend the method to ogbn-arxiv, whose features are dense embeddings with no occurrence counts. There we test only whether smoothness-based selection of embedding dimensions carries over.