Feature-Centric Unsupervised Node Representation Learning Without Homophily Assumption

AI summary

Overview

Research area: Graph machine learning — specifically unsupervised node representation learning, with a focus on graphs that violate the homophily assumption (i.e., graphs where connected nodes tend to be dissimilar).

Technical level: Intermediate. The paper assumes familiarity with graph neural networks, graph convolution, and basic clustering/embedding concepts, though its core idea is explained in intuitive terms.

Scope: The paper proposes FUEL, an unsupervised method that adaptively learns how much graph convolution to apply to node features so that learned embeddings separate latent (feature-derived) classes — without requiring node labels or homophily.

What This Paper Is About

Graph convolution mixes a node's features with those of its neighbors, which helps when connected nodes are similar (homophilic graphs) but hurts when they are not, because dissimilar neighbors get pushed toward similar embeddings. In supervised settings, models can learn how much graph convolution to use by minimizing a task loss, but in unsupervised settings there are no labels to guide that choice. This paper's goal is to learn an appropriate degree of graph convolution usage without labels, by using node features to define proxy "latent classes" and optimizing the embeddings so those proxies become cohesive internally and separated from each other.

Key Contributions

1. A clustering-based proxy for class separability. The authors introduce latent-class separability — the degree to which clusters found in feature space are internally cohesive and mutually distinct — as a stand-in for true class separability when labels are unavailable. They support this both empirically (correlation analysis on real graphs) and theoretically (a theorem showing an equivalence in ordering under stated conditions).

2. FUEL, an unsupervised method without a homophily assumption. FUEL is a two-step pipeline: Step 1 learns the weights of an adaptive graph convolution model via a specialized clustering scheme; Step 2 refines the resulting embeddings with a feed-forward network plus a skip connection to further improve latent-class separability.

3. Extensive empirical validation. The paper reports experiments with 14 unsupervised baseline methods plus input features alone ("Naive X"), across 14 real-world benchmark graphs spanning 8 non-homophilic and 6 homophilic datasets, on two downstream tasks: node classification and node clustering.

4. Ablation and design-goal analysis. Variants removing Step 1, Step 2, the skip connection, and the exponential loss function are evaluated to isolate each component's contribution.

Main Findings

• Latent-class separability tracks class separability. Across Cora and Citeseer (homophilic) and Actor and Cornell (non-homophilic), using 100 embeddings generated with randomly sampled, normalized graph convolution coefficients, Spearman rank correlation values exceeded 0.82 between latent-class separability (measured with the Calinski–Harabasz index) and class separability (measured by linear classifier test accuracy). Fitted linear regression lines had positive slopes. Nodes were split into 10% for training and 90% for testing.

• A theoretical ordering result holds. Theorem 1 states that, when either n₀ = n or both w and w′ lie in [max((n − 2n₀)/(2n − 2n₀), 0), 1], class separability is greater for one graph convolution coefficient than another if and only if the latent-class separability ordering agrees.

• FUEL achieves the best average ranking in node classification. Among the methods compared in Table 1, FUEL records the best average ranking (2.4). It obtains the best result on both the least homophilic graph reported (Texas, edge homophily 0.057, accuracy 84.6) and the most homophilic one (Photo, edge homophily 0.849, accuracy 94.2).

• FUEL achieves the best average ranking in node clustering. Using K-Means with K set to the number of unique labels and NMI as the metric, FUEL again records an average ranking of 2.4 and the best results on both Texas (40.8) and Photo (71.3), mirroring the classification pattern.

• FUEL's advantage is reported for 10 of 14 settings. The contributions section states FUEL is superior to baseline methods in 10 out of 14 settings across the two downstream tasks.

• Several baselines ran out of GPU memory. Tables 1 and 2 mark several entries as "O.O.M." (out-of-GPU memory), notably for GraphCL, MVGRL, GAE, HGRL, DSSL, GREET, NeCo, HLCL, PolyGCL, and HeterGCL on datasets such as Penn94 and Flickr. For graphs with |V| > 4 × 10⁴, the authors state they use scalable techniques.

• Two design goals are demonstrated. Figure 3 shows that FUEL's learned graph convolution weights vary with the level of graph homophily, and that the refinement step increases the latent-class separability of the intermediate embeddings.

• Ablations. Removing Step 1, Step 2, the skip connection ("w/o SK"), or the exponential loss ("w/o Exp") each degrades the average ranking relative to full FUEL (average rankings 8.3, 8.6, 5.5, and 6.1 respectively in Table 1, versus 2.4 for FUEL), although "w/o SK" exceeds FUEL on a few individual datasets.

• Not reported. The provided text is truncated in the middle of Section 5.4, so the detailed results for RQ3 (design-goal achievement) and RQ4 (component necessity) beyond the tables and Figure 3 captions are not fully available here. Exact per-epoch training times and total compute budgets are also not reported in the visible content.

Methodology in Plain English

The authors start from a simple intuition: since node features carry class-related information regardless of how the graph is wired, nodes with similar features should belong to the same class, forming clusters in feature space. They call these clusters "latent classes."

Their adaptive graph convolution model combines three terms — the raw features, a one-hop mixed version, and a two-hop mixed version — with weights α₀, α₁, α₂ that sum to 1. These weights are produced by applying softmax to three free parameters (c₀, c₁, c₂), so they can be learned by gradient descent.

Training in Step 1 uses three losses. The first (ℒ₁) encourages each node to have a confident assignment to a single cluster. The second (ℒ₂) pushes the average cluster-assignment distribution toward uniform so all nodes do not collapse into one cluster. The third (ℒ₃) is a distance loss that increases the mean distance between nodes assigned to different clusters relative to the mean distance within clusters. The combined objective is ℒ_clus = ℒ₁ + ℒ₂ + λℒ₃, and it optimizes both the softmax weights and learnable cluster centroids. The optimized weights then produce intermediate embeddings H.

Step 2 takes H and passes it through a small feed-forward network with a skip connection (Z = f_θ(H) + H), so the essential information in H is preserved. The refinement model is trained with a distance loss (ℒ_dist) that pulls nearest neighbors in the H space closer together and pushes other pairs apart, scaled by a temperature parameter τ and wrapped in an exponential so the overall loss behaves like a geometric average.

Evaluation follows a two-stage protocol: obtain embeddings with each method, then train an MLP classifier on them for node classification, or run K-Means on them for clustering. Each dataset–method pair is run for 10 trials, varying initialization and splits. Hyperparameters are tuned on a validation set.

Why This Matters

Impact on research. This work targets a real gap: the degree of graph convolution is heavily tuned in supervised graph learning but largely unexplored in unsupervised settings. By showing that an unsupervised, feature-derived proxy correlates (and, under conditions, provably orders) with true class separability, the paper offers a reusable principle for unsupervised method design — including for graphs where homophily does not hold. It also adds a theoretical result that is often missing from empirically driven graph representation papers.

Real-world applications. The paper does not enumerate deployments, but the problem setting maps naturally onto:

• Fraud and anomaly detection in transaction or review graphs, where fraudulent actors connect to legitimate ones and connectivity is therefore non-homophilic.
• Recommendation on social and e-commerce graphs, where user–item or user–user links may not imply similar attributes.
• Molecular and biological network analysis, where chemically distinct entities are frequently linked by reaction or interaction edges.
• Citation and co-authorship networks, where a paper's features (topic, venue) may differ from those of the papers it cites.

Industry relevance. The method requires no labels, which matters when annotation is expensive, and it reuses the same embeddings for both classification and clustering. Reported applicability across graphs from 183 to 167,343 nodes and homophily levels from 0.11 to 0.85 makes it relevant to production pipelines where graph structure varies widely across domains. Baseline failures marked "out-of-GPU memory" on datasets like Penn94 and Flickr also highlight a practical scaling concern the authors explicitly address.

Future Directions

• Broadening the theory. The proof covers two equal-sized classes with Gaussian feature distributions. Extending the equivalence result to multi-class, imbalanced, and non-Gaussian settings is a natural next step; the authors currently rely on empirical evidence (Figure 1 and Appendix D.10) for those cases.
• Estimating the number of clusters automatically. In the experiments, the number of clusters is set equal to the number of node classes, and the authors report that FUEL is not sensitive to this choice (Appendix D.12). Removing the need to know the class count would strengthen the unsupervised claim.
• Scaling further. The current approach uses additional scalable techniques for graphs with more than 4 × 10⁴ nodes; pushing toward much larger industrial graphs and characterizing where those techniques stop working remains open.
• Combining with other graph filters and learning regimes. The supplementary material analyzes APPNP and GPR-GNN as alternative convolution functions, and the main text notes supervised versions of this idea exist. Whether FUEL's proxy can be layered into semi-supervised or self-supervised pipelines more broadly is an open question.

Target Audience

Researchers and graduate students in graph machine learning, particularly those working on unsupervised node representation learning, non-homophilic graphs, and deep clustering. It is also relevant to practitioners who need label-free node embeddings for downstream classification or clustering on graphs whose homophily level is unknown or varies, and to theoretically inclined readers interested in when an unsupervised clustering criterion provably orders embeddings the same way a supervised criterion would. Readers without background in graph neural networks will need to consult the cited preliminaries, but the central argument — that feature-space cluster quality can substitute for label-based class separability — is accessible without deep mathematical preparation.

Authors’ abstract

Unsupervised node representation learning aims to obtain meaningful node embeddings without relying on node labels. To achieve this, graph convolution, which aggregates information from neighboring nodes, is commonly employed to encode node features and graph topology. However, excessive reliance on graph convolution can be suboptimal-especially in non-homophilic graphs-since it may yield unduly similar embeddings for nodes that differ in their features or topological properties. As a result, adjusting the degree of graph convolution usage has been actively explored in supervised learning settings, whereas such approaches remain underexplored in unsupervised scenarios. To tackle this, we propose FUEL, which adaptively learns the adequate degree of graph convolution usage by aiming to enhance intra-class similarity and inter-class separability in the embedding space. Since classes are unknown, FUEL leverages node features to identify node clusters and treats these clusters as proxies for classes. Through extensive experiments using 15 baseline methods and 14 benchmark datasets, we demonstrate the effectiveness of FUEL in downstream tasks, achieving state-of-the-art performance across graphs with diverse levels of homophily.