Scalable Graph Classification via Random Walk Fingerprints (Extended Abstract)

1 Introduction

We address the problem of graph classification. Similar to classifying text or image data, comparing graphs is fundamental to building a classifier. This task, known as graph similarity learning, is challenging due to the inherent variability in both the size and structure of the graphs.

Targeting graph similarity, the past decade has witnessed the success of graph kernels [Shervashidze et al., 2011; Borgwardt and Kriegel, 2005] and graph representation learning [Kipf and Welling, 2017; Tsitsulin et al., 2018]. The former compares substructures, while the latter utilizes supervised graph neural networks, or uses unsupervised embedding approaches paired with classifiers. Despite their success, scalability remains a critical issue. This is due to the increasing size of real-world graphs and the large volume of graph datasets, as both the scale of each graph and the number of graphs can be substantial. To address the scalability challenge, we introduce RandomWalk Fingerprints (RWF), an unsupervised structural feature extraction technique that can incorporate node attributes. The computational complexity of RWF is bounded by O(Nτc(mn + pn2 )), where N is the number of graphs; n and m are the number of nodes and edges per graph; τc is the maximum walk steps; and p is the dimension of node features. In the worst-case scenario where m = n2 , RWF exhibits a cubic time complexity regarding n. However, the typical sparsity of real-world graphs (m≪n2 ) generally ensures more manageable computational demands.

1 This is an extended abstract of a paper first published in the IEEE ICDM conference [Li et al., 2024].

2 Method

At its core, RWF quantifies intra- and inter-subset connection strengths among node subsets with distinct structural roles. By focusing on these role-based subsets, RWF enables soft alignment between structurally heterogeneous graphs, enabling meaningful comparisons. Based on these node subsets, heuristics like loop and walk, reflecting the connection strength, are used to construct the feature vector. Additionally, RWF can easily incorporate node features. After feature extraction, we use a basic classifier like SVM to get the classification results.

Structural-Role-based Vertex Partitioning

We divide the nodes of each graph into distinct subsets, thereby facilitating alignment among the node subsets across disparate graphs. This essential step enables us to identify local graph patterns, thus enhancing the representation power of our method. Given a graph G, we partition its nodes into k subsets, i.e., V = V1 ∪ · · · ∪ Vk, where each subset contains nodes that share the same structural role, and k is the number of predefined roles. In order to obtain size-invariant representations of graphs, the parameter k should be consistent for all graphs.

• Degree Heuristic. Degree is an essential statistic of nodes. High-degree nodes tend to be cores in the local central regions, while low-degree nodes often occupy peripheral positions. Hence, node degree serves as a naive indicator of the structural roles of nodes. Initially, we count the node degrees. We then sort the nodes by their degrees and divide the node set into k subsets, each containing |V |/k nodes.
• Core-Periphery Heuristic. This heuristic is based on the assumption that the arrangement of a graph includes densely connected core nodes and sparsely connected peripheral nodes. We utilize KM-config [Kojaku and Masuda, 2018] to identify core and peripheral nodes. It leverages the configuration model [Fosdick et al., 2018] as the null model to generate a target graph with idealized core-periphery pairs. Then, it maximizes the similarity between the target and source graphs through appropriate node labeling. Notably, KM-config can detect multiple core-periphery pairs, and it has a linear time complexity with respect to the number of edges.

Structural Feature Extraction

With the node partitions of each graph determined, subsequently, we show how to extract features based on the graph G and its node partitions (V1, V2, · · · , Vk). In the simplest form, we quantify the connection strength within and between the subsets of nodes based on the relational matrix T and its powers. The relational matrix T can be defined by the transition matrix Tp = D-1A, or the symmetric normalized adjacency matrix T = D- 12 AD- 12 , where D denotes the diagonal degree matrix and A denotes the adjacency matrix. Each entry of Tp and T quantifies a kind of connection strength between two nodes. In this paper, we select T since symmetric normalization enables computational efficiency. We introduce the following features.

Here, loopτVi represents the average strength of all τ-loops of nodes in Vi. walkτVi represents the average strength of all τ-walks that start and end at nodes within Vi. walkτVi→Vj denotes the average strength of all τ-walks traversing from Vi to Vj. In a nutshell, the three features measure the connection strength within and between node subsets.

Incorporation of Node Attributes

In addition to the structural features, our method is designed to incorporate node features. Accordingly, we define the following two matrices:

where P ∈ Rp×p and Q ∈ Rp×p are symmetric matrices encapsulating the interactions of node features within the node set Vi. Here, diag(TτVi ) and TτVi serve as kernels to modulate the influence of node features, while 1 |Vi| and 1 |Vi|2 are used to balance the numerical values. We further compute the row average of P and Q, producing two vectors xlτVi ∈ Rp and xwτVi ∈ Rp , which represent the aggregated features of the subset Vi at scale τ. This procedure yields a rich feature vector for the node subset that combines sub-structural and node-feature-based information.

3 Feature Interpretation

We demonstrate the connections between the extracted features and the graph spectrum, providing insight into the use of local feature extraction and a limited walking length.

Connections to Graph Spectrum

We factorize T as follows:

where the columns of U ∈ Rn×n are eigenvectors of T, and Λ is the diagonal matrix whose diagonal elements are the corresponding eigenvalues, denoted by {Λ1, · · · ,Λn}. Let UVi ∈ R|Vi|×n be the rows of U that corresponds to Vi, specifically, we use the node indices of Vi to extract a subset of rows of U to form UVi .

Let B = UTVi UVi , which is a symmetric n×n matrix, and {α1, α2, · · · , αn} are the corresponding diagonal entries. Let β = {β1, · · · , βn} ∈ R1×n and γ = {γ1, · · · , γn} ∈ R1×n be the row vector with the sum over each column of UVi and UVj , respectively. We have:

The above calculations establish the relationship between the three feature sets and the spectrum of Tτ , i.e., the three features represent the weighted aggregation of the eigenvalues of Tτ . Thus, the extracted features could be conceptualized as ensembles that capture the essence of the full eigenvalue spectrum of the graph. This connection may elucidate the efficacy of the extracted features, as several studies (e.g., [Tsitsulin et al., 2018; Dong et al., 2019; Sawlani et al., 2021]) have demonstrated the effectiveness of graph spectrum in graph classification tasks.

Why Use Local Feature Extraction?

Consider A as the adjacency matrix of an undirected graph. We alter an arbitrary edge euv by adjusting its weight, and the updated adjacency matrix becomes ˆA. After applying symmetric normalization to A and ˆA, we get T and ˆT, which denote the initial and modified transition matrices, respectively. We use d(x, y) to represent the shortest path distance between two nodes x and y. For the perturbed edge uv, we introduce a distance function d(w) = min{d(w, u), d(w, v)}, which measures the minimum distance from any node w to either node in the pair u or v. We give the following theorem derived from [Pan et al., 2022]. We have a different setting regarding T but the proof is the same.

Based on the above theorem, it is easy to understand that under structural perturbation, the change in T propagates outward from the perturbed nodes to their increasingly distant neighbors as the number of walk steps increases. If we omit the vertex partitioning process and only use loopτV and walkτV as features, we can still distinguish A and ˆA. But with vertex partitioning and the three features defined, it is possible to detect where the perturbation occurs, as node subsets act as local sensors. Therefore, vertex partitioning may enhance the distinguishing power of the defined features.

Fig. 1 shows the results of RWF on two graph datasets. Recall that the underlying assumption behind RWF is that graphs from different classes exhibit distinct local connectivity patterns. These patterns are reflected by node subsets that assume different structural roles. In the simplest form, we categorize the nodes of each graph into two subsets: high-degree and low-degree. Then we fix the maximum walk step τc to 6 and calculate {loopτVhigh , walkτVhigh }τc τ=1 , {loopτVlow , walkτVlow }τc τ=1 and {walkVhigh→Vlow }τc τ=1 . This division gives rise to three distinct feature domains: the connectivity strength within high-degree nodes, within lowdegree nodes, and between high-degree and low-degree nodes. As illustrated in Fig. 1, RWF features demonstrate strong discriminatory capabilities. Moreover, we can observe distinctions between the distributions of different classes, even when considering a single domain of RWF features independently.

Why Limit Walk Steps?

We explain why we use a limited number of steps as controlled by τc. Due to the symmetric normalization, the eigenvalues of T are bounded within the interval [-1, 1]. Based on the above calculations, it is evident that the three features can be expressed as weighted aggregations of the eigenvalues of Tτ , like f(τ) = ∑nt=1 δtΛτt , where the vector δ = {δ1, · · · , δn} ∈ R1×n contains some constant values. Without loss of generality, we assume the eigenvalues are sorted in descending order, with Λ1 and Λn representing the maximum and minimum eigenvalues, respectively. The maximum eigenvalue Λ1 = 1. The minimum eigenvalue Λn = -1 if and only if the corresponding graph is bipartite; otherwise, Λn lies in the range of (-1, 0]. For simplicity, we assume Λn follows the latter case, as bipartite graphs are special, and we consider general cases here. When τ becomes large:

The above calculation reveals that f(τ) ≈ δ1 when τ is large, and δ1 is a constant. This suggests that larger τc does not contribute additional structural information. In practice, we set τc to a value typically not exceeding 10 to ensure efficiency while capturing meaningful graph structure.

4 Experimental Evaluation

We evaluate our method against the following techniques:

• Unsupervised graph embedding algorithms: NetLSD [Tsitsulin et al., 2018], NetSimile [Berlingerio et al., 2013], FGSD [Verma and Zhang, 2017], A-DOGE [Sawlani et al., 2021], LDP [Cai and Wang, 2018] and FEATHER [Rozemberczki and Sarkar, 2020].

• Graph kernels: NH [Hido and Kashima, 2009], WL [Shervashidze et al., 2011], and DOSGK [Huang et al., 2021].
• Graph neural networks: GCN [Kipf and Welling, 2017], GIN [Xu et al., 2019], and GraphSAGE [Hamilton et al., 2017].

Due to brevity, we only show the results on four large datasets. The reader can find all the experiments in [Li et al., 2024].

The graph classification results on Deezer ego nets (DEE), REDDIT-MULTI-12K (RED-12K), Github stargazers (GIT), and Twitch egos (TWI), are reported in Table 1. RWFs achieve the best results in general.

5 Conclusion

In this paper, we proposed RWF, a scalable, interpretable, unsupervised feature extraction approach for graph classification. RWF learns a subset-based representation of graphs, central to which is the structural-role-based vertex partitioning scheme. This technique enables soft alignments across diverse graphs and thus facilitates the learning of local structures. Specifically, RWF extracts three features, measuring the connection strengths within and between node subsets. Additionally, a highlight of RWF is its flexibility in incorporating node attributes, making it a comprehensive tool for feature extraction. Our experimental analysis confirms the effectiveness and efficiency of RWF, illustrating its potential as a powerful approach to graph classification.