Learning Edge-Dependent Vertex Weights from Node Features with Random Features

Many datasets are hypergraphs: networks whose "edges" join any number of nodes, such as all the authors of a paper or all the documents that contain a word. Treating every member of such a group as equally important throws information away. A known fix is to give each node a weight that depends on which group it sits in (an edge-dependent vertex weight). With these weights, random walks, clustering and ranking on the hypergraph stop collapsing into ordinary pairwise graphs. The fix has a practical catch. Every published use takes the weights from hand-made metadata, such as author order, game scores or tf-idf. Most attributed hypergraphs have no such metadata, so the better model goes unused.

We propose to compute these weights from node features. A node's weight in a group measures how typical the node is of the other members, scored with a nonlinear similarity function (a kernel). We compute the score with random Fourier features, a standard trick that replaces a kernel with short explicit feature vectors. Each group is then summarized by one averaged vector, and every node-in-group weight becomes a single inner product. The cost grows with the number of node–group memberships rather than the square of group size. That matters because the groups where roles differ most, like common words or big collaborations, are also the largest ones.

Core Claim

A node's typicality within a hyperedge, under a Gaussian kernel and with the node left out of its own group's average, is a useful default edge-dependent vertex weight. It makes the existing walk and spectral methods usable on attributed hypergraphs without metadata. Random features make it cheap, and their error guarantee is of the kind these methods need. Concretely, let $z(x)\in\mathbb{R}^m$ be the random Fourier feature map of node features $x$. Let $\mu_{e\setminus v}=\frac{1}{|e|-1}\sum_{u\in e,u\neq v} z(x_u)$ be the average feature vector of hyperedge $e$ with $v$ removed. We define

$$\gamma_e(v)=\max\big(\tau,\ \langle z(x_v),\,\mu_{e\setminus v}\rangle\big)^{1/T},$$

where $\tau>0$ is a small floor that keeps weights positive, since the random-feature estimate can go negative, and $T$ is a temperature controlling how uneven the weights are. All $\mu_e$ are computed in one pass, and the leave-one-out version is a rank-one correction. Total cost is therefore $O(\mathrm{nnz}\cdot m)$, where nnz is the number of node–hyperedge memberships. Exact within-edge kernels cost $O(\sum_e |e|^2 d)$ for feature dimension $d$.

The weights differ across hyperedges because each $\mu_e$ differs. That is exactly the condition under which Random Walks on Hypergraphs with Edge-Dependent Vertex Weights shows the walk becomes non-reversible and escapes the clique-graph collapse.

The error argument is simple. Optimal Rates for Random Fourier Features bounds the uniform error $\|k-\hat k\|_\infty$ on a compact domain by $O(\sqrt{\log|S|}/\sqrt{m})$. Because this holds simultaneously for all pairs of points, every one of the nnz weights inherits the same additive error without a union bound over memberships. With the floor $\tau$, transition probabilities then have relative error $O(\sqrt{\log|S|}/(\tau\sqrt{m}))$. Standard Markov-chain perturbation arguments carry that error into the stationary distribution and the second eigenvector used by HyperClus-G, scaled by the chain's conditioning.

Why Not Linearize the Walk Itself

The combination suggested by the research file is to write the non-reversible walk as an asymmetric kernel and approximate it with Random fourier features for asymmetric kernels. That paper builds paired source and target feature maps for asymmetric kernels on continuous vectors.

We reject this idea. The edge-dependent walk operator is already factored as a sparse node-to-edge matrix times a sparse edge-to-node matrix. Its matrix–vector products, power iteration for the stationary distribution, and Lanczos iterations for eigenvectors all cost $O(\mathrm{nnz})$ per step. There is no dense Gram matrix for random features to remove. The "stationary distribution bottleneck" noted by Chitra and Raphael is a matter of iterations, not of density.

The genuine open problem in that paper is a different one: the weights themselves are heuristic. Inhomogeneous Hypergraph Clustering with Applications motivates the setting, since roles within predator–prey motifs mattered on the Florida Bay food web. It also constrains the design, because its submodular projections become expensive for large hyperedges, and any learned-weight scheme must avoid per-edge work that grows with the square of edge size.

The closest kernel-hypergraph work does not address weights at all. Hypergraph Modeling via Spectral Embedding Connection contracts an even-order uniform tensor kernel to an $n\times n$ Gram matrix. A Simple Hypergraph Kernel Convolution based on Discounted Markov Diffusion Process diffuses features over a hypergraph whose edges are uniform groups. Neither assigns roles to nodes within edges; we use kernels to create the weights, not to replace the walk.

The nearest methodological cousin is Adaptive Personalized Federated Learning via Multi-task Averaging of Kernel Mean Embeddings. It compresses per-client distributions into random-feature averages in order to weight collaboration between clients. We reuse that averaging technique, with the average taken inside each hyperedge and the output being vertex weights rather than client weights.

Research Program

The work has three parts.

First, we build the weight generator. Its kernel bandwidth is chosen by a self-supervised criterion that does not use the downstream objective. For held-out memberships, typicality should rank true members of a hyperedge above random non-members, scored by AUC. We also offer a multi-bandwidth variant, which samples frequencies from a mixture of spectral densities as in How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets. This addresses the known dependence of random-feature quality on bandwidth choice.

Second, we plug the weights, without modification, into three consumers:

  1. the two-step non-reversible walk for ranking and semi-supervised classification (Chitra and Raphael);
  2. HyperClus-G spectral clustering (Hypergraphs as Weighted Directed Self-Looped Graphs);
  3. the weighted splitting-function cuts of Hypergraph cuts with edge-dependent vertex weights, where the concave penalty keeps submodularity for any positive weights.

Third, we prove the perturbation bound sketched above and check empirically that the eigenvector and stationary-distribution error shrink with $m$ at the predicted $m^{-1/2}$ rate.

Baselines

The naive reference is uniform weights. This is the edge-independent case that Chitra and Raphael prove reduces to a clique graph. On Halo 2 the clique graph gave 61.1% versus 71.1% for metadata-based weights in their paper. Halo 2 has no node features, so it serves as a reminder of the size of the achievable gap rather than as a test bed.

The strongest weight competitor is hand-crafted metadata weights where they exist, namely tf-idf on 20 Newsgroups as used by Zhu and Segarra. That paper reports that these weights beat all-or-nothing and cardinality-based splitting, but no reported numerical result found on Lacuna for 20 Newsgroups accuracy. We will rerun it in the same pipeline. Matching tf-idf with no metadata would count as success; exceeding it would be a bonus.

The strongest end-to-end competitor for semi-supervised classification is GHSC / H-GCNII from Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs. That work reports 97.8% on ModelNet40 and state-of-the-art results on Cora, DBLP and Pubmed, though no per-dataset number for those citation benchmarks is found on Lacuna. We also compare against SHKC, reported at about 74% in its deep-diffusion setting. We will run each with its published hyperparameter grid and give our pipeline the same grid size. Beating GHSC is not required. We do require that feeding our weights into GHSC's operator improves it, since that operator currently needs $Q_1\propto Q_2$.

Two ablations isolate the key ingredients. The first uses exact Gaussian typicality computed pairwise inside each hyperedge; it has identical weights in expectation, so it isolates the approximation and the cost. The second uses linear typicality, the cosine to the leave-one-out centroid in raw feature space; it isolates the nonlinearity. We will also report symmetrized-walk variants.

Why not just…?

Why not just use cosine similarity to the hyperedge centroid in raw feature space? This is the real threat. It costs the same $O(\mathrm{nnz}\cdot d)$, and with high-dimensional sparse text features a linear kernel may already be adequate. Our linear-typicality ablation tests exactly this. If it matches the Gaussian version across benchmarks, we will report that the contribution is the leave-one-out typicality weighting itself and that random features are unnecessary. We expect a gap mainly on low-dimensional dense features, such as UCI data and ModelNet40 embeddings, where cluster shapes are nonlinear.

Why not just compute exact kernels within each hyperedge? For small hyperedges this is fine, and it is our accuracy ceiling. The cost grows with $|e|^2$, however, and word hyperedges in 20 Newsgroups and large co-citation groups in Pubmed are where roles differ most. We will report wall-clock time and memory against edge size, and weight error against $m$. This shows where the crossover lies rather than assuming random features always win.

Why not just learn the weights with attention inside a hypergraph neural network? With enough labels, end-to-end learning may win on classification, and we will say so if it does. But attention requires labels and a trained network. Clustering (UCI, food web) and ranking (ArnetMiner) have no labels. Neural oversmoothing is also documented: HGNN falls from about 69% to about 26% at 64 layers in SHKC. We present our weights as the unsupervised default and test them as an input to GHSC.

Why not just symmetrize the walk and use ordinary random features? Symmetrization discards direction. AsK-RFFs lost about 5% on letter when symmetrizing. HyperClus-G's authors show that symmetrized analyses produced incorrect Cheeger inequalities. The symmetrized variant stays in our tables as a check that the non-reversibility our weights create actually matters.

Proposed Experiments

Clustering. On the UCI suite (Mushroom, Zoo, Digit, Letter, Car, Covertype), we run HyperClus-G with uniform, linear, exact-Gaussian and random-feature weights. We report NCut and F1 in the paper's protocol; no numerical HyperClus-G values were found on Lacuna, so all runs will be ours. We repeat the comparison on the Florida Bay food web with InH-partition's functional-similarity measure, using species attributes where available.

Text. 20 Newsgroups uses documents as nodes and words as hyperedges. It is the head-to-head test against tf-idf weights, using latent semantic embeddings as node features to avoid reusing tf-idf directly.

Classification. On co-authorship and co-citation versions of Cora, Citeseer, Pubmed and DBLP, and on ModelNet40 k-nearest-neighbour hypergraphs, we run semi-supervised classification with the non-reversible walk and with GHSC under each weighting.

Ranking. ArnetMiner author ranking compares our weights against author-order weights.

Scaling. We sweep $m$ from 16 to 4096 and plot weight error, stationary-distribution error and eigenvector angle against $m$. The prediction is a $m^{-1/2}$ slope; a flatter slope would falsify the conditioning argument.

Decisive checks. The proposal succeeds if three things hold together. Learned weights must beat uniform weights by a margin comparable to the gaps these papers report for metadata weights. They must come within noise of tf-idf on 20 Newsgroups. And they must beat linear typicality on at least the dense-feature benchmarks at equal cost. If the second holds but the third fails, the paper becomes a simpler and still useful result: centroid typicality suffices, and the kernel machinery is unnecessary.