PaperlayerView exact revision on arXiv

Source-linked AI summary

Topology-induced Operators Reveal Complementary Graph Representations without Training

Meng Qin, Jinqiang Cui, Hongwei Zheng, Weihua Li, Sen Pei

arXiv:2609.08152v1cs.LGcs.SI

TL;DR

The paper asks whether informative graph embeddings require sophisticated learned models, given that topology, attributes, and learning are usually entangled. It propagates random features through random-walk and anonymous-walk hierarchical structures without gradient-based training, yielding complementary position and identity embeddings. Across broad tasks and datasets, these embeddings were competitive with established methods, while fusion improved some tasks and maintained favorable quality-efficiency trade-offs.

  • Problem

    Graph embedding quality is difficult to attribute to topology rather than attributes, feature processing, or parameter learning, especially because graphs contain complementary position and identity properties.

  • Method

    PI-HIST feeds random features through random-walk- and anonymous-walk-induced hierarchical structures using a single training-free feedforward propagation to derive position and identity embeddings.

  • Results

    Across 7 node-, edge-, and graph-level tasks, PI-HIST embeddings were informative without gradient-based training, competitive with classic and state-of-the-art baselines, and improved some tasks when combined.

  • Takeaways & Limitations

    Random-walk and anonymous-walk topology transformations can expose complementary graph information before learning, with fused embeddings sometimes improving inference quality.

  • Takeaways & Limitations

    The study assumes undirected, unweighted graphs with topology as the only input and leaves integration of attributes for future work.

Abstract

from arXiv · show

Graph representation learning has largely focused on designing increasingly sophisticated models to transform graph topology into vector representations, or embeddings. However, the extent to which embedding quality depends on model learning, rather than on the underlying topological transformations, remains unclear. Here, we show that informative embeddings can be derived without complicated model design and gradient-based training. Propagating random features through implicit hierarchical structures induced by random walks and anonymous walks yields embeddings that capture node proximity and structural role, respectively. These two training-free embeddings preserve complementary aspects of graph organization and perform competitively with classic and recent methods across various node-, edge-, and graph-level tasks. They often require substantially less computation, resulting in a favorable quality-efficiency trade-off. Combining the two types of embeddings further improves inference quality of some tasks compared with using either embedding type alone. Our results suggest that informative graph embeddings can arise from carefully chosen topological transformations before any learning operation is applied.

1 Introduction

Graph embeddings entangle topology, attributes, and learning, obscuring which structural properties they preserve. PI-HIST addresses this by propagating random features through random-walk and anonymous-walk structures without training, producing complementary position and identity embeddings evaluated broadly.

  • Graph representation learning maps nodes, edges, or whole graphs into low-dimensional embeddings for downstream inference tasks.
  • Node positions capture relative proximity, whereas node identities encode structural roles; these properties provide complementary views of graph organization.
  • Modern models intertwine topology-induced operators, attributes, trainable transformations, and task objectives, making topology-specific contributions difficult to isolate.
  • PI-HIST treats random walks and anonymous walks as topology-induced operators, propagating random features through their hierarchical structures with a single training-free feedforward propagation.
  • Across 7 node-, edge-, and graph-level tasks, 8 real-world and 9 synthetic graphs, and 18 baselines, PI-HIST produced informative embeddings without gradient-based training.
  • The position and identity embeddings showed different task strengths, while their combination improved some inference tasks and offered favorable quality-efficiency trade-offs.

2 Results

PI-HIST shows that random features propagated through random-walk- and anonymous-walk-induced hierarchical structures can produce complementary position and identity embeddings without gradient-based training. Across node-, edge-, and graph-level evaluations, the variants are competitive and efficient, while their fusion often improves inference quality.

  • Method: PI-HIST uses RW- and AW-induced hierarchical structures as parameter-free backbones, propagating random features through a single FFP with normalization, skip connections, and nonlinear activation.The RW and AW variants are denoted PI-HIST (R) and PI-HIST (A), respectively.
  • Position and identity embeddings: PI-HIST (R) captures community position, whereas PI-HIST (A) captures structural identity, including distinctions between leaders and strong supporters.Both variants produce embeddings consistent with node2vec and struc2vec despite using a single training-free FFP from random inputs.
  • Node-level tasks: Across node-level evaluations, at least one training-free PI-HIST variant achieves quality competitive with or better than the strongest baselines, with R favoring position tasks and A favoring identity tasks.The comparisons cover four node-level tasks on eight public real-world graph datasets and 18 baselines.
  • Efficiency: Both PI-HIST variants deliver top-tier efficiency in most cases because they avoid feature augmentation and iterative gradient-based optimization.Identity embedding baselines can encounter out-of-time or out-of-memory exceptions on large graphs.
  • Edge-level tasks: The relative importance of node position and identity varies across datasets and tasks, with PI-HIST variants broadly following established position- and identity-preserving baselines.Graph reconstruction favors identity embeddings on USA and PPI, while position-preserving methods perform better on Film and Actor; link prediction is not typically dominated by either property.
  • Combining complementary embeddings: Combining PI-HIST (R) and (A) generally improves inference over either variant alone, exceeding 1% in some Film link-prediction and graph-reconstruction cases.Intermediate fusion weights α ∈ {0.1, 0.2, · · · , 0.9} can outperform the single-variant boundary cases α ∈ {0.0, 1.0}, indicating that the gain is not merely selecting the better variant.
  • Graph-level tasks: At graph level, PI-HIST (R&A) produces more consistent real-world block structures and leverages the complementary grouping strengths of R and A on synthetic graphs.The most visually consistent correlation patterns generally occur for 0 < α < 1 rather than at α ∈ {0, 1}.

3 Discussion

PI-HIST isolates topology-induced information by generating complementary position- and identity-oriented embeddings without parameter learning. The discussion highlights broader extensions while noting current assumptions and trade-offs.

  • Topology-induced operators: PI-HIST uses random features with random-walk- and anonymous-walk-induced hierarchical structures to produce position- and identity-oriented embeddings through a single training-free FFP.The formulation isolates information exposed by topology-induced operators from feature learning and gradient-based optimization.
  • Empirical scope: Across 7 node-, edge-, and graph-level tasks on 8 real-world and 9 synthetic graphs, both PI-HIST variants achieve competitive or better inference quality while generally requiring less computation.Combining the two embedding types improves inference quality on several tasks.
  • Current limitations: The paper identifies manual parameter tuning as a current limitation because PI-HIST has no learning procedure.Future extensions could learn aggregation weights and other settings while retaining the topology-based formulation.
  • Future directions: Increasing training may improve inference quality but reduce efficiency, motivating a tunable quality-efficiency trade-off.Adaptive control of training extent is presented as one possible strategy.
  • Current limitations: PI-HIST currently assumes topology-only input, leaving integration of real-world node and edge attributes for further investigation.The authors propose weighting attributes according to their correlation with the topology property needed by a downstream task.
  • Future directions: The framework could be applied to other topology-induced hierarchical structures, including graph coarsening and the Weisfeiler-Lehman test.The paper also suggests extending PI-HIST from Euclidean to hyperbolic space to better preserve hierarchical structure.

4 Methods

The method separates graph topology into position and identity signals, then derives embeddings by propagating random features through random-walk- and anonymous-walk-induced hierarchical structures without learned parameters.

  • Problem formulation: The method assumes undirected, unweighted graphs and uses topology as the only input to isolate position and identity properties.Graph attributes are excluded, with their integration left for future work.
  • Problem formulation: PI-HIST treats node position as relative proximity and node identity as structural role, preserving complementary graph properties.Nodes with similar positions may have overlapping neighborhoods, whereas similar identities may share ego-net structures or degree statistics.
  • PI-HIST (R): position embedding inference: PI-HIST (R) propagates Gaussian random features through an L-step random-walk operator, with skip connections, normalization, and optional nonlinear activation.The operator (D^-1A)^L represents L-step random-walk transition probabilities, while the skip connection controls the balance between propagated and previous-layer features.
  • PI-HIST (A): identity embedding inference: PI-HIST (A) estimates anonymous-walk statistics, extracts node-specific hierarchical structures, and propagates random features through them to infer structural identity embeddings.The procedure includes random-walk sampling, anonymous-walk mapping, indexing, counting, statistic gathering, and hierarchical structure extraction.
  • Combination of PI-HIST (R) and PI-HIST (A): Combining the two embeddings uses weighted sums or concatenation, with different downstream tasks favoring different strategies.Weighted concatenation works better for two edge-level tasks, whereas weighted summation works better for graph-level superfamily identification.

Additional Experiment Results

Additional experiments examine metrics and datasets beyond the main figures, and ablations analyze how walk length, skip weighting, activation, and normalization affect PI-HIST.

  • Additional evaluation results: Supplementary Figure S1 reports additional node-level metrics and datasets, while Supplementary Figure S2 reports further edge-level task results.The reported additions include micro F1 on Europe, Actor, BlogCatalog, and Amazon, full three-metric results on USA, Film, PPI, and DBLP, and edge-level results on five datasets.
  • Ablation and parameter analyses: Ablation studies and parameter analyses vary walk length, ε, nonlinear activation, and normalization settings.Representative PI-HIST (R) analyses use macro F1 for PPI node position classification and modularity for USA community detection; supplementary analyses also examine PI-HIST (A).

Supplementary Section B

The supplementary methods specify PI-HIST algorithms and their theoretical basis: random-walk and anonymous-walk structures are converted into embeddings through sparse statistics, hierarchical propagation, and random projection.

  • PI-HIST (R) algorithm: Algorithm 1 derives PI-HIST (R) embeddings from a graph, embedding dimension, random-walk length, and skip-connection hyper-parameter.It produces an embedding matrix Z through the propagation and output transformations defined in the main paper.
  • PI-HIST (A) algorithm: PI-HIST (A) estimates anonymous-walk statistics by sampling random walks, mapping them to anonymous walks, indexing them, and counting node-index pairs.Large graphs are processed in batches, after which run-level statistics are combined.
  • Anonymous-walk indexing: Anonymous-walk indices are computed with dynamic programming over a tree whose root-to-leaf paths represent candidate anonymous walks.The precomputed table supports indexing without enumerating all candidate walks directly.
  • Statistics and hierarchical extraction: Observed anonymous-walk counts are sparse, so statistics are merged across runs and hierarchical structures are extracted by traversing nonzero entries.The extracted structures contain layered units and weighted links determined by anonymous-walk frequencies.
  • Complexity: The supplementary complexity analysis characterizes sampling, indexing, counting, merging, and extraction costs using graph size, walk length, batch count, and observed anonymous-walk sparsity.For large sparse graphs, the number of observed anonymous walks is much smaller than the number of candidates.
  • Theoretical support: Theoretical analysis interprets PI-HIST as a Gaussian random projection of topology-induced structural features and connects its two operators to diffusion profiles and rooted ego-net structures.The analysis supports random-feature embeddings through a Gaussian projection guarantee and task-relevant structural similarity arguments.

C.2 RW-induced operators preserve node-position information

Random-walk diffusion profiles make nodes within a metastable community similar, and Gaussian random projection preserves this proximity in PI-HIST (R).

  • Random walks initialized within a metastable community approach a shared within-community distribution before substantially escaping it.The assumptions bound within-community deviation and escape probability at the considered diffusion scale.
  • Proposition 1 establishes that any two nodes in the same metastable community have similar length-L random-walk diffusion profiles.
  • Gaussian random projection maps these structural diffusion features into embeddings while preserving within-community proximity with high probability.The result follows by combining the diffusion-similarity proposition with the random-projection argument.
  • Thus, PI-HIST (R) has a theoretical mechanism for preserving node-position information from random-walk topology.Its additional skip connection is controlled by ε.

D.1 Datasets

The evaluation uses diverse real-world and synthetic graphs spanning node identities and positions, alongside broad unsupervised embedding baselines.

  • The study evaluates PI-HIST on 8 public real-world datasets covering scales from thousands to millions of edges.The datasets include air-traffic, actor-film, protein-interaction, social, and academic-collaboration graphs.
  • The first and last four real-world datasets provide node-identity and node-position ground truth, respectively.
  • PI-HIST is compared with 18 classic and state-of-the-art unsupervised embedding baselines.The baselines include position-preserving, identity-preserving, efficient, and GNN-based self-supervised methods.
  • The evaluation covers 7 inference tasks spanning node, edge, and graph levels.

D.3.1 Node-Level Tasks

Node-level evaluation measures position and identity embeddings through classification, clustering, and inference-time efficiency on distinct task settings.

  • Four node-level tasks assess whether PI-HIST encodes node positions and identities while also examining quality-efficiency trade-offs.
  • Node Position and Identity Classification: Node position and identity classification uses logistic regression, macro and micro F1, and repeated 20%/10%/70% train-validation-test splits.Each evaluation is repeated 10 times, reporting mean and standard deviation.
  • Community Detection: Community detection evaluates position embeddings with KMeans and modularity, where larger average modularity indicates better quality.The procedure is repeated 10 times.
  • Node Identity Clustering: Node identity clustering evaluates identity embeddings using conductance, a lower-is-better metric based on a high-order-degree similarity graph.
  • Efficiency Evaluation: Efficiency is measured by mean embedding-inference time over 10 runs, with failures beyond 1 × 10^4 seconds counted as OOT.

D.3.2 Edge-Level Tasks

Edge-level evaluation tests whether position and identity embeddings provide complementary information for link prediction and graph reconstruction.

  • Link prediction and graph reconstruction are used to test whether node positions and identities together improve inference quality.Both tasks are treated as neither typically position- nor identity-dominant.
  • Both edge-level tasks use logistic regression with AUC as the quality metric, where larger AUC indicates better inference quality.
  • Link Prediction: Link prediction removes 20% of graph edges while preserving a spanning tree in the connected training topology.The remaining evaluation uses positive and sampled negative node pairs.
  • Graph Reconstruction: Graph reconstruction measures whether low-dimensional node vectors can recover the original graph topology using sampled node pairs.Sampling avoids directly scoring all N^2 node pairs on large graphs.

D.3.3 Graph-Level Tasks

The graph-level evaluation tests whether combining position and identity embeddings supports superfamily identification on real-world and synthetic graphs. It compares PI-HIST with established graph-level features and examines parameter settings and task-specific evaluation procedures.

  • Graph Superfamily Identification: Graph superfamily identification groups structurally similar graphs while separating graphs from different superfamilies using graph-level features or embeddings.Quality is assessed through correlation matrices, especially whether ground-truth superfamilies form main-diagonal blocks.
  • Real-world graphs: The real-world evaluation partitions eight graphs into four scenario-based superfamilies, including air-traffic and movie-related networks.Europe and USA form one superfamily, while Film and Actor form another; the remaining graphs are clustered similarly by scenario.
  • Synthetic graphs: Synthetic superfamily identification uses the LFR benchmark, which generates graphs from parameters controlling size, community structure, and degree characteristics.The benchmark varies N, θ, kavg, kmax, cmin, and cmax across synthetic graphs.
  • Baselines: PI-HIST is compared with BoD, BoHD, SSP, and CNS, spanning classic histogram features and more sophisticated graph-level methods.BoD and BoHD count distinct degree patterns, with BoHD using neighbor order r = 5.
  • Evaluation settings: Evaluation settings tune PI-HIST and baseline hyper-parameters separately for the relevant position- and identity-related tasks, with α controlling fusion when embeddings are combined.PI-HIST uses ε and L for embedding derivation, while α is the fusion weight for combining position and identity embeddings.

D.5 Experimental Environment

The experiments use a software stack and cloud-server environment that includes PyTorch-based implementations, official baseline implementations, and high-memory CPU/GPU hardware.

  • Implementation and hardware: PI-HIST is implemented with PyTorch, PyTorch Cluster, and Numba, while other baselines use their official open-source implementations.All experiments run on Ubuntu 22.04 using an AMD EPYC 9K84 96-Core CPU, 150GB memory, and one H20 GPU with 96GB memory.

Detailed Experiment Results

The supplementary materials provide detailed configurations, timing breakdowns, and numerical results for node-, edge-, and combined position–identity embedding evaluations. They report results across multiple datasets, validation and test splits, and fusion settings.

  • Node-level results: Node-level results are reported as mean ± standard deviation across Europe, USA, Actor, Film, PPI, BlogCatalog, DBLP, and Amazon.Supplementary Tables S5–S12 provide dataset-specific numerical results corresponding to the main and supplementary visualizations.
  • Configurations: PI-HIST configuration tables specify embedding dimension d, walk length L, aggregation weight ε, optional activation and normalization, and random-walk sampling counts.Separate tables describe PI-HIST (R), PI-HIST (A), and their combined settings, including fusion weight α and optional normalization γnorm(·).
  • Edge-level results: Edge-level results cover link prediction and graph reconstruction, with numerical outcomes reported for validation and test sets across all datasets.Supplementary Tables S14 and S15 provide the detailed task results, while Table S16 varies α for PI-HIST (R&A).
  • Inference time: The PI-HIST (A) timing breakdown separates random-walk sampling, anonymous-walk processing, statistic gathering, hierarchical extraction, and one FFP.The reported steps are RW, AW-MAP, AW-IDX, AW-CNT, CAT, HIER, and FFP, measured in seconds.
Loading 2609.08152v1…