Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models

Benedek Rozemberczki; Rik Sarkar

Source-linked AI summary

Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models

Benedek Rozemberczki, Rik Sarkar

arXiv:2005.07959v2May 16, 2020cs.LGcs.DMcs.SIstat.ML

TL;DR

Graph neighbourhood features span diverse, potentially unbounded attribute distributions that simple aggregates do not capture. The paper introduces FEATHER, which uses random-walk-weighted characteristic functions to create node and graph representations, and reports competitive performance, robust transfer learning, and linear practical scaling.

Problem
Neighbourhood attributes can have diverse, unknown, and unbounded distributions that simple linear aggregates such as means do not represent.
Method
FEATHER efficiently evaluates random-walk-weighted characteristic functions at learned or discrete points to represent neighbourhood feature distributions and support parametric classifiers.
Results
FEATHER variants were competitive with comparable embedding and graph neural network models, supported robust transfer learning, and scaled linearly with input size in practice.
Takeaways & Limitations
FEATHER provides efficient node and graph representations with theoretical isomorphism consistency, robustness to data corruption, and practical applicability to classification tasks.
Takeaways & Limitations
Evaluation was limited to social networks and web graphs, leaving biological and other dataset types for future testing.

Abstract

from arXiv · show

In this paper, we propose a flexible notion of characteristic functions defined on graph vertices to describe the distribution of vertex features at multiple scales. We introduce FEATHER, a computationally efficient algorithm to calculate a specific variant of these characteristic functions where the probability weights of the characteristic function are defined as the transition probabilities of random walks. We argue that features extracted by this procedure are useful for node level machine learning tasks. We discuss the pooling of these node representations, resulting in compact descriptors of graphs that can serve as features for graph classification algorithms. We analytically prove that FEATHER describes isomorphic graphs with the same representation and exhibits robustness to data corruption. Using the node feature characteristic functions we define parametric models where evaluation points of the functions are learned parameters of supervised classifiers. Experiments on real world large datasets show that our proposed algorithm creates high quality representations, performs transfer learning efficiently, exhibits robustness to hyperparameter changes, and scales linearly with the input size.

1 INTRODUCTION

The paper introduces characteristic functions for representing diverse node-neighborhood feature distributions, using random-walk tie strengths in FEATHER to produce efficient node embeddings and parametric classifiers. It establishes theoretical properties and evaluates FEATHER on node and graph classification tasks.

Contributions: Characteristic functions can be applied simultaneously to multiple features, supporting unified neighborhood representations for node-level machine learning tasks.Neighborhood features are motivated by their usefulness for node classification, link prediction, and community detection [15].
Motivation: Characteristic functions address the limitations of simple linear aggregates for heterogeneous attributes with unknown or unbounded distributions.They provide a unified way to represent and compare neighborhoods across multiple nodes and attributes.
Present work: FEATHER uses r-scale random-walk tie strengths to weight characteristic functions, efficiently producing Euclidean node embeddings from neighborhood feature distributions.Tie strength is defined as the probability that an r-length random walk from a source reaches a target.
Contributions: The paper proves that isomorphic graphs have identical mean-pooled characteristic-function representations and develops differentiable parametric models based on FEATHER.The resulting models include softmax regression and graph neural network variants with learned evaluation points.
Evaluation: FEATHER outperforms comparable unsupervised methods by up to 4.6% on node labeling and 12.0% on graph classification across real-world social and web graphs.The evaluation covers Facebook, Deezer, Twitch, Wikipedia, and GitHub datasets and compares against graph neural networks, neighborhood-preserving, and attributed node-embedding methods.

2 RELATED WORK

Prior work spans characteristic functions for heat diffusion wavelets, node and whole-graph embeddings, and statistical graph fingerprints. FEATHER is also related to graph neural network forward passes because it creates parameterized, multi-scale descriptors of vertex-feature distributions.

Characteristic functions were previously applied to heat diffusion wavelets [10], assuming uniform tie strengths and restricted feature types.
Node embedding methods represent vertices in Euclidean spaces while approximately preserving similarity, including neighborhood-preserving, attributed, and structural approaches [25] [15].
Whole-graph embeddings and statistical graph fingerprints represent graphs in Euclidean spaces using structural feature matrices, graph Laplacian eigenvalues, or graph-scanning information [26] [8] [12].
FEATHER parallels graph neural network forward passes [17] [22] by evaluating tie-strength-weighted vertex features to produce parameterized, multi-scale descriptors of feature distributions [1].This connection frames FEATHER as a multi-scale graph neural network-like procedure for describing vertex features.

3 CHARACTERISTIC FUNCTIONS ON GRAPHS

This section introduces characteristic functions on attributed graphs for describing node-feature distributions in neighborhoods. It proposes an r-scale random-walk-weighted variant, gives a linear-time computation algorithm, and establishes robustness and isomorphic-graph representation properties.

Characteristic functions are defined on attributed graphs to describe node-feature distributions within neighborhoods.
The proposed r-scale random-walk-weighted characteristic function can be calculated for all nodes in linear time.
The section proves robustness of these characteristic functions and their ability to represent isomorphic graphs.

3.1 Node feature distribution characterization

The section defines node-level characteristic functions for multiscale feature distributions, weighting vertices by random-walk transition probabilities. FEATHER efficiently samples these functions across nodes, features, and scales to produce node embeddings.

Characteristic-function structure: The real and imaginary components are weighted sums of cosine and sine waves, with evaluation point θ acting as time and feature values as angular frequencies.The real component is even, the imaginary component is odd, and both lie in [-1,1].
Random-walk weighting: At scale r, the characteristic function describes a source node’s neighborhood feature distribution using r-step random-walk transition probabilities.These probabilities equal entries of the rth power of the normalized adjacency matrix D−1A.
Node embeddings: Sampling d evaluation points from the function domain yields compact representations for all nodes, where similar rows indicate similar local feature distributions.The resulting representation acts as a node embedding and has whole-graph time complexity O(|E| ·d ·r) and memory complexity O(|V | · d).
Multiple features: FEATHER generalizes from one node feature to k real-valued feature vectors, computing a separate characteristic-function representation for each feature and scale.Its embedding-storage complexity is O(|V | · d · r · k), while total computation is O((|E| + |V |) · d · r2 · k).
FEATHER algorithm: FEATHER computes characteristic-function embeddings for every node feature across all scales up to r using the graph’s normalized adjacency matrix.The algorithm is sparsity-aware and returns a node embedding matrix Z.

3.2 Theoretical properties

The r-scale random-walk weighted characteristic function is robust to localized feature corruption and yields mean-pooled graph descriptors invariant under graph isomorphism. These descriptors support graph-level comparison and machine learning.

Robustness: Feature corruption at one node changes the characteristic-function values by an amount bounded by the tie strength, regardless of corruption magnitude.The bound follows from the maximal absolute difference between cosine functions being 2.
Graph descriptors: Mean-pooled characteristic functions characterize and compare whole graphs through structural properties.The pooled real and imaginary parts are defined as graph-level descriptors.
Graph descriptors: The resulting graph descriptors can serve as features for graph-level machine-learning algorithms.
Isomorphism invariance: Mean-pooled degree characteristic functions are identical for isomorphic graphs.The result follows because graph isomorphisms induce a permutation matrix relating both normalized adjacency matrices and degree vectors.

3.3 Parametric characteristic functions

Parametric characteristic-function models learn evaluation points jointly with classifier weights, selecting scales that are most discriminative for downstream node classification. The models include softmax and single-hidden-layer neural variants optimized on labeled nodes.

3.3 Parametric characteristic functions: Learned evaluation points make random-walk characteristic functions task-adaptive, selecting the most discriminative values for downstream classification.Algorithm 1 can be interpreted as a graph neural network forward pass using the normalized adjacency matrix.
3.3 Parametric characteristic functions: The softmax classifier combines the characteristic-function representation with trainable weights β to output node-class distributions.The representation Z is computed using Algorithm 1 with trainable evaluation points e_Θ, while β has shape (2·k·d·r)×C.
3.3 Parametric characteristic functions: A neural characteristic-function model adds one hidden feed-forward layer with trainable matrices β_0 and β_1 and element-wise ReLU activation.The matrices have shapes (2·k·d·r)×h and h×C, respectively.
3.3 Parametric characteristic functions: Both FEATHER-N and FEATHER-L minimize log-loss over labeled training nodes and optimize evaluation points and classifier weights by gradient descent.The optimized parameters are β for the softmax model and β_0, β_1 for the neural model, together with e_Θ.
3.3 Parametric characteristic functions: The softmax and neural models have O(k · r · d · C) and O(k · r · d · h + C · h) trainable parameters, respectively.The softmax model matches the parameter count of upstream FEATHER representations followed by logistic regression.

4 EXPERIMENTAL EVALUATION · 4.1 Datasets · 4.2 Node classification

FEATHER is evaluated on heterogeneous social-network and webgraph datasets for node and graph classification, with experiments highlighting representation quality, transfer learning, scalability, and robustness. For node classification, unsupervised FEATHER outperforms proximity-preserving, structural, and attributed node embeddings by 0.4%–4.6% in micro-averaged test AUC.

4 EXPERIMENTAL EVALUATION: FEATHER is evaluated for node and graph classification, while the experiments also assess transfer learning, scalability, and robustness.
4.1 Datasets: The evaluation uses publicly available and self-collected social-network and webgraph datasets whose descriptive statistics are summarized in Table 1.The datasets are heterogeneous with respect to size, density, and number of features.
4.1.1 Node level datasets.: The node-level datasets vary in size, density, and feature count and support binary or multi-class classification across Wikipedia Crocodiles, Twitch Social Networks, and Deezer Europe.Tasks include predicting Wikipedia-page popularity, adult-content streaming, and user gender from graph structure and liked artists.
4.1.2 Graph level datasets.: Graph-level evaluation uses many small, non-attributed social graphs with varying size, density, and diameter, including Reddit Threads, Twitch Egos, and GitHub Repos.These datasets support graph classification tasks such as thread versus non-thread identification and gamer-behavior categorization.
4.2 Node classification: Node-classification comparisons include FEATHER variants, neighbourhood-based, structural, and attributed embeddings, plus competitive graph neural network architectures.Unsupervised baselines use matched free-parameter counts and default Karate Club or Node2Vec settings.
4.2.1 Experimental settings.: FEATHER variants combine the graph with neighbourhood, structural, and generic vertex attributes; the unsupervised model uses 16 evaluation points per feature, r = 2, and logistic regression.Neighbourhood features use 32-dimensional Truncated SVD embeddings of the normalized adjacency matrix, while structural features use log degree and clustering coefficient.

4.3 Graph classification

FEATHER graph descriptors outperform supervised and unsupervised graph classification methods on three datasets, with significant AUC gains of 1.1%–12.0%. On Deezer Egos, FEATHER’s disadvantage is not significant.

Graph classification: The comparison evaluates unsupervised and supervised FEATHER against implicit matrix factorization, spectral fingerprinting, and graph neural network models.Average test AUCs with standard errors were computed from 10 seeded 20%/80% train-test splits.
Graph classification: Supervised models use one-hot encoded degree, clustering coefficient, and eccentricity with two graph-convolutional layers followed by pooling and a fully connected layer.Training minimizes log-loss with Adam [21] for 10 epochs using a learning rate of 0.01 and batch size 32.
Graph classification: Unsupervised FEATHER pools node characteristic-function features using permutation-invariant mean, maximum, or minimum aggregation before logistic regression.Node representations use log-transformed degree, with r = 5, d = 25, and evaluation points initialized uniformly in [0, 5].
Graph classification: FEATHER outperforms supervised and unsupervised graph classification methods on Reddit Threads, Twitch Egos, and Github Repos, with significant AUC gains of 1.1%–12.0%.The gains are significant at α = 1% on all three datasets.
Graph classification: On Deezer Egos, FEATHER’s disadvantage is not significant.

4.4 Sensitivity analysis

Sensitivity analysis shows that larger random-walk scales and more characteristic-function evaluation points improve predictive performance, with diminishing marginal gains. Supervised models especially benefit from higher-order neighborhoods and are more efficient when evaluation points are few.

Experimental setup: The analysis uses Facebook Page-Page with log-transformed degree features, a standard 20%/80% split, and mean test AUC over 10 seeded splits.Scale and evaluation-point effects were varied separately using 25 evaluation points or scale 5, respectively, with evaluation points initialized uniformly in [0, 5].
Random-walk scale: Higher-order neighborhoods improve classification, but scale yields diminishing marginal gains; supervised models substantially outperform unsupervised variants beyond one-hop neighborhoods.With only first-hop neighbors, the supervised and unsupervised variants show little performance difference.
Evaluation point count: More characteristic-function evaluation points improve downstream performance, while supervised models show decreasing marginal gains and the neural model reaches good performance with fewer points.Supervised models are more efficient when the number of evaluation points is low.

4.5 Transfer learning · 4.6 Runtime performances

FEATHER’s characteristic-function features transfer across Twitch graphs, with supervised neural models outperforming unsupervised and shallow variants, while runtime scales predictably with input size and random-walk scale. These results support both transfer-learning utility and the proposed runtime complexity analysis.

4.5 Transfer learning: Transfer learning trained each model on a fully labeled source graph and evaluated it on a target graph sharing the target variable and node-feature set.Experiments used r = 5 and d = 25 characteristic-function evaluation points, with log-transformed degree centrality included for every model.
4.5 Transfer learning: The transfer-learning evaluation used Twitch Germany, Spain, and Portugal as target graphs and measured predictive performance by mean AUC over 10 experimental repetitions.The results demonstrate that r-scale random-walk-weighted characteristic-function features can be used in transfer-learning settings.
4.5 Transfer learning: Neural FEATHER outperformed unsupervised FEATHER and shallow FEATHER-L models in transfer learning, with a 2.1–3.3% average AUC advantage for Portuguese users.Figure 4 reports mean AUC values over 10 seeded experiments on German, Spanish, and Portuguese Twitch target graphs.
4.5 Transfer learning: A characteristic function using only one structural feature outperformed random guessing in most Twitch transfer scenarios.The shared structural feature was log-transformed node degree centrality.
4.6 Runtime performances: Doubling the number of nodes, edges, features, or characteristic-function evaluation points doubled the expected FEATHER runtime.Figure 5 measured mean logarithmic runtimes over 10 repetitions on synthetic Erdős–Rényi graphs.
4.6 Runtime performances: Increasing the random-walk scale increased runtime, although the quadratic increase was not evident for small r values.The runtime experiments varied graph size, edge count, feature count, evaluation-point count, and random-walk scale.

5 CONCLUSIONS AND FUTURE DIRECTIONS

The paper introduces FEATHER as a linear-time method for characteristic-function representations on attributed graphs, with proven robustness to data corruption and isomorphism consistency. Experiments show competitive classification performance and robust transfer learning, while future work targets broader graph models and graph types.

Conclusions: FEATHER computes r-scale random-walk-weighted characteristic functions on large attributed graphs in linear time, producing Euclidean vector-space representations of nodes.The paper also proves robustness to data corruption and equal representations for isomorphic graphs.
Conclusions: Across real-world node and graph classification datasets, FEATHER variants are competitive with comparable embedding and graph neural network models, while transfer learning is efficient and robust.Sensitivity analysis and node-classification results indicate that supervised FEATHER models have an edge over unsupervised representations.
Future directions: Future work could integrate FEATHER’s forward pass into temporal, multiplex, and heterogeneous graph neural networks, develop learned permutation-invariant node pooling, and evaluate beyond social and web graphs.These directions would extend multi-scale vertex feature extraction, node-feature aggregation, and empirical coverage.