Low-Rank Representations Towards Classification Problem of Complex Networks

2025-05-06 0 0 485.33KB 4 页 10玖币

侵权投诉

Low-Rank Representations Towards Classification Problem of

Complex Networks

Murat Çelik

b21827263@cs.hacettepe.edu.tr

Department of Computer

Engineering,

Hacettepe University

Ankara, Turkey

Ali Baran Taşdemir

alibaran@tasdemir.us

Department of Computer

Engineering,

Hacettepe University

Ankara, Turkey

Lale Özkahya

ozkahya@cs.hacettepe.edu.tr

Department of Computer

Engineering,

Hacettepe University

Ankara, Turkey

ABSTRACT

Complex networks representing social interactions, brain activi-

ties, molecular structures have been studied widely to be able to

understand and predict their characteristics as graphs. Models and

algorithms for these networks are used in real-life applications, such

as search engines, and recommender systems. In general, such net-

works are modelled by constructing a low-dimensional Euclidean

embedding of the vertices of the network, where proximity of the

vertices in the Euclidean space hints the likelihood of an edge (link).

In this work, we study the performance of such low-rank represen-

tations of real-life networks on a network classication problem.

KEYWORDS

Graph embeddings, graph representations, low-dimensional em-

bedding, low-rank representation.

1 INTRODUCTION

Complex networks representing social interactions, brain activi-

ties, molecular structures have been studied widely to be able to

understand and predict their characteristics as graphs. Building

good models for complex networks, considering the role of so-

cial networks in understanding modern human interaction, is very

important [

]. In recent years, obtaining low-dimensional

embeddings of graph nodes in Euclidean space has been frequently

studied in machine learning applications,and in this way, thanks to

the geometry of the embedding, it has been tried to preserve the

structural properties of the graph [

]. Specically, the node embed-

ding method represents each node in the n-node graph as a vector

𝑥∈R𝑘

and

𝑘<< 𝑛

. In this way, the embedding method is used

in many subjects such as clustering, classication, link prediction,

together with machine learning [

]. In this sense, the probabil-

ity of an edge/link between two nodes can be deduced from the

geometric proximity of the vectors representing them.

Two of these embedding methods that are widely used are TSVD

(Truncated Singular Value Decomposition) and PCA (Logistic Prin-

cipal Component Analysis) methods such as decomposition of the

adjacency matrix of the given network (or graph) [

]. In recent

years, the method of learning graph embedding using deep neural

networks has been frequently used [

]. The question

these methods are trying to solve is to get a given large networks to

be represented by matrices of smaller dimensions than the original,

while preserving its structural properties. One of the still unan-

swered questions is how small of a matrix this representation can

be done while preserving the structural information of the network

[

]. For example, the frequent occurrence of triangles is

an important characteristic in social networks such as Facebook,

and the extent to which this can be preserved by graph embedding

techniques such as TSVD and PCA has been researched [

], [

binary node classication question, the class labels of the nodes

were applied as graph characteristics.

The main contribution of this work is to examine the perfor-

mance of the commonly used TSVD and LPCA graph embedding

techniques in the multiclass classication problem of the original

graph. The graph classication question is a problem that has been

studied in many dierent elds, and in some cases it has diculties

such as trying to extract class information without sucient net-

work information. Bonner et al. [

] developed a learning method for

graph classication by using the topology features of the network

using deep neural networks. One of the comprehensive studies in

terms of the variety of random graph models was done by Rossi and

Ahmed [18]. In this study, 9 network classes with distinctly dier-

ent structures, including network groups constructed with random

network models, are included in the classication question. It has

been observed that the reconstructed networks to be represented

at low dimensions by graph embedding methods largely preserve

their class properties. As a result of the experiments, it was seen

that the LPCA method gave better performance than the TSVD

method. It has been observed that random networks need much

larger sizes than real world networks in order to be successfully

represented.

2 METHOD

In the classication process, dierent real network groups such as

biology, economy and social networks, as well as dierent network

groups produced by random methods, constitute the classes of

the classication process. The performance of TSVD and LPCA

methods is compared to how much the representation of the original

networks given by the graph embedding methods by the graphs in

lower dimensions preserves the class feature.Classication is done

by using the graph features, which are known to play an important

role in graphs.

2.1 Graph Embedding Methods

TSVD :. TSVD (Truncated Singular Value Decomposition) is a

spectral method that approximates the adjacency matrix by us-

ing SVD (Singular Value Decomposition). The TSVD method is

used to reconstruct the adjacency matrix. For an adjacency matrix

𝐴∈{0,1}𝑁×𝑁

, let

𝑍∈R𝑁×𝑘

be the orthonormal matrix. The

arXiv:2210.11561v1 [cs.SI] 20 Oct 2022

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Low-RankRepresentationsTowardsClassificationProblemofComplexNetworksMuratÇelikb21827263@cs.hacettepe.edu.trDepartmentofComputerEngineering,HacettepeUniversityAnkara,TurkeyAliBaranTaşdemiralibaran@tasdemir.usDepartmentofComputerEngineering,HacettepeUniversityAnkara,TurkeyLaleÖzkahyaozkahya@cs.hacette...

展开>> 收起<<

Low-Rank Representations Towards Classification Problem of Complex Networks.pdf

共4页,预览1页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Low-Rank Representations Towards Classification Problem of Complex Networks

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: