Efficient multi-scale community search method based on spectral graph wavelet

doi:10.1007/s11704-022-2220-4

Front. Comput. Sci.

2023, Vol. 17

Issue (5) : 175335 https://doi.org/10.1007/s11704-022-2220-4

RESEARCH ARTICLE

Efficient multi-scale community search method based on spectral graph wavelet

Cairui YAN¹, Huifang MA^1,²(

), Qingqing LI¹, Fanyi YANG¹, Zhixin LI²

¹. College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China
². Guangxi Key Lab of Multi-source Information Mining and Security, Guangxi Normal University, Guilin 541004, China

Download: PDF(7394 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Community search is an important problem in network analysis, which has attracted much attention in recent years. As a query-oriented variant of community detection problem, community search starts with some given nodes, pays more attention to local network structures, and gets personalized resultant communities quickly. The existing community search method typically returns a single target community containing query nodes by default. This is a strict requirement and does not allow much flexibility. In many real-world applications, however, query nodes are expected to be located in multiple communities with different semantics. To address this limitation of existing methods, an efficient spectral-based Multi-Scale Community Search method (MSCS) is proposed, which can simultaneously identify the multi-scale target local communities to which query node belong. In MSCS, each node is equipped with a graph Fourier multiplier operator. The access of the graph Fourier multiplier operator helps nodes to obtain feature representations at various community scales. In addition, an efficient algorithm is proposed for avoiding the large number of matrix operations due to spectral methods. Comprehensive experimental evaluations on a variety of real-world datasets demonstrate the effectiveness and efficiency of the proposed method.

Keywords community search multi-scale spectral wavelets

Corresponding Author(s): Huifang MA

Just Accepted Date: 23 September 2022 Issue Date: 11 January 2023

Cite this article:

Cairui YAN,Huifang MA,Qingqing LI, et al. Efficient multi-scale community search method based on spectral graph wavelet[J]. Front. Comput. Sci., 2023, 17(5): 175335.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-2220-4
https://academic.hep.com.cn/fcs/EN/Y2023/V17/I5/175335

Notation	Definition
$G = (V, E)$	Network
$G = (V, E)$	Sampled subgraph
$H = (V H, E H)$	Induced subgraph/community of $G$
$A$ , A	Adjacency matrix of $G$ and $G$
$D$ , D	Diagonal matrix of $G$ and $G$
$S$	Query node set
B	Modularity matrix of $G$
L	Normalized graph Laplacian matrix of $G$

Tab.1 Some important symbols and definitions.

Fig.1 An example of community search

Fig.2 An illustration of MSCS. Input: a complex network and query node (marked in red). Output: the target community

H

at different scale

s

Fig.3 Sampling diagram. The query node

v 2

is selected as the initial candidate sampling node, and the node corresponding to the maximum value is continuously calculated using Eq. (1) to join the set of candidate sampling nodes. This process is repeated until the advance stopping condition is satisfied

Fig.4 The eigenvalue distribution of SP

Fig.5 An example of the improved Prim algorithm. (a) Graph G and a query node v_q; (b) a minimum spanning tree H in G starting from v_q

Tab.2 Descriptive statistics of real-world datasets

Fig.6 An example diagram of matching rule

Dataset	Metric	TDS	MRW	LEMON	LOSP	QD-GCN	SGW	LQ	MSCS
Amazon	$F 1$	0.534	0.562	0.588	0.665	0.782	0.794	0.768	0.854
Amazon	con	?	?	?	?	?	?	?	?
DBLP	$F 1$	0.551	0.547	0.584	0.673	0.727	0.607	0.799	0.872
DBLP	con	?	?	?	?	?	?	?	?
SP	$F 1$	?	?	?	?	?	0.741	0.726	0.866
SP	con	0.416	0.428	0.387	0.354	0.324	0.360	0.391	0.274
SRW	$F 1$	?	?	?	?	?	0.758	0.682	0.829
SRW	con	0.328	0.336	0.360	0.351	0.319	0.334	0.362	0.295

Tab.3 The performance of different methods on all real-world datasets

Dataset		SP			SRW
Method	Metric	1	2	3	1	2	3
SGW	rec	0.847	0.831	0.844	0.839	0.821	0.828
	pre	0.849	0.853	0.834	0.804	0.812	0.838
	$F 1$	0.857	0.844	0.837	0.849	0.845	0.837
LQ	rec	0.737	0.829	0.822	0.794	0.827	0.834
	pre	0.749	0.841	0.817	0.786	0.793	0.819
	$F 1$	0.747	0.805	0.829	0.774	0.817	0.821
MSCS	rec	0.851	0.847	0.853	0.848	0.853	0.849
	pre	0.859	0.861	0.847	0.826	0.861	0.849
	$F 1$	0.901	0.893	0.896	0.864	0.869	0.874

Tab.4 Comparison of MSCS on multi-scale benchmark datasets

Fig.7 Efficiency evaluation of model

Fig.8 Performance w.r.t. different |S| and K on Amazon and DBLP. (a) F₁-score for different values of |S| on different dataset; (b) F₁-score for different values of K on different dataset

Fig.9 Ablation studies of key components. (a) Effectiveness of structure-encoded sampling; (b) effectiveness of Chebyshev polynomial

Fig.10 Community search results at different scales in SP. (a) Original graph; (b) sampling subgraph; (c) s₁=2.46; (d) s₃=5.47; (e) s₇=8.21

1	S Fortunato . Community detection in graphs. Physics Reports, 2010, 486( 3−5): 75–174
2	A, Capriello L, Altinay A Monti . Exploring resource procurement for community−based event organization in social enterprises: evidence from Piedmont, Italy. Current Issues in Tourism, 2019, 22( 19): 2319–2322
3	S, Li X, Song H, Lu L, Zeng M, Shi F Liu . Friend recommendation for cross marketing in online brand community based on intelligent attention allocation link prediction algorithm. Expert Systems with Applications, 2020, 139: 112839
4	Y, Fang X, Huang L, Qin Y, Zhang W, Zhang R, Cheng X Lin . A survey of community search over big graphs. The VLDB Journal, 2020, 29( 1): 353–392
5	S, Forouzandeh M, Rostami K Berahmand . A hybrid method for recommendation systems based on tourism with an evolutionary algorithm and topsis model. Fuzzy Information and Engineering, 2022, 14( 1): 26–50
6	J, Li H, Ma Q, Li Z, Li L Chang . A two−stage community search method based on seed replacement and joint random walk. In: Proceedings of International Joint Conference on Neural Networks. 2021, 1–7
7	Y, Chang H, Ma L, Chang Z Li . Community detection with attributed random walk via seed replacement. Frontiers of Computer Science, 2022, 16( 5): 165324
8	J, Reichardt S Bornholdt . Statistical mechanics of community detection. Physical Review E, 2006, 74( 1): 016110
9	D K, Hammond P, Vandergheynst R Gribonval . Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 2011, 30( 2): 129–150
10	Q, Liu Y, Zhu M, Zhao X, Huang J, Xu Y Gao . VAC: vertex−centric attributed community search. In: Proceedings of the 36th IEEE International Conference on Data Engineering. 2020, 937–948
11	Z, Yang X, Li X, Zhang W, Luo K Li . K−truss community most favorites query based on top−t. World Wide Web, 2022, 25( 2): 949–969
12	C Tsourakakis . The k−clique densest subgraph problem. In: Proceedings of the 24th International Conference on World wide Web. 2015, 1122–1132
13	S, Meng H, Yang X, Liu Z, Chen J, Xuan Y Wu . Personalized influential community search in large networks: a K−ECC−based model. Discrete Dynamics in Nature and Society, 2021, 2021: 5363946
14	J, Wei H, Ma Y, Liu Z, Li N Li . Hierarchical high−order co−clustering algorithm by maximizing modularity. International Journal of Machine Learning and Cybernetics, 2021, 12( 10): 2887–2898
15	Q, Li H, Ma J, Li Z, Li Y Jiang . Incorporating user preference into multi−community and outliers search. In: Proceedings of International Joint Conference on Neural Networks. 2021, 1–8
16	Q, Li H, Ma J, Li Z, Li Y Jiang . Searching target communities with outliers in attributed graph. Knowledge−Based Systems, 2022, 235: 107622
17	J, Gao J, Chen Z, Li J Zhang . ICS−GNN: lightweight interactive community search via graph neural network. Proceedings of the VLDB Endowment, 2021, 14( 6): 1006–1018
18	Y, Jiang Y, Rong H, Cheng X, Huang K, Zhao J Huang . Query driven-graph neural networks for community search: from non-attributed, attributed, to interactive attributed. 2021, arXiv preprint arXiv: 2104, 0358: 3
19	Luxburg U Von . A tutorial on spectral clustering. Statistics and Computing, 2007, 17( 4): 395–416
20	M E J Newman . Spectral methods for community detection and graph partitioning. Physical Review E, 2013, 88( 4): 042822
21	S, Zhang R S, Wang X S Zhang . Identification of overlapping community structure in complex networks using fuzzy c−means clustering. Physica A: Statistical Mechanics and its Applications, 2007, 374( 1): 483–490
22	H T, Ali R Couillet . Improved spectral community detection in large heterogeneous networks. The Journal of Machine Learning Research, 2017, 18( 1): 8344–8392
23	Kumar S, Panda B S, Aggarwal D. Community detection in complex networks using network embedding and gravitational search algorithm. Journal of Intelligent Information Systems, 2021, 57(1): 51–72
24	A, Karaaslanlı S Aviyente . Community detection in dynamic networks: equivalence between stochastic blockmodels and evolutionary spectral clustering. IEEE Transactions on Signal and Information Processing over Networks, 2021, 7: 130–143
25	Gupta P, Bahga S S. High-resolution numerical simulations of electrophoresis using the Fourier pseudo-spectral method. Electrophoresis, 2021, 42(7 − 8): 890 − 898
26	Li Y, Sha C, Huang X, Zhang Y. Community detection in attributed graphs: An embedding approach. In: Proceedings of the 32nd AAAI conference on artificial intelligence. 2018
27	F R K Chung . Spectral Graph Theory. Providence: American Mathematical Society, 1997
28	N, Leonardi De Ville D Van . Tight wavelet frames on multislice graphs. IEEE Transactions on Signal Processing, 2013, 61( 13): 3357–3367
29	Zellmer C, Tran T A, Sridhar S. Seeing the bigger picture. Nature Reviews Microbiology, 2021, 19(12): 745 −745
30	Mason J C, Handscomb D C. Chebyshev polynomials. Chapman and Hall/CRC, 2002
31	Phillips G M. Interpolation and approximation by polynomials. Springer Science \& Business Media, 2003
32	T J Rivlin . Chebyshev Polynomials. Mineola: Dover Publications, Inc., 2020
33	M E J Newman . Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103( 23): 8577–8582
34	J, Yang J Leskovec . Defining and evaluating network communities based on ground−truth. Knowledge and Information Systems, 2015, 42( 1): 181–213
35	Sales-Pardo M, Guimera R, Moreira A A, Nunes Amaral L A. Extracting the hierarchical organization of complex systems. Proceedings of the National Academy of Sciences, 2007, 104(39): 15224−15229
36	Y, Bian Y, Yan W, Cheng W, Wang D, Luo X Zhang . On multi−query local community detection. In: Proceedings of IEEE International Conference on Data Mining. 2018, 9–18
37	He K, Sun Y, Bindel D, Hopcroft J, Li Y. Detecting overlapping communities from local spectral subspaces. In: Proceedings of IEEE International Conference on Data Mining. 2015: 769 − 774
38	K, He P, Shi D, Bindel J E Hopcroft . Krylov subspace approximation for local community detection in large networks. ACM Transactions on Knowledge Discovery from Data, 2019, 13( 5): 1–30
39	N, Tremblay P Borgnat . Graph wavelets for multiscale community mining. IEEE Transactions on Signal Processing, 2014, 62( 20): 5227–5239
40	W, Luo D, Zhang L, Ni N Lu . Multiscale local community detection in social networks. IEEE Transactions on Knowledge and Data Engineering, 2021, 33( 3): 1102–1112

[1]

FCS-22220-of-CY_suppl_1

Download

[1]	Mingdi HU, Long BAI, Jiulun FAN, Sirui ZHAO, Enhong CHEN. Vehicle color recognition based on smooth modulation neural network with multi-scale feature fusion[J]. Front. Comput. Sci., 2023, 17(3): 173321-.
[2]	Bo WANG, Li HU, Bowen WEI, Zitong KANG, Chongyi LI. Nighttime image dehazing using color cast removal and dual path multi-scale fusion strategy[J]. Front. Comput. Sci., 2022, 16(4): 164706-.

Viewed

Full text

Abstract

Cited

Shared

Discussed