2025-11-20T02:28:14.687819

Heterogeneous Attributed Graph Learning via Neighborhood-Aware Star Kernels

Huang, Yao, Chen et al.

Attributed graphs, typically characterized by irregular topologies and a mix of numerical and categorical attributes, are ubiquitous in diverse domains such as social networks, bioinformatics, and cheminformatics. While graph kernels provide a principled framework for measuring graph similarity, existing kernel methods often struggle to simultaneously capture heterogeneous attribute semantics and neighborhood information in attributed graphs. In this work, we propose the Neighborhood-Aware Star Kernel (NASK), a novel graph kernel designed for attributed graph learning. NASK leverages an exponential transformation of the Gower similarity coefficient to jointly model numerical and categorical features efficiently, and employs star substructures enhanced by Weisfeiler-Lehman iterations to integrate multi-scale neighborhood structural information. We theoretically prove that NASK is positive definite, ensuring compatibility with kernel-based learning frameworks such as SVMs. Extensive experiments are conducted on eleven attributed and four large-scale real-world graph benchmarks. The results demonstrate that NASK consistently achieves superior performance over sixteen state-of-the-art baselines, including nine graph kernels and seven Graph Neural Networks.

academic

विषमांगी विशेषता युक्त ग्राफ सीखना पड़ोस-जागरूक स्टार कर्नेल के माध्यम से

मूल जानकारी

पेपर ID: 2511.11245
शीर्षक: Heterogeneous Attributed Graph Learning via Neighborhood-Aware Star Kernels
लेखक: Hong Huang, Haiming Chen, Hang Gao, Chengyu Yao
संस्था: Institute of Software, Chinese Academy of Sciences
वर्गीकरण: cs.LG (मशीन लर्निंग)
प्रकाशन समय: 14 नवंबर 2025 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2511.11245

सारांश

विशेषता युक्त ग्राफ (attributed graphs) सामाजिक नेटवर्क, जैव सूचना विज्ञान और रासायनिक सूचना विज्ञान जैसे क्षेत्रों में व्यापक रूप से पाए जाते हैं, जिनमें आमतौर पर अनियमित टोपोलॉजी संरचना और संख्यात्मक तथा श्रेणीबद्ध मिश्रित विशेषताएं होती हैं। यद्यपि ग्राफ कर्नेल विधियां ग्राफ समानता माप के लिए सैद्धांतिक ढांचा प्रदान करती हैं, लेकिन मौजूदा कर्नेल विधियों को विषमांगी विशेषता शब्दार्थ और पड़ोस की जानकारी दोनों को एक साथ कैप्चर करना मुश्किल है। यह पेपर पड़ोस-जागरूक स्टार कर्नेल (NASK) प्रस्तावित करता है, जो एक नई ग्राफ कर्नेल विधि है। NASK गोवर समानता गुणांक के घातीय रूपांतरण का उपयोग करके संख्यात्मक और श्रेणीबद्ध विशेषताओं को कुशलतापूर्वक मॉडल करता है, और वाइसफेइलर-लेहमैन पुनरावृत्ति द्वारा बढ़ाए गए स्टार उप-संरचनाओं का उपयोग करके बहु-पैमाने पड़ोस संरचना जानकारी को एकीकृत करता है। सिद्धांत रूप से NASK सकारात्मक निश्चित है, जो SVM जैसे कर्नेल सीखने के ढांचे के साथ संगतता सुनिश्चित करता है। 11 विशेषता ग्राफ और 4 बड़े पैमाने पर वास्तविक ग्राफ बेंचमार्क पर व्यापक प्रयोग 16 अत्याधुनिक आधारभूत विधियों (9 ग्राफ कर्नेल और 7 ग्राफ तंत्रिका नेटवर्क सहित) पर लगातार श्रेष्ठ प्रदर्शन दर्शाते हैं।

अनुसंधान पृष्ठभूमि और प्रेरणा

1. समाधान की जाने वाली मूल समस्याएं

विशेषता युक्त ग्राफ सीखना दो मूल चुनौतियों का सामना करता है:

विषमांगी विशेषता मॉडलिंग: ग्राफ नोड्स और किनारों में एक साथ संख्यात्मक और श्रेणीबद्ध विशेषताएं होती हैं, मौजूदा विधियों को एकीकृत रूप से संभालना मुश्किल है
संरचना जानकारी कैप्चर करना: स्थानीय पड़ोस संरचना जानकारी और बहु-हॉप निर्भरता संबंधों को प्रभावी ढंग से एकीकृत करने की आवश्यकता है

2. समस्या की महत्ता

विशेषता युक्त ग्राफ कई महत्वपूर्ण क्षेत्रों में व्यापक अनुप्रयोग हैं:

रासायनिक सूचना विज्ञान: आणविक संरचना प्रतिनिधित्व (परमाणु प्रकार श्रेणीबद्ध विशेषताएं, रासायनिक गुण संख्यात्मक विशेषताएं)
जैव सूचना विज्ञान: प्रोटीन संरचना विश्लेषण
सामाजिक नेटवर्क: उपयोगकर्ता प्रोफाइल और संबंध मॉडलिंग

3. मौजूदा विधियों की सीमाएं

ग्राफ कर्नेल विधियों की कमियां:

असतत विधियां (जैसे Hash Graph Kernel) मूल विशेषता शब्दार्थ को खो देती हैं
वितरण-आधारित विधियां (जैसे WWL) सकारात्मक निश्चितता के औपचारिक गारंटी की कमी करती हैं
सीधी संयोजन विधियां (भारित योग) शब्दार्थ जानकारी हानि का कारण बनती हैं

ग्राफ तंत्रिका नेटवर्क की सीमाएं:

अभिव्यक्ति क्षमता सैद्धांतिक रूप से 1-WL परीक्षा से अधिक नहीं है
छोटे नमूने परिदृश्य में स्थिरता कम है
व्याख्या क्षमता अपर्याप्त है

4. अनुसंधान प्रेरणा

यह पेपर एक ग्राफ कर्नेल विधि डिजाइन करने का लक्ष्य रखता है जो निम्नलिखित आवश्यकताओं को एक साथ पूरा करे:

एकीकृत विषमांगी विशेषता प्रसंस्करण: असतत विधि से जानकारी हानि से बचना
समृद्ध संरचना अभिव्यक्ति: निश्चित उप-संरचना की सीमा से परे जाना
सैद्धांतिक गारंटी: सकारात्मक निश्चितता सिद्ध करना सीखने एल्गोरिदम के अभिसरण को सुनिश्चित करने के लिए
कम्प्यूटेशनल दक्षता: बड़े पैमाने पर ग्राफ पर स्केलेबिलिटी बनाए रखना

मूल योगदान

NASK कर्नेल विधि प्रस्तावित करना: विषमांगी विशेषताओं और पड़ोस संरचना जानकारी दोनों को प्रभावी ढंग से संभालने वाली पहली सकारात्मक निश्चित ग्राफ कर्नेल
सकारात्मक निश्चित विशेषता समानता फ़ंक्शन डिजाइन करना: गोवर समानता गुणांक के घातीय रूपांतरण पर आधारित, सैद्धांतिक रूप से सकारात्मक निश्चितता सिद्ध करना, संख्यात्मक और श्रेणीबद्ध विशेषताओं को एकीकृत रूप से मॉडल करना
स्टार उप-संरचना और WL पुनरावृत्ति का संलयन: स्टार ग्राफ को स्थानीय संरचना इकाई के रूप में उपयोग करना, WL एल्गोरिदम के माध्यम से विस्तारित करना बहु-हॉप पड़ोस जानकारी एकत्रीकरण को लागू करना
संपूर्ण सैद्धांतिक विश्लेषण: NASK और इसके सभी घटकों की सकारात्मक निश्चितता को औपचारिक रूप से सिद्ध करना, प्रभावी पुनरुत्पादन कर्नेल हिल्बर्ट स्पेस (RKHS) को प्रेरित करना सुनिश्चित करना
व्यापक प्रयोग सत्यापन: 15 बेंचमार्क डेटासेट पर 16 मजबूत आधारभूत विधियों को पार करना, पारंपरिक ग्राफ कर्नेल और GNN विधियां सहित, सटीकता में अधिकतम 10.2% सुधार

विधि विवरण

कार्य परिभाषा

इनपुट: विशेषता ग्राफ संग्रह $\mathcal{G} = \{G_1, G_2, ..., G_N\}$ , जहां प्रत्येक ग्राफ $G = \langle A, V, E, \lambda, F \rangle$

$V$ : नोड्स का समुच्चय
$E$ : किनारों का समुच्चय
$A$ : विशेषता नामों का समुच्चय
$F$ : विशेषता मानों का समुच्चय (संख्यात्मक और श्रेणीबद्ध मान सहित)
$\lambda: A \times (V \cup E) \rightarrow F$ : विशेषता मानचित्रण फ़ंक्शन

आउटपुट: ग्राफ के बीच कर्नेल मैट्रिक्स $K \in \mathbb{R}^{N \times N}$ , जहां $K_{ij} = K_{NAS}(G_i, G_j)$

उद्देश्य: ग्राफ वर्गीकरण कार्य के लिए सकारात्मक निश्चित कर्नेल फ़ंक्शन डिजाइन करना (SVM के माध्यम से)

मॉडल आर्किटेक्चर

NASK तीन-स्तरीय प्रगतिशील डिजाइन अपनाता है:

स्तर 1: विशेषता समानता फ़ंक्शन P

एकल विशेषता आयाम $d$ के लिए, पहले गोवर समानता को परिभाषित करें:

संख्यात्मक विशेषताएं: $s_d(x_d, x'_d) = 1 - \frac{|x_d - x'_d|}{\text{range}_d}$

श्रेणीबद्ध विशेषताएं: $s_d(x_d, x'_d) = \begin{cases} 1, & \text{यदि } x_d = x'_d \\ 0, & \text{अन्यथा} \end{cases}$

फिर सकारात्मक निश्चित कर्नेल प्राप्त करने के लिए घातीय रूपांतरण लागू करें: $s'_d(x_d, x'_d) = \exp(-\gamma(1 - s_d(x_d, x'_d)))$

बहु-आयामी विशेषता समानता: $P(v, v') = \frac{1}{D} \sum_{d=1}^{D} s'_d(\lambda(A,v)_d, \lambda'(A',v')_d)$

मुख्य नवाचार: यह सिद्ध करके कि $f_d(x_d, x'_d) = 1 - s_d(x_d, x'_d)$ सशर्त नकारात्मक निश्चित (CND) फ़ंक्शन है, Berg आदि के शास्त्रीय परिणाम का उपयोग करके, घातीय रूपांतरण के बाद सकारात्मक निश्चितता सुनिश्चित करना।

स्तर 2: स्टार उप-ग्राफ कर्नेल $k_s$

स्टार उप-ग्राफ परिभाषा: $S = \langle A, V, E, \lambda, F, C, L \rangle$

$C$ : केंद्रीय नोड
$L$ : पत्ती नोड्स का समुच्चय (केंद्रीय नोड के सभी पड़ोसी)

स्टार उप-ग्राफ निष्कर्षण: $\mathcal{F}(v, G) = \langle G.A, \{v\} \cup N(v), \{(v,u) \in E | u \in N(v)\}, G.\lambda, G.F, v, N(v) \rangle$

स्टार उप-ग्राफ कर्नेल: $k_s(S, S') = \sum_{n \in R^{-1}(S)} \sum_{n' \in R^{-1}(S')} P(C, C') \cdot P(n, n')$

जहां $R^{-1}(S)$ स्टार ग्राफ का वैध विघटन है (नोड्स और किनारे), $P(C, C')$ पद केंद्रीय नोड समानता के महत्व को जोर देता है।

स्तर 3: पड़ोस-जागरूक स्टार कर्नेल $K_{NAS}^{(H)}$

WL पुनरावृत्ति विस्तार: $\mathcal{L}: S^{h-1} \times G \rightarrow S^h$

प्रारंभिक: $\hat{S}^{(1)}(G) = \{\mathcal{F}(v, G) | v \in V\}$

पुनरावर्ती: $\hat{S}^{(h)}(G) = \{\mathcal{L}(S^{(h-1)}, G) | S^{(h-1)} \in \hat{S}^{(h-1)}(G)\}$

अंतिम कर्नेल परिभाषा: $K_{NAS}^{(H)}(G, G') = \sum_{h=1}^{H} \sum_{S \in \hat{S}^{(h)}(G)} \sum_{S' \in \hat{S}^{(h)}(G')} k_s(S, S')$

जब $H=1$ हो तो यह आधार स्टार कर्नेल $K_S$ में परिणत होता है; $H$ बढ़ने के साथ, उच्च-क्रम संरचना अंतःक्रिया को कैप्चर करता है।

तकनीकी नवाचार बिंदु

1. एकीकृत विषमांगी विशेषता प्रसंस्करण

One-Hot एन्कोडिंग के साथ तुलना: आयाम विस्फोट और विरलता समस्या से बचना
यूक्लिडियन दूरी के साथ तुलना: संख्यात्मक विशेषताओं के लिए सामान्यीकरण, श्रेणीबद्ध विशेषताओं के लिए अर्थपूर्ण समानता प्रदान करना
लाभ: कम्प्यूटेशनल दक्षता बनाए रखते हुए मूल शब्दार्थ संरक्षित करना

2. स्टार उप-संरचना की तर्कसंगतता

सार्वभौमिकता: वास्तविक ग्राफ में व्यापक रूप से पाई जाती है
शब्दार्थिकता: नोड के स्थानीय पड़ोस पैटर्न को कैप्चर करना
दक्षता: सभी स्टार ग्राफ निष्कर्षण के लिए रैखिक समय जटिलता $O(|V|)$
यादृच्छिक चलने के साथ तुलना: निश्चित केंद्र प्रतिनिधित्व अधिक स्थिर शब्दार्थ संबंध प्रदान करता है

3. WL पुनरावृत्ति की आवश्यकता

निश्चित उप-संरचना की सीमा को दूर करना
क्रमिक रूप से बहु-हॉप पड़ोस जानकारी एकत्रीकरण
सैद्धांतिक रूप से अभिव्यक्ति क्षमता को बढ़ाना (k-WL परीक्षा के करीब)
विलोपन प्रयोग दिखाते हैं कि WL को हटाने से 3.5%-6.7% प्रदर्शन में गिरावट आती है

4. सैद्धांतिक गारंटी की पूर्णता

सकारात्मक निश्चितता प्रमाण की संपूर्ण श्रृंखला:

Lemma 1: $f_d$ CND है
Lemma 2: $s'_d$ सकारात्मक निश्चित है
Theorem 1: $P$ सकारात्मक निश्चित है
Theorem 2: $k_s$ सकारात्मक निश्चित है
Theorem 3: $K_S$ सकारात्मक निश्चित है
Theorem 4: $K_{NAS}^{(H)}$ सकारात्मक निश्चित है

जटिलता विश्लेषण

सबसे खराब स्थिति समय जटिलता: $O(Hn^2(n+m)^2d)$

$H$ : WL पुनरावृत्ति गहराई
$n, m$ : नोड्स और किनारों की संख्या
$d$ : विशेषता आयाम

व्यावहारिक रन में कर्नेल समानता थ्रेशोल्ड प्रूनिंग के माध्यम से महत्वपूर्ण त्वरण।

प्रयोग सेटअप

डेटासेट

श्रेणीबद्ध विशेषता ग्राफ (5):

MUTAG (188 ग्राफ, आणविक उत्परिवर्तनशीलता)
NCI1 (4,110 ग्राफ, यौगिक गतिविधि)
PTC_MR (344 ग्राफ, कार्सिनोजेनिकता)
D&D (1,178 ग्राफ, प्रोटीन संरचना)
PROTEINS (1,113 ग्राफ, प्रोटीन कार्य)

संख्यात्मक विशेषता ग्राफ (2):

SYNTHETIC (4,337 ग्राफ, सिंथेटिक अणु)
SYNTHIE (400 ग्राफ, 4 वर्ग सिंथेटिक डेटा)

विषमांगी विशेषता ग्राफ (4):

ENZYMES (600 ग्राफ, एंजाइम वर्गीकरण, 18-आयामी संख्यात्मक + श्रेणीबद्ध विशेषताएं)
PROTEINS_full (1,113 ग्राफ, मिश्रित विशेषताएं)
BZR (405 ग्राफ, दवा अणु)
COX2 (467 ग्राफ, दवा अणु)

बड़े पैमाने पर वास्तविक ग्राफ (4):

Pubmed (उद्धरण नेटवर्क, TF-IDF विशेषताएं)
Cora (2,708 पेपर, 1,433-आयामी)
Citeseer (3,327 पेपर, 3,703-आयामी)
Pokec (सामाजिक नेटवर्क, उपयोगकर्ता विशेषताएं)

मूल्यांकन मेट्रिक्स

वर्गीकरण सटीकता: 10-गुना क्रॉस-सत्यापन 10 बार दोहराया गया (कुल 100 रन)
रिपोर्ट प्रारूप: माध्य ± मानक विचलन
सांख्यिकीय महत्व: कई रन के माध्यम से सुनिश्चित

तुलना विधियां

ग्राफ कर्नेल विधियां (9):

WL-VH, PK, GH, ML: प्रारंभिक विधियां
HGK-WL: हैश त्वरण
WWL: Wasserstein दूरी
RetGK: रिटर्न संभावना
RWK: नियमित यादृच्छिक चलना
SWWL: स्लाइस Wasserstein

ग्राफ तंत्रिका नेटवर्क (7):

GCN, GraphSAGE, GIN: शास्त्रीय आर्किटेक्चर
GAT: ध्यान तंत्र
KerGNN, AKGNN, KAGNN: कर्नेल-बढ़ाए गए GNN

कार्यान्वयन विवरण

NASK कॉन्फ़िगरेशन:

$\gamma$ : सत्यापन समुच्चय के माध्यम से चयन
WL गहराई $H$ : डिफ़ॉल्ट 4 (संवेदनशीलता विश्लेषण द्वारा निर्धारित)
SVM पैरामीटर $C$ : $\{10^{-3}, ..., 10^3\}$ ग्रिड खोज से

GNN कॉन्फ़िगरेशन:

2-स्तरीय आर्किटेक्चर, प्रति स्तर 64 छिपी इकाइयां
ReLU सक्रियण, वैश्विक योग पूलिंग
सीखने की दर: {0.001, 0.005, 0.01}
प्रारंभिक रोकना: patience=10

हार्डवेयर वातावरण:

GPU: NVIDIA RTX 4090
सभी विधियां समान हार्डवेयर पर मूल्यांकन

प्रयोग परिणाम

मुख्य परिणाम

संख्यात्मक और विषमांगी विशेषता ग्राफ (तालिका 1)

डेटासेट	सर्वश्रेष्ठ आधारभूत	NASK	सुधार
SYNTHETIC	RetGK: 96.2%	97.9%	+1.7%
SYNTHIE	WWL: 96.0%	97.1%	+1.1%
ENZYMES	RWK: 76.4%	78.3%	+1.9%
PROTEINS_full	RWK: 79.3%	81.1%	+1.8%
BZR	RWK: 86.2%	88.8%	+2.6%
COX2	RWK: 81.2%	82.9%	+1.7%

मुख्य निष्कर्ष:

सभी 6 डेटासेट पर SOTA प्राप्त करना
सर्वश्रेष्ठ ग्राफ कर्नेल की तुलना में औसत 2.0% सुधार
GNN विधियों को महत्वपूर्ण रूप से पार करना (जैसे ENZYMES पर GIN केवल 59.6%)

श्रेणीबद्ध विशेषता ग्राफ (तालिका 2)

डेटासेट	सर्वश्रेष्ठ आधारभूत	NASK	सुधार
MUTAG	RWK: 93.6%	95.9%	+2.3%
NCI1	WL-VH: 85.2%	88.0%	+2.8%
PTC_MR	KerGNN: 70.5%	76.7%	+6.2%
D&D	RetGK: 81.6%	82.1%	+0.5%
PROTEINS	RetGK: 75.8%	82.6%	+6.8%

मुख्य निष्कर्ष:

PTC_MR पर सबसे महत्वपूर्ण सुधार (+6.2%), जटिल आणविक संरचना के मजबूत मॉडलिंग क्षमता को दर्शाता है
PROTEINS पर GNN की तुलना में 9.5% सुधार (vs GCN 63.1%)

बड़े पैमाने पर वास्तविक ग्राफ (तालिका 3)

डेटासेट	सर्वश्रेष्ठ आधारभूत	NASK	सुधार
Pubmed	KernelGCN: 87.84%	89.53%	+1.69%
Cora	KernelGCN: 88.40%	89.24%	+0.84%
Citeseer	KernelGCN: 80.28%	80.78%	+0.50%
Pokec	KAGNN: 81.07%	83.05%	+1.98%

मुख्य निष्कर्ष:

सभी बड़े पैमाने पर डेटासेट पर सर्वश्रेष्ठ बनाए रखना
स्केलेबिलिटी और व्यावहारिकता को सिद्ध करना

विलोपन प्रयोग

घटक योगदान विश्लेषण (तालिका 4, MUTAG/PTC_MR/PROTEINS_full/BZR):

वेरिएंट	औसत सटीकता में गिरावट
यादृच्छिक चलना के साथ	-6.7%
One-Hot के साथ	-4.5%
यूक्लिडियन के साथ	-3.8%
WL पुनरावृत्ति के बिना	-5.0%

विस्तृत विश्लेषण:

स्टार उप-संरचना की महत्ता:
- यादृच्छिक चलने से प्रतिस्थापन D&D में 21.5% गिरावट का कारण बनता है
- निश्चित केंद्र प्रतिनिधित्व अधिक समृद्ध शब्दार्थ संबंध को कैप्चर करता है
विशेषता समानता फ़ंक्शन P के लाभ:
- PROTEINS_full पर One-Hot से 3.7% अधिक
- यूक्लिडियन दूरी से 2.2% अधिक
- मिश्रित विशेषताओं को एकीकृत रूप से संभालने की क्षमता महत्वपूर्ण है
WL पुनरावृत्ति की आवश्यकता:
- हटाने से 3.5%-6.7% गिरावट आती है
- जटिल संरचना मॉडलिंग के लिए बहु-हॉप पड़ोस जानकारी महत्वपूर्ण है

WL गहराई संवेदनशीलता विश्लेषण

सटीकता प्रवृत्ति (चित्र 2a):

NASK-1 से NASK-4: सटीकता लगातार सुधरती है
NCI1: 85.0% → 88.0% (+3.0%)
PROTEINS: 79.8% → 82.5% (+2.7%)
NASK-5: कुछ डेटासेट पर अतिसज्जन दिखाई देता है

रन समय (चित्र 2b):

NASK-4 से NASK-5: रन समय में महत्वपूर्ण वृद्धि
NCI1: +28.7%
PROTEINS: +41.8%

सर्वश्रेष्ठ कॉन्फ़िगरेशन: NASK-4 सटीकता और दक्षता के बीच सर्वश्रेष्ठ संतुलन प्राप्त करता है

केस विश्लेषण

NCI1 आणविक ग्राफ दृश्य (चित्र 3):

k=1 से k=4 हॉप स्टार उप-ग्राफ विस्तार दिखाना
k=1: प्रत्यक्ष रासायनिक वातावरण को कैप्चर करना (सरल कार्यात्मक समूह)
k बढ़ना: बड़ी उप-संरचना और संबंध निर्भरता को कैप्चर करना
स्टार उप-ग्राफ निष्कर्षण डिजाइन की प्रभावशीलता को सत्यापित करना

वर्ग संभावना हीटमैप (चित्र 6):

मजबूत ऊर्ध्वाधर पट्टियां: मॉडल वर्ग आवंटन के लिए उच्च आत्मविश्वास
गलत वर्गीकृत नमूने दुर्लभ और केंद्रित
विवेचक क्षमता और भविष्यवाणी सामंजस्य दिखाना

मजबूती विश्लेषण

विशेषता व्यवधान प्रयोग (चित्र 5):

गाऊसी शोर:

BZR: सटीकता >86% बनी रहती है (30% शोर)
COX2: >77% बनी रहती है
माध्यिका सटीकता स्थिर

विशेषता मास्किंग:

प्रदर्शन में अधिक महत्वपूर्ण गिरावट लेकिन अभी भी प्रतिस्पर्धी
संकीर्ण चतुर्थक श्रेणी स्थिरता दिखाती है

निष्कर्ष: NASK निरंतर व्यवधान के प्रति सहिष्णुता असतत सूचना हानि से बेहतर है

रन समय तुलना

दक्षता सत्यापन (तालिका 6):

MUTAG: 0.61s (vs ML 8h+)
NCI1: 12m (vs GH 3.7h)
PROTEINS_full: 59s (vs ML 2.8h)

मुख्य लाभ:

GH और ML की तुलना में कई परिमाण तेजी से
हल्के विधियों (PK, RetGK) के साथ प्रतिस्पर्धी
मध्यम से बड़े पैमाने पर डेटासेट पर बेहतर

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

विधि प्रभावशीलता: NASK 15 बेंचमार्क पर 16 मजबूत आधारभूत विधियों को व्यापक रूप से पार करता है, औसत 2-6% सुधार
सैद्धांतिक पूर्णता: सकारात्मक निश्चितता को पूरी तरह से सिद्ध करना, प्रभावी RKHS को प्रेरित करना सुनिश्चित करना, SVM जैसे सीखने एल्गोरिदम के अभिसरण और सामान्यीकरण क्षमता को सुनिश्चित करना
एकीकृत मॉडलिंग क्षमता: विषमांगी विशेषताओं और संरचना जानकारी के संयुक्त मॉडलिंग की कठिनाई को सफलतापूर्वक हल करना
व्यावहारिकता: बड़े पैमाने पर वास्तविक ग्राफ पर प्रतिस्पर्धी क्षमता बनाए रखना, स्वीकार्य रन समय

सीमाएं

कम्प्यूटेशनल जटिलता:
- सबसे खराब स्थिति $O(Hn^2(n+m)^2d)$
- हालांकि प्रूनिंग अनुकूलन है, लेकिन अति-बड़े पैमाने पर ग्राफ (लाखों नोड्स) पर अभी भी सीमित हो सकता है
हाइपरपैरामीटर संवेदनशीलता:
- $\gamma$ पैरामीटर को सत्यापन समुच्चय द्वारा ट्यून करने की आवश्यकता है
- WL गहराई $H$ की पसंद सटीकता और दक्षता के बीच संतुलन की आवश्यकता है
धारणा शर्तें:
- विशेषता श्रेणी ज्ञात मानी जाती है (सामान्यीकरण के लिए)
- लापता विशेषताओं के संभालने पर विस्तृत चर्चा नहीं
अभिव्यक्ति क्षमता सीमा:
- हालांकि 1-WL से परे, लेकिन अभी भी k-WL द्वारा सीमित
- कुछ उच्च-क्रम ग्राफ समरूपता समस्याओं को अलग करने में असमर्थ हो सकता है

भविष्य की दिशाएं

अनुमानित एल्गोरिदम:
- नमूनाकरण रणनीति स्टार उप-ग्राफ जोड़ी संख्या को कम करने के लिए
- कर्नेल मैट्रिक्स गणना को त्वरित करने के लिए निम्न-रैंक अनुमान
गहन सीखने का संलयन:
- NASK को GNN के ध्यान तंत्र के रूप में उपयोग करना
- कर्नेल पैरामीटर को अंत से अंत तक सीखना
गतिशील ग्राफ विस्तार:
- समय-श्रृंखला विशेषता ग्राफ को संभालना
- कर्नेल मैट्रिक्स को वृद्धिशील रूप से अपडेट करना
बहु-कार्य सीखना:
- नोड वर्गीकरण और लिंक भविष्यवाणी
- ग्राफ जनरेशन कार्य

गहन मूल्यांकन

लाभ

1. सैद्धांतिक कठोरता (★★★★★)

सकारात्मक निश्चितता प्रमाण की संपूर्ण श्रृंखला (6 प्रमेय/लेम्मा)
CND फ़ंक्शन और Berg प्रमेय के शास्त्रीय परिणामों का उपयोग
सीखने एल्गोरिदम के अभिसरण की औपचारिक गारंटी
यह ग्राफ कर्नेल क्षेत्र में अपेक्षाकृत दुर्लभ है, अधिकांश विधियों में सैद्धांतिक गारंटी की कमी है

2. विधि नवाचार (★★★★★)

विशेषता मॉडलिंग: गोवर गुणांक के घातीय रूपांतरण को पहली बार ग्राफ कर्नेल में उपयोग करना, दक्षता और अभिव्यक्ति क्षमता को संतुलित करना
संरचना मॉडलिंग: स्टार उप-संरचना + WL पुनरावृत्ति का संयोजन नया है, स्थानीय और वैश्विक जानकारी को संतुलित करना
एकीकृत ढांचा: विषमांगी विशेषताओं और संरचना को निर्बाध रूप से एकीकृत करना, सूचना हानि से बचना

3. प्रयोग पूर्णता (★★★★★)

डेटासेट विविधता: 15 डेटासेट श्रेणीबद्ध/संख्यात्मक/विषमांगी विशेषताओं को कवर करते हैं
आधारभूत व्यापकता: 16 मजबूत आधारभूत (9 ग्राफ कर्नेल + 7 GNN)
विलोपन पूर्णता: प्रत्येक घटक के योगदान का व्यवस्थित विश्लेषण
मजबूती सत्यापन: शोर व्यवधान प्रयोग
दृश्य विश्लेषण: केस अध्ययन व्याख्या क्षमता को बढ़ाते हैं

4. लेखन स्पष्टता (★★★★☆)

विधि का क्रमिक विवरण
विस्तृत गणितीय व्युत्पत्ति और प्रमाण (परिशिष्ट)
समझ को सहायता देने के लिए समृद्ध चार्ट
छोटी खामी: कुछ प्रतीक पहली बार उपयोग से पहले परिभाषित नहीं हैं

5. व्यावहारिक मूल्य (★★★★☆)

कोड कार्यान्वयन अपेक्षाकृत सरल (मौजूदा पुस्तकालयों पर आधारित)
रन समय स्वीकार्य सीमा में
कई व्यावहारिक क्षेत्रों (रसायन, जीव विज्ञान, सामाजिक नेटवर्क) में लागू

कमियां

1. स्केलेबिलिटी सीमा (★★★☆☆)

हालांकि मध्यम पैमाने पर ग्राफ पर अच्छा प्रदर्शन, लेकिन लाखों नोड्स स्तर के ग्राफ पर प्रयोज्यता सत्यापित नहीं
कर्नेल मैट्रिक्स भंडारण $O(N^2)$ बड़े डेटासेट पर बाधा बन सकता है
सुझाव: अनुमानित एल्गोरिदम या वितरित कार्यान्वयन प्रदान करना

2. प्रयोग सेटअप विवरण (★★★☆☆)

कुछ आधारभूत के हाइपरपैरामीटर चयन विस्तार से नहीं बताए गए
GNN प्रशिक्षण epoch कम (अधिकतम 100), पूर्ण अभिसरण नहीं हो सकता
सांख्यिकीय महत्व परीक्षण की कमी (जैसे t-test)

3. तुलना विश्लेषण गहराई (★★★☆☆)

WWL जैसी वितरण विधियों के साथ सैद्धांतिक तुलना पर्याप्त नहीं
सकारात्मक निश्चितता गारंटी व्यावहारिक रूप से क्यों महत्वपूर्ण है? विफलता केस विश्लेषण की कमी
सुझाव: गैर-सकारात्मक निश्चित कर्नेल के कारण SVM विफलता के उदाहरण दिखाना

4. सामान्यीकरण क्षमता चर्चा (★★★☆☆)

सिंथेटिक डेटासेट पर प्रदर्शन अलग से विश्लेषण नहीं
क्रॉस-डोमेन सामान्यीकरण क्षमता (जैसे रसायन से सामाजिक नेटवर्क) मूल्यांकन नहीं
छोटे नमूने सीखने परिदृश्य अन्वेषित नहीं

5. कम्प्यूटेशनल अनुकूलन स्पेस (★★★☆☆)

कर्नेल मैट्रिक्स गणना की समानांतरकरण रणनीति पर चर्चा नहीं
GPU त्वरण की क्षमता पूरी तरह से उपयोग नहीं
प्रूनिंग रणनीति के विशिष्ट कार्यान्वयन विवरण अपर्याप्त

प्रभाव मूल्यांकन

क्षेत्र में योगदान (★★★★★)

सैद्धांतिक योगदान: ग्राफ कर्नेल की सकारात्मक निश्चितता के लिए नया प्रतिमान
विधि योगदान: विषमांगी विशेषता मॉडलिंग का एकीकृत समाधान
अनुभवजन्य योगदान: कई बेंचमार्क पर नया SOTA स्थापित करना

व्यावहारिक मूल्य (★★★★☆)

रासायनिक सूचना विज्ञान: आणविक गुण भविष्यवाणी के लिए प्रभावी उपकरण
जैव सूचना विज्ञान: प्रोटीन कार्य वर्गीकरण
सीमा: कर्नेल विधि पृष्ठभूमि ज्ञान की आवश्यकता

पुनरुत्पादनीयता (★★★★☆)

लाभ:
- विधि विवरण विस्तृत
- गणितीय सूत्र संपूर्ण
- डेटासेट सार्वजनिक रूप से उपलब्ध
कमी:
- कोड खुला स्रोत नहीं (प्रकाशन तक)
- कुछ कार्यान्वयन विवरण (जैसे प्रूनिंग थ्रेशोल्ड) स्पष्ट नहीं

प्रेरणा (★★★★★)

अनुवर्ती कार्य दिशाएं:
- कर्नेल विधियों और गहन सीखने का संलयन
- गतिशील और समय-श्रृंखला ग्राफ का विस्तार
- अन्य क्षेत्रों में अनुप्रयोग (जैसे सिफारिश प्रणाली)

प्रयोज्य परिदृश्य

दृढ़ता से अनुशंसित परिदृश्य

छोटे नमूने ग्राफ वर्गीकरण: प्रशिक्षण डेटा सीमित होने पर, कर्नेल विधियां GNN से अधिक स्थिर
विषमांगी विशेषता ग्राफ: एक साथ संख्यात्मक और श्रेणीबद्ध विशेषताएं
उच्च व्याख्या क्षमता आवश्यकता: मॉडल निर्णय आधार को समझने की आवश्यकता
सैद्धांतिक गारंटी आवश्यकता: सुरक्षा-महत्वपूर्ण अनुप्रयोग जैसे

प्रयोज्य परिदृश्य

मध्यम पैमाने पर ग्राफ: नोड्स <10,000
स्थिर ग्राफ: संरचना और विशेषताएं समय के साथ नहीं बदलती
पर्यवेक्षित सीखना: लेबल डेटा उपलब्ध

अनुशंसित नहीं परिदृश्य

अति-बड़े पैमाने पर ग्राफ: लाखों नोड्स, कम्प्यूटेशनल लागत बहुत अधिक
विशेषता-रहित ग्राफ: शुद्ध संरचना जानकारी, WL कर्नेल आदि विधियां सरल
वास्तविक समय भविष्यवाणी: कर्नेल मैट्रिक्स गणना विलंब अधिक
अनुपर्यवेक्षित सीखना: विधि पर्यवेक्षित वर्गीकरण के लिए डिजाइन की गई

व्यापक स्कोरिंग

आयाम	स्कोर	विवरण
नवाचार	9/10	विधि डिजाइन नया, सिद्धांत कठोर
कठोरता	9/10	संपूर्ण प्रमाण, प्रयोग व्यापक
व्यावहारिकता	7/10	प्रयोज्य परिदृश्य स्पष्ट, लेकिन स्केलेबिलिटी सीमित
लेखन गुणवत्ता	8/10	संरचना स्पष्ट, विवरण समृद्ध
प्रभाव	8/10	ग्राफ कर्नेल क्षेत्र में महत्वपूर्ण योगदान
कुल स्कोर	8.2/10	उत्कृष्ट पेपर

संदर्भ (चयनित)

Haussler (1999): Convolution kernels on discrete structures - R-convolution सिद्धांत आधार
Berg et al. (1984): Harmonic Analysis on Semigroups - CND फ़ंक्शन और सकारात्मक निश्चित कर्नेल के शास्त्रीय परिणाम
Gower (1971): A general coefficient of similarity - गोवर समानता गुणांक मूल पेपर
Leman & Weisfeiler (1968): WL एल्गोरिदम मूल पेपर
Togninalli et al. (2019): WWL kernel - मुख्य प्रतिस्पर्धी विधि
Morris et al. (2023): Weisfeiler and Leman go machine learning - WL विधि सर्वेक्षण

सारांश

NASK एक सैद्धांतिक और व्यावहारिक संयोजन उत्कृष्ट ग्राफ कर्नेल विधि पेपर है। इसका मूल योगदान कठोर गणितीय प्रमाण के माध्यम से, विषमांगी विशेषताओं और संरचना जानकारी दोनों को एक साथ संभालने वाली पहली सकारात्मक निश्चित ग्राफ कर्नेल प्रदान करना है। प्रयोग परिणाम विश्वास दिलाते हैं, कई बेंचमार्क पर नया SOTA स्थापित करते हैं। हालांकि अति-बड़े पैमाने पर ग्राफ पर स्केलेबिलिटी में सुधार की गुंजाइश है, लेकिन यह विधि ग्राफ कर्नेल अनुसंधान के लिए नया प्रतिमान प्रदान करती है, विशेष रूप से सैद्धांतिक गारंटी और व्याख्या क्षमता की आवश्यकता वाले अनुप्रयोग परिदृश्यों में महत्वपूर्ण मूल्य रखती है। ग्राफ मशीन लर्निंग, कर्नेल विधियों और संरचित डेटा विश्लेषण में काम करने वाले शोधकर्ताओं को पढ़ने के लिए अनुशंसित।